Metody strojove´ho vnı´ma´nı´ Za´klady zpracova´nı´ signa´lu˚, obrazu˚ a prˇirozene´ rˇecˇi. Pocˇ´ıtacˇove´ videˇnı´, vznik obrazu, analy´za sce´ny, stereovideˇnı´, syste´my vı´ce kamer, analy´za pohybu. Vypracova´nı´ sta´tnicove´ ota´zky cˇ. 7 okruhu IV novy´ch ota´zek
Martin Matousˇek, leden 2000
Obsah I
Zpracova´nı´ prˇirozene´ rˇecˇi
1
1
Analy´za akusticke´ho rˇecˇove´ho signa´lu 1.1 Model vytva´rˇenı´ rˇecˇi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Akusticka´ analy´za rˇecˇi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Foneticka´ analy´za . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 1 2 2
2
Automaticke´ rozpozna´va´nı´ rˇecˇi 2.1 Metody rozpozna´va´nı´ zalozˇene´ na porovna´va´nı´ vzoru˚ . . . . . . . . . . . . . . . . . . . 2.2 Statisticky´ prˇ´ıstup k rozpozna´va´nı´ rˇecˇi . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Znalostnı´ prˇ´ıstup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 3 3 3
II Pocˇ´ıtacˇove´ videˇnı´
4
3
´ vod U 3.1 Dveˇ u´rovneˇ zpracova´nı´ obrazu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Za´kladnı´ kroky zpracova´nı´ obrazu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Procˇ je porozumeˇnı´ v u´loha´ch 3D pocˇ´ıtacˇove´ho videˇnı´ teˇzˇke´? . . . . . . . . . . . . . . .
4 4 4 5
4
Vznik obrazu 4.1 Formova´nı´ obrazu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Snı´ma´nı´ obrazu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Digitalizace obrazu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 5 6 6
5
Zpracova´nı´ digita´lnı´ho obrazu na nı´zke´ u´rovni 5.1 Bodove´ jasove´ transformace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Geometricke´ transformace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Loka´lnı´ prˇedzpracova´nı´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 7 8 8
6
Analy´za 2D obrazu 10 6.1 Segmentace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.2 Popis objektu˚ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
7
Analy´za pohybu 12 7.1 Rozdı´love´ metody analy´zy pohybu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 7.2 Opticky´ tok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 7.3 Detekce vy´znamny´ch bodu˚ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8
Analy´za 3D objektu˚ 14 ˇ ´ızenı´ obrazovy´mi daty – rˇ´ızenı´ zdola nahoru. . . . . . . . . . . . . . . . . . . . . . . . 14 8.1 R ˇ ´ızenı´ podle vnitrˇnı´ho modelu – rˇ´ızenı´ shora dolu˚. . . . . . . . . . . . . . . . . . . . . 15 8.2 R
9
Geometrie pro pocˇ´ıtacˇove´ videˇnı´ 16 9.1 Jedna kamera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 9.2 Syste´m vı´ce kamer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Cˇa´st I
Zpracova´nı´ prˇirozene´ rˇecˇi 1 1.1
Analy´za akusticke´ho rˇecˇove´ho signa´lu Model vytva´rˇenı´ rˇecˇi
Zdrojem rˇecˇovy´ch kmitu˚ jsou rˇecˇove´ orga´ny: hlasivky, dutina hrdelnı´, u´stnı´ a nosnı´, meˇkke´ a tvrde´ patro, zuby a jazyk. Zdrojem hlasove´ energie jsou plı´ce a dy´chacı´ svaly. Zdrojem zneˇly´ch zvuku˚ jsou hlasivky vyda´vajı´cı´ za´kladnı´ to´n hlasu (150 azˇ 400 Hz). Samohla´sky vytva´rˇ´ı volny´ pru˚chod vzduchu hlasovy´m traktem. V akusticke´m spektru se objevujı´ zesı´lene´ to´ny vznikajı´cı´ rezonancı´ v dutina´ch hlasove´ho traktu – formanty. Souhla´sky jsou vytva´rˇeny turbulencı´ – trˇenı´m vzduchu o prˇeka´zˇku (jazyk, zuby, rty). Je-li prˇeka´zˇka u´plna´ jedna´ se o za´veˇrove´ souhla´sky (p, t, t’, k, b, d, d’, g, m, n, nˇ). Dalsˇ´ı typ je u´zˇinova´ souhla´ska, vznikajı´cı´ sˇumem zpu˚sobeny´m zu´zˇenı´m cesty vzduchu (f, v, s, sˇ, z, zˇ, j, ch, h, l, r, rˇ). Oba typy prˇeka´zˇek (postupneˇ) se objevujı´ u souhla´sek poloza´veˇrovy´ch (c, cˇ). Souhla´sky lze da´le rozdeˇlit podle zneˇlosti (zneˇla´–nezneˇla´), pa´rove´ (p-b, t-d, t’-d’, k-g, s-z, sˇ-zˇ, f-v, ch-h, c-dz, cˇ-dzˇ) a pouze zneˇle´ nepa´rove´ (m, n, nˇ, l, j, r, rˇ). Strˇ´ıda´nı´m poloh hlasove´ho u´strojı´ vznikajı´ akusticke´ signa´ly, z nichzˇ se formujı´ zvukove´ elementy – fone´my (v cˇesˇtineˇ odpovı´dajı´ prˇiblizˇneˇ vysloveny´m hla´ska´m). Fone´my se meˇnı´ podle kontextu – za´visı´ na prˇedchozı´m a na´sledujı´cı´m zvuku – koartikulace. Cı´lem modelova´nı´ produkce rˇecˇi je nale´zt matematicke´ vztahy pouzˇitelne´ pro reprezentaci fyzika´lnı´ch deˇju˚ spojeny´ch s touto produkcı´. Lidska´ rˇecˇ je nelinea´rnı´ cˇasoveˇ promeˇnny´ proces. Lze ale udeˇlat jiste´ zjednodusˇujı´cı´ prˇedpoklady: pro mnohe´ zvuky platı´, zˇe typ buzenı´ a vlastnosti hlasove´ho traktu jsou jsou te´meˇrˇ konstantnı´ v intervalu 10–20 ms. Pak lze vytvorˇit model (obra´zek 1) slozˇeny´ z linea´rnı´ho modelu hlasove´ho traktu s pomalu se meˇnı´cı´mi parametry, ktery´ je buzen vhodny´m budı´cı´m signa´lem (periodicky´ sled impulsu˚ pro zneˇlou, cˇi sˇumovy´ signa´l pro nezneˇlou rˇecˇ).
Obra´zek 1: Model vytva´rˇenı´ rˇecˇi. Model hlasove´ produkce na obra´zku 1 respektuje chova´nı´ hlasivek, hlasove´ho traktu i proces vyzarˇova´nı´
1
zvuku ze rtu˚ a nozder. Jeho z-prˇenos je ve tvaru celopo´love´ho filtru Q-te´ho rˇa´du: 1 , H(z) = PQ 1 + i=1 ai z −i kde ai jsou parametry modelu a Q v rozsahu 8–14.
1.2
Akusticka´ analy´za rˇecˇi
Prˇedpoklad pomaly´ch zmeˇn vlastnostı´ signa´lu vede na metody kra´tkodobe´ analy´zy, kdy se signa´l rozdeˇlı´ na samostatne´ mikrosegmenty de´lky 10 azˇ 30 ms. Signa´l se vzorkuje a kvantuje, pouzˇ´ıva´ se pulsnı´ ko´dova´ modulace. Analy´za v cˇasove´ oblasti lze vyja´drˇit vztahem Qn =
X
τ (s(k))w(n − k),
Qn je kra´tkodoba´ charakteristika, s(k) je vzorek akusticke´ho signa´lu v cˇase k, τ (.) je transformacˇnı´ funkce a w(n) je va´hova´ posloupnost – oke´nko, vybı´rajı´cı´ prˇ´ıslusˇne´ vzorky signa´lu. Analy´za ve frekvencˇnı´ oblasti pouzˇ´ıva´ kra´tkodobou Fourierovu transformaci signa´lu rovneˇzˇ v oke´nku. Dalsˇ´ı metody analy´zy jsou kepstra´lnı´ analy´za a linea´rnı´ prediktivnı´ ko´dova´nı´.
1.3
Foneticka´ analy´za
Metody odhadu fundamenta´lnı´ frekvence – za´kladnı´ hlasivkovy´ to´n odpovı´dajı´cı´ kmitu˚m hlasivek. Vyuzˇ´ıva´ se autokorelacˇnı´ funkce. Proble´m je odlisˇit za´kladnı´ frekvenci od formantu˚. Informace o formantovy´ch frekvencı´ch – ve spektra´lnı´ oba´lce signa´lu. Pouzˇ´ıva´ se vyhlazene´ signa´love´ spektrum. Prˇ´ıklad vy´voje spektra´lnı´ oba´lky je na obra´zku 2. Prˇi dalsˇ´ım zpracova´nı´ se cˇasto uzˇ´ıva´ vektorova´ kvantizace – aproximace analogove´ hodnoty popisujı´cı´ mikrosegment celocˇ´ıselnou. Ko´dova´ kniha – reprodukcˇnı´ abeceda typovy´ch spektra´lnı´ch vzoru˚, konstruuje se z tre´novacı´ mnozˇiny.
Obra´zek 2: Cˇasovy´ pru˚beˇh zmeˇn tvaru˚ spektra´lnı´ch oba´lek slova „cˇtyrˇi“.
2
Automaticke´ rozpozna´va´nı´ rˇecˇi
Pouzˇ´ıvajı´ se metody zalozˇene´ na porovna´va´nı´ vzoru˚, na statisticke´m prˇ´ıstupu a na znalostnı´m prˇ´ıstupu. 2
2.1
Metody rozpozna´va´nı´ zalozˇene´ na porovna´va´nı´ vzoru˚
Zejme´na klasifikace izolovany´ch slov. Kazˇde´ slovo ve slovnı´ku ma´ neˇkolik vzoru˚ vyja´drˇeny´ch rˇeteˇzci prˇ´ıznaku˚. Pouzˇ´ıva´ se porovna´nı´ se vzory, cˇasto krite´rium minima´lnı´ vzda´lenosti nebo pravidlo nejblizˇsˇ´ıho souseda. Proble´m je porovna´nı´ obrazu vzorove´ho a nezna´me´ho slova, protozˇe mezi slovy jsou odlisˇnosti v cˇasove´m cˇleneˇnı´. K porovna´va´nı´ se pouzˇ´ıva´ dynamicke´ programova´nı´ – nalezenı´ funkce ktera´ nelinea´rneˇ upravı´ cˇasovou osu tak, aby si slova byla co nejvı´ce podobna´ (bortiva´ funkce, dynamic time warping).
2.2
Statisticky´ prˇ´ıstup k rozpozna´va´nı´ rˇecˇi
Pouzˇ´ıvajı´ se Markovske´ modely, vyuzˇ´ıva´ se vektorova´ kvantizace.
2.3
Znalostnı´ prˇ´ıstup
Je trˇeba prove´st formalizaci znalostı´ o vytva´rˇenı´ rˇecˇi (ba´ze znalostı´) a u´daju˚ o konkre´tnı´ rˇecˇi (ba´ze dat). Pouzˇ´ıvajı´ se principy expertnı´ch syste´mu˚. Akusticko-foneticke´ znalosti vyjadrˇujı´ vztah mezi foneticky´m prˇepisem promluvy. Lexika´lnı´ a fonologicke´ znalosti prˇedstavujı´ v podstateˇ slovnı´k. Prozodicke´ znalosti slouzˇ´ı k lokalizaci prˇ´ızvucˇny´ch slabik a segmentaci promluvy do syntakticky´ch fra´zı´. Syntakticke´ znalosti jsou reprezentova´ny vhodnou gramatikou, vyjadrˇujı´ prˇ´ıpustnou konstrukci veˇt. Se´manticke´ znalosti se vyuzˇ´ıvajı´ prˇi ocenˇova´nı´ smyslu nebo prˇ´ıpustnosti obsahu analyzovany´ch veˇt. Pragmaticke´ znalosti reprezentujı´ kontext. Pouzˇ´ıva´ se neˇkolik modelu˚ organizace a rˇ´ızenı´ znalostı´: Hierarchicky´ model. Pouzˇ´ıva´ se rezˇim zdola-nahoru (zpracova´nı´ od akusticke´ u´rovneˇ), rezˇim shora-dolu (generova´nı´ a oveˇrˇova´nı´ hypote´z) a rezˇim kombinovany´. Heterarchicky´ model. Umozˇnˇuje komunikaci mezi libovolny´mi dveˇma zdroji znalostı´. Nevy´hoda – mnozˇstvı´ informacˇnı´ch spojenı´. Model tabule. Zdroje dat komunikujı´ pomocı´ spolecˇne´ datove´ struktury.
3
Cˇa´st II
Pocˇ´ıtacˇove´ videˇnı´ ´ vod U
3
Pocˇ´ıtacˇove´ videˇnı´ je disciplı´na, ktera´ se snazˇ´ı technicky´mi prostrˇedky alesponˇ cˇa´stecˇneˇ napodobit lidske´ videˇnı´ – zdroj prˇeva´zˇne´ veˇtsˇiny informacı´ o okolnı´m sveˇteˇ. Prˇ´ı vyhodnocenı´ vizua´lnı´ informace hraje obrovskou roli inteligence cˇloveˇka, ktera´ umozˇnˇuje reprezentovat dlouho naby´vane´ znalosti a zkusˇenosti o okolnı´m sveˇteˇ. Vy´zkum pocˇ´ıtacˇove´ho videˇnı´ se snazˇ´ı o rˇesˇenı´ analogicky´ch u´loh. Teoreticky i technicky jsou ale zvla´dnuty jen velmi jednoduche´ proble´my. Pro pocˇ´ıtacˇove´ videˇnı´ je typicka´ snaha porozumeˇt obecne´ trojrozmeˇrne´ sce´neˇ. Zpracova´nı´ a rozpozna´va´nı´ obrazu pocˇ´ıtacˇem se lisˇ´ı od pocˇ´ıtacˇove´ grafiky. Cı´lem grafiky je zobrazit informaci z pocˇ´ıtacˇe, pocˇ´ıtacˇove´ videˇnı´ se naopak veˇnuje vstupu obrazove´ informace o skutecˇne´m sveˇteˇ a jejı´mu vyhodnocenı´.
3.1
Dveˇ u´rovneˇ zpracova´nı´ obrazu
Ve zpracova´nı´ obrazu se dajı´ rozlisˇit dveˇ hlavnı´ u´rovneˇ. Postupy pocˇ´ıtacˇove´ho videˇnı´ jsou znacˇneˇ slozˇite´, s teˇzˇisˇteˇm v interpretaci obrazovy´ch dat, ktera´ jsou nejcˇasteˇji reprezentova´na symbolicky. Ja´drem pokrocˇilejsˇ´ıch postupu˚ jsou znalostnı´ syste´my a techniky umeˇle´ inteligence. Te´to cˇa´sti pocˇ´ıtacˇove´ho videˇnı´ se rˇ´ıka´ vysˇsˇ´ı u´rovenˇ a jde v nı´ o porozumeˇnı´ obrazu. Prˇedpokladem porozumeˇnı´ je vsˇak pra´ce s obrazem na nizˇsˇ´ı u´rovni. Cı´lem nizˇsˇ´ı u´rovneˇ pocˇ´ıtacˇove´ho videˇnı´ je analyzovat vstupnı´ dvojrozmeˇrna´ obrazova´ data cˇ´ıselne´ho charakteru a najı´t kvalitativnı´ symbolickou informaci potrˇebnou pro vysˇsˇ´ı u´rovenˇ. Postupy nizˇsˇ´ı u´rovneˇ jsou take´ bezprostrˇedneˇ prakticky pouzˇitelne´ pro odstranˇova´nı´ sˇumu z obrazu, rozpozna´va´nı´ jednoduchy´ch objektu˚ v obraze apod. Pro nizˇsˇ´ı u´rovenˇ se take´ pouzˇ´ıva´ na´zev zpracova´nı´ obrazu pocˇ´ıtacˇem (image processing). Jednotlive´ u´rovneˇ zpracova´nı´ obrazu spolu vsˇak souvisejı´, ovlivnˇujı´ se a lze mezi nimi najı´t zpeˇtne´ vazby.
3.2
Za´kladnı´ kroky zpracova´nı´ obrazu
Postup zpracova´nı´ a rozpozna´va´nı´ obrazu rea´lne´ho sveˇta se darˇ´ı obvykle rozlozˇit do posloupnosti za´kladnı´ch kroku˚: 1. Snı´ma´nı´, digitalizace a ulozˇenı´ obrazu v pocˇ´ıtacˇi. Snı´ma´nı´ je prˇevod vstupnı´ opticke´ velicˇiny na elektricky´ signa´l spojity´ v cˇase i u´rovni. Vstupnı´ informacı´ mu˚zˇe by´t jas (z TV kamery, scanneru), intenzita rentgenove´ho za´rˇenı´, ultrazvuk, tepelne´ za´rˇenı´ aj. Snı´mat se mu˚zˇe v jednom nebo vı´ce spektra´lnı´ch pa´smech. Pro barevne´ snı´ma´nı´ stacˇ´ı trˇi spektra´lnı´ slozˇky (cˇervena´, zelena´, modra´), zpracova´va´me-li obraz, ktery´ bude pozorova´n cˇloveˇkem (odpovı´da´ typu˚m cˇidel na sı´tnici oka). Digitalizace prˇeva´dı´ vstupnı´ spojity´ signa´l do diskre´tnı´ho tvaru. Signa´l je popsa´n funkcı´ f (i, j) sourˇadnic v obraze. Funkcˇnı´ hodnota odpovı´da´ naprˇ. jasu. Vstupnı´ signa´l je vzorkova´n a kvantova´n. Vy´sledkem je matice prˇirozeny´ch cˇ´ısel popisujı´cı´ch obraz. Prvek matice = bod, pixel, da´le nedeˇlitelna´ jednotka. Existujı´ i jine´ mozˇnosti reprezentace vstupnı´ho obrazu v pocˇ´ıtacˇi. Cˇasty´m prˇ´ıpadem je popis obrazu 4
koeficienty dvourozmeˇrne´ Fourierovy transformace. Vy´hodou je to, zˇe Fourierovu transformaci lze prove´st okamzˇiteˇ opticky´mi prostrˇedky jizˇ prˇed digitalizacı´. 2. Prˇedzpracova´nı´. Cı´lem je potlacˇit sˇum a zkreslenı´ vznikle´ prˇi digitalizaci a prˇenosu obrazu nebo zvy´razneˇnı´ urcˇity´ch rysu˚ obrazu podstatny´ch pro dalsˇ´ı zpracova´nı´ (naprˇ´ıklad hleda´nı´ hran). 3. Segmentace obrazu na objekty. je jeden s nejteˇzˇsˇ´ıch kroku˚. Za objekty se podobneˇ jako v obecne´ teorii syste´mu˚ povazˇujı´ ty cˇa´sti obrazu, ktere´ na´s z hlediska dalsˇ´ıho zpracova´nı´ zajı´majı´. Prˇi segmentaci se tedy zhusta vyuzˇ´ıva´ znalosti interpretace obrazu (se´mantika). 4. Popis objektu˚. Lze je popsat bud’ kvantitativneˇ pomocı´ souboru cˇ´ıselny´ch charakteristik a/nebo kvalitativneˇ pomocı´ relacı´ mezi objekty. 5. Porozumeˇnı´ obsahu obrazu (cˇasto jen klasifikace objektu˚). Jednoduchy´ prˇ´ıpad je klasifikace objektu˚ do neˇkolika prˇedem zna´my´ch trˇ´ıd. V obecne´m prˇ´ıpadeˇ prˇedstavuje porozumeˇnı´ interpretaci obrazovy´ch dat, o ktery´ch se prˇedem nic neprˇedpokla´da´. Porozumeˇnı´ obrazu je potom zalozˇeno na znalosti, cı´lı´ch, tvorbeˇ pla´nu˚ a vyuzˇitı´ zpeˇtny´ch vazeb mezi ru˚zny´mi u´rovneˇmi zpracova´nı´. Pouzˇ´ıvajı´ se postupy vysˇsˇ´ı u´rovneˇ zpracova´nı´, vyuzˇ´ıva´ se technik znalostnı´ch syste´mu˚. Analy´za obrazu je slozˇiteˇjsˇ´ı, kdyzˇ je prˇi vyhodnocenı´ trˇeba bra´t v u´vahu nejen skala´rnı´ obrazovou funkci za´vislou na dvou sourˇadnicı´ch v rovineˇ, ktera´ odpovı´da´ jednomu staticke´mu monochromaticke´mu obrazu. Obrazova´ funkce nemusı´ by´t staticka´, ale v cˇase promeˇnna´. Dalsˇ´ı komplikacı´ je, kdyzˇ obrazova´ funkce nenı´ skala´rnı´, ale vektorova´ (vı´cerozmeˇrna´) – vı´cespektra´lnı´ obrazova´ funkce, velmi cˇasto ale pro jednoduchost zpracova´vana´ jako neza´visle´ monochromaticke´ obrazy.
3.3
Procˇ je porozumeˇnı´ v u´loha´ch 3D pocˇ´ıtacˇove´ho videˇnı´ teˇzˇke´?
Je-li senzorem jedina´ kamera, informace se ztra´cı´ perspektivnı´m zobrazenı´m. Zpeˇtna´ u´loha odvozenı´ 3D vlastnosti objektu˚ z obrazu kamery ma´ tedy nekonecˇneˇ rˇesˇenı´. Lze rˇesˇit jen za pouzˇitı´ dalsˇ´ıch omezenı´. Druhou komplikacı´ je vztah mezi meˇrˇeny´m jasem a tvarem povrchu 3D objektu˚ v obraze – jas za´visı´ na ´ loha urcˇenı´ mnoha vlivech (odrazivost povrchu, poloha a vlastnosti zdroju˚ sveˇtla, orientace povrchu). U 3D vlastnostı´ objektu˚ na za´kladeˇ pozorovane´ho jasu je take´ nedostatecˇneˇ urcˇena´ u´loha. Trˇetı´ prˇeka´zˇkou je velike´ mnozˇstvı´ obrazovy´ch dat a v neposlednı´ rˇadeˇ sˇum, ktery´ je v rea´lne´m obraze vzˇdy prˇ´ıtomen. V prakticky´ch aplikacı´ch se snazˇ´ıme, abychom u´lohu porozumeˇnı´ nerˇesˇili v jejı´ plne´ obecnosti. Jde-li to, prˇevedeme trojrozmeˇrnou u´lohu na dvojrozmeˇrnou nebo naprˇ. je mozˇne´ vhodnou volbou osveˇtlenı´ objektu˚ nahradit slozˇite´ postupy segmentace obrazu na jednoduche´ prahova´nı´ podle jasu. Neˇktere´ prakticky zajı´mave´ veˇdnı´ a technicke´ obory zpracova´vajı´ obrazy, ktere´ majı´ prˇ´ımo 2D povahu. Rˇesˇenı´ u´loh, ktere´ majı´ 2D povahu, je mnohem jednodusˇsˇ´ı nezˇ snaha porozumeˇt 3D sce´neˇ.
4 4.1
Vznik obrazu Formova´nı´ obrazu
Matematicky´m modelem obrazu mu˚zˇe by´t spojita´ funkce f (i, j) dvou argumentu˚, sourˇadnic v rovineˇ. Funkci f (i, j) se obvykle rˇ´ıka´ obrazova´ funkce. Hodnotou obrazova´ funkce je nejcˇasteˇji jas (intenzita), – meˇrˇ´ı veˇtsˇina cˇidel pro vstup obrazu. Jas souhrnneˇ vyjadrˇuje vlastnosti obrazove´ho signa´lu zpu˚sobem, ktery´ odpovı´da´ jeho vnı´ma´nı´ cˇloveˇkem. Neˇkdy mu˚zˇe obrazova´ funkce reprezentovat i jine´ fyzika´lnı´ velicˇiny, jako distribuci tlaku, vzda´lenost od pozorovatele, teplotu. 5
Prostrˇedı´, ve ktere´m se beˇzˇneˇ pohybujeme, ma´ trojrozmeˇrnou (3D) povahu. Dvojrozmeˇrna´ (2D) obrazova´ funkce je vy´sledkem perspektivnı´ho zobrazenı´ cˇa´sti 3D prostrˇedı´ – realisticky´ model odpovı´dajı´cı´ zı´ska´nı´ obrazu v dı´rkove´ komorˇe. Geometrie viz obra´zek 3. Necht’ (x, y, z) jsou sourˇadnice bodu ve 3D sce´neˇ a f je ohniskova´ vzda´lenost. Potom bod po perspektivnı´m zobrazenı´ ma´ v obrazove´ rovineˇ sourˇadnice: xf yf x0 = ; y0 = . z z Prˇi snaze o zjednodusˇenı´ se neˇkdy nelinea´rnı´ perspektivnı´ zobrazenı´ nahrazuje pravou´hly´m (ortograficky´m) zobrazenı´m, kde se prˇedpokla´da´, zˇe ohniskova´ vzda´lenost objektivu je nekonecˇna´.
Obra´zek 3: Perspektivnı´ zobrazenı´. Popisem vzniku obrazu se podrobneˇ zaby´va´ fotometrie a radiometrie, pracujı´cı´ s pojmy jako sveˇtelny´ a za´rˇivy´ tok a oza´rˇenı´. Prˇi analy´ze obrazu jsou cˇasto bra´ny zjednodusˇujı´cı´ prˇedpoklady na vznik obrazu. Hlavnı´ z nich je prˇedpoklad Lambertovske´ho povrchu – idea´lneˇ matny´ povrch, ktery´ odra´zˇ´ı sveˇtlo rovnomeˇrneˇ do vsˇech smeˇru˚.
4.2 Snı´ma´nı´ obrazu Pro zpracova´nı´ obrazu pocˇ´ıtacˇem je trˇeba ho nejprve sejmout – prˇevod opticke´ velicˇiny na elektrickou. Nejbeˇzˇneˇjsˇ´ımi zarˇ´ızenı´mi pro snı´ma´nı´ opticke´ho obrazu jsou: scanner, TV kamera a v poslednı´ dobeˇ te´zˇ CCD kamera.
4.3 Digitalizace obrazu Cˇidla pro vstup obrazove´ funkce jsou (naprˇ. TV kamera) jsou veˇtsˇinou zdrojem spojite´ho signa´lu (neplatı´ pro CCD kameru). Abychom obrazovou fci mohli zpracovat v PC, musı´me nejdrˇ´ıve zı´skat jejı´ digita´lnı´ ekvivalent – vzorkova´nı´ obrazu v matici MxN bodu˚ a kvantova´nı´ jasove´ u´rovneˇ do K intervalu˚. Jasova´ fce tedy naby´va´ celocˇ´ıselny´ch hodnot. Ota´zku vzda´lenosti vzorku˚ (plosˇna´ vzorkovacı´ frekvence) rˇesˇ´ı Shannonova veˇta (frekvence musı´ by´t alesponˇ dvakra´t veˇtsˇ´ı nezˇ nejvysˇsˇ´ı frekvence ve vzorkovane´m signa´lu, tedy je prˇizpu˚sobena nejmensˇ´ım detailu˚m v obraze). Da´le je trˇeba vybrat plosˇne´ usporˇa´da´nı´ bodu˚ pro vzorkova´nı´ (mrˇ´ızˇka). Obvykle se pouzˇ´ıva´ cˇtvercova´ (cˇasteˇjsˇ´ı) nebo hexagona´lnı´ mrˇ´ızˇka (vy´hodou je pravidelnost vzhledem k okolı´ bodu).
6
Kvantova´nı´ je ovlivneˇno pozˇadavkem na prˇesnost reprezentace obrazu. Pocˇet kvantovacı´ch u´rovnı´ ma´ by´t dostatecˇneˇ velky´, aby byly prˇesneˇ vyja´drˇeny jemne´ detaily obrazu, nevznikaly falesˇne´ obrysy a aby se citlivost zarˇ´ızenı´ blı´zˇila citlivosti lidske´ho oka (cˇloveˇk rozpozna´ najednou asi 50 u´rovnı´ jasu). Veˇtsˇina syste´mu˚ pro digita´lnı´ zpracova´nı´ obrazu pouzˇ´ıva´ kvantova´nı´ do k stejny´ch intervalu˚. Pouzˇijeme-li b bitu˚, je pocˇet u´rovnı´ jasu k = 2b . Obvykle se pouzˇ´ıva´ 8 bitu˚ na obrazovy´ element. Pouzˇijeme-li pouze 1 bit, hovorˇ´ıme o bina´rnı´ch obrazech. Neˇkdy je vy´hodne´ pouzˇ´ıt nelinea´rnı´ kvantova´nı´, ktere´ zveˇtsˇuje rozsah teˇch intervalu˚ jasu, jejichzˇ zastoupenı´ nenı´ v obraze pravdeˇpodobne´.
5
Zpracova´nı´ digita´lnı´ho obrazu na nı´zke´ u´rovni
Uvazˇujme cˇtvercovou mrˇ´ızˇku, reprezentovanou v PC dvojrozmeˇrnou maticı´ cely´ch cˇ´ısel. Prˇedstavu o rozdeˇlenı´ jasovy´ch u´rovnı´ v digita´lnı´m obraze zı´ska´me pomocı´ histogramu – vektor s pocˇtem slozˇek rovny´m pocˇtu jasovy´ch u´rovnı´. Hodnota kazˇde´ slozˇky odpovı´da´ cˇetnosti bodu˚ prˇ´ıslusˇne´ho jasu v obraze. Histogram cˇasto by´va´ jedinou globa´lnı´ informacı´ o obraze. Mu˚zˇeme ho pouzˇ´ıt prˇi nastavova´nı´ podmı´nek pro snı´ma´nı´ a digitalizaci, prˇi zmeˇna´ch jasove´ stupnice a prˇi segmentaci. Obraz mu˚zˇe by´t zatı´zˇen ru˚zny´mi nezˇa´doucı´mi poruchami, ktere´ se obvykle nazy´vajı´ sˇum. Ten mu˚zˇe vzniknout prˇi snı´ma´nı´, prˇenosu i zpracova´nı´ obrazu. Mu˚zˇe by´t na obrazove´m signa´lu bud’ za´visly´, nebo neza´visly´. Sˇum se veˇtsˇinou popisuje pravdeˇpodobnostnı´mi a frekvencˇnı´mi charakteristikami (bı´ly´ sˇum – vsˇechny frekvence, Gaussu˚v sˇum – norma´lnı´ rozdeˇlenı´ pravdeˇpodobnosti). Sˇum neza´visly´ na signa´lu je oznacˇen jako aditivnı´ sˇum (f (x, y) = g(x, y) + v(x, y), v je sˇum a g je vstupnı´ obraz). V rˇadeˇ prˇ´ıpadu˚ za´visı´ velikost sˇumu na velikosti obrazove´ho signa´lu – multiplikativnı´ sˇum (f = g + vg). Kvantizacˇnı´ sˇum se objevı´ pokud nenı´ pouzˇit dostatecˇny´ pocˇet jasovy´ch u´rovnı´. Metody (prˇed)zpracova´nı´ obrazu slouzˇ´ı ke zlepsˇenı´ obrazu z hlediska dalsˇ´ıho zpracova´nı´. Tato hlediska budou jina´, pokud bude vy´sledny´ obraz pozorovat na monitoru cˇloveˇka, nebo kdyzˇ budeme usilovat o automaticke´ zpracova´nı´ obrazu. Cı´lem prˇedzpracova´nı´ je potlacˇit sˇum vznikly´ prˇi digitalizaci a prˇenosu obrazu, odstranit zkreslenı´ dane´ vlastnostmi snı´macı´ho zarˇ´ızenı´ (naprˇ. korekce zakrˇivenı´ zemske´ho povrchu u druzˇicovy´ch snı´mku˚) nebo potlacˇit cˇi zvy´raznit jine´ rysy obrazu du˚lezˇite´ z hlediska dalsˇ´ıho zpracova´nı´. Je du˚lezˇite´ si uveˇdomit, zˇe v pru˚beˇhu prˇedzpracova´nı´ nezı´ska´me z hlediska Shannonovy teorie zˇa´dnou novou informaci (meˇrˇenou entropiı´). Lze jen neˇkterou informaci potlacˇit nebo zvy´raznit.
5.1
Bodove´ jasove´ transformace
Jasove´ korekce. Jas v bodeˇ vy´stupnı´ho obrazu za´visı´ pouze na jasu bodu vstupnı´ho obrazu se stejny´mi sourˇadnicemi. Slouzˇ´ı k odstraneˇnı´ systematicke´ poruchy prˇevodnı´ charakteristiky. Nejcˇasteˇji se prˇedpokla´da´ porusˇenı´ obrazu multiplikativnı´m koeficientem e(i, j). Pro kazˇdy´ bod pu˚vodnı´ho obrazu g(i, j) zı´ska´me na vy´stupu zkresleny´ bod f (i, j) = e(i, j)g(i, j). Funkci e(i, j) mu˚zˇeme zı´skat sejmutı´m obrazu o zna´me´m pru˚beˇhu jasove´ funkce. Zmeˇna jasove´ stupnice. Transformace jasove´ stupnice neza´visı´ na poloze v obraze. Transformace T vy´chozı´ stupnice jasu p na novou stupnici q je da´na vztahem q = T (p). Touto transformacı´ lze realizovat fce „negativ“, zvy´sˇenı´ kontrastu (vyrovna´nı´m histogramu), prahova´nı´. Transformace jasove´ stupnice se realizuje pomocı´ tzv. vyhleda´vacı´ tabulky (look up table). V terminologii PC se pouzˇ´ıva´ pojem paleta.
7
5.2
Geometricke´ transformace
Prˇi snı´ma´nı´ mu˚zˇe by´t obraz geometricky zkreslen, je proto trˇeba toto zkreslenı´ korigovat. Geometricka´ transformace TG je vektorova´ fce, ktera´ transformuje bod v rovineˇ (x, y) do bodu (x0 , y 0 ). Transformace TG je definova´na slozˇkovy´mi vztahy x0 = Tx (x, y), y 0 = Ty (x, y). Transformacˇnı´ vztahy Tx a Ty mohou by´t bud’ zna´mi prˇedem (rotace, posun, zveˇtsˇenı´), nebo je mozˇne´ hledat transformacˇnı´ vztah na za´kladeˇ znalostı´ pu˚vodnı´ho i transformovane´ho obrazu (neˇkolik zna´my´ch bodu˚). Geometricka´ transformace se skla´da´ ze dvou kroku˚: plosˇna´ transformace (najde k bodu vstupnı´ho obrazu odpovı´dajı´cı´ bod vy´stupnı´ho obrazu) a nalezenı´ u´rovneˇ jasu. Transformacˇnı´ vztahy se obvykle aproximujı´ polynomy.
5.3
Loka´lnı´ prˇedzpracova´nı´
Tyto metody vyuzˇ´ıvajı´ pro vy´pocˇet jasu bodu vy´stupnı´ho obrazu loka´lnı´ho okolı´ odpovı´dajı´cı´ho bodu ve vstupnı´m obraze. Lze je rozdeˇlit do dvou velky´ch skupin: vyhlazova´nı´ obrazu (potlacˇenı´ vysˇsˇ´ıch frekvencı´ obrazove´ fce – potlacˇenı´ sˇumu) a gradientnı´ operace (zdu˚razneˇnı´ vysˇsˇ´ıch frekvencı´). Pouzˇ´ıvajı´ se linea´rnı´ a nelinea´rnı´ metody. Linea´rnı´ pocˇ´ıtajı´ vy´sledny´ jas pomocı´ diskre´tnı´ konvoluce vstupnı´ho obrazu s ja´drem h: f (i, j) =
X X
h(i − m, j − n)g(m, n).
(m,n) ∈O
Loka´lnı´ operace prˇedzpracova´nı´ obvykle jen ma´lo vyuzˇ´ıvajı´ prˇedbeˇzˇne´ znalosti obsahu obrazu. Vzhledem k maly´m rozmeˇru˚m okolı´ zpracova´vane´ho bodu si tuto se´mantickou znalost nemohou odvodit ani v pru˚beˇhu sve´ cˇinnosti. Zvla´sˇteˇ pro operace vyhlazova´nı´ je vhodne´ zna´t charakter poruch nebo sˇumu a podle neˇho prˇizpu˚sobit zpracova´nı´. Konvolucˇnı´ linea´rnı´ operace (filtry) jsou pouzˇitelne´ pro vyhlazova´nı´, detekci hran nebo cˇar. Filtrace Filtrace je soubor transformacı´, jezˇ majı´ za cı´l zvy´raznit nebo potlacˇit neˇktere´ vlastnosti obrazove´ fce. Cˇasto pozˇadujeme potlacˇenı´ rozdı´lu jasu uvnitrˇ oblastı´, ktery´ zaprˇ´ıcˇinˇuje sˇum. Volba transformace je za´visla´ na velikosti objektu˚. Ve frekvencˇnı´m spektru odpovı´da´ filtraci potlacˇenı´ vysoky´ch plosˇny´ch frekvencı´ (vy´sledek dvojrozmeˇrne´ Fourierovy transformace obrazu). S filtracı´ obrazu je spojen proble´m rozmaza´nı´ hran. Obycˇejne´ pru˚meˇrova´nı´ filtruje obraz tak, zˇe jako novy´ jas bodu prˇirˇadı´ aritmeticky´ pru˚meˇr jasu bodu˚ obde´lnı´kove´ho okolı´. Nevy´hodou je velke´ rozmaza´va´nı´ hran. K potlacˇenı´ sˇumu dojde proto, zˇe uvazˇujeme-li aditivnı´ sˇum s na´hodny´m rozdeˇlenı´m se strˇednı´ hodnotou 0 a smeˇrodatnou odchylkou σ, pak smeˇrodatna´ odchylka zpru˚meˇrovane´ na´hodne´ velicˇiny je √σn . Pokud ma´me k dispozici n obrazu˚ te´zˇe prˇedlohy, lze filtrovat sˇum bez rozmaza´nı´ hran pru˚meˇrova´nı´m prˇes tyte´zˇ body v ru˚zny´ch obrazech.
8
Obycˇejne´ pru˚meˇrova´nı´ je specia´lnı´ prˇ´ıpad diskre´tnı´ konvoluce s ja´drem (pro okolı´ 3x3):
1 1 1 1 h = 1 1 1 . 9 1 1 1 Neˇkdy se zveˇtsˇuje va´ha neˇktery´ch bodu˚ masky aby se le´pe aproximoval sˇum s Gaussovsky´m rozdeˇlenı´m.
1 1 1 1 h= 1 2 1 , 10 1 1 1
1 2 1 1 h= 2 4 2 . 16 1 2 1
Potı´zˇe s rozmaza´va´nı´m hran eliminujı´ dalsˇ´ı filtracˇnı´ metody, ktere´ pru˚meˇrujı´ jen tu cˇa´st okolı´, ke ktere´ bod pravdeˇpodobneˇ patrˇ´ı. Cˇasto se pouzˇ´ıva´ filtrace metodou media´nu (50% kvantil, vycha´zı´ z metod robustnı´ statistiky). Nevy´hodou je porusˇenı´ tenky´ch cˇar a ostry´ch rohu˚. Tento nedostatek se da´ obejı´t pouzˇitı´m jine´ho tvaru okolı´, naprˇ. krˇ´ızˇ. Metoda media´nu je specia´lnı´ prˇ´ıpad OS (order statistic) filtrace – statistika pocˇ´ıtana´ z posloupnosti serˇazeny´ch bodu˚ okolı´ (media´n, min, max, linea´rnı´ kombinace). Filtrace metodou rotujı´cı´ masky se snazˇ´ı podle homogenity jasu najı´t k filtrovane´mu bodu cˇa´st jeho okolı´, ke ktere´ pravdeˇpodobneˇ patrˇ´ı. Pro vy´pocˇet pru˚meˇrova´nı´m je pak pouzˇita jen tato cˇa´st. Metoda nerozmaza´va´ hrany a ma´ mı´rneˇ ostrˇ´ıcı´ charakter. Detekce hran, ostrˇenı´ Hrana je vektorova´ velicˇina urcˇena´ velikostı´ a smeˇrem (vycha´zı´ z gradientu obrazove´ fce) a indikuje body obrazu ve ktery´ch docha´zı´ ke zmeˇna´m obrazova´ fce. Hrana je vlastnost kazˇde´ho pixelu. Opera´tory pro detekci hran vycha´zejı´ z parcia´lnı´ho diferencia´lnı´ho opera´toru. Zajı´ma´me-li se pouze o velikost gradientu pouzˇ´ıva´ se cˇasto Laplaceu˚v opera´tor, aproximujı´cı´ druhou derivaci. Gradientnı´ch opera´toru˚ lze vyuzˇ´ıt i pro ostrˇenı´ obrazu – zdu˚razneˇnı´ vysoky´ch frekvencı´. Pro obraz f , ktery´ je vy´sledkem ostrˇenı´ obrazu g, platı´ f (i, j) = g(i, j) − C
S(i, j),
kde C je kladny´ soucˇinitel uda´vajı´cı´ sı´lu ostrˇenı´ a S(i, j) je hranovy´ opera´tor. Hranove´ opera´tory lze rozdeˇlit do dvou skupin: • Opera´tory aproximujı´cı´ derivace obrazove´ fce diferencı´ pomocı´ diskre´tnı´ konvoluce (Laplaceu˚v opera´tor, Robertsu˚v opera´tor). • Opera´tory zalozˇene´ na hleda´nı´ hran v mı´stech, kde druha´ derivace obrazove´ fce procha´zı´ nulou – inflexe (opera´tor Marra a Hildrethove´, Cannyho detektor). Robertsu˚v opera´tor pouzˇ´ıva´ okolı´ 2x2 (dosti male´ a tudı´zˇ je citlivy´ na sˇum): "
h1 =
1 0 0 −1
#
"
,
h2 =
a velikost gradientu se urcˇ´ı vztahem:
9
0 1 −1 0
#
|∇g(i, j)| = |g(i, j) − g(i + 1, j + 1)| + |g(i, j + 1) = g(i + 1, j)|. Sobelu˚v opera´tor le´pe aproximuje prvnı´ parcia´lnı´ derivace, proto je smeˇroveˇ za´visly´. Dveˇ masky pro okolı´ 3x3 jsou: 1 2 1 0 1 2 0 0 , h2 = −1 0 1 . h1 = 0 −1 −2 −1 −2 −1 0 Ostatnı´ch 8 masek vznikne jen pootocˇenı´m. Prˇedchozı´ opera´tory majı´ hlavnı´ nevy´hodu – za´vislost na sˇumu a na velikosti objektu˚ v obraze. Novy´ hranovy´ detektor se nazy´va´ hleda´nı´ pru˚chodu˚ nulou. Prakticky je jednodusˇsˇ´ı hledat pru˚chody druhe´ derivace nulou nezˇ maxima prvnı´ch derivacı´. Druha´ derivace obrazove´ fce se da´ velmi dobrˇe najı´t pomocı´ filtru s norma´lnı´m rozdeˇlenı´m. Druhou derivaci na´m poskytne Laplaceu˚v opera´tor. Prˇi jeho prˇ´ıme´m pouzˇitı´ jsou proble´my se sˇumem, dı´ky lineariteˇ operacı´ lze vsˇak zameˇnit porˇadı´ vyhlazova´nı´ Gaussovy´m filtrem G pomocı´ konvoluce ◦ a druhe´ derivace. Pro pru˚chody nulou potom platı´: ∇2 (G ◦ g) = (∇2 G) ◦ g = 0. Derivace Gaussova filtru ∇2 G se da´ spocˇ´ıtat prˇedem analyticky.
Obra´zek 4: Ilustrace pru˚chodu nulou. Cannyho hranovy´ detektor (podobny´ ∇2 G) realizuje hleda´nı´ nejlepsˇ´ıho rozlisˇenı´ hran. Je optima´lnı´ pro skokove´ hrany vu˚cˇi trˇem krite´riı´m. Detekcˇnı´ krite´rium zajisˇt’uje neopomenutı´ vy´znamny´ch hran. Lokalizacˇnı´ krite´rium minimalizuje rozdı´l mezi skutecˇnou a nalezenou pozicı´ hrany. Krite´rium jednoznacˇnosti zajisˇt’uje, aby detektor nereagoval vı´cekra´t na jednu hranu. Cannyho detektor se uzˇ´ıva´ dodnes uzavrˇel snahu o nalezenı´ idea´lnı´ho detektoru.
6
Analy´za 2D obrazu
Tato cˇa´st popisuje metody analy´zy obrazu. Jsou vynecha´ny metody klasifikace (automaticke´ho trˇ´ıdeˇnı´), ktere´ jsou obsahem jine´ ota´zky.
6.1 Segmentace Segmentace slouzˇ´ı k nalezenı´ objektu˚ v obraze – oddeˇlenı´ objektu od pozadı´. Pokud soubor nalezeny´ch oblastı´ jednoznacˇneˇ koresponduje s objekty vstupnı´ho obrazu, jde o kompletnı´ segmentaci, pokud 10
prˇ´ımo nesouhlası´, jde o cˇa´stecˇnou segmentaci. Pro kompletnı´ segmentaci je nezbytna´ spolupra´ce s vysˇsˇ´ı u´rovnı´ zpracova´nı´ a znalost ˇresˇene´ho proble´mu. Podle dominantnı´ vlastnosti vyuzˇ´ıvane´ pro segmentaci lze metody rozdeˇlit do trˇ´ı skupin: metody vyuzˇ´ıvajı´cı´ globa´lnı´ znalosti obrazu (reprezentovane´ obvykle histogramem), postupy vycha´zejı´cı´ z urcˇova´nı´ hranic mezi oblastmi a postupy vytva´rˇejı´cı´ oblasti. Segmentace prahova´nı´m Prahova´nı´ je nejrychlejsˇ´ı segmentacˇnı´ metodou, lze ji prova´deˇt v rea´lne´m cˇase. Je to transformace vstupnı´ho obrazu f na vy´stupnı´ bina´rnı´ obraz g dle vztahu: g(i, j) =
1 pro 0 pro
f (i, j) ≥ T, f (i, j) < T,
kde T je prˇedem urcˇena´ konstanta – pra´h a g(i, j) = 1 pro obrazove´ elementy na´lezˇ´ıcı´ objektu˚m. Spra´vna´ volba prahu je za´sadnı´ proble´m – lze ji urcˇit interaktivneˇ nebo automaticky (analy´zou histogramu). Neˇkdy je trˇeba pracovat s ru˚zny´m prahem v ru˚zny´ch cˇa´stech obrazu. Segmentace pomocı´ detekce hran Pouzˇ´ıva´ se neˇktery´ z hranovy´ch opera´toru˚. Nalezeny´ obraz hran je trˇeba nejprve prahovat. Pote´ na´sleduje dalsˇ´ı zpracova´nı´, ktere´ spojuje hrany do rˇeteˇzu˚, ktere´ odpovı´dajı´ pru˚beˇhu˚m hranic objektu˚. Zna´me-li vlastnosti tvaru˚ objektu˚ v obraze, je vy´hodne´ jich vyuzˇ´ıt – heuristicke´ sledova´nı´ hranice. Hrany nalezene´ hranovy´m opera´torem tvorˇ´ı uzly grafu a k hleda´nı´ hranic je mozˇne´ vyuzˇ´ıt postupu˚ umeˇle´ inteligence (heuristicke´ prohleda´va´nı´ grafu, A? ). K vyhleda´va´nı´ hranice se take´ pouzˇ´ıva´ Houghova transformace. Ta se pouzˇ´ıva´ v prˇ´ıpadeˇ, zˇe obraz obsahuje prˇedmeˇty zna´me´ho tvaru (a velikosti). Hledany´ prˇedmeˇt je parametrizova´n (naprˇ. prˇ´ımka ma´ rovnici se dveˇma parametry) a kazˇdy´ bod hrany „hlasuje“ do prostoru parametru˚ (akumula´tor) pro vsˇechny mozˇne´ objekty jimzˇ mu˚zˇe patrˇit. Objekty (jejich parametry) jsou potom urcˇeny maximy v akumula´toru. Segmentace naru˚sta´nı´ oblastı´ Metody naru˚sta´nı´ oblastı´ se pouzˇ´ıvajı´ v obrazech se sˇumem, v nichzˇ se hranice urcˇujı´ obtı´zˇneˇ. Vy´znamnou vlastnostı´ oblasti je jejı´ homogenita. Za´kladnı´ mysˇlenkou segmentace naru˚sta´nı´m oblastı´ je rozcˇlenit obraz do maxima´lnı´ch homogennı´ch souvisly´ch oblastı´. Krite´rium homogenity se mu˚zˇe opı´rat o jasove´ vlastnosti, texturu cˇi o vytva´rˇeny´ model obrazu. Pouzˇ´ıva´ se algoritmus spojova´nı´ oblastı´, ktere´ jsou dle krite´ria homogenity „podobne´“. Dalsˇ´ı mozˇnostı´ je algoritmus sˇteˇpenı´ oblastı´, ktery´ velke´ nehomogennı´ oblasti deˇlı´ na mensˇ´ı. Rovneˇzˇ je mozˇna´ kombinace obou postupu˚.
6.2
Popis objektu˚
K rozpozna´nı´ objektu˚ je potrˇebny´ jejich popis. Popis hranice objektu˚. Pouzˇ´ıvajı´ se ru˚zne´ metody: • aproximace u´secˇkami – seznam sourˇadnic krajnı´ch bodu˚, • rˇeteˇzove´ ko´dy – kroky sledova´nı´ hranice, 11
• krˇivka ϕ − s – spojity´ prˇ´ıpad rˇeteˇzove´ho ko´du, • Fourierovske´ popisovacˇe – koeficienty F-transformace, • de´lka hranice, • popis krˇivosti hranice, • popis segmentu˚ hranice Reprezentace oblastı´. Segmentovane´ oblasti je trˇeba nejprve identifikovat barvenı´m – prˇirˇazenı´ identifika´toru˚ jednotlivy´m oblastem. Da´le se pouzˇ´ıvajı´ tyto charakteristiky: • linea´rnı´ pole prˇ´ıslusˇnosti k oblasti, • velikost oblasti, • jas – strˇednı´ hodnota a rozptyl, • podlouhlost, pravou´hlost, vy´strˇednost, • projekce – vy´sˇka, sˇ´ırˇka, • smeˇr, • kompaktnost, • momenty, definovane´ vztahem mpq = • centra´lnı´ momenty, mpq =
RR ∞
−∞ (x
RR ∞
p q −∞ x y f (x, y)dx dy,
− xc )p (y − yc )q f (x, y)dx dy,
• konvexnı´ obal.
7
Analy´za pohybu
Z hlediska praxe lze nale´zt trˇi typy u´loh: 1. Detekce pohybu – opticky´ hlı´dacˇ, ostraha objektu˚ apod. 2. Sledova´nı´ trajektorie – cı´lem je nale´zt umı´steˇnı´ pohybujı´cı´ch se objektu˚, prˇ´ıpadneˇ sledova´nı´ jejich trajektoriı´ cˇi predikce dalsˇ´ı dra´hy. 3. Urcˇenı´ 3D vlastnostı´ objektu˚ Probı´ha´-li analy´za postupem za´visly´m na detekci pohybujı´cı´ch se objektu˚, je vy´hodne´ pouzˇ´ıvat na´sledujı´cı´ch prˇedpokladu˚ o pohybu tuhy´ch teˇles: a) Prˇedpoklad maxima´lnı´ rychlosti. b) Prˇedpoklad male´ho zrychlenı´ vzhledem k nenulove´ hmotnosti. c) Prˇedpoklad spolecˇne´ho pohybu tuhy´ch teˇles.
12
7.1
Rozdı´love´ metody analy´zy pohybu
Jednoducha´ detekce pohybu se prova´dı´ vy´pocˇtem rozdı´lu˚ mezi obrazy. Rozdı´lovy´ obraz je bina´rnı´ obraz takovy´, zˇe hodnoty nula prˇedstavujı´ sobeˇ odpovı´dajı´cı´ mı´sta dvou obrazu˚, v nichzˇ nedosˇlo k vy´znamne´ zmeˇneˇ (veˇtsˇ´ı nezˇ stanoveny´ pra´h) jasu mezi okamzˇiky snı´ma´nı´. Tı´m lze detekovat pohyb objektu jasoveˇ odlisˇne´ho od pozadı´. Z rozdı´love´ho obrazu nelze rozhodnout o smeˇru pohybu objektu˚, proto se uzˇ´ıva´ akumulativneˇ rozdı´lovy´ obraz. Hodnota akumulativnı´ho rozdı´lu rˇ´ıka´, kolikra´t se hodnota jasu na snı´mcı´ch posloupnosti lisˇila od hodnoty jasu v prvnı´m obraze. Jednotlive´ obrazy jsou prˇed prˇipocˇtenı´m k akumula´toru va´zˇeny va´hovy´mi koeficienty. Potom smeˇr monoto´nnı´ho na´ru˚stu hodnot v akumula´toru vypovı´da´ o smeˇru pohybu.
7.2
Opticky´ tok
Opticky´ tok zachycuje vsˇechny zmeˇny obrazu za cˇas dt. Kazˇde´mu bodu obrazu opticke´ho toku odpovı´da´ dvojrozmeˇrny´ vektor rychlosti, vypovı´dajı´cı´ o smeˇru a velikosti rychlosti pohybu v dane´m mı´steˇ obrazu (obra´zek 5). Vy´pocˇet opticke´ho toku je nutny´m prˇedpokladem zpracova´nı´ vysˇsˇ´ı u´rovneˇ, ktere´ dovoluje pracovat se staticky´m i pohyblivy´m umı´steˇnı´m pozorovatele, umozˇnˇuje urcˇit parametry pohybu, relativnı´ vzda´lenosti prˇedmeˇtu˚ v obraze apod. Urcˇenı´ opticke´ho toku vycha´zı´ z loka´lnı´ch vlastnostı´ obrazu.
Obra´zek 5: Opticky´ tok. Druhy pohybu, ktere´ se v dynamicky´ch obrazech mohou vyskytnout, lze popsat jako kombinaci cˇtyrˇ za´kladnı´ch pohybu˚ – translace v konstantnı´ vzda´lenosti, translace do da´lky, rotace v konstantnı´ vzda´lenosti a rotace kolma´ na osu pohledu. Prˇi analy´ze pohybu z opticke´ho toku lze uvedene´ za´kladnı´ pohyby od sebe odlisˇit aplikacı´ diferencia´lnı´ch opera´toru˚ na opticky´ tok.
7.3
Detekce vy´znamny´ch bodu˚
Zprˇ´ıstupneˇnı´m metody opticke´ho toku i pro obrazy snı´mane´ v cˇasovy´ch intervalech, ktere´ nelze povazˇovat za velmi male´, je analy´za pohybu na za´kladeˇ detekce vy´znamny´ch bodu˚ pohybujı´cı´ch se objektu˚. Jejı´m za´kladem je opeˇt vyrˇesˇit proble´m vza´jemne´ korespondence sobeˇ odpovı´dajı´cı´ch cˇa´stı´ pohybujı´cı´ch se objektu˚ v ru˚zny´ch cˇasovy´ch okamzˇicı´ch. Zna´me-li vza´jemnou korespondenci bodu˚ v obrazech snı´many´ch v ru˚zny´ch cˇasovy´ch okamzˇicı´ch, lze jizˇ snadno vytvorˇit obraz rychlostnı´ho pole. Prvnı´m krokem je nale´zt v posloupnosti takova´ mı´sta, ktera´ jsou vy´znamna´ – jsou co nejme´neˇ podobna´ sve´mu okolı´, vrcholy, hranice atd. Pro potrˇebu analy´zy pohybu jsou podstatne´ jen vy´znamne´ body jejichzˇ poloha se v cˇase meˇnı´. K jejich detekci lze u´speˇsˇneˇ pouzˇ´ıt rozdı´love´ metody. Druhy´m krokem je zjisˇteˇnı´ korespondence vy´znamny´ch bodu˚ mezi po sobeˇ na´sledujı´cı´mi obrazy, a tak postupneˇ vytvorˇit obraz rychlostnı´ho pole. Pro urcˇenı´ potenciona´lnı´ch korespondencı´ je vy´hodne´ uzˇ´ıt prˇedpoklad maxima´lnı´ 13
rychlosti pohybu, ktery´ vy´razneˇ omezı´ mnozˇinu potenciona´lnı´ch korespondujı´cı´ch bodu˚.
8
Analy´za 3D objektu˚
ˇ ´ıdı´cı´ strategie vedoucı´ Cı´lem za´kladnı´ u´lohy pocˇ´ıtacˇove´ho videˇnı´ je porozumeˇt objektu˚m v 3D sce´neˇ. R k porozumeˇnı´ obrazu lze rozdeˇlit na dveˇ skupiny: rˇ´ızenı´ zdola nahoru a rˇ´ızenı´ shora dolu˚. Oba rˇ´ıdı´cı´ mechanismy se nelisˇ´ı typem operacı´, ny´brzˇ porˇadı´m jejich vykona´va´nı´ a skutecˇnostı´, zda jsou aplikova´na na vsˇechna data nebo jen na data vybrana´.
8.1
ˇ ´ızenı´ obrazovy´mi daty – rˇ´ızenı´ zdola nahoru. R
Zpracova´nı´ postupuje od rastrove´ho obrazu k obrazu segmentovane´mu, k popisu a rozpozna´nı´ objektu˚ a oblastı´ obrazu. Vy´voj strategie zdola nahoru ovlivnila pra´ce D. Marra v 80. letech, inspirovana´ principy biologicke´ho videˇnı´. Pro rˇesˇenı´ u´lohy jsou pouzˇity cˇtyrˇi u´rovneˇ reprezentace sce´ny: Intenzitnı´ obraz – obrazova´ fce. Prvotnı´ na´cˇrtek uchova´va´ informaci podstatnou pro porozumeˇnı´ tvaru – hrany. 2.5D rozmeˇrny´ na´cˇrtek vyjadrˇuje vzda´lenost kazˇde´ho bodu obrazu od pozorovatele a loka´lnı´ orientaci povrchu. Plna´ 3D reprezentace objektu zachycuje objekt ve formeˇ vhodne´ k rozpozna´va´nı´. Reprezentace se opı´ra´ o geometricke´ vlastnosti objektu vyja´drˇene´ v sourˇadne´m syste´mu objektu. Tuto reprezentaci se dosud nedarˇ´ı uspokojiveˇ zı´skat. Zı´ska´nı´ 2.5D na´cˇrtku K zı´ska´nı´ 2.5D na´cˇrtku se pouzˇ´ıvajı´ metody „tvar z X“, kde X je jedna z neˇkolika mozˇny´ch technik – stereovideˇnı´, informace o pohybu, texturˇe, jasu, stı´nova´nı´ apod. Tvar ze sterea umozˇnˇuje zı´skat hloubkovou mapu ze dvou (neˇkdy i vı´ce, robustnost) obrazu˚. Meˇjme dveˇ kamery (obra´zek 6) s rovnobeˇzˇny´mi osami a zna´mou vzda´lenostı´. Najdeme-li k bodu leve´ kamery odpovı´dajı´cı´ bod prave´ kamery, lze zı´skat hloubku tohoto bodu od pozorovatele: z=
−2df − f, xL − xR
2d je vzda´lenost kamer, f jejich ohniskova´ vzda´lenost a xL a xR sourˇadnice zobrazeny´ch bodu˚. Stereo nenı´ jednoduchou u´lohou, potı´zˇe zpu˚sobuje korespondencˇnı´ proble´m – je obtı´zˇne´ automaticky najı´t odpovı´dajı´cı´ body. Pro hleda´nı´ korespondencı´ se cˇasto uzˇ´ıva´ informace o hrana´ch. Podobnou u´lohou jako tvar ze sterea je tvar z pohybu. Hloubkomeˇry (range finders) se deˇlı´ na aktivnı´ (vysı´lajı´ energii na meˇrˇenou sce´nu) a pasivnı´. Hloubkomeˇr mu˚zˇe pracovat na principu radaru (elmg. vlny nebo laser) nebo sonaru. Dalsˇ´ım pouzˇ´ıvany´m principem je triangularizace – hloubkomeˇr na principu prouzˇkove´ho osveˇtlenı´ (obra´zek 7). Prˇedmeˇt je osveˇtlen pruhem sveˇtla a pozorova´n kamerou z jine´ho mı´sta. Vza´jemna´ poloha kamery a zdroje sveˇtla
14
Obra´zek 6: Geometrie stereovideˇnı´.
Obra´zek 7: Hloubkomeˇr na principu prouzˇkove´ho osveˇtlenı´. (laser) je pevna´ a zna´ma´ a cela´ sestava se pohybuje prˇes cely´ prˇedmeˇt. Hloubkovou mapu lze vypocˇ´ıtat z deformace zobrazovane´ho prouzˇku na povrchu prˇedmeˇtu. Moire´ prouzˇky. Sce´na se osveˇtlı´ prˇes pravidelnou mrˇ´ızˇku. Dı´ky interferenci se na povrchu objektu objevı´ strˇ´ıdajı´cı´ se tmave´ a sveˇtle´ prouzˇku s vy´znamem vrstevnic. Tvar ze stı´nova´nı´, tvar z jasu. Jas za´visı´ na orientaci povrchu a poloze sveˇtelny´ch zdroju˚. Za zjednodusˇujı´cı´ch prˇedpokladu˚ (zna´ma poloha bodovy´ch zdroju˚ sveˇtla, Lambertovsky´ povrch) lze informaci o jasu pouzˇ´ıt k zjisˇteˇnı´ 3D tvaru. Tvar z textury vyuzˇ´ıva´ perspektivnı´ho zkreslenı´ pravidelny´ch opakujı´cı´ch se cˇa´stı´ povrchu. Orientace povrchu se hleda´ z gradientu textury.
8.2
ˇ ´ızenı´ podle vnitrˇnı´ho modelu – rˇ´ızenı´ shora dolu˚. R
Na za´kladeˇ znalostı´ vysˇsˇ´ı u´rovneˇ je vytvorˇen souhrn prˇedpokladu˚ a ocˇeka´vany´ch vlastnostı´, jejichzˇ pravdivost je oveˇrˇova´na v obrazovy´ch reprezentacı´ch ru˚zny´ch u´rovnı´ smeˇrem shora dolu˚ azˇ po pu˚vodnı´ obrazova´ data. Jedna´ se o verifikaci vytvorˇene´ho modelu.
15
Obra´zek 8: Interakce mezi cˇa´stmi videˇnı´ na za´kladeˇ 3D modelu. Proces zı´ska´nı´ senzorovy´ch dat I poskytuje obraz (hloubkovou mapu). Proces popisu˚ objektu˚ D poskytuje prˇ´ıznaky. Proces M slouzˇ´ı k zı´ska´nı´ plne´ho 3D modelu. Proces rozpozna´va´nı´ U hleda´ shodu mezi daty a modelem. Model v nalezene´ pozici se mu˚zˇe promı´tnout procesem R technikami pocˇ´ıtacˇove´ grafiky.
9 9.1
Geometrie pro pocˇ´ıtacˇove´ videˇnı´ Jedna kamera
Pro popis projekce kamery je vy´hodne´ pouzˇ´ıvat projektivnı´ geometrii (homogennı´ sourˇadnice). V homogennı´ch sourˇadnicı´ch lze vyja´drˇit posun i rotaci jednotneˇ maticovy´m na´sobenı´m. Je-li x = (x1 , x2 , x3 ) bod v 3D euklidovsky´ch sourˇadnicı´ch, potom jeho homogennı´ sourˇadnice jsou X = α(X1 , X2 , X3 , 1), kde α je libovolne´ rea´lne´ nenulove´ cˇ´ıslo. Prˇ´ımka je dua´lnı´ entita k bodu a zapı´sˇe se stejny´m zpu˚sobem, λ = (λ1 , λ2 , λ3 , λ4 ) (je to vlastneˇ norma´lovy´ vektor prˇ´ımky v projektivnı´m prostoru). Projekce bodu X sce´ny na bod u obrazu kamerou je linea´rnı´ projekce z projektivnı´ho prostoru dimenze 3 do projektivnı´ho prostoru dimenze 2 (obra´zek 9): αu = PX, kde P je projekcˇnı´ matice 3x4. Ta mu˚zˇe by´t rozlozˇena: P = K(R| − Rt), R je rotace a t je posun – transformace se sourˇadne´ho syste´mu sce´ny do sourˇadne´ho syste´mu kamery, K obsahuje vnitrˇnı´ parametry kamery (ohniskovou vzda´lenost, rozlisˇenı´, tvar stı´nı´tka) a reprezentuje transformaci ze soustavy kamery do soustavy obrazu. Projekcˇnı´ matici P lze zı´skat analyticky nebo meˇrˇenı´m – kalibracı´. Je trˇeba zna´t 3D sourˇadnice neˇkolika kalibracˇnı´ch bodu˚ a jejich projekci kamerou. Kalibrace pak prˇedstavuje rˇesˇenı´ (prˇeurcˇene´) maticove´ rovnice a rˇesˇ´ı se numericky´mi metodami (SVD a spol).
9.2
Syste´m vı´ce kamer
Necht’bod X sce´ny je pozorova´n K kamerami s projekcˇnı´mi maticemi P(1) azˇ P(K) : 16
Obra´zek 9: Geometrie linea´rnı´ perspektivnı´ kamery.
α(i) u(i) = P(i) X Jestlizˇe oznacˇ´ıme
p1 P = p2 p3 a eliminujeme-li α, mu˚zˇeme rovnice psa´t ve tvaru
u1 p2 − u2 p1 r u2 p3 − u3 p2 X = s X = 0 u3 p1 − u1 p3 t pro kazˇdou kameru. Rovnice jsou za´visle´, volı´me pouze dveˇ pro kazˇdou kameru a sestavı´me je do jedne´ matice:
... r(i) s(i) ...
X = AX = 0.
Tato rovnice musı´ platit pro nenulove´ X, tj hod(A) ≤ 3 a determinanty sub-matic rˇa´du 4 vybrane´ z A musı´ by´t nulove´. Oznacˇme determinant matice ze cˇtyrˇ rˇa´dku˚ jako [a, b, c, d]. Podle pocˇtu va´zany´ch pohledu˚ existujı´ trˇi skupiny vazebnı´ch podmı´nek pro syste´m vı´ce kamer: 1. Dva pohledy. Do sub-matice rˇa´du 4 vybereme dva rˇa´dky z jedne´ a dva rˇa´dky z druhe´ kamery: [r(1) , s(1) , r(2) , s(2) ] = 0. Tuto podmı´nku zapı´sˇeme (po neˇkolika u´prava´ch) jako: u(1)T Fu(2) = 0, kde F je fundamenta´lnı´ matice, obsahujı´cı´ vesˇkerou informaci o vza´jemne´ poloze dvou kamer. 17
2. Trˇi pohledy. Dva rˇa´dky jsou vybra´ny z jedne´ kamer, trˇetı´ rˇa´dek z jine´ kamery a cˇtvrty´ rovneˇzˇ z jine´ kamery. To da´va´ 12 skala´rnı´ch podmı´nek: [r(1) , s(1) , r(2) , r(3) ] [r(2) , s(2) , r(3) , r(1) ] [r(3) , s(3) , r(1) , r(2) ] .. .. .. . . .
!
= 0.
Kazˇdy´ determinant mu˚zˇe by´t prˇepsa´n jako trilinea´rnı´ funkce. Pouze cˇtyrˇi z teˇchto trilinearit jsou neza´visle´. Koeficienty lze sdruzˇit do trifoka´lnı´ho tenzoru, cozˇ je analogie fundamenta´lnı´ matice pro trˇi pohledy. Vy´hodneˇjsˇ´ı nezˇ da´vat do vztahu body je da´vat do vztahu bod u(1) a prˇ´ımky λ(2) a λ(3) : (2) (3) (1) Tijk λj λk ui = 0 3. Cˇtyrˇi pohledy. Kazˇdy´ rˇa´dek sub-matice je bra´n z jine´ kamery. To da´va´ 24 = 16 podmı´nek. Mu˚zˇe by´t zapsa´no jako kvadrilinea´rnı´ funkce s 81 neza´visly´mi koeficienty.
Literatura [1] V. Hlava´cˇ, M. Sˇonka. Pocˇ´ıtacˇove´ videˇnı´. Grada, Praha, 1992. [2] V. Marˇ´ık, O. Sˇteˇpa´nkova´, J. Lazˇansky´ a kolektiv. Umeˇla´ inteligence (2). Academia, Praha, 1997. [3] Milan Sˇonka, Va´clav Hlava´cˇ, Roger D. Boyle. Image Processing, Analysis and Machine Vision. Chapman and Hall, London, UK, first edition, 1993.
18
