ITS ´ zprava ´ Technicka - FIT - VG20102015006 - 2011 - 05 ´ ık, ing. Petr Nohejl, ing. Aleˇs Lan´ ´ Martin Kolaˇ ´ r M.Sc. ing. Jiˇr´ı Kral,
Faculty of Information Technology, Brno University of Technology 1.12.2011
Obsah
1 ITS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Webov´ y klient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Webov´ y server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Django framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 N´ avrh webov´e aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Relaˇcn´ı datab´azov´ y model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Struktura Django projektu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Tr´enov´an´ı SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Extrakce pˇr´ıznak˚ u.......................................................... 4.2 Stochastic Gradient Descent pro SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Handler pro obsluhu VideoTerror datab´aze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Klasifikace SVM sk´ ore s pouˇzit´ım grafu spojitost´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Datov´e uloˇziˇstˇe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Souˇcasn´ y stav ˇreˇsen´eho probl´emu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0
1 3 4 4 4 4 5 6 6 6 7 8 10 11
Abstrakt C´ılem projektu ITS (Image Tag Suggestion) je vytvoˇrit webovou aplikaci, kter´ a zajiˇst’uje spr´ avu fotografi´ı a automatick´e tagov´ an´ı na z´ akladˇe klasifikace obrazu. Aplikace funguje na principu soci´ aln´ıch s´ıt´ı a umoˇzn ˇuje uˇzivatel˚ um sd´ılet data mezi sebou, vytv´ aˇret skupiny, vyhled´ an´ı v obrazov´ ych datech atd. Hlavn´ı oblast´ı z´ ajmu v tomto projektu je vˇsak inteligentn´ı tagov´ an´ı tzn. uˇzivateli jsou automaticky generov´ any moˇzn´e tagy v obraze a to jak na z´ akladˇe klasifikace z detektor˚ u r˚ uzn´ ych objekt˚ u (napˇr. detektor obliˇcej˚ u, postav, aut . . . ) tak i na z´ akladˇe znalost´ı dodan´ ych uˇzivatelem (j´ım oznaˇcen´ ych tag˚ u) a pravdˇepodobnosti v´ yskytu tˇechto tag˚ u souˇcasnˇe.
1
ITS
Projekt ITS si klade za c´ıl vytvoˇrit webovou aplikaci, kter´ a zajiˇst’uje spr´ avu fotografi´ı a automatick´e tagov´an´ı na z´ akladˇe klasifikace obrazu. Na diagramu 1.1 je zn´azornˇena z´ akladn´ı struktura syst´emu.
Obr´ azek 1.1. Sch´ema funkˇcn´ıch blok˚ u projektu ITS
– Web Client Pˇredstavuje webov´ y prohl´ıˇzeˇc, ve kter´em se zobrazuj´ı HTML v´ ystupy front-endov´e ˇca´sti proˇ jektu. Rada uˇzivatelsk´ ych funkc´ı, jako napˇr´ıklad tagov´an´ı obr´azk˚ u nebo nahr´ av´ an´ı obrazov´ ych 1
dat na server zajiˇst’uje klientsk´ y JavaScript, kter´ y skrze skrze JSON1 komunikuje se serverem. Tento blok je podrobnˇeji rozeps´an v kapitole 2.
– Web Server Web server zaˇstituje obsluhu klientsk´ ych ˇca´st´ı a spouˇstˇen´ı klasifikaˇcn´ıch blok˚ u. Obrazov´a data jsou ukl´ad´ana do datov´eho uloˇziˇstˇe na samostatn´em serveru pˇres Video Terror API (d´ale jen VTAPI). V´ıce o tomto bloku v kapitole 3.
– Interaktivn´ı klasifik´ ator Interaktivn´ı klasifik´ ator generuje strom moˇzn´ ych tag˚ u na z´ akladˇe pravdˇepobnosti tag˚ u dan´ ych statick´ ym klasifik´ atorem, tag˚ u dan´ ych uˇzivatelem a pravdˇepodobnosti v´ yskytu jednotliv´ ych tag˚ u mezi sebou. V kapitole 5 je podrobnˇeji pops´ ana ˇcinnost tohoto bloku.
– Statick´ y klasifik´ ator Statick´ y klasifik´ ator generuje pravdˇepodobnosti tag˚ u pouze na z´ akladˇe pˇr´ıznak˚ u z obrazov´ ych dat. Tento blok m˚ uˇze obsahovat libovoln´e klasifik´atory (napˇr. AdaBoost, SVM , . . . ). Viz kapitola 4.
– Feature extraktory Tento blok zajiˇst’uje extrakci pˇr´ıznakov´ ych vektoru k obrazov´ ym dat˚ um. Obecnˇe se m˚ uˇze jednat o libovoln´e pˇr´ıznaky (napˇr. LBP2 , SURF3 , . . . ) podrobnˇeji viz kapitola 4.
– Datov´ e uloˇ ziˇ stˇ e Uloˇziˇstˇe poskytuj´ıc´ı prostor pro ukl´ad´an´ı a naˇc´ıt´an´ı obrazov´ ych ale i programov´ ych (pˇr´ıznakov´e vektory, v´ ystupy statick´ ych klasifik´ator˚ u) dat. Podrobnˇeji viz kapitola 6.
Datov´a komunikace mezi jednotliv´ ymi bloky je realizov´ana pomoc´ı VTAPI kromˇe pˇred´ av´ an´ı dat webov´eho serveru s klientem, kde jiˇz z principu je vyuˇzit protokol HTTP.
1 2 3
http://www.json.org/ Local binary patterns[3] Speeded-Up Robust Features[1]
2
2
Webov´ y klient
Klientsk´a ˇca´st cel´eho syst´emu je generov´ana jako dynamick´a webov´a str´anka skrze webov´ y framework Django (viz kapitola 3). Pro potˇreby uˇzivatelsk´eho rozhran´ı (d´ale jen UI) inteligentn´ıho tagov´an´ı se vyuˇz´ıvaj´ı scripty bˇeˇz´ıc´ı na klientsk´e ˇc´asti napsan´e v jazyce Java script. Tyto scripty komunikuj´ı s webov´ ym serverem skrze form´at JSON. Jedn´ a se pˇredevˇs´ım o dotazy na tagy obs´ ahl´e v aktu´aln´ım obraze, pˇrid´ an´ı nov´eho tagu a mimo jin´e dotaz na navrhovan´e tagy. UI klientsk´e ˇca´sti bylo navrhnuto s ohledem na jednoduchost pouˇzit´ı a snaˇz´ı se kop´ırovat trendy, kter´e lze vysledovat na port´ alech obdobn´ ych sluˇzeb. Na obr´ azku 2.1 je zn´azornˇen n´ avrh UI, respektive nejd˚ uleˇzitˇejˇs´ı ˇca´sti a to interaktivn´ıho tagovac´ıho n´ astroje.
Obr´ azek 2.1. N´ avrh UI projektu ITS
V tomto n´ avrhu je zhruba nast´ınˇena moˇznost jak´ ym zp˚ usobem by mˇelo b´ yt prov´adˇeno napov´ıd´an´ı tag˚ u, kter´e se v obraze ˇrad´ı do hierarchick´e stromov´e struktury. Do budoucna se poˇc´ıt´a s implementac´ı rozliˇcn´ ych verz´ı t´eto komponenty za u ´ˇcelem zlepˇsen´ı pouˇzitelnosti rozhran´ı (napˇr. 3D zobrazen´ı zkrze WebGL4 ). 4
Web-based Graphics Library
3
3
Webov´ y server
Webov´e rozhran´ı ITS projektu je implementov´ano v jazyce Python s vyuˇzit´ım frameworku Django. 3.1
Django framework
Django je otevˇren´ y komplexn´ı webov´ y framework napsan´ y v jazyce Python. Umoˇzn ˇ uje rychl´ y v´ yvoj webov´ ych aplikac´ı a efektivn´ı spr´ avu dat pomoc´ı vlastn´ıho administraˇcn´ıho rozhran´ı. Cel´ y framework je zaloˇzen na konceptu ”DRY”(Don’t repeat yourself) a znovupouˇzitelnosti jednotliv´ ych komponent. Pouˇz´ıv´ a relaˇcn´ı datab´azov´ y model a podporuje nˇekolik datab´azov´ ych syst´em˚ u vˇcetnˇe PostgreSQL, kter´ y projekt ITS pouˇz´ıv´ a. Django je zaloˇzeno na softwarov´e architektuˇre MVC (Modelview-controller). J´adro frameworku tvoˇr´ı ORM (objektovˇe-relaˇcn´ı mapper), kter´ y propojuje datov´ y model, reprezentovan´ y tˇr´ıdami, s relaˇcn´ı datab´az´ı. Vestavˇen´ y ˇsablonovac´ı syst´em umoˇzn ˇ uje snadno renderovat modˇ elov´a data do HTML str´anek. Sablony rovnˇeˇz podporuj´ı dˇediˇcnost. Django d´ ale nab´ız´ı vlastn´ı webserver urˇcen´ y pro v´ yvoj a testov´an´ı aplikac´ı. Pro ostr´ y provoz se obvykle pouˇz´ıv´ a webserver Apache 2 s modulem Mod Python nebo WSGI. 3.2
N´ avrh webov´ e aplikace
Webov´a aplikace umoˇzn ˇuje nahr´ avat, prohl´ıˇzet, sd´ılet a spravovat fotografie. Fotografie lze sdruˇzovat do galeri´ı. Syst´em umoˇzn ˇuje registraci nov´eho uˇzivatele a pˇrihl´aˇsen´ı. Uˇzivatel m´a moˇznost vytv´aˇret a spravovat galerie, vytv´aˇret a spravovat skupiny uˇzivatel˚ u, sd´ılet galerie mezi skupinami. Jednotliv´ ym fotografi´ım je moˇzn´e pˇriˇrazovat tagy. Uˇzivatel m˚ uˇze urˇcit pozitivn´ı i negativn´ı klasifikaci tagu. Syst´em d´ ale umoˇzn ˇuje ukl´adat historii vˇsech operac´ı a zobrazovat notifikace na v´ yznaˇcn´e ud´ alosti (napˇr. uˇzivatel ve skupinˇe, jej´ımˇz jsem ˇclenem, vytvoˇril novou galerii). 3.3
Relaˇ cn´ı datab´ azov´ y model
Datab´ azov´ y model webov´e aplikace zn´azorˇ nuje n´ asleduj´ıc´ı diagram 3.1.
Obr´ azek 3.1. Datab´ azov´ y model django aplikace
4
Uveden´ y ER diagram pˇredstavuje ORM model, definovan´ y jednotliv´ ymi tˇr´ıdami v jazyce Python. Tˇr´ıda User je souˇca´st´ı vestavˇen´eho modulu django.contrib.auth frameworku Django. Modul poskytuje metody pro oˇsetˇren´ı autentifikace uˇzivatele. Pouˇzit´ı modulu je z´ aroveˇ n nezbytn´e pro spuˇstˇen´ı administraˇcn´ıho rozhran´ı Djanga. Pˇr´ıznak is staff znaˇc´ı, zda m´a uˇzivatel pˇr´ıstup do administraˇcn´ıho rozhran´ı. Pˇr´ıznak is active znaˇc´ı, zda se m˚ uˇze uˇzivatel pˇrihl´asit. Hodnota false obvykle znamen´ a, ˇze uˇzivatel smazal sv˚ uj u ´ˇcet, nebo byl zablokov´an administr´ atorem. Poloˇzka is superuser urˇcuje, zda m´a uˇzivatel pln´a pr´ava upravovat data v administr´ atorsk´em rozhran´ı. Tˇr´ıda UserProfile rozˇsiˇruje vestavˇen´ y model User a uchov´av´ a nav´ıc cestu k avataru. Tˇr´ıda HistoryItem uchov´av´ a informace o proveden´e operaci v r´amci jedn´e transakce (napˇr. pˇrid´ an´ı fotografi´ı do galerie, smaz´ an´ı, sd´ılen´ı atd.). Poloˇzka timestamp ukl´ad´a ˇcasov´e raz´ıtko operace a promˇenn´a action urˇcuje typ operace. Model Gallery uchov´av´ a vˇsechny dostupn´e galerie. D˚ uleˇzit´ a je zde poloˇzka identificator, kter´ a pˇredstavuje jednoznaˇcn´ y prim´ arn´ı kl´ıˇc do galerie v rozhran´ı VTAPI. Promˇenn´a cover znaˇc´ı cestu k n´ ahledov´emu obr´ azku galerie. Model Photo m´a svoje pojmenov´an´ı a ukl´ad´a cestu k obr´ azku na serveru. Tˇr´ıda Tag uchov´av´ a jm´eno tagu, popis a podobnˇe jako Gallery jednoznaˇcn´ y identificator tagu ve VTAPI. Model TagMembership urˇcuje, kter´ a fotografie m´a pˇriˇrazen´ y urˇcit´ y tag. Tˇr´ıda Clan pˇredstavuje skupinu uˇzivatel˚ u. Kaˇzd´a skupina m´a sv´eho vlastn´ıka, n´ azev a vlastn´ı avatar. Model ClanMembership definuje pˇr´ısluˇsnost jednotliv´ ych uˇzivatel˚ u do skupin. Tˇr´ıda Permission ukl´ad´a informace o pˇr´ıstupov´ ych pr´avech ke galerii. Definuj´ı se z´ akladn´ı pr´ava pro ˇcten´ı, z´ apis a dalˇs´ı rozˇsiˇruj´ıc´ı pr´ava.
3.4
Struktura Django projektu
Projekt pouˇz´ıv´ a nˇekolik extern´ıch modul˚ u. Modul django schemata zajiˇst’uje pr´aci s PostgreSQL sch´ematem. ITS projekt pouˇz´ıv´ a dvˇe sch´emata. Prvn´ı sch´ema Public vyuˇz´ıv´ a pˇr´ımo rozhran´ı VTAPI. Druh´e sch´ema Django pouˇz´ıv´ a samotn´a webov´a aplikace. Modul sorl.thumbnail umoˇzn ˇuje vytv´aˇret n´ ahledy obr´ azk˚ u a vyuˇz´ıv´ a se u galeri´ı. Modul its.multiuploader zajiˇst’uje hromadn´e ukl´ad´an´ı obrazov´ ych dat na server. Hlavn´ı modul cel´e webov´e ˇca´sti je potom its.itsapp, kter´ y pˇredstavuje front-endovou ˇca´st aplikace. V koˇrenov´em adres´ aˇri projektu se nach´ az´ı n´ astroje pro synchronizaci datab´azov´eho modelu s objektov´ ym modelem, spuˇstˇen´ı v´ yvojov´eho webserveru, nastaven´ı pr´av soubor˚ u a dalˇs´ı potˇrebn´e skripty. D´ale se zde nach´ az´ı konfiguraˇcn´ı soubor, nastavuj´ıc´ı pˇripojen´ı k datab´azi, sch´emata datab´aze, pouˇzit´e moduly, cestu ke statick´ ym soubor˚ um, cestu k m´edi´ım, cesty k ˇsablon´ am a r˚ uzn´a dalˇs´ı nastaven´ı. Hlavn´ı modul its.itsapp tvoˇr´ı 3 z´ akladn´ı ˇca´sti. Prvn´ı je objektov´ y datov´ y model, jenˇz je pomoc´ı ORM mapov´an na relaˇcn´ı datab´azi. Dalˇs´ı ˇca´st tvoˇr´ı URL dispatcher, kter´ y pomoc´ı regul´ arn´ıch v´ yraz˚ u mapuje URL cesty na funkce, zpracov´avaj´ıc´ı dan´ y HTTP poˇzadavek. D˚ uleˇzitou souˇca´st´ı modulu jsou views. Jedn´ a se o metody, kter´e vol´a URL dispatcher pˇri zasl´an´ı HTTP poˇzadavku. Na jejich vstupu jsou zad´ any parametry poˇzadavku a v´ ystupem je HTML str´anka. View zpracuje zadan´e poˇzadavky, provede poˇzadovanou funkˇcnost a pˇred´ a v´ ysledn´a data ˇsablonovac´ımu syst´emu. ˇ Sablonovac´ ı syst´em data zpracuje a vygeneruje pˇr´ısluˇsnou HTML str´anku. 5
4
Tr´ enov´ an´ı SVM
4.1
Extrakce pˇ r´ıznak˚ u
Extrakce pˇr´ıznak˚ u kaˇzd´eho obr´ azku se skl´ad´a ze dvou ˇca´st´ı, prvn´ı je extrakce n´ızko´ urovˇ nov´ ych pˇr´ıznak˚ u pomoc´ı programu compute descriptors 32bit.ln5. N´ızko´ urovˇ nov´e pˇr´ıznaky jsou z´ısk´av´ any napˇr´ıklad extraktory SIFT, CSIFT a dalˇs´ımi. Tyto extraktory jsou d´ ale parametrizov´any, pro pˇr´ıklad uvedu parametr pro urˇcen´ı velikosti oblasti z´ ajmu: -dense 8 8. Ve druh´e ˇca´sti se pˇrev´ad´ı pˇr´ıznaky z n´ızko´ urovˇ nov´ ych extraktor˚ u do Bag-of-visual-words reprezentace. Vstupem pro pˇrevod jsou pˇr´ıznaky, a slovn´ık. Pˇrevod tedy spoˇc´ıv´ a v tom, ˇze se poˇc´ıt´a poˇcet v´ yskyt˚ u jednotliv´ ych visu´ aln´ıch slov neboli kombinac´ı n´ızko´ urovˇ nov´ ych pˇr´ıznak˚ u, pro dan´ y obr´ azek. Kaˇzd´ y n´ızko´ urovˇ nov´ y pˇr´ıznak m˚ uˇze b´ yt nav´ıc pˇriˇrazen do jednoho nebo v´ıce slov, podle toho jakou poˇzadujeme pˇresnost. Velikost slovn´ıku pak urˇcuje poˇcet vysoko´ urovˇ nov´ ych pˇr´ıznak˚ u. V´ ystupy extrakce pˇr´ıznak˚ u jsou pˇred´ any handleru, kter´ y je uloˇz´ı do datab´aze pod n´ azvem, kter´ y odpov´ıd´a dan´e parametrizaci. Napˇr´ıklad pro dense sampling s polomˇerem 16 pixel˚ u, CSIFT azev deskriptoru deskriptor, pˇrevod pomoc´ı slovn´ıku KM L12 a nejist´e pˇriˇrazov´an´ı dostaneme n´ DESC DENSE16 CSIFT NoA UNC K32 o10 L01 KM L12. Pro extrakci pˇr´ıznak˚ u byl vytvoˇreny skripty pro lok´aln´ı v´ ypoˇcet a tak´e pro v´ ypoˇcty na SGE. Oba tyto skripty byly vytvoˇreny tak aby minimalizovaly z´ apisy na s´ıt’ov´e disky. 4.2
Stochastic Gradient Descent pro SVM
V souˇcasn´e dobˇe je dostupn´ ych mnoho implementac´ı tr´enovac´ıch algoritm˚ u a n´ astroj˚ u pro Support Vector Machine, s r˚ uzn´ ymi moˇznostmi pouˇzit´ı. V tomto projektu je vyuˇzit Stochastic Gragient Descent (SGD-SVM), protoˇze je schopn´ y, podobnˇe jako jin´e implementace line´arn´ıch SVM, pracovat s rozs´ ahlou datovou sadou. V´ yhodou SGD-SVM je vˇsak rychlost, se kterou zpracov´av´ a vstupy, je totiˇz schopn´ y online zpracov´an´ı dat. SGD-SVM vych´ az´ı z gradientn´ıch metod, kter´e vˇsak d´ıky stochastiˇcnosti procesu maj´ı mnohem menˇs´ı ˇsanci uv´ aznout v lok´aln´ıch extr´emech. Historicky se metody zaloˇzen´e na Stochastick´em Gradient Descentu (SGD) pojily hlavnˇe s neuronov´ ymi s´ıtˇemi, ale L´eon Bottou vytvoˇril implementaci SGD pro vˇetˇsinu tr´enovac´ıch algoritm˚ u a pr´avˇe i pro SVM. Implementace v tomto projektu je zaloˇzen´ a pr´avˇe na jeho implementaci SGD-SVM, ale je implementov´ana v Matlabu, a je rozˇs´ıˇrena o Cross-validaci a s n´ı spojen´e obsluˇzn´e postupy. Matlab byl vybr´ an pro implementaci kv˚ uli rychlosti pr´ace s maticemi. Algoritmus je pops´ an v n´ asleduj´ıc´ım pseudok´odu 0.1: % stratifies input data into __cv_count__ bins according to y [train test] = stratified_sampling(x,y,cv_count) % train and test are fields for all bins for all lambda init(params) for i = 1:epochs new_params = train_sgd_svm(cur_train,params) params = new_params end results = test_sgd_svm(cur_test) store(results,params) end end best_bin_params =best_bin(results,params) store(avg(best_bin_params)) 5
http://kahlan.eps.surrey.ac.uk/featurespace/web/desc/compute descriptors 32bit.ln
6
Listing 0.1. Algoritmus pro tr´enov´an´ı SGD-SVM
Jak je vidˇet z pseudok´odu algoritmus prov´ad´ı tr´enov´an´ı na datech v takzvan´ ych epoch´ ach, kter´ ych je voliteln´ y poˇcet. D´ale tak´e je dobr´e si vˇsimnout pr˚ umˇerov´an´ı parametr˚ u nejlepˇs´ıho cross´ validaˇcn´ıho shluku. Ukolem metody vykon´avaj´ıc´ı tento pseudok´od je zjistit, jak´e nastaven´ı parametru λ je nejlepˇs´ı, a spolu s t´ımto parametrem uloˇzit odpov´ıdaj´ıc´ı nastaven´ı klasifik´atoru pro danou tˇr´ıdu.
V´ ysledky tr´enov´an´ı (parametry) ale i odezvy jednotliv´ ych SVM prodan´e obr´ azky jsou uloˇzeny do DB pomoc´ı handleru, kter´ y je uloˇz´ı do datab´aze pod zadan´ ym n´ azvem.
4.3
Handler pro obsluhu VideoTerror datab´ aze
Tento program shrnuje funkcionalitu potˇrebnou pro pr´aci s VideoTerror datab´az´ı v r´amci projektu ITS. Za pomoc´ı VTAPI umoˇzn ˇuje spravovat a ukl´adat informace k obr´ azk˚ um (interval˚ um), extraktor˚ um deskriptor˚ u, SVM klasifik´ator˚ um (proces˚ um) a tag˚ um. Pro kaˇzd´ y obr´ azek budeme ukl´adat deskriptory (vektory typu float), odezvy SVM pro kaˇzd´ y tag a kaˇzdou parametrizaci (vektory typu float) a tagy (ohodnocen´ı 1,0,-1 znaˇc´ıc´ı pˇr´ıtomnost,neznalost,nepˇr´ıtomnost dan´eho tagu). Pro deskriptory budeme ukl´adat pouze n´ azvy parametrizac´ı a parametry pro spuˇstˇen´ı extraktoru. V procsu SVM budeme ukl´adat parametry SVM (vektor float a dalˇs´ı float promˇenn´e). 7
5
Klasifikace SVM sk´ ore s pouˇ zit´ım grafu spojitost´ı
Pro kaˇzd´ y obr´ azek jsou zn´am´e v´ ystupy SVM klasifik´atoru pro kaˇzd´ y tag (tˇr´ıdu), a tak´e jiˇz zn´am´e uˇzivatelsk´e ohodnocen´ı pˇr´ıtomnosti nebo nepˇr´ıtomnosti nˇekter´ ych tag˚ u {true, false}. Tyto informace se zkombinuj´ı v grafu, kter´ y je konstruov´an na z´ akladˇe pˇredchoz´ıch spojitost´ı. Na nˇem se n´ aslednˇe pouˇzije inferenˇcn´ı algoritmus Gibbs Sampling. V´ ystupy SVM jsou vˇsak nedostateˇcnˇe informativn´ı (viz obr´ azek 5.1), a proto napom´ ahaj´ı informace o spojitosti mezi objekty.
Obr´ azek 5.1. Visualizace SVM v´ ystup˚ u
Nejdˇr´ıve se provede multi-dimension´ aln´ı logistick´a regrese v´ ystup˚ u SVM. Tato regrese se kalibruje na vˇsech SVM pro dan´ y tag. Proces kalibrace je nez´avisl´ y na zbytku algoritmu a uˇz´ıv´ a pouze informace o stavu zn´am´ ych tagu. V´ ystupem kalibrace je ohodnocen´ı {true, false} pro kaˇzd´ y tag a pro kaˇzd´ y obr´ azek. Z´ avislosti mezi vˇsemi p´ ary tag˚ u (x, y) se seˇrad´ı podle abs(p(x, y) − p(x)p(y)), protoˇze p(x, y) = p(x)p(y) odpov´ıd´a nez´ avislosti. Vybere se jenom n nejv´ıce z´ avisl´ ych, a z nich se vytvoˇr´ı graf. (viz obrazek 5.2)
Pak se stejn´ ym zp˚ usobem do grafu pˇridaj´ı spojitosti mezi v´ ystupem logistick´e regrese SVM pro kaˇzd´ y tag. Testov´an´ı bylo zat´ım prov´adˇeno nez´avisle na t´eto ˇca´sti. Pro dan´ y obr´ azek jsou zn´am´e jist´e tagy (ano a ne), a ty jsou zafixovan´e v grafu. Na zbytku grafu se pouˇzije Gibbs sampling[2], tedy n´ ahodn´ a aktualizace n´ ahodn´ ych uzl˚ u podle aktu´aln´ıho 8
Obr´ azek 5.2. Graf spojitost´ı tag˚ u
stavu okoln´ıch uzl˚ u a distribuc´ı mezi nimi. M´ısto modelov´an´ı distribuce kaˇzd´e hrany se pouˇz´ıv´ a neparametrick´e spojen´ı skuteˇcn´ ych dat, coˇz ˇreˇs´ı probl´em s propagac´ı velmi n´ızk´e pravdˇepodobnosti kaˇzd´eho tagu. Tato metoda je optimalizov´ana pouˇzit´ım mex6 C k´odu v matlabu. Samotn´ y Matlab na inferenci jednoho obr´ azku potˇrebuje cca. 20 vteˇrin, a optimalizovan´a metoda s pˇredzpracov´an´ım umoˇzn´ı na stoln´ım PC 500 inferenc´ı za vteˇrinu.
Obr´ azek 5.3. ROC kˇrivky
Na obr´ azku 5.3 jsou vyobrazeny v´ ysledky metody pro subset obr´ azk˚ u, kter´ y m´a v´ıce neˇz n zn´am´ ych tag˚ u. N je pouˇzito na inferenci a ostatn´ı na mˇeˇren´ı kvality pˇredpovˇedi. ROC kˇrivka vlevo zobrazuje true positive rate vs false positive rate pro pˇr´ıpad n = 9. V pravo pak kˇrivka zobrazuje povrch pod kaˇzdou ROC kˇrivkou pro hodnoty n ∈ (1, 38). 6
MATLAB Executable - mechanizmus poskytuj´ıc´ı rozhran´ı mezi Matlabem a subrutinami napsan´ ymi v nativn´ım k´ odu
9
6
Datov´ e uloˇ ziˇ stˇ e
Tagy, fotografie a veˇsker´e informace o nich jsou uloˇzeny ve VTAPI datab´azi, kter´ a pouˇz´ıv´ a datab´azov´ y syst´em PostgreSQL. Server komunikuje s VTAPI datab´az´ı pomoc´ı speci´ aln´ıho middleware. Middleware pˇredstavuje program napsan´ y v jazyce C a pouˇz´ıvaj´ıc´ı VTAPI rozhran´ı. Pokud chce server komunikovat s VTAPI, spust´ı pˇr´ısluˇsn´ y middleware jako konzolov´ y program a ten mu vr´ at´ı poˇzadovan´a data ve form´atu JSON. Tato data pak server d´ ale zpracuje. Middleware tedy slouˇz´ı jako spojovac´ı m˚ ustek mezi serverem napsan´ ym v jazyce Python a VTAPI napsan´em v jazyce C. Do budoucna se poˇc´ıt´a s odstranˇen´ım tohoto mezi bloku pomoc´ı portu VTAPI do jazyka Python. Datab´ aze VTAPI bˇeˇz´ı na serveru vidte.fit.vutbr.cz. Samotn´ a obrazov´a data jsou uchov´av´ ana na serveru matylda1.fit.vutbr.cz a vˇsechny cesty k tˇemto soubor˚ um jsou uchov´av´ any ve VTAPI datab´azi.
Obr´ azek 6.1. Datov´ a komunikace mezi uloˇziˇsti
Samotn´ y webserver potom bˇeˇz´ı prozat´ım na serveru medusa.fit.vutbr.cz. Datab´aze VTAPI obsahuje dvˇe sch´emata. Prvn´ı sch´ema Public uchov´av´ a data galeri´ı, fotografi´ı, tag˚ u a dalˇs´ıch dat, souvisej´ıc´ıch se zpracov´an´ım obrazu a logicky se vztahuje k samotn´emu VTAPI rozhran´ı. Druh´e sch´ema Django uchov´av´ a informace o uˇzivatel´ıch, skupin´ach, opr´ avnˇen´ıch, sd´ılen´ı apod. S t´ımto sch´ematem pˇr´ımo pracuje webserver. Uˇzivatelsk´ a data jako napˇr. avatary, obr´ azky skupin apod. se rovnˇeˇz ukl´adaj´ı na server matylda1.fit.vutbr.cz a nejsou tedy uloˇzeny lok´alnˇe na serveru medusa. Tato data se ukl´adaj´ı do speci´ alnˇe urˇcen´e galerie. Pˇr´ıznakov´e vektory, kter´e vzniknou zpracov´an´ım obrazu extraktory pˇr´ıznak˚ u jsou ukl´ad´any pˇr´ımo do VTAPI datab´aze odkud jsou ˇcteny jednak statick´ ymi klasifik´atory a tak´e interaktivn´ım klasifik´ atorem. V´ ysledky klasifikace z klasifik´atoru jsou rovnˇeˇz ukl´ad´any do VTAPI datab´aze. 10
7
Souˇ casn´ y stav ˇ reˇ sen´ eho probl´ emu
V souˇcasn´e dobˇe (tedy prosinec 2011) jsou z navrhnovan´eho syst´emu hotovy n´ asleduj´ıc´ı bloky. – Web Client Z´ akladn´ı verze klientsk´e ˇca´sti je hotov´a, kromˇe ˇca´sti tagovac´ıho n´ astroje, na kter´e se v souˇcasn´e dobˇe dˇel´ a. – Web Server Na serveru medusa.fit.vutbr.cz byl nainstalov´an framework Django a byl naimplementov´an webov´ y server, kter´ y implementuje z´ akladn´ı ˇcinost serveru. – Interaktivn´ı klasifik´ ator Byl zpracov´ana z´ akladn´ı verze interaktivn´ıho klasifik´atoru, kter´ a nab´ız´ı vhodn´e tagy. Prozat´ım nen´ı tento blok prov´az´an se zbytkem syst´emu. – Statick´ y klasifik´ ator a feature extraktory Je zpracov´an z´ akladn´ı mechanizmus multitˇr´ıdn´ı klasifikace. Jedn´ a se o 500 tˇr´ıd pˇrevzat´ ych z tasku SIN projektu Trecvid (viz http://www-nlpir.nist.gov/ projects/tv2011/tv2011.html#sin). Prozat´ım nen´ı tento blok prov´az´an se zbytkem syst´emu. – Datov´ e uloˇ ziˇ stˇ e Na serveru vidte.fit.vutbr.cz byla nainstalov´ana PostgreSQL datab´aze, ke kter´e se pˇristupuje skrze VTAPI. Na serveru matylda1.fit.vutbr.cz vzniklo uloˇziˇstˇe pro ukl´ad´an´ı obrazov´ ych dat (tedy dat, na kter´e referuj´ı odkazy z VTAPI datab´aze).
11
Reference 1. H Bay, a Ess, T Tuytelaars, and L Vangool. Speeded-Up Robust Features (SURF). Computer Vision and Image Understanding, 110(3):346–359, ˇcervna 2008. 2. S. Geman and D. Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. Pattern Analysis and Machine Intelligence, IEEE Transactions on, (6):721–741, 1984. 3. Timo Ojala, Matti Pietik¨ ainen, and David Harwood. A comparative study of texture measures with classification based on featured distributions. Pattern Recognition, 29(1):51–59, 1996.
12
