Cartesian Fourier Descriptors

Fourier descriptors, like the chain code, use only the boundary of the ob- ject. In contrast to the chain code, Fourier descriptors do not describe curves on a discrete grid. They can be formulated for continuous or sam- pled curves. Consider the closed boundary curve sketched in Fig. 19.6. We can describe the boundary curve in a parametric description by tak-

T

ing the path length p from a starting point Σ x₀, y₀Σ as a parameter.

19.4 Fourier Descriptors                                                                503

 

(x0, y0)

1  0 P-1

2               P-2

3

4

5

 

 

Figure 19.6: Illustration of a parametric representation of a closed curve. The

T

parameter p is the path length from the starting point Σ x₀, y₀Σ  in the counter-

clockwise direction. An equidistant sampling of the curve with P points is also

shown.

 

It is not easy to generate a boundary curve with equidistant samples. Discrete boundary curves, like the chain code, have signifi cant disad- vantages. In the 8-neighborhood, the samples are not equidistant. In the 4-neighborhood, the samples are equidistant, but the boundary is jagged because the pieces of the boundary curve can only go in hori- zontal or vertical directions. Therefore, the perimeter tends to be too long. Consequently, it does not seem a good idea to form a continuous boundary curve from points on a regular grid. The only alternative is to extract subpixel-accurate object boundary curves directly from the gray scale images. But this is not an easy task. Thus, the accurate determi- nation of Fourier descriptors from contours in images still remains a challenging research problem.

=     +

The continuous boundary curve is of the form x(p) and y(p). We can combine these two curves into one curve with the complex function z(p) x(p) iy(p). This curve is cyclic. If P is the perimeter of the curve, then

z(p + nP) = z(p) n ∈ Z.                                        (19.7)

A cyclic or periodic curve can be expanded in a Fourier series (see also Table 2.1). The coeffi cients of the Fourier series are given by

P

P

0

P

zˆ _v = 1 ∫  z(p) exp. − 2π ivpΣ  dp  v ∈ Z.                            (19.8)

∞

P

The periodic curve can be reconstructed from the Fourier coeffi cients by

 

z(p) =

v=.− ∞

zˆ _v exp. 2π ivpΣ  .                                (19.9)

504                                                             19 Shape Presentation and Analysis

 

P

P

The coeffi cients zˆ _v are known as the Cartesian Fourier descriptors of the boundary curve. Their meaning is straightforward. The fi rst coeffi - cient

P

P

zˆ ₀ = 1 ∫

z(p)dp = 1 ∫

x(p)dp + i ∫

 

y(p)dp              (19.10)

                                                  

P

P

gives the mean vortex or centroid of the boundary. The second coeffi - cient describes a circle

P

z₁(p) = zˆ ₁ exp. 2π ip Σ  = r₁ exp.iϕ ₁ + 2π ip/PΣ  .                                   (19.11) The radius r₁ and the starting point at an angle ϕ ₁ are given by zˆ ₁ =

r₁ exp(iϕ ₁). The coeffi cient zˆ _{− 1} also results in a circle

.                    Σ

z_{− 1}(p) = r_{− 1} exp iϕ _{− 1} − 2π ip/P)  ,                                     (19.12)

but this circle is traced in the opposite direction (clockwise). With both complex coeffi cients together — in total four parameters — an ellipse can be formed with arbitrary half-axes a and b, orientation ϑ of the main axis a, and starting angle ϕ ₀ on the ellipses. As an example, we take ϕ ₁ = ϕ _{− 1} = 0. Then,

P

P

z₁ + z_{− 1} = (r₁ + r_{− 1}) · cos. 2π p Σ + i(r₁ − r_{− 1}) sin. 2π p Σ .                           (19.13)

 

This curve has the parametric form of an ellipse where the axes lie along the coordinate axes and the starting point is on the x axis.

From this discussion it is obvious that Fourier descriptors must al- ways be paired. The pairing of higher-order coeffi cients also results in ellipses. These ellipses, however, are cycled n times. Added to the basic ellipse of the fi rst pair, this means that the higher-order Fourier descrip- tors add more and more details to the boundary curve.

For further illustration, the reconstruction of the letters T and L is shown with an increasing number of Fourier descriptors (Fig. 19.7). The example show that only a few coeffi cients are required to describe even quite complex shapes.

Fourier descriptors can also be computed easily from sampled bound- aries z_n. If the perimeter of the closed curve is P, N samples must be taken at equal distances of P /N (Fig. 19.6). Then,

N− 1

zˆ _v =  1  .  z_n exp.− 2π inv Σ  .                                  (19.14)

N n=0                                       N

All other equations are valid also for sampled boundaries. The sam- pling has just changed the Fourier series to a discrete Fourier transform with only N wave number coeffi cients that run from 0 to N − 1 or from

− N/2 to N/2 − 1 (see also Table 2.1).

19.4 Fourier Descriptors                                                               505

a

b

Figure 19.7: Reconstruction of shape of a the letter “L” and b the letter “T” with 2, 3, 4, and 8 Fourier descriptor pairs.

 

⇐ Предыдущая76777879808182838485Следующая ⇒

Поделиться: