Newsgroups: comp.infosystems.gis
Date:         Thu, 23 Jul 1992 10:39:47 GMT
              <GIS-L@UBVM.BITNET>
From:         Robert Weibel <K491170@CZHRZU1A.BITNET>
Subject:      Re: no subject (file transmission)

Re: Line filtering, generalization, fractals and all that

To take up again the subject of weeks ago and add some of my own comments
to the views expressed by Tom Poiker more recently...

Suitability of algorithms:

No algorithm solves ALL problems of generalization. The D-P algorithm
was developed with line thinning in mind, and does that very well. On
the other hand, what some people sometimes use that procedure for makes
me shiver. The algorithm you are using for generalizing a certain
feature class needs to be tailored to the process that generated those
features. For instance, you would not want to use the same algorithm for
a political boundary (which usually is made up of boundary-stones
connected by straight line segments) and a winding road (which may have
straight segments, bends of a certain minimal radius, etc.). Both FC's
are man-made, but they require different approaches. For boundary lines,
line simplification by elimination of points may work best, in the case
of the road feature, I would prefer a constrained smoothing algorithm.

Summa: To cover line generalization comprehensively, we need a mutlitude
of algorithms, or even better, adaptive algorithms. The current
mechanistic approaches help, but fail for complex situations and large
scale reductions. Note that I am only talking about the generalization
of lines, not areas or points or surfaces, let alone interdependent
generalization of the FC's of a map. There are people who use line
algorithms to generalize areas (by generalizing their outlines), which
is very questionable, but that's another story...
Still a long way to go.


Fractals:

There are two potential uses of fractals in generalization that I can
perceive: 1) fractal dimension as a measure of object complexity (to
guide the selection of parameters in the generalization process); and 2)
fractals as a generator of additional detail (augmentation, enhancement).

AD 1: Fractal dimension not well suited as a measure of object
complexity (e.g., line complexity) due to various problems. Different
algorithms for the extraction of the fractal dimension produce different
estimates, which is not surprising: discrete geometry, problems in
calibrating the parameters for the extraction procedure, difficulties in
fitting a model to the semi-variogram (if that method is used), etc. So,
little explanatory value due to unreliable estimates. Much simpler
measures will estimate the object complexity more reliably. Also read
Jasinski's MA Thesis (published as NCGIA report 90-1) on this subject.

AD 2: This is potentially more interesting. Among others, Geoff Dutton
has done it for lines (The American Cartographer, 8/1: 23-40, 1981). One
could also perceive the usefulness of fractal processes to add detail to
the foreground of perspective views of DTM's (where huge facets result
in the foreground, whereas excessive facets have to be eliminated in the
background prior to projection and hidden object removal).
On the other hand, I guess I would agree with Tom Poiker that the
usefulness of fractals here is also limited. Other recursive procedures
to add "noise" may be used in the case of lines and surfaces. If
fractals are to be used for more than just enhancement of local details,
I would prefer to use physically based modeling approaches. In the
case of surfaces, for instance, fractal surfaces do indeed resemble
natural terrain to some extent. However, they have some limitations with
respect to their explanatory value for geomorphology. For instance, on
eroded natural landscape, the number of pits (local minima on the
surface) will be far less than the number of peaks (local maxima). On
"perfect" fractal surfaces, the number is equal. That may only hold for
lunar surfaces or other surfaces unexposed to erosion or denudation.

Sources for physically based modeling of terrain surfaces: see various
SIGGRAPH proceedings, e.g., Kelley et al. (SIGGRAPH '88) or Musgrave et
al. (SIGGRAPH '89). There are more.

Rob Weibel
Geography, U. of Zurich
K491170@CZHRZU1A.bitnet
Newsgroups: comp.infosystems.gis