4.6. Совмещенные алгоритмы ДПФ

При обработке изображений с помощью ДПФ исходный сигнал чаще всего представлен последовательностью действительных чисел. Кроме того, как указывалось в § 3.8, при вычислении свертки с помощью ДПФ сигнал приходится иногда четным образом дополнять. В результате оказывается, что преобразуемые последовательности имеют двойную (за счет вещественности) или даже четырехкратную (за счет вещественности и четности) избыточность. Эта избыточность может быть использована для соответствующего ускорения вычисления дискретных преобразований Фурье.

Совмещенные алгоритмы ДПФ действительных последовательностей.

Можно указать два способа использования двойной избыточности ДПФ последовательностей действительных чисел. Первый — совмещение преобразования двух последовательностей, второй — разбиение одной последовательности с четным числом членов на две подпоследовательности, совместное преобразование этих подпоследовательностей и пересчет результата на всю последовательность.

Рассмотрим сначала первый способ; второй в конечном счете сводится к первому.

Пусть — две последовательности действительных чисел длиной Образуем последовательность

и найдем ее ДПФ

где

а индексы означают действительные и мнимые части соответствующих чисел.

Так как

(см. табл. 3.1, строка 5), то

Поэтому

т. е.

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

Описанная процедура вычислений иллюстрируется схемой на рис. 4.11, а. Такой способ совмещения ДПФ целесообразно применять, например, при преобразовании двумерных массивов, когда в качестве удобно выбирать соседние пары строк массива.

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

Рис. 4.11.

Пусть — последовательность действительных чисел длиной и необходимо найти ее дискретное преобразование Фурье

Выделим в сумме (4.96) четные и нечетные слагаемые:

Таким образом, ДПФ всей последовательности можно найти, вычислив от двух ее подпоследовательностей, составленных соответственно из четных и нечетных членов исходной последовательности, и затем просуммировав полученные результаты по формуле

где от соответственно. Что касается то их можно наити, пользуясь первым способом совмещенного ДПФ (4.95). В результате получим

где

. Значения для остальных находятся по формуле (4.92).

Как видно из сравнения формул (4.95) и (4.99), второй способ требует более сложных дополнительных вычислений.

Описанные алгоритмы совмещенного преобразования Фурье легко обратить и получить алгоритмы вычисления ДПФ комплексно-сопряженных последовательностей. Действительно, на рис. 4.11, а нетрудно видеть, что, имея две последовательности такие, что можно образовать из них последовательность по следующему правилу:

Тогда действительная часть фурье-преобразования этой последовательности есть фурье-преобразование а мнимая — фурье-преобразование Схема этого алгоритма показана на рис. 4.11,б.

Точно так же, имея одну последовательность длиной можно образовать из нее две последовательности

после чего действовать так, как описано выше Для двух отдельных последовательностей.

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

Совмещенный алгоритм СДПФ (1/2, 0) четных и действительных четных последовательностей.

Для четных последовательностей с четным числом членов выполняются следующие соотношения (см. табл. 3 3, строки 7, 13):

Их можно использовать для построения совмещенных алгоритмов четных последовательностей. Действительно, пусть две [четные последовательности с четным числом членов:

Образуем последовательности

Ее будет равно

где соответственно

В соответствии с (4.103 а) и (4.103 в)

Поэтому

Значения и рдля других можно найти из (4.103 а).

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

Если преобразуемые последовательности являются еще и действительными, то коэффициенты их также чисто действительные (табл. 3.3, строка 8). Поэтому действительная и мнимая части в (4.107) являются соответственно действительной и мнимой частей Таким образом, формируя из двух пар действительных четных

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