Исследование быстрого преобразования Фурье

Размещено на http://www.allbest.ru/

Исследование быстрого преобразования Фурье

быстрый преобразование фурье изображение

Быстрым преобразованием Фурье (БПФ) называется частный случай ДПФ с теми же формулами для определения коэффициентов разложения

, (1)

только число дискретных отсчётов должно быть

N=2n, ,

т.е. N=4,8,16,32,64,...

Это условие не ограничивает возможности использования БПФ, так как N всегда выбирается достаточно большим, чтобы выдержать условие дискретизации, то есть N2BL, где B - полоса частот сигнала x(t); L - длительность сигнала. Возможно использование БПФ и для N2n с помощью специальных приемов.

Рис. 1

Можно воспользоваться универсальной схемой вычисления значений каждой последующей итерации по двум предшествующим значениям, как это показано на рис.1, где использованы обозначения

C=A+WSB,

D=A-WSB,

а коэффициенты WS вычисляются Рис.1 по формуле

(2)

В приведенном графе вычисления БПФ коэффициенты не делятся на число отсчетов исходной последовательности N.

Вычисление обратного быстрого преобразования Фурье (ОБПФ) осуществляется по аналогичной методике с использованием такого же графа, при этом значения результатов делятся на N.

На рис.2 изображен восьмиточечный алгоритм БПФ.

Рис. 2

На каждом этапе вычисления БПФ необходимо выполнять не более N/2 комплексных умножений. Поскольку общее количество этапов равно log2N, то число комплексных умножений, необходимых для нахождения N-точечного ДПФ приблизительно равно N/2log2N. На всех этапах БПФ используется коэффициенты Wk. Для вычисления этих коэффициентов можно использовать формулу:

Wk = Wk-1 Wk. (3)

Одномерное прямое БПФ.

Рассмотрим последовательность из действительных чисел (N=4):

Таблица 1. Исходные данные

Входная последовательность f(n), n=0:N-1
		f(0)=21
		f(1)=19
		f(2)=18
		f(3)=-8

Таблица 2. Базовая операция алгоритма БПФ

Базовая операция алгоритма БПФ
A	C	C=A+W^k*B
B	D	D=A-W^k*B
	Множитель W
W=exp(-i*2П/N),
где N-длина преобразуемой последоват.
W-комплексное число, поэтому его можно представить в тригоном. Форме
W=cos(2П/N)-i*sin(2П/N)
W^k=exp(1i*k*2П/N)=cos(k*2П/N)-i*sin(k*2П/N)

Таблица 3. Граф вычисления БПФ

Граф вычисления БПФ для 4 отсчетов имеет вид:
f(0)	w^0	P(0)		F(0)
			w^0
f(1)		P(1)		F(1)
			w^1
f(2)	w^0	P(2)		F(2)
f(3)		P(3)		F(3)

Таблица 4. Вычисление первой ступени преобразования.

Вычисляется первая ступень преобразования
Рассчитайте и введите значение P(2)
f(0)	w^0	P(0)		f(0)=21,00+i 0,00
f(2)		P(1)		f(1)=19,00+i 0,00
f(1)	w^0	P(2)		f(2)=18,00+i 0,00
f(3)		P(3)		f(3)=-8,00+i 0,00

Значение P(2) равно

f(1)+f(3)=11,00+i 0.00.

Указываем данное значение.

Таблица 5. Вычисление второй ступени преобразования.

Вычисляется вторая ступень преобразования
Рассчитайте и введите значение F(2)
P(0)	w^0	F(0)	P(0)=39,00+i 0,00
P(1)		F(1)	P(1)=3,00+i 0,00
	w^1
P(2)		F(2)	P(2)=11,00+i 0,00
P(3)		F(3)	P(3)=27,00+i 0,00

Значение F(2) равно

P(0)-P(2)=28,00+i 0.00.

Указываем данное значение.

Таблица 6. Результат вычисления прямого БПФ.

Результат вычисления прямого БПФ:
f(0)=21,00+i 0,00	F(0)=50,00+i 0,00
f(1)=19,00+i 0,00	F(1)=3,00-i 27,00
f(2)=18,00+i 0,00	F(2)=28,00+i 0,00
f(3)=-8,00+i 0,00	F(3)=3,00+i 27,00

Рассмотрим последовательность из комплексных чисел (N=4):

Таблица 7. Исходные данные

Входная последовательность f(n), n=0:N-1
f(0)=-15+i 12
f(1)=1-i 17
f(2)=-14-i 17
f(3)=-18-i 15

Таблица 8. Вычисление первой ступени преобразования

