Transformácia pomocou waveletov

Fourierova analýza poskytuje len globálnu informáciu, ktorá nie je použiteľná na detekovanie kompaktných vzorov. Gabor[19] zaviedol lokálnu aplikáciu Fourierovej analýzy s posúvajúcim sa oknom, dôsledkom čoho vytvoril akúsi časovo-frekvenčnú analýzu. Táto metóda je aplikovateľná len vtedy, keď spojitý čas je nezávislý od frekvencie[44]. Morlet-Grossmannova definícia spojitej wavelet transformácie pre jednorozmerný signál $f(x)\in L^{2}(R)$

$$W(a,b) = \frac{1}{\sqrt{a}}\int_{-\infty}^{\infty}f(x)\psi^{*}(\frac{x-a}{b})dx$$ (3.12)

pričom $z^{*}$ je komplexné združené číslo k $z$, $\psi^{*}$ je analyzujúci wavelet, $a(>0)$ je scale parameter, $b$ je position parameter. Vlastnosti tejto transformácie sú lineárnosť, kovariancia pri posune ( $f(x) \rightarrow f(x-u) \Rightarrow W(a,b)\rightarrow W(a,b-u)$), kovariancia pri dilatácii ( $f(x)\rightarrow f(sx) \Rightarrow W(a,b)\rightarrow s^{-\frac{1}{2}}W(sa,sb)$). Posledná vlastnosť robí wavelet transformáciu vhodnú pre hierarchické štruktúry. Funguje ako matematický mikroskop, vlastnosti transformácie nie sú závislé na zväčšení.
Ako konkrétny príklad waveletu [52]

$$\hat{g} (\omega) = e^{-2\pi^{2}(\nu - \nu_{0}) }$$ (3.13)

je komplexný wavelet, môže byť rozložený na reálnu a imaginárnu časť

$$g_{r} (x) = \frac{1}{\sqrt{2\pi}}e^{-\frac{x^{2}}{2}}cos(2\pi \nu_{0}x)$$ (3.14)

$$g_{i} (x) = \frac{1}{\sqrt{2\pi}}e^{-\frac{x^{2}}{2}}sin(2\pi \nu_{0}x)$$ (3.15)

pričom $\nu_{0}$ je konštanta. Kritérium prijateľnosti je $\nu_{0} > 0.8$. Výstup takejto funkcie je uvedený na obrázkoch 3.1, 3.2.

Obrázok: Výstup reálnej časti

Obrázok: Výstup imaginárnej časti

Pri spracovaní obrazov vzorkovanie je robené v súlade so všeobecne známou Shannonovou teorémou. Diskrétna wavelet transformácia môže byť odvodená z tejto teorémy v prípade, že spracovaný signál má obmedzenú frekvenciu. Digitálnu analýzu získame diskretizáciou vzťahu 3.12. Wavelet funkcia $\psi^{*}(x)$ obyčajne nemá obmedzené frekvenčné pásmo, tým pádom je potrebné potlačiť hodnoty mimo pracovného intervalu, aby sme predišli rozmazaniu signálu. Môžme pracovať vo Fourierovom priestore a vypočítavať transformáciu postupne. Zredukovať počet elementov v jednotlivých krokoch transformácie je možné len pre wavelety s obmedzeným frekvenčným pásmom. Multirezolučná analýza [37] vychádza z množín generovaných interpoláciou pri rôznych rozlíšeniach. Funkcia $f(x)$ je premietnutá v každom kroku $j$ na podmnožinu $V_{j}$. Projekcia je definovaná súčinom prvkov $c_{j}(k)$, $f(x)$ a $\phi(x)$, pričom

$$c_{j}(k) = < f(x), 2^{-j}\phi (2^{-j}(x-k)) >$$ (3.16)

Funkcia $\phi(x)$ je škálovacia funkcia ktorá má vlastnosť

$$\frac{1}{2}\phi(\frac{x}{2}) = \sum_{n}h(n)\phi(x-n)$$ (3.17)

alebo

