Automatická tvorba her typu puzzle na dotykovém zařízení s OS Android
Diplomová práce
Studijní program: Otevřená informatika (magisterský) Studijní obor: Počítačové vidění a digitální obraz Vedoucí práce: RNDr. Daniel Průša, Ph.D.
Bc. Václav Pruner
Praha 2015
Katedra kybernetiky
Katedra kybernetiky
ZADÁNÍ DIPLOMOVÉ PRÁCE
Student: Bc. Václav P r u n e r
Studijní program: Otevřená informatika (magisterský) Obor: Počítačové vidění a digitální obraz
Název tématu: Automatická tvorba her typu puzzle na dotykovém zařízení s OS Android
Pokyny pro vypracování:
Cílem práce je navrhnout aplikaci pro dotykové zařízení s OS Android, která bude
podporovat sestavování skládačky z dílků. Návrh konkrétní podoby skládačky je součástí práce. Kritériem je pouze zábavnost hry, nemusí se jednat o žádnou z tradičních variant.
Jako cílová skupina se předpokládá dítě ve věku 3-6 let. Významnou funkcionalitou bude automatická tvorba zadání podle zvoleného obrázku/fotografie. Na základě segmentace obrazu a dalšího zpracování budou detekovány signifikantní objekty, od kterých se bude odvíjet rozložení na dílky. Implementaci segmentace provede autor vlastní.
Úspěšnost a spolehlivost generování zadání bude analyzována pro různé typy vstupů.
Kromě implementace bude vytvořena uživatelská příručka a programátorská dokumentace.
Seznam odborné literatury:
[1] Šonka M., Hlaváč V., Boyle R.: Image Processing, Analysis and Machine vision, 3rd edition, Thomson Learning, Toronto, Canada, 2007.
[2] Nudelman G.: Android Design Patterns, 1st edition, Wiley, Indianapolis, USA, 2013.
Vedoucí diplomové práce: RNDr. Daniel Průša, Ph.D.
Platnost zadání: do konce letního semestru 2015/2016
L.S.
doc. Dr. Ing. Jan Kybic vedoucí katedry
prof. Ing. Pavel Ripka, CSc.
děkan V Praze dne 21. 1. 2015
Na tomto m´ıstˇe bych chtˇel podˇekovat panu RNDr. Danielu Pr˚uˇsovi, Ph.D. za vˇecn´e pˇripom´ınky a odborn´y dohled nad touto prac´ı. D´ale bych chtˇel podˇekovat rodinˇe za podporu bˇehem cel´eho studia.
Prohl´ aˇ sen´ı autora pr´ ace
Prohlaˇsuji, ˇze jsem pˇredloˇzenou pr´aci vypracoval samostatnˇe a ˇze jsem uvedl veˇsker´e pouˇzit´e informaˇcn´ı zdroje v souladu s Metodick´ym pokynem o dodrˇzov´an´ı etick´ych princip˚u pˇri pˇr´ıpravˇe vysokoˇskolsk´ych z´avˇereˇcn´ych prac´ı.
V Praze dne . . . . Podpis autora pr´ace
C´ılem t´eto pr´ace je vyvinut´ı aplikace pro zaˇr´ızen´ı s operaˇcn´ım syst´emem An- droid, kter´a automaticky vytvoˇr´ı hru typu puzzle pro libovoln´y vstupn´ı obr´azek.
Jednotliv´e d´ılky skl´adanky by mˇely reflektovat objekty v pˇr´ısluˇsn´em vstupu.
Automatick´a tvorba je zaloˇzena na segmentaci obrazu a kompaktnosti geome- trick´ych ´utvar˚u. C´ılovou skupinou jsou dˇeti pˇribliˇznˇe ve vˇeku od tˇr´ı do ˇsesti let.
Kl´ıˇ cov´ a slova
segmentace obrazu, kompaktnost geometrick´ych ´utvar˚u, Android
Abstract
The goal of this thesis is to develop an application for devices with Android operating system, which automatically creates a puzzle game for arbitrary input image. Every piece of the puzzle should reflect objects in its respective input. Automatic creation is based on image segmentation and compactness of geometric shapes. The target group are children from about three to six years old.
Keywords
image segmentation, geometric shape compactness, Android
1 Uvod´ 11
2 Souˇcasn´y stav 13
3 Algoritmus 15
3.1 Pˇredzpracov´an´ı obrazu . . . 15
3.1.1 Interpolace pomoc´ı nejbliˇzˇs´ıho souseda . . . 17
3.1.2 Biline´arn´ı interpolace . . . 17
3.1.3 Bikubick´a interpolace . . . 18
3.1.4 Porovn´an´ı metod . . . 19
3.2 Segmentace . . . 20
3.2.1 Zvaˇzovan´e metody . . . 22
3.2.2 Barevn´y model HSV . . . 23
3.2.3 Algoritmus zdol´av´an´ı kopc˚u (Hill-Climbing) . . . 24
3.3 Prvn´ı dˇelen´ı na z´akladˇe velikosti . . . 26
3.4 Prostorov´e oddˇelen´ı segment˚u a druh´e dˇelen´ı na z´akladˇe velikosti 27 3.5 Krit´erium pro vyb´ır´an´ı segment˚u . . . 31
3.5.1 V´ypoˇcet kompaktnosti geometrick´eho tvaru . . . 31
3.5.2 V´ypoˇcet IP Q indexu . . . 33
3.6 Operace ovlivˇnuj´ıc´ıIP Qindex . . . 37
3.6.1 Matematick´a morfologie . . . 37
3.6.2 Zaplˇnov´an´ı velk´ych dˇer . . . 40
3.6.3 V´ysledky operac´ı . . . 42
3.7 Vyb´ır´an´ı segment˚u podle IP Qindexu . . . 42
3.7.1 V´ybˇer kompaktn´ıch segment˚u - 1. pr˚uchod . . . 42
3.7.2 Rozdˇelen´ı pˇr´ıliˇs velk´ych segment˚u . . . 45
3.7.3 V´ybˇer kompaktn´ıch segment˚u - 2. pr˚uchod . . . 46
3.8 Tvorba dodateˇcn´ych segment˚u . . . 46
3.9 Fin´aln´ı ´uprava segment˚u . . . 48
3.10 Rozmaz´an´ı vyseparovan´ych ˇc´ast´ı ve vstupn´ım obr´azku . . . 49
4.1 Struktura aplikace . . . 55
4.2 Funkˇcn´ı vlastnosti aplikace . . . 57
4.2.1 Skl´ad´an´ı skl´adanky . . . 57
4.2.2 Zpracov´an´ı obr´azku . . . 58
4.2.3 V´ybˇer vstupn´ıho obr´azku . . . 59
4.2.4 Uloˇzen´ı skl´adanky . . . 59
4.2.5 Naˇcten´ı uloˇzen´e skl´adanky . . . 60
5 Testov´an´ı 63 5.1 Okolnosti ovlivˇnuj´ıc´ı segmentaci obrazu . . . 63
5.2 Testov´an´ı s uˇzivateli . . . 66
6 Z´avˇer 67
Literatura 69
A Ovl´ad´an´ı aplikace 73
B Seznam pouˇzit´ych zkratek 77
C Obsah pˇriloˇzen´eho DVD 79
1 Animal Jigsaw Puzzles For Kids . . . 13
2 Toddlers Puzzle Woozzle . . . 14
3 V´yvojov´y diagram algoritmu . . . 16
4 Vliv pˇridˇelen´eho poˇctu pixel˚u na zachov´an´ı tvar˚u v obraze . . 16
5 Biline´arn´ı interpolace - hodnota nov´eho pixelu . . . 17
6 Bikubick´a interpolace - hodnota nov´eho pixelu . . . 18
7 Interpolaˇcn´ı j´adra . . . 19
8 Porovn´an´ı interpolaˇcn´ıch metod . . . 21
9 Barevn´y model HSV . . . 23
10 Zn´azornˇen´ı indexace pixel˚u (obr´azek o rozmˇerech 4x3) . . . . 24
11 Hill-Climbing algoritmus . . . 26
12 Prvn´ı dˇelen´ı na z´akladˇe velikosti . . . 27
13 Prostorovˇe neoddˇelen´e segmenty . . . 27
14 Okol´ı pixelu (o) pouˇzit´e pˇri prostorov´em dˇelen´ı . . . 28
15 Pˇr´ıklad oddˇelovan´eho segmentu . . . 29
16 Hodnoty matice rastr po tˇrech kroc´ıch algoritmu . . . 29
17 Koneˇcn´e hodnoty matice rastr . . . 29
18 Freeman˚uv ˇretˇezov´y k´od . . . 34
19 Pˇr´ıklad popisu hranice objektu . . . 34
20 Pˇr´ıklad segmentu . . . 35
21 Porovn´an´ı metod na mˇeˇren´ı obvodu . . . 36
22 Pˇr´ıklad segmentu jako bin´arn´ıho obrazu . . . 37
23 Nejˇcastˇeji pouˇz´ıvan´e strukturn´ı elementy . . . 38
24 Posunut´ı o radiusvektor . . . 38
25 Transpozice . . . 38
26 Bin´arn´ı dilatace . . . 39
27 Bin´arn´ı eroze . . . 39
28 Pouˇzit´y strukturn´ı element B . . . 40
29 V´yvojov´y diagram vyplˇnov´an´ı segment˚u . . . 40
30 Zmˇena indexu v z´avislosti na hodnotˇe ˇretˇezov´eho k´odu . . . . 41
31 Zlepˇsov´an´ı vlastnost´ı segmentu. . . 43
33 Neˇz´adouc´ı efekt dˇelen´ı velk´ych segment˚u. . . 45
34 V´yvojov´y diagram tvorby dodateˇcn´ych segment˚u . . . 47
35 Pˇr´ıklad segmentu jako bin´arn´ıho obrazu . . . 49
36 Rozmaz´an´ı vyseparovan´ych ˇc´ast´ı ve vstupn´ım obr´azku . . . . 51
37 Pod´ıl operaˇcn´ıch syst´em˚u na trhu v roce 2014 . . . 53
38 Srovn´an´ı zastoupen´ı verz´ı OS Android v listopadu 2014 a dubnu 2015 . . . 54
39 Hlavn´ı aktivitaMainActivity . . . 55
40 Ostatn´ı aktivity . . . 56
41 Diagram uˇzit´ı . . . 57
42 Sekvenˇcn´ı diagram zpracov´an´ı obr´azku . . . 58
43 Sekvenˇcn´ı diagram v´ybˇeru obr´azku . . . 59
44 Sekvenˇcn´ı diagram uloˇzen´ı skl´adanky . . . 59
45 Sekvenˇcn´ı diagram naˇcten´ı uloˇzen´e skl´adanky . . . 61
46 Prototypy vstupn´ıch obr´azk˚u . . . 63
47 Porovn´an´ı segmentace pro r˚uzn´e vstupn´ı form´aty . . . 64
48 Rozliˇsov´an´ı odst´ın˚u pˇri segmentaci . . . 65
49 Hodnocen´ı uˇzivatel˚u . . . 66
50 V´ychoz´ı obrazovka . . . 73
51 Ovl´ad´an´ı aplikace . . . 73
52 Pr˚ubˇeh zpracov´an´ı . . . 74
53 Potvrzen´ı uloˇzen´ı . . . 74
54 Dlaˇzdicov´a galerie pro naˇc´ıt´an´ı . . . 75
55 Obsah pˇriloˇzen´eho DVD . . . 79
Kapitola 1 Uvod ´
Chytr´e telefony a tablety si v souˇcasn´e dobˇe uˇz´ıvaj´ı znaˇcn´e popularity, kter´a, jak se zd´a, bude d´ale jen r˚ust. S t´ım je spojen i vzr˚ustaj´ıc´ı z´ajem o v´yvoj aplikac´ı pro tato zaˇr´ızen´ı, kter´y byl i pohnutkou pro v´ybˇer t´ematu - apli- kov´an´ı velmi ˇcasto v´ypoˇcetnˇe n´aroˇcn´ych metod poˇc´ıtaˇcov´eho vidˇen´ı na mo- biln´ıch zaˇr´ızen´ıch, kter´a maj´ı menˇs´ı v´ypoˇcetn´ı v´ykon a pamˇet’ov´e moˇznosti neˇz poˇc´ıtaˇce.
C´ılem pr´ace bylo navrhnout aplikaci pro zaˇr´ızen´ı s operaˇcn´ım syst´emem An- droid, kter´a pro libovoln´y vstupn´ı obr´azek vytvoˇr´ı hru typu puzzle; c´ılovou skupinou jsou dˇeti ve vˇeku od tˇr´ı do ˇsesti let. Jednotliv´e d´ılky, nalezen´e ve vstupu metodami poˇc´ıtaˇcov´eho vidˇen´ı, by mˇely reflektovat koherentn´ı objekty v obraze. Kompletn´ı seznam z´akladn´ıch poˇzadavk˚u na vyv´ıjenou aplikaci je n´asleduj´ıc´ı:
• Uˇzivatel m´a moˇznost vybrat libovoln´y vstupn´ı obr´azek
• Uˇzivatel m´a moˇznost uloˇzit st´avaj´ıc´ı skl´adanku
• Uˇzivatel m´a moˇznost naˇc´ıst dˇr´ıve uloˇzenou skl´adanku Vlastn´ı hran´ı hry prob´ıh´a
”vlepov´an´ım“ vytvoˇren´ych d´ılk˚u zpˇet do p˚uvodn´ıho obr´azku operac´ı
”uchopit a t´ahnout“ (
”Drag & Drop“). Pˇri v´yvoji byl kladen d˚uraz zejm´ena na n´avrh algoritmu, kter´y v´yslednou skl´adanku vytvoˇr´ı.
Kapitola 2
Souˇ casn´ y stav
Aplikace pro operaˇcn´ı syst´em Android jsou distribuovan´e sluˇzbou Google Play[1], konkr´etnˇe jej´ı sekc´ı Google Play Store (existuj´ı jeˇstˇe sekce Google Play Music pro distribuci hudby, Google Play Movies & TV pro distribuci vide´ı a Goo- gle Play Books pro distribuci elektronick´ych knih[2]). Sluˇzba Google Play je dostupn´a z kaˇzd´eho zaˇr´ızen´ı vybaven´eho operaˇcn´ım syst´emem Android.
Google Play obsahuje velk´e mnoˇzstv´ı her typu puzzle pro dˇeti, kter´e jsou ovˇsem pouze variacemi na dvˇe varianty. Prvn´ı variantou jsou aplikace na z´akladˇe kla- sick´ych fyzick´ych puzzl˚u, jedn´a se tedy o pouh´e rozˇrez´an´ı obr´azku. Pˇr´ıkladem m˚uˇze b´yt aplikace Animal Jigsaw Puzzles For Kids[3], viz Obr.1.
Obr. 1Animal Jigsaw Puzzles For Kids
Druh´a varianta se principi´alnˇe pˇribliˇzuje poˇzadavk˚um na zad´an´ı t´eto pr´ace - jedn´a se o
”vlepov´an´ı“ vyˇr´ızl´ych objekt˚u zpˇet do p˚uvodn´ıho obr´azku, tvorba v´yˇrez˚u ovˇsem neprob´ıh´a automaticky a dvojice obr´azek - v´yˇrezy jsou dod´any v´yvoj´aˇrem aplikace.
Obr. 2Toddlers Puzzle Woozzle
Z´astupcem tohoto typu skl´adanek je napˇr´ıklad hra Toddlers Puzzle Woozzle[4], viz Obr.2.
Aplikace, kter´a byla vyv´ıjena jako c´ıl t´eto pr´ace, tedy nem´a v distribuˇcn´ı sluˇzbˇe Google Play zastoupen´ı.
Kapitola 3 Algoritmus
Vstupem pouˇzit´eho algoritmu (viz. v´yvojov´y diagram Obr.3) je vybran´y obr´azek, pˇresnˇeji pole s RGB hodnotami jeho pixel˚u. V´ystupem jsou indexy vyseparo- van´ych obrazc˚u (kaˇzd´y obrazec m´a seznam index˚u sv´ych pixel˚u) a obr´azek, kter´y je na vyseparovan´ych pozic´ıch rozmaz´an (opˇet jde tedy o pole s RGB hodnotami jeho pixel˚u).
Vstupn´ı obr´azek je nejprve zmenˇsen kv˚uli urychlen´ı v´ypoˇcetn´ıch ˇcas˚u, pot´e je provedena segmentace a prostorov´e oddˇelen´ı vzniknuvˇs´ıch segment˚u. U seg- ment˚u spr´avn´e velikosti (tzn. ani pˇr´ıliˇs mal´ych ani pˇr´ıliˇs velk´ych) je pot´e po- rovn´ana jejich kompaktnost s pˇredem stanoven´ym kompaktnostn´ım prahem.
Pˇrijat´e segmenty jsou nakonec zvˇetˇseny zp´atky na p˚uvodn´ı velikost vstupn´ıho obr´azku, kter´y je na jejich pozic´ıch rozmaz´an.
3.1 Pˇ redzpracov´ an´ı obrazu
Aby algoritmus pracoval v pˇrijateln´ych ˇcasov´ych relac´ıch je tˇreba vstupn´ı ob- raz nejprve zmenˇsit. Na jeden sn´ımek je alokov´ano pˇribliˇznˇe 250 tis´ıc pixel˚u.
Obraz s pomˇerem stran 4:3 bude m´ıt po takov´emto zmenˇsen´ı rozmˇery pˇribliˇznˇe 580px x 430px, obraz s pomˇerem stran 16:9 pˇribliˇznˇe 680px x 380px a obraz s pomˇerem stran 16:10 pˇribliˇznˇe 640px x 400px.
Alokov´an´ı menˇs´ıho poˇctu pixel˚u vede sice k rychlejˇs´ım v´ypoˇcetn´ım ˇcas˚um, doch´az´ı nicm´enˇe ke zkreslen´ı objekt˚u ve sc´enˇe (zejm´ena jejich hranic), viz.
Obr.4. Analogicky vˇetˇs´ı poˇcet pixel˚u vede k delˇs´ımu trv´an´ı v´ypoˇctu a k lepˇs´ımu zachov´an´ı tvar˚u.
Jako algoritmy ke zmenˇsen´ı velikosti obrazu byly zvaˇzov´any interpolace pomoc´ı nejbliˇzˇs´ıho souseda, biline´arn´ı interpolace a bikubick´a interpolace.
Pˇred- zpracov´an´ı
obrazu
Segmentace Prvn´ı dˇelˇen´ı podle velikosti
Prostorov´e oddˇelen´ı segment˚u
Druh´e dˇelen´ı podle velikosti
Aplikace bin´arn´ı morfologie a vyplnˇen´ı segment˚u
V´ybˇer kom- paktn´ıch segment˚u -
1.pr˚uchod
Rozdˇelen´ı velk´ych segment˚u
V´ybˇer kom- paktn´ıch segment˚u -
2.pr˚uchod
Tvorba do- dateˇcn´ych
segment˚u
Fin´aln´ı ´uprava segment˚u
Rozmaz´an´ı vyseparo- van´ych ˇc´ast´ı
Obr. 3V´yvojov´y diagram algoritmu
(a) rozmˇery 633px x 475px (b) rozmˇery 200px x 150px Obr. 4Vliv pˇridˇelen´eho poˇctu pixel˚u na zachov´an´ı tvar˚u v obraze
3.1.1 Interpolace pomoc´ı nejbliˇ zˇ s´ıho souseda
Jak jiˇz n´azev napov´ıd´a, interpolace pomoc´ı nejbliˇzˇs´ıho souseda (Nearest nei- ghbour interpolation)[5][7] pˇriˇrad´ı na interpolovanou pozici hodnotu intenzity nejbliˇzˇs´ıho pixelu. Nev´yhoda, t´eto jinak pˇr´ımoˇcar´e metody, je tvorba
”schod˚u“
u objekt˚u s ostr´ymi hranicemi (patrnˇejˇs´ı u zvˇetˇsov´an´ı obrazu).
3.1.2 Biline´ arn´ı interpolace
Biline´arn´ı interpolace (Bilinear interpolation)[5][6] pˇredpokl´ad´a, ˇze funkce in- tenzity je line´arn´ı ve sv´em okol´ı a hodnotu intenzity interpolovan´eho pixelu poˇc´ıt´a jako v´aˇzen´y pr˚umˇer ˇctyˇrech okoln´ıch pixel˚u z p˚uvodn´ıho obrazu.
Konkr´etnˇe je hodnota intenzity interpolovan´eho pixelu J(r0, c0) vypoˇc´ıt´ana podle vzorce
J(r0, c0) =I(r, c)·(1− 4r)·(1− 4c) +I(r+ 1, c)· 4r·(1− 4c) +I(r, c+ 1)·(1− 4r)· 4c +I(r+ 1, c+ 1)· 4r· 4c
kde I(x,y) ud´av´a hodnotu intenzity p˚uvodn´ıho pixelu na souˇradnic´ıch (x, y), v´yznam ostatn´ıch promˇenn´ych je patrn´y z Obr.5. Biline´arn´ı interpolace m˚uˇze
Obr. 5Biline´arn´ı interpolace - hodnota nov´eho pixelu
d´ıky povaze pr˚umˇerov´an´ı zp˚usobit rozmaz´an´ı, redukuje efekt ”schod˚u”pˇredsta- ven´y u interpolace pomoc´ı nejbliˇzˇs´ıho souseda.
3.1.3 Bikubick´ a interpolace
Bikubick´a interpolace[5][7][8] jeˇstˇe d´ale zpˇresˇnuje hodnotu intenzity interpolo- van´eho pixelu t´ım, ˇze bere v ´uvahu ˇsestn´act sousedn´ıch pixel˚u z p˚uvodn´ıho ob- razu (viz. Obr.6). Obecnˇe se hodnota intenzity interpolovan´eho pixeluJ(r’,c’) vypoˇcte podle vzorce
J(r0, c0) =
2
X
m=−1 2
X
n=−1
I(r+m, c+n)·Rc(m− 4r)·Rc(4c−n)
Obdobnˇe jako u biline´arn´ı interpolace ud´av´a I(x,y) hodnotu intenzity pixelu na souˇradnic´ıch (x,y) v p˚uvodn´ım obrazu, v´yznam 4r a 4cje moˇzno odeˇc´ıst z Obr.6; funkce Rc (interpolaˇcn´ı funkce ˇci interpolaˇcn´ı j´adro) ud´av´a v´ahy in- tenzit kaˇzd´eho z ˇsestn´acti sousedn´ıch pixel˚u p˚uvodn´ıho obrazu ve v´ysledn´e sumˇe, z ˇcehoˇz plyne, ˇze volbou vhodn´e funkce Rc lze vyj´adˇrit i biline´arn´ı in- terpolaci a interpolaci pomoc´ı nejbliˇzˇs´ıho souseda.
Obr. 6Bikubick´a interpolace - hodnota nov´eho pixelu
Jednou z ˇcasto pouˇz´ıvan´ych funkc´ı je funkce typu Bell[7][8], viz. Obr.7(a) (i kdyˇz se v prav´em slova smyslu nejedn´a o bikubickou interpolaci, jelikoˇz
pˇredpis neobsahuje ˇz´adnou mocninu tˇr´ı)
Rc(x) =
1
2 x+3 2
!2
−3
2≤x≤ −1 2 3
4−x2 −1
2≤x≤ 1 2 1
2 x− 3 2
!2
1
2≤x≤ −3 2
0 jinak
Dalˇs´ı ˇcasto pouˇz´ıvan´ym j´adrem je J´adro CatMull-Rom[7][9], viz. Obr.7(b)
Rc(x) =
9|x|3−15|x|2+ 6 |x|<1
−3|x|3+ 15|x|2−24|x|+ 12 1≤ |x|<2
0 jinak
Bikubick´a interpolace se dok´aˇze vypoˇr´adat s efektem ”schod˚u”interpolace
(a) Bell (b) CatMull-Rom
Obr. 7Interpolaˇcn´ı j´adra
pomoc´ı nejbliˇzˇs´ıho souseda a potlaˇcuje i rozmaz´an´ı pˇr´ıtomn´e u biline´arn´ı in- terpolace. Na prvn´ı pohled je vˇsak patrn´e, ˇze je ˇcasovˇe n´aroˇcnˇejˇs´ı neˇz pˇredeˇsl´e dva zp˚usoby.
3.1.4 Porovn´ an´ı metod
Porovn´an´ı v´yˇse zm´ınˇen´ych ˇctyˇrech metod je demonstrov´ano na Obr.8. P˚uvodn´ı obr´azek Obr.8(a) o velikosti 3392px x 3328px byl zmenˇsen pomoc´ı kaˇzd´e z v´yˇse zm´ınˇen´ych metod na rozmˇery 500px x 428px. Na sn´ımc´ıch Obr.8(b) aˇz Obr.8(e) je detail (zv´yraznˇen´y zelen´ym obd´eln´ıkem na Obr.8(a)) kaˇzd´e t´eto zmenˇseniny.
Je vidˇet, ˇze s pokroˇcilejˇs´ı metodou doch´az´ı k postupn´emu zlepˇsov´an´ı ´urovnˇe
interpolovan´eho obrazu, zejm´ena na hranici objektu.
Pˇrestoˇze bikubick´a interpolace produkuje z pohledu lidsk´eho vn´ım´an´ı obrazu nejlepˇs´ı v´ysledky, byla jako metoda pro pˇredzpracov´an´ı (pˇresnˇeji zmenˇsen´ı) obrazu zvolena biline´arn´ı interpolace. Jev´ı se totiˇz jako vhodn´y kompromis mezi rychlost´ı a v´ykonem. Nav´ıc u zmenˇsov´an´ı obrazu nejsou nedostatky tolik patrn´e (Obr.5 z´amˇernˇe zveliˇcuje tyto nedostatky pˇribl´ıˇzen´ım ˇc´asti zmenˇsen´eho sn´ımku).
3.2 Segmentace
Segmentace obrazu[5] obn´aˇs´ı rozdˇelen´ı obrazu na oblasti, kter´e silnˇe koreluj´ı s re´aln´ymi objekty ˇci oblastmi obsaˇzen´ymi v obraze. Nejˇcastˇeji se jako roz- hoduj´ıc´ı atribut pouˇz´ıv´a hodnota intenzity pro jednobarevn´e obrazy a jednot- liv´e komponenty barev (napˇr. kaˇzd´y z kan´al˚u RGB barevn´eho sch´ematu) pro v´ıcebarevn´e obrazy[8].
Neexistuje ˇz´adn´a ucelen´a teorie o segmentaci obrazu[8], n´asledkem ˇcehoˇz ne- vznikla pouze jedin´a univerz´aln´ı metoda pro tento probl´em. Existuje vˇetˇs´ı mnoˇzstv´ı metod, kter´e vznikly jako ˇreˇsen´ı urˇcit´eho probl´emu a postupnˇe z´ıskaly na popularitˇe. Protoˇze existuje velk´e mnoˇzstv´ı segmentaˇcn´ıch metod, je tˇreba nˇejak hodnotit jejich v´ysledky. Haralick a Shapiro[10] stanovili, ˇze segmenty by mˇely splˇnovat n´asleduj´ıc´ı vlastnosti
• Oblasti segment˚u by mˇely b´yt uniformn´ı a homogenn´ı
• Vnitˇrky segment˚u by nemˇely obsahovat mnoho mal´ych dˇer
• Hranice kaˇzd´eho segmentu by mˇely b´yt jednoduch´e, prostorovˇe pˇresn´e a pokud moˇzno nepˇr´ıliˇs ˇclenit´e
• Sousedn´ı segmenty by mˇely b´yt co nejv´ıce rozd´ıln´e (s ohledem na seg- mentaˇcn´ı atribut, podle kter´eho je oblast segmentu uniformn´ı)
Jeden ze zp˚usob˚u jak hodnotit segmentaˇcn´ı metody pˇredpokl´ad´a, ˇze spr´avn´a segmentace je zn´ama pˇredem. V´ysledky mˇeˇren´e metody jsou potom porovn´av´any s touto ”ground truth”. Tento postup je vˇsak velmi pracn´y[5] a nav´ıc pro vze- vrubn´e posouzen´ı metody, je tˇreba m´ıt objemnou datab´azi takov´ychto obraz˚u (nejzn´amˇejˇs´ı je nejsp´ıˇse The Berkeley Segmentation Dataset [11]).
Dalˇs´ım ze zp˚usob˚u je hodnocen´ı bez dohledu (unsupervised evaluation), kter´y je ovˇsem zpravidla testov´an na syntetick´ych datasetech a na vlastnosti ob- raz˚u zav´ad´ı restrikce, kter´e ˇcasto nemohou b´yt pouˇzit´e v aplikac´ıch z re´aln´eho svˇeta.[5]
(a) P˚uvodn´ı obraz
(b) Nejbliˇzˇs´ı soused (c) Biline´arn´ı int.
(d) Bell (e) Catmul-Rom
Obr. 8Porovn´an´ı interpolaˇcn´ıch metod
Moment´alnˇe vˇsak neexistuje ˇz´adn´y konsensus o tom, jak tyto metody hodnotit.
Pro praktick´e pouˇzit´ı se zpravidla zodpov´ıdaj´ı tˇri ot´azky[5]
1. Jak ˇcasto metoda selˇze (tzn. metoda ned´a rozumn´y v´ysledek) 2. Jak pˇresn´a metoda je
3. Do jak´e m´ıry je metoda reprodukovateln´a na ´uspˇeˇsn´ych pˇr´ıpadech
3.2.1 Zvaˇ zovan´ e metody
Jak jiˇz bylo zm´ınˇeno v´yˇse, existuje nepˇrebern´e mnoˇzstv´ı metod, kter´e dok´aˇz´ı obraz segmentovat. Prvn´ım zvaˇzovan´ym algoritmem byla, na z´akladˇe doporuˇcen´ı vedouc´ıho pr´ace, segmentace s vyuˇzit´ım hled´an´ı minim´aln´ıho ˇrezu (maxim´aln´ıho tok) grafu - GrabCut[12]. Tato metoda je inicializov´ana nalezen´ım bod˚u n´aleˇz´ıc´ıch pozad´ı a popˇred´ı, kter´e slouˇz´ı jako pevn´e omezen´ı (hard constraint); dodateˇcn´a flexibiln´ı omezen´ı (soft constraints) mohou b´yt zavedena, aby reflektovala in- formaci o oblastech nebo hranic´ıch objekt˚u. Vzhledem k tomu, ˇze tato metoda segmentuje obraz pouze na pozad´ı a popˇred´ı a ˇze poˇzadovan´y algoritmus by mˇel b´yt plnˇe automatick´y, byla nakonec segmentace s vyuˇzit´ım hled´an´ı mi- nim´aln´ıho ˇrezu grafu zam´ıtnuta.
Dalˇs´ım zvaˇzovan´ym algoritmem bylo velmi rozˇs´ıˇren´e shlukov´an´ı pomoc´ı k- means[5], kter´e lze popsat n´asledovnˇe
1. V obrazu je vybr´ano (v nejprimitivnˇejˇs´ı verzi n´ahodnˇe) k bod˚u - cen- troid˚u
2. Kaˇzd´y bod obrazu je pˇriˇrazen ke sv´emu nejbliˇzˇs´ımu stˇredu (nejbliˇzˇs´ımu ve smyslu zvolen´e metriky, ˇcasto pouˇz´ıvanou je euklidovsk´a vzd´alenost) 3. Pro kaˇzd´y takto vznikl´y shluk je pr˚umˇerov´an´ım vypoˇcten nov´y centroid
a shlukov´an´ı zaˇc´ına od 1. kroku
K-means iteruje dokud nedojde ke zmˇenˇe ˇz´adn´eho shluku (ide´aln´ı pˇr´ıpad) nebo dokud nen´ı pˇrekroˇcen poˇcet pˇredem dan´ych iterac´ı. ´Uskal´ım t´eto metody je volba parametru k, kter´y ud´av´a celkov´y poˇcet shluk˚u. Existuj´ı sice metody na automatick´e zjiˇstˇen´ık (napˇr´ıklad pomoc´ı detekce hran [13] nebo porovn´an´ım segment˚u pro r˚uzn´a k[14]), zav´adˇej´ı ovˇsem dalˇs´ı vrstvu komplexity do cel´eho algoritmu. Nav´ıc k-means velmi ˇcasto konverguj´ı k lok´aln´ımu optimu, ˇc´ımˇz doch´az´ı ke ztr´atˇe poˇctu segment˚u a nepˇresnostem v segmentaci.
Nakonec byl zvolen algoritmus zdol´av´an´ı kopc˚u (Hill-Climbing), kter´y dos´ahne segmentace hled´an´ım lok´aln´ıch maxim v trojrozmˇern´em histogramu[15].
3.2.2 Barevn´ y model HSV
Dobr´y barevn´y model pro segmentaci obrazu by mˇel splˇnovat vlastnost, ˇze vn´ıman´a rozd´ılnost barev odpov´ıd´a jejich euklidovsk´e vzd´alenosti v tomto modelu. HSV barevn´y model tuto vlastnost splˇnuje a nav´ıc velmi dobˇre od- pov´ıd´a lidsk´emu vn´ım´an´ı barev[15]. Barevn´y model HSV je podobnˇe jako RGB tˇr´ısloˇzkov´y - H (hue) je odst´ın barvy, S (satruation) sytost barvy a V (value) pˇredstavuje jas v porovn´an´ı s b´ılou barvou.
Obr. 9Barevn´y model HSV
Na Obr.9[15] je barevn´y HSV model zn´azornˇen´y - H jako hodnota na barevn´em kotouˇci, S urˇcuje pozici na kotouˇci od stˇredu a V je pozice barevn´eho kotouˇce na ose ˇcern´a-b´ıl´a.
RGB hodnoty se na HSV pˇrevedou podle n´asledn´ych vztah˚u[16]
R0 = R
255, G0 = G
255, B0 = B 255 Cmax = max{R0, G0, B0}
Cmin = min{R0, G0, B0} 4=Cmax−Cmin
H =
0 4= 0
60 G0 −B0
4 mod 6
!
Cmax=R0
60 B0−R0 4 + 2
!
Cmax=G0 60 R0−G0
4 + 4
!
Cmax=B0
S =
0 Cmax = 0
4
Cmax Cmax 6= 0 V =Cmax
3.2.3 Algoritmus zdol´ av´ an´ı kopc˚ u (Hill-Climbing)
Vstupem zvolen´eho segmentaˇcn´ıho algortimu[15] je pole s RGB hodnotami pixel˚u zpracov´avan´eho obrazu, kde poˇrad´ı v poli odpov´ıd´a um´ıstˇen´ı pixelu v obraze (viz. Obr.10). V´ystupem je pole clusters stejn´e velikosti jako vstup, kter´e obsahuje rozˇrazen´ı pixel˚u do segment˚u -clusters(i) =j znamen´a, ˇzei-t´y pixel n´aleˇz´ıj-t´emu shluku.
0 1 2 3
4 5 6 7
8 9 10 11
Obr. 10 Zn´azornˇen´ı indexace pixel˚u (obr´azek o rozmˇerech 4x3)
RGB hodnoty jsou pˇrevedeny do HSV a upraveny tak, aby nejmenˇs´ı hodnota kaˇzd´e sloˇzky byla 0 a nejvˇetˇs´ı hodnota kaˇzd´e sloˇzky 1 (tedy nafitov´an´ı do inter- valu h0,1i) a pot´e je pomoc´ı Hill-Climbing algoritmu proveden´a segmentace.
Jednorozmˇern´y Hill-Climbing algoritmus pro H sloˇzku vypad´a n´asledovnˇe.
1. Vytvoˇren´ı jednorozmˇern´eho barevn´eho histogramu.
2. Zdol´av´an´ı kopce - zaˇc´ın´a se na libovoln´em nenulov´em binu (tj. datov´em intervalu) a podle n´asleduj´ıc´ıch pravidel, se hled´a vrchol (kopec), tj.
lok´aln´ı maximum v histogramu
(a) Porovn´an´ı poˇctu pixel˚u aktu´aln´ıho binu s jeho lev´ym a prav´ym sou- sedem. Je d˚uleˇzit´e si uvˇedomit, ˇze H sloˇzka je hodnota na barevn´em kotouˇci (Obr.6) a tedy lev´y krajn´ı bin soused´ı s prav´ym krajn´ım bi- nem.
(b) Pokud maj´ı sousedn´ı biny rozd´ıln´y poˇcet pixel˚u, dojde k pˇresunu vzh˚uru k binu s vˇetˇs´ım poˇctem pixel˚u.
(c) Pokud maj´ı sousedn´ı biny stejn´y poˇcet pixel˚u, dojde k posouv´an´ı na dalˇs´ı sousedy, dokud nejsou nalezeny biny s rozd´ıln´ym poˇctem pixel˚u. Pˇresun vzh˚uru je proveden na bin s vˇetˇs´ım poˇctem pixel˚u.
(d) Postup 2(a)-2(c) je opakov´an, dokud nedojde k nalezen´ı binu, z kter´eho jiˇz ˇz´adn´ym zp˚usobem nen´ı moˇzn´y pohyb vzh˚uru, tj. sousedn´ı biny obsahuj´ı menˇs´ı poˇcet pixel˚u. Tento bin je indentifikov´an jako peak (vrchol ˇci kopec), jedn´a se o lok´aln´ı maximum v histogramu 3. Je zvolen dalˇs´ı libovoln´y nenulov´y, avˇsak dosud nezpracovan´y, bin a je
zopakov´an krok ˇc´ıslo 2. Tento krok se opakuje, dokud nejsou zpracov´any vˇsechny biny histogramu.
4. Identifikovan´a lok´aln´ı maxima pˇredstavuj´ı poˇcet shluk˚u v obraze (pozn.
tato metoda by tedy mohla b´yt jednou z dalˇs´ıch moˇznost´ı automatizace segmentace pomoc´ı k-means shlukov´an´ı)
5. Jednotliv´e biny jsou pˇriˇrazeny k tomu lok´aln´ımu maximu, ke kter´emu se doˇslo v kroce 2; t´ımto je segmentace hotova.
Obr.11[15] zn´azorˇnuje pr˚ubˇeh algoritmu - (a) hled´an´ı vrchol˚u (peak˚u), (b) pˇriˇrazov´an´ı bin˚u k vrchol˚um.
Zobecnˇen´ı tohoto postupu do tˇr´ı rozmˇer˚u (tedy pro vˇsechny tˇri sloˇzky HSV) je pˇr´ımoˇcar´e. V 1. kroce je vytvoˇren trojrozmˇern´y histogram m´ısto jedno- rozmˇern´eho a ve 2. kroce se pouze liˇs´ı poˇcet sousedn´ıch bin˚u, se kter´ymi se porovn´av´a poˇcet jejich pixel˚u. Ve tˇrech rozmˇerech m´a obecnˇe kaˇzd´y bin m´ısto dvou dvacet ˇsest soused˚u (neplat´ı pro krajn´ı biny histogramu); d´ale je tˇreba si uvˇedomit, ˇze zat´ımco mezn´ı biny H komponenty spolu soused´ı, pro S a V sloˇzku toto neplat´ı. Nav´ıc je tˇreba zav´est n´asleduj´ıc´ı podm´ınku - pokud je hodnota S pˇr´ıliˇs mal´a (pˇribliˇznˇe 0.1), porovn´avaj´ı se pouze sousedn´ı biny ve smˇeru V sloˇzky. Kdyˇz jsou hodnoty S pˇr´ıliˇs mal´e, lidsk´e oko nedok´aˇze rozeznat zmˇenu barvy pˇri zmˇenˇe hodnoty V.
(a) (b) Obr. 11 Hill-Climbing algoritmus
Jedin´ymi parametry tohoto algoritmu je poˇcet jednotliv´ych bin˚u histogramu.
Pravidlem je, ˇze H sloˇzka je kvantizov´ana do v´ıce ´urovn´ı neˇz zbyl´e dvˇe sloˇzky tak, aby reflektovala r˚uznorodost barev. Doporuˇcen´y pomˇeru bin˚u H:S:V je 16:8:8[15], pˇri tomto rozloˇzen´ı ovˇsem doch´az´ı u vˇetˇs´ıch obrazu k ˇc´asteˇcn´emu pˇresegmentov´an´ı a zvolen byl proto nakonec pomˇer 15:7:7.
Pro kaˇzd´y bin histogramu je prozkoum´ano vˇsech jeho 26 soused˚u a kaˇzd´y pi- xel obrazu mus´ı b´yt pˇriˇrazen k jednomu z lok´aln´ıch maxim v histogramu (tzn.
k segmentu). Pˇri poˇctu bin˚u Ni a celkov´em poˇctu pixel˚u Np je tedy ˇcasov´a sloˇzitost Hill-climbing segmentaceO(26Ni+Np).
3.3 Prvn´ı dˇ elen´ı na z´ akladˇ e velikosti
Jak je patrn´e z Obr.12(b) (segmenty zn´azornˇen´e odst´ıny ˇsedi), segmentace po- moc´ı Hill-Climbing algoritmu vytv´aˇr´ı velmi zrnit´e oblasti na hranic´ıch jednot- liv´ych objekt˚u v obraze. Jedn´a se o mal´e segmenty o velikosti ˇr´adovˇe nˇekolika des´ıtek aˇz nˇekolika stovek pixel˚u (v´yjimkou ovˇsem nejsou ani nˇekolikapixelov´e segmenty). Z hlediska pragmatiˇcnosti nejsou tyto segmenty nijak d˚uleˇzit´e a je tedy moˇzno je pˇr´ımo oddˇelit od dostateˇcnˇe velik´ych segment˚u. Toto je vy- kon´ano obyˇcejn´ym prahov´an´ım - nejdˇr´ıve je vypoˇctena jejich velikost (tj. poˇcet pixel˚u) a pokud je menˇs´ı neˇz stanoven´y pr´ah, segment je ”zahozen”. Pr´ah byl urˇcen na 0.4% celkov´eho poˇctu pixel˚u v obraze, coˇz je pˇri alokaci 250000 pixel˚u na obraz pˇribliˇzne 1000 pixel˚u. Pouˇzit´ım takov´eho prahov´an´ı doˇslo u Obr.12 k odstranˇen´ı ˇctyˇriceti dvou segment˚u (odstranˇen´e ˇc´asti jsou zn´azornˇeny fialo- vou barvou na Obr.12(c)).
Pˇri celkov´em poˇctu pixel˚uNp a celkov´em poˇctu segment˚uk je ˇcasov´a sloˇzitost oddˇelen´ı mal´ych segment˚uO(Np+k) - ke spoˇc´ıt´an´ı velikosti staˇc´ı jednou proj´ıt v´ystup z Hill-Climbing algoritmu (odtud O(Np)) a pot´e je kaˇzd´y poˇcet po- rovn´an s prahem (odtud O(k)).
(a) P˚uvodn´ı obr´azek
(b) Segmentace (c) Odstranˇen´ı mal´ych segment˚u Obr. 12 Prvn´ı dˇelen´ı na z´akladˇe velikosti
3.4 Prostorov´ e oddˇ elen´ı segment˚ u a druh´ e dˇ elen´ı na z´ akladˇ e velikosti
Segmentace pomoc´ı Algoritmu zdol´av´an´ı kopc˚u nebere v ´uvahu prostorov´e rozloˇzen´ı segment˚u, viz jednoduch´y pˇr´ıklad na Obr.13 (segmentace na Obr.13(b) opˇet zn´azornˇena odst´ıny ˇsedi; v tomto pˇr´ıpadˇe pouze ˇcernou a b´ılou barvou, jelikoˇz existuj´ı pouze dva segmenty p˚uvodn´ıho obrazu - oranˇzov´a a modr´a ˇ
c´ast).
(a) P˚uvodn´ı obr´azek (b) Segmentace Obr. 13 Prostorovˇe neoddˇelen´e segmenty
Vstupem algoritmu je pole s rozˇrazen´ım pixel˚u do segment˚u (po odstranˇen´ı mal´ych segment˚u); v´ystupem je seznam index˚u patˇr´ıc´ıch segmentu (pro kaˇzd´y segment jeden seznam). K prostorov´emu oddˇelen´ı je pouˇz´ıv´ano okol´ı (pro potˇreby tohoto textu nazvan´e1 4 okol´ı) pixelu (bodu) z Obr.14 - o pˇredstavuje zpracov´avan´y pixel (bod), x zkouman´e okol´ı.
x x x
x o
Obr. 14 Okol´ı pixelu (o) pouˇzit´e pˇri prostorov´em dˇelen´ı
Pro kaˇzd´y segment vypad´a pseudok´od algoritmu pro prostorov´e oddˇelen´ı n´asledovnˇe 0. Inicializace algoritmu:
index:= 1
rastr := matice o rozmˇerech p˚uvodn´ıho obr´azku, defaultn´ı hodnota 0 belong:= pr´azdn´e pole
1. Pro∀pixelp zpracov´avan´eho segmentu (p je na pozici(i,j) v p˚uvodn´ım obr´azku): neigh := nenulov´e hodnoty 1 4 okol´ıbodu rastr(i,j)
(a) Je-li neigh pr´azdn´e, potom:
• rastr(i, j) :=index
• belong.add(index)
• index:=index+ 1
(b) Nen´ı-li neigh pr´azdn´e, potom:
• idmin := minim´aln´ı hodnota neigh
• rastr(i, j) :=idmin
• pro ∀i∈neigh: belong(i) = idmin
2. Vytvoˇren´ı pr´azdn´eho seznamu pro kaˇzd´y prostorovˇe samostatn´y seg- ment, celkov´y poˇcet je tˇechto seznam˚u je maxim´aln´ı hodnota polebelong 3. Pro ∀l, m takov´a, ˇze rastr(l, m) 6= 0 je do z-t´eho seznamu pˇrid´an in- dex odpov´ıdaj´ıc´ı pozici (l,m); z je hodnota pole belong na pozici dan´e indexem rastr(l,m)
Popsan´y algoritmus je vysvˇetlen na n´asleduj´ıc´ım pˇr´ıkladu. Je uvaˇzov´an obr´azek o rozmˇerech 6x2 a po Hill-Climbing segmentaci zauj´ım´a jeden ze segment˚u in- dexy na pozic´ıch [2,4,6,7,8,10,11], viz. Obr.15 - nalevo jsou kˇr´ıˇzky vyznaˇceny body patˇr´ıc´ı segmentu, napravo je zn´azornˇena indexace jednotliv´ych pixel˚u.
x x
x x x x x
0 1 2 3 4 5
6 7 8 9 10 11
Obr. 15 Pˇr´ıklad oddˇelovan´eho segmentu
Inicializace algoritmu (krok 0) pouze vytvoˇr´ı pr´azdnou nulovou matici rastr o rozmˇerech 2 ˇr´adky a 6 sloupc˚u, vytvoˇr´ı pr´azdn´e pole belong a do promˇenn´e index pˇriˇrad´ı hodnotu 1.
Prvn´ı pixel segmentu je na pozici 2, 1 4 okol´ı tohoto bodu v rastr neobsa- huje ˇz´adnou nenulovou hodnotu, a tak se pokraˇcuje podle kroku 1.(a) - do rastr(0,2) je pˇriˇrazena hodnota 1, do pole belong je pˇrid´ana jedniˇcka (pro- zat´ım jednoprvkov´e pole) a hodnota promˇenn´eindex je nav´yˇsena na 2.
Dalˇs´ı zpracov´avan´y bod je na pozici 4 a opˇet jsou v jeho1 4 okol´ısam´e nuly. Na rastr(0,4) je pˇriˇrazena hodnota 2, belong je dvojprvkov´e pole s s hodnotami 1 a 2 a index je zvˇetˇsen na 3.
Pˇr´ıliˇs se toho nezmˇen´ı ani pˇri zpracov´an´ı dalˇs´ıho bodu (pozice 6) - belong je nyn´ı tˇr´ıprvkov´e pole [1,2,3] a rastr je na Obr.16
0 0 1 0 2 0
3 0 0 0 0 0
Obr. 16 Hodnoty maticerastr po tˇrech kroc´ıch algoritmu
Prvn´ım ”zaj´ımav´ym”pixelem je bod na pozici 7, v jeho 1 4 okol´ı jsou 1 a 3 (mimo dvou nul, kter´e jsou ovˇsem ignorov´any). Postupuje se podle kroku 1.(b), do idmin je pˇriˇrazena menˇs´ı z hodnot, tedy 1; na rastr(1,1) je pˇriˇrazena tat´aˇz hodnota a dojde i k ´upravˇe pole belong, jeˇz nyn´ı vypad´a n´asledovnˇe: [1,2,1]
(Pozn.: je moˇzn´e si vˇsimnout mal´e nesrovnalosti v indexac´ıch, zat´ımco matice rastr a vˇsechna prozat´ım zmiˇnovan´a pole zaˇc´ınaj´ı indexem 0, polebelongzaˇc´ın´a indexem 1. Tato indexace, aˇc moˇzn´a matouc´ı, je z´amˇern´a.)
Hodnoty rastr po dokonˇcen´ı 1. kroku algoritmu jsou ve Obr.17; polebelong se jiˇz nezmˇenilo - [1,2,1]. V´yznam tohoto pole spoˇc´ıv´a v pˇriˇrazen´ı r˚uzn´ych hodnot matice rastr prostorovˇe souvisl´emu shluku. Hodnota 1 na tˇret´ım indexu pole belong znamen´a, ˇze indexy vrastr s hodnotou 3 patˇr´ı do stejn´eho shluku jako indexy s hodnotou 1; na druhou stranu indexy s hodnotou 2 tvoˇr´ı samostatn´y shluk.
0 0 1 0 2 0
3 1 1 0 2 2
Obr. 17 Koneˇcn´e hodnoty matice rastr
N´aslednˇe jsou podle 2. kroku vytvoˇreny dva pr´azdn´e seznamy a podle 3.
kroku jsou do nich pˇridˇelov´any indexy. V´ysledkem jsou tedy segmenty popsan´e indexy [2,6,7,8] a [4,10,11].
Neˇz´adouc´ım vedlejˇs´ım produktem prostorov´eho oddˇelov´an´ı je moˇznost tvorby pˇr´ıliˇs mal´ych segment˚u. To se m˚uˇze st´at v pˇr´ıpadˇe, ˇze segment projde prvn´ım testem na minim´aln´ı velikost a n´aslednˇe je v tomto kroku rozdˇelen na dvˇe ˇ
ci v´ıce ˇc´ast´ı, kter´e by t´ım sam´ym testem jiˇz neproˇsly. Proto je tˇreba znovu otestovat velikosti a mal´e segmenty odstranit - opˇet je nastavena hranice 0.4%
celkov´eho poˇctu pixel˚u (pˇri alokaci 250000 pixel˚u na obraz pˇribliˇznˇe 1000 pi- xel˚u). Z´aroveˇn jsou odstranˇeny (pˇresnˇeji vzato jsou uloˇzeny ”bokem”, protoˇze je tˇechto segment˚u potˇreba v urˇcit´ych situac´ıch, viz. d´ale) pˇr´ıliˇs velk´e seg- menty, kter´e mohou b´yt povaˇzov´any za patˇr´ıc´ı pozad´ı. V prvn´ım dˇelen´ı podle velikosti nemohlo k tomuto ´ukonu doj´ıt, nebot’ nebylo moˇzn´e rozeznat pˇr´ıliˇs velk´e celistv´e segmenty od pˇr´ıliˇs velk´ych necelistv´ych segment˚u, tj. takov´ych, kter´e maj´ı po prostorov´em oddˇelen´ı pˇrijatelnou velikost. Pr´ah maxim´aln´ı ve- likosti byl urˇcen na 15% celkov´eho poˇctu pixel˚u v obraze, coˇz dˇel´a pˇribliˇznˇe 37500 pixel˚u pˇri nastaven´e alokaci.
Algoritmus pro kaˇzd´y segment vytvoˇr´ı jednu matici o velikosti p˚uvodn´ıho obr´azku - prvky matice jsou v 1. kroku sekvenˇcnˇe proch´azeny, je kontrolov´ano jejich 1 4 okol´ı a upravov´ana jejich hodnota. Zjiˇstˇen´ı 1 4 okol´ı nen´ı z´avisl´e na celkov´em poˇctu pixel˚u ani na poˇctu segment˚u a lze tedy z´ıskat v kon- stantn´ım ˇcase. K ´upravˇe pole belong doch´az´ı (i kdyˇz zpravidla tomu tak nen´ı) v kaˇzd´e iteraci 1. kroku algoritmu, tj. pro kaˇzd´y prvek matice - jsou mˇenˇeny maxim´alnˇe ˇctyˇri jeho hodnoty (tolik je maximum nenulov´ych hodnot v 1 4 okol´ıkaˇzd´eho bodu). Pˇri velikosti tohoto pole Nm, celkov´em poˇctu pixel˚uNp a poˇctu zpracov´avan´ych segment˚ukje tedy ˇcasov´a sloˇzitost 1. kroku algoritmu O(4kNmNp).
2. krok algoritmu je oˇcividnˇe ˇcasovˇe konstantn´ı, doch´az´ı v nˇem pouze ke stano- ven´ı poˇctu oddˇelen´ych segment˚u. Ve 3. kroku algoritmu doch´az´ı k opˇetovn´emu sekvenˇcn´ımu proch´azen´ı (a opˇet pro kaˇzd´y zpracovan´y segment) a k pˇriˇrazov´an´ı index˚u jednotliv´ym segment˚um. ˇCasov´a sloˇzitost 3. kroku je tedyO(kNp).
Celkov´a ˇcasov´a sloˇzitost prostorov´eho oddˇelen´ı je O(kNp(4Nm+ 1)), kde k Np a Nm Np. k je zpravidla v ˇr´adech jednotek aˇz nˇekolika m´alo des´ıtek;
Nm je zpravidla tak´e v ˇr´adech jednotek aˇz nˇekolika m´alo des´ıtek a je z´avisl´e na ˇclenitosti hranic segment˚u.
Sloˇzitost odstranˇen´ı segment˚u neˇz´adouc´ıch velikost´ı je rovna O(k) - kaˇzd´y segment m´a sv˚uj vlastn´ı seznam, staˇc´ı tedy pouze zkontrolovat velikost kaˇzd´eho seznamu a porovnat s nastaven´ymi prahy.
3.5 Krit´ erium pro vyb´ır´ an´ı segment˚ u
C´ılem algoritmu popsan´eho na zaˇc´atku t´eto kapitoly je vybrat z libovoln´eho vstupn´ıho obr´azku ˇc´asti tak, aby tyto ˇc´asti odpov´ıdaly objekt˚um v obraze.
Toho se dos´ahne v´yˇse popsan´ym segmentaˇcn´ım algoritmem. Vybran´e ˇc´asti by d´ale mˇely b´yt vizu´alnˇe pˇrijateln´e, a i kdyˇz se jedn´a o vcelku v´agn´ı a hlavnˇe do- sti subjektivnˇe zaloˇzen´y poˇzadavek, existuj´ı deskriptory geometrick´ych tvar˚u (shape descriptors), podle kter´ych je moˇzn´e rozhodnout.
Zvaˇzov´any byly n´asledn´e deskriptory zaloˇzen´e na oblasti popisovan´eho geome- trick´eho tvaru (region-based shape descriptors[5])
• Eccentricity ud´av´a pomˇer d´elky hlavn´ı osy (major axis) a ve- dlejˇs´ı osy (minor axis)
• Elongatedness ud´av´a podobnost tvaru pˇr´ımce a spoˇc´ıt´a se jako pomˇer ˇs´ıˇrky a v´yˇsky nejmenˇs´ıho obklopuj´ıc´ıho obd´eln´ıku (minimum area enclosing rectangle) dan´eho tvaru
• Rectangularity mˇeˇr´ı podobnost obd´eln´ıku a je vypoˇctena jako pomˇer obsahu dan´eho tvaru ku souˇcinu rozmˇer˚u nejmenˇs´ıho obklopuj´ıc´ıho obd´eln´ıku
• Compactness vyjadˇruje podobnost geometrick´eho tvaru a kruˇznice
Elongatedness nelze snadno (pomoc´ı nejmenˇs´ıho obklopuj´ıc´ıho obd´eln´ıku) vy- poˇc´ıtat pro v´ıce zakˇriven´e tvary, coˇz z n´ı dˇel´a nevhodn´eho kandid´ata pro po- pis ”dobr´ych“ tvar˚u. Podobnost obd´eln´ıku (rectangularity) ˇci ”zploˇstˇen´ı”tvaru (eccentricity) byly tak´e zam´ıtnuty jako vlastnosti, kter´e nepopisuj´ı vhodnost tvaru. Vybr´ana byla tedy kompaktnost; podobnost kruˇznici (kruhu) se totiˇz jevila jako vizu´alnˇe uspokojiv´a.
3.5.1 V´ ypoˇ cet kompaktnosti geometrick´ eho tvaru
Kompaktnost geometrick´eho tvaru (tak´e nˇekdy naz´yv´ana shape index) je nu- merick´a kvantita vyjadˇruj´ıc´ı kompaktnost tvaru (a nebo jako bylo zm´ınˇeno dˇr´ıve, podobnost tvaru a kruˇznice). Kompaktnost je uzn´av´ana jako jedna z nejzaj´ımavˇejˇs´ıch a nejd˚uleˇzitˇejˇs´ıch vlastnost´ı geometrick´eho tvaru a je hojnˇe pouˇz´ıv´ana nejen v odvˇetv´ı poˇc´ıtaˇcov´eho vidˇen´ı[17]. Mezi pˇr´ıklady pouˇzit´ı patˇr´ı definov´an´ı a anal´yza homogenn´ıch oblast´ı v´yskytu v ekologii, object matching
a rozpozn´av´an´ı vzor˚u (pattern recognition) v oblasti umˇel´e inteligence, po- pis a vyhled´av´an´ı objekt˚u v obrazov´ych datab´az´ıch[17]. V psychologick´ych studi´ıch byla kompaktnost zavedena jako ukazatel stability a estetiˇcnosti geo- metrick´eho tvaru[18], coˇz jen umocˇnuje jej´ı v´ybˇer pro selekci ”dobr´ych”tvar˚u.
Snahy o vyj´adˇren´ı kompaktnosti geometrick´eho tvaru maj´ı dlouho historii([17]).
V roce 1822 navrhl Ritter vyj´adˇren´ı kompaktonosti jako pomˇer obvodu P ku ploˇse tvaru A. I kdyˇz je takov´e vyj´adˇren´ı pˇr´ımoˇcar´e, tento jednoduch´y pomˇer se zmˇen´ı pˇri zmˇenˇe velikosti tvaru. Tuto veliˇcinu je moˇzn´e uˇcinit bezrozmˇernou, pokud se vypoˇcte pomˇer plochy ku druh´e mocninˇe obvodu; mezi mnoh´e vari- anty tohoto postupu patˇr´ı napˇr´ıklad pomˇer 4A/P2 (Miller, 1953) ˇci 2√
πA/P (Richardson, 1961). Nejpouˇz´ıvanˇejˇs´ım vyj´adˇren´ım kompaktnosti tohoto typu je potom IPQ index (Osserman, 1978) dan´y pˇredpisem
CIP Q = 4πA P2
HodnotyCIP Qn´aleˇz´ı intervalu (0,1i. Geometrick´e tvary s vyˇsˇs´ı hodnotouCIP Q jsou kompaktnˇejˇs´ı neˇz tvary s niˇzˇs´ı hodnotou CIP Q, nejkompkatnˇejˇs´ı je kruh s CIP Q rovn´ym jedn´e.
Dalˇs´ım zp˚usobem ˇc´ıseln´eho vyj´adˇren´ı kompaktnosti je porovn´av´an´ı s refe- renˇcn´ımi tvary. Cole v roce 1964 navrhl porovn´av´an´ı plochy A zkouman´eho tvaru s plochou nejmenˇs´ı opsan´e kruˇznice tomuto tvaru ASC jako alternativu ke Gibbsovˇe (1961) pomˇeru 4A/L2, kde Lje vzd´alenost dvou nejvzd´alenˇejˇs´ıch bod˚u na obvodu tvaru. V roce 1984 zavedli Kim a Anderson toto porovn´an´ı jako index DCM (digital compactness measure)
CDCM = A ASC
Stejnˇe jako uCIP Q n´aleˇz´ı hodnotyCDCM intervalu (0,1i, kdy nejkompaktnˇejˇs´ı kruh nab´yv´a opˇet hodnoty jedna.CDCM nen´ı bohuˇzel moˇzn´e pouˇz´ıt na nevy- plnˇen´e geometrick´e tvary (tj. tvary s otvory) a nav´ıc nen´ı invariantn´ı v˚uˇci zmˇenˇe velikosti.
Bottema v roce 2000 navrhl dalˇs´ı veliˇcinu vyuˇz´ıvaj´ıc´ı referenˇcn´ıch tvar˚u CBottema = 1− |A∩A0|
A0
kter´a vyuˇz´ıv´a kruhu stejn´e plochy jako mˇeˇren´y geometrick´y objekt, konkr´etnˇe velikosti pr˚uniku tohoto kruhu a mˇeˇren´eho geometrick´eho objektu (Aje povrch
objektu, A0 povrch kruhu). Dalˇs´ı index podobn´y CBottema pˇredstavil v roce 2000 Wentz. Jeho podoba je (pˇri stejn´e notaci jako uCBottema)
El = |A∩A0|
|A∪A0|
CBottemaiEl lze pouˇz´ıt na objekty s otvory; nev´yhodou je vˇsak potˇreba nalezen´ı optim´aln´ıho (tj. maxim´aln´ıho) pˇrekryt´ı mˇeˇren´eho objektu a zkonstruovan´eho kruhu a nav´ıc opˇet nen´ı ani jeden index invariantn´ı v˚uˇci zmˇenˇe velikosti.
Bribiesca v roce 1997 navrhl index NDC (normalized discrete compactness) pˇr´ımo pro rastrov´a data
CN DC =
4n−p
2 −n+ 1 n−2√
n+ 1
kde p je poˇcet (mezn´ıch) hran mˇeˇren´eho geometrick´eho tvaru a n celkov´y poˇcet pixel˚u tohoto tvaru.CN DC je invariantn´ı v˚uˇci zmˇenˇe velikosti a reflektuje nevyplˇnenost objekt˚u, je vˇsak potˇreba urˇcit poˇcet hran p mˇeˇren´eho objektu.
Z v´yˇse popsan´ych veliˇcin na mˇeˇren´ı kompaktnosti geometrick´eho objektu byl vybr´an index CIP Q. Nejen, ˇze lze relativnˇe snadno vypoˇc´ıtat, nem´a ˇz´adn´e z´asadn´ı nev´yhody (dok´aˇze si poradit s d´ırovan´ymi objekty a je invariantn´ı v˚uˇci zmˇenˇe velikosti).
3.5.2 V´ ypoˇ cet IP Q indexu
Pro pˇripomenut´ı, pˇredpis pro v´ypoˇcet CIP Q indexu dvojrozmˇern´eho geomet- rick´eho obrazce pˇri zn´am´em obvodu P (z anglick´eho perimeter) a pˇri zn´am´em obsahu A (area) je
CIP Q = 4πA P2
Hodnota A se pro jednotliv´e segmenty snadno z´ısk´a jako poˇcet prvk˚u v se- znamu index˚u reprezentuj´ıc´ıho dan´y segment, kter´y byl z´ısk´an pˇri prostorov´em oddˇelov´an´ı (posledn´ı prov´adˇen´y ´ukol); trochu problematiˇctˇejˇs´ı je to s urˇcen´ım obvodu P.
K v´ypoˇctu obvodu geometrick´eho obrazce je nejprve potˇreba zjistit hranici ob- jektu, k ˇcemuˇz byl pouˇzit Freeman˚uv ˇretˇezov´y k´od (Freeman’s chain code nebo jen Freeman’s code)[19]. Tento k´od slouˇz´ı k popisu hranic objekt˚u a vyuˇz´ıv´a k tomu oznaˇcen´ı okoln´ıch pixel˚u zkouman´eho pixelu ˇc´ısly viz Obr.18. Pro ´uˇcely t´eto pr´ace byla pouˇzita 8-kontektivita (z Freemanova ˇretˇezov´eho k´odu tak´e vznikl n´azev1 4 okol´ı pouˇz´ıvan´y v kapitole o oddˇelov´an´ı segment˚u).
(a) 4-konektivita (b) 8-konektivita Obr. 18 Freeman˚uv ˇretˇezov´y k´od
Od poˇc´ateˇcn´ıho pixelu, kter´y je prvn´ım a z´aroveˇn i posledn´ım prvkem ˇretˇezov´eho k´odu, je sekvenc´ı (ˇretˇezem) takov´ychto ˇc´ısel pops´ana hranice objektu zpravidla ve smˇeru hodinov´ych ruˇciˇcek. Napˇr´ıklad ˇretˇezov´y k´od [0,1,2,7,0,6,5,7,1,0,0,1]
popisuje ˇc´ast hranice na Obr.19[20].
Obr. 19 Pˇr´ıklad popisu hranice objektu
Algoritmus pro nalezen´ı k´odu[21] zaˇc´ın´a v jednom z extr´emn´ıch pixel˚u, tzn.
v jednom z pixel˚u leˇz´ıc´ıch nejv´ıce vlevo, nejv´ıce vpravo, nejv´ıce dole nebo nejv´ıce nahoˇre. Jelikoˇz prvn´ı pixel v seznamu kaˇzd´eho segmentu je z podstaty algoritmu na prostorov´e oddˇelen´ı z´aroveˇn pixelem leˇz´ıc´ım nejv´ıce nahoˇre, je zvolen pr´avˇe tento pixel. Dalˇs´ı pixely segmentu mohou sice leˇzet ve stejn´e v´yˇsce (a to pouze napravo od prvn´ıho pixelu seznamu), pro zjiˇstˇen´ı ˇretˇezov´eho k´odu to ovˇsem nen´ı ˇz´adnou pˇrek´aˇzkou. Ze zvolen´eho poˇc´ateˇcn´ıho bodu m˚uˇze ˇretˇez pokraˇcovat pouze ve smˇerech 0, 7, 6 a 5; smˇery 1, 2 a 3 jsou vylouˇceny, jelikoˇz ˇz´adn´y pixel nem˚uˇze leˇzet nad startovn´ı pozic´ı a smˇer 4 je vylouˇcen na
z´akladˇe argumentu z pˇredchoz´ı vˇety, tj. startovn´ı pozice nem˚uˇze z principu m´ıt souseda vlevo. Je tˇreba dodrˇzovat i poˇrad´ı prohled´avan´ych sousedn´ıch smˇer˚u - ze startovn´ıho pixelu je tˇreba nejprve prozkoumat pixel ve smˇeru 0 a teprve pokud tento pixel nen´aleˇz´ı segmentu, pokraˇcuje se ve smˇeru 7 (a n´aslednˇe 6 a 5, je-li to nutn´e). Po nalezen´ı spr´avn´eho pixelu z hranice segmentu se stejn´ym zp˚usobem pokraˇcuje v z´ısk´av´an´ı dalˇs´ıch ˇc´ast´ı k´odu, dokud se algo- ritmus nevr´at´ı opˇet na zaˇc´atek. V kaˇzd´em kroku jsou ovˇsem prozkoum´av´any jin´e smˇery (tzn. 0, 7, 6, 5 nejsou univerz´aln´ı posloupnost´ı kandid´at˚u); prvn´ı takov´yto smˇer je o dva v´ıce neˇz posledn´ı pˇridan´y, napˇr´ıklad je-li posledn´ım prvkem ˇretˇezov´eho k´odu 4, prvn´ım kandid´atem je smˇer 6 a v pˇr´ıpadˇe jeho nevybr´an´ı se pokraˇcuje d´ale ve smˇeru hodinov´ych ruˇciˇcek (tj. 5, 4, 3 atd.).
Popsan´y algoritmus je vysvˇetlen na n´asleduj´ıc´ım pˇr´ıkladu. Je uvaˇzov´an obr´azek o rozmˇerech 4x4 a segment popsan´y indexy [1,2,4,5,6,8,9,10,11,13,14], viz.
Obr.20 - nalevo jsou kˇr´ıˇzky vyznaˇceny body patˇr´ıc´ı segmentu, napravo je zn´azornˇena indexace jednotliv´ych pixel˚u.
x x
x x x
x x x x
x x x
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Obr. 20 Pˇr´ıklad segmentu
Zaˇc´ın´a se bodem, kter´y m´a index 1, a postupnˇe jsou prohled´av´any smˇery 0, 7, 6 a 5. Pˇresnˇeji ˇreˇceno by tyto smˇery byly prozkoum´av´any, jiˇz smˇer 0 ovˇsem n´aleˇz´ı segmentu, je tedy pˇrid´an do ˇretˇezov´eho k´odu a algoritmus pokraˇcuje.
Prvn´ım kandid´atem na dalˇs´ı postup je smˇer o dva vˇetˇs´ı neˇz posledn´ı pˇridan´y, tj. 2. Pixel v tomto smˇeru ovˇsem nen´aleˇz´ı segmentu (neleˇz´ı ani v obr´azku samotn´em) a tak je prozkoum´ana n´asleduj´ıc´ı moˇznost po smˇeru hodinov´ych ruˇciˇcek (tj. 1), kter´a je vˇsak tak´e zam´ıtnuta. Postupnˇe jsou zavrhnuty i smˇery 0 a 7. Bod ve smˇeru 6 je jiˇz souˇc´ast´ı segmentu, a tak je pˇrid´an do ˇretˇezov´eho k´odu, kter´y m´a nyn´ı tvar 0-6. Algoritmus pokraˇcuje podle stejn´eho principu d´ale (dalˇs´ı krok zvaˇzuje nejdˇr´ıve smˇer 0), dokud se obrys objektu neuzavˇre.
V´ysledn´y ˇretˇezov´y k´od m´a podobu 0-6-7-6-4-4-3-2-1.
Po zjiˇstˇen´ı obrysu (reprezentov´an ˇretˇezov´ym k´odem) je jiˇz moˇzno vypoˇc´ıtat (pˇresnˇeji vzato odhadnout) hodnotu obvoduP, viz. [20]. Prvn´ı moˇznost´ı je jed- noduch´e poˇc´ıt´an´ı pixel˚u, a i kdyˇz se jedn´a o velmi pˇr´ımoˇcarou moˇznost, doch´az´ı k podhodnocen´ı v´ysledn´eho obvodu; diagon´aln´ı kroky (lich´a ˇc´ısla v ˇretˇezov´em k´odu) maj´ı totiˇz ve skuteˇcnosti vˇetˇs´ı d´elku neˇz uvaˇzovan´ych 1. Freeman navrhl pro kaˇzd´y takov´y diagon´aln´ı krok pˇriˇc´ıtat√
2 nam´ısto 1, viz. [19], coˇz reflektuje skuteˇcnou vzd´alenost stˇred˚u pixel˚u. Probl´em re´aln´ych objekt˚u a jejich obrys˚u
spoˇc´ıv´a v digitalizaci dat. Je-li souˇc´ast´ı hranice rovn´a pˇr´ımka (ve smyslu kol- mosti k hranic´ım obr´azku), vˇse funguje tak jak m´a. Je-li ovˇsem ta sam´a pˇr´ımka m´ırnˇe natoˇcena (napˇr. o nˇekolik m´alo stupˇn˚u), dojde pˇreveden´ım na obraz sloˇzen´y z pixel˚u k jej´ımu ”zazubatˇen´ı”a souˇcet vzd´alenost´ı stˇred˚u pixel˚u tedy neodpov´ıd´a jej´ı skuteˇcn´e d´elce. Proffitt a Rosen[22] toto reflektovali a odhad upravili na P = 0.948e+ 1.340o, kdee je poˇcet sud´ych ˇc´ısel v ˇretˇezov´em k´odu ao je poˇcet lich´ych ˇc´ısel v ˇretˇezov´em k´odu. Vossepoel a Smeulders[23] v´ypoˇcet d´ale zpˇresnili na P = 0.948e+ 1.340o−0.091c, kde e ao maj´ı stejn´y v´yznam jako v pˇredchoz´ım vzorci a c ud´av´a kolikr´at ˇretˇezov´y k´od zmˇenil hodnotu (corner count).
Luengo provedl experiment[20], kdy postupnˇe nat´aˇcel obd´eln´ık a pro kaˇzd´e natoˇcen´ı mˇeˇril kaˇzdou z metod jeho obvod. V´ysledky jsou zn´azornˇeny na Obr.55 - na oseyje hodnota odhadnut´eho obvodu, na osex natoˇcen´ı obd´eln´ıku, modˇre jsou hodnoty pro poˇc´ıt´an´ı pixel˚u ˇretˇezov´eho k´odu, zelenˇe Freemanovo zlepˇsen´ı, ˇcervenˇe metoda od Proffitta a Rosena, tyrkysovˇe metoda od Vos- sepoela a Smeulderse a ˇc´arkovanˇe je na ose y skuteˇcn´a hodnota obvodu. Je vidˇet, ˇze poˇc´ıt´an´ı pixel˚u podhodnocuje obvod u jak´ehokoli natoˇcen´ı a tak´e, ˇze metoda od Vossepoela a Smeulderse se s natoˇcen´ım vypoˇr´ad´a opravdu nejl´epe z pˇredstaven´ych metod.
Obr. 21 Porovn´an´ı metod na mˇeˇren´ı obvodu
Vypoˇcten´ıIP Qindexu jednoho segmentu je pˇri poˇctu pixel˚u v tomto segmentu Ns roven O(Ns). Obsah segmentu A lze z´ıskat konstantˇe, je roven velikosti seznamu reprezentuj´ıc´ıho segment. Obvod segmentu P je z´ısk´an v ˇcaseO(Ns) - pˇri poˇc´ıt´an´ı ˇretˇezov´eho k´odu jsou prozkoum´any pixely hranice (maxim´alnˇe Ns) a u kaˇzd´eho je v konstantn´ım ˇcase urˇcen smˇer postupu (8 moˇzn´ych smˇer˚u nez´avisl´ych na poˇctu pixel˚u).
3.6 Operace ovlivˇ nuj´ıc´ı IP Q index
Jak je patrn´e z Obr.12, segmenty jsou u sv´ych hranic velmi ˇclenit´e a obsa- huj´ı pomˇernˇe velk´e mnoˇzstv´ı r˚uznˇe velik´ych otvor˚u. Pˇred samotn´ym v´ybˇerem ˇ
z´adouc´ıch segment˚u s dostateˇcn´ym IP Qindexem jsou proto tyto vizu´aln´ı ne- dostatky odstranˇeny pomoc´ı dvou operac´ı, kter´e IP Q index mˇen´ı (zvˇetˇsuj´ı).
Tyto operace jsou vysvˇetleny v n´asleduj´ıc´ıch dvou podkapitol´ach.
3.6.1 Matematick´ a morfologie
Prvn´ı z pouˇzit´ych metod na vizu´aln´ı zlepˇsen´ı segmentu se op´ır´a o bin´arn´ı mate- matickou morfologii[5] (tj. morfologii bin´arn´ıch obraz˚u), matematick´y n´astroj pouˇz´ıvaj´ıc´ı neline´arn´ı oper´atory operuj´ıc´ı na tvaru objektu. Jelikoˇz se jedn´a o pomˇernˇe sloˇzitou problematiku, bude zde diskutov´ana hlavnˇe s d˚urazem na praktick´e pouˇzit´ı.
Morfologick´a anal´yza vyuˇz´ıv´a moˇznosti z´apisu bin´arn´ıch obraz˚u jako podmnoˇzin dvojrozmˇern´eho prostoru cel´ych ˇc´ısel Z2. Napˇr´ıklad segment (coˇz je vlastnˇe bin´arn´ı obraz - pixely segmentu patˇr´ı obrazu, tj. maj´ı hodnotu 1 a zb´yvaj´ıc´ı pixely obrazu nepatˇr´ı, jejich hodnota je 0) na Obr.22,
× ×
× ×
× ×
Obr. 22 Pˇr´ıklad segmentu jako bin´arn´ıho obrazu
kde × pˇredstavuj´ı pixely patˇr´ıc´ı segmentu a je poˇc´atek souˇradnicov´e sou- stavy, tj. m´a souˇradnice (0,0), lze vyj´adˇrit jako mnoˇzinu
X ={(1,0),(2,0),(0,1),(1,1),(1,2),(2,2)}
Morfologick´a transformace je vyj´adˇrena relac´ı mnoˇzinovˇe zapsan´eho bin´arn´ıho obrazu a strukturn´ıho elementu - mal´e mnoˇziny vztaˇzen´e k lok´aln´ımu poˇc´atku, kter´a slouˇz´ı jako ”lok´aln´ı sonda”v morfologick´ych operac´ıch. Nejˇcastˇeji pouˇz´ıvan´e strukturn´ı elementy jsou ve Obr.23
× × ×
× × ×
× × ×
×
× × ×
×
× × ×
×
×
×
×
×
Obr. 23 Nejˇcastˇeji pouˇz´ıvan´e strukturn´ı elementy
Prvn´ım z pomocn´ych ´ukon˚u pouˇz´ıvan´ych v bin´arn´ı morfologii je translace Xh mnoˇziny X o radiusvektor h dan´a vztahem.
Xh ={p∈ E2 :p=x+h pro∀x∈X}
kde E2 oznaˇcuje 2D euklidovsk´y prostor. Pˇr´ıklad je na Obr.24
× ×
× × × ×
×
× ×
× ×
× ×
X h Xh
Obr. 24 Posunut´ı o radiusvektor
Druhou pomocnou operac´ı je transpozice ˘B mnoˇziny B (nˇekdy oznaˇcov´ano jako stˇredov´a symetrie)
B˘ ={−b: ∀b ∈B} Pˇr´ıklad transpozice je na Obr.25
× ×
× ×
× ×
B B˘
Obr. 25 Transpozice
Bin´arn´ı matematick´a morfologie vyuˇz´ıv´a dvou z´akladn´ıch operac´ı, kter´e jsou neinvertovateln´e, dilatace a eroze. Bin´arn´ı dilatace ⊕lze vyj´adˇrit jako
X⊕B ={p∈ E2 :p=x+b, x ∈X, b ∈B}
nebo pomoc´ı Minkowsk´eho souˇctu jako sjednocen´ı posunut´ych mnoˇzin X⊕B = [
b∈B
Xb
Pˇr´ıklad bin´arn´ı dilatace je na Obr.26
× ×
× × × ×
× ×
× × ×
× × × × × ×
X B X⊕B
Obr. 26 Bin´arn´ı dilatace
Bin´arn´ı erozi je tak´e moˇzn´e zapsat dvˇema zp˚usoby. Bud’ se kontroluje, zda vˇsechna moˇzn´a posunut´ıx+b leˇz´ı v p˚uvodn´ı mnoˇzinˇeX a pokud ano, n´aleˇz´ı bod x tak´e v´ysledku (tj. erodovan´e mnoˇzinˇe)
X B ={p∈ E2 :p=x+b∈X pro∀b ∈B}
a nebo je eroze urˇcena jako Minkowsk´eho rozd´ıl (pr˚unik vˇsech posunut´ı mnoˇziny X o kaˇzd´y vektor −b)
X B = \
b∈B
X−b
Pˇr´ıklad bin´arn´ı eroze je na Obr.27
×
× × ×
× × ×
×
× × ×
×
X B X B
Obr. 27 Bin´arn´ı eroze
Na kaˇzd´y segment je pouˇzita bin´arn´ı dilatace (se strukturn´ım elementem z Obr.28), ˇ
c´ımˇz dojde k zaplnˇen´ı drobn´ych dˇer a ´uzk´ych z´aliv˚u. Z´aroveˇn vˇsak dojde k ”na- kynut´ı”objektu a z toho d˚uvodu je n´aslednˇe pouˇzita bin´arn´ı eroze (s totoˇzn´ym
strukturn´ım elementem). Takov´eto posloupnosti operac´ıX•B = (X⊕B) B se ˇr´ık´a bin´arn´ı uzavˇren´ı•. V´ysledkem je segment s menˇs´ım (nebo v pˇripadˇe
”pˇekn´ych“ objekt˚u stejn´ym) obvodem a vˇetˇs´ım (nebo opˇet v pˇr´ıpadˇe
”pˇekn´ych“
objekt˚u stejn´ym) obsahem neˇz segment p˚uvodn´ı.
× × ×
× × ×
× × ×
Obr. 28 Pouˇzit´y strukturn´ı element B
Urˇcen´ı ˇcasov´e sloˇzitosti z´aleˇz´ı na datov´e struktuˇre, zat´ım v´agnˇe oznaˇcovan´e jako seznam, ve kter´e je segment uchov´an. V kaˇzd´em pˇr´ıpadˇe je tˇreba prov´est 8 posunut´ı segmentu a tato posunut´ı pro dilataci sjednotit a pro erozi po dvojic´ıch proniknout.
3.6.2 Zaplˇ nov´ an´ı velk´ ych dˇ er
Aplikace matematick´e morfologie, konkr´etnˇe bin´arn´ıho uzavˇren´ı, se vypoˇr´ad´a mimo ˇclenitosti hranic i s mal´ymi otvory v objektech, v tˇech ovˇsem mohou i nad´ale z˚ustat otvory vˇetˇs´ıho charakteru.
Indexy se liˇs´ı o 1
ano
ne
Pokraˇcuje se dalˇs´ı dvojic´ı
Oba in- dexy patˇr´ı
hranici
ano
ne Do segmentu
jsou pˇrid´any chybˇej´ıc´ı indexy
Obr. 29 V´yvojov´y diagram vyplˇnov´an´ı segment˚u
V´yvojov´y diagram algoritmu pro jejich vyplnˇen´ı je na Obr.29 Sekvenˇcnˇe je proch´azen seˇrazen´y seznam s indexy segmentu a po dvojic´ıch jsou kontrolov´any sousedn´ı indexy. Liˇs´ı-li se tyto indexy pouze o jedna, nen´ı zde ˇz´adn´y prostor pro jak´ykoli otvor a pokraˇcuje se tedy dalˇs´ı dvojic´ı. Pixely hranice segmentu leˇz´ı v seznamu na sousedn´ıch pozic´ıch a liˇsit se mohou i o v´ıce neˇz jedna, v tomto pˇr´ıpadˇe se ovˇsem tak´e o otvor v objektu nejedn´a a je tedy opˇet moˇzno pˇrej´ıt na dalˇs´ı dvojici. K vyplnˇen´ı dojde pouze tehdy, jsou-li sousedn´ı indexy rozd´ıln´e o v´ıce neˇz jeden a alespoˇn jeden z nich neleˇz´ı na hranici objektu, tj.
leˇz´ı nˇekde uvnitˇr. V tomto pˇr´ıpadˇe je tˇreba po jedn´e doplnit vˇsechny dalˇs´ı indexy v rozmez´ı t´eto dvojice.
Pro algoritmus je tedy nutn´e zjistit indexy leˇz´ıc´ı na hranici segmentu. K tomu se vyuˇzije ˇretˇezov´y k´od reprezentuj´ıc´ı hranici, kter´y je spoˇc´ıt´an v tˇechto m´ıstech a d´ale se pouˇzije i pro v´ypoˇcetIP Qindexu, jelikoˇz vyplnˇen´ı mezer v objektech nijak nezmˇen´ı hranici objektu. Jak bylo ˇreˇceno dˇr´ıve, prvn´ı index v seznamu kaˇzd´eho segmentu je tak´e poˇc´ateˇcn´ım pixelem pro v´ypoˇcet ˇretˇezov´eho k´odu.
Toho se vyuˇzije pˇri zjiˇst’ov´an´ı hraniˇcn´ıch index˚u, kter´e je moˇzno odvodit z ta- bulky ve Obr.30 (w je ˇs´ıˇrka obr´azku v pixelech)
hodnota
ˇretˇezov´eho k´odu 0 1 2 3 4 5 6 7
zmˇena indexu +1 -(w-1) -w -(w+1) -1 +w-1 +w +w+1
Obr. 30 Zmˇena indexu v z´avislosti na hodnotˇe ˇretˇezov´eho k´odu
D´ale je tˇreba poˇc´ıtat s nepˇr´ıliˇs ˇcastou eventualitou, kdy jeden segment m˚uˇze b´yt uvnitˇr druh´eho. V tomto pˇr´ıpadˇe je vyplnˇen´ı otvoru patˇr´ıc´ımu menˇs´ımu segmentu ve vˇetˇs´ım segmentu neˇz´adouc´ı. K zjiˇst’ov´an´ı takov´eto situace jsou pouˇzity pozice mezn´ıch pixel˚u kaˇzd´eho objektu, tj. pozice nejv´ıce vlevo, po- zice nejv´ıce vpravo, pozice nejv´ıce dole a pozice nejv´ıce nahoˇre, podle kter´ych se d´a snadno zjisti zda je segment potenci´alnˇe uvnitˇr jin´eho ˇci nikoli. Nav´ıc z´ısk´an´ı tˇechto mezn´ıch pozic nic nestoj´ı, je moˇzno je zjistit jako vedlejˇs´ı pro- dukt bin´arn´ıho uzavˇren´ı, pˇri kter´em jsou proch´azeny vˇsechny indexy kaˇzd´eho segmentu.
Algoritmus zkoum´a kaˇzdou sousedn´ı dvojici v seˇrazen´em seznamu a v pˇr´ıpadˇe, kdy se jejich hodnota liˇs´ı o v´ıce neˇz jedna zjiˇst’uje, zda jsou oba pixely hraniˇcn´ı.
Seznam s hraniˇcn´ımi pixely o velikosti Nb nemus´ı b´yt seˇrazen, a tak je tˇreba ho sekvenˇcnˇe proj´ıt; ˇcasov´a sloˇzitost tohoto ´ukonu je tedy O(Nb). Pˇrid´av´an´ı chybˇej´ıc´ıch pixel˚u je pˇri poˇctu tˇechto pixel˚uNmiss moˇzn´e v ˇcaseO(Nmiss). Pˇri celkov´em poˇctu pixel˚u segmentu Ns se tedy ˇcasov´a sloˇzitost m˚uˇze vyˇsplhat na O(NmissNbNs +Ns), nebot’ je tˇreba jeˇstˇe vypoˇc´ıtat Freeman˚uv ˇretˇezov´y k´od segmentu (sloˇzitost diskutov´ana dˇr´ıve). Nav´ıc vˇetˇsinou plat´ı, ˇzeNb Ns
a Nmiss Ns. Zpravidla je ovˇsem poˇcet vyplˇnovan´ych ˇc´ast´ı v ˇr´adu jednotek a algoritmus se tak velmi bl´ıˇz´ı sloˇzitosti O(Ns).
Zjiˇstˇen´ı, zda jeden segment leˇz´ı uvnitˇr jin´eho, je pˇri celkov´em poˇctu seg- ment˚u k moˇzn´y v ˇcase O(k(k+ 1)/2) - je potˇreba porovnat ˇctyˇri mezn´ı hod- noty kaˇzd´e dvojice. Samotn´e odstranˇen´ı pixel˚u menˇs´ıho segmentu z vˇetˇs´ıho je ˇ
casovˇe n´aroˇcn´e, pˇri velikosti mal´eho segmentuNsmall a velk´eho segmentu Nbig je ˇcasov´a sloˇzitost O(NsmallNbig) - pro kaˇzd´y pixel menˇs´ıho objektu je tˇreba zjistit, zda tento n´aleˇz´ı ve vˇetˇs´ım. Naˇstˇest´ı k tomuto jevu doch´az´ı velmi zˇr´ıdka.
3.6.3 V´ ysledky operac´ı
V´ysledky obou v´yˇse popsan´ych operac´ı jsou zn´azornˇeny na pˇr´ıkladu Obr.31.
Na Obr.31(a) je podoba p˚uvodn´ıho segmentu, na prvn´ı pohled je patrn´e velk´e mnoˇzstv´ı r˚uznˇe velik´ych dˇer a tak´e ˇclenitost jeho hranice viz. Obr.31(b). Apli- kace bin´arn´ıho uzavˇren´ı odstran´ı velk´e mnoˇzstv´ı dˇer a z´aroveˇn i vyhlad´ı hra- nice, viz. Obr.31(c) a Obr.31(d). St´ale je vˇsak patrn´a pˇr´ıtomnost otvor˚u, jeˇz jsou odstranˇeny algoritmem k tomu urˇcen´ym Obr.31(e).
3.7 Vyb´ır´ an´ı segment˚ u podle IP Q indexu
Po ´upravˇe segment˚u z pˇredchoz´ı kapitoly je nyn´ı moˇzn´e vybrat v´ysledn´e seg- menty. V´ybˇer prob´ıh´a ve tˇrech f´az´ıch:
1. Prahov´an´ı s n´ızk´ym prahem a zohlednˇen´ım pozice segmentu v obraze 2. Dˇelen´ı velk´ych, tj. pˇr´ıliˇs vysok´ych ˇci pˇr´ıliˇs ˇsirok´ych, segment˚u
3. Prahov´an´ı s vyˇsˇs´ım prahem a bez zohlednˇen´ı pozice segmentu v obraze
3.7.1 V´ ybˇ er kompaktn´ıch segment˚ u - 1. pr˚ uchod
V prvn´ı f´azi je zohlednˇena pozice segmentu, konkr´etnˇe je kontrolov´ano zda segment neleˇz´ı v pˇr´ıliˇsn´e bl´ızkosti hranic obr´azku a pokud ano, je umˇele sn´ıˇzen jeho IP Q index. Tento ´ukon vych´az´ı z myˇslenky, ˇze
”nehezk´e“ (tj. nepˇr´ıliˇs kompaktn´ı) objekty jsou vizu´alnˇe pˇrijatelnˇejˇs´ı, pokud leˇz´ı uprostˇred obr´azku.
K urˇcen´ı vzd´alenosti od hranice je pouˇzito tˇeˇziˇstˇe segmentu CoG (center of gravity), kter´e je vypoˇcteno n´asledovnˇe
(a) P˚uvodn´ı segment (b) Hranice p˚uvodn´ıho segmentu
(c) Segment po aplikaci bin´arn´ıho uzavˇren´ı
(d) Hranice segmentu po aplikaci bin´arn´ıho uzavˇren´ı
(e) Segment po vyplnˇen´ı dˇer Obr. 31Zlepˇsov´an´ı vlastnost´ı segmentu.
CoG= (x0, y0)
x0 = PA
i=1
$s(i) w
%
A y0 =
PA
i=1(s(i) mod w) A
kdesje seznam s indexy segmentu,Aje plocha segmentu (poˇcet prvk˚us) awje ˇs´ıˇrka obr´azku.
IP Q index je pˇren´asoben konstantou k, viz. Obr.32 k=
d0.3 pro objekty v bl´ızkosti hranic
1 jinak
kde d je relativn´ı vzd´alenost tˇeˇziˇstˇe objektu od hranice obr´azku k hodnotˇe mez z Obr.32, konkr´etnˇe minimum vzd´alenost´ıy0 od lev´eho a prav´eho okraje a minimum vzd´alenost´ıx0 od horn´ıho ˇci doln´ıho okraje. Hodnota mez je 20%
celkov´e ˇs´ıˇrky, respektive 15% celkov´e v´yˇsky
Obr. 32 Uprava´ IP Qindexu v bl´ızkosti hranic obr´azku.
k je poˇc´ıt´ano zvl´aˇst’ pro vzd´alenost od lev´eho a prav´eho okraje a zvl´aˇst’ pro vzd´alenost od horn´ıho a spodn´ıho okraje. IP Q index je potom pˇren´asoben menˇs´ı z obou hodnot, jelikoˇz pˇren´asoben´ı obˇema by velmi znev´yhodˇnovalo objekty v roz´ıch obr´azku.
