Rozpozn´av´an´ı obliˇcej˚ u v digit´aln´ım svˇetˇe.
9. u ´nora 2013
1
´ Uvod
Vizu´aln´ı rozpozn´av´ an´ı obliˇcej˚ u je pro ˇclovˇeka snadn´a u ´loha. Jedn´a se o schopnost, kterou si po narozen´ı osvojuje jako jednu z prvn´ıch a kter´ a je z´ akladem soci´aln´ı interakce mezi lidmi. Pro poˇc´ıtaˇc jde vˇsak o netrivi´ aln´ı probl´em. Pˇritom jeho zvl´adnut´ı je d˚ uleˇzit´e v mnoha odvˇetv´ıch. Pˇredevˇs´ım souˇcasn´ y velk´ y rozmach v oblasti vizu´aln´ıch m´edi´ı pˇr´ımo vyb´ız´ı k automatick´emu zpracov´ an´ı. Facebook nebo Picasa obsahuj´ı statis´ıce fotografi´ı s v´ yskytem obliˇcej˚ u a pr´avˇe jejich automatick´e rozpozn´av´an´ı je z´akladem mnoha rozˇs´ıˇren´ ych funkc´ı. Prvn´ı pokusy poloautomatick´eho rozpozn´av´an´ı obliˇcej˚ u poch´azej´ı jiˇz z roku 1966. Klasifikace obliˇcej˚ u byla prov´adˇena pomoc´ı specifick´ ych bod˚ u (kraje oˇc´ı, kraje pusy, ˇspiˇcka nosu atd.), kter´e byli na fotografi´ıch lokalizov´any ruˇcnˇe. Porovn´ avan´e parametry potom tvoˇrily normalizovan´e geometrick´e vzd´alenosti a pomˇery mezi tˇemito body. Modern´ı algoritmy rozpozn´ av´ an´ı obliˇcej˚ u tento postup tak´e ˇc´asteˇcnˇe vyuˇz´ıvaj´ı. B´ yvaj´ı rozdˇeleny na 2 f´aze. V prvn´ı f´azi jde o to pokusit se lokalizovat hlavu jedince. K tomuto se ˇcasto vyuˇz´ıv´a lokalizace oˇc´ı, pusy a nosu spolu s faktem, ˇze tyto body b´ yvaj´ı geometricky sv´az´any. Takto zachycen´a oblast pˇredpokl´ adan´e ho v´ yskytu obliˇceje se n´ aslednˇe spr´ avnˇe otoˇc´ı a pˇreˇsk´aluje do nˇejak´e standardn´ı velikosti (v nˇekter´ ych algoritmech k ot´aˇcen´ı nedoch´ az´ı). V´ ysledek potom vstupuje do druh´e f´aze, ve kter´e se urˇcuje, jestli se skuteˇcnˇe jedn´a o lidsk´ y obliˇcej a pˇr´ıpadˇe o jakou osobu konkr´etnˇe. Ve vˇsech algoritmech pouˇz´ıvan´ ych pro hled´an´ı obliˇcej˚ u hraje matematika v´ yznaˇcnou u ´lohu. Detailn´ı popis nej´ uspˇeˇsnˇejˇs´ıch souˇcasn´ ych algoritm˚ u by byl nad r´amec tohoto textu. Z´akladn´ı princip, kter´ y v nich b´ yv´a obsaˇzen, vˇsak vysvˇetl´ıme pomˇernˇe snadno.
2
Matematick´ y popis
Fotografie je v digit´ aln´ı podobˇe reprezentov´ana pomoc´ı ˇctvercov´e s´ıtˇe n × m (n - ˇs´ıˇrka, m - v´ yˇska) bod˚ u naz´ yvan´ ych pixely. Kaˇzd´ y pixel m´ a nˇejakou barvu a jeho pozici je moˇzn´e identifikovat pomoc´ı souˇradnic. Barva pixelu b´ yv´ a obvykle vyj´ adˇrena ve formˇe trojice ˇc´ısel (r, g, b), kter´e pˇredstavuj´ı zastoupen´ı tˇr´ı z´akladn´ıch barev, ˇcerven´e (r), zelen´e (g) a modr´e (b). Kaˇzd´e z tˇechto ˇc´ısel pˇri tom znamen´a relativn´ı velikost intenzity dan´e barvy v rozsahu 0 aˇz 1, kde 0 znamen´a, ˇze dan´a barva nen´ı v˚ ubec pˇr´ıtomna a 1 ˇ znamen´a, ˇze dan´a barva je pˇr´ıtomna v pln´e intenzitˇe. Cistou ˇcervenou tud´ıˇz reprezentuje trojice (1, 0, 0), ˇcistou modrou (0, 0, 1), ˇcern´ a je (0, 0, 0) a b´ıl´ a potom (1, 1, 1). Pro u ´ˇcely detekce obliˇcej˚ u je v´ yhodn´e pracovat pouze s odst´ıny ˇsedi. Kaˇzd´emu pixelu je v takov´em pˇr´ıpadˇe pˇriˇrazeno pouze jedno ˇc´ıslo od 0 do 1 vyjadˇruj´ıc´ı relativn´ı intenzitu I dan´eho bodu. Bod s intenzitou 0 je tedy ˇcern´ y a bod s intenzitou 1 je b´ıl´ y. Pˇrevod z RGB do odst´ın˚ u ˇsedi m˚ uˇze b´ yt r˚ uzn´ y, ale nejˇcastˇeji se pouˇz´ıv´a vztah I = 0,21 · r + 0,72 · g + 0,07 · b, kter´ y dostateˇcnˇe reflektuje vn´ımavost lidsk´eho oka k r˚ uzn´ ym barv´am. 1
Obr´azek o velikosti n × m v odst´ınech ˇsedi si tedy m˚ uˇzeme pˇredstavit jako tabulku ˇc´ısel od 0 do 1, kter´a m´a m ˇr´adk˚ u a n sloupc˚ u. Takov´emu u ´tvaru ˇr´ık´ame v matematice matice a znaˇc´ıme je velk´ ymi p´ısmeny. Rozmˇery uv´ ad´ıme pomoc´ı poˇctu ˇra´dk˚ u × poˇctu sloupc˚ u. Pˇr´ıkladem je tˇreba n´asleduj´ıc´ı matice A o rozmˇerech 2 × 3: 0 0,1 1 A= . 1 0 0 Pozici v matici urˇcujeme pomoc´ı dvou ˇc´ısel, kde prvn´ı z nich znamen´a ˇc´ıslo ˇr´adku a druh´e ˇc´ıslo sloupce. Tedy prvek matice A na pozici 1, 3 je ˇc´ıslo 1 a prvek na pozici 1, 2 je ˇc´ıslo 0,1. Prvek matice A na pozici i, j obvykle znaˇc´ıme symbolem Ai,j . Pro pˇredchoz´ı matici tud´ıˇz napˇr´ıklad m´ame A1,1 = 0, A1,2 = 0,1, A2,1 = 1. Obr´azek o rozmˇerech n × m pro n´ as od nynˇejˇska bude pˇredstavovat matici o rozmˇerech m × n. Na obr´azku 1 je uveden pˇr´ıklad takov´e reprezentace. 1
2
3
4
5
1
1 1/2 1/2 1/2 1 1/2 0 1 0 1/2 . A= 1/2 1 0 1 1/2 1 1/2 1/2 1/2 1
2 3 4
Obr´azek 1: Reprezentace obr´ azku pomoc´ı matice ˇc´ısel od 0 do 1 o rozmˇerech 4 × 5.
3
Lokalizace totoˇ zn´ eho obliˇ ceje
Abychom vysvˇetlili z´ akladn´ı princip metody, uvaˇzujme nejprve n´asleduj´ıc´ı pˇr´ıklad. Pˇredstavme-si, ˇze m´ ame fotku reprezentovanou matic´ı I, na kter´e je obliˇcej. Obd´eln´ıkov´a ˇc´ast obsahuj´ıc´ı tento obliˇcej pˇredstavuje novou matici F . Pˇr´ıklad je uveden na obr´ azku 2. Chceme-li nyn´ı na fotografii lokalizovat tento obliˇcej, znamen´a to naj´ıt v matici I ˇc´ast F . Oznaˇcme si mF poˇcet ˇr´adk˚ u matice F , nF poˇcet sloupc˚ u matice F a mI poˇcet ˇr´adk˚ u I a nI poˇcet sloupc˚ u I. Naˇs´ım c´ılem je tedy naj´ıt obd´eln´ıkovou ˇc´ ast matice I o rozmˇerech mF × nF , kter´a je stejn´a jako F . To znamen´ a naj´ıt indexy i a j takov´e, ˇze F1,1 = Ii+1,j+1 , F1,2 = Ii+1,j+2 a obecnˇe Fk,l = Ii+k,j+l pro vˇsechna k od 1 do mF a pro vˇsechna l od 1 do nF . Jin´ ymi slovy, chceme, aby prvek matice F na pozici 1, 1 byl prvkem matice I na pozici i + 1, j + 1 a podobnˇe pro vˇsechny ostatn´ı prvky F . Napˇr´ıklad pro matice 1 1/2 1/2 1/2 1 1/2 0 1 0 1/2 1 0 a F = , I= 1/2 1 0 1 1/2 0 1 1 1/2 1/2 1/2 1 by zˇrejmˇe platilo i = 1 a j = 2, protoˇze F1,1 = 1 = I2,3 = I1+1,2+1 atd. K tomu abychom dok´ azali naj´ıt pozici matice F v matici I, m˚ uˇzeme pouˇz´ıt n´asleduj´ıc´ı postup: 1. Budeme proch´ azet vˇsechny dvojice index˚ u i, j, pro i od 0 do mI − mF a j od 0 do nI − nF .
2
Obr´azek 2: Fotografie odpov´ıdaj´ıc´ı matici 581 × 493 s v´ ysekem pˇredstavuj´ıc´ım obliˇcej. 2. Pro kaˇzdou dvojici vybereme z matice I v´ yˇrez o velikosti mF × nF , kter´ y oznaˇc´ıme G(i, j). 3. Tento v´ yˇrez G(i, j) porovn´ ame s matic´ı F . 4. Pokud budou stejn´e, jsme hotovi, pokud budou r˚ uzn´e, pokraˇcujeme s dalˇs´ımi hodnotami i a j. Nejd˚ uleˇzitejˇs´ım ˇc´ ast´ı algoritmu je bod 3. Jedn´a se o porovn´an´ı dvou matic s c´ılem kvantifikovat odliˇsnosti. Vˇenujme se tedy tomuto bodu podrobnˇeji.
3.1
Eukleidovsk´ a vzd´ alenost
Pokusme se nyn´ı navrhnout nˇejakou metodu, kterou bude moˇzn´e porovn´avat dvˇe matice F a G stejn´e velikosti. Nejjednoduˇsˇs´ı porovn´ an´ı by bylo pod´ıvat se, zda maj´ı obˇe matice shodn´e prvky. Tj. ovˇeˇrit, zda rovnost Fk,l = Gk,l plat´ı pro vˇsechna k = 1, . . . , mF (matematick´ y z´apis tvrzen´ı – k od 1 do mF ) a l = 1, . . . , nF . Tento zp˚ usob vˇsak nen´ı v´ yhodn´ y s ohledem na pozdˇejˇs´ı rozˇsiˇrov´an´ı algoritmu na u ´lohu lokace nezn´ am´eho obliˇceje. V takov´em pˇr´ıpadˇe totiˇz absoulutn´ı shoda vˇsech prvk˚ u nikdy nenastane. Matice F a G si budou pouze do jist´e m´ıry podobn´e. Pojd’me tedy obecnˇe kvantifikovat m´ıru odliˇsnosti matic F a G. Jako v´ yhodn´ y ukazatel se ˇcasto pouˇz´ıv´ a vzd´alenost“. Pojem vzd´ alenosti zn´ ame pˇredevˇs´ım z fyziky a analytick´e geometrie. Vzd´alenost bodu A o ” souˇradnic´ıch A = (xA , yA ) od bodu B o souˇradnic´ıch B = (xB , yB ) se tam poˇc´ıt´a jako d´elka spojnice tˇechto dvou bod˚ u, kter´a je d´ ana vztahem p d = (xA − xB )2 − (yA − yB )2 . Je to tedy odmocnina ze souˇctu kvadr´ at˚ u rozd´ılu souˇradnic obou bod˚ u. Nen´ı nic jednoduˇsˇs´ıho, neˇz pˇredstavit si jednotliv´e prvky matice jako takov´eto souˇradnice a vytvoˇrit pro vzd´alenost dvou matic F a G analogick´ y vztah: v u mF nF uX X (Fk,l − Gk,l )2 , (1) d(F, G) = t k=1 l=1
3
P F kde symbol nl=1 oznaˇcuje souˇcet, ve ker´em za l postupnˇe d´av´ame ˇc´ısla od 1 do nF . Jednoduch´ ym pˇr´ıkladem P4 t´eto symboliky budiˇz: i=1 ai = a1 + a2 + a3 + a4 . Vid´ıme, ˇze d(F, G) je vˇzdy kladn´e ˇc´ıslo nebo 0. Pˇritom 0 je pouze v pˇr´ıpadˇe, ˇze jsou matice F a G totoˇzn´e. Pokud se ale liˇs´ı (byt’ jen na jedin´e pozici), dostaneme d(F, G) > 0. Tako definovan´e vzd´alenosti se ˇr´ık´a Eukleidovsk´a. Existuj´ı i dalˇs´ı moˇzn´e v´ ypoˇcty vzd´alenosti, kter´e maj´ı podobn´e vlastnosti. Pˇr´ıkladem je napˇr. maximov´a, Mahalanobisova apod. Pro naˇse potˇreby je ovˇsem Eukleidovsk´a vzd´alenost dostaˇcuj´ıc´ı.
3.2
Matice vzd´ alenost´ı
Nyn´ı jiˇz um´ıme kvantifikovat vzd´ alenost dvou matic stejn´e velikosti. Body 1 aˇz 3 v algoritmu hledaj´ıc´ım obliˇcej F na fotografii I m˚ uˇzeme kompaktnˇe vyj´adˇrit pomoc´ı jedn´e matice D o rozmˇerech (mI − mF + 1) × (nI − nF + 1) shrnuj´ıc´ı v´ ypoˇcet vzd´ alenost´ı pro vˇsechny moˇzn´e v´ yˇrezy. Pro i mezi 0 a mI − mF a j mezi 0 a nI − nF poloˇzme Di+1,j+1 = d(F, G(i, j)). Rozep´ıˇsme-li tuto formuli pouze pomoc´ı p˚ uvodn´ıch matic I a F dost´av´ame v u mF nF uX X Di+1,j+1 = t (Fk,l − Ii+k,j+l )2 .
(2)
k=1 l=1
Pozici obliˇceje na fotografii I pak urˇc´ıme tak, ˇze najdeme 0 v matici D. Nach´az´ı-li se 0 na pozici i, j, znamen´a to, ˇze lev´ y horn´ı roh obliˇceje F urˇcen´ y prvkem F1,1 je totoˇzn´ y s prvkem Ii+1,j+1 um´ıstˇen´ ym v matici I na pozici i + 1, j + 1. Matice D na naˇsem pˇr´ıkladu je zobrazena na obr´azku 3.
ˇ ım v´ıce je barva modˇrejˇs´ı a tmavˇs´ı, t´ım Obr´azek 3: Vizualizace matice eukleidovsk´ ych vzd´alenost´ı D. C´ je vzd´alenost v´ yˇrezu z matice I a obliˇceje F menˇs´ı. Nulov´a vzd´alenost nast´av´a pro i = 159 a j = 133 (D160,134 = 0). Tato ˇc´ısla opravdu odpov´ıdaj´ı volbˇe lev´eho horn´ıho okraje pˇri v´ yˇrezu F z I.
4
4
Lokalizace odliˇ sn´ eho obliˇ ceje
Tento pˇr´ıklad pˇredstavuje pˇr´ım´e zobecnˇen´ı pˇredchoz´ıho. Naˇs´ım c´ılem bude lokalizovat obliˇcej na fotografii I, ovˇsem jako vzorov´ y referenˇcn´ı obliˇcej n´ am nebude slouˇzit v´ yˇrez z I n´ ybrˇz nˇejak´ y jin´ y obliˇcej F . Pˇr´ıklad takov´e situace je zn´ azornˇen na obr´ azku 4.
Obr´ azek 4: Fotografie I (594 × 805) a obliˇcej F , kter´ y netvoˇr´ı v´ yˇrez z I. Nejprve zkusme pouˇz´ıt pˇredchoz´ı algoritmus. Podle vztahu (2) vypoˇcteme matici vzd´alenost´ı D. Protoˇze se v matici I matice F pˇr´ımo nevyskytuje, okamˇzitˇe v´ıme, ˇze 0 se v matici D vyskytovat nem˚ uˇze. Ot´ azka tedy zn´ı jak lokalizovat obliˇcej v I. Nejpˇrirozenˇejˇs´ı je zˇrejmˇe naj´ıt pozici, kde je vzd´alenost F od v´ yˇrezu v I minim´aln´ı Na obr´ azku 5 je vyobrazena matice D. Nejmenˇs´ı vzd´alenost, kter´ a se vyskytuje v matici D je 6,29. Nast´av´a ovˇsem pro hodnoty index˚ ui=5 a j = 151. Pˇritom, jak je patrno z obr´ azku, obliˇcej vyobrazen´e osoby se nach´az´ı vpravo nahoˇre od stˇredu obr´azku coˇz odpov´ıd´ a i ≈ 160 a j ≈ 360. S t´ımto probl´emem se m˚ uˇzeme vyrovnat nˇekolika zp˚ usoby. Abychom si je mohli uvˇedomit, pojd’me se na problematiku vzd´ alenosti pod´ıvat podrobnˇeji. Pˇredstavme-si, ˇze m´ame nˇejak´ y obliˇcej F a potom u ´plnˇe stejn´ y obliˇcej F1 , kter´ y byl ale vyfocen pˇri troˇsku vˇetˇs´ım osvˇetlen´ı. V takov´em pˇr´ıpadˇe lze pˇredpokl´ adat, ˇze pˇribliˇznˇe plat´ı F1 = F + , kde je nˇejak´e mal´e kladn´e ˇc´ıslo (zmˇena intenzity). Pojd’mˇe se pod´ıvat jak´a v takov´em pˇr´ıpadˇe bude vzd´alenost matic d(F1 , F ). v v u mF nF u mF nF p uX X uX X √ 2 t d(F, F1 ) = d(F, F + ) = (Fk,l − Fk,l + ) = t 2 = mF · nF 2 = mF nF . k=1 l=1
k=1 l=1
V pˇr´ıpadˇe, ˇze je matice F pˇribliˇznˇe ˇctvercov´ a (mF = nF ) dostaneme mF . Pro hodnoty = 0,1 a mF = 100 tak dost´av´ame d(F, F + 0,1) = 10, coˇz je desetina maxim´aln´ı moˇzn´e odchylky 2 matic (matice 0 a matice 1), kter´a je pro matice 100 × 100 rovna 100. Podobnˇe jako na zvˇetˇsen´ı intenzity o konstantu, je naˇse vzd´alenost citliv´a na zmˇenu intenzity vyn´asoben´ım. Je zˇrejm´e, ˇze je tˇreba modifikovat n´ aˇs algoritmus, abychom se takov´ ychto odchylek vyvarovali. Uk´ aˇzeme si zde 2 moˇznosti modifikace v´ ypoˇctu vzd´ alenosti.
5
Obr´azek 5: Vizualizace matice eukleidovsk´ ych vzd´alenost´ı D. Vid´ıme, ˇze zde nen´ı ˇz´adn´e zˇreteln´e minimum. Skuteˇcn´e minimum je vyznaˇceno ˇcerven´ ym kˇr´ıˇzkem a odpov´ıdaj´ıc´ı v´ ysek, pro kter´e nast´av´a, je vyznaˇcen na fotografii ˇcerven´ ym r´ ameˇckem.
4.1
Eukleidovsk´ a vzd´ alenost stˇ redovan´ ych matic
Prvn´ı moˇznost´ı je nepoˇc´ıtat pˇr´ımo vzd´ alenost d(F, G) ale nejprve matice F a G nˇejak´ ym zp˚ usobem pˇribl´ıˇz´ıt (se zachov´an´ım morfologick´ ych odliˇsnost´ı). Velmi rozumn´e pˇribl´eˇzen´ı pˇredstavuje odeˇcten´ı stˇredn´ı hodnoty. Stˇredn´ı hodnotu matice F pro naˇse u ´ˇcely definujeme jako pr˚ umˇernou hodnotu vˇsech ˇc´ısel v matici se vyskytuj´ıc´ıch. Je to tedy jedno ˇc´ıslo, kter´e budeme znaˇcit F¯ a poˇc´ıtat vztahem F¯ =
mF X nF X 1 Fk,l . mF · nF
(3)
k=1 l=1
¯ G) matic F a G budeme nyn´ı br´at vzd´alenost matic, od kter´ Jako novou vzd´alenost d(F, ych jsme odeˇcetli jejich stˇredn´ı hodnoty, tj. ¯ G) = d(F − F¯ , G − G). ¯ d(F, ¯ F + ) = d(F, F + − F¯ − ) = d(F, F ) = 0! Tato nov´a vzd´ Protoˇze (F + ) = F¯ + dost´ av´ ame d(F, alenost po vystˇredov´an´ı nen´ı citliv´ a v˚ uˇci zmˇenˇe intenzity pˇriˇcten´ım konstanty. Bez dalˇs´ıho dokazov´an´ı poznamenejme, ˇze st´ale z˚ ust´ av´ a citliv´ a na zmˇenu intenzity vyn´asoben´ım. Aplikace t´eto modifikace na n´aˇs pˇr´ıklad je zn´azornˇena na obr´ azku 6.
4.2
Korelaˇ cn´ı koeficient
Jinou moˇznost´ı jak urˇcovat bl´ızkost matic F a G stejn´ ych rozmˇer˚ u mF × nF je poˇc´ıtat jejich korelaˇcn´ı koeficient r(F, G) definovan´ y vztahem PmF PnF ¯ − F¯ )(Gk,l − G) k=1 l=1 (Fk,lq r(F, G) = qP . (4) mF PnF ¯ )2 PmF PnF (Gk,l − G) ¯ 2 (F − F k,l k=1 l=1 k=1 l=1 Vˇsimnˇeme si, ˇze ve jmenovateli se nach´ azej´ı Eukleidovsk´e vzd´alenosti matic F a G od sv´ ych pr˚ umˇer˚ u F¯ ¯ a G. Korelaˇcn´ı koeficient je d˚ uleˇzit´ a veliˇcina v teorii pravdˇepodobnosti a statistice. Interpretace hlubˇs´ıho 6
¯ Ani v tomto pˇr´ıpadˇe nen´ı Obr´azek 6: Vizualizace matice vystˇredovan´ ych eukleidovsk´ ych vzd´alenost´ı D. ˇz´adn´e zˇreteln´e minimum. Skuteˇcn´e minimum je vyznaˇceno ˇcerven´ ym kˇr´ıˇzkem a odpov´ıdaj´ıc´ı v´ ysek, pro kter´e nast´av´a, je vyznaˇcen na fotografii ˇcerven´ ym r´ameˇckem. v´ yznamu je vˇsak nad r´ amec tohoto textu. Pˇripomeˇ nme pouze, ˇze vˇzdy plat´ı −1 ≤ r(F, G) ≤ 1. Z definice r(F, G) d´ale plyne, ˇze korelaˇcn´ı koeficient nen´ı ovlivˇ nov´an zmˇenou intenzity vstupn´ıch matic po pˇriˇcten´ı konstanty, ani po vyn´ asoben´ı kladn´ ym ˇc´ıslem. Pro korelaˇcn´ı koeficient plat´ı, ˇze r(F, G) = 1 pr´avˇe tehdy, kdyˇz je F v line´arn´ım vztahu ke G, tj. existuje kladn´e ˇc´ıslo a a ˇc´ıslo b tak, ˇze F = aG + b (specielnˇe tak´e v pˇr´ıpadˇe, ˇze F = G). Shoda mezi F a G je tedy t´ım vˇetˇs´ı, ˇc´ım vˇetˇs´ı je korelaˇcn´ı koeficient. V naˇsem pˇr´ıpadˇe to znamen´ a, ˇze m´ısto matice vzd´alenost´ı D zaveden´e vztahem (2) budeme pouˇz´ıvat matici korelac´ı R urˇcenou vztahem R(i + 1, j + 1) = r(F, G(i, j)) a budeme hledat jej´ı maximum. Lev´ y horn´ı roh v´ yseku, ve kter´em se nach´az´ı hledan´ y obliˇcej, tedy bude odpov´ıdat nejvˇ etˇ s´ı hodnotˇe v matici R. V´ ysledn´ a matice R pro n´ aˇs pˇr´ıklad je na obr´azku 7.
4.3
Porovn´ an´ı r˚ uzn´ ych pattern˚ u
Mohlo by se zd´at, ˇze nejlepˇs´ı v´ ysledky, dost´ av´ ame pouˇzit´ım korelaˇcn´ıho koeficientu, zat´ımco pomoc´ı Eukleidovsk´e vzd´alenosti (ani stˇredovan´e) nejsme schopni obliˇcej lokalizovat. v tomto jednoduch´em pˇr´ıpadu tomu tak skuteˇcnˇe je, ovˇsem v pokroˇcilejˇs´ıch algoritmech hraje Eukleidovsk´a vzd´alenost opˇet v´ yznamnou roli. Pro srovn´an´ı uved’me tabulku hodnot, kter´e dostaneme pouˇzit´ım tˇr´ı v´ yˇse uveden´ ych metod pˇri porovn´ an´ı pouˇz´ıvan´eho obliˇceje s r˚ uzn´ ymi obr´ azky.
d(F, G) ¯ G) d(F, r(F, G)
5,43 5.31 0.63
14.00 8.09 -0.12
50.70 7.86 -0.01
13.58 12.87 -0.09
16.39 15.21 0.27 7
11.13 7.87 0.70
26.88 7.67 0.00
7.21 6.36 0.73
33.36 7.63 0.40
Obr´azek 7: Vizualizace matice korelaˇcn´ıch koeficient˚ u R (vlevo). V tomto pˇr´ıpadˇe je zˇreteln´e maximum s hodnotou 0,733. Toto maximum je v matici R vyznaˇceno ˇcern´ ym kˇr´ıˇzkem a odpov´ıdaj´ıc´ı v´ ysek, pro kter´e nast´av´a, je vyznaˇcen na fotografii vpravo ˇcerven´ ym r´ameˇckem.
5
Lokalizace pr˚ umˇ ern´ e tv´ aˇ re
ˇ Casto je naˇs´ım c´ılem nal´ezt pouze obliˇcej ˇclovˇeka a teprve potom se pˇr´ıpadnˇe zab´ yvat t´ım, o koho se jedn´a. Pˇri takov´em zad´ an´ı nen´ı vhodn´e volit jako referenˇcn´ı obliˇcej F nˇejak´ y konkr´etn´ı obliˇcej, ale je vhodn´e zkonstruovat matici odpov´ıd´ a pr˚ umˇern´emu“ obliˇceji. A bychom toho doc´ılili vezmeme nˇekolik ” stejnˇe velk´ ych obliˇcej˚ u zhruba stejnˇe um´ıstˇen´ ych a p˚ umˇern´ y obliˇcej spoˇcteme jako zpr˚ umˇerov´an´ı tˇechto obliˇcej˚ u bod po bodu. Pokud m´ ame n obliˇcej˚ u reprezentovan´ ych maticemi F (1), F (2), . . . , F (n), definujeme pr˚ umˇern´ y obliˇcej jako F¯i,j = Fi,j (1) + Fi,j (2) +· · · + Fi,j (n). Z obliˇcej˚ u v pˇredchoz´ı tabulce tak dostaneme pr˚ umˇern´ y obliˇcej uveden´ y na obr´azku 8. Tento obliˇcej je nyn´ı v´ yhodn´e vyuˇz´ıt k lokalizaci obliˇceje na fotografii.
Obr´ azek 8: Pr˚ umˇern´ y obliˇcej sestaven´ y z obliˇcej˚ u v pˇredchoz´ı tabulce. Pouˇzijeme-li v naˇsem pˇr´ıkladu k v´ ypoˇctu Eukleidovsk´e stˇredovan´e vzd´alenosti pr˚ umˇern´ y obliˇcej dostaneme daleko zaj´ımavˇejˇs´ı v´ ysledky, neˇz v pˇr´ıpadˇe konkr´etn´ıho obliˇceje (byt’ patˇr´ıc´ıho stejn´e osobˇe). To sam´e plat´ı pˇri v´ ypoˇctu korelace. Nejprve porovn´ ame pr˚ umˇern´ y obliˇcej se stejn´ ymi vzorky jako v minul´e tabulce.
8
d(F¯ , G) ¯ F¯ , G) d( r(F¯ , G)
11.33 6.73 0.61
9.65 8.53 -0.11
44.05 8.33 -0.04
15.24 10.02 0.16
10.91 10.89 0.68
4.68 4.67 0.88
20.28 8.13 0.04
10.83 5.48 0.85
26.55 6.37 0.59
¯ F¯ , G) a koZ t´eto tabulky je zˇretelnˇe patrno, ˇze v pˇr´ıpadˇe stˇredovan´e Eukleidovsk´e vzd´alenosti d( relaˇcn´ıho koeficientu se obr´ azky neodpov´ıdaj´ıc´ı obliˇceji relativnˇe hodnˇe vzd´alili od obr´azk˚ u, kter´e obliˇcej˚ um odpov´ıdaj´ı. V´ yjimku tvoˇr´ı 5. obr´ azek, u kter´eho je moˇzn´e obliˇcej rozpoznat pouze za pomoc´ı korelaˇcn´ıho koeficientu. Co se t´ yˇce aplikace na lokalizaci obliˇceje na fotografii z naˇsi v´ yˇse uveden´ ych pˇr´ıklad˚ u. Opˇet d´av´a nejlepˇs´ı v´ ysledky pouˇzit´ı korelaˇcn´ıho koeficientu. Pˇri pouˇzit´ı pr˚ umˇern´eho obliˇceje je vˇsak v naˇsem konkr´etn´ım pˇr´ıkladu moˇzn´e lokalizovat obliˇcej i s pouˇzit´ım stˇredovan´e Eukleidovsk´e vzd´alenosti. Na obr´azc´ıch 9 a 10 jsou uvedeny v´ ysledky pro obˇe tyto metody.
¯ pro pˇr´ıklad pr˚ Obr´azek 9: Vizualizace matice vystˇredovan´ ych eukleidovsk´ ych vzd´alenost´ı D umˇern´eho referenˇcn´ıho obliˇceje F V tomto v m´ıstˇe obliˇceje opravdu existuje minimum s hodnotou 5,1857, nen´ı vˇsak ¯ vyznaˇceno ˇcerven´ od ostatn´ıch mal´ ych hodnot nijak v´ yraznˇe oddˇeleno. Toto minimum je v matici D ym kˇr´ıˇzkem a odpov´ıdaj´ıc´ı v´ ysek, pro kter´e nast´ av´a, je vyznaˇcen na fotografii vpravo ˇcerven´ ym r´ameˇckem.
6
Z´ avˇ er
Pˇredstavili jsme si nˇekolik jednoduch´ ych metod, kter´e se daj´ı pouˇz´ıt k lokalizaci obliˇceje (o pˇredem zn´ am´e velikosti) na fotografi´ıch. Nejintuitivnˇejˇs´ı metoda za pomoci urˇcov´an´ı Eukleidovsk´e vzd´alenosti matic byla u ´spˇeˇsn´a pˇri zpˇetn´e lokalizaci obliˇceje na obr´ azku, ze kter´eho byl vyjmut. K lokalizaci jin´eho obliˇceje se jiˇz nehodila. Proto jsme nejprve zavedli zlepˇsen´ı pomoc´ı stˇredovan´e Eukleidovsk´e vzd´alenosti. To jeˇstˇe st´ ale neumoˇznilo lokalizovat jin´ y obliˇcej. Pouze v pˇr´ıpadˇe, ˇze jsme pouˇz´ıvali pr˚ umˇern´ y obliˇcej, byla tato metoda u ´spˇeˇsn´a. Jak je vˇsak patrno, nejedn´ a se ani v tomto pˇr´ıpadˇe o nejvhodnˇejˇs´ı metodu. Posledn´ı a nej´ uspˇeˇsnˇejˇs´ı metoda vyuˇz´ıvala korelaˇcn´ı koeficient mezi dvˇema maticemi. Tento konstrukt jiˇz nen´ı zdaleka tak intuitivn´ı 9
Obr´azek 10: Vizualizace matice korelaˇcn´ıch koeficient˚ u R (vlevo) pro pˇr´ıklad pr˚ umˇern´eho referenˇcn´ıho obliˇceje F . V tomto pˇr´ıpadˇe je zˇreteln´e maximum s hodnotou 0,8593. Toto maximum je v matici R vyznaˇceno ˇcern´ ym kˇr´ıˇzkem a odpov´ıdaj´ıc´ı v´ ysek, pro kter´e nast´av´a, je vyznaˇcen na fotografii vpravo ˇcerven´ ym r´ameˇckem. jako Eukleidovsk´a vzd´ alenost, ale d´ av´ a jednoznaˇcnˇe nejlepˇs´ı v´ ysledky. I bez pouˇzit´ı pr˚ umˇern´eho obliˇceje bylo moˇzn´e lokalizovat podobn´ y obliˇcej na fotografii. Pˇri pouˇzit´ı pr˚ umˇern´eho obliˇceje se tato metoda jeˇstˇe vylepˇsuje. V praxi obvykle neb´ yvaj´ı takto zjednoduˇsen´e podm´ınky. Obliˇceje b´ yvaj´ı r˚ uzn´ ych velikost´ı, r˚ uznˇe natoˇcen´e a tak´e focen´e z r˚ uzn´ ych u ´hl˚ u. Pˇresto je lze velmi u ´spˇeˇsnˇe lokalizovat metodami, jejichˇz princip jsme zde uk´azali. Jedn´a se pouze o dalˇs´ı a dalˇs´ı rozˇs´ıˇren´ı. K pochopen´ı tˇechto u ´spˇeˇsn´ ych metod je vˇsak nejprve tˇreba hloubˇeji porozumˇet vysokoˇskolsk´e matematice.
Reference [1] J. Kalina, Robustn´ı anal´yza obrazu obliˇceje pro genetick´e aplikace, EJB, 2/2010. [2] M. Turk a A. Pentland, ¿Eigenfaces for Recognition, Journal of Cognitive Neuroscience (1991), Vol. 3, Num. 1, 72-86. [3] T. Heseltine, N. Pears, J. Austin a Z. Chen, Face Recognition: A Comparision of Appearance-Based Approaches, Proc. VIIth Digital Image Computing: Techniques and Applications, (2003), Sydney.
10
