Detekce kartografick´eho zobrazen´ı z mnoˇziny bod˚ u, praktick´e zkuˇsenosti Tom´aˇs Bayer Katedra aplikovan´e geoinformatiky a kartografie, Pˇr´ırodovˇedeck´a fakulta, Univerzita Karlova v Praze, Albertov 6, ˇ a republika,
[email protected] 120 78, Praha 2, Cesk´
Abstrakt ˇ Cl´ anek se zab´ yv´ a praktick´ ym postupem detekce kartografick´eho zobrazen´ı z mnoˇziny bod˚ u vyuˇz´ıvaj´ıc´ım v´ ypoˇcet vlastn´ıch ˇc´ısel nad jednotliv´ ymi Voronoiov´ yni buˇ nkami sestrojen´ ymi nad touto mnoˇzinou. Vlastn´ı anal´ yza je provedena porovn´ an´ım mnoˇzin vstupn´ıch bod˚ u (s r˚ uzn´ ymi geometrick´ ymi parametry) s odpov´ıdaj´ıc´ımi mnoˇzinami bod˚ u v nˇekolika kartografick´ ych zobrazen´ıch. Postup je prakticky ilustrov´ an na 6 mnoˇzin´ ach srovn´ avan´ ych s 16 kartografick´ ymi zobrazen´ımi.
´ Uvod
1
(popˇr. jin´ ych bod˚ u) v rovinˇe kartografick´eho zobrazen´ı.
Principem metody detekce kartografick´eho zobrazen´ı z mnoˇziny bod˚ u popsan´e pˇredchoz´ım ˇcl´ anku je srovn´an´ı parametr˚ u bunˇek Voronoiova diagramu t´eto mnoˇziny s buˇ nkami Voronoiova diagramu (VD) nad odpov´ıdaj´ıc´ı mnoˇzinou bod˚ u (jejich obraz˚ u) v analyzovan´em kartografick´em zobrazen´ı. Postup vych´ az´ı z myˇslenky, ˇze podobn´e mnoˇziny bod˚ u generuj´ı podobn´e VD. C´ılem metody je nalezen´ı co nejpodobnˇejˇs´ı dvojice VD nad mnoˇzinou analyzovan´ ych bod˚ u a mnoˇzinou jim odpov´ıdaj´ıc´ıch bod˚ uv kartografick´em zobrazen´ı.
1.1
2. Souˇradnice x, y uzlov´ ych bod˚ u zemˇepisn´e s´ıtˇe analogov´eho mapov´eho podkladu v rovinˇe kartografick´eho zobrazen´ı. Prvn´ı mnoˇzina bod˚ u byla poˇr´ızena v´ ypoˇctem, autor pouˇzil vlastn´ı program WinKart. Druh´a mnoˇzina vznikla digitalizac´ı analogov´eho mapov´eho podkladu, kter´ y byl do elektronick´e formy pˇreveden skenov´an´ım. Chyba ze skenov´an´ı nebyla do dalˇs´ıch v´ ypoˇct˚ u prom´ıtnuta, skener byl povaˇzov´an za bezchybn´ y. Z prvn´ıho kartografick´eho podkladu byly z´ısk´any jak body s pravideln´ ym rozloˇzen´ım ve formˇe rastru (kroky ∆ϕ = konst a 4λ = konst), tak body nepravidelnˇe rozloˇzen´e. Z druh´eho kartografick´eho podkladu byly z´ısk´any pouze body s pravideln´ ym rozloˇzen´ım.
Mnoˇ zina vstupn´ıch bod˚ u
Mnoˇzina vstupn´ıch bod˚ u je ovlivnˇena pouˇzit´ ym kartografick´ ym podkladem, jehoˇz kartografick´e zobrazen´ı se snaˇz´ıme urˇcit. Parametry mnoˇziny P zˇrejmˇe ovlivˇ nuj´ı v´ ysledek anal´ yzy. Jako d˚ uleˇzit´ a se jev´ı volba poˇctu bod˚ u N , jejich rozloˇzen´ı, velikost u ´zem´ı a pˇresnost zn´ azornˇen´ı bod˚ u v mapˇe. Pokus´ıme se uk´ azat z´ avislost u ´spˇeˇsnosti detekce kartografick´eho zobrazen´ı na tˇechto parametrech. Vzhledem k rozsahu pˇr´ıspˇevku se nebude jednat o podrobnou anal´ yzu probl´emu, ale sp´ıˇse o naznaˇcen´ı princip˚ u a vz´ajemn´ ych z´ avislost´ı jednotliv´ ych parametr˚ u.
Parametry mnoˇ zin bod˚ u. K vlastn´ı anal´ yze bylo pouˇzito k mnoˇzin P , v dalˇs´ım textu oznaˇcen´ ych jako P (k) , a jim odpov´ıdaj´ıc´ıch mnoˇzin Q(k,j) v j kartografick´ ych zobrazen´ıch. Vz´ajemnˇe se liˇsily sv´ ymi geometrick´ ymi parametry: poˇctem bod˚ u N , polohou na referenˇcn´ı ploˇse, velikost´ı u ´zem´ı (pˇredstavovanou plochou min-max boxu nad P ), pˇresnost´ı urˇcen´ı. Velikost u ´zem´ı lze pro naˇse u ´ˇcely l´epe vyj´adˇrit jako pomˇer obsahu min-max boxu vztaˇzen´ y k celkov´emu obsahu referenˇcn´ı plochy. Z hlediska numerick´eho vyj´adˇren´ı je vhodnˇejˇs´ı pracovat s ob, kde razy, tj. pomˇer p lze vyj´adˇrit jako p = Smin−max Sref hodnota Smin−max pˇredstavuje obsah min-max boxu v obraze kartografick´eho zobrazen´ı, Sref obsah referenˇcn´ı plochy v obraze kartografick´eho zobrazen´ı. Chybu, kter´e
Typy kartografick´ ych podklad˚ u. Pro prov´adˇen´ı anal´ yz byly pouˇzity dva typy kartografick´ ych podklad˚ u. Prvn´ı z nich byl k dispozici pˇr´ımo v digit´ aln´ı formˇe, druh´ y v analogov´e formˇe: 1. Soubor souˇradnic x, y uzlov´ ych bod˚ u zemˇepisn´e s´ıtˇe 1
se t´ımto postupem dopust´ıme, lze zanedbat. Hodnoty pomˇeru p nepotˇrebujeme zn´ at s pˇr´ıliˇs velkou pˇresnost´ı. Z d˚ uvodu jednoduchosti v´ ypoˇctu je vhodn´e hodnoty Smin−max , Sref uv´ adˇet ve v´ alcov´em ekvivalentn´ım zobrazen´ı. Pokud jsou body rozloˇzeny pravidelnˇe ve formˇe rastru, hodnota koeficientu p je funkc´ı krok˚ u ∆ϕ, 4λ, poˇctu bod˚ u N a souˇradnic bod˚ u ϕ, λ. Pˇrehled tˇechto parametr˚ u pro jednotliv´e mnoˇziny P pouˇzit´e v tomto ˇcl´anku nalezneme v tab 1. Situace P (1) −P (2) pˇredstavuj´ı u ´zem´ı rozloˇzen´e symetricky kolem rovn´ıku s velkou rozlohou. Prvn´ı varianta vyuˇz´ıv´ a kroky ∆ϕ = 4λ = 10◦ , druh´ a varianta poloviˇcn´ı krok ∆ϕ = 4λ = 5◦ , jedn´ a se o pravideln´ y rastr. Situace P (3) − P (4) pˇredstavuj´ı u ´zem´ı leˇz´ıc´ı ve stˇredn´ıch zemˇepisn´ ych ˇs´ıˇrk´ ach s v´ yraznˇe menˇs´ı rozlohou reprezentovan´e pravideln´ ym rastrem s kroky ∆ϕ = 4λ = 2◦ a ∆ϕ = 4λ = 0.5◦ . Mnoˇziny P (1) , P (2) a P (3) , P (4) popisuj´ı tot´eˇz u ´zem´ı, pouze krok rastru je r˚ uzn´ y. Situace P (5) pˇredstavuje nepravidelnˇe rozloˇzenou mnoˇzinu bod˚ u nach´ azej´ıc´ıch se pouze na hranici analyzovan´eho u ´zem´ı ˇ e republiky). O kroc´ıch ∆ϕ, 4λ zde nem˚ (hranice Cesk´ uˇzeme hovoˇrit, vzd´ alenost dvou sousedn´ıch bod˚ u ˇcin´ı cca 0.002◦ .
Pokud byly body rozloˇzeny nepravidelnˇe, postup v´ ypoˇctu byl analogick´ y. Hodnoty [ϕi , λi ] jsou zn´amy, nemus´ı b´ yt urˇcov´any s pouˇzit´ım cyklu. Pˇri naplˇ nov´an´ı mnoˇzin P a Q n´aleˇz´ıc´ıch dle (1.1) do druh´e skupiny jsme postupovali takto: • Souˇradnice bod˚ u mnoˇziny P byly urˇceny kartometrickou digitalizac´ı uzlov´ ych bod˚ u poledn´ık˚ u a rovnobˇeˇzek z naskenovan´eho kartografick´eho podkladu. U tˇechto bod˚ u byly souˇcasnˇe odeˇcteny jejich zemˇepisn´e souˇradnice [ϕi , λi ]. • Souˇradnice bod˚ u mnoˇzin Q(k,1) − Q(k,m) vznikly dosazen´ım [ϕi , λi ] do jejich zobrazovac´ıch rovnic. Pokud je v analyzovan´em kartografick´em d´ıle uvedeno kartografick´e zobrazen´ı, porovn´av´ame mnoˇziny Q(k,1) − Q(k,m) s mnoˇzinou P (k) .
Postup naplnˇ en´ı mnoˇ zin bod˚ u P a Q. Aby bylo moˇzno l´epe otestovat u ´spˇeˇsnost detekce kartografick´eho zobrazen´ı, analyzovan´e kartografick´e zobrazen´ı bylo ve vˇsech pˇr´ıpadech pˇredem zn´ am´e. Postup tedy vyuˇz´ıv´a srovn´ an´ı mnoˇziny bod˚ u zn´ am´eho kartografick´eho zobrazen´ı s mnoˇzinami odpov´ıdaj´ıc´ıch bod˚ u (obraz˚ u) v m r˚ uzn´ ych kartografick´ ych zobrazen´ıch, j = 1, .., m, (ve kter´ ych je analyzovan´e zobrazen´ı tak´e obsaˇzeno). V tomto pˇr´ıpadˇe m = 16. Pokud byly body rozloˇzeny pravidelnˇe, tvoˇrily uzly s´ıtˇe poledn´ık˚ u a rovnobˇeˇzek. Pˇredstavovaly tedy rastr s pˇredem zvolen´ ymi hodnotami krok˚ u ∆ϕ, 4λ, poˇctem bod˚ u N a zemˇepisn´ ych souˇradnic ϕ, λ.
Obr´ azek 1: Voronoi diagram testovac´ı mnoˇziny bod˚ u P.
1.2
Pouˇ zit´ a kartografick´ a zobrazen´ı
Pro testov´an´ı byla pouˇzit soubor 16 kartografick´ ych zobrazen´ı. Byl volena tak, aby obsahoval nejˇcastˇeji pouˇz´ıvan´e z´astupce jednotliv´ ych skupin kartografick´ ych zobrazen´ı pouˇz´ıvan´ ych zejm´ena pro mapy mal´ ych a stˇredn´ıch mˇeˇr´ıtek: zobrazen´ı jednoduch´a, zobrazen´ı neprav´ a, zobrazen´ı polyk´onick´a. Podrobn´ y popis kartografick´ ych parametr˚ u tˇechto zobrazen´ı lze nal´ezt v n´asleduj´ıc´ı kapitole. Podrobn´ y popis kartografick´ ych parametr˚ u tˇechto zobrazen´ı lze nal´ezt v n´asleduj´ıc´ı kapitole.
• Mnoˇzina P pˇredstavuj´ıc´ı body analyzovan´eho kartografick´eho zobrazen´ı vznikla v´ ypoˇctem souˇradnic [xi , yi ],i = 1, ..., N , ze souˇradnic [ϕi , λi ] dosazen´ ych do zobrazovac´ıch rovnic tohoto kartografick´eho zobrazen´ı. V´ ypoˇcet byl realizov´ an za pouˇzit´ı dvou vnoˇren´ ych cykl˚ u. Aby nebyla tato mnoˇzina bod˚ u zcela totoˇzn´ a s pozdˇeji urˇcenou mnoˇzinou Q, m´ısto jednotkov´e koule byla pouˇzita referenˇcn´ı koule R = 1000m s n´ asledn´ ym zaokrouhlen´ım souˇradnic na metry.
Pˇ rehled zobrazovac´ıch rovnic. Pro pouˇzit´ a kartografick´a zobrazen´ı uvedeme zobrazovac´ı rovnice 1 . Symbol 1NR pˇredstavuje jednu nezkreslenou rovnobˇeˇzku se zemˇepisnou ˇs´ıˇrkou ϕ0 . V´alcov´e ekvidistantn´ı zobrazen´ı: • Kaˇzd´e mnoˇzinˇe P (k) odpov´ıdaj´ı mnoˇziny Q(k,1) − Q(k,m) . Tyto mnoˇziny vznikly v´ ypoˇctem souˇradnic x = Rλ, [x0i , yi0 ] ze souˇradnic [ϕi , λi ] “stejn´ ych bod˚ u” v m y = Rϕ. kartografick´ ych zobrazen´ıch. 1 Tvary zobrazovac´ ıch rovnic byly zjednoduˇseny za pouˇ zit´ı pˇr´ıkazu simplify, nejsou tedy v obvykle zn´ am´ ych tvarech uv´ adˇ en´ ych v kartografick´ ych publikac´ıch.
2
V´ alcov´e ekvivalentn´ı zobrazen´ı: x
= Rλ,
y
= R sin ϕ.
Bonneovo zobrazen´ı:
x
V´ alcov´e konformn´ı zobrazen´ı: x
= Rλ,
y
= R ln(tan
ϕ π + ). 2 4
y
Kuˇzelov´e ekvidistantn´ı zobrazen´ı (1NR): R (1 + (−1 + (−ϕ0 + ϕ) tan ϕ0 )) · tan ϕ0 · cos(λ sin ϕ0 )), R = − (−1 + (−ϕ + ϕ) tan ϕ) sin(λ sin(ϕ)). tan ϕ0
x =
y
Hammerovo zobrazen´ı: √ 2 2R cos ϕ sin λ2 x = q , 1 + cos ϕ cos λ2 √ 2R sin ϕ y = q . 1 + cos ϕ cos λ2
Kuˇzelov´e ekvivalentn´ı zobrazen´ı (1NR): x
y
R (1 + (ϕ0 − ϕ) tan ϕ0 · tan ϕ0 λ cos ϕ · sin )., cot ϕ0 + ϕ0 − ϕ R = (−1 + (1 + (ϕ0 − ϕ) tan ϕ0 ) · tan ϕ0 λ cos ϕ · cos ). cot ϕ0 + ϕ0 − ϕ
=
R (− cos ϕ0 + sin ϕ0 p + − cos2 ϕ0 + 2 − 2 sin ϕ0 sin ϕ · cos(λ sin ϕ0 )) R p = − cos2 ϕ0 + 2 − 2 cos ϕ0 sin ϕ · sin ϕ0 · sin(λ sin ϕ0 ). = −
Mollweidovo zobrazen´ı: √ 2 2 x = Rλ cos ϕ, π √ y = R 2 sin ϕ.
Kuˇzelov´e konformn´ı zobrazen´ı (1NR): x
y
Mercator-Sansonovo zobrazen´ı:
sin ϕ0
tan( ϕ20 + π4 ) R )· (−1 + tan ϕ0 tan( ϕ2 + π4 ) · cos(λ sin ϕ0 ), sin ϕ0 tan( ϕ20 + π4 ) R = sin(λ sin ϕ0 ). tan ϕ0 tan( ϕ2 + π4 )
= −
y
=
x
=
y
=
π − ϕ) cos λ, . 2 π R( − ϕ) sin λ. 2
y
R(
y
=
= Rϕ.
λ cos ϕ π − ϕ) sin( π ), 2 2 −ϕ π λ cos ϕ = R(ϕ − ) cos( π ). 2 2 −ϕ
Urmaevovo zobrazen´ı:
π−ϕ cos λ, 2 π−ϕ 2R sin sin λ. 2
x
=
y
=
2R sin
2 √ 1 4 R 3λ cos( arcsin(ϕ)) 3 2 3 √ 4 R 3(arcsin(ϕ)) 2
Hasslerovo zobrazen´ı:
Azimut´ aln´ı konformn´ı zobrazen´ı: x =
y
= R(
Azimut´ aln´ı ekvivalentn´ı zobrazen´ı: x
= Rλ cos ϕ,
Werner-Staabovo zobrazen´ı:
Azimut´ aln´ı ekvidistantn´ı zobrazen´ı: x =
x
π−ϕ cos λ, 2 π−ϕ 2R tan sin λ. 2
x =
2R tan
y 3
=
R (1 − cos(λ sin ϕ) + ϕ tan ϕ), tan ϕ R sin(λ sin ϕ). tan ϕ
mnoˇziny P (6) byl v´ ypoˇcet m´ıry identity proveden za pouˇzit´ı Helmertovy, afinn´ı, kvadratick´e a kubick´e transformace. Maxim´aln´ı hodnoty odchylek mezi obˇema mnoˇzinami bod˚ u, pˇrepoˇcten´e na pixely, jsou uvedeny v tab. ??. Z tabulky je patrn´e, ˇze mezi obˇema mnoˇzinami nen´ı line´arn´ı vztah. Hodnoty souˇradnic zˇrejmˇe tak´e nejsou zat´ıˇzeny hrub´ ymi chybami.
3
Konstrukce VD je prov´adˇena inkrement´aln´ım algoritmem v souladu s postupem publikovan´ ym v prvn´ı ˇc´ asti . tohoto ˇcl´anku. Vzhledem k maxim´aln´ımu poˇctu dat N = 1500 se doba v´ ypoˇctu parametr˚ u VD vˇcetnˇe konverze do form´atu DXF pohybovala v ˇr´adech s (t < 10s). Pro vˇetˇs´ı soubory dat by algoritmus bylo moˇzno implementovat efektivnˇeji, ˇci vyuˇz´ıt nˇekter´ y z bˇeˇznˇe dostupn´ ych opensource knihoven geometrick´ ych algoritm˚ u. Pˇred vlastn´ı konstrukc´ı je nutno z mnoˇzin P a Q odstranit identick´e body. N´asledovala selekce dvojic bunˇek V (Pi ) a V (Qi ) takov´ ych: jejichˇz gener´atory Pi ,Qi leˇzely na konvexn´ı ob´ alce nebo jejichˇz poˇcet hran byl r˚ uzn´ y nebo jejichˇz tvary byly v´ yraznˇe odliˇsn´e (tj. nesplˇ novaly dle 2.6 uveden´ a geometrick´a krit´eria). D˚ uleˇzit´ ym faktorem je poˇcet odstranˇen´ ych bunˇek V (Pi ) a V (Qi ), kter´ y by mˇel b´ yt menˇs´ı neˇz ych bunˇek V (Pi ) a V (Qi ) oznaˇc´ıme cca. 54 N . Poˇcet zbyl´ 0 N 0 . Relativn´ı poˇcet zachovan´ ych bunˇek NN pro jednotliv´e varianty mnoˇzin je uveden v tab. 3. Kartografick´ a zobrazen´ı jsou oznaˇcena zkratkami.
Obr´ azek 2: Voronoi diagram odpov´ıdaj´ıc´ı mnoˇziny Q v Hasslerovˇe zobrazen´ı. Parametry kartografick´ ych zobrazen´ı. Volba parametr˚ u kartografick´eho zobrazen´ı je z´ avisl´ a na mnoˇzinˇe vstupn´ıch bod˚ u. Pro mnoˇziny P (1) , P (2) , P (6) byly pouˇzity norm´ aln´ı i obecn´ a poloha kartografick´eho zobrazen´ı, v ostatn´ıch pˇr´ıpadech pouze norm´ aln´ı poloha zobrazen´ı. Vzhledem k poloze u ´zem´ı mohly b´ yt parametry nˇekter´ ych kartografick´ ych zobrazen´ı voleny optim´ alnˇeji, na v´ ysledek anal´ yzy tento fakt nem´ a zˇrejmˇe v´ yznamnˇejˇs´ı vliv. • Mnoˇziny P (1) , P (2) V´ alcov´e zobrazen´ı: kartografick´ y p´ ol Q = [0◦ , 210◦ ], ◦ 1NR ϕ0 = 0 ; kuˇzelov´e zobrazen´ı Q = [0◦ , 120◦ ], 1NR ϕ0 = 30◦ ; azimut´ aln´ı zobrazen´ı Q = [0◦ , 120◦ ]. • Mnoˇziny P (3) − P (5) Vˇsechna zobrazen´ı v norm´ aln´ı poloze. V´ alcov´a zobrazen´ı 1NR ϕ0 = 0◦ , kuˇzelov´ a zobrazen´ı 1NR ϕ0 = 40◦ . • Mnoˇzina P (6) V´ alcov´e zobrazen´ı v norm´ aln´ı poloze, 1NR ϕ0 = 0◦ ; kuˇzelov´e zobrazen´ı Q = [−90◦ , 0◦ ], 1NR ϕ0 = −40◦ ; azimut´ aln´ı zobrazen´ı Q = [−90◦ , 0◦ ].
2
Konstrukce VD a jejich selekce
Urˇ cen´ı m´ıry identity.
Zobr.
P (1)
P (2)
P (3)
P (4)
P (5)
P (6)
VED
0
0
0
0
0.35
0
VEV
0
0
0
0
0.27
0
VKO
0
0
0
0
0.95
0
KED
0
0
0
0
0.60
0
KEV
0
0
0
0
0.92
0
KKO
0
0
0
0
0.97
0
AED
0.41
0.65
0
0
0.65
0
AEV
0.41
0.66
0
0
0.56
0
AKO
0.10
0
0
0
0.97
0
BON
0.31
0.55
0.63
0.80
0.90
0.27
WER
0.22
0.54
0.70
0.83
0.76
0.32
HAM
0.47
0.67
0.57
0.75
0.42
0.14
MER
0.53
0.73
0.56
0.75
0.49
0.16
MOL
0.51
0.70
0.56
0.75
0.49
0.16
Dalˇs´ı krok pˇredstavuje posouzen´ı m´ıry identity mnoˇzin URM 0.43 0.67 0.56 0.75 0.33 0.23 P a Q. Vzhledem k charakteru vstupn´ıch dat u mnoˇzin HAS 0.14 0.47 0.64 0.80 0.88 0.32 P (1) − P (5) (z´ısk´ any v´ ypoˇctem stejn´eho souboru bod˚ u [ϕi , λi ]), u kter´ ych s v´ yjimkou zaokrouhlovac´ıch chyb nepˇredpokl´ ad´ ame v´ yskyt dalˇs´ıch systematick´ ych ˇci n´ahod- Tabulka 3: Relativn´ı poˇcet zachovan´ych VD pro jednotliv´e n´ ych chyb, nebudeme urˇcen´ı m´ıry identity prov´adˇet. U varianty P . 4
Mnoˇziny P , u kter´ ych je zachov´ an dostateˇcn´ y poˇcet Upraven´a matice α0 m´a prvky N 0 azornˇeny kurV (P ) k anal´ yze, N > 5 , jsou v tabulce zn´ s tQ z´ıvou. 0 α = |q| tP Vlastn´ı v´ ypoˇcet testovac´ıho krit´eria m0α provedeme ze vztahu rP vα0 vα0 0 mα = (1) N0 − 1 Pˇripomeˇ nme, ˇze pokud neexistuje ˇz´adn´e V (Pi ) a V (Qi ) se stejn´ ym poˇctem hran, je hodnota testovac´ıho krit´eria m0α = ∞. Pˇrehled hodnot krit´eri´ı m0α pro jednotliv´e Obr´ azek 3: Voronoi diagram odpov´ıdaj´ıc´ı mnoˇziny Q v mnoˇziny P nalezneme v tab. 4. Bonneovˇe zobrazen´ı. 0
Pod´ıv´ ame -li se podrobnˇeji na hodnotu pomˇeru NN u jednotliv´ ych mnoˇzin P (i) , vˇsimneme si, ˇze je tato hodnota v pˇeti ze ˇsesti pˇr´ıpad˚ u nejvˇetˇs´ı u kartografick´eho zobrazen´ı, kter´e bylo n´ aslednˇe detekov´ ano jako zobrazen´ı analyzovan´eho kartografick´eho podkladu. Hodnoty pomˇeru se zˇrejmˇe zvyˇsuj´ı i s rostouc´ım poˇctem bod˚ u N , buˇ nky V (Pi ) a V (Qi ) jsou si vz´ ajemnˇe “podobnˇejˇs´ı”. Vˇsimnˇeme si tohoto faktu u mnoˇzin P (1) , P (2) a P (3) , P (4) pˇredstavuj´ıc´ıch “tot´eˇz u ´zem´ı”. Jedn´a se o d˚ usledek sn´ıˇzen´ı velikost´ı krok˚ u ∆ϕ a ∆λ vedouc´ı ke vzniku jemnˇejˇs´ıho rastru; Voronoiovy buˇ nky nad t´ımto rastrem jsou v obou mnoˇzin´ ach “podobnˇejˇs´ı”. V dalˇs´ım kroku provedeme pˇrevod zbyl´ ych Voronoiov´ ych bunˇek na u ´pln´e orientovan´e grafy. Pro kaˇzdou dvojici bunˇek V (Pi ) a V (Qi ) tedy urˇc´ıme matice WPi a WQi . Pˇresnost v´ ypoˇctu hodnot wij z´ avis´ı na velikosti analyzoˇ ım je velikost u van´eho u ´zem´ı. C´ ´zem´ı menˇs´ı, t´ım pˇresnˇeji je tˇreba hodnoty wij urˇcit. V praxi postaˇcuje uv´adˇet je s relativn´ı pˇresnost´ı cca 1 · 10−6 .
3.1
tQ . tP
Mnoˇziny P, Q mohou obsahovat numericky znaˇcnˇe odliˇsn´e hodnoty, je proto vhodn´e pˇred v´ ypoˇctem testovac´ıho krit´eria prov´est alespoˇ n jejich pˇribliˇzn´e znormov´an´ı. Pˇribliˇzn´e normalizaˇcn´ı krit´erium |q| lze stanovit jako tiQ i=1 tiP N0
PN 0 |q| =
P (2)
P (3)
P (4)
P (5)
P (6)
VED
∞
∞
∞
∞
318.2
∞
VEV
∞
∞
∞
∞
543.5
∞
VKO
∞
∞
∞
∞
0
∞
KED
∞
∞
∞
∞
79.4
∞
KEV
∞
∞
∞
∞
18.7
∞
KKO
∞
∞
∞
∞
18.2
∞
AED
15.8
26.4
∞
∞
67.7
∞
AEV
13.7
26.6
∞
∞
100.5
∞
AKO
11.1
∞
∞
∞
25.3
∞
BON
64.9
39.8
3.3
3.6
24.3
924.9
WER
16.3
52.8
0
0
43.6
950.3
HAM
62.4
23.1
134.7
8.3
201.2
37.4
MER
0.8
2.0
1.7
1.8
190.0
28.3
MOL
20.6
25.8
27.3
30.2
185.2
83.4
URM
23.6
36.0
13.1
14.4
310.5
13.5
HAS
122.1
151.9
9.3
7.7
23.7
960.5
Srovn´an´ım hodnot m0α zjist´ıme, ˇze detekce kartografick´eho zobrazen´ı probˇehla u ´spˇeˇsnˇe ve vˇsech ˇsesti pˇr´ıpadech. U mnoˇzin P (1) , P (2) se hodnota min(m0α ) bl´ıˇz´ı k nule. Souˇradnice xi , yi bod˚ u tˇechto mnoˇzin byly pˇri v´ ypoˇctu zaokrouhleny na cel´a ˇc´ısla. Shoda obou mnoˇzin tedy nen´ı “´ upln´a”, obˇe mnoˇziny jsou “velmi podobn´e” mnoˇzinˇe Q(1,13) , Q(2,13) Mercator-Sansonova zobrazen´ı. Hodnota min(m0α ) je rovna nule u mnoˇzin P (3) , P (4) , kter´e jsou aˇz na konstantu (jin´ y polomˇer referenˇcn´ı plochy) shodn´e s mnoˇzinami Q(3,11) , Q(4,11) Werner-Staabova a v´alcov´eho konformn´ıho zobrazen´ı. Nejvyˇsˇs´ı odchylku od “nuly” vykazuje hodnota min(m0α ) u mnoˇziny P (6) , kter´ a byla poˇr´ızena digitalizac´ı rastrov´eho podkladu. Souˇradnice jsou zˇrejmˇe zat´ıˇzeny n´ahodn´ ymi i systematick´ ymi chybami (chyba zobrazen´ı, chyba ze sr´aˇzky mapov´eho listu, chyba z digitalizace, atd...). Tyto chyby vˇsak byly natolik mal´e, ˇze neovlivnily proces detekce kartografick´eho zobrazen´ı, viz tab. ??. I v tomto pˇr´ıpadˇe bylo Urma-
V´ ypoˇcet testovac´ıho krit´eria α byl podrobnˇe pops´an v pˇredch´ azej´ıc´ı ˇc´ asti ˇcl´ anku. Pˇripomeˇ nme, ˇze vych´az´ı ze vzorce r
P (1)
a P. Tabulka 4: Hodnoty krit´eri´ı m0α pro jednotliv´
V´ ypoˇ cet testovac´ıho krit´ eria
α=
Zobr.
. 5
Z´ avˇ er evovo zobrazen´ı u ´spˇeˇsnˇe detekov´ ano. Znaˇcn´e rozd´ıly mezi 4 hodnotami min(m0α ) se projevily u mnoˇzin P (1) , P (2) a yval praktick´ ym postupem detekce P (3) , P (4) zejm´ena u Hammerova a Werner Staabova zob- Tento ˇcl´anek se zab´ kartografick´ e ho zobrazen´ ı z mnoˇ z iny bod˚ u metodou anarazen´ı, kde zjemnˇen´ım krok˚ u ∆ϕ a ∆λ doˇslo ke generol´ y zy parametr˚ u Voronoiova diagramu sestrojen´ eho nad v´ an´ı “podobnˇejˇs´ıch” bunˇek V (Pi ) a V (Qi ). touto mnoˇzinou bod˚ u. Dosaˇzen´e v´ ysledky naznaˇcuj´ı ˇze metoda vykazuje pomˇernˇe znaˇcnou invarianci testovac´ıho koeficientu vzhledem k poˇctu bod˚ u, jejich rozloˇzen´ı na referenˇcn´ı ploˇse a velikosti analyzovan´eho u ´zem´ı. Podm´ınkou u ´spˇeˇsn´e detekce je poˇzadavek, aby plocha, na kter´e se nach´az´ı analyzovan´a mnoˇzina bod˚ u, byla vˇetˇs´ı neˇz cca 100km2 . To znesnadˇ nuje prov´adˇen´ı detekce na velko´ eˇsnost anal´ mˇeˇr´ıtkov´ ych mapov´ ych podkladech. Uspˇ yzy bude niˇzˇs´ı v bl´ızk´em okol´ı singul´arn´ıch bod˚ u (tj. zemˇepisn´ ych a kartografick´ ych) p´ol˚ u, pod´el z´akladn´ıch poledn´ık˚ u ˇci rovnobˇeˇzek zvolen´ ych pro zn´azornˇen´ı u ´zem´ı s minim´aln´ımi deformacemi. Ve vˇetˇsinˇe kartografick´ ych zobrazen´ı bude obraz tohoto u ´zem´ı “velmi podobn´ y”. Spr´ avnost vˇsech pˇredpoklad˚ u je vˇsak nutno potvrdit dalˇs´ımi yzami. Obr´ azek 4: Voronoi diagram odpov´ıdaj´ıc´ı mnoˇziny Q v anal´ Hammerovˇe zobrazen´ı.
5
Podˇ ekov´ an´ı
ˇ anek vznikl za podpory projektu grantu GACR ˇ ˇc. Cl´ 205/04/088 s n´azvem “Kartometrick´a a semiotick´ a anal´ yza a vizualizace star´ ych map ˇcesk´ ych zem´ı z obdob´ı 1518-1720”.
Grafick´e zn´ azornˇen´ı VD pro jednotliv´e vstupn´ı mnoˇziny bod˚ u s provedenou selekc´ı pˇr´ısluˇsn´ ych bunˇek nalezneme na obr. 1 - 4. Vˇsimnˇeme si znaˇcn´e odliˇsnosti tvar˚ u VD, kter´e usnadˇ nuje proces anal´ yzy.
Reference [1] Heb´ ak P.: V´ıcerozmˇern´e statistick´e metody, Informatorium, 2005, Praha. ˇ [2] Buchar P., Hojovec V.: Matematick´ a kartografie, Vydavatelstv´ı CVUT, 1996, Praha. [3] Rourke O. J.: Computational Geometry in C, Cambridge University Press, 2005.
6
