Print deze pagina

Automated aggregation of geographic objects

Van Smaalen, Automated, 55

A new approach to the conceptual generalisation of geographic databases
J.W.N. van Smaalen

Publications on Geodesy 55, Delft, 2003. 104 pagina's.
ISBN-13: 978 90 6132 282 5. ISBN-10: 90 6123 282 0.


Summary

Since the late 1960's automated methods for map generalisation have been studied, but thus far no comprehensive system has been achieved. This is due to the general complexity of the matter, part of which is caused by the inability to separate the conceptual and the graphic issues. These aspects of map generalisation are considered separate issues ever since the advent of GIS but in practice it has been difficult to disconnect the conceptual issues from the impediments of graphic representation, either in the form of a paper map or on a computer screen. Current research into automated map generalisation generally appears to be in a cul-de-sac for this reason.

This study therefore aims to concentrate on strictly non-graphic operations and large generalisation steps, i.e. big scale changes. Whereas most existing methods work towards a clear end result, this approach does not. Instead, it is entirely based on the input data. Minimizing generalisation errors is a priority and assessment of the generalisation results is also an issue to consider. The goal is to develop a system for the generalisation of object- and vector-based categorical maps, such as large-scale topographic data, that is to a large extent automated and can be operated by non-expert users. In the past, several generalisation procedures have been developed for individual objects and dichotomous maps, but the number of procedures for categorical maps is still limited and the methods that do exist rely on similarity and importance factors that are hard to determine.

Large-scale categorical data mostly form an area partition, i.e. the whole spatial extent of the dataset is covered by objects and the objects do not overlap. This implies that objects cannot simply be removed - since this would cause 'holes' - but have to be combined or aggregated.

Objects can be aggregated based on taxonomy or partonomy relationships. Taxonomy relationships are based on similarity between the objects or classes. Aggregation based on taxonomy relationships has been described extensively in map generalisation literature, but only works within a limited spatial range. Since this study is aimed at large-scale changes it is based on the much less described partonomy relationships. Inter-object and inter-class relationships are used to determine functionally related classes in order to aggregate the object instances of the class. It is assumed that spatial correlations indicate functional relationships. The class adjacency index is used as a measure of spatial correlation between classes. Combinations of classes with a high class adjacency index are likely candidates for the creation of composite classes. Adjacent objects of these classes can subsequently be aggregated and reclassified to create composite objects.

The class adjacency index is determined based on adjacency measures of the member objects. The input dataset must therefore form a topologically correct, object-based area partition. The implementation is based on a stored adjacency graph and uses regular relational database management software. The data model is object-based and supports the concept of composite objects. In the process a multiple representations dataset is produced by connecting the composite objects created in every aggregation cycle to the constituent parts in the previous level.

The process can be fully automated but it is also possible to allow user interaction at several points in the process without compromising the approach. Since it is entirely based on characteristics of the input dataset, the method is also suited for exploratory purposes. To a certain degree, the meaning of the classes is not even relevant, although in interactive mode the user naturally has to be aware of the classes.

The method was applied to two Dutch topographic datasets: TOP 10vector and GBKN. The results show that this is a very promising method for conceptual generalisation. The concept of composite classes makes that generalisation errors are not an issue. Therefore, it cannot be evaluated using conventional generalisation effect measures. The output of the aggregation process is not readily suitable for mapping purposes, and additional cartographic generalisation is in that case required. The current, implementation is not intended as a complete solution for conceptual generalisation. But since it is set in an environment of other conceptual generalisation operations, such as structural generalisation and extended adjacency graphs, it can be extended to create such a comprehensive system.


Contents

    • Introduction
    • Related literature
    • Conceptual data model
    • Abstraction process
    • Datasets
    • Implementation
    • Results and discussion
    • Conclusions and recommendations
      • References
      • List of symbols

Samenvatting

Sinds het einde van de zestiger jaren wordt onderzoek gedaan naar geautomatiseerde methoden voor kaartgeneralisatie. Tot dusverre zijn geen alomvattende systemen gerealiseerd. Dit omdat het een zeer ingewikkeld onderwerp betreft, deels veroorzaakt doordat de conceptuele en de cartografische aspecten niet goed (kunnen) worden gescheiden. Deze beide aspecten worden als afzonderlijke onderwerpen gezien sinds de opkomst van de geografische informatiesystemen, maar in de praktijk blijkt het erg moeilijk de conceptuele zaken te scheiden van de beperkingen die een grafische weergave in de vorm van een kaart met zich meebrengen. Hierbij maakt het niet uit of het een papieren kaart betreft of een afbeelding op een beeldscherm. Het onderzoek naar geautomatiseerde kaartgeneralisatie lijkt hierdoor grotendeels op een dood spoor te zijn beland.

