Príznaky v obraze

SIFT bol vytvorený Dr. Davidom G. Loweom a ide o techniku detekcie tvarov resp. objektov v obraze. Jednou z výhod je, že ide o škálovo a rotačne invariantný detektor. To znamená, že aj pri zmene mierky a pri rotácii obrazu sa daný kľúčový bod  - príznak (v anglosaskej literatúre key-point) v danom obraze nájde. Príkladom môže byť porovnanie dvoch obrazov zachytených pod rôznym uhlom. V prvom kroku sú nájdené body, v ďalších sú pre tieto body vytvorené  deskriptory [1]. SIFT algoritmus môže byť popísaný nasledujúcimi krokmi:

• Detekcia kľúčových bodov (škálovanie)
• Lokácie kľúčových bodov
• Odstránenie nevhodných kľúčových bodov
• Orientácia kľúčových bodov
• Deskriptory kľúčových bodov [2, 3]

Obr. 1. Ukážka škálovej a rotačnej invariancie [9]

Tvorba pyramídy

Základom celého algoritmu je pyramídová reprezentácia obrazu. Táto zabezpečuje spomínanú invarianciu. Zostavenie pyramídy pozostáva z nasledujúcich krokov:

• Zmena mierky obrazu - škálovanie 
• Gaussova filtrácia (DP – filter)
• Rozdiel Gaussových obrazov

Zmena mierky obrazu

Na pôvodný obraz sa aplikuje funkcia, ktorá podla zadaného parametru zmenší mierku obrazu. Na toto zmenšenie sú využité decimačné filtre. Najčastejšie sa decimácia vykonáva s faktorom 2, teda  obraz sa filtruje DP filtrom a následne sa vypustí každý druhý riadok a každý druhý stĺpec. Obrazy sú pred samotnou decimáciou najprv filtrované pomocou Gaussovho filtra. Zmena mierky zabezpečí rozdelenie do oktáv. Pod pojmom oktáva rozumieme súbor obrazov s rovnakou mierkou, ktoré sa od seba líšia úrovňou Gaussovej filtrácie.     

Gaussov filter

Gaussov filter bol popísaný v prednáške č. 3. Na každý obraz z predchádzajúceho kroku je aplikovaný Gaussov filter podľa nasledujúcej rovnice.

kde σ² predstavuje smerodajnú odchýlku, x (riadok) a y (stĺpec) predstavujú polohu op v obraze . Hodnoty smerodajnej odchýlky sú uvedené v nasledujúcej tabuľke.

Konvolúciou vstupného obrazu I(x,y) a variabilnej Gaussovej funkcie G(x,y,σ), získame škálovaný obraz L(x,y,σ), tomuto procesu zodpovedá nasledujúca rovnica[4].

Obr. 4 Obrazy po aplikovaní gaussovho filtra pre a) prvú, b) druhú, c) tretiu, d) štvrtú oktávu

Rozdiel Gaussových obrazov

Pre efektívnejšie vyhľadanie stabilných kľúčových bodov je potrebné vykonať rozdiel Gaussových obrazov, ktorý predstavuje rozdiel dvoch blízkych mierok lišiacich sa faktorom „k“. Táto funkcia sa nazýva Difference of Gaussian (DoG) a konvolúciou so vstupným obrazom vytvára funkciu D(x, y, σ), ktorá je tiež definovaná rozdielom škálovaných obrazov L(x, y, kσ) a L(x, y, σ) s rovnakým „k“ faktorom ako pri DoG. Tento spôsob je  efektívny aj z dôvodu jednoduchého odčítania obrazov. Proces získania  DoG je definovaný nasledujúcou rovnicou a ilustrovaný je na obr. 5. 

kde k=2^(1/s), predstavuje zmenu parametra σ a s je celé číslo.

Obr. 5 Rozdelenie obrazu do oktáv [4]

Vstupný obraz je postupne konvolučne násobený s Gaussovou funkciou s rôznym faktorom k. Takto vznikajú Gaussove obrazy s rôznou mierou filtrácie. To zobrazuje ľavá časť obr.5.. Pre každú oktávu je potrebné vytvoriť s+3 obrazov, aby detekované extrémy pokrývali celú oktávu. Na to, aby sme dostali pravý stĺpec, čo predstavuje funkciu DoG, je potrebné odčítať jednotlivé obrazy ľavého stĺpca oktávy. Ak je spracovanie prvej oktávy dokončené, algoritmus prejde do druhej oktávy. Druhá oktáva má obrazy v ľavom stĺpci 2x zmenšené, čo predstavuje zobrazenie každého druhého op v riadku a stĺpci. Následne je aj pre túto oktávu vykonaná DoG, čím dostaneme pravý stĺpec. Celý proces sa opakuje, až kým sa nevyčerpajú všetky oktávy[4].

