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

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

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

Если 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} .$

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

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

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

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

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

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

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

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

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

Другой распространенный способ визуализации преобразования Фурье - это отображение

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

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

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

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

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

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

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

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

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

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

$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) являются коэффициентами DFT f (m, n). Коэффициент нулевой частоты, F (0,0), часто называют «компонент постоянного тока». DC является электрическим инженерным термином, который обозначает постоянный ток. (Обратите внимание, что матричные индексы в MATLAB^® всегда начинаться с 1, а не с 0; поэтому элементы матрицы f (1,1) и F (1,1) соответствуют математическим величинам f (0,0) и F (0,0), соответственно.

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

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

Коэффициенты DFT F (p, q) являются выборками F преобразования Фурье (ω 1, ω 2).

$\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);
```
Эта команда zero-pads 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)

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

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

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

Открыть Live Script

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

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

Создайте две простые матрицы, A и B. A является M-на-N матрицей и B является P-на-Q матрицей.

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

Устройство с нулевым A и B так, чтобы они были по меньшей мере (M + P-1) -by- (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

Выполните корреляцию на основе FFT, чтобы найти функции изображения

Открыть Live Script

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

Прочтите образец изображения в рабочую область.

bw = imread('text.png');

Создайте шаблон для соответствия путем извлечения буквы «а» из изображения. Обратите внимание, что вы также можете создать шаблон с помощью интерактивного синтаксиса 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.

Figure contains an axes. The axes contains an object of type image.

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

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.

Figure contains an axes. The axes contains an object of type image.

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