Automatická tvorba her typu puzzle na dotykovém zařízení s OS Android

Č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é pˇripom´ınky a odborn´ y dohled nad touto prac´ı. Dále bych chtˇel podˇekovat rodinˇe za podporu bˇehem celého studia.

Prohl´ aˇ sen´ı autora pr´ ace Prohlaˇsuji, ˇze jsem pˇredloˇzenou práci vypracoval samostatnˇe a ˇze jsem uvedl veˇskeré pouˇzité informaˇcn´ı zdroje v souladu s Metodick´ ym pokynem o dodrˇzován´ı etick´ ych princip˚ u pˇri pˇr´ıpravˇe vysokoˇskolsk´ ych závˇereˇcn´ ych prac´ı.

V Praze dne

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

.................................. Podpis autora práce

Anotace C´ılem této práce je vyvinut´ı aplikace pro zaˇr´ızen´ı s operaˇcn´ım systémem Android, která automaticky vytvoˇr´ı hru typu puzzle pro libovoln´ y vstupn´ı obrázek. Jednotlivé d´ılky skládanky by mˇely reflektovat objekty v pˇr´ısluˇsném vstupu. Automatická 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án´ı obrazu . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Interpolace pomoc´ı nejbliˇzˇs´ıho souseda . . . . . . . . . 3.1.2 Bilineárn´ı interpolace . . . . . . . . . . . . . . . . . . . 3.1.3 Bikubická interpolace . . . . . . . . . . . . . . . . . . . 3.1.4 Porovnán´ı metod . . . . . . . . . . . . . . . . . . . . . 3.2 Segmentace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Zvaˇzované metody . . . . . . . . . . . . . . . . . . . . 3.2.2 Barevn´ y model HSV . . . . . . . . . . . . . . . . . . . 3.2.3 Algoritmus zdoláván´ı kopc˚ u (Hill-Climbing) . . . . . . 3.3 Prvn´ı dˇelen´ı na základˇe velikosti . . . . . . . . . . . . . . . . . 3.4 Prostorové oddˇelen´ı segment˚ u a druhé dˇelen´ı na základˇe velikosti 3.5 Kritérium pro vyb´ırán´ı segment˚ u . . . . . . . . . . . . . . . . 3.5.1 V´ ypoˇcet kompaktnosti geometrického tvaru . . . . . . 3.5.2 V´ ypoˇcet IP Q indexu . . . . . . . . . . . . . . . . . . . 3.6 Operace ovlivˇ nuj´ıc´ı IP Q index . . . . . . . . . . . . . . . . . . 3.6.1 Matematická morfologie . . . . . . . . . . . . . . . . . 3.6.2 Zaplˇ nován´ı velk´ ych dˇer . . . . . . . . . . . . . . . . . . 3.6.3 V´ ysledky operac´ı . . . . . . . . . . . . . . . . . . . . . 3.7 Vyb´ırán´ı 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áln´ı u ´prava segment˚ u . . . . . . . . . . . . . . . . . . . . . 3.10 Rozmazán´ı vyseparovan´ ych ˇcást´ı ve vstupn´ım obrázku . . . . . . . . . . . . . . . . . . . . . . . . .

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ádán´ı skládanky . . . . 4.2.2 Zpracován´ı obrázku . . . . 4.2.3 V´ ybˇer vstupn´ıho obrázku . 4.2.4 Uloˇzen´ı skládanky . . . . . 4.2.5 Naˇcten´ı uloˇzené skládanky

. . . . . . .

53 55 57 57 58 59 59 60

5 Testov´ an´ı 5.1 Okolnosti ovlivˇ nuj´ıc´ı segmentaci obrazu . . . . . . . . . . . . . 5.2 Testován´ı 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ého poˇctu pixel˚ u na zachován´ı tvar˚ u v obraze Bilineárn´ı interpolace - hodnota nového pixelu . . . . . . . Bikubická interpolace - hodnota nového pixelu . . . . . . . Interpolaˇcn´ı jádra . . . . . . . . . . . . . . . . . . . . . . . Porovnán´ı interpolaˇcn´ıch metod . . . . . . . . . . . . . . . Barevn´ y model HSV . . . . . . . . . . . . . . . . . . . . . Znázornˇen´ı indexace pixel˚ u (obrázek o rozmˇerech 4x3) . . Hill-Climbing algoritmus . . . . . . . . . . . . . . . . . . . Prvn´ı dˇelen´ı na základˇe velikosti . . . . . . . . . . . . . . . Prostorovˇe neoddˇelené segmenty . . . . . . . . . . . . . . . Okol´ı pixelu (o) pouˇzité pˇri prostorovém dˇelen´ı . . . . . . . Pˇr´ıklad oddˇelovaného segmentu . . . . . . . . . . . . . . . Hodnoty matice rastr po tˇrech kroc´ıch algoritmu . . . . . Koneˇcné hodnoty matice rastr . . . . . . . . . . . . . . . . Freeman˚ uv ˇretˇezov´ y kód . . . . . . . . . . . . . . . . . . . Pˇr´ıklad popisu hranice objektu . . . . . . . . . . . . . . . Pˇr´ıklad segmentu . . . . . . . . . . . . . . . . . . . . . . . Porovnán´ı metod na mˇeˇren´ı obvodu . . . . . . . . . . . . . Pˇr´ıklad segmentu jako binárn´ıho obrazu . . . . . . . . . . Nejˇcastˇeji pouˇz´ıvané strukturn´ı elementy . . . . . . . . . . Posunut´ı o radiusvektor . . . . . . . . . . . . . . . . . . . Transpozice . . . . . . . . . . . . . . . . . . . . . . . . . . Binárn´ı dilatace . . . . . . . . . . . . . . . . . . . . . . . . Binárn´ı eroze . . . . . . . . . . . . . . . . . . . . . . . . . Pouˇzit´ y strukturn´ı element B . . . . . . . . . . . . . . . . V´ yvojov´ y diagram vyplˇ nován´ı segment˚ u . . . . . . . . . . Zmˇena indexu v závislosti na hodnotˇe ˇretˇezového kódu . . Zlepˇsován´ı 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ázku. . . . . Neˇzádouc´ı efekt dˇelen´ı velk´ ych segment˚ u. . . . . . . . . V´ yvojov´ y diagram tvorby dodateˇcn´ ych segment˚ u . . . Pˇr´ıklad segmentu jako binárn´ıho obrazu . . . . . . . . Rozmazán´ı vyseparovan´ ych ˇca´st´ı ve vstupn´ım obrázku

. . . . .

44 45 47 49 51

37 38

53

39 40 41 42 43 44 45

Pod´ıl operaˇcn´ıch systém˚ u na trhu v roce 2014 . . . . . . . . . Srovnán´ı zastoupen´ı verz´ı OS Android v listopadu 2014 a dubnu 2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hlavn´ı aktivita MainActivity . . . . . . . . . . . . . . . . . . . Ostatn´ı aktivity . . . . . . . . . . . . . . . . . . . . . . . . . . Diagram uˇzit´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . Sekvenˇcn´ı diagram zpracován´ı obrázku . . . . . . . . . . . . . Sekvenˇcn´ı diagram v´ ybˇeru obrázku . . . . . . . . . . . . . . . Sekvenˇcn´ı diagram uloˇzen´ı skládanky . . . . . . . . . . . . . . Sekvenˇcn´ı diagram naˇcten´ı uloˇzené skládanky . . . . . . . . .

54 55 56 57 58 59 59 61

46 47 48 49

Prototypy vstupn´ıch obrázk˚ u . . . . . . . . . . . Porovnán´ı segmentace pro r˚ uzné vstupn´ı formáty Rozliˇsován´ı odst´ın˚ u pˇri segmentaci . . . . . . . . Hodnocen´ı uˇzivatel˚ u . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

63 64 65 66

50 51 52 53 54

V´ ychoz´ı obrazovka . . . . . . . Ovládán´ı aplikace . . . . . . . . Pr˚ ubˇeh zpracován´ı . . . . . . . Potvrzen´ı uloˇzen´ı . . . . . . . . Dlaˇzdicová galerie pro naˇc´ıtán´ı .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

73 73 74 74 75

55

Obsah pˇriloˇzeného DVD . . . . . . . . . . . . . . . . . . . . .

79

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

´ Kapitola 1. Uvod

11

Kapitola 1 ´ Uvod Chytré telefony a tablety si v souˇcasné dobˇe uˇz´ıvaj´ı znaˇcné popularity, která, jak se zdá, bude dále jen r˚ ust. S t´ım je spojen i vzr˚ ustaj´ıc´ı zájem o v´ yvoj aplikac´ı pro tato zaˇr´ızen´ı, kter´ y byl i pohnutkou pro v´ ybˇer tématu - aplikován´ı velmi ˇcasto v´ ypoˇcetnˇe nároˇcn´ ych metod poˇc´ıtaˇcového vidˇen´ı na mobiln´ıch zaˇr´ızen´ıch, která maj´ı menˇs´ı v´ ypoˇcetn´ı v´ ykon a pamˇet’ové moˇznosti neˇz poˇc´ıtaˇce. C´ılem práce bylo navrhnout aplikaci pro zaˇr´ızen´ı s operaˇcn´ım systémem Android, která pro libovoln´ y vstupn´ı obrázek vytvoˇr´ı hru typu puzzle; c´ılovou skupinou jsou dˇeti ve vˇeku od tˇr´ı do ˇsesti let. Jednotlivé d´ılky, nalezené ve vstupu metodami poˇc´ıtaˇcového vidˇen´ı, by mˇely reflektovat koherentn´ı objekty v obraze. Kompletn´ı seznam základn´ıch poˇzadavk˚ u na vyv´ıjenou aplikaci je následuj´ıc´ı: • Uˇzivatel má moˇznost vybrat libovoln´ y vstupn´ı obrázek • Uˇzivatel má moˇznost uloˇzit stávaj´ıc´ı skládanku • Uˇzivatel má moˇznost naˇc´ıst dˇr´ıve uloˇzenou skládanku Vlastn´ı hran´ı hry prob´ıhá vlepován´ım“ vytvoˇren´ ych d´ılk˚ u zpˇet do p˚ uvodn´ıho ” obrázku operac´ı uchopit a táhnout“ ( Drag & Drop“). Pˇri v´ yvoji byl kladen ” ” d˚ uraz zejména na návrh algoritmu, kter´ y v´ yslednou skládanku vytvoˇr´ı.

12

´ Kapitola 1. Uvod

Kapitola 2. Souˇcasn´ y stav

13

Kapitola 2 Souˇ casn´ y stav Aplikace pro operaˇcn´ı systém Android jsou distribuované sluˇzbou Google Play[1], konkrétnˇ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á z kaˇzdého zaˇr´ızen´ı vybaveného operaˇcn´ım systémem Android. Google Play obsahuje velké mnoˇzstv´ı her typu puzzle pro dˇeti, které jsou ovˇsem pouze variacemi na dvˇe varianty. Prvn´ı variantou jsou aplikace na základˇe klasick´ ych fyzick´ ych puzzl˚ u, jedná se tedy o pouhé rozˇrezán´ı obrázku. 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á varianta se principiálnˇe pˇribliˇzuje poˇzadavk˚ um na zadán´ı této práce jedná se o vlepován´ı“ vyˇr´ızl´ ych objekt˚ u zpˇet do p˚ uvodn´ıho obrázku, tvorba ” v´ yˇrez˚ u ovˇsem neprob´ıhá automaticky a dvojice obrázek - v´ yˇrezy jsou dodány v´ yvojáˇrem aplikace.

14

Kapitola 2. Souˇcasn´ y stav

Obr. 2 Toddlers Puzzle Woozzle

Zástupcem tohoto typu skládanek je napˇr´ıklad hra Toddlers Puzzle Woozzle[4], viz Obr.2. Aplikace, která byla vyv´ıjena jako c´ıl této práce, tedy nemá v distribuˇcn´ı sluˇzbˇe Google Play zastoupen´ı.

Kapitola 3. Algoritmus

15

