Fourierov deskriptor

Existujú dva všeobecne známe Fourierove deskriptory (FD), popísané v [81] a [57], budeme sa na nich odvolávať pod skratkou ``FD1'' a ``FD2''. Hodnoty Fourierových deskriptorov sú produkované Fourierovou transformáciou časti obrazu obsahujúcej objekt vo frekvenčnej oblasti. Deskriptory nižších frekvencií popisujú hrubú informáciu o tvare, kým deskriptory vyšších frekvencií popisujú detaily v obraze. Z toho vyplýva, že komponenty nižších frekvencií definujú hrubý tvar pôvodného objektu. Postup popisu tvaru je taký, že obraz, resp. jeho časť sa premietne do roviny komplexných čísel. Tým pádom súradnice každého bodu na hranici objektu môžu byť vyjadrené ako komplexné číslo $x+jy$. Ak postupne prejdeme hranicou pohybujúc sa proti smeru hodinových ručičiek konštantnou rýchlosťou, dostaneme postupnosť komplexných čísel, t.j. jednorozmernú funkciu komplexnej premennej 3.6.

Obrázok: Reprezentácia obrysu v komplexnej rovine

Prechádzanie hranice viac ako raz nás vedie k periodickej funkcii. Vychádzajúc zo vzťahu 3.10 a 3.8 a rozpísaním $e^{-jA} = cos(A) - jsin(A)$ dostaneme

$$F(u)=\left( \frac{1}{N}\right) \sum_{x=0}^{N-1}f(x+jy)(cos(Ax)-jsin(Ax)),\\ A=\frac{2\pi u}{N}$$ (3.41)

Diskrétna Fourierova transformácia (DFT) postupnosti komplexných čísel získaných prechodom cez hranicu určitého objektu nám dáva hodnoty Fourierovho deskriptoru daného obrysu. DFT je reverzibilná lineárna transformácia, takže zachovaná pôvodnú informačnú hodnotu. Informácia získaná po transformácii je v takom tvare, ktorá nám umožní izolovať rôzne nežiaduce faktory, dokonca existuje možnosť úplného odstránenia takýchto faktorov. V tomto zmysle, hodnoty Fourierovho deskriptora môžu byť normalizované, tým dosiahneme nezávislosť transformácie od posunu, zväčšenia a natočenia pôvodného obrysu.
Posun obrysu o nejaké komplexné číslo, ktoré má zložky $x$ a $y$, zodpovedá matematickej operácii súčtu konštanty $(x+jy)$ s každým prvkom obrysu. V prípade DFT má posun pomocou takejto konštanty vplyv na koeficient $F(0)$ vo Fourierovom rade. Preto normalizáciu pozície uskutočníme splnením požiadavky $F(0)=0$.
Úpravu mierky dosiahneme vynásobením všetkých prvkov obrysu konštantnou hodnotou. V prípade Fourierovho radu sa to prejaví vynásobením všetkých členov radu danou konštantou. Tým pádom predelením celého radu jedným z jeho členov dosiahneme normalizáciu pre veľkosť. Môže byť dokázané, že v prípade prechodu obrysom proti smeru hodinových ručičiek a disjunktnej kontúry, koeficient $F(1)$ bude stále najväčší. Normalizácia v tomto prípade znamená predelenie každého prvku $F(n)$ magnitúdou $F(1)$. Vzniknuté koeficienty necháme v zlomkovom tvare.
Normalizácia rotácie sa dá dosiahnuť nájdením koeficientov dvoch prvkov s najväčšou magnitúdou. Následne nastavíme ich fázový uhol na nulu. Ako bolo už v predchádzajúcom spomenuté, $F(1)$ je koeficient najväčšej magnitúdy. Nech $F(k)$ je koeficient druhej najväčšej magnitúdy. Tento koeficient $F(k)$ má násobnosť normalizácie (normalisation multiplicity) $m$ kde $m=\vert k-1\vert$. Teda podmienka, aby $F(1)$ a $F(k)$ mali nulový fázový uhol môže byť splnená $m$ rôznymi orientáciami a kombináciami štartovacích bodov. V prípade $k=2$, orientácia a štartovací bod sú definované jedinečným spôsobom.
$FD1$ je málo efektívne pri rekonštrukcii obrysu, preto sa zameriame na FD2.
Pohyb bodu po hranici $\gamma$ oblasti je popísaný komplexnou funkciou $u(l) = x(l) + jy(l)$. FD2 je definované ako:

$$a_{n} = \frac{1}{L(\frac{2\pi n}{L})}\sum_{k=1}^{N_{V}}(b_{k-1} - b_{k}) e^{-j\left(\frac{2\pi nl_{k}}{L}\right)}$$ (3.42)

pričom $L$ je absolútna dĺžka $\gamma$; $l_{k} = \sum_{i=1}^{k}\vert V_{i} - V_{i-1}\vert$ pre $k > 0$ a $l_{0} = 0$; a $b_{k} = \frac{V_{k+1}-V_{k}}{\vert V_{k+1}-V_{k}\vert}$.
Nech $a_{n}$ a $b_{n}$ značia dva FD pre krivky $\alpha$ a $\beta$, ďalej sa predpokladá použitie $N_{C}$ harmonických, potom metrika vzdialenosti je daná:

$$d(\alpha,\beta) = \sqrt{\sum_{n=-N_{C}}^{N_{C}} \vert a_{n}-b_{n}\vert^2}$$ (3.43)

Na to, aby sme vzali do úvahy zmenu merítka ($s$), rotáciu ($\phi$) a polohu štartovacieho bodu ($p$), je potrebné minimalizovať metriku vzdialenosti

$$d^{*}(\alpha,\beta) = min_{s,\phi,p}\sum_{n=-M,n\neq0}^{M}\vert a_{n} - se^{j(np+\phi)}b_{n}\vert^2$$ (3.44)

pomocou nastavenia parametrov ($s$,$\phi$,$p$). Toto je výpočtovo náročná optimalizácia a tým pádom je FD2 nepraktické pre použitie v real-time spracovaní informácie, hlavne vtedy keď počet obrázkov je veľký.