Вычисляется первая ступень преобразования
Рассчитайте и введите значение P(0)
f(0)	w^0	P(0)	f(0)=-15+i 12,00
f(2)		P(1)	f(1)=1-i 17,00
f(1)	w^0	P(2)	f(2)=-14-i 17,00
f(3)		P(3)	f(3)=-18-i 15,00

Значение P(2) равно

f(2)+f(0)=-29,00-i 5.00.

Указываем данное значение.

Таблица 9. Вычисление второй ступени преобразования

Вычисляется вторая ступень преобразования
Рассчитайте и введите значение F(2)
P(0)	w^0	F(0)	P(0)=-29,00-i 5,00
P(1)		F(1)	P(1)=-1,00+i 29,00
	w^1
P(2)		F(2)	P(2)=-17,00-i 42,00
P(3)		F(3)	P(3)=19,00+i 8,00

Значение F(2) равно

P(0)-P(2)=-12,00+i 37.00.

Указываем данное значение.

Таблица 10. Результат вычисления прямого БПФ.

Результат вычисления прямого БПФ:
f(0)=-15+i 12,00	F(0)=-46,00-i 47,00
f(1)=1-i 17,00	F(1)=7,00+i 10,00
f(2)=-14-i 17,00	F(2)=-12,00+i 37,00
f(3)=-18-i 15,00	F(3)=-9,00+i 48,00

Рассмотрим вычисление одномерного обратного ДПФ.

Таблица 11. Исходные данные

Входная последовательность f(n), n=0:N-1
f(0)=3
f(1)=-5
f(2)=-14
f(3)=3

Таблица 12. Результат вычисления прямого БПФ.

Результат вычисления прямого БПФ:
f(0)=3,00+i 0,00	F(0)=-13,00+i 0,00
f(1)=-5,00+i 0,00	F(1)=17,00-i 27,00
f(2)=-14,00+i 0,00	F(2)=-9,00+i 0,00
f(3)=3,00+i 0,00	F(3)=17,00+i 27,00

Вычисление обратного БПФ с помощью БПФ производится по следующему алгоритму:

Определяется комплексно сопряженные значения F”(n),n=0:N-1 по исходной ОБПФ последовательности F(n),n=0:N-1

Вычисляется БПФ, входной последовательностию которого является F”(n), n=0:N-1.

Находится комплексно сопряженные значения результатов БПФ, которые делятся на N.

Таблица 13. Исходная последовательность для вычисления ОБПФ

Входная последовательность F(n), n=0:N-1
F(0)=-13,00+i 0,00
F(1)=17,00+i 8,00
F(2)=-9,00+i 0,00
F(3)=17,00-i 8,00

Таблица 14. Вычисление первой ступени преобразования.

Вычисляется первая ступень преобразования
Рассчитайте и введите значение P(1)
F(0)	w^0	P(0)	F(0)=-13,00+i 0,00
F(2)		P(1)	F(1)=17,00+i 8,00
F(1)	w^0	P(2)	F(2)=-9,00+i 0,00
F(3)		P(3)	F(3)=17,00+i 8,00

Значение P(1) равно

f(0)-f(2)= -4,00+i 0.00.

Указываем данное значение.

Таблица 15. Вычисление второй ступени преобразования

Рассчитайте и введите значение f”(2)
P(0)	w^0	f”(0)	P(0)=-22,00+i 0,00
P(1)		f”(1)	P(1)=-4,00+i 0,00
	w^1
P(2)		f”(2)	P(2)=34,00+i 0,00
P(3)		f”(3)	P(3)=-0,00-i 16,00

Значение f”(2) равно

P(0)-P(2)=--56,00+i 0.00.

Указываем данное значение.

Таблица 16. Результат вычисления прямого БПФ

Результат вычисления прямого БПФ:
F”(0)=-13,00i 0,00	f“(0)=12,00+i 0,00
F”(1)=17,00i 8,00	f”(1)=-20,00-i 0,00
F”(2)=-9,00i 0,00	f”(2)=-56,00+i 0,00
F”(3)=17,00i 8,00	f”(3)=12,00+i 0,00

Таблица 17. Результат вычисления обратного ДПФ.

Результат вычисления обратного ДПФ:
F(0)=-13,00+i 0,00	f(0)=3,00+i 0,00
F(1)=17,00+i 8,00	f(1)=-5,00-i 0,00
F(2)=-9,00+i 0,00	f(2)=-14,00+i 0,00
F(3)=17,00+i 8,00	f(3)=3,00-i 0,00

Сложение, вычитание и умножение многозональных изображений