Kapitola 3 Algoritmus Vstupem pouˇzitého algoritmu (viz. v´ yvojov´ y diagram Obr.3) je vybran´ y obrázek, pˇresnˇeji pole s RGB hodnotami jeho pixel˚ u. V´ ystupem jsou indexy vyseparovan´ ych obrazc˚ u (kaˇzd´ y obrazec má seznam index˚ u sv´ ych pixel˚ u) a obrázek, kter´ y je na vyseparovan´ ych pozic´ıch rozmazán (opˇet jde tedy o pole s RGB hodnotami jeho pixel˚ u). Vstupn´ı obrázek je nejprve zmenˇsen kv˚ uli urychlen´ı v´ ypoˇcetn´ıch ˇcas˚ u, poté je provedena segmentace a prostorové oddˇelen´ı vzniknuvˇs´ıch segment˚ u. U segment˚ u správné velikosti (tzn. ani pˇr´ıliˇs mal´ ych ani pˇr´ıliˇs velk´ ych) je poté porovnána jejich kompaktnost s pˇredem stanoven´ ym kompaktnostn´ım prahem. Pˇrijaté segmenty jsou nakonec zvˇetˇseny zpátky na p˚ uvodn´ı velikost vstupn´ıho obrázku, kter´ y je na jejich pozic´ıch rozmazán.

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áno pˇribliˇznˇe 250 tis´ıc pixel˚ u. Obraz s pomˇerem stran 4:3 bude m´ıt po takovémto 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án´ı menˇs´ıho poˇctu pixel˚ u vede sice k rychlejˇs´ım v´ ypoˇcetn´ım ˇcas˚ um, docház´ı nicménˇe ke zkreslen´ı objekt˚ u ve scénˇe (zejména jejich hranic), viz. Obr.4. Analogicky vˇetˇs´ı poˇcet pixel˚ u vede k delˇs´ımu trván´ı v´ ypoˇctu a k lepˇs´ımu zachován´ı tvar˚ u. Jako algoritmy ke zmenˇsen´ı velikosti obrazu byly zvaˇzovány interpolace pomoc´ı nejbliˇzˇs´ıho souseda, bilineárn´ı interpolace a bikubická interpolace.

16


Pˇredzpracován´ı obrazu

Segmentace

Prvn´ı dˇelˇen´ı podle velikosti

Prostorové oddˇelen´ı segment˚ u

Druhé dˇelen´ı podle velikosti

Aplikace binárn´ı 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áln´ı u ´prava segment˚ u

Rozmazán´ı vyseparovan´ ych ˇcást´ı

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ého poˇctu pixel˚ u na zachován´ı tvar˚ u v obraze


3.1.1

17

Interpolace pomoc´ı nejbliˇ zˇ s´ıho souseda

Jak jiˇz název napov´ıdá, 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éto jinak pˇr´ımoˇcaré metody, je tvorba schod˚ u“ ” u objekt˚ u s ostr´ ymi hranicemi (patrnˇejˇs´ı u zvˇetˇsován´ı obrazu).

3.1.2

Biline´ arn´ı interpolace

Bilineárn´ı interpolace (Bilinear interpolation)[5][6] pˇredpokládá, ˇze funkce intenzity je lineárn´ı ve svém okol´ı a hodnotu intenzity interpolovaného pixelu poˇc´ıtá jako váˇzen´ y pr˚ umˇer ˇctyˇrech okoln´ıch pixel˚ u z p˚ uvodn´ıho obrazu. Konkrétnˇe je hodnota intenzity interpolovaného pixelu J(r0 , c0 ) vypoˇc´ıtána 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ává 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árn´ı interpolace m˚ uˇze

Obr. 5 Bilineárn´ı interpolace - hodnota nového pixelu

d´ıky povaze pr˚ umˇerován´ı zp˚ usobit rozmazán´ı, redukuje efekt ”schod˚ u”pˇredstaven´ y u interpolace pomoc´ı nejbliˇzˇs´ıho souseda.

18

3.1.3


Bikubick´ a interpolace

Bikubická interpolace[5][7][8] jeˇstˇe dále zpˇresˇ nuje hodnotu intenzity interpolovaného pixelu t´ım, ˇze bere v u ´vahu ˇsestnáct sousedn´ıch pixel˚ u z p˚ uvodn´ıho obrazu (viz. Obr.6). Obecnˇe se hodnota intenzity interpolovaného 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árn´ı interpolace udává 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ádro) udává váhy intenzit kaˇzdého z ˇsestnácti sousedn´ıch pixel˚ u p˚ uvodn´ıho obrazu ve v´ ysledné sumˇe, z ˇcehoˇz plyne, ˇze volbou vhodné funkce Rc lze vyjádˇrit i bilineárn´ı interpolaci a interpolaci pomoc´ı nejbliˇzˇs´ıho souseda.

Obr. 6 Bikubick´ a interpolace - hodnota nového 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ém slova smyslu nejedná o bikubickou interpolaci, jelikoˇz


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ádrem je Jádro 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á interpolace se dokáˇze vypoˇra´dat s efektem ”schod˚ u”interpolace

(a) Bell

(b) CatMull-Rom Obr. 7 Interpolaˇcn´ı jádra

pomoc´ı nejbliˇzˇs´ıho souseda a potlaˇcuje i rozmazán´ı pˇr´ıtomné u bilineárn´ı interpolace. Na prvn´ı pohled je vˇsak patrné, ˇze je ˇcasovˇe nároˇcnˇejˇs´ı neˇz pˇredeˇslé dva zp˚ usoby.

3.1.4

Porovn´ an´ı metod

Porovnán´ı v´ yˇse zm´ınˇen´ ych ˇctyˇrech metod je demonstrováno na Obr.8. P˚ uvodn´ı obrázek Obr.8(a) o velikosti 3392px x 3328px byl zmenˇsen pomoc´ı kaˇzdé 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éln´ıkem na Obr.8(a)) kaˇzdé této zmenˇseniny. Je vidˇet, ˇze s pokroˇcilejˇs´ı metodou docház´ı k postupnému zlepˇsován´ı u ´rovnˇe

20


interpolovaného obrazu, zejména na hranici objektu. Pˇrestoˇze bikubická interpolace produkuje z pohledu lidského vn´ımán´ı obrazu nejlepˇs´ı v´ ysledky, byla jako metoda pro pˇredzpracován´ı (pˇresnˇeji zmenˇsen´ı) obrazu zvolena bilineárn´ı interpolace. Jev´ı se totiˇz jako vhodn´ y kompromis mezi rychlost´ı a v´ ykonem. Nav´ıc u zmenˇsován´ı obrazu nejsou nedostatky tolik patrné (Obr.5 zámˇernˇe zveliˇcuje tyto nedostatky pˇribl´ıˇzen´ım ˇcásti zmenˇseného sn´ımku).

3.2

Segmentace

Segmentace obrazu[5] obnáˇs´ı rozdˇelen´ı obrazu na oblasti, které silnˇe koreluj´ı s reáln´ ymi objekty ˇci oblastmi obsaˇzen´ ymi v obraze. Nejˇcastˇeji se jako rozhoduj´ıc´ı atribut pouˇz´ıvá hodnota intenzity pro jednobarevné obrazy a jednotlivé komponenty barev (napˇr. kaˇzd´ y z kanál˚ u RGB barevného schématu) pro v´ıcebarevné obrazy[8]. Neexistuje ˇzádná ucelená teorie o segmentaci obrazu[8], následkem ˇcehoˇz nevznikla pouze jediná univerzáln´ı metoda pro tento problém. Existuje vˇetˇs´ı mnoˇzstv´ı metod, které vznikly jako ˇreˇsen´ı urˇcitého problému a postupnˇe z´ıskaly na popularitˇe. Protoˇze existuje velké 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ásleduj´ı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ého segmentu by mˇely b´ yt jednoduché, prostorovˇe pˇresné a pokud moˇzno nepˇr´ıliˇs ˇclenité • Sousedn´ı segmenty by mˇely b´ yt co nejv´ıce rozd´ılné (s ohledem na segmentaˇcn´ı atribut, podle kterého je oblast segmentu uniformn´ı) Jeden ze zp˚ usob˚ u jak hodnotit segmentaˇcn´ı metody pˇredpokládá, ˇze správná segmentace je známa pˇredem. V´ ysledky mˇeˇrené metody jsou potom porovnávány s touto ”ground truth”. Tento postup je vˇsak velmi pracn´ y[5] a nav´ıc pro vzevrubné posouzen´ı metody, je tˇreba m´ıt objemnou databázi takov´ ychto obraz˚ u (nejznámˇ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án na syntetick´ ych datasetech a na vlastnosti obraz˚ u zavád´ı restrikce, které ˇcasto nemohou b´ yt pouˇzité v aplikac´ıch z reálného svˇeta.[5]


21

(a) P˚ uvodn´ı obraz

(b) Nejbliˇzˇs´ı soused

(c) Bilineárn´ı int.

(d) Bell

(e) Catmul-Rom

Obr. 8 Porovnán´ı interpolaˇcn´ıch metod

22


Momentálnˇe vˇsak neexistuje ˇzádn´ y konsensus o tom, jak tyto metody hodnotit. Pro praktické pouˇzit´ı se zpravidla zodpov´ıdaj´ı tˇri otázky[5] 1. Jak ˇcasto metoda selˇze (tzn. metoda nedá rozumn´ y v´ ysledek) 2. Jak pˇresná metoda je 3. Do jaké m´ıry je metoda reprodukovatelná 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é mnoˇzstv´ı metod, které dokáˇz´ı obraz segmentovat. Prvn´ım zvaˇzovan´ ym algoritmem byla, na základˇe doporuˇcen´ı vedouc´ıho práce, segmentace s vyuˇzit´ım hledán´ı minimáln´ıho ˇrezu (maximáln´ıho tok) grafu - GrabCut[12]. Tato metoda je inicializována nalezen´ım bod˚ u náleˇz´ıc´ıch pozad´ı a popˇred´ı, které slouˇz´ı jako pevné omezen´ı (hard constraint); dodateˇcná 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án´ı minimáln´ıho ˇrezu grafu zam´ıtnuta. Dalˇs´ım zvaˇzovan´ ym algoritmem bylo velmi rozˇs´ıˇrené shlukován´ı pomoc´ı kmeans[5], které lze popsat následovnˇe 1. V obrazu je vybráno (v nejprimitivnˇejˇs´ı verzi náhodnˇe) k bod˚ u - centroid˚ u 2. Kaˇzd´ y bod obrazu je pˇriˇrazen ke svému nejbliˇzˇs´ımu stˇredu (nejbliˇzˇs´ımu ve smyslu zvolené metriky, ˇcasto pouˇz´ıvanou je euklidovská vzdálenost) 3. Pro kaˇzd´ y takto vznikl´ y shluk je pr˚ umˇerován´ım vypoˇcten nov´ y centroid a shlukován´ı zaˇc´ına od 1. kroku K-means iteruje dokud nedojde ke zmˇenˇe ˇza´dného shluku (ideáln´ı pˇr´ıpad) nebo ´ dokud nen´ı pˇrekroˇcen poˇcet pˇredem dan´ ych iterac´ı. Uskal´ ım této metody je volba parametru k, kter´ y udává celkov´ y poˇcet shluk˚ u. Existuj´ı sice metody na automatické zjiˇstˇen´ı k (napˇr´ıklad pomoc´ı detekce hran [13] nebo porovnán´ım segment˚ u pro r˚ uzná k [14]), zavádˇej´ı ovˇsem dalˇs´ı vrstvu komplexity do celého algoritmu. Nav´ıc k-means velmi ˇcasto konverguj´ı k lokáln´ımu optimu, ˇc´ımˇz docház´ı ke ztrátˇe poˇctu segment˚ u a nepˇresnostem v segmentaci. Nakonec byl zvolen algoritmus zdoláván´ı kopc˚ u (Hill-Climbing), kter´ y dosáhne segmentace hledán´ım lokáln´ıch maxim v trojrozmˇerném histogramu[15].


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á rozd´ılnost barev odpov´ıdá jejich euklidovské vzdálenosti v tomto modelu. HSV barevn´ y model tuto vlastnost splˇ nuje a nav´ıc velmi dobˇre odpov´ıdá lidskému vn´ımán´ı 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án´ı s b´ılou barvou.

Obr. 9 Barevn´ y model HSV

Na Obr.9[15] je barevn´ y HSV model znázornˇen´ y - H jako hodnota na barevném kotouˇci, S urˇcuje pozici na kotouˇci od stˇredu a V je pozice barevného kotouˇce na ose ˇcerná-b´ılá. RGB hodnoty se na HSV pˇrevedou podle následn´ 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


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ého segmentaˇcn´ıho algortimu[15] je pole s RGB hodnotami pixel˚ u zpracovávaného obrazu, kde poˇrad´ı v poli odpov´ıdá um´ıstˇen´ı pixelu v obraze (viz. Obr.10). V´ ystupem je pole clusters stejné velikosti jako vstup, které obsahuje rozˇrazen´ı pixel˚ u do segment˚ u - clusters(i) = j znamená, ˇze i -t´ y pixel náleˇz´ı j -tému shluku. 0 4 8

1 5 9

2 6 10

3 7 11

Obr. 10 Zn´ azornˇen´ı indexace pixel˚ u (obrázek o rozmˇerech 4x3)

RGB hodnoty jsou pˇrevedeny do HSV a upraveny tak, aby nejmenˇs´ı hodnota kaˇzdé sloˇzky byla 0 a nejvˇetˇs´ı hodnota kaˇzdé sloˇzky 1 (tedy nafitován´ı do intervalu h0, 1i) a poté je pomoc´ı Hill-Climbing algoritmu provedená segmentace. Jednorozmˇern´ y Hill-Climbing algoritmus pro H sloˇzku vypadá následovnˇe. 1. Vytvoˇren´ı jednorozmˇerného barevného histogramu.


25

2. Zdoláván´ı kopce - zaˇc´ıná se na libovolném nenulovém binu (tj. datovém intervalu) a podle následuj´ıc´ıch pravidel, se hledá vrchol (kopec), tj. lokáln´ı maximum v histogramu (a) Porovnán´ı poˇctu pixel˚ u aktuáln´ıho binu s jeho lev´ ym a prav´ ym sousedem. Je d˚ uleˇzité si uvˇedomit, ˇze H sloˇzka je hodnota na barevném 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án´ı 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án, dokud nedojde k nalezen´ı binu, z kterého 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án jako peak (vrchol ˇci kopec), jedná se o lokáln´ı maximum v histogramu 3. Je zvolen dalˇs´ı libovoln´ y nenulov´ y, avˇsak dosud nezpracovan´ y, bin a je zopakován krok ˇc´ıslo 2. Tento krok se opakuje, dokud nejsou zpracovány vˇsechny biny histogramu. 4. Identifikovaná lokáln´ı 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án´ı) 5. Jednotlivé biny jsou pˇriˇrazeny k tomu lokáln´ımu maximu, ke kterému se doˇslo v kroce 2; t´ımto je segmentace hotova. Obr.11[15] znázorˇ nuje pr˚ ubˇeh algoritmu - (a) hledán´ı vrchol˚ u (peak˚ u), (b) pˇriˇrazován´ı 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é. V 1. kroce je vytvoˇren trojrozmˇern´ y histogram m´ısto jednorozmˇerného a ve 2. kroce se pouze liˇs´ı poˇcet sousedn´ıch bin˚ u, se kter´ ymi se porovnává poˇcet jejich pixel˚ u. Ve tˇrech rozmˇerech má obecnˇe kaˇzd´ y bin m´ısto dvou dvacet ˇsest soused˚ u (neplat´ı pro krajn´ı biny histogramu); dále 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ést následuj´ıc´ı podm´ınku - pokud je hodnota S pˇr´ıliˇs malá (pˇribliˇznˇe 0.1), porovnávaj´ı se pouze sousedn´ı biny ve smˇeru V sloˇzky. Kdyˇz jsou hodnoty S pˇr´ıliˇs malé, lidské oko nedokáˇze rozeznat zmˇenu barvy pˇri zmˇenˇe hodnoty V.

