2.2. ПРЕОБРАЗОВАНИЯ ФУРЬЕ И ПРЕОБРАЗОВАНИЯ ДРУГИХ ВИДОВ

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

Если — функция двух переменных определенная на бесконечной плоскости, то ее образ при двухмерном

В качестве синонима понятия преобразования Фурье часто

а для двухмерного

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

Уравнения (2.3) и (2.4) обычно называют дискретным преобразованием Фурье (ДПФ). Пределы суммирования у каждой из двух сумм могут быть различными, что позволяет определить ДПФ на прямоугольной области. Нельзя, однако, определить двухмерное преобразование Фурье на области произвольной формы. Если ограничить пределы интегрирования в уравнении (2.2) или пределы суммирования в (2.4), то результат преобразования будет зависеть не только от значений функции но и от формы области суммирования/интегрирования. Дискретное обратное преобразование Фурье (ДОПФ) определяется следующим образом:

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

Другими словами, . В большинстве прикладных задач не только является четным числом, но равно также степени числа 2. Матрицу можно упростить, если учесть, что

Отметим также, что данная матрица — симметрическая, а скалярное произведение любого из ее столбцов (или строк) и некоторого другого столбца (или строки) равно нулю. Скалярное произведение любого из ее столбцов (или строк) с самим собой равно Таким образом, матрица обладает тем важным свойством, что ее обратная матрица равна ее сопряженной транспонированной матрице, умноженной на Матрица вида которой обратная матрица равна ее сопряженной транспонированной матрице, называется унитарной. Обозначим через вектор-столбец, компонентами которого служат значения а через — вектор-столбец, компонентами которого служат

значения . Теперь уравнение (2.3) можно записать в матричном виде:

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

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

Преобразования других видов можно определить, воспользовавшись уравнениями (2.8) и (2.9) и изменив задание матрицы таким образом, чтобы оставалась унитарной матрицей. Таким образом можно, в частности, определить преобразование Адамара. Матрицы для этого преобразования можно рекурсивно задать следующим образом:

Таким образом, преобразование Адамара соответствует разложению по периодическим функциям прямоугольной формы в отличие от преобразования Фурье, предусматривающего разложение по синусоидальным и косинусоидальным компонентам. Более того, матрицу можно задавать в виде, аналогичном выражению (2.7), положив и взяв другое правило изменения показателей степени. Главным преимуществом преобразования Адамара является замена умножений комплексных величин изменениями знаков — существенное обстоятельство для первого периода развития вычислительной техники, когда арифметические устройства с плавающей запятой были малодоступны. Во всех остальных отношениях это преобразование позволяет получать точно такие же результаты, как и преобразование Фурье.

Эти преобразования находят применение, главным образом, при конструировании фильтров, предназначенных для улучшения качества изображений, а также при реализации некоторых методов сжатия данных. Они составляют также основу восстановления изображений по проекциям (см. гл. 5). Использование преобразований для сжатия данных оправданно в случаях, когда большая часть компонентов равна нулю. При выполнении этого условия можно воспользоваться уравнением (2.5) или (2 6)

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

Использование определяющих уравнений для реализации преобразования, заданного уравнением (2.8), требует выполнения вычислительных операций в одномерном случае и — в двухмерном. Более эффективный алгоритм — быстрое преобразование Фурье

— можно получить, перегруппировав члены суммы в уравнении (2.3) и использовав то обстоятельство, что произведение принимает одни и те же значения при различных значениях и и к. Это преобразование описано в приложении причем показано, что в одномерном случае для его реализации требуется всего лишь операций. Алгоритм БПФ можно использовать для получения двухмерного фурье-образа: сначала определяется образ каждой строки изображения, а затем — для всех столбцов. Этот метод иллюстрируется алгоритмом 2.1, в котором процедура обеспечивает замену -элементной матрицы х ее дискретным фурье-образом.

Алгоритм 2.1. Двухмерное БПФ

(см. скан)

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