Fakulta dopravní ČVUT v Praze. Identifikace zóny zájmu v obraze

ˇ Fakulta dopravn´ı CVUT v Praze

Bohumil Kováˇr Identifikace z´ ony z´ ajmu v obraze

1998

Prohl´ aˇ sen´ı

ˇ Cestnˇ e prohlaˇsuji, ˇze jsem diplomovou práci vypracoval samostatnˇe, s pouˇzit´ım uvedené literatury a za pˇrispˇen´ı vedouc´ıho diplomové práce.

..........................................

ˇ Fakulta dopravn´ı CVUT v Praze Identifikace z´ ony z´ ajmu v obraze Bohumil Kováˇr 1998 Kl´ıˇ cov´ a slova: poˇc´ıtaˇcové vidˇen´ı, zpracován´ı obrazu, zóna zájmu, segmentace, autonomn´ı vozidlo, dopravn´ı znaˇcky, silnice

Abstrakt

Tato práce je souˇc´ ast´ı projektu “Automatické rozpozn´ an´ı a klasifikace dopravn´ıch znaˇcek 2 – RS ”. C´ılem této diplomové práce je navrhnout vhodnou metodu pro ˇreˇsen´ı identifikace z´ ony z´ ajmu v obraze. Z´ ona z´ ajmu pˇredstavuje tu oblast v obraze, kde je moˇzné s velkou pravdˇepodobnost´ı oˇcekávat svislé dopravn´ı znaˇcen´ı. Zóna zájmu je v obraze rozpoznána na základˇe segmentace silnice. V této práci jsou popsány základn´ı segmentaˇcn´ı techniky a jejich vhodnost pro ˇreˇsen´ı dané problematiky. Metoda identifikace zóny zájmu, popsaná v této práci, byla experimentálnˇe ovˇeˇrena na reáln´ ych datech dopravn´ıch scén. V závˇeru této práce je uveden vlastn´ı algoritmus a jeho implementace.

Obsah ´ 1 Uvod 2 Poˇ c´ıtaˇ cov´ e vidˇ en´ı 2.1 Základn´ı pojmy . . . . . . . . . 2.2 Digitáln´ı obraz . . . . . . . . . 2.3 Operace pˇredzpracov´ an´ı obrazu 2.4 Popis objekt˚ u v obraze . . . . .

11

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

14 14 15 16 17

3 Z´ ona z´ ajmu – filosofie 18 3.1 Projekty autonomn´ıch vozidel . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1 Projekt CAPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1.2 Projekt VaMoRs . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4 Segmentace z´ ony z´ ajmu 4.1 Segmentace - u ´vod . . . . . . . . . . . . . . . . . . . 4.2 Segmentaˇcn´ı algoritmy . . . . . . . . . . . . . . . . . 4.2.1 Segmentace prahován´ım . . . . . . . . . . . . 4.2.2 Segmentace prostˇrednictv´ım hranové detekce 4.2.3 Barevná segmentace . . . . . . . . . . . . . . 4.3 Algoritmus . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Stanoven´ı homogenity povrchu vozovky . . . 4.3.2 Segmentace silnice v dopravn´ı scénˇe . . . . . 4.3.3 Revize v´ ysledku segmentace . . . . . . . . . . 4.3.4 Geometrick´ y model a stanoven´ı zóny zájmu .

. . . . . . . . . .

24 24 25 25 28 30 38 39 41 45 46

5 Experimenty a v´ ysledky 5.1 V´ ysledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47 48

6 Implementace 6.1 Objektovˇe orientovan´ y pˇr´ıstup . . . . . . . . . . . . . . . . . . . . . . . 6.2 Aplikace Zone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53 53 54

7 Z´ avˇ er

56

8

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

Seznam obr´ azk˚ u 1.1

Systém automatické klasifikace dopravn´ıch znaˇcek RS2 . . . . . . . . . .

12

3.1

Paraleln´ı architektura systému VaMoRs . . . . . . . . . . . . . . . . . .

23

4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.10 4.9 4.11

Urˇcen´ı hodnoty prahu z histogramu jasu . . . . . . . . . . . . . . Histogram intenzit jasu celého obrazu a povrchu silnice . . . . . . Predikce okraje silnice . . . . . . . . . . . . . . . . . . . . . . . . V´ ysledky segmentace prahován´ım (obrázek 012.bmp a 041.bmp) V´ ysledky hranové detekce . . . . . . . . . . . . . . . . . . . . . . Grafick´ a reprezentace modelu RGB . . . . . . . . . . . . . . . . . Grafick´ a reprezentace modelu HSV . . . . . . . . . . . . . . . . . Definice funkce s(P) a konstanty D pro S = 107 . . . . . . . . . . Velikost a pozice testované oblasti . . . . . . . . . . . . . . . . . Blokové schema algoritmu segmentace zóny zájmu v obraze . . . Zóna zájmu v obraze . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

26 27 28 29 29 31 32 34 39 40 46

5.1 5.2 5.3 5.4 5.5

Pˇr´ıklad scén, ve kter´ ych zóna zájmu nebyla stanovena . . . . V´ ysledky segmentace zóny zájmu v obraze – neznaˇcené silnice V´ ysledky segmentace zóny zájmu v obraze – znaˇcené silnice . V´ ysledky segmentace zóny zájmu v obraze – mˇesto . . . . . . V´ ysledky segmentace zóny zájmu v obraze – mˇesto . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

48 49 50 51 52

6.1 6.2

Aplikace segmentace zóny zájmu – Zone . . . . . . . . . . . . . . . . . . Ovládac´ı panel programu Zone . . . . . . . . . . . . . . . . . . . . . . .

54 55

9

. . . . .

. . . . .

Seznam tabulek 3.1

Pouˇzité senzory a jejich funkce . . . . . . . . . . . . . . . . . . . . . . .

20

4.1 4.2 4.3 4.4

Popisné statistiky . . . . . . . . . . . . . . . . . . . . . . Tabulka základn´ıch barev v systému RGB . . . . . . . . Vztah mezi hodnotou H a jménem barvy v modelu RGB ´ eˇsnost segmentace pˇri pouˇzit´ı r˚ Uspˇ uzn´ ych pˇr´ıznak˚ u . . .

27 31 32 35

10

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Kapitola 1

´ Uvod ˇ Druhá etapa studia na Fakultˇe dopravn´ı CVUT je projektovˇe orientovaná. To znamená, ˇze skupina student˚ u v rámci v´ yuky pracuje pod odborn´ ym veden´ım na konkrétn´ım problému a t´ım z´ısk´ av´ a teoretické, ale i praktické poznatky, které vyuˇzije v závˇeru studia pˇri vypracov´ an´ı diplomové práce. V roce 1995 jsem se zapojil projektu Zpracov´ an´ı obrazové informace v dopravˇe, spoleˇcného projektu Katedry aplikované maˇ ˇ tematiky FD CVUT a Katedry teorie obvod˚ u FEL CVUT. Projekt je podporován ˇ Grantovou agenturou CVUT a firmou Texas Instruments Deutschland GmbH/Freising. V pr˚ ubˇehu následuj´ıc´ıch dvou let jsem se seznámil s mnoha algoritmy zpracován´ı obrazu a poˇc´ıtaˇcového vidˇen´ı. Na diplomové práci jsem pracoval od bˇrezna roku 1997. Rozvoj v´ ypoˇcetn´ı techniky v posledn´ım desetilet´ı dvacátého stolet´ı umoˇznil realizaci problém˚ u a rozvoj technologi´ı, které byly jeˇstˇe pˇred nˇekolika lety pro svou komplikovanost neuskuteˇcnitelné. Tento rozvoj se samozˇrejmˇe t´ yká i dopravy a je zvláˇstˇe patrn´ y v silniˇcn´ı dopravˇe. V Evropˇe existuje nˇekolik projekt˚ u podporovan´ ych Evropskou uni´ı, které maj´ı zaveden´ım nov´ ych technologi´ı zv´ yˇsit bezpeˇcnost automobilové dopravy a zároveˇ n zv´ yˇsit propustnost infrastruktury, sn´ıˇzit zat´ıˇzen´ı ˇzivotn´ıho prostˇred´ı a celkovˇe zv´ yˇsit ekonomiku dopravy. Obdobné projekty prob´ıhaj´ı i v Japonsku a USA. Projekt Zpracov´ an´ı obrazové informace zaˇcal na Fakultˇe elektrotechnické jeˇstˇe pˇred rokem 1995. V té dobˇe Tom´ aˇs Zikmund pouˇzil algoritmus zaloˇzen´ y na lokáln´ıch orientac´ıch pro detekci geometrick´ ych tvar˚ u, zvláˇstˇe s ohledem na dopravn´ı znaˇcky, v ploˇse obrazu. [12]. Tento algoritmus tvoˇr´ı základ systému RS2 – Road Sign Recognition System. Systém RS2 je moˇzné rozloˇzit na tˇri samostané subsystémy se spoleˇcn´ ym rozhran´ım. Jedná se o • Identifikace z´ ony z´ ajmu v obraze – tento subsystém ve vstupn´ım obraze vyznaˇc´ı regiony, ve kter´ ych je moˇzné s velkou pravdˇepodobnost´ı oˇcekávat dopravn´ı znaˇcky, • Rozpozn´ an´ı tvaru dopravn´ıch znaˇcek – tento modul ve vstupn´ım obraze nacház´ı geometrické tvary shodné s dopravn´ımy znaˇckami, a jejich polohu a velikost poskytuje posledn´ımu modulu, • Klasifikace dopravn´ıch znaˇcek – tento modul ovˇeˇruje, zda nalezen´ y geometrick´ y tvar reprezentuje dopravn´ı znaˇcku. V kladném pˇr´ıpadˇe provede jej´ı u ´plnou klasifikaci. C´ılem této diplomové práce je popsat v´ yvoj algoritm˚ u Identifikace z´ ony z´ ajmu v obraze tak, jak jsou implementované v systému RS2 . Zónou zájmu rozum´ım ty oblasti, 11

Obr´ azek 1.1: Systém automatické klasifikace dopravn´ıch znaˇcek RS2

12

ˇ ˇ ˇ kde se dle norem CSN 01 8020, CSN 73 6101 a CSN 73 6110 m˚ uˇze vyskytovat svislé ˇ dopravn´ı znaˇcen´ı. Dle normy CSN 73 6101 se dopravn´ı znaˇcky osazuj´ı: 1. na znaˇckov´ ych sloupc´ıch nebo konstrukc´ıch um´ıstˇen´ ych na nezpevnˇen´ ych ploch´ ach nebo svaz´ıch tˇelesa silniˇcn´ı komunikace, 2. na portálov´ ych konstrukc´ıch nad j´ızdn´ımy pásy, které mus´ı respektovat pr˚ ujezdné ˇ v´ yˇsky a bezpeˇcnostn´ı vzdálenosti podle CSN 73 6201. Pˇritom nesm´ı ˇz´ adná jejich ˇc´ ast zasahovat do volné (popˇr. do d´ılˇc´ı volné) ˇs´ıˇrky nebo voln´ ych v´ yˇsek silniˇcn´ı komunikace. Pˇri definován´ı problému rozpoznáván´ı dopravn´ıch znaˇcek byla problematika omezena na bod 1, na pravou ˇcást silniˇcn´ı komunikace. Algoritmy identifikace zóny zájmu byly navrˇzené s ohledem na snadné rozˇs´ıˇren´ı, tak aby ˇ pokryly celou problematiku osazován´ı dopravn´ıch znaˇcek dle normy CSN 73 6101. Z´ ona zájmu je definov´ ana na základˇe segmentace povrchu vozovky a geometrického modelu silnice v dopravn´ı scénˇe. Ostatn´ı projekty, které ˇreˇs´ı problémy autonomn´ıch vozidel (kapitola 3.1) pˇristupuj´ı k rozpoznán´ı silnice odliˇsnˇe. Informace o poloze silnice v obraze je z´ısk´ ana na základˇe hranové detekce vod´ıc´ıho prouˇzku. T´ım se problematika zuˇzuje pouze na dobˇre znaˇcené silnice s nepoˇskozen´ ym povrchem. Po prostudov´ an´ı jiˇz implementovan´ ych metod jsem se rozhodl problematiku rozˇs´ıˇrit o segmentaci neznaˇcených silniˇcn´ıch komunikac´ı, s t´ım, ˇze na povrch (texturu) vozovky nejsou kladeny ˇz´ adné speciáln´ı poˇzadavky1 . Vyvinuté algoritmy jsou natolik obecné, ˇze je je moˇzné po drobn´ ych u ´prav´ ach pouˇz´ıt i pro ˇreˇsen´ı dalˇs´ıch problém˚ u autonomn´ıch vozidel (navigace, steering, . . . ). Vˇsechny testované algoritmy popsané v kapitole 4.2, byly vyv´ıjené tak, aby jejich v´ ypoˇcetn´ı nároky byly obdobné, nebo niˇzˇs´ı, neˇz v algoritmech pouˇzit´ ych v konkurenˇcn´ıch projektech [14], [13]. Algoritmy, které tvoˇr´ı systém RS2 , byly navrhovány s pˇrihlédnut´ım k implementaci v reálném ˇcase prostˇrednictv´ım signálového procesoru firmy Texas Instruments TMS320C80. Pˇri v´ yvoji byl pro d´ılˇc´ı simulace pouˇzit systém Matlab, vlastn´ı implementace je provedena v jazyce C/C++ a to zejména pro relativnˇe snadnou pˇrenositelnost algoritm˚ u do prostˇred´ı signálového procesoru. V souˇcasné dobˇe je dokonˇcen v´ yvoj algoritm˚ u v programovac´ım jazyku C++ a prob´ıhá paralelizace aplikace a implementace v prostˇred´ı signálového procesoru.

1

vlastn´ı definice problému a omezen´ı problematiky je uvedeno v kapitole 4.3

13

Kapitola 2

Poˇ c´ıtaˇ cov´ e vidˇ en´ı C´ılem této kapitoly nen´ı glob´ aln´ı výklad z´ akladn´ıch pojm˚ u a algoritm˚ u poˇc´ıtaˇcového vidˇen´ı, ale definov´ an´ı pojm˚ u a element´ arn´ıch algoritm˚ u, které budou pouˇz´ıvané v n´ asleduj´ıc´ıch kapitol´ ach. Detailn´ı výklad poˇc´ıtaˇcového vidˇen´ı a zde popisovaných témat je moˇzné z´ıskat napˇr. v [3], [4], [7].

2.1

Z´ akladn´ı pojmy

Poˇc´ıtaˇcové vidˇen´ı je discipl´ına, která se snaˇz´ı technick´ ymi prostˇredky alespoˇ n ˇcásteˇcnˇe napodobit lidské vidˇen´ı. Zrak je pro ˇclovˇeka zdrojem pˇreváˇzné vˇetˇsiny informac´ı o okoln´ım svˇetˇe. S t´ım souvis´ı i to, ˇze vizuáln´ı informaˇcn´ı komplex je nejsloˇzitˇejˇs´ı ze vˇsech smyslov´ ych komplex˚ u lidského mozku ([25] str. 169 - 189) . Teoreticky, ale i technicky jsou zvládnuty jen velmi jednoduché problémy. Postupy poˇc´ıtaˇcového vidˇen´ı jsou znaˇcnˇe sloˇzité. Kaˇzd´ y algoritmus zpracován´ı a interpretace obrazu je obvykle moˇzné dekomponovat na niˇzˇs´ı a vyˇsˇs´ı u ´roveˇ n. C´ılem niˇzˇs´ı u ´rovnˇe je analyzovat vstupn´ı dvojrozmˇerná obrazová data ˇc´ıselného charakteru a naj´ıt kvalitativn´ı informace potˇrebné pro algoritmy vyˇsˇs´ı u ´rovnˇe. Postupy niˇzˇs´ı u ´rovnˇe se pouˇz´ıvaj´ı napˇr´ıklad pro potlaˇcen´ı ˇsumu v obraze, rozpoznáván´ı jednoduch´ ych obrazc˚ u v obraze apod. Pro niˇzˇs´ı u ´roveˇ n se ˇcasto pouˇz´ıvá název zpracován´ı obrazu (image processing). Postupy vyˇsˇs´ı u ´rovnˇe jsou typické pouˇzit´ım nároˇcn´ ych algoritm˚ u expertn´ıch systém˚ u a technik umˇelé inteligence. Vyˇsˇs´ı u ´roveˇ n je oznaˇcována jako poˇc´ıtaˇcové vidˇen´ı (computer vision). Postup zpracován´ı a rozpoznán´ı obrazu je moˇzné dekomponovat do nˇekolika základn´ıch krok˚ u. Jednotlivé u ´rovnˇe zpracován´ı obrazu spolu sovisej´ı a je moˇzné ˇr´ıci, ˇze bez kvalitn´ıch algoritm˚ u niˇzˇs´ı u ´rovnˇe by nebylo moˇzné provést postupy vyˇsˇs´ı u ´rovnˇe, zvláˇstˇe pak porozumˇen´ı obsahu obrazu. Základn´ımy kroky zpracován´ı obrazu jsou: 1. sn´ım´ an´ı a digitalizace obrazu, 2. pˇredzpracov´ an´ı 3. segmentace obrazu 4. popis objekt˚ u 5. porozumˇen´ı obsahu obrazu.

14

