Дискретне у часі перетворення фур'є. Перетворення Фур'є
Лінійна фільтраціязображень може здійснюватися як у просторовій, так і частотній області. При цьому вважається, що "низьким" просторовим частотам відповідає основний зміст зображення - фон та великорозмірні об'єкти, а "високим" просторовим частотам - дрібнорозмірні об'єкти, дрібні деталі. великих формта шумова компонента.
Традиційно для переходу в область просторових частот використовуються методи, засновані на $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 (Nlog 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)$. Этот алгоритм эффективно фильтрует
засоренные однородные поверхности (области) фона. Однако при попадании в
скользящее окно обработки неоднородных участков фона импульсная
характеристика фильтра сужается ввиду резкого изменения локальных статистик,
и эти неоднородности (контуры, пятна) передаются практически без
расфокусировки, свойственной неадаптивным методам линейной фильтрации. До переваг методів лінійної фільтрації слід віднести їх ясний фізичний зміст і простоту аналізу результатів. Однак при різкому погіршенні співвідношення сигнал/шум, при можливих варіантах площадного зашумлення і високопульсного імпульсного шуму лінійні методи попередньої обробки можуть виявитися недостатніми. У цій ситуації значно потужнішими виявляються нелінійні методи. Нехай 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): Зворотне дискретне перетворення Фур'є (ОДПФ) має вигляд: Видно, що ДПФ є комплексним перетворенням. Модуль цього перетворення представляє амплітуду спектра зображення і обчислюється як квадратний корінь із суми квадратів дійсної і уявної частин ДПФ. Фаза (кут зсуву фази) визначається як арктангенс відношення уявної частини ДПФ до дійсної. Енергетичний спектр дорівнює квадрату амплітуди спектра, або сумі квадратів уявної та дійсної частин спектру. Теорема про пакунок Відповідно до теореми про згортку, згортка двох функцій у просторовій області може бути отримана ОДПФ твори їх ДПФ, тобто Фільтрація в частотній ділянці дозволяє за ДПФ зображення підібрати частотну характеристику фільтра, що забезпечує необхідне перетворення зображення. Розглянемо частотні характеристики найпоширеніших фільтрів. Перетворення Фур'є При використанні перетворень Фур'є зображення подається у вигляді суми складних показових функцій змінних амплітуди, частоти та фази. Перетворення Фур'є відіграє дуже важливу роль у багатьох областях обробки зображень, включаючи покращення, аналіз, відновлення та стиснення. Основні визначення перетворення Фур'є Якщо ƒ(m,n)є функцією двох дискретних просторових змінних m і n, тоді двовимірне перетворення Фур'є функції ƒ(m,n)може бути представлено наступним виразом Змінні є кутовими частотами. Таким чином, є функцією ƒ(m,n)у частотній області. є комплекснозначною функцією з відповідними частотами. Частоти перебувають у межах діапазону , . Відмітимо, що F(0,0) подається у вигляді суми всіх змінних ƒ(m,n). З цієї причини F(0,0) часто називають постійною складовою перетворення Фур'є. Зворотне двовимірне перетворення Фур'є є виразом Тобто. цей вираз представляє ƒ(m,n)як суми нескінченного числа складних експоненційних функцій (синусоїд) з різними частотами. Амплітуда і фаза визначають внесок частот у виставу. Візуалізація Фур'є-перетворення При ілюстрації Фур'є-перетворення припустимо, що функція ƒ(m,n)дорівнює 1 і представлена у вигляді прямокутника. Для спрощення діаграми, функція ƒ(m,n)буде представлятися безперервною функцією двох дискретних змінних mі n. На малюнку внизу з використанням функції mesh візуалізовано значення амплітуд, які отримані при перетворенні Фур'є прямокутної функції, представленої на попередньому малюнку. Візуалізацію амплітуди ще називають візуалізацією перетворень Фур'є. Пік функції знаходиться в центрі та відображає значення F(0,0), яке є сумою всіх значень ƒ(m,n). Всі інші складові є розподілом енергії по вертикальним і горизонтальним частотам. Інший шлях візуалізації Фур'є-перетворення полягає у відображенні значень у вигляді зображення. Розглянемо приклади перетворення Фур'є функцій різних простих форм. Дискретне косинусне перетворення Дискретні косинусні перетворення являють зображення у вигляді суми синусоїд з різною амплітудою та частотою. Функція dct2 у програмі Image Processing Toolbox реалізує двовимірні дискретні косинусні перетворення зображень. Одна з особливостей дискретного перетворення Фур'є у тому, деякі локальні ділянки зображення можна охарактеризувати невеликою кількістю коефіцієнтів дискретного перетворення Фур'є. Ця властивість часто використовується при розробці методів стиснення зображень. Наприклад, дискретне косинусне перетворення є основою міжнародного стандарту, який використовується в алгоритмі стиснення зображень із втратами JPEG. Назва формату "JPEG" складається з перших букв назви робочої групи, яка брала участь у розробці цього стандарту (Joint Photographic Experts Group). Двовимірне дискретне косинусне перетворення матриці Aз розмірами реалізується згідно з таким виразом Значення B pqназивають коефіцієнтами дискретного косинусного перетворення матриці A. (Слід зазначити, що індекси матриці в MATLAB завжди починаються з 1, а не з 0. Тому елементи матриці, які представлені в MATLAB як A(1,1) та B(1,1), будуть відповідати елементам A 00і B 00із наведеної вище формули.) Зворотне дискретне косинусне перетворення реалізується згідно з виразами Вираз зворотного дискретного косинусного перетворення може інтерпретуватися як подання матриці Aз розмірами у вигляді суми наступних функцій Ці функції називаються основними (базовими) функціями дискретного косинусного перетворення. Коефіцієнти дискретного косинусного перетворення B pqможна розглядати як вагові за кожної базової функції. Наприклад, для матриці з розміром елементів існує 64 базові функції, що показано на зображенні. Горизонтальні частоти збільшуються ліворуч, а вертикальні – зверху вниз. Матриця дискретних косинусних перетворень Image Processing Toolbox пропонує два різні шляхи реалізації дискретних косинусних перетворень. Перший метод реалізований функції dct2. Функція dct2 використовує швидке перетворення Фур'є для прискорення обчислень. Другий метод використовує матрицю дискретних косинусних перетворень, яка повертається функцією dctmtx. Матриця перетворень T формується згідно з наступним виразом Для матриці Aз розмірами є матрицею з розмірами , де кожен стовпець містить одномірне дискретне косинусне перетворення A. Двовимірне дискретне косинусне перетворення Aобчислюється як B=T*A*T'. Зворотне двовимірне дискретне косинусне перетворення Bобчислюється як T'*B*T. Дискретні косинусні перетворення та стиснення зображень В алгоритмі стиснення зображень JPEG вихідне зображення поділяється на блоки розмірів або елементів. Далі для кожного блоку обчислюється двовимірне косинусне дискретне перетворення. Коефіцієнти дискретних косинусних перетворень квантуються, кодуються та передаються. Одержувач JPEG даних декодує коефіцієнти дискретного косинусного перетворення, обчислює зворотне двовимірне дискретне косинусне перетворення в кожному блоці і далі поєднує їх разом в одне зображення. Розглянемо приклад обчислення двовимірних дискретних косинусних перетворень у блоках із розмірами елементів вихідного зображення. Далі при реконструкції зображення враховуватимемо лише 10 коефіцієнтів з кожного блоку, решту прирівняємо до нуля. При проведенні описаних обчислень використовуватиметься також матриця перетворень. I = imread("cameraman.tif"); I = im2double(I); T = dctmtx(8); B = blkproc(I,,"P1*x*P2",T,T"); mask = ; B2 = blkproc(B,,"P1.*x",mask); *x*P2",T",T); imshow(I); figure, imshow(I2) На малюнку представлено два зображення – вихідне та реконструйоване. При реконструкції зображення використовувалося лише 15% коефіцієнтів дискретних косинусних перетворень. Однак, слід зазначити, що якість реконструйованого зображення є досить прийнятною. Для перегляду інших властивостей дискретного косинусного перетворення див. функцію dctdemo. Перетворення Радону Функція radon у програмі Image Processing Toolbox обчислює матрицю проекцій зображення вздовж заданих напрямків. Проекція двовимірної функції f(x,y) дорівнює інтегралу вздовж зазначеної лінії. Функція Радона є обчисленням проекцій зображення на осі, які задаються кутами в градусах щодо горизонталі проти годинникової стрілки. На малюнку показано проекцію деякої фігури під вказаним кутом На малюнку внизу показані горизонтальні та вертикальні проекції для простої двовимірної функції. Проекції можуть обчислюватися вздовж довільного кута theta. Вбудована у програму Image Processing Toolbox функція radon обчислює проекції зображення вздовж певних напрямків. Проекція двовимірної функції f(x,y) на вісь x' є лінійним інтегралом. Таким чином, осі x’ y’ задаються поворотом на кут проти годинникової стрілки. На зображенні знизу проілюстровано геометрію перетворення Радона. Візуалізація перетворень Радону При проведенні перетворень Радону необхідно вказати вихідне зображення та вектор кутів theta. Radon (I, theta); Rє матрицею, в якій кожен стовпець є перетворенням Радону для одного з кутів, який міститься у векторі theta. Вектор xp містить відповідні координати вздовж осі x. Центральний піксель I визначається згідно з виразом floor((size(I)+1)/2). Розглянемо, як у перетвореннях Радона обчислюються проекції. Розглянемо проекції під кутом 0 і 45 °. I = zeros (100,100); I(25:75, 25:75) = 1; imshow(I) Radon(I,); figure; plot(xp,R(:,1)); title("R_(0^o) (x\prime)") Перетворення Радону за 0° Figure; plot(xp,R(:,2)); title("R_(45^o) (x\prime)") Перетворення Радона при великій кількості кутів часто відображається у вигляді зображення. У цьому прикладі розглянуто перетворення Радона для зображення у вигляді квадрата при діапазоні кутів від 0 до 180 з дискретністю 1. Theta = 0: 180; = Radon (I, theta); imagesc(theta, xp, R); title("R_(\theta) (X\prime)"); xlabel("theta (degrees)"); ylabel("X\prime"); set(gca, "XTick", 0:20: 180); colormap(hot); colorbar Використання перетворень Радону при детектуванні ліній Перетворення Радона аналогічні до інших відомих операцій, які відомі як перетворення Хоха. Функцію radon можна використовувати для визначення прямих ліній. Розглянемо основні етапи цього процесу. Найбільший пік у матриці Rвідповідає = 1 ° і x '= -80. З центру вихідного зображення проводиться лінія під кутом на відстань x'. Перпендикулярно до цієї лінії проводиться пряма, яка відповідає прямій вихідному зображенні. Крім того, на зображенні присутні інші лінії, які представлені в матриці Rвідповідними піками. Це одне з перетворень Фур'є, що широко застосовуються в алгоритмах цифрової обробки сигналів (його модифікації застосовуються в стисненні звуку в MP3, стисненні зображень в JPEG та ін), а також в інших областях, пов'язаних з аналізом частот у дискретному (наприклад, оцифрованому аналоговому ) сигнал. Дискретне перетворення Фур'є вимагає як вход дискретну функцію. Такі функції часто створюються шляхом дискретизації (вибірки значень із безперервних функцій). Дискретні перетворення Фур'є допомагають вирішувати приватні диференціальні рівняння та виконувати такі операції, як згортки. Дискретні перетворення Фур'є також активно використовують у статистиці, під час аналізу тимчасових рядів. Перетворення бувають одновимірні, двовимірні і навіть тривимірні. Пряме перетворення: Зворотне перетворення: Позначення: § N- кількість значень сигналу, виміряних у період, і навіть кількість компонент розкладання; § - виміряні значення сигналу (у дискретних часових точках з номерами, які є вхідними даними для прямого перетворення та вихідними для зворотного; § - Nкомплексних амплітуд синусоїдальних сигналів, що становлять вихідний сигнал; є вихідними даними для прямого перетворення та вхідними для зворотного; оскільки амплітуди комплексні, то ними можна обчислити одночасно і амплітуду, і фазу; § - звичайна (речова) амплітуда k-го синусоїдального сигналу; § arg( X k) - фаза k-го синусоїдального сигналу (аргумент комплексного числа); § k- Частота k-го сигналу, рівна , де T- Період часу, протягом якого бралися вхідні дані. З останнього видно, що перетворення розкладає сигнал на синусоїдальні складові (які називаються гармоніками) з частотами N коливань за період до одного коливання за період. Оскільки частота дискретизації як така дорівнює N відрахунків у період, то високочастотні складові неможливо знайти коректно відображені - виникає муаров ефект. Це призводить до того, що друга половина N комплексних амплітуд, фактично, є дзеркальним відображенням першої і не несе додаткової інформації. Розглянемо деякий періодичний сигнал x(t) З періодом рівним T. Розкладемо його в ряд Фур'є: Проведемо дискретизацію сигналу те щоб на періоді було N відліків. Дискретний сигнал подаємо у вигляді відліків: x n = x(t n), де , Тоді ці відліки через ряд Фур'є запишуться наступним чином: Використовуючи співвідношення: , отримуємо: Таким чином, ми отримали зворотне дискретне перетворення Фур'є. Помножимо тепер скалярний вираз для x nна та отримаємо: Тут використані: а) вираз для суми кінцевого числа членів (експонент) геометричної прогресії; б) вираз символу Кронекера як межі відношення функцій Ейлера для комплексних чисел. Звідси слідує що: Ця формула описує пряме дискретне перетворення Фур'є. У літературі прийнято писати множник у зворотному перетворенні, і тому зазвичай пишуть формули перетворення у такому вигляді: Дискретне перетворення Фур'є є лінійним перетворенням, яке переводить вектор тимчасових відрахунків у вектор спектральних відліків тієї ж довжини. Таким чином, перетворення може бути реалізоване як множення квадратної матриці на вектор: У радіотехніці часто застосовується поняття згортки двох сигналів. Так, наприклад, сигнал на виході чотириполюсника можна знайти за допомогою згортки вхідного сигналу та імпульсної характеристики чотириполюсника. Оскільки були розглянуті дискретні та цифрові сигнали, то визначимо поняття згортки для дискретних сигналів, або дискретний пакунок. Нехай є дискретний сигнал х Д (t), Що складається з Nвідліків х до, і дискретний сигнал у д (Г), що складається з Nвідліків у до,тоді дискретним пакункомцих двох сигналів називається сигнал z A(t), для котрого Дискретні сигнали набули широкого поширення при створенні систем з імпульсною модуляцією. Пристрій дискретизації в найпростішому випадку являє собою каскад (ключ), що стробується, відкривається на час т ііз періодом А (рис. 4.7). Мал. 4. Інтервал дискретизації може бути постійним (рівномірна дискретизація) або змінним (адаптивна дискретизація). Найбільш поширеною формою дискретизації є рівномірна, основу якої лежить теорема Котельникова. Імпульсний модуляторце пристрій з двома входами, на один з яких подається аналоговий сигнал, а на другий надходять короткі синхронізуючі імпульси з періодом повторення А. При цьому в момент надходження синхроімпульсу відбувається вимір миттєвого значення сигналу лс(г). На виході модулятора виникає послідовність імпульсів, кожен із яких має площу, пропорційну відповідному відлікового значення аналогового сигналу (рис. 4.7). Сигнал Хмпн ( t) на виході імпульсного модулятора називають модульованою імпульсною послідовністю(МІП). Математично МІП записується так а спектральна щільність МІПвиражається через спектральну густину аналогового сигналу наступним чином: Модель дискретного сигналу передбачає, що відлікові значення аналогового сигналу можна отримати в необмеженому числі точок на осі часу. Практично обробка завжди ведеться на кінцевому інтервалі часу. Розглянемо особливості спектрального подання дискретного сигналу, заданого на інтервалі своїми відліками x 0, x x, ..., x N _ x.Повна кількість відліків N - Т/А. Методика вивчення таких дискретних сигналів у тому, що отримана вибірка отсчетных значень подумки повторюється нескінченне число раз. Через війну сигнал стає періодичним (рис. 4.8). Зіставивши такому сигналу математичну модель, можна скористатися розкладанням у ряді Фур'є і знайти відповідні амплітудні коефіцієнти. Сукупність цих коефіцієнтів утворює спектр дискретного періодичного сигналу. Мал. 4.8. Запишемо модель обмеженого періодичного сигналу у вигляді послідовності дельта-імпульсів: Розкладемо сигнал ХМІП (0 в ряд Фур'є: тут заміна змінних? = f / А. Остаточно отримуємо Ця формула визначає послідовність коефіцієнтів, що утворюють дискретне перетворення Фур'є
(ДПФ) аналізованого сигналу. ДПФ має такі властивості:
1. ДПФ є лінійне перетворення, тобто якщо z k = а х до + /? у до,то З "Z П ~ ^ С Х п Р Су п . 2. Число різних коефіцієнтів Cq,Ci,...,C n _i дорівнює числу Nвідліків за період, при n = Nкоефіцієнт C N= З 0. 3. З 0 є середнім значенням усіх відліків З 0 = - хдо. N до=о iy/i=0 ДПФ застосовується для обчислення спектрів функцій, заданих таблицями або графіками, обробки експериментальних даних, знаходження сигналу на виході дискретного фільтра тощо. Якщо на основі відліків x 0 ,x l ,...,x N _ lдеякого сигналу знайдено коефіцієнти ДПФ C 0 ,Ci,... 9 C n/2 , то ними можна відновити аналоговий сигнал з обмеженим спектром x(t).Ряд Фур'є такого сигналу має вигляд (при парному N)
де | Q | - модуль коефіцієнтів ДПФ; = arg - фазовий кут (аргумент) коефіцієнтів ДПФ Частота першої гармоніки: f= -/ в = - = -/i- непарному Nостанній доданок у формулі (4.17) дорівнює: Для обчислення дискретних відліків х доза наявними коефіцієнтами ДПФ існує така формула: Ця формула має назву зворотного дискретного перетворення Фур'є (ОДПФ)Комплексне уявлення перетворення Фур'є.
Швидке перетворення Фур'є.
Двовимірне перетворення Фур'є.
Згортка з використанням перетворення Фур'є.
Фільтрування зображень у частотній області.
сферичної лінзи
Прямокутна функція
Амплітуда зображення прямокутної функції
Логарифмічне подання Фур'є-перетворення прямокутної функції
Приклади Фур'є перетворення функцій різних простих форм
64 базові функції, отримані для матриці з розмірами елементів
Паралельно-променева проекція з кутом повороту theta
Горизонтальна та вертикальна проекції деякої простої функції
Геометрія перетворення Радону
Перетворення Радону за 45°
Перетворення радону з використанням 180 проекцій
Геометрія перетворення Радону при детектуванні прямих ліній
де 
