Преобразование Фурье

Определение преобразования Фурье

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

Если f (m, n) является функцией двух дискретных пространственных переменных m и n, то двумерное преобразование Фурье f (m, n) задано отношением

$F (ω_{1}, ω_{2}) = \sum_{m = - \infty}^{\infty} \sum_{n = - \infty}^{\infty} f (m, n) e^{- j ω_{1} m} e^{- j ω_{2} n} .$

Переменные ω ₁ и ω ₂ являются переменными частоты; их модули являются радианами на выборку. F (ω ₁, ω ₂) часто называется представлением частотного диапазона f (m, n). F (ω ₁, ω ₂) является комплексной функцией, которая является периодической и в ω ₁ и в ω ₂ с периодом $2 π$ . Из-за периодичности, обычно только область значений $- π \leq ω_{1}, ω_{2} \leq π$ отображен. Обратите внимание на то, что F (0,0) является суммой всех значений f (m, n). Поэтому F (0,0) часто называется постоянным компонентом или компонентом DC преобразования Фурье. (DC обозначает постоянный ток; это - электротехническое понятие, которое относится к источнику питания постоянного напряжения, в противоположность источнику питания, напряжение которого варьируется синусоидально.)

Инверсия преобразования является операцией, которая, когда выполняется на преобразованном изображении производит оригинальное изображение. Обратным двумерным преобразованием Фурье дают

$f (m, n) = \frac{1}{4 π^{2}} \int_{ω_{1} = - π}^{π} \int_{ω_{2} = - π}^{π} F (ω_{1}, ω_{2}) e^{j ω_{1} m} e^{j ω_{2} n} d ω_{1} d ω_{2} .$

Примерно разговор, это уравнение означает, что f (m, n) может быть представлен как сумма бесконечного числа комплексных экпонент (синусоиды) с различными частотами. Величина и фаза вклада на частотах (ω ₁, ω ₂) даны F (ω ₁, ω ₂).

Визуализация преобразования Фурье

Чтобы проиллюстрировать, рассмотрите функциональный f (m, n), который еще равняется 1 в прямоугольной области и 0 везде. Чтобы упростить схему, f (m, n) показывается непрерывной функцией, даже при том, что переменные m и n дискретны.

Прямоугольная функция

Следующий рисунок показывает, как сетчатый график, величина преобразования Фурье,

$| F (ω_{1}, ω_{2}) |,$

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

Изображение величины прямоугольной функции

Пиком в центре графика является F (0,0), который является суммой всех значений в f (m, n). График также показывает, что F (ω ₁, ω ₂) имеет больше энергии на высоких горизонтальных частотах, чем в высоких частотах кадровой развертки. Это отражает то, что горизонтальные сечения f (m, n) являются узкими импульсами, в то время как вертикальные сечения являются кадровыми импульсами. Узкие импульсы имеют больше высокочастотного содержимого, чем кадровые импульсы.

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

$\log | F (ω_{1}, ω_{2}) |$

как изображение, как показано.

Журнал преобразования Фурье прямоугольной функции

Используя логарифм помогает произвести детали преобразования Фурье в областях, где F (ω ₁, ω ₂) очень близко к 0.

Примеры преобразования Фурье для других простых форм показывают ниже.

Преобразования Фурье некоторых простых форм

Дискретное преобразование Фурье

Работа с преобразованием Фурье на компьютере обычно включает форму преобразования, известного как дискретное преобразование Фурье (DFT). Дискретное преобразование является преобразованием, значения ввода и вывода которого являются дискретными выборками, делая его удобным для манипуляции с компьютерами. Существует две основных причины использования этой формы преобразования:

Ввод и вывод ДПФ оба дискретен, который делает его удобным для манипуляций с компьютерами.
Существует алгоритм FAST для вычисления ДПФ, известного как быстрое преобразование Фурье (FFT).

ДПФ обычно задается для дискретного функционального f (m, n), который является ненулевым только по конечной области $0 \leq m \leq M - 1$ и $0 \leq n \leq N - 1$ . Двумерным ДПФ M на n и обратными отношениями ДПФ M на n дают

$F (p, q) = \sum_{m = 0}^{M - 1} \sum_{n = 0}^{N - 1} f (m, n) e^{- j 2 π p m / M} e^{- j 2 π q n / N} \begin{matrix} p = 0, 1, ..., M - 1 \\ q = 0, 1, ..., N - 1 \end{matrix}$

$f (m, n) = \frac{1}{M N} \sum_{p = 0}^{M - 1} \sum_{q = 0}^{N - 1} F (p, q) e^{j 2 π p m / M} e^{j 2 π q n / N} \begin{matrix} m = 0, 1, ..., M - 1 \\ n = 0, 1, ..., N - 1 \end{matrix}$

Значения F (p, q) коэффициенты ДПФ f (m, n). Коэффициент нулевой частоты, F (0,0), часто называется "компонентом DC". DC является электротехническим понятием, которое обозначает постоянный ток. (Обратите внимание на то, что матричные индексы в MATLAB^® всегда запускаются в 1, а не 0; поэтому, элементы матрицы f (1,1) и F (1,1) соответствуют математическим количествам f (0,0) и F (0,0), соответственно.)

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

Отношение к преобразованию Фурье

Коэффициенты ДПФ F (p, q) выборки преобразования Фурье F (ω ₁, ω ₂).