26


(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ána do v´ıce u ´rovn´ı neˇz zbylé 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áz´ı u vˇetˇs´ıch obrazu k ˇca´steˇcnému pˇresegmentován´ı a zvolen byl proto nakonec pomˇer 15:7:7. Pro kaˇzd´ y bin histogramu je prozkoumáno vˇsech jeho 26 soused˚ u a kaˇzd´ y pixel obrazu mus´ı b´ yt pˇriˇrazen k jednomu z lokáln´ıch maxim v histogramu (tzn. k segmentu). Pˇri poˇctu bin˚ u Ni a celkovém poˇctu pixel˚ u Np je tedy ˇcasová sloˇzitost Hill-climbing segmentace O(26Ni + Np ).

3.3

Prvn´ı dˇ elen´ı na z´ akladˇ e velikosti

Jak je patrné z Obr.12(b) (segmenty znázornˇené odst´ıny ˇsedi), segmentace pomoc´ı Hill-Climbing algoritmu vytváˇr´ı velmi zrnité oblasti na hranic´ıch jednotliv´ ych objekt˚ u v obraze. Jedná se o malé 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é segmenty). Z hlediska pragmatiˇcnosti nejsou tyto segmenty nijak d˚ uleˇzité a je tedy moˇzno je pˇr´ımo oddˇelit od dostateˇcnˇe velik´ ych segment˚ u. Toto je vykonáno obyˇcejn´ ym prahován´ım - nejdˇr´ıve je vypoˇctena jejich velikost (tj. poˇcet pixel˚ u) a pokud je menˇs´ı neˇz stanoven´ y práh, segment je ”zahozen”. Práh byl urˇcen na 0.4% celkového 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ého prahován´ı doˇslo u Obr.12 k odstranˇen´ı ˇctyˇriceti dvou segment˚ u (odstranˇené ˇca´sti jsou znázornˇeny fialovou barvou na Obr.12(c)). Pˇri celkovém poˇctu pixel˚ u Np a celkovém poˇctu segment˚ u k je ˇcasová sloˇzitost oddˇelen´ı mal´ ych segment˚ u O(Np +k) - ke spoˇc´ıtán´ı velikosti staˇc´ı jednou proj´ıt v´ ystup z Hill-Climbing algoritmu (odtud O(Np )) a poté je kaˇzd´ y poˇcet porovnán s prahem (odtud O(k)).


27

(a) P˚ uvodn´ı obrázek

(b) Segmentace

(c) Odstranˇen´ı mal´ ych segment˚ u

Obr. 12 Prvn´ı dˇelen´ı na základˇe velikosti

3.4

Prostorov´ e oddˇ elen´ı segment˚ u a druh´ e dˇ elen´ı na z´ akladˇ e velikosti

Segmentace pomoc´ı Algoritmu zdoláván´ı kopc˚ u nebere v u ´vahu prostorové rozloˇzen´ı segment˚ u, viz jednoduch´ y pˇr´ıklad na Obr.13 (segmentace na Obr.13(b) opˇet znázornˇ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 modrá ˇca´st).


(b) Segmentace

Obr. 13 Prostorovˇe neoddˇelené segmenty

28


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ému oddˇelen´ı je pouˇz´ıváno okol´ı (pro potˇreby tohoto textu nazvané 1 4 okol´ı) pixelu (bodu) z Obr.14 - o pˇredstavuje zpracovávan´ y pixel (bod), x zkoumané okol´ı. x x

x o

x

Obr. 14 Okol´ı pixelu (o) pouˇzité pˇri prostorovém dˇelen´ı

Pro kaˇzd´ y segment vypadá pseudokód algoritmu pro prostorové oddˇelen´ı následovnˇe 0. Inicializace algoritmu: index := 1 rastr := matice o rozmˇerech p˚ uvodn´ıho obrázku, defaultn´ı hodnota 0 belong := prázdné pole 1. Pro ∀ pixel p zpracovávaného segmentu (p je na pozici (i,j) v p˚ uvodn´ım obrázku): neigh := nenulové hodnoty 1 4 okol´ı bodu rastr(i,j) (a) Je-li neigh prázdné, potom: • rastr(i, j) := index • belong.add(index) • index := index + 1 (b) Nen´ı-li neigh prázdné, potom: • idmin := minimáln´ı hodnota neigh • rastr(i, j) := idmin • pro ∀i ∈ neigh : belong(i) = idmin 2. Vytvoˇren´ı prázdného seznamu pro kaˇzd´ y prostorovˇe samostatn´ y segment, celkov´ y poˇcet je tˇechto seznam˚ u je maximáln´ı hodnota pole belong 3. Pro ∀l, m taková, ˇze rastr(l, m) 6= 0 je do z -tého seznamu pˇridán index odpov´ıdaj´ıc´ı pozici (l,m); z je hodnota pole belong na pozici dané indexem rastr(l,m) Popsan´ y algoritmus je vysvˇetlen na následuj´ıc´ım pˇr´ıkladu. Je uvaˇzován obrázek o rozmˇerech 6x2 a po Hill-Climbing segmentaci zauj´ımá 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ázornˇena indexace jednotliv´ ych pixel˚ u.


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ého segmentu

Inicializace algoritmu (krok 0) pouze vytvoˇr´ı prázdnou nulovou matici rastr o rozmˇerech 2 ˇrádky a 6 sloupc˚ u, vytvoˇr´ı prázdné pole belong a do promˇenné 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ána jedniˇcka (prozat´ım jednoprvkové pole) a hodnota promˇenné index je nav´ yˇsena na 2. Dalˇs´ı zpracovávan´ y bod je na pozici 4 a opˇet jsou v jeho 1 4 okol´ı samé nuly. Na rastr(0, 4) je pˇriˇrazena hodnota 2, belong je dvojprvkové 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án´ı dalˇs´ıho bodu (pozice 6) - belong je nyn´ı tˇr´ıprvkové 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é jsou ovˇsem ignorovány). 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áˇz hodnota a dojde i k u ´pravˇe pole belong, jeˇz nyn´ı vypadá následovnˇe: [1, 2, 1] (Pozn.: je moˇzné si vˇsimnout malé nesrovnalosti v indexac´ıch, zat´ımco matice rastr a vˇsechna prozat´ım zmiˇ novaná pole zaˇc´ınaj´ı indexem 0, pole belong zaˇc´ıná indexem 1. Tato indexace, aˇc moˇzná matouc´ı, je zámˇerná.) 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á v pˇriˇrazen´ı r˚ uzn´ ych hodnot matice rastr prostorovˇe souvislému shluku. Hodnota 1 na tˇret´ım indexu pole belong znamená, ˇze indexy v rastr s hodnotou 3 patˇr´ı do stejného 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é hodnoty matice rastr

30


Následnˇe jsou podle 2. kroku vytvoˇreny dva prázdné seznamy a podle 3. kroku jsou do nich pˇridˇelovány indexy. V´ ysledkem jsou tedy segmenty popsané indexy [2, 6, 7, 8] a [4, 10, 11]. Neˇzádouc´ım vedlejˇs´ım produktem prostorového oddˇelován´ı je moˇznost tvorby pˇr´ıliˇs mal´ ych segment˚ u. To se m˚ uˇze stát v pˇr´ıpadˇe, ˇze segment projde prvn´ım testem na minimáln´ı velikost a následnˇe je v tomto kroku rozdˇelen na dvˇe ˇci v´ıce ˇcást´ı, které by t´ım sam´ ym testem jiˇz neproˇsly. Proto je tˇreba znovu otestovat velikosti a malé segmenty odstranit - opˇet je nastavena hranice 0.4% celkového poˇctu pixel˚ u (pˇri alokaci 250000 pixel˚ u na obraz pˇribliˇznˇe 1000 pixel˚ u). Zároveˇ 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ále) pˇr´ıliˇs velké segmenty, které mohou b´ yt povaˇzovány za patˇr´ıc´ı pozad´ı. V prvn´ım dˇelen´ı podle velikosti nemohlo k tomuto u ´konu doj´ıt, nebot’ nebylo moˇzné rozeznat pˇr´ıliˇs velké celistvé segmenty od pˇr´ıliˇs velk´ ych necelistv´ ych segment˚ u, tj. takov´ ych, které maj´ı po prostorovém oddˇelen´ı pˇrijatelnou velikost. Práh maximáln´ı velikosti byl urˇcen na 15% celkového poˇctu pixel˚ u v obraze, coˇz dˇelá pˇribliˇznˇe 37500 pixel˚ u pˇri nastavené alokaci. Algoritmus pro kaˇzd´ y segment vytvoˇr´ı jednu matici o velikosti p˚ uvodn´ıho obrázku - prvky matice jsou v 1. kroku sekvenˇcnˇe procházeny, je kontrolováno jejich 1 4 okol´ı a upravována jejich hodnota. Zjiˇstˇen´ı 1 4 okol´ı nen´ı závislé na celkovém 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áz´ı (i kdyˇz zpravidla tomu tak nen´ı) v kaˇzdé iteraci 1. kroku algoritmu, tj. pro kaˇzd´ y prvek matice - jsou mˇenˇeny maximálnˇe ˇctyˇri jeho hodnoty (tolik je maximum nenulov´ ych hodnot v 1 4 okol´ı kaˇzdého bodu). Pˇri velikosti tohoto pole Nm , celkovém poˇctu pixel˚ u Np a poˇctu zpracovávan´ ych segment˚ u k je tedy ˇcasová sloˇzitost 1. kroku algoritmu O(4kNm Np ). 2. krok algoritmu je oˇcividnˇe ˇcasovˇe konstantn´ı, docház´ı v nˇem pouze ke stanoven´ı poˇctu oddˇelen´ ych segment˚ u. Ve 3. kroku algoritmu docház´ı k opˇetovnému sekvenˇcn´ımu procházen´ı (a opˇet pro kaˇzd´ y zpracovan´ y segment) a k pˇriˇrazován´ı ˇ index˚ u jednotliv´ ym segment˚ um. Casová sloˇzitost 3. kroku je tedy O(kNp ). Celková ˇcasová sloˇzitost prostorového 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álo des´ıtek; Nm je zpravidla také v ˇra´dech jednotek aˇz nˇekolika málo des´ıtek a je závislé 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á sv˚ uj vlastn´ı seznam, staˇc´ı tedy pouze zkontrolovat velikost kaˇzdého seznamu a porovnat s nastaven´ ymi prahy.


3.5

31

Krit´ erium pro vyb´ır´ an´ı segment˚ u

