logo NCGeo

Variable-scale Geo-information

Pog 76, Lucasz Grus, Assessing Spatial Data Infrastructures

Martijn Meijers

Publications on Geodesy 77
Delft, 2011. 244 pagina's. ISBN: 978 90 6132 335 8. Alleen verkrijgbaar als pdf.


Summary

The use of geo-information is changing by the advent of newmobile devices, such as tablet-pc's that harness a lot of computing power. This type of information is more and more applied in mainstream digital consumer products, in a netcentric environment (i. e. dissemination takes place via the Internet) and the advances inmobile hardware also have changed the way people can interact with the geographic information at hand, compared to 'old-fashioned' paper maps.

However, current state-of-the-art solutions for storing, maintaining and disseminating digital maps still mimic the analogue map-series concept in the sense that for every map scale in the serie (e. g. 1:25k, 1:50k, 1:250k) a different digital copy with independent data is kept and maintained at the producers site. The challenge of this work was to get to a representation of the real world with gradually changing level of detail, instead of representations with discrete levels of detail (organised in multiple, independent layers, each layer representing only one resolution level).

Vario-scale data structures try to avoid this redundancy of the geometric description of the map by storing references to composing map elements of the highest level of detail for any other element of a lower level of detail. An example of variable-scale data structures are the tGAP data structures (van Oosterom, 2005). In addition to the geometry and references, an importance value for every object is stored and based on this importance value dierent representations (where the level of detail is gradually changing) can be derived on the y from these structures according to the needed level of detail.

The overall aim of this research has been to investigate variable-scale geoinformation, by dening theoretical underpinnings of vario-scale geo-information and improving the initial tGAP structures. The objective we had with this research is expressed in the main question, which was formulated as:

How can we realise improved vario-scale geo-information having minimal redundancy?

The overall outline of the research design draws heavily upon the paradigmof design research (Hevner et al., 2004). In an iterative fashion we performed theory building, prototype developments and experiments with real world data sets. Over the course of this research, we have made the following main contributions to the design of a vario-scale geo-information environment.We have:

  • formalised the concept of variable-scale data as a conceptual 3D model (the space-scale cube, ssc), where 2D space and 1D scale is integrated;
  • shown for the tGAP data structures how minimal data redundancy can be obtained when applying a merge operation, how to perform a parallel simplication of lines, without introducing unwanted topological errors and proposed a split operation, for which it was analysed what the impacts are on the designed data structures;
  • shown how to derive a 2D map from the structures with a particular number of objects, as well as investigated progressive data streaming;
  • proposed an improved way of generating data so that even smoother graphic transitions can be derived for visualisation.

The main conclusions that can be drawn from these contributions:

  • With the concept of the proposed space-scale cube (SSC) we have formalised what vario-scale vector data entails. In a sense, the improved design of the tGAP data structures can be seen as a lossless encoding of the data that is captured for a ssc.
  • To make vario-scale geo-information operational, we need specic generalisation operations. These vario-scale generalisation operations should be designed carefully to be able to give guarantees on the amount of data to be stored and output topologically consistent vario-scale data.
  • Although the improved tGAP structures are capable of providing a smooth zooming end user experience, we still store and visualise discrete steps – albeit smaller and more local than is common with current state of the art solutions. Therefore we proposed how smoothness of the vario-scale data can be improved (where the smooth SSC taking a small step in scale leads to a small change in the 2D derived map). A novelty of this approach is that, as it is one integrated space-scale partition, using a non-horizontal slice plane leads to a valid, mixed-scale planar partition: this is useful for use in 3D computer graphics (far away from an observer having less detail than close by).

Although this research has generated some knowledge for a vario-scale environment, it also paves the way for future research. The main recommendations for future work are:

  • Investigate how to deal with very large data sets that do not fit in main memory (during the generalisation process or during visualisation) deserves attention.
  • The smooth encoding of the ssc has the same building challenge as the classic tGAP with respect to applying the right sequence of generalisation operators (remove or merge, collapse or split, simplify) to obtain maps with sucient cartographic quality.

Another point for further research is the smooth interactions: it is of importance to know how users perceive these.¿e same holds for mixedscale slices (in a 3D world).

  • Focus of this research has been mostly on obtaining and viewing varioscale data. Performing analysis with vario-scale data is another interesting aspect that deserves attention, e. g. vario-scale data could be of help in data integration.
  • Investigate how tomake the structures dynamic: currently the tGAP structure (including the new smooth variant) is a static structure and has to be re-built if the source data changes. Being able to perform incremental updates (partially re-generalising data for a new situation) would be bene- cial if the data volume increases.

