Z TURISTICKÉ MAPY FAKULTA INFORMAČNÍCH TECHNOLOGIÍ BRNO UNIVERSITY OF TECHNOLOGY

ˇ ´ UCEN ´I TECHNICKE ´ V BRNE ˇ VYSOKE BRNO UNIVERSITY OF TECHNOLOGY

ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ˇ ´ITACOV ˇ ´ ´ ´I USTAV POC E´ GRAFIKY A MULTIMEDI FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER GRAPHICS AND MULTIMEDIA

ˇ ´ ´ REKONSTRUKCE VY´ SKOV EHO TERENU Z TURISTICKE´ MAPY

´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS

´ AUTOR PRACE AUTHOR

BRNO 2008

ˇ DAVID TUSKA

ˇ ´I TECHNICKE ´ V BRNE ˇ VYSOKE´ UCEN BRNO UNIVERSITY OF TECHNOLOGY

ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ˇ ´ITACOV ˇ ´ ´ GRAFIKY A MULTIMEDI ´ ´I USTAV POC E FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER GRAPHICS AND MULTIMEDIA

ˇ ´ ´ REKONSTRUKCE VY´ SKOV EHO TERENU Z TURISTICKE´ MAPY LANDSCAPE RECONSTRUCTION FROM TOURIST MAP

´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS

´ AUTOR PRACE

ˇ DAVID TUSKA

AUTHOR

´ VEDOUC´I PRACE SUPERVISOR

BRNO 2008

ˇ ˇ Ing. MICHAL SPAN EL

5

Abstrakt Bakal´aˇrsk´ a pr´ ace se zab´ yv´ a problematikou digitalizace turistick´ ych map. C´ılem je z´ıskat z turistick´e mapy informace o vrstevnic´ıch a v´ yˇskov´ ych hodnot´ach v jednotliv´ ych m´ıstech na mapˇe. Pomoc´ı tˇechto informac´ı se vytvoˇr´ı v´ yˇskov´a mapa, kter´a je vhodn´a k dalˇs´ımu zpracov´ an´ı. Pˇr´ıkladem m˚ uˇze b´ yt zobrazen´ı trojrozmˇern´eho modelu krajiny, kter´a m˚ uˇze b´ yt pouˇzita pˇri tvorbˇe poˇc´ıtaˇcov´ ych her.

Kl´ıˇ cov´ a slova rekonstrukce ter´enu, v´ yˇskov´ a mapa, poˇc´ıtaˇcov´e vidˇen´ı, zpracov´an´ı obrazu, detekce hran, segmentace, turistick´ a mapa

Abstract This work deals with problems of digitizing tourist map. The goal of this project is proposal and implementation computer program, which can be able to create heightmap from tourist map. Heightmap is a raster image used to store values of surface elevation. For example heightmaps are widely used in terrain rendering software and modern video games.

Keywords landscape reconstruction, heightmap, computer vision, image processing, edge detection, segmentation, tourist map

Citace David Tuˇska: Rekonstrukce v´ yˇskov´eho ter´enu z turistick´e mapy, bakal´aˇrsk´a pr´ace, Brno, FIT VUT v Brnˇe, 2008

Rekonstrukce v´ yˇ skov´ eho ter´ enu z turistick´ e mapy Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem tuto bakal´ aˇrskou pr´aci vypracoval samostatnˇe pod veden´ım pana Ing. Michala ˇ Spanˇ ela. Uvedl jsem vˇsechny liter´arn´ı prameny a publikace, ze kter´ ych jsem ˇcerpal. ....................... David Tuˇska 9. kvˇetna 2008

Podˇ ekov´ an´ı ˇ R´ad bych podˇekoval Ing. Michalu Spanˇ elovi za odborn´e veden´ı, u ´ˇceln´e pˇripom´ınky a konzultace.

c David Tuˇska, 2008.

Tato pr´ ace vznikla jako ˇskoln´ı d´ılo na Vysok´em uˇcen´ı technick´em v Brnˇe, Fakultˇe informaˇcn´ıch technologi´ı. Pr´ ace je chr´ anˇena autorsk´ym z´ akonem a jej´ı uˇzit´ı bez udˇelen´ı opr´ avnˇen´ı autorem je nez´ akonn´e, s v´yjimkou z´ akonem definovan´ych pˇr´ıpad˚ u.

Obsah ´ 1 Uvod

2

2 Zpracov´ an´ı obrazu 2.1 Co je to obraz . 2.2 Segmentace . . 2.3 Detekce hran . 2.4 Gauss˚ uv filtr . 2.5 V´ yˇskov´ a mapa

. . . . .

3 3 3 4 8 9

. . . .

10 10 12 15 19

4 Implementace 4.1 Zobrazen´ı v´ ysledn´eho 3D modelu . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Programov´ a dokumentace . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22 22 22

5 Zhodnocen´ı dosaˇ zen´ ych v´ ysledk˚ u ´ eˇsn´ 5.1 Uspˇ y pˇrevod na v´ yˇskovou mapu . . . . . . . . . . . . . . . . . . . . . . . 5.2 Uk´ azky nedostatk˚ u vybran´ ych metod . . . . . . . . . . . . . . . . . . . . . .

23 23 23

6 Z´ avˇ er

28

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3 N´ avrh 3.1 Nalezen´ı vrstevnic v obraze 3.2 Oprava z´ıskan´ ych dat . . . 3.3 Znaˇckov´ an´ı v´ yˇsek vrstevnic 3.4 Pˇrevod na v´ yˇskovou mapu .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

1

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

Kapitola 1

´ Uvod Turistickou mapu drˇzel v ruce t´emˇeˇr kaˇzd´ y z n´as. Avˇsak pouze nˇekteˇr´ı se v n´ı dok´ aˇz´ı spr´avnˇe zorientovat. Nalezneme zde cesty, hrady, z´amky, nejvyˇsˇs´ı hory a nejhlubˇs´ı jezera. Tato oznaˇcen´ı rozpozn´ a spr´ avnˇe vˇetˇsina v´ yletn´ık˚ u. Pˇredstavme si vˇsak n´asleduj´ıc´ı situaci. M´ame na v´ ybˇer dvˇe moˇzn´e cesty k naˇsemu c´ıli. Jistˇe n´as napadne ot´azka: Kter´a cesta ” je nejkratˇs´ı?“ Mus´ı n´ as vˇsak zaj´ımat nejen vzd´alenost, ale i sch˚ udnost. Zn´am´ y Murphyho z´akon ˇr´ık´ a: Zkratka je nejdelˇs´ı vzd´alenost mezi dvˇema body“. Nejkratˇs´ı cesta nen´ı vˇzdy ” tou nejoptim´ alnˇejˇs´ı. Naj´ıt nejl´epe vyhovuj´ıc´ı trasu, kter´a by nebyla pˇrehnanˇe strm´a a nesch˚ udn´ a, je mnohdy tˇeˇzk´ ym u ´kolem. Pokud nechceme n´asledovat tis´ıckr´at vyˇslapan´e cesty, mus´ıme se vyznat ve vrstevnic´ıch a alespoˇ n trochu v matematice. M´a bakal´ aˇrsk´ a pr´ ace by mˇela tento probl´em ulehˇcit. Zab´ yv´a se n´avrhem a implementac´ı algoritm˚ u, kter´e jsou schopn´e sestrojit 3D model krajiny z turistick´e mapy reprezentovan´e grafick´ ym obr´ azkem. Trojrozmˇern´e zobrazen´ı krajiny je jistˇe uˇzivatelsky zaj´ımavˇejˇs´ı a n´asledn´e hled´ an´ı turisticky nejpˇr´ıjemnˇejˇs´ı cesty m˚ uˇze b´ yt pro uˇzivatele dokonce z´abavn´e. Po prozkoum´ an´ı souˇcasn´ ych pˇr´ıstup˚ u k t´ematu m´e bakal´aˇrsk´e pr´ace jsem objevil bakal´aˇrskou pr´ aci Daniela Bierzy: Vytvoˇren´ı v´ yˇskov´e mapy z vrstevnic v rastrov´e mapˇe“. ” [1] Avˇsak po d˚ ukladn´em prozkoum´an´ı jsem doˇsel k n´azoru, ˇze je vhodn´e pouˇzit´ı jin´ ych metod pro zpracov´ av´ an´ı vrstevnic z turistick´e mapy, chtˇel bych se pokusit dospˇet k lepˇs´ım v´ ysledk˚ um, neˇz se doposud podaˇrilo panu Birzovi. Hlavn´ı rozd´ıl m´eho pˇr´ıstupu je nepˇrev´adˇet vrstevnice na vektorov´e kˇrivky, ale pracovat s nimi jako se skupinou bod˚ u v rastrov´e grafice. Proces pˇrevodu na vektorov´e kˇrivky je velmi n´aroˇcn´ y. Pokud po segmentaci 3.1 z´ısk´ame ne´ upln´ a data n´ aslednˇe reprezentovan´a pˇreruˇsen´ ymi vrstevnicemi, vyjde snaha t´emˇeˇr napr´ azdno. V´ ysledek pˇrevodu nem´ a b´ yt pˇresn´ y matematick´ y model, ale v´ yˇskov´a mapa. Prvn´ı kapitola Zpracov´ an´ı obrazu“ n´as seznamuje se z´akladn´ımi principy algoritm˚ u, ” kter´e se pouˇz´ıvaj´ı v poˇc´ıtaˇcov´e grafice, pˇredevˇs´ım pˇri pr´aci s obrazov´ ymi daty. Druh´a kapitola pojedn´ av´ a o n´ avrhu programu pro pˇrevod turistick´e mapy na v´ yˇskovou mapu, nalezneme zde anal´ yzy metod, kter´e byly pouˇzity k vytvoˇren´ı v´ ysledn´eho programu. Ve tˇret´ı kapitole je zm´ınˇena implementace programu, pojedn´av´a se zde o pouˇzit´e aplikaci pro v´ ysledn´e zobrazen´ı v´ yˇskov´e mapy. Posledn´ı kapitola se zab´ yv´a dosaˇzen´ ymi v´ ysledky a porovn´av´an´ım jednotliv´ ych algoritm˚ u.

