Двумерное ДПФ

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

,

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

Здесь N1xN2 - размер исходного сигнала, он же - размер спектра. k1 и k2 - это номера базисных функций (номера коэффициентов двумерного ДПФ, при которых эти функции находятся). Поскольку размер спектра равен размеру исходного сигнала, то k1 = 0,…,N1-1; k2 = 0,…,N2-1.1 и n2 - переменные-аргументы базисных функций. Поскольку область определения базисных функций совпадает с областью определения сигнала, то n1 = 0,…,N1-1; n2 = 0,…,N2-1.

Двумерное ДПФ (в комплексной форме) определяется следующими формулами (здесь x[n1,n2] - исходный сигнал, а X[k1,k2] - его спектр):

,

.

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

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

При этом результаты всех одномерных комплексных ДПФ нужно записывать на место исходных данных для этих ДПФ. Например, при вычислении одномерного ДПФ первой строки изображения нужно результат ДПФ записать в первую строку этого изображения (он имеет тот же размер). Для этого нужно каждый "пиксель" хранить в виде комплексного числа.

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

Лучшие статьи по информатике

Разработка системы управления электроприводом нажимного устройства реверсивного четырехвалкового стана 5000 горячей прокатки
Целью проекта является разработка системы управления электроприводом нажимного устройства реверсивного четырехвалкового стана «5000» горячей прокатки. По ...

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

Характеристика аппаратуры на ООО Заполярпромгражданстрой
В соответствии с учебным планом я проходил учебную практику в обществе с ограниченной ответственностью «Заполярпромгражданстрой» с 22 апреля 2013 года по 12 ...