Automated distinguishing of hydrographical channels in the georeference database/Automatizuotas hidrografijos kanalu isskyrimas Lietuvos georeferencinio pagrindo duomenu bazeje.

Kryzanauskas, Audrius ; Motiejauskas, Danas

1. Ivadas

2009 m. antroje puseje atliekant georeferencinio pagrindo (toliau GDB10LT) atnaujinimo darbus, linijines hidrografijos atkarpos sluoksnyje hidro_l buvo skirstomos i 4 tipus, t. y. priskiriamos upems, kanalams, grioviams bei nezinomam (nenustatytam) tipui. Atliekant analize, pirmiausia buvo atskirta kategorija "upe". Pagal tuometine duomenu parengimo bukle tai atkarpos, duomenu rinkinyje turincios pavadinimus. Pagrindines darbo sanaudos kanalu ir grioviu kategorijoms atskirti--rankiniu budu reiketu isnagrineti labai daug linijiniu objektu vizualiai nustatant ju jungumo savybes.

Atlikus tyrima laikomasi poziurio, kad pagrindinis kanalu ir grioviu skirtumas yra tai, jog kanalas sujungia kitus vandens telkinius, o griovys yra skirtas tiesiog vandeniui is aplinkines teritorijos nuvesti. Skirstymas atliktas automatizuotai pasinaudojant geoinformaciniu priemoniu analizes funkcionalumu bei sukuriant specifini grafu analizes algoritma. Nagrinejant duomenu struktura, parinktos funkciju sekos, susije su specifiniu duomenu parengimu tinklinei analizei bei sia analize.

Del duomenu rinkinio oficialumo pasirinkta istatymu apibrezta kanalo ir griovio savoku formuluote, kuri galbut atspindi ne visu hidrografinio tinklo tyrinetoju nuomone. Kanalai daznai traktuojami kaip laivybos statiniai (The Digital Geographic ... 2000), siuo poziuriu Lietuvoje zinomiausias Karaliaus Vilhelmo kanalas, kitur apskritai kanalu kategorijai butu priskiriami ir grioviai (Vieningas georeferenciniu duomenu modelis ... 2008). Melioracijoje o ir patys kanalai skirstomi smulkiau: magistraliniai, salutiniai. Aprasomi metodai galetu padeti gilinantis i konkrecius specifiskai suformuluotus kanalu tinklo charakteristiku analizes uzdavinius.

2. Duomenu ypatumai ir uzduoties specifika

Georeferencinis pagrindas taikomas kaip pradinis duomenu saltinis (topografinis pagrindas) kitiems valstybiniams geografiniu duomenu rinkiniams kurti. Del duomenu oficialumo privalu vadovautis oficialiais dokumentais, apibrezianciais kaupiamu objektu savokas. Kanalo ir griovio savokos apibreziamos Lietuvos Respublikos aplinkos ministro 2001 m. lapkricio 7 d. isakyme Nr. 540 "Del pavirsiniu vandens telkiniu apsaugos zonu ir pakranciu apsaugos juostu nustatymo tvarkos apraso patvirtinimo".

Nagrinetinos dvi savokos--"griovys" ir "kanalas" apibreziamos taip:

--griovys--hidrotechnikos statinys, irengiamas iskasant atvira vaga grunte ir skirtas perteklinio vandens nuvedimui/nuleidimui. Sureguliuotos upes nelaikomos grioviais;

--kanalas--dirbtinis pavirsinis vandens telkinys su nuolatine vandens tekme, irengiamas grunte iskasant/irengiant atvira vaga, kurios pradzia ir pabaiga jungiasi su kitu pavirsiniu vandens telkiniu (upe, ezeru, Kursiu mariomis arba tvenkiniu), skirtas vandeniui tiekti drekinimo, hidroenerge-tikos, vandentiekos ir kitoms reikmems, naudoti laivybai ir pan. Sureguliuotos upes nelaikomos kanalais.

Formaliai perfrazuojant sia kanalo savoka GDB10LT duomenu prasme, tai yra atkarpos, neturincios pavadinimu, kuriomis galima sujungti kitus vandens telkinius, turincius pavadinimus.