2

Kapitola 2

Zpracov´ an´ı obrazu Poˇc´ıtaˇcov´ a grafika je jednou z nejrychleji se rozv´ıjej´ıc´ıch discipl´ın oboru informatiky. M˚ uˇzeme ji rozdˇelit na dvˇe z´ akladn´ı ˇc´ asti. Prvn´ı je vytv´aˇren´ı grafick´ ych obraz˚ u, virtu´aln´ıch sc´en a animac´ı. Tato ˇc´ ast je zastoupena v poˇc´ıtaˇcov´ ych hr´ach a kresl´ıc´ıch programech. Druhou oblast´ı, kterou se zab´ yv´ a poˇc´ıtaˇcov´ a grafika, je zpracov´an´ı obrazu a poˇc´ıtaˇcov´e vidˇen´ı. V´ ysledky je moˇzn´e vyuˇz´ıt pˇri rozpozn´ av´ an´ı textu, ˇr´ızen´ı pr˚ umyslov´ ych robot˚ u, porovn´av´an´ı otisk˚ u prst˚ u a rovnˇeˇz pro rekonstrukci v´ yˇskov´eho ter´enu z turistick´e mapy.

2.1

Co je to obraz

Matematick´ ym modelem obrazu m˚ uˇze b´ yt spojit´a funkce f (i, j) dvou argument˚ u, souˇradnic ” v rovinˇe. Funkci f (i, j) se obvykle ˇr´ık´a obrazov´a funkce. Hodnotou obrazov´e funkce je nejˇcastˇeji jas (intenzita). Jas je veliˇcina, kter´a souhrnnˇe vyjadˇruje vlastnosti obrazov´eho sign´alu zp˚ usobem, kter´ y odpov´ıd´ a jeho vn´ım´an´ı ˇclovˇekem.“ Obraz m˚ uˇze b´ yt v jednoduˇsˇs´ım pˇr´ıpadˇe monochromatick´ y. Je reprezentov´am jedinou ” obrazovou funkc´ı f (i, j). Ve sloˇzitˇejˇs´ım pˇr´ıpadˇe pracujeme s barevn´ ym (multispektr´aln´ım) obrazem. Kaˇzd´e dvojici ploˇsn´ ych souˇradnic (i, j) odpov´ıd´a vektor hodnot - napˇr. jas˚ u pro jednotliv´e barevn´e sloˇzky obrazu.“ [2]

2.2

Segmentace

Segmentace obrazu je jedn´ım z nejd˚ uleˇzitˇejˇs´ıch krok˚ u vedouc´ıch k anal´ yze obsahu zpra” cov´avan´ ych obrazov´ ych dat. Snahou je rozˇclenit obraz do ˇc´ast´ı, kter´e maj´ı u ´zkou souvislost s pˇredmˇety ˇci oblastmi re´ aln´eho svˇeta zachycen´eho na obraze. V´ ysledkem m´a b´ yt sou’ bor vz´ ajemnˇe se nepˇrekr´ yvaj´ıc´ıch oblast´ı, kter´e bud jednoznaˇcnˇe koresponduj´ı s objekty vstupn´ıho obrazu, pak jde o kompletn´ı segmentaci, nebo vytvoˇren´e segmenty nemus´ı pˇr´ımo souhlasit s objekty obrazu, a pak jde o ˇc´asteˇcnou segmentaci.“ [2] Jedn´ım z hlavn´ıch probl´em˚ u, kter´e ovlivˇ nuj´ı segmentaci, je nejednoznaˇcnost obrazov´ ych dat. Data jsou ˇcasto doprov´ azena informaˇcn´ım ˇsumem, kter´eho se snaˇz´ıme pomoc´ı segmentace zbavit a t´ım i v´ yraznˇe redukovat objem zpracov´avan´ ych dat.

2.2.1

Prahov´ an´ı

Jednou z nejjednoduˇsˇs´ıch a nejstarˇs´ıch metod segmentace je prahov´an´ı. Tato metoda je dnes v jednoduch´ ych pˇr´ıpadech st´ale pouˇz´ıv´ana. Jedn´ım z d˚ uvod˚ u je jej´ı jednoduchost implementace a tak´e rychlost. 3

C´ılem prahov´ an´ı je pro kaˇzd´ y bod obrazu (pixelu) pˇriˇradit hodnotu 1, pokud dan´ y bod leˇz´ı v hledan´e oblasti, nebo hodnotu 0 ostatn´ım bod˚ um (body pozad´ı). Prahov´an´ı je zaloˇzeno na pˇredpokladu, ˇze hledan´a oblast m´a stejnou nebo velmi podobnou hodnotu jasu. Hled´ame tedy body, jeˇz maj´ı jas v pˇredem dan´em imtervalu ha, bi 2.1. Druhou moˇznost´ı 2.2 implementace je zvolit si jak´ ysi pr´ah t. Body, kter´e maj´ı hodnotu vyˇsˇs´ı neˇz zadan´ y pr´ ah, jsou oznaˇceny za souˇc´ ast hledan´e oblasti. Ostatn´ı body jsou oznaˇceny jako body pozad´ı.  1, prof (x, y) ∈ ha, bi g (x, y) = (2.1) 0, jiank nebo  g (x, y) =

1, prof (x, y) ≥ t 0, prof (x, y) < t

(2.2)

´ eˇsnost prahov´ Uspˇ an´ı z´ avis´ı na znalosti spr´avn´e hodnoty prahu. Jestliˇze tuto hodnotu ” nezn´ame, je moˇzn´e pokusit se ji stanovit na z´akladˇe informac´ı z´ıskan´ ych z obrazu, kter´ y m´ a b´ yt segmentov´ an. Pro obrazy s bimod´aln´ım histogramem (histogram se dvˇema vrcholy) jasu se napˇr. ˇcasto doporuˇcuje volit jako hodnotu t prahu hodnotu, v n´ıˇz histogram dosahuje mezi obˇema vrcholy minima.“[3] (Obr´azek 2.1)

Obr´ azek 2.1: Bimod´aln´ı histogram jasu

Obr´azek 2.2: Vlevo p˚ uvodn´ı obr´azek. Vpravo prahov´an´ı s prahem 128. Pˇrevzato z [4]

2.3

Detekce hran

Hranu v obraze si m˚ uˇzeme pˇredstavit jako hranici mezi dvˇema oblastmi. M˚ uˇzeme ji tak´e naj´ıt na rozhran´ı svˇetla a st´ın˚ u. Hrana je vektorov´a veliˇcina, kter´a je urˇcena velikost´ı 4

Obr´ azek 2.3: Prahov´an´ı s optim´aln´ım prahem 74. Pˇrevzato z [4] a smˇerem. Form´ alnˇeji se d´ a definovat hrana jako m´ısto v obraze, kde doch´az´ı k velk´e zmˇenˇe jasov´e funkce. V tomto m´ıstˇe si m˚ uˇzeme povˇsimnout, ˇze prvn´ı derivace funkce jasu m´a vysokou hodnotu (Obr´ azek 2.4 Graf 2). Proto je nutn´e stanovit velikost prahu, kter´ y mus´ı derivace v dan´em bodˇe pˇres´ ahnout, aby byl bod povaˇzov´an za hranu. Z tohoto vypl´ yv´ a: Nejjednoduˇsˇs´ımi hranov´ ymi oper´atory jsou zjevnˇe derivace δf /δx ” a δf /δy, kter´e popisuj´ı zmˇenu u ´rovnˇe jasu ve smˇeru os x a y. Tˇechto oper´ator˚ u by bylo moˇzn´e pouˇz´ıt k hled´ an´ı hran rovnobˇeˇzn´ ych se souˇradn´ ymi osami. Pˇri hled´an´ı hran obecn´eho smˇeru je zapotˇreb´ı vyˇsetˇrovat pr˚ ubˇeh jasu ve smˇeru kolm´em na smˇer potenci´aln´ı hrany.“ [3] Kv˚ uli jednoduˇsˇs´ımu v´ ypoˇctu se vˇsak hrany detekuj´ı pouze ve dvou, respektive ve ˇctyˇrech smˇerech. Pˇri praktick´e implementaci vˇetˇsinou nepouˇz´ıv´ame pro popis obraz˚ u spojit´e funkce, ale funkce diskr´etn´ı. Snaˇz´ıme se proto derivace obrazov´e funkce aproximovat pomoc´ı diferenc´ı realizovan´ ych diskr´etn´ı konvoluc´ı. Oper´atory, kter´e odhaduj´ı prvn´ı derivaci, pouˇz´ıvaj´ı nˇekolik masek. Smˇer gradientu je moˇzno odhadovat hled´an´ım t´e masky, kter´a odpov´ıd´ a nejvˇetˇs´ı velikosti gradientu. Druhou moˇznost´ı, jak hledat hrany v obraze, je hledat m´ısto, kde druh´a derivace obrazov´e funkce proch´ az´ı nulou (Obr´ azek 2.4 Graf 3). Pˇr´ıkladem je Cannyho hranov´ y detektor.

2.3.1

Roberts˚ uv oper´ ator

Roberts˚ uv oper´ ator je nejstarˇs´ı a velmi jednoduch´ y hranov´ y oper´ator, kter´ y vyuˇz´ıv´a mal´e konvoluˇcn´ı masky (2x2), a tud´ıˇz je dosti citliv´ y na ˇsum v obraze. Jeho konvoluˇcn´ı masky jsou:     +1 0 0 +1 m1 = , m2 = (2.3) 0 −1 −1 0