Спектральный анализ - это один из методов обработки сигналов, который позволяет охарактеризовать частотный состав измеряемого сигнала. Преобразование Фурье является математической основой, которая связывает временной или пространственный сигнал (или же некоторую модель этого сигнала) с его представлением в частотной области.

Важной стороной спектрального анализа является вычисление пространственночастотных спектров изображений, получаемых на основе преобразования Фурье. Наиболее важными составляющими спектра изображений являются амплитудный и фазовый спектры. В амплитудном спектре заключена информация о яркости и резкости изображения. Информация о наличии положения световой границы, в основном, заключена в фазовом спектре.

Одним из важных методов анализа многослойной (многозональной) информации является послойный пространственный спектральный анализ полутоновых изображений (сюжетов). При этом пространственный спектральный анализ позволяет получать не только отдельные спектральные характеристики наблюдаемых объектов земной поверхности, но и учитывать эти характеристики при решении задач распознавания. В частности такой спектральный анализ дает возможность учесть и оценить, как автокорреляцию отдельных слоев, так и их взаимную корреляцию.

Значительная часть задач, возникающих при обработке изображений, связана с повышением их качества, апостериорным устранением дефектов аппаратуры, увеличением разрешения, словом, всем тем, что в совокупности называется восстановлением изображений. В целом восстановление изображений - это научное направление по разработке методов и средств компенсации искажений, вносимых в изображения в процессе их формирования различными средствами.

В спектральном анализе важную роль играют линейные операции (сложение, вычитание, умножение) над изображениями, амплитудными и фазовыми спектрами. Операции сложения, вычитания, умножения, выполняемые с изображениями отдельных зон, а также с амплитуднопространственными и фазопространственными спектрами позволит реализовать сравнение яркостных и пространственночастотных отсчетов изображений, вычисляя различия и оценивать функциональные преобразования изображений, отдельных фрагментов или сюжетов.

Исходное цветовое изображение и его R-, G-, B- спектры представлены на рис. 3.

Рис. 3. Исходное изображение и его R-, G-, B- спектры.

В результате разложения получили три спектра цветного изображения: самое темное из них получилось изображение G-спектра.

Смесь 100% всех трех цветов дает белый, N%(0<N<100) дает оттенки серого, а смесь 0% всех трех цветов дает черный.

В любом изображении значение пиксела изменяется от 0 до 255. Значение пикселов исходного цветного изображения имеет вид:

P=a*R+b*G+c*B, (4)

Где a, b, c - коэффициенты, сумма которых должна не превышать 1.

R, G, B - цвета, величина которых всегда равно 255.

При разложении исходного изображения на спектральные составляющие формула (4) будет иметь следующий вид:

P=a*R+0*G+0*B

- для R-спектра,

P=0*R+b*G+0*B

- для G-спектра,

P=0*R+0*G+c*B

- для B-спекстра.

Сложение

В оттенках серого суммы различных спектров изображения будут выглядеть следующим образом.

Рис. 4. Суммы различных спектров изображений

При сложении двух спектров изображений величина пиксела в полученном изображении складывается из значений пикселов спектров. При выходе за пределы диапазона нами применяется специальная формула пересчета:

Pновое=(P1спектра + P2спектра)-255 (5).



Рис. 5. Сложение красного спектра с различными константами

Рис. 6. Сложение зеленого спектра с различными константами

Рис. 7. Сложение синего спектра с различными константами

С прибавлением константы к каждому пикселу изображения, его значение изменяется на эту величину. Т.к. один пиксел (Р) имеет максимальное значение, равное 255, при превышении этого значения, величина пиксела будет равной

Pновое=(Pстарое + const)-255 (6).

Вычитание

В оттенках серого разности различных спектров изображения будут выглядеть следующим образом.

Рис. 8. Разности различных спектров изображения

При вычитании двух спектров изображения величина пиксела в полученном изображении - разность значений пикселов спектров. При входе за пределы диапазона нами применяется специальная формула пересчета:

Pновое=(P1спектра - P2спектра)+255 (7).



Рис. 9. Разности красной спектральной составляющей с различными константами

Рис. 10. Разности зеленой спектральной составляющей с различными константами

Рис. 11. Разности синей спектральной составляющей с различными константами

С вычитанием константы из каждого пиксела изображения его значение изменяется на эту величину. Т.к. один пиксел (Р) не может принимать отрицательного значения, при отрицательной разности, величина пиксела будет равна:

Pновое=(Pстарое - const)+255 (8).

Умножение

Умножение двух спектральных составляющих изображения представлены на рисунке.

Рис. 12. Умножение спектральных составляющих изображений

