After least 
resented in 
rch process 
computed. 
r to extract 
are solved 
first curve 
es to detect 
| a B-spline 
the actual 
S remain 
sformation. 
7 from each 
veen these 
basic rigid 
roduct, but 
tion. Given 
on-rational 
th the end 
(1) 
or guiding 
the curve). 
hat can be 
ently) with 
rithm (de 
ant parts of 
. Good and 
practical references to B-spline algorithms are (de Boor, 
1978), (Schumaker, 1981) and (Piegl et al., 1995). 
Following basic things need to be considered in least 
squares B-spline curve fitting problems. Given noisy 
data points (observations) solve the coefficients of a 
approximating spline curve. Curve parameter, t, is 
unknown for every observation, so usually this paramet- 
rization problem is solved first and perhaps is improved 
later if needed. Chord length parametrization is 
invariant to rigid motions. To get more information on 
parametrization see (Ma et al, 1995). Specially in 
matching problems it usually helps a lot if chosen 
parametrization is invariant to used geometric trans- 
formation (for example if affine geometric transformation 
is used then affine invariant parametrization is good 
choice). Knots divides the chosen curve parametrization 
to finite segments. The number of knots and placement 
is needed. Usually knots are chosen using heuristic 
rules, such as every n:th data point is a knot (value of a 
knot is a curve parameter value of that point). Auto- 
matic selection of number and positions of the knots see 
(Cox et al. 1988) and references there. The number of 
knots defines also the number of spline coefficients 
(number is not the same, see definitions). Also suitable 
degree of a curve should be selected. Curve parameters, 
knots and degree of a curve defines the basis functions, 
B-splines. Resulting linear least square system is sparse. 
If a fitting problem is formulated selecting for example 
chord length parametrization a result can be seen in 
figure 1 (knots have been placed to curve parameter 
value of every tenth observation, degree of the curve is 
three). Small circles are observations and line between 
a circle and the curve is a residual. As mentioned earlier 
curve parametrization can be improved, see (Guéziec et 
al., 1994), (Sarkar et al., 1991). We select optimization 
algorithm that finds minimum length between an 
observation and the curve by golden section search and 
parabolic fitting. Optimization algorithm computes the 
new curve parameter values. With the new curve 
parameters the least square problem for spline coeffi- 
cients is solved once again. This may be repeated if 
needed or solution satisfies the specified criterion, see 
figure 2. 
  
  
  
  
Figure 1 
653 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
  
  
  
  
  
Figure 2 
2. MATCHING 
The first geometric invariant used here is angle between 
three consecutive spline coefficient vectors, see figure 3 
for a third degree spline curve and figure 4 for a first 
degree spline curve. An angle can be defined for example 
clockwise from a first segment to a second segment. This 
feature is computed at every node but first and last of 
the coefficient polygon. For a closed curve, the angle can 
be computed at all nodes. In 3-D case three consecutive 
coefficient vectors form a local plane and the angle is 
defined in that plane. So the defined angles does not 
change if a rigid motion applied to the coefficient 
vectors. 
The second invariant is product of two distances com- 
puted between three consecutive coefficient vectors. 
The third feature is combination of both previously 
defined invariants, dot product of two vectors formed by 
three consecutive spline coefficients. Also absolute value 
of a vector product is rigid motion invariant but it is not 
used here. 
Three chosen invariants do not need any derivative 
information as many differential rigid motion invariants 
do. Invariant measures are computed for coefficients of 
a curve and effective area of a coefficient depends on the 
degree, n, of a curve. Effective area (or support area) of 
one coefficient is n consecutive knot segments. See 
figures 3 and 4, a curve is changing locally when one 
coefficient has moved (notice the arrow).