Vlastn´ı velikost hrany v bodˇe (x,y) se vypoˇc´ıt´a podle funkce 2.4. q g (x, y) = (f (x, y) − f (x + 1, y + 1))2 + (f (x + 1, y) − f (x, y + 1))2

5

(2.4)

Obr´azek 2.4: Graf 1 Obrazov´ a funkce - Hrana v obraze, Graf 2 Prvn´ı derivace obrazov´e funkce. Graf 3 - Druh´ a derivace. Pˇrevzato z [5]

Obr´ azek 2.5: Detekce hran pomoc´ı Sobelova oper´atoru. Pˇrevzato z [10]

2.3.2

Sobel˚ uv oper´ ator

Oper´ator˚ u pro nalezen´ı hran v obraze je cel´a ˇrada - napˇr. Prewittov´e, Robinson˚ uv, Kirsch˚ uv a Sobel˚ uv oper´ ator. Jednotliv´e oper´atory se liˇs´ı pˇredevˇs´ım velikost´ı a koeficienty konvoluˇcn´ı masky. Velikost masky ovlivˇ nuje pˇredevˇs´ım reakci na ˇsum v obraze, ˇc´ım vˇetˇs´ı konvoluˇcn´ı maska, t´ım je reakce na ˇsum menˇs´ı. Koeficenty konvoluˇcn´ı masky ovlivnuj´ı reakci na konkr´etn´ı vlastnosti ob´ azku napˇr. rychlost r˚ ustu gradientu nebo tvar hrany. Bez ” znalost´ı statistick´ ych vlastnost´ı obr´azku nelze pˇredem ˇr´ıci, kter´ y z tˇechto oper´ator˚ u bude lepˇs´ı. Velmi ˇcasto se vhodn´ y oper´ator vyb´ır´a pokusem.“ [2] Sobel˚ uv oper´ ator je vˇetˇsinou definov´an pomoc´ı dvou konvoluˇcn´ıch matic (2.5) velikosti 3x3. Matice Gx je pouˇzita pro hled´an´ı hrany rovnobˇeˇzn´e s vodorovnou osou x, druh´a matice Gy pro hled´ an´ı hrany rovnobˇeˇzn´e s osou y. Pokud se na matice pod´ıv´ame podrobnˇeji, zjist´ıme, ˇze prvn´ı matice je pouze otoˇcenou verz´ı druh´e. Teoreticky bychom mohli matici Gx postupnˇe ot´ aˇcet o 45◦ a t´ım z´ıskat osm matic pro detekci hran v osmi smˇerech. Pro naˇse 6

u ´ˇcely n´ am ale postaˇc´ı pouze dvˇe matice 2.5.     +1 0 −1 +1 +2 +1 0 0  Gx =  +2 0 −2  , Gy =  0 +1 0 −1 −1 −2 −1

(2.5)

Pokud pomoc´ı konvoluˇcn´ıch matic 2.5 vypoˇcteme velikost gradientu ve smˇeru x a y, m˚ uˇzeme pot´e dle vzorce 2.6 vypoˇc´ıtat velikost gradientu G (Obr´azek 2.6). Pˇri implementaci hranov´eho oper´ atoru m˚ uˇzeme v´ ypoˇcet zjednoduˇsit a poˇc´ıtat pouze pˇribliˇznou hodnotu gradientu jako souˇcet absolutn´ıch hodnot gradient˚ u ve smˇerech x a y 2.7. Pro porovn´av´ an´ı velikosti gradientu s prahem, kter´ y urˇc´ı zda je bod souˇc´ast´ı hrany, n´am pˇribliˇzn´a pˇresnost postaˇc´ı. p Gx + Gy

(2.6)

G = |Gx | + |Gy |

(2.7)

G=

Z obr´ azku 2.6 m˚ uˇzeme zjistit, ˇze na z´akladˇe Gx a Gy lze velmi jednoduˇse vypoˇc´ıtat smˇer gradientu a t´ım z´ aroveˇ n smˇernici kolmice k samotn´e hranˇe. θ = arctan

Gx Gy

Obr´ azek 2.6: Smˇer a velikost hrany

7

(2.8)

2.4

Gauss˚ uv filtr

Filtrace je jednou ze z´ akladn´ıch metod u ´pravy obr´azk˚ u, m˚ uˇze b´ yt vyuˇz´ıv´ana pro vyhlazen´ı obrazu, rozostˇren´ı obrazu, potlaˇcen´ı ˇsumu, zv´ yraznˇen´ı kontrastu a ˇrady dalˇs´ıch u ´loh. Gauss˚ uv filtr je nejpouˇz´ıvanˇejˇs´ı filtr pro rozostˇrov´an´ı obr´azk˚ u a redukci ˇsumu. Jeho funkce je zaloˇzena na konvoluci obr´azku s Gaussovou funkc´ı. Konvoluci prov´ad´ıme pomoci konvoluˇcn´ı masky 2.10, kter´ a je sloˇzen´a z element˚ u urˇcen´ ych Gaussovou funkc´ı. Dvourozmˇernou Gaussovu funkci definuje 2.9, kde σ je smˇerodatn´a odchylka Gaussovy funkce. −(u2 +v 2 ) 1 2σ 2 e 2πσ 2 Konvoluˇcn´ı maska (5x5) Gaussova filtru se smˇerodatnou odchylkou σ = 0, 4:   2 4 5 4 2  4 9 12 9 4   1   5 12 15 12 5  B=   159  4 9 12 9 4  2 4 5 4 2

G(u, v) =

(2.9)

(2.10)

Obr´azek 2.7: Uk´ azka konvoluˇcn´ı matice Gaussovy funkce pro okol´ı 10 pixel˚ u a smˇerodatnou odchylku σ = 1, 8 . Pˇrevzato z [9]

Obr´ azek 2.8: Uk´ azka pouˇzit´ı Gaussova filtru s σ = 2. Pˇrevzato z [8]

8

2.5

V´ yˇ skov´ a mapa

V´ yˇskov´ a mapa (anglglicky height fields nebo height map) je vyuˇz´ıv´ana v mnoha grafick´ ych aplikac´ıch pˇredevˇs´ım pro reprezentaci ter´enu v hr´ach a simulaˇcn´ıch programech, kter´e zobrazuj´ı trojrozmˇern´ y model krajiny. Pˇr´ıklad vyuˇzit´ı v´ yˇskov´e mapy pˇri rekonstrukci ter´enu m˚ uˇzete vidˇet na obr´ azku 2.9. V´ yˇskov´ a mapa je grafick´ a reprezentace funkce, kter´a pro souˇradnice x a y vrac´ı souˇradnici z dan´e mapy tj. informaci o v´ yˇsce v dan´em bodˇe. V´ yˇskov´a mapa je zobrazena jako ˇcernob´ıl´ y obr´azek, kde ˇcern´ a barva reprezentuje nejniˇzˇs´ı v´ yˇsku (m´ısto) a b´ıl´a barva reprezentuje nejvyˇsˇs´ı v´ yˇsku (m´ısto) na mapˇe (Obr´azek 2.10). Jin´e zobrazen´ı m˚ uˇze b´ yt pomoc´ı matice hodnot, kde kaˇzd´ a buˇ nka dan´e matice reprezentuje pˇresnou v´ yˇsku ter´enu. [7]

Obr´ azek 2.9: V´ yˇskov´ a mapa a n´asledn´e zobrazen´ı ter´enu. Pˇrevzato z [7]

Obr´ azek 2.10: V´ yˇskov´ a mapa reprezentuj´ıc´ı v´ yˇsku mapy. Pˇrevzato z [6]

9

Kapitola 3

N´ avrh V n´asleduj´ıc´ı kapitole se postupnˇe sezn´am´ıme s jednotliv´ ymi kroky pˇrevodu rastrov´eho obr´azku na v´ yˇskovou mapu. Jednotliv´e kroky: • Selekce vrstevnic ze zdrojov´ ych dat pomoc´ı filtrace vybran´ ych barev. ´ • Uprava nalezen´ ych vrstevnic pro dosaˇzen´ı lepˇs´ıch v´ ysledk˚ u a jednoduˇsˇs´ı pr´ aci s vrstevnicemi. • Pˇ riˇ razen´ı v´ yˇ sek vrstevnic´ım po zad´an´ı nˇekolika vrchol˚ u. • Pˇ revod na v´ yslednou v´ yˇ skovou mapu, kter´a se m˚ uˇze d´ale vyuˇz´ıt, a samotn´ a rekonstrukci v´ yˇskov´eho ter´enu.

3.1

Nalezen´ı vrstevnic v obraze

Vstupn´ı rastrov´ y obr´ azek obsahuje mnoho informac´ı. Protoˇze by se s takov´ ym obr´azkem pracovalo obt´ıˇznˇe, mus´ıme z nˇej nejprve z´ıskat jednotliv´e vrstevnice. Ostatn´ı informace zat´ım nebudeme vyuˇz´ıvat, pro tuto chv´ıli jsou pro n´as nadbyteˇcn´e.

3.1.1

Filtrace podle barvy

Nejjednoduˇsˇs´ı moˇzn´ y zp˚ usob z´ısk´an´ı vrstevnic je selekce dle vybran´e barvy. M´ame jednu nebo v´ıce zvolen´ ych barev a dovolenou odchylku od referenˇcn´ıch barev. Pro kaˇzd´ y bod obr´azku vypoˇcteme podle vzorce 3.1 souˇcet absolutn´ıch hodnot rozd´ıl˚ u jednotliv´ ych barevn´ ych sloˇzek. Pokud vypoˇcten´ a hodnota je menˇs´ı neˇz hodnota zvolen´e odchylky, prohl´as´ıme dan´ y bod za bod vrstevnice. odchylka = |Rref − Rsel | + |Gref − Gsel | + |Bref − Bsel |

