ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE Fakulta elektrotechnická Katedra kybernetiky
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
České vysoké učení technické v Praze Fakulta elektrotechnická 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
Podˇ ekov´ an´ı 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
Anotace C´ılem t´eto pr´ace je vyvinut´ı aplikace pro zaˇr´ızen´ı s operaˇcn´ım syst´emem Android, 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 geometrick´ ych u ´tvar˚ 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 u ´tvar˚ 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
Obsah ´ 1 Uvod
11
2 Souˇ casn´ y stav
13
3 Algoritmus 3.1 Pˇredzpracov´an´ı obrazu . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Interpolace pomoc´ı nejbliˇzˇs´ıho souseda . . . . . . . . . 3.1.2 Biline´arn´ı interpolace . . . . . . . . . . . . . . . . . . . 3.1.3 Bikubick´a interpolace . . . . . . . . . . . . . . . . . . . 3.1.4 Porovn´an´ı metod . . . . . . . . . . . . . . . . . . . . . 3.2 Segmentace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Zvaˇzovan´e metody . . . . . . . . . . . . . . . . . . . . 3.2.2 Barevn´ y model HSV . . . . . . . . . . . . . . . . . . . 3.2.3 Algoritmus zdol´av´an´ı kopc˚ u (Hill-Climbing) . . . . . . 3.3 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 3.5 Krit´erium pro vyb´ır´an´ı segment˚ u . . . . . . . . . . . . . . . . 3.5.1 V´ ypoˇcet kompaktnosti geometrick´eho tvaru . . . . . . 3.5.2 V´ ypoˇcet IP Q indexu . . . . . . . . . . . . . . . . . . . 3.6 Operace ovlivˇ nuj´ıc´ı IP Q index . . . . . . . . . . . . . . . . . . 3.6.1 Matematick´a morfologie . . . . . . . . . . . . . . . . . 3.6.2 Zaplˇ nov´an´ı velk´ ych dˇer . . . . . . . . . . . . . . . . . . 3.6.3 V´ ysledky operac´ı . . . . . . . . . . . . . . . . . . . . . 3.7 Vyb´ır´an´ı segment˚ u podle IP Q indexu . . . . . . . . . . . . . . 3.7.1 V´ ybˇer kompaktn´ıch segment˚ u - 1. pr˚ uchod . . . . . . . 3.7.2 Rozdˇelen´ı pˇr´ıliˇs velk´ ych segment˚ u . . . . . . . . . . . . 3.7.3 V´ ybˇer kompaktn´ıch segment˚ u - 2. pr˚ uchod . . . . . . . 3.8 Tvorba dodateˇcn´ ych segment˚ u. . . . . . . . . . . . . . . . . . 3.9 Fin´aln´ı u ´prava segment˚ u . . . . . . . . . . . . . . . . . . . . . 3.10 Rozmaz´an´ı vyseparovan´ ych ˇc´ast´ı ve vstupn´ım obr´azku . . . . . . . . . . . . . . . . . . . . . . . . .
15 15 17 17 18 19 20 22 23 24 26 27 31 31 33 37 37 40 42 42 42 45 46 46 48 49
4 Implementace 4.1 Struktura aplikace . . . . . . . . 4.2 Funkˇcn´ı vlastnosti aplikace . . . . 4.2.1 Skl´ad´an´ı skl´adanky . . . . 4.2.2 Zpracov´an´ı obr´azku . . . . 4.2.3 V´ ybˇer vstupn´ıho obr´azku . 4.2.4 Uloˇzen´ı skl´adanky . . . . . 4.2.5 Naˇcten´ı uloˇzen´e skl´adanky
. . . . . . .
53 55 57 57 58 59 59 60
5 Testov´ an´ı 5.1 Okolnosti ovlivˇ nuj´ıc´ı segmentaci obrazu . . . . . . . . . . . . . 5.2 Testov´an´ı s uˇzivateli . . . . . . . . . . . . . . . . . . . . . . .
63 63 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
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
Seznam obr´ azk˚ u 1 2
Animal Jigsaw Puzzles For Kids . . . . . . . . . . . . . . . . . Toddlers Puzzle Woozzle . . . . . . . . . . . . . . . . . . . . .
13 14
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
V´ yvojov´ y diagram algoritmu . . . . . . . . . . . . . . . . . Vliv pˇridˇelen´eho poˇctu pixel˚ u na zachov´an´ı tvar˚ u v obraze Biline´arn´ı interpolace - hodnota nov´eho pixelu . . . . . . . Bikubick´a interpolace - hodnota nov´eho pixelu . . . . . . . Interpolaˇcn´ı j´adra . . . . . . . . . . . . . . . . . . . . . . . Porovn´an´ı interpolaˇcn´ıch metod . . . . . . . . . . . . . . . Barevn´ y model HSV . . . . . . . . . . . . . . . . . . . . . Zn´azornˇen´ı indexace pixel˚ u (obr´azek o rozmˇerech 4x3) . . Hill-Climbing algoritmus . . . . . . . . . . . . . . . . . . . Prvn´ı dˇelen´ı na z´akladˇe velikosti . . . . . . . . . . . . . . . Prostorovˇe neoddˇelen´e segmenty . . . . . . . . . . . . . . . Okol´ı pixelu (o) pouˇzit´e pˇri prostorov´em dˇelen´ı . . . . . . . Pˇr´ıklad oddˇelovan´eho segmentu . . . . . . . . . . . . . . . Hodnoty matice rastr po tˇrech kroc´ıch algoritmu . . . . . Koneˇcn´e hodnoty matice rastr . . . . . . . . . . . . . . . . Freeman˚ uv ˇretˇezov´ y k´od . . . . . . . . . . . . . . . . . . . Pˇr´ıklad popisu hranice objektu . . . . . . . . . . . . . . . Pˇr´ıklad segmentu . . . . . . . . . . . . . . . . . . . . . . . Porovn´an´ı metod na mˇeˇren´ı obvodu . . . . . . . . . . . . . Pˇr´ıklad segmentu jako bin´arn´ıho obrazu . . . . . . . . . . Nejˇcastˇeji pouˇz´ıvan´e strukturn´ı elementy . . . . . . . . . . Posunut´ı o radiusvektor . . . . . . . . . . . . . . . . . . . Transpozice . . . . . . . . . . . . . . . . . . . . . . . . . . Bin´arn´ı dilatace . . . . . . . . . . . . . . . . . . . . . . . . Bin´arn´ı eroze . . . . . . . . . . . . . . . . . . . . . . . . . Pouˇzit´ y strukturn´ı element B . . . . . . . . . . . . . . . . V´ yvojov´ y diagram vyplˇ nov´an´ı segment˚ u . . . . . . . . . . Zmˇena indexu v z´avislosti na hodnotˇe ˇretˇezov´eho k´odu . . Zlepˇsov´an´ı vlastnost´ı segmentu. . . . . . . . . . . . . . . .
16 16 17 18 19 21 23 24 26 27 27 28 29 29 29 34 34 35 36 37 38 38 38 39 39 40 40 41 43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32 33 34 35 36
´ Uprava IP Q indexu v bl´ızkosti hranic obr´azku. . . . . Neˇz´adouc´ı efekt dˇelen´ı velk´ ych segment˚ u. . . . . . . . . V´ yvojov´ y diagram tvorby dodateˇcn´ ych segment˚ u . . . Pˇr´ıklad segmentu jako bin´arn´ıho obrazu . . . . . . . . Rozmaz´an´ı vyseparovan´ ych ˇca´st´ı ve vstupn´ım obr´azku
. . . . .
44 45 47 49 51
37 38
53
39 40 41 42 43 44 45
Pod´ıl operaˇcn´ıch syst´em˚ u na trhu v roce 2014 . . . . . . . . . Srovn´an´ı zastoupen´ı verz´ı OS Android v listopadu 2014 a dubnu 2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hlavn´ı aktivita MainActivity . . . . . . . . . . . . . . . . . . . Ostatn´ı aktivity . . . . . . . . . . . . . . . . . . . . . . . . . . Diagram uˇzit´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . Sekvenˇcn´ı diagram zpracov´an´ı obr´azku . . . . . . . . . . . . . Sekvenˇcn´ı diagram v´ ybˇeru obr´azku . . . . . . . . . . . . . . . Sekvenˇcn´ı diagram uloˇzen´ı skl´adanky . . . . . . . . . . . . . . Sekvenˇcn´ı diagram naˇcten´ı uloˇzen´e skl´adanky . . . . . . . . .
54 55 56 57 58 59 59 61
46 47 48 49
Prototypy vstupn´ıch obr´azk˚ u . . . . . . . . . . . Porovn´an´ı segmentace pro r˚ uzn´e vstupn´ı form´aty Rozliˇsov´an´ı odst´ın˚ u pˇri segmentaci . . . . . . . . Hodnocen´ı uˇzivatel˚ u . . . . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
63 64 65 66
50 51 52 53 54
V´ ychoz´ı obrazovka . . . . . . . Ovl´ad´an´ı aplikace . . . . . . . . Pr˚ ubˇeh zpracov´an´ı . . . . . . . Potvrzen´ı uloˇzen´ı . . . . . . . . Dlaˇzdicov´a galerie pro naˇc´ıt´an´ı .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
73 73 74 74 75
55
Obsah pˇriloˇzen´eho DVD . . . . . . . . . . . . . . . . . . . . .
79
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
´ Kapitola 1. Uvod
11
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 - aplikov´an´ı velmi ˇcasto v´ ypoˇcetnˇe n´aroˇcn´ ych metod poˇc´ıtaˇcov´eho vidˇen´ı na mobiln´ı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 Android, 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´ı.
12
´ Kapitola 1. Uvod
Kapitola 2. Souˇcasn´ y stav
13
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 Google 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 klasick´ 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. 1 Animal 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.
14
Kapitola 2. Souˇcasn´ y stav
Obr. 2 Toddlers 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
15
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 vyseparovan´ 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 segment˚ u spr´avn´e velikosti (tzn. ani pˇr´ıliˇs mal´ ych ani pˇr´ıliˇs velk´ ych) je pot´e porovn´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´ı obraz 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.
16
Kapitola 3. Algoritmus
Pˇredzpracov´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 kompaktn´ıch segment˚ u1.pr˚ uchod
Rozdˇelen´ı velk´ ych segment˚ u
V´ ybˇer kompaktn´ıch segment˚ u2.pr˚ uchod
Tvorba dodateˇcn´ ych segment˚ u
Fin´aln´ı u ´prava segment˚ u
Rozmaz´an´ı vyseparovan´ ych ˇc´ast´ı
Obr. 3 V´ yvojov´ y diagram algoritmu
(a) rozmˇery 633px x 475px
(b) rozmˇery 200px x 150px
Obr. 4 Vliv pˇridˇelen´eho poˇctu pixel˚ u na zachov´an´ı tvar˚ u v obraze
Kapitola 3. Algoritmus
3.1.1
17
Interpolace pomoc´ı nejbliˇ zˇ s´ıho souseda
Jak jiˇz n´azev napov´ıd´a, interpolace pomoc´ı nejbliˇzˇs´ıho souseda (Nearest neighbour 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 intenzity 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. 5 Biline´arn´ı interpolace - hodnota nov´eho pixelu
d´ıky povaze pr˚ umˇerov´an´ı zp˚ usobit rozmaz´an´ı, redukuje efekt ”schod˚ u”pˇredstaven´ y u interpolace pomoc´ı nejbliˇzˇs´ıho souseda.
18
3.1.3
Kapitola 3. Algoritmus
Bikubick´ a interpolace
Bikubick´a interpolace[5][7][8] jeˇstˇe d´ale zpˇresˇ nuje hodnotu intenzity interpolovan´eho pixelu t´ım, ˇze bere v u ´vahu ˇsestn´act sousedn´ıch pixel˚ u z p˚ uvodn´ıho obrazu (viz. Obr.6). Obecnˇe se hodnota intenzity interpolovan´eho pixelu J(r’,c’) vypoˇcte podle vzorce
0
0
J(r , c ) =
2 2 X X
I(r + m, c + n) · Rc (m − 4r) · Rc (4c − n)
m=−1 n=−1
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 4c je moˇzno odeˇc´ıst z Obr.6; funkce Rc (interpolaˇcn´ı funkce ˇci interpolaˇcn´ı j´adro) ud´av´a v´ahy intenzit 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´ı interpolaci a interpolaci pomoc´ı nejbliˇzˇs´ıho souseda.
Obr. 6 Bikubick´ 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
Kapitola 3. Algoritmus
19
pˇredpis neobsahuje ˇza´dnou mocninu tˇr´ı) !2 1 3 x+ 2 2 3 − x2 4 Rc (x) = !2 1 3 x− 2 2 0
1 3 − ≤x≤− 2 2 1 1 − ≤x≤ 2 2 1 3 ≤x≤− 2 2 jinak
Dalˇs´ı ˇcasto pouˇz´ıvan´ ym j´adrem je J´adro CatMull-Rom[7][9], viz. Obr.7(b) 9|x|3 − 15|x|2 + 6 |x| < 1 −3|x|3 + 15|x|2 − 24|x| + 12 1 ≤ |x| < 2 Rc (x) = 0 jinak Bikubick´a interpolace se dok´aˇze vypoˇra´dat s efektem ”schod˚ u”interpolace
(a) Bell
(b) CatMull-Rom Obr. 7 Interpolaˇcn´ı j´adra
pomoc´ı nejbliˇzˇs´ıho souseda a potlaˇcuje i rozmaz´an´ı pˇr´ıtomn´e u biline´arn´ı interpolace. 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´ı u ´rovnˇe
20
Kapitola 3. Algoritmus
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 rozhoduj´ıc´ı atribut pouˇz´ıv´a hodnota intenzity pro jednobarevn´e obrazy a jednotliv´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 nevznikla 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 segmentaˇ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 vzevrubn´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 obraz˚ u zav´ad´ı restrikce, kter´e ˇcasto nemohou b´ yt pouˇzit´e v aplikac´ıch z re´aln´eho svˇeta.[5]
Kapitola 3. Algoritmus
21
(a) P˚ uvodn´ı obraz
(b) Nejbliˇzˇs´ı soused
(c) Biline´arn´ı int.
(d) Bell
(e) Catmul-Rom
Obr. 8 Porovn´an´ı interpolaˇcn´ıch metod
22
Kapitola 3. Algoritmus
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 u ´spˇ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 informaci 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´ı minim´aln´ıho ˇrezu grafu zam´ıtnuta. Dalˇs´ım zvaˇzovan´ ym algoritmem bylo velmi rozˇs´ıˇren´e shlukov´an´ı pomoc´ı kmeans[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 - centroid˚ 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 ˇza´dn´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].
Kapitola 3. Algoritmus
3.2.2
23
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 odpov´ı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. 9 Barevn´ 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
Cmax = max{R0 , G0 , B 0 } Cmin = min{R0 , G0 , B 0 } 4 = Cmax − Cmin
B0 =
B 255
24
Kapitola 3. Algoritmus
H=
0 60 60 60
S=
4=0 ! G0 − B 0 mod 6 4 ! B 0 − R0 +2 4 ! R0 − G0 +4 4
0
Cmax = R0
Cmax = G0 Cmax = B 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, ˇze i -t´ y pixel n´aleˇz´ı j -t´emu shluku. 0 4 8
1 5 9
2 6 10
3 7 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 intervalu 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.
Kapitola 3. Algoritmus
25
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 sousedem. 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 binem. (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 ˇza´dn´ 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 jednorozmˇ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.
26
Kapitola 3. Algoritmus
(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 u ´rovn´ı 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 ˇca´steˇ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 pixel 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 segmentace O(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 pomoc´ı Hill-Climbing algoritmu vytv´aˇr´ı velmi zrnit´e oblasti na hranic´ıch jednotliv´ ych objekt˚ u v obraze. Jedn´a se o mal´e segmenty o velikosti ˇra´dovˇ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 vykon´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 ˇca´sti jsou zn´azornˇeny fialovou barvou na Obr.12(c)). Pˇri celkov´em poˇctu pixel˚ u Np a celkov´em poˇctu segment˚ u k je ˇcasov´a sloˇzitost oddˇelen´ı mal´ ych segment˚ u O(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 porovn´an s prahem (odtud O(k)).
Kapitola 3. Algoritmus
27
(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 u ´vahu 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 ˇca´st).
(a) P˚ uvodn´ı obr´azek
(b) Segmentace
Obr. 13 Prostorovˇe neoddˇelen´e segmenty
28
Kapitola 3. Algoritmus
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´e 1 4 okol´ı) pixelu (bodu) z Obr.14 - o pˇredstavuje zpracov´avan´ y pixel (bod), x zkouman´e okol´ı. x x
x o
x
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 ∀ pixel p 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 segment, celkov´ y poˇcet je tˇechto seznam˚ u je maxim´aln´ı hodnota pole belong 3. Pro ∀l, m takov´a, ˇze rastr(l, m) 6= 0 je do z -t´eho seznamu pˇrid´an index 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 indexy 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.
Kapitola 3. Algoritmus
x
x
29
x x
x x
0 6
x
1 7
2 8
3 9
4 5 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 neobsahuje ˇza´dnou 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 (prozat´ım jednoprvkov´e pole) a hodnota promˇenn´e index je nav´ yˇsena na 2. Dalˇs´ı zpracov´avan´ y bod je na pozici 4 a opˇet jsou v jeho 1 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 3
0 0
1 0
0 0
2 0
0 0
Obr. 16 Hodnoty matice rastr 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 u ´pravˇ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, pole belong zaˇ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; pole belong 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 v rastr 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 3
0 1
1 1
0 0
2 2
0 2
Obr. 17 Koneˇcn´e hodnoty matice rastr
30
Kapitola 3. Algoritmus
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 pixel˚ 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 segmenty, kter´e mohou b´ yt povaˇzov´any za patˇr´ıc´ı pozad´ı. V prvn´ım dˇelen´ı podle velikosti nemohlo k tomuto u ´konu 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´ı velikosti 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 konstantn´ım ˇcase. K u ´pravˇ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˚ u Np a poˇctu zpracov´avan´ ych segment˚ u k je tedy ˇcasov´a sloˇzitost 1. kroku algoritmu O(4kNm Np ). 2. krok algoritmu je oˇcividnˇe ˇcasovˇe konstantn´ı, doch´az´ı v nˇem pouze ke stanoven´ı 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 tedy O(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 ˇra´dech jednotek aˇz nˇekolika m´alo des´ıtek; Nm je zpravidla tak´e v ˇra´dech 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ˇza´douc´ı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.
Kapitola 3. Algoritmus
3.5
31
Krit´ erium pro vyb´ır´ an´ı segment˚ u
C´ılem algoritmu popsan´eho na zaˇca´tku t´eto kapitoly je vybrat z libovoln´eho vstupn´ıho obr´azku ˇc´asti tak, aby tyto ˇca´sti odpov´ıdaly objekt˚ um v obraze. Toho se dos´ahne v´ yˇse popsan´ ym segmentaˇcn´ım algoritmem. Vybran´e ˇca´sti 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 dosti 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 geometrick´eho tvaru (region-based shape descriptors[5]) • Eccentricity
ud´av´a pomˇer d´elky hlavn´ı osy (major axis) a vedlejˇ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 a kruˇznice
podobnost
geometrick´eho
tvaru
Elongatedness nelze snadno (pomoc´ı nejmenˇs´ıho obklopuj´ıc´ıho obd´eln´ıku) vypoˇc´ıtat pro v´ıce zakˇriven´e tvary, coˇz z n´ı dˇel´a nevhodn´eho kandid´ata pro popis 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 numerick´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
32
Kapitola 3. Algoritmus
a rozpozn´av´an´ı vzor˚ u (pattern recognition) v oblasti umˇel´e inteligence, popis 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 geometrick´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 varianty tohoto postupu patˇr´ı napˇr´ıklad pomˇer 4A/P 2 (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
Hodnoty CIP Q n´aleˇz´ı intervalu (0, 1i. Geometrick´e tvary s vyˇsˇs´ı hodnotou CIP 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 referenˇ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 L je 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 u CIP Q n´aleˇz´ı hodnoty CDCM 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 nevyplnˇ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 (A je povrch
Kapitola 3. Algoritmus
33
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 u CBottema ) El =
|A ∩ A0 | |A ∪ A0 |
CBottema i El 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 −n+1 2 √ = 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 geometrick´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 seznamu 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´ yu ´kol); 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 objektu, 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´azev 1 4 okol´ı pouˇz´ıvan´ y v kapitole o oddˇelov´an´ı segment˚ u).
34
Kapitola 3. Algoritmus
(a) 4-konektivita
(b) 8-konektivita
Obr. 18 Freeman˚ uv ˇretˇezov´ y k´od
Od poˇca´teˇ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 ˇca´st 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ˇca´teˇ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 ˇza´dn´ y pixel nem˚ uˇze leˇzet nad startovn´ı pozic´ı a smˇer 4 je vylouˇcen na
Kapitola 3. Algoritmus
35
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 algoritmus 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 4 8 12
1 5 9 13
2 6 10 14
3 7 11 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ˇca´st´ı 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 obvodu P, viz. [20]. Prvn´ı moˇznost´ı je jednoduch´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
36
Kapitola 3. Algoritmus
spoˇc´ıv´a v digitalizaci dat. Je-li souˇca´st´ı hranice rovn´a pˇr´ımka (ve smyslu kolmosti 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, kde e je poˇcet sud´ ych ˇc´ısel v ˇretˇezov´em k´odu a o 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 a o 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 ose y je hodnota odhadnut´eho obvodu, na ose x 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 Vossepoela a Smeulderse a ˇca´rkovanˇ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ˇra´d´a opravdu nejl´epe z pˇredstaven´ ych metod.
Obr. 21 Porovn´ an´ı metod na mˇeˇren´ı obvodu
Vypoˇcten´ı IP Q indexu 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 ˇcase O(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).
Kapitola 3. Algoritmus
3.6
37
Operace ovlivˇ nuj´ıc´ı IP Q index
Jak je patrn´e z Obr.12, segmenty jsou u sv´ ych hranic velmi ˇclenit´e a obsahuj´ı pomˇernˇe velk´e mnoˇzstv´ı r˚ uznˇe velik´ ych otvor˚ u. Pˇred samotn´ ym v´ ybˇerem ˇza´douc´ıch segment˚ u s dostateˇcn´ ym IP Q indexem jsou proto tyto vizu´aln´ı nedostatky 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´ı matematickou 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 2 dvojrozmˇern´eho prostoru cel´ ych ˇc´ısel Z . 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ˇca´tek souˇradnicov´e soustavy, 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ˇca´tku, 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
38
Kapitola 3. Algoritmus × × × ×
×
× ×
×
× × ×
×
×
× ×
×
× ×
×
× ×
×
Obr. 23 Nejˇcastˇeji pouˇz´ıvan´e strukturn´ı elementy
Prvn´ım z pomocn´ ych u ´kon˚ u pouˇz´ıvan´ ych v bin´arn´ı morfologii je translace Xh mnoˇziny X o radiusvektor h dan´a vztahem. Xh = {p ∈ E 2 : p = x + h pro ∀x ∈ X} kde E 2 oznaˇcuje 2D euklidovsk´ y prostor. Pˇr´ıklad je na Obr.24 × × ×
×
×
× ×
×
X
h
× × ×
× ×
Xh
Obr. 24 Posunut´ı o radiusvektor
˘ mnoˇziny B (nˇekdy oznaˇcov´ano Druhou pomocnou operac´ı je transpozice B 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 ∈ E 2 : p = x + b, x ∈ X, b ∈ B}
Kapitola 3. Algoritmus
39
nebo pomoc´ı Minkowsk´eho souˇctu jako sjednocen´ı posunut´ ych mnoˇzin [ X ⊕B = Xb b∈B
Pˇr´ıklad bin´arn´ı dilatace je na Obr.26 × × ×
×
×
× × × X
× × ×
×
× × ×
× ×
X ⊕B
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ˇe X a pokud ano, n´aleˇz´ı bod x tak´e v´ ysledku (tj. erodovan´e mnoˇzinˇe) X B = {p ∈ E 2 : 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 X B = b∈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 u ´zk´ ych z´aliv˚ u. Z´aroveˇ n vˇsak dojde k ”nakynut´ı”objektu a z toho d˚ uvodu je n´aslednˇe pouˇzita bin´arn´ı eroze (s totoˇzn´ ym
40
Kapitola 3. Algoritmus
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ˇra´d´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
Pokraˇcuje se dalˇs´ı dvojic´ı
ne
Oba indexy 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
Kapitola 3. Algoritmus
41
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 ˇza´dn´ 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ˇcet IP Q indexu, 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ˇca´teˇ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 tabulky 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, pozice 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´ı produkt 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 u ´konu je tedy O(Nb ). Pˇrid´av´an´ı chybˇej´ıc´ıch pixel˚ u je pˇri poˇctu tˇechto pixel˚ u Nmiss moˇzn´e v ˇcase O(Nmiss ). Pˇri celkov´em poˇctu pixel˚ u segmentu Ns se tedy ˇcasov´a sloˇzitost m˚ uˇze vyˇsplhat na O(Nmiss Nb Ns + 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´ı, ˇze Nb Ns
42
Kapitola 3. Algoritmus
a Nmiss Ns . Zpravidla je ovˇsem poˇcet vyplˇ novan´ ych ˇca´st´ı v ˇra´du 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 segment˚ u k moˇzn´ y v ˇcase O(k(k + 1)/2) - je potˇreba porovnat ˇctyˇri mezn´ı hodnoty 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 segmentu Nsmall a velk´eho segmentu Nbig je ˇcasov´a sloˇzitost O(Nsmall Nbig ) - 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). Aplikace bin´arn´ıho uzavˇren´ı odstran´ı velk´e mnoˇzstv´ı dˇer a z´aroveˇ n i vyhlad´ı hranice, 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 u ´pravˇe segment˚ u z pˇredchoz´ı kapitoly je nyn´ı moˇzn´e vybrat v´ ysledn´e segmenty. 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 u ´kon 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
Kapitola 3. Algoritmus
43
(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. 31 Zlepˇsov´an´ı vlastnost´ı segmentu.
44
Kapitola 3. Algoritmus
CoG = (x0 , y0 ) $ % s(i) PA i=1 w x0 = A PA i=1 (s(i) mod w) y0 = A kde s je seznam s indexy segmentu, A je plocha segmentu (poˇcet prvk˚ u s) a w je ˇs´ıˇrka obr´azku. IP Q index je pˇren´asoben konstantou k, viz. Obr.32 0.3 pro objekty v bl´ızkosti hranic d k= 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 Q indexu 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.
Kapitola 3. Algoritmus
45
IP Q index kaˇzd´eho segmentu je pot´e porovn´av´an s mezn´ı hodnotou 0.22 a segmenty s menˇs´ım IP Q indexem jsou zahozeny. Pro kaˇzd´ y segment je tˇreba spoˇc´ıtat jeho tˇeˇziˇstˇe, k ˇcemuˇz je tˇreba proj´ıt vˇsechny indexy segmentu. Pˇri celkov´em poˇctu pixel˚ u v segmentu Ns je tedy ˇcasov´a sloˇzitost t´eto operace rovna O(Ns ), jelikoˇz je tˇreba proj´ıt vˇsechny indexy segmentu.
3.7.2
Rozdˇ elen´ı pˇ r´ıliˇ s velk´ ych segment˚ u
N´asleduje dˇelen´ı segment˚ u, kter´e sice splˇ nuj´ı krit´eria omezuj´ıc´ı celkovou plochu, avˇsak jsou bud’ pˇr´ıliˇs ˇsirok´e, a nebo pˇr´ıliˇs vysok´e. Mez´ı pro rozdˇelov´an´ı je 35% celkov´e ˇs´ıˇrky obr´azku a 30% celkov´e v´ yˇsky obr´azku. Segmenty jsou nejprve rozˇrez´any na ˇs´ıˇrku a pot´e pod´elnˇe. Takov´ ymto dˇelen´ım m˚ uˇze ovˇsem doj´ıt k neˇz´adouc´ımu efektu - tvorbˇe prostorovˇe nesouvisl´ ych segment˚ u, viz Obr.33. Je tedy tˇreba opˇet pouˇz´ıt algoritmus pˇredstaven´ y v kapitole 3.4.
(a) Pˇr´ıliˇs velk´ y segment
(b) Hranice dˇelen´ı segmentu
(c) Prostorovˇe nesouvisl´ y segment Obr. 33 Neˇz´adouc´ı efekt dˇelen´ı velk´ ych segment˚ u.
Pˇri celkov´em poˇctu pixel˚ u v segmentu Ns je ˇcasov´a sloˇzitost dˇelen´ı O(2Ns ) - je tˇreba nejprve proj´ıt indexy pˇri dˇelen´ı na ˇs´ıˇrku a pˇriˇradit je novˇe vytvoˇren´emu segmentu a pak je tˇreba obdobnˇe postupovat pˇri dˇelen´ı pod´eln´em. Celkov´a sloˇzitost tohoto kroku je tedy pˇri poˇctu nov´ ych segment˚ u l rovna O(2lNs +lZ), kde Z je sloˇzitost prostorov´eho oddˇelen´ı nesouvisl´ ych segment˚ u (diskutov´ana v pˇr´ısluˇsn´e kapitole).
46
Kapitola 3. Algoritmus
3.7.3
V´ ybˇ er kompaktn´ıch segment˚ u - 2. pr˚ uchod
Po rozdˇelen´ı pˇr´ıliˇs velk´ ych segment˚ u je aplikov´ano druh´e dˇelen´ı segment˚ u podle IP Q indexu. Tentokr´ate nen´ı zohlednˇena pozice objektu v˚ uˇci hranic´ım obrazu, ’ nebot se pˇredpokl´ad´a odstranˇen´ı neˇz´adouc´ıch objekt˚ u pˇri prvn´ım prahov´an´ı. Je vˇsak zv´ yˇsena hranice pro odm´ıtnut´ı - nyn´ı jiˇz mus´ı IP Q index dosahovat alespoˇ n hodnoty 0.28. Hlavn´ı myˇslenkou dvoustupˇ nov´eho prahov´an´ı je d´at ˇsanci velk´ ym objekt˚ um, kter´e sice samy o sobˇe nejsou kdov´ıjak kompaktn´ı, jejich ˇc´asti vˇsak po jejich rozdˇelen´ı jiˇz kompaktn´ı b´ yti mohou. ˇ Casov´a sloˇzitost tohoto kroku je pro jeden segment rovna O(Ns ), kde Ns je celkov´ y poˇcet pixel˚ u v segmentu - je totiˇz tˇreba pˇrepoˇc´ıtat ˇretˇezov´ y k´od, kter´ y se vlivem pˇr´ıpadn´eho dˇelen´ı mohl zmˇenit.
3.8
Tvorba dodateˇ cn´ ych segment˚ u
V pˇr´ıpadˇe nˇekter´ ych vstupn´ıch obr´azku je moˇzn´e, ˇze dosavadn´ım postupem nedojde k vybr´an´ı dostateˇcn´eho mnoˇzstv´ı segment˚ u, nemus´ı b´ yt vybr´an dokonce ani jeden. Napˇr´ıklad u obr´azku tvoˇren´eho ˇctyˇrmi r˚ uznobarevn´ ymi a stejnˇe velk´ ymi ˇctverci vzniknou sice po segmentaci ˇctyˇri kompaktn´ı segmenty, kter´e ovˇsem neprojdou druh´ ym dˇelen´ım na z´akladˇe velikosti (vˇsechny segmenty by mˇely velikost 25% celkov´eho poˇctu pixel˚ u, stanoven´a mez je vˇsak 15%). V takov´ ychto a podobn´ ych situac´ıch je tˇreba nˇejak umˇele dotvoˇrit dalˇs´ı segmenty tak, aby jejich celkov´ y poˇcet byl pˇrijateln´ y. K tomu je pouˇzit postup z Obr.34. Nejprve jsou prozkoum´any takov´e segmenty, kter´e neproˇsly prahov´an´ım jejich IP Q indexu. Konkr´etnˇe je sn´ıˇzena mez pˇrijatelnosti z 0.28 na 0.18. Nejedn´a se tedy prozat´ım o tvorbu nov´ ych v´ yˇrez˚ u. Pokud ani sn´ıˇzen´ı prahu IP Q indexu nepˇrinese k´ yˇzen´ y poˇcet segment˚ u, jsou pouˇzity velk´e segmenty, kter´e byly odstranˇeny dˇr´ıve (kapitola 3.4). Nejsou vˇsak pouˇzity cel´e, dojde pouze k vyˇr´ıznut´ı jejich ˇca´st´ı. Velikost tˇechto v´ yˇrez˚ u je 12% procent celkov´e ˇs´ıˇrky obrazu na 12% celkov´e v´ yˇsky obrazu (zpravidla se tedy jedn´a o obd´eln´ıky). Tvorba jednoho takov´eho v´ yˇrezu prob´ıh´a n´asledovnˇe: 1. N´ahodn´a volba um´ıstˇen´ı v´ yˇrezu (samozˇrejmˇe tak, aby leˇzel uvnitˇr pˇr´ısluˇsn´eho velk´eho segmentu) 2. Kontrola pˇr´ıpustnosti v´ yˇrezu - prot´ın´a-li se v´ yˇrez s jiˇz existuj´ıc´ım segmentem nebo leˇz´ı-li v´ yˇrez pˇr´ıliˇs u okraje obr´azku (tj. ˇc´ast v´ yˇrezu by mˇela b´ yt mimo obr´azek), pokraˇcuje se 1. krokem. 3. Kontrola velikosti v´ yˇrezu - je-li v´ yˇrez pˇr´ıliˇs mal´ y (opˇet menˇs´ı neˇz 4% z celkov´eho poˇctu pixel˚ u), pokraˇcuje se krokem ˇc´ıslo 1. Tento pˇr´ıpad m˚ uˇze nastat, jelikoˇz k odstranˇen´ı velk´ ych segment˚ u doˇslo pˇred vyplˇ nov´an´ım
Kapitola 3. Algoritmus
47
dˇer. V´ yˇrez tedy m˚ uˇze b´ yt velmi dˇerovan´ y a nav´ıc m˚ uˇze leˇzet u okraje velk´eho segmentu, z kter´eho je vytv´aˇren, coˇz znamen´a, ˇze m˚ uˇze b´ yt menˇs´ı neˇz poˇzadovan´ ych 12% obou rozmˇer˚ u. 4. Vyplnˇen´ı v´ yˇrezu (stejn´ y postup jako v kapitole 3.6.2) a pˇrid´an´ı do v´ ysledku.
ano
Dostateˇcn´ y poˇcet segment˚ u
ne
ano
Dostateˇcn´ y poˇcet segment˚ u
ne
Tvorba z velk´ ych segment˚ u
ano
Dostateˇcn´ y poˇcet segment˚ u
ne
Tvorba n´ahodn´ ych segment˚ u
Konec
Segmenty s niˇzˇs´ım IP Q
Obr. 34 V´ yvojov´ y diagram tvorby dodateˇcn´ ych segment˚ u
Snahou je dotvoˇrit vyˇrez´av´an´ım z velk´ ych segment˚ u dostateˇcn´ y poˇcet segment˚ u. Z principu v´ yˇse popsan´eho postupu se to vˇsak nemus´ı vˇzdy podaˇrit. Napˇr´ıklad existuje-li jen jeden velk´ y segment, kter´ y nen´ı nikterak obrovsk´ y, a z kter´eho je tˇreba vytvoˇrit nˇekolik v´ yˇrez˚ u, z´aleˇz´ı uskuteˇcnitelnost tohoto u ´konu na jejich um´ıst’ov´an´ı, kter´e je ovˇsem n´ahodn´e. M˚ uˇze se tedy st´at, ˇze dalˇs´ı v´ yˇrez jiˇz nen´ı moˇzn´e vybrat (v 1. kroku nen´ı moˇzn´e jakkoli vybrat jeho um´ıstˇen´ı tak, aby se neprot´ınal s jiˇz vytvoˇren´ ymi v´ yˇrezy) a popsan´ y algoritmus se zacykl´ı. Z tohoto d˚ uvodu je poˇcet pokus˚ u na tvorbu v´ yˇrezu z velk´eho segmentu omezen. V pˇr´ıpadˇe, ˇze ani po vyˇrez´av´an´ı z velk´ ych segment˚ u nen´ı dostateˇcn´ y poˇcet v´ ysledk˚ u, je pouˇzito vyˇrez´av´an´ı z obr´azku bez omezen´ı. Princip je t´emˇeˇr totoˇzn´ y
48
Kapitola 3. Algoritmus
jako u postupu v pˇredchoz´ım odstavci, neexistuje vˇsak omezen´ı na um´ıstˇen´ı v´ yˇrezu spjat´e s pˇr´ısluˇsnost´ı k segmentu a v´ yˇrezy jsou jiˇz vyplnˇen´e. Pˇri rozumn´em minim´aln´ım poˇctu v´ ysledn´ ych segment˚ u (v ˇr´adu jednotek, konkr´etnˇe byla pouˇzita mez rovna pˇeti) nedojde ani k zacyklen´ı algoritmu a je tedy vˇzdy moˇzn´e vybrat v´ yˇrez. Tˇret´ı f´aze dodateˇcn´e tvorby vˇsak neprodukuje vizu´alnˇe celistv´e v´ yˇrezy.
3.9
Fin´ aln´ı u ´ prava segment˚ u
Na zaˇca´tku algoritmu byl kv˚ uli ˇcasov´ ym u ´spor´am vstupn´ı obraz zmenˇsen, coˇz znamen´a, ˇze i v´ ysledn´e segmenty jsou zmenˇsen´e a je tedy tˇreba je zvˇetˇsit na p˚ uvodn´ı velikost. Opˇet je pouˇzita biline´arn´ı interpolace a pro kaˇzd´ y segment je postupov´ano n´asledovnˇe: 1. Vytvoˇren´ı bin´arn´ıho obrazu ze segmentu. Prozat´ım byl segment reprezentov´an seznamem a je tedy potˇreba z nˇej vytvoˇrit bin´arn´ı obraz. Napˇr´ıklad ze segmentu [1, 2, 5] vznikne (pˇri velikosti p˚ uvodn´ıho obr´azku 4 x 2) bin´arn´ı obraz [0, 1, 1, 0, 0, 1, 0, 0]. 2. Biline´arn´ı interpolac´ı je tento bin´arn´ı obraz pˇreveden zpˇet na p˚ uvodn´ı velikost. 3. Indexy ve zvˇetˇsen´em obraze s nenulovou hodnotou patˇr´ı zvˇetˇsen´emu segmentu (opaˇcn´ ym zp˚ usobem neˇz v 1. kroku je z obrazu vytvoˇren seznam). Rychlejˇs´ım postupem by zajist´e bylo vytvoˇrit jeden bin´arn´ı“ obraz ze vˇsech ” segment˚ u, kde kaˇzd´emu segmentu by bylo pˇriˇrazeno rozd´ıln´e cel´e ˇc´ıslo. Probl´em by ovˇsem nastal u segment˚ u, kter´e se pˇred zvˇetˇsen´ım dot´ ykaj´ı. Napˇr´ıklad u dot´ ykaj´ıc´ıch se segment˚ u ˇc´ıslo 1 a 7 se po zvˇetˇsen´ı na jejich spoleˇcn´ ych hranic´ıch mohou vyskytovat hodnoty v intervalu h1, 7i a nen´ı tedy jasn´e, jak tyto hraniˇcn´ı pixely pˇriˇrazovat. Doposud byl seznam kaˇzd´eho segmentu obyˇcejn´ ym v´ yˇctem index˚ u, kter´e segmentu n´aleˇzely. Pro zmenˇsen´ y obr´azek se nejednalo o podstatn´ y probl´em, pro segmenty obr´azku p˚ uvodn´ı (vˇetˇs´ı) velikosti doch´az´ı vˇsak k tvorbˇe obrovsk´ ych v´ yˇct˚ u a pˇritom je vˇetˇsina obsaˇzen´e informace pˇrebyteˇcn´a. K popisu segment˚ u je tedy pouˇzita datov´a struktura, kter´a popisuje souvisl´e ˇc´asti jako dvojici ve form´atu od-do“. Pˇresnˇeji se jedn´a o pole [Z1 , K1 , Z2 , K2 , Z3 , K3 , ...], kde ” dvojice Zi , Ki znamen´a, ˇze segment obsahuje vˇsechny hodnoty v intervalu hZi , Ki i.Tato struktura je d´ale vysvˇetlena na n´asleduj´ıc´ım pˇr´ıkladu. Je uvaˇzov´an obr´azek s rozmˇery 5x5, viz Obr.35, a segment dan´ y v´ yˇctem index˚ u [0, 1, 2, 5, 6, 7, 11, 12, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24]. Tento segment lze
Kapitola 3. Algoritmus
49 × × ×
× × × × ×
× × × × ×
× ×
× × ×
Obr. 35 Pˇr´ıklad segmentu jako bin´arn´ıho obrazu
u ´spornˇeji zapsat jako [0, 2, 5, 7, 11, 12, 14, 14, 15, 19, 21, 24], kde napˇr´ıklad dvojice 15,19 znamen´a: segment obsahuje vˇsechny indexy poˇc´ınaje 15, konˇce 19.
3.10
Rozmaz´ an´ı vyseparovan´ ych ˇ c´ ast´ı ve vstupn´ım obr´ azku
Posledn´ı f´az´ı algoritmu je oznaˇcen´ı vyseparovan´ ych oblast´ı ve vstupn´ım obrazu, k ˇcemuˇz je pouˇzito rozmaz´an´ı obrazu. Pˇresnˇeji je vytvoˇren nov´ y obraz, kter´ y je rozmazanou variantou p˚ uvodn´ıho a ˇca´sti v p˚ uvodn´ım obraze patˇr´ıc´ı segmentu jsou nahrazeny odpov´ıdaj´ıc´ımi ˇca´stmi z t´eto rozmazan´e varianty. K rozmaz´an´ı obrazu pouˇz´ıv´a konvoluce ∗, kterou lze vyj´adˇrit vztahem[5] X (f ∗ h)(i, j) = h(i − m, j − n)f (m, n) m,n∈O
kde O je okol´ı souˇcasn´e pozice, h je konvoluˇcn´ı j´adro (t´eˇz konvoluˇcn´ı maska). Pˇri volbˇe Gaussovy funkce jako j´adra (tak´e oznaˇcov´ano jako Weierstrassova transformace)[24] dojde k poˇzadovan´emu rozmaz´an´ı. Pˇri pouˇzit´ı takov´eho j´adra o polomˇeru r je ˇcasov´a sloˇzitost t´eto operace pˇri celkov´em poˇctu pixel˚ u n rovna 2 O(r n)[25]. K urychlen´ı t´eto operace lze vyuˇz´ıt separability v´ yˇse zm´ınˇen´eho dvojrozmˇern´eho j´adra, tzn. ˇze j´adro lze vyj´adˇrit jako souˇcin dvou jednorozmˇern´ ych jader[26] a pot´e postupnˇe pouˇz´ıt jednorozmˇernou konvoluci[27](tj. nejdˇr´ıve je pouˇzita jednorozmˇern´a konvoluce podle ˇr´adk˚ u a na v´ ysledek je pouˇzita jednorozmˇern´a konvoluce podle sloupc˚ u) danou vztahem X (f ∗ h)(i) = h(i − m)f (m) m∈O
=
X
h(i)f (i − m)
m∈O
ˇ Casov´ a sloˇzitost se zmenˇs´ı na O(2rn)[24]. K dalˇs´ımu zrychlen´ı lze vyuˇz´ıt faktu, ˇze aproximovat konvoluci gaussovsk´ ym filtrem lze opˇetovn´ ym konvolov´an´ım
50
Kapitola 3. Algoritmus
s uniformn´ım konvoluˇcn´ım j´adrem.[27] Uniformn´ı konvoluˇcn´ı j´adro je tak´e separabiln´ı a nav´ıc lze hodnoty konvoluce vypoˇc´ıtat v line´arn´ım ˇcase[25], nebot’ pro sousedn´ı body i a i + 1 pˇri hodnot´ach konvoluˇcn´ıho j´adra w plat´ı, ˇze X (f ∗ h)(i) = h(i)f (i − m) m∈O
=
i2 X
wf (i − m)
i=i1
= wf (i1 − m) +
i2 X
wf (i − m)
i=i1 +1
(f ∗ h)(i + 1) =
X
h(i)f (i − m)
m∈O
=
iX 2 +1
wf (i − m)
i=i1 +1
= wf (i2 − m) +
i2 X
wf (i − m)
i=i1 +1
a hodnotu v bodˇe i + 1 lze tedy v line´arn´ım ˇcase (pomoc´ı jednoho pˇriˇcten´ı a jednoho odeˇcten´ı) z´ıskat z hodnoty v bode i jako (f ∗ h)(i + 1) = (f ∗ h)(i) − wf (i1 − m) + wf (i2 − m) ˇ Casov´ a sloˇzitost rozmaz´an´ı je potom nez´avisl´a na velikosti (uniformn´ıho) j´adra (velikost j´adra byla stanovena na sedm) a pˇri trojn´asobn´em konvolov´an´ı, kter´e bylo pouˇzito pro aproximaci, je rovna O(6n). Nahrazen´ı segment˚ u v p˚ uvodn´ım obraze odpov´ıdaj´ıc´ımi ˇca´stmi rozmazan´eho obrazu je moˇzn´e v jednom pr˚ uchodu (pokud pixel patˇr´ı segmentu je nahrazen pokud mu nepatˇr´ı, pokraˇcuje se dalˇs´ım pixelem), coˇz zvˇetˇsuje celkovou sloˇzitost na O(7n). Hranice kaˇzd´eho segmentu jsou pro snadnˇejˇs´ı rozpozn´an´ı d´ale oznaˇceny (tyrkysovˇe), k ˇcemuˇz je tˇreba spoˇc´ıtat ˇretˇezov´ y k´od kaˇzd´eho segmentu. Pˇri celkov´em poˇctu segment˚ u k a poˇctu pixel˚ u v segmentu Ns je tedy celkov´a sloˇzitost rozmaz´an´ı vyseparovan´ ych ˇc´ast´ı ve vstupn´ım obr´azku rovna O(7n + kNs ). Porovn´an´ı p˚ uvodn´ıho obr´azku a obr´azku s rozmazan´ ymi ˇca´stmi na m´ıstˇe segment˚ u je na Obr.36
Kapitola 3. Algoritmus
51
(a) P˚ uvodn´ı obr´azek
(b) Obr´ azek s rozmazan´ ymi ˇc´astmi na m´ıstˇe segment˚ u Obr. 36 Rozmaz´an´ı vyseparovan´ ych ˇc´ast´ı ve vstupn´ım obr´azku
52
Kapitola 3. Algoritmus
Kapitola 4. Implementace
53
Kapitola 4 Implementace V´ ysledn´a aplikace implementuj´ıc´ı algoritmus popsan´ y v pˇredchoz´ı kapitole byla navrˇzena a implementov´ana pro operaˇcn´ı syst´em Android[28][29]. Hlavn´ım krit´eriem pro v´ ybˇer tohoto operaˇcn´ıho syst´emy bylo jeho znaˇcn´e rozˇs´ıˇren´ı v roce 2014 byl Android pˇr´ıtomen na 48.61% procentech (viz. Obr.37) zaˇr´ızen´ı (mobiln´ı telefony, tablety a osobn´ı poˇc´ıtaˇce) a na rok 2015 je dokonce pˇredpov´ıd´an n´ar˚ ust na 58.90%[30]. Pod´ıl na trhu mobiln´ıch zaˇr´ızen´ı je dokonce jeˇstˇe mnohem vyˇsˇs´ı - pˇribliˇznˇe 80%[31]. iOS Windows
14.00%
26.34%
11.05%
48.61%
others Android
Obr. 37 Pod´ıl operaˇcn´ıch syst´em˚ u na trhu v roce 2014
Spoleˇcnost Google, kter´a operaˇcn´ı syst´em Android spravuje, vyd´av´a pˇribliˇznˇe kaˇzd´ ych ˇsest aˇz devˇet mˇes´ıc˚ u inkrement´aln´ı upgrade, a tak doch´az´ı ke znaˇcn´e
54
Kapitola 4. Implementace
roztˇr´ıˇstˇenosti trhu, kdy nov´e verze operaˇcn´ıho syst´emu postupnˇe vytlaˇcuj´ı starˇs´ı verze, viz Obr.38[32][33].
Verze 2.2 2.3.3 - 2.3.7 4.0.3 - 4.0.4 4.1.x 4.2.x 4.3 4.4 5.0 5.1
K´odov´e oznaˇcen´ı Froyo Gingerbread Ice Cream Sandwich Jelly Bean KitKat Lollipop
API 8 10 15 16 17 18 19 21 22
listopad 2014
Pod´ıl v procentech listopad 2014 duben 2015 0.6 0.4 9.8 6.4 8.5 5.7 22.8 16.5 20.8 18.6 7.3 5.6 30.2 41.4 5.0 0.4 duben 2015
API 8
API 16
API 19
API 10
API 17
API 21
API 15
API 18
API 22
Obr. 38 Srovn´ an´ı zastoupen´ı verz´ı OS Android v listopadu 2014 a dubnu 2015
V dobˇe poˇc´atku v´ yvoje (zaˇca´tek podzimu 2014) napˇr´ıklad jeˇstˇe neexistovala verze 5.0, kter´a je nyn´ı jiˇz na 5% zaˇr´ızen´ı. Aplikace je tedy dimenzov´ana pro zaˇr´ızen´ı s verz´ı operaˇcn´ıho syst´emu Android 4.x (minim´aln´ı je API verze 14, coˇz odpov´ıd´a Android 4.0-4.0.2 Ice Cream Sandwich). V´ yvoj prob´ıhal v programovac´ım jazyce Java.
Kapitola 4. Implementace
4.1
55
Struktura aplikace
Z´akladn´ımi stavebn´ımi kameny kaˇzd´e android´ı aplikace jsou[34]: • Aktivity (Activities). Uˇzivatelsk´e rozhran´ı aplikace je tvoˇreno aktivitami, kter´e by se daly pˇripodobnit okn˚ um ˇci dialog˚ um bˇeˇzn´e aplikace pro stoln´ı poˇc´ıtaˇce. Myˇslenkou aplikace pro Android je velk´e mnoˇzstv´ı jednoduch´ ych aktivit, mezi kter´ ymi se v r´amci aplikace pˇrech´az´ı (je zde hojnˇe vyuˇz´ıv´ano tlaˇc´ıtko Zpˇet natolik bˇeˇzn´e pro chytr´e telefony i tablety). • Sluˇzby (Services). Aktivity maj´ı zpravidla kr´atkou dobu ˇzivota a jsou ˇcasto ukonˇcov´any (napˇr´ıklad jin´ ymi aktivitami), proto existuj´ı sluˇzby, kter´e jsou urˇceny k operac´ım prob´ıhaj´ıc´ım na pozad´ı“. Pˇr´ıkladem sluˇzby ” m˚ uˇze b´ yt pˇrehr´av´an´ı hudby na pozad´ı - hudba hraje, i kdyˇz aktivita, kter´a pˇrehr´av´an´ı odstartovala jiˇz nemus´ı nutnˇe existovat. • Poskytovatel´e obsahu (Content providers). Poskytovatel´e obsahu umoˇzn ˇuj´ı sd´ılen´ı dat mezi aplikacemi zaˇr´ızen´ı, k ˇcemuˇz v´ yvojov´ y model pro Android pˇr´ımo nab´ad´a. Jedn´a se napˇr´ıklad o lok´aln´ı datab´aze. • Z´amˇery (Intents). Z´amˇery jsou syst´emov´e zpr´avy, pomoc´ı kter´ ych operaˇcn´ı syst´em informuje aplikace o r˚ uzn´ ych ud´alostech (napˇr´ıklad datov´e pˇrenosy). Nav´ıc se z´amˇery nepracuje pouze operaˇcn´ı syst´em, ale i samotn´e aplikace - napˇr´ıklad vytvoˇren´ı nov´e aktivity prob´ıh´a pomoc´ı z´amˇeru. Uˇzivatelsk´e rozhran´ı se skl´ad´a ze tˇr´ı aktivit. Pˇresnˇeji ˇreˇceno ze ˇctyˇr aktivit, jenˇze jednou z nich je galerie, kterou poskytuje pˇr´ımo operaˇcn´ı syst´em a jej´ı vzhled je tedy z´avisl´ y na konkr´etn´ı verzi Androidu, proto zde nebude d´ale (pˇr´ıliˇs) diskutov´ana.
(a) Sch´ema hlavn´ı aktivity
(b) Screenshot hlavn´ı aktivity
Obr. 39 Hlavn´ı aktivita MainActivity
56
Kapitola 4. Implementace
Hlavn´ı aktivita aplikace MainActivity (viz. Obr.39) se skl´ad´a ze tˇr´ı ˇca´st´ı: • Vˇetˇsinu aktivity zab´ır´a plocha pro zobrazen´ı vstupn´ıho obr´azku, kter´ y m˚ uˇze vyuˇz´ıt celou ˇs´ıˇrku a 80% v´ yˇsky cel´e obrazovky. Po dokonˇcen´ı algoritmu je vstupn´ı obr´azek nahrazen svou rozmazanou variantou s vyznaˇcen´ ymi hranicemi vyjmut´ ych ˇca´st´ı, viz Obr.36(b). • V prav´e doln´ı ˇca´st´ı je plocha pro jednotliv´e d´ılky skl´adanky. • Aplikace se ovl´ad´a z lev´e doln´ı ˇc´asti - moˇznost Start, po jej´ımˇz v´ ybˇeru dojde ke spuˇstˇen´ı algoritmu z kapitoly 3, a moˇznost Menu, jeˇz slouˇz´ı k zobrazen´ı dalˇs´ıch funkcionalit. Menu aplikace, viz. Obr.40(a), je tvoˇreno ˇctyˇrmi tlaˇc´ıtky v lev´e doln´ı ˇca´sti, jejichˇz funkce je n´asleduj´ıc´ı: • Select - zvolen´ı nov´eho vstupn´ıho obr´azku • Save - uloˇzen´ı zpracovan´eho vstupn´ıho obr´azku • Load - naˇcten´ı dˇr´ıve uloˇzen´eho vstupn´ıho obr´azku • Menu - opuˇstˇen´ı menu Zbytek obrazovky je zast´ınˇen´ım“ hlavn´ı aktivity (pr˚ uhlednost 50%) a nem´a ” ˇza´dn´e funkˇcn´ı vyuˇzit´ı.
(a) MenuActivity
(b) LoadActivity Obr. 40 Ostatn´ı aktivity
Posledn´ı aktivitou je v´ ybˇer uloˇzen´eho obr´azku pˇri jeho naˇc´ıt´an´ı - LoadActivity, viz. Obr.40(b). Jedn´a se o dlaˇzdicovou galerii s miniaturami uloˇzen´ ych obr´azk˚ u, kter´a m´a stejnˇe jako MenuActivity pr˚ uhledn´e pozad´ı (celkov´a pr˚ uhlednost je sn´ıˇzena o dalˇs´ıch 30%, tj. na 20%).
Kapitola 4. Implementace
4.2
57
Funkˇ cn´ı vlastnosti aplikace
Pˇr´ıpady uˇzit´ı aplikace jsou zn´azornˇeny na diagramu uˇzit´ı (use case diagram) na Obr.41.
Obr. 41 Diagram uˇzit´ı
Uˇzivatel m´a moˇznost: • Skl´adat st´avaj´ıc´ı skl´adanku • Zpracovat vybran´ y obr´azek, tj. vytvoˇrit z nˇej skl´adanku • Vstoupit do menu a – Vybrat nov´ y obr´azek ke zpracov´an´ı – Uloˇzit st´avaj´ıc´ı skl´adanku – Naˇc´ıst dˇr´ıve uloˇzenou skl´adanku – Odej´ıt z menu
4.2.1
Skl´ ad´ an´ı skl´ adanky
Samotn´e skl´ad´an´ı, coˇz je hlavn´ım smyslem cel´e aplikace, je moˇzn´e po zpracov´an´ı vstupn´ıho obr´azku nebo po naˇcten´ı dˇr´ıve uloˇzen´ ych dat. Uˇzivatel akc´ı ’ uchopit a t´ahnout“ ( Drag & Drop“) umist uje jednotliv´e d´ılky na jejich ” ” pˇr´ısluˇsn´e pozice. Po u ´spˇeˇsn´em um´ıstˇen´ı je d´ılek odstranˇen z hrac´ı plochy, v obr´azku je nahrazena rozmazan´a ˇca´st p˚ uvodn´ı (tj. nerozmazanou) a z´aroveˇ n dojde i k odstranˇen´ı tyrkysov´ ych hranic. Po u ´spˇeˇsn´em um´ıstˇen´ı vˇsech d´ılk˚ u vyd´a aplikace kr´atk´ y oznamovac´ı t´on.
58
4.2.2
Kapitola 4. Implementace
Zpracov´ an´ı obr´ azku
Vˇsechny v´ ypoˇcetnˇe sloˇzitˇejˇs´ı operace je nutno prov´adˇet mimo hlavn´ı UI vl´akno (v tomto pˇr´ıpadˇe MainActivity), nebot’ prov´ad´ı-li toto vl´akno jednu operaci delˇs´ı dobu (nˇekolik m´alo vteˇrin), zobraz´ı android ANR chybovou hl´aˇsky Apli” kace neodpov´ıd´a“ ( Application not responding“) a dojde k ukonˇcen´ı aplikace. ” Proto drtiv´a vˇetˇsina u ´kon˚ u prob´ıh´a ve sv´ ych vlastn´ıch vl´aknech, kter´e jsou v pˇr´ıpadˇe t´eto aplikace spouˇstˇeny v´ yhradnˇe z hlavn´ıho UI vl´akna. V´ yjimkou tomu nen´ı ani vytvoˇren´ı skl´adanky z vybran´eho obr´azku, jehoˇz sekvenˇcn´ı diagram je na Obr.42.
Obr. 42 Sekvenˇcn´ı diagram zpracov´an´ı obr´azku
Pˇred samotn´ ym spuˇstˇen´ım v´ ypoˇcetn´ıch vl´aken jsou zablokov´ana tlaˇc´ıtka Start, kter´ ym je tento u ´kon spuˇstˇen, a Menu. Nejprve je spuˇstˇeno vl´akno ImageProcessing, kter´e zpracuje obr´azek (pˇredan´ y vl´aknu ve formˇe bitmapy - objekt Bitmap) podle dˇr´ıve popsan´eho algoritmu, nedojde vˇsak prozat´ım k rozmaz´an´ı vyjmut´ ych ˇc´ast´ı. ImageProcessing pˇred sv´ ym ukonˇcen´ım odeˇsle hlavn´ımu UI vl´aknu v´ ysledky - seznam index˚ u kaˇzd´eho v´ yˇrezu, seznam index˚ u hranice kaˇzd´eho v´ yˇrezu a informace o um´ıstˇen´ı v´ yˇrezu ve vstupn´ım obr´azku. Tyto v´ ysledky spoleˇcnˇe se vstupn´ım obr´azkem jsou pˇred´any druh´emu vl´aknu (ImageButtons), kter´e na jejich z´akladˇe vytvoˇr´ı UI prvky pro kaˇzd´ y v´ yˇrez a poˇsle je zpˇet hlavn´ımu vl´aknu, ve kter´em jsou tyto prvky um´ıstˇeny na obrazovku. Posledn´ım vl´aknem je Blurring, ve kter´em, jak jiˇz n´azev napov´ıd´a, dojde na z´akladˇe v´ ysledk˚ u z ImageProcessing k rozmaz´an´ı pˇr´ısluˇsn´ ych ˇca´st´ı ve zpracov´avan´em obr´azku. Uˇzivatel je v pr˚ ubˇehu v´ ypoˇct˚ u informov´an pomoc´ı progress baru o aktu´aln´ım stavu v´ ypoˇctu. Po skonˇcen´ı vˇsech tˇr´ı vl´aken je zpˇr´ıstupnˇena moˇznost Menu v MainActivity.
Kapitola 4. Implementace
4.2.3
59
V´ ybˇ er vstupn´ıho obr´ azku
Sekvenˇcn´ı diagram v´ ybˇeru obr´azku ke zpracov´an´ı je na Obr.43. Uˇzivatel nejdˇr´ıve stiskne tlaˇc´ıtko Menu, ˇc´ımˇz dojde v aktivitˇe MainActivity k vytvoˇren´ı nov´eho z´amˇeru, kter´ y spust´ı aktivitu MenuActivity.
Obr. 43 Sekvenˇcn´ı diagram v´ ybˇeru obr´azku
V´ ybˇerem Select v MenuActivity dojde, opˇet pomoc´ı z´amˇeru, k otevˇren´ı nativn´ı android´ı galerie, kde si uˇzivatel m˚ uˇze vybrat poˇzadovan´ y vstup. Po vybr´an´ı putuje v obr´acen´em poˇrad´ı cesta vstupn´ıho obr´azku, kter´ y je v MainActivity um´ıstˇen na plochu jemu urˇcenou (dojde k upraven´ı velikosti obr´azku tak, aby byl zachov´an pomˇer stran a z´aroveˇ n aby byla vyuˇzita co moˇzn´a nejvˇetˇs´ı ˇca´st t´eto plochy). Po naˇcten´ı nov´eho vstupu je zpˇr´ıstupnˇena moˇznost Start.
4.2.4
Uloˇ zen´ı skl´ adanky
Sekvenˇcn´ı diagram uloˇzen´ı skl´adanky je na Obr.44. Pˇr´ıstup do menu prob´ıh´a stejnˇe jako pˇri vyb´ır´an´ı nov´eho vstupu. Stisknut´ım tlaˇc´ıtka Save je hlavn´ımu UI vl´aknu ozn´ameno, ˇze uˇzivatel chce uloˇzit st´avaj´ıc´ı skl´adanku. Hlavn´ı UI vl´akno n´aslednˇe zablokuje tlaˇc´ıtka Menu a Start a spust´ı vl´akno urˇcen´e pr´avˇe tomuto u ´konu.
Obr. 44 Sekvenˇcn´ı diagram uloˇzen´ı skl´adanky
60
Kapitola 4. Implementace
Kaˇzd´a skl´adanka je uloˇzena ve formˇe ˇsesti soubor˚ u s unik´atn´ım prefixem (souˇcasn´ y ˇcas v milisekund´ach) a n´asleduj´ıc´ımi koncovkami (prvn´ı soubor m´a pˇr´ıponu .png, ostatn´ı jsou bez pˇr´ıpony): • PNG soubor bez koncovky - obr´azek s rozmazan´ ymi a ohraniˇcen´ ymi pˇr´ısluˇsn´ ymi ˇc´astmi, slouˇz´ı pˇri naˇc´ıt´an´ı uloˇzen´ ych skl´adanek • bl - v´ yˇcet RGBA hodnot pixel˚ u obr´azku (Android k´oduje pro kaˇzd´ y pixel tyto hodnoty do jednoho bajtu, kaˇzd´a sloˇzka zab´ır´a 8 bit˚ u), kter´ y m´a vyjmut´e ˇca´sti rozmazan´e • sg - v´ yˇcet RGBA hodnot pixel˚ u kaˇzd´eho v´ yˇrezu (jednotliv´e segmenty jsou oddˇeleny znakem x) • pr - seznam UI parametr˚ u kaˇzd´eho v´ yˇrezu (parametry jednotliv´ ych segment˚ u jsou opˇet oddˇeleny znakem x) • in - bounding box kaˇzd´eho v´ yˇrezu • pb - vz´ajemn´a poloha v´ yˇrez˚ u Po naˇcten´ı je opˇet zpˇr´ıstupnˇeno tlaˇc´ıtko Menu a MainActivity zobraz´ı potvrzovac´ı dialog. Ukl´ad´an´ı skl´adanky je moˇzn´e pouze dokonˇcen´ı zpracov´an´ı obr´azku a nebo po naˇcten´ı uloˇzen´e skl´adanky; pokud je aktu´aln´ı skl´adanka alespoˇ n ˇc´asteˇcnˇe sloˇzen´a, tlaˇc´ıtko Save je zablokov´ano.
4.2.5
Naˇ cten´ı uloˇ zen´ e skl´ adanky
Naˇcten´ı uloˇzen´e skl´adanky (Obr.45) je v´ıcem´enˇe reverzn´ı operace k jej´ımu uloˇzen´ı. Po v´ ybˇeru moˇznosti Load v MenuActivity dojde ke spuˇstˇen´ı LoadActivity, kde si uˇzivatel m˚ uˇze vybrat jednu z uloˇzen´ ych skl´adanek (kaˇzd´a skl´adanka je reprezentov´ana zmenˇseninou PNG souboru vytvoˇren´eho pˇri jej´ım ukl´ad´an´ı). Cesta uloˇzen´eho souboru, konkr´etnˇe v´ yˇse zm´ınˇen´ y prefix, je pˇres MenuActivity zasl´ana MainActivity, kter´a spust´ı vl´akno Loading. To na z´akladˇe cesty naˇcte informace z pˇr´ısluˇsn´ ych soubor˚ u a pˇred´a je zpˇet hlavn´ımu UI vl´aknu, kter´e podle nich vytvoˇr´ı v aplikaci skl´adanku.
Kapitola 4. Implementace
61
Obr. 45 Sekvenˇcn´ı diagram naˇcten´ı uloˇzen´e skl´adanky
Bˇehem naˇc´ıt´an´ı jsou opˇet zablokov´ana obˇe tlaˇc´ıtka v MainActivity a po jeho dokonˇcen´ı je zpˇr´ıstupnˇeno tlaˇc´ıtko Menu.
62
Kapitola 4. Implementace
Kapitola 5. Testov´an´ı
63
Kapitola 5 Testov´ an´ı Vzhledem k c´ılov´e skupinˇe, pro kterou byla aplikace vyv´ıjena, byl algoritmus (konkr´etnˇe jeho parametry) navrhov´an pro specifick´ y typ vstupn´ıch obr´azk˚ u. Pˇredpokl´adaj´ı se jednoduch´e obr´azky, tvoˇren´e ze zˇreteln´ ych a jednoduch´ ych objekt˚ u (geometrick´ ych tvar˚ u), viz. Obr.46. Algoritmus si pˇresto dok´aˇze poradit s jak´ ymkoli vstupn´ım obr´azkem.
(a) Prototyp dobr´eho“ vstupn´ıho ” obr´ azku
(b) Prototyp ˇspatn´eho“ vstupn´ıho ” obr´azku
Obr. 46 Prototypy vstupn´ıch obr´azk˚ u
5.1
Okolnosti ovlivˇ nuj´ıc´ı segmentaci obrazu
V´ ysledek algoritmu je z´avisl´ y pˇredevˇs´ım na segmentaci obrazu, kter´a je do znaˇcn´e m´ıry ovlivnˇena form´atem vstupn´ıho souboru. Jako experiment demonstruj´ıc´ı tuto z´avislost byl vytvoˇren syntetick´ y obr´azek, Obr.47(a), kter´ y byl uloˇzen ve vˇsech tˇrech bˇeˇzn´ ych form´atech, tj. PNG, JPG (JPEG) a GIF.
64
Kapitola 5. Testov´an´ı
Kaˇzd´a varianta byla pot´e algoritmem zpracov´ana a bylo dosaˇzeno n´asleduj´ıc´ıch z´avˇer˚ u. PNG je bezeztr´atov´ y form´at, coˇz znamen´a, ˇze komprese nesniˇzuje kvalitu obr´azku[35]. Jak je patrn´e z Obr.47(d) (segmenty jako odst´ıny ˇsedi), nedoch´az´ı ke vzniku zrnit´ ych oblast´ı na hranic´ıch objekt˚ u popsan´ ych v kapitole 3.3. Segmenty maj´ı ostr´e hranice a jedin´e artefakty vznikaj´ıc´ı segmentac´ı jsou u ´seˇckovit´eho charakteru a nen´ı jich pˇr´ıliˇs. Segmentac´ı vzniklo 17 segment˚ u, 7 z nich bylo hned po segmentaci odstranˇeno pro nedostateˇcnou velikost (v´ yˇse zm´ınˇen´e u ´seˇckovit´e artefakty na hranic´ıch objekt˚ u).
(a) Origin´ aln´ı obr´ azek
(b) GIF
(c) JPG
(d) PNG
Obr. 47 Porovn´ an´ı segmentace pro r˚ uzn´e vstupn´ı form´aty
JPG soubory pouˇz´ıvaj´ı ztr´atovou kompresi, takˇze doch´az´ı k patrn´e ztr´atˇe kvality pˇri pˇribl´ıˇzen´ı[35]. Segmentac´ı JPG soubor˚ u, viz. Obr.47(c), vznikaj´ı zrnit´e oblasti na hranic´ıch objekt˚ u pˇresnˇe tak, jak bylo pops´ano v kapitole 3.3, d˚ usledkem ˇcehoˇz mohou m´ıt segmenty ˇclenit´e hranice. Segmentac´ı vzniklo 36 segment˚ u, 26 bylo pro nedostateˇcnou velikost z´ahy odstranˇeno (celkov´ y poˇcet d´ale zpracov´avan´ ych segment˚ u tedy z˚ ustal stejn´ y jako u PNG souboru).
Kapitola 5. Testov´an´ı
65
GIF form´at pouˇz´ıv´a pouze paletu 256 barev. Barvy mimo tuto paletu jsou zaokrouhlov´any tak, aby v n´ı leˇzely, ˇc´ımˇz v obraze vznikaj´ı skvrnit´e oblasti[35]. Tyto oblasti jsou patrn´e i pˇri segmentaci, Obr.47(b), kdy doch´az´ı k roztˇr´ıˇstˇen´ı objekt˚ u, kter´e u pˇredchoz´ıch dvou form´at˚ u z˚ ustaly celistv´e. Segmentac´ı vzniklo 25 segment˚ u, ale 17 z nich bylo kv˚ uli poˇzadavk˚ um na minim´aln´ı velikost odstranˇeno a algoritmus tedy pokraˇcoval s m´enˇe segmenty neˇz tomu bylo o soubor˚ u PNG a JPG. Segmenty nav´ıc mohou m´ıt ˇclenit´e hranice. Segmentace je mimo form´atu vstupn´ıho souboru ovlivnˇena tˇremi parametry - poˇctem bin˚ u v trojrozmˇern´em histogramu. Volbou pomˇeru bin˚ u 15:7:7 (pro sloˇzky H:S:V) ovˇsem dojde k m´ırn´emu podsegmentov´an´ı, coˇz je patrn´e z Obr.48. Konkr´etnˇe nejsou rozezn´any podobn´e odst´ıny, napˇr´ıklad ˇcerven´a a oranˇzov´a nebo tmavˇe modr´a a fialov´a. Zv´ yˇsen´ım poˇctu bin˚ u by sice doˇslo k odstranˇen´ı tohoto nechtˇen´eho efektu, doch´azelo by ovˇsem naopak k pˇresegmentov´an´ı obrazu.
(a) Origin´ aln´ı obr´azek
(b) Segmentace
Obr. 48 Rozliˇsov´an´ı odst´ın˚ u pˇri segmentaci
Pomˇer 15:7:7 byl tedy zvolen jako pˇrijateln´ y kompromis. Nav´ıc se poˇc´ıtalo s jednoduchost´ı vstupn´ıch obr´azk˚ u, konkr´etnˇe se pˇri obr´azc´ıch sloˇzen´ ych z jednoduch´ ych geometrick´ ych tvar˚ u neoˇcek´avala pˇr´ıliˇsn´a barevn´a shoda sousedn´ıch tvar˚ u.
66
Kapitola 5. Testov´an´ı
5.2
Testov´ an´ı s uˇ zivateli
Pro testov´an´ı s uˇzivateli byly vytvoˇreny 3 sady vstupn´ıch obr´azk˚ u: • Set I. 30 jednoduch´ ych obr´azku ˇcasto tvoˇren´ ych pouze jednoduch´ ymi geometrick´ ymi tvary. Obr´azky obsahuj´ı jasnˇe identifikovateln´e a rozeznateln´e objekty a maj´ı jednoduch´e (jednobarevn´e) pozad´ı. • Set II. 51 m´ırnˇe sloˇzitˇejˇs´ıch obr´azk˚ u - identifikace objekt˚ u je sloˇzitˇejˇs´ı neˇz u pˇredchoz´ı sady a pozad´ı m˚ uˇze b´ yt sloˇzitˇejˇs´ı. • Set III. 17 sloˇzit´ ych obr´azk˚ u - identifikace objekt˚ u nen´ı zˇrejm´a, velmi ˇcasto komplexn´ı pozad´ı. Testov´an´ı se u ´ˇcastnilo celkem 5 osob; kaˇzd´e z nich byly ukazov´any vstupn´ı obr´azky a v´ ysledn´a skl´adanka vytvoˇren´a aplikac´ı. Tester mˇel subjektivnˇe posoudit vizu´aln´ı pˇritaˇzlivost vyseparovan´ ych d´ılk˚ u a jejich korespondenci s objekty v obraze podle stupnice: 1 - velmi ˇspatn´e 2 - ˇspatn´e 3 - uspokojiv´e 4 - dobr´e 5 - velmi dobr´e V´ ysledky testov´an´ı, viz. Obr.49, jsou v souladu s poˇzadovan´ ymi c´ıli. Set I, tedy sada obr´azk˚ u, s kter´ ymi je vzhledem k c´ılov´e skupinˇe aplikace poˇc´ıt´ano jako s ˇza´douc´ımi vstupy, je hodnocen pozitivnˇe (nejl´epe hodnocen´ y je obr´azek Obr.46(a)). Naopak Set III, kter´ y obsahuje napˇr´ıklad fotografie krajiny ˇci staveb, se setkal sp´ıˇse s negativn´ımi ohlasy (nejh˚ uˇre hodnocen´ y je obr´azek Obr.46(b)).
I Set II III
01 3.83 3.39 2.23
Uˇzivatel 02 03 04 4.30 3.93 3.33 3.63 3.33 2.86 3.06 2.06 2.12
05 3.70 3.35 2.52
Obr. 49 Hodnocen´ı uˇzivatel˚ u
Pr˚ umˇer 3.82 3.31 2.40
Kapitola 6. Z´avˇer
67
Kapitola 6 Z´ avˇ er Byla vytvoˇrena funkˇcn´ı aplikace pro operaˇcn´ı syst´em Android splˇ nuj´ıc´ı z´akladn´ı poˇzadavky - automatickou tvorbu hry typu puzzle z libovoln´eho vstupn´ıho obr´azku na z´akladˇe segmentace obrazu. Aplikace umoˇzn ˇuje uˇzivateli, mimo v´ ybˇeru vstupn´ıho obr´azku libovoln´eho form´atu a vlastn´ıho hran´ı, uloˇzen´ı vytvoˇren´e skl´adanky a jej´ı opˇetovn´e naˇcten´ı. Pˇresto existuj´ı oblasti, kter´e by bylo moˇzn´e v budouc´ım v´ yvoji zlepˇsit. Co se t´ yk´a algoritmu pro tvorbu skl´adanky, nebylo by od vˇeci zv´aˇzit i jin´a krit´eria pro v´ ybˇer ˇz´adouc´ıch d´ılk˚ u neˇz jejich kompaktnost, pˇr´ıpadnˇe krit´eria nˇejak zkombinovat. D´ale by st´aly za zv´aˇzen´ı dalˇs´ı moˇznosti pˇri zobrazen´ı vyjmut´ ych ˇca´st´ı ve vstupn´ım obr´azku, napˇr. efekt vtlaˇcen´ı. Tak´e aplikace samotn´a by mohla nab´ızet dalˇs´ı volby. Pˇri tvorbˇe velk´eho poˇctu d´ılk˚ u (m˚ uˇze jich b´ yt aˇz nˇekolik des´ıtek na jeden obr´azek) by pˇriˇsla vhod moˇznost pro pˇrep´ın´an´ı poˇctu zobrazen´ ych d´ılk˚ u (napˇr´ıklad 1-5, 5-10, 10+). Dalˇs´ı funkc´ı, kter´a by mohla b´ yt d´ale implementov´ana, je maz´an´ı uloˇzen´ ych skl´adanek pˇr´ımo z aplikace, prozat´ım je uloˇzenou skl´adanku moˇzn´e odstranit pouze ruˇcn´ım smaz´an´ım pˇr´ısluˇsn´ ych soubor˚ u ve sloˇzce aplikace.
68
Kapitola 6. Z´avˇer
Literatura
69
Literatura [1] Google Play [online]. [cit. 2015-05-04]. Dostupn´e z: https://play.google.com/store [2] Google Play. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2015-05-04]. Dostupn´e z: http://cs.wikipedia.org/wiki/Google Play [3] Animal Jigsaw Puzzles For Kids. Google Play [online]. [cit. 2015-05-04]. Dostupn´e z: https://play.google.com/store/apps/details?id=com.tula.kidjigsaws [4] Toddlers Puzzle Woozzle. Google Play [online]. [cit. 2015-05-04]. Dostupn´e z: https://play.google.com/store/apps/details?id=com.woozle ˇ ´C ˇ a Roger BOYLE. Image processing, ana[5] SONKA, Milan, V´aclav HLAVA lysis, and machine vision. 3rd ed. Toronto: Thomson, 2008, xxv, 829 s. ISBN 978-0-495-08252-1. [6] Lectures on Image Processing. PETERS II, Richard Alan. [online]. [cit. 2015-04-16]. Dostupn´e z: https://archive.org/details/Lectures on Image Processing [7] Zoom An Image With Different Interpolation Types. [online]. [cit. 2015-0416]. Dostupn´e z: http://www.codeproject.com/Articles/236394/Bi-Cubicand-Bi-Linear-Interpolation-with-GLSL [8] PRATT, William K. Digital image processing: PIKS Scientific inside. 4th ed. Hoboken.: Wiley-Interscience, c2007, xix, 782 s. ISBN 978-0-471-76777-0. [9] MITCHELL, Don P. a Arun N. NETRAVALI. Reconstruction filters in computer-graphics. ACM SIGGRAPH Computer Graphics. 1988, vol. 22, issue 4, s. 221-228. DOI: 10.1145/378456.378514.
70
Literatura
[10] HARALICK, Robert M. a Linda G. SHAPIRO. Image segmentation techniques. Computer Vision, Graphics, and Image Processing. 1985, vol. 29, issue 1, s. 100-132. DOI: 10.1016/s0734-189x(85)90153-7. [11] The Berkeley Segmentation Dataset and Benchmark. ARBELAEZ, Pablo, Charless FOWLKES a David MARTIN. [online]. [cit. 2015-04-17]. Dostupn´e z: http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ [12] ROTHER, Carsten, Vladimir KOLMOGOROV a Andrew BLAKE. ”GrabCut”. ACM Transactions on Graphics. 2004-08-01, vol. 23, issue 3, s. 309-. DOI: 10.1145/1015706.1015720. Dostupn´e z: http://portal.acm.org/citation.cfm?doid=1015706.1015720 [13] PATIL, R. V. a K. C. JONDHALE. Edge based technique to estimate number of clusters in k-means color image segmentation. 2010 3rd International Conference on Computer Science and Information Technology. 2010. DOI: 10.1109/iccsit.2010.5563647. [14] TURI, Rose a Siddheswar RAY. Determination of number of clusters in K-means clustering and application in colour image segmentation. In: PAL, Nikhil R, Arun K DE a Jyotirmay DAS. Advances in pattern recognition and digital techniques. New Delhi: Narosa Pub. House, c2000, s. 137-143. ISBN 8173193479. [15] OHASHI, Takumi, Zaher AGHBARI a Akifumi MAKINOUCHI. Hillclimbing Algorithm for Efficient Color-based Image Segmentation. In: HAMZA, Ed.: M. H. Proceedings of the IASTED International Conference on Signal Processing, Pattern Recognition, and Applications: June 30 July 2, 2003, Rhodes, Greece. Anaheim [u.a.]: Acta Press, 2003, s. 59-97. ISBN 0889863636. [16] RGB to HSV conersion. Online Reference & Tools [online]. 2014 [cit. 2015-04-18]. Dostupn´e z: http://www.rapidtables.com/convert/color/rgbto-hsv.htm [17] LI, Wenwen, Michael F. GOODCHILD a Richard CHURCH. An efficient measure of compactness for two-dimensional shapes and its application in regionalization problems. International Journal of Geographical Information Science. 2013, vol. 27, issue 6, s. 1227-1250. DOI: 10.1080/13658816.2012.752093.
Literatura
71
[18] FRIEDENBERG, Jay. Aesthetic judgment of triangular shape: compactness and not the golden ratio determines perceived attractiveness. IPerception 2012, vol. 3, issue 3, s. 163-175. DOI: 10.1068/i0484. Dostupn´e z: http://i-perception.perceptionweb.com/journal/I/article/i0484 [19] FREEMAN, Herbert. On the Encoding of Arbitrary Geometric Configurations. IEEE Transactions on Electronic Computers. 1961, EC-10, issue 2, s. 260-268. DOI: 10.1109/TEC.1961.5219197. Dostupn´e z: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5219197 [20] Measuring boundary length. Cris’s Image Analysis Blog [online]. [cit. 2015-04-25]. Dostupn´e z: http://www.cb.uu.se/ cris/blog/index.php/archives/310 [21] How to obtain the chain code. Cris’s Image Analysis Blog [online]. [cit. 2015-04-25]. Dostupn´e z: http://www.cb.uu.se/ cris/blog/index.php/archives/324 [22] PROFFITT, D. a D. ROSEN. Metrication errors and coding efficiency of chain-encoding schemes for the representation of lines and edges. Computer Graphics and Image Processing. 1979, vol. 10, issue 4, s. 318-332. DOI: 10.1016/S0146-664X(79)80041-6. Dostupn´e z: http://linkinghub.elsevier.com/retrieve/pii/S0146664X79800416 [23] VOSSEPOEL, A.M. a A.W.M. SMEULDERS. Vector code probability and metrication error in the representation of straight lines of finite length. Computer Graphics and Image Processing. 1982, vol. 20, issue 4, s. 347-364. DOI: 10.1016/0146-664X(82)90057-0. Dostupn´e z: http://linkinghub.elsevier.com/retrieve/pii/0146664X82900570 [24] Gaussian blur. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2015-04-29]. Dostupn´e z: http://en.wikipedia.org/wiki/Gaussian blur [25] Fastest Gaussian Blur (in linear time). KUCKIR, Ivan. Algorithms and Stuff [online]. [cit. 2015-04-29]. Dostupn´e z: http://blog.ivank.net/fastest-gaussian-blur.html [26] Separable convolution. MATLAB Central: Steve on Image Processing [online]. 2006 [cit. 2015-04-29]. Dostupn´e z: http://blogs.mathworks.com/steve/?p=78?s cid=srchtitle [27] Gaussian filtering. Cris’s Image Analysis Blog [online]. [cit. 2015-04-29]. Dostupn´e z: http://www.cb.uu.se/ cris/blog/index.php/archives/22
72
Literatura
[28] Android [online]. [cit. 2015-05-02]. Dostupn´e z: https://www.android.com/ [29] Android (operating system). In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2015-05-02]. Dostupn´e z: http://en.wikipedia.org/wiki/Android %28operating system%29 [30] Gartner Says Tablet Sales Continue to Be Slow in 2015. Gartner Inc.: Technology Research [online]. 2015 [cit. 2015-05-02]. Dostupn´e z: http://www.gartner.com/newsroom/id/2954317 [31] Smartphone OS Market Share, Q4 2014. IDC: The premier global market intelligence firm [online]. 2015 [cit. 2015-05-02]. Dostupn´e z: http://www.idc.com/prodserv/smartphone-os-market-share.jsp [32] Android Distribution Updated for April 2015 – Lollipop Jumps to 5.4%. textitDroid Life [online]. [cit. 2015-05-02]. Dostupn´e z: http://www.droidlife.com/2015/04/08/android-distribution-updated-for-april-2015-lollipopjumps-to-5-4/ [33] Android Distribution Updated for November 2014, Kit Kat Hits 30%. Droid Life [online]. [cit. 2015-05-02]. Dostupn´e z: http://www.droidlife.com/2014/11/03/android-distribution-updated-for-october-2014-kitkat-hits-30/ [34] ALLEN, Grant. Beginning Android 4. Apress: distributed by Springer Science Business Media, c2012, xx, 582 pages. ISBN 14-302-3984-0. [35] GIF vs. JPG vs. PNG: What’s the Difference?. Digital Trends: Technology News and Product Reviews [online]. [cit. 2015-05-04]. Dostupn´e z: http://www.digitaltrends.com/computing/whats-the-differencebetween-a-gif-a-jpg-and-a-png-file/
Pˇr´ıloha A. Ovl´ad´an´ı aplikace
73
Pˇ r´ıloha A Ovl´ ad´ an´ı aplikace V´ ychoz´ı stav aplikace je na Obr.50. Aplikace je ovl´ad´ana dvˇema tlaˇc´ıtky v lev´em doln´ım rohu hlavn´ıho okna, viz Obr.51(b) - pokud m´a tlaˇc´ıtko ˇsed´e pozad´ı (viz. tlaˇc´ıtko Start na Obr.51(a)), je zablokovan´e, pokud m´a ˇcern´e pozad´ı, je aktivn´ı (uˇzivatel jej m˚ uˇze pouˇz´ıt).
Obr. 50 V´ ychoz´ı obrazovka
(a)
(b)
(c)
Obr. 51 Ovl´ad´an´ı aplikace
Ve v´ ychoz´ım stavu je pˇr´ıstupn´a jen moˇznost Menu, po jej´ımˇz zvolen´ı se zobraz´ı menu z Obr.51(c).
74
Pˇr´ıloha A. Ovl´ad´an´ı aplikace
Pro vybr´an´ı nov´eho obr´azku ke zpracov´an´ı je tˇreba otevˇr´ıt menu a zvolit Select (ikona s puzzlem), kter´e otevˇre galerii (jej´ı vzhled je z´avisl´ y na verzi operaˇcn´ıho syst´emu) pro v´ ybˇer vstupn´ıho obr´azku. Po v´ ybˇeru nov´eho vstupu je zpˇr´ıstupnˇena moˇznost Start v hlavn´ım oknˇe, viz. 51(b), po jej´ıˇz volbˇe dojde ke zpracov´an´ı obr´azku. Bˇehem v´ ypoˇctu jsou zablokov´any moˇznosti Start a Menu a uˇzivatel je informov´an o pr˚ ubˇehu pomoc´ı progress baru, viz. Obr.52(a). Po dokonˇcen´ı zpracov´av´an´ı zmiz´ı progress bar a na pozici vedle ovl´adac´ıch prvk˚ u jsou vyskl´ad´any vytvoˇren´e d´ılky, viz. Obr.52(b).
(a)
(b) Obr. 52 Pr˚ ubˇeh zpracov´an´ı
Uloˇzen´ı vytvoˇren´e skl´adanky se prov´ad´ı z menu pomoc´ı tlaˇc´ıtka Save, viz. 51(c), kter´e je aktivn´ı pouze po dokonˇcen´ı zpracov´an´ı vstupu a nebo po naˇcten´ı uloˇzen´e skl´adanky. Bˇehem ukl´ad´an´ı je uˇzivatel pˇrenesen zpˇet na hlavn´ı obrazovku a dojde ke kr´atkodob´emu zablokov´an´ı moˇznost´ı Start a Menu. Uˇzivatel je posl´eze informov´an o u ´spˇeˇsn´em proveden´ı uloˇzen´ı, viz. Obr.53, naˇceˇz je opˇet zpˇr´ıstupnˇena moˇznost Menu.
Obr. 53 Potvrzen´ı uloˇzen´ı
Naˇcten´ı dˇr´ıve uloˇzen´e skl´adanky je moˇzn´e pokaˇzd´e, pokud je pˇr´ıstupna moˇznost Menu. Po zvolen´ı moˇznosti Load v menu je zobrazena dlaˇzdicov´a galerie s miniaturami uloˇzen´ ych skl´adanek, viz. Obr.54. Po v´ ybˇeru uloˇzen´eho objektu
Pˇr´ıloha A. Ovl´ad´an´ı aplikace
75
je uˇzivatel pˇrenesen zpˇet do hlavn´ıho okna, kam je naˇctena i poˇzadovan´a skl´adanka.
Obr. 54 Dlaˇzdicov´a galerie pro naˇc´ıt´an´ı
Tlaˇc´ıtko Menu, viz. Obr.51(b) a Obr.51(c), se vyskytuje jak na hlavn´ı obrazovce, tak v menu aplikace a slouˇz´ı pro pˇrep´ın´an´ı mezi tˇemito dvˇema. Vlastn´ı hran´ı hry prob´ıh´a intuitivnˇe pomoc´ı operace uchopit a t´ahnout“ ” ( Drag & Drop“), kdy uˇzivatel umist’uje jednotliv´e d´ılky na jejich p˚ uvodn´ı ” pozice. Po um´ıstˇen´ı vˇsech d´ılk˚ u je spuˇstˇen v´ıtˇezn´ y t´on.
76
Pˇr´ıloha A. Ovl´ad´an´ı aplikace
Pˇr´ıloha B. Seznam pouˇzit´ ych zkratek
Pˇ r´ıloha B Seznam pouˇ zit´ ych zkratek HSV
Hue Saturation Value
RGB
Red Green Blue
RGBA
Red Green Blue Alpha
px
pixel
IPQ
Isoperimetric Quotient
DCM
Digital Compactness Measure
NDC
Normalized Discrete Compactness
CoG
Center of Gravuty
API
Application Programming Interface
ANR
Application Not Responding
UI
User Interface
PNG
Portable Network Graphics
JPG, JPEG
Joint Photographic Experts Group
GIF
Graphics Interchange Format
77
78
Pˇr´ıloha B. Seznam pouˇzit´ ych zkratek
Pˇr´ıloha C. Obsah pˇriloˇzen´eho DVD
Pˇ r´ıloha C Obsah pˇ riloˇ zen´ eho DVD
Obr. 55 Obsah pˇriloˇzen´eho DVD
79