GDB10LT hidrografijos sluoksnis pakankamai sutvarkytas, tinka ne tik kartografinio pagrindo funkcijai atlikti, gali buti naudojamas sudetingesnei geoinforma-cinei analizei. Del topologinio informacijos vientisumo yra galimybe atlikti tinklo analizes uzdavinius; siais principais nuspresta vadovautis isskiriant kanalus. Patikslinta analizes uzdavinio formuluote--reikia rasti visus imanomus marsrutus (jungtis) tarp nuotekio tasku. Visos atkarpos, kuriomis imanoma sujungti nuotekio taskus, isskiriamos kaip kanalai.

Kanalai isskiriami linijiniame hidrografijos sluoksnyje hidro_l papildomai irasant atributa TIPAS=2 kanalams ir 3 grioviams, taciau kartu nagrinejamas ir zemes dangos plotu sluoksnis "plotai", kuriame yra informacija apie plotinius vandens telkinius. Linijiniu hidrografijos objektu santykis su plotais svarbus keletu aspektu: siekiant sujungti upe i tekme, neturincia trukiu, breziama menama pratekanciu pro ezerus ir tvenkinius upiu asine linija. Upiu, kurios isreiskiamos kaip plotiniai vandens telkiniai, hidro_l sluoksnyje saugomos asines linijos. Siu upiu intakai padalijami, ties plotinio objekto isorine riba sukuriant papildoma taska ir plotiniu vandens telkiniu viduje esancia atkarpa pazymint kaip menama linija. Bevardes menamos linijos taip pat tipizuojamos skirstant jas i griovius ir kanalus.

Problema naudojant tik upiu asines linijas kyla tais atvejais, kai atkarpa, interpretuotina kaip griovys, jungiasi su asine upes linija, esancia plotinio vandens telkinio viduje. Atkreipiame demesi, jog ir asine linija, ir plotinis vandens telkinys pagal anksciau suformuluotas marsruto (nuotekio) tasku taisykles yra tinkami objektai. Siuo atveju susidarytu situacija, jog griovio, itekancio i upes asine linija per plotini vandens telkini, menama linija taip pat butu priskirta kanalu kategorijai, nors jungia tik upes asine linija su ta pacia upe reprezentuojancio ploto isorine riba. Veliau siu atkarpu atrinkimas butu gana komplikuotas.

Atliekant analize linijini hidrografijos sluoksni sudare 357 272 atkarpos, is kuriu 88 261 identifikuotina upe su vardais, visos kitos 269 011--bevardes nagrinejamos atkarpos.

3. Automatizuoto kanalu isskyrimo eiga

Duomenu apdorojimo GIS funkciju seka, teikianti laukta rezultata, nustatyta keleta kartu vykdant duomenu atranka. Projektuojant procesa patogus naudoti programu sistemu inzinerijoje taikomi procesu aprasymo bei dekompozicijos metodai (Ross 1977).

Pradiniu tasku, briaunu atrinkimo--marsrutu skaiciavimo dalis isskaidoma i du etapus, panasius pagal atliekamus marsrutu skaiciavimus, taciau besiskiriancius marsruto tasku ir judejimo briaunu atrinkimo logika. Pirmiausia randamos tos kanalu dalys, kurios nepatenka i plotiniu vandens objektu vidu. Antru etapu randamos kitos kanalu dalys, kurios jungia pirmu etapu isskirtas atkarpas su menamomis hidrografijos asinemis linijomis (esanciomis plotiniu objektu viduje).

