4.7. Рекуррентный алгоритм вычисления ДПФ

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

Рис. 4.12.

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

Тогда спектр второго фрагмента, смещенного по координатам на и относительно первого, можно записать как (см. рис. 4.12)

(см. скан)

или после группировки и замены переменных

Таким образом, вычисляется через и три усеченных ДПФ.

В частном случае смещения только в одном направлении (например, вдоль

Если смещение равно одному элементу, как при так называемой «скользящей» обработке,

В одномерном случае, очевидно,

и при „скользящей" обработке

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