Разработка программно-математического обеспечения корреляционного совмещения изображений с использованием быстрого преобразования Фурье
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ющих коэффициентов:
,(3.23)
,(3.24)
,(3.25)
.(3.26)
На 2-м этапе на основе значений () вычисляются коэффициенты () 4-точечного БПФ:
,
,
,
.
Одним из главных пунктов в алгоритме быстрого преобразования Фурье является метод вычисления "бабочкой". Еще один важный момент заключается в последовательных разбиениях ряда значений сигнала на две группы и перестановке значений сигнала таким образом, чтобы в последующем перейти к методу вычисления "бабочкой". Способ перестановки значений функции называется техникой сортировки. Техника сортировки основана на перестановке разрядов. Ряд значений функции расстанавливается в порядке , , , (в случае БПФ из 4-х членов) и в порядке , , , , , , , (в случае БПФ из 8-и членов). Таким образом, значение индекса получается из исходного перестановкой старших и младших разрядов. Это правило является универсальным для любого числа членов ряда.
Например, двумерное 32x32-точечное БПФ вычисляется путем вычисления коэффициентов для каждой строки изображения за счет последующего их умножения на величину :
,(3.27)
,(3.28)
3.4 Определение числа коэффициентов, необходимых для анализа изображения
Для анализа изображений по их Фурье-образам необходимо определить достаточное для анализа количество коэффициентов. Это позволит сократить время анализа. Ниже приводятся примеры описания простых изображений посредством коэффициентов ряда Фурье.
1)Описание одиночной точки на черном фоне
Воспользовавшись зависимостями (3.17) и (3.18) можно получить следующие выражения: ,(3.29)
,(3.30)
,(3.31)
,(3.32)
.(3.33)
Из совокупности зависимостей (3.29) - (3.33) можно выразить координаты x и y, описывающие одиночную точку на черном фоне:
,(3.34)
.(3.35)
Как видно из зависимостей (3.34) - (3.35), одиночная точка на черном фоне описывается 3-мя коэффициентами ряда Фурье. Из этого следует, что для уменьшения числа коэффициентов ряда Фурье, необходимых для анализа изображения, следует проводить контрастирование исходного изображения.
2)Описание линии по горизонтали, состоящей из двух точек, на черном фоне
Такое изображение согласно (3.5) и (3.6) имеет следующее описание:
,(3.36)
,(3.37)
(3.38)
,(3.39)
,(3.40)
где и - координаты точек линии.
Из выражений (3.24) - (3.28) следует, что координаты искомого объекта могут быть найдены как:
,(3.41)
.(3.42)
Как видно из совокупности (3.41) - (3.42) линия по горизонтали, состоящая из двух точек, описывается четырьмя коэффициентами ряда Фурье.
3.5 Восстановление изображений на основе Фурье-образов
Для проверки правильности нахождения Фурье-образа необходимо осуществить восстановление исходного изображения путем обратного преобразования Фурье, которое осуществляется согласно следующей зависимости:
(3.43)
3.6 Нахождение корреляционной функции радиолокационного и моделируемого изображений на основе их Фурье образов
Корреляционный анализ радиолокационного и моделируемого изображений целесообразно осуществлять на основе их Фурье-образов. Так корреляционная функция Фурье-образов радиолокационного и моделируемого изображений примет вид:
,(3.44)
,(3.45)
где - корреляционная функция радиолокационного и моделируемого изображений по коэффициенту ряда Фурье (т.е. по косинусному ряду);
- корреляционная функция радиолокационного и моделируемого изображений по коэффициенту ряда Фурье (т.е. по синусному ряду);
и - коэффициенты ряда Фурье для радиолокационного изображения;
и - коэффициенты ряда Фурье для моделируемого изображения;
- размер сравниваемых изображений.
Алгоритм нахождения корреляционной функции при совмещении радиолокационного и моделируемого изображений, основанный на вычислении зависимостей (3.44) и (3.45) представлен на рисунке 3.5.
Рисунок 3.5 - Алгоритм нахождения корреляционной функции при совмещении радиолокационного и моделируемого изображений
3.7 Алгоритмы быстрого преобразования Фурье FFT (fast Fourier transform). Принцип построения
Рассмотрим выражение для дискретного преобразования Фурье:
(3.46)
ДПФ N отсчетам сигнала s(n), n=0..N-1(в общем случае комплексным) ставит в соответствие N комплексных отсчетов спектра S(k), k=0..N-1, причем для вычисления одного спектрального отсчета требуется N операций комплексного умножения и сложения. Таким образом вычислительная сложность алгоритма ДПФ составляет N2 комплексных умножений и сложений. При этом можно заметить что если одно ДПФ на N точек (отсчетов) заменить вычислением двух ДПФ по N/2 точек, то это приведет к уменьшению количества операций в 2 раза. Замена N-точечного ДПФ двумя N/2 точечными представлено на рисунке 3.6.
Рисунок 3.5 - Замена N-точечного ДПФ двумя N/2-точечными ДПФ
При этом каждое из N/2 - точечных ДПФ также можно вычислить путем замены N/2 - точечного ДПФ на два N/4-точечных. В этом случае количество вычислительных операций равно 4*(N2/16)= N2/4. Таким образом, можно продолжать разбиение исходной последовательности до тех пор, пока возможно деление последовательности на две. Для N=8 (L=3) такое разбиение представлено на рисунке 3.6.
Рисунок 3.6 - Разбиение и объединение последовательностей при N = 8
Каждое разбиение делит последовательность на две половинной длительности (красную и синюю), а каждое объединение собирает из