Prvn´ım krokem ve zpracován´ı obrazu je sn´ımán´ı, digitalizace a uloˇzen´ı obrazu v ˇc´ıselné podobˇe do poˇc´ıtaˇce. Pˇri sn´ımán´ı se pˇrevádˇej´ı vstupn´ı optické veliˇciny na elektrick´ y signál spojit´ y v ˇcase. Vstupn´ı optickou veliˇcinou m˚ uˇze b´ yt jas, intenzita tepelného nebo jiného záˇren´ı. Sn´ımat je moˇzné v jednom nebo v´ıce spektráln´ıch pásmech. Digitalizac´ı se pˇrev´ ad´ı vstupn´ı spojit´ y signál do diskrétn´ı podoby. Vstupn´ı signál je popsán funkc´ı f (i, j), jej´ıˇz funkˇcn´ı hodnota pˇredstavuje velikost jasu (nebo jiné veliˇciny). Tento signál je vzorkov´ an a kvantov´ an a v´ ysledkem je matice pˇrirozen´ ych ˇc´ısel, která popisuje obraz. Jednomu prvku této matice se ˇr´ıká obrazov´ y element (picture element – pixel ). Druh´ ym krokem je pˇredzpracován´ı obrazu. C´ılem pˇredzpracován´ı je potlaˇcit ˇsum a jiné poruchy vzniklé pˇri pˇrenosu a digitalizaci. Pˇredzpracován´ım je také moˇzné zv´ yraznit pro nás zaj´ımavé (pro dalˇs´ı algoritmus d˚ uleˇzité) rysy obrazu. Tˇret´ım a asi nejtˇeˇzˇs´ım krokem postupu zpracován´ı obrazu je segmentace, která umoˇzn ˇuje v obraze vyhledat objekty, které jsou pro nás z pohledu dalˇs´ıho zpracován´ı zaj´ımavé. Pˇri segmentaci se pouˇz´ıvá znalosti interpretovaného obrazu (semantika). Segmentaci a segmentaˇcn´ım algoritm˚ um bude vˇenována kapitola 4.2. ˇ Ctvrt´ ym krokem postupu je popis nalezen´ ych objekt˚ u v obraze. Lze je popsat kvantitativnˇe za pomoci souboru ˇc´ıseln´ ych charakteristik nebo kvalitativnˇe pomoc´ı relac´ı mezi jednotliv´ ymi objekty. Posledn´ım krokem v tomto postupu je porozumˇen´ı obsahu obrazu. Ve skuteˇcnosti se vˇetˇsinou jedná pouze o klasifikaci segmentovan´ ych objekt˚ u do nˇekolika tˇr´ıd. Porozumˇen´ı obrazu nebo proces rozhodov´ an´ı na základˇe informac´ı obsaˇzen´ ych v obraze je v souˇcasné dobˇe moˇzn´ y pouze u nˇekolika triviáln´ıch problém˚ u (ve srovnán´ı se schopnostmi ˇclovˇeka).

2.2

Digit´ aln´ı obraz

Kaˇzd´ y obraz m˚ uˇze b´ yt popsán dvourozmˇernou funkc´ı f (x, y) jej´ıˇz funkˇcn´ı hodnota popisuje hodnotu jasu nebo jiné optické veliˇciny na souˇradnic´ıch x a y. Funkci f (x, y) se obvykle ˇr´ık´ a obrazov´ a funkce. V této práci bude digitáln´ı obraz reprezentován jako FP ×Q = [f (x, y)]P ×Q

(2.1)

kde P × Q jsou rozmˇery obrazu a f (x, y) ∈ GL = {0, 1, . . . , L − 1} je mnoˇzina funkˇcn´ıch hodnot. Vˇetˇsina systém˚ u pro digitáln´ı zpracován´ı obrazu pouˇz´ıvá kvantován´ı do L stejn´ ych interval˚ u. Pro reprezentaci informace o obrazovém elementu vˇetˇsinou postaˇcuje pouˇzit´ı 8 bit˚ u (pro monochromatick´ y obraz). Pak L = 28 = 256. Pouze pˇri zpracován´ı barevného obrazu se jeden vzorek reprezentuje 16, 24 nebo dokonce 32 bity. V pˇr´ıpadˇe, ˇze byl vstupn´ı obraz sn´ım´ an v nˇekolika spektráln´ıch pásmech (nejˇcastˇeji RGB) pak kaˇzdé spektráln´ı pásmo budeme popisovat obrazovou funkc´ı fi (x, y), kde i ∈ {R, G, B}. D˚ uleˇzitou informaci o digitáln´ım obrazu udává vzd´ alenost mezi dvˇema obrazov´ ymi elementy se souˇradnicemi (i, j) a (k, l). M˚ uˇzeme ji definovat nˇekolika zp˚ usoby na základˇe teorie metrick´ ych prostor˚ u. Intuitivn´ı a v matematice obvyklá Euklidova vzdálenost DE =

q

(i − k)2 + (j − l)2

(2.2)

je oproti ostatn´ım metrikám v´ ypoˇcetnˇe nároˇcnˇejˇs´ı, ale jej´ı pouˇzit´ı pˇrináˇs´ı lepˇs´ı v´ ysledky ve srovn´ an´ı s definicemi D8 = max{|i − k|, |j − l|}

(2.3) 15

D4 = |i − k| + |j − l|

(2.4)

V´ yznamnou lokáln´ı informac´ı o obrazu lze z´ıskat pomoc´ı hran. Hrana je vlastnost´ı obrazového elementu a jeho lokáln´ıho okol´ı. Je urˇcena velikost´ı a smˇerem. Velikost odpov´ıd´ a modulu gradientu spojité obrazové funkce v pˇr´ısluˇsném pixelu a gradient ukazuje smˇer nejvˇetˇs´ıho r˚ ustu obrazové funkce (t.j. od ˇcerné k b´ılé). Za pˇredpokladu, ˇze objekty v obraze m˚ uˇzeme charakterizovat jako mnoˇziny obrazov´ ych element˚ u s pˇribliˇznˇe stejn´ ym jasem, pak hranice objekt˚ u jsou v m´ıstech s v´ yznamnou zmˇenou jasu. Pro detekci hran v obraze slouˇz´ı napˇr´ıklad gradientn´ı operátory [3]. Z´ akladn´ı pˇredstavu o rozdˇelen´ı jednotliv´ ych jasov´ ych u ´rovn´ı z´ıskáme pomoc´ı histogramu. Histogram jasu je vektor (v pˇr´ıpadˇe barevného obrazu matice) jehoˇz poˇcet prvk˚ u je roven poˇctu jasov´ ych u ´rovn´ı. Hodnota kaˇzdého prvku odpov´ıdá ˇcetnosti bod˚ u pˇr´ısluˇsného jasu v obraze. Histogram b´ yvá zobrazován jako sloupcov´ y graf. Jedná se o nejsnaˇzˇs´ı metodu, pomoc´ı které z´ıskáme pˇrehled o rozloˇzen´ı jasu (pˇr´ıpadnˇe barev) v obraze. Z´ıskané informace je moˇzné vyuˇz´ıt v pˇredzpracován´ı obrazu, pˇr´ıpadnˇe pˇri segmentaci.

2.3

Operace pˇ redzpracov´ an´ı obrazu

Pˇredzpracov´ an´ı obrazu je spoleˇcn´ y název pro operace niˇzˇs´ı u ´rovnˇe. C´ılem b´ yvá zvláˇstˇe potlaˇcen´ı ˇsumu a zv´ yraznˇen´ı informace, která je d˚ uleˇzitá pro sémantick´ y popis obrazu. Jednou z operac´ı lokáln´ıho pˇredzpracován´ı je filtrace obrazu. Podle u ´ˇcelu je moˇzné filtraci rozdˇelit na dvˇe skupiny – vyhlazov´ an´ı obrazu (potlaˇcen´ı ˇsumu) a gradientn´ı operace (zv´ yrazˇ nován´ı hran). Lokáln´ı pˇredzpracován´ı pˇriˇrazuje v´ ysledn´ y jas bodu na základˇe v´ ypoˇct˚ u jasu v lokáln´ım okol´ı. Tento v´ ypoˇcet (transformace) m˚ uˇze b´ yt lineárn´ı nebo nelineárn´ı. Lineárn´ı kombinace poˇc´ıtaj´ı v´ yslednou hodnotu jasu v bodˇe (i, j) jako lineárn´ı kombinaci jas˚ u v okol´ı O vstupn´ıho obrazu g() s váhov´ ymi koeficienty h() f (i, j) =

X

(m,n)∈O

h(i − m, j − n)g(m, n).

(2.5)

Vztah (2.5) je dvojrozmˇern´ a diskrétn´ı konvoluce s konvoluˇcn´ım jádrem h. Toto konvoluˇcn´ı jádro b´ yv´ a nˇekdy oznaˇcováno jako konvoluˇcn´ı maska, v teorii filtr˚ u jako impulsn´ı odezva filtru. V´ ypoˇcetnˇe nejsnaˇzˇs´ı operac´ı pro vyhlazován´ı obrazu je prosté lokáln´ı pr˚ umˇerován´ı. Filtrace pr˚ umˇerov´ an´ım je pˇr´ıklad diskrétn´ı konvoluce. Napˇr´ıklad pro lokáln´ı okol´ı 3 × 3 je konvoluˇcn´ı maska 



1 1 1 1  h=  1 1 1  9 1 1 1

(2.6)

Hranice objekt˚ u v obraze (hrany) se vyznaˇcuj´ı náhl´ ymi zmˇenami jasové funkce. Operátory pro detekci a ohodnocen´ı hran v digitáln´ım obraze [4] vycházej´ı z parciáln´ıho diferenci´ aln´ıho operátoru. Velikost gradientu je dána vztahem |grad f | =

s

∂f ∂x

2

+

∂f ∂y

2

(2.7) 16

druhou sloˇzkou urˇcuj´ıc´ı gradient je smˇer φ = arctan

∂f ∂f / ∂x ∂y

,

∂f 6= 0. ∂y

(2.8)

V digitáln´ım obrazu jsou gradientn´ı operátory aproximovány diskrétn´ı konvoluc´ı. Mezi nejˇcastˇeji pouˇz´ıvané operátory patˇr´ı Roberts˚ uv operátor, Laplace˚ uv operátor a Sobel˚ uv oper´ ator. Konvoluˇcn´ı maska Sobelova operátoru pro dva z osmi smˇer˚ u je dána konvoluˇcn´ımi maticemi 



1 2 1   h1 =  0 0 0 , −1 −2 −1

 

h2 = 

1 2 1



0 −1  0 −2  . 0 −1

(2.9)

V algoritmech zpracov´ an´ı obrazu se gradientn´ı operátory pouˇz´ıvaj´ı zvláˇstˇe na vyhled´ av´ an´ı hran a ostˇren´ı obrazu. Vhodn´ y v´ ybˇer konvoluˇcn´ıho jádra b´ yvá zaloˇzen na experimentech, popˇr. znalosti kmitoˇctov´ ych vlastnost´ı obrazového signálu. Srovnán´ı v´ ypoˇcetn´ı nároˇcnosti zde uveden´ ych gradientn´ıch operátor˚ u a dalˇs´ıch nejv´ıce pouˇz´ıvan´ ych je moˇzné nalézt v [5].

2.4

Popis objekt˚ u v obraze

Popis objekt˚ u1 v obraze je d˚ uleˇzit´ y pro následuj´ıc´ı algoritmy, zvláˇstˇe pak pro rozpoznáv´ an´ı. Existuje ˇrada metod, které je moˇzné pouˇz´ıt pro popis nalezen´ ych objekt˚ u. Mezi nˇe patˇr´ı popis hranic objekt˚ u, popis oblasti (traru) a popis povrchu (textury). Hranice objekt˚ u je ve vˇetˇsinˇe pˇr´ıpad˚ u moˇzné aproximovat pomoc´ı u ´seˇcek nebo polynom˚ u. Tomuto popisu se ˇr´ık´ a vektorizace. K popisu hranic sloˇzitˇejˇs´ıch objekt˚ u se pouˇz´ıvaj´ı speciáln´ı abecedy s vlastn´ı sematikou. Popis tvaru oblasti b´ yvá velice d˚ uleˇzit´ y pro klasifikaci objekt˚ u. K popisu tvaru se pouˇz´ıvaj´ı základn´ı atributy objektu jako velikost, jasové vlastnosti, excentricita, podlouhlost, pravo´ uhlost, nekompaktnost a v pˇr´ıpadˇe statistického popisu momenty. Textura [6] pˇredstavuje v obraze (nebo jeho ˇcásti) relativn´ı pravidelnost svázanou z element˚ u. Tyto elementy jsou naz´ yvány texely – texturn´ı elementy. Pro popis textury se pouˇz´ıvaj´ı statistické metody a frekvenˇcn´ı anal´ yza obrazové funkce.

1

Segmentaˇcn´ım algoritm˚ um, které se pouˇz´ıvaj´ı pro extrakci objekt˚ u je vˇenov´ ana kapitola 4.2

17

Kapitola 3

Z´ ona z´ ajmu – filosofie Pro algoritmy poˇc´ıtaˇcového vidˇen´ı je typická jejich znaˇcná v´ ypoˇcetn´ı nároˇcnost. I velmi jednoduché aplikace sv´ ymi poˇzadavky ˇcasto pˇrevyˇsuj´ı moˇznosti konvenˇcn´ıch poˇc´ıtaˇc˚ u. Napˇr´ıklad bˇeˇzn´ y monochromatick´ y televizn´ı signál digitalizovan´ y do obrazu o rozliˇsen´ı 512 × 512 obrazov´ ych bod˚ u pˇri 256 jasov´ ych u ´rovn´ıch a 25 sn´ımc´ıch za sekundu pˇredstavuje datov´ y tok 6.5 MB/s. Kromˇe znaˇcného datového toku algoritmy poˇc´ıtaˇcového vidˇen´ı ˇcasto obsahuj´ı operace jako je konvoluce a v´ ypoˇcty s rozsáhl´ ymi maticemi. Tyto operace jsou na konvenˇcn´ıch poˇc´ıtaˇc´ıch relativnˇe pomalé a bez speciáln´ıch procesor˚ u je velmi tˇeˇzké programovat aplikace zpracován´ı obrazu tak, aby pracovaly v reálném ˇcase. I to je pˇr´ıˇcinou toho, ˇze se v aplikac´ıch poˇc´ıtaˇcového vidˇen´ı zpracovávaj´ı ˇcasto jen statické obrazy. Sn´ıˇzen´ı datového toku a t´ım i v´ ypoˇcetn´ıch nárok˚ u m˚ uˇze b´ yt doc´ıleno nˇekolika zp˚ usoby. Vhodnou metodou b´ yvá podvzorkován´ı obrazu a t´ım sn´ıˇzen´ı rozliˇsen´ı. Sn´ıˇzen´ım rozliˇsen´ı ovˇsem ztrác´ıme detaily, a t´ım zhorˇsujeme rozpoznávac´ı schopnost dalˇs´ıch algoritm˚ u, zvláˇstˇe pak klasifikaci segmentovan´ ych objekt˚ u. Dalˇs´ım ˇreˇsen´ım tohoto problému m˚ uˇze b´ yt pouˇzit´ı pyramid´ aln´ı struktury pro reprezentaci obrazu. To znamená, ˇze obraz je uchováván v nˇekolika rozliˇsen´ıch, od nejvyˇsˇs´ıho z´ıskaného kamerou aˇz po nejniˇzˇs´ı, z´ıskané nˇekolikanásobn´ ym podvzorkován´ım p˚ uvodn´ıho obrazu. Algoritmy poˇc´ıtaˇcového vidˇen´ı prob´ıhaj´ı na nejniˇzˇs´ım moˇzném rozliˇsen´ı a pouze v pˇr´ıpadˇe nutnosti pˇrecházej´ı na rozliˇsen´ı vyˇsˇs´ı. Pˇr´ıkladem m˚ uˇze b´ yt segmentace na objekty v n´ızkém aˇz stˇredn´ım rozliˇsen´ı a poté klasifikace do tˇr´ıd v nejvyˇsˇs´ım rozliˇsen´ı. Pouˇzit´ı pyramid´ aln´ı struktury rovnˇeˇz umoˇzn ˇuje rozpoznán´ı objekt˚ u v libovolné velikosti (je tedy invariantn´ı v˚ uˇci velikosti) [15]. Z tohoto d˚ uvodu je pyramidáln´ı struktura pouˇzita pˇri rozpoznáván´ı geometrick´ ych tvar˚ u v obraze v systému RS2 . ˇ Casto pouˇz´ıvanou moˇznost´ı je proveden´ı anal´ yzy obrazu a t´ım z´ıskán´ı dalˇs´ıch informac´ı o scénˇe, které mohou b´ yt pouˇzity jako apriorn´ı informace v dalˇs´ıch algoritmech systému. Tyto informace mohou b´ yt z´ıskány predikc´ı podobnˇe jako v systému VaMoRs (kapitola 3.1.2), nebo segmentac´ı, tak jako v této diplomové práci. Z´ onou z´ ajmu rozum´ım oblasti v obraze, z´ıskané pomoc´ı rychl´ ych algoritm˚ u, ve kter´ ych je moˇzné s velkou pravdˇepodobnost´ı oˇcekávat objekty, které se snaˇz´ıme rozpoznat a klasifikovat – objekty z´ ajmu. Systém RS2 se sklád´ a ze tˇr´ı ˇcást´ı. C´ılem je implementace algoritm˚ u v prostˇred´ı signálového procesoru a bˇeh systém˚ u v reálném ˇcase. Subsystém Rozpozn´ an´ı geometrických tvar˚ u v obraze je velmi nároˇcn´ y na v´ ypoˇcetn´ı v´ ykon a kapacitu operaˇcn´ı pamˇeti poˇc´ıtaˇce. Z tohoto d˚ uvodu jsme jsme se rozhodli systém rozˇs´ıˇrit o segmentaci zóny zájmu a t´ım sn´ıˇzit v´ ypoˇcetn´ı nároky systému. 18

3.1

Projekty autonomn´ıch vozidel

