n of features or
ed Tomography
urfaces through
se 3D data are
el of the whole
ry step of this
ion of 3D data,
1 be carried out
late representa-
rk, the surface
e collected 3D
surface point is
ncodes global
nate reference
etween surface
itching. In this
ller and easier
omputed using
. exploiting the
his aim, object
re its vertices
|Ween vertices
Ct surface is
he concept of
defined as the
d the surface
all the object
linate system
x= p))
(1)
? through the
listance to the
n (Fig. 1).
"sid
mal
e object will
her than the
consider the
nple points.
h is able to
ution of 3D
D space (a,
imulates the
] histogram
ution (Fig.
ecording on
nts of a 3D
surface. By way of spin images one may associate a collection
of images to a 3D surface mesh, as every point of the surface
can generate a spin-image. Two surfaces representing the same
object from different view-points will be associated to two sets
of different spin images: corresponding points in the common
region between two 3D images will have similar spin-images
(not identical, due to noise and discretization effects) because
spin-images exclusively depend on shape’s characteristics. The
problem of determining the common region between two 3D
images in this way can be turned into the recognition of the
most similar images of two image sets, a well studied problem
for which a number of techniques are available.
—
Figure 3: example of spin-image of a point of the amphora
3. THE MATCHING ALGORITHM
In presented work surface matching is achieved by matching
oriented points using spin-images. Spin-images from points on
one surface are compared to spin-images from points on another
surface; when two spin-images are similar, a point correspon-
dence between the surfaces is established. This approach requi-
res therefore to define a way of ranking matches between spin-
images. To this aim a similarity measure has been developed,
which is based on the computation of a linear correlation
coefficient:
C(P,0)=(atamb(R(P,0)}* ~ A) @)
In this formula, N represents the number of overlapping pixels
used in the computation of correlation coeficient R, then it takes
into account the effect of the size of the overlapping area, while
A is a weight term, discriminating the point at which the overlay
becomes important for comparison of spin-images. Through the
factor N, spin-images having a reduced common area will
provide a low similarity measure, even in presence of an high
correlation between them, avoiding in this way the use of less
meaningful correspondences. The assumption of linear correla-
tion can be justified noting that two spin-images from proximal
points on the surface of two different views of the same object
will be linearly related because the number of points that fall in
corresponding bins will be similar (provided that the two surfa-
ces have the same point distribution). Therefore, established a
way to comparing and ranking spin-images pairs based on simi-
larity measure, an algorithm for determination of point
correspondences between oriented points on partially overlap-
ping view pairs, can be implemented.
Firstly, spin-images are generated for all surface points of one
mesh (A). Next, for each point of a subset of surface points of
the second mesh (B), the corresponding spin-image is compu-
ted. Each of these spin-images is correlated with all the images
of mesh A and the similarity measure for each image pair is
calculated. Resulting values are stored in a histogram, in which
possible upper outliers are searched for, because they represent
plausible point correspondences between their associated
oriented points. The end result of this procedure, repeated for
each point of subset of mesh B, is represented by a list of
possible correpondences between points of the two meshes.
Figure 4 shows the correspondences detected on the surface of a
little statue for two spin-images. The number and the way the
point subset of mesh B are selected, affects play a prominent
role for the global effectiveness and performance of the
algorithm. The better approach would involve the selection of a
limited number of points belonging to the overlapping area
between the meshes.
20 0 -20 40 80 80 100
Figure 4: detected correspondences btw 2 spin-images
Since no a priori information is available about this zone, the
points are randomly choosen. Anyway, on the ground of several
test, in the current implementation of the algorithm the number
of these points is set to 1/20 of the total amount of the vertices
of mesh B.
In order to compute an initial estimate of rototranslation
parameters between two partially overlapping views, at least
three point correspondences need to be established. Spin-image
matching drastically reduces the number of possible point corre-
spondences by associating only view points that have similar
spin-images. However, the implemented algorithm still finds
multiple correspondences. The evaluation of all combinations of
three point correspondences for estimating a plausible view
transformation would lead to a combinatoric explosion. Further-
more, some detected correpondences are incorrect and must be
eliminated from the list. The source of these errors concern with
simmetry in the data, too much spatially close surface points
-317-
