‚eeded for
ror proné
ht require
n even for
r thinning
ial feature
tolerances
zular lines
extract the
opological
algorithms
ent spatial
rithms and
to develop
1 diagrams
> show that
ctly on the
s in spatial
sed in natu-
4) as “stolen
ss” of data
been exten-
iper, 1993),
stolen from
query point,
|| neighbour
led from or-
ts of points
|. (Anton el
Roos (Gold
wulas for the
n area. The
the analysis
wtial deriva
on a normed
iagrams of a
between the
present three
International Archives of the Photogrammetry, Remote §
our centreline algorithm that uses the natural neighbour interpo-
lation technique and skeletonisation. In section 7 we present the
experimental results. Finally, in section 8 we present discussion.
2 THE VORONOI DIAGRAM OF A SET OF POINTS
Let us first introduce the definition of the Voronoi diagram for a
set of sites (i.e. objects) in the Euclidean plane.
Definition 1. Let O be a set of sites in the Euclidean plane. For
each site o of O, the Voronoi cell V (0) of o is the set of points
that are closer to o than to other sites of O. The Voronoi diagram
V (O) is the space partition induced by Voronoi cells.
Then let us introduce the definition of the Delaunay triangulation
of a set of sites (or objects) in the Euclidean plane.
Definition 2. The Delaunay triangulation of O is the geometric
dual of the Voronoi diagram of O: two sites of O are linked by
an edge in the Delaunay triangulation if and only if their cells are
incident in the Voronoi diagram of O.
3 SKELETONS FROM VORONOI DIAGRAMS
A very illustrative definition of the skeleton is given by the prairie-
fire analogy: the boundary of an object is set on fire and the skele-
ton is the loci where the fire fronts meet and quench each other.
Imagine a fire along all edges of the polygon, burning inward
at a constant speed. The skeleton (Skiena, 1997) is marked by
all points where two or more fires meet. This operation is also
called the medial-axis transformation and is useful in thinning a
polygon, or, as is sometimes called, finding its skeleton (Skiena,
1997). Another approach to compute skeletons is based on the
Voronoi diagram. The medial-axis transform of a polygon P is
simply the portion of the line-segment Voronoi diagram that lies
within 7.
The simplest and most readily implementable thinning algorithm
(Skiena, 1997) starts at each vertex of the polygon and grows
the skeleton inward with an edge bisecting the angle between the
two neighboring edges. Eventually, these two edges meet at an
internal vertex, a point equally far from three line segments. One
of the three is now enclosed within a cell, while a bisector of
the two surviving segments grows out from the internal vertex.
This process repeats until all edges terminate in vertices (Skiena,
1997). The Voronoi diagram of a discrete set of points (called
generating points) is the partition of the given space into cells so
that each cell contains exactly one generating point and it is the
locus of all points which are nearer to this generating point than
to other generating points.
Each polygon formed by edges of the map has sample points near
its boundary. If the density of the boundary points (as generat-
ing points) goes to infinity then the boundary of the union of all
the Voronoi zones belonging to points of the same polygon con-
verges to that polygon. The boundaries between Voronoi zones
belonging to points of different polygons converges towards the
skeleton of the objects in the polygon. This property is impor-
tant in designing the algorithms for sampling the map features on
the scanned maps. In the next section we will present the edge
detection algorithms that we used for sampling the images.
4 EDGE DETECTION IN SCANNED MAPS
ensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
are built are: the derivative in the direction of the gradient, the
Laplacian, the directional derivatives and the statistical differenc-
ing.
We select the data points where the variation of the intensity is
the highest i.e. at the edges. In order to get sample points around
the high frequency changes in the image we use two edge detec-
tion algorithms based on the Laplacian and one edge detection
algorithm based on the derivative in the direction of the gradient.
The gradient is the first order differential of the interpolant at the
point. The derivative in the direction of the gradient gives the
highest variation of the interpolant (in our case the level of grey)
at the point. This derivative in the direction of the gradient equals
to the highest magnitude of the derivative. i.e. the square root of
the sum of the squares of the derivatives in any pair of orthogonal
1
x 215
directions, e.g. |n" + (557 . This is a well behaved
function used in image sharpening and edge detection. In the
gradient based sampling that we used, we took the square root of
the sum of the square ofthe difference between the row above and
the row below the pixel, and the square of the difference between
the strip on the left and right of the pixel.
The Laplacian (v* zr D
5:2 y? ) is proportional to the varia-
tion of the derivative of the interpolant at the point with respect to
an annulus centered at the point. We used two different computa-
tions for the Laplacian, the standard Laplacian, and an alternative
Laplacian where the “annulus” is composed of eight pixels in-
stead of four. In this alternative Laplacian, a = actor is used to
compensate for the wider diagonal pixel separation. These two
Laplacian based sampling techniques are the other two sampling
techniques we used in our experimentation.
Figure 1: Annulus of 4 pixels
Figure 2: Annulus of 8 pixels
The sampling consists in selecting all the pixels whose derivative
operator value is bigger than some threshold. After the image is
irregularly sampled, the Voronoi diagram (and its dual graph: the
regularly for
:sent the nat-
5. we present
There are a wide variety of edge detection algorithms that exists,
but the set of basic tools on which most of the general algorithms
1179