Celosvˇetovˇe prob´ıh´ a nˇekolik projekt˚ u jejichˇz c´ılem je autonomn´ı vozidlo – automobil, kter´ y je schopn´ y bez zásahu ˇridiˇce projet stanovenou trasu. Protoˇze se jedná o velmi komplikovan´ y problém, jsou v souˇcasné dobˇe ˇreˇsené d´ılˇc´ı problémy. V následuj´ıc´ıch kapitolách budou pˇribl´ıˇzeny nˇekteré prob´ıhaj´ıc´ı projekty a t´ım i problematika autonomn´ıho vozidla. Jiˇz nyn´ı je vyvynuto nˇekolik subsystém˚ u autonomn´ıho vozidla, které se ˇcasto ozna1 ˇcuj´ı jako DSS . DSS si m˚ uˇzeme pˇredstavit jako lidského spolujezdce v automobilu – sleduje ˇridiˇce, automobil, oblast pˇred a za vozidlem, naviguje a informuje ˇridiˇce o v´ yskytu kritick´ ych situac´ı. Velmi dobr´ ych v´ ysledk˚ u bylo dosaˇzeno v rámci evropského EUREKA projektu PROMETHEUS (PROgraMme for a European Traffic with Highest Efficiency and Unprecedented Safety, 1986 – 1994). Obdobné projekty byly realizovány i v Japonsku a USA (napˇr´ıklad IVHS – Intelligent Vehicles Highway System). Vˇsechny projekty autonomn´ıch vozidel pouˇz´ıvaj´ı ve velké m´ıˇre algoritmy zpracován´ı obrazu a poˇc´ıtaˇcového vidˇen´ı. Mezi základn´ı operace poˇc´ıtaˇcového vidˇen´ı v systémech DSS je detekce, sledován´ı silnice a objekt˚ u na n´ı. Je bezpodm´ıneˇcnˇe nutné, aby vˇsechny systémy pracovaly v reálném ˇcase. Toho je moˇzné dosáhnout pouze za pouˇzit´ı tˇech nejv´ ykonnˇejˇs´ıch pracovn´ıch stanic. I z tˇechto d˚ uvod˚ u jeˇstˇe nejsou DSS systémy zaloˇzené na algoritmech zpracován´ı obrazu souˇc´ ast´ı automobil˚ u. DSS je moˇzné dále rozdˇelit na nˇekolik subsystém˚ u, které pln´ı specifické, pro provoz autonomn´ıho vozidla nutné u ´lohy: 1. Z´ akladn´ı navigace – sledov´ an´ı vod´ıc´ıho prouˇzku. V prob´ıhaj´ıc´ıch projektech (viz. n´ asleduj´ıc´ı kapitoly) se osvˇedˇcilo vod´ıc´ı prouˇzek v obraze rozpoznat pomoc´ı hranové detekce v nˇekolika oknech (viz obr. 3.1). Okna jsou um´ıstˇena v tˇech m´ıstech, kde je v´ yskyt vod´ıc´ıho prouˇzku pˇredpokládán. Optimáln´ı poˇcet oken byl na z´ akladˇe praktick´ ych experiment˚ u stanoven v rozmez´ı 3 aˇz 10 [14]. 2. Rozpozn´ an´ı kˇriˇzovatek. V této problematice bylo provedeno pouze nˇekolik experiment˚ u. Kˇriˇzovatka je nejˇcastˇeji zjednoduˇsenˇe definována jako pˇreruˇsen´ y vod´ıc´ı prouˇzek pˇr´ıpadnˇe jako stop ˇcára napˇr´ıˇc j´ızdn´ım pruhem. 3. Rozpozn´ an´ı vodorovných dopravn´ıch znaˇcek. Kromˇe vod´ıc´ıch prouˇzk˚ u obsahuj´ı j´ızdn´ı pruhy dalˇs´ı znaˇcen´ı. Jedná se o smˇerové ˇsipky, parkovac´ı znaˇcky, znaˇcen´ı pro cyklisty a autobusy atp. Zásadn´ım problémem je, ˇze vodorovné dopravn´ı znaˇcen´ı b´ yv´ a ˇc´ asteˇcnˇe zakryto ostatn´ımi automobily. O této problematice zat´ım bylo publikov´ ano velmi málo ˇclánk˚ u. 4. Dopravn´ı znaˇcky. Dopravn´ı znaˇcky a dopravn´ı osvˇetlen´ı je um´ısováno v pˇredem zn´ am´ ych oblastech v obraze. Z tohoto d˚ uvodu je moˇzné v obraze vymezit subregiony, ve kter´ ych mohou b´ yt dopravn´ı znaˇcky na základˇe tvaru a barvy rychle rozpoznány a klasifikov´ any. 5. Rozpozn´ an´ı pˇrek´ aˇzek. Pˇrekáˇzky jsou detekovány jako v´ yznamná porucha v textuˇre vozovky v m´ıstˇe, kde je silnice predikována, nebo pomoc´ı v´ ypoˇctu optického toku. Prvn´ı zp˚ usob je v´ ypoˇcetnˇe ménˇe nároˇcn´ y, ale poˇcet skuteˇcnˇe detekovan´ ych 1

Driver Support System

19

pˇrek´ aˇzek je n´ızk´ y a naopak poˇcet nezprávn´ ych rozpoznán´ı vysok´ y. V´ yhodné je pˇrek´ aˇzky rozpoznat na základˇe v´ ypoˇctu optického toku, zvláˇstˇe pak pˇri pouˇzit´ı dvou kamer.

3.1.1

Projekt CAPC

Jedná se o projekt podporovan´ y U.S. Army Tank Automative a firmou Ford Motor Company [13].V USA doch´ az´ı k dopravn´ım nehodám z jedné tˇretiny na dálnic´ıch. Témˇeˇr tˇretina z tˇechto nehod je zp˚ usobena u ńavou, intoxikac´ı nebo nemoc´ı ˇridiˇce a projevuje se vyjet´ım automobilu z vozovky – pˇrejezdem b´ılého (ˇzlutého) vod´ıc´ıho prouˇzku krajnice. Systém CAPC2 je podp˚ urný palubn´ı varovn´ y systém, kter´ y upozorn´ı ˇridiˇce pˇred nebezpeˇc´ım vyjet´ı ze silnice a v pˇr´ıpadˇe nutnosti aktivn´ım zásahem do ˇr´ızen´ı uprav´ı dráhu vozidla. To znamená, ˇze tento systém je modern´ım prvkem aktivn´ı bezpeˇcnosti. Systém je vybaven elektronikou podporovanou algoritmy poˇc´ıtaˇcového vidˇen´ı, které umoˇzn ˇuj´ı zpracovan´ı obrazu do vzdálenosti 100 m pˇred automobilem. V´ ypoˇcty jsou aktualizov´ any desetkrát za sekundu, prob´ıhá v´ ypoˇcet predikce pr˚ ubˇehu silnice. Po porovn´ an´ı s geometrick´ ym a kinematick´ ym modelem je z´ıskán ˇcas potˇrebn´ y k vyjet´ı z vozovky pˇri nezmˇenˇené rychlosti a smˇeru j´ızdy. V pˇr´ıpadˇe, ˇze je tento ˇcas menˇs´ı neˇz stanoven´ y práh, je aktivov´ an varovn´ y zvukov´ y signál. V letoˇsn´ım roce prob´ıhá implementace automatické podpory ˇr´ızen´ı realizovaná brzdˇen´ım kol na levé a pravé stranˇe automobilu. I v pˇr´ıpadˇe intervence systému do ˇr´ızen´ı má ˇridiˇc plnou kontrolu nad vozidlem. Nejedná se tedy o systém autonomn´ıho vozidla, ale o prvek aktivn´ı bezpeˇcnosti, kter´ y upozorˇ nuje na nebezpeˇcné situace a pomáhá je v kooperaci s ˇridiˇcem ˇreˇsit.

Senzor Kamera, B&W, digit´ aln´ı v´ ystup

Mˇeˇren´ı geometrie vod´ıc´ıho prouˇzku

Akcelerometr Gyroskop

zrychlen´ı u ´hlovou rychlost otáˇcen´ı ω

Rychlost otáˇcen´ı rychlost vozidla kol (z instalovaného ABS) LVDT na pˇredn´ı u ´hel natoˇcen´ı kol n´ apravˇe

V´ ypoˇcet v´ ypoˇcet ˇcasu potˇrebného pro vyjet´ı z vozovky, aktualizace polohy vozidla a predikce polohy vod´ıc´ıho prouˇzku dynamick´ y model vozidla v´ ypoˇcet ˇcasu potˇrebného pro vyjet´ı z vozovky, aktualizace polohy vozidla v´ ypoˇcet ˇcasu potˇrebného pro vyjet´ı z vozovky, aktualizace polohy vozidla a predikce polohy vod´ıc´ıho prouˇzku v´ ypoˇcet ˇcasu potˇrebného pro vyjet´ı z vozovky, aktualizace polohy vozidla a predikce polohy vod´ıc´ıho prouˇzku

Tabulka 3.1: Pouˇzité senzory a jejich funkce 2

Crewman’s Associate for Path Control

20

Systém CAPC ja tvoˇren jak hardwarov´ ymi tak softwarov´ ymi prostˇredky. Aby nebylo nutné v poˇc´ ateˇcn´ı fázi v´ yvoje investovat pˇr´ıliˇs mnoho financ´ı do speciáln´ıch zaˇr´ızen´ı byla pˇrijata tato omezen´ı: • vozidlo jede po dálnici s b´ıl´ ym vod´ıc´ım prouˇzkem za n´ızkého provozu, mimo n´ ajezdy nebo v´ yjezdy z dálnice, v m´ıstech, kde je b´ıl´ y vod´ıc´ı prouˇzek nepˇreruˇsen´ y, • experimenty jsou prov´ adˇeny za denn´ıho svˇetla, bez st´ın˚ u, povrch vozovky nen´ı tvoˇren dlaˇzbou, • povrch vozovky je ve velmi dobrém stavu, nen´ı pokryt vodou, snˇehem nebo jin´ ymi neˇcistotami, • okraje silnice neobsahuj´ı ruˇsivé objekty alespoˇ n do vzdálenosti ˇs´ıˇrky automobilu, • ostatn´ı automobily na silnici se nevyskytuj´ı bl´ıˇze neˇz 50 m pˇred automobilem. Algoritmy poˇ c´ıtaˇ cov´ eho vidˇ en´ı Algoritmus pro identifikaci vod´ıc´ıho prouˇzku LMS3 byl vyvinut v Environmental Research Institute of Michigan (ERIM) tak, aby splˇ noval poˇzadavky systému CAPC: 1. rozpoznán´ı vod´ıc´ıho prouˇzku aˇz 100 m pˇred vozidlem, za podm´ınek stanoven´ ych v pˇredchoz´ı kapitole, 2. aktualizace dat popisuj´ıc´ıch vod´ıc´ı prouˇzek kaˇzd´ ych 100 ms, 3. detekce polohy vod´ıc´ıho prouˇzku kaˇzdé dva metry v intervalu 6 – 20 m pˇred vozidlem a kaˇzd´ ych deset metr˚ u v intervalu 30 – 100 m pˇred vozidlem, 4. pˇrepoˇcet z´ıskan´ ych dat vzhledem k rychlosti automobilu a geometrickému modelu vozovky. LMS systém se sklád´ a z digitáln´ı CCD kamery Pulnix 9701 (748 × 484), frame-grabberu MuTech MV-1000 PCI a poˇc´ıtaˇce na bázi procesoru Intel Pentium 100 MHz. Tento poˇc´ıtaˇc zpracov´ av´ a vˇsechny operace poˇc´ıtaˇcového vidˇen´ı. Kamera je napevno um´ıstˇena uvnitˇr automobilu. Vod´ıc´ı prouˇzek je v obraze hledán ve vzdálenosti od 6 do 20 m pˇred automobilem. Takto z´ıskan´ a data jsou extrapolována aˇz do vzdálenosti 100 m. Z matice popisuj´ıc´ı obraz jsou vybrány vektrory v~j , které reprezentuj´ı horizontáln´ı ˇrezy obrazem ve vzdálenosti j = 6, 8, 10, . . . , 20 m pˇred automobilem. V tˇechto vektorech jsou hledány krátké sekvence – m´ısta nejvˇetˇs´ıho gradientu jasu. V kaˇzdé sekvenci je nalezeno m´ısto s nejvˇetˇs´ım jasem Imax (x) a následuj´ıc´ı hodnota s minimáln´ım jasem Imin (y). Za stˇred vod´ıc´ıho prouˇzku je povaˇzov´ ana hodnota (x + y)/2. Touto metodou jsou v kaˇzdém ˇrezu z´ıskány aˇz ˇctyˇri moˇzné hodnoty polohy vod´ıc´ıch prouˇzk˚ u, ze kter´ ych jsou dva správné vybr´ any na základˇe v´ ysledk˚ u v pˇredchoz´ım ˇrezu a porovnán´ım s geometrick´ ym modelem. Z v´ yˇse popsaného algoritmu je zˇrejmé, ˇze je velmi jednoduch´ y a funkˇcn´ı pouze za podm´ınek, které autoˇri stanovili. Nejedná se tedy o univerzáln´ı metodu, která by se mohla stát souˇc´ ast´ı algoritm˚ u autonomn´ıho vozidla. Tˇeˇziˇstˇe práce autor˚ u této metody vˇsak bylo ve stanoven´ı dynamického modelu j´ızdy. 3

Lane mark sensor

21

3.1.2

Projekt VaMoRs

Tento projekt prob´ıh´ a od roku 1986 na technické univerzitˇe v Mnichovˇe a je veden profesorem Dickmannem [14]. Projekt je podporován firmou Daimler–Benz AG a jeho c´ılem je v´ yvoj plnˇe autonomn´ıho vozidla. Systém VaMoRs byl poprvé prezentován v roce 1991 v Torinu a jiˇz tehdy umoˇzn ˇoval: 1. rozpoznán´ı vod´ıc´ıho prouˇzku i v pˇr´ıpadˇe zhorˇsen´ ych podm´ınek (st´ıny od okoln´ıch strom˚ u na silnici), 2. ˇr´ızen´ı v noci pˇri pouˇzit´ı bˇeˇzn´ ych svˇetel, 3. detekce pˇrek´ aˇzek aˇz do vzdálenosti 90 m pˇred vozidlem, 4. v´ ypoˇcet vzdálenosti za pomoci pouze jedné kamery, 5. pˇri rychlosti 50 km/h bezpeˇcné zastaven´ı pˇred pˇrekáˇzkou. Systém se sklád´ a ze dvou CCD kamer, které jsou namontovány v oblasti zpˇetného c zrcátka. Kamery jsou vybaveny objektivy s r˚ uzn´ ymi ohniskov´ ymi vzdálenostmi. iroko´ uhl´ y obraz z jedné kamery se pouˇz´ıvá pro globáln´ı anal´ yzu scény – detekci vod´ıc´ıho prouˇzku a aktualizaci geometrického modelu. Detailnˇejˇs´ı obraz z druhé kamery je pouˇzit zvláˇstˇe pro detekci objekt˚ u a pˇrekáˇzek na silnici. Zpracován´ı obrazu v reálném ˇcase je realizov´ ano pomoc´ı 14 paralelnˇe pracuj´ıc´ıch poˇc´ıtaˇc˚ u. I pˇri takto masivn´ı paraleln´ı architektuˇre je zpracov´ av´ an obraz o rozliˇsen´ı pouze 256 × 244 × 8 bit. Zpracov´ an´ı obrazu prob´ıh´ a ve tˇrech horizontáln´ıch u ´rovn´ıch a skládá se ze ˇctyˇr d´ılˇc´ıch u ´kol˚ u – detekce vod´ıc´ıho prouˇzku, rozpoznán´ı pˇrekáˇzek na silnici, aktualizace modelu a navigace (ˇr´ızen´ı). Pouˇzité rozliˇsen´ı obrazu vyˇzaduje zpracován´ı 1.6 MB dat za sekundu. Pouˇzit´ım z´ ony z´ ajmu, osmi oken o rozliˇsen´ı 48 × 48, je datov´ y tok redukován pˇribliˇznˇe na 0.5 MB/s. Informace obsaˇzené v zónˇe zájmu jsou dále zpracovávány ˇctyˇrmi poˇc´ıtaˇci a t´ım se datov´ y tok sn´ıˇz´ı na 140 kB/s na jeden poˇc´ıtaˇc. Pouˇzit´ım paraleln´ı architektury zpracov´ an´ı dat a implementac´ı zóny zájmu je dosaˇzeno bˇehu systému v reálném ˇcase.

Algoritmy poˇ c´ıtaˇ cov´ eho vidˇ en´ı Paraleln´ı procesory (PP1 - PP10) jsou pouˇzity pro hranovou detekci. Takto z´ıskané informace o hranách a jejich orientac´ıch jsou nejv´ yznamˇejˇs´ımi pˇr´ıznaky pro detekci vod´ıc´ıho prouˇzku a pro rozpoznán´ı pˇrekáˇzek na silnici. Hranové detektory jsou softwarovˇe implementované na standardn´ıch procesorech 80386. Vstupem do hranového detektoru je nepˇredzpracovan´ y obraz. Dickmanns v [14] uvád´ı, ˇze systém produkuje ˇspatné v´ ysledky, v pˇr´ıpadˇe ˇspatného osvˇetlen´ı, nepravidelné textury nebo silnˇe zaˇsumˇelého obrázku. Závˇerem poznamenáv´ a, ˇze tyto podm´ınky jsou v pˇr´ıpadˇe reáln´ ych scén velmi ˇcasté a proto je nutné algoritmus doplnit o co nejv´ıce apriorn´ıch informac´ı a kvalitn´ı geometrick´ y model scény. V´ ysledkem hranové detekce je obvykle mnoˇzina moˇzn´ ych hran a jejich orientac´ı. Interpretace v´ ysledk˚ u hranové detekce prob´ıhá v procesorech GPP1 a GPP2. Na základˇe predikce pozice hran a jejich orientac´ı jsou z mnoˇziny moˇzn´ ych hran vybrány ty, které skuteˇcnˇe reprezentuj´ı okraj silnice. Takto z´ıskané hrany jsou dále pouˇzity pro predikci 22

