Разработка программно-математического обеспечения корреляционного совмещения изображений с использованием быстрого преобразования Фурье
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
p>
Выделим в (3.2) элементы, независимые от t, и обозначим их как Re и Im:
x = Re cos(2?t/T) - Im sin(2?t / T) (3.3) = A cos ?, Im = A sin ?
По величинам Re и Im можно однозначно восстановить амплитуду и фазу исходной гармоники:
и (3.4)
Обратное преобразование Фурье будет выглядеть следующим образом:
(3.5)
Раскладывая каждое комплексное Xk на мнимую и действительную составляющие Xk = Rek + j Imk; разкладывая экспоненту по формуле Эйлера на синус и косинус действительного аргумента; перемножая полученные выражения; внеся 1/N под знак суммы и перегруппировав элементы в две суммы, получаем:
(3.6)
Рассмотрим следующую ситуацию. Пусть у нас есть звуковое или какое-либо иное колебание в виде функции x = f(t). Пусть это колебание задано в виде графика для отрезка времени [0, T]. Для обработки средствами вычислительной техники необходимо выполнить дискретизацию. Отрезок делится на N-1 частей и сохраняются значения функции x0, x1, x2,..., xN для N точек на границах отрезков t0 = 0, t1 = T/N, t2 = 2T/N,..., tn =nT/N,..., tN = T.
Рисунок 3.4 - Дискретизация непрерывного сигнала
В результате прямого дискретного преобразования Фурье были получены N значений для Xk:
(3.7)
Если применить обратное дискретное преобразование Фурье, то получится исходная последовательность {x}. Исходная последовательность состояла из действительных чисел, а последовательность {X} в общем случае комплексная.
Вернемся к рассмотрению формулы (3.6). В левой части находится действительное число xn, а справа - две суммы, одна из которых помножена на мнимую единицу j. Сами же суммы состоят из действительных слагаемых. Отсюда следует, что вторая сумма равна нулю, если исходная последовательность {x} была действительной. Отбрасывая её, получаем:
(3.8)
Поскольку при дискретизации были выбраны tn = nT/N и xn = f(tn), то можно выполнить замену: n = tnN/T. В результате получим:
(3.9)
Сопоставляя эту формулу с формулами (3.1) и (3.3) для гармоники:
x = A cos(2?t/T + ?) = A cos(2??t + ?) = A cos(?t + ?) (3.1) = Re cos(2?t/T) - Im sin(2?t / T) (3.3)
Сумма (3.1.9) представляет собой сумму из N гармонических колебаний разной частоты, фазы и амплитуды:
(3.10)
Функцию
Gk(t) = Ak cos(2?tk/T + ?k) (3.11)
Будем называть k-й гармоникой.
Амплитуда, фаза, частота и период каждой из гармоник связаны с коэффициентами Xk формулами:
(3.12)
Физический смысл дискретного преобразования Фурье состоит в том, чтобы представить некоторый дискретный сигнал в виде суммы гармоник. Параметры каждой гармоники вычисляются прямым преобразованием, а сумма гармоник - обратным.
3.2 Использование двумерного дискретного преобразования Фурье для обработки изображений
Двумерное дискретное преобразование Фурье является преобразованием Фурье для последовательности конечной длины, являющееся само по себе также конечной последовательностью, а не непрерывной функцией, и соответствует равноудаленным по частоте выборкам преобразования Фурье-сигнала. Дискретное преобразование Фурье (ДПФ) играет центральную роль в разработке ряда алгоритмов обработки сигналов вследствие существования эффективных алгоритмов вычисления ДПФ.
Представление двумерной последовательности дискретным преобразованием Фурье имеет большое значение при дискретной обработке двумерных сигналов (фотографии, изображения и т.п.). Двумерное ДПФ может быть описано следующим образом:
,(3.13)
где - функция, описывающая исходное прямоугольное изображение, состоящее из N строк и M столбцов;
- Фурье-образ изображения ;
- мнимая единица;
, .
Зависимость (4.1) может быть представлена следующим образом:
,(3.14)
где , .
Число является комплексным, поэтому с учетом равенства зависимости (3.13) и (3.14) соответственно примут вид:
, (3.15)
(3.16)
Из выражения (3.15) можно выразить коэффициенты и , определяющие действительную и мнимую части числа :
,(3.17)
.(3.18)
3.3 Повышение быстродействия преобразования Фурье на основе быстрого двумерного преобразования Фурье
Использование алгоритма дискретного преобразования Фурье является не очень практичным вследствие больших затрат времени на его реализацию. Поэтому на практике используют алгоритмы быстрого преобразования Фурье (БПФ). В БПФ обычно число данных ограничено и выражено степенью с основанием 2 (2, 4, 8, 16, 32, 64, 128, тАж). Но, несмотря на это ограничение, БПФ всё равно используется благодаря практичности и высокой скорости вычислений.
БПФ - это алгоритм вычисления, который успешно использует свойства периодичности тригонометрических функций для того, чтобы избежать ненужных вычислений в дискретном преобразовании Фурье.
При вычислении ДПФ для значений необходимо умножить раз и сложить раз. Если невелико, как в приведенном примере, то объем вычислений тоже мал, но если , например, равно 1000, то число операций достигает 1000000, что крайне затрудняет аппаратную реализацию алгоритма.
Алгоритм вычисления БПФ называется методом вычисления "бабочкой". Так, для одномерной 4-точечной функции он выглядит следующим образом:
,(3.19)
,(3.20)
,(3.21)
,(3.22)
где - комплексный член дискретного ряда Фурье;
;
- число точек функции .
Вычисление совокупности зависимостей (3.19) - (3.21) осуществляется в 2 этапа. На 1-м этапе осуществляется нахождение следу