C´ılem algoritmu popsaného na zaˇca´tku této kapitoly je vybrat z libovolného vstupn´ıho obrázku ˇcásti tak, aby tyto ˇca´sti odpov´ıdaly objekt˚ um v obraze. Toho se dosáhne v´ yˇse popsan´ ym segmentaˇcn´ım algoritmem. Vybrané ˇca´sti by dále mˇely b´ yt vizuálnˇe pˇrijatelné, a i kdyˇz se jedná o vcelku vágn´ı 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é rozhodnout. Zvaˇzovány byly následné deskriptory zaloˇzené na oblasti popisovaného geometrického tvaru (region-based shape descriptors[5]) • Eccentricity

udává pomˇer délky hlavn´ı osy (major axis) a vedlejˇs´ı osy (minor axis)

• Elongatedness

udává podobnost tvaru pˇr´ımce a spoˇc´ıtá se jako pomˇer ˇs´ıˇrky a v´ yˇsky nejmenˇs´ıho obklopuj´ıc´ıho obdéln´ıku (minimum area enclosing rectangle) daného tvaru

• Rectangularity

mˇeˇr´ı podobnost obdéln´ıku a je vypoˇctena jako pomˇer obsahu daného tvaru ku souˇcinu rozmˇer˚ u nejmenˇs´ıho obklopuj´ıc´ıho obdéln´ıku

• Compactness

vyjadˇruje a kruˇznice

podobnost

geometrického

tvaru

Elongatedness nelze snadno (pomoc´ı nejmenˇs´ıho obklopuj´ıc´ıho obdéln´ıku) vypoˇc´ıtat pro v´ıce zakˇrivené tvary, coˇz z n´ı dˇelá nevhodného kandidáta pro popis dobr´ ych“ tvar˚ u. Podobnost obdéln´ıku (rectangularity) ˇci ”zploˇstˇen´ı”tvaru ” (eccentricity) byly také zam´ıtnuty jako vlastnosti, které nepopisuj´ı vhodnost tvaru. Vybrána byla tedy kompaktnost; podobnost kruˇznici (kruhu) se totiˇz jevila jako vizuálnˇe uspokojivá.

3.5.1

V´ ypoˇ cet kompaktnosti geometrick´ eho tvaru

Kompaktnost geometrického tvaru (také nˇekdy naz´ yvána shape index) je numerická kvantita vyjadˇruj´ıc´ı kompaktnost tvaru (a nebo jako bylo zm´ınˇeno dˇr´ıve, podobnost tvaru a kruˇznice). Kompaktnost je uznávána jako jedna z nejzaj´ımavˇejˇs´ıch a nejd˚ uleˇzitˇejˇs´ıch vlastnost´ı geometrického tvaru a je hojnˇe pouˇz´ıvána nejen v odvˇetv´ı poˇc´ıtaˇcového vidˇen´ı[17]. Mezi pˇr´ıklady pouˇzit´ı patˇr´ı definován´ı a anal´ yza homogenn´ıch oblast´ı v´ yskytu v ekologii, object matching

32


a rozpoznáván´ı vzor˚ u (pattern recognition) v oblasti umˇelé inteligence, popis a vyhledáván´ı objekt˚ u v obrazov´ ych databáz´ıch[17]. V psychologick´ ych studi´ıch byla kompaktnost zavedena jako ukazatel stability a estetiˇcnosti geometrického tvaru[18], coˇz jen umocˇ nuje jej´ı v´ ybˇer pro selekci ”dobr´ ych”tvar˚ u. Snahy o vyjádˇren´ı kompaktnosti geometrického tvaru maj´ı dlouho historii([17]). V roce 1822 navrhl Ritter vyjádˇren´ı kompaktonosti jako pomˇer obvodu P ku ploˇse tvaru A. I kdyˇz je takové vyjádˇren´ı pˇr´ımoˇcaré, tento jednoduch´ y pomˇer se zmˇen´ı pˇri zmˇenˇe velikosti tvaru. Tuto veliˇcinu je moˇzné uˇcinit bezrozmˇernou, pokud se vypoˇcte pomˇer plochy ku druhé 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ádˇren´ım kompaktnosti tohoto typu je potom IPQ index (Osserman, 1978) dan´ y pˇredpisem

CIP Q =

4πA P2