Obr´ azek 3.1: Paraleln´ı architektura systému VaMoRs

hran v následuj´ıc´ım oknˇe. Pro extrakci orientac´ı je pouˇzito 16 kanál˚ u, tedy rozliˇsen´ı je pˇribliˇznˇe 11 stupˇ n˚ u. V kaˇzdém oknˇe mohou b´ yt rozliˇseny aˇz ˇctyˇri moˇzné hrany, tedy je tˇreba analyzovat a interpretovat aˇz 32 moˇzn´ ych hran. Popis geometrického modelu a dalˇs´ı podrobnosti jsou uvedeny v [14].

23

Kapitola 4

Segmentace z´ ony z´ ajmu 4.1

Segmentace - u ´ vod

Segmentace obrazu je jedn´ım z nejd˚ uleˇzitˇejˇs´ıch krok˚ u v algoritmech zpracován´ı obrazu. Segmentov´ an´ım rozum´ıme postup, kter´ y obraz rozˇclen´ı na segmenty – ˇcásti obrazu, které maj´ı urˇcit´ y vztah k objekt˚ um obsaˇzen´ ym v obraze. V´ ysledkem segmentace je mnoˇzina vzájemnˇe se nepˇrekr´ yvaj´ıc´ıch oblast´ı. V pˇr´ıpadˇe, ˇze tyto oblasti jednoznaˇcnˇe koresponduj´ı s objekty v obraze, pak mluv´ıme o kompletn´ı segmentaci. Segmentace komplexn´ıch scén je velice sloˇzitá a kompletn´ı segmentace nen´ı v této fázi zpracován´ı obrazu dosaˇziteln´ a bez pouˇzit´ı postup˚ u vyˇsˇs´ı u ´rovnˇe. Rozumn´ ym c´ılem m˚ uˇze b´ yt ˇc´ asteˇcn´ a segmentace, ve které oblasti z´ıskané segmentac´ı nemus´ı pˇresnˇe souhlasit s objekty v obraze. V´ ysledky z´ıskané ˇc´ asteˇcnou segmentac´ı je moˇzné dále zpˇresˇ novat za pomoci algoritm˚ u vyˇsˇs´ı u ´rovnˇe, zvláˇstˇe pak semantické znalosti segmentovaného obrazu. Jedn´ım z hlavn´ıch problém˚ u segmentace je nejednoznaˇcnost obrazov´ ych dat, která ˇcasto obsahuj´ı ˇsum. Obraz je segmentov´ an do oblast´ı na základˇe kritéria stejnorodosti. Vlastnosti, které tvoˇr´ı kritérium stejnorodosti mohou b´ yt r˚ uzné. V nejjednoduˇsˇs´ıch algoritmech se jedná o hodnoty jasu nebo barvy testovaného elementu, ve sloˇzitˇejˇs´ıch algoritmech o statistickou anal´ yzu okol´ı testovaného bodu. Pˇr´ıkladem m˚ uˇze b´ yt segmentace na základˇe textury. Nejabstraktnˇejˇs´ı vlastnost´ı m˚ uˇze b´ yt sémantická pˇr´ısluˇsnost elementu k segmentovanému objektu. V literatuˇre je moˇzné nalézt mnoho definic segmentace [3], [4], [8], [9]. To je zp˚ usobeno t´ım, ˇze autoˇri definuj´ı segmentaci na základˇe aplikace, ve které byla pouˇzita (segmentace objekt – pozad´ı, segmentace na objekty, . . . ). Jako obecnou definici segmentace m˚ uˇzeme uvést napˇr´ıklad tuto: Def 1: Nech X je mnoˇzina vˇsech obrazov´ ych bod˚ u obrazu A a P (.) logick´ y v´ yrok definovan´ y na uzavˇrené mnoˇzinˇe pixel˚ u. Potom segmentac´ı rozum´ıme rozdˇelen´ı mnoˇziny X na N disjunktn´ıch podmnoˇzin Xi tak, aby platilo: 1. ∪N i=1 Xi = X, 2. Xi , ∀i = 1, . . . , N jsou uzavˇrené mnoˇziny, 3. P (Xi ) = 1, ∀i = 1, . . . , N , 4. P (Xi ∪ Xj ) = 0, ∀i 6= j, kde Xi a Xj . 24

V´ yrok P definovan´ y ve tˇret´ı podm´ınce urˇcuje vlastnost, pˇr´ıpadnˇe vlastnosti, segmentované oblasti, které jsou pouˇzity pˇri segmentaci (napˇr. homogenn´ı jas). Druhá podm´ınka ˇr´ık´ a, ˇze segmentované oblasti mus´ı b´ yt spojité, napˇr. sloˇzené ze sousedn´ıch obrazov´ ych bod˚ u. Tento pˇredpoklad je velice d˚ uleˇzit´ y, zvláˇstˇe pro segmentaci nar˚ ustán´ım oblasti. Formulace v´ yroku P ovlivˇ nuje v´ ysledek segmentace. V pˇr´ıpadˇe sloˇzité v´ yrokové formule doch´ az´ı velice ˇcasto k podsegmentován´ı a naopak v pˇr´ıpadˇe jednoduch´ ych v´ yrok˚ u k pˇresegmentov´ an´ı. Pro optimáln´ı stanoven´ı segmentaˇcn´ıho kritéria se pouˇz´ıvaj´ı optimalizaˇcn´ı a adaptivn´ı algoritmy zaloˇzené na lokáln´ı anal´ yze obrazu.

4.2

Segmentaˇ cn´ı algoritmy

V literatuˇre jsou popsány stovky segmentaˇcn´ıch algoritm˚ u, ale neexistuje univerzáln´ı metoda, která by mohla b´ yt u ´spˇeˇsnˇe pouˇzita pro vˇsechny aplikace a typy obrazu. Je moˇzné ˇr´ıci, ˇze algoritmus vyvynut´ y pro jednu tˇr´ıdu obrazu (intenzitn´ı monochromatick´ y obraz) nelze pouˇz´ıt pro tˇr´ıdy jiné. Existuje mnoho segmentaˇcn´ıch pˇr´ıstup˚ u (prahov´ an´ı, hranov´ a detekce, nar˚ ust´ an´ı oblasti, statistick´ a analýza, Markovské ˇretˇezce, neuronové s´ıtˇe, fuzzy logika, . . . ). Vhodnou metodu je moˇzné vybrat na základˇe semantické informace v obraze, pˇr´ıpadnˇe experimentálnˇe. V následuj´ıc´ıch kapitolách budou popsány nejv´ıce pouˇz´ıvané segmentaˇcn´ı algoritmy. U nˇekter´ ych bude diskutována i jejich vhodnost pro segmentaci a anal´ yzu dopravn´ı scény.

4.2.1

Segmentace prahov´ an´ım

Prahov´ an´ı je jedna z nejstarˇs´ıch, nejjednoduˇsˇs´ıch a hodnˇe pouˇz´ıvan´ ych segmentaˇcn´ıch technik. Prahov´ an´ı m˚ uˇze b´ yt zaloˇzené na globáln´ı informaci (napˇr´ıklad histogram rozloˇzen´ı jasov´ ych u ´rovn´ı) nebo na lokáln´ı informaci – matice okol´ı segmentovaného elementu. V pˇr´ıpadˇe, ˇze pro prahován´ı pouˇzijeme pouze jednu hodnotu prahu (nehledˇe na glob´ aln´ı nebo lokáln´ı informaci) pro cel´ y obraz, pak tento typ segmentace naz´ yváme glob´ aln´ı prahov´ an´ı. Pokud je obraz rozdˇelen do nˇekolika ˇcást´ı, nejlépe na základˇe kontextu´ aln´ı informace, a pro kaˇzdou ˇcást je pouˇzita jiná hodnota prahu, pak mluv´ıme o lok´ aln´ım prahov´ an´ı. Nˇekteˇr´ı autoˇri tento typ segmentace naz´ yvaj´ı adaptivn´ı prahov´ an´ı. V´ ysledkem segmentace pˇri pouˇzit´ı jednoho prahu je binárn´ı obraz, kter´ y obsahuje dvˇe oblasti – objekt (ˇcern´ a barva) a pozad´ı (b´ılá barva). V pˇr´ıpadˇe, ˇze obraz obsahuje nˇekolik objekt˚ u s r˚ uznou charakteristikou povrchu, pak je vhodné pouˇz´ıt prahov´ an´ı s v´ıce prahy. Obecnˇe m˚ uˇzeme prahován´ı definovat g(i, j) =

(

1, 0,

f (i, j) ≤ T f (i, j) > T

(4.1)

a v pˇr´ıpadˇe prahov´ an´ı s v´ıce prahy

g(i, j) =

 0,      1,

..   .   

n,

f (i, j) ∈ M0 f (i, j) ∈ M1

(4.2)

f (i, j) ∈ Mn

Kde g(i, j) pˇredstavuje segmentovan´ y obraz a f (i, j) vstupn´ı obrazová data. Na segmentaci prahov´ an´ım se také m˚ uˇzeme d´ıvat jako na klasifikaci. Segmentace obrazu s jedn´ım 25

prahem je v podstatˇe klasifikace obrazového bodu do dvou tˇr´ıd – objekt a pozad´ı. Na tomto základˇe a za pˇredpokladu, ˇze barvy objektu a pozad´ı maj´ı normáln´ı rozdˇelen´ı s urˇcit´ ym rozptylem, je moˇzné pomˇernˇe snadno vypoˇc´ıtat hodnotu prahu. V pˇr´ıpadˇe, ˇze je obraz tvoˇren nˇekolika regiony se shodnou intenzitou jasu, která je dostateˇcnˇe odliˇsn´ a od jasu pozad´ı, je moˇzné hodnotu prahu urˇcit na základˇe histogramu (obr. 4.1). Objekt a pozad´ı budou v histogramu znázornˇeny jako dva vrcholy. Hodnota prahu bude tedy logicky leˇzet mezi tˇemito vrcholy.

Obr´ azek 4.1: Urˇcen´ı hodnoty prahu z histogramu jasu

Segmentaci prahov´ an´ım, tak jak je popsaná napˇr. v [3], [4], nen´ı moˇzné pouˇz´ıt pro segmentaci silnice v dopravn´ı scénˇe a to zejména z tˇechto d˚ uvod˚ u: • intenzita jasu povrchu vozovky nen´ı dostateˇcnˇe odliˇsná od ostatn´ıch objekt˚ u v obraze a proto nelze pouˇz´ıt metody v´ ypoˇctu prahu popsané v [3], • textura povrchu vozovky nen´ı homogenn´ı. Povrch vozovky je tvoˇren nepravideln´ ymi poruchami r˚ uzn´ ych rozmˇer˚ u a tvar˚ u, b´ yvá ˇcasto pokryt list´ım a jin´ ymi neˇcistotami. V pˇr´ıpadˇe, ˇze pro segmentaci silnice zaloˇzené na prahován´ı pouˇzijeme i sematickou informaci obsaˇzenou v obraze, m˚ uˇzeme dosáhnout pˇrekvapivˇe dobr´ ych v´ ysledk˚ u. Pˇri segmentaci dopravn´ı scény známe pˇribliˇznou polohu silnice. Dále v´ıme, ˇze silnice bude v obraze zaˇc´ınat v jeho doln´ı ˇcásti a smˇerem k horizontu se bude zuˇzovat. M˚ uˇzeme odhadnout pod´ıl plochy obrazu, kter´ y obsahuje silnici. Na základˇe znalosti o pˇribliˇzné poloze silnice je moˇzné v obraze vymezit oblast O, která je s velkou pravdˇepodobnost´ı jej´ı souˇc´ ast´ı. Na této oblasti vypoˇcteme základn´ı popisné statistiky. Pˇredpokládejme, ˇze povrch vozovky je homogenn´ı. Potom intenzita jasu povrchu silnice má norm´ aln´ı rozdˇelen´ı Y ∼ N (µ, σ), kde µ je parametr polohy a σ parametr mˇeˇr´ıtka. Parametr polohy µ je pˇredstavov´ an mediánem, t.j. stˇredn´ı hodnotou, náhodného v´ ybˇeru. V´ ypoˇcet medi´ anu je pomˇernˇe nároˇcn´ y a v tomto pˇr´ıpadˇe je moˇzné s pˇrijatelnou chybou provést jeho náhradu v´ ybˇerov´ ym pr˚ umˇerem1 µ= 1

1 X f (i, j) n i,j∈O

(4.3)

s roztouc´ım rozsahem v´ ybˇeru konverguje pr˚ umˇer ke stˇredn´ı hodnotˇe

26

kde n je rozsah v´ ybˇeru – intenzity jasu vˇsech obrazov´ ych bod˚ u z oblasti O. Smˇerodatná odchylka σ vyjadˇruje m´ıru homogenity v´ ybˇeru a t´ım urˇcuje, zda je moˇzné pro tento obraz pouˇz´ıt segmentaci prahov´ an´ım. σ=

s P

n

P

f (i, j)2 − ( f (i, j))2 n(n − 1)

(4.4)

V dopravn´ı scénˇe tvoˇr´ı silnice znaˇcnou ˇcást obrazu. Za pˇredpokladu, ˇze je jej´ı povrch homogenn´ı, je moˇzné silnici v histogramu identifikovat jako v´ yznamn´ y vrchol. Jeho polohu urˇcuje hodnota µ a prahy je moˇzné urˇcit na základˇe hodnoty σ.

a) histogram obrázku 012.bmp

c) histogram obrázku 015.bmp

b) histogram povrchu vozovky na obr´ azku 012.bmp

d) histogram povrchu vozovky na obrázku 015.bmp

Obr´ azek 4.2: Histogram intenzit jasu celého obrazu a povrchu silnice

Na obrázku 4.2 jsou zobrazeny histogramy intenzit jasu pro dva testovac´ı obrázky. Na základˇe kontextu´ aln´ı informace jsou v obraze vyznaˇceny dostateˇcnˇe velké regiony, které jsou s velkou pravdˇepodobnost´ı souˇcást´ı povrchu silnice. V pˇr´ıpadˇe, ˇze je smˇerodatn´ a odchylka σ ≤ 15 pak je tento v´ ybˇer dostateˇcnˇe homogenn´ı. V tˇechto pˇr´ıpadech je moˇzné pro segmentaci povrchu vozovky pouˇz´ıt segmentaci prahován´ım. Parametry polohy a mˇeˇr´ıtka tˇechto v´ ybˇer˚ u jsou shrnuty v tabulce 4.1. Pokud nen´ı krajnice vozovky oznaˇcena vod´ıc´ım prouˇzkem, pak je nutné pro bezchybnou segmentaci pouˇz´ıt predikci okraje silnice zaloˇzené na apriorn´ıch pravdˇepodobnostech polohy silnice v obraze.

Statistiky V´ ybˇerov´ y pr˚ umˇer µ Smˇerodatná odchylka σ Rozsah v´ ybˇeru

Obrázek 012.bmp 167.00 5.40 1000

Obrázek 015.bmp 136.00 24.04 1000

Tabulka 4.1: Popisné statistiky

27

Vlivem perspektivn´ı projekce se silnice v obraze zuˇzuje. Pokud obraz rozdˇel´ıme do vrstev o ˇs´ıˇrce jednoho obrazového bodu, potom bude ˇs´ıˇrka silnice ve vrstvˇe i menˇs´ı nebo rovna ˇs´ıˇrce silnice ve vrstvˇe i − 1. Na základˇe tohoto pˇredpokladu m˚ uˇzeme definovat apriorn´ı pravdˇepodobnosti polohy silnice v obraze tak, jak je znázornˇeno na obrázku 4.3.

Obr´ azek 4.3: Predikce okraje silnice

V pˇr´ıpadˇe, ˇze pouˇzijeme vˇsechny v´ yˇse popsané metody, je moˇzné v ˇradˇe pˇr´ıpad˚ u pouˇz´ıt pro segmentaci silnice v obraze prahován´ı. Jedná se o velmi jednoduchou a rychlou metodu, kterou je moˇzné pouˇz´ıt pouze pro silnice s homogenn´ım povrchem vozovky. Na obrázku 4.4 jsou zobrazeny v´ ysledky segmentace na dvou obrázc´ıch, které splˇ nuj´ı podm´ınku homogenity (viz. histogram na obrázku 4.2). Dalˇs´ı podrobnosti o pouˇzit´ı této metody pro segmentaci zóny zájmu budou uvedeny v kapitolách 4.3.2 a 5.

4.2.2

Segmentace prostˇ rednictv´ım hranov´ e detekce

Jak bylo uvedeno v kapitole 2.3, hrany se vyznaˇcuj´ı náhl´ ymi, v´ yrazn´ ymi zmˇenami jasové funkce. Jednoduché gradientn´ı operátory jako Roberts˚ uv reaguj´ı nejen na hrany v obraze, ale také na izolované body (ˇsum). Z tohoto pohledu se jako v´ yhodn´ y gradientn´ı operátor jev´ı Sobel˚ uv operátor, kter´ y je odolnˇejˇs´ı proti ˇsumu v obraze, zvláˇstˇe pokud zvˇetˇs´ıme konvoluˇcn´ı masku na velikost 5 × 5. Re´ alné obrázky dopravn´ıch scén obsahuj´ı kromˇe ˇsumu také st´ıny od ostatn´ıch objekt˚ u v obraze, povrch silnice b´ yvá velmi ˇcasto poruˇsen, pˇr´ıpadnˇe pokryt r˚ uzn´ ymi neˇcistotami. V tˇechto pˇr´ıpadech z´ıskáme prostˇrednictv´ım gradientn´ıch operátor˚ u velké mnoˇzstv´ı moˇzn´ ych hran, které nemus´ı popisovat okraj silnice. V pˇr´ıpadˇe, ˇze okraj silnice nen´ı zv´ yraznˇen vod´ıc´ım prouˇzkem, pak nen´ı moˇzné ani za pomoci apriorn´ı informace 28

