Линейная фильтрация изображений может осуществляться как в пространственной, так и в частотной области. При этом считается, что "низким" пространственным частотам соответствует основное содержание изображения - фон и крупноразмерные объекты, а "высоким" пространственным частотам - мелкоразмерные объекты, мелкие детали крупных форм и шумовая компонента.
Традиционно для перехода в область пространственных частот используются методы, основанные на $\textit{преобразовании Фурье}$. В последние годы все большее применение находят также методы, основанные на $\textit{вейвлет-преобразовании (wavelet-transform)}$.
Преобразование Фурье.
Преобразование Фурье позволяет представить практически любую функцию или набор данных в виде комбинации таких тригонометрических функций, как синус и косинус, что позволяет выявить периодические компоненты в данных и оценить их вклад в структуру исходных данных или форму функции. Традиционно различаются три основные формы преобразования Фурье: интегральное преобразование Фурье, ряды Фурье и дискретное преобразование Фурье.
Интегральное преобразование Фурье переводит вещественную функцию в пару вещественных функций или одну комплексную функцию в другую.
Вещественную функцию $f(x)$ можно разложить по ортогональной системе тригонометрических функций, то есть представить в виде
$$ f\left(x \right)=\int\limits_0^\infty {A\left(\omega \right)} \cos \left({2\pi \omega x} \right)d\omega -\int\limits_0^\infty {B\left(\omega \right)} \sin \left({2\pi \omega x} \right)d\omega , $$
где $A(\omega)$ и $B(\omega)$ называются интегральными косинус- и синус-преобразованиями:
$$ A\left(\omega \right)=2\int\limits_{-\infty }^{+\infty } {f\left(x \right)} \cos \left({2\pi \omega x} \right)dx; \quad B\left(\omega \right)=2\int\limits_{-\infty }^{+\infty } {f\left(x \right)} \sin \left({2\pi \omega x} \right)dx. $$
Ряд Фурье представляет периодическую функцию $f(x)$, заданную на интервале $$, в виде бесконечного ряда по синусам и косинусам. То есть периодической функции $f(x)$ ставится в соответствие бесконечная последовательность коэффициентов Фурье
$$ f\left(x \right)=\frac{A_0 }{2}+\sum\limits_{n=1}^\infty {A_n } \cos \left({\frac{2\pi xn}{b-a}} \right)+\sum\limits_{n=1}^\infty {B_n \sin \left({\frac{2\pi xn}{b-a}} \right)} , $$
$$ A_n =\frac{2}{b-a}\int\limits_a^b {f\left(x \right)} \cos \left({\frac{2\pi nx}{b-a}} \right)dx; \quad B_n =\frac{2}{b-a}\int\limits_a^b {f\left(x \right)} \sin \left({\frac{2\pi nx}{b-a}} \right)dx. $$
Дискретное преобразование Фурье переводит конечную последовательность вещественных чисел в конечную последовательность коэффициентов Фурье.
Пусть $\left\{ {x_i } \right\}, i= 0,\ldots, N-1 $ - последовательность вещественных чисел - например, отсчеты яркости пикселов по строке изображения. Эту последовательность можно представить в виде комбинации конечных сумм вида
$$ x_i =a_0 +\sum\limits_{n=1}^{N/2} {a_n } \cos \left({\frac{2\pi ni}{N}} \right)+\sum\limits_{n=1}^{N/2} {b_n \sin \left({\frac{2\pi ni}{N}} \right)} , $$
$$ a_0 =\frac{1}{N}\sum\limits_{i=0}^{N-1} {x_i } , \quad a_{N/2} =\frac{1}{N}\sum\limits_{i=0}^{N-1} {x_i } \left({-1} \right)^i, \quad a_k =\frac{2}{N}\sum\limits_{i=0}^{N-1} {x_i \cos \left({\frac{2\pi ik}{N}} \right)}, $$
$$
b_k =\frac{2}{N}\sum\limits_{i=0}^{N-1} {x_i \sin \left({\frac{2\pi ik}{N}} \right)},
\quad
i\le k Основное отличие между тремя формами преобразования Фурье заключается в том,
что если интегральное преобразование Фурье определено по всей области
определения функции $f(x)$, то ряд и дискретное преобразование Фурье
определены только на дискретном множестве точек, бесконечном для ряда Фурье
и конечном для дискретного преобразования. Как видно из определений преобразования Фурье, наибольший интерес для систем
цифровой обработки сигналов представляет дискретное преобразование Фурье.
Данные, получаемые с цифровых носителей или источников информации,
представляют собой упорядоченные наборы чисел, записанные в виде векторов
или матриц. Обычно принимается, что входные данные для дискретного преобразования
представляют собой равномерную выборку с шагом $\Delta $, при этом величина
$T=N\Delta $ называется длиной записи, или основным периодом. Основная
частота равна $1/T$. Таким образом, в дискретном преобразовании Фурье
производится разложение входных данных по частотам, которые являются целым
кратным основной частоты. Максимальная частота, определяемая размерностью
входных данных, равна $1/2 \Delta $ и называется $\it{частотой Найквиста}$. Учет частоты Найквиста
имеет важное значение при использовании дискретного преобразования. Если
входные данные имеют периодические составляющие с частотами, превышающими
частоту Найквиста, то при вычислении дискретного преобразования Фурье
произойдет подмена высокочастотных данных более низкой частотой, что может
привести к ошибкам при интерпретации результатов дискретного преобразования. Важным инструментом анализа данных является также $\it{энергетический спектр}$. Мощность сигнала на
частоте $\omega $ определяется следующим образом: $$
P \left(\omega \right)=\frac{1}{2}\left({A \left(\omega \right)^2+B \left(\omega \right)^2} \right) .
$$ Эту величину часто называют $\it{энергией сигнала}$ на частоте $\omega $. Согласно теореме
Парсеваля общая энергия входного сигнала равна сумме энергий по всем
частотам. $$
E=\sum\limits_{i=0}^{N-1} {x_i^2 } =\sum\limits_{i=0}^{N/2} {P \left({\omega _i } \right)} .
$$ График зависимости мощности от частоты называется энергетическим спектром
или спектром мощности. Энергетический спектр позволяет выявлять скрытые
периодичности входных данных и оценивать вклад определенных частотных
компонент в структуру исходных данных. Кроме тригонометрической формы записи дискретного преобразования Фурье
широко используется $\it{комплексное представление}$. Комплексная форма записи преобразования Фурье широко
используется в многомерном анализе и в частности при обработке изображений. Переход из тригонометрической в комплексную форму осуществляется на
основании формулы Эйлера $$
e^{j\omega t}=\cos \omega t+j\sin \omega t,
\quad
j=\sqrt {-1} .
$$ Если входная последовательность представляет собой $N$ комплексных чисел, то
ее дискретное преобразование Фурье будет иметь вид $$
G_m =\frac{1}{N}\sum\limits_{n=1}^{N-1} {x_n } e^{\frac{-2\pi jmn}{N}},
$$ а обратное преобразование $$
x_m =\sum\limits_{n=1}^{N-1} {G_n } e^{\frac{2\pi jmn}{N}}.
$$ Если входная последовательность представляет собой массив вещественных
чисел, то для нее существует как комплексное, так и синусно-косинусное
дискретное преобразование. Взаимосвязь этих представлений выражается
следующим образом: $$
a_0 =G_0 ,
\quad
G_k =\left({a_k -jb_k } \right)/2,
\quad
1\le k\le N/2;
$$ остальные $N/2$ значений преобразования являются комплексно сопряженными и не
несут дополнительной информации. Поэтому график спектра мощности дискретного
преобразования Фурье симметричен относительно $N/2$. Простейший способ вычисления дискретного преобразования Фурье (ДПФ) -
прямое суммирование, оно приводит к $N$ операциям на каждый коэффициент. Всего
коэффициентов $N$, так что общая сложность $O\left({N^2} \right)$. Такой
подход не представляет практического интереса, так как существуют гораздо
более эффективные способы вычисления ДПФ, называемые быстрым преобразованием
Фурье (БПФ), имеющее сложность $O (N\log N)$.
БПФ применяется только к последовательностям, имеющим длину (число
элементов), кратную степени 2. Наиболее общий принцип, заложенный в алгоритм
БПФ, заключается в разбиении входной последовательности на две
последовательности половинной длины. Первая последовательность заполняется
данными с четными номерами, а вторая - с нечетными. Это дает возможность
вычисления коэффициентов ДПФ через два преобразования размерностью $N/2$. Обозначим $\omega _m =e^{\frac{2\pi j}{m}}$, тогда $G_m =\sum\limits_{n=1}^{(N/2)-1} {x_{2n} } \omega
_{N/2}^{mn} +\sum\limits_{n=1}^{(N/2)-1} {x_{2n+1} }
\omega _{N/2}^{mn} \omega _N^m $. Для $m < N/2$ тогда можно записать $G_m =G_{\textrm{even}} \left(m \right)+G_{\textrm{odd}}
\left(m \right)\omega _N^m $. Учитывая, что элементы ДПФ с индексом
б ольшим, чем $N/2$, являются комплексно сопряженными к элементам с индексами
меньшими $N/2$, можно записать $G_{m+(N/2)} =G_{\textrm{even}} \left(m \right)-G_{\textrm{odd}}
\left(m \right)\omega _N^m $. Таким образом, можно вычислить БПФ длиной $N$,
используя два ДПФ длиной $N/2$. Полный алгоритм БПФ заключается в рекурсивном
выполнении вышеописанной процедуры, начиная с объединения одиночных элементов в пары,
затем в четверки и так до полного охвата исходного массива данных. Дискретное преобразование Фурье для двумерного массива чисел размера
$M\times N$ определяется следующим образом: $$
G_{uw} =\frac{1}{NM}\sum\limits_{n=1}^{N-1} {\sum\limits_{m=1}^{M-1} {x_{mn}
} } e^{{-2\pi j\left[ {\frac{mu}{M}+\frac{nw}{N}} \right]} },
$$ а обратное преобразование $$
x_{mn} =\sum\limits_{u=1}^{N-1} {\sum\limits_{w=1}^{M-1} {G_{uw} } }
e^{ {2\pi j\left[ {\frac{mu}{M}+\frac{nw}{N}}
\right]} }.
$$ В случае обработки изображений компоненты двумерного преобразования Фурье
называют $\textit{пространственными частотами}$. Важным свойством двумерного преобразования Фурье является возможность его
вычисления с использованием процедуры одномерного БПФ: $$
G_{uw} =\frac{1}{N}\sum\limits_{n=1}^{N-1} { \left[
{\frac{1}{M}\sum\limits_{m=0}^{M-1} {x_{mn} e^{\frac{-2\pi jmw}{M}}} } \right] } e^{\frac{-2\pi jnu}{N}},
$$ Здесь выражение в квадратных скобках есть одномерное преобразование строки
матрицы данных, которое может быть выполнено с одномерным БПФ. Таким
образом, для получения двумерного преобразования Фурье нужно сначала
вычислить одномерные преобразования строк, записать результаты в исходную
матрицу и вычислить
одномерные преобразования для столбцов полученной
матрицы. При вычислении двумерного преобразования Фурье низкие частоты будут
сосредоточены в углах матрицы, что не очень удобно для дальнейшей обработки
полученной информации. Для перевода получения представления двумерного
преобразования Фурье, в котором низкие частоты сосредоточены в центре
матрицы, можно выполнить простую процедуру, заключающуюся в умножении
исходных данных на $-1^{m+n}$. На рис. 16 показаны исходное изображение и его Фурье-образ. Полутоновое изображение и его Фурье-образ (изображения получены в системе LabVIEW) Свертка функций $s(t)$ и $r(t)$ определяется как $$
s\ast r\cong r\ast s\cong \int\limits_{-\infty }^{+\infty } {s(\tau)} r(t-\tau)d\tau .
$$ На практике приходится иметь дело с дискретной сверткой, в которой
непрерывные функции заменяются наборами значений в узлах равномерной сетки
(обычно берется целочисленная сетка): $$
(r\ast s)_j \cong \sum\limits_{k=-N}^P {s_{j-k} r_k }.
$$ Здесь $-N$ и $P$ определяют диапазон, за пределами которого $r(t) = 0$. При вычислении свертки с помощью преобразования Фурье используется свойство
преобразования Фурье, согласно которому произведение образов функций в
частотной области эквивалентно свертке этих функций во временн ой области. Для вычисления сверки необходимо преобразовать исходные данные в частотную
область, то есть вычислить их преобразование Фурье, перемножить результаты
преобразования и выполнить обратное преобразование Фурье, восстановив
исходное представление. Единственная тонкость в работе алгоритма связана с тем, что в случае
дискретного преобразования Фурье (в отличие от непрерывного) происходит
свертка двух периодических функций, то есть наши наборы значений задают
именно периоды этих функций, а не просто значения на каком-то отдельном
участке оси. То есть алгоритм считает, что за точкой $x_{N }$ идет не ноль, а
точка $x_{0}$, и так далее по кругу. Поэтому, чтобы свертка корректно
считалась, необходимо приписать к сигналу достаточно длинную
последовательность нулей. Линейные методы фильтрации относятся к числу хорошо структурированных
методов, для которых разработаны эффективные вычислительные схемы,
основанные на быстрых алгоритмах свертки и спектральном анализе. В общем
виде линейные алгоритмы фильтрации выполняют преобразование вида $$
f"(x,y) = \int\int f(\zeta -x, \eta -y)K (\zeta , \eta) d \zeta d \eta ,
$$ где $K(\zeta ,\eta)$ - ядро линейного преобразования. При дискретном представлении сигнала интеграл в данной формуле вырождается
во взвешенную сумму отсчетов исходного изображения в пределах некоторой
апертуры. При этом выбор ядра $K(\zeta ,\eta)$ в соответствии с тем или
иным критерием оптимальности может привести к ряду полезных свойств
(гауссовское сглаживание при регуляризации задачи численного
дифференцирования изображения и др.). Наиболее эффективно линейные методы обработки реализуются в частотной
области. Использование Фурье-образа изображения для выполнения операций фильтрации
обусловлено прежде всего более высокой производительностью таких операций.
Как правило, выполнение прямого и обратного двумерного преобразования Фурье
и умножение на коэффициенты Фурье-образа фильтра занимает меньше времени,
чем выполнение двумерной свертки исходного изображения. Алгоритмы фильтрации в частотной области основываются на теореме о свертке.
В двумерном случае преобразование свертки выглядит следующим образом: $$
G\left({u,v} \right)=H\left({u,v} \right)F\left({u,v} \right),
$$ где $G$ - Фурье-образ результата свертки, $H$ - Фурье-образ фильтра, а
$F$ - Фурье-образ исходного изображения. То есть в частотной области двумерная
свертка заменяется поэлементным перемножением образов исходного изображения
и соответствующего фильтра. Для выполнения свертки необходимо выполнить следующие действия. Связь между функцией фильтра в частотной и пространственной области можно
определить, используя теорему о свертке $$
\Phi \left[ {f\left({x,y} \right)\ast h(x,y)} \right]=F\left({u,v}
\right)H\left({u,v} \right),
$$ $$
\Phi \left[ {f\left({x,y} \right)h(x,y)} \right]=F\left({u,v} \right)\ast
H\left({u,v} \right).
$$ Свертка функции с импульсной функцией может быть представлена следующим
образом: $$
\sum\limits_{x=0}^M {\sum\limits_{y=0}^N {s\left({x,y} \right)}
} \delta \left({x-x_0 ,y-y_0 } \right)=s(x_0 ,y_0).
$$ Фурье-преобразование импульсной функции $$
F\left({u,v} \right)=\frac{1}{MN}\sum\limits_{x=0}^M
{\sum\limits_{y=0}^N {\delta \left({x,y} \right) } } e^{ {-2\pi
j\left({\frac{ux}{M}+\frac{vy}{N}}
\right)} }
=\frac{1}{MN}.
$$ Пусть $f(x,y) = \delta (x,y)$, тогда свертка $$
f\left({x,y} \right)\ast h(x,y)=\frac{1}{MN}h\left({x,y} \right),
$$ $$
\Phi \left[ {\delta \left({x,y} \right)\ast h(x,y)} \right]=\Phi
\left[ {\delta \left({x,y} \right)} \right]H\left({u,v}
\right)=\frac{1}{MN}H\left({u,v} \right).
$$ Из этих выражений видно, что функции фильтра в частотной и пространственной
областях взаимосвязаны через преобразование Фурье. Для данной функции
фильтра в частотной области всегда можно найти соответствующий фильтр в
пространственной области, применив обратное преобразование Фурье. То же верно
и для обратного случая. Используя данную взаимосвязь, можно определить
процедуру синтеза пространственных линейных фильтров.
{$\textit{Идеальный фильтр низких частот}$} $H(u,v)$ имеет вид
$$H(u,v) = 1, \quad \mbox{если }D(u,v) < D_0 ,$$
$$H(u,v) = 0, \quad \mbox{если }D(u,v) \ge D_0 ,$$
где $D\left({u,v} \right)=\sqrt {\left({u-\frac{M}{2}} \right)^2+\left({v-\frac{N}{2}} \right)^2}$ - расстояние от центра частотной плоскости. {$\textit{Идеальный высокочастотный фильтр}$} получается путем
инверсии идеального низкочастотного фильтра: $$
H"(u,v) = 1-H(u,v).
$$ Здесь происходит полное подавление низкочастотных компонент при сохранении
высокочастотных. Однако как и в случае идеального низкочастотного фильтра,
его применение чревато появлением существенных искажений. Для синтеза фильтров с минимальными искажениями используются различные
подходы. Одним из них является синтез фильтров на основе экспоненты. Такие
фильтры привносят минимальные искажения в результирующее изображение и
удобны для синтеза в частотной области. Широко используемым при обработке изображений является семейство фильтров на
основании вещественной функции Гаусса. $\textit{Низкочастотный гауссовский фильтр}$ имеет вид $$
h\left(x \right)=\sqrt {2\pi } \sigma Ae^{-2\left({\pi \sigma
x} \right)^2} \mbox{ и } H\left(u \right)=Ae^{-\frac{u^2}{2\sigma ^2}}
$$ Чем уже профиль фильтра в частотной области (чем больше $\sigma $), тем он
шире в пространственной. {$\textit{Высокочастотный гауссовский фильтр}$} имеет вид $$
h\left(x \right)=\sqrt {2\pi } \sigma _A Ae^{-2\left({\pi \sigma _A x}
\right)^2}-\sqrt {2\pi } \sigma _B Be^{-2\left({\pi \sigma _B x} \right)^2 },
$$ $$
H\left(u \right)=Ae^{-\frac{u^2}{2\sigma _A^2 }}-Be^{-\frac{u^2}{2\sigma
_B^2 }}.
$$ В двумерном случае {$\it{низкочастотный}$} фильтр гаусса
выглядит следующим образом: $$
H\left({u,v} \right)=e^{-\frac{D^2\left({u,v} \right)}{2D_0^2 }}.
$$ {$\it{Высокочастотный}$} гауссовский фильтр имеет вид $$
H\left({u,v} \right)=1-e^{-\frac{D^2\left({u,v} \right)}{2D_0^2 }}.
$$ Рассмотрим пример фильтрации изображения (рис. 1) в частотной области
(рис. 17 - 22). Заметим, что частотная фильтрация изображения может
иметь смысл как сглаживания ($\textit{низкочастотная фильтрация}$), так и выделения контуров и мелкоразмерных
объектов ($\textit{высокочастотная фильтрация}$). Как видно из рис. 17, 19, по мере нарастания "мощности" фильтрации в низкочастотной
составляющей изображения все сильнее проявляется эффект "кажущейся расфокусировки" или
$\it{размытия}$ изображения. В то же время в высокочастотную составляющую, где в начале
наблюдаются лишь контура объектов, постепенно переходит большая часть
информационного содержания изображения (рис. 18, 20 - 22). Рассмотрим теперь поведение высокочастотных и низкочастотных фильтров
(рис. 23 - 28)
в присутствии аддитивного гауссовского шума на изображении (рис. 7). Как видно из рис. 23, 25, свойства низкочастотных фильтров по
подавлению аддитивной случайной помехи аналогичны свойствам ранее
рассмотренных линейных фильтров - при достаточной мощности фильтра помехи
подавляются, однако платой за это является сильное размытие контуров и
"расфокусировка" всего изображения. Высокочастотная составляющая
зашумленного изображения перестает быть информативной, так как помимо
контурной и объектовой информации там теперь также полностью присутствует и
шумовая компонента (рис. 27, 28). Применение частотных методов наиболее целесообразно в случае, когда известны
статистическая модель шумового процесса или/и оптическая передаточная
функция канала передачи изображения. Учесть такие априорные данные удобно,
выбрав в качестве восстанавливающего фильтра обобщенный управляемый
(параметрами $\sigma$ и $\mu$) фильтр следующего вида: $$
F(w_1,w_2)=
\left[
{ \frac
{1}
{P(w_1,w_2)}
}\right]
\cdot
\left[
{\frac
{{\vert P(w_1,w_2) \vert }^2}
{\vert P(w_1,w_2) \vert ^2 + \alpha \vert Q(w_1,w_2) \vert ^2}
}\right].
$$ где $0 < \sigma < 1$, $0 < \mu < 1$ - назначаемые параметры фильтра,
$P(w_{1}$, $w_{2})$ - передаточная функция системы, $Q(w_{1}$, $w_{2})$ -
стабилизатор фильтра, согласованный с энергетическим спектром фона. Выбор
параметров $\sigma = 1$, $\mu = 0$ приводит к чисто инверсной фильтрации,
$\sigma =\mu = 1$ к \it{винеровской фильтрации}, что позволяет получить изображение, близкое к
истинному в смысле минимума СКО при условии, что спектры
плотности мощности
изображения и его шумовой компоненты априорно известны. Для дальнейшего
улучшения эффекта сглаживания в алгоритм линейной (винеровской) фильтрации
вводят адаптацию, основанную на оценке локальных статистик: математического
ожидания $M(P)$ и дисперсии $\sigma (P)$. Этот алгоритм эффективно фильтрует
засоренные однородные поверхности (области) фона. Однако при попадании в
скользящее окно обработки неоднородных участков фона импульсная
характеристика фильтра сужается ввиду резкого изменения локальных статистик,
и эти неоднородности (контуры, пятна) передаются практически без
расфокусировки, свойственной неадаптивным методам линейной фильтрации. К достоинствам методов линейной фильтрации следует отнести их ясный
физический смысл и простоту анализа результатов. Однако при резком ухудшении
соотношения сигнал/шум, при возможных вариантах площадного зашумления и
наличии высокоамплитудного импульсного шума линейные методы предварительной
обработки могут оказаться недостаточными. В этой ситуации значительно более
мощными оказываются нелинейные методы. Многие сигналы удобно анализировать, раскладывая их на синусоиды (гармоники). Тому есть несколько причин. Например, подобным образом работает человеческое ухо. Оно раскладывает звук на отдельные колебания различных частот. Кроме того, можно показать, что синусоиды являются «собственными функциями» линейных систем (т.к. они проходят через линейные системы, не изменяя формы, а могут изменять лишь фазу и амплитуду). Еще одна причина в том, что теорема Котельникова формулируется в терминах спектра сигнала. Преобразование Фурье (Fourier transform)– это разложение функций на синусоиды (далее косинусные функции мы тоже называем синусоидами, т.к. они отличаются от «настоящих» синусоид только фазой). Существует несколько видов преобразования Фурье.
1.
Непериодический непрерывный сигнал можно разложить в интеграл Фурье.
2.
Периодический непрерывный сигнал можно разложить в бесконечный ряд Фурье.
3.
Непериодический дискретный сигнал можно разложить в интеграл Фурье.
4.
Периодический дискретный сигнал можно разложить в конечный ряд Фурье.
Компьютер способен работать только с ограниченным объемом данных, следовательно, реально он способен вычислять только последний вид преобразования Фурье. Рассмотрим его подробнее. Пусть дискретный сигнал x
имеет периодN
точек. В этом случае его можно представить в виде конечного ряда (т.е. линейной комбинации) дискретных синусоид: 2π
k
(n
+
ϕ
k
) x
=
∑
C
k
cos (ряд Фурье) k =
0
Эквивалентная запись (каждый косинус раскладываем на синус и косинус, но теперь – без фазы): 2
π
kn 2
π
kn x
=
∑
A
k
cos +
∑
B
k
sin (ряд Фурье) k =
0
k =
0
Рис. 6
. Базисные функции ряда Фурье для 8-точеченого дискретного сигнала. Слева – косинусы, справа – синусы. Частоты увеличиваются сверху вниз. Базисные синусоиды имеют кратные частоты. Первый член ряда (k
=0) – это константа, называемаяпостоянной составляющей
(DC offset
) сигнала. Самая первая синусоида (k
=1) имеет такую частоту, что ее период совпадает с периодом самого исходного сигнала. Самая высокочастотная составляющая (k
=N
/2) имеет такую частоту, что ее период равен двум отсчетам. КоэффициентыA
k
и B
k
называютсяспектром
сигнала (spectrum
). Они показывают амплитуды си- нусоид, из которых состоит сигнал. Шаг по частоте между двумя соседними синусоидами из разложения Фурье называется частотным разрешением
спектра. На рис. 6 показаны синусоиды, по которым происходит разложение дискретного сигнала из 8 точек. Каждая из синусоид состоит из 8 точек, то есть является обычным дискретным сигналом. Непрерывные синусоиды показаны на рисунке для наглядности. вить исходный сигнал, вычислив сумму ряда Фурье в каждой точке. Разложение сигнала на синусоиды (т.е. получение коэффициентов) называется прямым преобразованием Фурье
. Обратный процесс – синтез сигнала по синусоидам – называетсяобратным преобразованием Фурье
(inverse Fourier transform
). Алгоритм обратного преобразования Фурье очевиден (он содержится в формуле ряда Фурье; для проведения синтеза нужно просто подставить в нее коэффициенты). Рассмотрим алгоритм прямого преобразования Фурье, т.е. нахождения коэффициентов A
k
иB
k
. 2
π
kn 2
π
kn
от аргумента n
является ор- Система функций K
=
0,..., тогональным базисом в пространстве периодических дискретных сигналов с периодом N
. Это значит, что для разложения по ней любого элемента пространства (сигнала) нужно посчитать скалярные произведения этого элемента со всеми функциями системы, и полученные коэффициенты нормировать. Тогда для исходного сигнала будет справедлива формула разложения по базису с коэффициентамиA
k
иB
k
. Итак, коэффициенты A
k
иB
k
вычисляются как скалярные произведения (в не- прерывном случае – интегралы от произведения функций, в дискретном случае – суммы от произведения дискретных сигналов): N −
1
2
π
ki
, приk
=
1,..., A
k=
∑
x
cos −1
N i
=
0
N −
1
A
k=
∑
x
cos2
π
ki
, приk
=
0, N i
=
0
N −
1
2
π
ki NB
0
иB
N
2
всегда равны нулю (т.к. соответствующие им «базисные» сигналы тождественно равны нулю в дискретных точках), и их можно отбросить при вычислении обратного и прямого преобразований Фурье. Итак, мы выяснили, что спектральное представление сигнала полностью эквивалентно самому сигналу. Между ними можно перемещаться, используя прямое и обратное преобразования Фурье. Алгоритм вычисления этих преобразований содержится в приведенных формулах. Вычисление преобразований Фурье требует очень большого числа умножений (около N
2
) и вычислений синусов. Существует способ выполнить эти преобразования значительно быстрее: примерно заN
log2
N
операций умножения. Этот способ называется
быстрым преобразованием Фурье(БПФ,
FFT,
fast Fourier transform). Он основан на том, что среди множителей (синусов) есть много повторяющихся значений (в силу периодичности синуса). Алгоритм БПФ группирует слагаемые с одинаковыми множителями, значительно сокращая число умножений. В результате быстродействие БПФ может в сотни раз превосходить быстродействие стандартного алгоритма (в зависимости от
N). При этом следует подчеркнуть, что алгоритм БПФ является точным. Он даже точнее стандартного, т.к. сокращая число операций, он приводит к меньшим ошибкам округления.
Однако у большинства алгоритмов БПФ есть особенность: они способны работать лишь тогда, когда длина анализируемого сигнала N
является степенью двойки. Обычно это не представляет большой проблемы, так как анализируемый сигнал всегда можно дополнить нулями до необходимого размера. Число N называется
размеромили
длиной БПФ(FFT size).
До сих пор мы рассматривали ДПФ от действительных сигналов. Обобщим теперь ДПФ на случай комплексных сигналов. Пусть x
, n
=0,…,N
-1 – исходный комплексный сигнал, состоящий изN
комплексных чисел. ОбозначимX
, k
=0,…N
-1 – его комплексный спектр, также состоящий изN
комплексных чисел. Тогда справедливы следующие формулы прямого и обратного преобразо- ваний Фурье (здесь j
=
−
1): N −
1
X [
k]
=
∑
x[
n]
e−
jnk
(2
π
N
)
n=
0
N −
1
∑
X
[
k
]
e
jnk(2
π
N)
N k
=
0
Если по этим формулам разложить в спектр действительный сигнал, то первые N
/2+1 комплексных коэффициентов спектра будут совпадать со спектром «обычного» действительного ДПФ, представленным в «комплексном» виде, а остальные коэффициенты будут их симметричным отражением относительно Обозначим через двумерное поле (двумерный
сигнал), описывающее дискретное изображение размера строк и столбцов. Вне указанных границ
этот сигнал не определен. Выполним периодическое продолжение данного
финитного сигнала, введя двумерный периодический сигнал Если сигнал существует только внутри
прямоугольника со
сторонами элементов
(рис. 3.4.а), то сигнал определен на всей плоскости и является на ней прямоугольно-периодическим
(рис. 3.4.б). Рис. 3.4. Реальное (а) и
периодически продолженное (б) изображения Любой периодический сигнал может
быть представлен в виде ряда Фурье, но, в отличие от одномерных
сигналов, двумерные описываются двумерным рядом Фурье, имеющим вид: Базисные функции этого двумерного
представления - двумерные комплексные экспоненты (иногда называемые
комплексными синусоидами) имеющие, как и сигнал , прямоугольную
периодичность с тем же периодом . Здесь (,) - двумерный номер базисной функции, а
величины имеют
смысл пространственных частот. Иногда пространственными частотами называют
целочисленные величины и . Коэффициенты
Фурье ряда
(3.22) образуют двумерный частотный спектр сигнала и определяются формулой прямого
преобразования Фурье: Выражение (3.22),
восстанавливающее сигнал по его спектру , является обратным
преобразованием Фурье. В справедливости преобразований (3.22) и (3.24),
называемых двумерным ДПФ, можно убедиться, подставив (3.24) в (3.22) и
приведя правую часть полученного равенства к значению левой, т.е. к . Заметим, что для точного
представления дискретного сигнала с двумерным периодом элементов согласно
формулам БПФ достаточно конечного числа базисных функций (3.23) - ряд (3.22)
является конечным. Это и понятно, поскольку сам представляемый сигнал
содержит в одном периоде конечное число точек, т.е. имеет конечное число
степеней свободы. Ясно, что число степеней свободы в спектре не может
отличаться от числа степеней свободы в самом сигнале. Остановимся на наиболее
существенных свойствах двумерного дискретного спектра Фурье. Вычислим
спектральные коэффициенты (3.24) в частотных точках Поскольку при любых целых
значениях и
последний
множитель в полученном выражении равен единице, то отсюда имеем равенство: означающее прямоугольную
периодичность двумерного ДПФ. Следовательно, картина двумерного ДПФ подобна
картине двумерного периодически продолженного сигнала, качественно показанной
на рис. 3.4.б (если на ней пространственные координаты заменить частотными ). Однако необходимо
иметь в виду, что спектральные коэффициенты , как это следует из (3.24), являются комплексными
числами, в том числе и при вещественном сигнале . Но тогда возникает вопрос.
Общее количество спектральных компонент, как установлено, равно . Комплексное число
эквивалентно паре вещественных чисел - действительной и мнимой частям при
алгебраическом или модулю и фазе при экспоненциальном представлении.
Следовательно, полный спектр описывается вещественными числами, что вдвое
превышает размерность самого сигнала . В этом, на первый взгляд, содержится
противоречие. Оно находит свое разъяснение при дальнейшем изучении свойств
двумерного ДПФ. Преобразуем соотношение (3.25)
следующим образом. Во-первых, вместо частот подставим частоты . Во-вторых, выполним
комплексное сопряжение обеих частей, что не нарушит равенства. В результате
нетрудно получить выражение: которым устанавливается
однозначная связь между спектральными коэффициентами в двух различных точках
спектрального прямоугольника . Полученным соотношением и снимается
противоречие, поскольку количество независимых спектральных коэффициентов
уменьшается благодаря данной спектральной симметрии в два раза. Согласно
установленному свойству, спектрально-сопряженной зависимостью связаны между
собой спектральные коэффициенты, принадлежащие левому верхнему и правому
нижнему углам прямоугольника . Аналогично также связаны между собой
коэффициенты Фурье из правого верхнего и левого нижнего участков спектрального
прямоугольника . В заключение данного пункта
укажем, что при практическом применении двумерного ДПФ - как прямого, так и
обратного, совсем не требуется оперировать периодическими сигналами и
спектрами, как это предполагается, казалось бы, преобразованиями (3.22) и
(3.24). От этой необходимости избавляют сами соотношения (3.22) и (3.24). В
самом деле, прямое преобразование Фурье (3.24) содержит в правой части значения
периодически продолженного сигнала лишь в пределах одного “главного” прямоугольника . Но в этих пределах
исходный и
периодически продолженный сигналы полностью совпадают, что дает
возможность использовать в формуле (3.24) исходный сигнал . Аналогичные пояснения можно
сделать и относительно обратного преобразования (3.22), откуда следует, что
практически в процессе вычислений оперировать следует “основным”
участком спектра, относящимся к спектральной области . Из сделанных пояснений, имеющих
лишь исключительно вычислительное значение, не следует делать вывода об
искусственности и ненужности рассмотренных математических моделей периодических
полей. При обработке изображений возникают многочисленные задачи, правильное
толкование и решение которых возможно только на основе этих математических
интерпретаций. Одной из таких важнейших задач является цифровая двумерная
фильтрация в спектральной области, осуществление которой связано с выполнением
так называемой циклической свертки. Пусть f
(x
1 , x
2) – функция двух переменных. По аналогии с одномерным преобразованием Фурье можно ввести двумерное преобразование Фурье: Функция при фиксированных значениях ω 1 , ω 2 описывает плоскую волну в плоскости x
1 , x
2 (рисунок 19.1). Величины ω 1 , ω 2 имеют смысл пространственных частот и размерность мм
−1 , а функция F(ω 1 , ω 2) определяет спектр пространственных частот. Сферическая линза способна вычислять спектр оптического сигнала (рисунок 19.2). На рисунке 19.2 введены обозначения: φ - фокусное расстояние, Рисунок 19.1 – К определению пространственных частот Двумерное преобразование Фурье обладает всеми свойствами одномерного преобразования, кроме того отметим два дополнительных свойства, доказательство которых легко следует из определения двумерного преобразования Фурье. Рисунок 19.2 – Вычисление спектра оптического сигнала с использованием Факторизация
. Если двумерный сигнал факторизуется, то факторизуется и его спектр: Радиальная симметрия
. Если двумерный сигнал радиально-симметричен, то есть Где – функция Бесселя нулевого порядка. Формулу, определяющую связь между радиально-симметричным двумерным сигналом и его пространственным спектром называют преобразованием Ганкеля. ЛЕКЦИЯ 20. Дискретное преобразование Фурье. Низкочастотный фильтр
Прямое двумерное дискретное преобразование Фурье (ДПФ) преобразует изображение, заданное в пространственной координатной системе (x, y
), в двумерное дискретное преобразование изображения, заданное в частотной координатной системе (u,v
): Обратное дискретное преобразование Фурье (ОДПФ) имеет вид: Видно, что ДПФ является комплексным преобразованием. Модуль этого преобразования представляет амплитуду спектра изображения и вычисляется как корень квадратный из суммы квадратов действительной и мнимой частей ДПФ. Фаза (угол сдвига фазы) определяется как арктангенс отношения мнимой части ДПФ к действительной. Энергетический спектр равен квадрату амплитуды спектра, или сумме квадратов мнимой и действительной частей спектра. Теорема о свертке
В соответствии с теоремой о свертке, свертка двух функций в пространственной области может быть получена ОДПФ произведения их ДПФ, то есть Фильтрация в частотной области позволяет по ДПФ изображения подобрать частотную характеристику фильтра, обеспечивающую необходимое преобразование изображения. Рассмотрим частотные характеристики наиболее распространенных фильтров. Преобразование Фурье
– это семейство математических методов, основанных на разложении исходной непрерывной функции от времени на совокупность базисных гармонических функций (в качестве которых выступают синусоидальные функции) различной частоты, амплитуды и фазы. Из определения видно, что основная идея преобразования заключается в том, что любую функцию можно представить в виде бесконечной суммы синусоид, каждая из которых будет характеризоваться своей амплитудой, частотой и начальной фазой. Преобразование Фурье является основоположником спектрального анализа. Спектральный анализ – это способ обработки сигналов, который позволяет охарактеризовать частотный состав измеряемого сигнала. В зависимости от того, каким образом представлен сигнал, используют разные преобразования Фурье. Различают несколько видов преобразования Фурье: – Непрерывное преобразование Фурье (в англоязычной литературе Continue Time Fourier Transform – CTFT
или, сокращенно, FT
); – Дискретное преобразование Фурье (в англоязычной литературе Discrete Fourier Transform – DFT
); – Быстрое преобразование Фурье (в англоязычной литературе Fast Fourier transform – FFT
). Непрерывное преобразование Фурье
Преобразование Фурье является математическим инструментом, применяемым в различных научных областях. В некоторых случаях его можно использовать как средство решения сложных уравнений, описывающих динамические процессы, которые возникают под воздействием электрической, тепловой или световой энергии. В других случаях оно позволяет выделять регулярные составляющие в сложном колебательном сигнале, благодаря чему можно правильно интерпретировать экспериментальные наблюдения в астрономии, медицине и химии. Непрерывное преобразование фактически является обобщением рядов Фурье при условии, что период разлагаемой функции устремить к бесконечности. Таким образом, классическое преобразование Фурье имеет дело со спектром сигнала, взятым во всем диапазоне существования переменной. Существует несколько видов записи непрерывного преобразования Фурье, отличающихся друг от друга значением коэффициента перед интегралом (две формы записи): где и - Фурье-образ функцииили частотный спектр функции ; Следует отметить, что разные виды записи встречаются в различных областях науки и техники. Нормировочный коэффициент необходим для корректного масштабирования сигнала из частотной области во временную. Нормировочный коэффициент уменьшает амплитуду сигнала на выходе обратного преобразования для того чтобы она совпадала с амплитудой исходного сигнала. В математической литературе прямое и обратное преобразование Фурье умножаются на множитель , в то время как в физике чаще всего при прямом преобразовании множитель не ставят, а при обратном ставят множитель . Если последовательно рассчитать прямое преобразование Фурье некоторого сигнала, а после взять обратное преобразование Фурье, то результат обратного преобразования должен полностью совпадать с исходным сигналом. Если функция нечетная на интервале (−∞, +∞), то преобразование Фурье может быть представлено через синус-функцию: Если функция четная на интервале (−∞, +∞), то преобразование Фурье может быть представлено через косинус-функцию: Таким образом, непрерывное преобразование Фурье позволяет представить непериодическую функцию в виде интеграла функции, представляющей в каждой своей точке коэффициент ряда Фурье для непериодической функции. Преобразование Фурье является обратимым, то есть если по функции был рассчитан ее Фурье-образ , то по Фурье-образу можно однозначно восстановить исходную функцию . Под обратным преобразованием Фурье понимают интеграл вида (две формы записи): где - Фурье-образ функцииили частотный спектр функции ; Если функция нечетная на интервале (−∞, +∞), то обратное преобразование Фурье может быть представлено через синус-функцию: Если функция четная на интервале (−∞, +∞), то обратное преобразование Фурье может быть представлено через косинус-функцию: В качестве примера, рассмотрим следующую функцию Поскольку функция является четной функцией, то непрерывное преобразование Фурье будет определяться следующим образом: В результате получили зависимость изменения исследуемой экспоненциальной функции на частотном интервале (см. ниже). Непрерывное преобразование Фурье используют, как правило, в теории при рассмотрении сигналов, которые изменяются в соответствии с заданными функциями, но на практике обычно имеют дело с результатами измерений, которые представляют собой дискретные данные. Результаты измерений фиксируются через равные промежутки времени с определённой частотой дискретизации, например, 16000 Гц или 22000 Гц. Однако в общем случае дискретные отсчёты могут идти неравномерно, но это усложняет математический аппарат анализа, поэтому на практике обычно не применяется. Существует важная теорема Котельникова (в иностранной литературе встречается название «теорема Найквиста-Шеннона», «теорема отсчетов»), которая гласит, что аналоговый периодический сигнал, имеющий конечный (ограниченный по ширине) спектр (0…fmax), может быть однозначно восстановлен без искажений и потерь по своим дискретным отсчётам, взятым с частотой, большей или равной удвоенной верхней частоте спектра - частота дискретизации (fдискр >= 2*fmax). Другими словами, при частоте дискретизации 1000 Гц из аналогового периодического сигнала можно восстановить сигнал с частотой до 500 Гц. Следует отметить, что дискретизация функции по времени приводит к периодизации ее спектра, а дискретизация спектра по частоте приводит к периодизации функции. Это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов. Прямое дискретное преобразование Фурье ставит в соответствие временной функции , которая определена N-точками измерений на заданном временном интервале, другую функцию , которая определена на частотном интервале. Следует отметить, что функция на временном интервале задается с помощью N-отсчетов, а функция на частотном интервале задается с помощью K-кратного спектра. k ˗ индекс частоты. Частота k-го сигнала определяется по выражению где T - период времени, в течение которого брались входные данные. Прямое дискретное преобразование может быть переписано через вещественную и мнимую составляющие. Вещественная составляющая представляет собой массив, содержащий значения косинусоидальных составляющих, а мнимая составляющая представляет собой массив, содержащий значения синусоидальных составляющих. Из последних выражений видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от одного колебания за период до N колебаний за период. Дискретное преобразование Фурье имеет особенность, так как дискретная последовательность может быть получена суммой функций с различным составом гармонического сигнала. Другими словами, дискретная последовательность раскладывается на гармонические переменные – неоднозначно. Поэтому при разложении дискретной функции с помощью дискретного преобразования Фурье во второй половине спектра возникают высокочастотные составляющие, которых не было в оригинальном сигнале. Данный высокочастотный спектр является зеркальным отображением первой части спектра (в части частоты, фазы и амплитуды). Обычно вторая половина спектра не рассматривается, а амплитуды сигнала первой части спектра - удваиваются. Следует отметить, что разложение непрерывной функции не приводит к появлению зеркального эффекта, так как непрерывная функция однозначно раскладывается на гармонические переменные. Амплитуда постоянной составляющей является средним значением функции за выбранный промежуток времени и определяется следующим образом: Амплитуды и фазы частотных составляющих сигнала определяются по следующим соотношениям: Полученные значения амплитуды и фазы называют полярным представлением (polar notation). Результирующий вектор сигнала будет определяться следующим образом: Рассмотрим алгоритм преобразования дискретно заданной функции на заданном интервале (на заданном периоде) с количеством исходных точек Д
искретное преобразование Фурье В результате преобразования получаем вещественное и мнимое значение функции , которая определена на частотном диапазоне. Обратное дискретное преобразование Фурье ставит в соответствие частотной функции , которая определена K-кратным спектром на частотном интервале, другую функцию , которая определена на временном интервале. N ˗ количество значений сигнала, измеренных за период, а также кратность частотного спектра; k ˗ индекс частоты. Как уже было сказано, дискретное преобразование Фурье N-точкам дискретного сигнала ставит в соответствие N-комплексных спектральных отсчетов сигнала . Для вычисления одного спектрального отсчета требуется N операций комплексного умножения и сложения. Таким образом, вычислительная сложность алгоритма дискретного преобразования Фурье является квадратичной, другими словами требуется операций комплексного умножения и сложения.Комплексное представление преобразования Фурье.
Быстрое преобразование Фурье.
Двумерное преобразование Фурье.
Свертка с использованием преобразования Фурье.
Фильтрация изображений в частотной области.
Преобразования Фурье
ДПФ вещественного сигнала
Комплексное ДПФ
. (3.21)
(3.23)
(3.24)
:
,
,
сферической линзы
или 
- круговая частота.
или 
- круговая частота.
. График исследуемой экспоненциальной функции представлен ниже.
