Updating of geographic data in a multiple representation database (MRDB)
Final Report Abstract
Die Ausgangsfragen lassen sich nach Abschluss des Projektes folgendermaßen beantworten. Für das Aggregationsproblem wurden zwei Kriterien identifiziert, anhand derer die Qualität einer Lösung gemessen werden kann: Klassenänderungen sollen gering sein, geometrisch kompakte Formen sind zu bevorzugen. Um Klassenänderungen zu quantifizieren, wurde eine semantische Distanz zwischen Klassen vorgeschlagen. Oft zielt die Generalisierung auch darauf ab, Muster in Datensätzen zu erhalten. Ob ein generalisierter Datensatz dieser Anforderung gerecht wird, ist auch eine Frage der semantischen Genauigkeit. Für die Zukunft ist angestrebt, Maße zu finden, die Muster charakterisieren. Unter Verwendung dieser Maße wäre auch eine Losung durch Optimierung möglich: Charakteristische Mar ße sollen sich möglichst wenig ändern. Für die Aggregation wurde ein Ansatz durch gemischt-ganzzahlige Optimierung vorgeschlagen. Dieser lässt sich auf andere Probleme der Generalisierung übertragen, wie bereits am Beispiel der Gebäudegeneralisierung gezeigt werden konnte Grundsätzlich wurde die Notwendigkeit erkannt, dass stärker als bisher zwischen harten Nebenbedingungen der Generalisierung und Zielen der Generalisierung unterschieden werden muss. Eine harte Nebenbedingung ist beispielsweise, dass selbstschneidende Polygone unzulässig sind. Die Vermeidung von Klassenänderungen ist dagegen ein Ziel der Generalisierung. Wurden die wesentlichen Ziele und Nebenbedingungen der Generalisierung identifiziert und formalisiert, so ist eine Lösung durch (kombinatorische) Optimierung möglich: Die Ziel- oder Kostenfunktion wird unter den Nebenbedingungen minimiert. Eine integrierte Modellierung der Generalisierung als Optimierungsproblem, also die simultane Berücksichtigung aller Variationsmöglichkeiten, ist allerdings oft nicht realisierbar: Das Problem kann zu komplex werden und ist möglicherweise nicht mehr effizient lösbar. Aus diesem Grund ist eine Zerlegung der Generalisierungsaufgabe in Teilaufgaben sinnvoll. Um eine Landbedeckungskarte zu generalisieren, wurden drei Operatoren entwickelt, die nacheinander angewendet wurden: Kollaps von Flächen zu Linien, Flächenzusammenfassung und Liniengeneralisierung. Wir haben gesehen, dass der momentan am weitesten verbreitete Ansatz durch Region Growing nicht zu Ergebnissen hoher Qualität führt. Die Produktion qualitativ hochwertiger digitaler Landschaftsmodelle erfordert einen Mehraufwand an Rechenzeit, der sicherlich tolerabel ist, solange er sich in Maßen hält. Allerdings kann die exakte Lösung kleiner Instanzen des Aggregationsproblems (ca. 50 Flächen) bereits mehrere Tage dauem - der Grund hierfür liegt in der NP-Schwere des Problems. Natürlich ist eine derartig lange Rechenzeit in der Praxis inakzeptabel. Daher sind gute Heuristiken für die Generalisierung erforderlich. Um sehr große Datensätze prozessieren zu können, ist es notwendig, einen Datensatz in kleinere Datensätze zerlegen zu können. Eine der entwickelten Heuristiken erlaubt eine derartige Zerlegung. Sie beruht auf der Annahme, dass die Klassen großer Flächen unverändert bleiben. Diese Zerlegung in Teilinstanzen ermöglicht die Handhabung sehr großer Datensätze und die effiziente Propagierung von Aktualisierungen. Ein Kartenblatt der digitalen topographischen Karte 1:50000 mit 5537 Flächen wurde in 82 Minuten für den Zielmaßstab 1:250000 generalisiert. Im Vergleich zum Region Growing konnten, bei Vernachlässigung der Kompaktheit, die Kosten für Klassenänderungen um 37.5% reduziert werden. Wurde die Kompaktheit als weiteres Optimierungsziel berücksichtigt, so ergab sich eine Reduktion der Kosten für Klassenänderungen um 19.8%; die Kosten für nicht kompakte Flächen wurden um 1.8% reduziert. Zusammenfassend ist zu sagen, dass das vierjährige, von der DFG geförderte Forschungsprojekt zu weitreichenden neuen Erkenntnissen über die Generalisierung geführt hat. Insbesondere die Herangehensweise, ein Qualitätsmaß für die Generalisierung zu definieren und dieses Maß konsequent als Kostenfunktion in einem Optimierungsansatz anzuwenden, stellt eine Neuerung dar. Dieser Ansatz erlaubt es, Ergebnisse zu erzielen, die den Ergebnissen gängiger Ansätze hinsichtlich der Qualität klar überlegen sind. Darüber hinaus bietet der entwickelte Ansatz die Möglichkeit einer exakten Lösung für kleine Instanzen und liefert somit Referenzlösungen, an denen die Qualität von Heuristiken abgeschätzt werden kann.
Publications
- 2004. MRDB to connect 3D city models, cadastral, and topographic data together. In: Proceedings 24th Urban Data Management Symposium (UDMS'04), 27.-29. Oktober 2004, Chioggia (Venedig), Italien
Anders, K.-H., & Haunert, J.-H.
- 2004. Using the straight skeleton for generalisation in a multiple representation environment. In: Proceedings 7th ICA Workshop on Generalisation and Multiple Representation, 20.-21. August 2004, Leicester, UK
Haunert, J.-H., & Sester, M.
- 2005. Geometrietypwechsel in einer Multi-Resolution-Datenbank. In: Mitteilungen des Bundesamtes für Kartographie und Geodäsie, Band 34- Arbeitsgruppe Automation in der Kartographie - Tagung 2004. Verlag des Bundesamtes für Kartographie und Geodäsie, Frankfurt am Main, Deutschland
Haunert, J.-H.
- 2005. Link based conflation of geographic datasets. In: Proceedings 8th ICA Workshop on Generalisation and Multiple Representation, 7.-8. Juli 2005, La Coruña, Spanien
Haunert, J.-H.
- 2005. Propagating updates between linked data sets of different scale. In: Proceedings 22nd International Cartographic Conference (ICC'05), 11.-16. Juli 2005, La Coruña, Spanien
Haunert, J.-H., & Sester, M.
- 2006. Aktualisierung von Geodäten in einer Multiple Representation Database. In: Publikationen der Deutschen Gesellschaft für Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2006, Berlin, Deutschland
Haunert, J.-H.
- 2006. Generalization of land cover maps by mixed integer programming. Seiten 75-82 von: Proceedings 14th Annual ACM International Symposium on Advances in Geographic Information Systems (ACM-GIS'06), 11.-16. November 2006, Arlington, VA, USA
Haunert, J.-H., & Wolff, A.
- 2006. Hierarchical structures for rule-based incremental generalisation. Seiten 49-57 von: Proceedings ISPRS Workshop on Multiple Representation and Interoperability of Spatial Data, 22.-24. Februar 2006, Hannover, Deutschland International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, no. XXXVI(Part 2/W40)
Haunert, J.-H., Anders, K.-H., & Sester, M.
- 2007. A formal model and mixed-integer program for area aggregation in map generalization. Seiten 161-166 von: Photogrammetric Image Analysis (PIA '07), 19.-21. September 2007, München, Deutschland Intemational Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, no. XXXVI(Part 3/W49A). ISPRS
Haunert, J.-H.
- 2007. Efficient area aggregation by combination of different techniques. In: Proceedings 10th ICA Workshop on Generalisation and Multiple Representation, 2.-3. Augusi 2007, Moskau, Russland
Haunert, J.-H.
- 2007. Optimization methods for area aggregation in land cover maps. In: Proceedings 23rd International Cartographic Conference (ICC'07), 4.-10. August 2007, Moskau, Russland
Haunert, J.-H.
- 2007. Quality assessment for polygon generalization. In: Proceedings 5th International Symposium on Spatial Data Quality, 13.-15. Juni 2007, Enschede, Niederlande
Podolskaya, E. S,, Anders, K.-H., Haunert, J.-H., & Sester, M.
- 2008. Aggregation in Map Generalization by Combinatorial Optimization. Dissertation, Leibniz Universität Hannover. Reihe C, Heft 626, Veröffentlichungen der Deutschen Geodätischen Kommission, München, Deutschland
Haunert, J.-H.
- 2008. Area collapse and road centerlines based on straight skeletons. Geolnformatica, 12(2), 169-191
Haunert, J.-H., & Sester, M.
- 2008. Assuring logical consistency and semantic accuracy in map generalization. Photogrammetrie - Fernerkundung - Geoinformation (PFG), 2008(3), 165-173
Haunert, J.-H., & Sester, M.
- 2008. Optimal simplification of building ground plans. In: Proceedings XXIst ISPRS Congress, 3.-11. Juli 2008, Peking, China
Haunert, J.-H., & Wolff, A.
