AUTOMATIC POINT MATCHING OF GIS GEOMETRIC FIGURES
A. Beinat, F. Crosilla, E. Sossai
Dept. of Georesources and Territory, University of Udine, Via Cotonificio 114, 1-33100 Udine (Italy)
Tel. ++39 0432 558702 Fax ++39 0432 558700 - (beinat, crosilla, sossai)@dgt.uniud.it
KEY WORDS: Cartography, GIS, CAD, Automation, Identification, Databases
ABSTRACT:
GIS and digital mapping operations frequently require the automatic comparison and superimposition of geometric figures
represented by sets of vertex coordinates supported by structural and topological information. When the configurations are not
structured, that is the only vertex coordinates of the figures are available, manual intervention is needed in order to establish
correspondences among the different geometries.
To overcome this limitation, an automatic method has been developed to detect the correspondences between two or more equivalent
sets of unlabeled points, representing n-dimensional geometric figures. The proposed technique performs a geometrical analysis of
the adjacency matrices of the point configurations, in order to identify, for each one, the vertex of maximal asymmetry. A pairwise
comparison of the sorted components of the adjacency matrix relative to these vertices, leads to the identification of the point
correspondences. A directly-computed Procrustes conformal transformation is then applied to the geometric figures in order to
achieve their optimal alignment.
Also in case of geometric entities included into another, the problem solution starts trying to find some minimal asymmetric sub-
configurations (kernels) that arc similar in both figures. A Procrustes superimposition of these corresponding kernels is then applied,
and extended to the remaining points of the included configuration. A shape test is finally executed in order to identify the best
solution. Specific geometric rules and filters are implemented to optimise the computation process.
The method has been successfully tested on cadastral cartographic matching problems. In addition, it is suitable for a wider range of
possible applications, like CAD/CAM, computer vision and reverse engineering.
1. INTRODUCTION Therefore. when such a kind of information is not available, or
is incompatible, it is only possible to assume the fundamental
Most of the GIS tools used to handle a digital map, and many geometrical information, i.e. the coordinates of the composing
CAD/CAM applications, are not currently provided of specific points that graphically define the involved geometrical
functions able to automatically identify the geometrical configurations.
correspondence between a specific geometrical figure, and that Problems of this type have already attracted the attention of
part of a more general drawing containing it. This is not true researchers mainly working in the field of the computer
just for the cases in which the reference data files are graphics. One fundamental contribution to the problem solution
appropriately structured. is due to Ullman (1979), who recognised the importance of
Problems of this kind often arise in digital mapping and in GIS, using the stiffness of the existing constraints between two
where, given a cartographic element, for instance a cadastral vertices, with the aim of identifying the correspondence among
parcel, the problem is to automatically recognize it within a point sets. Later, many authors, being inspired by Ullman's
general map. An analogous case is given by the automatic work, developed algorithms, using the weighed proximity
research of a predefined structural or mechanical component matrix as a function of the computed distance lengths among the
unit within some CAD/CAM files containing the entire points. In particular, Scott and Longuett-Higgins (1991) have
structure or mechanism. determined the correspondence by the spectral decomposition of
[n particular cases, the solution of these problems is possible the proximity matrix relative to point configurations under
through the a priori definition of some topological relationships study. Shapiro and Brady (1992) reached the objective through
among the object points, or from the availability of structural the comparison of the modal structures deduced from each
information, explanatory of how the points are mutually proximity matrix referred, this time, to a single configuration.
connected in order to represent specific shapes. It is established, Finally Umeyama (1988) came up with the definition. of
for instance, that a collection of points, properly ordered and correspondence using the spectral decomposition of the
joined according to a certain rule, define a cadastral parcel, and adjacency matrices relative to weighed graphs of equal measure.
the comparison between the specific structured dataset and the The same author has later reconsidered (1993) these ideas,
cadastral map is carried out. In this case, the map is considered applying them for the solution of the matching problems among
like a cluster of unit parcels defined by a proper series of points complex objects.
organized in a topologically compatible manner. More recently many authors have tried to model the structural
To structure the data archives in such a way, it requires a heavy deformations of point sets. In this regard, Amit and Kong
and time spending manipulation, however not sufficient to solve (1996) have used the graph theory to model the deformations of
the problems of identification and automatic comparison in the 2-D shapes contained in some medical images. Finally, other
various ways in which they occur. It is impossible, for instance, authors have formalised the concept of correspondence by using
to compare a new object with the existing archive, if the the links of a rigid body: we mention the work done by Morgera
topology of the new object is unknown, undefined, or and Cheong (1995). Cross and Hancock (1988) proposed
instead, for the correspondence problem solution, a statistical
incompatible.
methodology based on the theorem of Bayes. Afterwards Luo
92
Inte
and
Pro
bet
An
and
pro
ider
of ]
gen
Case
met
solu
The
reco
num
com
accc
put
repri
corr
thos
entir
kno
in tl
proc
acqu
with
infor
conn
The
acco
proci
two
entit
assul
the s
mear
geon
one,
whic
nota
For |
main
math
softw
2.1.
The
confi;
entiti
GIS a
- the
point:
- the |
confi;
These
geom
not re
factor
procei
config
topolc
