AN ALGORITHM FOR CENTRELINE EXTRACTION USING NATURAL NEIGHBOUR
INTERPOLATION
Darka Mioc 4, Francois Anton b and Girija Dharmaraj à
Department of Geomatics Engineering
University of Calgary
2500 University Drive NW, Calgary, AB, Canada, T2N 1N4
mioc(@geomatics.ucalgary.ca, gdharmar@ucalgary.ca
bDepartment of Computer Science
University of Calgary
2500 University Drive NW, Calgary, AB, Canada, T2N 1N4
antonf@cpsc.ucalgary.ca
KEY WORDS: acquisition, GIS, integration, extraction, automation, triangulation, digitisation
ABSTRACT
Data caption and conversion are two of the most costly operations of
spatial data acquisition. They can represent up to 80 percent of the tot
and costly operation, especially due to the lack of expli
the batch processing of the whole map. Currently, comi
simple scanned black and white maps. Various comme
of the pixels forming the line, but these approaches have shown diff
extraction in raster/vector conversion systems is based on
settings, what causes difficulties in the extraction of com
and complex intersections of linear features. The approach we
basic spatial features from raster data. These spatial features can be use
iis research is the definition of deterministic topological rules and algorithms
. These spatial features can then be represented in different spatial
data structure - the Voronoi diagram. The novel part of tl
for extracting the spatial features from the Voronoi data structure
data structures that can be implemented in
data structures for integrated raster/vector models le
a software toolkit for automated raster/vector conversion.
using natural neighbour interpolation. In this paper we presen
the skeleton extracted from the map features can approxin
Voronoi cells, for the extraction of complex spatial features.
data acquisition reducing significan
1 INTRODUCTION
In this paper we present an algorithm for raster to vector con-
version of scanned maps using skeletonisation from Voronoi dia-
gram. This involves sampling the scanned map irregularly using
edge detection algorithms and then applying the natural neigh-
bour interpolation. Since we are considering a scanned map in
grayscale, the interpolant is the level of grey.
In spatial interpolation, local techniques have been used in or-
der to get an interpolation continuous at data points, and smooth
around data points. In these local techniques, the data points
which influence the interpolant are the ones neighbouring the
given interpolation point. The interpolation is thus based on the
definition of adjacency or of neighbourliness. In ID, the neigh-
s given by the natural topology of the real line, in-
al order. In 2D, there is no such relationship, and
d by some topological struc-
ation, that
bourliness i
duced by its tot
the neighbourliness can be define
ture. Such structures include the Delaunay triangul
is the dual of the Voronoi diagram. The Delaunay triangulation
in linear interpolation (which corre-
e triangle or Barlett filter (Foley et
que is the natural neighbour in-
has been extensively used
sponds to convoluting with th
al.. 1996)). Another local techni
terpolation (Sibson, 1981) based on local coordinates.
These local coordinates were
plex spatial features, for e
use here is based on image processing filtering techniques to extract the
a GIS. In this research we
ading to the improvement of d
The approach is based on computing the skeleton f
t the algorithm for ske
aate the centreline of the map object. We apply this algorithm directly on the
This research can lead to the improvement of current practices in spatial
introduced by Sibson (Sibson, 1980).
any GIS, in terms of computer time and manual work needed for
al implementation costs. Manual digitising is a very error prone
cit topology in commercial GIS systems. Indeed, each map update might require
nercial GIS do not offer completely automatic raster/vector conversion even for
rcial raster/vector conversion products exist for the skeleto
iculties with the extraction of good topology. The spatial feature
line tracing algorithms. In order to operate they need user defined tolerances
nisation or thinning
xample: road junctions, curved or irregular lines
d for the reconstruction of the image within the topological
use the topological approach to develop new algorithms and
ata caption and conversion in GIS and to develop
rom Voronoi diagrams
leton extraction from scanned maps. We show that
tly the cost and amount of work needed.
Local coordinates based on the Voronoi diagram are used in natu-
ral neighbour interpolation (also studied in (Gold, 1994) as “stolen
area” interpolation), to quantify the “neighbourliness” of data
sites. The properties of these local coordinates have been exten-
sively studied by Sibson (Sibson, 1980) and Piper (Piper, 1993),
who gave a formula for the gradient of the volume stolen from
neighbouring Voronoi regions due to the insertion of a query point,
obtained from two directional derivatives. The natural neighbour
or stolen area interpolation technique has been extended from or-
dinary Voronoi diagrams to Voronoi diagrams for sets of points
and line segments in (Anton et al., 1998). Anton et al. (Anton et
al.. 1998) extended the results presented in Gold and Roos (Gold
and Roos, 1994), by providing direct vectorial formulas for the
first order and second order derivatives for the stolen area. The
analysis presented in (Anton et al., 1998) generalises the analysis
of Piper (Piper, 1993) based on the formalism of partial deriva-
tives, to the formalism of derivatives of a function on a normed
space.
roduce the concept of Voronoi diagrams ofa
In section 2, we int
ationship between the
set of points. In section 3 we present the rel
skeleton and the Voronoi diagram. In section 4 we present three
different techniques to sample the scanned map irregularly for
. [n section 5, we present the nat-
detecting the edges in the map
esent
ural neighbour interpolation technique. In section 6, we pr
1178
—— --
ing
the
ver
bel
ske
tan
the
det
The
but
