Двумерные дискретные преобразования Фурье и Хартли

Для обработки двумерных сигналов, в частности, изображений, широко используются двумерные спектральные преобразования. Двумерное дискретное преобразование Фурье имеет вид [11, 21]:

(6.6)

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

Действительно,

откуда получаем с учетом (2.16):

Введя обозначение

(6.7)

получим:

. (6.8)

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

(6.9).

Из (2.19) следует, что двумерное ДПФ сводится вначале к одномерному ДПФ матрицы X по столбцам, а затем к одномерному ДПФ по строкам матрицы промежуточных результатов .

Сложность вычислений на первом этапе составит N раз по N² базовых операций, под которыми понимаются операции вычисления выражения под знаком суммы в (6.7) и (6.8), и столько же на втором, откуда: Q_ДПФ = 2N³ (Б.О.)

В то же время непосредственные вычисления двумерного ДПФ по формуле (2.16) требуют вычислительных затрат:

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

Поэтому использование свойства разделимости ядра двумерного ДПФ по переменным суммирования приводит к снижению сложности вычислений в N/2 раз.

Однако далеко не все ядра двумерных спектральных ортогональных преобразований в явном виде обладают свойством разделимости. К таким преобразованиям относится, например, двумерное дискретное преобразование Хартли [3]:

Рассмотрим применение специального или модифицированного преобразования Хартли, в котором искусственно выполнено разделение ядра по координатам [3]:

(6.11)

Очевидно, что выражение (6.11) может быть представлено в виде:

Представляет интерес установить взаимосвязь между традиционным двумерным преобразованием Хартли (выражение (6.20)) и модифицированным преобразованием Хартли, определяемым согласно выражению (6.21). После ряда тригонометрических и алгебраических преобразований ядра в выражении (2.21) нетрудно получить [24]:

(6.12)

где в силу цикличности ядра (N-k)modN = -k; (N-l)modN = -l.

От компонент спектра Хартли можно перейти к компонентам спектра Фурье, используя известное соотношение:

Если записать в виде, подобном выражению (6.12), то получим выражение, определяющее связь между компонентами спектра Фурье и компонентами модифицированного преобразования Хартли:

(6.13)

Следует подчеркнуть, что определение как через традиционное, так и через модифицированное преобразование Хартли требует вычисления только лишь или соответственно. Остальные требуемые слагаемые легко могут быть найдены путем перекомпоновки матрицы или

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

Пусть Тогда , а формулы (6.12) и (6.13) приобретают вид:

Если , то как преобразование Хартли, так и преобразование Фурье эквивалентны модифицированному преобразованию Хартли:

;