Рис. 13. Умножение красной спектральной составляющей с различными константами

Рис. 13. Умножение зеленой спектральной составляющей с различными константами

Рис. 14. Умножение синей спектральной составляющей с различными константами

Зашумление, автокорреляция, взаимная корреляция, свертка и восстановление многозональных и псевдозональных видео космических изображений

Видеокосмические изображения, полученные с искусственных спутников Земли, стали широко доступными, и это дало колоссальный толчок исследованиям в области обработки изображений. Громадный объем видеоинформации вместе с естественным желанием извлечь из нее как можно больше сведений ведут к необходимости автоматизации процессов ее обработки.

Спектральный анализ дает возможность учесть и оценить, как автокорреляцию отдельных слоев изображения, так и их взаимную корреляцию.

Автокорреляционная функция по пространству изображений, как вторичная функция спектральных разложений, позволяет определить интервал корреляции, для разных уровней отсчета и также дает дополнительную информацию распознающих признаков.

Функцию автокорреляции для j-гo изображения обычно определяют следующим образом [13]:

(9)

- площадь прямоугольника, в который вписано изображение.

и - смещения реализации j-гo изображения LC (x+,y+,j) относительно реализации этого же изображения LC (x,y,j) по осям х и у соответственно.

Взаимно корреляционная функция двух дискретных последовательностей действительных чисел {X(m)} и {Y(m)}, при которых X(m)Cx(k), Y(m)Cy(k),определяется соотношением [13,22]

(10)

Для ее вычисления используются коэффициенты дискретного преобразования Фурье в виде

(11)

где - коэффициент комплексной сопряженности .

Теорема корреляции дает формулу

(12)

Вычисление пространственной межзональной взаимно корреляционной функции позволяет оценить степень зависимости между спектральными зонами, а для отдельных сюжетов характеризовать их степень коррелированности.

При наблюдении видеокосмических изображений возникают такие явления, как размытие и смазывание изображения, вызванные несовершенством оптической системы, и другие искажения. Поэтому при проведении спектрального анализа также осуществляется анализ влияния шумовых импульсных помех на спектральный состав изображений отдельных зон. В этой операции предусматривается введение в исследовательских целях импульсных помех с различным уровнем шума и различной степенью зашумленности.

Восстановление изображений предназначено для использования в качестве предварительной обработки при распознавания образов.

Существуют линейные методы для восстановления изображения. Линейные методы применяются для восстановления изображения по линейным моделям искажения и сводятся к нахождению некоторого линейного оператора, действующего на искаженное изображение

где - оценка входного изображения; R - линейный оператор;

G - искаженное изображение.

Оператор Ra зависит от параметра б, и называется регуляризующим. Регуляризация решения состоит в построении семейства обратных операторов, зависящих от числового оператора , называемого параметром регуляризации. Каждый оператор семейства дает решение корректной задачи, причем при согласованном стремлении к нулю параметра и ошибки исходных данных решение корректной задачи стремится к истинному решению соответствующей некорректной задачи.

Устойчивое решение задачи линейного восстановления достигается на основе тихоновской регуляризации, которая в матричном виде может быть представлена в следующем виде:

, (13)

где - оценка восстанавливаемого изображения в пространственно-частотном представлении;

H = H (w)

- частотная характеристика искажающей системы; G (w) - пространственночастотный спектр искаженного изображения; - параметр регуляризации; Q - квадратная матрица, играющая роль стабилизатора задачи.

Основной положительной чертой линейных методов является простота их реализации, а также возможность их использования в широких масштабах с относительно малыми затратами времени и усилий.

Линейные методы имеют принципиальные недостатки. Во-первых, линейные методы восстановления не учитывают важного для изображений ограничения на неотрицательность решения.

Во-вторых, линейные методы принципиально ограничены по полосе частот. Т.е. линейные методы не могут восстановить информацию, лежащую за пределами частоты среза системы формирования.

Использование линейных методов оправдано в случае не слишком сильных искажений и зашумленности изображений.

Порог шума - 5, Степень зашумленности (%) - 8	Порог шума - 5, Степень зашумленности (%) - 27	Порог шума - 5, Степень зашумленности (%) - 52
Порог шума - 12, Степень зашумленности (%) - 8	Порог шума - 12, Степень зашумленности (%) - 27	Порог шума - 12, Степень зашумленности (%) - 52

Рис. 15. Зашумленность R-спектра

Рис. 16. Зашумленность G-спектра

Порог шума - 5, Степень зашумленности (%) - 8	Порог шума - 5, Степень зашумленности (%) - 27	Порог шума - 5, Степень зашумленности (%) - 52
Порог шума - 12, Степень зашумленности (%) - 8	Порог шума - 12, Степень зашумленности (%) - 27	Порог шума - 12, Степень зашумленности (%) - 52