Dit onderzoek richt zich daarom strikt op niet-cartografische operaties en daarnaast op grote stappen in het generalisatieproces, i.e. grote schaalovergangen. Waar de meeste bestaande methoden naar een bekend eindresultaat toewerken, is dat in dit onderzoek niet het geval. In plaats daarvan is het volledig gebaseerd op de uitgangsgegevens. Het minimaliseren van generalisatiefouten is een prioriteit en ook wordt er aandacht besteed aan verschillende manieren om de resultaten te beoordelen. Doel is te komen tot een systeem voor generalisatie van object- en vectorgebaseerde, geclassificeerde gegevenssets - zoals grootschalige topografische data - dat voor een zo groot mogelijk deel is geautomatiseerd en kan worden toegepast door niet-ingewijde gebruikers. In het verleden zijn diverse generalisatiemethoden ontwikkeld voor individuele objecten en zogenaamde aan- en afwezigheidskaarten, maar methoden voor geclassificeerde kaarten zijn schaars en de methoden die er zijn, zijn gebaseerd op moeilijk vast te stellen factoren die overeenkomst en importantie weergeven.

Geclassificeerde grootschalige gegevens zijn meestal opgebouwd uit een aaneengesloten bedekking van vlakken. Dat wil zeggen dat de hele ruimte is bedekt met objecten die elkaar niet overlappen. Dit betekent echter dat objecten niet simpelweg kunnen worden verwijderd - omdat er dan gaten in de beschrijving ontstaan - maar moeten worden samengevoegd met aangrenzende objecten.

Objecten kunnen worden samengevoegd op basis van taxonomische relaties (classificatierelaties) of op zogenaamde 'deel-van'-relaties. Taxonomische relaties zijn gebaseerd op overeenkomsten tussen de objecten of de klassen. Samenvoeging (aggregatie) op basis van deze relaties komt veel voor in de literatuur over kaartgeneralisatie, maar werkt slechts binnen een beperkt ruimtelijk bereik. Omdat dit onderzoek zich richt op grote aggregatiestappen is het in plaats daarvan gebaseerd op de veel minder beschreven 'deel-van'-relaties. Relaties tussen objecten onderling, objecten en klassen, en klassen onderling worden gebruikt om functioneel gerelateerde klassen te vinden. Hierbij wordt verondersteld dat ruimtelijke correlatie wijst op functionele relaties. Als maat voor de ruimtelijke correlatie tussen klassen wordt de class adjacency index gebruikt. Combinaties van klassen met een hoge waarde voor de class adjacency index zijn het meest geschikt om samengestelde klassen te vormen. Aangrenzende objecten van deze klassen kunnen vervolgens worden samengevoegd en geherclassificeerd tot samengestelde objecten.

De class adjaceney index wordt bepaald op basis van buurrelaties tussen de objecten in de klassen. De uitgangsgegevens dienen daarom te bestaan uit een topologisch correcte, aaneengesloten bedekking van objecten. De implementatie is gebaseerd op een opgeslagen topologische graaf van buurrelaties en maakt gebruik van gangbare relationele database management software. Het datamodel is objectgebaseerd en ondersteunt het gebruik van samengestelde objecten. Tijdens het proces wordt een meerschalige dataset gecreëerd doordat de samengestelde objecten uit elke aggregatiecyclus worden gekoppeld aan de objecten uit de voorgaande cyclus waaruit ze zijn samengesteld.

Het proces kan volledig worden geautomatiseerd, maar het is ook mogelijk om de gebruiker het proces op diverse punten te laten beïnvloeden zonder inbreuk te doen op de aanpak. Omdat de methode volledig is gebaseerd op kenmerken van de uitgangsgegevens is zij ook geschikt voor het verkennen van een dataset. De betekenis van de klassen is tot op zekere hoogte niet van belang. Hoewel de gebruiker in de interactieve modus natuurlijk wel op de hoogte moet zijn van de betekenis.

De methode is toegepast op twee topografische datasets: TOP 10vector en GBKN. De resultaten tonen aan dat dit een veelbelovende methode voor conceptuele generalisatie is. Door het concept van samengestelde klassen is er geen sprake van generalisatiefouten. Evaluatie met de gebruikelijke generalisatie-effectmaten is daardoor niet mogelijk. De output van het aggregatieproces is niet zonder meer te gebruiken voor het maken van kaarten. In dat geval is aanvullende cartografische generalisatie noodzakelijk. De huidige implementatie beoogt ook niet een volledige oplossing voor conceptuele generalisatie te zijn, maar omdat zij is ingebed in een omgeving met andere conceptuele generalisatie- operaties kan zij worden uitgebreid om een dergelijk volledig systeem te creëren.