Related to this is higher dimensionality of smooth, vario-scale data (e. g. 3D data) leading to integrated 5D data management (integrating dimensions of space (2D or 3D), time (updates, 1D) and scale (level of detail, 1D).


Contents

  • Acknowledgements ... i
  • Setting the scene ... 1
  • Research background ... 19
  • Formalising valid vario-scale data ... 53
  • Improving variable-scale data structures ... 83
  • Improving vario-scale data dissemination ... 141
  • A new era: smooth vario-scale data ... 173
  • Conclusions and Future work ... 191
  • Bibliography ... 205
  • Summary ... 227
  • Samenvatting ... 231
  • Curriculum Vitae ... 235

Samenvatting

Variabele-schaal Geo-informatie

Het gebruik van geo-informatie is de laatste tijd sterk veranderd door de opkomst van nieuwe mobiele hardware, zoals tablet pc's die over veel rekenkracht beschikken. Daarnaast wordt geo-informatie, zoals topograsche kaarten,meer en meer toegepast in consumentenproducten (denk aan mobiele telefoons) binnen een netwerk-georiënteerde omgeving (i. e. de verspreiding van de informatie vindt plaats via het internet) en de nieuwe mobiele hardware biedt tevens nieuwe mogelijkheden, ten opzichte van ‘ouderwetse’ papieren kaarten, voor de manieren waarop mensen interacties kunnen hebben met de geograsche informatie.

Echter, de huidige state-of-the-art oplossingen voor het opslaan, onderhouden en verspreiden van digitale kaarten bootsen nog steeds de analoge kaartseries na, in de zin dat voor elke kaartschaal in de serie (bijvoorbeeld 1:25k, 1:50k, 1:250k) een aparte digitale kopie met onafhankelijke gegevens wordt bewaard en onderhouden door de producent. De uitdaging van dit onderzoek is om tot één representatie van de echte wereld met geleidelijk veranderende mate van detail te komen, in plaats van meerdere voorstellingen met hun eigen discrete detailniveaus (die ook nog georganiseerd zijn als aparte en onafhankelijke kaartlagen).

Vario-schaal datastructuren proberen om de redundantie van de geometrische beschrijving te vermijden door de kaarten op te slaan als verwijzingen in een structuur, waarbij elementen van een laag detailniveau verwijzen naar elementen van het hoogste detailniveau. Een voorbeeld van deze zogenaamde variabele-schaal datastructuren zijn de tGAP datastructuren (van Oosterom, 2005). In aanvulling op de geometrie en referenties, wordt voor elk element een zogenaamde belangrijkheidswaarde opgeslagen en op basis van deze waarde kunnen 2D kaarten on-the-fly worden afgeleid (waarbij demate van detail geleidelijk verandert).

Het algemene doel van dit onderzoek is het deniëren van de theoretische onderbouwing van variabele-schaal geo-informatie en het verbeteren van de initiële tGAP structuren. Dit doel komt tot uitdrukking in de onderzoeksvraag, die werd geformuleerd als:

Hoe kunnen we verbeterde vario-schaal geo-informatie realiseren, waarbij minimaal redundante data-opslag gewaarborgd is?

De onderzoeksopzet leunt op het paradigma van design research (Hevner et al., 2004). In een iteratieve manier hebben we theorievorming, prototype ontwikkelingen en experimenten met data sets uit de praktijk afgewisseld. In de loop van dit onderzoek zijn de volgende bijdragen aan het ontwerp van een vario-schaal geo-informatie omgeving gerealiseerd. We hebben:

  • het concept van variabele-schaal gegevens geformaliseerd als een conceptueel 3D model (de ruimte-schaal kubus, Engels: space-scale cube ssc), waar 2D ruimte en 1D schaal in is geïntegreerd;
  • weergegeven hoe voor de tGAP datastructuren een minimale redundante opslag van gegevens kan worden verkregen na de toepassing van een samenvoeg-actie, hoe parallel lijnen te versimpelen, zonder dat er ongewenste topologische fouten optreden en een splits operatie voorgesteld, waarvoor werd geanalyseerd wat de effecten zijn op de ontworpen data structuren;
  • laten zien hoe een 2D kaart uit de structuren met een ingesteld gemiddeld aantal objecten kan worden afgeleid, evenals dat we progressieve data overdracht hebben onderzocht;
  • een verbeterde manier van het genereren van vario-schaal gegevens voorgesteld, zodat nog geleidelijkere grasche overgangen kunnen worden afgeleid voor visualisatie doeleinden.

De belangrijkste conclusies die getrokken kunnen worden uit deze onderzoeksbijdragen:

  • Met het concept van de voorgestelde ruimte-schaal cube (SSC) hebben we geformaliseerd wat vario-schaal vector data inhoudt. In zekere zin kan het verbeterde ontwerp en vullen van de tGAP data structuren gezien worden als een exact omkeerbare (Engels: lossless) codering van de gegevens die worden vastgelegd voor een ssc.
  • Om vario-schaal geo-informatie operationeel te maken is er behoeve aan specieke generalisatie operaties. Deze operaties moeten zorgvuldig ontworpen worden om de hoeveelheid van de gegevens die worden opgeslagen te beperken en de topologische consistentie te waarborgen.
  • Hoewel de verbeterde tGAP data structuren in staat zijn om een geleidelijke overdracht van gegevens aan een eindgebruiker aan te bieden (van grof naar jn) worden nog steeds discrete stappen opgeslagen – alhoewel het kleinere en lokalere stappen zijn, dan wat gebruikelijk is voor de huidige state-of-the-art oplossingen (multi-representatie databases, MRDBs). Daarom hebben we voorgesteld hoe de geleidelijkheid van vario-schaal gegevens kan worden verbeterd (met de geleidelijke ssc, waarbij het nemen van een delta in schaal ook leidt tot een delta in het 2D afgeleide kaartbeeld).

Het bijzondere van deze aanpak is dat, omdat het een geïntegreerde ruimteschaal partitie is, het gebruik van een niet-horizontale doorsnede ook leidt tot een valide vlakkenpartitie, maar dan met een gemengde kaartschaal (Engels: mixed-scale): dit is nuttig voor gebruik in 3D computer graek toepassingen (waarbij ver weg van een waarnemer minder detail nodig is dan dichtbij).

Hoewel dit onderzoek hee geleid tot nieuwe kennis over een vario-schaal omgeving, zijn er genoeg vragen onbeantwoord gebleven voor verder toekomstig onderzoek. Als belangrijkste punten voor toekomstige onderzoek onderscheiden we:

  • Onderzoek hoe om te gaan met zeer grote data sets die niet meer in het hoofdgeheugen van de computer passen (noch tijdens het generalisatie proces, noch tijdens de on-the-fly visualisatie).
  • De geleidelijke ssc hee dezelfde uitdagingen als de klassieke tGAP data structuren met betrekking tot de toepassing van de juiste volgorde van generalisatie operatoren (samenvoegen, splitsen, lijnversimpeling) om kaarten te verkrijgen met voldoende kartograsche kwaliteit. Een ander punt voor verder onderzoek is de interactie mogelijkheden die de geleidelijkheid brengt: het is van belang om te weten hoe de gebruikers dit ervaren. Hetzelfde geldt voor afbeeldingen met een gemengde kaartschaal (mixed-scale, voor toepassing in een virtuele 3D wereld).
  • Nadruk van dit onderzoek hee vooral op het verkrijgen en bekijken van vario-schaal gegevens gelegen. Het uitvoeren van analyses met varioschaal gegevens is een ander interressant aspect dat aandacht verdient, e. g. vario-schaal gegevens zouden kunnen helpen bij het proces van dataintegratie.
  • Onderzoek hoe de structuren dynamisch gemaakt kunnen worden: op dit moment is de tGAP structuur (inclusief de nieuwe geleidelijke variant) een statische structuur en moet opnieuw worden gebouwd, indien de brongegevens veranderen. In staat zijn om incrementele wijzigingen uit te voeren, viz. het gedeeltelijk kunnen hergeneraliseren van de (gewijzigde) startgegevens voor een nieuwe situatie, is nodig (vanuit praktisch oogpunt) als het volume van de opgeslagen gegevens toeneemt.

Gerelateerd aan het dynamisch maken is het verhogen van de dimensionaliteit van de geleidelijke, vario-schaal partitie. Geïntegreerd data management (met de volgende geïntegreerd dimensies: ruimte (2D of 3D), tijd (updates, 1D) en schaal (niveau van detail, 1D) zou kunnen worden uitgevoerd op een 5D datamodel (waarbij gelijktijdig historie bijgehouden wordt).

Ga naar boven
JSN Boot template designed by JoomlaShine.com