Hodnoty CIP Q náleˇz´ı intervalu (0, 1i. Geometrické 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é. Dalˇs´ım zp˚ usobem ˇc´ıselného vyjádˇren´ı kompaktnosti je porovnáván´ı s referenˇcn´ımi tvary. Cole v roce 1964 navrhl porovnáván´ı plochy A zkoumaného tvaru s plochou nejmenˇs´ı opsané kruˇznice tomuto tvaru ASC jako alternativu ke Gibbsovˇe (1961) pomˇeru 4A/L2 , kde L je vzdálenost dvou nejvzdálenˇejˇs´ıch bod˚ u na obvodu tvaru. V roce 1984 zavedli Kim a Anderson toto porovnán´ı jako index DCM (digital compactness measure) CDCM =

A ASC

Stejnˇe jako u CIP Q náleˇz´ı hodnoty CDCM intervalu (0, 1i, kdy nejkompaktnˇejˇs´ı kruh nab´ yvá opˇet hodnoty jedna. CDCM nen´ı bohuˇzel moˇzné pouˇz´ıt na nevyplnˇené geometrické 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á vyuˇz´ıvá kruhu stejné plochy jako mˇeˇren´ y geometrick´ y objekt, konkrétnˇe velikosti pr˚ uniku tohoto kruhu a mˇeˇreného geometrického objektu (A je povrch


33

objektu, A0 povrch kruhu). Dalˇs´ı index podobn´ y CBottema pˇredstavil v roce 2000 Wentz. Jeho podoba je (pˇri stejné 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áln´ıho (tj. maximáln´ıho) pˇrekryt´ı mˇeˇreného objektu a zkonstruovaného 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á data

CN DC

4n − p −n+1 2 √ = n−2 n+1

kde p je poˇcet (mezn´ıch) hran mˇeˇreného geometrického 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ého objektu. Z v´ yˇse popsan´ ych veliˇcin na mˇeˇren´ı kompaktnosti geometrického objektu byl vybrán index CIP Q . Nejen, ˇze lze relativnˇe snadno vypoˇc´ıtat, nemá ˇzádné zásadn´ı nev´ yhody (dokáˇ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ého geometrického obrazce pˇri známém obvodu P (z anglického perimeter) a pˇri známém obsahu A (area) je CIP Q =

4πA P2

Hodnota A se pro jednotlivé segmenty snadno z´ıská jako poˇcet prvk˚ u v seznamu index˚ u reprezentuj´ıc´ıho dan´ y segment, kter´ y byl z´ıskán pˇri prostorovém oddˇelován´ı (posledn´ı provádˇen´ yu ´kol); trochu problematiˇctˇejˇs´ı je to s urˇcen´ım obvodu P. K v´ ypoˇctu obvodu geometrického obrazce je nejprve potˇreba zjistit hranici objektu, k ˇcemuˇz byl pouˇzit Freeman˚ uv ˇretˇezov´ y kód (Freeman’s chain code nebo jen Freeman’s code)[19]. Tento kód slouˇz´ı k popisu hranic objekt˚ u a vyuˇz´ıvá k tomu oznaˇcen´ı okoln´ıch pixel˚ u zkoumaného pixelu ˇc´ısly viz Obr.18. Pro u ´ˇcely této práce byla pouˇzita 8-kontektivita (z Freemanova ˇretˇezového kódu také vznikl název 1 4 okol´ı pouˇz´ıvan´ y v kapitole o oddˇelován´ı segment˚ u).

34


(a) 4-konektivita

(b) 8-konektivita

Obr. 18 Freeman˚ uv ˇretˇezov´ y kód

Od poˇca´teˇcn´ıho pixelu, kter´ y je prvn´ım a zároveˇ n i posledn´ım prvkem ˇretˇezového kódu, je sekvenc´ı (ˇretˇezem) takov´ ychto ˇc´ısel popsána hranice objektu zpravidla ve smˇeru hodinov´ ych ruˇciˇcek. Napˇr´ıklad ˇretˇezov´ y kód [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ódu[21] zaˇc´ıná v jednom z extrémn´ı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ého segmentu je z podstaty algoritmu na prostorové oddˇelen´ı zároveˇ n pixelem leˇz´ıc´ım nejv´ıce nahoˇre, je zvolen právˇe tento pixel. Dalˇs´ı pixely segmentu mohou sice leˇzet ve stejné v´ yˇsce (a to pouze napravo od prvn´ıho pixelu seznamu), pro zjiˇstˇen´ı ˇretˇezového kódu to ovˇsem nen´ı ˇzádnou pˇrekáˇzkou. Ze zvoleného 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


35

základˇ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ávan´ 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áleˇz´ı segmentu, pokraˇcuje se ve smˇeru 7 (a následnˇe 6 a 5, je-li to nutné). Po nalezen´ı správného pixelu z hranice segmentu se stejn´ ym zp˚ usobem pokraˇcuje v z´ıskáván´ı dalˇs´ıch ˇcást´ı kódu, dokud se algoritmus nevrát´ı opˇet na zaˇcátek. V kaˇzdém kroku jsou ovˇsem prozkoumávány jiné smˇery (tzn. 0, 7, 6, 5 nejsou univerzáln´ı posloupnost´ı kandidát˚ 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ého kódu 4, prvn´ım kandidátem je smˇer 6 a v pˇr´ıpadˇe jeho nevybrán´ı se pokraˇcuje dále ve smˇeru hodinov´ ych ruˇciˇcek (tj. 5, 4, 3 atd.). Popsan´ y algoritmus je vysvˇetlen na následuj´ıc´ım pˇr´ıkladu. Je uvaˇzován obrázek 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ázornˇ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á se bodem, kter´ y má index 1, a postupnˇe jsou prohledávány smˇery 0, 7, 6 a 5. Pˇresnˇeji ˇreˇceno by tyto smˇery byly prozkoumávány, jiˇz smˇer 0 ovˇsem náleˇz´ı segmentu, je tedy pˇridán do ˇretˇezového kódu a algoritmus pokraˇcuje. Prvn´ım kandidátem 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áleˇz´ı segmentu (neleˇz´ı ani v obrázku samotném) a tak je prozkoumána následuj´ıc´ı moˇznost po smˇeru hodinov´ ych ruˇciˇcek (tj. 1), která je vˇsak také 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án do ˇretˇezového kódu, kter´ y má nyn´ı tvar 0-6. Algoritmus pokraˇcuje podle stejného principu dále (dalˇs´ı krok zvaˇzuje nejdˇr´ıve smˇer 0), dokud se obrys objektu neuzavˇre. V´ ysledn´ y ˇretˇezov´ y kód má podobu 0-6-7-6-4-4-3-2-1. Po zjiˇstˇen´ı obrysu (reprezentován ˇretˇezov´ ym kódem) je jiˇz moˇzno vypoˇc´ıtat (pˇresnˇeji vzato odhadnout) hodnotu obvodu P, viz. [20]. Prvn´ı moˇznost´ı je jednoduché poˇc´ıtán´ı pixel˚ u, a i kdyˇz se jedná o velmi pˇr´ımoˇcarou moˇznost, docház´ı k podhodnocen´ı v´ ysledného obvodu; diagonáln´ı kroky (lichá ˇc´ısla v ˇretˇezovém kódu) maj´ı totiˇz ve skuteˇcnosti vˇetˇs´ı délku√neˇz uvaˇzovan´ ych 1. Freeman navrhl pro kaˇzd´ y takov´ y diagonáln´ı krok pˇriˇc´ıtat 2 nam´ısto 1, viz. [19], coˇz reflektuje skuteˇcnou vzdálenost stˇred˚ u pixel˚ u. Problém reáln´ ych objekt˚ u a jejich obrys˚ u

36


spoˇc´ıvá v digitalizaci dat. Je-li souˇca´st´ı hranice rovná pˇr´ımka (ve smyslu kolmosti k hranic´ım obrázku), vˇse funguje tak jak má. Je-li ovˇsem ta samá pˇr´ımka m´ırnˇe natoˇcena (napˇr. o nˇekolik málo stupˇ n˚ u), dojde pˇreveden´ım na obraz sloˇzen´ y z pixel˚ u k jej´ımu ”zazubatˇen´ı”a souˇcet vzdálenost´ı stˇred˚ u pixel˚ u tedy neodpov´ıdá jej´ı skuteˇcné délce. 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ém kódu a o je poˇcet lich´ ych ˇc´ısel v ˇretˇezovém kódu. Vossepoel a Smeulders[23] v´ ypoˇcet dále 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ává kolikrát ˇretˇezov´ y kód zmˇenil hodnotu (corner count). Luengo provedl experiment[20], kdy postupnˇe natáˇcel obdéln´ık a pro kaˇzdé natoˇcen´ı mˇeˇril kaˇzdou z metod jeho obvod. V´ ysledky jsou znázornˇeny na Obr.55 - na ose y je hodnota odhadnutého obvodu, na ose x natoˇcen´ı obdéln´ıku, modˇre jsou hodnoty pro poˇc´ıtán´ı pixel˚ u ˇretˇezového kódu, 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á hodnota obvodu. Je vidˇet, ˇze poˇc´ıtán´ı pixel˚ u podhodnocuje obvod u jakéhokoli natoˇcen´ı a také, ˇze metoda od Vossepoela a Smeulderse se s natoˇcen´ım vypoˇra´dá opravdu nejlépe 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án v ˇcase O(Ns ) - pˇri poˇc´ıtán´ı ˇretˇezového kódu jsou prozkoumány pixely hranice (maximálnˇe Ns ) a u kaˇzdého je v konstantn´ım ˇcase urˇcen smˇer postupu (8 moˇzn´ ych smˇer˚ u nezávisl´ ych na poˇctu pixel˚ u).


3.6

37

Operace ovlivˇ nuj´ıc´ı IP Q index

Jak je patrné z Obr.12, segmenty jsou u sv´ ych hranic velmi ˇclenité a obsahuj´ı pomˇernˇe velké 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áln´ı nedostatky odstranˇeny pomoc´ı dvou operac´ı, které IP Q index mˇen´ı (zvˇetˇsuj´ı). Tyto operace jsou vysvˇetleny v následuj´ıc´ıch dvou podkapitolách.

3.6.1

Matematick´ a morfologie

Prvn´ı z pouˇzit´ ych metod na vizuáln´ı zlepˇsen´ı segmentu se op´ırá o binárn´ı matematickou morfologii[5] (tj. morfologii binárn´ıch obraz˚ u), matematick´ y nástroj pouˇz´ıvaj´ıc´ı nelineárn´ı operátory operuj´ıc´ı na tvaru objektu. Jelikoˇz se jedná o pomˇernˇe sloˇzitou problematiku, bude zde diskutována hlavnˇe s d˚ urazem na praktické pouˇzit´ı. Morfologická anal´ yza vyuˇz´ıvá moˇznosti zápisu binárn´ıch obraz˚ u jako podmnoˇzin 2 dvojrozmˇerného prostoru cel´ ych ˇc´ısel Z . Napˇr´ıklad segment (coˇz je vlastnˇe binárn´ı 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árn´ıho obrazu

kde × pˇredstavuj´ı pixely patˇr´ıc´ı segmentu a je poˇca´tek souˇradnicové soustavy, tj. má souˇradnice (0,0), lze vyjádˇrit jako mnoˇzinu X = {(1, 0), (2, 0), (0, 1), (1, 1), (1, 2), (2, 2)} Morfologická transformace je vyjádˇrena relac´ı mnoˇzinovˇe zapsaného binárn´ıho obrazu a strukturn´ıho elementu - malé mnoˇziny vztaˇzené k lokáln´ımu poˇca´tku, která slouˇz´ı jako ”lokáln´ı sonda”v morfologick´ ych operac´ıch. Nejˇcastˇeji pouˇz´ıvané strukturn´ı elementy jsou ve Obr.23

38

Kapitola 3. Algoritmus × × × ×

×

× ×

×

× × ×

×

×

× ×

×

× ×

×

× ×

×

Obr. 23 Nejˇcastˇeji pouˇz´ıvané strukturn´ı elementy

Prvn´ım z pomocn´ ych u ´kon˚ u pouˇz´ıvan´ ych v binárn´ı morfologii je translace Xh mnoˇziny X o radiusvektor h daná 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áno Druhou pomocnou operac´ı je transpozice B jako stˇredová symetrie) ˘ = {−b : ∀b ∈ B} B Pˇr´ıklad transpozice je na Obr.25 × ×

×

B

× ×

× ˘ B

Obr. 25 Transpozice

Binárn´ı matematická morfologie vyuˇz´ıvá dvou základn´ıch operac´ı, které jsou neinvertovatelné, dilatace a eroze. Binárn´ı dilatace ⊕ lze vyjádˇrit jako X ⊕ B = {p ∈ E 2 : p = x + b, x ∈ X, b ∈ B}


39

nebo pomoc´ı Minkowského souˇctu jako sjednocen´ı posunut´ ych mnoˇzin [ X ⊕B = Xb b∈B

Pˇr´ıklad binárn´ı dilatace je na Obr.26 × × ×

×

×

× × × X

× × ×

×

× × ×

× ×

X ⊕B

B Obr. 26 Binárn´ı dilatace

Binárn´ı erozi je také moˇzné zapsat dvˇema zp˚ usoby. Bud’ se kontroluje, zda vˇsechna moˇzná posunut´ı x + b leˇz´ı v p˚ uvodn´ı mnoˇzinˇe X a pokud ano, náleˇz´ı bod x také v´ ysledku (tj. erodované mnoˇzinˇe) X B = {p ∈ E 2 : p = x + b ∈ X pro ∀b ∈ B} a nebo je eroze urˇcena jako Minkowského 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árn´ı eroze je na Obr.27 × × ×

× ×

X

×

× ×

×

×

×

× B

X B

Obr. 27 Binárn´ı eroze

Na kaˇzd´ y segment je pouˇzita binárn´ı dilatace (se strukturn´ım elementem z Obr.28), ˇc´ımˇz dojde k zaplnˇen´ı drobn´ ych dˇer a u ´zk´ ych záliv˚ u. Zároveˇ n vˇsak dojde k ”nakynut´ı”objektu a z toho d˚ uvodu je následnˇe pouˇzita binárn´ı eroze (s totoˇzn´ ym

40


strukturn´ım elementem). Takovéto posloupnosti operac´ı X • B = (X ⊕ B) B se ˇr´ıká binárn´ı 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é sloˇzitosti záleˇz´ı na datové struktuˇre, zat´ım vágnˇe oznaˇcované jako seznam, ve které je segment uchován. V kaˇzdém pˇr´ıpadˇe je tˇreba provést 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é morfologie, konkrétnˇe binárn´ıho uzavˇren´ı, se vypoˇra´dá mimo ˇclenitosti hranic i s mal´ ymi otvory v objektech, v tˇech ovˇsem mohou i nadále 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ány chybˇej´ıc´ı indexy Obr. 29 V´ yvojov´ y diagram vyplˇ nován´ı segment˚ u


41

V´ yvojov´ y diagram algoritmu pro jejich vyplnˇen´ı je na Obr.29 Sekvenˇcnˇe je procházen seˇrazen´ y seznam s indexy segmentu a po dvojic´ıch jsou kontrolovány 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é o otvor v objektu nejedná 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é 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é doplnit vˇsechny dalˇs´ı indexy v rozmez´ı této dvojice. Pro algoritmus je tedy nutné zjistit indexy leˇz´ıc´ı na hranici segmentu. K tomu se vyuˇzije ˇretˇezov´ y kód reprezentuj´ıc´ı hranici, kter´ y je spoˇc´ıtán v tˇechto m´ıstech a dále 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ého segmentu je také poˇca´teˇcn´ım pixelem pro v´ ypoˇcet ˇretˇezového kódu. Toho se vyuˇzije pˇri zjiˇst’ován´ı hraniˇcn´ıch index˚ u, které je moˇzno odvodit z tabulky ve Obr.30 (w je ˇs´ıˇrka obrázku v pixelech) hodnota ˇretˇezového kódu

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ávislosti na hodnotˇe ˇretˇezového kódu

Dále je tˇreba poˇc´ıtat s nepˇr´ıliˇs ˇcastou eventualitou, kdy jeden segment m˚ uˇze b´ yt uvnitˇr druhého. 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ádouc´ı. K zjiˇst’ován´ı takovéto situace jsou pouˇzity pozice mezn´ıch pixel˚ u kaˇzdého 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á snadno zjisti zda je segment potenciálnˇe uvnitˇr jiného ˇci nikoli. Nav´ıc z´ıskán´ı tˇechto mezn´ıch pozic nic nestoj´ı, je moˇzno je zjistit jako vedlejˇs´ı produkt binárn´ıho uzavˇren´ı, pˇri kterém jsou procházeny vˇsechny indexy kaˇzdého segmentu. Algoritmus zkoumá kaˇzdou sousedn´ı dvojici v seˇrazeném 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á sloˇzitost tohoto u ´konu je tedy O(Nb ). Pˇridáván´ı chybˇej´ıc´ıch pixel˚ u je pˇri poˇctu tˇechto pixel˚ u Nmiss moˇzné v ˇcase O(Nmiss ). Pˇri celkovém poˇctu pixel˚ u segmentu Ns se tedy ˇcasová 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ód segmentu (sloˇzitost diskutována dˇr´ıve). Nav´ıc vˇetˇsinou plat´ı, ˇze Nb Ns

42


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ého, je pˇri celkovém 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é dvojice. Samotné odstranˇen´ı pixel˚ u menˇs´ıho segmentu z vˇetˇs´ıho je ˇcasovˇe nároˇcné, pˇri velikosti malého segmentu Nsmall a velkého segmentu Nbig je ˇcasová sloˇzitost O(Nsmall Nbig ) - pro kaˇzd´ y pixel menˇs´ıho objektu je tˇreba zjistit, zda tento náleˇz´ı ve vˇetˇs´ım. Naˇstˇest´ı k tomuto jevu docház´ı velmi zˇr´ıdka.

3.6.3

V´ ysledky operac´ı

V´ ysledky obou v´ yˇse popsan´ ych operac´ı jsou znázornˇeny na pˇr´ıkladu Obr.31. Na Obr.31(a) je podoba p˚ uvodn´ıho segmentu, na prvn´ı pohled je patrné velké mnoˇzstv´ı r˚ uznˇe velik´ ych dˇer a také ˇclenitost jeho hranice viz. Obr.31(b). Aplikace binárn´ıho uzavˇren´ı odstran´ı velké mnoˇzstv´ı dˇer a zároveˇ n i vyhlad´ı hranice, viz. Obr.31(c) a Obr.31(d). Stále je vˇsak patrná 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é vybrat v´ ysledné segmenty. V´ ybˇer prob´ıhá ve tˇrech fáz´ıch: 1. Prahován´ı 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án´ı 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ázi je zohlednˇena pozice segmentu, konkrétnˇe je kontrolováno zda segment neleˇz´ı v pˇr´ıliˇsné bl´ızkosti hranic obrázku a pokud ano, je umˇele sn´ıˇzen jeho IP Q index. Tento u ´kon vycház´ı z myˇslenky, ˇze nehezké“ (tj. nepˇr´ıliˇs ” kompaktn´ı) objekty jsou vizuálnˇe pˇrijatelnˇejˇs´ı, pokud leˇz´ı uprostˇred obrázku. K urˇcen´ı vzdálenosti od hranice je pouˇzito tˇeˇziˇstˇe segmentu CoG (center of gravity), které je vypoˇcteno následovnˇe


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árn´ıho uzavˇren´ı

(e) Segment po vyplnˇen´ı dˇer Obr. 31 Zlepˇsován´ı vlastnost´ı segmentu.

44


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ázku. IP Q index je pˇrenásoben konstantou k, viz. Obr.32  0.3 pro objekty v bl´ızkosti hranic  d k=  1 jinak kde d je relativn´ı vzdálenost tˇeˇziˇstˇe objektu od hranice obrázku k hodnotˇe mez z Obr.32, konkrétnˇe minimum vzdálenost´ı y0 od levého a pravého okraje a minimum vzdálenost´ı x0 od horn´ıho ˇci doln´ıho okraje. Hodnota mez je 20% celkové ˇs´ıˇrky, respektive 15% celkové v´ yˇsky

´ Obr. 32 Uprava IP Q indexu v bl´ızkosti hranic obrázku.

k je poˇc´ıtáno zvláˇst’ pro vzdálenost od levého a pravého okraje a zvláˇst’ pro vzdálenost od horn´ıho a spodn´ıho okraje. IP Q index je potom pˇrenásoben menˇs´ı z obou hodnot, jelikoˇz pˇrenásoben´ı obˇema by velmi znev´ yhodˇ novalo objekty v roz´ıch obrázku.


45

IP Q index kaˇzdého segmentu je poté porovnáván 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ém poˇctu pixel˚ u v segmentu Ns je tedy ˇcasová sloˇzitost této 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ásleduje dˇelen´ı segment˚ u, které sice splˇ nuj´ı kritéria omezuj´ıc´ı celkovou plochu, avˇsak jsou bud’ pˇr´ıliˇs ˇsiroké, a nebo pˇr´ıliˇs vysoké. Mez´ı pro rozdˇelován´ı je 35% celkové ˇs´ıˇrky obrázku a 30% celkové v´ yˇsky obrázku. Segmenty jsou nejprve rozˇrezány na ˇs´ıˇrku a poté podélnˇe. Takov´ ymto dˇelen´ım m˚ uˇze ovˇsem doj´ıt k neˇzádouc´ı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ádouc´ı efekt dˇelen´ı velk´ ych segment˚ u.

Pˇri celkovém poˇctu pixel˚ u v segmentu Ns je ˇcasová 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ému segmentu a pak je tˇreba obdobnˇe postupovat pˇri dˇelen´ı podélném. Celková 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ého oddˇelen´ı nesouvisl´ ych segment˚ u (diskutována v pˇr´ısluˇsné kapitole).

46


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áno druhé dˇelen´ı segment˚ u podle IP Q indexu. Tentokráte nen´ı zohlednˇena pozice objektu v˚ uˇci hranic´ım obrazu, ’ nebot se pˇredpokládá odstranˇen´ı neˇzádouc´ıch objekt˚ u pˇri prvn´ım prahován´ı. 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ého prahován´ı je dát ˇsanci velk´ ym objekt˚ um, které sice samy o sobˇe nejsou kdov´ıjak kompaktn´ı, jejich ˇcásti vˇsak po jejich rozdˇelen´ı jiˇz kompaktn´ı b´ yti mohou. ˇ Casová 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ód, kter´ y se vlivem pˇr´ıpadného dˇelen´ı mohl zmˇenit.

3.8

Tvorba dodateˇ cn´ ych segment˚ u

V pˇr´ıpadˇe nˇekter´ ych vstupn´ıch obrázku je moˇzné, ˇze dosavadn´ım postupem nedojde k vybrán´ı dostateˇcného mnoˇzstv´ı segment˚ u, nemus´ı b´ yt vybrán dokonce ani jeden. Napˇr´ıklad u obrázku tvoˇreného ˇctyˇrmi r˚ uznobarevn´ ymi a stejnˇe velk´ ymi ˇctverci vzniknou sice po segmentaci ˇctyˇri kompaktn´ı segmenty, které ovˇsem neprojdou druh´ ym dˇelen´ım na základˇe velikosti (vˇsechny segmenty by mˇely velikost 25% celkového poˇctu pixel˚ u, stanovená 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ány takové segmenty, které neproˇsly prahován´ım jejich IP Q indexu. Konkrétnˇe je sn´ıˇzena mez pˇrijatelnosti z 0.28 na 0.18. Nejedná 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é segmenty, které byly odstranˇeny dˇr´ıve (kapitola 3.4). Nejsou vˇsak pouˇzity celé, dojde pouze k vyˇr´ıznut´ı jejich ˇca´st´ı. Velikost tˇechto v´ yˇrez˚ u je 12% procent celkové ˇs´ıˇrky obrazu na 12% celkové v´ yˇsky obrazu (zpravidla se tedy jedná o obdéln´ıky). Tvorba jednoho takového v´ yˇrezu prob´ıhá následovnˇe: 1. Náhodná volba um´ıstˇen´ı v´ yˇrezu (samozˇrejmˇe tak, aby leˇzel uvnitˇr pˇr´ısluˇsného velkého segmentu) 2. Kontrola pˇr´ıpustnosti v´ yˇrezu - prot´ıná-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ázku (tj. ˇcást v´ yˇrezu by mˇela b´ yt mimo obrázek), 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ého 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án´ım


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ého segmentu, z kterého je vytváˇren, coˇz znamená, ˇ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án´ı do v´ ysledku.

ano

Dostateˇcn´ y poˇcet segment˚ u

ne

ano


ne

Tvorba z velk´ ych segment˚ u

ano


ne

Tvorba náhodn´ 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áván´ım z velk´ ych segment˚ u dostateˇcn´ y poˇcet segment˚ u. Z principu v´ yˇse popsaného 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ého je tˇreba vytvoˇrit nˇekolik v´ yˇrez˚ u, záleˇz´ı uskuteˇcnitelnost tohoto u ´konu na jejich um´ıst’ován´ı, které je ovˇsem náhodné. M˚ uˇze se tedy stát, ˇze dalˇs´ı v´ yˇrez jiˇz nen´ı moˇzné vybrat (v 1. kroku nen´ı moˇzné 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ého segmentu omezen. V pˇr´ıpadˇe, ˇze ani po vyˇrezáván´ı z velk´ ych segment˚ u nen´ı dostateˇcn´ y poˇcet v´ ysledk˚ u, je pouˇzito vyˇrezáván´ı z obrázku bez omezen´ı. Princip je témˇeˇr totoˇzn´ y

48


jako u postupu v pˇredchoz´ım odstavci, neexistuje vˇsak omezen´ı na um´ıstˇen´ı v´ yˇrezu spjaté s pˇr´ısluˇsnost´ı k segmentu a v´ yˇrezy jsou jiˇz vyplnˇené. Pˇri rozumném minimáln´ım poˇctu v´ ysledn´ ych segment˚ u (v ˇrádu jednotek, konkrétnˇe byla pouˇzita mez rovna pˇeti) nedojde ani k zacyklen´ı algoritmu a je tedy vˇzdy moˇzné vybrat v´ yˇrez. Tˇret´ı fáze dodateˇcné tvorby vˇsak neprodukuje vizuálnˇe celistvé v´ yˇrezy.

3.9

Fin´ aln´ı u ´ prava segment˚ u

Na zaˇca´tku algoritmu byl kv˚ uli ˇcasov´ ym u ´sporám vstupn´ı obraz zmenˇsen, coˇz znamená, ˇze i v´ ysledné segmenty jsou zmenˇsené a je tedy tˇreba je zvˇetˇsit na p˚ uvodn´ı velikost. Opˇet je pouˇzita bilineárn´ı interpolace a pro kaˇzd´ y segment je postupováno následovnˇe: 1. Vytvoˇren´ı binárn´ıho obrazu ze segmentu. Prozat´ım byl segment reprezentován seznamem a je tedy potˇreba z nˇej vytvoˇrit binárn´ı obraz. Napˇr´ıklad ze segmentu [1, 2, 5] vznikne (pˇri velikosti p˚ uvodn´ıho obrázku 4 x 2) binárn´ı obraz [0, 1, 1, 0, 0, 1, 0, 0]. 2. Bilineárn´ı interpolac´ı je tento binárn´ı obraz pˇreveden zpˇet na p˚ uvodn´ı velikost. 3. Indexy ve zvˇetˇseném obraze s nenulovou hodnotou patˇr´ı zvˇetˇsenému segmentu (opaˇcn´ ym zp˚ usobem neˇz v 1. kroku je z obrazu vytvoˇren seznam). Rychlejˇs´ım postupem by zajisté bylo vytvoˇrit jeden binárn´ı“ obraz ze vˇsech ” segment˚ u, kde kaˇzdému segmentu by bylo pˇriˇrazeno rozd´ılné celé ˇc´ıslo. Problém by ovˇsem nastal u segment˚ u, které 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é, jak tyto hraniˇcn´ı pixely pˇriˇrazovat. Doposud byl seznam kaˇzdého segmentu obyˇcejn´ ym v´ yˇctem index˚ u, které segmentu náleˇzely. Pro zmenˇsen´ y obrázek se nejednalo o podstatn´ y problém, pro segmenty obrázku p˚ uvodn´ı (vˇetˇs´ı) velikosti docház´ı vˇsak k tvorbˇe obrovsk´ ych v´ yˇct˚ u a pˇritom je vˇetˇsina obsaˇzené informace pˇrebyteˇcná. K popisu segment˚ u je tedy pouˇzita datová struktura, která popisuje souvislé ˇcásti jako dvojici ve formátu od-do“. Pˇresnˇeji se jedná o pole [Z1 , K1 , Z2 , K2 , Z3 , K3 , ...], kde ” dvojice Zi , Ki znamená, ˇze segment obsahuje vˇsechny hodnoty v intervalu hZi , Ki i.Tato struktura je dále vysvˇetlena na následuj´ıc´ım pˇr´ıkladu. Je uvaˇzován obrázek 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


49 × × ×

× × × × ×

× × × × ×

× ×

× × ×

Obr. 35 Pˇr´ıklad segmentu jako binárn´ı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á: 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áz´ı algoritmu je oznaˇcen´ı vyseparovan´ ych oblast´ı ve vstupn´ım obrazu, k ˇcemuˇz je pouˇzito rozmazán´ı 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éto rozmazané varianty. K rozmazán´ı obrazu pouˇz´ıvá konvoluce ∗, kterou lze vyjádˇ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é pozice, h je konvoluˇcn´ı jádro (téˇz konvoluˇcn´ı maska). Pˇri volbˇe Gaussovy funkce jako jádra (také oznaˇcováno jako Weierstrassova transformace)[24] dojde k poˇzadovanému rozmazán´ı. Pˇri pouˇzit´ı takového jádra o polomˇeru r je ˇcasová sloˇzitost této operace pˇri celkovém poˇctu pixel˚ u n rovna 2 O(r n)[25]. K urychlen´ı této operace lze vyuˇz´ıt separability v´ yˇse zm´ınˇeného dvojrozmˇerného jádra, tzn. ˇze jádro lze vyjádˇrit jako souˇcin dvou jednorozmˇern´ ych jader[26] a poté postupnˇe pouˇz´ıt jednorozmˇernou konvoluci[27](tj. nejdˇr´ıve je pouˇzita jednorozmˇerná konvoluce podle ˇrádk˚ u a na v´ ysledek je pouˇzita jednorozmˇerná 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án´ım

50


s uniformn´ım konvoluˇcn´ım jádrem.[27] Uniformn´ı konvoluˇcn´ı jádro je také separabiln´ı a nav´ıc lze hodnoty konvoluce vypoˇc´ıtat v lineárn´ım ˇcase[25], nebot’ pro sousedn´ı body i a i + 1 pˇri hodnotách konvoluˇcn´ıho jádra 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árn´ı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án´ı je potom nezávislá na velikosti (uniformn´ıho) jádra (velikost jádra byla stanovena na sedm) a pˇri trojnásobném konvolován´ı, které bylo pouˇzito pro aproximaci, je rovna O(6n). Nahrazen´ı segment˚ u v p˚ uvodn´ım obraze odpov´ıdaj´ıc´ımi ˇca´stmi rozmazaného obrazu je moˇzné 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ého segmentu jsou pro snadnˇejˇs´ı rozpoznán´ı dále oznaˇceny (tyrkysovˇe), k ˇcemuˇz je tˇreba spoˇc´ıtat ˇretˇezov´ y kód kaˇzdého segmentu. Pˇri celkovém poˇctu segment˚ u k a poˇctu pixel˚ u v segmentu Ns je tedy celková sloˇzitost rozmazán´ı vyseparovan´ ych ˇcást´ı ve vstupn´ım obrázku rovna O(7n + kNs ). Porovnán´ı p˚ uvodn´ıho obrázku a obrázku s rozmazan´ ymi ˇca´stmi na m´ıstˇe segment˚ u je na Obr.36


51


(b) Obr´ azek s rozmazan´ ymi ˇcástmi na m´ıstˇe segment˚ u Obr. 36 Rozmazán´ı vyseparovan´ ych ˇcást´ı ve vstupn´ım obrázku

52


Kapitola 4. Implementace

53

Kapitola 4 Implementace V´ ysledná aplikace implementuj´ıc´ı algoritmus popsan´ y v pˇredchoz´ı kapitole byla navrˇzena a implementována pro operaˇcn´ı systém Android[28][29]. Hlavn´ım kritériem pro v´ ybˇer tohoto operaˇcn´ıho systémy bylo jeho znaˇcné 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án nár˚ 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ém˚ u na trhu v roce 2014

Spoleˇcnost Google, která operaˇcn´ı systém Android spravuje, vydává pˇribliˇznˇe kaˇzd´ ych ˇsest aˇz devˇet mˇes´ıc˚ u inkrementáln´ı upgrade, a tak docház´ı ke znaˇcné

54


roztˇr´ıˇstˇenosti trhu, kdy nové verze operaˇcn´ıho systému 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ódové 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átku v´ yvoje (zaˇca´tek podzimu 2014) napˇr´ıklad jeˇstˇe neexistovala verze 5.0, která je nyn´ı jiˇz na 5% zaˇr´ızen´ı. Aplikace je tedy dimenzována pro zaˇr´ızen´ı s verz´ı operaˇcn´ıho systému Android 4.x (minimáln´ı je API verze 14, coˇz odpov´ıdá Android 4.0-4.0.2 Ice Cream Sandwich). V´ yvoj prob´ıhal v programovac´ım jazyce Java.


4.1

55

Struktura aplikace

Základn´ımi stavebn´ımi kameny kaˇzdé android´ı aplikace jsou[34]: • Aktivity (Activities). Uˇzivatelské rozhran´ı aplikace je tvoˇreno aktivitami, které by se daly pˇripodobnit okn˚ um ˇci dialog˚ um bˇeˇzné aplikace pro stoln´ı poˇc´ıtaˇce. Myˇslenkou aplikace pro Android je velké mnoˇzstv´ı jednoduch´ ych aktivit, mezi kter´ ymi se v rámci aplikace pˇrecház´ı (je zde hojnˇe vyuˇz´ıváno tlaˇc´ıtko Zpˇet natolik bˇeˇzné pro chytré telefony i tablety). • Sluˇzby (Services). Aktivity maj´ı zpravidla krátkou dobu ˇzivota a jsou ˇcasto ukonˇcovány (napˇr´ıklad jin´ ymi aktivitami), proto existuj´ı sluˇzby, které jsou urˇceny k operac´ım prob´ıhaj´ıc´ım na pozad´ı“. Pˇr´ıkladem sluˇzby ” m˚ uˇze b´ yt pˇrehráván´ı hudby na pozad´ı - hudba hraje, i kdyˇz aktivita, která pˇrehráván´ı odstartovala jiˇz nemus´ı nutnˇe existovat. • Poskytovatelé obsahu (Content providers). Poskytovatelé 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ádá. Jedná se napˇr´ıklad o lokáln´ı databáze. • Zámˇery (Intents). Zámˇery jsou systémové zprávy, pomoc´ı kter´ ych operaˇcn´ı systém informuje aplikace o r˚ uzn´ ych událostech (napˇr´ıklad datové pˇrenosy). Nav´ıc se zámˇery nepracuje pouze operaˇcn´ı systém, ale i samotné aplikace - napˇr´ıklad vytvoˇren´ı nové aktivity prob´ıhá pomoc´ı zámˇeru. Uˇzivatelské rozhran´ı se skládá 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ém a jej´ı vzhled je tedy závisl´ y na konkrétn´ı verzi Androidu, proto zde nebude dále (pˇr´ıliˇs) diskutována.

(a) Schéma hlavn´ı aktivity

(b) Screenshot hlavn´ı aktivity

Obr. 39 Hlavn´ı aktivita MainActivity

56


Hlavn´ı aktivita aplikace MainActivity (viz. Obr.39) se skládá ze tˇr´ı ˇca´st´ı: • Vˇetˇsinu aktivity zab´ırá plocha pro zobrazen´ı vstupn´ıho obrázku, kter´ y m˚ uˇze vyuˇz´ıt celou ˇs´ıˇrku a 80% v´ yˇsky celé obrazovky. Po dokonˇcen´ı algoritmu je vstupn´ı obrázek nahrazen svou rozmazanou variantou s vyznaˇcen´ ymi hranicemi vyjmut´ ych ˇca´st´ı, viz Obr.36(b). • V pravé doln´ı ˇca´st´ı je plocha pro jednotlivé d´ılky skládanky. • Aplikace se ovládá z levé doln´ı ˇcásti - 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é doln´ı ˇca´sti, jejichˇz funkce je následuj´ıc´ı: • Select - zvolen´ı nového vstupn´ıho obrázku • Save - uloˇzen´ı zpracovaného vstupn´ıho obrázku • Load - naˇcten´ı dˇr´ıve uloˇzeného vstupn´ıho obrázku • Menu - opuˇstˇen´ı menu Zbytek obrazovky je zast´ınˇen´ım“ hlavn´ı aktivity (pr˚ uhlednost 50%) a nemá ” ˇza´dné funkˇcn´ı vyuˇzit´ı.

(a) MenuActivity

(b) LoadActivity Obr. 40 Ostatn´ı aktivity

Posledn´ı aktivitou je v´ ybˇer uloˇzeného obrázku pˇri jeho naˇc´ıtán´ı - LoadActivity, viz. Obr.40(b). Jedná se o dlaˇzdicovou galerii s miniaturami uloˇzen´ ych obrázk˚ u, která má stejnˇe jako MenuActivity pr˚ uhledné pozad´ı (celková pr˚ uhlednost je sn´ıˇzena o dalˇs´ıch 30%, tj. na 20%).


4.2

57

Funkˇ cn´ı vlastnosti aplikace

Pˇr´ıpady uˇzit´ı aplikace jsou znázornˇeny na diagramu uˇzit´ı (use case diagram) na Obr.41.

Obr. 41 Diagram uˇzit´ı

Uˇzivatel má moˇznost: • Skládat stávaj´ıc´ı skládanku • Zpracovat vybran´ y obrázek, tj. vytvoˇrit z nˇej skládanku • Vstoupit do menu a – Vybrat nov´ y obrázek ke zpracován´ı – Uloˇzit stávaj´ıc´ı skládanku – Naˇc´ıst dˇr´ıve uloˇzenou skládanku – Odej´ıt z menu

4.2.1

Skl´ ad´ an´ı skl´ adanky

Samotné skládán´ı, coˇz je hlavn´ım smyslem celé aplikace, je moˇzné po zpracován´ı vstupn´ıho obrázku nebo po naˇcten´ı dˇr´ıve uloˇzen´ ych dat. Uˇzivatel akc´ı ’ uchopit a táhnout“ ( Drag & Drop“) umist uje jednotlivé d´ılky na jejich ” ” pˇr´ısluˇsné pozice. Po u ´spˇeˇsném um´ıstˇen´ı je d´ılek odstranˇen z hrac´ı plochy, v obrázku je nahrazena rozmazaná ˇca´st p˚ uvodn´ı (tj. nerozmazanou) a zároveˇ n dojde i k odstranˇen´ı tyrkysov´ ych hranic. Po u ´spˇeˇsném um´ıstˇen´ı vˇsech d´ılk˚ u vydá aplikace krátk´ y oznamovac´ı tón.

58

4.2.2


Zpracov´ an´ı obr´ azku

Vˇsechny v´ ypoˇcetnˇe sloˇzitˇejˇs´ı operace je nutno provádˇet mimo hlavn´ı UI vlákno (v tomto pˇr´ıpadˇe MainActivity), nebot’ provád´ı-li toto vlákno jednu operaci delˇs´ı dobu (nˇekolik málo vteˇrin), zobraz´ı android ANR chybovou hláˇsky Apli” kace neodpov´ıdá“ ( Application not responding“) a dojde k ukonˇcen´ı aplikace. ” Proto drtivá vˇetˇsina u ´kon˚ u prob´ıhá ve sv´ ych vlastn´ıch vláknech, které jsou v pˇr´ıpadˇe této aplikace spouˇstˇeny v´ yhradnˇe z hlavn´ıho UI vlákna. V´ yjimkou tomu nen´ı ani vytvoˇren´ı skládanky z vybraného obrázku, jehoˇz sekvenˇcn´ı diagram je na Obr.42.

Obr. 42 Sekvenˇcn´ı diagram zpracován´ı obrázku

Pˇred samotn´ ym spuˇstˇen´ım v´ ypoˇcetn´ıch vláken jsou zablokována tlaˇc´ıtka Start, kter´ ym je tento u ´kon spuˇstˇen, a Menu. Nejprve je spuˇstˇeno vlákno ImageProcessing, které zpracuje obrázek (pˇredan´ y vláknu ve formˇe bitmapy - objekt Bitmap) podle dˇr´ıve popsaného algoritmu, nedojde vˇsak prozat´ım k rozmazán´ı vyjmut´ ych ˇcást´ı. ImageProcessing pˇred sv´ ym ukonˇcen´ım odeˇsle hlavn´ımu UI vláknu v´ ysledky - seznam index˚ u kaˇzdého v´ yˇrezu, seznam index˚ u hranice kaˇzdého v´ yˇrezu a informace o um´ıstˇen´ı v´ yˇrezu ve vstupn´ım obrázku. Tyto v´ ysledky spoleˇcnˇe se vstupn´ım obrázkem jsou pˇredány druhému vláknu (ImageButtons), které na jejich základˇe vytvoˇr´ı UI prvky pro kaˇzd´ y v´ yˇrez a poˇsle je zpˇet hlavn´ımu vláknu, ve kterém jsou tyto prvky um´ıstˇeny na obrazovku. Posledn´ım vláknem je Blurring, ve kterém, jak jiˇz název napov´ıdá, dojde na základˇe v´ ysledk˚ u z ImageProcessing k rozmazán´ı pˇr´ısluˇsn´ ych ˇca´st´ı ve zpracovávaném obrázku. Uˇzivatel je v pr˚ ubˇehu v´ ypoˇct˚ u informován pomoc´ı progress baru o aktuáln´ım stavu v´ ypoˇctu. Po skonˇcen´ı vˇsech tˇr´ı vláken je zpˇr´ıstupnˇena moˇznost Menu v MainActivity.


4.2.3

59

V´ ybˇ er vstupn´ıho obr´ azku

Sekvenˇcn´ı diagram v´ ybˇeru obrázku ke zpracován´ı 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ého zámˇeru, kter´ y spust´ı aktivitu MenuActivity.

Obr. 43 Sekvenˇcn´ı diagram v´ ybˇeru obrázku

V´ ybˇerem Select v MenuActivity dojde, opˇet pomoc´ı zámˇeru, k otevˇren´ı nativn´ı android´ı galerie, kde si uˇzivatel m˚ uˇze vybrat poˇzadovan´ y vstup. Po vybrán´ı putuje v obráceném poˇrad´ı cesta vstupn´ıho obrázku, kter´ y je v MainActivity um´ıstˇen na plochu jemu urˇcenou (dojde k upraven´ı velikosti obrázku tak, aby byl zachován pomˇer stran a zároveˇ n aby byla vyuˇzita co moˇzná nejvˇetˇs´ı ˇca´st této plochy). Po naˇcten´ı nového vstupu je zpˇr´ıstupnˇena moˇznost Start.

4.2.4

Uloˇ zen´ı skl´ adanky

Sekvenˇcn´ı diagram uloˇzen´ı skládanky je na Obr.44. Pˇr´ıstup do menu prob´ıhá stejnˇe jako pˇri vyb´ırán´ı nového vstupu. Stisknut´ım tlaˇc´ıtka Save je hlavn´ımu UI vláknu oznámeno, ˇze uˇzivatel chce uloˇzit stávaj´ıc´ı skládanku. Hlavn´ı UI vlákno následnˇe zablokuje tlaˇc´ıtka Menu a Start a spust´ı vlákno urˇcené právˇe tomuto u ´konu.

Obr. 44 Sekvenˇcn´ı diagram uloˇzen´ı skládanky

60


Kaˇzdá skládanka je uloˇzena ve formˇe ˇsesti soubor˚ u s unikátn´ım prefixem (souˇcasn´ y ˇcas v milisekundách) a následuj´ıc´ımi koncovkami (prvn´ı soubor má pˇr´ıponu .png, ostatn´ı jsou bez pˇr´ıpony): • PNG soubor bez koncovky - obrázek s rozmazan´ ymi a ohraniˇcen´ ymi pˇr´ısluˇsn´ ymi ˇcástmi, slouˇz´ı pˇri naˇc´ıtán´ı uloˇzen´ ych skládanek • bl - v´ yˇcet RGBA hodnot pixel˚ u obrázku (Android kóduje pro kaˇzd´ y pixel tyto hodnoty do jednoho bajtu, kaˇzdá sloˇzka zab´ırá 8 bit˚ u), kter´ y má vyjmuté ˇca´sti rozmazané • sg - v´ yˇcet RGBA hodnot pixel˚ u kaˇzdého v´ yˇrezu (jednotlivé segmenty jsou oddˇeleny znakem x) • pr - seznam UI parametr˚ u kaˇzdého v´ yˇrezu (parametry jednotliv´ ych segment˚ u jsou opˇet oddˇeleny znakem x) • in - bounding box kaˇzdého v´ yˇrezu • pb - vzájemná 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ádán´ı skládanky je moˇzné pouze dokonˇcen´ı zpracován´ı obrázku a nebo po naˇcten´ı uloˇzené skládanky; pokud je aktuáln´ı skládanka alespoˇ n ˇcásteˇcnˇe sloˇzená, tlaˇc´ıtko Save je zablokováno.

4.2.5

Naˇ cten´ı uloˇ zen´ e skl´ adanky

Naˇcten´ı uloˇzené skládanky (Obr.45) je v´ıceménˇ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ádanek (kaˇzdá skládanka je reprezentována zmenˇseninou PNG souboru vytvoˇreného pˇri jej´ım ukládán´ı). Cesta uloˇzeného souboru, konkrétnˇe v´ yˇse zm´ınˇen´ y prefix, je pˇres MenuActivity zaslána MainActivity, která spust´ı vlákno Loading. To na základˇe cesty naˇcte informace z pˇr´ısluˇsn´ ych soubor˚ u a pˇredá je zpˇet hlavn´ımu UI vláknu, které podle nich vytvoˇr´ı v aplikaci skládanku.


61

Obr. 45 Sekvenˇcn´ı diagram naˇcten´ı uloˇzené skládanky

Bˇehem naˇc´ıtán´ı jsou opˇet zablokována obˇe tlaˇc´ıtka v MainActivity a po jeho dokonˇcen´ı je zpˇr´ıstupnˇeno tlaˇc´ıtko Menu.

62


Kapitola 5. Testován´ı

63

Kapitola 5 Testov´ an´ı Vzhledem k c´ılové skupinˇe, pro kterou byla aplikace vyv´ıjena, byl algoritmus (konkrétnˇe jeho parametry) navrhován pro specifick´ y typ vstupn´ıch obrázk˚ u. Pˇredpokládaj´ı se jednoduché obrázky, tvoˇrené ze zˇreteln´ ych a jednoduch´ ych objekt˚ u (geometrick´ ych tvar˚ u), viz. Obr.46. Algoritmus si pˇresto dokáˇze poradit s jak´ ymkoli vstupn´ım obrázkem.

(a) Prototyp dobrého“ vstupn´ıho ” obr´ azku

(b) Prototyp ˇspatného“ vstupn´ıho ” obrázku

Obr. 46 Prototypy vstupn´ıch obrázk˚ u

5.1

Okolnosti ovlivˇ nuj´ıc´ı segmentaci obrazu

V´ ysledek algoritmu je závisl´ y pˇredevˇs´ım na segmentaci obrazu, která je do znaˇcné m´ıry ovlivnˇena formátem vstupn´ıho souboru. Jako experiment demonstruj´ıc´ı tuto závislost byl vytvoˇren syntetick´ y obrázek, Obr.47(a), kter´ y byl uloˇzen ve vˇsech tˇrech bˇeˇzn´ ych formátech, tj. PNG, JPG (JPEG) a GIF.

64


Kaˇzdá varianta byla poté algoritmem zpracována a bylo dosaˇzeno následuj´ıc´ıch závˇer˚ u. PNG je bezeztrátov´ y formát, coˇz znamená, ˇze komprese nesniˇzuje kvalitu obrázku[35]. Jak je patrné z Obr.47(d) (segmenty jako odst´ıny ˇsedi), nedocház´ı ke vzniku zrnit´ ych oblast´ı na hranic´ıch objekt˚ u popsan´ ych v kapitole 3.3. Segmenty maj´ı ostré hranice a jediné artefakty vznikaj´ıc´ı segmentac´ı jsou u ´seˇckovitého 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é u ´seˇckovité 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é vstupn´ı formáty

JPG soubory pouˇz´ıvaj´ı ztrátovou kompresi, takˇze docház´ı k patrné ztrátˇe kvality pˇri pˇribl´ıˇzen´ı[35]. Segmentac´ı JPG soubor˚ u, viz. Obr.47(c), vznikaj´ı zrnité oblasti na hranic´ıch objekt˚ u pˇresnˇe tak, jak bylo popsáno v kapitole 3.3, d˚ usledkem ˇcehoˇz mohou m´ıt segmenty ˇclenité hranice. Segmentac´ı vzniklo 36 segment˚ u, 26 bylo pro nedostateˇcnou velikost záhy odstranˇeno (celkov´ y poˇcet dále zpracovávan´ ych segment˚ u tedy z˚ ustal stejn´ y jako u PNG souboru).


65

GIF formát pouˇz´ıvá pouze paletu 256 barev. Barvy mimo tuto paletu jsou zaokrouhlovány tak, aby v n´ı leˇzely, ˇc´ımˇz v obraze vznikaj´ı skvrnité oblasti[35]. Tyto oblasti jsou patrné i pˇri segmentaci, Obr.47(b), kdy docház´ı k roztˇr´ıˇstˇen´ı objekt˚ u, které u pˇredchoz´ıch dvou formát˚ u z˚ ustaly celistvé. Segmentac´ı vzniklo 25 segment˚ u, ale 17 z nich bylo kv˚ uli poˇzadavk˚ um na minimáln´ı velikost odstranˇeno a algoritmus tedy pokraˇcoval s ménˇe segmenty neˇz tomu bylo o soubor˚ u PNG a JPG. Segmenty nav´ıc mohou m´ıt ˇclenité hranice. Segmentace je mimo formátu vstupn´ıho souboru ovlivnˇena tˇremi parametry - poˇctem bin˚ u v trojrozmˇerném histogramu. Volbou pomˇeru bin˚ u 15:7:7 (pro sloˇzky H:S:V) ovˇsem dojde k m´ırnému podsegmentován´ı, coˇz je patrné z Obr.48. Konkrétnˇe nejsou rozeznány podobné odst´ıny, napˇr´ıklad ˇcervená a oranˇzová nebo tmavˇe modrá a fialová. Zv´ yˇsen´ım poˇctu bin˚ u by sice doˇslo k odstranˇen´ı tohoto nechtˇeného efektu, docházelo by ovˇsem naopak k pˇresegmentován´ı obrazu.

(a) Origin´ aln´ı obrázek

(b) Segmentace

Obr. 48 Rozliˇsován´ı 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ázk˚ u, konkrétnˇe se pˇri obrázc´ıch sloˇzen´ ych z jednoduch´ ych geometrick´ ych tvar˚ u neoˇcekávala pˇr´ıliˇsná barevná shoda sousedn´ıch tvar˚ u.

66


5.2

Testov´ an´ı s uˇ zivateli

Pro testován´ı s uˇzivateli byly vytvoˇreny 3 sady vstupn´ıch obrázk˚ u: • Set I. 30 jednoduch´ ych obrázku ˇcasto tvoˇren´ ych pouze jednoduch´ ymi geometrick´ ymi tvary. Obrázky obsahuj´ı jasnˇe identifikovatelné a rozeznatelné objekty a maj´ı jednoduché (jednobarevné) pozad´ı. • Set II. 51 m´ırnˇe sloˇzitˇejˇs´ıch obrázk˚ 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ázk˚ u - identifikace objekt˚ u nen´ı zˇrejmá, velmi ˇcasto komplexn´ı pozad´ı. Testován´ı se u ´ˇcastnilo celkem 5 osob; kaˇzdé z nich byly ukazovány vstupn´ı obrázky a v´ ysledná skládanka vytvoˇrená aplikac´ı. Tester mˇel subjektivnˇe posoudit vizuáln´ı pˇritaˇzlivost vyseparovan´ ych d´ılk˚ u a jejich korespondenci s objekty v obraze podle stupnice: 1 - velmi ˇspatné 2 - ˇspatné 3 - uspokojivé 4 - dobré 5 - velmi dobré V´ ysledky testován´ı, viz. Obr.49, jsou v souladu s poˇzadovan´ ymi c´ıli. Set I, tedy sada obrázk˚ u, s kter´ ymi je vzhledem k c´ılové skupinˇe aplikace poˇc´ıtáno jako s ˇza´douc´ımi vstupy, je hodnocen pozitivnˇe (nejlépe hodnocen´ y je obrázek 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ázek 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ávˇer

67

Kapitola 6 Z´ avˇ er Byla vytvoˇrena funkˇcn´ı aplikace pro operaˇcn´ı systém Android splˇ nuj´ıc´ı základn´ı poˇzadavky - automatickou tvorbu hry typu puzzle z libovolného vstupn´ıho obrázku na základˇe segmentace obrazu. Aplikace umoˇzn ˇuje uˇzivateli, mimo v´ ybˇeru vstupn´ıho obrázku libovolného formátu a vlastn´ıho hran´ı, uloˇzen´ı vytvoˇrené skládanky a jej´ı opˇetovné naˇcten´ı. Pˇresto existuj´ı oblasti, které by bylo moˇzné v budouc´ım v´ yvoji zlepˇsit. Co se t´ yká algoritmu pro tvorbu skládanky, nebylo by od vˇeci zváˇzit i jiná kritéria pro v´ ybˇer ˇzádouc´ıch d´ılk˚ u neˇz jejich kompaktnost, pˇr´ıpadnˇe kritéria nˇejak zkombinovat. Dále by stály za zváˇzen´ı dalˇs´ı moˇznosti pˇri zobrazen´ı vyjmut´ ych ˇca´st´ı ve vstupn´ım obrázku, napˇr. efekt vtlaˇcen´ı. Také aplikace samotná by mohla nab´ızet dalˇs´ı volby. Pˇri tvorbˇe velkého poˇctu d´ılk˚ u (m˚ uˇze jich b´ yt aˇz nˇekolik des´ıtek na jeden obrázek) by pˇriˇsla vhod moˇznost pro pˇrep´ınán´ı poˇctu zobrazen´ ych d´ılk˚ u (napˇr´ıklad 1-5, 5-10, 10+). Dalˇs´ı funkc´ı, která by mohla b´ yt dále implementována, je mazán´ı uloˇzen´ ych skládanek pˇr´ımo z aplikace, prozat´ım je uloˇzenou skládanku moˇzné odstranit pouze ruˇcn´ım smazán´ım pˇr´ısluˇsn´ ych soubor˚ u ve sloˇzce aplikace.

68

Kapitola 6. Závˇer

Literatura

69

Literatura [1] Google Play [online]. [cit. 2015-05-04]. Dostupné 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é z: http://cs.wikipedia.org/wiki/Google Play [3] Animal Jigsaw Puzzles For Kids. Google Play [online]. [cit. 2015-05-04]. Dostupné z: https://play.google.com/store/apps/details?id=com.tula.kidjigsaws [4] Toddlers Puzzle Woozzle. Google Play [online]. [cit. 2015-05-04]. Dostupné z: https://play.google.com/store/apps/details?id=com.woozle ˇ Ć ˇ a Roger BOYLE. Image processing, ana[5] SONKA, Milan, Václav 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é z: https://archive.org/details/Lectures on Image Processing [7] Zoom An Image With Different Interpolation Types. [online]. [cit. 2015-0416]. Dostupné 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é 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é 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é 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é 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é 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é 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é 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é 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é 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é 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é 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é 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é z: http://www.cb.uu.se/ cris/blog/index.php/archives/22

72

Literatura

[28] Android [online]. [cit. 2015-05-02]. Dostupné 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é 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é 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é 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é 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é 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é z: http://www.digitaltrends.com/computing/whats-the-differencebetween-a-gif-a-jpg-and-a-png-file/

Pˇr´ıloha A. Ovládán´ı aplikace

73

Pˇ r´ıloha A Ovl´ ad´ an´ı aplikace V´ ychoz´ı stav aplikace je na Obr.50. Aplikace je ovládána dvˇema tlaˇc´ıtky v levém doln´ım rohu hlavn´ıho okna, viz Obr.51(b) - pokud má tlaˇc´ıtko ˇsedé pozad´ı (viz. tlaˇc´ıtko Start na Obr.51(a)), je zablokované, pokud má ˇcerné pozad´ı, je aktivn´ı (uˇzivatel jej m˚ uˇze pouˇz´ıt).

Obr. 50 V´ ychoz´ı obrazovka

(a)

(b)

(c)

Obr. 51 Ovládán´ı aplikace

Ve v´ ychoz´ım stavu je pˇr´ıstupná jen moˇznost Menu, po jej´ımˇz zvolen´ı se zobraz´ı menu z Obr.51(c).

74


Pro vybrán´ı nového obrázku ke zpracován´ı je tˇreba otevˇr´ıt menu a zvolit Select (ikona s puzzlem), které otevˇre galerii (jej´ı vzhled je závisl´ y na verzi operaˇcn´ıho systému) pro v´ ybˇer vstupn´ıho obrázku. Po v´ ybˇeru nového 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án´ı obrázku. Bˇehem v´ ypoˇctu jsou zablokovány moˇznosti Start a Menu a uˇzivatel je informován o pr˚ ubˇehu pomoc´ı progress baru, viz. Obr.52(a). Po dokonˇcen´ı zpracováván´ı zmiz´ı progress bar a na pozici vedle ovládac´ıch prvk˚ u jsou vyskládány vytvoˇrené d´ılky, viz. Obr.52(b).

(a)

(b) Obr. 52 Pr˚ ubˇeh zpracován´ı

Uloˇzen´ı vytvoˇrené skládanky se provád´ı z menu pomoc´ı tlaˇc´ıtka Save, viz. 51(c), které je aktivn´ı pouze po dokonˇcen´ı zpracován´ı vstupu a nebo po naˇcten´ı uloˇzené skládanky. Bˇehem ukládán´ı je uˇzivatel pˇrenesen zpˇet na hlavn´ı obrazovku a dojde ke krátkodobému zablokován´ı moˇznost´ı Start a Menu. Uˇzivatel je posléze informován o u ´spˇeˇsném 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é skládanky je moˇzné pokaˇzdé, pokud je pˇr´ıstupna moˇznost Menu. Po zvolen´ı moˇznosti Load v menu je zobrazena dlaˇzdicová galerie s miniaturami uloˇzen´ ych skládanek, viz. Obr.54. Po v´ ybˇeru uloˇzeného objektu


75

je uˇzivatel pˇrenesen zpˇet do hlavn´ıho okna, kam je naˇctena i poˇzadovaná skládanka.

Obr. 54 Dlaˇzdicová galerie pro naˇc´ıtán´ı

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án´ı mezi tˇemito dvˇema. Vlastn´ı hran´ı hry prob´ıhá intuitivnˇe pomoc´ı operace uchopit a táhnout“ ” ( Drag & Drop“), kdy uˇzivatel umist’uje jednotlivé 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ón.

76


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ého DVD

Pˇ r´ıloha C Obsah pˇ riloˇ zen´ eho DVD

Obr. 55 Obsah pˇriloˇzeného DVD

79

Automatická tvorba her typu puzzle na dotykovém zařízení s OS Android

Recommend Documents