2004
dy,
ints i
ssible
scale
]ence
ssary
case,
ssible
id R,,
d, the
ubset
| with
rs are
let of
ously
rison,
ssible
is not
f sdk
ists.
ond to
| fails,
rocess
us 1 />
gle, is
owing
nce is
[ready
cone,
where
cation
A,
cernel:
all the
yrithm,
This
t of a
r one,
set of
jective
ind out
otropic
satisfy
ng the
sidered
is the
e basic
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
Referring to the notation previously introduced, the solution
proposed by Umeyama (1991) is now explained. In the case in
which the rank of K,, is equal to k, it follows:
R=USV" (7)
t=m, —sRm, (8)
s -lm(Ds) (9)
n
if the rank of K,, is equal to k-1, the elements of matrix S in the
SVD of R are the following:
I if det(U)det(V) 21
diag(1,1,...1,-1) X ifdet(U)det(V) «-1
The basic triangle will be therefore rotated, translated and
scaled, according to the rules of the Procrustes analysis, to fit in
the best way the kernel of possible correspondence. The
application of the just mentioned transformation parameters to
the entire configuration, allows, with good approximation, the
insertion of this configuration in the datum of the enclosing
configuration.
Once the two geometrical entities are represented in the same
reference system, the solution of the residual correspondences is
obtained by a simple comparison of the mutual distances. The
nearest point B to a fixed vertex of A (expressed in the new
coordinate system) will be its probable correspondent.
By solving all the residual correspondences, one possible
complete image of the enclosed configuration A in the
enclosing B, can be identified.
The final solution is defined, also in this case, by a test of shape.
For each possible image previously identified, the value of the
Procrustean shape parameter & is determined, assuming as
reference the enclosed configuration. The most probable image
will be that one corresponding to the lowest value of c.
3. CONCLUSIONS
In this paper we have illustrated a novel procedure to
automatically identify correspondences between geometrical
entities missing of topological structure. The method is based
only on the knowledge of the vertices coordinates describing the
geometrical entities considered, referred to their own and
different Cartesian reference systems.
The entire process is developed without the necessity that the
points are acquired or defined according to a prefixed order, and
without requirements about structural or topological
information, relative to the links among such a vertices. The
recognition of the homologous points of two correspondent
configurations of the same geometrical entity is solved,
independently for the coordinate systems assumed, and for the
reciprocal scale rate.
For the inclusion problem solution, the methodology is able to
identify a geometrical configuration completely contained
within another one, more general, also in the case in which the
approximate knowledge of the reciprocal scale factor is not
available.
Further developments of the proposed method will consider the
case of partial inclusion, that is the identification of the subset
of common points belonging to two different configurations.
Finally, a research field will be the identification of shape
07
parameters alternative to that employed, and the introduction of
methods and principles of the fuzzy logic.
AKNOWLEDGMENTS
This work was carried out within the research activities
supported by the INTERREG IIIA Italy-Slovenia 2003-2006
project "Cadastral map updating and regional technical map
integration for the Geographical Information Systems of thc
regional agencies by testing advanced and innovative survey
techniques"
REFERENCES
Amit, Y., Kong, A., 1996. Graphical templates for model
registration. /EEE Transactions on Pattern Analysis and
Machine Intelligence, 18, pp. 225-236
Beinat, A., Crosilla. F., 2003. Generalised Procrustes
Algorithms for the Conformal Updating of a Cadastral Map. Zfv
mit Zeitschrift © fir Geoddsie, Geoinformation und
Landmanagement, 5, pp 341—349.
Beinat, A., Crosilla, F., Sossai, E. 2003. Ricerca automatica di
corrispondenze fra entità gcometriche di una cartografia
catastale. Atti della 7a Conferenza Nazionale ASITA, Verona,
28-21/11, pp. 241—246.
Beinat, A., Crosilla, F., Sossai, E., 2004. Riconoscimento
automatico di entità geometriche non strutturate di una
cartografia catastale. Bollettino della SIFET, (in printing).
Cross, A.D.J., Hancock, E.R., 1988. Graph matching with a
dual-step EM algorithm. [EEE Trans. on Pattern Analvsis and
Machine Intelligence, 20(11), pp. 1236-1253.
Luo, B., Hancock, E., 2002. Iterative Procrustes alignment with
the EM algorithm. Image and Vision Computing, 20, pp. 377—
396.
Morgera, S.D., Cheong, P.I..C., 1995. Rigid-body constrained
noisy point pattern-matching. /EEE Transactions on Image
Processing, 4(5), pp. 630-641.
Papadimitriou, C. H., Steiglitz, K., 1982. Combinatorial
optimisation | algorithm | and | complexity, Prentice-Hall,
Englewood Cliffs, NJ.
Scott, G.L., Longuet-Higgins, H.C., 1991. An algorithm for
associating the features of 2 images. Proc. of the Roval Society
of London Series B (Biological), 244(1309), pp. 21-26
Shapiro, L.S., Brady, J.M., 1992. Feature-based correspondence
- an eigenvector approach. /mage and Vision Computing, 10,
pp. 283-288.
Sossai, E., 2003. Ricerca automatica di corrispondenze fra
entità geometriche di una cartografia catastale. Degree Thesis.
Faculty of Engineering. University of Udine. Academic Year
2002-2003.
Umeyama, S., 1988. An eigendecomposition approach to
weighted graph matching problems. [EEE Transactions on
Paitern Analysis and Machine Intelligence, 10, pp. 695-703.
Umeyama, S., 1991. Least squares estimation of transformation
parameters between two point sets. /EEE Transactions on
Pattern Analysis and Machine Intelligence, 13(4), pp. 376-380.
Umeyama, S., 1993. Parameterised point pattern matching and
its application to recognition of object families. /EEE
Transactions on Pattern Analysis and Machine Intelligence, 15,
pp. 136—144.
Ullman, S., 1979. The Interpretation of Visual Motion. MIT
Press, Cambridge, MA.
Cs ae a a SE
Sh LS Er Ne
aS a
x rae
ui
!
i
=
i iat
E
à
LUNES