(3.1)

Jelikoˇz vrstevnice mohou m´ıt m´ısty odliˇsnou barvu, m˚ uˇzeme selekci podle barvy m´ırnˇe ´ poupravit. Uprava spoˇc´ıv´ a v tom, ˇze do zvolen´ ych barev zahrneme i barvy okol´ı bodu, jestliˇze jsou dan´e body okol´ı jiˇz souˇc´ast´ı vrstevnice. Tato u ´prava n´am sn´ıˇz´ı poˇcet nutn´ ych zad´avan´ ych referenˇcn´ıch barev a t´ım i poˇcet nutn´ ych z´asah˚ u uˇzivatele. Stejn´eho v´ ysledku bychom mohli dos´ ahnout zv´ yˇsen´ım dovolen´e odchylky, to by ale mohlo v´est k tomu, ˇze budou vybr´ any i neˇz´ adouc´ı body. 10

Obr´ azek 3.1: Selekce vybrala i okol´ı, kter´e nepatˇr´ı vrstevnici

Obr´ azek 3.2: Spr´avn´a detekce vrstevnic

3.1.2

Neˇ z´ adouc´ı okol´ı jin´ ych objekt˚ u

V okol´ı jin´ ych objekt˚ u, neˇz jsou vrstevnice, m˚ uˇzeme naj´ıt stejn´e barvy, jeˇz jsme vybrali pro selekci. Dan´ y neˇz´ adouc´ı efekt m˚ uˇzeme vidˇet na obr´azku 3.1. Proto uprav´ıme filtraci podle barvy tak, ˇze stanov´ıme jednu nebo v´ıce barev, kter´e se nesm´ı vyskytovat v tˇesn´em okol´ı vrstevnice. Pot´e vˇzdy zkoum´ ame, zda dan´ y bod obr´azku je v toleranci zvolen´e odchylky a pokud ano, zjist´ıme, zda-li v jeho bl´ızkosti nen´ı jedna ze zak´azan´ ych barev okol´ı. Spr´avnou selekci vrstevnic m˚ uˇzeme vidˇet na obr´azku 3.2. Pˇrestoˇze jsme eliminovali neˇz´ adouc´ı nadetekovan´e body na minimum, nalezneme na obr´ azku osamocen´e body, kter´e nepatˇr´ı vrstevnic´ım. Proto objekty, jeˇz jsou tvoˇreny m´enˇe neˇz tˇremi pixely, nebudeme povaˇzovat za vrstevnice.

3.1.3

Detekce hran

Pro z´ısk´ an´ı vrstevnic bychom mohli vyuˇz´ıt rovnˇeˇz detekci hran. Metoda samotn´a by vˇsak odhalila i hrany, kter´e nepatˇr´ı jednotliv´ ym vrstevnic´ım. K nalezen´ı jednotliv´ ych vrstevnic jsem proto pouˇzil selekci podle barvy. Jelikoˇz jsem dos´ahl pomoc´ı t´eto metody uspokojiv´ ych v´ ysledk˚ u, nepokouˇsel jsem se jiˇz modifikovat selekci podle barvy s detekc´ı hran, 11

Obr´ azek 3.3: Matice pro nalezen´ı koncov´ ych bod˚ u kde by detekce hran vytv´ aˇrela mapu pravdˇepodobnosti. N´asledn´a selekce podle barvy by pot´e pracovala s mapou pravdˇepodobnosti tak, ˇze by v m´ıstech, kde byla nalezena hrana, zvyˇsovala dovolenou odchylku od zvolen´e barvy vrstevnice.

3.1.4

Indexace

K dalˇs´ımu zpracov´ an´ı vrstevnic mus´ıme jednotliv´e nadetekovan´e body seskupit do objekt˚ u. Doc´ıl´ıme toho tak, ˇze budeme proch´azet jednotliv´e body obr´azku a pokud naraz´ıme na bod, kter´ y je souˇc´ ast´ı vrstevnice a z´aroveˇ n jiˇz nen´ı souˇc´ast´ı nˇejak´eho objektu (nem´a dosud pˇriˇrazeno ˇz´ adn´e ˇc´ıslo), tak mu pˇriˇrad´ıme ˇc´ıslo o 1 vyˇsˇs´ı neˇz pˇredchoz´ımu objektu. N´aslednˇe se pod´ıv´ ame na osmi-okol´ı kolem dan´eho bodu. Jestliˇze je nˇekter´ y bod tak´e neindexovan´ y bod vrstevnice, pˇriˇrad´ıme mu stejnou hodnotu jako pˇredch´azej´ıc´ımu objektu. Dan´ y princip opakujeme, dokud nenajdeme vˇsechny body dan´e vrstevnice. D´ale pokraˇcujeme v proch´ azen´ı obr´ azku a hled´ an´ı dalˇs´ıho objektu.

3.2

Oprava z´ıskan´ ych dat

Z´ıskat data pomoc´ı segmentace se nikdy nepodaˇr´ı bezchybnˇe. Jednotliv´e vrstevnice jsou ˇcasto pˇrekryty jin´ ymi znaˇckami a znaˇcen´ımi. Tato ˇc´ast kapitoly by se proto mˇela zab´ yvat opravou pˇreruˇsen´ ych vrstevnic, aby se s nimi dalo n´aslednˇe pracovat co nejjednoduˇseji.

3.2.1

Nalezen´ı koncov´ ych bod˚ u

Spojov´ an´ı pˇreruˇsen´ ych vrstevnic je zaloˇzeno na principu spojov´an´ı koncov´ ych bod˚ u dan´ ych objekt˚ u. Nejprve tedy budeme muset naj´ıt koncov´e body jednotliv´ ych vrstevnic. Detekce koncov´ ych bod˚ u je zaloˇzena na postupn´em proch´azen´ı obr´azku po bodech a pˇrikl´ ad´ an´ı matice (Obr´ azek 3.3) k jednotliv´ ym bod˚ um. Pokud je matice pˇriloˇzena tak, ˇze vˇsechny body matice oznaˇceny pomoc´ı X nezasahuj´ı do ˇz´adn´e vrstevnice, tak je prostˇredn´ı bod matice oznaˇcen jako koncov´ y bod dan´e vrstevnice. Body matice oznaˇceny zelenou barvou nejsou pro posuzov´ an´ı, zda je dan´ y bod koncov´ ym bodem vrstevnice, d˚ uleˇzit´e.

3.2.2

Spojov´ an´ı pˇ reruˇ sen´ ych vrstevnic

Nyn´ı jsme nalezli koncov´e body vrstevnic a m˚ uˇzeme se pokusit opravit pˇreruˇsen´e vrstevnice. Nejednoduˇsˇs´ım postupem, jak spojit poˇskozen´e ˇc´asti vrstevnic, je spojit nejbliˇzˇs´ı koncov´e body dvou r˚ uzn´ ych vrstevnic. Postupn´ ym pˇrikl´ad´an´ım plovouc´ıho okna“ vybereme ˇctverec ” pixel˚ u o rozmˇerech N xN . s vybran´ ymi pixely n´aslednˇe pracujeme a rozhodneme, zda se maj´ı poˇskozen´e ˇc´ asti vrstevnic spojit.

12

Pokud v r´ amci dan´eho ˇctvercov´eho v´ ybˇeru nalezneme koncov´e body, kter´e patˇr´ı dvˇema vrstevnic´ım, m˚ uˇzeme dan´e body spojit. T´ımto spoj´ıme dvˇe poˇskozen´e vrstevnice v jednu. Podm´ınkou u ´spˇeˇsn´eho spojen´ı je, aby se v dan´em v´ ybˇeru vyskytovaly pouze dan´e dvˇe vrstevnice. Pokud by ve v´ ybˇeru byla jeˇstˇe jin´a vrstevnice, hrozilo by nespr´avn´e spojen´ı koncov´ ych bod˚ u (Obr´ azek 3.6). Spr´avn´e spojen´ı koncov´ ych bod˚ u m˚ uˇzeme vidˇet na obr´azku 3.4.

Obr´ azek 3.4: Spr´avn´e spojen´ı vrstevnic (okno 7x7)

Obr´ azek 3.5: Chybn´e spojen´ı vrstevnic (okno 15x15)

Obr´ azek 3.6: Nespojeno z d˚ uvodu moˇzn´e chyby (okno 15x15)

13

Vyuˇzitelnost jednoduch´e metody spojov´an´ı nejbliˇzˇs´ıch konc˚ u vrstevnic je omezen´ a. V m´ıstech, kde je obr´ azek v´ıce poruˇsen, je tˇreba pouˇz´ıt vˇetˇs´ı rozmˇery plovouc´ıho okna“. To ” vede k tomu, ˇze mohou b´ yt spojeny ˇspatn´e koncov´e body jednotliv´ ych vrstevnic. Nespr´avn´e spojen´ı m˚ uˇzeme vidˇet na obr´ azku 3.5. Lepˇs´ıch v´ ysledk˚ u m˚ uˇzeme dos´ahnout, pokud velikost okna budeme postupnˇe zvˇetˇsovat. Avˇsak zvˇetˇsovat p˚ ujde pouze do pˇredem dan´e velikosti okna, kter´a je dle zkuˇsenost´ı je 12x12 pixel˚ u. Tuto metodu je vhodn´e vyuˇz´ıt pˇredevˇs´ım pro opravu drobn´ ych pˇreruˇsen´ı, kter´e jsou zp˚ usobeny napˇr´ıklad ˇrekami. Proto se pod´ıv´ame na zp˚ usob spojov´an´ı koncov´ ych bod˚ u pomoc´ı jejich smˇernic.

3.2.3

Nalezen´ı smˇ ernice vrstevnice