$$\hat\phi(2\nu) = \hat h(\nu)\hat\phi(\nu),$$ (3.18)

kde $\hat h(\nu)$ je Fourierova transformácia funkcie $\sum_{n}h(n)\delta(x-n)$. Z toho vyplýva, že $\hat h(\nu) = \sum_{n} h(n) e^{-2\pi n\nu}$. Vzťah 3.17 nám umožňuje vypočítať množinu $c_{j+1}(k)$ z množiny $c_{j}(k)$, a to pomocou vzťahu

$$c_{j+1}(k) = \sum_{n} h(n-2k)c_{j}(k)$$ (3.19)

V každom kroku je počet skalárnych súčinov delený dvomi. Krok za krokom je signál vyhladzovaný a informácie sa postupne strácajú. Znovuzískanie informácie je možné použitím spätnej transformácie s príslušnou wavelet funkciou $\psi(x)$, ktorá má vhodné parametre - posun, dilatáciu.

$$\hat\psi(2\nu) = \hat g(\nu)\hat\phi(\nu)$$ (3.20)

Komplementárny podpriestor $w_{j+1}$ k $v_{j+1}$ získame výpočtom skalárnych súčinov $<f(x),2^{-(j+1)}\psi(2^{-(j+1)}x-k) >$ pomocou vzťahu

$$w_{j+1}(k) = \sum_{n}g(n-2k)c_{j}(n)$$ (3.21)

Za účelom získania pôvodných dát [37] využil vlastnosť ortogonálnych waveletov. V [1] bola teória zovšeobecnená pre širšiu triedu filtrov zavedením $\tilde{h}$ a $\tilde{g}$ združených ku $h$ a $g$. Spätná transformácia (obnovenie) je potom daná vzťahom

$$c_{j}(k) = 2\sum_{l}[c_{j+1}(l)\tilde{h}(k+2l) + w_{j+1}(l)\tilde{g}(k+2l)].$$ (3.22)

Aby sme získali korektnú transformáciu musia byť splnené podmienky 3.23(dealiasing) a 3.24(exact restoration).

$$\hat{h}(\nu + \frac{1}{2})\hat{\tilde{h}}(\nu) + \hat{g}(\nu + \frac{1}{2})\hat{\tilde{g}}(\nu) = 0$$ (3.23)

$$\hat{h}(\nu)\hat{\tilde{h}}(\nu) + \hat{g}(\nu)\hat{\tilde{g}}(\nu) = 1$$ (3.24)

Pri dekompozícii sa na funkciu aplikujú filtre $H$(nízke frekvencie) a $G$(vysoké frekvencie). Naopak, pri rekonštrukcii aplikujeme filtre $\tilde{H}$ a $\tilde{G}$. Ortogonálne wavelety zodpovedajú prípadu, keď

$$\hat{g}(\nu) = e^{-2\pi\nu}\hat{h}^{*}(\nu + \frac{1}{2})$$ (3.25)

a platí: $\hat{\tilde{h}}(\nu) = \hat{h}^{*}(\nu)$, $\hat{\tilde{g}}(\nu) = \hat{g}^{*}(\nu)$ a je splnená podmienka

$$\vert\hat{h}(\nu)\vert^{2} + \vert\hat{h}(\nu + \frac{1}{2})\vert^{2} = 1$$ (3.26)

Je jednoducho dokázateľné, že táto množina vyhovuje podmienkam 3.23, 3.24. Biortogonálne Daubechie-wavelety [1] sú len konkrétnym príkladom ortogonálnych waveletov, platí pre nich

$$\hat{g}(\nu) = e^{-2\pi\nu}\hat{\tilde{h}}^{*}(\nu + \frac{1}{2})$$ (3.27)

$$\hat{\tilde{g}}(\nu) = e^{2\pi\nu}\hat{h}^{*}(\nu + \frac{1}{2})$$ (3.28)

