iants. The most common correspondences are points,
curves and surfaces.
In some situations, coarse registration techniques can be
classified on shape features or matching metho ds. The first
group searches for characteristics of points, using usually
neighborhood information, in order to search for corre-
spondences. Examples of this group are Point Signature,
Spin Image, etc. Matching methods are based on the pro-
cess of matching points from both surfaces, as Ransac or
Genetic Algorithm. In some situations both techniques
can be combined to find correspondences, as Brunnstro
¨
m
[13], who used the normal vectors at every point to define
the fitness function of the genetic algorithm. On the other
hand, techniques of both groups can be used independently
as Ransac which do not use features in the matching pro-
cess or Point Signature that when points are characterized
only a comparison between features from both surfaces is
required to detect correspondences.
3.1. Point signature
Point signature is a point descriptor introduced by Chua
[9] and used to search for correspondences. Given a point
p, the curve of the surface that intersects with a sphere of
radius r centered to p gives the contour of points (C). These
points are then represented in a new coordinate frame cen-
tered at p. The orientation axes are given by the normal
vector (n
1
)atp, a reference vector (n
2
) and the vector
obtained by the cross-product. All points on C are project-
ed to the tangent plane giving a curve C
0
. The vector n
2
is
computed as the unit vector from p to a point on C
0
which
gives the largest dist ance. Thus, every point on C can be
characterized by: (a) the signed distance between its own
correspondence in C
0
; and (b) a clockwise rotation angle
h from the reference vector n
2
. Depending on the resolu-
tion, different Dhs are chosen. Then, the point signature
can be e xpressed as a set of distances in each h from 0
to 360. Finally point signatures from two views are com-
pared to determine potential correspondences. The match-
ing process is very fast and efficient.
The main drawback of the algorithm is the process to
compute the point signature. The intersection of a sphere
to the surface is not very easy, especially when the surface
is represented as a cloud of points or a triangulated surface.
In this situation interpolation is required, incrementing the
computing time and decrementing the quality of the point
signature. Moreover the computation of the reference vec-
tor is very sensible to noise, and errors in this computation
effects the point signature descri ptor obtained considerably.
3.2. Spin image
Spin image is a 2D image characterization of a point
belonging to a surface [14]. Like point signature, spin
image was initially proposed for image recognition. How-
ever, it has been used in several registration applications
since then.
Consider a given point at which a tangent plane is com-
puted by using the position of its neighboring points. Then,
a region around the given point is considered in which two
distances are computed to determine the spin image: (a) the
distance a between each point to the normal vector defined
by the tangent plane; (b) the distance b between this point
to the tangent plane; obtaining:
a ¼
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
kx pk
2
ðnðx pÞÞ
2
q
ð1Þ
b ¼ nðx pÞð2Þ
where p is the given point, n is the normal vector at this
point, and x is the set of neighboring points used to gener-
ate the spin image. Using these distances, a table is gener-
ated representing a on the x-axis and b on the y-axis. Each
cell of this table contains the number of points that belong
to the corresponding region. In order to choose the size of
the table that determines the resolution of the image, the
double length of the triangle mesh is selected.
Some spin images are computed in the first view and
then, for each one, the best corresponden ces are searched
for in the second view. When the point-correspondences
are found, outliers are removed by using the mean and
the standard deviation of the residual as a threshold. The
rigid transformation is finally computed from the best cor-
respondence found.
The main problem of this method is that the spin image
strongly depends on the resolution of the method. In order
to solve this problem, Carmichael et al. [15] propo sed the
face-based spin image in which a set of points are interpo-
lated inside every triangular mesh with the aim of uniform-
ing the number of points in every spin image computation.
In addition, other approaches have been presented to solve
the problem of false mesh triangles given by surface bound-
aries and occlusions [16]. In this case, the method is used as
a filter to remove such false triangles before registration.
Finally, using the variants of spin image, good results
can be found in Range Image Registration. The spin image
feature is very robust, except in case of symmetries or
repeated regions in the object. However this is a problem
present in most part of coarse regis tration techniques.
3.3. Principal component analysis
This method is based on using the direction of the main
axis of the volume given by the cloud of points of the range
image to align the sequence of range images between them.
If the overla pping region is large enough, both main axes
should be almost coincident and related to a rigid motio n
so that registra tion may succeed. Therefore, this transfor-
mation matrix is found to be the one that aligns both axes
by only applying a simple product (see Eq. (5)). This
method is very fast with respect to others that identify
point or curve correspondences. However, the overlapping
region must be a very important part of the view in order to
obtain good results. Chung and Lee [17] proposed a regis-
tration algorithm using the direction vectors of a cloud of
J. Salvi et al. / Image and Vision Computing 25 (2007) 578–596 581