Jak je vidˇet na obr´ azku 3.5, metoda spojov´an´ı nejbliˇzˇs´ıch koncov´ ych bod˚ u m´a nev´ yhodu - mohou b´ yt spojeny koncov´e body, kter´e s velkou pravdˇepodobnost´ı nepatˇr´ı stejn´ ym vrstevnic´ım. Z tohoto d˚ uvodu by bylo v´ yhodn´e zav´est metodu spojov´an´ı, kter´a je zaloˇzena na porovn´ av´ an´ı smˇernic vrstevnic. Podm´ınka spojen´ı dvou vrstevnic by byla splnˇena, pokud pr´avˇe dvˇe vrstevnice maj´ı smˇernice opaˇcn´e. Smˇernici vypoˇc´ıt´ ame tak, ˇze koncov´ y bod um´ıst´ıme do ˇctverce 5x5 pixel˚ u (Obr´azek 3.7). Zjist´ıme, ve kter´ ych m´ıstech n´am prot´ın´a dan´a vrstevnice ˇctverec. Z tohoto m´ısta vedeme vektor do koncov´eho bodu vrstevnice. Tento vektor je z´aroveˇ n n´ami hledan´a smˇernice vrstevnice.

Obr´ azek 3.7: V´ ypoˇcet smˇernice v konci vrstevnice Pokud je vrstevnice tlustˇs´ı neˇz 1 pixel, bude prot´ınat ˇctverec na v´ıce m´ıstech vedle sebe. V takov´em pˇr´ıpadˇe vytvoˇr´ıme ze souˇradnic dan´ ych bod˚ u aritmetick´ y pr˚ umˇer. V m´ıstech, kde jsou vrstevnice velmi zakˇriveny, m˚ uˇze tato metoda urˇcit smˇernici nepˇresnˇe, coˇz vede ke spojen´ı kˇrivek, kter´e nepatˇr´ı stejn´e vrstevnici. Pro spr´avn´e napojen´ı velmi zakˇriven´ ych vrstevnic by bylo zapotˇreb´ı zn´at alespoˇ n ˇc´asteˇcn´e informace o v´ yˇsk´ach jednotliv´ ych vrstevnic. Proto se nejprve pokus´ıme pˇriˇradit nˇekter´ ym vrstevnic´ım v´ yˇsku. K t´ematu spojov´ an´ı vrstevnic se vr´ at´ıme v podkapitole Oprava vrstevnic na z´akladˇe znalosti o v´ yˇsce“ ” 3.3.2.

14

3.3

Znaˇ ckov´ an´ı v´ yˇ sek vrstevnic

V kapitole 3.1 jsme z´ıskali ze vstupn´ıch dat informace o vrstevnic´ıch. Snaˇzili jsme se z´ıskan´ a data upravit 3.2, aby se s nimi l´epe pracovalo. Nyn´ı se pokus´ıme pˇriˇradit vrstevnic´ım spr´avnou v´ yˇsku.

3.3.1

Distribuce v´ yˇ sek vrchol˚ u

Abychom mohli jednotliv´ ym vrstevnic´ım pˇriˇradit re´alnou v´ yˇsku, je tˇreba, aby uˇzivatel zadal v´ yˇsku nˇekolika vrchol˚ u na mapˇe. V´ yˇsku ze zadan´ ych vrchol˚ u budeme distribuovat pomoc´ı paprsk˚ u, kter´e postupnˇe vys´ıl´ ame z vrchol˚ u do okol´ı (Obr´azek 3.8). Kaˇzd´emu paprsku nejprve pˇriˇrad´ıme hodnotu odpov´ıdaj´ıc´ı v´ yˇsce dan´eho vrcholu zaokrouhlen´eho na des´ıtky smˇerem dol˚ u. Pokaˇzd´e, kdyˇz se paprsek protne s vrstevnic´ı, tak pˇriˇrad´ıme dan´e vrstevnici aktu´aln´ı hodnotu paprsku. N´ aslednˇe hodnotu paprsku sn´ıˇz´ıme o 10, coˇz je v´ yˇskov´ y rozd´ıl jednotliv´ ych vrstevnic na mapˇe. T´ımto zp˚ usobem pˇriˇrad´ıme vrstevnic´ım, kter´e leˇz´ı nejbl´ıˇze vrcholu, nˇekolik v´ yˇskov´ ych hodnot. Z tˇechto hodnot m˚ uˇzeme pot´e vybrat tu nejˇcetnˇejˇs´ı nebo z dan´ ych hodnot vytvoˇrit aritmetick´ y pr˚ umˇer.

Obr´ azek 3.8: K´otov´an´ı pomoc´ı paprsk˚ u z vrcholu Paprsky z jednotliv´ ych vrchol˚ u budeme vys´ılat jen do pˇredem dan´e vzd´alenosti od vrcholu. K z´ akladn´ımu ok´ otov´ an´ı nejbliˇzˇs´ıch vrstevnic n´am bude staˇcit paprsky vys´ılat pˇribliˇzne 70 aˇz 150 pixel˚ u od vrcholu. V ide´aln´ım pˇr´ıpadˇe bychom tedy vytvoˇrili kruˇznici se stˇredem ve vrcholu urˇcit´e hory. N´aslednˇe bychom vedli pˇr´ımky z vrcholu k jednotliv´ ym bod˚ um kruˇznice. Dan´e pˇr´ımky by n´am pot´e reprezentovaly jednotliv´e paprsky. Abychom nemuseli implementovat pohyb bodu po kruˇznici, spokoj´ıme se s t´ım, ˇze m´ısto kruˇznice pouˇzijeme ˇctverec. Dosaˇzen´ y v´ ysledek bude stejn´ y a implementace pohybu bodu po ˇctverci (Obr´azek 3.8), kter´ y budeme propojovat s vrcholem, bude mnohem jednoduˇsˇs´ı. T´ımto zp˚ usobem jsme z´ıskali z´akladn´ı ok´otov´an´ı nejbliˇzˇs´ıch vrstevnic okolo vrchol˚ u.

3.3.2

Oprava vrstevnic na z´ akladˇ e znalosti o v´ yˇ sce

Nyn´ı se pokus´ıme vr´ atit k opravˇe jednotliv´ ych vrstevnic za pomoc´ı novˇe z´ıskan´ ych informac´ı o v´ yˇsk´ ach vrstevnic, kter´e leˇz´ı nejbl´ıˇze vrchol˚ um. Od kaˇzd´eho vrcholu si vybereme nejbliˇzˇs´ı vrstevnice tj. vrstevnice, kter´e maj´ı nejˇcetnˇejˇs´ı pˇriˇrazenou hodnotu rovnu v´ yˇsce vrcholu zaokrouhlenou na des´ıtky dol˚ u. Napˇr´ıklad pro vrchol vysok´ y 837m vybereme vˇsechny vrstevnice, kter´e maj´ı nejˇcetnˇejˇs´ı pˇriˇrazenou hodnotu

15

830m. Jelikoˇz vybran´e vrstevnice maj´ı stejnou velikost, je velmi pravdˇepodobn´e, ˇze to jsou ˇc´asti jedn´e pˇreruˇsen´e vrstevnice. Proto se pokus´ıme dan´e ˇc´asti vrstevnice spojit.

Obr´ azek 3.9: Zv´ yraznˇen´ı nejˇcetnˇejˇs´ı pˇriˇrazen´e hodnoty po prvn´ım ok´otov´an´ı Postupnˇe se budeme pokouˇset jednotliv´e ˇc´asti vrstevnic spojit tak, ˇze kaˇzd´e vrstevnici nalezneme nelbliˇzˇs´ı vrstevnici, se kterou danou vrstevnici spoj´ıme. Pro kaˇzd´e dvˇe vrstevnice si tedy vypoˇc´ıt´ ame jejich vz´ajemnou vzd´alenost. Vyuˇzijeme informaci o koncov´ ych bodech, vzd´ alenosti budeme poˇc´ıtat pouze mezi tˇemito body. Jednotliv´e vzd´alenosti mezi vrstevnicemi seˇrad´ıme vzestupnˇe, takto vybereme nejbliˇzˇs´ı dvˇe vrstevnice, kter´e spoj´ıme. Pro spojen´ı dvou ˇc´ ast´ı vrstevnic m´ame dvˇe z´akladn´ı podm´ınky. Prvn´ı podm´ınkou je stejn´a pˇriˇrazen´ a v´ yˇska spojovan´ ych ˇc´ast´ı, kter´a je zajiˇstˇena v´ ybˇerem vrstevnic, nad nimiˇz prov´ad´ıme dan´e operace. Dalˇs´ı nutnou podm´ınkou je, ˇze pˇri propojov´an´ı jednotliv´ ych vrstevnic nen´ı pˇrekˇr´ıˇzena ˇz´ adn´ a jin´ a vrstevnice. Po propojen´ı dvou kˇrivek v jednu vrstevnici se pokus´ıme znovu naj´ıt koncov´e body vrstevnice tak, aby se odruˇsily koncov´e body v okol´ı spojen´ı. Algoritmus spojov´ an´ı jednotliv´ ych ˇc´ast´ı vrstevnic opakujeme tak dlouho, dokud n´am nez˚ ustane pouze jedna vrstevnice, nebo nejde vytvoˇrit propojen´ı, kter´e by neporuˇsilo z´akladn´ı pravidla propojen´ı.

Obr´ azek 3.10: Oprava nejbliˇzˇs´ı vrstevnice Pokud n´ am po spojov´ an´ı z˚ ustane pouze jedna vrstevnice, m˚ uˇzeme se domn´ıvat, ˇze je elipsovit´eho tvaru (Obr´ azek 3.10). M˚ uˇzeme se pokusit danou elipsu uzavˇr´ıt. Abychom zjistili, zda je vhodn´e koncov´e body vrstevnice spojit, lze vyuˇz´ıt smˇernice vrstevnice v koncov´ ych bodech 3.2.3. Pokud jsou jednotliv´e smˇernice v koncov´ ych bodech bodech opaˇcn´e, ◦ nebo alespoˇ n s pˇresnost´ı 30 , m˚ uˇzeme koncov´e body dan´e vrstevnice spojit a takto p´adem uzavˇr´ıt vrstevnici. 16

