Разработка программно-математического обеспечения корреляционного совмещения изображений с использованием быстрого преобразования Фурье
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?вух последовательностей одну удвоенной длительности.
Алгоритмы БПФ, которые используют выборки длиной N=2L, называются алгоритмами БПФ по основанию 2. Данные алгоритмы получили наибольшее распространение, из-за того что в машинной арифметике N=2L является круглым числом. Далее мы будем рассматривать только алгоритмы по основанию 2.
Очевидно что делить последовательности на две можно по-разному, однако от этого зависит сможем ли мы при объединении получить неискаженный спектр сигнала и чего с точки зрения вычислительных затрат это будет нам стоить. Можно сказать, что эффективность алгоритма БПФ полностью зависит от способа разбиения и объединения последовательности, поскольку если не учитывать операции на разбиение-объединение, то для расчета спектра требуется N/2 раз посчитать ДПФ на 2 точки, в результате общее количество вычислительных операций составит 2*N, то есть количество операций линейно зависит от величины выборки.
Мы рассмотрим два способа разбиения - объединения: прореживание по времени и прореживание по частоте.
Перед рассмотрением способов разбиения - объединения требуется рассмотреть обратное дискретное преобразование Фурье (ОДПФ):
(3.47)
которое ставит в соответствие N комплексным отсчетам спектра S(k), k=0..N-1 N комплексных значений сигнала s(n), k=0..N-1.
Имея алгоритм вычисления БПФ, логично использовать его и для обратного преобразования. Для этого обратим внимание на то, что:
(3.48)
Другими словами комплексные экспоненты в выражении для прямого и обратного ДПФ являются комплексно-сопряженными (черта сверху означает комплексное сопряжение). Теперь рассмотрим два комплексных числа x=a+jb и y=c+jd.
Рассмотрим произведение x на комплексно-сопряженное y:
(3.49)
Теперь рассмотрим произведение комплексно-сопряженного на y:
(3.50)
Сравнивая (3.49) и (3.50) можно сделать вывод:. (3.51)
Применительно для выражения ОДПФ можно записать:
(3.52)
Таким образом, берется комплексно-сопряженный спектр выполняется прямое ДПФ, и результат подвергается комплексному сопряжению. Вычисление ОДПФ при использовании ДПФ приведено на рисунке 3.7.
Рисунок 3.7 - Вычисление обратного ДПФ через прямое
Если вместо ДПФ использовать БПФ, то получим обратное быстрое преобразование Фурье (ОБПФ). При этом для выполнения комплексного сопряжения необходимо лишь поменять знак перед мнимой частью спектра до вызова функции БПФ и результата после БПФ.
3.8 БПФ по основанию 2 с прореживанием по времени
Ранее были приведены выражения для ДПФ и схема процедуры разбиения-объединения. Они потребуются нам для дальнейшего изложения, поэтому приведем их без пояснений.
Выражение для ДПФ имеет вид:
(3.53)
Процедура разбиения-объединения представлена на рисунке 3.8.
Рисунок 3.8 - Разбиение и объединение последовательностей при N = 8
Вначале комплексную экспоненту в выражении (3.53) обозначим как:
(3.54)
Тогда выражение (3.53) принимает вид:
(3.55)
Прореживание по времени заключается в разбиении исходной последовательности отсчетов s(n), n=0..N-1 на две последовательности длительности N/2 s0(n) и s1(n) , n=0..N-1, таких что s0(n)=s(2n), а s1(n)=s(2n+1), n=0..N/2-1. Другими словами, последовательность s0(n) содержит отсчеты последовательности s(n) с четными индексами, а s1(n) - с нечетными. Прореживание по времени для N = 8 наглядно представлено на рисунке 3.9.
Рисунок 3.9 - Прореживание по времени для N=8
Рассмотрим ДПФ сигнала прореженного по времени:
(3.56)
Если рассмотреть только первую половину спектра S(k), k=0..N-1, а также учесть что
, (3.57)
тогда (3.8.4) можно записать:
(3.58)
где S0(k) и S1(k) - точечные ДПФ последовательностей четной s0(n) и нечетной s1(n), n=0..N/2-1
(3.59)
Прореживание по времени можно считать алгоритмом разбиения последовательности на две половинной длительности. Первая половина объединенного спектра есть сумма спектра четной последовательности и спектра нечетной последовательности, умноженного на коэффициенты , которые носят названия поворотных коэффициентов.
Процедура объединения. Граф Бабочка
Теперь рассмотрим вторую половину спектра S(k+N/2), k=0..N/2-1:
(3.60)
Рассмотрим подробнее множитель.
(3.61)
Учтем что,
(3.62)
тогда выражение (3.60) справедливо для любого целого n, тогда (3.59) можно записать :.
(3.63)
Рассмотрим теперь поворотный коэффициент в (3.8.8):
. (3.64)
Тогда выражение (3.60) с учетом (3.63) и (3.64) принимает вид:
(3.65)
Таким образом окончательно можно записать:
(3.66)
Выражение (3.66) представляет собой алгоритм объединения при прореживании по времени. Данную процедуру объединения можно представить в виде графа (рисунок 3.10), который называется Бабочка.
Рисунок 3.10 - Процедура объединения на основе графа Бабочка
Представим в виде графа алгоритм БПФ с прореживанием по времени основанный на разбиении - объединении при (рисунок 3.11).
Рисунок 3.11 - Граф алгоритма БПФ с прореживанием по времени при N=8
На первом этапе отсчеты входного сигнала переставляются местами и исходная последовательность делится н