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