z' Us! i cos —sin0 2—2. 
Ez] E oet 
\Ze Az 
la (10) 
where 
v,' and vy are residuals. 
Having the observation equations, a least-squares adjust- 
ment can be conducted to solve the unknowns of S, 0, Az 
and Ay, by minimizing the summation of v2, and v2.. 
In practice, however, corresponding points between 
two lines are difficult to define, due to the differences of 
sampling density, scale and starting point. A possible so- 
lution is to model the lines with some mathematical func- 
tions and resample the lines at equally spaced points. For 
instance, one could take the Fourier descriptors to model 
each line and resample the lines at every 27/n interval, 
in which n is the number of points to be resampled for 
each line. Total number of 2n observation equations can 
be formed accordingly. Although this method is feasible, 
it seems not rigorous and efficient. First, the resampling 
space is difficult to determine. A complicated line requires 
a small sampling space, but a smaller sampling space in- 
creases computation time. Second, the computation is not 
straightforward. The lines are transformed into the fre- 
quency domain when modeling, and are transformed back 
to the spatial domain when resampling. Therefore, an idea 
of matching lines in frequency domain, matching Fourier 
descriptors, emerges to remedy these problems [Zhan and 
Roskies, 1972]. 
4.2 Matching in the Frequency Domain 
Instead of matching spatial coordinates, Fourier de- 
scriptors of each harmonic are matched in the frequency 
domain. The problem of finding corresponding points no 
longer exists. The transformation parameters can be di- 
rectly solved in the frequency domain and they naturally 
correspond to the idea of the centroid-based transforma- 
tion, so that the computation becomes efficient and useful. 
Since the Fourier descriptors of a closed line and an 
open line have different properties, the algorithms of closed- 
line matching and open-line matching are different. In gen- 
eral, open-line matching is a simplified case of the closed- 
line matching. Because a phase shift does not change the 
centroid, the translation parameters can be directly cal- 
culated for the both cases by using the following formula 
derived from Eq. (5): 
Ss (11) 
For the case of matching closed lines, each harmonic 
(except the zero one) has 4 coefficients, so that 4 observation 
equations can be constructed for each harmonic. Let ax, bs, 
cy and d, be the Fourier coefficients of a candidate line, and 
the coefficients with a prime represent the given line. If a 
similarity transformation is applied, then the observation 
equations can be derived from Eq. (9) as follows: 
472 
a Val, Ok be —Ck —dk 
A 3 Ub. ee b, —Gkr —d, Ck 
C, Ve, Ck d, ag b, 
k Vay de —cx by —an 
cos 0 cos kAt 
cos 0 sin kAt 
sin 0 cos kAt | (12) 
sin 0 sin kAt 
In Eq. (12), the parameters, S, 0 and At, are un- 
knowns, and the equations are nonlinear. Combining the 
equations of all the harmonics from 1 to a maximum har- 
monic m, we obtain an redundant system of nonlinear equa- 
tions. Least-squares adjustment can be used to solve the 
unknowns by minimizing the summation of squared residu- 
als. An iterative approach of least-squares adjustment can 
be applied to solve such nonlinear equations with the given 
approximations of the unknowns. 
For open-line matching, Eq. (12) can be simplified as 
ab cosÜ —sin0 a4 cos kAt 
[a Se. 3) 
In order to linearize the equations, we let e = S cos0 and 
f = Ssin6. In addition, the starting point is assumed to be 
at either end of the open line, so that At = 0 or x. When 
At = 0, the observation equations will be 
E] e 
When At = m, they become 
HEMBEFESEJHES 
The observation equations become linear in this case, 
so that unknowns can be solved without iteration. However, 
in order to know whether Eqs. (14) or (15) should be used, 
the parameter At should be determined in advance. The 
method to approach this will be described in section 4.4. 
The parameters S and 0 can be derived from the solution 
of e and f by using 
arctan( f/e). ‘ (16) 
sun 
| 
4.3 Weight Matrix and Mean-Square Error 
Using least-squares adjustment, the mean value of the 
coordinate differences between two matched lines should be 
0, and a mean square error can be calculated from the differ- 
ences. If we treat the coordinates z' and y' as observations 
with a variance c?, the mean-square error of the match is 
the best estimate of o°. It is obvious that those properties 
of least-squares adjustment are defined in the spatial do- 
main. Because the matching is performed in the frequency 
domain, two questions arise. First, what should the weight 
matrix for the observations a4, b,, c, and d; be? Second, 
how 
and 
cov: 
lyze 
be 
COO: 
cov: 
Zerc 
cier 
tior 
coe 
is a 
alsc 
squ 
squ 
If t] 
Pro 
By 
be « 
Bec 
Bec 
We