Obr. 6 Obrazy zodpovedajúce DoG pre a) prvú, b) druhú, c)tretiu, d)štvrtú oktávu (Pozn. pre lepšiu vizuálnu ukážku bol výstupný obraz zosilnený faktorom 10)

Lokálne extrémy

Pre nájdenie lokálnych extrémov (minimá a maximá) D(x, y, σ), sa každý op porovná s ôsmymi op v aktuálnom obraze a deviatimi op susedných obrazov. Op spĺňa  podmienku minima a maxima, ak jeho hodnota je menšia alebo väčšia ako susedné op. Ak tento op spĺňa podmienku, je označený ako „kľúčový bod - key point“ (KB). Pri niektorých op nie je potrebné vykonať porovnanie zo všetkými susedmi a už po pár porovnaniach je tento bod vylúčený a nie je ďalej vedený ako KB. Detekcia KB nie je vykonávaná na spodných ani vrchných obrazoch oktávy, pretože op nemajú dostatočný počet susedov. Označené KB sú len približné lokálne extrémy, pretože ležia veľmi často medzi op. Pre presnejšie určenie je potrebné ďalšie spracovanie matematicky [4].

Na obr. 8 je možné vidieť nájdené KB pre štyri oktávy. Na prvej oktáve bolo nájdených 712 KB, na druhej oktáve 233 KB, na tretej oktáve 66 KB a na štvrtej oktáve 21 KB. S týmito kľúčovými bodmi sa pracuje v ďalších krokoch algoritmu. 

Odstránenie nevhodných KB

Po nájdení kľúčových bodov pomocou lokálnych extrémov je možné vykonať odstránenie op s nízkym kontrastom a op, ktoré sa nachádzajú pozdĺž hrán. Odstránenie nájdených KB s nízkym kontrastom sa vykonáva prahovaním. Na to sa používa Taylorova expanzia funkcie D(x,y,σ), ktorú možno definovať v nasledujúcom tvare.

kde  X = (x,y,σ)^T je posun od daného bodu a D a derivácie sú vyhodnocované pre daný bod X, kde X je popísaný parametrami x, y a σ. To znamená, že každý bod je derivovaný podľa x, y a σ. Umiestnenie daného bodu a jeho extrému je určené z derivácie tejto funkcie s ohľadom na x a nastavenie x do nuly. Z toho dostaneme nasledujúcu rovnicu.

Funkčnú hodnotu extrému D(z) je možné použiť na odstránenie KB s nízkym kontrastom. To je možné dosiahnuť pomocou rovnice:      

   Z experimentov bolo zistené , že hodnota |D(z)|, ktorá je menšia ako 0,03 by mala byť odstránená[4].

Na obr. 10 môžme vidieť, že po tomto kroku bolo odstránené značné množstvo KB, ktoré nespĺňali túto podmienku. Do ďalšieho spracovania pokračovalo pre prvú oktávu 261 KB, pre druhú 116 KB, pre tretiu 45 KB a pre štvrtú 18 KB.  

Ďalším dôležitým krokom je odstránenie KB blízko okraja. Tieto body prinášajú nestabilitu pre ďalšie kroky spracovania. Tieto body môžu byť určené pomocou Hessianovej matice H ,o veľkosti 2x2.

Vlastné hodnoty H poskytujú veľa informácií o lokálnej štruktúre okolo KB. V skutočnosti vlastné hodnoty sú len minimá a maximá zakrivenia povrchu plochy D(x,y,σ). Hrana bude mať vysoké maximálne zakrivenie a nízke minimálne zakrivenie. Rohový KB má vysoké minimálne aj maximálne zakrivenie. Nech α je maximum a β je minimum zakrivenia. Potom je daný súčet vlastných hodnôt:

a ich determinant:  kde:    

kde r je pomer medzi najväčšou a najmenšou hodnotou vlastnej hodnoty. V niektorých prípadoch môže byť determinant záporný. To znamená, že bod nie je extrém a je vyradený z pomedzi kľúčových bodov. Môžeme zadefinovať pomer Tr(H) a Det(H) z predchádzajúcich rovníc.

Výsledná hodnota (r+1)²/r je minimálna, ak sú dve vlastné hodnoty rovnaké a zvyšuje sa s hodnotou r. Na zistenie či je pomer hlavných zakrivení pod prahom,  stačí ho vykonať nasledovne:

Obr. 11. Kľúčové body po odstránení bodov pozdĺž hrán (r = 10)

V tomto kroku bolo odstránených podstatne menej KB, ako v predchádzajúcom. Konečný počet KB, pre ktoré bude nájdená orientácia a budú opísané deskriptorom je pre prvú oktávu 254 KB, druhú oktávu 114 KB, tretiu oktávu 42 KB, a štvrtú oktávu 18 KB.