Kiekvieno mineto etapo pagrindas--isrinkti ir parengti erdvinius duomenis tinklinei analizei. Isrenkami taskai, tarp kuriu butina rasti kelia, bei kanalu linijos (grafo briaunos), kuriomis ieskomas marsrutas (jungtis) tarp tasku. Atliekamoje grafu analizeje nesvarbus atkarpos ilgis, svarbiausia yra faktas, jog atkarpa yra jungties tarp dvieju hidrografijos objektu su pavadinimais dalis. Vadinasi, siekiant veliau informacija susieti su pradiniu duomenu saltiniu, pakanka zinoti briaunu virsuniu numerius bei briaunos identifikatoriu. Tokiai analizei labai patogi topologine duomenu struktura, naudojama ArcIn-fo duomenu modelyje,--cia nurodomas linijos pradzios mazgas (FNODE), pabaigos mazgas (TNODE), galima sugeneruoti pacius taskus fiziskai. Be abejo, norint parengti pageidaujama duomenu struktura, galima naudoti ir aibe kitu priemoniu, taciau sio tyrimo metu buvo pasirinktas konvertavimas i ArcInfo topologini duomenu modeli. Taikant si modeli skaiciavimai atliekami greitai, duomenys yra aiskiai suprantami.

[FIGURE 1 OMITTED]

Toliau apibudinami suformuluoti duomenu analizes zingsniai.

Pirmasis analizes etapas:

1. Atrinkti visas briaunas, kurios neturi pavadinimu. Tai yra nagrinejamu atkarpu aibe.

2. Pasalinti is atrinktos aibes plotiniu vandens telkiniu viduje esancias briaunas (jos pirmuoju skaiciavimu etapu neitrauktos).

3. Atrinkti visus mazgus, kurie yra ant isorines plotiniu vandens objektu su pavadinimais ribos. 4. Atrinkti mazgus, kurie yra ant linijiniu hidrografijos objektu su pavadinimais.

5. Is atrinktu mazgu atrinkti tik tuos, kurie lieciasi su hidrografijos linijomis be pavadinimu. Teoriskai sis zingsnis nera butinas, taciau taip labai sumazinamos skaiciavimu apimtys, nes visi siuo etapu nufiltruoti (nepasirinkti) mazgai (marsruto taskai) yra ne ant mus dominanciu kanalu, o ant hidrografijos objektu su pavadinimais.

6. Atlikti grafu analize ir atrinkti atkarpas, kuriomis galima sujungti atrinktus marsruto taskus (1 pav., B).

Antrasis analizes etapas:

7. Atrinkti atkarpas be pavadinimu, kurios yra plotiniu hidrografijos objektu viduje.

8. Atrinkti taskus, kurie lieciasi su hidrogarfijos objektais, turinciais pavadinimus. Siuo etapu atrenkami ir tokie taskai, kurie nepriskirtini kanalams, todel taskus reikia papildomai nufiltruoti.

9. Is atrinktu tasku atrinkti tik tuos, kurie lieciasi su pirmuoju etapu isskirtais kanalais.

10. Papildomai atrinkti taskus, kurie yra ant hidrografijos liniju su pavadinimais ir yra plotiniu objektu viduje. Teoriskai siame zingsnyje atrenkama per daug marsruto tasku, taciau su jais besijungiancios bevardes atkarpos netures nuotekio tasko kitame atkarpos gale.

11. Atlikti antruoju etapu atrinktu atkarpu, zyminciu menamus hidrografinius objektus, grafu analize. Sio zingsnio pabaigoje turime atrinktas menamas kanalu atkarpas plotiniu vandens telkiniu viduje (1 pav., C).

12. Sujungiami abieju etapu rezultatai (1 pav. D pavaizduoti violetine spalva).

Atlikus skaiciavimus, per duomenu patikra paaiskejo dar keletas specifiniu duomenu strukturu--tai upiu issisakojimai, senvages bei i sias atkarpas itekantys grioviai.

GDB10LT duomenu rinkinyje kaupiama erdvine informacija apie pagrindine upes vaga ir hidrografinius objektus, nepriskirtinus pagrindinei vagai--atsakos, senvages ir pan. Nors sios atkarpos priskiriamos upiu tipui (tiksliau, tai bendras tipas, apimantis upes ir kanalus), taciau joms nesuteikiamas pavadinimas ir pozymis GRAK-TAS siekiant atskirti sias atkarpas nuo pagrindines upes tekmes. Pagal anksciau aprasyta duomenu atrinkimo algoritma sios atkarpos butu atrenkamos kaip potencialus kanalai, nes abiem galais remiasi i hidrografini objekta, identifikuojama kaip upe, o kitu specifiniu atributu, atskirianciu nuo kitos atkarpu aibes, neturi.

