ˇ Fakulta dopravn´ı CVUT v Praze
Bohumil Kov´aˇr Identifikace z´ ony z´ ajmu v obraze
1998
Prohl´ aˇ sen´ı
ˇ Cestnˇ e prohlaˇsuji, ˇze jsem diplomovou pr´aci vypracoval samostatnˇe, s pouˇzit´ım uveden´e literatury a za pˇrispˇen´ı vedouc´ıho diplomov´e pr´ace.
..........................................
ˇ Fakulta dopravn´ı CVUT v Praze Identifikace z´ ony z´ ajmu v obraze Bohumil Kov´aˇr 1998 Kl´ıˇ cov´ a slova: poˇc´ıtaˇcov´e vidˇen´ı, zpracov´an´ı obrazu, z´ona z´ajmu, segmentace, autonomn´ı vozidlo, dopravn´ı znaˇcky, silnice
Abstrakt
Tato pr´ace je souˇc´ ast´ı projektu “Automatick´e rozpozn´ an´ı a klasifikace dopravn´ıch znaˇcek 2 – RS ”. C´ılem t´eto diplomov´e pr´ace 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´e s velkou pravdˇepodobnost´ı oˇcek´avat svisl´e dopravn´ı znaˇcen´ı. Z´ona z´ajmu je v obraze rozpozn´ana na z´akladˇe segmentace silnice. V t´eto pr´aci jsou pops´any z´akladn´ı segmentaˇcn´ı techniky a jejich vhodnost pro ˇreˇsen´ı dan´e problematiky. Metoda identifikace z´ony z´ajmu, popsan´a v t´eto pr´aci, byla experiment´alnˇe ovˇeˇrena na re´aln´ ych datech dopravn´ıch sc´en. V z´avˇeru t´eto pr´ace je uveden vlastn´ı algoritmus a jeho implementace.
Obsah ´ 1 Uvod 2 Poˇ c´ıtaˇ cov´ e vidˇ en´ı 2.1 Z´akladn´ı pojmy . . . . . . . . . 2.2 Digit´aln´ı 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´an´ım . . . . . . . . . . . . 4.2.2 Segmentace prostˇrednictv´ım hranov´e detekce 4.2.3 Barevn´a segmentace . . . . . . . . . . . . . . 4.3 Algoritmus . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Stanoven´ı homogenity povrchu vozovky . . . 4.3.2 Segmentace silnice v dopravn´ı sc´enˇe . . . . . 4.3.3 Revize v´ ysledku segmentace . . . . . . . . . . 4.3.4 Geometrick´ y model a stanoven´ı z´ony z´ajmu .
. . . . . . . . . .
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´em automatick´e klasifikace dopravn´ıch znaˇcek RS2 . . . . . . . . . .
12
3.1
Paraleln´ı architektura syst´emu 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´eho obrazu a povrchu silnice . . . . . . Predikce okraje silnice . . . . . . . . . . . . . . . . . . . . . . . . V´ ysledky segmentace prahov´an´ım (obr´azek 012.bmp a 041.bmp) V´ ysledky hranov´e 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´e oblasti . . . . . . . . . . . . . . . . . Blokov´e schema algoritmu segmentace z´ony z´ajmu v obraze . . . Z´ona z´ajmu 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´en, ve kter´ ych z´ona z´ajmu nebyla stanovena . . . . V´ ysledky segmentace z´ony z´ajmu v obraze – neznaˇcen´e silnice V´ ysledky segmentace z´ony z´ajmu v obraze – znaˇcen´e silnice . V´ ysledky segmentace z´ony z´ajmu v obraze – mˇesto . . . . . . V´ ysledky segmentace z´ony z´ajmu v obraze – mˇesto . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
48 49 50 51 52
6.1 6.2
Aplikace segmentace z´ony z´ajmu – Zone . . . . . . . . . . . . . . . . . . Ovl´adac´ı panel programu Zone . . . . . . . . . . . . . . . . . . . . . . .
54 55
9
. . . . .
. . . . .
Seznam tabulek 3.1
Pouˇzit´e senzory a jejich funkce . . . . . . . . . . . . . . . . . . . . . . .
20
4.1 4.2 4.3 4.4
Popisn´e statistiky . . . . . . . . . . . . . . . . . . . . . . Tabulka z´akladn´ıch barev v syst´emu RGB . . . . . . . . Vztah mezi hodnotou H a jm´enem 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´a etapa studia na Fakultˇe dopravn´ı CVUT je projektovˇe orientovan´a. To znamen´a, ˇze skupina student˚ u v r´amci v´ yuky pracuje pod odborn´ ym veden´ım na konkr´etn´ım probl´emu a t´ım z´ısk´ av´ a teoretick´e, ale i praktick´e poznatky, kter´e vyuˇzije v z´avˇeru studia pˇri vypracov´ an´ı diplomov´e pr´ace. V roce 1995 jsem se zapojil projektu Zpracov´ an´ı obrazov´e informace v dopravˇe, spoleˇcn´eho projektu Katedry aplikovan´e maˇ ˇ tematiky FD CVUT a Katedry teorie obvod˚ u FEL CVUT. Projekt je podporov´an ˇ Grantovou agenturou CVUT a firmou Texas Instruments Deutschland GmbH/Freising. V pr˚ ubˇehu n´asleduj´ıc´ıch dvou let jsem se sezn´amil s mnoha algoritmy zpracov´an´ı obrazu a poˇc´ıtaˇcov´eho vidˇen´ı. Na diplomov´e pr´aci jsem pracoval od bˇrezna roku 1997. Rozvoj v´ ypoˇcetn´ı techniky v posledn´ım desetilet´ı dvac´at´eho stolet´ı umoˇznil realizaci probl´em˚ u a rozvoj technologi´ı, kter´e byly jeˇstˇe pˇred nˇekolika lety pro svou komplikovanost neuskuteˇcniteln´e. Tento rozvoj se samozˇrejmˇe t´ yk´a i dopravy a je zvl´aˇstˇe patrn´ y v silniˇcn´ı dopravˇe. V Evropˇe existuje nˇekolik projekt˚ u podporovan´ ych Evropskou uni´ı, kter´e maj´ı zaveden´ım nov´ ych technologi´ı zv´ yˇsit bezpeˇcnost automobilov´e dopravy a z´aroveˇ n zv´ yˇsit propustnost infrastruktury, sn´ıˇzit zat´ıˇzen´ı ˇzivotn´ıho prostˇred´ı a celkovˇe zv´ yˇsit ekonomiku dopravy. Obdobn´e projekty prob´ıhaj´ı i v Japonsku a USA. Projekt Zpracov´ an´ı obrazov´e informace zaˇcal na Fakultˇe elektrotechnick´e jeˇstˇe pˇred rokem 1995. V t´e dobˇe Tom´ aˇs Zikmund pouˇzil algoritmus zaloˇzen´ y na lok´aln´ıch orientac´ıch pro detekci geometrick´ ych tvar˚ u, zvl´aˇstˇe s ohledem na dopravn´ı znaˇcky, v ploˇse obrazu. [12]. Tento algoritmus tvoˇr´ı z´aklad syst´emu RS2 – Road Sign Recognition System. Syst´em RS2 je moˇzn´e rozloˇzit na tˇri samostan´e subsyst´emy se spoleˇcn´ ym rozhran´ım. Jedn´a se o • Identifikace z´ ony z´ ajmu v obraze – tento subsyst´em ve vstupn´ım obraze vyznaˇc´ı regiony, ve kter´ ych je moˇzn´e s velkou pravdˇepodobnost´ı oˇcek´avat dopravn´ı znaˇcky, • Rozpozn´ an´ı tvaru dopravn´ıch znaˇcek – tento modul ve vstupn´ım obraze nach´az´ı geometrick´e tvary shodn´e 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´em pˇr´ıpadˇe provede jej´ı u ´plnou klasifikaci. C´ılem t´eto diplomov´e pr´ace je popsat v´ yvoj algoritm˚ u Identifikace z´ ony z´ ajmu v obraze tak, jak jsou implementovan´e v syst´emu RS2 . Z´onou z´ajmu rozum´ım ty oblasti, 11
Obr´ azek 1.1: Syst´em automatick´e 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´e ˇ 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´alov´ ych konstrukc´ıch nad j´ızdn´ımy p´asy, kter´e mus´ı respektovat pr˚ ujezdn´e ˇ v´ yˇsky a bezpeˇcnostn´ı vzd´alenosti podle CSN 73 6201. Pˇritom nesm´ı ˇz´ adn´a jejich ˇc´ ast zasahovat do voln´e (popˇr. do d´ılˇc´ı voln´e) ˇs´ıˇrky nebo voln´ ych v´ yˇsek silniˇcn´ı komunikace. Pˇri definov´an´ı probl´emu rozpozn´av´an´ı dopravn´ıch znaˇcek byla problematika omezena na bod 1, na pravou ˇc´ast silniˇcn´ı komunikace. Algoritmy identifikace z´ony z´ajmu byly navrˇzen´e s ohledem na snadn´e rozˇs´ıˇren´ı, tak aby ˇ pokryly celou problematiku osazov´an´ı dopravn´ıch znaˇcek dle normy CSN 73 6101. Z´ ona z´ajmu je definov´ ana na z´akladˇe segmentace povrchu vozovky a geometrick´eho modelu silnice v dopravn´ı sc´enˇe. Ostatn´ı projekty, kter´e ˇreˇs´ı probl´emy autonomn´ıch vozidel (kapitola 3.1) pˇristupuj´ı k rozpozn´an´ı silnice odliˇsnˇe. Informace o poloze silnice v obraze je z´ısk´ ana na z´akladˇe hranov´e detekce vod´ıc´ıho prouˇzku. T´ım se problematika zuˇzuje pouze na dobˇre znaˇcen´e 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´ych silniˇcn´ıch komunikac´ı, s t´ım, ˇze na povrch (texturu) vozovky nejsou kladeny ˇz´ adn´e speci´aln´ı poˇzadavky1 . Vyvinut´e algoritmy jsou natolik obecn´e, ˇze je je moˇzn´e po drobn´ ych u ´prav´ ach pouˇz´ıt i pro ˇreˇsen´ı dalˇs´ıch probl´em˚ u autonomn´ıch vozidel (navigace, steering, . . . ). Vˇsechny testovan´e algoritmy popsan´e v kapitole 4.2, byly vyv´ıjen´e tak, aby jejich v´ ypoˇcetn´ı n´aroky byly obdobn´e, nebo niˇzˇs´ı, neˇz v algoritmech pouˇzit´ ych v konkurenˇcn´ıch projektech [14], [13]. Algoritmy, kter´e tvoˇr´ı syst´em RS2 , byly navrhov´any s pˇrihl´ednut´ım k implementaci v re´aln´em ˇcase prostˇrednictv´ım sign´alov´eho procesoru firmy Texas Instruments TMS320C80. Pˇri v´ yvoji byl pro d´ılˇc´ı simulace pouˇzit syst´em Matlab, vlastn´ı implementace je provedena v jazyce C/C++ a to zejm´ena pro relativnˇe snadnou pˇrenositelnost algoritm˚ u do prostˇred´ı sign´alov´eho procesoru. V souˇcasn´e dobˇe je dokonˇcen v´ yvoj algoritm˚ u v programovac´ım jazyku C++ a prob´ıh´a paralelizace aplikace a implementace v prostˇred´ı sign´alov´eho procesoru.
1
vlastn´ı definice probl´emu a omezen´ı problematiky je uvedeno v kapitole 4.3
13
Kapitola 2
Poˇ c´ıtaˇ cov´ e vidˇ en´ı C´ılem t´eto kapitoly nen´ı glob´ aln´ı v´yklad z´ akladn´ıch pojm˚ u a algoritm˚ u poˇc´ıtaˇcov´eho vidˇen´ı, ale definov´ an´ı pojm˚ u a element´ arn´ıch algoritm˚ u, kter´e budou pouˇz´ıvan´e v n´ asleduj´ıc´ıch kapitol´ ach. Detailn´ı v´yklad poˇc´ıtaˇcov´eho vidˇen´ı a zde popisovan´ych t´emat je moˇzn´e z´ıskat napˇr. v [3], [4], [7].
2.1
Z´ akladn´ı pojmy
Poˇc´ıtaˇcov´e vidˇen´ı je discipl´ına, kter´a se snaˇz´ı technick´ ymi prostˇredky alespoˇ n ˇc´asteˇcnˇe napodobit lidsk´e vidˇen´ı. Zrak je pro ˇclovˇeka zdrojem pˇrev´aˇzn´e vˇetˇsiny informac´ı o okoln´ım svˇetˇe. S t´ım souvis´ı i to, ˇze vizu´aln´ı informaˇcn´ı komplex je nejsloˇzitˇejˇs´ı ze vˇsech smyslov´ ych komplex˚ u lidsk´eho mozku ([25] str. 169 - 189) . Teoreticky, ale i technicky jsou zvl´adnuty jen velmi jednoduch´e probl´emy. Postupy poˇc´ıtaˇcov´eho vidˇen´ı jsou znaˇcnˇe sloˇzit´e. Kaˇzd´ y algoritmus zpracov´an´ı a interpretace obrazu je obvykle moˇzn´e 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´a obrazov´a data ˇc´ıseln´eho charakteru a naj´ıt kvalitativn´ı informace potˇrebn´e 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´av´an´ı jednoduch´ ych obrazc˚ u v obraze apod. Pro niˇzˇs´ı u ´roveˇ n se ˇcasto pouˇz´ıv´a n´azev zpracov´an´ı obrazu (image processing). Postupy vyˇsˇs´ı u ´rovnˇe jsou typick´e pouˇzit´ım n´aroˇcn´ ych algoritm˚ u expertn´ıch syst´em˚ u a technik umˇel´e inteligence. Vyˇsˇs´ı u ´roveˇ n je oznaˇcov´ana jako poˇc´ıtaˇcov´e vidˇen´ı (computer vision). Postup zpracov´an´ı a rozpozn´an´ı obrazu je moˇzn´e dekomponovat do nˇekolika z´akladn´ıch krok˚ u. Jednotliv´e u ´rovnˇe zpracov´an´ı obrazu spolu sovisej´ı a je moˇzn´e ˇr´ıci, ˇze bez kvalitn´ıch algoritm˚ u niˇzˇs´ı u ´rovnˇe by nebylo moˇzn´e prov´est postupy vyˇsˇs´ı u ´rovnˇe, zvl´aˇstˇe pak porozumˇen´ı obsahu obrazu. Z´akladn´ımy kroky zpracov´an´ı 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´an´ı obrazu je sn´ım´an´ı, digitalizace a uloˇzen´ı obrazu v ˇc´ıseln´e podobˇe do poˇc´ıtaˇce. Pˇri sn´ım´an´ı se pˇrev´adˇej´ı vstupn´ı optick´e veliˇciny na elektrick´ y sign´al spojit´ y v ˇcase. Vstupn´ı optickou veliˇcinou m˚ uˇze b´ yt jas, intenzita tepeln´eho nebo jin´eho z´aˇren´ı. Sn´ımat je moˇzn´e v jednom nebo v´ıce spektr´aln´ıch p´asmech. Digitalizac´ı se pˇrev´ ad´ı vstupn´ı spojit´ y sign´al do diskr´etn´ı podoby. Vstupn´ı sign´al je pops´an funkc´ı f (i, j), jej´ıˇz funkˇcn´ı hodnota pˇredstavuje velikost jasu (nebo jin´e veliˇciny). Tento sign´al je vzorkov´ an a kvantov´ an a v´ ysledkem je matice pˇrirozen´ ych ˇc´ısel, kter´a popisuje obraz. Jednomu prvku t´eto matice se ˇr´ık´a obrazov´ y element (picture element – pixel ). Druh´ ym krokem je pˇredzpracov´an´ı obrazu. C´ılem pˇredzpracov´an´ı je potlaˇcit ˇsum a jin´e poruchy vznikl´e pˇri pˇrenosu a digitalizaci. Pˇredzpracov´an´ım je tak´e moˇzn´e zv´ yraznit pro n´as zaj´ımav´e (pro dalˇs´ı algoritmus d˚ uleˇzit´e) rysy obrazu. Tˇret´ım a asi nejtˇeˇzˇs´ım krokem postupu zpracov´an´ı obrazu je segmentace, kter´a umoˇzn ˇuje v obraze vyhledat objekty, kter´e jsou pro n´as z pohledu dalˇs´ıho zpracov´an´ı zaj´ımav´e. Pˇri segmentaci se pouˇz´ıv´a znalosti interpretovan´eho obrazu (semantika). Segmentaci a segmentaˇcn´ım algoritm˚ um bude vˇenov´ana 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´a pouze o klasifikaci segmentovan´ ych objekt˚ u do nˇekolika tˇr´ıd. Porozumˇen´ı obrazu nebo proces rozhodov´ an´ı na z´akladˇe informac´ı obsaˇzen´ ych v obraze je v souˇcasn´e dobˇe moˇzn´ y pouze u nˇekolika trivi´aln´ıch probl´em˚ u (ve srovn´an´ı se schopnostmi ˇclovˇeka).
2.2
Digit´ aln´ı obraz
Kaˇzd´ y obraz m˚ uˇze b´ yt pops´an dvourozmˇernou funkc´ı f (x, y) jej´ıˇz funkˇcn´ı hodnota popisuje hodnotu jasu nebo jin´e optick´e veliˇciny na souˇradnic´ıch x a y. Funkci f (x, y) se obvykle ˇr´ık´ a obrazov´ a funkce. V t´eto pr´aci bude digit´aln´ı obraz reprezentov´an 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´em˚ u pro digit´aln´ı zpracov´an´ı obrazu pouˇz´ıv´a kvantov´an´ı do L stejn´ ych interval˚ u. Pro reprezentaci informace o obrazov´em elementu vˇetˇsinou postaˇcuje pouˇzit´ı 8 bit˚ u (pro monochromatick´ y obraz). Pak L = 28 = 256. Pouze pˇri zpracov´an´ı barevn´eho 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´aln´ıch p´asmech (nejˇcastˇeji RGB) pak kaˇzd´e spektr´aln´ı p´asmo budeme popisovat obrazovou funkc´ı fi (x, y), kde i ∈ {R, G, B}. D˚ uleˇzitou informaci o digit´aln´ım obrazu ud´av´a 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´akladˇe teorie metrick´ ych prostor˚ u. Intuitivn´ı a v matematice obvykl´a Euklidova vzd´alenost DE =
q
(i − k)2 + (j − l)2
(2.2)
je oproti ostatn´ım metrik´am v´ ypoˇcetnˇe n´aroˇcnˇejˇs´ı, ale jej´ı pouˇzit´ı pˇrin´aˇ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´aln´ı informac´ı o obrazu lze z´ıskat pomoc´ı hran. Hrana je vlastnost´ı obrazov´eho elementu a jeho lok´aln´ıho okol´ı. Je urˇcena velikost´ı a smˇerem. Velikost odpov´ıd´ a modulu gradientu spojit´e obrazov´e funkce v pˇr´ısluˇsn´em pixelu a gradient ukazuje smˇer nejvˇetˇs´ıho r˚ ustu obrazov´e funkce (t.j. od ˇcern´e k b´ıl´e). 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´atory [3]. Z´ akladn´ı pˇredstavu o rozdˇelen´ı jednotliv´ ych jasov´ ych u ´rovn´ı z´ısk´ame pomoc´ı histogramu. Histogram jasu je vektor (v pˇr´ıpadˇe barevn´eho obrazu matice) jehoˇz poˇcet prvk˚ u je roven poˇctu jasov´ ych u ´rovn´ı. Hodnota kaˇzd´eho prvku odpov´ıd´a ˇcetnosti bod˚ u pˇr´ısluˇsn´eho jasu v obraze. Histogram b´ yv´a zobrazov´an jako sloupcov´ y graf. Jedn´a se o nejsnaˇzˇs´ı metodu, pomoc´ı kter´e z´ısk´ame pˇrehled o rozloˇzen´ı jasu (pˇr´ıpadnˇe barev) v obraze. Z´ıskan´e informace je moˇzn´e vyuˇz´ıt v pˇredzpracov´an´ı obrazu, pˇr´ıpadnˇe pˇri segmentaci.
2.3
Operace pˇ redzpracov´ an´ı obrazu
Pˇredzpracov´ an´ı obrazu je spoleˇcn´ y n´azev pro operace niˇzˇs´ı u ´rovnˇe. C´ılem b´ yv´a zvl´aˇstˇe potlaˇcen´ı ˇsumu a zv´ yraznˇen´ı informace, kter´a je d˚ uleˇzit´a pro s´emantick´ y popis obrazu. Jednou z operac´ı lok´aln´ıho pˇredzpracov´an´ı je filtrace obrazu. Podle u ´ˇcelu je moˇzn´e filtraci rozdˇelit na dvˇe skupiny – vyhlazov´ an´ı obrazu (potlaˇcen´ı ˇsumu) a gradientn´ı operace (zv´ yrazˇ nov´an´ı hran). Lok´aln´ı pˇredzpracov´an´ı pˇriˇrazuje v´ ysledn´ y jas bodu na z´akladˇe v´ ypoˇct˚ u jasu v lok´aln´ım okol´ı. Tento v´ ypoˇcet (transformace) m˚ uˇze b´ yt line´arn´ı nebo neline´arn´ı. Line´arn´ı kombinace poˇc´ıtaj´ı v´ yslednou hodnotu jasu v bodˇe (i, j) jako line´arn´ı kombinaci jas˚ u v okol´ı O vstupn´ıho obrazu g() s v´ahov´ 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´etn´ı konvoluce s konvoluˇcn´ım j´adrem h. Toto konvoluˇcn´ı j´adro b´ yv´ a nˇekdy oznaˇcov´ano jako konvoluˇcn´ı maska, v teorii filtr˚ u jako impulsn´ı odezva filtru. V´ ypoˇcetnˇe nejsnaˇzˇs´ı operac´ı pro vyhlazov´an´ı obrazu je prost´e lok´aln´ı pr˚ umˇerov´an´ı. Filtrace pr˚ umˇerov´ an´ım je pˇr´ıklad diskr´etn´ı konvoluce. Napˇr´ıklad pro lok´aln´ı 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´ahl´ ymi zmˇenami jasov´e funkce. Oper´atory pro detekci a ohodnocen´ı hran v digit´aln´ım obraze [4] vych´azej´ı z parci´aln´ıho diferenci´ aln´ıho oper´atoru. Velikost gradientu je d´ana 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´aln´ım obrazu jsou gradientn´ı oper´atory aproximov´any diskr´etn´ı konvoluc´ı. Mezi nejˇcastˇeji pouˇz´ıvan´e oper´atory patˇr´ı Roberts˚ uv oper´ator, Laplace˚ uv oper´ator a Sobel˚ uv oper´ ator. Konvoluˇcn´ı maska Sobelova oper´atoru pro dva z osmi smˇer˚ u je d´ana 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´atory pouˇz´ıvaj´ı zvl´aˇstˇe na vyhled´ av´ an´ı hran a ostˇren´ı obrazu. Vhodn´ y v´ ybˇer konvoluˇcn´ıho j´adra b´ yv´a zaloˇzen na experimentech, popˇr. znalosti kmitoˇctov´ ych vlastnost´ı obrazov´eho sign´alu. Srovn´an´ı v´ ypoˇcetn´ı n´aroˇcnosti zde uveden´ ych gradientn´ıch oper´ator˚ u a dalˇs´ıch nejv´ıce pouˇz´ıvan´ ych je moˇzn´e nal´ezt v [5].
2.4
Popis objekt˚ u v obraze
Popis objekt˚ u1 v obraze je d˚ uleˇzit´ y pro n´asleduj´ıc´ı algoritmy, zvl´aˇstˇe pak pro rozpozn´av´ an´ı. Existuje ˇrada metod, kter´e je moˇzn´e 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´e 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´aln´ı abecedy s vlastn´ı sematikou. Popis tvaru oblasti b´ yv´a velice d˚ uleˇzit´ y pro klasifikaci objekt˚ u. K popisu tvaru se pouˇz´ıvaj´ı z´akladn´ı atributy objektu jako velikost, jasov´e vlastnosti, excentricita, podlouhlost, pravo´ uhlost, nekompaktnost a v pˇr´ıpadˇe statistick´eho popisu momenty. Textura [6] pˇredstavuje v obraze (nebo jeho ˇc´asti) relativn´ı pravidelnost sv´azanou z element˚ u. Tyto elementy jsou naz´ yv´any texely – texturn´ı elementy. Pro popis textury se pouˇz´ıvaj´ı statistick´e metody a frekvenˇcn´ı anal´ yza obrazov´e funkce.
1
Segmentaˇcn´ım algoritm˚ um, kter´e 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´eho vidˇen´ı je typick´a jejich znaˇcn´a v´ ypoˇcetn´ı n´aroˇcnost. I velmi jednoduch´e 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´al 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´eho datov´eho toku algoritmy poˇc´ıtaˇcov´eho vidˇen´ı ˇcasto obsahuj´ı operace jako je konvoluce a v´ ypoˇcty s rozs´ahl´ ymi maticemi. Tyto operace jsou na konvenˇcn´ıch poˇc´ıtaˇc´ıch relativnˇe pomal´e a bez speci´aln´ıch procesor˚ u je velmi tˇeˇzk´e programovat aplikace zpracov´an´ı obrazu tak, aby pracovaly v re´aln´em ˇcase. I to je pˇr´ıˇcinou toho, ˇze se v aplikac´ıch poˇc´ıtaˇcov´eho vidˇen´ı zpracov´avaj´ı ˇcasto jen statick´e obrazy. Sn´ıˇzen´ı datov´eho toku a t´ım i v´ ypoˇcetn´ıch n´arok˚ u m˚ uˇze b´ yt doc´ıleno nˇekolika zp˚ usoby. Vhodnou metodou b´ yv´a podvzorkov´an´ı obrazu a t´ım sn´ıˇzen´ı rozliˇsen´ı. Sn´ıˇzen´ım rozliˇsen´ı ovˇsem ztr´ac´ıme detaily, a t´ım zhorˇsujeme rozpozn´avac´ı schopnost dalˇs´ıch algoritm˚ u, zvl´aˇstˇe pak klasifikaci segmentovan´ ych objekt˚ u. Dalˇs´ım ˇreˇsen´ım tohoto probl´emu m˚ uˇze b´ yt pouˇzit´ı pyramid´ aln´ı struktury pro reprezentaci obrazu. To znamen´a, ˇze obraz je uchov´av´an v nˇekolika rozliˇsen´ıch, od nejvyˇsˇs´ıho z´ıskan´eho kamerou aˇz po nejniˇzˇs´ı, z´ıskan´e nˇekolikan´asobn´ ym podvzorkov´an´ım p˚ uvodn´ıho obrazu. Algoritmy poˇc´ıtaˇcov´eho vidˇen´ı prob´ıhaj´ı na nejniˇzˇs´ım moˇzn´em rozliˇsen´ı a pouze v pˇr´ıpadˇe nutnosti pˇrech´azej´ı na rozliˇsen´ı vyˇsˇs´ı. Pˇr´ıkladem m˚ uˇze b´ yt segmentace na objekty v n´ızk´em aˇz stˇredn´ım rozliˇsen´ı a pot´e klasifikace do tˇr´ıd v nejvyˇsˇs´ım rozliˇsen´ı. Pouˇzit´ı pyramid´ aln´ı struktury rovnˇeˇz umoˇzn ˇuje rozpozn´an´ı objekt˚ u v libovoln´e velikosti (je tedy invariantn´ı v˚ uˇci velikosti) [15]. Z tohoto d˚ uvodu je pyramid´aln´ı struktura pouˇzita pˇri rozpozn´av´an´ı geometrick´ ych tvar˚ u v obraze v syst´emu RS2 . ˇ Casto pouˇz´ıvanou moˇznost´ı je proveden´ı anal´ yzy obrazu a t´ım z´ısk´an´ı dalˇs´ıch informac´ı o sc´enˇe, kter´e mohou b´ yt pouˇzity jako apriorn´ı informace v dalˇs´ıch algoritmech syst´emu. Tyto informace mohou b´ yt z´ısk´any predikc´ı podobnˇe jako v syst´emu VaMoRs (kapitola 3.1.2), nebo segmentac´ı, tak jako v t´eto diplomov´e pr´aci. Z´ onou z´ ajmu rozum´ım oblasti v obraze, z´ıskan´e pomoc´ı rychl´ ych algoritm˚ u, ve kter´ ych je moˇzn´e s velkou pravdˇepodobnost´ı oˇcek´avat objekty, kter´e se snaˇz´ıme rozpoznat a klasifikovat – objekty z´ ajmu. Syst´em RS2 se skl´ad´ a ze tˇr´ı ˇc´ast´ı. C´ılem je implementace algoritm˚ u v prostˇred´ı sign´alov´eho procesoru a bˇeh syst´em˚ u v re´aln´em ˇcase. Subsyst´em Rozpozn´ an´ı geometrick´ych tvar˚ u v obraze je velmi n´aroˇ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´em rozˇs´ıˇrit o segmentaci z´ony z´ajmu a t´ım sn´ıˇzit v´ ypoˇcetn´ı n´aroky syst´emu. 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´asahu ˇridiˇce projet stanovenou trasu. Protoˇze se jedn´a o velmi komplikovan´ y probl´em, jsou v souˇcasn´e dobˇe ˇreˇsen´e d´ılˇc´ı probl´emy. V n´asleduj´ıc´ıch kapitol´ach budou pˇribl´ıˇzeny nˇekter´e prob´ıhaj´ıc´ı projekty a t´ım i problematika autonomn´ıho vozidla. Jiˇz nyn´ı je vyvynuto nˇekolik subsyst´em˚ u autonomn´ıho vozidla, kter´e se ˇcasto ozna1 ˇcuj´ı jako DSS . DSS si m˚ uˇzeme pˇredstavit jako lidsk´eho 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´amci evropsk´eho EUREKA projektu PROMETHEUS (PROgraMme for a European Traffic with Highest Efficiency and Unprecedented Safety, 1986 – 1994). Obdobn´e projekty byly realizov´any i v Japonsku a USA (napˇr´ıklad IVHS – Intelligent Vehicles Highway System). Vˇsechny projekty autonomn´ıch vozidel pouˇz´ıvaj´ı ve velk´e m´ıˇre algoritmy zpracov´an´ı obrazu a poˇc´ıtaˇcov´eho vidˇen´ı. Mezi z´akladn´ı operace poˇc´ıtaˇcov´eho vidˇen´ı v syst´emech DSS je detekce, sledov´an´ı silnice a objekt˚ u na n´ı. Je bezpodm´ıneˇcnˇe nutn´e, aby vˇsechny syst´emy pracovaly v re´aln´em ˇcase. Toho je moˇzn´e dos´ahnout 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´emy zaloˇzen´e na algoritmech zpracov´an´ı obrazu souˇc´ ast´ı automobil˚ u. DSS je moˇzn´e d´ale rozdˇelit na nˇekolik subsyst´em˚ u, kter´e pln´ı specifick´e, pro provoz autonomn´ıho vozidla nutn´e 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´e 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´ad´an. Optim´aln´ı 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´eto problematice bylo provedeno pouze nˇekolik experiment˚ u. Kˇriˇzovatka je nejˇcastˇeji zjednoduˇsenˇe definov´ana jako pˇreruˇsen´ y vod´ıc´ı prouˇzek pˇr´ıpadnˇe jako stop ˇc´ara napˇr´ıˇc j´ızdn´ım pruhem. 3. Rozpozn´ an´ı vodorovn´ych dopravn´ıch znaˇcek. Kromˇe vod´ıc´ıch prouˇzk˚ u obsahuj´ı j´ızdn´ı pruhy dalˇs´ı znaˇcen´ı. Jedn´a se o smˇerov´e ˇsipky, parkovac´ı znaˇcky, znaˇcen´ı pro cyklisty a autobusy atp. Z´asadn´ım probl´emem je, ˇze vodorovn´e dopravn´ı znaˇcen´ı b´ yv´ a ˇc´ asteˇcnˇe zakryto ostatn´ımi automobily. O t´eto problematice zat´ım bylo publikov´ ano velmi m´alo ˇcl´ank˚ u. 4. Dopravn´ı znaˇcky. Dopravn´ı znaˇcky a dopravn´ı osvˇetlen´ı je um´ısov´ano v pˇredem zn´ am´ ych oblastech v obraze. Z tohoto d˚ uvodu je moˇzn´e v obraze vymezit subregiony, ve kter´ ych mohou b´ yt dopravn´ı znaˇcky na z´akladˇe tvaru a barvy rychle rozpozn´any a klasifikov´ any. 5. Rozpozn´ an´ı pˇrek´ aˇzek. Pˇrek´aˇzky jsou detekov´any jako v´ yznamn´a porucha v textuˇre vozovky v m´ıstˇe, kde je silnice predikov´ana, nebo pomoc´ı v´ ypoˇctu optick´eho toku. Prvn´ı zp˚ usob je v´ ypoˇcetnˇe m´enˇe n´aroˇ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´avn´ ych rozpozn´an´ı vysok´ y. V´ yhodn´e je pˇrek´ aˇzky rozpoznat na z´akladˇe v´ ypoˇctu optick´eho toku, zvl´aˇstˇe pak pˇri pouˇzit´ı dvou kamer.
3.1.1
Projekt CAPC
Jedn´a se o projekt podporovan´ y U.S. Army Tank Automative a firmou Ford Motor Company [13].V USA doch´ az´ı k dopravn´ım nehod´am z jedn´e tˇretiny na d´alnic´ıch. T´emˇeˇr tˇretina z tˇechto nehod je zp˚ usobena u ´navou, intoxikac´ı nebo nemoc´ı ˇridiˇce a projevuje se vyjet´ım automobilu z vozovky – pˇrejezdem b´ıl´eho (ˇzlut´eho) vod´ıc´ıho prouˇzku krajnice. Syst´em CAPC2 je podp˚ urn´y palubn´ı varovn´ y syst´em, kter´ y upozorn´ı ˇridiˇce pˇred nebezpeˇc´ım vyjet´ı ze silnice a v pˇr´ıpadˇe nutnosti aktivn´ım z´asahem do ˇr´ızen´ı uprav´ı dr´ahu vozidla. To znamen´a, ˇze tento syst´em je modern´ım prvkem aktivn´ı bezpeˇcnosti. Syst´em je vybaven elektronikou podporovanou algoritmy poˇc´ıtaˇcov´eho vidˇen´ı, kter´e umoˇzn ˇuj´ı zpracovan´ı obrazu do vzd´alenosti 100 m pˇred automobilem. V´ ypoˇcty jsou aktualizov´ any desetkr´at za sekundu, prob´ıh´a v´ ypoˇcet predikce pr˚ ubˇehu silnice. Po porovn´ an´ı s geometrick´ ym a kinematick´ ym modelem je z´ısk´an ˇcas potˇrebn´ y k vyjet´ı z vozovky pˇri nezmˇenˇen´e rychlosti a smˇeru j´ızdy. V pˇr´ıpadˇe, ˇze je tento ˇcas menˇs´ı neˇz stanoven´ y pr´ah, je aktivov´ an varovn´ y zvukov´ y sign´al. V letoˇsn´ım roce prob´ıh´a implementace automatick´e podpory ˇr´ızen´ı realizovan´a brzdˇen´ım kol na lev´e a prav´e stranˇe automobilu. I v pˇr´ıpadˇe intervence syst´emu do ˇr´ızen´ı m´a ˇridiˇc plnou kontrolu nad vozidlem. Nejedn´a se tedy o syst´em autonomn´ıho vozidla, ale o prvek aktivn´ı bezpeˇcnosti, kter´ y upozorˇ nuje na nebezpeˇcn´e situace a pom´ah´a 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´aˇcen´ı ω
Rychlost ot´aˇcen´ı rychlost vozidla kol (z instalovan´eho ABS) LVDT na pˇredn´ı u ´hel natoˇcen´ı kol n´ apravˇe
V´ ypoˇcet v´ ypoˇcet ˇcasu potˇrebn´eho 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´eho pro vyjet´ı z vozovky, aktualizace polohy vozidla v´ ypoˇcet ˇcasu potˇrebn´eho pro vyjet´ı z vozovky, aktualizace polohy vozidla a predikce polohy vod´ıc´ıho prouˇzku v´ ypoˇcet ˇcasu potˇrebn´eho pro vyjet´ı z vozovky, aktualizace polohy vozidla a predikce polohy vod´ıc´ıho prouˇzku
Tabulka 3.1: Pouˇzit´e senzory a jejich funkce 2
Crewman’s Associate for Path Control
20
Syst´em CAPC ja tvoˇren jak hardwarov´ ymi tak softwarov´ ymi prostˇredky. Aby nebylo nutn´e v poˇc´ ateˇcn´ı f´azi v´ yvoje investovat pˇr´ıliˇs mnoho financ´ı do speci´aln´ıch zaˇr´ızen´ı byla pˇrijata tato omezen´ı: • vozidlo jede po d´alnici s b´ıl´ ym vod´ıc´ım prouˇzkem za n´ızk´eho provozu, mimo n´ ajezdy nebo v´ yjezdy z d´alnice, 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´em stavu, nen´ı pokryt vodou, snˇehem nebo jin´ ymi neˇcistotami, • okraje silnice neobsahuj´ı ruˇsiv´e objekty alespoˇ n do vzd´alenosti ˇ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´emu CAPC: 1. rozpozn´an´ı 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´e 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´emu modelu vozovky. LMS syst´em se skl´ad´ a z digit´aln´ı CCD kamery Pulnix 9701 (748 × 484), frame-grabberu MuTech MV-1000 PCI a poˇc´ıtaˇce na b´azi procesoru Intel Pentium 100 MHz. Tento poˇc´ıtaˇc zpracov´ av´ a vˇsechny operace poˇc´ıtaˇcov´eho vidˇen´ı. Kamera je napevno um´ıstˇena uvnitˇr automobilu. Vod´ıc´ı prouˇzek je v obraze hled´an ve vzd´alenosti od 6 do 20 m pˇred automobilem. Takto z´ıskan´ a data jsou extrapolov´ana aˇz do vzd´alenosti 100 m. Z matice popisuj´ıc´ı obraz jsou vybr´any vektrory v~j , kter´e reprezentuj´ı horizont´aln´ı ˇrezy obrazem ve vzd´alenosti j = 6, 8, 10, . . . , 20 m pˇred automobilem. V tˇechto vektorech jsou hled´any kr´atk´e sekvence – m´ısta nejvˇetˇs´ıho gradientu jasu. V kaˇzd´e sekvenci je nalezeno m´ısto s nejvˇetˇs´ım jasem Imax (x) a n´asleduj´ıc´ı hodnota s minim´aln´ı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´em ˇrezu z´ısk´any aˇz ˇctyˇri moˇzn´e hodnoty polohy vod´ıc´ıch prouˇzk˚ u, ze kter´ ych jsou dva spr´avn´e vybr´ any na z´akladˇe v´ ysledk˚ u v pˇredchoz´ım ˇrezu a porovn´an´ım s geometrick´ ym modelem. Z v´ yˇse popsan´eho algoritmu je zˇrejm´e, ˇze je velmi jednoduch´ y a funkˇcn´ı pouze za podm´ınek, kter´e autoˇri stanovili. Nejedn´a se tedy o univerz´aln´ı metodu, kter´a by se mohla st´at souˇc´ ast´ı algoritm˚ u autonomn´ıho vozidla. Tˇeˇziˇstˇe pr´ace autor˚ u t´eto metody vˇsak bylo ve stanoven´ı dynamick´eho modelu j´ızdy. 3
Lane mark sensor
21
3.1.2
Projekt VaMoRs
Tento projekt prob´ıh´ a od roku 1986 na technick´e univerzitˇe v Mnichovˇe a je veden profesorem Dickmannem [14]. Projekt je podporov´an firmou Daimler–Benz AG a jeho c´ılem je v´ yvoj plnˇe autonomn´ıho vozidla. Syst´em VaMoRs byl poprv´e prezentov´an v roce 1991 v Torinu a jiˇz tehdy umoˇzn ˇoval: 1. rozpozn´an´ı 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´alenosti 90 m pˇred vozidlem, 4. v´ ypoˇcet vzd´alenosti za pomoci pouze jedn´e kamery, 5. pˇri rychlosti 50 km/h bezpeˇcn´e zastaven´ı pˇred pˇrek´aˇzkou. Syst´em se skl´ad´ a ze dvou CCD kamer, kter´e jsou namontov´any v oblasti zpˇetn´eho c zrc´atka. Kamery jsou vybaveny objektivy s r˚ uzn´ ymi ohniskov´ ymi vzd´alenostmi. iroko´ uhl´ y obraz z jedn´e kamery se pouˇz´ıv´a pro glob´aln´ı anal´ yzu sc´eny – detekci vod´ıc´ıho prouˇzku a aktualizaci geometrick´eho modelu. Detailnˇejˇs´ı obraz z druh´e kamery je pouˇzit zvl´aˇstˇe pro detekci objekt˚ u a pˇrek´aˇzek na silnici. Zpracov´an´ı obrazu v re´aln´em ˇ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´aln´ıch u ´rovn´ıch a skl´ad´a se ze ˇctyˇr d´ılˇc´ıch u ´kol˚ u – detekce vod´ıc´ıho prouˇzku, rozpozn´an´ı pˇrek´aˇzek na silnici, aktualizace modelu a navigace (ˇr´ızen´ı). Pouˇzit´e rozliˇsen´ı obrazu vyˇzaduje zpracov´an´ı 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´an pˇribliˇznˇe na 0.5 MB/s. Informace obsaˇzen´e v z´onˇe z´ajmu jsou d´ale zpracov´av´any ˇ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´ony z´ajmu je dosaˇzeno bˇehu syst´emu v re´aln´em ˇcase.
Algoritmy poˇ c´ıtaˇ cov´ eho vidˇ en´ı Paraleln´ı procesory (PP1 - PP10) jsou pouˇzity pro hranovou detekci. Takto z´ıskan´e informace o hran´ach a jejich orientac´ıch jsou nejv´ yznamˇejˇs´ımi pˇr´ıznaky pro detekci vod´ıc´ıho prouˇzku a pro rozpozn´an´ı pˇrek´aˇzek na silnici. Hranov´e detektory jsou softwarovˇe implementovan´e na standardn´ıch procesorech 80386. Vstupem do hranov´eho detektoru je nepˇredzpracovan´ y obraz. Dickmanns v [14] uv´ad´ı, ˇze syst´em produkuje ˇspatn´e v´ ysledky, v pˇr´ıpadˇe ˇspatn´eho osvˇetlen´ı, nepravideln´e textury nebo silnˇe zaˇsumˇel´eho obr´azku. Z´avˇerem poznamen´av´ a, ˇze tyto podm´ınky jsou v pˇr´ıpadˇe re´aln´ ych sc´en velmi ˇcast´e a proto je nutn´e algoritmus doplnit o co nejv´ıce apriorn´ıch informac´ı a kvalitn´ı geometrick´ y model sc´eny. V´ ysledkem hranov´e detekce je obvykle mnoˇzina moˇzn´ ych hran a jejich orientac´ı. Interpretace v´ ysledk˚ u hranov´e detekce prob´ıh´a v procesorech GPP1 a GPP2. Na z´akladˇe predikce pozice hran a jejich orientac´ı jsou z mnoˇziny moˇzn´ ych hran vybr´any ty, kter´e skuteˇcnˇe reprezentuj´ı okraj silnice. Takto z´ıskan´e hrany jsou d´ale pouˇzity pro predikci 22
Obr´ azek 3.1: Paraleln´ı architektura syst´emu VaMoRs
hran v n´asleduj´ıc´ım oknˇe. Pro extrakci orientac´ı je pouˇzito 16 kan´al˚ u, tedy rozliˇsen´ı je pˇribliˇznˇe 11 stupˇ n˚ u. V kaˇzd´em oknˇe mohou b´ yt rozliˇseny aˇz ˇctyˇri moˇzn´e hrany, tedy je tˇreba analyzovat a interpretovat aˇz 32 moˇzn´ ych hran. Popis geometrick´eho 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´an´ı obrazu. Segmentov´ an´ım rozum´ıme postup, kter´ y obraz rozˇclen´ı na segmenty – ˇc´asti obrazu, kter´e maj´ı urˇcit´ y vztah k objekt˚ um obsaˇzen´ ym v obraze. V´ ysledkem segmentace je mnoˇzina vz´ajemnˇ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´en je velice sloˇzit´a a kompletn´ı segmentace nen´ı v t´eto f´azi zpracov´an´ı 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´e oblasti z´ıskan´e segmentac´ı nemus´ı pˇresnˇe souhlasit s objekty v obraze. V´ ysledky z´ıskan´e ˇc´ asteˇcnou segmentac´ı je moˇzn´e d´ale zpˇresˇ novat za pomoci algoritm˚ u vyˇsˇs´ı u ´rovnˇe, zvl´aˇstˇe pak semantick´e znalosti segmentovan´eho obrazu. Jedn´ım z hlavn´ıch probl´em˚ u segmentace je nejednoznaˇcnost obrazov´ ych dat, kter´a ˇcasto obsahuj´ı ˇsum. Obraz je segmentov´ an do oblast´ı na z´akladˇe krit´eria stejnorodosti. Vlastnosti, kter´e tvoˇr´ı krit´erium stejnorodosti mohou b´ yt r˚ uzn´e. V nejjednoduˇsˇs´ıch algoritmech se jedn´a o hodnoty jasu nebo barvy testovan´eho elementu, ve sloˇzitˇejˇs´ıch algoritmech o statistickou anal´ yzu okol´ı testovan´eho bodu. Pˇr´ıkladem m˚ uˇze b´ yt segmentace na z´akladˇe textury. Nejabstraktnˇejˇs´ı vlastnost´ı m˚ uˇze b´ yt s´emantick´a pˇr´ısluˇsnost elementu k segmentovan´emu objektu. V literatuˇre je moˇzn´e nal´ezt mnoho definic segmentace [3], [4], [8], [9]. To je zp˚ usobeno t´ım, ˇze autoˇri definuj´ı segmentaci na z´akladˇe aplikace, ve kter´e byla pouˇzita (segmentace objekt – pozad´ı, segmentace na objekty, . . . ). Jako obecnou definici segmentace m˚ uˇzeme uv´est 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´e 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´e 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´e oblasti, kter´e jsou pouˇzity pˇri segmentaci (napˇr. homogenn´ı jas). Druh´a podm´ınka ˇr´ık´ a, ˇze segmentovan´e oblasti mus´ı b´ yt spojit´e, napˇr. sloˇzen´e ze sousedn´ıch obrazov´ ych bod˚ u. Tento pˇredpoklad je velice d˚ uleˇzit´ y, zvl´aˇstˇe pro segmentaci nar˚ ust´an´ım oblasti. Formulace v´ yroku P ovlivˇ nuje v´ ysledek segmentace. V pˇr´ıpadˇe sloˇzit´e v´ yrokov´e formule doch´ az´ı velice ˇcasto k podsegmentov´an´ı a naopak v pˇr´ıpadˇe jednoduch´ ych v´ yrok˚ u k pˇresegmentov´ an´ı. Pro optim´aln´ı stanoven´ı segmentaˇcn´ıho krit´eria se pouˇz´ıvaj´ı optimalizaˇcn´ı a adaptivn´ı algoritmy zaloˇzen´e na lok´aln´ı anal´ yze obrazu.
4.2
Segmentaˇ cn´ı algoritmy
V literatuˇre jsou pops´any stovky segmentaˇcn´ıch algoritm˚ u, ale neexistuje univerz´aln´ı metoda, kter´a by mohla b´ yt u ´spˇeˇsnˇe pouˇzita pro vˇsechny aplikace a typy obrazu. Je moˇzn´e ˇ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´e. Existuje mnoho segmentaˇcn´ıch pˇr´ıstup˚ u (prahov´ an´ı, hranov´ a detekce, nar˚ ust´ an´ı oblasti, statistick´ a anal´yza, Markovsk´e ˇretˇezce, neuronov´e s´ıtˇe, fuzzy logika, . . . ). Vhodnou metodu je moˇzn´e vybrat na z´akladˇe semantick´e informace v obraze, pˇr´ıpadnˇe experiment´alnˇe. V n´asleduj´ıc´ıch kapitol´ach budou pops´any nejv´ıce pouˇz´ıvan´e segmentaˇcn´ı algoritmy. U nˇekter´ ych bude diskutov´ana i jejich vhodnost pro segmentaci a anal´ yzu dopravn´ı sc´eny.
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´e na glob´aln´ı informaci (napˇr´ıklad histogram rozloˇzen´ı jasov´ ych u ´rovn´ı) nebo na lok´aln´ı informaci – matice okol´ı segmentovan´eho elementu. V pˇr´ıpadˇe, ˇze pro prahov´an´ı pouˇzijeme pouze jednu hodnotu prahu (nehledˇe na glob´ aln´ı nebo lok´aln´ı informaci) pro cel´ y obraz, pak tento typ segmentace naz´ yv´ame glob´ aln´ı prahov´ an´ı. Pokud je obraz rozdˇelen do nˇekolika ˇc´ast´ı, nejl´epe na z´akladˇe kontextu´ aln´ı informace, a pro kaˇzdou ˇc´ast je pouˇzita jin´a 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´arn´ı obraz, kter´ y obsahuje dvˇe oblasti – objekt (ˇcern´ a barva) a pozad´ı (b´ıl´a barva). V pˇr´ıpadˇe, ˇze obraz obsahuje nˇekolik objekt˚ u s r˚ uznou charakteristikou povrchu, pak je vhodn´e pouˇz´ıt prahov´ an´ı s v´ıce prahy. Obecnˇe m˚ uˇzeme prahov´an´ı 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´a data. Na segmentaci prahov´ an´ım se tak´e m˚ uˇzeme d´ıvat jako na klasifikaci. Segmentace obrazu s jedn´ım 25
prahem je v podstatˇe klasifikace obrazov´eho bodu do dvou tˇr´ıd – objekt a pozad´ı. Na tomto z´akladˇe a za pˇredpokladu, ˇze barvy objektu a pozad´ı maj´ı norm´aln´ı rozdˇelen´ı s urˇcit´ ym rozptylem, je moˇzn´e 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´a je dostateˇcnˇe odliˇsn´ a od jasu pozad´ı, je moˇzn´e hodnotu prahu urˇcit na z´akladˇe histogramu (obr. 4.1). Objekt a pozad´ı budou v histogramu zn´azornˇ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´a napˇr. v [3], [4], nen´ı moˇzn´e pouˇz´ıt pro segmentaci silnice v dopravn´ı sc´enˇe a to zejm´ena z tˇechto d˚ uvod˚ u: • intenzita jasu povrchu vozovky nen´ı dostateˇcnˇe odliˇsn´a od ostatn´ıch objekt˚ u v obraze a proto nelze pouˇz´ıt metody v´ ypoˇctu prahu popsan´e 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´a ˇcasto pokryt list´ım a jin´ ymi neˇcistotami. V pˇr´ıpadˇe, ˇze pro segmentaci silnice zaloˇzen´e na prahov´an´ı pouˇzijeme i sematickou informaci obsaˇzenou v obraze, m˚ uˇzeme dos´ahnout pˇrekvapivˇe dobr´ ych v´ ysledk˚ u. Pˇri segmentaci dopravn´ı sc´eny zn´ame pˇribliˇznou polohu silnice. D´ale v´ıme, ˇze silnice bude v obraze zaˇc´ınat v jeho doln´ı ˇc´asti a smˇerem k horizontu se bude zuˇzovat. M˚ uˇzeme odhadnout pod´ıl plochy obrazu, kter´ y obsahuje silnici. Na z´akladˇe znalosti o pˇribliˇzn´e poloze silnice je moˇzn´e v obraze vymezit oblast O, kter´a je s velkou pravdˇepodobnost´ı jej´ı souˇc´ ast´ı. Na t´eto oblasti vypoˇcteme z´akladn´ı popisn´e statistiky. Pˇredpokl´adejme, ˇze povrch vozovky je homogenn´ı. Potom intenzita jasu povrchu silnice m´a norm´ aln´ı rozdˇelen´ı Y ∼ N (µ, σ), kde µ je parametr polohy a σ parametr mˇeˇr´ıtka. Parametr polohy µ je pˇredstavov´ an medi´anem, t.j. stˇredn´ı hodnotou, n´ahodn´eho v´ ybˇeru. V´ ypoˇcet medi´ anu je pomˇernˇe n´aroˇcn´ y a v tomto pˇr´ıpadˇe je moˇzn´e s pˇrijatelnou chybou prov´est jeho n´ahradu 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´a odchylka σ vyjadˇruje m´ıru homogenity v´ ybˇeru a t´ım urˇcuje, zda je moˇzn´e 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´enˇe tvoˇr´ı silnice znaˇcnou ˇc´ast obrazu. Za pˇredpokladu, ˇze je jej´ı povrch homogenn´ı, je moˇzn´e silnici v histogramu identifikovat jako v´ yznamn´ y vrchol. Jeho polohu urˇcuje hodnota µ a prahy je moˇzn´e urˇcit na z´akladˇe hodnoty σ.
a) histogram obr´azku 012.bmp
c) histogram obr´azku 015.bmp
b) histogram povrchu vozovky na obr´ azku 012.bmp
d) histogram povrchu vozovky na obr´azku 015.bmp
Obr´ azek 4.2: Histogram intenzit jasu cel´eho obrazu a povrchu silnice
Na obr´azku 4.2 jsou zobrazeny histogramy intenzit jasu pro dva testovac´ı obr´azky. Na z´akladˇe kontextu´ aln´ı informace jsou v obraze vyznaˇceny dostateˇcnˇe velk´e regiony, kter´e jsou s velkou pravdˇepodobnost´ı souˇc´ast´ı 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´e pro segmentaci povrchu vozovky pouˇz´ıt segmentaci prahov´an´ı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´e pro bezchybnou segmentaci pouˇz´ıt predikci okraje silnice zaloˇzen´e na apriorn´ıch pravdˇepodobnostech polohy silnice v obraze.
Statistiky V´ ybˇerov´ y pr˚ umˇer µ Smˇerodatn´a odchylka σ Rozsah v´ ybˇeru
Obr´azek 012.bmp 167.00 5.40 1000
Obr´azek 015.bmp 136.00 24.04 1000
Tabulka 4.1: Popisn´e statistiky
27
Vlivem perspektivn´ı projekce se silnice v obraze zuˇzuje. Pokud obraz rozdˇel´ıme do vrstev o ˇs´ıˇrce jednoho obrazov´eho bodu, potom bude ˇs´ıˇrka silnice ve vrstvˇe i menˇs´ı nebo rovna ˇs´ıˇrce silnice ve vrstvˇe i − 1. Na z´akladˇe tohoto pˇredpokladu m˚ uˇzeme definovat apriorn´ı pravdˇepodobnosti polohy silnice v obraze tak, jak je zn´azornˇeno na obr´azku 4.3.
Obr´ azek 4.3: Predikce okraje silnice
V pˇr´ıpadˇe, ˇze pouˇzijeme vˇsechny v´ yˇse popsan´e metody, je moˇzn´e v ˇradˇe pˇr´ıpad˚ u pouˇz´ıt pro segmentaci silnice v obraze prahov´an´ı. Jedn´a se o velmi jednoduchou a rychlou metodu, kterou je moˇzn´e pouˇz´ıt pouze pro silnice s homogenn´ım povrchem vozovky. Na obr´azku 4.4 jsou zobrazeny v´ ysledky segmentace na dvou obr´azc´ıch, kter´e splˇ nuj´ı podm´ınku homogenity (viz. histogram na obr´azku 4.2). Dalˇs´ı podrobnosti o pouˇzit´ı t´eto metody pro segmentaci z´ony z´ajmu budou uvedeny v kapitol´ach 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´ahl´ ymi, v´ yrazn´ ymi zmˇenami jasov´e funkce. Jednoduch´e gradientn´ı oper´atory jako Roberts˚ uv reaguj´ı nejen na hrany v obraze, ale tak´e na izolovan´e body (ˇsum). Z tohoto pohledu se jako v´ yhodn´ y gradientn´ı oper´ator jev´ı Sobel˚ uv oper´ator, kter´ y je odolnˇejˇs´ı proti ˇsumu v obraze, zvl´aˇstˇe pokud zvˇetˇs´ıme konvoluˇcn´ı masku na velikost 5 × 5. Re´ aln´e obr´azky dopravn´ıch sc´en obsahuj´ı kromˇe ˇsumu tak´e st´ıny od ostatn´ıch objekt˚ u v obraze, povrch silnice b´ yv´a velmi ˇcasto poruˇsen, pˇr´ıpadnˇe pokryt r˚ uzn´ ymi neˇcistotami. V tˇechto pˇr´ıpadech z´ısk´ame prostˇrednictv´ım gradientn´ıch oper´ator˚ u velk´e mnoˇzstv´ı moˇzn´ ych hran, kter´e 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´e ani za pomoci apriorn´ı informace 28
012.bmp
041.bmp
Obr´ azek 4.4: V´ ysledky segmentace prahov´an´ım (obr´azek 012.bmp a 041.bmp)
urˇcit okraj silnice. Pro rozpozn´an´ı objekt˚ u v obraze je nutn´ y struktur´aln´ı popis, kter´ y ’ sebou pˇrin´ aˇs´ı zv´ yˇsen´e v´ ypoˇcetn´ı a pamˇet ov´e n´aroky. Obr´azek 4.5 zn´azorˇ nuje v´ ysledek Sobelova hranov´eho detektoru (2.9) na tˇrech obr´azc´ıch z testovac´ı datab´aze. Obr´azek 016.bmp obsahuje silnici bez dopravn´ıho znaˇcen´ı, povrch vozovky je ˇc´asteˇcnˇe poˇskozen a je mokr´ y. V´ ysledkem hranov´e detekce je velk´e mnoˇzstv´ı nespojit´ ych hran. Obr´azek 033.bmp pˇredstavuje typick´ y pˇr´ıklad dobˇre znaˇcen´e silnice s nepoˇskozenou texturou vozovky. V´ ysledkem jsou v´ yrazn´e, spojit´e hrany, kter´e jsou vhodn´e pro segmentaci obrazu.
016.bmp
033.bmp
Obr´ azek 4.5: V´ ysledky hranov´e detekce
29
Experiment´ alnˇe jsem zjistil, ˇze metoda segmentace silnice zaloˇzen´a na hranov´e detekci je pouˇziteln´ a pouze pro tˇretinu obr´azk˚ u z testovac´ı datab´aze. Na z´akladˇe experimentu se domn´ıv´ am, ˇze segmentace prostˇrednictv´ım hranov´e detekce nen´ı vhodnou metodou pro anal´ yzu dopravn´ı sc´eny. Proto jsem vyvinul metodu zaloˇzenou na barevn´e segmentaci, kter´a je v´ ypoˇcetnˇe obdobnˇe n´aroˇcn´ a jako segmentace hranovou detekc´ı, ale pouˇziteln´ a pro vˇetˇsinu obr´azk˚ u. Teoretick´a ˇc´ast bude pops´ana v n´asleduj´ıc´ı kapitole, vlastn´ı algoritmus pak v kapitol´ach 4.3.
4.2.3
Barevn´ a segmentace
V literatuˇre je pops´ano mnoho algoritm˚ u pro segmentaci barevn´ ych obr´azk˚ u [9], ale jejich poˇcet nen´ı ani zdaleka tak bohat´ y jako pro ˇsedot´onov´e obr´azky. Tento nedostatek je patrn´ y zvl´aˇstˇe pro algoritmy zaloˇzen´e na segmentaci nar˚ ust´an´ım oblasti. Je moˇzn´e pouˇz´ıt nˇekolik krit´eri´ı, na jejichˇz z´akladˇe rozhodujeme o tom, zda obrazov´ y element n´aleˇz´ı do segmentovan´e oblasti. Tato krit´eria mohou b´ yt definov´ana na nˇekolika rozliˇsovac´ıch u ´rovn´ıch – lok´aln´ı, region´aln´ı nebo glob´aln´ı. Pˇri lok´aln´ım rozliˇsen´ı rozhodujeme o tom, zda sousedn´ı pixely n´aleˇz´ı do testovan´eho regionu. Pˇri region´ aln´ım rozliˇsen´ı o tom, zda testovan´ y region n´aleˇz´ı do segmentovan´e oblasti. Glob´aln´ı rozliˇsovac´ı u ´roveˇ n se pouˇz´ıv´ a zvl´aˇ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´eria 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´aroky algoritmu dodateˇcnou anal´ yzou hraniˇcn´ıch oblast´ı, kter´a b´ yv´a 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´an´ı obrazu je barevn´a informace. Kaˇzd´ a barva odpov´ıd´ a urˇcit´e frekvenci elektromagnetick´eho vlnˇen´ı v p´asmu 8 10 MHz. Rozsah barev je od ˇcerven´e – 430 nm aˇz po fialovou – 750 nm. V r´amci viditeln´eho spektra je ˇclovˇek schopen rozliˇsit v´ıce neˇz 4 × 105 barevn´ ych odst´ın˚ u. Podle frekvence, kter´e vys´ıl´ a svˇeteln´ y zdroj je moˇzn´e barvy rozdˇelit na • achromatick´e – barva tˇelesa je tvoˇrena kombinac´ı frekvenc´ı odraˇzen´ ych od tˇelesa. Pokud pˇrevl´ ad´ a frekvence z urˇcit´e oblasti spektra, pak mluv´ıme o dominantn´ı frekvenci. • monochromatick´e – barva tˇelesa je urˇcena odrazem jen jedn´e frekvence - napˇr. frekvenc´ı zelen´e barvy. Mnoho fyziologick´ ych studi´ı prok´azalo, ˇze barevn´a informace je tˇr´ısloˇzkov´a. To znamen´ a, ˇze k pops´an´ı vˇsech barevn´ ych odst´ın˚ u je nutn´e pouˇz´ıt tˇri promˇenn´e. Libovolnou 3 barvu tedy m˚ uˇzeme popsat vektorem v < . Jednotliv´e barevn´e odst´ıny se odvozuj´ı od tˇr´ı z´akladn´ıch barev aditivn´ım nebo subtraktivn´ım m´ıch´an´ım. Existuje mnoho metod (barevn´ ych model˚ u), kter´ ymi se popisuje barevn´a informace a na jejich z´akladˇe je moˇzn´e kaˇzd´ y barevn´ y odst´ın dekomponovat na z´akladn´ı sloˇzky. Kaˇzd´ y barevn´ y model je pops´an mnoˇzinou z´akladn´ıch barev, zp˚ usobem jejich m´ıch´an´ı a pravidly pomoc´ı kter´ ych se mˇen´ı barevn´e charakteristiky.
30
Barevn´ y model RGB V tomto modelu jsou barvy vytv´aˇreny aditivn´ım zp˚ usobem. Z´akladn´ı sloˇzky jsou R red - ˇcerven´ a, G - green - zelen´a, B - blue - modr´a. Pro tyto barvy je charakteristick´e pr´avˇe to, ˇze lidsk´e oko m´a nejvˇetˇs´ı citlivost pr´avˇe pro jejich vlnov´e d´elky (630nm, 530nm a 450nm). Intenzita z´akladn´ıch barev se v tomto modelu pohybuje v intervalu < 0, 1 >. V technick´ ych aplikac´ıch jako je poˇc´ıtaˇcov´e vidˇen´ı a zpracov´an´ı obrazu je tento interval pˇrev´adˇen do digit´aln´ı formy. Nejˇcastˇejˇs´ı je k´odov´an´ı do 8-bitov´eho rozliˇsen´ı (256 u ´rovn´ı).
Obr´ azek 4.6: Grafick´a reprezentace modelu RGB
Barevn´ y model RGB se nejˇcastˇeji zn´azorˇ nuje jako krychle um´ıstˇen´a v os´ach RGB. Z toho vypl´ yv´ a, ˇze mnoˇzina z´akladn´ıch barev je tvoˇrena 8 barvami. Vrchol [0, 0, 0] (t.j. stˇred souˇradnicov´eho syst´emu) odpov´ıd´a ˇcern´e 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´e odst´ıny. V´ yˇse popsan´ y barevn´ y model se nejv´ıce pouˇz´ıv´a v technick´ ych aplikac´ıch. Uplatnˇen´ı naˇsel zejm´ena ve videotechnice. Na z´akladˇe obr´azku 4.6 m˚ uˇzeme vytvoˇrit tabulku z´akladn´ıch barev RGB modelu. Barva ˇcern´ a modr´a zelen´ a tyrkysov´a ˇ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´akladn´ıch barev v syst´emu RGB
Barevn´ y model HSV CIE – Commission Internationale de l’Eclairege standardisovala modely, kter´e umoˇzn ˇuj´ı rozdˇelit libovolnou barvu na jej´ı z´akladn´ı sloˇzky. Doporuˇcila pˇrirozen´ y barevn´ y model RGB, kter´ y ovˇsem neodpov´ıd´a lidsk´emu ch´ap´an´ı svˇetla. Z tohoto pohledu je vhodn´e pouˇz´ıvat barevn´ y model HSV, kter´ y barvy popisuje na z´akladˇe tˇr´ı intuitivn´ıch atribut˚ u:
31
• V - value – jas. Reprezentuje mnoˇzstv´ı svˇetla pˇrijat´eho senzorem. Z´aleˇz´ı na svˇeteln´ ych podm´ınk´ ach a na intenzitˇe svˇeteln´eho zdroje. • H - hue – barevn´ y odst´ın. Hodnota kter´a reprezentuje jednu ze z´akladn´ıch barev modelu RGB. H 0 1 2 3 4 5
Barva ˇcerven´a ˇzlut´a zelen´a tyrkysov´a modr´a fialov´a
Tabulka 4.3: Vztah mezi hodnotou H a jm´enem barvy v modelu RGB
• S - saturation – saturace (sytost). Saturace popisuje napˇr. rozd´ıly mezi ˇcervenou a r˚ uˇzovou. Tmavˇe ˇcerven´e odpov´ıd´a vysok´a hodnota saturace a naopak r˚ uˇzov´e n´ızk´ a.
Obr´ azek 4.7: Grafick´a 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´eho syst´emu. Souˇradnice v a s se podobnˇe jako u modelu RGB mˇ en´ı od 0 do 1, pˇr´ıpadnˇe jsou k´odov´any do 8 bitov´eho rozliˇsen´ı. Souˇradnice h je u ´hlov´ a. Vrchol jehlanu v bodˇe [0, 0, 0] pˇredstavuje ˇcernou barvu. B´ıl´a barva je ve stˇredu podstavy. Jas kles´a od podstavy k vrcholu. Sytost je d´ana vzd´alenost´ı od osy jehlanu. Z´akladn´ı barvy se nach´ azej´ı ve vrcholech ˇsesti´ uheln´ıkov´e podstavy. Matematick´ y popis modelu HSV Existuje nˇekolik metod pomoc´ı kter´ ych je moˇzn´e transformovat RGB model na model HSV. Rovnice 4.5, 4.6, 4.7 pˇredstavuj´ı nejjednoduˇsˇs´ı a v´ ypoˇcetnˇe nejm´enˇe n´aroˇcn´ y zp˚ usob. Uveden´ a transformace vyˇzaduje pouze N n´asoben´ı a 2N dˇelen´ı, kter´e mohou b´ yt nav´ıc pˇredpoˇc´ıtan´e v tabulce. Ostatn´ı transformace jako Lu∗ v ∗ uveden´e 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´aroky t´eto transformace jsou 5 kr´at vyˇsˇs´ı. V n´asleduj´ıc´ıch rovnic´ıch pˇredpokl´ad´ ame 8 bitov´e barevn´e 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´e promˇenn´e 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´aˇ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´e komponenty RGB jsou normalizovan´e a nab´ yvaj´ı tedy hodnot z intervalu [0, 1]. Na z´akladˇe rovnice 4.8 je alespoˇ n jedna ze sloˇzek nulov´ a. Pˇredpokl´adejme, ˇze cR = 1. Potom jsou normalizovan´e −1 sloˇzky cG , cB nulov´e a H = 1−0 = −1. Pro hodnotu cR = 0.5 je v´ ysledek rovnice 4.7 1 nebo −1. To znamen´a, ˇze H pro pˇr´ıpad V = R nab´ yv´a hodnoty z intervalu [−1, 1]. Obdobnou u ´vahou pro V = B nab´ yv´a hodnot z intervalu [3, 5]. To znamen´a, ˇze v´ ysledek t´eto transformace leˇz´ı v intervalu [−1, 5]. Abychom z´ıskali v´ ysledek z intervalu [0, 6], je z´avˇerem nutn´e prov´est dˇelen´ı H mod 6. Pˇri segmentaci je velmi ˇcasto nutn´e spoˇc´ıtat vzd´alenost dvou pˇr´ıznak˚ u. V barevn´em modelu HSV nelze pouˇz´ıt pro v´ ypoˇcet vzd´alenosti metody popsan´e v kapitole 2.2. Pˇredpokl´adejme, ˇze H1 a H2 jsou barevn´e odst´ıny dvou bod˚ u v HSV barevn´em prostoru a splˇ nuj´ı tuto podm´ınku: (H1 , H2 ) ∈ [0, 6]
(4.9)
Vzd´alenost 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´an za zhorˇsen´ ych svˇeteln´ ych podm´ınek, pak jsou objekty v obraze tmav´e (maj´ı n´ızkou sytost – hodnotu S). Tyto objekty je v HSV modelu obt´ıˇzn´e segmentovat. Z rovnice 4.6 vypl´ yv´a, ˇ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´e barvy. Pokud jsou splnˇeny podm´ınky rovnice 4.11, potom doch´az´ı v rovnici 4.7 k dˇelen´ı nulou a tedy H nen´ı definovan´e – model se st´av´a aritmeticky nestabiln´ı. 33
Z´ akladn´ım probl´emem tedy je naj´ıt v barevn´em spektru obrazu ty body, ve kter´ ych nen´ı H definov´ ano. Tyto body jsou charakteristick´e t´ım, ˇze maj´ı n´ızkou saturaci. V literatuˇre bylo prok´az´ ano [1], ˇze H je nejv´ yznamˇejˇs´ı popisn´ y atribut HSV modelu a t´ım je velmi vhodn´ y pro segmentaci. Probl´emem ovˇsem z˚ ust´av´a ˇc´asteˇcn´a 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´y a nebo achromatick´y a tedy nevhodn´ y pro segmentaci na z´akladˇe hodnoty H. V pˇr´ıpadˇe, ˇze sc´ena byla sn´ım´ana za ˇspatn´ ych svˇeteln´ ych podm´ınek, tak obsahuje achromatick´e oblasti. Achromatick´e oblasti se v obraze vyskytuj´ı napˇr´ıklad za tˇechto podm´ınek: • pˇri n´ızk´em nasv´ıcen´ı sc´eny, potom jsou objekty tmav´e, nˇekdy aˇz ˇcern´e, • a naopak, pokud je sc´ena pˇresv´ıcena, doch´az´ı 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´e 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´e klasifikovat pixely do chromatick´ ych a achromatick´ ych oblast´ı a t´ım rozhodnout o zp˚ usobu segmentace. Vhodn´a metoda je uvedena napˇr´ıklad v [1]. Autoˇri definuj´ı funkci (rovnice 4.13), kter´a popisuje stupeˇ n chromaticity pixelu c(P ) =
d 1 + s(P ) tanh( D ) , 2
(4.13)
kde s(P ) je konstanta, definovan´a pomoc´ı hodnot S a V nab´ yvaj´ıc´ı hodnoty [-1,0,1], identifikuje chromatick´e a achromatick´e oblasti v HSV barevn´em prosoru, d je vzd´alenost od testovan´eho pixelu P a konstanty s(P ) a D je konstanta, definuj´ıc´ı prostor pˇrechodu od chromatick´e k achromatick´e 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´ano 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´e reference v literatuˇre, nen´ı HSV barevn´ y model nejlepˇs´ım ˇreˇsen´ım pro segmentaci povrchu vozovky. D˚ uvodem je jeho aritmetick´a nestabilita pro achromatick´e oblasti. V re´aln´ ych dopravn´ıch sc´en´ach, kde m´a silnice tmav´ y nebo ˇsed´ y povrch, je velice ˇcasto splnˇena rovnice 4.11 a pro segmentaci je pot´e pouˇzito (slab´e) kriterium dan´e 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´e, ˇze barevn´a segmentace pˇrin´aˇs´ı lepˇs´ı v´ ysledky, neˇz segmentace ˇsedot´ onov´ ych obr´azk˚ u. Z´aroveˇ n je zˇrejm´e, ˇze implementace v´ ypoˇcetnˇe n´aroˇ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´ahl´e systematick´e experimenty, tak aby nalezl soubor vhodn´ ych a efektivn´ıch barevn´ ych atribut˚ u pro segmentaci nar˚ ust´an´ım oblast´ı [9]. Zjistil, ˇze velmi kvalitn´ı atributy je moˇzn´e 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´akladn´ı sadu transformaˇcn´ıch rovnic je vhodn´e rozˇs´ıˇrit jeˇstˇe o vzd´alenost ˇcerven´e a zelen´e, pˇr´ıpadnˇe ˇzlut´e a modr´e 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´em˚ u pˇri anal´ yze obrazu. Z´avis´ı jednak na pouˇzit´em barevn´em prostoru a jednak na pouˇzit´e metrice. Definice vzd´alenosti 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´eho modelu RGB se obvykle pouˇz´ıv´a Euklidova metrika. Potom vzd´alenost dvou bod˚ u v RGB prostoru je definov´ana 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´e umˇet spoˇc´ıtat tak´e vzd´alenost barvy od shluku barev. Shluk barev je v tomto pˇr´ıpadˇe zastoupen stˇredn´ı hodnotou jednotliv´ ych sloˇzek barevn´eho modelu. d2E (f (x, y), S) = (fR (x, y) − SR )2 + (fG (x, y) − SG )2 +
(4.17)
2
(fB (x, y) − SB ) ,
Vzd´alenost 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´alenost. Homogenitu shluku barev je moˇzn´e spoˇc´ıtat tak jako v kapitole 4.2.1. Pokud je smˇerodatn´a odchylka nadprahov´a, je vhodn´e pro v´ ypoˇcet vzd´alenosti pouˇz´ıt Mahalanobiho vzd´ alenost, kter´a je definov´ana 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´a odchylka shluku barev. Vzd´alenost barvy od shluku, nebo dvou shluk˚ u je moˇzn´e spoˇc´ıtat i jinak, napˇr´ıklad na z´akladˇe statistick´e anal´ yzy shluku. V literatuˇre [6] se uv´ad´ı napˇr´ıklad tyto vzd´alenosti 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´eho algoritmu pro segmentaci silnice v dopravn´ı sc´enˇe jsem se zab´ yval tak´e v´ ybˇerem vhodn´ ych pˇr´ıznak˚ u a segmentaˇcn´ıch krit´eri´ı. Pouˇzit´ı nevhodn´eho pˇr´ıznaku m˚ uˇze v´ yraznˇe sn´ıˇzit u ´spˇeˇsnost jinak vhodnˇe navrˇzen´eho algoritmu. V prvn´ı f´azi v´ yvoje jsem pouˇz´ıval pouze ˇsedot´ onov´e 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´e hodnoty jasu dvou sousedn´ıch segment˚ u, • pr˚ umˇern´ a hustota textury segmentu definovan´a T (s) =
1 X X |fi − fj | As i j∈N (i) 8
(4.20)
kde fi je hodnota jasu i-t´eho pixelu, N (i) je mnoˇzina osmi sousedn´ıch pixel˚ ua As je plocha segmentu, definovan´a jako poˇcet pixel˚ u, kter´e leˇz´ı v segmentu. Zjistil jsem, ˇze kombinace prvn´ıch dvou pˇr´ıznak˚ u pˇrin´aˇs´ı lepˇs´ı v´ ysledky segmentace neˇz pˇri pouˇzit´ı pr˚ umˇern´e hustoty textury. V dalˇs´ıch experimentech jsem pracovat uˇz v´ yhradnˇe s barevn´ym obrazem a mnoˇzinu studovan´ ych pˇr´ıznak˚ u jsem rozˇs´ıˇril o: • pr˚ umˇern´e hodnoty R, G, B sloˇzek barevn´eho modelu RGB, • sloˇzky barevn´eho modelu HSV (kapitola 4.2.3), 36
• Karhunen–Loaveho pˇr´ıznaky (4.14), • vzd´ alenosti ˇcerven´e a zelen´e, ˇzlut´e a modr´e sloˇzky barvy (4.15), • Euklidovu vzd´alenost 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´eri´ı je zaloˇzena na v´ ypoˇctu vzd´alenosti dvou barevn´ ych odst´ın˚ u, pˇr´ıpadnˇe vzd´alenosti barevn´eho odst´ınu od shluku barev. Pro v´ ypoˇcet vzd´alenosti dvou barevn´ ych odst´ın˚ u je pouˇzit vzorec 4.16, pro vzd´alenost 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´e 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´e specifikovat, zda pixel (x , y ) leˇz´ı v okol´ı pixelu (x, y), nebo regionu, kter´ y je s pixelem (x, y) reprezentov´an, zav´ad´ı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´e 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´e do shluku na z´akladˇe krit´eria 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´eho 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´avnou funkˇcnost kriteri´ı II a II’ je nutn´e ovˇeˇrit, zda testovan´ y region obsahuje dostatek pixel˚ u, kter´e 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´aln´ı poˇcet pixel˚ u, kter´e mus´ı uvnitˇr regionu splˇ novat kriterium I. Pˇri pouˇzit´ı masky 3 × 3 jsem zjistil, ˇze optim´aln´ı hodnota Ap je 6. Kriterium IV dE (CR (S), CR (S 0 )) ≤ TGHC
(4.31)
Toto kriterium urˇcuje, zda je moˇzn´e spojit dva sousedn´ı regiony do regionu jednoho. Kriterium IV je v hiearchick´e u ´rovni nejv´ yˇse a je tedy pouˇzit´e pro vlastn´ı nar˚ ust´an´ı oblasti. Volba prahu V literatuˇre je moˇzn´e nal´ezt nˇekolik studi´ı, kter´e se zab´ yvaly probl´emem urˇcen´ı prahu, pˇr´ıpadnˇe adaptivn´ım urˇcov´ an´ım prahu, na z´akladˇe kontextu´aln´ı nebo lok´aln´ı informace. Zjednoduˇsenˇe je moˇzn´e ˇr´ıci, ˇze u ´spˇech segmentace nar˚ ust´an´ım oblasti je tˇesnˇe spojen s vhodnou volbou prahu segmentaˇcn´ıho kriteria. Tyto prahy mohou b´ yt stejn´e pro vˇsechny obr´azky, nebo se mohou mˇenit na z´akladˇ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´akladˇe spoˇc´ıtan´ ych lok´aln´ıch charakteristik (napˇr´ıklad anal´ yza textury). Vˇetˇsina publikovan´ ych metod se vˇenuje v´ ypoˇctu prahu pro segmentaci prahov´an´ım s v´ıce prahy. Metody urˇcen´e pro v´ ypoˇcet prahu pro segmentaci nar˚ ust´an´ım oblasti [8], jsou v´ ypoˇcetnˇe natolik n´aroˇcn´e, ˇze je nen´ı moˇzn´e pouˇz´ıt v segmentaˇcn´ıch algoritmech syst´emu RS2 . Hodnoty prah˚ u jsou nastaveny a optimalizov´any experiment´alnˇe, tak aby byl algoritmus pouˇziteln´ y pro co nejvˇetˇs´ı mnoˇzstv´ı obr´azk˚ u.
4.3
Algoritmus
V t´eto kapitole budou pops´any algoritmy segmentace z´ony z´ajmu v obraze (AOI). Syst´em se skl´ad´ a z pˇeti hlavn´ıch algoritm˚ u, kter´e jsou blokovˇe zn´azornˇeny na obr´azku 4.9. Algoritmus I se pouˇz´ıv´ a pro v´ ypoˇcet homogenity textury povrchu vozovky. Na z´akladˇe v´ ysledku algoritmu I je zvolena segmentaˇcn´ı metoda. Pokud je povrch vozovky dostateˇcnˇe homogenn´ı, je zvolen Algoritmus II – segmentace prahov´an´ım. V opaˇcn´em pˇr´ıpadˇe je pouˇzita barevn´a segmetace – Algoritmus III, tak jak byla pops´ana v kapitole 38
4.2.3. Algoritmus IV na z´akladˇe porovn´an´ı v´ ysledk˚ u segmentace s geometrick´ ym modelem dopravn´ı sc´eny 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´avn´ y, pak algoritmus AOI pokraˇcuje zpracov´ an´ım dalˇs´ıho sn´ımku a ostatn´ı algoritmy syst´emu RS2 zpracov´avaj´ı obraz bez z´ony z´ajmu. V pˇr´ıpadˇe kladn´eho v´ ysledku je v obraze vyznaˇcen region, ve kter´em se mohou na z´akladˇe normy3 vyskytovat doprav´ı znaˇcky – Algoritmus V. Problematika segmentace z´ony z´ajmu je natolika rozs´ahl´a, ˇze pˇri zad´an´ı probl´emu byla pˇrijata urˇcit´ a omezen´ı: 1. dopravn´ı sc´ena je sn´ım´ ana barevnou kamerou za denn´ıho svˇetla, 2. z´onou z´ajmu se nerozum´ı oblast port´al˚ u, 3. pˇred automobilem je vozovka bez pˇrek´aˇzek do vzd´alenosti alespoˇ n 50 m
4.3.1
Stanoven´ı homogenity povrchu vozovky
´ Uvodn´ ım algoritmem syst´emu rozpozn´an´ı z´ony z´ajmu v obraze je algoritmus stanoven´ı homogenity textury povrchu vozovky. Na z´akladˇe apriorn´ı informace je v obraze vymezena oblast, kter´a je s velkou pravdˇepodobnost´ı souˇc´ast´ı povrchu vozovky. Velikost t´eto oblasti je nutn´e 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´akladn´ıch statistik dostateˇcnˇe velk´ y a v´ ypoˇcetn´ı n´aroky jsou pˇrimˇeˇren´e. Pˇri zvˇetˇsen´ı rozsahu v´ ybˇeru se vypoˇc´ıtan´e statistiky t´emˇeˇr nemˇen´ı, ale v´ ypoˇcetn´ı n´aroky algoritmu vzr˚ ustaj´ı.
Obr´ azek 4.10: Velikost a pozice testovan´e oblasti
Jak je zˇrejm´e z obr´azku 4.10, oblast, kter´a je pouˇzita pro v´ ypoˇcet homogenity, je um´ıstˇena uprostˇred v doln´ı ˇc´asti obrazu. Pokud automobil jede v prav´em 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´akladˇe anal´ yzy histogramu a v´ ypoˇctu z´akladn´ıch statistik, tak jak bylo pos´ano v kapitole 4.2.1. 3ˇ
CSN 73 6101 – Projektov´ an´ı silnic a d´ alnic
39
Obr´ azek 4.9: Blokov´e schema algoritmu segmentace z´ony z´ajmu 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´a data z testovan´eho regionu. V pˇr´ıpadˇe, ˇze je smˇerodatn´ a odchylka spoˇcten´a na ˇr´adku 15: menˇs´ı neˇz stanoven´ y konstantn´ı pr´ah, pak je povrch vozovky dostateˇcnˇe homogenn´ı a pro segmentaci silnice je moˇzn´e pouˇz´ıt segmentaci prahov´ an´ım. V opaˇcn´em pˇr´ıpadˇe je nutn´e 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´ony z´ajmu jsem testoval tˇri algoritmy – segmentaci prahov´an´ım, segmentaci na z´akladˇe detekce hran v obraze a barevnou segmentaci nar˚ ust´an´ım oblasti. Po prvn´ıch experimentech a po zkuˇsenostech s rozpozn´av´an´ım geometrick´ ych obrazc˚ u v obraze jsem v´ yvoj omezil pouze na dvˇe metody – segmentaci prahov´ an´ım a barevnou segmentaci. Teoretick´a ˇc´ast tˇechto segmentaˇcn´ıch algoritm˚ u byla pops´ana v kapitole 4.2.1 resp. v kapitole 4.2.3. Ostatn´ı segmentaˇcn´ı techniky jsou v´ ypoˇcetnˇe mnohem n´aroˇcnˇejˇs´ı a t´ım nevhodn´e pro algoritmus vymezen´ı z´ony z´ajmu v obraze, zvl´aˇstˇe pokud m´a b´ yt implementovan´ y v re´aln´em ˇ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´a pro popis a predikci okraje silnice v jednotliv´ ych segmentovan´ ych vrstv´ach. Konstanty c1 a c2 na ˇr´adku 6: a 7: jsou jedn´ım z parametr˚ u algoritmu. Pomoc´ı tˇechto konstant je nastavena ˇs´ıˇrka silnice v obraze v nult´e vrstvˇe. Toto nastaven´ı nen´ı bezpodm´ıneˇcnˇe nutn´e, zvl´aˇstˇe pokud jsou zpracov´ av´ any sekvence sn´ımk˚ u. Konstanta k na ˇr´adku 8: ovlivˇ nuje vzd´alenost, do jak´e bude silnice pˇred automobilem segmentov´ana (poˇcet segmentovan´ ych vrstev). Funkce BorderPrediction() na ˇr´ adku 28: se pouˇz´ıv´a k predikci polohy a ˇs´ıˇrky i + 1 vrstvy na z´akladˇe v´ ysledk˚ u segmentace vrstvy i. Okraj silnice je predikov´an na z´akladˇe apriorn´ıch pravdˇepodobnost´ı polohy silnice v obraze, tak jak bylo pops´ano v kapitole 4.2.1 a zn´azornˇeno na obr´azku 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´an´ım. V tˇechto pˇr´ıpadech je nutn´e pouˇz´ıt segmentaci nar˚ ust´an´ım oblasti, kter´a je zaloˇzena na anal´ yze lok´aln´ı informace v okol´ı testovan´eho 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´azi je cel´ y obraz rozdˇelen do vrstev. Poloha a velikost prvn´ı vrstvy je stanovena na z´akladˇe apriorn´ı informace, pˇr´ıpadnˇe na z´akladˇe v´ ysledk˚ u segmentace pˇredchoz´ıho sn´ımku. Poloha a velikost vˇsech n´asleduj´ıc´ıch vrstev je predikov´ana z v´ ysledk˚ u segmentace v pˇredchoz´ıch vrstv´ach. V tomto algoritmu jsou pouˇzita segmentaˇcn´ı kriteria I, II’ a III. Uveden´ y algoritmus je moˇzn´e velmi jednoduˇse rozˇs´ıˇrit i o kriterium IV pouˇzit´ım funkce ˇ CompareRegions(). Ctvrt´ e segmentaˇcn´ı kriterium je vhodn´e pouˇzit pouze v pˇr´ıpadˇe, ˇze velikost testovan´ ych (a porovn´avan´ ych) region˚ u je vˇetˇs´ı neˇz 3 × 3 obrazov´e body. Tˇret´ı segmentaˇcn´ı kriterium je zastoupeno funkc´ı PixelCount(). Tato funkce z´aroveˇ n oznaˇc´ı pouze ty obrazov´e elementy, kter´e 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´eho algoritmu t´ım, ˇze jsou poˇc´ıtan´e pouze pˇr´ıznaky nov´ ych (sousedn´ıch) region˚ u. Funkce BorderPrediction(), konstanty a promˇenn´e pouˇzit´e 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´ona z´ajmu je v obraze stanovena na z´akladˇe v´ ysledku segmentaˇcn´ıho algoritmu. Z tohoto d˚ uvodu je nutn´e rozhodnout, zda segmentace povrchu vozovky byla u ´spˇeˇsn´a. Z´onu z´ajmu nen´ı moˇzn´e stanovit, pokud v´ ysledek segmentace neodpov´ıd´a skuteˇcnosti. Pˇri segmentaci silnice m˚ uˇze doj´ıt v podstatˇe pouze k dvˇema chyb´am: 1. vlivem slab´eho segmentaˇcn´ıho krit´eria, doˇslo k pˇresegmentov´an´ı, 2. vlivem pˇr´ıliˇs siln´eho segmentaˇcn´ıho krit´eria (pˇr´ıpadnˇe v´ yrazn´e poruchy v textuˇre vozovky, pˇrek´ aˇzky na silnici, . . . ) dojede k podsegmentov´an´ı. Tyto chybn´e v´ ysledky je nutn´e identifikovat, aby nedoch´azelo k nespr´avn´emu stanoven´ı z´ony z´ajmu. V´ yhodou pˇri segmentaci silnice je apriorn´ı znalost sc´eny. Pˇri pouˇzit´ı tˇechto informac´ı je moˇzn´e vytvoˇrit jednoduch´ y geometrick´ y model polohy silnice ve sc´enˇ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´avn´ a else chybn´ a segmentace end if
45
4.3.4
Geometrick´ y model a stanoven´ı z´ ony z´ ajmu
Z´ona z´ajmu je v obraze stanovena porovn´an´ım s geometrick´ ym modelem sc´eny. Je velmi obt´ıˇzn´e urˇcit polohu a optimalizovat velikost z´ony z´ajmu pouze na z´akladˇe statick´ ych 2 obr´azk˚ u. Po pˇr´ıpadn´e modifikaci algoritm˚ u syst´emu RS na sekvence obr´azk˚ u by bylo moˇzn´e, po dalˇs´ıch experimentech, v´ yraznˇe zmenˇsit velikost z´ony z´ajmu.
Obr´ azek 4.11: Z´ona z´ajmu v obraze
Rozpozn´an´ı geometrick´eho tvaru dopravn´ıch znaˇcek prob´ıh´a v nˇekolika u ´rovn´ıch (rozliˇsen´ıch) pyramid´ aln´ı struktury. Tento pˇr´ıstup umoˇzn ˇuje rozpozn´an´ı dopravn´ıch znaˇcek v nˇekolika vzd´alenostech pˇred automobilem, pˇri pouˇzit´ı pouze jednoho, univerz´ aln´ıho algoritmu. Optim´aln´ım ˇreˇsen´ım by bylo vymezen´ı z´ony z´ajmu pro kaˇzdou vzd´alenost danou pyramid´ aln´ı strukturou, pˇr´ıpadnˇe vymezit pouze jednu z´onu z´ajmu, a to takovou, ve kter´e bude m´ıt dopravn´ı znaˇcka vhodnou velikost pro klasifikaˇcn´ı algoritmus. Tento pˇr´ıstup vyˇzaduje spoleˇcn´e rozhran´ı a v´ ymˇenu informac´ı jednotliv´ ych algoritm˚ u syst´emu RS2 , kter´e 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´ony z´ajmu 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´azky sv´ ym charakterem neodpov´ıdaly zadan´emu probl´emu, 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´aznam byl pot´e grabbov´an, pˇreveden na sekvenci sn´ımk˚ u 1 ve form´atu BMP, na poˇc´ıtaˇci SGI Indy . Pouˇzit´ı poˇc´ıtaˇce SGI bylo v´ yhodn´e zejm´ena pro bezprobl´emovou pr´aci s kompozitn´ım video-sign´alem. Pˇri digitalizaci na bˇeˇzn´em grabberu jsem mˇel probl´emy se synchronizac´ı jednotliv´ ych sn´ımk˚ u a proto byl v´ ysledek t´emˇeˇr nepouˇziteln´ y. Koncem roku 1997 jsme pˇri v´ yvoji syst´emu RS2 zaˇcaly pouˇz´ıvat barevnou digit´aln´ı CCD kameru Sony, kter´a velmi dobˇre spolupracuje s grabberem firmy Matrox. Dalˇs´ı obrazov´ a data pro v´ yvoj algoritm˚ u segmentace z´ony z´ajmu byla z´ısk´av´ana pouze touto kamerou. Vˇetˇsina obrazov´ ych dat v projektu RS2 byla nasn´ım´ana z jedouc´ıho automobilu pˇr´ımo do pamˇeti poˇc´ıtaˇce a ukl´ad´ana na disk za podm´ınek, kter´e odpov´ıdaj´ı bˇeˇzn´emu provozu na pozemn´ıch komunikac´ıch. V souˇcasn´e dobˇe je k dispozici datab´aze 3000 sn´ımk˚ u dopravn´ıch sc´en. Vˇsechny sn´ımky jsou v rozliˇsen´ı PAL a pokr´ yvaj´ı vˇetˇsinu situac´ı, kter´e mohou na pozemn´ıch komunikac´ıch nastat. Nˇekter´e sekvence byly sn´ım´any za zhorˇsen´ ych meterologick´ ych podm´ınek (za deˇstˇe a po deˇsti). V datab´azi jsou jednak sn´ımky dobˇre znaˇcen´ ych silnic s kvalitn´ım povrchem, ale tak´e sn´ımky neznaˇcen´ ych komunikac´ı s poˇskozen´ ym povrchem. V´ yvoj algoritm˚ u segmentace z´ony z´ajmu v obraze prob´ıhal pˇrev´aˇznˇe na poˇc´ıtaˇc´ıch IBM PC kompatibiln´ıch s procesory Intel Pentium pod operaˇcn´ımy syst´emy MS Windows 95/NT a Linux. Pˇri v´ yvoji bylo pouˇzito programov´e vybaven´ı zejm´ena firem The MathWorks Inc. – Matlab a firmy Microsoft – MS Visual C++. Poˇc´ateˇcn´ı experimenty prob´ıhaly v prostˇred´ı programu Matlab 4.2. Aplikace poˇc´ıtaˇcov´eho vidˇen´ı jsou n´aroˇcn´e na v´ ypoˇcetn´ı v´ ykon, kter´ y Matlab jako interpreter nem˚ uˇze poskytnout. Proto jsem se rozhodl vytvoˇrit vlastn´ı v´ yvojov´e prostˇred´ı v jazyku C++ pro ˇreˇsen´ı segmentace z´ony z´ajmu v obraze. Toto prostˇred´ı bude popsan´e v kapitole 6. Na n´asleduj´ıc´ıch str´ank´ ach budou uvedeny komentovan´e v´ ysledky syst´emu pro segmentaci z´ony z´ajmu v obraze. Jedn´a se o typick´e obr´azky z testovac´ı datab´aze. Obdobn´ ych v´ ysledk˚ u je dosaˇzeno i u ostatn´ıch obr´azk˚ u stejn´e tˇridy a typu. 1
pouˇzit´ı t´eto v´ ypoˇcetn´ı techniky umoˇznilo Oddˇelen´ı zpracov´ an´ı obrazu UTIA CAS
47
5.1
V´ ysledky
V t´eto kapitole budou shrnuty v´ ysledky algoritmu segmentace z´ony z´ajmu v obraze v situac´ıch, kter´e mohou na pozemn´ıch komunikac´ıch nastat. Uvedeno je pouze nˇekolik charakteristick´ ych obr´azk˚ u. Obdobn´ ych v´ ysledk˚ u je dosaˇzeno i pro vˇetˇsinu ostatn´ıch obr´azk˚ u z testovac´ı datab´aze. V´ ypoˇcet segmentace z´ony z´ajmu v obraze na poˇc´ıtaˇci s procesorem Pentium 100 MHz trv´a 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´ale sn´ıˇz´ı na u ´roveˇ n stovek mikrosekund. Na obr´azku 5.2 jsou uvedeny v´ ysledky algoritmu pro silnice bez dopravn´ıho znaˇcen´ı (vod´ıc´ıho prouˇzku, stˇredov´e ˇc´ ary) a s ˇc´asteˇcnˇe poˇskozen´ ym povrchem vozovky. V tˇechto pˇr´ıpadech je segmentace hranovou detekc´ı nevhodn´a. Na obr´azku 5.3 jsou pˇrev´aˇznˇe obr´azky s kvalitn´ım povrchem vozovky a s dopravn´ım znaˇcen´ım. Tyto dopravn´ı sc´eny je moˇzn´e segmentovat i pomoc´ı metod uveden´ ych v kapitole 3.1. Na obr´azc´ıch 5.4 je zaznamen´ an pr˚ ujezd Prahou z Dejvic na Jiˇzn´ı Mˇesto. Na obr´azku 5.1 jsou pˇr´ıklady situac´ı, ve kter´ ych z´ona z´ajmu 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´eria pro stanoven´ı z´ony z´ajmu v obraze. Ve 2% pˇr´ıpad˚ u doch´ az´ı ˇspatn´emu v´ ysledku segmentace. Tyto pˇr´ıpady jsou identifikov´ any algoritmem IV a nen´ı pro nˇe z´ona z´ajmu stanovena.
Obr´ azek 5.1: Pˇr´ıklad sc´en, ve kter´ ych z´ona z´ajmu nebyla stanovena
48
Obr´ azek 5.2: V´ ysledky segmentace z´ony z´ajmu v obraze – neznaˇcen´e silnice
49
Obr´ azek 5.3: V´ ysledky segmentace z´ony z´ajmu v obraze – znaˇcen´e silnice
50
Obr´ azek 5.4: V´ ysledky segmentace z´ony z´ajmu v obraze – mˇesto
51
Obr´ azek 5.5: V´ ysledky segmentace z´ony z´ajmu 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´aˇstˇe pokud m´a b´ yt implementovan´e v re´aln´em ˇcase (kapitola 3). Algoritmy poˇc´ıtaˇcov´eho vidˇen´ı je moˇzn´e vyv´ıjet v r˚ uzn´ ych prostˇred´ıch. Pod operaˇcn´ım syst´emem MS Windows je velmi obl´ıben´ y syst´em Matlab a jeho rozˇs´ıˇren´ı – Image Processing Toolbox. V operaˇcn´ım syst´emu Linux existuje ekvivalentn´ı syst´em pro zpracov´an´ı sign´al˚ u a obrazu – Khoros. Jak Matlab tak i Khoros jsou interprety a tedy algoritmy v nich implementovan´e jsou pomal´e. Z tohoto d˚ uvodu nejsou vhodn´e pro v´ yvoj rozs´ahlejˇs´ıch aplikac´ı jako je syst´em rozpozn´an´ı a klasifikace dopravn´ıch znaˇcek. Naˇs´ım c´ılem je implementace syst´emu RS2 v re´aln´em ˇcase prostˇrednictv´ım sign´alov´eho procesoru TMS320C80. Tento procesor se programuje pˇrev´aˇznˇe v assembleru, pˇr´ıpadnˇe v jazyce C. Proto vˇsechny d´ılˇc´ı algoritmy byly programovan´e v jazyce C s t´ım, ˇze jejich implementace v prostˇred´ı digit´aln´ıho sign´alov´eho procesoru bude snaˇzˇs´ı. Pro v´ yvoj algoritm˚ u segmentace z´ony z´ajmu v obraze jsem se rozhodl vytvoˇrit samostatnou aplikaci – Zone, kter´a bude popsan´a na n´asleduj´ıc´ıch str´ank´ach.
6.1
Objektovˇ e orientovan´ y pˇ r´ıstup
Aplikace Zone byla naprogramov´ana pod operaˇcn´ım syst´emem MS Windows ve v´ yvojov´em 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´akladn´ı operace s obrazem, jako je nahr´av´ an´ı a ukl´ad´ an´ı obr´azk˚ u ve form´atech BMP, GIF, PNG, JPEG jsem zvolil 1 tˇr´ıdy z knihovny CImage , kterou vytvoˇril Julian Smart. Metody t´eto tˇr´ıdy mimo jin´e umoˇzn ˇuj´ı modifikovat vstupn´ı obraz na u ´rovni jednotliv´ ych pixel˚ u – pˇristupovat na dan´e souˇradnice v obraze, ˇc´ıst a mˇenit RGB hodnoty pixel˚ u atp. Pro vlastn´ı implementaci algoritm˚ u segmentace z´ony z´ajmu v obraze, popsan´ ych v t´eto pr´aci, jsem vytvoˇril n´asleduj´ıc´ı tˇr´ıdy: • CCVLib – metody t´eto tˇr´ıdy umoˇzn ˇuj´ı nahr´avat a ukl´adat obrazov´a data, pˇristupovat k metod´am segmentaˇcn´ıch algoritm˚ u, kter´e jsou implementovan´e v n´asleduj´ıc´ıch tˇr´ıd´ ach. Mezi atributy tˇr´ıdy CCVlib patˇr´ı pˇrev´aˇznˇe glob´aln´ı struktury pouˇz´ıvan´e v ostatn´ıch tˇr´ıd´ ach. • CHistogram – metody t´eto tˇr´ıdy ˇreˇs´ı problematiku implementace anal´ yzy histogramu. Souˇc´ ast´ı t´eto tˇr´ıdy je i algoritmus segmentace prahov´an´ı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´eto tˇr´ıdy implementuj´ı transformaci RGB barevn´eho modelu na model HSV a barevnou segmentaci nar˚ ust´an´ım oblasti, tak jak je popsan´a v t´eto pr´aci. • CArea – vlastn´ı v´ ypoˇcet polohy a velikosti z´ony z´ajmu na z´akladˇ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´emem MS Windows 95 nebo MS Windows NT 4.0. Program nepouˇz´ıv´ a registraˇcn´ı datab´aze uveden´ ych operaˇcn´ıch syst´emu, konfiguraˇcn´ı informace jsou zapisov´any do hlavn´ıho adres´aˇre disku C:.
Obr´ azek 6.1: Aplikace segmentace z´ony z´ajmu – Zone
Obrazovka programu Zone (obr´azek 6.1) se skl´ad´a z nˇekolika ˇc´ast´ı. Program je moˇzn´e ovl´ adat pomoc´ı rolovac´ıho menu nebo pomoc´ı n´astrojov´e liˇsty. Z´akladn´ı parametry segmentaˇcn´ıch algoritm˚ u se nastavuj´ı zmˇenamy konstant v ovl´adac´ım panelu (obr´ azek 6.2). Horn´ı polovina obrazovky je tvoˇrena datab´az´ı obr´azk˚ u se z´akladn´ımy 54
informacemi. Pouˇzit´ım prav´eho tlaˇc´ıtka myˇsi je moˇzn´e vyvolat ”pop-up” menu ve kter´em lze ke kaˇzd´emu obr´azku vytvoˇrit koment´aˇre a t´ım zlepˇsit orientaci v rozs´ahl´ ych datab´ az´ıch. Datab´aze umoˇzn ˇuje rychl´ y pˇr´ıstup ke vˇsem obr´azk˚ um, kter´e 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´an´ı 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´adˇeny d´ılˇc´ı informace o pr˚ ubˇehu segmentace a stanoven´ı vlastn´ı z´ony z´ajmu.
Obr´ azek 6.2: Ovl´adac´ı panel programu Zone
Ovl´ adac´ı panel slouˇz´ı k nastavov´an´ı parametr˚ u algoritm˚ u segmentace z´ony z´ajmu. Pod z´aloˇ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´aloˇzkou Prediction se nastavuj´ı parametry revize v´ ysledku segmentace a konstanty pouˇzit´e pro vlastn´ı stanoven´ı z´ony z´ajmu. Pod z´aloˇzkou Options je nutn´e nastavit cestu k obr´azk˚ um a k datab´azov´ ym dokument˚ um. Ovl´adac´ı panel se vyvol´av´a kliknut´ım na odpov´ıdaj´ıc´ı tlaˇc´ıtko n´astrojov´e liˇsty, pˇr´ıpadnˇe volbou v rolovac´ım menu.
55
Kapitola 7
Z´ avˇ er V t´eto diplomov´e pr´aci byl pops´an v´ yvoj metody identifikace z´ony z´ajmu v obraze. Z´ona z´ajmu je definov´ ana na z´akladˇe segmentace povrchu vozovky a geometrick´eho modelu silnice v dopravn´ı sc´enˇe. Ostatn´ı projekty, kter´e ˇreˇs´ı problematiku autonomn´ıch vozidel (kapitola 3.1) pˇristupuj´ı k rozpozn´an´ı silnice v obraze odliˇsnˇe. Informace o poloze silnice v obraze je z´ısk´ ana na z´akladˇe hranov´e detekce vod´ıc´ıho prouˇzku. T´ım se problematika zuˇzuje pouze na dobˇre znaˇcen´e 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´ych silniˇcn´ıch komunikac´ı, s t´ım, ˇze na povrch (texturu) vozovky nejsou kladeny ˇz´ adn´e speci´aln´ı poˇzadavky (kapitola 4.3). Vyvinut´e algoritmy jsou natolik obecn´e, ˇze je je moˇzn´e po drobn´ ych u ´prav´ach pouˇz´ıt i pro ˇreˇsen´ı dalˇs´ıch probl´em˚ u autonomn´ıch vozidel (navigace, steering, . . . ). Vˇsechny algoritmy, popsan´e v t´eto pr´aci jsou navrˇzen´e s ohledem na implementaci v re´aln´em ˇcase prostˇrednictv´ım sign´alov´eho procesoru firmy Texas Instruments TMS320C80. V´ ysledky prezentovan´e v kapitole 5.1 je moˇzn´e d´ale zlepˇsit pouˇzit´ım speci´aln´ıch senzor˚ u. Poˇcet chybn´ ych v´ ysledk˚ u algoritmu identifikace z´ony z´ajmu v obraze by bylo moˇzn´e sn´ıˇzit implementac´ı dalˇs´ıch metod, kter´e analyzuj´ı dopravn´ı sc´enu. Jedn´a se zejm´ena o rozpozn´an´ı kˇriˇzovatek a detekci pˇrek´aˇzek na silnici. I pˇres tato omezen´ı je popsan´a metoda dostateˇcnˇe robustn´ı a tedy vhodn´a pro identifikaci z´ony z´ajmu v obraze v syst´emu RS2 .
ˇ Z´avˇerem bych chtˇel podˇekovat vˇsem profesor˚ um CVUT, vedouc´ımu diplomov´e pr´ace Ing. Pavlu Zahradn´ıkovi za cenn´e 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´e Montpellier II/CNRS, Internal Report [2] Nov´ ak M., Faber J., Kufudaki O.: Neuronov´e s´ıtˇe a informaˇcn´ı syst´emy ˇziv´ych organism˚ u, Grada, Praha 1993 ˇ [3] Hlav´ aˇc V., Sonka M.: Poˇc´ıtaˇcov´e 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¨at, 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´e skripˇ tum, CVUT, Praha, 1993 [12] Zikmund T.: Identifikace geometrick´ych tvar˚ u v obraze, Diplomov´a pr´ace, 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´aˇr SNTL, Praha 1990 [26] L´ıbal V., Zikmund T., Pacl´ık P., Kr´al´ık M., Kov´aˇ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´yvojov´eho prostˇred´ı MS Visual C++, 1994-98 [33] Microsoft: Microsoft Developer Network, CD-ROM, 1997 [34] Dokumentace operaˇcn´ıho syst´emu Linux a DTP syst´emu teTEX
58