012.bmp

041.bmp

Obr´ azek 4.4: V´ ysledky segmentace prahován´ım (obrázek 012.bmp a 041.bmp)

urˇcit okraj silnice. Pro rozpoznán´ı objekt˚ u v obraze je nutn´ y strukturáln´ı popis, kter´ y ’ sebou pˇrin´ aˇs´ı zv´ yˇsené v´ ypoˇcetn´ı a pamˇet ové nároky. Obrázek 4.5 znázorˇ nuje v´ ysledek Sobelova hranového detektoru (2.9) na tˇrech obrázc´ıch z testovac´ı databáze. Obrázek 016.bmp obsahuje silnici bez dopravn´ıho znaˇcen´ı, povrch vozovky je ˇcásteˇcnˇe poˇskozen a je mokr´ y. V´ ysledkem hranové detekce je velké mnoˇzstv´ı nespojit´ ych hran. Obrázek 033.bmp pˇredstavuje typick´ y pˇr´ıklad dobˇre znaˇcené silnice s nepoˇskozenou texturou vozovky. V´ ysledkem jsou v´ yrazné, spojité hrany, které jsou vhodné pro segmentaci obrazu.

016.bmp

033.bmp

Obr´ azek 4.5: V´ ysledky hranové detekce

29

Experiment´ alnˇe jsem zjistil, ˇze metoda segmentace silnice zaloˇzená na hranové detekci je pouˇziteln´ a pouze pro tˇretinu obrázk˚ u z testovac´ı databáze. Na základˇe experimentu se domn´ıv´ am, ˇze segmentace prostˇrednictv´ım hranové detekce nen´ı vhodnou metodou pro anal´ yzu dopravn´ı scény. Proto jsem vyvinul metodu zaloˇzenou na barevné segmentaci, která je v´ ypoˇcetnˇe obdobnˇe nároˇcn´ a jako segmentace hranovou detekc´ı, ale pouˇziteln´ a pro vˇetˇsinu obrázk˚ u. Teoretická ˇcást bude popsána v následuj´ıc´ı kapitole, vlastn´ı algoritmus pak v kapitolách 4.3.

4.2.3

Barevn´ a segmentace

V literatuˇre je popsáno mnoho algoritm˚ u pro segmentaci barevn´ ych obrázk˚ u [9], ale jejich poˇcet nen´ı ani zdaleka tak bohat´ y jako pro ˇsedotónové obrázky. Tento nedostatek je patrn´ y zvláˇstˇe pro algoritmy zaloˇzené na segmentaci nar˚ ustán´ım oblasti. Je moˇzné pouˇz´ıt nˇekolik kritéri´ı, na jejichˇz základˇe rozhodujeme o tom, zda obrazov´ y element náleˇz´ı do segmentované oblasti. Tato kritéria mohou b´ yt definována na nˇekolika rozliˇsovac´ıch u ´rovn´ıch – lokáln´ı, regionáln´ı nebo globáln´ı. Pˇri lokáln´ım rozliˇsen´ı rozhodujeme o tom, zda sousedn´ı pixely náleˇz´ı do testovaného regionu. Pˇri region´ aln´ım rozliˇsen´ı o tom, zda testovan´ y region náleˇz´ı do segmentované oblasti. Globáln´ı rozliˇsovac´ı u ´roveˇ n se pouˇz´ıv´ a zvláˇstˇe pro stanoven´ı segmentaˇcn´ıch logick´ ych v´ yrok˚ u v niˇzˇs´ıch rozliˇsen´ıch. V pˇr´ıpadˇe, ˇze implementujeme rozhodovac´ı kritéria ze vˇsech rozliˇsen´ı, m˚ uˇzeme minimalizovat chybu segmentace na pˇrijatelnou u ´roveˇ n. Nemus´ıme tedy zvyˇsovat v´ ypoˇcetn´ı nároky algoritmu dodateˇcnou anal´ yzou hraniˇcn´ıch oblast´ı, která b´ yvá oznaˇcov´ ana jako de-growing proces. Reprezentace barev Jedn´ım z nejd˚ uleˇzitˇejˇs´ıch atribut˚ u, pouˇz´ıvan´ ych pˇri zpracován´ı obrazu je barevná informace. Kaˇzd´ a barva odpov´ıd´ a urˇcité frekvenci elektromagnetického vlnˇen´ı v pásmu 8 10 MHz. Rozsah barev je od ˇcervené – 430 nm aˇz po fialovou – 750 nm. V rámci viditelného spektra je ˇclovˇek schopen rozliˇsit v´ıce neˇz 4 × 105 barevn´ ych odst´ın˚ u. Podle frekvence, které vys´ıl´ a svˇeteln´ y zdroj je moˇzné barvy rozdˇelit na • achromatické – barva tˇelesa je tvoˇrena kombinac´ı frekvenc´ı odraˇzen´ ych od tˇelesa. Pokud pˇrevl´ ad´ a frekvence z urˇcité oblasti spektra, pak mluv´ıme o dominantn´ı frekvenci. • monochromatické – barva tˇelesa je urˇcena odrazem jen jedné frekvence - napˇr. frekvenc´ı zelené barvy. Mnoho fyziologick´ ych studi´ı prokázalo, ˇze barevná informace je tˇr´ısloˇzková. To znamen´ a, ˇze k popsán´ı vˇsech barevn´ ych odst´ın˚ u je nutné pouˇz´ıt tˇri promˇenné. Libovolnou 3 barvu tedy m˚ uˇzeme popsat vektorem v < . Jednotlivé barevné odst´ıny se odvozuj´ı od tˇr´ı základn´ıch barev aditivn´ım nebo subtraktivn´ım m´ıchán´ım. Existuje mnoho metod (barevn´ ych model˚ u), kter´ ymi se popisuje barevná informace a na jejich základˇe je moˇzné kaˇzd´ y barevn´ y odst´ın dekomponovat na základn´ı sloˇzky. Kaˇzd´ y barevn´ y model je popsán mnoˇzinou základn´ıch barev, zp˚ usobem jejich m´ıchán´ı a pravidly pomoc´ı kter´ ych se mˇen´ı barevné charakteristiky.

30

Barevn´ y model RGB V tomto modelu jsou barvy vytváˇreny aditivn´ım zp˚ usobem. Základn´ı sloˇzky jsou R red - ˇcerven´ a, G - green - zelená, B - blue - modrá. Pro tyto barvy je charakteristické právˇe to, ˇze lidské oko má nejvˇetˇs´ı citlivost právˇe pro jejich vlnové délky (630nm, 530nm a 450nm). Intenzita základn´ıch barev se v tomto modelu pohybuje v intervalu < 0, 1 >. V technick´ ych aplikac´ıch jako je poˇc´ıtaˇcové vidˇen´ı a zpracován´ı obrazu je tento interval pˇrevádˇen do digitáln´ı formy. Nejˇcastˇejˇs´ı je kódován´ı do 8-bitového rozliˇsen´ı (256 u ´rovn´ı).

Obr´ azek 4.6: Grafická reprezentace modelu RGB

Barevn´ y model RGB se nejˇcastˇeji znázorˇ nuje jako krychle um´ıstˇená v osách RGB. Z toho vypl´ yv´ a, ˇze mnoˇzina základn´ıch barev je tvoˇrena 8 barvami. Vrchol [0, 0, 0] (t.j. stˇred souˇradnicového systému) odpov´ıdá ˇcerné barvˇe. Naproti tomu vrchol [1, 1, 1] pˇredstavuje b´ılou barvu. Barvy leˇz´ıc´ı na u ´hlopˇr´ıˇcce mezi tˇemito vrcholy reprezentuj´ı vˇsechny ˇsedot´ onové odst´ıny. V´ yˇse popsan´ y barevn´ y model se nejv´ıce pouˇz´ıvá v technick´ ych aplikac´ıch. Uplatnˇen´ı naˇsel zejména ve videotechnice. Na základˇe obrázku 4.6 m˚ uˇzeme vytvoˇrit tabulku základn´ıch barev RGB modelu. Barva ˇcern´ a modrá zelen´ a tyrkysová ˇcerven´ a fialov´ a ˇzlut´ a

R(ed) 0 0 0 0 255 255 255

G(reen) 0 0 255 255 0 0 255

B(lue) 0 255 0 255 0 255 0

Tabulka 4.2: Tabulka základn´ıch barev v systému RGB

Barevn´ y model HSV CIE – Commission Internationale de l’Eclairege standardisovala modely, které umoˇzn ˇuj´ı rozdˇelit libovolnou barvu na jej´ı základn´ı sloˇzky. Doporuˇcila pˇrirozen´ y barevn´ y model RGB, kter´ y ovˇsem neodpov´ıdá lidskému chápán´ı svˇetla. Z tohoto pohledu je vhodné pouˇz´ıvat barevn´ y model HSV, kter´ y barvy popisuje na základˇe tˇr´ı intuitivn´ıch atribut˚ u:

31

• V - value – jas. Reprezentuje mnoˇzstv´ı svˇetla pˇrijatého senzorem. Záleˇz´ı na svˇeteln´ ych podm´ınk´ ach a na intenzitˇe svˇetelného zdroje. • H - hue – barevn´ y odst´ın. Hodnota která reprezentuje jednu ze základn´ıch barev modelu RGB. H 0 1 2 3 4 5

Barva ˇcervená ˇzlutá zelená tyrkysová modrá fialová

Tabulka 4.3: Vztah mezi hodnotou H a jménem barvy v modelu RGB

• S - saturation – saturace (sytost). Saturace popisuje napˇr. rozd´ıly mezi ˇcervenou a r˚ uˇzovou. Tmavˇe ˇcervené odpov´ıdá vysoká hodnota saturace a naopak r˚ uˇzové n´ızk´ a.

Obr´ azek 4.7: Grafická reprezentace modelu HSV

Barevn´ y model HSV se nejˇcastˇeji zobrazuje jako ˇsestibok´ y jehlan (obr. 4.7), jehoˇz vrchol leˇz´ı v poˇc´ atku souˇradnicového systému. Souˇradnice v a s se podobnˇe jako u modelu RGB mˇ en´ı od 0 do 1, pˇr´ıpadnˇe jsou kódovány do 8 bitového rozliˇsen´ı. Souˇradnice h je u ´hlov´ a. Vrchol jehlanu v bodˇe [0, 0, 0] pˇredstavuje ˇcernou barvu. B´ılá barva je ve stˇredu podstavy. Jas klesá od podstavy k vrcholu. Sytost je dána vzdálenost´ı od osy jehlanu. Základn´ı barvy se nach´ azej´ı ve vrcholech ˇsesti´ uheln´ıkové podstavy. Matematick´ y popis modelu HSV Existuje nˇekolik metod pomoc´ı kter´ ych je moˇzné transformovat RGB model na model HSV. Rovnice 4.5, 4.6, 4.7 pˇredstavuj´ı nejjednoduˇsˇs´ı a v´ ypoˇcetnˇe nejménˇe nároˇcn´ y zp˚ usob. Uveden´ a transformace vyˇzaduje pouze N násoben´ı a 2N dˇelen´ı, které mohou b´ yt nav´ıc pˇredpoˇc´ıtané v tabulce. Ostatn´ı transformace jako Lu∗ v ∗ uvedené v [1] 32

vyˇzaduj´ı 2N dˇelen´ı, 19N n´ asoben´ı, N druh´ ych odmocnin, N tˇret´ıch odmocnin a N v´ ypoˇct˚ u funkce arctan. V´ ypoˇcetn´ı nároky této transformace jsou 5 krát vyˇsˇs´ı. V následuj´ıc´ıch rovnic´ıch pˇredpoklád´ ame 8 bitové barevné rozliˇsen´ı. V = sup(R, G, B) S = 256 ·

H=

(4.5)

V − inf(R, G, B) V

 G−B   V −inf(R,G,B) ,      

2+

B−R V −inf(R,G,B)

(4.6) V =R

,

        4+ R−G V −inf(R,G,B) ,

V =G

(4.7)

V =B

Nyn´ı zavedeme tˇri normalizované promˇenné cR , cG , cB . Jejich hodnoty m˚ uˇzeme povaˇzovat za pomˇer RGB sloˇzek v barvˇe. Uvaˇzujme, ˇze odst´ın barvy vytváˇr´ıme kombinac´ı dvou ze tˇr´ı sloˇzek RGB. cR + cG + cB = 1

(4.8)

cR · cG · cB = 0 Rovnice (4.7) ukazuje, ˇze H je periodick´ a promˇenn´ a. Jednotlivé komponenty RGB jsou normalizované a nab´ yvaj´ı tedy hodnot z intervalu [0, 1]. Na základˇe rovnice 4.8 je alespoˇ n jedna ze sloˇzek nulov´ a. Pˇredpokládejme, ˇze cR = 1. Potom jsou normalizované −1 sloˇzky cG , cB nulové a H = 1−0 = −1. Pro hodnotu cR = 0.5 je v´ ysledek rovnice 4.7 1 nebo −1. To znamená, ˇze H pro pˇr´ıpad V = R nab´ yvá hodnoty z intervalu [−1, 1]. Obdobnou u ´vahou pro V = B nab´ yvá hodnot z intervalu [3, 5]. To znamená, ˇze v´ ysledek této transformace leˇz´ı v intervalu [−1, 5]. Abychom z´ıskali v´ ysledek z intervalu [0, 6], je závˇerem nutné provést dˇelen´ı H mod 6. Pˇri segmentaci je velmi ˇcasto nutné spoˇc´ıtat vzdálenost dvou pˇr´ıznak˚ u. V barevném modelu HSV nelze pouˇz´ıt pro v´ ypoˇcet vzdálenosti metody popsané v kapitole 2.2. Pˇredpokládejme, ˇze H1 a H2 jsou barevné odst´ıny dvou bod˚ u v HSV barevném prostoru a splˇ nuj´ı tuto podm´ınku: (H1 , H2 ) ∈ [0, 6]

(4.9)

Vzdálenost barevn´ ych odst´ın˚ u tˇechto dvou bod˚ u potom je δ = ∆(H1 , H2 ) =

