International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
Besides high demands for the storage of those large number of
representations on the server, this also has high requirements
concerning the transmission of the data, as a large number of
potentially large data sets has to be transmitted. Due to the fact
that changes in the data occur only at selected places in the data
sets, potentially also highly redundant data is sent. Alternatives
are to provide only a limited set of representations, where large
changes occur — comparable to the map series of topographic
maps. The project GiMoDig aims at providing a combination of
on-line generalization and access to pre-generalized data
[Sarjakoski et al, 2002]. Bertolotto & Egenhofer [2001]
describe an approach for progressively transmitting vector data
by pre-computing a sequence of map representations at
different Levels of Detail (LoDs). Between adjacent scales,
appropriate interpolations or morphing operations can be done
([Cecconi et al., 2002], [van Kreveld 2002]).
Another alternative is to sent only changes or differences in the
data set, which already can reduce the amount of data
considerably. This is e.g. well known from the progressive
transmission of GIF-images over the internet. Thiemann [2002]
proposes to use this method for the visualization of 3D building
data in different levels of detail. A further possibility is not to
send the changes as such, but a set of operations that describe
the object and the changes. This requires that on the client side
these instructions can be interpreted in order to correctly restore
the object. A basic requirement for the coding scheme is that
the amount of data to be transmitted should be less than that
would be needed to transmit the original data set.
In order to represent different levels of detail of vector
geometry, hierarchical schemes can be used. On example is the
GAP-tree for the coding of area partitionings in different levels
of detail [van Oosterom, 1995]. The BLG (binary line
generalization) tree hierarchically decomposes a line using e.g.
the Douglas-Peuker algorithm [Douglas & Peucker, 1973].
[n our approach a set of elementary operations was defined that
allow for describing geometric and topologic changes in vector
data sets. Generalization operations can be decomposed into a
sequence of operations leading to a sequential reduction /
increase of detail. Thus data coded in a vocabulary of so called
Simple Operations (SO's) can be sent to the client, where it is
restored again in order to be visualized.
3. GENERALIZATION OPERATIONS
Generalization operations can be characterized by changes
occurring to objects which are either discrete or continuous.
These changes can affect individual objects and groups of
objects, respectively. In the following examples for both types
of changes are given.
3.1 Discrete changes of individual objects
Changes of this kind can be characterized by the fact that the
topology and the geometry of the object changes. Examples for
this class of changes are operations like the simplification of
building ground plans or simplification of lines (point
reduction) using e.g. Douglas-Peuker filtering.
32 Continuous changes of individual objects
Continuous changes of objects occur when the topology
remains the same, however geometry changes by shifting either
the whole object or individual points of the object.
Displacement is a typical representative for such a change. Also
in the case of enlargement, only the position of object vertices
changes, not affecting the topological structure of the objects.
3.3 Discrete changes of groups of objects
These changes typically occur when larger scale changes have
to be traversed and thus the aggregation level and often the type
of object changes. An example is typification, where a group of
objects is represented by a new group consisting of less objects.
The following table gives a classification of the different
generalization operations into the different categories. Based on
this analysis examples for the implementation of the operations
are given. The operations highlighted in bold are described in
more detail.
Operation Discrete, Discrete, Continuous |
individual | group (3.2)
(3. 1j (3.3)
Simplification (e.g. X
Gauss)
Point reduction (e.g. X
Douglas-Peuker)
Building X
generalization
Displacement X
Typification X
Aggregation X X
Enhancement (e.g. X
enlargement)
4. DECOMPOSITION OF CHANGES INTO
ELEMENTARY OPERATIONS
The coding scheme has been developed for the generalization of
polygons, especially building ground plans. It is, however,
obvious, that the approach is generally applicable to all the
above mentioned generalization operations.
4.1 The Generalization Chain
Similar to the ideas introduced by Hoppe for triangulated
meshes [Hoppe 96], we define for a polygon P consisting of n
vertices a minimal representation P". with m £n vertices, and
a maximal representation P^ P, consisting of all original
vertices. The minimal representation is the one which is still
sensible from a cartographic viewpoint, for example in case of a
building a rectangle, m = 4 , or the empty polygon.
During pre-processing, map generalization starts from polygon
P". successively simplifying its representation using
generalization operations as described in Section 5.2, finally
yielding polygon P". Assume that k. generalization steps are
involved (each leading to one or more removed polygon
vertices), and the number of polygon vertices are numbered
2H, d. ndm, then a sequence of generalized
polygons
Pa P = Pt} Per Ph =P”
£o 81 Sk-1
is obtained, where g, denotes the j-th generalization operation.
Every generalization step g, Is tied to a certain value of a
1294
Internation
control par.
be — as dis
edge in the
the edge wl
alternativel
Since genet
sequence «
consequenc
operations
generalizati
operations
However, 1
operations
polygon fro
pr == Pi
where agai
modification
correspondi
generalizati
information
the minimal
of inverse gt
4.2 Encodi
We call th:
elementary
generalizatic
EGO's. Eac
operations (
there are op
namely the
which affect
operations.
operation i
convenience
operations
parameters o
inverse oper;
which the ii
specify the Ic
Opcode | D
IV In
DV D
V
MV IM
RV Re
Vi
EC
Figure 1 sho
realizes the
