Robusztus szemdetektor fejlesztése predikciós módszerek felhasználásával Diplomamunka
Bárdosi Zoltán Robin Témavezet˝o: dr.habil. L˝orincz András 2007. május 22.
Tartalomjegyzék 1. Diplomalejelent˝ o-lap
3
2. Bevezetés 2.1. Bevezet˝o . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. A dolgozat felépítése . . . . . . . . . . . . . . . . . . . . 2.3. Tézisek . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 4 6 6
3. Az emberi látás 3.1. A szem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Szemmozgások típusai . . . . . . . . . . . . . . . . . . 3.3. Szemmozgások modellezése, figyelem . . . . . . . . . .
8 8 11 12
4. SIFT leírók, BOK algoritmus 4.1. Bevezetés . . . . . . . . . . . . . . . . . . . . . . 4.2. SIFT algoritmus . . . . . . . . . . . . . . . . . . 4.2.1. Bevezet˝o . . . . . . . . . . . . . . . . . . . 4.2.2. Skála-tér extrémumok detektálása . . . 4.2.3. Kulcspont lokalizáció . . . . . . . . . . . 4.2.4. F˝oirány hozzárendelése a kulcsponthoz . 4.2.5. Lokális képi leíró számítása . . . . . . . 4.3. PCA algoritmus . . . . . . . . . . . . . . . . . . . 4.3.1. Matematikai háttér . . . . . . . . . . . . . 4.3.2. Alkalmazás . . . . . . . . . . . . . . . . . 4.4. K-Means algoritmus . . . . . . . . . . . . . . . . 4.4.1. Matematikai háttér . . . . . . . . . . . . . 4.4.2. Alkalmazás . . . . . . . . . . . . . . . . . 4.5. GMM - Gauss Keverék Modell . . . . . . . . . . 4.5.1. GMM Model . . . . . . . . . . . . . . . . .
14 14 17 17 17 18 20 21 23 23 24 26 26 26 27 27
1
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
4.5.2. EM algoritmus . . 4.5.3. Kulcspont-zsákok 4.5.4. SVM . . . . . . . . 4.6. A BOK algoritmus tesztje 4.6.1. Els˝o teszt . . . . . 4.6.2. Második teszt . . . 4.6.3. Harmadik teszt . . 4.6.4. Negyedik teszt . . 4.6.5. Diszkusszió . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
28 30 32 33 34 34 34 35 39
5. Biológiailag motivált saliency-detektorok 5.1. Bevezetés . . . . . . . . . . . . . . . . . . . . . . 5.2. Motiváció . . . . . . . . . . . . . . . . . . . . . . 5.3. Kísérlet . . . . . . . . . . . . . . . . . . . . . . . 5.3.1. Adatbázis . . . . . . . . . . . . . . . . . . 5.3.2. Saliency detektálás osztályozási feladata 5.3.3. Konzisztens fixációs pontok . . . . . . . 5.3.4. Tanítóminta összeállítása . . . . . . . . . 5.3.5. Tanítás . . . . . . . . . . . . . . . . . . . . 5.3.6. Eredmények . . . . . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
40 40 40 41 41 42 42 43 43 44
6. SIFT-Saliency modell 6.1. Bevezetés . . . . . . . . . . . . . . . . 6.2. Adatbázis . . . . . . . . . . . . . . . . 6.3. Fixációs térképek . . . . . . . . . . . 6.4. Els˝o kísérlet . . . . . . . . . . . . . . . 6.5. Fixációs pontok távolsághisztogramja 6.6. Második kísérlet . . . . . . . . . . . . 6.7. Diszkusszió . . . . . . . . . . . . . . . 6.8. Harmadik kísérlet . . . . . . . . . . . 6.9. Diszkusszió . . . . . . . . . . . . . . . 6.10.Kitekintés . . . . . . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
45 45 46 47 50 52 55 57 58 60 62
7. Köszönetnyilvánítás
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
64
2
1. fejezet Diplomalejelent˝ o-lap
3
2. fejezet Bevezetés 2.1.
Bevezet˝ o
Az emberiség történelme folyamán kevés új technológia fejl˝odött olyan hatalmas sebességgel és tört be mindennapjainkba olyan hirtelen, mint az informatika. Ma már nehéz olyan tevékenységet találni, amely muveléséhez ˝ ne lenne elengedhetetlenül szükséges, vagy legalábbis rendkívül hasznos a számítógépek használata. A kezdetben szuk ˝ szakmai közösségek által kifejlesztett és felhasznált eszközök egyre szukösebbé ˝ váltak azáltal, hogy a felhasználók köre kiszélesedett. A különböz˝o felhasználások különböz˝o helyzeteket és a számítógéppel való kommunikáció újabb és újabb változatos formáit igénylik. A HCI (humán-számítógép interakció) kutatási feladatai közé tartozik, hogy olyan új, alternatív kommunikációs (adat ki- és beviteli) eszközöket és módszereket fejlesszen, amelyek segítik az ember és gép közötti kapcsolatot az ember számára minél természetesebbé, magától értet˝od˝ové tenni. Az ember számára az egyik legfontosabb információforrás a látás. Meghatározó szerepet játszik a körülöttünk lév˝o világ megismerésében, de ezzel egyid˝oben a látás folyamata sokat elárul a látó bels˝o tudatállapotáról is, szándékairól, hangulatáról. Szemmozgásaink lehet˝oséget biztosítanak a számítógépnek arra, hogy megismerhesse szándékainkat, és természetes módon segíthessen a feladatok megoldásában. Ez nagy segítséget nyújthat a legtöbb
4
ember számára aki számítógépekkel dolgozik, igazán nélkülözhetetlenné viszont olyan testi fogyatékos emberek esetén válik, akik más módon nem, vagy csak nehezen tudnak környezetükkel (és így a számítógépekkel is) kommunikálni. Az ELTE Információs Rendszerek Tanszékén muköd˝ ˝ o NIPG csoportban a többéves kutatómunka eredményeként már rendelkezésre állnak különböz˝o kísérleti kommunikációs eszközök (például szemegér, fejegér, hangegér), amelyek olcsón és széleskörben rendelkezésre álló hardvereszközök (webkamera, mikrofon) segítségével lehet˝oséget nyújtanak a testi fogyatékos emberek számára, hogy a számítógéppel kommunikálhassanak, ezek azonban kifinomult feladatok megoldására nem használhatóak. A jelenleg rendelkezésre álló szemdetektor program még nem alkalmas a felhasználó tekintetének követésére, azaz annak megállapítására a bemeneti kép alapján, hogy a felhasználó pontosan mit is néz, mire fókuszál a képerny˝on. Dolgozatom célja az volt, hogy olyan megoldásokat keressek, amelyek a meglév˝o hardvereszközök segítségével használhatóak, és megbízhatóbbá, pontosabbá teszik annak muködését. ˝ Mivel célunk az volt, hogy a számítógép által használt bemeneti információk megváltoztatása nélkül (a felvételezés módja, a kamera felbontása, stb.) fejlesszük az algoritmust, így kutatási útként els˝odlegesen az új képfeldolgozási, mesterséges intelligencia, illetve kognitív modellezési eredmények megismerését, és az általuk adódó, a témában felhasználható lehet˝oségek felkutatását választottam. A munka folyamán a vizsgált problémakör szerteágazósága miatt az egyes részfeladatokat és ezek elvi megoldhatóságának lehet˝oségét, illetve módjait külön és nagyobb általánosságban vizsgáltam. A diplomamunkámban tárgyalt algoritmusok két, jól elkülöníthet˝o célt szolgálnak. Az els˝o azon képfeldolgozási módszerek javítása és az azokon végezhet˝o id˝obeli predikciós módszerek bemutatása, amelyek a számítógép szempontjából „bemeneti” adatoknak min˝osülnek. Ez a konkrét feladatban a webkamera által nyújtott kép feldolgozási módjait jelenti. A második feladatkör, amely végül hangsúlyosabb szerepet kapott, magának a felhasználónak a modellezhet˝oségét, illetve az általa a látottakra adott válaszreakciók el˝orejelezhet˝oségének kérdését vizsgálja, az általa látott kép (azaz a számítógép által megjele5
nített képek) ismeretében. A második feladatkörben egy már mu˝ köd˝o tekintetkövet˝o rendszer által rögzített adatbázis került feldolgozásra. Az alapötlet az, hogy ha ismerjük a mutatott kép azon régióit, amelyek jó eséllyel vonzzák az alany tekintetét, akkor ez az információ felhasználható a tekintet helyzetének pontosabb becsléséhez.
2.2.
A dolgozat felépítése
A dolgozatom 3. fejezetében röviden összefoglalom az emberi látás fiziológiáját, illetve az ahhoz kapcsolódó alapvet˝o kognitív modellek felépítését. A 4. fejezetben bemutatom a SIFT leírók, illetve az azokra épül˝o általános képi kategorizációra alkalmas „bag-of-keypoints” algoritmus elméleti hátterét, és eredményeit. Ez az algoritmus a szemdetektor szempontjából többcélúan is felhasználható. Egyrészt segíthet a valósideju ˝ gyors AdaBoost detektorok [1] által talált szempozíciók felismerési arányának javításában, másrészt lehet˝oséget biztosít olyan robusztus, felhasználóra jellemz˝o képi jellemz˝ok keresésében, amelyek segítségével pontosabbá tehet˝o a becsült szempozíció, és így a webkamera kép által a fixáció helyére vonatkozó információ is. Az 5. fejezetben bemutatom a SIFT jellemz˝ok neurobiológiai relevanciáját, amely alkalmassá teszi o˝ ket arra, hogy az emberi bottom-up érdekl˝odés egy modelljének épít˝okövévé választhassuk. A 6. fejezetben ismertetek egy egyszeru ˝ bottom-up saliency predikciós modellt, amely a SIFT jellemz˝ok által generált fixációs térképeken alapul, és az ezekkel végzett kísérleteket, és eredményeket.
2.3.
Tézisek
1. A „bag-of-keypoints” módszerrel lehetséges olyan képfeldolgozási keretrendszert létrehozni, amely felhasználásával jó eredményeket tud elérni az általános vizuális kategorizáció felada-
6
tában. Ezt egy objektumdetektálási feladaton keresztül mutatom be. 2. Az el˝oz˝o módszerben használt SIFT detektorok neurobiológiailag relevánsak. 3. A SIFT jellemz˝ok által generált fixációs térképek segítségével jól azonosíthatóak a felhasználó által nézett képek. 4. A fixációs pontok távolságának eloszlása bizonyos mértékig segíthet a felhasználó azonosításában. 5. A fixációs pontok távolságának eloszlása és a SIFT fixációs térképek bizonyos fokig el˝orejelezhet˝ové teszik a felhasználó által a t+1. id˝opontban választott fixációs pontokat a t. id˝opont ismeretében.
7
3. fejezet Az emberi látás 3.1.
A szem
Az emberi érzékek közül a látás rendelkezik az egyik legkifinomultabb szenzoros rendszerrel, a szemmel. A fény a szembe az elején található változtatható méretu ˝ „optikai” nyíláson, a pupillán keresztül jut be. Ezután áthatol a szemlencsén, amely fókuszálja és a szem hátsó falára vetíti, a retinára. A retina felületén helyezkednek el a fényérzékelésért felel˝os sejtek. Az emberi szem sematikus ábrázolása látható a 3.1 ábrán. A fejezetben található képek els˝odleges forrásai: [29, 31].
3.1. ábra.
Itt alapvet˝oen kétféle típusú fényérzékel˝o sejt található. A pálcika sejtek felel˝osek a fényer˝o illetve a kontraszt érzékelésért, ezek 8
rendelkeznek a legnagyobb érzékenységgel, már 1-2 foton beérkezése is aktiválhatja ezt a sejttípust. A különböz˝o hullámhosszú fényt ezek a sejtek nem tudják megkülönböztetni. A színérzékelésért a sejtek másik típusa, a csapsejtek felel˝osek, amelyeknek nagyobb fényer˝ore van szüksége a muködéshez. ˝ A csapsejtek három altípusba sorolhatóak, aszerint, hogy melyik hullámhossz tartományra érzékeny látópigmentet tartalmaznak, a szemben a vörös, a zöld, illetve a kék fényre érzékeny csapsejtek találhatóak. Bár ezen sejtek egy-egy színtartományra specializálódtak, részben érzékenyek a színtartományuk határain található átmeneti színekre is, így az ember által érzékelt színek a három érzékelt „alapszín” keveredési aránya szerint állnak el˝o. Például a sárga szín a vörös és zöld érzékel˝osejtek egyforma arányú aktivitásából származik, ha pedig mindhárom csoport egyformán aktív, akkor fehér színt érzékelünk. A szem ezen tulajdonságán alapul az additív színkeverés, amely a számítógépes megjelenít˝okben mukö˝ dik.
3.2. ábra. A retinán (3.2 ábra) a kétféle sejttípus nem egyenletesen oszlik meg. A retina közepén található a finomfelbontású és csapsejtekben gazdag terület, a fovea centralis. Ez a terület dolgozza fel a szem által fixált pozícióból érkez˝o információkat, azonban terjedelme csak 1-2 fok, szemben a teljes emberi látószöggel, amely körülbelül 50-60 fokos. A 3.3 ábrán látható a foveától távolodva a a csap (cone) és pálcika (rod) sejtek eloszlása a retinán. A fovea területén több mint 200 ezer csapsejt található szorosan egymás mellett elhelyezkedve. A pálcika sejtek ezen a területen minimális számban vannak jelen. A foveától távolodva a csapsejtek száma drasztikusan csökken. A pálcika sejtek maximális számban a foveától számított 20-30 fok közötti tartományban találhatóak. 9
Mivel az éjszakai látásért els˝osorban a pálcikasejtek felelnek, ezért tapasztalhatjuk, hogy látásunk éjszaka nem a fókuszpontban a legjobb, hanem mindig kicsit „mellé” kell néznünk a vizsgált tárgynak.
3.3. ábra. A retina részletes feldolgozásának lokális jellege miatt az ember képtelen egyszerre befogadni és feldolgozni a látható világból érkez˝o teljes képet, emiatt speciális agyi folyamatok által vezérelt mintavételezési és feldolgozási folyamatra van szüksége, hogy gyorsan felmérhesse az o˝ t körülvev˝o világot, és az azon belül figyelmet igényl˝o részleteket. Valószínusíthet˝ ˝ o, hogy a lokális feldolgozásra azért van szükség, mert a látóideg adatátviteli sebessége korlátozott, így az agyba egyszerre csak egy kis terület részletes képe juthat el. Mivel az egész látómez˝or˝ol így párhuzamosan nem alkothat képet az agy, ezért egy szekvenciális feldolgozási folyamatra kényszerül, amelyben a látott információk alapján visszacsatolva egy aktívan vezérelt „letapogatási útvonalat” kell bejárnia a szemnek. A tekintetkövet˝o rendszerek lehet˝oséget adnak a szem útvonalának rögzítésére, és az így nyert információk segítségével már jó eredményeket értek el különböz˝o objektum-detektálási, videó és képtömörítési, illetve vizuális kategorizálási feladatok megoldásában [2, 3, 5, 6]. Ezen megoldások közös jellemz˝oje, hogy a fovea feldolgozási rendszeréhez hasonlóan lokális képi tulajdonságok statisztikus tulajdonságai segítségével próbálják megoldani az adott feladatot. Az objektumdetektálás lokális képi statisztikán alapuló egy módszerének hatékonyságát mutatom be a „bag-of-keypoints” algoritmussal foglalkozó fejezetben. 10
A háttérben zajló feldolgozási folyamat tulajdonságairól sokat elárulnak a különböz˝o szemmozgás típusok, amelyek röviden a következ˝o részben veszek át.
3.2.
Szemmozgások típusai
Az emberi szemmozgások [24, 30] közül kiemelten kétfélét mutatok be: Az els˝o az úgynevezett fixációs szemmozgások csoportja, amelyek olyan kis, és tudattalan szemmozgások, amelyek a vizuális fixáció alatt jelentkeznek. Három kategóriába sorolhatóak (microsaccades, ocular drifts, ocular microtremor). Bár létezésük már az 1950-es évek óta ismert, pontos szerepük máig vitatott. A legújabb kutatási eredmények szerint [25] a fixációs mozgások az els˝odleges látókéregben (V1) található neuronok folyamatos aktivitásának fenntartására hivatottak, amelyek a legnagyobb érzékenységet az un. tranziens stimulusokra (azaz a jel hirtelen megváltozásaira) mutatják. Amennyiben ezen fixációs szemmozgások hatását kísérleti körülmények között kioltjuk, úgy a fixáció által érzékelt látvány gyorsan megfakul, vagy bizonyos esetekben (alacsony kontrasztú képek, élek hiánya) teljesen el is tunik. ˝ A tekintetkövetési adatbázisokban a fixációs szemmozgásokat külön nem mérik, hanem csak a fixáció átlagpozíciója, illetve ideje szerepel. A továbbiakban a szem fixációs pontja alatt ezt az átlagos pozíciót fogom érteni. A fixációk átlagos ideje 100-200 ms. A másik fontos szemmozgás az úgynevezett szakkádikus szemmozgás (vagy szakkád), amely alatt a két szem gyors, azonos irányú mozgását értjük. A szakkádikus szemmozgás az emberi test leggyorsabb mozgása, a szögsebessége elérheti az 1000 fok / másodpercet is. A szakkád átlagos ideje 20-tól 200 ms-ig terjed. A szakkádok ideje alatt a retinán elmosódó kép jelenik meg, amelyet az idegrendszer a képalkotásban nem vesz figyelembe, így a szakkád ideje alatt a látottak nem tudatosulnak. Ezt az effektust hívjuk szakkádikus elnyomásnak (saccadic suppression, saccadic masking). A szakkád ideje alatt fellép˝o villanásokra, vagy tárgyak elmozdulására az agyunk érzéketlen.
11
Bár „tudatosan” a szakkád ideje alatt az emberek tulajdonképpen vakok, kísérletek bizonyítják, hogy a szakkád ideje alatt fellép˝o változások mégiscsak befolyásolni tudják a szakkádtervez˝o rendszer muködését. ˝ Ennek pontos muködése ˝ azonban még nem ismert.
3.3.
Szemmozgások modellezése, figyelem
Ahhoz hogy pontosabban megérthessük, feldolgozhassuk és esetlegesen el˝orejelezhessük az egy adott kép megfigyelése folyamán el˝oálló emberi letapogatási útvonalakat, fontos megismerni a háttérben meghúzódó tervezési folyamatot. Az elmúlt években sok kísérlet történt olyan modellek alkotására, amelyek jól magyarázzák az emberi szemmozgások útvonalait [12, 14, 15]. A fontosabb publikált modellek közös tulajdonsága, hogy két f˝o komponensre osztják a vezérl˝o folyamatot. Az els˝o az úgynevezett alulról-felfele terjed˝o vezérelvu ˝ (bottom-up, BU) figyelmi komponens , amelynek bemenetét tulajdonképpen az aktuális látottak alkotják, általában tudattalanok, „automatikusak”, amelyek mintegy el˝oszelektálják a néz˝o figyelmére érdemes képi elemeket. A figyelmi kontrol másik részét a felülr˝ol-lefele terjed˝o vezérelvu ˝ (top-down, TD) komponensek határozzák meg. Ezek bemenete tulajdonképpen a megfigyel˝o bels˝o állapota, azaz a néz˝o tudatos motivációi, tudatalatti / érzelmi állapota, illetve a feladatfügg˝o faktorok. Mivel a tudatos gondolkodás rendkívül összetett és egyénileg is változatos folyamat, nehéz lenne olyan TD modellt alkotni, amely minden tényez˝ot kell˝o pontossággal és súllyal figyelembe tud venni. A modellek pontosan emiatt inkább a bottom-up tényez˝ok pontos modellezésre törekszenek, és a TD befolyásokat csak nagyon egyszeru ˝ modellezési módszerekkel, vagy egyáltalán nem veszik figyelembe. Közös tulajdonsága még a modelleknek, hogy a BU kontrolt olyan „érdekesség térképek” (saliency map) segítségével definiálják, amelyek a kép pontjainak függvényében adják meg azok fontosságát. Dolgozatom második felében én is ezt a sémát követve felépítek egy SIFT lokális képi jellemz˝okön [5, 7] alapuló saliency map-et, 12
majd ennek predikciós képességeit vizsgálom. Választásom azért esett a SIFT jellemz˝ok felhasználására, mert a tapasztalatok alapján ezek a képfeldolgozásban széles körben és jó eredményekkel történtek felhasználásra [2, 3, 6]. A bottom-up feldolgozás modellezésében fontos szerepet kap az a tény is, hogy az emberi agy a jelenleg elfogadott modellek szerint már a vizuális feldolgozás elején kettéosztja a feldolgozás menetét. Az egyik feldolgozási pálya az un. ventrális pálya (ventral pathway), amely els˝osorban „mit látok” kérdésre felel, a látott textúrák, színek, formák struktúrális aspektusait vizsgálja, de nem veszi figyelembe azok elhelyezkedését. A másik ilyen feldolgozási útvonal az un. dorzális (dorsal) pálya, amely inkább ezen komponensek térbeli elhelyezkedésével foglalkozik. A dolgozatom els˝o felében bemutatott általános vizuális kategorizációt megvalósító „bag-of-keypoints” algoritmus felépítésében a ventrális pálya által ellátott feladatkör egyfajta modelljének is tekinthet˝o, hiszen muködését ˝ csak a lokális jellemz˝ok terében számított leíró-eloszlások befolyásolják, azok térbeli pozícióját nem veszi figyelembe.
13
4. fejezet SIFT leírók, BOK algoritmus 4.1.
Bevezetés
A számítógépes képfeldolgozásban felmerül˝o egyik legáltalánosabb probléma, hogy az adott hatalmas dimenziós pixelszintu ˝ bemen˝o adatokat valamilyen általunk specifikált (általában magasszintu) ˝ elv szerint osztályokba rendezhessük. A képfeldolgozási eszközök általában az alacsonyszintu ˝ pixeltér egyes tulajdonságainak kiemelésével, azok szurésével ˝ foglalkoznak. A legtöbb tervezett algoritmus ezen alapvet˝o módszerek ügyes kombinációi segítségével oldja meg a célfeladatot. A klasszikus módszereknél azonban fontos megemlíteni, hogy ezek mindig egy-egy speciális részfeladatra vonatkoznak, általánosító képességük általában gyenge, és az eljárások érzékenyek a paraméterezésre. A fenti problémakör egy általánosabb és nehezebb megfogalmazása az, amikor nem el˝ore nem ismert az osztályozás vezérelve, és a rendszernek képesnek kell lennie az alacsonyszintu ˝ vizuális adatokat magasszintu, ˝ szemantikus kategóriákhoz rendelni. A GVC (generic visual categorization - általános vizuális kategorizálás) feladatok célja, hogy tanítóminták alapján modelleze ezeket olyan módon, hogy kapcsolatot létesít ezen kategóriák, illetve a vizuális adatokból kinyerhet˝o alacsonyszintu ˝ információk között. A GVC feladat jelenleg ismert leghatékonyabb megoldását az un. kulcspont-zsákok („bag-of-keypoints”) jelentik [2, 3, 6]. A továbbiakban ismertett módszer a Xerox laboratóriumban végzett és publi-
14
kált kutatások reprodukcióján alapszik. A tesztek során az itt leírt módszerek saját implementációját használtam fel, amelyr˝ol részletes információkat a nagyprogramom dokumentációja tartalmaz, amely a diplomamunkámhoz mellékelt CD-ROM-on elérhet˝o. A program implementációja során felhasznált könyvtárak elérhet˝osége: [34, 35, 36]. A módszer lényege hogy az egyes képekb˝ol kinyerhet˝o alacsonyszintu, ˝ de bizonyos invariancia-tulajdonságokkal rendelkez˝o képi jellemz˝okb˝ol a szövegfeldolgozásban (text processing) elterjedt kulcsszókivonatolás (bag-of-keywords) algoritmusokhoz [4] analóg módon kulcspontok (lokális képi leírók) kivonatolásával, illetve azok eloszlásának számításával modellezi a képet. A képek kulcspont-zsákokkal történ˝o leírása közben az alacsonyszintu ˝ jellemz˝ok képbeli, illetve egymáshoz képesti helyzete, mint információ elveszik, emiatt az algoritmus els˝osorban egyes jellemz˝ok jelenlétét képes meghatározni az adott képeken, azok poziciójára és orientációjára érzéketlen marad. Ez a látszólagos gyengesége teszi mégis rendkívül er˝ossé a kategorizálási feladatok megoldásában. A „bag-of-keyponts” vagy BOK séma els˝o lépése mindig az alacsonyszintu ˝ képi jellemz˝ok kivonatolása a tanulási, illetve tesztmintákból. Fontos, hogy ezek a jellemz˝ok lehet˝oleg reprodukálhatóak legyenek, azaz egy adott kategórián belüli képek esetén képesek legyenek olyan, az adott osztályra jellemz˝o diszkriminatív információt nyújtani, ami lehet˝ové teszi hogy az adott osztályt azonosítsuk. Példaképpen, amennyiben egy konkrét objektum felismerése a cél, akkor a kiválasztott alacsonyszintu ˝ jellemz˝oknek olyan módon kell jellemezni az objektumot, illetve annak részeit, hogy különböz˝o irányból, távolságból, illetve megvilágítással készült képek esetén maguk a jellemz˝ok is közel azonos pontokat vegyenek fel, illetve leíróik értékei is hasonlóak legyenek. Ilyen alacsonyszintu ˝ jellegzetességek keresésére alkalmas a SIFT algoritmus, amely a BOK séma alacsonyszintu ˝ képfeldolgozást biztosító eljárása. A BOK séma második lépése az, hogy a képekb˝ol kivonatolt jellemz˝ok segítségével megadott számú kulcspontot határoz meg, amelyek jellemz˝oek az adott tanulási feladatra. A kulcspontok számának, illetve a kulcspontok értékének jó meghatározása fontos az algoritmus hatékonyságának szempontjából. Minél jobban si15
kerül a kulcspontoknak meghatározni azon jellemz˝oket, amelyek a legjobb leírást adják az egyes vizuális kategóriákról, annál megbízhatóbb modelleket nyújtanak az ezeken alapuló kulcspont-zsákok. A program kétféle sémát tartalmaz a kulcspontok meghatározására, mindkett˝o a statisztikában és mesterséges intelligenciában nem-felügyelt tanulási algoritmusként ismeretes (unsupervised-learning algorithm), amelyek lehet˝oséget adnak a képekb˝ol kinyert jellemz˝ok klaszterezésére, és a kulcspontok meghatározására ezen klaszterek középpontjai segítségével. Az els˝o ilyen algoritmus a K-means, amely az egyik legegyszerubb ˝ ismert klaszterez˝o. Ez a módszer az un. „hard-clustering” probléma lokális megoldását adja, amelyben minden elem pontosan egy klaszterhez tartozhat. Ennél egy finomabb megoldást jelent a GMM (Gaussian-Mixture-Modell) modell, amely Gauss eloszlások keverekével képes a megadott adatokat modellezni. A GMM illesztés tulajdonképpen egy valószínuségi ˝ alapú „soft-clustering” módszer, amelyben az egyes adatpontokat a klaszterközéppontokhoz tartozás valószínusége ˝ jellemzi. Mindkét modellre igaz, hogy lokális-optimalizációra képes, és el˝ore megadott számú klaszterrel dolgozik, ezért tanításukat speciális iterációban kell végezni, amely fokozatosan növeli a kért kulcspontok számát, illetve egy-egy kulcspontszám mellett is több iterációra lehet szükség, hogy az optimális kulcspontokat meg tudjuk határozni. Ez az algoritmus leginkább id˝oigényes lépése, az iteráció egy egy lépése is órákban mérhet˝o egy kb. 150 képet tartalmazó adatbázis feldolgozása esetén. A BOK algoritmus diszkriminációs képességei er˝osen függnek a kulcspontok helyes megválasztásától. Az algoritmus harmadik lépésében a tanult modell alapján lehet˝oség van a képek kulcspont-zsákokkal való jellemzésére. Itt generáljuk az un. középszintu ˝ jellemz˝ot, amely a kép középszintu ˝ leírójaként funkcionál. Ezek a leírók a bemenetei az utolsó lépcs˝oben alkalmazott felügyelt osztályozást megvalósító SVM algoritmusnak. A kulcspont-hisztogramok számolásának, illetve a diszkriminációs képesség mérési módjának részletei a fejezet végén kerülnek bemutatásra.
16
4.2. 4.2.1.
SIFT algoritmus Bevezet˝ o
A digitális képek pixelszintu ˝ információi a képek szemantikus értelmezéséhez több szempont miatt is hátrányosak. Els˝osorban azért, mert rendkívül magas a dimenziószámuk, ami kritikus a legtöbb mai tanulóalgoritmus számára. Ezenkívül a pixelek, mint alapszintu ˝ jellemz˝oi a képnek nagyon érzékenyek a kép elkészítésekor fennáló körülményekre, mint például a megvilágításra, a képalkotó berendezés sajátosságaira (felbontás, fényérzékenység, színérzékenység, zaj), illetve a felvételezés sajátosságaira (kamera távolsága, iránya). A fenti okok miatt a legtöbb képfeldolgozási algoritmus els˝o lépésében transzformálja (szuri) ˝ a képeket olyan jellemz˝ok egy halmazára, amelyek a megoldandó feladat szempontjából relevánsak, és lehet˝oség szerint a kiinduló adathalmaz méretét is jelent˝osen csökkentik. Az objektumok felismeréshez rendkívül fontos, hogy olyan képi jellemz˝oket tudjunk keresni, amelyek a leginkább invariánsak a szokásos képi transzformációkra (affin transzformációk, szín és fényer˝o eltérések, pixel szintu˝ zaj). A programban felhasznált SIFT (Scale-Invariant Feature Transform) jellemz˝ok [7] lehet˝oséget nyújtanak ilyen jellegu ˝ kulcspontok, illetve azokhoz tartozó leírók keresésére. A SIFT jellemz˝ok számításához az alábbi f˝obb lépcs˝ok szükségesek:
4.2.2.
Skála-tér extrémumok detektálása
Legyen I(x, y) a kétdimenziós kép. Ekkor a skála-teret az alábbi függvény definiálja: L(x, y, σ) = G(x, y, σ) ∗ I(x, y) ahol ∗ a konvolúció operátort jelöli (x, y)-ban, és G(x, y, σ) =
1 − (x2 +y2 2 ) e 2σ 2πσ 2
egy 2 dimenziós σ skálájú diszkrét Gauss sur ˝ uségfüggvény ˝ (x, y)ban. 17
A stabil invariáns kulcspontok detektálásának hatékony megvalósításához szükség van a DoG (Difference-of-Gaussians) konvolúció definiálására is. Ez két, egymáshoz közeli skálán fekv˝o Gauss eloszlás különbségének konvolúciója a képpel: D(x, y, σ) = (G(x, y, kσ) − G(x, y, σ)) ∗ I(x, y) = L(x, y, kσ) − L(x, y, σ) a fenti DoG egy approximációját adja az LoG (Laplacian-of-Gaussians) függvénynek (σ 2 ∇2 G), amelyr˝ol [5] belátta, hogy széls˝oértékei adják az ismert detektorok közül az elforgatásra és skálázásra leginkább invariáns képi jellemz˝ok pozícióit. σ∇2 G =
∂G G(x, y, kσ) − G(x, y, σ) ≈ ∂σ kσ − σ
és emiatt, G(x, y, kσ) − G(x, y, σ) ≈ (k − 1)σ 2 ∇2 G vagyis a DoG approximáció csak konstans szorzóban tér el a szükséges LoG értékekt˝ol, amely nem befolyásolja a széls˝oértékek helyét. D(x, y, σ) széls˝oértékeinek hatékony meghatározásához a skálateret oktávokra (azaz 2n σ szerint), azon belül pedig k-szerinti diszkrét lépésekre kell osztani. Ezután minden oktávon lehet a szomszédos L(x, y, kσ), illetve L(x, y, σ) képek különbségeként el˝oállítani az adott σ-hoz tartozó D(x, y, σ) „képeket”. Ezután D(x, y, σ) lokális széls˝oértékeit úgy határozhatjuk meg, hogy megkeressük azon pontokat, amelyek kisebbek/nagyobbak az o˝ ket az azonos σ skálán körülvev˝o 8 pixelnél, illetve az eggyel felette és alatta található σkhoz tartozó D képek, 3x3-as (x, y) közepu ˝ régiók pixeleinél. (Azaz olyan térbeli 3x3x3-as „kocka” középpontokat keresünk amelyekben D felvett értéke kisebb/nagyobb a pont szomszédaiban felvett értékeknél). A 4.1 ábrán a DoG approximációs séma 1, illetve 2D ábrázolását láthatjuk.
4.2.3.
Kulcspont lokalizáció
A DoG széls˝oértékekhez tartozó pontokban csak akkor van tényleges invariáns tulajdonságokkal rendelkez˝o jellegzetesség, hogyha 18
4.1. ábra. kizárható, hogy az adott pont környezete alacsony kontrasztú, illetve hogy az adott pont nem egy élen fekszik. Mindkett˝ohöz szükséges, hogy finomítsuk a széls˝oérték pontos koordinátáit szubpixel pontossággal. Brown módszere szerint, 3 dimenziós kvadratikus felület illesztésével elérhet˝o, hogy a pontosabban határozzuk meg a széls˝oérték helyzetét, kiindulva a D(x, y, σ) Taylor sorfejtéséb˝ol: D(x) = D +
1 ∂2D ∂DT x + xT x ∂x 2 ∂x2
ahol D és a deriváltak a mintaközéppontban vannak kiszámolva, x = (x, y, σ)T pedig a mintaközépponttól való offszetet jelöl. A tényleges széls˝oérték helyzetére adódó képlet, deriválás és nullává tétel után: −1 ∂ 2 D ∂D x ˆ=− 2 ∂x ∂x ahol a másodrendu ˝ deriváltmátrix (Hessian), illetve a deriváltmátrix közelíthet˝o D szomszédos mintapontokon felvett értékeivel. Ez egy 3x3-as lineáris egyenletrendszerhez vezet. Ha x ˆ bármely dimenzióban nagyobb 0.5-nél, akkor a számolást meg kell ismételni a hozzá közelebb es˝o mintapontban vett értékek segítségével. D(ˆ x) értékének segítségével könnyen meghatározható, hogy az adott pontban elegend˝o mértéku-e ˝ a kontraszt. D(ˆ x) = D +
1 ∂DT x ˆ 2 ∂x
Amennyiben |D(ˆ x)| < threshold, ahol threshold egy el˝ore megadott érték (a cikkben 0.03, nálunk nagyságrendileg hasonló érték), a kulcspont elutasításra kerül, mivel alacsony kontrasztú. 19
Az élek kiszurésére ˝ a Harris éldetektort használjuk. Ennek alapötlete, hogy meghatározza az adott pontban a f˝oirányokban vett görbületek arányát, és ha ez magasabb egy adott küszöbértéknél, akkor él van az adott pontban, tehát a kulcspont eldobandó. A f˝ogörbületeket az alábbi Hessian mátrixból kiindulva számítjuk ki: Dxx Dxy H= Dxy Dyy ahol a másodrendu ˝ deriváltakat a szomszédos mintapontokból közelítjük. H sajátértékei arányosak D f˝ogörbületeivel az (x, y) pontban. Jelöljük α-val a nagyobbik, és β-val a kisebbik sajátértéket. Ekkor T r(H) = Dxx + Dyy = α + β Det(H) =Dxx Dyy − (Dxy )2 = αβ Legyen r az arányossági tényez˝o a két sajátérték között, azaz α = rβ. Ekkor: T r(H)2 (r + 1)2 (α + β)2 (rβ + β)2 = = = Det(H) αβ rβ 2 r A fenti képletek segítségével egy adott pontban könnyen megállapítható, hogy a f˝ogörbületek aránya meghalad-e egy bizonyos küszöböt, azaz él található-e az adott pontban. Az r arányossági tényez˝o az edge_threshold, amely szintén el˝ore definiált érték az algoritmusban.
4.2.4.
F˝ oirány hozzárendelése a kulcsponthoz
A kulcspontok irányultsága alatt az egyes kulcspontokhoz tartozó irányvektort értünk, amelyhez képest relatívan számolhatóak a kulcsponthoz tartozó leíró-értékek. Ahhoz, hogy a kulcspontok elforgatás invariánsak legyenek, ennek a f˝oiránynak jól reprodukálhatónak kell lennie. A SIFT eljárásban az alábbi algoritmust használjuk a f˝oirány meghatározására: 20
Legyen x ˆ = (ˆ x, yˆ, σ ˆ )T a kulcspont helyzete a skála-térben, és L(x, y) = L(x, y, σ), ahol σ a σ ˆ -hoz legközelebbi rendelkezésre álló Gauss-finomított kép skálája. Így az orientáció, mivel a tényleges pozícióhoz legközelebbi skálán végezzük a számítást, skálafüggetlen lesz. Ezután, minden L(x, y) mintához hozzárendelünk egy gradiensmagnitúdót, és egy orientációt az alábbi módokon: p m(x, y) = (L(x + 1, y) − L(x − 1, y))2 + (L(x, y + 1) − L(x, y − 1))2 amely az (x, y) ponthoz tartozó gradiens magnitúdó, θ(x, y) = tan−1 ((L(x, y + 1) − L(x, y − 1))/(L(x + 1, y) − L(x − 1, y))) A fenti értékekb˝ol egy orientáció-hisztogram készül, amelynek 36 rekesze reprezentálja a 360 fokos elforgatási teret. Minden egyes minta a gradiens magnitúdóval, illetve egy G(x, y, 1.5σ) Gauss eloszlással súlyozva kerül bele a hisztogram megfelel˝o rekeszébe. A hisztogram legmagasabb csúcsához tartozó irány lesz a kulcspont f˝oiránya. Amennyiben a hisztogramnak van további csúcsa is, amely legalább 80%-a a legmagasabb csúcsnak, ezekkel a f˝oirányokkal is elkészülnek a SIFT jellemz˝ok, és így az adott ponthoz több jellemz˝o is készül, különböz˝o orientációkkal. Ez az algoritmus stabilitását segíti el˝o.
4.2.5.
Lokális képi leíró számítása
Az eddigiek alapján rendelkezésre áll egy adott kulcspont pozíciója a skála-térben, illetve a hozzárendelt orientáció. A tényleges képi jellemz˝ot ezek segítségével számoljuk. A leírók számításához használt modell neurobiológiai indíttatású, viselkedésük hasonló az els˝odleges látókéregben található komplex sejtek muködéséhez. ˝ Ezek a sejtek egy adott térbeli frekvencián egy adott orientációra érzékenyek, miközben a térbeli pozícióra korlátozottan érzéketlenek. Egy lokális képi leíró a SIFT-128 modellben a kulcspont körüli 16x16-os rácsot képezi le 4x4 darab, egyenként 8 orientációt tartalmazó hisztogramra, amelyek el˝oállítása a f˝oirány keresés algoritmusának megfelel˝oen történik. 21
Így az egyes hisztogramok egy 4x4-es képtartományt összegeznek, és az ehhez a tartományhoz tartozó leíró számértékek a 8 rekeszes orientációhisztogram értékei lesznek.
22
4.3.
PCA algoritmus
A PCA (Principal Component Analysis - f˝okomponens analízis, amely diszkrét Karhunen-Loève transzformáció néven is ismert) algoritmus [28] a képfeldolgozásban, adatbányászatban és mesterséges intelligencia kutatásban elterjedt statisztikai módszer, amelynek segítségével magasdimenziós adathalmazokban tudunk olyan f˝okomponenseket keresni, amelyeknek információt adhatnak az adathalmazt generáló alacsonyabb dimenziós folyamatok struktúrájáról. Az algoritmus tulajdonképpen egy új „bázist” állít fel a meglév˝o adathalmazon (azaz orthogonális transzformációt végez), amelynek elemei az adott irányba es˝o varianciák nagysága szerint sorrendbe állíthatóak. Feltételezve, hogy az adatok els˝osorban ezek mentén a nagy-varianciájú irányok mentén tartalmaznak fontos információt, míg az adatokat terhel˝o zaj varianciája nagyságrendben kisebb, lehet˝oség van dimenziócsökkentésre oly módon, hogy az adathalmazt vetítjük a f˝obb komponensekre.
4.3.1.
Matematikai háttér
Legyen A ∈ RdxN , ahol N ∈ N az adatbázisban szerepl˝o minták (vektorok) száma, d ∈ N pedig a vektorok dimenziója. Ekkor A = a11 · · · a1N .. . . .. , és legyen . . . ad1 · · · adN ai = (a1i , . . . , adi )T az i.-ik mintavektor, valamint ¯i = (a1i − a a ¯i , . . . , adi − a ¯i )T az i.-ik centrált mintavektor, ahol a ¯i =
N 1 X aik , i ∈ {1 . . . d} N k=1
a dimenziók szerinti mintaátlagok. 23
Ekkor Dimi , és Dimj , i, j ∈ {1 . . . d}, azaz az adatok i. és j. dimenziója közötti kovarianciája: PN (aik − a ¯i )(ajk − a ¯j ) cov(Dimi , Dimj ) = k=1 N −1 Ekkor az adatokhoz rendelhet˝o kovariancia-mátrix a következ˝o alakú: C = (cij : cij = cov(ai , aj )) ∈ Rdxd
(i, j ∈ {1 . . . d})
A fenti kovariancia-mátrix sajátértékeinek (λk ), k ∈ {1 . . . d} sorrendje határozza meg a f˝okomponensek sorrendjét, a legnagyobb sajátértékhez tartozik a legnagyobb variancia. Az adott λk sajátértékhez tartozó sajátvektor (vi ∈ Rd ) határozza meg az ahhoz tartozó f˝okomponenst. A sajátvektorokat a sajátértékük szerint csökken˝o sorrendbe helyezve, kaphatjuk meg a PCA transzformációs mátrixát: MP CA = v1 · · · vd amelynek segítségével az egyes mintavektorok PCA térbe transzformált elemei a következ˝o módon kaphatóak meg: pi = MP CA · ¯ ai Ha a kisebb sajátértékekhez tartozó sajátvektorokat elhagyjuk a PCA transzformációs mátrixából, akkor projekciós mátrixot kapunk, amely csökkenti a minták dimenzióját, miközben igyekszik az adatok össze varianciájából, és így annak információtartalmából a lehet˝o legtöbbet megtartani.
4.3.2.
Alkalmazás
A BOK algoritmus az egyes tanulóképekb˝ol alkotott alacsonyszintu ˝ jellegzetességeket a SIFT-128 algoritmus segíségével számítja ki, képenként nagyságrendben 1000-1500 jellegzetességet. Nagyobb tanulóminta esetén (pl. 150 kép esetén) ez mintegy 400 ezer SIFT minta. Egyrészt a kés˝obbi kluszterez˝oalgoritmusok id˝o és helyigénye, másrészt a SIFT-128 adatok redundanciája miatt is hasznos 24
az alacsonyszintu ˝ jellegzetességek dimenziójának csökkentése. A tesztek során a a 128 dimenziós SIFT jellemz˝oket redukáltuk 50 dimenziós jellemz˝okké, az univerzális tanítómintán alkalmazott PCA segítségével. Ez a kés˝obbi algoritmusok helyigényét is több mint 50%-al csökkentette.
25
4.4. 4.4.1.
K-Means algoritmus Matematikai háttér
A K-means egy úgynevezett klaszterez˝o algoritmus, amelynek segítségével K partícióra lehet osztani a mintaadatokat, attribútumaik alapján. Az eljárás feltételezi, hogy ezek az attributumok egy N dimenziós vektorteret alkotnak. A módszer lényege, hogy megállapítjuk azt a K darab mintaközéppontot (az adott klaszterbe tartozó minták átlagát), illetve a mintapontok egy olyan felcímkézését, hogy az alábbi célfüggvény minimális legyen: V =
K X X
|xj − µi |2
i=1 xj ∈Si
P ahol Si , i ∈ {1, . . . , K} a klaszterhalmazok, µi = |S1i | xj ∈Si xj az egyes klaszterek centroid középpontja. Els˝o lépésében az algoritmus véletlenszeruen, ˝ vagy el˝ore megadott heurisztika alapján particionálja a mintákat. Ezután minden egyes lépésben az algoritmus megállapítja az új centroidokat, majd újraparticionálja a mintapontokat, hozzárendelve mindegyiket a hozzá legközelebbi centroid által reprezentált klaszterhez. A fenti két lépést addig iterálja, ameddig az nem konvergál, azaz a partíciók nem stabilizálódnak. Mivel a K-means algoritmus nemdeterminisztikus és lokális minimumhelyet keres, ezért érdemes egy adott adathalmazon többször is futtatni, és ezek közül kiválasztani azon pontokat, amelyek a legjobban felhasználhatóak a kulcspontzsákok alkalmazásához, vagyis amely kulcspontokon a legjobb diszkriminációs arányt éri el az SVM osztályozó.
4.4.2.
Alkalmazás
A k-means algoritmus által meghatározott középpontok felhasználhatóak a kulcspont hisztogramok számításához közvetlenül [?], vagy pedig felhasználhatóak a GMM modellek tanításához indítási paraméterekként. 26
4.5.
GMM - Gauss Keverék Modell
A Gauss Keverék Modell (Gaussian Mixture Model), vagy GMM lehet˝oséget biztosít arra, hogy a K-means kulcspontokon értelmezett diszkrét eloszlások hisztogramjai (amelyek alapesetben a kulcspontzsákok hisztogramjainak felelnek meg [6]-ben) helyett egy folytonos eloszlásmodellel dolgozhassunk. Ennek az az el˝onye, hogy így nem csak azt tudjuk meghatározni, hogy egy adott alacsonyszintu ˝ jellemz˝o melyik kulcsponthoz esik legközelebb, hanem hogy milyen valószínuséggel ˝ tartozik egy adott kulcsponthoz. Ezzel a plusz információval súlyozva a hisztogramot, az folytonosabbá tehet˝o, ami megnövelheti az osztályozók diszkriminációs képességeit az adatokon.
4.5.1.
GMM Model
A GMM modell rögzített N számú k-dimenziós Gauss eloszlás keverékével modellez egy tetsz˝oleges k-dimenziós eloszlásfüggvényt. Legyenek Gi ∼ N (µi , Σi ) az alap Gauss eloszlások µi várható értékkel és Σi kovarianciamátrixszal. A továbbiakban feltesszük, hogy a kovarianciamátrix diagonális. Ez jelent˝osen csökkenti a modell illesztésének költségét. Legyenek wi -k az adott indexu ˝ keverék el˝ofordulásának valószínuségei ˝ a modellben. Így a GMM modell összes paraméterei: λ = (wi , µi , Σi : i ∈ {1, . . . , N }) Egy adott x megfigyelés esetén, annak valószínusége, ˝ hogy x-et a λparaméterezésu ˝ GMM modell generálta: P (x | λ) =
N X
wi pi (x)
i=1
ahol az egyes komponensekhez tartozó valószínuségek: ˝ 1 exp − 2 (x − µi )T Σ−1 i (x − µi ) pi (x) = 1 (2π)k/2 |Σi | 2 27
ahol |·| a determináns-operátort jelöli.
4.5.2.
EM algoritmus
Legyen X = {xt }Tt=1 a tanítóminták halmaza, T a tanítóminták száma, N a keverékben található Gauss eloszlások száma, λ pedig a GMM paraméterei. A GMM Model tanításához az EM (expectation-maximization) algoritmust használjuk [10], amely egy két lépéses iterációs algoritmus, és a paraméterekben vett log-likelihood függvény (log P (X | λ)) maximalizálásán alapul. Az els˝o lépésben (E-step) az algoritmus kiszámolja, hogy az egyes xt minták milyen valószínuséggel ˝ generálódtak az i. Gauss keveréktag által: wi Pi (xt ) γt (i) = P (i | xt , λ) = PN j=1 wj Pj (xt ) A második lépésben (M-step) az algoritmus frissíti a GMM paramétereket a E-lépés eredményével: T 1X wˆi = γt (i) T t=1
PT
µ ˆi = Pt=1 T
γt (i)xt
t=1
2
(ˆ σi ) =
PT
γt (i)
2 t=1 γt (i)xt PT t=1 γt (i)
− (ˆ µi )2
ahol x2 = diag(xxT ). Az EM algoritmus igen érzékeny az inicalizáló paraméterekre, mivel csak lokális optimumponthoz való konvergenciája garantált. Ugyan a GMM illesztéshez léteznek már globális optimalizációs módszerek [9], ezek sebessége azonban jóval lassabb, és a felhasznált adatbázisok esetén túlságosan sok ideig tartana a tanítás. Az itt felhasznált implementációban a lokális EM módszernél maradtam.
28
A legelterjedtebb inicializálási megoldás az, hogy a K-means algoritmus által el˝ozetesen meghatározott klaszterközéppontok kerülnek a kiindulási µi értékek helyére, a variancia pedig az ezen klasztereken számolt empirikus variancia értékek. Egy alternatív megoldást vázol fel az inicializálási problémára [6]. Ebben a megoldásban kiindulásképpen csak N = 1 Gauss eloszlás szerepel a GMM keverékben, majd ezeknek a számát iteratívan növelik. Az iteráció két f˝o lépésb˝ol áll. Az els˝o lépésben minden olyan Gauss eloszlást, amelyhez egy adott küszöbértéknél több megfigyelés tartozott, kettésosztunk, és kis mértékben perturbáljuk az új eloszlások átlagát. A második lépésben ezután folytatjuk az EM iterációt egészen addig, ameddig nem konvergál. Ezt a két lépést addig ismételjük, ameddig a kívánt Gauss eloszlások számát a keverékben el nem érjük. A módszer további el˝onye, hogy mivel minden lépésben elleno˝ rizhet˝o az aktuális kulcspontokon a kulcspontzsák algoritmussal tanított osztályozók hatékonysága, ezért menetközben megállapítható az is, hogy mennyi az adott feladathoz optimális kulcspontzsákhoz szükséges Gauss eloszlások száma. Erre a módszerre a kés˝obbiekben progresszív GMM tanításként fogok hivatkozni. Általánosságban elmondható, hogy a BOK algoritmus tanításai lépései közül a klaszterezés bizonyult a leginkább gép és id˝oigényes részfeladatnak. A tesztek futtatása során egy adott kulcspontszám el˝ozetes meghatározása után mindig a progresszív GMM tanítási sémát alkalmaztam. A [11] cikk eredményei szerint a lokális optimumot garantáló EM algoritmus több nagyságrenddel történ˝o gyorsítására is lehet˝oség van az adatok megfelel˝o el˝ofeldolgozása esetén, valamint az egyes iterációk is párhuzamosíthatóak többprocesszoros rendszerek segítségével.
29
4.5.3.
Kulcspont-zsákok
Egy kulcspont-zsák egy adott kép jellegér˝ol ad információt, az alacsonyszintu ˝ jellegzetességek kulcspontok szerinti eloszlásának hisztogramja segítségével. Egy adott képhez tartozó zsák el˝oállításához els˝o lépésben szükséges a képen található alacsonyszintu ˝ jellegzetességek meghatározása. Ezt a SIFT algoritmus segítségével végezzük. Mivel ezek a jellegzetességek még magasdimenziósak, ezért szükség van az univerzális tanítómintán alkalmazott PCA algoritmus által meghatározott bázis segítségével dimenziócsökkentésre. Itt a tanításhoz hasonló módon a 128 dimenziós SIFT jellemz˝oket 50 dimenziós jellemz˝okké transzformáljuk. A továbbiakban kétféle módon lehet eljárni. Amennyiben a Kmeans modellel dolgozunk, minden egyes jellemz˝or˝ol meg kell állapítanunk, hogy melyik centroidhoz (kulcsponthoz) tartozik. Ezt a jellemz˝o, illetve a kulcspontok közötti euklidészi távolság segítségével állapíthatjuk meg, minden jellemz˝ot a hozzá legközelebb álló centroidhoz rendelve. Ezáltal meghatározhatjuk az aktuális kép jellemz˝oinek eloszlását a kulcspontokon. Ezt az eloszlást (hisztogramot) nevezzük az adott képhez tartozó kulcspont-zsáknak. A második lehet˝oség a GMM modellek használata. Az eljárás itt is az el˝oz˝ohöz hasonlóan zajlik, itt azonban egy alacsonyszintu ˝ jellemz˝ot nem egyetlen kulcsponthoz rendelünk, hanem a hisztogram összes eleméhez, az adott kulcspont által reprezentált Gauss eloszláshoz tartozó el˝ofordulási valószínuséggel. ˝ Az el˝ofordulási valószínuség ˝ azt határozza meg, milyen valószínuséggel ˝ generálta a jellemz˝ot az adott kulcspontot reprezentáló Gauss eloszlás (P (x | Gi ) = wi Pi (x)). Ez a módszer jobban kiegyensúlyozza és folytonosabbá teszi a hisztogramokat, amelyek így jobb bemen˝o információt szolgáltatnak az osztályozó algoritmus számára. Az algoritmus tanítási fázisában szükség van az összes tanítóminta kulcspont-zsákjának meghatározására az univerzális kulcspontkészlet modell alapján. Ezenkívül minden egyes mintát fel kell címkézni, hogy az adott szemantikus kategória tagja-e (+1 - benne van, -1 - nincs benne). A tényleges osztályozást a kulcspont-zsákokon tanított SVM gépek végzik. Minden kategóriához szükség van egy 1-vs-all osztályozóra. Ezeket úgy kapjuk, hogy minden az osztályhoz tartozó képet 30
a pozitív mintákhoz sorolunk, míg az összes többi osztályt és az osztályon kívüli elemeket a negatív mintákhoz. Mivel mindkét kulcspont modell használata esetén el˝ore meg kell határozni a kulcspontok számát, ezért érdemes mindkét esetben a GMM módszernél bemutatott „progresszív” módon elvégezni a tanítást, azaz kiindulva egy alacsonyabb értékb˝ol, folyamatosan tanítva az osztályozókat, keresni azt az optimális kulcspontszámot, amellyel a maximális felismerési ráta elérhet˝o a tesztképek adatbázisán.
31
4.5.4.
SVM
A szupportvektor-gépek (support vector machines, SVM) [?] segítségével lehet˝oség van címkézett minták alapján tanuló általános felügyelt tanulásra. Ezek segítségével történik a képek tényleges osztályozása a megadott kategóriacímkék alapján. Az SVM-ek a generalizált lineáris osztályozók családjába tartoznak, speciális tulajdonságuk, hogy szimultán minimalizálják az empirikus osztályozási hibát, miközben igyekeznek maximalizálni az általánosítóképességet (maximum margin property). Legyen {(xi , ci ), i ∈ N} a tanítóminták halmaza, ahol xi ∈ Rd a d dimenziós tanítóminták (a mi esetünkben a kulcspont-zsák hisztogramok), ci ∈ {−1, +1} pedig az egyes mintákhoz tartozó kategóriák címkéi. A tanítómintákat normáljuk a [0, 1] intervallumban. A (lineáris) SVM lényege, hogy az adott címkézett mintapontok alapján egy olyan optimális elválasztó hipersíkot találjon, amely egyúttal teljesíti a maximum margin feltételt is, azaz keressük azokat a b, illetve w paramétereket, amelyre: wxi − b = 1 wxj − b = −1 ahol i a pozitív minta-szupport-vektorok indexeit, j pedig az ellenpéldák szupport-vektorainak indexeit jelöli. A felmerül˝o kvadratikus programozási feladat primál alakja a következ˝o: 1 min kwk2 2 a ci (wxi − b) ≥ 1, 1 ≤ i ≤ n feltételek mellett (ahol ci -k az un. slack változók). Az SVM gépek duális alakjának felírása lehet˝oséget ad nemlineáris osztályozók tanítására is, a „kernel-trükk” segítségével, mi azonban hasonlóan [6]-hez a lineáris kernelnél, azaz a lineáris SVM módszernél maradunk, azaz két tanítóminta távolságát az euklidészi távolságukkal mérjük.
32
A tesztek futtatása során sor került kett˝onél több osztályból álló osztályozási feladatok megoldására is az SVM osztályozók segítségével. Ezt a gyakorlatban az SVM tanítási folyamatában a „1-vs-1” tanítási séma alkalmazásával oldjuk meg, azaz N osztály esetén összesen N ·(N2 −1) osztályozó tanítására kerül sor, minden kategóriapárhoz külön. Az osztályozáskor a tenisz-mérközések lebonyolításához hasonló módon az osztályozók pármérk˝ozésben, kieséses alapon döntik el minden szinten, hogy az adott két osztály közül a minta melyikbe illik jobban, majd az egyes szintek gy˝oztes osztályozói alkotják az eggyel magasabb szint résztvev˝oinek halmazát (továbbjutók). Az SVM által végül kiválasztott osztály így a legmagasabb szinten nyertes osztályozó által reprezentált osztály lesz.
4.6.
A BOK algoritmus tesztje
A „bag-of-keypoints” kategorizáló algoritmust els˝oként egy objektumfelismerési feladaton vizsgáltam, egy valós fényképeket tartalmazó adatbázis [33] segítségével. A kategorizálandó képeket két osztályba osztottam, aszerint, hogy tartalmaznak-e látható kerékpárt a képek, vagy sem. A tanító adatbázisomban 50 pozitív, azaz kerékpárt tartalmazó, illetve 100 db negatív (motorkerékpárt vagy autót tartalmazó, illetve városi, vagy természeti egyéb kategóriás) képet helyeztem el. A 4.2 ábrán látható egy pozitív mintakép, a 4.3 ábrán pedig egy negatív. A BOK modellt az el˝oz˝oekben leírt módon és paraméterekkel tanítottam a GMM fázisig bezárólag a teljes 150 képet tartalmazó adatbázison, majd háromféle tesztelési módot választottam. Ezek eredményeit ismertetik az 1-3. tesztek eredményei. A negyedik tesztben az algoritmust „éles” helyzetben, a szemdetektor programban várható környezet szerint teszteltem. Ehhez egy általam a NIPG csoport önkéntes tagjain készített speciális házi adatbázist használtam fel. A kísérlet részletes leírását a kés˝obbiekben, a negyedik teszt részletes leírásánál ismertetem.
33
4.6.1.
Els˝ o teszt
Az els˝o tesztben a teljes 150 képet tartalmazó tanító adatbázis által generált hisztogram mintán tanítottam az SVM osztályozót, majd 100 db, a tanító adatbázisban nem szerepl˝o képen teszteltem. A 100 darab képet a BOK algoritmus így pozitív, vagy negatív címkével látta el. A mér˝oszám a helyes címkézések aránya volt. Az algoritmus a „nem látott” képeken ezzel a módszerrel 86%-os teljesítményt ért el.
4.6.2.
Második teszt
A második tesztben az un. cross-validation tesztelési eljárás speciális változatát a „leave-one-out” módszert alkalmaztam, amelynek a lényege az, hogy a tesztadatbázis N eleme közül minden tanítási ciklusban els˝o lépésként kiválasztom a tesztelemet, majd a fennmaradó N-1 elemen tanítom be az algoritmust. Ez összesen N tanítási ciklust jelent, és minden ciklusban a tanítás folyamán nem látott tesztképen vizsgáljuk a felismerést. A végs˝o mér˝oszámot ezen bináris felismerési értékek (helyes -1 / nem helyes - 0) átlaga adja meg. Ez az érték a legrosszabb esetben K osztály esetén a véletlen választás módszerének várható értéke szerint 1/K értéket vesz fel, azaz a jelenlegi tesztben 0.5-et. Az osztályozó sikeres mukö˝ dése esetén ez az érték 1 közeli lesz. A második tesztben az eredeti 150 képes adatbázisból választottam ki rendre egy képet, amely a tesztminta lett, és az SVM osztályozót, csak a maradék 149 kép hisztogramján tanítottam. Az így kapott 150 tanítási és tesztelési ciklus helyes címkézéseinek átlaga adta a tesztelési mér˝oszámot. A „leave-one-out” teszt eredménye szintén 86%-os lett, ami arra utal hogy az algoritmus egy véletlenszeruen ˝ választott tesztadatbázison jó eséllyel hasonló eredményt érhet el, azaz stabil.
4.6.3.
Harmadik teszt
A harmadik tesztemben az SVM osztályozó paramétereit próbáltam finomhangolni oly módon, hogy azok maximális felismerési arányt biztosítsanak a „leave-one-out” eljárás során (második tesztben bemutatott módszer). Az SVM osztályozó lineáris verziójának egy 34
hangolható paramétere van (C), amely a modell komplexitása és a tréningadatbázison elvégzett pontos osztályozás közötti egyensúlyt képes beállítani. A harmadik tesztben a C paraméter szerint maximalizáltam a felismerési arányt C a [−100, 100] egy diszkrét intervallumfelosztásán. Az optimális C=0.25 lett a kerékpár adatbázisra. Az így elért legjobb felismerési arány 90%-os lett.
4.2. ábra.
4.3. ábra.
4.6.4.
Negyedik teszt
A negyedik tesztben a meglév˝o szemdetektor program szemkörnyék detektora által detektált régiók diszkriminálhatóságát vizsgáltam a szem iránya szerint. Ehhez a meglév˝o szemdetektor programot úgy módosítottam, hogy lehet˝oség legyen felvételeket készíteni a 35
szem pillanatnyi helyzetér˝ol a webkamera segítségével, miközben az alanyok egy el˝ore elkészített diasorozatot látnak és vizsgálnak. Az adatbázis felvételéhez egy speciális prezentációt készítettem, amelyben a képerny˝ot 5 részre (bal szél közepe, közép, jobb szél közepe, fels˝o szél közepe, alsó szél közepe) osztottam, ezekre a helyekre került fixálható objektum. A 4.4 ábrán látható az alanyok által látott diasorozat sémája. A képen látható 5 csillag közül egyszerre csak egy volt látható, véletlen sorrendben. Az alanyok fixáltak az adott pozícióra, majd felvétel készült róluk a megfelel˝o címkével. Minden alanyról összesen 15 felvétel készült, amely a teljes 5-ös felosztás 3-szori megismétléséb˝ol tev˝odött össze.
4.4. ábra. A tesztalanyoknak a monitortól és a webkamerától nagyjából 60cm-re ülve kellett szemükkel fixálni az éppen látható objektumot, eközben felvételek készültek a webkamerán keresztül a szem irányáról. A felvételezéshez egy Wide Screen 15.4”-os Fujistu-Siemens hordozható számítógépet használtam, valamint egy Logitech Quickcam for Notebooks Pro típusú webkamerát. Az így nyert adatbázist a szemkörnyék detektorok várható pozíciója alapján manuálisan szegmentáltam oly módon, hogy a képek csak a szemet és a szem környékét tartalmazó képterületet tartalmazzák, hasonlóan a már meglév˝o szemkörnyékdetektor által optimális esetben adott régióhoz. A szegmentálásba „zaj” is került a kézi módszer során, ez azonban a BOK algoritmus szempontjából nem releváns, mert az a pozíciókat nem, csak a lokális tartományon belüli képi statisztikát veszi figyelembe. A 4.1 táblázatbeli képek 2 alany 2 különböz˝o tekintetpozícióban felvett képét mutatják. 36
4.1. táblázat. A kapott képeken minden alanyra külön betanítottam a megfelel˝o BOK kulcspontokat. Ezután minden egyes képre elkészítettem a hozzátartozó BOK hisztogramokat. Minden alanyhoz a hozzátartozó kulcspontokon készültek el a BOK hisztogramok. A kísérletben nem konstans kulcspontszámot használtam, hanem minden esetben kézzel optimalizáltam a felismerési arány szempontjából legmegfelel˝obbnek tun˝ ˝ o kulcspontszámot, figyelembe véve azt a tényt is, hogy az adatbázisban található képeken átlagosan hány darab jellemz˝ot talált a SIFT algoritmus (ami képenként körülbelül 15-70 darab jellemz˝ot jelentett ezeken a képeken). A felismerési teszteket a kerékpár adatbázison is használt „leaveone-out” módszer segítségével végeztem, azonban attól eltér˝oen itt a tanítómintát nem 2 osztályba, hanem a tekintet irányoknak megfelel˝oen 5 osztályba soroltam, és az SVM algoritmust ezen a többosztályos mintán tanítottam. Az SVM osztályozás ilyenkor az SVM fejezetben ismertetett „1-vs-1” séma szerint muködik. ˝ Az így készített osztályozó teljesítménye ekkor a legrosszabb esetben a véletlen választás várható értéke, azaz 20% (0.2). A tanítás során az egyes kulcspontszámokra külön optimalizálásra került az SVM C paramétere is. A tesztet összesen 4 alany adatain végeztem el. A különböz˝o paraméterek mellett elért legjobb osztályozási arányokat a 4.2 táblázatban foglaltam össze. Az els˝o oszlopban az aktuális BOK kulcspontok számát (KP#) találhatjuk. Az els˝o sorban az egyes alanyok szerinti képsorozatok azonosítói (S1-S4), illetve a hozzájuk tartozó SVM C paraméterek (C) és legjobb felismerési arányok (RR) láthatóak. Az adott sorozatban elért legjobb felismerési arányok (RR) vastag betuvel ˝ szerepelnek. Azokon a helyeken, ahol a C paramé37
tert˝ol (C vizsgált értéktartományán belül, ami az [1, 200] intervallum volt) függetlenül azonos volt a felismerési arány, ott a C érték helyett egy ~ jel szerepel. KP# S1,C S1,RR S2,C S2,RR S3,C S3,RR S4,C S4,RR 3 30 0.266 ~ 0 ~ 0 40 0.2 5 40 0.4 ~ 0 13 0.333 80 0.26 10 60 0.3 150 0.2 13 0.466 70 0.43 12 100 0.333 150 0.16 13 0.466 80 0.36 15 20 0.466 100 0.13 13 0.566 60 0.23 17 22 0.466 60 0.36 13 0.466 80 0.26 20 13 0.333 50 0.16 20 0.433 80 0.3 4.2. táblázat.
Amint az a 4.2 táblázat eredményein is látszik, a BOK algoritmus ilyen kevés mintából, bár a véletlen kiválasztás statisztikáit sok esetben meghaladja, nem képes igazán jó és robusztus diszkriminációra a különböz˝o szempozíciókról készült felvételek között. Ennek egyik oka az lehet, hogy a képek viszonylag kis felbontásúak, és emiatt eleve viszonylag kevés SIFT jellemz˝o áll képenként rendelkezésre, másrészre az egyes kategóriákból is nagyon kevés minta áll rendelkezésre (kategóriánként 3), és ezért a jellemz˝ok statisztikai eloszlása sem modellezhet˝o megfelel˝oen. Nagyobb adatbázis esetén elképzelhet˝o, hogy az algoritmus valamivel stabilabb és jobb eredményeket adna, azonban a könnyu ˝ kalibrálhatóság igénye feltételezi, hogy a rendszer kalibrációs fázisában az elkészíthet˝o címkézett adatbázis mérete limitált. A fenti okokon kívül még feltételezhet˝o volt az is, hogy az algoritmus topológiamentes képleírása is felel˝os lehet az eredmények gyengeségéjért, hiszen elképzelhet˝o olyan speciális eset, amelyben maguk a lokális invariáns jellemz˝ok és azok eloszlásai nem változnak meg, csak esetlegesen az egymáshoz viszonyított relatív helyzetük. Ez a feltevés feltételezi, hogy lokális jellemz˝ok rendelkezésre állnak magán a szemen, a szemoldökön, illetve a tekintet mozgása közben változó szemkörnyéki jellemz˝okön, amelyek nem szunnek ˝ 38
meg a tekintet mozgása közben, hanem csak elmozdulnak egy stabilabb referenciajellemz˝ohöz képest. Ennek teszteléséhez szükséges a meglév˝o topológiamentes BOK/SIFT leírókat kiegészíteni oly módon, hogy az amennyire lehet skála- és elforgatás invariáns módon reprezentálni tudja az egyes kulcspontok relatív távolságait. Erre az invariáns topologikus léírásra egy lehet˝oséget adhat például az egyes különböz˝o kulcspont-klaszterbe tartozó SIFT jellemz˝ok távolságainak átlagolása és ezen átlag távolságok mátrixának egy alacsonydimenziós PCA reprezentációja. Az alacsonydimenziós PCA projekció azért tekinthet˝o értelmes ábrázolásnak, mivel feltételezhet˝o hogy azon átlag kulcspont-távolságok varianciája lesz maximális, amelyek egyúttal a legtöbb diszkriminatív információt tartalmazzák a tekintet mozgásáról az adatbázis képein.
4.6.5.
Diszkusszió
A „bag-of-keypoints” algoritmus egy általános, és robusztus képfeldolgozási eszköz, amely azonban hosszadalmas tanítási ciklussal rendelkezik, és érzékeny a tanításkor választott paraméterezésre. Ezenfelül megbízható muködéséhez ˝ viszonylag nagy tanítóadatbázisra van szükség. Jó minták és paraméterválasztás esetén viszont kell˝oen robusztus általános célú kategorizálási feladatok megoldásában és els˝osorban egy-egy kép globális jellegének, típusának meghatározásában. A SIFT jellemz˝ok detektálása a skálatér számítás id˝oigénye miatt a jelenlegi implementációban és hardveren nem alkalmas valósideju ˝ detektálásra a vizsgált képméreteken, azonban lehet˝oség van valósideju ˝ implementációra a grafikus kártyák GPUjának feldolgozószalagjai felhasználásával [8]. Ez a lehet˝oség, tekintetbe véve a kés˝obbiekben bemutatott, a SIFT tekintet-predikciós alkalmazási lehet˝oségeit is, fontos szerephez juttatja a GPU-SIFT jellemz˝oket mind a szemdetektor program bemeneti adatokat feldolgozó, mind pedig a kimeneti információ alapú predikciók el˝ofeldolgozási lépése során.
39
5. fejezet Biológiailag motivált saliency-detektorok 5.1.
Bevezetés
Az ebben a fejezetben bemutatott kísérletet [21, 22]-ben találhatjuk meg részletesen, itt csak körvonalazom a motivációt, a kísérleti módszereket, illetve a fontosabb eredményeket, amelyekre a kés˝obbi predikciós kísérleteimben én is építettem.
5.2.
Motiváció
A bevezet˝o fejezetekben már ismertettem, hogy a szakkádtervezés legtöbb jelenleg ismert modellje különválasztja a top-down és bottom-up vezérlés fogalmát, és ezen belül a legtöbb modell a bottomup keresésére helyezi a hangsúlyt. Ebben a módszerben sincs ez másként, viszont ellentétben a többi modellel, itt nem el˝ore definiált, biológiailag a látás szempontjából fontosnak gondolt lineáris szur˝ ˝ ok által adott értékek nemlineáris kombinálásával áll el˝o a tényleges saliency-detektor, hanem magának az alapképeknek a pixeltartományán dolgozó tanulóalgoritmusok állítják azt el˝o, minden el˝ozetes (biológiai) modellfeltevés nélkül. Ez azért fontos eredmény, mert képes pusztán a gépi tanulás eszközeivel el˝oállítani azokat a szur˝ ˝ oket, amelyek kés˝obb felhasználhatóak a saliencydetektorok elkészítésénél. Ett˝ol egyrészt specializálhatóbb, az adott 40
problématípushoz jobban megfelel˝o képi jellemz˝o detektorok kialakulását adja, másrészt információt adhat arról is, hogy milyen típusú bottom-up feldolgozás befolyásolja az emberi tekintet kontrollt. Az eredmények részben látható lesz, hogy a gépi tanulás elvei által készített szur˝ ˝ ok nagyban hasonlítanak a neurobiológiai kísérletekben már megismert típusokhoz, azon belül is speciálisan az un. center-surround jellegu ˝ receptív mez˝okhöz, amelyeket legtöbbször a DoG szur˝ ˝ okkel modelleznek. Ez az itt bemutatott predikciós kísérletek szempontjából azért rendkívül fontos, mert a SIFT detektor, mint saliency-detektor felhasználhatóságát ezek a kísérletek támasztották alá.
5.3. 5.3.1.
Kísérlet Adatbázis
A felhasznált adatbázisban 200 természetben készített kép szerepel, amelyek felbontása 4064x2704 pixel volt. Ezekb˝ol véletlenszeruen ˝ kiválasztott 1024x768 pixeles ablakok, színmélységük pedig 8 bites szürkeskálás volt. A képeket 14 naív alany figyelte meg egy 19”-olos CRT monitoron, 60cm-es távolságból, amely 37◦ × 27◦ -os vizuális látószögnek felel meg. A képekhez tartozó tekintetkövetési adatbázisban összesen 18065 fixációs pozíció található. Az alanyoknak nem volt semmilyen konkrét feladatuk a képekkel kapcsolatban, csak szabadon nézegetniük kellett o˝ ket, és minden képet nagyjából 3 másodpercig láthattak. Minden kép megjelenítése el˝ott egy homogén hátteru ˝ képen elhelyezked˝o „el˝ofixációs” objektumot láttak, amelyre fixálniuk kellett. Ezek az objektumok minden kép el˝ott véletlenszeru ˝ pozícióban jelentek meg, és véletlenszeru ˝ ideig. Maguk a képek is véletlen sorrendben kerültek megjelenítésre, és megjelenítés ideje sem volt teljesen egyforma. Minden tizedik kép után egy 4x3-as felosztásban kalibrációs objektumokat tartalmazó képet láthattak, amelyekre fixálniuk kellett, és az így nyert adatokkal lehetett a tekintetkövet˝o rendszer eredményeit pontosítani.
41
5.3.2.
Saliency detektálás osztályozási feladata
Mivel a saliency detektor egy olyan I/O rendszer, amelynek bemenete a kép egy adott koordinátáján található lokális képi információ, kimenete pedig egy skalár, amely az adott pont „relevanciáját” méri, ezért a meglév˝o adatok birtokában az optimális saliency detektor keresése felfogható egy osztályozási feladatként, amely lokális képrészletek (patch-ek), és bináris címkék (érdekes / nem érdekes) segítségével tanulható egy megfelel˝o tanulási algoritmus által. A tanuláshoz a képrészlet adatbázist a konzisztens fixációs pontok segítségével lehet elkészíteni, a részletes módját egy kés˝obbi pontban írom le. Ha a tanítóminta rendelkezésre áll, egy egyszeru ˝ osztályozóval, mint például a korábban ismertetett SVM gépek, a detektor generálható.
5.3.3.
Konzisztens fixációs pontok
Ismert, hogy a szemmozgásokat nem csak a bottom-up, hanem a top-down tényez˝ok is befolyásolják. A feladatot tovább nehezíti, hogy az egyes alanyoknak eltérhet a bels˝o értelmezése a „nézegetés” feladatáról, és id˝oben is változhat. Ezt ellensúlyozandó a kísérletben csak azok a fixációs pontok lettek figyelembe véve, amelyek konzisztensek, azaz több alanynál is egymástól függetlenül megjelentek, méghozzá kell˝o gyakorisággal. Emögött az a feltevés húzódik meg, hogy az egyes alanyok top-down kontrollja túlságosan komplex ahhoz, semhogy statisztikailag szignifikánsan jelentkeznének top-down motivált és közös fixációs pontok. Emiatt a konzisztens pontokról feltehet˝o, hogy id˝oben állandóak, és kizárólag a képi információk alapján számoltak, azaz teljesen bottom-up kontroll alatt állnak. A konzisztens fixációs pontok kiszámításához az alábbi formulák használhatóak. Feltételezve, hogy σm a mérési hiba szórása, a várható értéke pedig 0, számolható, hogy az egyes (x, y) koordinátákhoz tartozó pont milyen valószínuséggel ˝ fixációs pont: p(x, y|F ) =
1 X 2 exp(− k(x, y)i − (x, y)k /2σm ) |F | F
42
ahol F = {(x, y)i } az összes mért fixációs pont (az összes alany szerint) az adott képre. A p(x, y|F ) összes olyan lokális maximumhelye, amely értékben egy adott küszöbérték (a kísérletben δ = 1.8/|F |) felett található, konzisztens fixációs pont helynek címkézend˝o. Ez a threshold érték manuálisan választott. Szemléletesen: például akkor válik (x, y) egy konzisztens fixációs ponttá, ha legalább két alany fixálta 0.25◦ os sugáron belül. Az itt leírt konzisztenciaszámítás kés˝obb az általam végzett kísérletekben is szerepet kap a saliency térképek számításakor.
5.3.4.
Tanítóminta összeállítása
A tanítómintában kétféle mintára van szükség. Az els˝o, az un. pozitív mintákat tartalmazó halmazba kerülnek azok a minták, amelyek olyan képekr˝ol és olyan pozíciókról lettek kivágva, amelyek konzisztens fixációs pontot tartalmaztak. A negatív halmazban olyan, véletlenszeruen ˝ kiválasztott pozíciókról vett minták kerülnek, amelyek nem tartalmaztak konzisztens fixációs pontot. A kivágott képrészletek végs˝o mérete mindig 13x13-as, azaz 169 dimenziós a bemeneti vektor. A képrészletek azonban 10 skáláról kerültek ki, azaz az eredeti kép 10 féle skáláján mintavételezték o˝ ket. Ennek eredményeképp a 10 féle patch a 0.6-t˝ol 25 fokos látószögnek megfelel˝o méretu ˝ mez˝ok bemenetének felel meg. Az optimális látószöget az osztályozó teljesítménye alapján választja ki az algoritmus.
5.3.5.
Tanítás
A tanításhoz a szerz˝ok egy RBF kernelu ˝ SVM gépet használtak, így a tényleges detektor függvénye az alábbi alakú lett: f (x) =
m X
αi yi exp(−γ kxi − xk2 )
i=1
ahol (xi , yi ) ∈ R169 × {−1; 1} a címkézett tanítóminták halmaza, m pedig a minták száma, az αi skalárok pedig az SVM lineáris súly 43
paraméterei. Az így nyert osztályozó tehát tulajdonképpen egy valósértéku ˝ saliency mértéket ad minden 13x13-as képrészlethez.
5.3.6.
Eredmények
A fenti kísérletnek a bottom-up kontroll el˝orejelezhet˝oségének szempontjából két fontos eredménye is volt. Az els˝o az, hogy az így nyert detektor nagyjából hasonló saliency-felismerési eredményeket tud produkálni, mint az eddigi, neurobiológiai modellekre alapuló detektorrendszerek. A másik fontos eredmény, hogy az így kapott saliency mértéknek megállapítható a minimális, illetve maximális választ kiváltó inputja, azaz hogy milyen típusú receptív mez˝ok szükségesek a bottom-up kontroll hatékony megvalósításához. A kapott eredmények egyértelmuen ˝ azt mutatják, hogy a BU modellek gépi tanulási modellje a már neurobiológiából is ismert center-surround típusú receptív mez˝oket részesíti el˝onyben. A center-surround típusú sejtek a pontszeru ˝ kontrasztkülönbségekre érzékenyek, azaz akkor maximális a stimulus, ha kontrasztkülönbség lép fel a receptív mez˝o középs˝o területei, illetve az azt körül vev˝o területek között. Fontos észrevenni, hogy a SIFT modellekben használt DoG approximáció is pontosan a center-surround típusú pontokat részesíti el˝onyben a detektor által detektált képi jellemz˝ok kiválasztása során, azaz feltehet˝o, hogy a skálatéren közelített Laplace függvény széls˝oértékei szoros kapcsolatban vannak az ember által is BU szempontból fontosnak talált pozíciókkal. A következ˝o fejezetben bemutatott SIFT-saliency modell pontosan erre a megfigyelésre épít.
44
6. fejezet SIFT-Saliency modell 6.1.
Bevezetés
Ebben a fejezetben egy egyszeru ˝ valószínuségi ˝ alapú fixációspontpredikciós modellt mutatok be. Célom az itt bemutatott kísérletekkel az volt, hogy a rendelkezésünkre álló tekintetkövetési adatbázis adatait feldolgozva predikciós módszereket fejlesszek, amelyek segítségével az egyes alanyok szemmozgása, annak dinamikája tanulható, egymástól megkülönböztethet˝o, illetve el˝orejelezhet˝o. A bevezet˝o fejezetekben már szó esett arról, hogy az emberi szemmozgások egy aktív leképezési folyamat eredményei, amellyet az agy oly módon vezérel, hogy a szemb˝ol érkez˝o korlátozott mennyiségu ˝ információ segítségével minél hamarabb fel tudja építeni a bels˝o mentális képet a környezetér˝ol. Eddigi ismereteink alapján ez egy két szinten vezérelt folyamat, szerepet kapnak benne a bottomup (a képi információ által vezérelt, tudattalan / tudatalatti) befolyások, illetve az alany pillatnyi bels˝o állapota (emóciók, fáradtság, feladat, stb.), röviden összefoglalva a top-down vezérlés. A továbbiakban e két folyamatot a modellben elkülönítjük, és feltesszük, hogy azok egymástól (statisztikailag) függetlenek. Ezenkívül feltesszük, hogy mindkét kontroll id˝oben állandó. Természetesen ezek a feltevések nem lehetnek igazak a folyamat visszacsatolt és aktív természete miatt a teljes megfigyelési folyamatra, azonban feltehet˝o, hogy az olyan típusú feladatoknál, ahol az alanyoknak nincs konkrét feladata az adott képpel kapcsolatban, a
45
kezdeti fázisban egy ehhez közelálló TD/BU megközelítés helytálló lehet.
6.2.
Adatbázis
Az ebben a fejezetben felhasznált tekintetkövetési adatbázis 17 naív alany tekintetkövetési adatait tartalmazza, akik festményeket vizsgáltak. Az alanyoknak nem volt külön feladata („gyönyörködtek a képben”). A képeket egy 19”-os CRT monitoron nézték, 100Hz-es mintavételezési id˝ovel. A szem-monitor távolság körülbelül 80 cm volt, amely egy 25.7◦ × 19.3◦ -os látószöget eredményezett (horizontálisan, illetve vertikálisan). Minden alany véletlen sorrendben végignézte mind a 40 képet egy-egy sorozatban, egy képet átlagosan 1 percig láthattak. Az adatbázisban így egy képhez egy alanytól átlagosan 200 fixációs pont tartozik. A képek 24 bites színmélységuek ˝ és 1152x864 pixeles felbontásúak. A 6.1 ábrán az adatbázis egyik képe látható, 3 különböz˝o alany fixációs útvonalának berajzolásával. Jól látható, hogy a kép közepén található emberi arcokon gyakoribbak a fixációs pontok. Ez a jelenség már korábbi kutatásokból is ismeretes, hogy egy-egy képtér vizsgálatakor els˝odlegesen az emberi arcokra vagyunk érzékenyek.
6.1. ábra.
46
6.3.
Fixációs térképek
A tekintetkövetési adatbázisból nyerhet˝o fixációs pontok sorozatát a következ˝okben egy 2 dimenziós feltételes eloszlásból vett mintának fogjuk tekinteni, és célunk a továbbiakban ennek az eloszlásnak az approximálása, illetve képfeldolgozási módszerekkel a képi predikciója lesz. Ehhez el˝obb ismertetetem az alapvet˝o valószínu˝ ségi modellt, amellyel dolgozom. A fixációs pontokat tehát els˝oként olyan független, azonos eloszlású mintáknak fogom tekinteni, amelyek az alábbi eloszlásból vett mintáknak felelnek meg: P (F (x, y)|I, H) ahol F (x, y) egy 2 dimenziós diszkrét valószínuségi ˝ változó, amely k · s értéket vesz fel, ha az adott (x, y) ponthoz tartozik az I képen a H alanytól származó fixációs pont, méghozzá k darab és összesen s ideig tartott a fixáció milliszekundumban, azaz az adott koordináták olyan képi jellemz˝ot tartalmaznak, amely érdekes (tehát fixáció történt rajta) az adott I képen az adott H felhasználó számára. A modellben fel fogjuk tenni, hogy a fenti eloszlás faktorizálható a következ˝o módon: P (F (x, y)|I, H) = P (F (x, y)|I) · P (F (x, y)|H) A teljes valószínuségi ˝ tétel szerint, lévén modellünkben H mint feltétel diszjunkt, és elegend˝o számú ember esetén feltételezzük, hogy „teljes” eseményrendszert ír le, ezért igaznak gondoljuk a következ˝o approximációkat: P (F (x, y)|I) ∝
1 X P (F (x, y)|I, Hi ) |H| i∈H
Ahol H az alanyokra vonatkozó indexhalmaz, Hi , (i ∈ H) pedig az a feltétel, hogy az i. alany fixációs pontjait vizsgáljuk. Ez szemléletesen azt jelenti, hogy úgy gondoljuk azok a jellemz˝o fixációs pozíciók, amelyek sok alanynál azonosan és nagy valószínuséggel ˝ fordultak el˝o, els˝osorban képfügg˝oek, azaz bottom-up vezéreltek. 47
Ez a feltevés nagyban hasonlít a konzisztens fixációs pontok feltételeire, amelyeket a biológiailag motivált detektoroknál is ismertettem. A fentihez hasonló módon felírhatjuk a P (F (x, y)|H) ∝
1 X P (F (x, y)|Ii , H) |I| i∈I
összefüggést is, ahol most I a képekre vonatkozó indexhalmaz lesz, Ii pedig az a feltétel, hogy az i. képen vett fixációs pontokat vizsgáljuk. Ez a megközelítés esetleg lehet˝oséget adhat olyan felhasználóspecifikus információk megállapítására, amelyek lehet˝oséget adnak az adott felhasználó azonosítására, illetve a top-down viselkedés bizonyos fokú el˝orejelzésére. Mivel a Bayes-szabály alapján P (I|F (x, y)) =
P (F (x, y)|I) · P (I) P (F (x, y))
ahol P (I) és P (F (x, y))-t egyenletes eloszlásokkal közelíhetjük, így eredményül azt kapjuk, hogy P (I|F (x, y)) = α · P (F (x, y)|I), α ∈ R+ ami azt jelenti, hogy a jobb oldali és a bal oldali eloszlások egymással korrelálnak, azaz ha egy adott F (x, y) ismeretében becsülni akarjuk hogy az melyik I képhez tartozik, elegend˝o egy olyan eloszlást találnunk, amelyr˝ol ismert, hogy I-hez tartozik és közel van P (F (x, y)|I)-hez. Feltételezve, hogy a SIFT detektorok jól közelítik a bottom-up saliency által kiválasztott képi jellemz˝oket, illetve hogy a fent definiált eloszlás is els˝osorban a bottom-up hatásokat mutatja ki, tehát egy közelítését adják P (F (x, y)|I)-nek egy adott kép esetén, ezért a SIFT detektorok által generált „fixációs” eloszlások közelíteni fogják az alanyok átlagából az adott képre számolt fixációs térképet (ami tulajdonképpen szintén P (F (x, y)|I) közelítése). Mivel a gyakorlatban már a P (F (x, y)|I, Hi ) eloszlásokból is csak minták állnak rendelkezésre, és ezek is mérési hibával terheltek, ezért a fixációs térképek számításakor az 5. fejezetben ismertetett 48
számításhoz hasonló módon az alábbi képletet használjuk az egyes (x, y) pontok fixációs pontként való el˝ofordulási valószínuségének ˝ megállapítására: p(x, y|F ) =
1 X 2 si · exp(− k(x, y)i − (x, y)k /2σm ) |F | F
Ez a gyakorlatban azt jelenti, hogy a fixációs térképben minden fixációs pontot egy σ = 10 paraméteru ˝ Gauss-blobbal közelítünk, amelynek a középpontja a mindenkori (x, y) fixációs pont, súlya pedig a fixációs pont s id˝otartama. Az id˝otényez˝ovel való súlyozás azért került a képletbe, mert úgy gondoltuk az egyes jellemz˝ok relevanciája nem csak a látogatási frekvenciától, hanem az ott eltöltött id˝ot˝ol is függ. Így tehát kétféle fixációs térképet definiálunk minden egyes Ire. Egyrészt a tekintetkövetési adatbázisból számolt alanyokra jellemz˝o humán-fixációs térképet, másrészt a legnagyobb magnitúdójú SIFT jellemz˝ok pozíciójának felhasználásával, mint fixációs pontokkal létrehozott SIFT-fixációs térképet. A 6.2 ábrán látható egy humán fixációs térkép, normalizált ábrázolásban. Egy pont fixációja annál valószínubb, ˝ mintél fehérebben ábrázoltuk. A 6.3 ábrán az el˝obbi fixációs térkép egy küszöbölt és binarizált verziója látható, visszavetítve az eredeti képre.
6.2. ábra.
49
6.3. ábra.
6.4.
Els˝ o kísérlet
Els˝o kísérletemben azt vizsgáltam, hogy a különböz˝o paraméterezések mellett a SIFT fixációs térképek és humán fixációs térképek összehasonlítása alapján milyen bizonyossággal tudom a tekintetkövetési útvonalak ismeretében azonosítani, hogy azok melyik képhez tartoztak. Ehhez els˝o lépésben minden egyes képhez el˝oállítottam a hozzájuk tartozó humán fixációs térképeket, illetve az egyes képekhez tartozó SIFT-fixációs térképeket. A tényleges „osztályozást” nem tanulási algoritmussal, hanem a két térkép közötti korreláció maximalizálással oldottam meg, azaz akkor tekintem az adott humán térképet az i. képhez tartozónak, ha az i. SIFT fixációs térkép korrelál a legjobban a humán fixációs térképpel. A korrelációs együtthatót az alábbi keresztkorrelációs (crosscorrelation) képlettel számoltam a két fixációs térkép között, amely a 2 dimenziós jelekre A, B ∈ Rm×n felírva a következ˝o alakú: P P (Amn − A)(Bmn − B) r(A, B) = q P P m n P P ( m n (Amn − A)2 )( m n (Bmn − B)2 ) ahol X=
1 XX · Xmn mn m n
a 2 dimenziós jel mintaátlaga. 50
A kísérletben 2 futó paramétert használtam, az egyik azt határozta meg, hogy a SIFT fixációs térképben a legnagyobb magnitúdójú jellemz˝ok közül maximálisan hányat vegyek figyelembe (S), a másik paraméter pedig azt határozta meg, hogy az emberi fixációs pontok közül mennyi szerepeljen a fixációs térképben (K). S értékeit az 50 és 3200, K értékeit pedig az 5 és 200 közötti intervallumon vizsgáltam. Itt K az alanyok számával szorzódott, azaz például ha K=1, akkor minden alany els˝o fixációs pontját vettem figyelembe, azaz összesen 17-et. Az osztályozás teljesítményének mérésére a felismerési arányt választottam a teljes adatbázison, azaz az i. képhez Ri = 1 tartozik, ha sikerült azonosítani a fixációs térképek korrelációja alapján, és Ri = 0, ha nem. A végs˝o mér˝oszámot az adott S,K paraméter mellett az 1 X R= Ri N i∈1..N összefüggés határozta meg, amely az átlagos felismerési arány (N=40, a képek száma). A legrosszabb várható eredmény a véletlen választás eredménye, azaz 1/40. A kísérlet eredményei a 6.4, 6.5 ábrákon láthatóak. A kísérlet eredményei tehát a következ˝ok voltak: 1. Minél több SIFT jellemz˝ot veszek figyelembe a SIFT-fixációs térképek számításakor, annál jobb lesz a felismerési arány. 2. A felismerési arány akkor a legmagasabb, ha a felhasználók els˝o 100-150 fixációs pontját veszem figyelembe, ezután csökkenni kezd, ami azt jelenti, hogy nagyjából ebben a tartományban használható jól a SIFT algoritmus, mint bottom-up modell. 3. Az elért maximális 74%-os arány a 40-címkés osztályozási feladatban jó eredménynek számít, azaz a legnagyobb magnitúdójú SIFT jellemz˝okb˝ol számolt fixációs térképek sok információt nyújtanak a kép beazonosításához. A fenti algoritmus tesztelése során megvizsgáltam azt, is hogy szükségese a legnagyobb magnitúdójú jellemz˝ok kiválasztása a jó felismerési 51
6.4. ábra. arányok eléréséhez. Ellenpróbaként a maximális helyett a minimális magnitúdójú SIFT jellemz˝ok segítségével generált fixációs térképekre is elvégeztem a kísérletet. A kapott eredmény azt mutatja, hogy szükséges a maximális magnitúdójú jellemz˝ok kiválasztása, enélkül az algoritmus rossz, véletlen választáshoz közeli eredményeket produkál.
6.5.
Fixációs pontok távolsághisztogramja
Az el˝oz˝o részben ismertetett fixációs térképek segítségével tehát a trajektóriák ismeretében jól beazonosítható, hogy azok a meglév˝o adatbázisban melyik kép vizsgálata közben készültek. A biometrikai kutatások eredményei alapján [26] várható, hogy a szemmozgások bizonyos paraméterei alapján az egyes alanyok esetleg megkülönböztethet˝oek. Ebben a pontban definiálok egy módszert, amely az egymás utáni fixációs pozíciók átlagos távolságának hisztogramjai alapján próbálja egy adott trajektóriáról meg52
6.5. ábra. határozni, hogy az melyik felhasználótól származik, majd bemutatom az ezen az adatbázison elérhet˝o eredményeket. A továbbiakban tehát az adott alany által az adott képen felvett tekintet-trajektóriákra, mint egy 2 dimenziós id˝osorra fogok tekinteni: GI,H (t) = (xI,H (t), yI,H (t)) Ahol I, H az adott kép és az adott alanyt azonosító indexek, t ∈ {1, . . . , TI,H } „id˝oindex”, amely meghatározza, hogy hányadik fixációs pontról van épp szó az adott kép trajektóriájában, xI,H ∈ {1, . . . , TI,H } → R és yI,H ∈ {1, . . . , TI,H } → R pedig megadja az adott fixációs pont vízszintes, illetve függ˝oleges tengelyen meghatározott koordinátáit. Az egyes t. id˝opillanathoz tartozó fixációs ponttávolság ebb˝ol adódóan a következ˝o képlettel számolható: DI,H (t) = k(xI,H (t + 1), yI,H (t + 1)) − (xI,H (t), yI,H (t))k2 ahol t ∈ {1, . . . , TI,H − 1}. 53
Az adatbázisban minden alanyhoz és minden képhez tartozik egy TI,H − 1 elemu ˝ „távolság-trajektória”, azaz egy adott i. alanyhoz P rendelkezésre áll összesen I (TI,Hi − 1) darab távolságminta. Legyen d egy valószínuségi ˝ változó, amely az i. alany által „választott” távolságokat modellezi, elhanyagolva az id˝obeliséget. Ahhoz hogy modellezhessük a P (d|Hi ) feltételes eloszlást a meglév˝o adatok alapján, diszkretizálni fogjuk a távolságokat egy hisztogram segítségével. A hisztogramot pontosan N részre (bin) osztjuk, és a hisztogramban az egyes bin-ek egy egy távolság-intervallumot fognak reprezentálni. Ezzel diszkretizálhatjuk d értékeit: Bi = [bi , bi+1 ) ahol i ∈ 1, . . . , N − 1, b1 = 0, bN = maxI,H,t DI,H (t) + , > 0 ∈ R. Legyen dˆI,H : N → N és dˆI,H (t) = i ⇔ DI,H (t) ∈ Bi A fenti módon értelmezhet˝o a fixációs pontok távolsághisztogramja egy adott alany esetén Hi ∈ RN , ahol P ˆ I,t χ(dI,Hi (t) = j) P Hi (j) = I TI,Hi ahol χ a logikai értékek halmazát képezi le a {0, 1} halmazra oly módon, hogy 1-et rendel az igaz állításokhoz, 0-át pedig a hamisakhoz. Az i. alanyhoz rendelt Hi adja a P (DI,Hi ) eloszlás egy diszkrét közelítését. A 6.6 ábrán az egyik alanyhoz tartozó fixációs pontok távolsághisztogramja látható. A függ˝oleges tengely mutatja az adott fixációs távolság el˝ofordulásának valószínuségét, ˝ a vízszintes tengelyen pedig az adott távolságintervallumok azonosítószáma látható. A képen látható adatok esetében a minimális távolság (b0 ) értéke 0 volt, a maximális távolságé (bN ) pedig 800. A képen látható hisztogram 180 bin-re volt felosztva ezen az intervallumon. A távolság-hisztogramok vizsgálatakor fontos észrevétel volt, hogy az egyes alanyok által definiált eloszlások alakja és lefutása nagyon hasonló, azaz felismerhet˝o egy alanytól független tendencia is a fixációs távolságok eloszlásában. 54
6.6. ábra.
6.6.
Második kísérlet
A tekintetkövetési adatbázison elvégzett második kísérletemben azt vizsgáltam, hogy az el˝oz˝o szekcióban definiált diszkretizált fixációspont távolság eloszlások hisztogramjai milyen paraméterek mellett milyen arányban teszik lehet˝ové az egyes alanyok megkülönböztetését, egy adott trajektória ismeretében, egy eddig nem látott képen. A kísérlet els˝o lépésében rendre kiválasztottam egy k ∈ {1, . . . , 40} indexet, amely a vizsgálandó kép indexe. Ezek után a fennmaradó 39 képen rendelkezésre álló trajektória adatok segítségével kiszámoltam mind a 17 alany fixációspont távolság hisztogramját. Ezek szolgáltak az egyes alanyok modelljéül. Miután az alanyok hisztogramjai rendelkezésre álltak, a k. kép adatait felhasználva kiszámoltam a tesztkép által generált távolsághisztogramokat a 17 alany szerint. Ezek szolgáltak a k. képen az egyes alanyok által bejárt trajektóriák jellemzésére. Egy alanyt a tesztképen rögzített trajektóriája alapján ahhoz a modell-alanyhoz kötöttem az osztályozás során, amely alanytól származó modell-hisztogramhoz a vizsgált alany teszt-hisztogramja 55
a legközelebb állt. A hisztogramok távolságát a Kullback-Leibler divergencia egy szimmetrizált változatának segítségével határoztam meg (Jensen-Shannon divergencia), amely a következ˝o képlettel számolható diszkrét valószínuségi ˝ változók eloszlásának összehasonlítása esetén: DJS (P kQ) = DJS (QkP ) =
1 X logP (i) X logQ(i) ·( P (i) · + Q(i) · ) 2 Q(i) P (i) i i
Mivel a fenti egyenletben P (i) és Q(i) értékei osztóként is szerepelnek, ezért a kiszámíthatóság érdekében a fixációs hisztogramokban minden olyan tényez˝ot, amely értéke 0-át vett fel, helyettesítem egy 0 közeli = 1e − 10 értékkel a divergencia értékének kiszámítása során. A k. kép tesztelése során akkor mondjuk, ha a k. képen az i. alany által definiált fixációspont távolság hisztogram KL-divergencia távolságban az i. alany által a 39 maradék képen definiált modellhisztogramhoz esik a legközelebb. Ebben az esetben az adott (k,i) párhoz tartozó R (felismerési arány) értéke 1, ellenkez˝o esetben pedig R értéke 0. A végs˝o felismerési arányt R átlagos értéke adja, azaz R=
1 X R(i, k) 40 · 17 i,k
Ennek értéke a legrosszabb, véletlen kiválasztás várható érté1 ≈ 0.0588. A kísérlet paramétere volt még S, kének megfelel˝oen 17 a fixációspont távolság hisztogram diszkretizációja során használt intervallum mérete. S értékei a kísérletben az {1, . . . , 400} intervallum elemei voltak. A 6.7 ábrán láthatóak az egyes S értékekhez (vízszintes tengely) tartozó R értékek, azaz átlagos felismerési arányok (függ˝oleges tengely). Eredményül az látható, hogy a trajektóriák ezen reprezentációjában a felhasználók legjobb jellemzésére alkalmas S értéke 191 volt, és az így elért átlagos felismerési arány 12.19%.
56
6.7. ábra.
6.7.
Diszkusszió
A fejezetben vizsgált fixációs pont rákövetkezési távolságok hisztogramjai bizonyos fokig jellemzik ugyan az adott felhasználót, de diszkriminatív erejük ebben a feladatban kicsi. Fontos azonban megfigyelni, hogy ezek az eloszlások stabil tendenciát követnek minden egyes alany esetén, és az eloszlások egymáshoz közeliek. Ez lehet˝oséget ad arra, hogy alanytól független valószínuségi ˝ becslést tudjunk adni arra nézve, hogy egy adott t. id˝opillanat után a t+1. id˝opillanathoz tartozó fixációs pont távolsága az aktuális ponttól mérve milyen eloszlású lehet. Az el˝oz˝o fejezetben ismertetett fixációs térképek által kijelölt érdekes (valószínuleg ˝ fixált) pontok eloszlása ezáltal tovább súlyozható az aktuális pont és az ismert távolság eloszlások segítségével és így egy kombinált valószínuségi ˝ becslés adható arra nézve, hogy a t. id˝opillanatban fixált pont után a képen mely pozíciók esélyesek, mint a t+1. id˝opillanatban fixált pontok.
57
6.8.
Harmadik kísérlet
Az adatbázison elvégzett harmadik kísérletben az el˝oz˝o két módszer egy hibrid változatának teljesítményét mérem a trajektóriák id˝osorainak predikciója szempontjából. Ehhez a kísérlethez ismertetek egy egylépéses predikciós modellt, amely az el˝oz˝o két kísérlet eredményeire épül. A következ˝okben felteszem, hogy a fixációs pontok sorozatának generátorfolyamata nem rendelkezik memóriával, azaz a t. id˝opont ismerete elegend˝o a t+1. id˝opillanatbeli fixációs pozíciók meghatározásához. Ez formálisan azt jelenti, hogy a fixpontok sorozatára, mint sztochasztikus változóra teljesül a Markov-tulajdonság, azaz a korábbi jelölések felhasználásával, a trajektóriákat 2 dimenziós valószínuségi ˝ változónak tekintve: P (GI,H (t + 1)|GI,H (1), . . . , GI,H (t)) = P (GI,H (t + 1)|GI,H (t)) A tényleges modell valójában két, egymástól független folyamat által lesz vezérelt. A bottom-up vezérlést a már ismertetett SIFTfixációs térképek segíségével valósítjuk meg oly módon, hogy azok a képi pozíciók lesznek valószínu ˝ fixációs pozíciók, amelyek a térképben magas súllyal szerepelnek, vagyis feltételezzük, hogy a mindenkori fixációs pontok a legnagyobb valószínuséggel ˝ ezeken a pontokon helyezkednek el. Ez a tag tulajdonképpen stacioner, id˝oben állandó tagként szerepel. A SIFT térképek elkészítésekor maximálisan az els˝o 6000 legnagyobb magnitúdójú SIFT jellemz˝ot használtam fel minden kép esetén. Így tehát a bottom-up tag egy adott (x,y) pontra a következ˝o képlettel írható le: Pbu ((x, y)) = PSif t (F |I) ahol PSif t a már korábban ismertetett SIFT-fixációs térképnek felel meg. A modell top-down komponensét az alanyhoz tartozó fixációsponttávolság hisztogram eloszlása és a t. id˝opontbeli fixációs pont helyzete határozza meg oly módon, hogy az adott t. fixációs ponttól mért távolságokra található pontok valószínusége ˝ megegyezzen a fixációspont-távolság hisztogram által ehhez a távolsághoz rendelt valószínuséggel, ˝ azaz: 58
Ptd ((xt+1 , yt+1 )|(xt , yt )) = Hi (Bin(k(xt+1 , xt+1 ) − (xt , yt )k)) Itt Bin a diszkretizációs függvényt jelöli, amely meghatározza, hogy az adott valós távolság melyik diszkrét hisztogram bin-be esik, az i pedig az alany indexe. Egy adott t. id˝opontban tehát a t+1. id˝opontbeli fixációs pontok eloszlására adott becslés a következ˝o alakot veszi fel: P ((xt+1 , yt+1 )|(xt , yt )) = Pbu ((xt+1 , yt+1 )) · Ptd ((xt+1 , yt+1 )|(xt , yt )) Az ezzel a képlettel definiált 2D valószínuségi ˝ eloszlást ezekután normáljuk maxx,y (P ((x, y)|(xt , yt ))) értékével, hogy a legvalószínubb ˝ ˆ esetekhez 1-et rendeljen (P -térkép). Az így kapott térkép t. id˝opillanatbeli „relevanciája” az I kép, illetve H alany esetén: RI,H (t) = Pˆ (GI,H (t + 1)) azaz az érték, hogy milyen valószínunek ˝ tartja a modell a t. id˝opillanat ismeretében a tényleges t+1. id˝opillanatban bekövetkez˝o fixációs pontot. Amennyiben a becsült eloszlás nem egyenletesen magas értékeket rendel minden lehetséges ponthoz, úgy ez a „relevancia” mérhet˝ové teszi a predikció teljesítményét. A kísérletben az így kapott relevanciapontokaz alanyonként és t id˝opillanatokra lebontva számítom ki, a 40 képen átlagolva, így a t. id˝opillanatokhoz tartozó relevancia-érték: P RI,H (t) RH (t) = I |I| Ellenpróbaképp a predikciós algoritmust lefuttattam véletlen, egyenletes eloszlású mesterséges trajektóriák esetére is (az adatok száma az valóságos trajektóriákéval egyez˝o, de a koordinátafüggvények véletlenszeruek), ˝ hogy mérhet˝o legyen, mennyivel jobb a „relevancia” érték a tekintetkövetési adatbázison. A kísérlet eredményeit a 6.8, 6.9 és a 6.10 ábrákon láthatjuk. Az els˝o két ábrán két különböz˝o tesztalany egyedi eredményei, a harmadik ábrán pedig a 17 alany átlagos eredménye látható. A 59
6.8. ábra. vízszintes tengely jelzi a fixációs pontok indexeit. A kísérletekben az els˝o 200 fixációs pontot vettem figyelembe. A függ˝oleges tengely az egyes fixációs indexekhez a 40 kép predikciós vizsgálata során hozzárendelt átlagos relevancia értékek szerepelnek. A kék színnel jelölt görbe a valós trajektóriák alapján készült, a piros színnel jelölt görbe a véletlenszeru ˝ ellenmintára adott eredményeket mutatja.
6.9.
Diszkusszió
A kísérleti eredményekb˝ol kiderült, hogy még az itt alkalmazott leegyszerusített, ˝ részben statikus és a szigorú Markov tulajdonságot feltételez˝o predikciós modell segítségével is lehet˝oség van a tekintet-trajektóriák bizonyos mértéku ˝ el˝orejelzésére. Bár az abszolút relevancia értékek nem magasak, azaz szigorúan nem követik a modell által valószínusített ˝ pozíciókat, mégis tendenciájában a modell sokkal magasabb értékeket biztosít a valós trajektóriák vizsgálatakor, a véletlenszeru ˝ adatokkal szemben. Az itt ismertetett modell már önmagában is lehet˝oséget ad arra, hogy a felhasználó által látott kimeneti információ ismeretében el˝orejelzéseket tegyünk annak várható tekintetmozgására. Az eredményeket kombinálva a már meglév˝o, illetve a korábban bemutatott 60
6.9. ábra.
6.10. ábra.
61
képfeldolgozási módszerek eredményeivel, könnyebben eldönthet˝o, hogy a következ˝o id˝opillanatban a felhasználó várhatóan melyik képterületet fixálja, és így a predikciós információt visszacsatolva a detektorok muködése ˝ pontosítható. Természetesen a modell abszolút pontossága a gyakorlati céloknak valószínuleg ˝ még nem felelne meg, azonban az itt bemutatott módszer számos egyszerusít˝ ˝ o feltevést tett, amelyek elhagyásával és komplexebb dinamikák modellezésével az eredmények is várhatóan pontosabbá tehet˝ok.
6.10.
Kitekintés
Az itt bemutatott modell számos olyan egyszerusít˝ ˝ o feltevést tartalmaz, amelyek a tényleges szakkádvezérlési rendszerben valószínuleg ˝ nem teljesülnek. A szem által feldolgozott információkban például legalább olyan fontos szerepet kapnak a színek variációiból adódóan feltun˝ ˝ o pontok a bottom-up vezérlésben, mint a kontraszt - és lokális struktúra - által vezéreltek. A felhasznált SIFT detektorok jelenlegi formájukban csak a színskála egy dimenzióját, a luminanciát, és annak változásait tudják figyelembe venni, azonban már léteznek olyan általánosítások, amelyek képesek a modellt kiterjeszteni a színes információ feldolgozására is, ezáltal b˝ovítve az észlelhet˝o invariáns pontok halmazát. Ezzel a lehet˝oséggel foglalkozik részletesebben [19], és [20]. Mivel az emberek a valóságban általában nem állóképeket, hanem dinamikusan mozgó képrendszert látnak, ezért a szakkádtervez˝o rendszer muködésében ˝ fontos szerepet kapnak az id˝obeli tranziens jelek is. Egy hirtelen feltun˝ ˝ o / eltun˝ ˝ o tárgy, egy gyors mozgás nem feltétlenül vonja magára a figyelmünket akkor, ha csak egy állóképen vizsgáljuk azt. Dinamikus esetben épp ezért a felhasznált szur˝ ˝ okészletünket ki kell egészíteni olyan módszerekkel, amelyek képesek az id˝obeli tranziens jelek detektálására. Az itt ismertetett statikus modellel szemben feltehet˝o az is, hogy a szakkádtervezés nem rendelkezik a Markov tulajdonsággal, azaz a rendszernek van memóriája. Önmagában viszont ez sem elég, hiszen például egy periódikus, folyamatosan jelenlév˝o tranziens jel (például a kurzor villogása, egy kerék forgása), egy id˝o után kikerül az érdekl˝odésünk középpontjából. 62
A figyelem egy másik modellje szerint mindig az ember a szakkádok tervezése közben mindig az új információkat keresi, amelyek változtathatnak a bels˝o, világról kialakult eddigi modellen. Ennek egy valószínuségszámítási ˝ alapokon nyugvó modelljét adja [12], amely a saliency fogalmát úgy definiálja, hogy azok a legérdekesebb pontok egy adott képen / filmen, amelyek a pillanatnyi modellünkhöz képest a legtöbb újdonságot hordozzák (azaz nem illeszkednek jól a pillanatnyi modellbe). A legfrissebb kutatások pedig igyekeznek a lokális információkon alapuló predikciót gyors, a képre globálisan jellemz˝o információk segítségével javítani [13]. Az itt bemutatott kutatási területek eredményei a közvetlen predikciós eredményeken túl, megfelel˝o top-down modellek birtokában a jöv˝oben felhasználhatóak lesznek arra is, hogy az egyes szakterületeken dolgozó emberek tudását is modelezzhessék annak olyan olyan aspektusait rögzítve, amelyek a konvencionális oktatás során nem, vagy csak nehezen adhatóak át, és modellben is nehezen rögzíthet˝oek a jelenleg használt szakért˝oi rendszerek keretei között. Példaképp említhet˝o az orvosi diagnosztika területe, ahol a diagnosztikai médiumok általában képek és videók. Itt a szükséges szakmai tudást jól modellezni képes algoritmusoknak szerep juthat mind a diagnózisok felállításának folyamatában, mind a leend˝o szakemberek vizsgáztatásában és felkészítésében. Az itt bemutatott eredményekb˝ol tehát kiderül, hogy a tekintetkövetés egy aktívan fejl˝od˝o ág, amely a neurobiológia, a fiziológia, a kognitív modellezés és a képfeldolgozás eredményeit ötvözve fontos szerepet kap önmagunk megismerésének folyamatában.
63
7. fejezet Köszönetnyilvánítás Köszönöm L˝orincz Andrásnak, témavezet˝omnek és az ELTE NIPG csoport vezet˝ojének, hogy lehet˝oségem volt a diplomatémám írása közben a csoport tagjaként a munkájukban is részt venni, és a rengeteg segítséget, amit t˝ole és a csoport tagjaitól kaptam. Külön köszönet illeti Szirtes Gábort, aki kifogyhatatlan ötlet-áradattal segített a problémák leküzdésében. Ezenkívül szeretnék köszönetet mondani családomnak, különösen édesanyámnak, aki a családi feladatokon túl még tev˝olegesen is részt vállalt diplomámban, a képek manuális szegmentálásának fárasztó folyamatában nyújtott segítségével.
64
Irodalomjegyzék [1] Paul Viola and Michael J. Jones. Robust real-time object detection. Technical Report CRL-2001-01, Cambridge Research Laboratory, 2001. [2] Csurka, G., Dance, C., Fan, L., Willamowski, J., & Bray, C. (2004). Visual categorization with bags of keypoints. Proc. ECCV International Workshop on Statistical Learning in Computer Vision. [3] Farquhar, J., Szedmak, S., Meng, H., & Shawe-Taylor, J. (2005). Improving "bag-of-keypoints" image categorisation (Technical Report). University of Southampton. [4] Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998 [5] Mikolajczyk, K., & Schmid, C. (2003). A performance evaluation of local descriptors. Proc. CVPR (pp. 257–263). [6] Perronnin, F., Dance, C., Csurka, G., & Bressan, M. (2006). Adapted vocabularies for generic visual categorization. Proc. ECCV. [7] D.G.Lowe; "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, Vol.60, No.2, pp.91-110, 2004. [8] Heymann,S., Müller,K., Smolic,A., Fröhlich,B., Wiegand,T.; SIFT Implementation and Optimization for General-Purpose 65
GPU. WSCG’2007 The 15th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (2007) [9] Botev, Z.; Kroese, D.P. Global likelihood optimization via the cross-entropy method with an application to mixture models. Simulation Conference, 2004. [10] Jeff A. Bilmes; A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. International Computer Science Institute, 1998. [11] Andrew Moore, Very Fast EM-based Mixture Model Clustering using Multiresolution kd-trees. In: Neural Information Processing Systems Conference, 1998. [12] L. Itti, P. Baldi, Bayesian Surprise Attracts Human Attention, In: Advances in Neural Information Processing Systems, Vol. 19 (NIPS*2005), pp. 1-8, Cambridge, MA:MIT Press, 2006. [13] Beyond bottom-up: Incorporating task-dependent influences into a computational model of spatial attention. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Jun 2007. [14] L. Itti, P. Baldi, Modeling what attracts human gaze over dynamic natural scenes, In: Computational Vision in Neural and Machine Systems, (L. Harris, M. Jenkin Ed.), Cambridge, MA:Cambridge University Press, 2006. [15] U. Rutishauser, C. Koch; Probabilistic modeling of eye movement data during conjunction search via feature-based attention. Journal of Vision (2007) 7(6):5, 1-20 [16] T. Serre, A. Oliva, T. Poggio; A feedforward architecture accounts for rapid categorization. Proc. of the National Academy of Sciences of USA. (2007)
66
[17] Robert E. Schapire, Yoav Freund, et al.; Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods. Proc. 14th International Conference on Machine Learning (1997) [18] Y. Abramson, Y. Freund; Active Learning for Visual Object Recognition. UCSD Technical report. (2006) [19] J. Stöttinger, N. Sebe et al.; Colour Interest Points for Image Retrieval. Computer Vision Winter Workshop 2007, Michael Grabner, Helmut Grabner (eds.) St. Lambrecht, Austria, February 6-8 Graz Technical University [20] Joost van de Weijer, C. Schmid; Coloring Local Feature Extraction. European Conference on Computer Vision, vol. 2, pp. 334-348, Springer, 2006 [21] W. Kienzle, F. A. Wichmann, B. Schölkopf, M. O. Franz; A Nonparametric Approach to Bottom-Up Visual Saliency. In: Advances in Neural Information Processing Systems: NIPS 2006, 1-8 (12 2006) [22] W. Kienzle, F. A. Wichmann, B. Schölkopf, M. O. Franz; Learning an Interest Operator from Human Eye Movements. In: 2006 Conference on Computer Vision and Pattern Recognition Workshop, 1-8 (04 2006) [23] L. Itti; Quantitative modelling of perceptual salience at human eye position. Visual Cognition, Psychology Press, Volume 14, Numbers 4-8, -8/August-December 2006, pp. 959-984(26) [24] Stefan Van Der et al.; Eye movement trajectories and what they tell us. In: Neuroscience and biobehavioral reviews (Neurosci. biobehav. rev.) ISSN 0149-7634 006, vol. 30, no5, pp. 666-679 [25] Martinez-Conde S, Macknik SL, Hubel DH.; The role of fixational eye movements in visual perception. Nat Rev Neurosci. 2004 Mar;5(3):229-40.
67
[26] R. Bednarik, K. Tomi, et al.; Eye-movements as a biometric. In: Scandinavian conference on image analysis, vol. 3540, pp. 780-789 (2005) [27] http://en.wikipedia.org/wiki/Support_vector_machine (2007. 05. 21.) [28] http://en.wikipedia.org/wiki/Principal_components_analysis (2007. 05. 21.) [29] http://en.wikipedia.org/wiki/Eye (2007. 05. 21.) [30] http://en.wikipedia.org/wiki/Eye_movement (2007. 05. 21.) [31] http://en.wikipedia.org/wiki/Retina (2007. 05. 21.) [32] http://www.l-a-v-a.org/ (2007.05.21.) [33] http://www.emt.tugraz.at/~pinz/data/GRAZ_01/ (2007.05.21.) [34] http://www.intel.com/technology/computing/opencv/index.htm (2007.05.21.) [35] http://www.torch.ch (2007.05.21) [36] Chih-Chung Chang, Chih-Jen Lin; LIBSVM: a library for support vector machines. 2001 http://www.csie.ntu.edu.tw/~cjlin/libsvm/ (2007.05.21)
68