Tais atvejais, kai issisakojima sudaro tik viena atkarpa, atskirti gana nesudetinga nagrinejant hidrografinio tinklo objektu tarpusavio rysius (2 pav.). Taikant duomenu struktura su nurodytu linijos pradzios ir pabaigos mazgo numeriu, galima lyginti upiu atkarpu aibe su bevardziu atkarpu aibe. Siu dvieju aibiu atributines lenteles sujungtos 4 kartus naudojant pradzios ir pabaigos mazgu numerius. Sasajose pradzia pradzia, pradzia--pabaiga, pabaiga--pradzia, pabaiga--pabaiga bevardziu atkarpu atributu lenteleje irasomas susijusios ivardytos upes atributas GRAKTAS, kuris yra unikalus vienai upei. Atliekant uzklausa isskiriamos bevardes atkarpos, kuriu pradzia ir pabaiga yra susijusi su ta pati koda turinciu hidrografiniu objektu. Tai tokios atkarpos, kuriu tas pats kodas kartojasi ir sasajoje pagal linijos pradzia, ir pagal pabaiga.

[FIGURE 2 OMITTED]

Atsaka padalijanti papildoma griovio linija neleidzia identifikuoti jos pagal anksciau apibudinta algoritma, nes tampa dviem atskiromis atkarpomis ir nebesiskiria nuo kitu nagrinejamu kanalu. Tokiu atveju yra labai mazai, taciau ju identifikavimas ipareigoja atidziau patikrinti upiu issisakojimo vietas redaguojant duomenis ir atliekant vizualine analize.

4. Kanalu isskyrimo algoritmas

Anksciau isnagrinetu analizes zingsniu tikslas yra tinkamai atrinkti ir parengti duomenis tinklo analizei. Aptarkime kanalu isskyrimo algoritma. Sis algoritmas, pagristas grafu teorija, kad atrinktu is visu atkarpu tas, kuriomis gali teketi srautas nuo vienos nuotekio virsunes iki kitos (kanalai), ir tas, kuriomis negali (grioviai).

Turima tinkla vaizduojame grafu, kurio briaunos yra anksciau atrinktos bevardes hidro_l sluoksnio atkarpos, o virsunes--siu atkarpu susijungimo taskai. Is visu virsuniu isskirkime ypatingas--nuotekio virsunes (taskus).

Is pirmo zvilgsnio atrodytu, kad paprasciausia yra surasti visus kelius tarp visu nuotekio virsuniu. Briaunos, kurios sudaro tuos kelius, ir bus kanalai. Gi visu keliu radimo uzdavinys yra sudetingas--O([absolute value of V][conjunction]3), cia [absolute value of V] zymi virsuniu skaiciu (Rubin 1978),--todel taikomas kitas algoritmas.

Pirmiausia pastebekime, kad turimas tinklas yra sudarytas is daug daliu, kurios tarpusavyje nesijungia. Kiekviena tokia dali nagrinekime atskirai.

Is karto galime isskirti keleta specialiuju atveju. Pirmasis tinkle yra viena atkarpa ir dvi virsunes. Jei abi virsunes yra nuotekio--briauna zymime kaip reiksminga (t. y. kaip kanala), taciau jei bent viena virsune nera nuotekio virsune--briauna zymime kaip nereiksminga (t. y. kaip griovi). Antrasis--tinkle yra tik viena nuotekio virsune. Tokiu atveju visas to tinklo briaunas galime zymeti kaip nereiksmingas, t. y. kaip griovius.

Liko isnagrineti pagrindini atveji--kai tinklas turi daugiau nei viena briauna ir dvi ar daugiau nuotekio virsuniu. Ieskome briaunos, kuri vienintele jungia dvi tinklo dalis. Pavadinkime ja tiltu. Tilto paprasciau ieskoti salinant briauna ir tikrinant, ar tinklas vis dar yra jungus. Jei tinklas tapo nejungiu (gavome dvi dalis, kurios nesusijungia),--radome reikiama briauna. Toliau analizuojame tinklo dalis is vienos ir is kitos briaunos puses. Jei kuri nors dalis neturi nuotekio virsuniu, per tos dalies briaunas ir nagrinejama briauna netekes srautas. Tokias briaunas zymime kaip griovius. Toliau vel ieskome briaunos, kuri vienintele jungia dvi tinklo dalis, ir atliekame ta pacia veiksmu seka. Kai tokiu briaunu neberandame--kitas nepazymetas briaunas pazymime kaip kanalus.

