International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol XXXV, Part B4. Istanbul 2004
- the correspondence problem solution valid for an entire
enclosed configuration, must also be appropriate for every
partial configuration of it.
It is therefore valid and correct to devote the attention, not to the
entire enclosed configuration, but to a particular and
characteristic minimal subset of it, constituted by three vertices,
called “basic triangle“ or also “correspondence kernel”.
Once such a triangle in the enclosed configuration is identified,
its images within the enclosing configuration have to be looked
for. To do so, the basic triangle is overlapped to cach image by
a Procrustean similarity transformation, and the condition that
every point of the remaining configuration A has a
correspondent one in the configuration B is verified. The final
solution is that one furnishing the best geometrical fit, and the
correct correspondence for all the points of A.
This procedure is described in the following (see for more
details: Sossai, 2003; Beinat, Crosilla & Sossai, 2004).
2.2.2 Construction of the basic triangle: The process starts
finding out, within the enclosed configuration A, the two
vertices separated by the largest distance. Let us call | and 2
these points, name a the segment 1-2, and d, its length. One of
the points, for instance point 2, it is assumed as the reference .
The third vertex is chosen, among the remaining points, as the
closest point to the reference. Called v the possible candidate,
the distances d,, e d,;, between v and the already defined points
| and 2, arc calculated. In order that v can be considered the
third vertex of the basic triangle, the following conditions must
be verified:
- [da - dol - dial = Ao;
- da -d3lz A [de — del 2 Ars 1d; - dal z As
The symbols A, e A, are threshold values proportional to the
required tolerances. The first condition aims to avoid that the
basic triangle be degenerate, for instance too flat. The second
condition guarantees that the basic triangle is not characterised
by symmetrical axes, that is, neither isosceles, nor equilateral.
These constraints arc chosen in order to define one
configuration able to minimise the ambiguity and the possibility
of errors, both in the phase of identification that during the
solution of the correspondences.
Let us call point 3 such a vertex and name with 5 the segment 1-
. with c the segment 2-3 (the shortest) and with d; e d. their
respective lengths. The configuration 1-2-3, so determined,
represents the basic triangle.
Since we are using coordinate values affected by errors, a
variability interval of the distances between the vertices must be
considered. For this reason the lengths of the sides d,, d; and d.
of the original triangle are substituted by the variability intervals
so defined:
A
3
R, 7 [d,-t; d.t] (6)
R, = [d.-t; d+]
where t is the tolerance parameter, that can be fixed or
proportional to the distance di. If the scale factor s in known,
the procedure defines also the rounded value R, — [d,-t; d,*t].
As a last thing, a shape parameter 8^ is computed, whose value
is proportional to the square mean of the tolerances computed
for the centroid distances of the correspondence kernel.
2.2.3 Images of the basic triangle: Once the basic triangle and
its admitted interval of variability are fixed, its possible images
in B are looked for. This generates a set of point triplets of
possible correspondence.
For the most general conditions, one triplet of possible
correspondence is a general subset of three vertices [i, /, k] of B
not degenerate, characterised by the fact that d; « dà « d,
where the symbols identify the distances between the points
and j, j and k. k and i, respectively.
For the definition of the point triplets: of possible
correspondences two alternatives can be present. If the scale
factor s is unknown, all the triplets of possible correspondence
will belong to the above mentioned set, and it will be necessary
to proceed with a combinatorial approach. In the opposite case,
if the scale factor is known, just the triplets of possible
correspondence, such that s-dy; is contained within the round R,,
will belong to the set. Once this particular set is constructed, the
attention moves to individuate, within the same set, the subset
of the kernels of possible correspondence.
The kernels for which exists a relationship of comparison with
the basic triangle, will belong to this set, while all the others are
excluded. Let us consider, for example, a generic triplet of
points [i, j, Æ] (note that the meaning of the symbols previously
introduced remain valid). It follows a geometric comparison,
based on the distances, between the triplet of points of possible
correspondence and the basic triangle. If the scale factor s is not
known, this will be estimated as a/d;;.
For d; 7 d, (case 1) it is:
segment i-/ — possible image of the segment c;
segment j-k = possible image of the segment 5;
segment k-i = possible image of the segment a.
In this case, if s-d, belongs to the round value R. and if sd;
belongs to the round value Ry, a relation of comparison exists.
For d, « d, (case 2), i-/ and j-k are swapped, so to correspond to
possible images of 5 and c respectively. If the comparison fails,
the examined triplet of points will be rejected, and the process
passes to examine the successive.
[n the comparison test, the correspondence among the points i, J,
k of the triplet, and the vertices 1, 2, 3 of the basic triangle, is
immediately defined. They remain valid, in fact, the following
results:
inthecase 1,i=2;j=3:k=1;
in the case 2: k= 1;/s3 i2.
The identification of a kernel of possible correspondence is
completed with the execution of the test of shape, already
introduced in the previous chapter. If also this test is overcome,
it follows the expansion of the kernel by the solution, where
possible, of the residual correspondences till the identification
of a possible complete image of the enclosed con figuration.
2.2.4 The expansion of the correspondence kernel:
During this phase, the basic triangle is overlapped to all the
selected correspondence kernels, by an appropriate algorithm,
obtained from the orthogonal Procrustes analysis. This
technique allows to obtain the mutual least squares fit of a
moving matrix configuration with respect to another one,
considered as a reference, by means of a proper set of
transformation parameters, so to satisfy a prefixed objective
function.
[n detail, the Procrustes algorithm makes it possible to find out
the rotation matrix R, the translation vector t, and the isotropic
deformation s, to apply to thé moving configuration, to satisfy
the minimum to the distance square mean £^ among the
correspondent points belonging to the two considered
configurations (see e.g. Beinat & Crosilla, 20032).
Let:
Y z {vi Ya — Ya! be the reference configuration, that is the
possible correspondence kernel;
X = (xi Xs, ., X,1 be the moving configuration, that is the basic
triangle.
96
3
SC
th
ap
in
CO
O1
ob
ne
co
By
co
en
Fo
Pr
rei
wi
