Prohlášení Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj. V Brně, dne 14.5.2011
................................. Petr Hájek
Poděkování Rád bych poděkoval svému vedoucímu, panu RNDr. Janu Sedmidubskému, Ph. D. za jeho cenné odborné rady, rychlé odpovědi a čas, který věnoval při pomoci na vzniku této práce a odstranění různých problémů. Dále bych rád poděkoval RNDr. Michalu Batkovi, Ph. D. za pomoc při vyřešení obtíží s extrakcí lokálních deskriptorů. A konečně bych rád poděkoval svojí rodině za morální a finanční podporu v průběhu psaní této práce, mámě za korekturu a také svým přátelům za podporu psychickou.
Shrnutí Tato práce se zabývá vyhledáváním podobných obrázků tetování. Cílem bylo vytvořit databázi obrázků tetování, vyextrahovat patřičné deskriptory a otestovat úspěšnost výsledků při použití lokálních a globálních deskriptorů.
Klíčová slova Podobnostní vyhledávání, tetování, SIFT, SURF, MPEG-7, MESSIF, MUFIN, globální deskriptory, lokální deskriptory, metrický prostor.
1 Obsah 1 Úvod..................................................................................................................................................1 2 Podobnostní vyhledávání...................................................................................................................2 2.1 Metrický prostor........................................................................................................................2 2.2 Vzdálenostní funkce...................................................................................................................2 2.3 Vyhledávací dotazy....................................................................................................................3 3 Použité technologie...........................................................................................................................5 3.1 MESSIF.....................................................................................................................................5 3.2 MUFIN.......................................................................................................................................5 4 Deskriptory........................................................................................................................................7 4.1 Globální deskriptory..................................................................................................................7 4.2 Lokální deskriptory....................................................................................................................9 5 Testování úspěšnosti globálních a lokálních deskriptorů pro podobnostní vyhledávání tetování...13 5.1 Zdrojová data...........................................................................................................................13 5.2 Kategorie tetování....................................................................................................................13 5.3 Extrakce globálních deskriptorů..............................................................................................14 5.4 Extrakce lokálních deskriptorů................................................................................................15 5.5 Vyhledávací engine..................................................................................................................17 5.6 Testovací rozhraní....................................................................................................................19 5.7 Metodika testování...................................................................................................................22 5.8 Výsledky testování...................................................................................................................22 6 Závěr................................................................................................................................................24 Literatura...........................................................................................................................................25 Příloha A – Kompletní výsledky testování........................................................................................27 Příloha B – Zdrojový kód PHP..........................................................................................................30 Příloha C – Obsah přiloženého CD...................................................................................................32
1 Úvod Rozpoznávání lidí je jedním z úkolů z oblasti výpočetní techniky, které jsou dnes velmi aktuální. Existuje mnoho aplikací, které se snaží tento úkol stále efektivněji, kvalitněji a sofistikovaněji vyřešit. Poptávka po takovýchto službách je velká – ať už jde o firmy, které si přejí autentizovat své zaměstnance či zákazníky, anebo především o sektor bezpečnosti. Hrozba teroristického útoku se stále častěji skloňuje ve všech médiích, ale využití takovýchto technologií je vhodné i pro obyčejnou prevenci zločinu či identifikaci vězňů. Nejčastější poznávací znak, použitý pro identifikaci osob, bývá obličej a na toto téma existuje nepřeberné množství (více či méně) úspěšných projektů. V této práci se nicméně zaměříme na jiný znak – tetování. Prvním důvodem je častý výskyt tetování mezi vězni a členy gangů [1]. Navíc, ačkoliv se v západní civilizaci sice tetování původně vyskytovalo téměř výhradně mezi kriminálními živly, během 20. století se stalo běžnou součástí módního stylu. Tetování tak můžeme v současnosti nalézt u vysokého procenta lidí napříč společností, především u mladé generace. Dalším důvodem je fakt, že tetování je zaneseno do poměrně hluboké vrstvy kůže, takže odolává poškození (i popálení) a rozkladu. Tudíž je možno ho použít pro identifikaci těl obětí zločinů či nehod, v případech, kdy to není možné učinit na základě jiných charakteristik. Hlavním cílem této práce je otestovat a porovnat efektivitu různých technik na tomto specifickém a (v budoucnu) prakticky využitelném úkolu, jakým je vyhledávání podobných obrázků tetování. Konkrétně jde o porovnání vyhledávání na základě lokálních deskriptorů s vyhledáváním na základě globálních deskriptorů. Tato práce využívá systém MUFIN [7], vyvíjený Fakultou informatiky Masarykovy univerzity. Práce je rozdělena na 6 kapitol. V druhé kapitole uvádí čtenáře do problematiky podobnostního vyhledávání a vysvětluje základní teoretické předpoklady. Jsou zde také uvedeny různé druhy podobnostních dotazů a určování míry podobnosti. Třetí kapitola je věnovaná popisu technologie systému MUFIN, který je postaven na knihovně MESSIF. Čtvrtá kapitola se věnuje popisu globálních a lokálních deskriptorů. Globální deskriptory jsou implementací standardu MPEG-7 a z lokálních deskriptorů jsou zde popsány dva nejběžnější – SIFT a SURF. Pátá kapitola je nejobsáhlejší a popisuje praktickou část této práce, tedy samotné testování. V rámci této kapitoly je popsáno nashromáždění požadovaného množství testovacích materiálů, tedy fotografií tetování. Následuje popis extrakce globálních a lokálních deskriptorů, vytvoření vyhledávacího rozhraní a metodiky testování. V závěru této kapitoly jsou vyhodnoceny výsledky. Poslední kapitolu tvoří závěr, který shrnuje tuto práci a nastiňuje možné směry vývoje do budoucna.
1
2 Podobnostní vyhledávání Vyhledávání je jednou z nejdůležitějších operací, kterou s daty můžeme provádět. V klasickém pojetí, kdy data tvoří text či případně čísla, je možné mít data uložené v databázi a vyhledávat na základě přesné shody. V případě moderních multimediálních dat, toto není tak jednoduché, neboť tyto data nemají požadovanou strukturu ani přesnost. Proto přicházíme s novým konceptem, kterým je kvantifikace podobnosti či nepodobnosti mezi dvěma objekty. Abstraktním modelem je metrický prostor, pro který nám postačuje, aby bylo možné změřit vzájemnou vzdálenost mezi dvěma objekty. Tato vzdálenost pak určuje, zda jsou tyto dva objekty podobné či nepodobné.
2.1 Metrický prostor Metrický prostor je obecný model, který může být použit pro efektivní indexování a vyhledávání dat na základě podobnosti. Samotné podobnostní vyhledávání je „[...] řazení objektů podle dotazovaného objektu, kde řadícím kritériem je vzdálenostní funkce.“ [23] Ačkoliv je možné použít jakoukoliv vzdálenostní funkci, byly stanoveny následující metrické postuláty, které vzdálenostní funkci omezují. Nechť D je doména objektů, d je totální vzdálenostní funkce a M= D , d je metrický prostor, definovaný pro tuto doménu a funkci. Vlastnosti funkce d : D x D → ℝ musí splňovat následující postuláty [23]: ∀ x , y ∈D , d x , y ≥0 ∀ x , y ∈D , d x , y =d y , x ∀ x , y ∈D , x = y ↔ d x , y =0 ∀ x , y , z ∈D , d x , z ≤d x , y d y , z
2.2 Vzdálenostní funkce Vzdálenostní funkce určuje vzdálenost mezi dvěma objekty v metrickém prostoru. Je tedy kvantifikací jejich podobnosti. Existuje několik základních typů, které jsou popsány v následujícím textu. Vzdálenostní funkce jsou také často vytvořeny přímo pro určitou doménu dat. Můžeme rozlišit dva typy vzdálenostních funkcí[23]: 1. diskrétní – vzdálenostní funkce, která vrací pouze malý soubor hodnot 2. kontinuální – vzdálenostní funkce, kde je kardinalita souboru vracených hodnot velmi vysoká až nekonečná
2
2.2.1 Minkowského vzdálenosti Minkowského vzdálenosti tvoří celou podskupinu metrických funkcí, které se také označují Lp metriky a závisí na hodnotě parametru p. Tyto funkce jsou definovány na n-dimenzionálních vektorech reálných čísel takto: L p [ x 1, , x n , y 1, , y n ]=
∑ p
n
i=1
∣x i− y i∣p
L1 metrika se nazývá Manhattanská vzdálenost [2] (nebo také City-Block vzdálenost). Tato metrika byla navržena Hermannem Minkowským a vychází z rozvržení ulic v New Yorku, kdy se auta nemohou pohybovat diagonálně. L2 metrika označuje Euklidovskou vzdálenost. To jest zřejmě nejběžnější metrika, kterou v běžné řeči označujeme jako „vzdušnou čarou“. L∞ se nazývá maximální vzdálenost, Čebyševova vzdálenost [3] nebo také šachovnicová vzdálenost. Můžeme si ji představit jako maximální vzdálenost, kterou může ujet král na šachovnici v n tazích. Všechny Lp metriky se hodí pro případy, kdy jsou jednotlivé vektory na sobě nezávislé, například při měřeních vědeckých experimentů nebo při studiích ekonometrických dat. 2.2.2 Jaccardův koeficient Pokud máme dva soubory dat, můžeme použít Jaccardův koeficient [4], vymyšlený Paulem Jaccardem. Ten je definován pro dva soubory dat A a B takto: ∣A ∩B∣ d A , B =1− ∣A ∪B∣ Tato vzdálenostní funkce je založena na poměru kardinalit průniku a sjednocení dvou porovnávaných sad dat. Příkladem použití může být zjištění podobnosti dvou různých textů.
2.3 Vyhledávací dotazy Vyhledávací dotaz je definovaný vyhledávaným objektem q a omezením vracených výsledků. Výsledkem jsou buď všechny objekty, které splňují zadané podmínky, nebo jen určitý počet objektů, které je splňují nejlépe. Toto jsou základní typy vyhledávacích dotazů, které se mohou vzájemně kombinovat. 2.3.1 Rozsahový dotaz Prvním ze základních typů je dotaz na rozsah R(q, r). Dotaz je specifikovaný dotazovaným objektem q a poloměrem rozsahu r, který je omezením vzdálenosti. Tento dotaz vrací všechny objekty, které se nacházejí ve vzdálenosti r a blíže od q. Formálně: R q , r={o∈ X , X ⊆D , d o , q ≤r }
Vracené objekty mohou být (ne nutně) uspořádány podle vzdálenosti od q. Dotazovaný 3
objekt q nemusí být v množině X, postačuje, pokud náleží do stejné metrické domény. Příkladem rozsahového dotazu pro databázi fotografií by mohlo být: Vrať všechny objekty, jejichž škálovatelná barevnost se liší od dotazované fotografie o maximálně 0.2. Speciálním případem rozsahového dotazu je dotaz na přesnou shodu, neboli R(q,0). V tom případě hledáme všechny shodné objekty s dotazovaným objektem. Použitím může být například algoritmus pro odstranění objektu z databáze. 2.3.2 Dotaz na nejbližší objekty Pokud chceme použít rozsahový dotaz, musíme určit maximální rozsah. To často způsobuje problém, jelikož musíme znát použitá data a vzdálenostní funkci. Obzvláště u komplikovaných vzdálenostních funkcí není jednoduché určit požadovaný rozsah. Důsledkem toho je, že rozsahový dotaz nevrací žádný objekt, případně jich vrací příliš mnoho (respektive všechny objekty). Především druhý případ je i zbytečně výpočetně náročný. Z toho důvodu se definuje další typ dotazu, čímž je dotaz na nejbližší objekt. Tento dotaz vrací nejpodobnější objekt k dotazovanému objektu q. Tento dotaz můžeme generalizovat na dotaz na k nejbližších objektů. V tom případě tzv. kNN(q) vrací k objektů, které jsou nejpodobnější objektu q. Pokud je k větší než počet objektů v databázi, pak kNN(q) vrací celou databázi. Formálně: kNN q={R⊆X ,∣R∣=k ∧∀ x ∈R , y ∈X −R :d q , x ≤d q , y }
Příkladem dotazu na nejbližší objekt pro databázi fotografií může být: Vrať 10 fotografií, které mají nejpodobnější tvar jako dotazovaná fotografie. Oba zmíněné dotazy je možné vzájemně kombinovat. Tedy výsledek bude omezen jak poloměrem vzdálenosti, tak počtem vracených výsledků, tj. kNN(q, r). Příkladem takového dotazu je např. dotaz na 3 nejbližší objekty vzdálené nejvíce 0.5 od dotazovaného objektu. Pokud bude více než k objektů v poloměru r od q, bude jich vráceno pouze k nejbližších. A naopak, pokud by některé z k nejbližších objektů byly vzdáleny od q více než r, pak nebudou vráceny. 2.3.3 Komplexní dotaz Předchozí dotazy platily pouze pro dotazy o jednom predikátu. V realitě se ale velmi často ptáme na více predikátů zároveň. V příkladech jsme se dotazovali na barevnost nebo na tvar. Problém nastává, pokud se chceme zeptat zároveň na barevnost i tvar (a případně i na další parametry). Nejlepší výsledek většinou nebývá mezi nejlepšími výsledky pro jednotlivé predikáty. V takovém případě potřebujeme agregační funkci, která přiřadí jednotlivým predikátům požadovanou váhu. Tyto dotazy bývají označovány jako komplexní dotazy.
4
3 Použité technologie Tato práce využívá technologií, vyvíjených již několik let v rámci projektu MUFIN (MUlti-Feature Indexing Network) na Fakultě informatiky Masarykovy univerzity v rámci Laboratoře vyhledávání a dialogu.1
3.1 MESSIF V předchozí kapitole jsme vysvětlili principy podobnostního vyhledávání. Pro další výzkum a provádění experimentů bylo potřeba vytvořit implementaci, která by umožňovala indexaci a vyhledávání v datech. Nejrůznější aplikace podobnostního vyhledávání využívají stejné principy a v některých případech i nízkoúrovňové struktury. Aby došlo k co nejvyššímu opětovnému využití kódu a aby se zjednodušilo vyhodnocování různých experimentů, byla vytvořena vývojová platforma MESSIF [5,6] (neboli Metric Similarity Search Implementation Framework). Její cíle jsou shrnuty následovně [5,6]: •
zajistit základní podporu pro indexování založené na metrickém prostoru
•
vytvořit unifikované a poloautomatické mechanismy pro měření a získávání statistik
•
definovat a použít uniformní rozhraní a tím zajistit modularitu a opětovné užití kódu
•
zajistit infrastrukturu pro distribuované zpracování s důrazem na P2P paradigma
•
podporovat komplexní podobnostní vyhledávání ve více metrických prostorech (viz kapitola 2.3.3 Komplexní dotaz)
Knihovna MESSIF je vytvářena jako svobodný software pod licencí GNU General Public License2 a její zdrojový kód lze nalézt na http://mufin.fi.muni.cz/trac/messif/.
3.2 MUFIN Technologie MUFIN3 [7] slouží jako obecný systém pro efektivní podobnostní vyhledávání ve velkých objemech dat. Celá technologie je založena na 4 základních úrovních (Obrázek 1: MUFIN – přehled systému). Na nejnižší úrovni se nachází P2P síť, která umožňuje, aby systém byl schopný využívat síť strojů, umístěných v různých místech na světě. Jednotlivé stroje si vyměňují data nezávisle na konkrétní hardwarové infrastruktuře a zároveň pro každý index dat (např. histogram barev) zvlášť. V druhé úrovni jsou tyto datové indexy spojeny dohromady. Tato vlastnost umožňuje, abychom vyhledávali pomocí komplexních dotazů (viz kapitola 2.3.3 Komplexní dotaz), jelikož v mnoha případech potřebujeme vyhledávat v různých metrických prostorech (např. hledání podobných obrázků na základě tvaru 1 http://lsd.fi.muni.cz/tiki-index.php 2 http://www.gnu.org/licenses/gpl.txt 3 http://mufin.fi.muni.cz
5
i barevného histogramu). Třetí úroveň obsahuje rozhraní pro spravování dat (vkládání a mazání objektů), zadávání dotazů (viz kapitola 2.3 Vyhledávací dotazy) a rozhraní pro spojování s externími indexy. A konečně nejvyšší úroveň obsahuje několik různých uživatelských rozhraní: Rozhraní pro dávkové zpracování dat, rozhraní telnet, rozhraní pro Java GUI aplikace, webové rozhraní, rozhraní WSDL, rozhraní pro mobilní telefony. [7] Systém je založen na již zmíněné knihovně MESSIF a je naprogramován v Javě. Mezi jeho hlavní výhody patří škálovatelnost pro velké množství dat díky P2P technologii a aproximační podobnostní vyhledávání. Tato vlastnost byla ověřena v experimentu, který proběhl v roce 2009, kdy bylo ozkoušeno podobnostní vyhledávání v reálném čase pro kolekci 50 milionů fotografií. [8] V současnosti funguje také ukázková webová aplikace, umožňující vyhledávat podobné obrázky v databázi, která čítá již 100 milionů fotografií: http://mufin.fi.muni.cz/imgsearch/
Obrázek 1: MUFIN – přehled systému
6
4 Deskriptory Abychom mohli porovnat jednotlivé fotografie a nalézt podobné, musíme z fotografií nejprve vyextrahovat smysluplné deskriptory, které zároveň nebudou příliš náročné, co se týče místa na disku a nebudou výpočetně náročné. Nejdříve obecná definice deskriptoru (angl. feature): „Deskriptor je funkce jednoho či více měření, vypočítaná tak, že kvantifikuje signifikantní rys objektu.“[9] Tato definice je poměrně obecná, a proto dále rozlišujeme deskriptory globální a lokální. Globální deskriptory jsou získávány pro zdrojový obrázek jako celek.
4.1 Globální deskriptory Pro vyjádření globálních deskriptorů používá systém MUFIN standard MPEG-7, který je standardem ISO/ETC [10]. Standard MPEG-7 je určený univerzálně pro všechna multimediální data. Obsahuje tedy deskriptory pro obraz, zvuk, video i pro specializované užití (např. v oblasti medicíny). Pro účely vyhledávání podobných obrázků byly tedy použity pouze MPEG-7 Visual Tools, které obsahují základní struktury a deskriptory pro následující vlastnosti: barva, textura, tvar, pohyb, lokalizace a rozpoznání tváře [11]. Z celkem 20 deskriptorů bylo zvoleno a implementováno následujících sedm [11]: •
Škálovatelná barva (Scalable Color) Tento deskriptor je barevným histogramem v barevném prostoru HSV [12], který je zakódován Haarovou transformací [13]. Implementace tohoto deskripturu v systému MUFIN používá 64 sloupců.
•
Struktura barvy (Color Structure) Tento deskriptor zachycuje jak barevný obsah (stejně jako předešlý deskriptor), tak zároveň i informace o struktuře jeho obsahu. Při extrakci prochází obrázek po strukturujících elementech o rozměrech 8x8 pixelů, nikoliv zvlášť po každém pixelu. Na rozdíl od předešlého deskriptoru je od sebe schopen rozlišit dva obrázky se stejným množstvím určité barvy, ale s jejím rozdílným rozložením.
•
Rozvržení barev (Color Layout) Tento deskriptor efektivně zaznamenává prostorové rozvržení barev v kompaktní podobě. Pro jeho získání se používá DCT (diskrétní kosinová transformace [14]). Jeho výhodou je nezávislost na formátu a nízká výpočetní náročnost. Nabízí škálovatelnost tím, že umožňuje nastavit počet koeficientů – přičemž systém MUFIN jich používá 12.
•
Histogram hran (Edge Histogram) Histogram hran reprezentuje rozložení hran v obrázku. Nejdříve je obrázek rozdělen na podobrázky a následně je každý obrázek zařazen do jedné z pěti kategorií hran: 7
Vertikální, horizontální, +45°, -45° a hrana beze směru. Výsledkem je v systému MUFIN vektor o 80 koeficientech. •
Stejnorodá textura (Homogenous Texture) Každý obrázek můžeme považovat za soubor stejnorodých textur. Pomocí tohoto deskriptoru můžeme nacházet obrázky s podobnými vzory. Použitý vektor obsahuje 62 koeficientů.
•
Tvar oblasti (Region Shape) Pomocí toho deskriptoru můžeme určit tvar obrázku, a to jak jednolitý, tak i složený z více oblastí. Extrakce probíhá pomocí techniky Angular Radial Tranform (ART), která zajišťuje odolnost vůči šumu, rotaci a rozdílným rozměrům. Výsledný vektor obsahuje koeficienty normalizovaných hodnot ART.
•
Tvar kontury (Contour Shape) Na rozdíl od předchozího tento deskriptor zachycuje charakteristiky tvaru okraje (kontury) daného obrázku. Používá k tomu reprezentaci obrazu Curvature Scale-Space. Je robustní vůči malým odchylkám tvaru, změně perspektivy a je kompaktní.
Systém MUFIN definuje metrickou funkci pro daný deskriptor. Každý deskriptor je pak obsažena v jedné vrstvě systému MUFIN, čímž využívá jednu z jeho vlastností – překrývání. Pro získání nejpodobnějšího obrázku pak používáme agregační funkci, která přiděluje jednotlivým deskriptorům váhu, tak aby bylo dosaženo nejlepších výsledků. Pro účely této práce využíváme pouze deskriptor Edge Histogram a Homogenous Texture v poměru vah 50:1, jelikož ostatní pro rozpoznávání tetování nejsou vhodné.
8
4.2 Lokální deskriptory S jiným postupem přicházejí lokální deskriptory. V tomto přístupu se snažíme nalézt lokální klíčové body, nejčastěji rohy objektů, nacházejících se uvnitř obrázku. To můžeme využít pro nejrůznější aplikace, jako je rozpoznávání objektů, případně automatické vytváření panoramat. Pro účely této práce nás zajímá schopnost těchto deskriptorů fungovat nezávisle na měřítku, jelikož jednotlivé testovací fotografie nejsou foceny ve stejných podmínkách (například některá fotografie obsahuje pouze tetování, zatímco jiná obsahuje i část těla, na které ono tetování je, a okolní prostředí). Algoritmů pro získání lokálních deskriptorů je celá řada4, nicméně pro tuto práci byly použity tyto dva: SIFT a SURF. V následujícím textu jsou popsány podrobněji. 4.2.1 SIFT Mezi nejpopulárnější metody patří SIFT (Scale-Invaraint Feature Transform). Tento algoritmus vymyslel a publikoval David Lowe v roce 1999 a posléze si ho nechal patentovat [15]. Jeho výhodou je, že je invariantní vůči měřítku, rotaci, iluminaci, šumu a změně úhlu pohledu. V následující části jsou postupně vysvětleny jednotlivé kroky tohoto algoritmu. Vytvoření škálovatelného prostoru V rámci oboru počítačového vidění byla vyvinuta teorie, jak pracovat se zobrazením, které zachycuje reálné objekty v různých měřítkách – teorie škálovatelného prostoru (scale-space). Základním principem je, že objekty mají svůj význam jen v určitém rozsahu měřítka. Pokud budeme uvažovat o měřítku metrů, pak má smysl rozlišovat objekt jako člověk, pokud budeme uvažovat v měřítku centimetrů, můžeme rozlišovat objekty jako je tetování, pokud použijeme měřítko nanometrů, můžeme rozlišovat jednotlivé buňky pokožky. Dále, v důsledku perspektivy mohou objekty, které jsou stejně velké v zobrazení, být ve skutečnosti různě velké. Proto musíme pracovat na různých úrovních měřítka. Ukazuje se, že takto funguje i vidění savců [16]. Řešením problému, jak získat další zobrazení z toho původního, je odstranit detaily, tzn. rozmazat zobrazení. Z teorie vyplývá [16], že jediným vhodným druhem rozmazání, které nevnáší nové struktury a detaily, je Gaussovo rozmazání. Transformace je provedena pro každý pixel konvolucí s Gaussovskou funkcí: L x , y , σ =G x , y , σ ∗I x , y L je výsledné zobrazení, I(x,y) je původní zobrazení, σ rozptyl Gaussovy funkce a G je následující Gaussova funkce: 2
G x , y , σ =
1 e 2πσ 2
2
− x y 2 2σ
4 Porovnáváním různých lokálních deskriptorů se podrobně zabývá publikace [24]
9
Pokud tento proces opakujeme pro výsledné zobrazení, získáme tak zobrazení v různých měřítkách. Tento soubor zobrazení se nazývá oktáva. Následně zobrazení zmenšíme na poloviční velikost a proces opakujeme. Tím získáme druhou oktávu. Počet rozmazání v oktávě i počet oktáv může být různý, původní návrh od Davida Lowa navrhuje 5 úrovní rozmazání a 4 oktávy [17]. DoG (Rozdíl Gaussových křivek) Dalším krokem je získat obrysy a hrany. K tomuto účelu slouží operace DoG (Difference of Gaussians). Tím získáme aproximaci Laplaceova operátoru Gaussových křivek. V každé oktávě odečteme rozmazané zobrazení od zobrazení, které bylo rozmazáno. Pokud oktáva obsahovala 5 zobrazení, pak takto získáme 4 DoG zobrazení. Matematický zápis, DoG zobrazení: D x , y , σ =L x , y , kσ −L x , y , σ Získání klíčových bodů Abychom získali klíčové body, provedeme další krok, kterým je nalezení extrémů. Každý pixel ve všech LoG porovnáme s jeho sousedy v daném měřítku (tj. 8 pixelů) i v měřítku o jedna menší i větší (9 + 9 pixelů)– tzn. celkem s 26 sousedy. Minimum a maximum těchto bodů jsou kandidáti na klíčový bod. Abychom získali polohu těchto bodů s vyšší přesností než jsou pixely, použijeme na získané hodnoty Taylorův rozvoj druhého řádu. Tím získáme přesnou polohu extrému jako [18]: −1
∂2 D z=− ∂ X2
∂D ∂X
D a jeho deriváty jsou vypočítány pro kandidáty na klíčové body a X=(x, y, σ) je odchylka od tohoto bodu. Eliminace nevhodných bodů V předchozím kroku jsme získali příliš mnoho bodů, z nichž některé nejsou vhodné, a tudíž je nutno je eliminovat. Mezi ně patří body s nízkým kontrastem a body nacházející se na hranách. Odstranění bodů s nízkým kontrastem je jednoduché, pro každý získaný extrém vypočítáme hodnotu D pomocí rovnice [18]: D z =D
1 ∂ D−1 z 2 ∂X
Pokud je absolutní hodnota výsledku menší než stanovená hranice, pak tento bod vyřadíme (v našem případě jsme použili hranici 0.04). Pro to, abychom odstranili body kolem hran a zbyly nám tak pouze body v rozích, využijeme toho, že hlavní křivost napříč hranou bude mnohem větší než hlavní křivost podél této hrany. Použijeme tedy Hessovu matici [18]: 10
H=
[
Dxx Dxy
D xy D yy
]
Pak můžeme zjistit, zda je tato křivost menší než stanovená hranice [18]: D xxD yy
D xx D yy − D xy 2
r12 r
Pokud nesplňuje daný bod tuto podmínku, bude vyřazen. V našem případě jsme použili hranici r=10. Orientace klíčových bodů V tomto kroku přiřadíme k nalezeným klíčovým bodům jednu či více orientací. Účelem toho kroku je zajistit invarianci vůči rotaci. Použijeme zobrazení L (x, y, σ) pro daný klíčový bod v dané úrovni rozmazanosti. Vypočítáme velikost (m) a orientaci (θ) gradientu pomocí této rovnice [18]: m x , y = L x1, y − L x−1, y L x , y 1−L x , y−1 2
θ x , y =tan
−1
L x , y 1−L x , y −1 L x1, y −L x−1, y
2
Tento výpočet provedeme pro všechny pixely v regionu sousedícím s klíčovým bodem v daném rozmazaném zobrazení L. Je vytvořen histogram orientace o 36 sloupcích, tzn. pro každých 10° z 360° jeden. Pro každý pixel přiřadíme do příslušného sloupce dle θ příslušnou náležitě zváženou velikost gradientu [18]. Nejvyšší vrchol tohoto histogramu je výsledná orientace. Pokud některý další sloupec dosahuje alespoň 80% velikosti nejvyššího sloupce, vytvoříme nový klíčový bod se stejným umístěním a orientací danou příslušným sloupcem (pro každý takový sloupec). Vytvoření deskriptorů Posledním krokem je vytvoření jedinečného označení každého nalezeného klíčového bodu. Nejdříve se kolem klíčového bodu vytvoří okno o velikosti 16x16, které je následně rozděleno na 4x4 podoblasti. Pro každou z těchto 16 podoblastí vypočteme velikost a orientaci gradientu (orientace je počítána relativně vůči orientaci klíčového bodu) a uložíme ji do histogramu o 8 sloupcích. Tím pro každý klíčový bod získáme 128dimenzionální vektor. Tato dimenze je poměrně vysoká, nicméně ukázalo se, že vektory o méně rozměrech nepodávaly srovnatelně kvalitní výsledky [15]. Abychom dosáhli invariance vůči iluminaci, tento vektor následně normalizujeme a stanovíme maximální možnou hodnotu jeho komponent. Počet těchto vektorů závisí na počtu nalezených klíčových bodů, což závisí na velikosti a rozlišení obrázku. Tento počet může být relativně vysoký, což vede při použití k vyšší výpočetní a paměťové náročnosti (např. obrázek warriortattoo95.jpg o velikosti 382px × 666px obsahoval 2233 klíčových bodů). 11
4.2.2 SURF Za účelem zrychlení celého procesu a zmenšení rozměrnosti výsledného deskriptoru probíhají neustále snahy o vytvoření nového algoritmu. Jako poměrně úspěšný se ukázal SURF (Speeded-Up Robust Features), poprvé představený v roce 2006 [19]. Jeho základní odlišnosti od dekriptoru SIFT jsou tyto [20]: •
Používá integrální obrazy [21], které nejsou výpočetně náročné.
•
Pro zjištění polohy klíčového bodu používá Hessovu matici (viz výše). Rozdíl je v tom, že nepoužívá Gaussův filtr, nýbrž aproximuje výsledek průměrováním (box filter). Klíčovými body jsou pak extrémy determinantu Hessovy matice.
•
Orientace nalezeného klíčového bodu je určena sumou odezev Haarových vlnek [13]. Deskriptor je následně vypočítán pro oblast okolo klíčového bodu, která je rozdělena na 4x4 podoblasti. Pro každou je vypočítána suma odezev Haarovy vlnky v horizontálním a vertikálním směru a suma absolutních hodnot těchto odezev. Tím získáme 64dimenzionální vektor, což je polovina dimenze deskriptoru SIFT.
Experimentální výsledky prokázaly, že tento deskriptor podává podobně kvalitní výsledky jako SIFT s kratší dobou a náročností výpočtu.[20] Pro názornou ilustraci je zde uvedeno zakreslení vektorů deskriptorů SIFT a SURF do původního obrázku.5 Pro přehlednost je zobrazeno jen 20 nejvýznačnějších z nich.
Obrázek 2: SIFT
Obrázek 3: SURF
5 Pro zobrazení byl použit program showfeats, jehož autorem je Mgr. Tomáš Homola. Více viz http://mufin.fi.muni.cz/~xhomola/showfeats.html
12
5 Testování úspěšnosti globálních a lokálních deskriptorů pro podobnostní vyhledávání tetování Tato kapitola se zabývá praktickým úkolem této práce, t.j. porovnat úspěšnost globálních a lokálních deskriptorů při plnění úkolu podobnostního vyhledávání fotografií tetování. V první fázi došlo ke shromáždění zdrojových fotografií z Internetu. V další fázi byly vyextrahovány globální a lokální deskriptory pro všechny fotografie a vytvořen vyhledávací engine. Dále došlo k vytvoření testovacího rozhraní a samotnému testování. V závěru došlo k vyhodnocení výsledků a navržení zlepšení pro budoucí vývoj.
5.1 Zdrojová data Pro účely našeho testování bylo nutné nejprve vytvořit databázi fotografií tetování. Zadáním bylo vytvořit soubor minimálně 500 fotografií. Po zmapování dostupných internetových zdrojů bylo prvním pokusem zvoleno zkontaktovat server www.bmezine.com, nicméně ten na výzvy ke spolupráci nereagoval. Proto byl zvolen jako zdroj server www.eviltattoo.com díky jednoduché dostupnosti všech fotografií v adresáři http://www.eviltattoo.com/images/. Původní zdroje fotografií na těchto stránkách jsou neznámé, jelikož o nich nejsou uvedeny žádné informace. Lze proto očekávat, že některé z nich mohou být autorsky chráněny. Fotografie byly staženy dávkově programem wget. Po stažení byly vyřazeny duplikáty pomocí programu VisiPics6. Byly vyřazeny pouze naprosto totožné fotografie, lišící se nejvýše rozdílným rozlišením. Fotografie stejného tetování z různého úhlu nebo s rozdílným ořezem byly naopak zachovány pro ověření schopnosti systému najít identické tetování. Dále byly vyřazeny fotografie jiných než klasických forem tetování, jelikož by tvořily kategorii samy o sobě. Těmito technikami bylo: skarifikace, cejchování, tetování bílým inkoustem a inkoustem viditelným pouze pod UV zářením. Výsledkem je sada 11946 fotografií tetování. Celková velikost tohoto souboru dat je 456 MB dat. Všechny tyto fotografie lze nalézt na přiloženém CD (viz Příloha C – Obsah přiloženého CD).
5.2 Kategorie tetování Dalším krokem bylo rozdělit jednotlivé fotografie do různých kategorií, abychom posléze mohli ověřit správnost jejich podobnostního vyhledávání. Základním kritériem bylo, aby jednotlivé kategorie byly spíše vyjádřením obrazové a nikoliv sémantické informace. Příkladem obrazové kategorie je je například srdce, kotva nebo kříž. Sémantická kategorie je 6 http://www.visipics.info/
13
láska, námořnictví nebo křesťanství. Ačkoliv hledání podobných tetování na základě sémantických kategorií by byl zajímavý a užitečný úkol, šlo by o velmi pokročilý úkol z oblasti umělé inteligence. Pro naše účely se spokojíme s hledáním obrazově podobných tetování. Pro rozdělení bylo tedy nakonec vybráno 51 kategorií, z nichž některé obsahují další podkategorie. Nezařazeno zůstalo 3778 fotografií. Rozdělení je subjektivní, což je problém, který obnáší práce s fotografiemi. V některých případech fotografie patří do více kategorií, jelikož tetování v mnoha případech kombinují více různých motivů dohromady. V rámci každé kategorie se vyskytují poměrně odlišná tetování, jelikož jde o umělecké ztvárnění, ke kterému jejich autoři přistupují se značnou volností (Obrázek 4 ukazuje, jak moc se mohou obrázky v jednotlivých kategoriích lišit). Z těchto kategorií bylo vybráno několik určených přímo pro testování. Jde především o ty kategorie, které obsahují nejjednodušší tvary, u kterých by mělo být jednodušší nacházet podobné tetování. Jmenovitě jsou to: Kotva, srdce, kříž, stopy, oko, Jin & Jang, hudba, anděl, hebrejština, latinka, hmyz, medvěd, obojživelník, štír, modlitba (sepjaté ruce), znak lilie (skautský znak), na rtu, na kloubech ruky.
Obrázek 4: Ukázka rozdílů v rámci jedné kategorie (kříž)
5.3 Extrakce globálních deskriptorů Extrakce proběhla ve dvou fázích. V první fázi došlo k extrakci globálních deskriptorů. V druhé fázi došlo k extrakci lokálních deskriptorů SIFT a SURF. Extrakce proběhla na školním stroji Fakulty Informatiky s názvem cybela1 (konfigurace: Intel Xeon E5405, 8x 2.0 Ghz, 27.5 GB RAM) kvůli vyšší výpočetní a paměťové náročnosti této operace. Extrakce globálních deskriptorů proběhla pomocí programu metaobject-dump. Tento program jako vstup bere buď soubor s obrázkem, nebo adresář s více obrázky, a jeho výstupem jsou vyextrahované MPEG-7 deskriptory (Scalable Color, Color Structure, Color Layout, Edge Histogram, Homogenous Texture, Region Shape, Contour Shape – viz kapitola 4.1 Globální deskriptory). Tento program lze nalézt na přiloženém CD (viz Příloha C – Obsah přiloženého CD). 14
Příklad použití programu: metaobject-dump /tattoos/infinity036.jpg > globaldescriptors Výstupem pak bude tato textová informace obsahující jednotlivé vektory: #objectKey messif.objects.keys. AbstractObjectKey /tattoos/infinity036.jpg ColorLayoutType; messif.objects.impl. ObjectColorLayout; ColorStructureType; messif.objects.impl. ObjectShortVectorL1; EdgeHistogramType; messif.objects.impl. ObjectVectorEdgecomp; HomogeneousTextureType; messif.objects.impl. ObjectHomogeneousTexture; ScalableColorType; messif.objects.impl. ObjectIntVectorL1; RegionShapeType; messif.objects.impl. ObjectXMRegionShape; ContourShapeType; messif.objects.impl. ObjectContourShape 17,20,16,15,18,2; 18,16,16; 46,15,16 7,0,0,0,0,0,0,0,224,255,0,0,0,0,0,0,0,0,0,0,0,0,0,0,100,94,96,86,11,8,0,0,1,1,0,0,12,1,1,0,71, 35,5,4,34,10,0,1,21,6,0,0,21,1,0,0,124,37,24,6,0,0,0,1 5,0,5,1,0,1,2,4,6,6,2,1,3,7,3,5,0,0,6,0,6,0,1,1,0,3,3,4,4,5,3,2,7,6,4,5,1,2,3,1,6,0,1,3,0,2,3,5,6, 5,4,3,4,5,3,5,0,2,3,1,6,0,5,0,1,5,1,4,4,2,3,1,3,6,3,5,0,1,2,0 113;185; 189,217,245,255,233,201,162,162,172,208,173,158,132,129,111,188,108,115,116,109,92,1 62,88,113,121,111,84,140,106,147; 188,220,247,254,236,204,148,153,164,206,163,153,119,121,93,180,92,108,104,91,87,153,7 9,117,104,91,67,146,83,133 -53,-37,-81,68,12,12,25,41,8,-1,4,19,-21,14,19,29,-7,5,0,2,-15,7,1,8,-15,2,2,1,-15,5,1,4,-3,1,0,1,-1,-1,1,2,5,1,-1,-1,-1,-1,4,1,5,0,2,2,2,3,3,1,-12,-2,0,-2,1,0,-3,-3 15,15,15,6,7,7,14,6,13,6,1,5,15,15,10,4,1,4,5,3,1,4,1,2,11,11,11,3,2,0,4,2,2,2,2,2 63; 22; 61; 63; 0,73,10,5,10,5 Výsledný soubor globálních deskriptorů všech fotografií tetování pak zabírá 17.2 MB.
5.4 Extrakce lokálních deskriptorů Extrakce lokálních deskriptorů proběhla pomocí programu extractfeats, jehož autorem je Mgr. Tomáš Homola7. Tento program umožňuje extrahovat jak deskriptory SIFT, tak deskriptory SURF. Program je napsaný v programovacím jazyce C++ za využití knihoven OpenCV a gsl. Pro extrakci byla použita staticky linkovaná verze pro 64bitový Linux. Extrakce proběhla opět na stroji cybela1 (viz výše). Použití programu je následovné: extractfeats --indir=DIR --infile=FILE --inprefix=DIR -r --siftsetname=FILE --siftscalelimit=FLOAT --surfsetname=FILE – surfscalelimit=FLOAT
Parametr --infile nastavuje zdrojový soubor respektive parametr --indir nastavuje zdrojový adresář (-r značí, že má být procházen rekurzivně)
•
Parametr --siftsetname určuje soubor, do kterého budou uloženy vyextrahované deskriptory SIFT (--surfsetname děla totéž pro deskriptory SURF)
•
Parametr --siftscalelimit (respektive --surfscalelimiti) určuje minimální délku škálovatelné komponenty daného deskriptoru SIFT (respektive SURF). Pomocí dalších parametrů lze nastavit další vlastnosti extrakce, viz podrobný popis programu.
Vyextrahovaná data jsou použitelná u deskriptorů SIFT jako MESSIF objekt messif.objects.impl. ObjectFeatureByteL2 a u deskriptorů SURF jako MESSIF objekt messif.objects.impl. ObjectFeatureFloatL2. Vyextrahovaný soubor deskriptorů SIFT pro daný soubor fotografií tetování zabírá 386 MB a soubor deskriptorů SURF 1085 MB, což je více než velikost původního souboru dat.
5.5 Vyhledávací engine Pro dotazování na podobné obrázky musíme vytvořit a spustit vyhledávací engine systému MUFIN na serveru, se kterým posléze můžeme komunikovat pomocí HTTP protokolu. Jelikož sady obrázků není příliš veliká, systém MUFIN využívá pro vyhledávání jednoduchou techniku sekvenčního hledání, která má lineární náklady. Vyhledávání probíhá pomocí dotazu kNN(q)(viz kapitola 2.3.2 Dotaz na nejbližší objekty). Pro vytvoření a spuštění vyhledávacího enginu se používá třída programu MESSIF messif.utility. HttpApplication. Příklad příkazu pro vytvoření vyhledávacího enginu pro globální deskriptory: java -cp "MESSIF.jar" messif.utility. HttpApplication "12345" "engine.cf" enginefile = "engine.bin" objectClass = 'messif.objects.impl.MetaObjectMap' extractor = "metaobject-dump -" datafile=“ globaldescriptors" build Vysvětlení jednotlivých parametrů: •
12345 značí číslo portu TCP, který bude tento engine používat pro komunikaci.
•
Soubor egine.cf obsahuje nastavení pro třídu messif.utility. HttpApplication, které obsahuje například pro globální deskriptory poměr vah pro agregační funkci.
•
Parametr enginefile určuje název výsledného binárního souboru, který obsahuje index.
•
Parametr objectClass určuje třídu, která vyhodnocuje vzdálenost mezi dvěma 16
objekty. Pro globální deskriptory byla použita třída MESSIFu MetaObjectMap, která určuje vzdálenost na základě tvaru a barvy a pro lokální deskriptory byla použita třída ObjectFeatureSetOrdpres. •
Parametr extractor označuje program, který bude použitý k extrakci (jeden z výše zmíněných).
•
Parametr datafile je nepovinný a používá se pouze, pokud je následován parametrem build. V případě, že jsou použity, je vytvořen binární index z deskriptorů uložených v souboru určeném parametrem datafile a tento index je uložen do souboru určeného parametrem enginefile (dojde k přepsání binárního souboru indexu, pokud již existuje se stejným názvem). Pokud nejsou použity, pak je použit již existující binární index.
Pro jednodušší použití byl vytvořen skript, který je spouštěn pouze dvěma či třemi parametry. Tento skript byl následně spuštěn na stroji cybela1. Pro vyhledávání tedy bylo nutné vytvořit SSH tunel spojující počítač, na kterém bylo spuštěno testovací prostředí, se strojem cybela1, na kterém běží engine. Jakmile je vyhledávací engine spuštěn, je s ním možné komunikovat pomocí HTTP protokolu na zadaném TCP portu. Engine umožňuje dvojí použití – vyhledávání k nejbližšísch sousedů pomocí příkazu search a vložení nového obrázku do enginu pomocí příkazu insert. V tomto projektu budeme využívat pouze příkaz search. Volání služby search probíhá pomocí metody http://<stroj>:<port>/search? k=
HTTP
POST
a její
url
je
Tělo této metody musí obsahovat soubor s obrázkem v binární podobě. Parametr k označuje počet nejhledanějších podobných obrázků (jde o dotaz kNN(q)). Tato metoda vrací kód 400, pokud k vyhledání nedošlo a v těle odpovědi je uveden důvod, proč hledání nebylo provedeno. Pokud vyhledání proběhlo úspěšně, metoda vrací kód 200 a v těle odpovědi vrací JSON8 pole o k položkách, kde každá je ve tvaru [vzdálenost, id], které označují k nejpodobnějších obrázků. Vzdálenost označuje výsledek vzdálenostní funkce (tj. nepodobnost mezi nimi) a id jednoznačně identifikuje daný obrázek.
8 http://json.org/
17
5.6 Testovací rozhraní Testovací rozhraní bylo vytvořeno ve skriptovacím jazyce PHP 9 pro předání vizuální informace uživateli, aby mohl vyhodnotit počet podobných či nepodobných obrázků. Jde tedy o grafické znázornění pole JSON, které vrací vyhledávací engine (viz výše), a které obsahuje k nejpodobnějších fotografií. Rozhraní zobrazuje vždy nejprve testovanou fotografii s jejím názvem a posléze tabulku k nejpodobnějších fotografií, u kterých je zobrazen výsledek vzdálenostní funkce od zdrojové fotografie. Následuje příklad volání skriptu, který obsahuje všechny parametry, které lze zadat (pokud nejsou zadány, jsou použity impicitní hodnoty). Pro spuštění je potřeba mít nainstalované a spuštěné PHP na lokálním stroji. http://localhost/upload.php? k=20&p=1234&u=localhost Parametr p určuje port, na kterém tento skript volá vyhledávací engine, parametr u název stroje, na kterém tento engine běží a parametr k počet vrácených obrázků (více viz výše). Zdrojový obrázek (respektive zdrojové obrázky) byly pro zjednodušení práce načítány z testovacího adresáře test_img, nicméně v případě potřeby by bylo možné umožnit jejich načítání pomocí komponenty upload přes webový formulář. Pro kompletní zdrojový kód viz Příloha B – Zdrojový kód PHP. Následují ukázky výsledků testovacího rozhraní pro stejný dotaz při použití globálních deskriptorů, deskriptorů SIFT a SURF. Pro porovnání byl také vytvořen optimální výsledek, který je určen dle subjektivního pohledu testujícího uživatele. Zobrazeno je 12 nejpodobnějších obrázků.
9 http://www.php.net/
18
Obrázek 5: Výsledek pro globální deskriptory
Obrázek 6: Výsledek pro SIFT 19
Obrázek 7: Výsledek pro SURF
Obrázek 8: Optimální výsledek 20
5.7 Metodika testování Pro porovnání úspěšnosti jednotlivých metod byla zvolena veličina z oboru vyhledávání informací – přesnost (precision). Tu získáme jako podíl počtu správně vrácených výsledků a celkového počtu vrácených výsledků. Matematicky vyjádřeno (S je množina správných výsledků a A množina všech výsledků): P=
∣S∩A∣ ∣A∣
Testy byly provedeny pomocí dotazu na nejbližší sousedy kNN(q). Jako hodnota k byly zvoleny tři různé hodnoty: k=5, k=20 a k=100, aby došlo k porovnání výsledků v nejbližším okolí vyhledávaného objektu s výsledky z širšího okolí. Samotné určení, zda obrázek je či není podobný, tedy zda patří do množiny správných výsledků probíhalo subjektivně, jelikož původní zařazení do kategorií není dokonalé a některé obrázky patří do více kategorií. Každý vrácený obrázek byl znovu vyhodnocen uživatelem a bylo subjektivně určeno, zda patří či nepatří do vyhledávané kategorie (např. kotva). Mezi správné výsledky nebyl započítán samotný zdrojový obrázek, který byl vždy nalezen ve vzdálenosti 0 (což je známka základní funkčnosti celého systému). Předpokládaná hypotéza byla taková, že lokální deskriptory by měly vracet lepší výsledky než globální deskriptory, jelikož jsou invariantní vůči měřítku, rotaci a iluminaci. Testování proběhlo na vybraných 21 obrázcích, které náležely do různých kategorií (viz kapitola 5.2 Kategorie tetování).
5.8 Výsledky testování Provedené testy původní hypotézu nepotvrdily. Téměř pro všechny testované obrázky byla vyšší přesnost při použití globálních deskriptorů než při použití deskriptorů SIFT či SURF (výjimkou bylo tetování obsahující znaky v hebrejštině nebo latince, nicméně ani zde nebyly výsledky signifikantně lepší). Navíc soubory s lokálními deskriptory zabírají výrazně více místa na disku a při použití jsou výpočetně mnohem náročnější než globální deskriptory. Pro kompletní výsledky všech testování viz Příloha A – Kompletní výsledky testování. Z těchto hodnot byl vytvořen průměrný počet správných odpovědí pro jednotlivé deskriptory a hodnoty k a z těch následně vypočítána průměrná přesnost. Průměrné hodnoty přesnosti vyjadřuje následující tabulka (GD znamená globální deskriptory):
Výsledek neodpovídal původní hypotéze. V následujícím textu se po analýze výsledků dospělo k těmto poznatkům o faktech, které ovlivnily úspěšnost jednotlivých metod. •
Rozdíly dat v rámci jednotlivých kategorií byly velmi výrazné. Ačkoliv jde o obrázek téhož (např. pavouka), jeho umělecké ztvárnění se často výrazně liší. Navíc dochází ke kombinaci více motivů v jednom tetování, případně je pomocí určitého motivu vyjádřeno něco zcela jiného (např. dva hadi ve tvaru srdce, atd.). Toto vše velmi ztěžuje úlohu automatického rozpoznávání. U komplexnějších či experimentálnějších tetování bylo často problematické rozlišit, co přesně tetování obsahuje i pro člověka. Pro další testování by bylo lepší vytvořit databázi totožných tetování, zachycených za různých podmínek.10 Příklady takovýchto rozdílných podmínek jsou například rozdílné rozostření, rotace, iluminace, digitální šum, aj. Testování by pak ukázalo, zda budou nalezeny tyto rozdílné verze stejného tetování.
•
V případě rozsáhlých tetování bylo při použití lokálních deskriptorů nalezeno velké množství klíčových bodů. To vedlo k tomu, že tato tetování mohla být vyhodnocena jako podobná k většímu množství obrázků, jelikož čím existuje více klíčových bodů, tím se zvětšuje pravděpodobnost, že bude některý z nich vyhodnocen jako shodný s klíčovým bodem v jiném obrázku. Pro účely hledání podobných tetování by tedy byla vhodnější spíše menší a kontrastnější tetování než od tetování přes celá záda (která navíc obsahují i mnoho různých motivů).
•
Bylo by vhodné vytvořit další třídy určující vzdálenostní funkci (než byla zde použitá ObjectFeatureSetOrdpres) a vyzkoušet, zda budou vracet lepší výsledky.
10 Tímto způsobem postupoval výzkumný tým, který se zabýval podobným tématem jako tato práce. Srov. [22]
22
6 Závěr Tato práce seznamuje čtenáře s problematikou podobnostního vyhledávání a globálních a lokálních deskriptorů. Cílem této práce bylo otestovat úspěšnost globálních a lokálních deskriptorů pro automatické rozpoznávání podobných obrázků tetování. Prvním úkolem bylo vytvořit testovací databázi alespoň 500 fotografií tetování. Tento úkol byl splněn a bylo celkem získáno 11946 fotografií. Druhým úkolem bylo vyextrahovat globální a lokální deskriptory a vytvořit vyhledávací index. Posledním úkolem bylo otestovat a porovnat úspěšnost vyhledávání na základě globálních deskriptorů s vyhledáváním na základě lokálních deskriptorů. Původní hypotéza byla, že vyhledávání za základě lokálních charakteristik bude vracet lepší výsledky. Výsledky testování tuto hypotézu nepotvrdily. Po analýze výsledků byly navrženy další kroky pro budoucí testování – vytvořit databázi totožných tetování zachycených za různých podmínek a zjistit, zda budou automaticky nalezeny. Další výzkum v této oblasti by mohl také vyzkoušet další lokální deskriptory mimo zde použitých SIFT a SURF. Dále by bylo možné zkusit navázat kontakt s Policií ČR a zjistit zda nevlastní databázi tetování, kterou by bylo možné použít pro rozšíření testovací sady.
23
Literatura [1]
GOLDBERG, Lina. Gang Tattoos: Signs of Belonging and the Transience of Signs. Linagoldberg.com [online]. 2001 [cit. 2011-05-14]. Dostupné z URL: .
[2]
Taxicab geometry. Wikipedia [online]. 2011 [cit. 2011-05-14]. Dostupné z URL: .
[3]
Chebyshev distance. Wikipedia [online]. 2011 [cit. 2011-05-14]. Dostupné z URL:
[4]
Jaccard index. Wikipedia [online]. 2011 [cit. 2011-05-14]. Dostupné z URL:
[5]
BATKO, Michal, NOVÁK, David, ZEZULA, Pavel: MESSIF: Metric similarity search implementation framework. Digital Libraries: Research and Development. Berlin, Heidelberg: Springer-Verlag, 2007, ISBN 978-3-540-77087-9, s. 1–10, Lecture Notes in Computer Science, Vol. 4877.
[6]
BATKO, Michal, NOVÁK, David, ZEZULA, Pavel: MESSIF: Metric Similarity Search Implementation Framework. In DELOS Conference 2007: Working Notes, Pisa, 2007. Pisa, Italy: Information Society Technologies, 2007. ISBN 2-912335-30-2, s. 11-23. 2007, Pisa, Italy.
[7]
BATKO, Michal, NOVÁK, David, DOHNAL, Vlastislav, SEDMIDUBSKÝ, Jan: MUFIN: A multi- feature indexing network. In SISAP ’09: Proceedings of the 2009 Second International Workshop on Similarity Search and Applications, pages 158– 159, Washington, DC, USA, 2009. IEEE Computer Society.
[8]
BATKO, Michal, FALCHI, Fabrizio, LUCCHESE, Claudio, NOVÁK, David, PEREGO, Raffaele, RABITTI, Fausto, SEDMIDUBSKÝ, Jan, ZEZULA, Pavel. Building a Web-scale Image Similarity Search System. Multimedia Tools and Applications, Springer Netherlands, 47, 3, od s. 599-629, 31 s. ISSN 1380-7501. 2010
[9]
CASTLEMAN, K. R.: Digital Image Processing, Prentice Hall, Englewood Cliffs, NJ, USA, 1996
[10] ISO/IEC 15938-3: 2002: Information technology – Multimedia content description interface – Part 3: Visual. Geneva, Switzerland: International Organization for Standardization, 2002. 175 s. – Dostupné z URL: [11] MPEG- 7 Overview. Chiariglione.org [online]. 2004 [cit. 2011-05-15]. Dostupné z URL: . [12] HSV.
Wikipedie
[online].
2011 24
[cit.
2011-05-14].
Dostupné
z URL:
[13] Haarova vlnka. Wikipedie [online]. 2011 [cit. 2011-05-14]. Dostupné z URL: [14] KHAYAM, Syed Ali. The Discrete Cosine Transform (DCT): Theory and Application. In ECE 802 – 602: Information Theory and Coding. 2003. s. 31. Dostupné z URL: . [15] Scale-invariant feature transform. Wikipedia [online]. 2011 [cit. 2011-05-14]. Dostupné z URL: [16] LINDEBERG, Tony: Scale- space. In: Encyclopedia of Computer Science and Engineering (Benjamin Wah, ed), John Wiley and Sons, Volume IV, s. 2495-2504, Hoboken, New Jersey, 2009 [cit. 2011-05-14]. Dostupné z URL: [17] LOWE, David G: Distinctive Image Features from Scale-Invariant Keypoints:. In Int. J. Comput. Vision. 2004. s. 91-110. Dostupné z URL: . ISSN 0920-5691 [18] MENG, Yu: Implementing the Scale Invariant Feature Transform (SIFT) Method. [cit. 2011-05-14]. Dostupné z URL: <www.cs.st-andrews.ac.uk/~yumeng/yumeng-SIFTreport-5.18_bpt.pdf> [19] SURF: Speeded Up Robust Features. ETH [online]. 2006 [cit. 2011-05-15]. Dostupné z URL: . [20] BAY, Herbert, ESS, Andreas, TUYTELAARS, Tinne, GOOL, Luc Van: SURF: Speeded Up Robust Features, Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, s. 346-359, 2008 [cit. 2011-05-15] Dostupné z URL: [21] Integrální obraz. Wikipedie [online]. 2011 [cit. 2011-05-14]. Dostupné z URL: [22] LEE, Jung-Eun, JAIN Anil K., JIN Rong: Scars, Marks and Tattoos (SMT): Soft Biometric for Suspect and Victim Identification. 2008 [cit. 2011-05-15]. Dostupné z URL: [23] ZEZULA, Pavel: Similarity search : the metric space approach. New York, NY : Springer, 2006. 220 s. ISBN 0387291466. [24] MIKOLAJCZYK K., TUYTELAARS T.: Local Invariant Feature Detectors : A Survey, Foundations and Trends R in Computer Graphics and Vision Vol. 3, No. 3 (2007) s. 177–280. 2008. DOI: 10.1561/0600000017
25
Příloha A – Kompletní výsledky testování Tato příloha obsahuje počet správně nalezených obrázků, které patří do stejné kategorie, pro 21 různých fotografií tetování, při použití různých hodnot k. nauticaltattoo100.jpg k=5 GD 0 SIFT 0 SURF 0
"; foreach ($info as $picture) { if ($picture[0]<34028234663852886) { echo "
$picture[0]
"; }} echo "
"; } else { echo "Error connecting."; }}} ?>
30
Příloha C – Obsah přiloženého CD Přiložené CD obsahuje tyto adresáře: •
/text Zde se nachází text bakalářské práce ve formátu ODT a ve vygenerovaném formátu PDF.
•
/images Tento adresář obsahuje kompletní sadu fotografií tetování rozdělenou hierarchicky do jednotlivých kategorií.
•
/php Zde se nachází PHP skript, jehož zdrojový kód je uveden v předchozí příloze.
•
/global Tento adresář obsahuje potřebné soubory pro extrakci globálních deskriptorů a spuštění vyhledávacího enginu pro globální deskriptory. Pro postup viz kapitola 5.3 Extrakce globálních deskriptorů a 5.5 Vyhledávací engine. Ke spuštění vyhledávacího enginu slouží skript engine.sh.
•
/local Tento adresář obsahuje potřebné soubory pro extrakci lokálních deskriptorů a spuštění vyhledávacího engine pro lokální deskriptory. Pro postup viz kapitola 5.4 Extrakce lokálních deskriptorů a 5.5 Vyhledávací engine). Ke spuštění vyhledávacího enginu pro deskriptory SIFT slouží skript ld-engine.sh, pro deskriptory SURF slouží skript ld-engine2.sh.
