1 Uvod Kategorizacija objektov spada med pomembnejše pro- bleme umetnega zaznavanja. V tem delu obravna- vamo ožje področje vizualne kategorizacije objektov, ki proučuje problem predstavitve in prepoznavanja kategorij objektov z uporabo vidne informacije. V okviru razvoja umetnih kognitivnih sistemov je vizualna kategorizacija pomembna predvsem kot funkcionalnost, ki premosti razliko med procesiranjem signala in višjenivojskim se- mantičnim procesiranjem, saj omogoča abstraktno inter- pretacijo prizorov in situacij. Eden prvih in vplivnejših poskusov računskega mo- dela za kategorizacijo objektov je Marrov model [12], ki temelji na postopnem procesu prepoznave tridimenzio- nalnih primitivov kot osnovnih gradnikov, iz katerih so sestavljeni kompleksnejši objekti. Marr predvideva, da lahko primitive uspešno rekonstruiramo, nakar prizor ka- tegoriziramo s pomočjo modela, na primer z uporabo in- terpretacijskih dreves [8]. Težavna rekonstrukcija primi- tivov in omejitve primitivov pri predstavitvi nestrukturi- ranih objektov so pogojevale postopen odmik od visoko- nivojskih predstavitev k izvorni slikovni informaciji, npr. k predstavitvam, zasnovanim na globalnem videzu objek- tov, ali pa k predstavitvam z lokalnimi značilkami. Lo- kalne predstavitve so še posebej uspešne kot osnova za statistično zasnovane modele kategorizacije. Ti se razli- 218 Jogan Slika 1. Shema modela za hierarhično iskanje ujemanj. S pravokotniki so uokvirjena lokalna področja, krogi pa pomenijo receptivna polja združevanja. Zavoljo preglednosti je na sliki prikazan le del hierarhičnega drevesa povezovanja dveh začetnih lokalnih regij. Figure 1. The outline of the framework for hierarchical matching. Rectangular outlines denote local regions, while circular regions denote binding receptive fields. For the sake of clarity, only one branch of binding is depicted, starting with two initial local regions. kujejo predvsem po vrsti lokalnih značilk in po načinu in stopnji integracije geometričnih relacij med značilkami. Leibe in sod. [9] tako implementirajo kategorizacijo s slo- varji lokalnih zaplat in implicitnim geometrijskim mo- delom, medtem ko Fei-Fei in sod. [2] ter Torralba in sod. [17] uporabljajo generativni model lokalnih konste- lacij. Hierarhične predstavitve [4, 3, 14, 6], ki predvide- vajo hierarhično kompozicionalnost objektov, poskušajo modelirati dele kot konstelacije lokalnih značilk na večih nivojih podrobnosti. Medtem ko našteti pristopi definirajo kategorije z učenjem značilnosti nad množico primerov ali z namen- sko definicijo lastnosti, pa lahko kategorije opredelimo le na podlagi podobnosti s prototipom [15], kjer podob- nost vrednotimo z iskanjem strukturnih ujemanj [16], z deformacijskim ujemanjem oblike [1] ali s primerjavo se- gmentacijskih dreves [18]. Večina predlaganih metod te- melji na predhodnem iskanju lokalnih ujemanj, ki pa je v kontekstu kategoričnega primerjanja objektov pogosto problematično. V predlaganem pristopu predlagamo model kategori- zacije s postopnim iskanjem lokalnih in strukturnih uje- manj s prototipom, kjer se ujemanja konstruirajo v hi- erarhičnem sosledju lokalnega združevanja in inhibicije. Tak način iskanja omogoča intenzivno odkrivanje podob- nosti na več nivojih podrobnosti. Podobnosti, ki naj pred- met opredelijo kot pripadnika določene kategorije, so to- rej izpeljane iz prototipne slike objekta v kanoničnem po- gledu [15] in niso vnaprej opredeljene. Učenje katego- rije ne predvideva obširnega zbiranja znanja o kategoriji objektov, temveč je implementirano kot sprotno učenje lastnosti prototipa in kot učenje in prilagajanje parame- trov združevanja. Diagram na sliki 1 prikazuje poeno- stavljeno shemo poteka kategorizacije. Prototipna slika je podlaga za učenje lokalnega slovarja filtrov za klasifi- kacijo lokalnih regij in za učenje lastnosti geometričnega konceptualnega prostora (GKP). Učenju sledi več nivo- jev združevanja značilk, iskanja ujemanj in inhibicije. Značilke se združujejo v pare, ki z vsakim nivojem ra- stejo, tako glede na velikost in kompleksnost sestavlje- nih značilnic kot tudi glede na površino slike, ki jo opi- sujejo. Ti procesi potekajo sinhrono, v okviru omeje- nih receptivnih polj prototipa in interpretirane slike. Če je bilo iskanje ujemanj med prototipom in interpretirano sliko uspešno, lokalna področja na končnem nivoju ob- segajo celotno površino prototipa in ustrezno površino in- terpretirane slike. Število visokonivojskih ujemanj odraža strukturno in vizualno podobnost s prototipom. Če sistem kategorij zasnujemo kot mrežo podobnosti, lahko na pod- lagi števila ujemanj objekt kategoriziramo. V nadaljevanju bomo najprej predstavili postopek de- tekcije, učenja in gručenja lokalnih regij, ki mu bo sledil opis hierarhičnega združevanja. Zaključili bomo z opi- som eksperimentalnih rezultatov in kritičnim ovrednote- njem metode. 2 Detekcija, učenje in gručenje lokalnih regij 2.1 Detekcija Z detekcijo stabilnih lokalnih regij želimo zagotoviti lo- kalno podporo za poznejše združevanje slikovne informa- cije. Klasične metode za razpoznavanje objektov na pod- lagi lokalnih regij uporabljajo informativne opisnike, ki so načrtovani z namenom minimizacije števila napačnih ujemanj [11]. Pri kategorizaciji objektov pa je značilno, da se objekti iz določene kategorije na lokalni ravni lahko zelo razlikujejo. Zato v pričujočem pristopu lokalno fo- tometrično informacijo uporabimo le kot osnovo za gra- dnjo značilk na višjih nivojih, ki opisno moč pridobijo šele na nivoju posameznega objekta. Kljub temu pa mo- rajo nizkonivojske značilke ustrezati merilom ponovljivo- sti in stabilnosti, imeti pa morajo tudi lastno merilo in ori- entacijo. Poleg tega želimo, da so lokalne regije gosto Hierarhično iskanje ujemanja za vizualno kategorizacijo objektov 219 Slika 2. Lokalne regije Ki, detektirane na prvih štirih oktavah. Pravokotniki ponazarjajo velikost regij in njihovo usmerjenost. Figure 2. Local regions Ki detected at the first four octaves. The size and orientation of the regions is denoted by oriented rectangles. posejane, tako da je začetna predstavitev redundantna. Lokalna območja poiščemo z detektorjem lokalnih re- gij, ki je zasnovan na podlagi lastnosti diferenčnih opera- torjev v prostoru meril [10, 11]. Sliko I(x, y) preslikamo v prostor meril L(x, y, σ), do katerega pridemo s konvo- lucijo slike z Gaussovim jedrom G(x, y, σ) spremenljive velikosti. Središča lokalnih regij definiramo kot lokalne ekstreme razlike Gaussovih jeder (Difference of Gaussi- ans, DoG) DoG(x, y, σ) = L(x, y, kσ) − L(x, y, σ) (1) v prostoru meril. Izberemo tiste kandidate, ki presežejo prag lokalnega kontrasta in so lokalni ekstrem tudi v lokalni slikovni soseščini. Kandidate za lokalne re- gije dodatno okarakteriziramo glede na prisotnost roba v središčni točki. Velikost posamezne regije je določena z merilom, na katerem je bila regija detektirana. Usmerjenost regije je določena kot smer, kjer histogram lokalnih gradientov za- vzame maksimalno vrednost [11]. Lokalne regije Ki so torej opisane z lokacijo CKi, usmerjenostjo oKi ter velikostjo rKi. Slika 2 prikazuje regije, detektirane na prvih štirih oktavah. 2.2 Učenje slovarja ICA Lokalne regije so zdaj opisane le s strukturnimi značilnostmi regije. Opis videza regije podamo na pod- lagi slovarja filtrov, katerih maksimalno razpršeni odzivi določajo razred lokalne regije. Število razredov in s tem Slika 3. Slovar ICA, naučen na prototipni sliki. Figure 3. ICA codebook learned from a prototype image. velikost slovarja je namenoma majhno, saj se želimo izo- gniti natančnemu opisu, ki bi preprečilo konstrukcijo vi- sokonivojskih ujemanj. Nabora filtrov se naučimo z analizo neodvisnih kom- ponent (Independent Component Analysis, ICA) slikovne matrike učnih regij, ki jih pridobimo iz prototipne slike, ali pa iz več slik objektov določene kategorije. V litera- turi se slovarji ICA pogosto obravnavajo kot model nev- ronskih receptorjev v primarnem vidnem korteksu [13, 5], vendar pa učenje slovarja vedno temelji na naključno iz- branih regijah naključnih slik. V nasprotju s pristopi v li- teraturi v tem delu računamo slovar le na informiranih po- dročjih, ki so bili že izbrani v postopku detekcije. Slovar se zato izogne modeliranju redundantne informacije in se osredini na opise značilnih struktur z generično smerjo in velikostjo, ki je določena že z algoritmom detekcije. Če poleg tega učenje omejimo na predmete ene katego- rije, lahko že manjši slovar opiše značilne dele objektov (slika 3). Slikovno matriko X sestavimo iz normaliziranih in- tenzitetnih vektorjev x, ki opisujejo posamezne regije v generični smeri. Posamezen vektor xi lahko predstavimo z linearno superpozicijo več izvorov bi, xi = N∑ j=1 aijbj (2) uteženo s koeficienti aij . Matrično obliko enačbe 2 zapišemo kot x = Ab. Če z u označimo izvore, ki jih rekonstruiramo na podlagi opazovanja vidnih vzorcev, potem preslikavo x v u zapišemo kot u = Wx, kjer je W = A−1, če je A invertibilen linearni sistem. Z analizo neodvisnih komponent pa izračunamo W in b tako, da pogojujemo statisično neodvisnost izvorov bj . Za izračun slovarja uporabimo algoritem FastICA [5]. Slika 3 je pri- mer slovarja petih filtrov po učenju iz prototipne slike ka- tegorije. Lokalne regije Ki dodelimo razredu wKi = m, ki je določen z indeksom filtra wm z najvišjo absolutno vrednostjo odziva w Ki = arg max m |ûm|; û = Ŵ x̂. (3) 2.3 Gručenje Gestalt Lokalne značilke, ki so osredišcene na robnih točkah, tipično nastopajo v redundantnih, gostih gručah. Redun- dantnost zmanjšamo z gručenjem robnih regij na pod- lagi principov Gestalt. Algoritem implementira princip 220 Jogan Slika 4. Značilke H0, pridobljene po gručenju Ki. Figure 4. H0 features after grouping of Ki. bližine (gručijo se le značilke v omejenem območju), po- dobnosti (gručijo se le značilke, ki pripadajo istemu ra- zredu) in skupne usode (gručijo se le značilke, katerih smeri tvorijo kongruenten kot α radianov). Slika 4 pri- kazuje rezultat gručenja in pridobljene značilke. Na pod- lagi gručenja so nove značilke H0 izpeljane iz lastnosti gruč K tako, da podedujejo razred odziva na slovar ICA wH0 = wKi, smer in velikost značilke pa se izračunata iz geometrijskih lastnosti gruče. 2.4 Hierarhično združevanje Združevanje značilk poteka prek več hierarhičnih nivo- jev. Značilke postopoma pridobivajo dodatno informa- cijo o relativni geometrijski konfiguraciji. Ker so geo- metrijske relacije podane relativno in na lokalni ravni, so značilke neodvisne od globalnega koordinatnega sistema, lokalni proces združevanja pa je popolnoma neodvisen od drugih procesov. Proces združevanja se začne s ko- rakom H0 → H1 in se načeloma lahko izvede za poljubno število nivojev. Na vsakem nivoju se n značilk v lokal- nem območju združi v n-terico. Ker združevanje večjega števila značilk hitro privede do prevelike informativnosti značilk, hierarhija združuje značilke le v pare. Par značilk uredimo glede na velikost regij, rHki > rHkj ter ga opišemo z atributi relativne velikosti sHk+1, razdalje lHk+1, kotov α1Hk+1 in α2Hk+1 med smerjo re- gij in povezovalno daljico in z oznako medsebojne lege smernih vektorjev orHk+1: s H k+1 = log ( 1 + rHki rHkj ) l H k+1 = log ( 1 + ||CHki CHkj ||2 rHki ) α1H k+1 = 6 ( oHki , CHki CHkj) α2H k+1 = 6 ( oHkj , CHki CHkj) or H k+1 ∈ {0, 1, 2, 3} Atribute predstavimo v diskretiziranem geometričnem konceptualnem prostoru (GKP), ki ustreza psihološkim modelom zaznavanja [7]. Geometrične atribute para Hki Input: Ĥk , Hk , Fk , inner, outer, f Output: Ĥk+1, Hk+1, Fk+1 foreach Fku = {( Ĥ k i , H k j )} do rMin = rĤki ∗ inner rMax = rĤki ∗ outer  = { Ĥ k l : C Ĥ k l ∈ R̂F (rMin, rMax) } while card (  ) < f ∧ rMin > 0 do if soseščina znotraj slike then rMax = rMax + eps else rMin = rMin − eps update (  ) Ĉ k+1 = bind ( Â, Ĥ k i ) R̂F = convexHull (  ) preslikaj R̂F v RF A = { H k m : ( C H k m ∈ RF ) ∧ ( ∃ Ĥ k n ∈  : ( Ĥ k n, H k m ) ∈ F k )} C k+1 = bind ( A, H k j ) F k+1 = Fk+1 ∪ match ( Ĉ, C ) Ĥ k+1 = Ĥk+1 ∪ { Ĉ k+1 m : Ĉ k+1 m ∈ F k+1 } H k+1 = Hk+1 ∪ { C k+1 m : C k+1 m ∈ F k+1 } Algoritem 1: Hierarhično združevanje, iskanje uje- manj in inhibicija. Algorithm 1: Hierarchical binding, matching and in- hibition. opišemo z diskretnim opisnikom GHk i : [ Qs( s H k i ),Ql( l H k i ),Qα( α1H k i ),Qα( α2H k i ), or H k i ] , kjer Q( • ) pomeni kvantizacijo. Naj Hk → Hk+1 označuje nivoje združevanja. Značilke na vsakem od ni- vojev lahko opišemo z diskretnim zaporedjem, ki popol- noma opisuje podrejeni značilki ter geometrijska razmer- ja med njima: D H 0 i = w H 0 i (4) D H k+1 m = G H k+1 m || D H k i || D H k j ; k > 0 . (5) Ker so distribucije geometrijskih parametrov na posa- meznih nivojih hierarhije odvisne od strukturnih lastnosti objektov, lahko kvantizacijo prilagodimo posameznemu prototipnemu modelu. Model pridobimo s hierarhičnim združevanjem prototipa s samim seboj. Tako pridobljene distribucije parametrov so unimodalne, zato lahko kvan- tizacijo prilagodimo na podlagi statističnih momentov. 2.5 Sinhrono združevanje, iskanje ujemanj in inhibicija Naj bodo Ĥk značilke prototipa, Hk značilke interpreti- rane slike, Fk pa indeks ujemanj F k = {( Ĥ k i ,H k j ) : DĤki = D H k j } . Združevanje poteka tako, da za vsak par iz množice ujemanj Fk aktiviramo receptivno polje Ĥki , v katerem Hierarhično iskanje ujemanja za vizualno kategorizacijo objektov 221 Slika 5. Sinhrono združevanje H1 → H2. Figure 5. Sychronous matching H1 → H2. Slika 6. Sinhrono združevanje H4 → H5. Figure 6. Sychronous matching H4 → H5. poiščemo f kandidatov. Del receptivnega polja, ki vse- buje te kandidate, nato preslikamo na nivo k interpreti- rane slike, kjer prav tako poiščemo in združimo kandidate za ujemanja. Lokalna ujemanja na Hk+1 ohranimo, druge značilke pa zavržemo. Postopek opisuje algoritem 1. Iz- hod iz algoritma so značilke Ĥk+1, Hk+1 ter indeks uje- manj Fk+1. Slika 5 ponazarja združene značilke po prvem koraku H0 → H1, slika 6 pa ponazarja končni rezultat, če predvidevamo pet nivojev združevanja. 3 Eksperimentalni rezultati Model smo preizkusili na problemu kategorizacije se- gmentiranih objektov v zbirki ETH80. Vsaka od osmih kategorij je predstavljena s prototipnim objektom v ka- nonični orientaciji. Zaradi manjšega števila detektiranih lokalnih regij učimo slovar ICA filtrov na več slikah iste kategorije, ki pa niso hkrati tudi v testni množici slik. Za vsakega od prototipov se naučimo kvantizacije geo- metričnega konceptualnega prostora. Slika 7 prikazuje povprečno število ujemanj vsakega od prototipov z vsemi drugimi slikami objektov v isti ka- nonični orientaciji na vsakem od petih nivojev hierarhije. Na desni strani grafikonov so prikazani prototipi kate- gorij, urejeni po padajočem številu ujemanj na H5. Vsi prototipi generirajo najvišje število ujemanj z objekti la- stne kategorije, medtem ko dobijo tudi strukturno zelo po- dobne kategorije v povprečju manj glasov. Iskanje uje- manj s preprostimi predmeti se konča z bistveno manjšim številom ujemanj pri kompleksnih objektih, saj naučen geometrični konceptualni prostor prilagodi iskanju pre- prostih oblik, kar tudi do določene mere preprečuje “ha- luciniranje“ preprostih oblik v kompleksnih objektih. Slika 8 prikazuje prvih pet objektov z najvišjim številom ujemanj na H5. Vidimo lahko, da ujemanja na višjih nivojih hierarhije opisujejo konsistentne strukturne podobnosti med objekti ter da so objekti iste kategorije praviloma med tistimi z največjim številom ujemanj na H5. 1 2 3 4 5 10 0 10 1 10 2 10 3 10 4 10 5 H Car 1 2 3 4 5 10 0 10 1 10 2 10 3 10 4 10 5 H Cow 1 2 3 4 5 10 0 10 1 10 2 10 3 10 4 10 5 H Horse 1 2 3 4 5 10 0 10 1 10 2 10 3 10 4 Tomato H Slika 7. Povprečna števila ujemanj na nivojih H1 - H5. Figure 7. Average number of matches at levels H1 - H5. Slika 8. Prvih pet objektov po številu H5 ujemanj. Figure 8. The five exemplars with the highest numbers of H5 matches. 4 Sklep Predstavili smo nov model kategorizacije objektov s po- stopnim iskanjem lokalnih in strukturnih ujemanj s pro- totipom, kjer se ujemanja konstruirajo v hierarhičnem so- sledju lokalnega združevanja, iskanja ujemanj in inhibi- cije. Rezultati dokazujejo uporabnost metode za katego- rizacijo objektov v kanoničnem pogledu. Pomembno je tudi, da metodo lahko uporabimo za detekcijo potencial- nih ujemanj med objekti na več nivojih podrobnosti, kar dosežemo z analizo nizkonivojskih ujemanj, na katerih te- meljijo visokonivojska ujemanja. Pokazali smo tudi, da lahko objekte na slikah učinkovito kategoriziramo z upo- rabo prototipne predstavitve, ki ne zahteva ekstenzivnega učenja na obsežnih učnih množicah. Metoda omogoča le prepoznavanje v kanoničnem po- gledu, vendar pa je bila razvita za implementacijo v širšem kognitivnem sistemu, kjer bi lahko z uporabo kon- tekstnega procesiranja, večmodalnosti in aktivnega zazna- vanja dosegli učinkovito kategorizacijo poljubnih objek- tov. 5 Literatura [1] S. Belongie, J. Malik, & J. Puzicha, Shape matching and object recognition using shape contexts. IEEE Trans. Pat- tern Anal. Mach. Intell., 24(4):509–522, 2002. [2] L. Fei-Fei, R. Fergus, & P. Perona, Learning generative visual models from few training examples. In Computer Vision and Pattern Recognition Workshop, 2004 Confe- rence on, pp. 178–178, 2004. [3] S. Fidler, M. Boben, & A. Leonardis, Similarity-based cross-layered hierarchical representation for object cate- gorization. In CVPR, 2008. [4] S. Fidler, & A. Leonardis, Towards scalable representati- ons of object categories: Learning a hierarchy of parts. In Computer Vision and Pattern Recognition, 2007. CVPR ’07. IEEE Conference on, pp. 1–8, 2007. [5] A. Hyvarinen & P. Hoyer, Emergence of complex cell properties by decomposition of natural images into in- dependent feature subspaces. In Artificial Neural Ne- tworks, 1999. ICANN 99. Ninth International Conference on (Conf. Publ. No. 470), Vol. 1, pp. 257–262vol.1, 1999. [6] Y. Jin & S. Geman, Context and hierarchy in a probabili- stic image model. In Computer Vision and Pattern Reco- gnition, 2006 IEEE Computer Society Conference on, Vol. 2, pp. 2145–2152, 2006. [7] G. A. Kelly, The Psychology of Personal Constructs. Ro- utledge, 1991. [8] J. Krivic & F. Solina, Part-level object recognition using superquadrics, Computer Vision and Image Understan- ding, 95(1):105–126, 2004. [9] B. Leibe, A. Leonardis, & B. Schiele, Robust object de- tection with interleaved categorization and segmentation. International Journal of Computer Vision, 77(1-3):259– 289, 2008. [10] T. Lindeberg & J. Eklundh, Scale detection and region extraction from a scale-space primal sketch. In Compu- ter Vision, 1990. Proceedings, Third International Confe- rence on, pp. 416–426, 1990. [11] D. Lowe, Object recognition from local scale-invariant fe- atures. In Proc. of the International Conference on Com- puter Vision, Corfu, IEEE Computer Society, 1999. [12] D. Marr, Vision. W. H. Freeman, San Francisco, CA, 1982. [13] B. A. Olshausen & D. Field, Emergence of simple–cell receptive field properties by learning a sparse code for na- tural images. Nature, (381):607–609, 1997. [14] M. Riesenhuber & T. Poggio, Models of object reco- gnition. Nature Neuroscience Supplement, 3:1199–1203, 2000. [15] E. Rosch, Natural categories. Cognitive Psychology, 4:328–350, 1973. [16] A. Shokoufandeh, et. al , The representation and matching of categorical shape. Computer Vision and Image Under- standing, 103(2):139–154, 2006. [17] E. Sudderth, A. Torralba, W. Freeman, & A. Willsky, Le- arning hierarchical models of scenes, objects, and parts. In Computer Vision, 2005. ICCV 2005. Tenth IEEE In- ternational Conference on, Vol. 2, pp. 1331–1338Vol.2, 2005. [18] S. Todorovic & N. Ahuja, Extracting subimages of an un- known category from a set of images. In Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on, Vol. 1, pp. 927–934, 2006. Matjaž Jogan je asistent na Fakulteti za računalništvo in infor- matiko v Ljubljani. Raziskovalno se ukvarja s hierarhičnimi mo- deli procesiranja vidne informacije. Je avtor in soavtor številnih raziskav s področij umetne zaznave prostorske informacije, sa- modejnega kartografiranja za lokalizacijo in navigacijo mobil- nih sistemov, robustnega in sprotnega učenja, ukvarja pa se tudi z uporabo umetnega vida v interaktivnih sistemih.