Fourier Descriptors

Each pixel on the contour c of a binary region can be represented by a complex number, the real and imaginary parts of which are the x and y coordinates of the pixel. This allows the contour to be expressed as a 1D complex sequence obtained by tracing around the contour in a selected direction, starting from a selected pixel:

where n is the pixel index and N is the number of pixels on the contour, and j here is the imaginary unit number. The DFT of this sequence

contains all the shape information of the contour that can be recovered with the inverse transform

un/N

The essential shape information is typically contained in the low-order coefficients of d(u) which constitute the Fourier shape descriptors.

The first coefficient d(0) is the centroid of the contour and varies with translation, while the remaining coefficients are all translation-invariant. All coefficients, however, depend on the pixel selected as the starting point. Consider d0(u) to be the Fourier coefficients obtained by starting the sequence c(n) from pixel p0. If the sequence is started ns pixels further than p0, the coefficients will be ds (u) = d0(u)e-j2nn'u/N

due to the shift property of the Fourier transform. If the contour is scaled by a factor a, the coefficients are also scaled by the same factor. Rotating the contour around the origin by an angle 6 imparts a multiplicative factor of ej6 to the Fourier coefficients. Therefore, the effects of starting point, scaling, and rotation can be summarized with dsa8(u) = d0(u)ae-j2™>u/Neje.

Fourier descriptors that are invariant to starting point, translation, scale, and rotation [21] are obtained with dinv (u)

The coefficient d(l) relates to the radius of the circle that approximates the shape, and its value is typically nonzero. The magnitudes of the normalized descriptors du ds(u) = d(T) u = 0

can be used as scale invariant metrics.

A shape factor [4] based on the magnitudes of the coefficients

invariance to translation, rotation, scale, and starting point. The value of FF varies between 0 and 1, and it increases with increasing object shape complexity and roughness. Figures 2 and 3 show the distributions of FF for benign and malignant microcalcifications in mammograms.

The formulation of Eq. (28) is based on the assumption that the elements of the sequence c (n) are equidistant on the path of the contour. If adjacent boundary pixels must be used, this uniform sampling can be achieved using 4-connected pixels. However, this sampling can significantly overestimate the length of contour segments that have an orientation around diagonals. Consequently, when adjacent pixels are used, both 4-connected and 8-connected contours have advantages and pitfalls for the computation of Fourier descriptors. If the region is large enough, an alternative is to select equidistant points along the contour to form c(n). If the fast Fourier transform (FFT) algorithm is used, the appropriate step size is computed with pc/2k, where pc is the contour perimeter in pixels computed with a step of 2 for diagonally connected pixels, and where k is the lowest integer power that yields 2k >pc. After points are selected with this step size, the sequence is zero padded to 2k to obtain c(n).

Among many applications, Fourier descriptors have been used to represent motion profiles for the diagnosis of low back disorders [22], to recognize human corneal endothelial cells [23], to represent the shape of prostate glands in magnetic resonance images [24], to quantify the shape of calcifications [1] and tumors [4] in mammograms, and to analyze chromosomes [25]. Fourier descriptors also have been extended to 3D and applied to magnetic resonance image data [26].

0 0

Post a comment