$$\hat{h}(\nu)\hat{\tilde{h}}(\nu) + \hat{h}^{*}(\nu + \frac{1}{2}) \hat{\tilde{h}}^{*}(\nu + \frac{1}{2}) = 1$$ (3.29)

Rozsiahla množina kompaktných waveletov môže byť odvodená. Mnoho rôznych filtrov bolo navrhnutých, a bolo ukázané [13], že voľba filtrov musí byť riadená regularitou škálovania (scaling) a wavelet funkciami. Algoritmus poskytuje pyramídu $N$ elementov, a jeho zložitosť je proporcionálny k $N$. Algoritmus pracujúci v 2D je založený na dvoch premenných uprednostňujúcich smery $x$ a $y$. Škálovacia funkcia je definovaná v tvare:

$$\phi(x,y) = \phi(x)\phi(y)$$ (3.30)

Prechod z jedného rozlíšenia na ďalšie je možné pomocou

$$f_{j+1}(k_{x},k_{y}) = \sum_{l_{x}=-\infty}^{\infty}\sum_{l... ...fty}^{\infty} h(l_{x}-2k_{x})h(l_{y}-2k_{y})f_{j}(l_{x},l_{y})$$ (3.31)

Pomocou funkcií 3.32(vertikálny wavelet), 3.33(horizontálny wavelet), 3.34(diagonálny wavelet)

$$\psi^{1} (x,y) = \phi(x)\psi(y)$$ (3.32)

$$\psi^{2} (x,y) = \psi(x)\phi(y)$$ (3.33)

$$\psi^{3} (x,y) = \psi(x)\psi(y)$$ (3.34)

získame transformáciu

$$C_{j+1}^{1}(k_{x},k_{y}) = \sum_{l_{x}=-\infty}^{\infty}\su... ...^{\infty} g(l_{x} - 2k_{x})h(l_{y} - 2k_{y})f_{j}(l_{x},l_{y})$$ (3.35)

$$C_{j+1}^{1}(k_{x},k_{y}) = \sum_{l_{x}=-\infty}^{\infty}\su... ...^{\infty} h(l_{x} - 2k_{x})g(l_{y} - 2k_{y})f_{j}(l_{x},l_{y})$$ (3.36)

$$C_{j+1}^{1}(k_{x},k_{y}) = \sum_{l_{x}=-\infty}^{\infty}\su... ...^{\infty} g(l_{x} - 2k_{x})g(l_{y} - 2k_{y})f_{j}(l_{x},l_{y})$$ (3.37)

pomocou ktorej rozdelíme obraz na tri časti[44], viď obrázok 3.3.

Obrázok: Reprezentácia obrazu po wavelet transformácii

Transformácia pomocou waveletov môže byť chápaná ako dekompozícia vo frekvenčnej oblasti s priestorovým usporiadaním. Diskrétny prístup k waveletovej transformácii môže byť implementovaný pomocou tzv. à trous algoritmu. Tento algoritmus predpokladá, že $c_{0}(k)$ sú skalárnym súčinom funkcie $f(x)$ a škálovacej funkcie $\phi(x)$, zodpovedajúcej filtru v nižšom pásme, v bode $k$. Prvá iterácia je potom vykonaná pri dvojnásobnom zväčšení, pomocou ktorej získame $c_{1}(k)$. Rozdiel ${c_{1}(k)}-{c_{0}(k)}$ obsahuje množinu, ktorá je charakteristická pre wavelet transformáciu pomocou funkcie $\phi(x)$. Príslušný wavelet $\psi(x)$ je potom definovaný ako

$$\frac{1}{2}\psi(\frac{x}{2}) = \phi(x) - \frac{1}{2}\phi(\frac{x}{2})$$ (3.38)

Vzdialenosť medzi vzorkami pri hladine zväčšenia (i-1), a konštantnom dvojnásobnom zväčšení medzi jednotlivými hladinami je

$$c_{i}(k) = \sum_{l}h(l)c_{i-1}(k+2^{i-1}l)$$ (3.39)