Takto jsme opravili nejbl´ıˇze leˇz´ıc´ı vrstevnici kaˇzd´eho vrcholu. Nyn´ı se pokus´ıme dan´ y postup opakovat a opravit i dalˇs´ı vrstevnice okolo vrcholu. Aby se n´am nekumulovala chyba z pˇredchoz´ıch k´ otov´ an´ı, odstran´ıme vˇsem vrstevnic´ım pˇriˇrazen´e hodnoty. Doc´ıl´ıme toho, ˇze n´asleduj´ıc´ı k´ otov´ an´ı bude pˇresnˇejˇs´ı. Celkov´ y postup budeme opakovat pˇribliˇznˇe 5 aˇz 10 kr´at. V´ ysledek opravy vrstevnic po opakov´an´ı algoritmu je vidˇet na obr´azku 3.11.

Obr´azek 3.11: Oprava vrstevnic po 1. a 6. iteraci algoritmu zaloˇzen´eho na znalosti v´ yˇsky vrstevnic

3.3.3

Distribuce v´ yˇ sek mezi vrstevnicemi

Jelikoˇz pˇresnost k´ otov´ an´ı pomoc´ı paprsk˚ u z vrcholu 3.3.1 s rostouc´ı vzd´alenost´ı od vrcholu kles´a, je nutn´e, abychom se zamˇeˇrili i na jin´e metody k´otov´an´ı. Pomoc´ı metody vys´ılan´ ych paprsk˚ u“ z vrcholu 3.3.1 se n´am podaˇrilo spr´avnˇe ok´otovat ” vrstevnice, kter´e leˇz´ı nejbl´ıˇze vrcholu. Protoˇze potˇrebujeme ok´otovat i vzd´alenˇejˇs´ı vrstevnice, bylo by vhodn´e distribuovat v´ yˇsku i mezi vrstevnicemi d´ale od vrcholu. Z kaˇzd´eho bodu vrstevnice povedeme kolmici na jej´ı smˇer vrstevnce (Obr´azek 3.12 ) a budeme se snaˇzit distribuovat v´ yˇsku obˇema smˇery.

Obr´ azek 3.12: Distribuce v´ yˇsky mezi vrstevnicemi 17

Na z´ akladˇe pˇriˇrazen´ ych hodnot hodnot zjist´ıme, ˇze nˇekter´e vrstevnice jsou ok´otov´any l´epe, jin´e h˚ uˇre. Pravdˇepodobnost spr´avn´eho“ ok´otov´an´ı vypoˇc´ıt´ame jako pomˇer nejˇcetnˇejˇs´ı ” pˇriˇrazen´e hodnoty ku celkov´emu poˇctu pˇriˇrazen´ ych hodnot. Napˇr´ıklad m˚ uˇzeme nal´ezt vrstevnici, kter´ a bude m´ıt nejˇcetnˇejˇs´ı v´ yˇsku 680m zastoupenu 75×, celkovˇe bude pˇriˇrazeno vrstevnici 100 hodnot. Pravdˇepodobnost, ˇze vrstevnice m´a v´ yˇsku 680m, je 75%. Zaˇcneme postupnˇe zpracov´ avat vrstevnice podle pravdˇepodobnosti ok´otov´an´ı. Nejprve ty, kter´e maj´ı pravdˇepodobnost nejvyˇsˇs´ı, pot´e vrstevnice s niˇzˇs´ı pravdˇepodobnost´ı. Pravdˇepodobnost zpracovan´ ych vrstevnic by nemˇela klesnout pod 75%. Pokud bychom zpracov´avali vrstevnice s pravdˇepodobnost´ı niˇzˇs´ı neˇz 75%, zvyˇsovala by se pravdˇepodobnost, ˇze vrstevnice je nespr´ avnˇe ok´ otovan´ a, coˇz by mˇelo za n´asledek distribuci chyby na okoln´ı vrstevnice. Pro v´ ypoˇcet kolmic k dan´e vrstevnici pouˇzijeme Sobel˚ uv oper´ator 2.3.2, kter´ y se vyuˇz´ıv´ a pro detekci hran. Lze jej vyuˇz´ıt tak´e k v´ ypoˇctu kolmice na hranu v dan´em bodˇe 2.8. Pro v´ ypoˇcet Solbelova oper´ atoru se pouˇzije p˚ uvodn´ı obr´azek turistick´e mapy, pokud bychom v´ ypoˇcet prov´ adˇeli z obr´ azku, ve kter´em jsou zv´ yraznˇeny pouze vrstevnice, byl by v´ ypoˇcet m´enˇe pˇresn´ y. Abychom nemuseli prov´adˇet v´ ypoˇcet Sobelova oper´atoru pro cel´ y obr´azek, budeme prov´ adˇet v´ ypoˇcet pouze v nejbliˇzˇs´ım okol´ı dan´e vrstevnice v m´ıstˇe kde je pˇredpokl´adan´ a hrana obrazu. Kolmici z hrany vrstevnice vedeme obousmˇernˇe do vzd´alenosti pˇribliˇznˇe 75 pixel˚ u. Vrstevnic´ım, kter´e kolmic´ı protneme, se budeme snaˇzit pˇriˇradit spr´avnou“ v´ yˇsku odvozenou ” z vrstevnice, ze kter´e vedeme kolmici. Pˇri distribuci a rozpoˇc´ıt´ av´ an´ı v´ yˇsky na sousedn´ı vrstevnice m˚ uˇze nastat nˇekolik pˇr´ıpad˚ u. Nejjednoduˇsˇs´ı pˇr´ıpad rozpoˇc´ıt´ av´ an´ı vid´ıme na obr´azku 3.12, kde v´ yˇsky vˇsech protnut´ ych vrstevnic tvoˇr´ı ryze monot´ onn´ı posloupnost (tj. klesaj´ıc´ı nebo rostouc´ı posloupnost). Snaˇz´ıme se tedy naj´ıt smˇer posloupnosti a n´aslednˇe v dan´em smˇeru rozpoˇc´ıtat v´ yˇsky sousedn´ıch vrstevnic.

Obr´ azek 3.13: Distribuce v´ yˇsky mezi vrstevnicemi - pˇrechod pˇres stejnou vrstevnici Sloˇzitˇejˇs´ı pˇr´ıpad k´ otov´ an´ı m˚ uˇzeme spatˇrit na obr´azku 3.13. Pˇri k´otov´an´ı dojde k tomu, ˇze jedna vrstevnice je protnuta dvakr´at, v tomto pˇr´ıpadˇe vrstevnice netvoˇr´ı monot´onn´ı posloupnost. V m´ıstˇe, kde je stejn´a vrstevnice protnuta dvakr´at za sebou se bude mˇenit smˇer posloupnosti. Bude zde lok´ aln´ı minimum nebo maximun posloupnosti.

18

Obr´ azek 3.14: Distribuce v´ yˇsky mezi vrstevnicemi - ˇspatn´e ok´otov´an´ı kv˚ uli pˇreruˇsen´ı Probl´em nastane, pokud se ned´a m´ısto, kde je vrstevnice protnuta dvakr´at, pˇresnˇe lokalizovat z d˚ uvodu pˇreruˇsen´ı vrstevnic (Obr´azek 3.14 ). Doch´az´ı k chybn´emu ok´otov´an´ı, kter´e m˚ uˇze zhorˇsit v´ ysledn´ y pˇrevod na v´ yˇskovou mapu. Po zpracov´ an´ı kaˇzd´e vrstevnice pˇrepoˇc´ıt´ame pravdˇepodobnosti ok´otov´an´ı jednotliv´ ych vrstevnic. Oznaˇc´ıme si vrstevnici, kterou jsme jiˇz zpracovali, a pokraˇcujeme dokud nezpracujeme vˇsechny ostatn´ı nebo dokud nenalezneme vrstevnici, kter´a by mˇela pravdˇepodobnost ok´otov´ an´ı vˇetˇs´ı neˇz 75%. T´ımto postupem by se n´am mˇelo podaˇrit ok´otovat i vrstevnice, kter´e leˇz´ı d´ ale od vrchol˚ u.

3.4

Pˇ revod na v´ yˇ skovou mapu

V tento okamˇzik m´ ame ok´ otovanou vˇetˇsinu vrstevnic a m˚ uˇzeme je zaˇc´ıt pˇrev´adˇet na c´ılovou v´ yˇskovou mapu. Nejprve ale mus´ıme vˇsem obr´azkov´ ym bod˚ um pˇriˇradit v´ yˇsku.

3.4.1

V´ ypoˇ cet v´ yˇ sky pomoc´ı paprsk˚ u od vrcholu