Pavyzdys. Turime tinkla, pavaizduota 3 paveiksle. Sio tinklo tiltai yra briaunos E4, E6 ir E17. Nagrinekime kiekviena briauna atskirai.

Briauna E4. Jungia viena taska (virsune) virsuje ir visa tinkla. Virsutine dalis (viena virsune) neturi nuotekio virsuniu, todel per E4 srautas netekes--zymime ja kaip griovi.

Briauna E6. Jungia tinkla E7, E8, E9 su likusiu tinklu. Ir vienoje, ir kitoje dalyje yra nuotekio virsuniu, todel per E6 tekes srautas.

Briauna E17. Jungia tinkla E18, E19, E20, E21, E22 su tinklu. Tinklas E18, E19, E20, E21, E22 neturi nuotekio virsuniu, todel per E17, E18, E19, E20, E21 ir E22 briaunas srautas netekes--zymime jas kaip griovius.

Turime briaunas, pazymetas kaip griovius--tai E4, E17, E18, E19, E20, E21 ir E22. Kitos briaunos yra kanalai.

[FIGURE 3 OMITTED]

Galutinai suformulavus reikalavimus pradiniams duomenims bei skaiciavimo algoritmui, efektyvumas buvo teoriskai palygintas su keleto egzistuojanciu algoritmu (Rubin 1978; Tarjan 1976). Nustatyta, kad pagal aprasyta uzduoties specifika ieskoti tiltu galima efektyviau. R. Tarjan algoritmas (Tarjan 1976) spartesnis, taciau ne toks intuityviai suprantamas. Musu aprasyto algoritmo skaiciavimo trukme yra apie 5 min., apdorojant visa hidro_l sluoksni. Vienkartinei operacijai tokios spartos pakanka, taciau jei norima skaiciavimus atlikti beveik realiu laiku arba apdoroti zymiai daugiau duomenu,--rekomenduotinas R. Tarjan pasiulytas tiltu paieskos algoritmas.

5. Keletas duomenu patikros klausimu

Atlikta analize pagelbejo sprendziant keleta vizualinio duomenu vertinimo klausimu. Kai kuriose vietose buvo pastebeti vizualiai vientisi hidrografijos tinklo atkarpu junginiai, taciau nepriskirti kanalu kategorijai. Tokias strukturas galima papildomai nagrineti, ar linijose nera trukiu del redagavimo netikslumu arba sisteminguju klaidu.

Kita vertus, kai kurios hidrografinio tinklo dalys yra atskirtos nedidelemis sankasomis, nesujungia dvieju upiu ir nera identifikuotinos kaip duomenu klaidos. Iprastinemis GIS priemonemis jos aptinkamos kaip "kabantys" mazgai, taciau sie mazgai negali buti automatiskai sujungiami su artimiausia tinklo atkarpa del minetu sankasu. Atliekant tinklo jungumo analize galima ivertinti, ar atkarpu grupe yra sujungta i vientisa struktura. Pagrindines duomenu klaidu vietos susiformuoja jau atrankos etapu, kai neatrenkami reikalingi kanalu nuotekio taskai, dazniausiai esantys ant plotiniu objektu isorines ribos; analizuojant atkarpu jungumo ir kanalu isskyrimo klausimus minetu tasku atkarpos lieka neatrinktos. Sie netikslumai susije su skirtingu sluoksniu tarpusavio informacijos suderinimo klausimais.

Pastebeta keletas sisteminguju klaidu, kurios nebuvo aptiktos ankstesniuose topologines analizes zingsniuose greiciausiai del iskraipymu, atsirandanciu duomenis konvertuojant ar ikeliant juos is isoriniu saltiniu. Paprastai vizualiai tokiose vietose matoma vientisa liniju struktura, taciau analizuojant tinkla kanalas neisskiriamas.

