hul 2004 International Archives of the Photogrammetry, Remote Sensing
and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
In fact, assuming that v(a:) is bounded, i.e., x lies within the inte-
rior of the convex hull S, we can obtain in the same way the area
of the region v(:r) Y v(P;) (Gold and Roos, 1994).
|
|
/
/
| Thus this allows us to finally compute the variable height h(x).
| The interpolated height is in fact the weighted average of the lev-
| els of grey of the neighbouring sample points with the weights
being the areas that would be stolen to the neighbouring sampled
points.
|
6 THE ALGORITHM
Now we will present the algorithm we developed for the skeleton-
isation of sampled map features. Even though there is a similar
algorithm for skeleton extraction from scanned maps proposed by
Gold (Gold, 1999) this algorithm is treating only black and white
images. Our algorithm is different in this sense because we are
interpolating the level of grey. We call "edges" of the picture, the
boundaries of the zones where the level of grey changes contin-
uously. The edges of the picture are first detected as a subset of
| the Voronoi diagram and of the Delaunay triangulation of the set
of sampled points. The edges are detected through several crite-
| rions on the edges of the Voronoi diagram of the sampled pixels.
| The first criterion is that the difference of the levels of grey of the
| extremities of the Voronoi edge should be smaller than the differ- Figure 6: Original picture
ence of the levels of grey of the extremities of the dual Delaunay
|
|
|
|
edge. The second criterion is that the dual Delaunay edge and the
Voronoi edge (considered as line segments) intersect. The third
criterion is that the levels of grey of the extremities of the Voronoi
edge and of the dual Delaunay edge are not all the same.
The resulting subset of the Voronoi diagram is the set of all the
edges of the picture, which we call the border set. We flag the
Voronoi edges adjacent to a Voronoi edge of the border set that
do not belong to the border set.
Then from this border set, we draw the skeleton using a traver-
sal of the Voronoi zones belonging to the interior of the border
set. For each Voronoi edge e of the border set, we traverse the
Voronoi edges of the Voronoi zone that belongs to the interior of
the border set starting from the Voronoi edge following c.
We mark each one of the traversed Voronoi edges as visited. For
cach one of those Voronoi edges f that belongs to the border set
and is not adjacent to e, we draw the bisector of e and f in the
skeleton.
For each one of those Voronoi edges f that are not in the border
se and such that one of its neighbours is flagged, then the Voronoi
edge is drawn in the skeleton.
à 7 EXPERIMENTAL RESULTS e 1
| In this section we present experimental results of our algorithm
| that are applied to processing of scanned maps. The original
Scanned map is shown in Figure ; ;
| p 2 Figure 7: Delaunay triangulation
The sample points are shown in F igure
The Delaunay triangulation of the sample points is shown in Fig-
ure
The border set and the skeleton are shown in Figures
1181