(

H2 − H1 , H2 − H1 − 6 sgn (H2 − H1 ),

|H2 − H1 | ≤ 3 |H2 − H1 | > 3

(4.10)

V pˇr´ıpadˇe, ˇze byl obraz sn´ımán za zhorˇsen´ ych svˇeteln´ ych podm´ınek, pak jsou objekty v obraze tmavé (maj´ı n´ızkou sytost – hodnotu S). Tyto objekty je v HSV modelu obt´ıˇzné segmentovat. Z rovnice 4.6 vypl´ yvá, ˇze S = 0 v pˇr´ıpadˇe sup(R, G, B) = inf(R, G, B) ⇐⇒ R = G = B

(4.11)

Rovnic´ı 4.11 vˇsak m˚ uˇzeme definovat vˇsechny odst´ıny ˇsedi, vˇcetnˇe b´ılé barvy. Pokud jsou splnˇeny podm´ınky rovnice 4.11, potom docház´ı v rovnici 4.7 k dˇelen´ı nulou a tedy H nen´ı definované – model se stává aritmeticky nestabiln´ı. 33

Z´ akladn´ım problémem tedy je naj´ıt v barevném spektru obrazu ty body, ve kter´ ych nen´ı H definov´ ano. Tyto body jsou charakteristické t´ım, ˇze maj´ı n´ızkou saturaci. V literatuˇre bylo prokáz´ ano [1], ˇze H je nejv´ yznamˇejˇs´ı popisn´ y atribut HSV modelu a t´ım je velmi vhodn´ y pro segmentaci. Problémem ovˇsem z˚ ustává ˇcásteˇcná nestabilita modelu. Jedn´ım z moˇzn´ ych ˇreˇsen´ı je pro kaˇzd´ y obrazov´ y bod vypoˇc´ıtat stupeˇ n chromaticity a t´ım rozhodnou zda je tento pixel chromatický a nebo achromatický a tedy nevhodn´ y pro segmentaci na základˇe hodnoty H. V pˇr´ıpadˇe, ˇze scéna byla sn´ımána za ˇspatn´ ych svˇeteln´ ych podm´ınek, tak obsahuje achromatické oblasti. Achromatické oblasti se v obraze vyskytuj´ı napˇr´ıklad za tˇechto podm´ınek: • pˇri n´ızkém nasv´ıcen´ı scény, potom jsou objekty tmavé, nˇekdy aˇz ˇcerné, • a naopak, pokud je scéna pˇresv´ıcena, docház´ı k pˇresycen´ı senzor˚ u a t´ım se umˇele zvyˇsuje hodnota S. V tˇechto pˇr´ıpadech pˇrest´ av´ a b´ yt atribut H v´ yznamn´ y a pro segmentaci je vhodné pouˇz´ıt intenzitu V definovanou jako V (x, y) =

6 fR (x, y) + 3 fG (x, y) + fB (x, y) 10

(4.12)

Pro optimizaci segmentaˇcn´ıho algoritmu a pro zv´ yˇsen´ı jeho efektivnosti je nutné klasifikovat pixely do chromatick´ ych a achromatick´ ych oblast´ı a t´ım rozhodnout o zp˚ usobu segmentace. Vhodná metoda je uvedena napˇr´ıklad v [1]. Autoˇri definuj´ı funkci (rovnice 4.13), která popisuje stupeˇ n chromaticity pixelu c(P ) =

d 1 + s(P ) tanh( D ) , 2

(4.13)

kde s(P ) je konstanta, definovaná pomoc´ı hodnot S a V nab´ yvaj´ıc´ı hodnoty [-1,0,1], identifikuje chromatické a achromatické oblasti v HSV barevném prosoru, d je vzdálenost od testovaného pixelu P a konstanty s(P ) a D je konstanta, definuj´ıc´ı prostor pˇrechodu od chromatické k achromatické oblasti.

Obr´ azek 4.8: Definice funkce s(P) a konstanty D pro S = 107

34

Algoritmus barevn´ e segmentace Barva je velmi v´ yznamn´ y atribut obrazu. Jak bylo popsáno v kapitole 4.2.3 obrazov´ y element popisujeme obvykle pomoc´ı tˇr´ı sloˇzek. Pˇri experimentech s jednotliv´ ymi barevn´ ymi modely jsem zjistil, ˇze i pˇres pˇr´ıznivé reference v literatuˇre, nen´ı HSV barevn´ y model nejlepˇs´ım ˇreˇsen´ım pro segmentaci povrchu vozovky. D˚ uvodem je jeho aritmetická nestabilita pro achromatické oblasti. V reáln´ ych dopravn´ıch scénách, kde má silnice tmav´ y nebo ˇsed´ y povrch, je velice ˇcasto splnˇena rovnice 4.11 a pro segmentaci je poté pouˇzito (slabé) kriterium dané rovnic´ı 4.12. Nˇekteˇr´ı autoˇri porovn´ avali vliv pouˇzit´ı jednotliv´ ych pˇr´ıznak˚ u na v´ ysledek segmentace [16]. Z tabulky 4.4 je zˇrejmé, ˇze barevná segmentace pˇrináˇs´ı lepˇs´ı v´ ysledky, neˇz segmentace ˇsedot´ onov´ ych obrázk˚ u. Zároveˇ n je zˇrejmé, ˇze implementace v´ ypoˇcetnˇe nároˇcn´ ych algoritm˚ u zlepˇs´ı v´ ysledek segmentace pouze nepatrnˇe. Pˇr´ıznak(y) Intenzita (rovnice 4.12) Barva (rovnice 4.15) Barva + Textura

´ eˇsnost [%] Uspˇ 73.4 85.0 87.1

´ eˇsnost segmentace pˇri pouˇzit´ı r˚ Tabulka 4.4: Uspˇ uzn´ ych pˇr´ıznak˚ u

V roce 1980 provedl Y. Ohta rozsáhlé systematické experimenty, tak aby nalezl soubor vhodn´ ych a efektivn´ıch barevn´ ych atribut˚ u pro segmentaci nar˚ ustán´ım oblast´ı [9]. Zjistil, ˇze velmi kvalitn´ı atributy je moˇzné z´ıskat Karhunen–Loave [9] transformac´ı R,G,B hodnot. I1 (x, y) = (fR (x, y) + fB (x, y) + fG (x, y))/3, I2 (x, y) =

(

(fR (x, y) − fB (x, y))/2 (fB (x, y) − fR (x, y))/2,

(4.14) fR (x, y) > fB (x, y),

I3 (x, y) = (2 fG (x, y) − fR (x, y) − fB (x, y))/4, Tuto základn´ı sadu transformaˇcn´ıch rovnic je vhodné rozˇs´ıˇrit jeˇstˇe o vzdálenost ˇcervené a zelené, pˇr´ıpadnˇe ˇzluté a modré sloˇzky barvy: CR−G = (fR (x, y) − fG (x, y) + 1)/2,

(4.15)

CY −B = (fR (x, y) + fG (x, y) − 2 fB (x, y) + 2)/4, V´ ypoˇ cet vzd´ alenosti dvou barev Mˇeˇren´ı rozd´ılu dvou barevn´ ych odst´ın˚ u je jeden z nejd˚ uleˇzitˇejˇs´ıch problém˚ u pˇri anal´ yze obrazu. Závis´ı jednak na pouˇzitém barevném prostoru a jednak na pouˇzité metrice. Definice vzdálenosti dvou barevn´ ych odst´ın˚ u modelu HSV byla uvedena v kapitole 4.2.3 jako rovnice 4.10. V pˇr´ıpadˇe barevného modelu RGB se obvykle pouˇz´ıvá Euklidova metrika. Potom vzdálenost dvou bod˚ u v RGB prostoru je definována jako d2E (f (x, y), f (i, j)) = (fR (x, y) − fR (i, j))2 + (fG (x, y) − fG (i, j))2 + 2

(fB (x, y) − fB (i, j)) , 35

(4.16)

V pˇr´ıpadˇe segmentace nar˚ ust´ an´ım oblasti je vhodné umˇet spoˇc´ıtat také vzdálenost barvy od shluku barev. Shluk barev je v tomto pˇr´ıpadˇe zastoupen stˇredn´ı hodnotou jednotliv´ ych sloˇzek barevného modelu. d2E (f (x, y), S) = (fR (x, y) − SR )2 + (fG (x, y) − SG )2 +

(4.17)

2

(fB (x, y) − SB ) ,

Vzdálenost definovan´ a rovnic´ı 4.17 nebere v u ´vahu rozptyl barev okolo stˇredn´ı hodnoty a tedy v pˇr´ıpadˇe, ˇze shluk nen´ı dostateˇcnˇe homogenn´ı, v´ ysledkem nen´ı skuteˇcn´ a vzdálenost. Homogenitu shluku barev je moˇzné spoˇc´ıtat tak jako v kapitole 4.2.1. Pokud je smˇerodatná odchylka nadprahová, je vhodné pro v´ ypoˇcet vzdálenosti pouˇz´ıt Mahalanobiho vzd´ alenost, která je definována takto: dM (f (x, y), S) =

dE (f (x, y), S) q

,

(4.18)

σ(S)

kde σ(S) = (σR (S) + σG (S) + σB (S))/3 je smˇerodatná odchylka shluku barev. Vzdálenost barvy od shluku, nebo dvou shluk˚ u je moˇzné spoˇc´ıtat i jinak, napˇr´ıklad na základˇe statistické anal´ yzy shluku. V literatuˇre [6] se uvád´ı napˇr´ıklad tyto vzdálenosti Fisherova, Kolmogorov–Smirnovova, Cramer–von Mise, chi-square a mnoho dalˇs´ıch. Studovan´ e pˇ r´ıznaky pro segmentaci nar˚ ust´ an´ım oblasti Pˇri v´ yvoji vhodného algoritmu pro segmentaci silnice v dopravn´ı scénˇe jsem se zab´ yval také v´ ybˇerem vhodn´ ych pˇr´ıznak˚ u a segmentaˇcn´ıch kritéri´ı. Pouˇzit´ı nevhodného pˇr´ıznaku m˚ uˇze v´ yraznˇe sn´ıˇzit u ´spˇeˇsnost jinak vhodnˇe navrˇzeného algoritmu. V prvn´ı fázi v´ yvoje jsem pouˇz´ıval pouze ˇsedot´ onové obr´ azky a tyto pˇr´ıznaky: • pr˚ umˇern´ a hodnota jasu segmentu I=

n 1X fi , n i=1

(4.19)

• kontrast mezi dvˇema segmenty – definovan´ y jako rozd´ıl pr˚ umˇerné hodnoty jasu dvou sousedn´ıch segment˚ u, • pr˚ umˇern´ a hustota textury segmentu definovaná T (s) =

1 X X |fi − fj | As i j∈N (i) 8

(4.20)

kde fi je hodnota jasu i-tého pixelu, N (i) je mnoˇzina osmi sousedn´ıch pixel˚ ua As je plocha segmentu, definovaná jako poˇcet pixel˚ u, které leˇz´ı v segmentu. Zjistil jsem, ˇze kombinace prvn´ıch dvou pˇr´ıznak˚ u pˇrináˇs´ı lepˇs´ı v´ ysledky segmentace neˇz pˇri pouˇzit´ı pr˚ umˇerné hustoty textury. V dalˇs´ıch experimentech jsem pracovat uˇz v´ yhradnˇe s barevným obrazem a mnoˇzinu studovan´ ych pˇr´ıznak˚ u jsem rozˇs´ıˇril o: • pr˚ umˇerné hodnoty R, G, B sloˇzek barevného modelu RGB, • sloˇzky barevného modelu HSV (kapitola 4.2.3), 36

• Karhunen–Loaveho pˇr´ıznaky (4.14), • vzd´ alenosti ˇcervené a zelené, ˇzluté a modré sloˇzky barvy (4.15), • Euklidovu vzdálenost dvou barevn´ ych odst´ın˚ u (rovnice 4.16 a 4.17). Studovan´ a krit´ eria pro segmentaci nar˚ ust´ an´ım oblasti Vˇetˇsina pouˇzit´ ych kritéri´ı je zaloˇzena na v´ ypoˇctu vzdálenosti dvou barevn´ ych odst´ın˚ u, pˇr´ıpadnˇe vzdálenosti barevného odst´ınu od shluku barev. Pro v´ ypoˇcet vzdálenosti dvou barevn´ ych odst´ın˚ u je pouˇzit vzorec 4.16, pro vzdálenost od shluku barev vzorec 4.17. Kriterium I: dE (f (x, y), f (x + i, y + j)) ≤ TLHC

(4.21)

kde TLHC je hodnota prahu a (x + i, y + j); i = −1, 0, 1; j = −1, 0, 1, jsou souˇradnice pixel˚ u, které soused´ı s pixelem (x, y). Kriterium II: dE (f (x, y), S) ≤ TAHC

(4.22)

u – ve vˇetˇsine pˇr´ıpad˚ u 8-okol´ı pixelu f (x, y). kde TAHC je hodnota prahu, S je shluk pixel˚ 0 0 Aby bylo moˇzné specifikovat, zda pixel (x , y ) leˇz´ı v okol´ı pixelu (x, y), nebo regionu, kter´ y je s pixelem (x, y) reprezentován, zavád´ım dvˇe funkce: 0

   1,

0

N(i,j) (i , j ) =

RS (i, j) =

(

 

0

1, 0

if f (i0 , j 0 ) = f (i + l, j + k); l = −1, 0, 1; k = −1, 0, 1

if f (i, j) ∈ S,

(4.23)

(4.24)

Nyn´ı je moˇzné spoˇc´ıtat pr˚ umˇernou hodnotu jednotliv´ ych barevn´ ych sloˇzek shluku pi2 xel˚ u tak, ˇze pˇri v´ ypoˇctu budou pouˇzity pouze ty pixely, které do shluku na základˇe kritéria I (4.21) patˇr´ı a v´ ysledek tedy nebude ovlivnˇen ˇsumem. CN (i, j) =

P P l

k

N(i,j) (i + l, j + k)f (i + l, j + k) l k N(i,j) (i + l, j + k)

P P

(4.25)

Obdobnˇe pˇri pouˇzit´ı funkce 4.24 m˚ uˇzeme spoˇc´ıtat pr˚ umˇernou hodnotu a smˇerodatnou odchylku barevn´ ych sloˇzek uvnitˇr regionu S. CR (S) =

P P i

j

(4.26)

j

(4.27)

i

2 σR (S) 2

=

P P i

RS (i, j)f (i, j) j RS (i, j)

P P

RS (i, j) d2E (CR (S), f (i, j)) P P i j RS (i, j)

vzorec 4.25 je uveden pouze pro jednu sloˇzku barevného modelu

37

Pˇri pouˇz´ıt´ı v´ yˇse uveden´ ych vzorc˚ u m˚ uˇzeme redefinovat kriterium II. Kriterium II’ dE (f (i, j), CN (i, j)) ≤ TAHC 0

(4.28)

dE (f (i, j), CR (S)) ≤ TAHC 00

(4.29)

Pro správnou funkˇcnost kriteri´ı II a II’ je nutné ovˇeˇrit, zda testovan´ y region obsahuje dostatek pixel˚ u, které splˇ nuj´ı kriterium I (testovan´ y region je dostateˇcnˇe homogenn´ı). Kriterium III XX l

k

N(i,j) (i + l, j + k) ≤ Ap

(4.30)

Toto kriterium urˇcuje minimáln´ı poˇcet pixel˚ u, které mus´ı uvnitˇr regionu splˇ novat kriterium I. Pˇri pouˇzit´ı masky 3 × 3 jsem zjistil, ˇze optimáln´ı hodnota Ap je 6. Kriterium IV dE (CR (S), CR (S 0 )) ≤ TGHC

(4.31)

Toto kriterium urˇcuje, zda je moˇzné spojit dva sousedn´ı regiony do regionu jednoho. Kriterium IV je v hiearchické u ´rovni nejv´ yˇse a je tedy pouˇzité pro vlastn´ı nar˚ ustán´ı oblasti. Volba prahu V literatuˇre je moˇzné nalézt nˇekolik studi´ı, které se zab´ yvaly problémem urˇcen´ı prahu, pˇr´ıpadnˇe adaptivn´ım urˇcov´ an´ım prahu, na základˇe kontextuáln´ı nebo lokáln´ı informace. Zjednoduˇsenˇe je moˇzné ˇr´ıci, ˇze u ´spˇech segmentace nar˚ ustán´ım oblasti je tˇesnˇe spojen s vhodnou volbou prahu segmentaˇcn´ıho kriteria. Tyto prahy mohou b´ yt stejné pro vˇsechny obrázky, nebo se mohou mˇenit na základˇe vlastnost´ı obrazu. Hodnoty prahu mohou b´ yt konstantn´ı pro cel´ y obraz, nebo se mohou pr˚ ubˇeˇznˇe mˇenit – aktualizovat na základˇe spoˇc´ıtan´ ych lokáln´ıch charakteristik (napˇr´ıklad anal´ yza textury). Vˇetˇsina publikovan´ ych metod se vˇenuje v´ ypoˇctu prahu pro segmentaci prahován´ım s v´ıce prahy. Metody urˇcené pro v´ ypoˇcet prahu pro segmentaci nar˚ ustán´ım oblasti [8], jsou v´ ypoˇcetnˇe natolik nároˇcné, ˇze je nen´ı moˇzné pouˇz´ıt v segmentaˇcn´ıch algoritmech systému RS2 . Hodnoty prah˚ u jsou nastaveny a optimalizovány experimentálnˇe, tak aby byl algoritmus pouˇziteln´ y pro co nejvˇetˇs´ı mnoˇzstv´ı obrázk˚ u.

4.3

Algoritmus

V této kapitole budou popsány algoritmy segmentace zóny zájmu v obraze (AOI). Systém se sklád´ a z pˇeti hlavn´ıch algoritm˚ u, které jsou blokovˇe znázornˇeny na obrázku 4.9. Algoritmus I se pouˇz´ıv´ a pro v´ ypoˇcet homogenity textury povrchu vozovky. Na základˇe v´ ysledku algoritmu I je zvolena segmentaˇcn´ı metoda. Pokud je povrch vozovky dostateˇcnˇe homogenn´ı, je zvolen Algoritmus II – segmentace prahován´ım. V opaˇcném pˇr´ıpadˇe je pouˇzita barevná segmetace – Algoritmus III, tak jak byla popsána v kapitole 38

4.2.3. Algoritmus IV na základˇe porovnán´ı v´ ysledk˚ u segmentace s geometrick´ ym modelem dopravn´ı scény rozhodne o v´ ysledku segmentace. Pokud v pr˚ ubˇehu segmentace doˇslo k chybˇe, nebo v´ ysledek segmentace nebyl oznaˇcen jako zprávn´ y, pak algoritmus AOI pokraˇcuje zpracov´ an´ım dalˇs´ıho sn´ımku a ostatn´ı algoritmy systému RS2 zpracovávaj´ı obraz bez zóny zájmu. V pˇr´ıpadˇe kladného v´ ysledku je v obraze vyznaˇcen region, ve kterém se mohou na základˇe normy3 vyskytovat doprav´ı znaˇcky – Algoritmus V. Problematika segmentace zóny zájmu je natolika rozsáhlá, ˇze pˇri zadán´ı problému byla pˇrijata urˇcit´ a omezen´ı: 1. dopravn´ı scéna je sn´ım´ ana barevnou kamerou za denn´ıho svˇetla, 2. zónou zájmu se nerozum´ı oblast portál˚ u, 3. pˇred automobilem je vozovka bez pˇrekáˇzek do vzdálenosti alespoˇ n 50 m

4.3.1

Stanoven´ı homogenity povrchu vozovky

´ Uvodn´ ım algoritmem systému rozpoznán´ı zóny zájmu v obraze je algoritmus stanoven´ı homogenity textury povrchu vozovky. Na základˇe apriorn´ı informace je v obraze vymezena oblast, která je s velkou pravdˇepodobnost´ı souˇcást´ı povrchu vozovky. Velikost této oblasti je nutné volit tak, aby rozsah v´ ybˇeru byl statisticky pr˚ ukazn´ y. Experiment´ alnˇe jsem ovˇeˇril, ˇze testovan´ y region o ploˇse tis´ıc obrazov´ ych bod˚ u je pro v´ ypoˇcet základn´ıch statistik dostateˇcnˇe velk´ y a v´ ypoˇcetn´ı nároky jsou pˇrimˇeˇrené. Pˇri zvˇetˇsen´ı rozsahu v´ ybˇeru se vypoˇc´ıtané statistiky témˇeˇr nemˇen´ı, ale v´ ypoˇcetn´ı nároky algoritmu vzr˚ ustaj´ı.

Obr´ azek 4.10: Velikost a pozice testované oblasti

Jak je zˇrejmé z obrázku 4.10, oblast, která je pouˇzita pro v´ ypoˇcet homogenity, je um´ıstˇena uprostˇred v doln´ı ˇcásti obrazu. Pokud automobil jede v pravém j´ızdn´ım pruhu, pak je pˇri um´ıstˇen´ı testovac´ı oblasti do tohoto m´ısta s velkou pravdˇepodobnost´ı zajiˇstˇeno, ˇze bude reprezentovat data povrchu vozovky. Homogenita textury vozovky je stanovena na základˇe anal´ yzy histogramu a v´ ypoˇctu základn´ıch statistik, tak jak bylo posáno v kapitole 4.2.1. 3ˇ

CSN 73 6101 – Projektov´ an´ı silnic a d´ alnic

39

Obr´ azek 4.9: Blokové schema algoritmu segmentace zóny zájmu v obraze

40

Algoritmus I – Stanoven´ı homogenity textury vozovky 1:

Init:

2: 3:

INT gray LONG sum, sumr

4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:

RECT rect = {x,y,w,h} INT µ, σ DWORD size

size = (w − x + 1)(h − y + 1) for j = y to y + h do for i = x to x + w do gray = (3r + 6g + b)/10 sum = sum + gray sumr = sumr + gray 2 end for end for µ = sum/size p σ = (size · sumr − sum · sum)/(size · (size − 1)) if σ < c then return true else return false end if

Vstupem tohoto algoritmu jsou obrazová data z testovaného regionu. V pˇr´ıpadˇe, ˇze je smˇerodatn´ a odchylka spoˇctená na ˇrádku 15: menˇs´ı neˇz stanoven´ y konstantn´ı práh, pak je povrch vozovky dostateˇcnˇe homogenn´ı a pro segmentaci silnice je moˇzné pouˇz´ıt segmentaci prahov´ an´ım. V opaˇcném pˇr´ıpadˇe je nutné pouˇz´ıt barevnou segmentaci nar˚ ust´ an´ım oblasti.

4.3.2

Segmentace silnice v dopravn´ı sc´ enˇ e

Bˇehem v´ yvoje segmentace zóny zájmu jsem testoval tˇri algoritmy – segmentaci prahován´ım, segmentaci na základˇe detekce hran v obraze a barevnou segmentaci nar˚ ustán´ım oblasti. Po prvn´ıch experimentech a po zkuˇsenostech s rozpoznáván´ım geometrick´ ych obrazc˚ u v obraze jsem v´ yvoj omezil pouze na dvˇe metody – segmentaci prahov´ an´ım a barevnou segmentaci. Teoretická ˇcást tˇechto segmentaˇcn´ıch algoritm˚ u byla popsána v kapitole 4.2.1 resp. v kapitole 4.2.3. Ostatn´ı segmentaˇcn´ı techniky jsou v´ ypoˇcetnˇe mnohem nároˇcnˇejˇs´ı a t´ım nevhodné pro algoritmus vymezen´ı zóny zájmu v obraze, zvláˇstˇe pokud má b´ yt implementovan´ y v reálném ˇcase. Algoritmus II – Segmentace prahov´ an´ım 1: 2: 3: 4: 5:

Init:

INT w, start, token = 0 INT gray INT lef t, actlef t, right, actright INT t1 , t2 BORDER border

41

6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29:

lef t = c1 right = c2 for j = 1 to k do start = lef t + ((right − lef t)/2) token = start while token ≤ right + 1 do gray = (3r + 6g + b)/10 if t1 < gray ∧ t2 > gray then actright = token end if token = token + 1 end while token = start while token ≥ lef t − 1 do gray = (3r + 6g + b)/10 if t1 < gray ∧ t2 > gray then actlef t = token end if token = token − 1 end while right = actright lef t = actlef t border = BorderPrediction(lef t, right) end for

Promˇenn´ a BORDER je abstraktn´ı datov´ y typ, kter´ y se pouˇz´ıvá pro popis a predikci okraje silnice v jednotliv´ ych segmentovan´ ych vrstvách. Konstanty c1 a c2 na ˇrádku 6: a 7: jsou jedn´ım z parametr˚ u algoritmu. Pomoc´ı tˇechto konstant je nastavena ˇs´ıˇrka silnice v obraze v nulté vrstvˇe. Toto nastaven´ı nen´ı bezpodm´ıneˇcnˇe nutné, zvláˇstˇe pokud jsou zpracov´ av´ any sekvence sn´ımk˚ u. Konstanta k na ˇrádku 8: ovlivˇ nuje vzdálenost, do jaké bude silnice pˇred automobilem segmentována (poˇcet segmentovan´ ych vrstev). Funkce BorderPrediction() na ˇr´ adku 28: se pouˇz´ıvá k predikci polohy a ˇs´ıˇrky i + 1 vrstvy na základˇe v´ ysledk˚ u segmentace vrstvy i. Okraj silnice je predikován na základˇe apriorn´ıch pravdˇepodobnost´ı polohy silnice v obraze, tak jak bylo popsáno v kapitole 4.2.1 a znázornˇeno na obrázku 4.3. V pˇr´ıpadˇe, ˇze povrch vozovky nen´ı dostateˇcnˇe homogenn´ı, pro segmentaci silnice v obraze nelze pouˇz´ıt rychlou segmentaci prahován´ım. V tˇechto pˇr´ıpadech je nutné pouˇz´ıt segmentaci nar˚ ustán´ım oblasti, která je zaloˇzena na anal´ yze lokáln´ı informace v okol´ı testovaného regionu.

42

Algoritmus III – Barevn´ a segmentace 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45:

Init:

INT w, start, token = 0 INT gray, fn , fo INT lef t, actlef t, right, actright RECT new, old BORDER border

for j = 1 to k do while token ≤ right + 1 do if PixelCount(new) ≥ Ta then for all pixels in new do fn = Average(new) end for if dE (fn , fo ) ≤ TLHC then actright = token token = token + widthof (new) Swap(new, old) else token = token + 1 fo = Average(old) end if else token = token + 1 fo = Average(old) end if end while token = start while token ≥ lef t − 1 do if PixelCount(new) ≥ a then for all pixels in new do fn = Average(new) end for if dE (fn , fo ) ≤ TLHC then actlef t = token token = token − widthof (new) Swap(new, old) else token = token − 1 fo = Average(old) end if else token = token − 1 fo = Average(old) end if end while lef t = actlef t right = actright 43

46: 47:

border = BorderPrediction(lef t, right) end for

48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66:

function PixelCount(region) for all pixels in region do sumr = sumr + fr sumg = sumg + fg sumb = sumb + fb end for fr = sumr /sizeof (region) fg = sumg /sizeof (region) fb = sumb /sizeof (region) for all pixels in region do dE = (fr − fr )2 + (fg − fg )2 + (fb − fb )2 if dE ≤ c1 then Ap = Ap + 1 designate pixel end if end for return Ap end function

67: 68: 69: 70: 71: 72: 73: 74:

function Average(region) for all designated pixels in region do sumi = sumi + fi , i ∈ {R, G, B} end for fi = sumi /sizeof (designated pixels), i ∈ {R, G, B} return fi end function

Barevn´ a segmentace silnice je zaloˇzena na algoritmu nar˚ ustan´ı oblasti. V prvn´ı fázi je cel´ y obraz rozdˇelen do vrstev. Poloha a velikost prvn´ı vrstvy je stanovena na základˇe apriorn´ı informace, pˇr´ıpadnˇe na základˇe v´ ysledk˚ u segmentace pˇredchoz´ıho sn´ımku. Poloha a velikost vˇsech následuj´ıc´ıch vrstev je predikována z v´ ysledk˚ u segmentace v pˇredchoz´ıch vrstvách. V tomto algoritmu jsou pouˇzita segmentaˇcn´ı kriteria I, II’ a III. Uveden´ y algoritmus je moˇzné velmi jednoduˇse rozˇs´ıˇrit i o kriterium IV pouˇzit´ım funkce ˇ CompareRegions(). Ctvrt´ e segmentaˇcn´ı kriterium je vhodné pouˇzit pouze v pˇr´ıpadˇe, ˇze velikost testovan´ ych (a porovnávan´ ych) region˚ u je vˇetˇs´ı neˇz 3 × 3 obrazové body. Tˇret´ı segmentaˇcn´ı kriterium je zastoupeno funkc´ı PixelCount(). Tato funkce zároveˇ n oznaˇc´ı pouze ty obrazové elementy, které budou pouˇzity pro v´ ypoˇcet pˇr´ıznak˚ u. T´ım je omezen vliv ˇsumu v obraze na v´ ysledek v´ ypoˇctu pˇr´ıznak˚ u. Funkce Swap() zvyˇsuje efektivitu celého algoritmu t´ım, ˇze jsou poˇc´ıtané pouze pˇr´ıznaky nov´ ych (sousedn´ıch) region˚ u. Funkce BorderPrediction(), konstanty a promˇenné pouˇzité v tomto algoritmu maj´ı stejn´ y v´ yznam jako v pˇredchoz´ıch algoritmech.

44

Rozˇ s´ıˇ ren´ı algoritmu III 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:

function CompareRegions(region1 , region2 ) for all designated pixels in region1 and region2 do sum1i = sum1i + fi1 , i ∈ {R, G, B} sum2i = sum2i + fi2 , i ∈ {R, G, B} end for fi1 = sum1i /sizeof (region1 ), i ∈ {R, G, B} fi2 = sum2i /sizeof (region2 ), i ∈ {R, G, B} if dE (f1 , f2 ) ≤ TGHC then return true else return f alse end if end function

4.3.3

Revize v´ ysledku segmentace

Zóna zájmu je v obraze stanovena na základˇe v´ ysledku segmentaˇcn´ıho algoritmu. Z tohoto d˚ uvodu je nutné rozhodnout, zda segmentace povrchu vozovky byla u ´spˇeˇsná. Zónu zájmu nen´ı moˇzné stanovit, pokud v´ ysledek segmentace neodpov´ıdá skuteˇcnosti. Pˇri segmentaci silnice m˚ uˇze doj´ıt v podstatˇe pouze k dvˇema chybám: 1. vlivem slabého segmentaˇcn´ıho kritéria, doˇslo k pˇresegmentován´ı, 2. vlivem pˇr´ıliˇs silného segmentaˇcn´ıho kritéria (pˇr´ıpadnˇe v´ yrazné poruchy v textuˇre vozovky, pˇrek´ aˇzky na silnici, . . . ) dojede k podsegmentován´ı. Tyto chybné v´ ysledky je nutné identifikovat, aby nedocházelo k nesprávnému stanoven´ı zóny zájmu. V´ yhodou pˇri segmentaci silnice je apriorn´ı znalost scény. Pˇri pouˇzit´ı tˇechto informac´ı je moˇzné vytvoˇrit jednoduch´ y geometrick´ y model polohy silnice ve scénˇe a porovn´ an´ım v´ ysledk˚ u segmentace s t´ımto modelem rozhodnout o v´ ysledku segmentace. Algoritmus IV - Revize v´ ysledku 1: 2: 3: 4: 5: 6: 7: 8:

l = posledn´ı segmentovan´ y pixel ve vrstvˇe 0 h = posledn´ı segmentovan´ y pixel ve vrstvˇe n α = arctan(n/|l − h|) if t1 < α < t2 then segmentace je zprávn´ a else chybn´ a segmentace end if

45

4.3.4

Geometrick´ y model a stanoven´ı z´ ony z´ ajmu

Zóna zájmu je v obraze stanovena porovnán´ım s geometrick´ ym modelem scény. Je velmi obt´ıˇzné urˇcit polohu a optimalizovat velikost zóny zájmu pouze na základˇe statick´ ych 2 obrázk˚ u. Po pˇr´ıpadné modifikaci algoritm˚ u systému RS na sekvence obrázk˚ u by bylo moˇzné, po dalˇs´ıch experimentech, v´ yraznˇe zmenˇsit velikost zóny zájmu.

Obr´ azek 4.11: Zóna zájmu v obraze

Rozpoznán´ı geometrického tvaru dopravn´ıch znaˇcek prob´ıhá v nˇekolika u ´rovn´ıch (rozliˇsen´ıch) pyramid´ aln´ı struktury. Tento pˇr´ıstup umoˇzn ˇuje rozpoznán´ı dopravn´ıch znaˇcek v nˇekolika vzdálenostech pˇred automobilem, pˇri pouˇzit´ı pouze jednoho, univerz´ aln´ıho algoritmu. Optimáln´ım ˇreˇsen´ım by bylo vymezen´ı zóny zájmu pro kaˇzdou vzdálenost danou pyramid´ aln´ı strukturou, pˇr´ıpadnˇe vymezit pouze jednu zónu zájmu, a to takovou, ve které bude m´ıt dopravn´ı znaˇcka vhodnou velikost pro klasifikaˇcn´ı algoritmus. Tento pˇr´ıstup vyˇzaduje spoleˇcné rozhran´ı a v´ ymˇenu informac´ı jednotliv´ ych algoritm˚ u systému RS2 , které jeˇstˇe nen´ı vyˇreˇseno. Algoritmus V – Vymezen´ı z´ ony z´ ajmu 1: 2: 3: 4: 5: 6: 7: 8:

Init:

RECT aoi INT width

[i, j] – posledn´ı segmentovan´ y pixel ve vrstvˇe n width = GetPictureWidth() aoi.x = cx · i aoi.y = cy · j aoi.w = aoi.x + (width − i) − k aoi.h = aoi.y + l

46

Kapitola 5

Experimenty a v´ ysledky Algoritmy segmentace zóny zájmu v obraze jsem vyv´ıjel od bˇrezna roku 1997. Obrazov´ a data pro prvn´ı experimenty jsem z´ıskal digitalizac´ı barevn´ ych a ˇcernob´ıl´ ych fotografi´ı. Protoˇze tyto obrázky sv´ ym charakterem neodpov´ıdaly zadanému problému, zaˇcal jsem od ˇcervna roku 1997 pracovat s obrazem nasn´ıman´ ym z jedouc´ıho automobilu bˇeˇznou Video 8 kamerou. Tento video záznam byl poté grabbován, pˇreveden na sekvenci sn´ımk˚ u 1 ve formátu BMP, na poˇc´ıtaˇci SGI Indy . Pouˇzit´ı poˇc´ıtaˇce SGI bylo v´ yhodné zejména pro bezproblémovou práci s kompozitn´ım video-signálem. Pˇri digitalizaci na bˇeˇzném grabberu jsem mˇel problémy se synchronizac´ı jednotliv´ ych sn´ımk˚ u a proto byl v´ ysledek témˇeˇr nepouˇziteln´ y. Koncem roku 1997 jsme pˇri v´ yvoji systému RS2 zaˇcaly pouˇz´ıvat barevnou digitáln´ı CCD kameru Sony, která velmi dobˇre spolupracuje s grabberem firmy Matrox. Dalˇs´ı obrazov´ a data pro v´ yvoj algoritm˚ u segmentace zóny zájmu byla z´ıskávána pouze touto kamerou. Vˇetˇsina obrazov´ ych dat v projektu RS2 byla nasn´ımána z jedouc´ıho automobilu pˇr´ımo do pamˇeti poˇc´ıtaˇce a ukládána na disk za podm´ınek, které odpov´ıdaj´ı bˇeˇznému provozu na pozemn´ıch komunikac´ıch. V souˇcasné dobˇe je k dispozici databáze 3000 sn´ımk˚ u dopravn´ıch scén. Vˇsechny sn´ımky jsou v rozliˇsen´ı PAL a pokr´ yvaj´ı vˇetˇsinu situac´ı, které mohou na pozemn´ıch komunikac´ıch nastat. Nˇekteré sekvence byly sn´ımány za zhorˇsen´ ych meterologick´ ych podm´ınek (za deˇstˇe a po deˇsti). V databázi jsou jednak sn´ımky dobˇre znaˇcen´ ych silnic s kvalitn´ım povrchem, ale také sn´ımky neznaˇcen´ ych komunikac´ı s poˇskozen´ ym povrchem. V´ yvoj algoritm˚ u segmentace zóny zájmu v obraze prob´ıhal pˇreváˇznˇe na poˇc´ıtaˇc´ıch IBM PC kompatibiln´ıch s procesory Intel Pentium pod operaˇcn´ımy systémy MS Windows 95/NT a Linux. Pˇri v´ yvoji bylo pouˇzito programové vybaven´ı zejména firem The MathWorks Inc. – Matlab a firmy Microsoft – MS Visual C++. Poˇcáteˇcn´ı experimenty prob´ıhaly v prostˇred´ı programu Matlab 4.2. Aplikace poˇc´ıtaˇcového vidˇen´ı jsou nároˇcné na v´ ypoˇcetn´ı v´ ykon, kter´ y Matlab jako interpreter nem˚ uˇze poskytnout. Proto jsem se rozhodl vytvoˇrit vlastn´ı v´ yvojové prostˇred´ı v jazyku C++ pro ˇreˇsen´ı segmentace zóny zájmu v obraze. Toto prostˇred´ı bude popsané v kapitole 6. Na následuj´ıc´ıch stránk´ ach budou uvedeny komentované v´ ysledky systému pro segmentaci zóny zájmu v obraze. Jedná se o typické obrázky z testovac´ı databáze. Obdobn´ ych v´ ysledk˚ u je dosaˇzeno i u ostatn´ıch obrázk˚ u stejné tˇridy a typu. 1

pouˇzit´ı této v´ ypoˇcetn´ı techniky umoˇznilo Oddˇelen´ı zpracov´ an´ı obrazu UTIA CAS

47

5.1

V´ ysledky

V této kapitole budou shrnuty v´ ysledky algoritmu segmentace zóny zájmu v obraze v situac´ıch, které mohou na pozemn´ıch komunikac´ıch nastat. Uvedeno je pouze nˇekolik charakteristick´ ych obrázk˚ u. Obdobn´ ych v´ ysledk˚ u je dosaˇzeno i pro vˇetˇsinu ostatn´ıch obrázk˚ u z testovac´ı databáze. V´ ypoˇcet segmentace zóny zájmu v obraze na poˇc´ıtaˇci s procesorem Pentium 100 MHz trvá 50 ms. V pˇr´ıpadˇe implementace algoritm˚ u v ANSI C (tedy bez tˇr´ıd MFC) se ˇcas v´ ypoˇctu dále sn´ıˇz´ı na u ´roveˇ n stovek mikrosekund. Na obrázku 5.2 jsou uvedeny v´ ysledky algoritmu pro silnice bez dopravn´ıho znaˇcen´ı (vod´ıc´ıho prouˇzku, stˇredové ˇc´ ary) a s ˇcásteˇcnˇe poˇskozen´ ym povrchem vozovky. V tˇechto pˇr´ıpadech je segmentace hranovou detekc´ı nevhodná. Na obrázku 5.3 jsou pˇreváˇznˇe obrázky s kvalitn´ım povrchem vozovky a s dopravn´ım znaˇcen´ım. Tyto dopravn´ı scény je moˇzné segmentovat i pomoc´ı metod uveden´ ych v kapitole 3.1. Na obrázc´ıch 5.4 je zaznamen´ an pr˚ ujezd Prahou z Dejvic na Jiˇzn´ı Mˇesto. Na obrázku 5.1 jsou pˇr´ıklady situac´ı, ve kter´ ych zóna zájmu nebyla stanovena. V tˇechto pˇr´ıpadech (6 %) segmentace silnice probˇehne u ´spˇeˇsnˇe, ale jej´ı v´ ysledek nesplˇ nuje kritéria pro stanoven´ı zóny zájmu v obraze. Ve 2% pˇr´ıpad˚ u doch´ az´ı ˇspatnému v´ ysledku segmentace. Tyto pˇr´ıpady jsou identifikov´ any algoritmem IV a nen´ı pro nˇe zóna zájmu stanovena.

Obr´ azek 5.1: Pˇr´ıklad scén, ve kter´ ych zóna zájmu nebyla stanovena

48

Obr´ azek 5.2: V´ ysledky segmentace zóny zájmu v obraze – neznaˇcené silnice

49

Obr´ azek 5.3: V´ ysledky segmentace zóny zájmu v obraze – znaˇcené silnice

50

Obr´ azek 5.4: V´ ysledky segmentace zóny zájmu v obraze – mˇesto

51

Obr´ azek 5.5: V´ ysledky segmentace zóny zájmu v obraze – mˇesto

52

Kapitola 6

Implementace Zpracov´ an´ı obrazu poˇc´ıtaˇcem vyˇzaduje znaˇcn´ y v´ ypoˇcetn´ı v´ ykon, zvláˇstˇe pokud má b´ yt implementované v reálném ˇcase (kapitola 3). Algoritmy poˇc´ıtaˇcového vidˇen´ı je moˇzné vyv´ıjet v r˚ uzn´ ych prostˇred´ıch. Pod operaˇcn´ım systémem MS Windows je velmi obl´ıben´ y systém Matlab a jeho rozˇs´ıˇren´ı – Image Processing Toolbox. V operaˇcn´ım systému Linux existuje ekvivalentn´ı systém pro zpracován´ı signál˚ u a obrazu – Khoros. Jak Matlab tak i Khoros jsou interprety a tedy algoritmy v nich implementované jsou pomalé. Z tohoto d˚ uvodu nejsou vhodné pro v´ yvoj rozsáhlejˇs´ıch aplikac´ı jako je systém rozpoznán´ı a klasifikace dopravn´ıch znaˇcek. Naˇs´ım c´ılem je implementace systému RS2 v reálném ˇcase prostˇrednictv´ım signálového procesoru TMS320C80. Tento procesor se programuje pˇreváˇznˇe v assembleru, pˇr´ıpadnˇe v jazyce C. Proto vˇsechny d´ılˇc´ı algoritmy byly programované v jazyce C s t´ım, ˇze jejich implementace v prostˇred´ı digitáln´ıho signálového procesoru bude snaˇzˇs´ı. Pro v´ yvoj algoritm˚ u segmentace zóny zájmu v obraze jsem se rozhodl vytvoˇrit samostatnou aplikaci – Zone, která bude popsaná na následuj´ıc´ıch stránkách.

6.1

Objektovˇ e orientovan´ y pˇ r´ıstup

Aplikace Zone byla naprogramována pod operaˇcn´ım systémem MS Windows ve v´ yvojovém prostˇred´ı firmy Microsoft – MS Visual C++ 4.2 a s pouˇzit´ım knihovny MFC ve verzi 4.0. Aplikace je tvoˇrena kompozic´ı nˇekolika tˇr´ıd. Pro základn´ı operace s obrazem, jako je nahráv´ an´ı a uklád´ an´ı obrázk˚ u ve formátech BMP, GIF, PNG, JPEG jsem zvolil 1 tˇr´ıdy z knihovny CImage , kterou vytvoˇril Julian Smart. Metody této tˇr´ıdy mimo jiné umoˇzn ˇuj´ı modifikovat vstupn´ı obraz na u ´rovni jednotliv´ ych pixel˚ u – pˇristupovat na dané souˇradnice v obraze, ˇc´ıst a mˇenit RGB hodnoty pixel˚ u atp. Pro vlastn´ı implementaci algoritm˚ u segmentace zóny zájmu v obraze, popsan´ ych v této práci, jsem vytvoˇril následuj´ıc´ı tˇr´ıdy: • CCVLib – metody této tˇr´ıdy umoˇzn ˇuj´ı nahrávat a ukládat obrazová data, pˇristupovat k metodám segmentaˇcn´ıch algoritm˚ u, které jsou implementované v následuj´ıc´ıch tˇr´ıd´ ach. Mezi atributy tˇr´ıdy CCVlib patˇr´ı pˇreváˇznˇe globáln´ı struktury pouˇz´ıvané v ostatn´ıch tˇr´ıd´ ach. • CHistogram – metody této tˇr´ıdy ˇreˇs´ı problematiku implementace anal´ yzy histogramu. Souˇc´ ast´ı této tˇr´ıdy je i algoritmus segmentace prahován´ım. 1

[email protected], http://web.ukonline.co.uk/Members/julian.smart

53

• CEdge - tˇr´ıda implementuj´ıc´ı Sobel˚ uv hranov´ y detektor • CColourSeg – metody této tˇr´ıdy implementuj´ı transformaci RGB barevného modelu na model HSV a barevnou segmentaci nar˚ ustán´ım oblasti, tak jak je popsaná v této práci. • CArea – vlastn´ı v´ ypoˇcet polohy a velikosti zóny zájmu na základˇe v´ ysledk˚ u segmentaˇcn´ıch algoritm˚ u pˇredchoz´ıch tˇr´ıd.

6.2

Aplikace Zone

Program Zone byl optimalizov´ an pro procesor Intel Pentium. Pro uspokojiv´ y chod aplikace je nutn´ y poˇc´ıtaˇc s procesorem Pentium, operaˇcn´ı pamˇet´ı alespoˇ n 32 MB a operaˇcn´ım systémem MS Windows 95 nebo MS Windows NT 4.0. Program nepouˇz´ıv´ a registraˇcn´ı databáze uveden´ ych operaˇcn´ıch systému, konfiguraˇcn´ı informace jsou zapisovány do hlavn´ıho adresáˇre disku C:.

Obr´ azek 6.1: Aplikace segmentace zóny zájmu – Zone

Obrazovka programu Zone (obrázek 6.1) se skládá z nˇekolika ˇcást´ı. Program je moˇzné ovl´ adat pomoc´ı rolovac´ıho menu nebo pomoc´ı nástrojové liˇsty. Základn´ı parametry segmentaˇcn´ıch algoritm˚ u se nastavuj´ı zmˇenamy konstant v ovládac´ım panelu (obr´ azek 6.2). Horn´ı polovina obrazovky je tvoˇrena databáz´ı obrázk˚ u se základn´ımy 54

informacemi. Pouˇzit´ım pravého tlaˇc´ıtka myˇsi je moˇzné vyvolat ”pop-up” menu ve kterém lze ke kaˇzdému obrázku vytvoˇrit komentáˇre a t´ım zlepˇsit orientaci v rozsáhl´ ych datab´ az´ıch. Databáze umoˇzn ˇuje rychl´ y pˇr´ıstup ke vˇsem obrázk˚ um, které mohou b´ yt uloˇzeny na r˚ uzn´ ych disc´ıch (i s´ıt’ov´ ych) a t´ım v´ yraznˇe urychluje proces v´ yvoje a testován´ı segmentaˇcn´ıch algoritm˚ u. Doln´ı polovina obrazovky je tvoˇrena pohledem na origin´ aln´ı a segmentovan´ y obraz. V dialogu zone status jsou uvádˇeny d´ılˇc´ı informace o pr˚ ubˇehu segmentace a stanoven´ı vlastn´ı zóny zájmu.

Obr´ azek 6.2: Ovládac´ı panel programu Zone

Ovl´ adac´ı panel slouˇz´ı k nastavován´ı parametr˚ u algoritm˚ u segmentace zóny zájmu. Pod záloˇzkou Segmentation se nastavuj´ı hodnoty promˇenn´ ych segmentaˇcn´ıch algoritm˚ u, typ segmentaˇcn´ıho algoritmu a pouˇzit´ y barevn´ y model a jeho metrika. Pod záloˇzkou Prediction se nastavuj´ı parametry revize v´ ysledku segmentace a konstanty pouˇzité pro vlastn´ı stanoven´ı zóny zájmu. Pod záloˇzkou Options je nutné nastavit cestu k obrázk˚ um a k databázov´ ym dokument˚ um. Ovládac´ı panel se vyvolává kliknut´ım na odpov´ıdaj´ıc´ı tlaˇc´ıtko nástrojové liˇsty, pˇr´ıpadnˇe volbou v rolovac´ım menu.

55

Kapitola 7

Z´ avˇ er V této diplomové práci byl popsán v´ yvoj metody identifikace zóny zájmu v obraze. Zóna zájmu je definov´ ana na základˇe segmentace povrchu vozovky a geometrického modelu silnice v dopravn´ı scénˇe. Ostatn´ı projekty, které ˇreˇs´ı problematiku autonomn´ıch vozidel (kapitola 3.1) pˇristupuj´ı k rozpoznán´ı silnice v obraze odliˇsnˇe. Informace o poloze silnice v obraze je z´ısk´ ana na základˇe hranové detekce vod´ıc´ıho prouˇzku. T´ım se problematika zuˇzuje pouze na dobˇre znaˇcené silnice s nepoˇskozen´ ym povrchem. Po prostudov´ an´ı jiˇz implementovan´ ych metod jsem se rozhodl problematiku rozˇs´ıˇrit o segmentaci neznaˇcených silniˇcn´ıch komunikac´ı, s t´ım, ˇze na povrch (texturu) vozovky nejsou kladeny ˇz´ adné speciáln´ı poˇzadavky (kapitola 4.3). Vyvinuté algoritmy jsou natolik obecné, ˇze je je moˇzné po drobn´ ych u ´pravách pouˇz´ıt i pro ˇreˇsen´ı dalˇs´ıch problém˚ u autonomn´ıch vozidel (navigace, steering, . . . ). Vˇsechny algoritmy, popsané v této práci jsou navrˇzené s ohledem na implementaci v reálném ˇcase prostˇrednictv´ım signálového procesoru firmy Texas Instruments TMS320C80. V´ ysledky prezentované v kapitole 5.1 je moˇzné dále zlepˇsit pouˇzit´ım speciáln´ıch senzor˚ u. Poˇcet chybn´ ych v´ ysledk˚ u algoritmu identifikace zóny zájmu v obraze by bylo moˇzné sn´ıˇzit implementac´ı dalˇs´ıch metod, které analyzuj´ı dopravn´ı scénu. Jedná se zejména o rozpoznán´ı kˇriˇzovatek a detekci pˇrekáˇzek na silnici. I pˇres tato omezen´ı je popsaná metoda dostateˇcnˇe robustn´ı a tedy vhodná pro identifikaci zóny zájmu v obraze v systému RS2 .

ˇ Závˇerem bych chtˇel podˇekovat vˇsem profesor˚ um CVUT, vedouc´ımu diplomové práce Ing. Pavlu Zahradn´ıkovi za cenné rady a pˇripom´ınky, a v neposledn´ı ˇradˇe rodiˇc˚ um za podporu bˇehem studi´ı.

56

Literatura [1] Pujas P., Aldon M.J.: Robust Colour Image Segmentation, Université Montpellier II/CNRS, Internal Report [2] Nov´ ak M., Faber J., Kufudaki O.: Neuronové s´ıtˇe a informaˇcn´ı systémy ˇzivých organism˚ u, Grada, Praha 1993 ˇ [3] Hlav´ aˇc V., Sonka M.: Poˇc´ıtaˇcové vidˇen´ı, Grada, Praha 1992 [4] Ballard D.H., Brown C.M.: Computer Vision, Prentice–Hall, Englewood Cliffs, 1982 [5] Seitz P.: Using local orientational information as image primitive for robust object recognition, SPIE Vol. 1199 Visual Communications and Image Processing, 1989 [6] Hofmann T., Puzicha J., Buhmann J.: A deterministic annealing framework for unsupervised texture segmentation, Rheinische Friedrich – Wilhelms – Universität, Bonn, 1996 [7] Kotek Z., Maˇr´ık V.: Metody rozpozn´ av´ an´ı a jejich aplikace, Academia, Praha, 1993 [8] Tremeau A., Borel N.: A region growing and merging algorithm to color segmentation, Pattern Recognition, 30(7), 1997 [9] Pal N. R., Pal S. K.: A review on image segmentation techniques, Pattern Recognition, 26(9), 1993 [10] Likeˇs J., Machek J.: Matematick´ a statistika, SNTL, Praha, 1988 [11] Beneˇs V., Dohnal G.: Pravdˇepodobnost a matematick´ a statistika, Doplˇ nkové skripˇ tum, CVUT, Praha, 1993 [12] Zikmund T.: Identifikace geometrických tvar˚ u v obraze, Diplomová práce, FEL ˇ CVUT, 1997, Praha [13] LeBlanc D.J., Gregory E.J.: CAPC: A Road–Departure Prevention System, IEEE Control Systems, (12), 1996 [14] Curwen R., Blake A.: Active Vision, MIT Press, Cambridge, MA, 1992 [15] Seitz P., Lang G.K., Gilliard B., Pandazis J.C.: The robust recognition of traffic signs from a moving car, Proc 13th DAGM symposium on pattern recognition, Informatik-Fachberichte, Springer, Berlin, 1991

57

[16] Campbell N.W., Mackeown P.J., Thomas B.T., Troscianko T.: Interpreting image databases by region classification, Pattern Recognition, 30(4), 1997 [17] Kumar V.P., Desai U.B.: Image Interpretation Using Bayesian Networks, IEEE Transactions on pattern analysis and machine intelligence, vol. 18, No. 1, January 1996 [18] Kim Y., Yang H.S.: An Integration Scheme for Image Segmentation and Labeling Based on Markov Random Fiel Model, IEEE Transactions on pattern analysis and machine intelligence, vol. 18, No. 1, January 1996 [19] Marroquin J.L., Girosi F.: Some Extensions of the K-Means Algorithm for Image Segmentation and Pattern Classification, C.B.C.L. Paper No. 079, Massachusetts Institute of Technology, 1993 [20] Saber E., Tekalp A.M., Bozdagi G.: Fusion of color and edge information for improved segmentation and edge linking, Image and Vision Computing, 15, 1997 [21] Priese L., Rehrmann V.: A Fast Hybrid Color Segmentation Method, Institut f¨ ur Informatik, Universit¨ at Koblenz-Landau [22] Harju P.T.:Polynomial Prediction Using Incomplete Data, IEEE Transaction on Signal Processing, Vol. 45, No. 3. March 1997 [23] Wildes R.P.: Iris Recognition: An Emerging Biometric Technology, Proceedings of the IEEE, Vol. 85, No. 9, September 1997 [24] Nickels K.M., Hutchinson S.: Texture image segmentation: returning multiple solutions, Image and Vision Computing, 15, 1997 [25] Nov´ ak V.: Fuzzy mnoˇziny a jejich aplikace, Matematick´ y semináˇr SNTL, Praha 1990 [26] L´ıbal V., Zikmund T., Pacl´ık P., Král´ık M., Kováˇr B., Zahradn´ık P., Vlˇcek M., Traffic Signs Identification and Automatic Template Generation, Proc Workˇ shop’96, CVUT Praha, 1996 [27] L´ıbal V., Pacl´ık P., Kov´ aˇr B., Zahradn´ık P., Vlˇcek M.: Road Sign Recognition System, Texas Instruments DSP Challenge, Praha 1997 [28] Rybiˇcka J.: LATEX pro zaˇc´ ateˇcn´ıky, Konvoj, Brno, 1995 [29] Eco U.: Jak napsat diplomovou pr´ aci, Votobia, Olomouc 1997 ˇ e Budˇejovice 1992 [30] Herout P.: Uˇcebnice jazyka C, Kopp, Cesk´ ˇ [31] Br˚ uha I, Richta K.: Programming Language C, skripta CVUT, Praha 1996 [32] Microsoft: Integrovan´ a n´ apovˇeda vývojového prostˇred´ı MS Visual C++, 1994-98 [33] Microsoft: Microsoft Developer Network, CD-ROM, 1997 [34] Dokumentace operaˇcn´ıho systému Linux a DTP systému teTEX

58

Fakulta dopravní ČVUT v Praze. Identifikace zóny zájmu v obraze

Recommend Documents