Prozat´ım jsme pˇriˇrazovali v´ yˇskovou hodnotu pouze vrstevnic´ım. Nyn´ı zaˇcneme pˇriˇrazovat v´ yˇsku tak´e jednotliv´ ym bod˚ um vstupn´ıho obr´azku. Pˇrevod na v´ yˇskovou mapu zaˇcneme podobnˇe jako pˇri k´ otov´ an´ı vrstevnic z vrchol˚ u 3.3.1. Tentokr´at budeme vys´ılat paprsky do vˇetˇs´ı vzd´ alenosti neˇz pˇri k´ otov´ an´ı, protoˇze jiˇz m´ame vrstevnice opraveny a ok´otov´any. Pokud vyˇsleme paprsek z vrcholu, protne n´am nˇekolik vrstevnic. T´ım se n´am paprsek rozdˇel´ı na nˇekolik ˇc´ ast´ı. Jednotliv´e ˇc´asti budeme zpracov´avat postupnˇe. Zaˇcneme prvn´ım u ´sekem, kter´ y vede od samotn´eho vrcholu k prvn´ı protnut´e vrstevnici. Zjist´ıme d´elku dan´eho u ´seku d (poˇcet pixel˚ u na u ´seku) a v´ yˇskov´ y rozd´ıl ∆h, kter´ y vypoˇc´ıt´ame jako rozd´ıl vrcholu a dan´e vrstevnice. Pomoc´ı vzorce 3.2 vypoˇcteme strmost dan´eho u ´seku. Ta n´ am ud´av´a v´ yˇskov´ y rozd´ıl mezi dvˇemi sousedn´ımi pixely. Jednotliv´ ym bod˚ um pomoc´ı strmosti pˇriˇrad´ıme vypoˇctenou v´ yˇsku. Tento postup opakujeme na dalˇs´ıch u ´sec´ıch d´ale od vrcholu. strmost =

3.4.2

∆h d

(3.2)

V´ ypoˇ cet v´ yˇ sky mezi vrstevnicemi

Pomoc´ı pˇredchoz´ı metody se n´ am podaˇrilo pˇrev´est vrcholy hor a jejich bl´ızk´e okol´ı na v´ yˇskovou mapu. Abychom pˇrevedli i zbytek mapy, pouˇzijeme metodu obdobnou metodˇe kolmic, jeˇz jsme pouˇzili pˇri k´ otov´an´ı 3.3.3.

19

Metoda paprsk˚ u n´ am k jednotliv´ ym bod˚ um pˇriˇradila 0 aˇz n v´ yˇskov´ ych hodnot. Postupnˇe projdeme vˇsechny vrstevnice, pokud bude m´ıt nˇekter´ y bod vrstevnice pˇriˇrazeno m´enˇe jak pˇet hodnot, tak z dan´eho bodu povedeme kolmici k vrstevnici. Kolmice n´am protne vrstevnice a pro z´ıskan´e u ´seky rozpoˇc´ıt´ame v´ yˇskov´e hodnoty podobnˇe jako u pˇredchoz´ı metody. Nakonec vypoˇc´ıt´ ame pro kaˇzd´ y obr´azkov´ y bod pr˚ umˇer pˇriˇrazen´ ych v´ yˇsek. Jednotliv´e hodnoty bychom mohli uloˇzit jako matici do textov´eho souboru, t´ım z´ısk´ame jeden moˇzn´ y zp˚ usob reprezentace v´ yˇskov´e mapy.

3.4.3

Uloˇ zen´ı v´ yˇ skov´ e mapy do obr´ azku

Nejpouˇz´ıvanˇejˇs´ı form´ at v´ yˇskov´e mapy (popsan´ y v kapitole 2.5) je ˇcernob´ıl´ y obr´azek, kter´ y obsahuje 256 stupˇ n˚ u ˇsedi. Pro kaˇzd´ y bod obr´azku pˇrevedeme vypoˇc´ıtanou v´ yˇsku na intenzitu ˇsedi pomoc´ı vzorce 3.3, kde hmin a hmax jsou minim´aln´ı a maxim´an´ı v´ yˇsky na dan´e mapˇe. int =

3.4.4

h − hmin ∗ 255 hmax − hmin

(3.3)

Vyhlazen´ı v´ yˇ skov´ e mapy

V´ ysledn´ a v´ yˇskov´ a mapa by mˇela splˇ novat z´akladn´ı dvˇe podm´ınky. Prvn´ı podm´ınkou je pˇresnost pˇrevodu zadan´e mapy na c´ılovou v´ yˇskovou mapu, druhou, ˇze v´ yˇskov´a mapa by mˇela tvoˇrit hladk´ y gradient bez hran. Na obr´ azku 3.15 vid´ıme uk´ azku okrajov´e ˇc´asti mapy, kde pˇri pˇrevodu na v´ yˇskovou mapu doˇslo k drobn´e chybˇe, kter´ a byla zp˚ usobena t´ım, ˇze na okraji mapy jiˇz nem´ame dostateˇcn´e informace pro v´ ypoˇcet spr´ avn´e v´ yˇsky. Aby byla v´ ysledn´a v´ yˇskov´a mapa l´epe pouˇziteln´ a zbav´ıme se prudk´ ych pˇrechod˚ u pomoc´ı Gaussova filtru 2.4. Filtr budeme aplikovat na cel´ y v´ ysledn´ y obr´ azek. M´ısta, kter´ a nejsou poˇskozen´a, by Gauss˚ uv filtr mˇel ovlivnit minim´alnˇe. V´ ysledn´e pouˇzit´ı Gaussova filtru pro vyhlazen´ı m˚ uˇzeme vidˇet na obr´azku 3.16.

20

Obr´azek 3.15: Vlevo ˇc´ ast poˇskozen´e v´ yˇskov´e mapy. Vpravo detekce hran pro urˇcen´ı chybn´eho pˇrevodu na v´ yˇskovou mapu

Obr´ azek 3.16: Pouˇzit´ı Gaussova filtru pro vyhlazen´ı v´ ysledn´e v´ yˇskov´e mapy

21

Kapitola 4

Implementace Pro implementaci aplikace jsem vybral programovac´ı jazyk C++ pˇredevˇs´ım z d˚ uvodu pˇrenositelnosti mezi OS MS Windows a Linux. Pro zpracov´av´an´ı obrazov´ ych dat a snadnˇejˇs´ı pr´aci s nimi jsem pouˇzil grafickou knihovnu OpenCV (Open Source Computer Vision Libary) vyv´ıjenou firmou Intel a dostupnou na internetov´e str´ance http://www.intel.com/technology/computing/opencv/. Hlavn´ım d˚ uvodem m´eho rozhodnut´ı bylo pˇr´ıvˇetiv´e rozhran´ı knihovn´ıch funkc´ı a jednoduch´e vestavˇen´e GUI (Grafick´e uˇzivatelsk´e rozhran´ı). Pˇri n´ avrhu aplikace je kladen d˚ uraz na oddˇelen´ı logick´e ˇc´asti programu od uˇzivatelsk´eho rozhran´ı. To n´ am dovoluje jednoduˇse pˇrepracovat uˇzivatelsk´e rozhran´ı bez nutn´eho z´asahu do samotn´e aplikace. Detailnˇejˇs´ı informace naleznete v programov´e dokumentaci 4.2.

4.1

Zobrazen´ı v´ ysledn´ eho 3D modelu

