Image search: kde slova nestaˇ cí Petra Budíková, ÚVT a FI MU
ideálu, ve kterém má poˇ cítaˇ c rozeznat d˚ uležité vlastnosti a pokusit se k nˇ emu najít co nejpodobnˇ ejší objekty.
Lidová moudrost pohádek praví, že když chtˇ el princ požádat o ruku krásnou princeznu, neposlal jí zdvoˇ rilou žádost, ale sv˚ uj obraz. Na nˇ em princezna uvidí, jak je pohledný a udatný, a hned se do nˇ ej zamiluje. O nˇ eco pozdˇ eji i tv˚ urci reklam objevili, že obrázek ˇ rekne víc než tisíc slov1 . Opakovanˇ e tedy zjišt’ujeme, že nejen textové, ale i obrazové informace jsou cenné – jakožto i jiná multimédia, princové také zpívali pod balkónem. . .
Jedním z hlavních úkol˚ u souˇ casného výzkumu je proto právˇ e snaha o zachycení lidského vnímání podobnosti. Aˇ ckoli nikdo pˇ resnˇ e neví, jak funguje lidský mozek pˇ ri vyhodnocování podobnosti obrázk˚ u, urˇ citˇ e vnímáme jak vizuální vlastnosti (barvy, tvary, velikosti), tak obsah obrázku (co je zobrazeno, jakým dojmem to na nás p˚ usobí). Tyto vlastnosti je proto vhodné pˇ ri práci s obrazem využívat. Z hlediska automatického vyhodnocování podobnosti je pomˇ ernˇ e dobˇ re zvládnuté rozpoznávání vizuálních vlastností obrazu. Existuje množství algoritm˚ u pro extrakci barev a tvar˚ u, pomocí nichž je možné zachytit jak vlastnosti celého obrazu (získané údaje se pak oznaˇ cují jako globální vizuální deskriptory), tak vlastnosti jednotlivých ˇ cástí obrazu (lokální deskriptory). Od roku 2002 se postupnˇ e vyvíjí ISO standard MPEG-72 , který mimo jiné definuje sadu globálních vizuálních deskriptor˚ u pro popis barev, tvar˚ u, textur, umístˇ ení a rozpoznávání obliˇ cej˚ u. Souˇ cástí standardu jsou také algoritmy pro výpoˇ cet podobnosti mezi deskriptory. Nejpoužívanˇ ejšími lokálními deskriptory jsou algoritmy SIFT3 a SURF4 , které popisují vlastnosti významných bod˚ u v obraze.
Textové i multimediální informace jsou dnes všude kolem nás, vˇ etšinou v digitální podobˇ e a v obrovských množstvích. Aby bylo možné najít to, co je pro nás cenné, potˇ rebujeme nˇ ejaké nástroje, které nám umožní velké objemy dat efektivnˇ e spravovat a prohledávat. Zatímco dˇ ríve byla pozornost zamˇ eˇ rena na vyhledávání v jednoduchých atributových datech a pozdˇ eji v rozsáhlých textových kolekcích, v poslední dobˇ e se intenzivnˇ e rozvíjí také metody pro vyhledávání v multimédiích, pˇ riˇ cemž nejˇ castˇ ejší aplikací je právˇ e vyhledávání obrázk˚ u. V tomto ˇ clánku se proto zkusíme porozhlédnout po existujících systémech a smˇ erech souˇ casného vývoje.
Mnohem nároˇ cnˇ ejší pro automatické zpracování je rozpoznání obsahu – sémantiky obrazu, kterou nelze jednoduše odvodit z rozpoznaných barev a tvar˚ u. Vizuálnˇ e velmi podobná žlutá koule m˚ uže být jednou tenisový míˇ c, jindy slunce a jindy pampeliška. Lidé rozpoznávají obsah na základˇ e své zkušenosti s reálným svˇ etem, poˇ cítaˇ ci je potˇ reba tuto zkušenost zprostˇ redkovat a uˇ cit jej spojovat sémantické koncepty (slova, slovní spojení) s vizuální podobou. Aby tedy v˚ ubec bylo možné sémantiku do vyhledávání zahrnout, je tˇ reba nejprve poskytnout poˇ cítaˇ ci dostateˇ cnˇ e velkou kolekci dat s anotacemi. V pˇ rípadˇ e
1 Jak na to Základním problémem, který je vždy potˇ reba vyˇ rešit pro práci se složitými daty, je zp˚ usob reprezentace jednotlivých objekt˚ u. Ta musí odpovídat ˇ potˇ rebám uživatele. Clovˇ ek se nezajímá o každý pixel obrázku, má spíše nˇ ejakou celkovou pˇ redstavu, jak má ten správný obrázek (dokument, písniˇ cka) vypadat. Tuto pˇ redstavu m˚ uže vyjádˇ rit napˇ ríklad slovním popisem ˇ ci pomocí nˇ ejakého vzorového obrázku. V každém pˇ rípadˇ e je zadání dotazu jakýmsi nepˇ resným popisem hledaného
2
http://en.wikipedia.org/wiki/MPEG-7 Scale-invariant feature transform, http://en. wikipedia.org/wiki/Scale-invariant_feature_ transform 4 Speeded Up Robust Features, http://en.wikipedia. org/wiki/SURF 3
1
Fráze „A picture is worth a thousand words“ je pˇ ripisována Fred R. Barnardovi, který ji použil pˇ ri propagaci obrázkových reklam. Viz http://en.wikipedia. org/wiki/A_picture_is_worth_a_thousand_words
1
aˇ ckoli jsou z vyhledávání vyˇ razeny všechny obrázky, které sice mohou mít správný obsah, ale nemají ten správný popisek. Naopak také m˚ užeme získat výsledky, které se zamýšleným dotazem v˚ ubec nesouvisí. Výsledky jsou uspoˇ rádány podle bˇ ežného PageRanku, který Google používá pro urˇ cování d˚ uležitosti stránek.
specializované medicínské databáze je ještˇ e reálné vytvoˇ rit dostateˇ cnˇ e reprezentativní vzorovou množinu se systematickými popisy, v pˇ rípadˇ e obecného vyhledávání mezi obrázky na webu to však možné není. V takovém pˇ rípadˇ e tedy nelze využít automatické rozpoznávání sémantiky a nezbývá než spolehnout se na anotace, které k obrázk˚ um poskytli uživatelé, pˇ rípadnˇ e se snažit získat klíˇ cová slova z okolního textu a podobnˇ e.
Obrázek 1 ukazuje nˇ ekolik výsledk˚ u vyhledávání pomocí Google Image Search. V prvním pˇ rípadˇ e je výsledek velmi dobrý, v dalších je vidˇ et problém s r˚ uznými významy slov – pokud uživatel hledal boxera-zápasníka, bude se muset pokusit to vyjádˇ rit jiným slovem. Poslední pˇ ríklad se týká vyhledávání pojmu, který je souˇ cástí názvu populárního filmu.
2 Implementace Odhlédnˇ eme nyní na chvíli od procesu získávání dat a pˇ redpokládejme, že jsme schopni k obrázku získat jak slovní popis obsahu, tak vizuální deskriptory, což jsou typicky vektory s vysokou dimenzí. Abychom získali fungující vyhledávací systém, musíme mít ještˇ e algoritmy, které jsou schopny s touto dvojí reprezentací efektivnˇ e pracovat. Zatímco algoritmy pro vyhledávání v textech jsou dobˇ re známé a vyladˇ ené, vysokodimenzionální vektory jsou stále považovány za tˇ ežko indexovatelné (mnoho navržených indexových struktur má problémy s pˇ rílišným dˇ elením prohledávaného prostoru pˇ ri vysokém poˇ ctu dimenzí). Je tedy logické, že první komerˇ cní obrázkové vyhledavaˇ ce vizuální hledání zanedbaly a pracovaly pouze s textovou informací. V souˇ casné dobˇ e funguje vˇ etšina komerˇ cních systém˚ u pro obrázkové hledání na základˇ e text˚ u, existují však také i systémy, které využívají skuteˇ cné podobnostní hledání na základˇ e vizuálních vlastností obrázk˚ u. V dalších odstavcích si pˇ redstavíme dva systémy, které stojí na opaˇ cných pólech spektra pˇ rístup˚ u, a porovnáme jejich schopnosti. 2.1
2.2 MUFIN Image Search Vyhledávání pomocí textu m˚ uže fungovat jen v pˇ rípadˇ e, kdy máme k obrázk˚ um nˇ ejaké textové informace. Existuje ale mnoho aplikací, kdy textových informací není dostatek nebo nejsou dostateˇ cnˇ e kvalitní. V takovém pˇ rípadˇ e je jedinou možností hledání podle obsahu dat, tedy podle vizuálních deskriptor˚ u v pˇ rípadˇ e hledání obrázk˚ u. Deskriptory je možné získat z každého obrázku a jsou tedy použitelné univerzálnˇ e. Pro jejich praktické nasazení je ale potˇ reba mít efektivní implementaci indexu, který umožˇ nuje vyhledávání ve vysokodimenzionálních vektorových prostorech. Pro takové úˇ cely je v posledních letech vyvíjen na Fakultˇ e informatiky týmem prof. Zezuly systém MUFIN – Multi-Feature Indexing Network. Tento obecný vyhledávací systém umožˇ nuje podobnostní vyhledávání v témˇ eˇ r libovolných datech – jedinou podmínkou je, že pro každé dva objekty musí existovat funkce, která vyjadˇ ruje jejich vzdálenost neboli nepodobnost a tato funkce musí být metrická (tj. reflexivní, symetrická a splˇ nující trojúhelníkovou nerovnost; detaily viz [1]). Díky využití distribuované vyhledávácí sítˇ e a paralelnímu zpracování poddotaz˚ u umožˇ nuje MUFIN interaktivní vyhledávání ve velmi rozsáhlých datových kolekcích.
Google Image Search
Asi nejznámˇ ejším systémem pro vyhledávání obrázk˚ u na webu je Google Image Search5 . Do vyhledávacího políˇ cka staˇ cí napsat výraz, který nás zajímá, a Google nám nabídne nˇ ekolik obrazovek náhled˚ u, které mají daná slova ve svých metadatech, tedy v názvu, adrese ˇ ci titulku. Vzhledem k množství dat, která má Google zaindexovaná, tento zp˚ usob vyhledávání postaˇ cuje k získání dostateˇ cného poˇ ctu relevantních výsledk˚ u, 5
Pro vyhledávání v obrázcích slouží prototypová aplikace MUFIN Image Search6 [2], která umož6
http://images.google.com/
2
http://mufin.fi.muni.cz/imgsearch
Obrázek 1: Výsledky Google Image Search pro dotazy: a) Eiffelova vˇ ež, b) boxer, c) kruh. ˇuje hledání v pˇ n ribližnˇ e sto milionech obrázk˚ u 7 z webové galerie Flickr . Každý obrázek je popsán pˇ eti globálními deskriptory dle standardu MPEG-7. Dotaz se zadává pomocí vzorového obrázku, který je možno vybrat náhodným procházením kolekce, zadáním klíˇ cových slov ˇ ci vložením vlastního obrázku. Výsledkem hledání jsou potom obrázky vizuálnˇ e podobné vzoru.
pomocí jednoho kritéria a získá se množina kandidátních objekt˚ u. Tyto jsou potom pˇ reuspoˇ rádány vzhledem ke druhému kritériu podobnosti a takto seˇ razený výsledek je zobrazen uživateli. 3.1 Google: Vizuálnˇ e podobné Právˇ e takovouto funkcionalitu nabízí Google pod volbou „Podobné“ (v originálu „Similar“), která je zobrazena u vˇ etšiny obrázk˚ u, najedete-li na nˇ e myší. V pˇ rípadˇ e Google je první fáze hledání samozˇ rejmˇ e založená na textu, pomocí nˇ ehož se získá pˇ ribližnˇ e 1000 nejlepších výsledk˚ u. Z nich se extrahují lokální vizuální deskriptory a spoˇ cítá se podobnost každé dvojice obrázk˚ u. Tyto informace jsou pak využity pro seˇ razení obrázk˚ u podle vizuální podobnosti. Obrázek 3 ukazuje rozdíl mezi výsledkem bˇ ežného obrázkového hledání Google a výsledkem hledání vizuálnˇ e podobných obrázk˚ u k danému vzoru.
Obrázek 2 ukazuje dva možné výsledky hledání pomocí MUFIN Image Search. Ve výsledku je vždy vyznaˇ cen vzorový obrázek, k nˇ emuž se hledaly podobné objekty. V obou pˇ rípadech je vidˇ et, že výsledky skuteˇ cnˇ e jsou vzoru podobné, ovšem pouze v prvním pˇ rípadˇ e všechny výsledky zobrazují to, co uživatel pravdˇ epodobnˇ e hledal. V druhém pˇ rípadˇ e se potvrzuje, že ˇ cistˇ e vizuální informace pro vyhledávání ˇ casto nestaˇ cí, nebot’ není dostateˇ cná pro zachycení sémantiky obrázku.
Je však tˇ reba podotknout, že kv˚ uli rychlosti Google vizuálnˇ e podobné obrázky nepoˇ cítá ve chvíli, kdy uživatel spustí dotaz, jak bychom oˇ cekávali. Vyhodnocování podobnosti pomocí lokálních deskriptor˚ u je výpoˇ cetnˇ e nároˇ cné, a tak je k velkému množství obrázk˚ u množina podobných objekt˚ u spoˇ cítaná pˇ redem. Proto je také možno narazit na pˇ ríklady, kdy volba „Podobné“ není zobrazena – Google postupnˇ e výsledky pˇ redpoˇ cítává podle popularity daného dotazu, u málo ˇ castých výsledky zatím chybí. Tento pˇ rístup je také neflexibilní – množina podobných obrázk˚ u je fixovaná do doby, dokud Google podobnost znovu nevyhodnotí. Pro ˇ casté dotazy s mnoha relevantními objekty jsou však výsledky dobré.
3 Trendy poslední doby: kombinované vyhledávání V pˇ redchozích odstavcích jsme ukázali, že jak pˇ rístup založený na textových popisech, tak vizuální vyhledávání mají své slabé stránky, které neumožˇ nují získání optimálního výsledku. Jednoduchým východiskem je oba pˇ rístupy zkombinovat a s využitím dvou r˚ uzných pohled˚ u na podobnost dosáhnout lepšího výsledku, který bude také odpovídat lidskému vnímání podobnosti. Touto cestou se nyní také ubírají vyhledávácí systémy obou pˇ redstavených typ˚ u. Opˇ et však narážíme na otázku efektivní implementace – ˇ cím více informací je pro vyhledávání využíváno, tím více dat je tˇ reba spravovat a procházet. Proto se ˇ casto používá dvoufázové vyhodnocování dotazu, kdy se v první fázi prohledá celá databáze 7
3.2 MUFIN ranking Také vyhledávaˇ c MUFIN jde s dobou a rozšiˇ ruje své obzory o další kritéria pro vyhodnocování
http://www.flickr.com/
3
Obrázek 2: MUFIN Image Search
Obrázek 3: a) Google Image Search, b) Google – „Podobné“
4 Závˇ er
podobnosti. V první ˇ radˇ e se samozˇ rejmˇ e nabízí textová informace, lze však pracovat i s dalšími metadaty, která mohou být k obrázku k dispozici – doba poˇ rízení, GPS souˇ radnice, popularita objektu mezi uživateli apod.
Dva pˇ redstavené vyhledávací systémy samozˇ rejmˇ e nejsou jediné, které lze pro hledání obrázk˚ u použít. Mohli bychom mluvit o mnoha dalších9 , které se nˇ ejakým zp˚ usobem snaží pracovat s obrázky a využívat text, vizuální deskriptory ˇ ci obojí k vyhledávání podobných objekt˚ u. R˚ uzné pˇ rístupy jsou vhodné pro r˚ uzné aplikace, ideální systém pro všechny situace zatím neexistuje a pravdˇ epodobnˇ e existovat ani nem˚ uže. Samotný pojem podobnosti, se kterým stále pracujeme, je tˇ ežko definovatelný, jeho vnímání je individuální a m˚ uže se lišit v r˚ uzných situacích. M˚ užeme se proto jen snažit o co nejlepší pˇ riblížení a co nejefektivnˇ ejší vyhodnocování.
Podobnˇ e jako Google, také MUFIN umí pracovat s více kritérii podobnosti v dvoufázovém vyhledávacím modelu. V prvním kole vyhodnocování se získá N vizuálnˇ e nejpodobnˇ ejších objekt˚ u a s touto množinou se potom dále pracuje. MUFIN ranking demo8 umožˇ nuje vyzkoušet si nˇ ekolik zp˚ usob˚ u pˇ reuspoˇ rádávání, které jsou zamˇ eˇ rené zejména na co nejlepší využití textových metadat [3]. Kromˇ e uspoˇ rádání výsledné množiny dle klíˇ cových slov hledaného objektu si uživatel sám m˚ uže vybrat, která slova jsou pro nˇ ej relevantní. Další možností je automatické získání nejd˚ uležitˇ ejších slov na základˇ e frekvence jejich výskytu v popisech daných N vizuálnˇ e nejpodobnˇ ejších objekt˚ u. Obrázek 4 ukazuje, jak m˚ uže zohlednˇ ení klíˇ cových slov vylepšit výsledek podobnostního dotazu – z výsledku jsou odfiltrovány objekty, které jsou vizuálnˇ e podobné, ale nezobrazují hledaný pˇ redmˇ et.
8
Vyhledávaˇ ce Google a MUFIN ukazují dva zcela odlišné pˇ rístupy. Zatímco komerˇ cní Google spoléhá pˇ redevším na obrovské množství dat10 , ve kterých se najde dostatek obrázk˚ u s pˇ ríslušným popisem, MUFIN se snaží vytvᡠret obecnˇ ejší ˇ rešení, použitelné pro r˚ uzné situace a r˚ uzné typy 9 Neúplný pˇ rehled systém˚ u, které nˇ ejakým zp˚ usobem implementují vyhledávání na základˇ e vizuální podobnosti, lze najít na http://en.wikipedia.org/wiki/List_of_ CBIR_engines 10 Dle tiskové zprávy z 7.2.2005 indexoval Google v té dobˇ e pˇ res miliardu obrázk˚ u; http://www.google.com/ press/annc/onebox.html
http://mufin.fi.muni.cz/ranking
4
Obrázek 4: a) MUFIN Image Search, b) totéž s dodateˇ cným pˇ reuspoˇ rádáním výsledku podle klíˇ cových slov dat. V obou pˇ rípadech stejnˇ e jako u dalších systém˚ u se souˇ casný vývoj zamˇ eˇ ruje pˇ redevším na efektivní implementaci složitˇ ejších vyhodnocovacích kritérií. V pˇ rípadˇ e MUFINu se chystáme v blízké dobˇ e provést experimentální vyhodnocení a porovnání r˚ uzných pˇ rístup˚ u ke kombinování textové a vizuální informace. Dalším z úkol˚ u pro podobnostní vyhledávání je pak umožnit flexibilní vyhledávání, které si uživatel m˚ uže pˇ rizp˚ usobit svým potˇ rebám.
Literatura [1] P. Zezula, G. Amato, V. Dohnal, M. Batko. Similarity Search: The Metric Space Approach, volume 32 of Advances in Database Systems. Springer-Verlag, 2006. [2] D. Novak, M. Batko, P. Zezula. Web-scale system for image similarity search: When the dreams are coming true. In Proc. of CBMI ’08, page 8. IEEE, 2008. [3] P. Budikova, M. Batko, P. Zezula. Similarity Query Postprocessing by Ranking. In Proc. of AMR ’10. Linz, 2010.
5