6. Isvados

Grafu analize yra efektyvus metodas specifiniams hidrografijos tinklo jungiems elementams isrinkti. Siekiant suskirstyti hidrografinio tinklo objektus i kitas specifines kategorijas aprasytoji metodika butu taikytina, taciau reiketu nustatyti tinkamus tinklo nuotekio tasku ir jungianciu atkarpu reikalavimus.

Sukurtas ir aprasytas grafu analizes algoritmas yra pakankamai efektyvus kanalu isskyrimo uzdaviniui spresti, vis delto, galutinai issiaiskinus ir suformulavus duomenu bei analizes principu reikalavimus, siulomas jau esamas R. Tarjan tiltu paieskos algoritmas, kuriam pakanka maziau skaiciavimo istekliu.

Analizes rezultatu vizualine analize patvirtino, jog tinklines analizes metodai taikytini hidrografijos tinklo duomenu klaidu paieskai ir vientisumui uztikrinti. Efektyviausiai klaidu vietos nustatomos kanalu ir upiu jungimosi vietose.

Esama daugiau kanalu sampratu, kurios gali buti taikomos kituose tyrimuose, todel itin svarbu yra uzdavinio sprendimo sekos aprasymas, kuris deklaruoja rezultatu prasme.

doi: 10.3846/gc.2010.18

Literatura

Lietuvos Respublikos teritorijos M 1:10 000 georeferencinio pagrindo duomenu baze GDB10LT. Nacionaline zemes tarnyba prie ZUM, 2009.

Lietuvos Respublikos aplinkos ministro 2001 m. lapkricio 7 d. isakymas Nr. 540 "Del pavirsiniu vandens telkiniu apsaugos zonu ir pakranciu apsaugos juostu nustatymo tvarkos apraso patvirtinimo".

Ross, D. T. 1977. Structured Analysis (SA): A Language for Communicating Ideas, IEEE Transactions on Software Engineering 3(1): 16-34. doi:10.1109/TSE.1977.229900

Rubin, F. 1978. Enumerating all simple paths in a graph, IEEE Transactions on Circuits and Systems 25(8): 641-642. doi:10.1109/TCS.1978.1084515

Tarjan, R. 1974. A Note on Finding the Bridges of a Graph, Information Processing Letters 2(6): 160-161. doi:10.1016/00200190(74)90003-9

The Digital Geographic Information Exchange Standard (DIGEST) V:2.1. 2000. Digital Geographic Information Working Group (DGIWG). Available from Internet: <https:// www. dgiwg.org/digest/>.

Vieningas georeferenciniu duomenu modelis. Geoobjektu katalogas [interaktyvus]. 2008. [Ziureta 2010-06-16]. Prieiga per interne-ta: <http://www.geoportal.lt/wps/poc?uri=page:Geoobjektukatalogas>.

Audrius Kryzanauskas (1), Danas Motiejauskas (2)

VI "GIS-Centras", Seliu g. 66, LT-08109 Vilnius, Lietuva El. pastas: (1) a.kryzanauskas@gis-centras.lt; (2) d.motiejauskas@gis-centras.lt

Iteikta 2010 06 15; priimta 2010 06 29

Audrius KRYZANAUSKAS. Doctoral student at Centre for Cartography, Vilnius University. System analyst at State Enterprise "GIS-Centras", Vilnius, Lithunania. Seliu g. 66, Vilnius. Ph. +370 5 2731 058; e-mail: a.kryzanauskas@gis-centras.lt

Research interests: geographic information portals, geographic Internet applications, applied geographic solutionsdescription and organizational aspects.

Danas MOTIEJAUSKAS. Master's degree student at Department of Mathematical Modelling, faculty of Fundamental Sciences at Vilnius Gediminas technical university. Programmer at State Enterprise "GIS-Centras", Vilnius, Lithunania. Seliu g. 66, Vilnius. Ph. +370 5 2724 741; e-mail: d.motiejauskas@ gis-centras.lt

Research interests: graph theory, computational geometry, discrete mathematics, analysis of algorithms, numerical methods.