Pro v´ ysledn´e zobrazen´ı v´ yˇskov´eho modelu byla pouˇzita aplikace vytvoˇren´a na z´akladˇe internetov´eho tutori´ alu Nehe (http://nehe.gamedev.net/data/lessons/lesson.asp?lesson=45). Aplikace je zaloˇzena na OpenGl a vyuˇz´ıv´a rozˇs´ıˇren´ı modern´ıch grafick´ ych karet naz´ yvan´e Vertex Buffer Object“. Pokud grafick´a karta nepodporuje dan´e rozˇs´ıˇren´ı, je pro vykreslen´ı ” pouˇzita pomalejˇs´ı metoda pomoc´ı Vertex Arrays“. ” Pˇrevzat´ a aplikace zpracov´ av´ a v´ yˇskovou mapu ve formˇe ˇcernob´ıl´eho obr´azku uloˇzen´eho ve form´ atu BMP (Microsoft Windows Bitmap). Na pˇriloˇzen´em CD m˚ uˇzete naj´ıt upravenou aplikaci, kter´ a kromˇe v´ yˇskov´e mapy dok´aˇze naˇc´ıst tak´e obr´azek s texturou, kter´a se model krajiny namapuje.

4.2

Programov´ a dokumentace

Programovou dokumentaci lze nal´ezt na pˇriloˇzen´em CD v adres´aˇri prog doc.

22

Kapitola 5

Zhodnocen´ı dosaˇ zen´ ych v´ ysledk˚ u Tato kapitola se zab´ yv´ a zhodnocen´ım v´ ysledk˚ u bakal´aˇrsk´e bakal´aˇrsk´e pr´ace. Nejprve se pod´ıv´ame na u ´spˇeˇsn´ y pokus pˇrevodu turistick´e mapy na v´ yˇskovou mapu, n´aslednˇe se zamˇeˇr´ıme na nedostatky vybran´ ych pouˇzit´ ych metod.

5.1

´ eˇ Uspˇ sn´ y pˇ revod na v´ yˇ skovou mapu

Na obr´ azc´ıch 5.1 aˇz 5.5 si m˚ uˇzeme vˇsimnout relativnˇe dobr´ ych v´ ysledk˚ u. Selekce 5.2 s n´asledn´ ym nalezen´ım koncov´ ych bod˚ u se podaˇrila velmi dobˇre. Na obr´ azku 5.3 je zn´ azornˇeno ok´otov´an´ı vrstevnic. Kaˇzd´e v´ yˇskov´e hodnotˇe je pˇriˇrazena barva podle dan´e v´ yˇsky (des´ıtek hodnoty v´ yˇsky). Vrstevnice tˇesnˇe kolem vrcholu jsou spr´avnˇe opraveny a ok´ otov´ any. Vzd´alenˇejˇs´ı vrstevnice mohou b´ yt h˚ uˇre ok´otov´any z d˚ uvodu pˇreruˇsen´ı vrstevnic. Bylo by vhodn´e pomoc´ı znalosti o v´ yˇsce opravovat vrstevnice nejen kolem vrcholu, ale i ty vzd´ alenˇejˇs´ı. Opravov´an´ı vzd´alenˇejˇs´ıch vrstevnic nese mimo jin´e i riziko, ˇze dojde k chybn´emu spojen´ı distribuuj´ıc´ıho se i d´ale. V´ yˇska jednotliv´ ych vrstevnic je line´arnˇe rozpoˇc´ıt´ana do okoln´ıch bod˚ u a pˇrevedena na v´ yˇskovou mapu, v´ ysledek pˇrevodu m˚ uˇzeme vidˇet na obr´azku 5.4. Na z´ akladˇe p˚ uvodn´ı turistick´e mapy a vytvoˇren´e v´ yˇskov´e mapy m˚ uˇzeme vytvoˇrit trojrozmˇern´ y model krajiny (Obr´ azek 5.5).

5.2

Uk´ azky nedostatk˚ u vybran´ ych metod

Pokud na mapˇe leˇz´ı vrstevnice bl´ızko u sebe, m˚ uˇze metoda selekce vrstevnic selhat a spojit nˇekolik vrstevnic v jednu 5.7. Pˇri k´otov´an´ı vrstevnic s dan´ ym probl´emem nepoˇc´ıt´ame, proto vede ke ˇspatn´ ym v´ ysledk˚ um pˇrevodu v´ yˇskov´e mapy. Na obr´ azku 5.8 vid´ıme, ˇze v nˇekter´ ych pˇr´ıpadech oprava vrstevnic pomoc´ı v´ yˇsky selh´av´ a. Toto selh´ an´ı m´ a za n´ asledek velmi ˇspatn´e v´ ysledky k´otov´an´ı i n´asledn´eho pˇrevodu na v´ yˇskovou mapu. Bylo by proto vhodn´e opravit tuto metodu. Napˇr´ıklad vyuˇz´ıt informaci o smˇernic´ıch spojovan´ ych ˇc´ ast´ı vrstevnic. Smˇernic jde vˇsak vyuˇz´ıt jen pˇri drobn´em poruˇsen´ı vrstevnic. Pokud jsou vrstevnice pˇreruˇseny v´ıce, jednotliv´e konce vrstevnic na sebe nemus´ı smˇeˇrovat. Z tohoto d˚ uvodu jsem metodu prozat´ım neupravoval.

23

Obr´ azek 5.1: Vstupn´ı turistick´a mapa

Obr´azek 5.2: Selekce vrstevnic a detekce koncov´ ych bod˚ u (koncov´e body zobrazeny zelenˇe)

24

Obr´ azek 5.3: Ok´ otov´ an´ı vrstevnic po zad´an´ı v´ yˇsky jednoho vrcholu

Obr´ azek 5.4: Pˇrevod na c´ılovou v´ yˇskovou mapu

25

Obr´ azek 5.5: Zobrazen´ı 3D modelu krajiny z v´ yˇskov´e mapy I

Obr´ azek 5.6: Zobrazen´ı 3D modelu krajiny z v´ yˇskov´e mapy II

26

Obr´ azek 5.7: Selh´ an´ı selekce vrstevnic - nˇekolik vrstevnic spojen´ ych v jednu

ˇ Obr´ azek 5.8: Spatn´ e spojen´ı vrstevnic na z´akladˇe znalosti o v´ yˇsce

27

Kapitola 6

Z´ avˇ er C´ılem m´e bakal´ aˇrsk´e pr´ ace bylo vytvoˇrit aplikaci, kter´a na z´akladˇe rastrov´eho obr´azku turistick´e mapy vytvoˇr´ı v´ yˇskovou mapu ter´enu. Poˇzadovan´eho c´ıle se mi podaˇrilo dos´ahnout. Pro jednoduchou“ turistickou mapu aplikace dok´aˇze vytvoˇrit odpov´ıdaj´ıc´ı v´ yˇskovou mapu. ” Pˇrevod na v´ yˇskovou mapu se prov´ad´ı pomoc´ı posloupnosti jednotliv´ ych krok˚ u - selekce, oprava vrstevnic, k´ otov´ an´ı, pˇrevod na v´ yˇskovou mapu. Selekci jsem provedl pomoc´ı upraven´e metody filtrace podle barvy“ vrstevnice 3.1. ” I pˇres jednoduchost dosahovala metoda velmi dobr´ ych v´ ysledk˚ u. Oprava vrstevnic je z´akladn´ım krokem ke spr´ avn´emu ok´ otov´ an´ı. Pro m´ısta, kde jsou vrstevnice pˇreruˇseny jen m´alo, je vhodn´e pouˇz´ıt metodu, kter´ a hled´a nejbliˇzˇs´ı koncov´ y bod jin´e vrstevnice 3.2.2. Oprava vrstevnic pˇri pouˇzit´ı znalosti o v´ yˇsce 3.3.2 je u ´ˇcinn´a v bl´ızkosti vrchol˚ u, kde nedoch´az´ı k velk´e distribuci chyb. Tato metoda nedosahuje vˇzdy dosahuje spr´avn´ ych v´ ysledk˚ u, a proto by bylo vhodn´e metodu upravit. Pokud se n´am podaˇr´ı opravit vrstevnice, kter´e leˇz´ı nejbl´ıˇze vrcholu, z´ısk´ ame tak vhodn´ a data pro pouˇzit´ı metody kolmic na vrstevnice 3.3.3 a ˇs´ıˇren´ı v´ yˇsek mezi jednotliv´ ymi vrstevnicemi. Pˇrevod na v´ yˇskovou mapu je z´avisl´ y na spr´avn´em ok´otov´ an´ı vrstevnic. Pokud m´ ame spr´avnˇe ok´otov´any vrstevnice, pˇrevod na v´ yˇskovou mapu 3.4 by n´ am jiˇz nemˇel ˇcinit probl´emy. Pokraˇcov´ an´ı t´eto bakal´ aˇrsk´e pr´ace by mˇelo spoˇc´ıvat hlavnˇe ve zlepˇsov´an´ı dosavadn´ıch metod a n´ avrhu nov´ ych metod, kter´e by byly v´ıce odolnˇejˇs´ı proti poruˇsen´ ym vrstevnic´ım. Napˇr´ıklad bychom mohli z vrchol˚ u postupnˇe zaplavovat“ okol´ı, a tak l´epe vyhled´avat ” sousedn´ı vrstevnice. D´ ale by bylo vhodn´e pracovat s v´ıce metodami k´otov´an´ı z´aroveˇ n, jednotliv´ ym metod´ am pˇriˇrazovat urˇcit´e pravdˇepodobnosti ohodnocen´ı, ze kter´ ych bychom pot´e urˇcovali spr´ avnou v´ yˇsku. Vhodn´e by bylo vyuˇz´ıt informaci o tom, ˇze kaˇzd´a p´at´a vrstevnice je na mapˇe vyznaˇcena ˇsirˇs´ı ˇc´arou. Tuto informaci jsem prozat´ım pro n´avrh algoritm˚ u nepouˇz´ıval, protoˇze dan´e znaˇcen´ı je pouze v nˇekter´ ych map´ach. Zaj´ımav´ ym rozˇs´ıˇren´ım by byla automatick´ a detekce vrchol˚ u a rozpozn´an´ı v´ yˇsky vrcholu pomoc´ı OCR. Posledn´ı u ´pravou, kter´ a by zlepˇsila pouˇzitelnost aplikace, je vytvoˇren´ı intuitivnˇejˇs´ıho uˇzivatelsk´eho rozhran´ı. Souˇcasn´e uˇzivatelsk´e rozhran´ı je postaveno na knihovnˇe OpenCV, kter´a m´ a omezenen´e prostˇredky pro tvorbu uˇzivatelsk´ ych rozhran´ı. Souˇc´ast´ı grafick´eho rozhran´ı by mohly b´ yt n´ astroje pro ruˇcn´ı opravu vrstevnic, protoˇze v nˇekter´ ych pˇr´ıpadech oprava jen jedn´e pˇreruˇsen´e vrstevnice m˚ uˇze v´ yraznˇe zlepˇsit celkov´ y v´ ysledek. R´ad bych pokraˇcoval ve v´ yvoji t´eto aplikace a vytvoˇril tak plnohodnotnou a uˇzivatelsky pˇr´ıjemnou aplikaci pro digitalizaci map, kter´a zjednoduˇs´ı orientaci v map´ach.

28

Literatura [1] Bierza Daniel. Vytvoˇren´ı v´yˇskov´e mapy z vrstevnic v rastrov´e mapˇe, [bakal´ aˇrsk´ a pr´ ace]. VUT Brno, 2006. ˇ [2] V´ aclav Hlav´ aˇc Milan Sonka. Poˇc´ıtaˇcov´e vidˇen´ı. Grada a.s., 1992, s. 23, 70, 97. ˇ - Technick´a [3] Dr. Ing. Eduard Sojka. Digit´ aln´ı zpracov´ an´ı a anal´yza obraz˚ u. VSB univerzita Ostrava, 2000, s. 74, 88. [4] WWW str´ anky. Generation 5 - thresholding and segmentation. http://www.generation5.org/content/2003/segmentation.asp (kvˇeten 2008). [5] WWW str´ anky. Gimp - uˇzivatelsk´a pˇr´ıruˇcka. http://docs.gimp.org/2.2/cs/filters-edge.html (kvˇeten 2008). [6] WWW str´ anky. Pov-ray height field. http://www.povray.org/documentation/view/3.6.1/279/ (kvˇeten 2008). [7] WWW str´ anky. School of computer science. http://www.cs.cmu.edu/afs/cs/academic/class/15462/web.06s/asst/project1/ (kvˇeten 2008). [8] WWW str´ anky. Wikipedia - gaussian blur. http://en.wikipedia.org/wiki/Gaussian blur (kvˇeten 2008). [9] WWW str´ anky. Wikipedia - odstranˇen´ı ˇsumu. http://cs.wikipedia.org/wiki/Odstranˇ en´ ıˇ sumu (kvˇeten 2008). [10] WWW str´ anky. Wikipedia - sobel operator. http://en.wikipedia.org/wiki/Sobel operator (kvˇeten 2008).

29