PO ÍTA OVÁ PODPORA DETEKCE „ZAJÍMAVÝCH“ OBRÁZK Pavel Krsek a Ji í Matas VUT, Fakulta elektrotechnická, Centrum aplikované kybernetiky Technická 2, 166 27 Praha 6
Úvod a motivace P i zpracování a vým n dat prost ednictvím velkokapacitních datových sítí je velmi obtížné zamezit jejich zneužití, nebo alespo takové zneužití odhalit. P i sledování komunikace v takovéto síti získáváme velké množství nejr zn jších dat. Jejich manuální analýza je velmi nákladná a asto nereálná z d vod omezených kapacit. V t chto p ípadech je možné využít automatickou i poloautomatickou analýzu dat, v naší úloze digitalizovaných obrázk . V lánku je popsána úloha, která vychází z konkrétní pot eby analyzovat velké množství obrazových dat. První krok této analýzy lze popsat jako hledání „zajímavých“ obrázk , které budou postoupeny k dalšímu vyhodnocení. Zadavatelem doposud používané manuální prohledávání je z d vodu velkého po tu prohledávaných obrázk
asov
náro né a pro operátora únavné. Typicky je pot eba prohledat desítky tisíc obrázk , v nichž je jen velmi málo „zajímavých“ obrázk . etnost hledaných obrázk je obvykle 1 ku tisíci až 1 k milionu. Naším cílem je podpo it proces vyhledávání „zajímavých“ obrázk metodami po íta ového zpracování obrazu a automatické klasifikace. Zadavatel uvedl, že „zajímavé“ obrázky jsou ve v tšin p ípad textové dokumenty i ná rtky. V menší mí e pak lze za „zajímavé“ ozna it také portrétní fotografie a identifika ní snímky konkrétních osob i míst a za ízení. Obrázky, které budeme klasifikovat, jsou získány na internetu a v odkládacích prostorech internetových server . V množin nezajímavých snímk p evládají proto p edevším erotické snímky a nejr zn jší loga s malým rozlišením. Vyhledávání „zajímavých“ obrázk spo ívá v rozpoznání obrazu a jeho za azení mezi obrázky, které budou analyzovány specialistou, nebo mezi obrázky, které nemá
smysl vyhodnocovat. Takto popsaný problém je klasickým p íkladem binární klasifikace do dvou t íd. P i klasifikaci popisujeme p edm t jednotlivými ísly – p íznaky. Na základ t chto p íznak rozhoduje klasifikátor o za azení objektu do t ídy. Existuje ada algoritm pro realizaci klasifikace v etn algoritm strojového u ení klasifikátoru. P íkladem mohou být algoritmy SVM [1] i AdaBoost [2].
Podpora vyhledávání Ze zkušenosti však vyplývá, že „zajímavostí“ obrázku je mnoho druh . Operátor sám není asto jednozna n schopen posoudit úrove
„zajímavosti“. Tu je možné p es-
n ji ur it až po složité analýze, porovnání s dalšími obrázky a s využitím dalších informací. Proto není vhodné pro rozhodování využít klasický binární klasifikátor, který neumožní operativní úpravu kritérií. V našem p ípad se ukázalo jako vhodn jší modelovat vlastnost „zajímavost“ spojit a reprezentovat ji reálným íslem. Obrázky jsou nejd íve parametrizovány a ohodnoceny mírou „zajímavosti“. Na základ tohoto hodnocení jsou set íd ny a prezentovány operátorovi, který rozhodne o jejich další analýze nejen na základ jejich ohodnocení. Jak pro binární klasifikátor, tak pro p ípad našeho spojitého ohodnocení obrazových dat, by bylo možné použít metod u ení na základ p íklad . Tyto metody dosahují použitelných výsledk jen za p edpokladu, že máme dostate ný po et p íklad , které vhodn popisují zadaný problém. Toho se v p ípad obrazové informace, kdy nejsou kritéria exaktn dána, dosahuje v tšinou velkým množstvím p íklad . V p ípad malého po tu p íklad je u klasifikátor nutno vzít v úvahu možnost p eu ení. To je p ípad kdy se klasifikátor nau í odlišit jednotlivé p íklady a umožní jejich 100% klasifikaci, ale ztratí p itom schopnost zobecn ní. Zpracovávaná data, která nebyla použita k u ení, jsou p i p eu ení klasifikována chybn . Toto nebezpe í se zvyšuje nejen s nedostatkem p íklad pro u ení, ale také s rostoucím po tem p íznak . My jsme m li k dispozici jen 16 p íklad „zajímavých“ obrázk , oproti více jak 11 tisíc m obrázk ostatních. Po et p íklad a jejich nevyváženost nám neumožnila použít metody strojového u ení. Proto jsme se zam ili na rozbor p íklad a p ípravu programu pro ru ní nastavení hodnotící funkce a její ov ování v praxi.
P íznaky Na základ informací od zadavatele a rozboru p íkladu jsme implementovali dv skupiny p íznak . První skupina je ur ena k detekci textu a ná rtk . Druhá skupina má za úkol potla it erotické snímky a p itom zachovat význam fotografií osob. Indikátory textu P edpokládáme, že textový dokument se bude vyzna ovat vysokým kontrastem jasu. Základem pro výpo et p íznak textu je histogram jas , který reprezentuje relativní etnost jednotlivých jasových úrovní v obraze. P íklad histogramu pro textový obrázek (Obr. 2a) m žeme vid t na obrázku (Obr. 1). Jasový histogram je pro p ehlednost zobrazen vynesen v semilogaritmických sou adnicích.
Obr. 1. Jasový histogram Globální kontrast G k definujeme jako jasovou vzdálenost dvou nejvyšších lokálních maxim v histogramu. Tato vzdálenost je udávána relativn k po tu v obraze použitých jasových úrovní. Oborem hodnot je interval (0-1). Nejv tší možný kontrast je reprezentován íslem 1.
Analýza histogramu umož uje segmentaci (binarizaci) obrázk textových dokument na pop edí a pozadí (Obr. 2b). Po segmentaci jsou vyhodnoceny níže popsané parametry pop edí. Segmentace probíhá prahováním. Práh je nalezen adaptivn jako jas odpovídající minimu na histogramu mezi dv ma nejv tšími lokálními maximy. Za pop edí je považována ta ást obrazu, která zabírá menší plochu – náleží k ní mén bod . To nám umož uje rozpoznat nejen dokumenty psané na sv tlém pozadí, ale i dokumenty psané bíle na tmavém pozadí.
(a)
(b)
Obr. 2. Segmentace textového dokumentu. Originální obrázek (a) a segmentovaný binární obrázek (b) Nelineární funkce plochy pop edí Pp vychází ze známého p edpokladu, že plocha pokrytá znaky, tj. erní (resp. bílou), je u tišt ných dokument cca 5% plochy dokumentu. P íznak v rozsahu (0-1) indikující textový dokument je nelineární transformací plochy pop edí. Funkce nabývá hodnoty 1 v intervalu 3-10%. V intervalu 0-3% roste a v intervalu nad 10% op t klesá k nule. Kompaktnost pop edí K p je p íznakem zachycujícím složitost tvaru pop edí. Lze o ekávat, že pop edí bude v p ípad textu rozd leno do v tšího po tu oblastí s adou otvor . Proto bude kompaktnost textu velmi malá. Kompaktnost m žeme vypoíst jako pom r plochy oblasti a kvadrátu délky její hranice. Kp =
16 Pp Hp
2
,
kde P p je plocha pop edí a H p je délka hranice pop edí, která se získá jako po et bod z pop edí sousedících s pozadím ve ty okolí. Pro klasifikaci používáme nelineární
transformaci kompaktnosti, která vyjad uje nekompaktní oblast íslem 1 a vyzna uje se rychlým poklesem p i lineárním r stu kompaktnosti. Barva lidské k že
Erotické obrázky jsou po etnou množinou obrázk , které nejsou pro zadavatele zajímavé. Pro jejich odlišení byl implementován p íznak relativní plocha oblastí barvy lidské pokožky K Z . V p ípad segmentace oblastí dané barvy vycházíme z modelu barvy pokožky. Model je realizován t írozm rným histogramem reprezentujícím pravd podobnost, že daná barva je barvou pokožky. Histogram byl získán analýzou barvy v sekvenci vzorových obrázk . P íklad segmentace lidské pokožky je na obrázku 3. Rozsahem hodnot tohoto p íznaku je interval (0-1). Detekce obli ej
Pro zkvalitn ní detekce identifika ních fotografií osob byla implementována detekce tvá í v obraze. Použitý detektor je založen na metod AdaBoost [3] jejímiž p íznaky jsou rozdíly jas oblastí v obraze. Jeho výhodou je postupné vyhodnocování p íznak , které umož uje postupn vy azovat jednotlivé hypotézy o p ítomnosti obli eje na dané pozici v obraze.
(a) (b) Obr. 3. Detekce oblastí odpovídajících barvou lidské pokožce. Originální obrázek (a) a obrázek (b) s ern vyzna enými oblastmi odpovídajícími pokožce Základním p íznakem, který vychází z výsledk detektoru tvá í je po et frontálních obli ej
F N . Krom prostého po tu detekovaných tvá í jsme implementovali
také relativní plochu detekovaných obli ej
Fa . Tento p íznak vychází z plochy ob-
délník opsaných detekovaným tvá ím. Tyto obdélníky jsou výstupem detektoru ur ujícím velikost a polohu detekovaných tvá í.
(a)
(b)
Obr. 4. Detekce tvá í v obrázku. Originální snímek (a) a obrázek s obdélníky ozna ujícími detekované tvá e (b). P edevším pro odlišení obrázk s erotickými nám ty jsme použili pom r plochy odpovídající svojí barvou k ži a plochy detekovaných obli ej . Vycházíme p itom z p edpokladu, že u „zajímavých“ snímk tvá e je plocha pokožky srovnatelná s plocho obli eje, zatímco u pro nás nezajímavých obrázk výrazn p evládá plocha pokožky. Samotný pom r ploch nevykazuje vhodný pr b h funkce pro oblast našeho zájmu. Navíc by byl její výsledek jen velmi t žko porovnatelný s výsledky ostatních p íznak . Proto jsme p ipravili nelineární funkci pom ru K z / Fa jejíž rozsah hodnot je interval (0-1). Hodnota 1 p itom znamená, že je pom r ve prosp ch plochy tvá í, zatímco klesající hodnota udává zvyšující se podíl plochy pokožky.
Vyhodnocení míry „zajímavosti“ Protože nebylo možné použít metody automatické konstrukce klasifikátoru, implementovali jsme klasifikátor pouze jako jednoduchou lineární funkci p íznak jejímž výsledkem je míra „zajímavosti“ obrázku. Tuto lineární funkci lze zapsat rovnicí:
Z=
N
ai zi ,
i =1
kde z i jsou hodnoty jednotlivých p íznak a a i jsou váhové koeficienty. Klasifikátor je nastavován obsluhou na základ experiment a požadavk na výb r obrázk . Lineární klasifika ní funkce byla vybrána práv s ohledem na možnost snadného nastavení jednotlivých koeficient . Její rozhodovací schopnost je však omezená. Nakonec jsou snímky set íd ny vzestupn podle výsledné hodnoty rozhodovací funkce. Implementace umož uje nastavovat její koeficienty a provád t p et íd ní obrázk , ímž umožní uživateli pro n j optimální nastavení. P íznaky jsou vypo teny p edem a tak se zm na váhových koeficient m že projevit tém
okamžit .
Záv r Implementace algoritmu je rozd lena do dvou ástí. Hlavní program provádí výpo et parametr , který p edstavuje asov nejnáro n jší operaci. Pro set íd ní a zobrazování je použit samostatný program v Matlabu. Výpo et p íznak trvá p ibližn 0.3 sekundy pro obrázek 640 x 480 bod na po íta i s procesorem AMD 1.2 GHz. P itom více jak 80% tohoto asu zabírá detekce tvá í. Navržené a implementované ešení není ideální z hlediska klasifikace a možností automatického u ení, ale je vyhovující z hlediska uživatele. Použití algoritm strojového u ení a klasifikace bylo omezeno p edevším nedostatkem p íklad „zajímavých“ obrázk , které z velké ásti nemohly být poskytnuty akademickému pracovišti. Zadavatel systém nasadil a vyjád il s jeho funkcí spokojenost. P edpokládáme, že další vývoj by mohl jít práv sm rem využití metod strojového u ení.
Pod kování Tato práce byla podporována z prost edk 1M0567.
projektu Ministerstva školství
R íslo
Literatura [1]
Vapnik: The Nature of Statistical Learning Theory. Berlin, Springer Verlag 1995.
[2]
Y. Freund a R.E. Shapire: A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, srpen 1997.
[3]
J. Šochman a J. Matas: WaldBoost - Learning for Time Constrained Sequential Detection Face detection. Proc. of Conference on Computer Vision and Pattern Recognition (CVPR), str. 150-157, IEEE Computer Society, erven 2005.
