Topográfiai térképek automatikus raszter-vektor konverziója Doktori értekezés tézisei Szendrei Rudolf Témavezet˝o: Dr. Elek István
Eötvös Loránd Tudományegyetem Informatikai Kar Informatikai Doktori Iskola Prof. Benczúr András, D.Sc. Információs rendszerek doktori program Prof. Benczúr András, D.Sc. Budapest, 2014.
1. Bevezetés Az értekezésben bemutatok egy olyan térkép-interpretációs módszert, amelyet a nagy lépték˝u, els˝osorban magyar, papír alapú topográfiai térképek vektorizálásának automatizálására dolgoztam ki. Ennek alapjául, illetve el˝ozményeként tekinthet˝o az IRIS projekt [4], amelynek második szakaszában résztvettem, illetve a [7] PhD értekezés eredményeire is támaszkodhattam. Dolgozatom alapvet˝o célja az volt, hogy a topográfiai térképek manuális vektorizálását informatikai megoldásokkal váltsuk ki, illetve legalább támogassuk egy magasabb szakért˝oi szintig. Az eltervezett m˝uködésben az emberi interakció a szoftvernek a térkép csoportokra való beállítására korlátozódik. Ennek során fogalmazódott meg az az alapgondolat, hogy a térképolvasó szakember tudását és látásmódját felhasználva a színes topográfiai térképek logikai rétegeit automatikusan lehessen szétválasztani (lásd 1. ábra, ahol fentr˝ol-lefelé haladva látható a pontszer˝u szimbólumok rétege, a hálózati, illetve a felületi réteg, végül pedig a rétegek egymásra rajzolódásának eredménye, a kész térkép). Ugyanez az ötlet került felhasználásra annak az anomáliának a kezelésekor is, amikor alsóbb rétegek objektumait fedik el fels˝obb rétegek objektumai. A rendszer eredményként egy-egy réteget állít el˝o vektoros állományként a pontszer˝u, hálózati, illetve felületi objektumok egy-egy típusából.
1. ábra. A térkép réteges logikai felépítése.
Téziseimet képezik az egyes térképi rétegtípusokhoz adott speciális feldolgozási módszerek (pontszer˝u, vonalas és felületi), a térképhez tartozó tudásalapú szabályleírás módszere, valamint egy olyan új algoritmus, amely képes a digitális képsz˝ur˝o algoritmusok dönt˝o hányadának automatikus párhuzamosítására. 1
A bemutatott térkép-interpretációs módszer szükségességét indokolja, hogy hazánk régi topográfiai térképei még nem kerültek vektorizálásra, valamint régiónkból kitekintve, a fejl˝od˝o országokban b˝oven vannak még vektorizálásra váró térképek a hivatalokban. Mivel a kutatás alapjául elkészített szoftvercsomag modulárisan b˝ovíthet˝o, ezt párosítva a tudásleírás lehet˝oségével [9] út nyílik a különböz˝o országok topográfiai térképeinek ugyanazon rendszerrel való feldolgozására.
2. Tudásalapú térkép-interpretációs megközelítés A használatban lév˝o szoftverek, illetve hardverek kényelmesebbé teszik ugyan vektorizáló munka elvégzését, de nem foglalkoznak a térkép értelmezésével. Ezek egy része csupán a manuális vektorizálást teszi könnyebbé, másik részük pedig tisztán kép feldolgozási lépésekkel próbál meg eljutni a vektoros adatmodellig. Mivel a topográfiai térképek ábrázolás módjai jelent˝osen eltérhetnek, illetve bizonyos térbeli viszonyok csak emberi tapasztalat alapján következtethet˝ok ki, ezért az említett módszerek nem elégségesek egy magyar topográfiai térkép interpretációjához. Ezen okból els˝o tézisemben a tudásalapú megközelítéssel [1, 2, 3] a korábbi, pusztán digitális sz˝ur˝okre épül˝o vektorizációs koncepciót szerettem volna egy hatékonyabbra [16] felváltani. Ennek során a térképi rétegeket a papírra kerülésük fordított sorrendjében tartottam célszer˝unek felismerni. A jelkulcsi elemeket az o˝ ket felismer˝o algoritmusok szerint három különböz˝o csoportba soroltam (pontszer˝u, vonalas vagy felületi). Az egyes rétegek interpretálásához szabályhalmazokat definiáltam, valamint a szabályokhoz kiértékel˝o algoritmusokat adtam. A módszer alapgondolata, hogy a térképek készítése és rétegeik papírra nyomtatása egy jól meghatározott sorrendben zajlik. A kés˝obb papírra kerül˝o rétegek objektumai takarást hoznak létre a korábbi rétegek objektumaiban. A fels˝obb rétegek eltávolítása után vizuális hiányosságok mutatkoznak a lentebbi rétegekben. Ezek megszüntetését összetett szabályrendszer kísérli meg a térkép-interpretációs tudás alapján.
3. Pontszeru˝ jelkulcsi elemek felismerése A pontszer˝u jelkulcsi elemek kisméret˝u ábrák, amelyek megtalálhatóak a jelmagyarázatok gy˝ujteményében. Az adott térképen szerepl˝o jelkulcsi elemek ezenfelül általában szerepelnek a térkép alján feltüntetett jelmagyarázatban is [10]. Fontos jellemz˝ojük, hogy a térképen mindig torzítatlan formában szerepelnek, kevés esetben elforgatott helyzetben. Második tézisem egy olyan, a pontszer˝u jelkulcsi elemek felismerésére adott módszer [11, 12, 15], amely képes a térképek speciális képi világát kihasználva a jelkulcsi elemek lineáris id˝oben történ˝o forgatás-invariáns felismerésére. 2
Az eljárás érdekessége, hogy segítségével nem csak a pontszer˝u szimbólumokat, hanem a felületi textúrákat is felismerhetjük, mivel a textúra egysége a pontszer˝u szimbólumhoz hasonló képi elem. Az algoritmus ötlete, hogy a térkép és a pontszer˝u jelkulcsi elem raszteres képét éldetektálásnak, majd Otsu küszöbölésnek vetjük alá. Az élpixeleknél kiszámított irányt és az élpixel helyzetét felhasználva a potenciális mintaillesztések mennyisége több nagyságrendben csökkenthet˝o. A módszer összevetésre került a [17] módszerrel, ami kb. 95%-os felismerési aránnyal rendelkezik. A szerz˝o által adott módszer napjaink átlag gépén nagyjából 261 másodperc alatt képes egy 100 megapixeles térkép feldolgozására, míg az új módszernél ez 2-3 másodpercet vesz igénybe. A pontszer˝u szimbólumok manuális vektorizálása akár 1 óráig is eltarthat. A lineáris futási id˝o a [11] cikkben került bizonyításra.
4. Vonalas jelkulcsi elemek felismerése Vonalas jelkulcsi elemek esetén az attribútum ábrázolás színekként és kis vonalas ábrákként nyomtatódik az útszer˝u objektum nyomvonalára vagy a poligon objektum határvonalára. Ezen elemek felismerése a raszter-vektor konverzió egyik legnehezebb feladata, mivel gyakran összetett, bonyolult ábrázolásmóddal rendelkeznek. Megengedett, hogy két vonalas jelkulcsi elem csak méretarányban térjen el egymástól, valamint az is, hogy a vonalas jelkulcsi elemek keresztezzék egymást vagy összekapcsolódjanak. Szintén nehézséget okoznak az összetartozó, párhuzamosan futó vonalak, amelyek megkülönböztetése a külön objektumokhoz tartozó, párhuzamosan futó vonalaktól még gyakorlott szemmel is nehézkes lehet. Az imént felsorolt anomáliák felismerése túlmutatott a célkit˝uzéseken, ezért csak olyan vonalas jelkulcsi elemek felismerése volt szempont, ahol feltehet˝o, hogy azok nem keresztezik egymást és nem találkoznak, továbbá összefügg˝oek, azaz nem szakad meg az ábrázolásuk. A [6] cikk bináris vonalas jelkulcsi elemek vektorizálását mutatja be raszteres képformátumú kataszteri térképeken, míg a [18] cikk topográfiai térképek szintvonalainak automatikus interpretációját mutatja be. Mivel a színes topografikus térképek elemeinek további tulajdonságai, mint útszélesség, burkolattípus stb., nem ismerhet˝o fel a klasszikus módon [8], ezért harmadik tézisemben a problémára egy új módszert [14] dolgoztam ki. Az eljárás els˝o lépésben egy-egy drótvázat állít el˝o a térképnek, valamint a vonalas jelkulcsi elemeknek a raszteres képeib˝ol. A drótvázakban ezután megkeresi azok speciális pontjait (elágazás, végz˝odés). Ezek a pontok jól ismertek az ujjlenyomat felismer˝o rendszerekben, ahol minutiae pontoknak hívják o˝ ket. Az ujjlenyomat esetében egy mintázat elágazása a komplementer mintában egy végz˝odést jelent, ezért a számítógépes gyakorlatban csak az egyik adattípus elemeit használják fel az azonosításra. 3
Fontos megjegyezni, hogy az említett komplementer tulajdonság a térképek esetében nem teljesül, így az elágazási és végz˝odési pontokra is egyaránt szükség van. A drótvázakat irányítás nélküli gráfokként értelmezve, továbbá az elágazásokat F-fel (fork), a végz˝odéseket pedig E-vel (end) címkézve kapjuk az egyes vonalas objektumok EF gráfjait. A címkézést elvégezve a térképnek és a vonalas jelkulcsi elemeknek a gráfjain, a vonalas objektumok elemi egységeinek struktúrái kereshet˝ové válnak a térkép gráfjában. Egy adott vonalas jelkulcsi elemnek a legkisebb egységéb˝ol ily módon képzett gráfjához további tulajdonságok is rendelhet˝ok. Például az elemnek a szomszédos speciális pontjait összeköt˝o út hosszát a megfeleltetett gráfbeli él súlyaként tekinthetjük, illetve a nyomvonalon fekv˝o speciális pontokat az ezen tulajdonságot leíró plusz címkével lehet ellátni. A nyomvonal attribútumot leíró címkék segítségével a vonalas jelkulcsi elem ciklikus tulajdonsága is leírható a nyomvonal végpontjainak megjelölésével. A módszer finomításként hibrid módon felhasználja az el˝ofeldolgozott képen található pixelek színindexeit is a találatok pontosításához. Az eljárás el˝onye, hogy véges determinisztikus automatával történ˝o megvalósítás esetén lineáris futásid˝ovel rendelkezik. Az eljárás végén az exportált vektoros adatok generalizálásra kerülnek [5]. A létrehozott EF gráf segítségével lehet˝oség nyílt a vonalas vektoros adatokból egy a jelkulcsi elem struktúrája, színe és további jellemz˝oi szerinti objektum felismerésre és legy˝ujtésre.
5. Homogén felületek felismerése A térképen található felületek felismerése során gyakran el˝oforduló tevékenység a vizuálisan elválasztott, de valójában összetartozó felületek egyesítése, valamint a térképi hibák kijavítása. Ennek a megoldását hivatott a negyedik tézisem bemutatni, ahol a felületek felismerését egy olyan maszk segítségével valósítjuk meg, amely megadja, hogy a térkép mely pontjai tekintend˝ok felületi pixeleknek. A maszk megadható például a pontszer˝u és vonalas jelkulcsi elemek eltávolítása után keletkez˝o területtel. További lehetséges módszer az, hogy a térképen közvetlenül elvégzett színszegmentálás után a felületi színekkel rendelkez˝o pontokat tekintjük maszknak. A maszkhoz tartozó pontokban a megfelel˝o felületi szín indexét állítjuk be, a maszkon kívüli pontokat pedig nem definiált típusúnak tekintjük. A megfelel˝o eredmény érdekében az említett két módszert együttesen kerül alkalmazásra. Ahhoz, hogy a felületeket felismerjük és jó min˝oségben poligonizálhassuk, egy heurisztikus szabályrendszert készítettem. Ennek segítségével lehet˝oség adódik annak leírására, hogy a térben egymáshoz közel fekv˝o, azonos vagy akár eltér˝o felület típusok miként „hatnak” egymásra. Más szóval, meghatározható az ismeretlen felületet határoló különféle felület típusok közötti dominancia. 4
A módszer segítségével nem csak arra van lehet˝oség, hogy egy ismeretlen típusú terület egy ismert, domináns típusú szomszédos felülethez legyen csatolva, hanem arra is, hogy a terület automatikusan felosztásra kerüljön a dominanciák alapján. A szabályrendszer kiértékeléséhez elkészítettem a megfelel˝o algoritmusokat, valamint a hozzájuk kapcsolódó, grafikus felülettel rendelkez˝o sz˝ur˝oket. Ezeken felül létrehoztam továbbá egy XML-re épül˝o, a szabályok leírását támogató formátumot is. Ennek segítségével a már megadott szabályok elmenthet˝oek és kés˝obb alkalmazhatóak a térképek kötegelt raszter-vektor konverziójában.
6. Digitális képszur˝ ˝ o algoritmusok automatikus párhuzamosítása Napjainkban a digitális képrögzít˝o eszközök sebessége és a rögzített képek mérete exponenciális növekedést mutat. Az ezzel együtt fellép˝o számítási igényre reagálva a processzor gyártók is szemléletet váltottak. Mivel architekturális akadályba ütköztek a buszsebesség további növelésével, ezért ehelyett mára már a processzor magok számának növelése a jellemz˝o. Mivel a régi, szekvenciális algoritmusok egyszerre csak egy processzor magot képesek kezelni, ezért a rendelkezésre álló számítási kapacitásnak csak a töredékét tudják kihasználni. Ötödik tézisemet egy olyan eljárás képezi, amellyel [13] a szekvenciális digitális képsz˝ur˝o algoritmusok többségét sikerült automatikusan párhuzamosítanom. Az eljárás a kép logikai particionálására épít, amely akkor használható, ha a sz˝ur˝o a memória elérését egy meghatározott sorrendben végzi, például a képet sorfolytonosan, blokkonként vagy rekurzívan dolgozza fel. A képsz˝ur˝o algoritmusok párhuzamos programozásának nehézsége f˝oként abból ered, hogy egy adott képpont értékének kiszámításához szükséges a környezetben lév˝o további képpontok értékének ismerete is. Ilyenkor a kép csupán diszjunkt felosztása nem oldja fel a területek határán található képpontok több folyamat általi egyidej˝u olvasását. Az átlapoló részek ezért nem olvashatóak egy id˝oben és nem is értékelhet˝oek ki. Ezek a területek a párhuzamosításnál az úgynevezett párhuzamosítási költséget növelik, mivel csak szekvenciálisan dolgozhatók fel. A módszer figyelembe veszi a párhuzamosítással járó ezen kritikus szakaszokat és lehet˝oség szerint minimalizálja az azokra fordítandó id˝ot. Mivel a párhuzamos programozás nagyobb szellemi és id˝oráfordítást igényel, ezért ezzel a megoldással sikerült csökkenteni a fejlesztési id˝ot, továbbá növelni az ezzel párhuzamosított kód min˝oségi mutatóját. A módszer használata kiküszöböli a párhuzamos programozáskor elkövethet˝o hibákat, melyek igen nehezen deríthet˝ok fel. Az eljárás alkalmazásával kapott párhuzamos sz˝ur˝ok futási sebességére jellemz˝o, hogy az aszimptotikusan lineárisan arányos a számítógép processzor magjainak számával, mivel a kritikus szakaszokat jelent˝o képrészletek mérete elhanyagolható a kép méretéhez viszonyítva. 5
7. Összefoglalás Egy olyan térkép interpretációs módszert dolgoztam ki öt új módszer összességeként, amely a korábbi koncepciókhoz képest jobban követi a térképolvasó ember és a térképkészít˝o szakember logikáját és látásmódját. Az alkalmazott logikát egy testreszabható szabályrendszer írja le, amelynek a kiértékel˝o algoritmusai is implementálásra kerültek. A szabályrendszer leírásához a széles körben elterjedt XML nyelv került felhasználásra, amelynek köszönhet˝oen a beállítások a programon belül és kívül egyaránt könnyen elvégezhet˝ok. A nyelv további el˝onye, hogy olyan digitális képsz˝ur˝okkel is b˝ovíthet˝o a rendszer, amelyeknek a paraméterei el˝ore nem ismertek. Az XML nyelvnek köszönhet˝oen az ismeretlen paraméterek ilyenkor ugyanis könnyedén figyelmen kívül hagyhatóak. Mind a pontszer˝u szimbólumok, mind pedig a vonalas, illetve a jelkulcsi elemek felismerését végz˝o algoritmusokat a megvalósítás során sikerült lineáris futási idej˝uvé tennem. Ezenfelül a képsz˝ur˝o algoritmusok hatékonyabb fejlesztéséhez és párhuzamos implementálásához kifejlesztettem egy olyan eszközt, amely képes a képsz˝ur˝o algoritmus automatikus párhuzamosítására. A lineáris futási idej˝u algoritmusoknak és az automatikus sz˝ur˝o párhuzamosításnak köszönhet˝oen a korábbiaknál egy gyorsabb, hatékonyabb térkép interpretációs eszközt sikerült készítenem. A sz˝ur˝oket párhuzamosító algoritmus szélesebb körben is hasznosnak mondható, mivel más célú képfeldolgozó eljárások esetében is alkalmazható.
6
Hivatkozások [1] Baik, S., et al.: A naive geography analyst system with cognitive support of imagery exploitation. Monroy, R., et al., editor, Lecture Notes in Artificial Intelligence, No. 2974, pp. 40–48, 2004. [2] Chen, H., et al.: A geographic knowledge representation system for multimedia geospatial retrieval and analysis. International Journal on Digital Libraries, No. 1, Vol. 2, pp. 132–152, 1997. [3] Corner, R.J.: Knowledge Representation in Geographic Information Systems. Ph.D. thesis, Curtin University of Technology, 1999. [4] Dezs˝o, B., Elek, I., Máriás, Zs.: Image processing methods in raster-vector conversion of topographic maps. Karras, A. D., et al., editor, Proceedings of the 2009 International Conference on Artificial Intelligence and Pattern Recognition, pp. 83–86, 2009. [5] Douglas, D. and Peucker, T.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 10(2), pp. 112–122, 1973. [6] Janssen, R. D. T. és Vossepoel, A. M.: Adaptive vectorization of line drawing images. Computer Vision and Image Understanding, 65(1), pp. 38–56, 1997. [7] Katona, E.: Automatikus térkép-interpretáció, Szegedi Tudományegyetem, 2000. [8] Liang, S., Chen, W.: Extraction of line feature in binary images. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E91A, 1890–1897, issue 8., 2008 [9] Mayer, H., Heipke, C., Maderlechner, G.: Knowledge-based interpretation of scanned large-scale maps using multi-level modeling. International Archives of Photogrammetry and Remote Sensing, 29 B3, pp. 578–585. 1992. [10] Samet H., Soffer A.: MAGELLAN: Map Acquisiton of GEographic Labels by Legend ANalysis. International Journal on Document Analysis and Recognition, Vol. 1, pp. 89–101. 1998. [11] Szendrei, R., Fekete, I., and Elek, I.: Texture based recognition of topographic map symbols. In Karras, A. D., et al., editor, Proceedings of the 2009 International Conference on Artificial Intelligence and Pattern Recognition, AIPR-09, pp. 7–10, ISBN: 978-1-60651-007-0, ISRST. 2009. 7
[12] Szendrei, R., Elek, I.: Automatic symbol recognition for topographic maps In Geomatics - Riga, pp. 42–48, 2009. [13] Szendrei, R.: Automatic parallelization of raster image filters. In Majkic, Z., et al., editor, Proceedings of the 2010 International Conference on Artificial Intelligence and Pattern Recognition, AIPR-10, pp. 30–33, ISBN: 978-1-60651-015-5, ISRST. 2010. [14] Szendrei, R., Elek, I., Márton, M.: Graph-based feature recognition of linelike topographic map symbols. Lecture Notes in Computer Science 6729, pp. 291–298, 2011. [15] Szendrei, R., Elek, I., Fekete, I.: Automatic recognition of topographic map symbols based on their textures. Lecture Notes in Computer Science 6729, pp. 299–306, 2011. [16] Szendrei, R., Fekete, I., Elek, I., Márton, M.: A knowledge-based approach to raster-vector conversion of large scale topographic maps. Acta Cybernetica 20, pp. 145–165, 2011. [17] Tsai, D., Tsai, Y.: Rotation-invariant pattern matching with color ringprojection. Pattern Recognition, 35(1), pp. 131–141, 2002. [18] Xin, D., Zhou, X., Zheng, H.: Contour Line Extraction from Paper-based Topographic Maps, Journal of Information and Computing Science Vol. 1, No. 5, pp. 275–283, 2006.
8
