ariants,
survey
, fields
riptors,
mputer
ntation
fulness
survey
, fields
gnition
ognise
t into a
mages.
This is
ic.) and
tion of
kes the
vision.
es have
n, area,
applied
also be
1 large-
xample
' into à
iveness
Laura Keyes
2 SHAPE DESCRIPTION TECHNIQUES
The recognition and description of objects plays a central role in automatic shape analysis for computer vision and it is
one of the most familiar and fundamental problems in pattern recognition. Common examples are the reading of
alphabetic characters in text and the automatic identification of aircraft. Most applications using Fourier descriptors,
moment invariants, scalar descriptors and boundary chain coding for shape recognition deal with the classification of
such definite shapes. To identify topographic objects each of the techniques need to be extended to deal with general
categories of shapes, for example houses, parcels and roads.
The data used for the experiments described in the following sections was extracted from vector data sets (NTF level 2)
representing large-scale (1:1250) plans of the Isle of Man (Kelly and Hilder 1998). A pre-processing operation was
required to transform the vector data from its original form to a new form suitable for further processing. In this case the
data was pre-processed to extract closed polygons from lines with the same feature codes. After extracting the required
polygonal data from the maps, an interpolation method was applied to sample the shape boundary at a finite number (N)
of equi-distant points. These points are then stored in the appropriate format for processing with each shape description
technique.
2. Fourier Descriptors
Fourier transform theory (Gonzalez and Wintz 1977) has played a major role in image processing for many years. It is a
commonly used tool in all types of signal processing and is defined both for one and two-dimensional functions. In the
scope of this paper, the Fourier transform technique is used for shape description in the form of Fourier descriptors. The
Fourier descriptor is a widely used all-purpose shape description and recognition technique (Granlund 1972, Winstanley
1998). The shape descriptors generated from the Fourier coefficients numerically describe shapes and are normalised to
make them independent of translation, scale and rotation. These Fourier descriptor values produced by the Fourier
transformation of a given image represent the shape of the object in the frequency domain (Wallace and Wintz 1980).
The lower frequency descriptors store the general information of the shape and the higher frequency the smaller details.
Therefore, the lower frequency components of the Fourier descriptors define a rough shape of the original object
The Fourier transform theory can be applied in different ways for shape description. One method works on the change
in orientation angle as the shape outline is traversed (Zahn and Roskies 1972), but for the purpose of this paper the
following procedure was implemented (Wood 1986). The boundary of the image is treated as lying in the complex
plane. So the row and column co-ordinates of each point on the boundary can be expressed as a complex number, x + jy
where j is sqrt (-1). Tracing once around the boundary in the counter-clockwise direction at a constant speed yields a
sequence of complex numbers, that is, a one-dimensional function over time. In order to represent traversal at a constant
speed it is necessary to interpolate equi-distant points around the boundary. Traversing the boundary more than once
results in a periodic function. The Discrete Fourier Transform (DFT) of the sequence of complex numbers, obtained by
the traversal of the object contour, gives the Fourier descriptor values of that shape. The Fourier descriptor values can
be normalised to make them independent of translation, scale and rotation of the original shape (Keyes and Winstanley
1999).
To apply the Fourier descriptor technique to the data set extracted from the Isle of Man map, the points are stored as a
series of complex numbers and then processed using the Fourier transform resulting in another complex series also of
length N. If the formula for the discrete Fourier transform were directly applied each term would require N iterations to
sum. As there are N terms to be calculated, the computation time would be proportional to N“. So the algorithm chosen
to compute the Fourier descriptors was the Fast Fourier Transform (FFT) for which the computation time is
proportional to NlogN. The FFT algorithm requires the number of points N defining the shape to be a power of two. In
the case of this project it was decided to use 512 sample points.
The FFT algorithm is applied to these 512 coefficients. The list is normalised for translation, rotation and scale. This
results in the first two terms always having the values 0 and 1.0 respectively which makes them redundant for
classification. Calculation of the Fourier Spectrum builds a new list and disposes of the Fourier transform list. The
result is 510 Fourier descriptor terms.
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 481