$\begin{matrix} F (p, q) = F (ω_{1}, ω_{2}) |_{\begin{array}{l} ω_{1} = 2 π p / M \\ ω_{2} = 2 π q / N \end{array}} & \begin{array}{l} p = 0, 1, ..., M - 1 \\ q = 0, 1, ..., N - 1 \end{array} \end{matrix}$

Визуализация дискретного преобразования Фурье

Создайте матричный f это похоже на функциональный f (m, n) в примере в Определении преобразования Фурье. Помните, что f (m, n) равен 1 в прямоугольной области и 0 в другом месте. Используйте двухуровневое изображение, чтобы представлять f (m, n).
```
f = zeros(30,30);
f(5:24,13:17) = 1;
imshow(f,'InitialMagnification','fit')
```
Вычислите и визуализируйте 30 30 ДПФ f с этими командами.
```
F = fft2(f);
F2 = log(abs(F));
imshow(F2,[-1 5],'InitialMagnification','fit');
colormap(jet); colorbar
```
Дискретное преобразование Фурье, вычисленное без дополнения
Этот график отличается от преобразования Фурье, отображенного в Визуализации преобразования Фурье. Во-первых, выборка преобразования Фурье намного более груба. Во-вторых, коэффициент нулевой частоты отображен в левом верхнем углу вместо традиционного местоположения в центре.
Чтобы получить более прекрасную выборку преобразования Фурье, добавьте нулевое дополнение в f при вычислении его ДПФ. Нулевое дополнение и расчет ДПФ могут быть выполнены на одном шаге с этой командой.
```
F = fft2(f,256,256);
```
Эта команда нулевые клавиатуры f 256 256 прежде вычислять ДПФ.
```
imshow(log(abs(F)),[-1 5]); colormap(jet); colorbar
```
Дискретное преобразование Фурье, вычисленное с дополнением
Коэффициент нулевой частоты, однако, все еще отображен в левом верхнем углу, а не центре. Можно решить эту проблему при помощи функционального fftshift, который подкачивает квадранты F так, чтобы коэффициент нулевой частоты был в центре.
```
F = fft2(f,256,256);F2 = fftshift(F);
imshow(log(abs(F2)),[-1 5]); colormap(jet); colorbar
```
Получившийся график идентичен один показанный в Визуализации преобразования Фурье.

Приложения преобразования Фурье

Этот раздел представляет несколько из многих связанных с обработкой изображений приложений преобразования Фурье.

Частотная характеристика линейных фильтров

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

h = fspecial('gaussian');
freqz2(h)

Частотная характеристика гауссова фильтра

Смотрите Линейные фильтры Проекта в Частотном диапазоне для получения дополнительной информации о линейной фильтрации, создании фильтра и частотных характеристиках.

Выполните быструю свертку Используя преобразование Фурье

Скрипт Open Live Script

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

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

Создайте две простых матрицы, A и BA матрица M на n и B P-by-Q матрица.

A = magic(3);
B = ones(3);

Нулевая клавиатура A и B так, чтобы они были, по крайней мере (M+P-1) (N+Q-1). (Часто A и B дополнены нулем к размеру, который является степенью 2 потому что fft2 является самым быстрым для этих размеров.) Пример заполняет матрицы, чтобы быть 8 8.

A(8,8) = 0;
B(8,8) = 0;

Вычислите двумерного ДПФ A и B использование fft2 функция. Умножьте эти двух ДПФ вместе и вычислите обратного двумерного ДПФ результата с помощью ifft2 функция.

C = ifft2(fft2(A).*fft2(B));

Извлеките ненулевой фрагмент результата и удалите мнимую часть, вызванную ошибкой округления.

C = C(1:5,1:5);
C = real(C)

C = 5×5

    8.0000    9.0000   15.0000    7.0000    6.0000
   11.0000   17.0000   30.0000   19.0000   13.0000
   15.0000   30.0000   45.0000   30.0000   15.0000
    7.0000   21.0000   30.0000   23.0000    9.0000
    4.0000   13.0000   15.0000   11.0000    2.0000

Выполните основанную на БПФ корреляцию, чтобы определить местоположение функций изображений

Скрипт Open Live Script

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

Считайте демонстрационное изображение в рабочую область.

bw = imread('text.png');

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

a = bw(32:45,88:98);

Вычислите корреляцию изображения шаблона с оригинальным изображением путем вращения изображения шаблона 180 градусами и затем использования основанного на БПФ метода свертки. (Свертка эквивалентна корреляции, если вы вращаете ядро свертки 180 градусами.), Чтобы совпадать с шаблоном к изображению, используйте fft2 и ifft2 функции. В получившемся изображении яркий peaks соответствует случаям буквы.

C = real(ifft2(fft2(bw) .* fft2(rot90(a,2),256,256)));
figure
imshow(C,[]) % Scale image to appropriate display range.

Чтобы просмотреть местоположения шаблона в изображении, найдите максимальное пиксельное значение и затем задайте пороговое значение, которое меньше этого максимума. Пороговое изображение показывает местоположения этого peaks как белые пятна в пороговом изображении корреляции. (Чтобы сделать местоположения легче видеть в этом рисунке, пример расширяет пороговое изображение, чтобы увеличить размер точек.)

max(C(:))

ans = 68

thresh = 60; % Use a threshold that's a little less than max.
D = C > thresh;
se = strel('disk',5);
E = imdilate(D,se);
figure
imshow(E) % Display pixels with values over the threshold.

Документация