ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision‘‘, Graz, 2002 
  
positions that are almost in correct relative positions (Besl 
1992, Chen 1991, Viola 1995). Distances between corre- 
sponding points on different patches are small in that case. 
Such automatic fine registration is very important, as it is 
usually easier to manually position the 3D patches more or 
less right, than it is to perform the fine docking by hand. Of 
course, it would be nicer if also the initial, crude position- 
ing could be done by the computer, as this would render 
the whole registration automatic. Also, if the 3D patches 
are presented to the system as an unstructured set, it will in 
many cases be difficult to find out which patches would fit. 
The problem becomes a 3D puzzle. Performing also crude 
registration automatically is the very goal of the work de- 
scribed next. 
Much like with a normal, 2D puzzle the pieces can be put 
together on the basis of two complementary types of in- 
formation. On the one hand there is their shapes, which 
should match. Here, it is not a matter of outlines that 
should tally, but the 3D shapes ought to be the same for 
the part where the patches overlap. On the other hand, the 
surface may contain texture. Ifthis is captured by the struc- 
tured light system, then it may yield very effective clues as 
well. Even more so, in cases where the shape does not al- 
low to build an unambiguous reconstruction for reasons of 
symmetry, the texture may break this symmetry. 
3.2 Approach for geometry-based registration 
Assume one has to find matches between overlapping, 3D 
patches. These patches overlap only partially. A naive way 
to approach the problem would be to take any pair, and to 
search for a Euclidean motion in 3D that generates a good 
fit. This process would be prohibitively slow. 
Again, invariants have proven instrumental in the devel- 
opment of methods that achieve such crude registration 
from arbitrary, initial 3D patch positions. They use spe- 
cial points or curves on the surface, which are charac- 
terised with invariants (Feldmar 1994, Johnson 1997). A 
feature type that we have found to be particularly useful 
are bitangent curves. They are interesting, because they 
are invariant under Euclidean, affine, and even projective 
transformations. Moreover, the curve pairs can be given 
simple, invariant descriptions, especially in the case of Eu- 
clidean and affine transformations. These descriptions re- 
quire only first derivatives (Vanden Wyngaerd 1999). Bi- 
tangent curves are formed as follows. Suppose a plane 
touches the surface at two points (i.e. it is a ‘bitangent 
plane’). Now one rolls this plane over the surface so that it 
keeps in touch at two points. This yields pairs of bitangent 
curves, as illustrated in figure 10. 
For the computation of bitangent curves we construct a 
dual surface. Rothwell (Rothwell 1994) already used dual 
representations of planar curves to find pairs of bitangent 
points. In that case, the dual is a curve and a bitangent 
point pair corresponds to a self-intersection of the dual. 
Here we use a direct extension of this idea for surfaces. 
A-10 
Figure 10: Bitangent planes can roll over the surface, 
thereby describing pairs of bitangent curves. 
For every point X of the surface the tangent plane is calcu- 
lated. This tangent plane can be represented by three pa- 
rameters. These three parameters are used to create a three- 
dimensional dual point. Replacing all surface points by 
their dual results in a dual surface. Since bitangent points 
have the same tangent plane, they have the same dual point 
and the bitangent curve pairs correspond to curves of self- 
intersection of the dual surface. Figure 11 shows an exam- 
ple of such a dual surface. 
   
(a) (b) 
Figure 11: (a) An example surface. (b) View of its dual 
surface. The dual surface is constructed by replacing all 
points by their duals. As described in the text, the dual 
point of a surface point X. represents its tangent plane. 
In our approach, crude registration is carried out through 
the matching of bitangent curve pairs on the different 
patches. In order to support efficient curve matching and to 
find point correspondences between different patches, we 
use an invariant description of the bitangent curve pairs. In 
our patch registration problem, invariance under 3D rota- 
tion and translation suffices. The bitangent curves are char- 
acterized by invariant signatures, which express an invari- 
ant as a function of an invariant parameter. A problem with 
signatures of single space curves is that they may require 
higher derivatives, such as the 2nd and 3rd derivatives for 
curvature and torsion in the Euclidean case (Mokhtarian 
1997). Semi-differential invariants (Van Gool 1992) use 
lower order derivatives in more than one point. Pajdla and 
Van Gool (Pajdla 1995) used them for Euclidean registra- 
tion of space curves. In general, semi-differential invari- 
ants use fixed reference points in combination with a vary- 
ing 
is 
the 
be 
the 
val 
sli 
In! 
IS | 
ant 
bo! 
cul 
gel 
sig 
we 
pat 
fac 
gel 
an 
WI 
len 
sel 
Wl 
the 
Th 
val 
As 
Cui 
di 
are 
dif 
cle 
ing 
sex 
on 
tio 
the