a diskrétna wavelet transformácia $w_{j}(k)=c_{j-1}(k) - c_{j}(k)$. Koeficienty ${h(k)}$ sú odvodené pomocou škálovacej funkcie $\phi(x)$:

$$\frac{1}{2}\phi(\frac{x}{2}) = \sum_{l} h(l)\phi(x-l)$$ (3.40)

Použijeme lineárnu interpoláciu funkcie $\phi(x) = 1 - \vert x\vert$ pre $x \in <-1,1>$, $\phi(x) = 0$ pre $x \not\in <-1,1>$. Interpoláciou získame funkciu $\phi$ a príslušnú funkciu psi v tvare uvedenom na obrázkoch 3.4,3.5

Obrázok: Lineárna interpolácia funkcie $\phi(x)$

Obrázok: Lineárna interpolácia funkcie $\psi(x)$

Vyššie popísaný algoritmus môže byť jednoducho rozšírený na dvojrozmerný. Dostanem konvolučnú masku o veľkosti $3\times3$ bodov pre wavelet spojený s lineárnou interpoláciou. Koeficienty masky sú:

$$\left( \begin{array}{ccc} \frac{1}{16} & \frac{1}{8} & \fra... ... \frac{1}{16} & \frac{1}{8} & \frac{1}{16} \end{array}\right)$$

Na každej hladine $j$ získame množinu hodnôt $w_{j}(k,l)$, ktorá obsahuje rovnaký počet bodov ako samotný obrázok. V prípade, že si zvolíme škálovaciu funkciu $B3$-spline, potom koeficienty jednorozmernej masky budú v tvare $(\frac{1}{16}, \frac{1}{4}, \frac{3}{8}, \frac{1}{4}, \frac{1}{16})$, a dvojrozmerná maska bude vyzerať:

$$\left( \begin{array}{ccccc} \frac{1}{256} & \frac{1}{64} & ... ...{3}{128} & \frac{1}{64} & \frac{1}{256} \\ \end{array}\right)$$

Vlastnosti textúr sú často získané prahovaním a morfologickou transformáciou priestorovej a priestorovo-frekvenčnej (spatial/spatial-frequency) časti obrazu. Textúra môže byť reprezentovaná ako binárny vektor príznakov, pričom každý prvok značí energiu v pomere ku prahu v zodpovedajúcom s/s-f pásme. Každý s/s-f kanál je reprezentovaný binárnym vektorom jednotkovej dĺžky {$b_{k}$}. {$b_{k}$} predstavuje množinu elementárnych, lineárne nezávislých vektorov, ktoré tvoria bázu pre binárny priestor textúr. Vektory príznakov popisujúce vlastností textúr sú tvorené kombináciou vektorov {$b_{k}$}. Proces extrakcie textúr z s/s-f pásma prahovaním a morfologickou analýzou identifikuje regióny textúr v rámci každého obrazu. Priestorová lokalizácia jednotlivých textúr slúži ako sekundárne kritérium pri určovaní podobnosti obrazov. Keďže väčšina algoritmov pre extrakciu príznakov vlastností textúr zachová tvar regiónu, popis tvaru regiónu môže slúžiť ako ďalšie kritérium podobnosti. Gabor functions produkujú priestorovo-frekvenčnú transformáciu obrazov s teoreticky malou mierou neurčitosti. Dosahujú maximálne možné rozlíšenie v spektre s/s-f vzťahmi $\Delta_{x}^{2} \cdot \Delta_{u}^{2}\geq\frac{1}{4\pi}$ a $\Delta_{y}^{2} \cdot \Delta_{v}^{2}\geq\frac{1}{4\pi}$, pričom $[\Delta_{x}^{2},\Delta_{y}^{2}]$ udáva priestorové rozlíšenie a $[\Delta_{u}^{2},\Delta_{v}^{2}]$ je rozlíšenie v priestorovo-frekvenčnej oblasti. K dobrým vlastnostiam pri diskriminácii a segmentácii textúr je opodstatnenie Gabor-ových filtrov podložené aj psychofyzikálnymi experimentmi[6].