Порог шума - 5, Степень зашумленности (%) - 8	Порог шума - 5, Степень зашумленности (%) - 27	Порог шума - 5, Степень зашумленности (%) - 52
Порог шума - 12, Степень зашумленности (%) - 8	Порог шума - 12, Степень зашумленности (%) - 27	Порог шума - 12, Степень зашумленности (%) - 52

Рис. 17. Зашумленность B-спектра

Увеличение степени зашумленности приводит к тому, что интенсивность влияния шумов на единицу изображения возрастает.

Теперь рассмотрим автокорреляцию. Для описания статических связей между элементами изображения часто используют функцию автокорреляции.

Рис. 18. Автокоррекляция рабочего изображения

Рис. 19. Взаимная автокорреляция

Рис. 20. Свертка

Основание гауссоиды - 7, Параметр расфокусировки - 1	Основание гауссоиды - 7, Параметр расфокусировки - 2	Основание гауссоиды - 7, Параметр расфокусировки - 5
Основание гауссоиды - 15, Параметр расфокусировки - 1	Основание гауссоиды - 32, Параметр расфокусировки - 1	Основание гауссоиды - 32, Параметр расфокусировки - 5
Основание гауссоиды - 7, Параметр расфокусировки - 32	Основание гауссоиды - 15, Параметр расфокусировки - 32	Основание гауссоиды - 32, Параметр расфокусировки - 32

Рис. 21. Фильтрация

Инверсная фильтрация	Тихоновская регуляризация	Сглаживание шума
Компенсация искажений	Среднегеометрическая фильтрация	Эволюционная фильтрация

Вычисление, перестановка спектров, восстановление по спектрам и сечение многозональных и псевдозональных видео космических изображений

Важной стороной спектрального анализа является вычисление пространственночастотных спектров изображений, получаемых в результате преобразования Фурье. Наиболее важными составляющими спектра изображений являются амплитудный и фазовый спектры. Амплитудный спектр, в общем, не содержит информации о наличии и положении световой границы, но в нем заключена информация о яркости (резкости) изображения. Информация о наличии положения световой границы, в основном, заключена в фазовом спектре. Изображение может быть подвергнуто значительным линейным и нелинейным искажениям, но если искажения фазового спектра при этом будут невелики, так что они не вызовут исчезновения или появления новых световых границ, изображение будет легко узнаваться. К таким искажениям относятся интегрирование (расфокусировка), дифференцирование (подчеркивание границ), поэлементное преобразование. Если же в результате преобразования существенно искажается фазовый спектр изображения, то может произойти полная потеря узнаваемости изображаемого объекта.

При передаче изображений особое влияние следует уделять передачи фазового спектра. В телевидении к этому выводу пришли давно, чисто опытным путем, заметив, что амплитудно-частотные и амплитудные (нелинейные) искажения менее заметны на изображении, чем фазочастотные.

Амплитудный спектр легко определить с помощью следующей формулы:

(14)

Для заданной временной последовательности X(m), m=0,1,…,N-1 фазовый спектр определяется из следующего выражения:

(15)

где Rx(k) и Ix(k) - соответственно действительная и мнимая части спектра Сx(k).

Фундаментальным свойством фазового спектра [2, 22] является его инвариантность к умножению {X(m)} на постоянную величину. Фазовый спектр, определенный выражением (15) представляет собой нечеткую относительно точки

k = N/2

функцию.

B	G	R

Рис. 22. Амплитудные спектры спектральных зон исходного изображения

B	G	R

Рис. 23. Фазовые спектры спектральных зон изображения

B	G	R

Рис. 24. lg действительной части спектральных зон изображения

Рис. 25. lg модуля части спектральных зон изображения

B	G	R

Примечание: для каждой комбинации спектров в системе существует свой индивидуальный файл поэтому если он уже вычислен то сразу выводится на экран иначе приходится ждать окончания вычисления.

Рис. 26. Сечение 100 строки восстановленного изображения

Список использованных источников

1. Исследование быстрого преобразования Фурье / Рязан. Гос. Радиотехн. акад.; В.Е.Борзых, Рязань, 1992, 8с

2. Методические указания к лабораторным работам по дисциплине «Информационные системы экспериментальных исследований»

3. Формирование и обработка изображений в информационно-исследовательских системах: Учебное пособие / Е.М. Дондик: Рязан. гос. радиотехн. акад.; Рязань, 40с.

Размещено на Allbest.ru