Orientácia KB

Priradením orientácie ku každému kľúčovému bodu v obraze na základe jeho vlastností je možné vynulovať vplyv invariantnosti otočenia obrazu. Výstupom tejto operácie je určenie deskriptoru, ktorý zahŕňa vlastnosti založené na rotačnej invariantnosti. Táto vlastnosť obmedzuje deskriptory tým, že neobsahuje niektoré informácie o obraze resp. o op. Z experimentov bolo zistené, že aj tak tento postup dosahuje najlepšie výsledky. Pre každý op prvok obrazu L(x,y) je gradient magnitúdy m(x,y) a orientácie θ(x,y) je možné určiť rozdiel op nasledovne:

Rovnice sú použité na vytvorenie orientačného histogramu. Tento histogram obsahuje 36 oblastí, ktoré pokrývajú 360 stupňový rozsah orientácií.  

Lokálne deskriptory

V tomto momente je každý kľúčový bod  opísaný tromi parametrami. Polohou, mierkou a orientáciou. Teraz nasleduje výpočet deskriptora. Vytvoríme blok v okolí kľúčového bodu o veľkosti 16x16. Každý z týchto blokov je ešte rozdelený na podbloky o veľkosti 4x4 ako je zobrazené na nasledujúcom obrázku.

Obr. 14 Bloky a podbloky pre kľúčový bod [2]

Pre každý podblok 4x4 je vytvorený histogram. Veľkosť jednotlivých stĺpcov histogramu závisí na hodnote gradientu a taktiež od vzdialenosti od kľúčového bodu. Váhu vzdialenosti zabezpečí Gaussova váhovacia funkcia. Jednoduchým prenásobením hodnoty gradientu s touto funkciou zabezpečí správnu hodnotu.

Obr. 15 Gaussova váhovacia funkcia [2]

Ako bolo zobrazené na obr. výsledkom je 128 čísel. Tieto čísla je potrebné normalizovať a tým získame jedinečný vektor kľúčového bodu[2][9].

Zaujímavé výsledky:

Zaujímava prednáška zo SIFT-u:

[1] E.Šikudova, Z.Černekova, W.Benešová, Z.Haladová, J.Kučerova, Počítačové videnie - Detekcia a rozpoznávanie objektov [Online]. Available: http://sccg.sk/~cernekova/Pocitacove_videnie.pdf [Cit. 22 5 2019].

[2] U.Sinha, SIFT: Theory and Practice, [Online]. Available: http://aishack.in/tutorials/sift-scale-invariant-feature-transform-features/ [Cit. 22 5 2019].

[3] A.Mordvintsev, K.Abid, Introduction to SIFT(Scale-Invariant Feature Transform) [Online]. Available: https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_sift_intro/py_sift_intro.html

[Cit. 22 5 2019].

[4] D.G.Lowe, Distinctive Image Features from Scale-Invariant Keypoints, [Online]. Available:  https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf [Cit. 22 5 2019].

[5] D.G.Lowe, Object Recognition from Local Scale-Invariant Features, [Online]. Available: https://www.cs.ubc.ca/~lowe/papers/iccv99.pdf [Cit. 22 5 2019].

[6] Scale space, [Online]. Available: http://www.cs.uu.nl/docs/vakken/ibv/reader/chapter9.pdf [Cit. 22 5 2019].

[7] A. Rajwade, Scale-Invariant Feature Transform (SIFT), [Online]. Available: https://www.cse.iitb.ac.in/~ajitvr/CS763/SIFT.pdf  [Cit. 22 5 2019].

[8] Z.Tomori, M.Nikorovič, Počítačové videnie v praxi, [Online]. Available: https://home.saske.sk/~tomori/Downloads/Poc_videnie/PV_2016.pdf [Cit. 22 5 2019].

[9] D.Tyagi, Introduction to SIFT, [Online]. Available: https://medium.com/@deepanshut041/introduction-to-sift-scale-invariant-feature-transform-65d7f3a72d40 [Cit. 1 12 2019].

[10] A. Jakubovic, Image Feature Matching and Object Detection Using Brute-Force Matchers , [Online]. Available: https://www.researchgate.net/publication/328991586_Image_Feature_Matching_and_Object_Detection_Using_Brute-Force_Matchers/figures?lo=1 [Cit. 1 12 2019].

[11] M. Rodríguez, G. Facciolo, R. G. v. Gioi, P. Musé, J.-M. Morel and J. Delon AID : an affine invariant descriptor for SIFT, [Online]. Available: https://rdguez-mariano.github.io/pages/sift-aid.html [Cit. 1 12 2019].