CIP A 2003 XIX th International Symposium, 30 September- 04 October, 2003, Antalya, Turkey
because it generates better, less spurious results. The upper right
corner of the all leaf parts was selected as starting point for the
boundary-tracing algorithm. After the operation, inner boundary
coordinates of every leaf were saved to an ASCII file. The
developed software can generate boundary coordinates of the
leaf images in a semi-automatic or fully automatic manner.
2.4 Fourier Descriptors
Fourier descriptors method is a 2-D boundary analysis method,
based on Fourier analysis of the function derived from the
boundary (Richard and Hemami, 1974, Zhan and Roskies,
1972, Persoon and Fu, 1977). The main advantage of the
method is its invariance to translation, rotation and scaling of
the shape to be described. Therefore, shape description becomes
independent of the relative position and size of the object in the
image space. One of the most popular implementation area of
the Fourier descriptors is handwritten character recognition
(Granlund, 1972, Cao et al., 1994). A classification of 2-D
partial shapes using Fourier descriptors was given by Lin and
Chellapa (1986). Another interesting implementation of Fourier
descriptors in medicine was presented by Veropoulos et al.
(1998). In this work, boundary tracing followed by Fourier
shape descriptors was used to represent Tubercle Bacilli. In
photogrammetry, the matching of area and line features with
Fourier descriptors was proposed as a feature-based matching
method by Tseng and Schenk (1992), Tseng et al. (1997).
Let us represent the boundary points as coordinate pairs; (x 0 ,y 0 ),
(xi,yi),...,(x N _i,yN-i)- Each coordinate pair can also be
represented as a complex number. In this case, the x axis is
treated as the real axis and the y axis as the imaginary axis of a
sequence of complex numbers.
i(k)= x(k) +jy(k) k = 0,1, ... ,N-l (2)
This representation has one great advantage: It reduces a 2D to
a ID problem. The discrete ID Fourier transform ofs(k) is:
Figure 5: (a) original boundary with 708 boundary elements,
(b), (c), (d), (e), and (f) are inverse Fourier transforms
using 250, 150, 75, 25, and 10 coefficients,
respectively.
In this application, Fourier descriptors of the boundary elements
were calculated using ID Fast Fourier transformation. Then, the
Euclidean distance between the first 250 Fourier descriptors of
the two different leaves is used as a shape similarity measure.
The number of Fourier descriptors (250) used for calculation of
the shape similarity measure was determined empirically
(Figure 6). Also, these distance measures are aided by
additional shape features (area and dMax) with proper weights
(Figure 7).
Figure 6: The original boundary has 1532 boundary elements.
250 Fourier coefficients (~16%) were used to capture
the whole leaf part boundary.
N-1
a(u) = — y^i(k)exp[-j27tuk/A^] u = 0,1, ... ,7V-1 (3)
N *
k=0
The complex coefficients a(u) are called the Fourier
descriptors of the boundary. The inverse Fourier transform of
the a(u)’s restores s(k).
N-1
s(k)= ^a(u)exp[j27iuk/A] k = 0,1,... ,AM (4)
u=0
i ^ dMax
!/
area
Figure 7: Additional shape features.
The Euclidean distance between the two vectors is calculated
as:
Instead of the full set of a(u) coefficients only the first M
coefficients can be used in the inverse transformation. The
result is an approximation of s(k).
M-1
?(k)= ^Ta(u)exp[j27tuk/zV] k = 0,1, ... ,N-\ (5)
u=0
where M is less than N ( M < N ). That is, the same number of
points exists in the approximate boundary, but not as many
terms are used in the reconstruction of each point. High
frequency components represent fine details, and low frequency
components determine the global shape. Thus the smaller M
becomes, the more detail is lost on the boundary (Figure 5). A
few Fourier descriptors can be used to capture the gross essence
of a boundary. This property is valuable, because these
coefficients carry shape information. Thus they can be used as
the basis for differentiating between distinct boundary shapes
(Gonzales and Woods, 1993).
" a ( u o)j - a ( u o)j
"l
0 .
. 0
0
a ( u l)i - a ( u l)j
0
I .
. 0
0
P =
dMax - dMax ^
0
0 .
• ^dMax
0
area, - area )
0
0 .
: o
^area _
where vector v,j is (252x1), and weight matrix P is (252x252).
IFdMax and If area are weights, determined empirically
(If d Max = 0-l , IFarea = 0-001). This relates the different kind of
parameters to each other. The Euclidean distance d u between
the z-th andy-th leaves is
d l} = ij vj Pvjj i,j = {0,I,...,65) i*j (7)
All Euclidean distances among the leaves were calculated, and
an overall symmetric distance matrix was generated:
