and surface normal noise. Thus, in order to reduce the number
of correspondences candidates, filtering and grouping strategies
are applied. In the first method the similarity measure is used to
remove unlikely correspondences. Namely, a threshold value is
set to 1/3 of the maximum value of the similarity measure of the
list of correspondences. Then, all correspondences having a
similarity measure less than the threshold are filtered out. The
second method is based on geometric consistency. In this case,
remaining correspondences are grouped together according to a
geometrical constrain, represented by the euclidean distance
between point correpondences on the same view, as specified
below:
I = Zell - dis D,;. (3)
where Dmin denotes the mesh resolution. In order to achieve a
better estimate of rototranslation parameters, the correspon-
dences of a group should be uniform distributed on the common
area of object surface. Furthermore, very spatially close point
correspondences (p; or qj) should not fall in the same group, in
order to reduce the influence of data noise on transformation
estimate. A solution of these issues is achieved using a modified
version of euclidean distance (3), which is evaluated as follows:
d, —d.| if d, »4R and d, »AR
diff (c,,c,) - | | mad (4)
OR otherwise
where now the mesh resolution is denoted by R. In this way,
point correspondences closer than 4 times the resolution are
considered not consistent, and therefore they are not grouped
together. Through the grouping algorithm a set of lists,
descently ordered according to the similarity measures, are
generated. Next, for each created group a least square estimate
of rototranslation parameters is computed. Since large groups
of correspondences will lead to a better estimate of the transfor-
mation between view pairs, in current implementation of such
algorithm only groups with at least five elements are taken into
account. Results of filtering and grouping strategies are
displayed in figure 5, where incorrect correspondences of figure
4 are eliminated and a group of 12 well separated and uniform
distributed correspondences are depicted. As a result, from 93
correspondences which passed the filtering step, only 7 groups
were obtained with grouping method, drastically reducing the
number of possible transformation to be estimated.
I
©
40
20
-20
Figure 5: filtered and grouped correspondences of fig. 4
4. DETERMINATION OF THE OVERLAPPING AREA
Once a set of correspondences are determined and grouped,
rototranslation parameters can be calculated for each group.
However, in order to estimate the optimal transformation a
refinement of the registration has to be applied. This can be
achieved using registration methods such ICP [ ] or the
Frequency Domain algorithm [ ]. Both methods work on
common areas rather than on a set of matching points, therefore
the problem arises to determine such areas on the ground of
point correspondences computed through spin-images. In
current section a method to solve for this problem is presented.
À first rough determination of the common area between view
pair can be performed through the least square estimate of the
transformation which minimizes the residual distances
according to following relationship:
Er => Ip: — T(a)ll? = 3 ll; — (Ra - £)]P (5)
fi
Where p; and q; are point correpondences of a generic group
G = {[p.qil, [P2:].---[Pn:4n]}. The rotation matrix R and
traslational vector t can be estimated using quaternion represen-
tation, as proposed by Horn [5]. As result of this approach, a
minimum for each group is computed, and normalizing by the
number of group elements, the average distance between two
corresponding vertices of the same group can be obtained.
Although a logical choice for the optimal transformation would
be the rototranslation providing the minimum average distance,
this criterion presents following disadvantage: groups with a
few correspondences could provide an average distance lower
than the one associated with larger groups. Therefore one could
compute a set of transformation parameters using a low number
of correspondences, resulting in a less accurate estimate.
Figure 6 shows the result of application of Horn method.
Figure 6: approximate alignement of two views with Horn
A more efficient method has been therefore implemented. For
each group, the two meshes are registered through the transfor-
mation parameters calculated by Horn method. Next, for each
point of mesh A the closest point of mesh B is determined. If
the distance is less than 1.5 times the mesh resolution, then
selected point is most likely belonging to the common area.
This criterion allows to easily compute an overlapping zone for
each point correpondences group. The optimal transformation is
associated with the wider common area.
—318—
