n 
I (at 
A LEAST-SQUARES APPROACH TO MATCHING LINES WITH 
FOURIER DESCRIPTORS 
Yi-Hsing Tseng 
Toni Schenk 
Department of Geodetic Science and Surveying 
The Ohio State University, Columbus, Ohio 43210-1247 
USA 
Commission III 
ABSTRACT 
A common problem in computer vision, digital photogrammetry and cartography is to find the best match between a given 
line and a set of candidate lines, based on characteristics of shape. Fourier descriptors have been used successfully to match 
lines. In this paper we show how the best geometric fit of two matched lines is determined. The translation, scaling and 
rotation parameters are found by matching the Fourier descriptors with a least- squares adjustment. A mean-square error can 
be calculated after matching. This offers the advantage of a quantitative measure of goodness of fit. Experimental results 
using synthetic data demonstrate the feasibility of the proposed algorithm. 
KEY WORDS: Pattern Recognition, Machine Vision, Image Matching, Algorithm. 
1. INTRODUCTION 
To classify a set of patterns or to match two sets of 
features are common problems in computer vision, digital 
photogrammetry and cartography. These tasks are broadly 
known as pattern recognition. The fundamental approach 
to these problems is to find the best match in shape be- 
tween a given feature and a set of candidate features. Each 
candidate feature should be fitted against the given feature 
one by one, based on their characteristics of shape. This 
matching process is often conducted to come out with some 
quantities of intrinsic measure for checking the degree of 
similarity. The best match is then determined according to 
the intrinsic measure. 
An ambiguity may emerge on the determination of 
the best match, if there are more than one candidate fea- 
tures having a similar shape to that of the given feature. 
Because features may be distorted in practice, it is not sur- 
prising that the best match in shape is not guaranteed to 
be a correct match. Under the circumstance, additional in- 
formation is needed to make a better decision. An extrinsic 
measure, such as a measure of the relative location, orienta- 
tion and dilation between features, is considered to be key 
information to resolve this ambiguity. We therefore suggest 
that a matching process should generate both of intrinsic 
and extrinsic measures. 
Geometric information of features is often described 
by lines of the vector form. Image features, such as object 
boundaries, skeletons, edges or textures can be represented 
by lines. Although other geometric information such as 
area, perimeter, number of holes and moments is believed 
to be useful, the information content of lines is thought 
to be the most compact, accurate and useful. This paper, 
therefore, focuses on the matching of lines. 
In the last two decades, many techniques, such as 
polygonal approximation [Pavlidis and Ali, 1975; Green- 
feld and Schenk, 1989], 4 — s curves [Ballard and Brown, 
1982; Schenk, Li and Toth, 1991], and invariants of Fourier 
469 
descriptors [Granlund, 1972; Lin and Hwang, 1987], have 
been proposed to tackle the problem of matching linear 
features. These techniques emphasize the use of shape in- 
variants, a kind of intrinsic measure, to discriminate linear 
features. Although these techniques were reported efficient 
in some cases, two disadvantages were recognized. First, 
measuring similarity by comparing the shape invariants be- 
tween features does not provide a clear statistical sense. 
Second, they cannot provide any extrinsic measure. 
In this paper, a new matching process is proposed. It 
is designed to generate both of intrinsic and extrinsic mea- 
sures. Our strategy is to transform each candidate line to 
be optimally matched, in the condition of the least-squares 
fit, with the given line. The transformation parameters are 
solved by means of least-squares adjustment. A statistical 
quantity, the mean-square error, can be calculated after the 
adjustment. This quantity presents an ideal intrinsic mea- 
sure. And the estimated transformation parameters offer 
an extrinsic measure. 
A conventional transformation is usually performed 
about the origin of the coordinate system. The spatial rela- 
tionships between the original and the transformed features 
cannot be explicitly described by using the parameters of 
a conventional transformation. We, therefore, developed 
a centroid-based transformation which transforms a feature 
about its centroid - the mean position. 
The quantities of intrinsic and extrinsic measures are 
needed to be referred to a spatial coordinate system. It 
seems necessary to perform the matching process in the 
spatial domain. However, it is required to pre-define corre- 
sponding points between the lines. Difficulties in finding the 
corresponding points are expected because of the differences 
of sampling density, scale and starting point. In order to 
remedy this problem, an algorithm to perform the match- 
ing process in the frequency domain is developed, where 
the Fourier descriptors of lines are matched. The results of 
matching in the frequency domain are also interpreted with 
respect to the quantities desired in the spatial domain.