Fourier transforms of boundaries

• Suppose C is a closed curve (boundary) in the complex plane (Fig 11(a)).

• Traveling anti-clockwise along this curve keeping constant speed, a complex function z(t) is obtained, where t is a time variable.

• The coefficients Tn of the series are called the Fourier descriptors of the curve C. It is more useful to consider the curve distance s in comparison to time

• The descriptors are influenced by the curve shape and by the initial point of the curve. Working with digital image data, boundary co-ordinates are discrete and the function z(s) is not continuous. Assume that z(k) is a discrete version of z(s), where 4-connectivity is used to get a constant sampling interval; the descriptors Tncan be computed from the discrete Fourier transform.

z(k) ← DFT → T_n

• The Fourier descriptors can be invariant to translation and rotation if the co-ordinate system is appropriately chosen.

• The coefficients an, bnare not invariant, but after the transform

• To achieve magnification invariance the descriptors wn are used:

• The first 10-15 descriptors wnare found to be sufficient for character description.

Fig 11: Fourier description of boundaries (a) Descriptors Tn (b) Descriptors Sn

• A closed boundary can be represented as a function of angle tangents versus the distance between the boundary points from which the angles were determined

• The high quality boundary shape representation obtained using only a few lower order coefficients is a favorable property common to Fourier descriptors.

Boundary description using segment sequences

• If the segment type is known for all segments, the boundary can be described as a chain of segment types, a code-word consisting of representatives of a type alphabet.

• A polygonal representation approximates a region by a polygon, the region being represented using its vertices. Polygonal representations are obtained as a result of simple boundary segmentation.

• Another method for determining the boundary vertices is a tolerance interval approach based on setting a maximum allowed difference e.

Assume that point x1 is the end point of a previous segment and so by definition the first point of new segment. Define points x2, x3 positioned a distance e from the point x1 to be rectilinear-- x1, x2, x3 are positioned on a straight line (Fig 8). The next step is to locate a segment which can fit between parallels directed form points x2 and x3. Resulting segments are sub-optimal, although optimality can be achieved with a substantial increase in computational effort.

Fig 12: Tolerance interval

• Recursive boundary splitting.

Fig 13: Recursive boundary splitting

• Boundary segmentation into segments of constant curvature or curve segmentation into circular arcs and straight lines is used.

o Segments are considered as primitives for syntactic shape recognition procedures.

Fig 14: Structural description of chromosomes by a chain of boundary segments, code word: d,b,a,b,c,b,a,b,d,b,a,b,c,b,a,b.

• Sensitivity of shape descriptors to scale is also important if a curve is to be divided into segments -- a scale-space approach to curve segmentation.

• Only new segmentation points can appear at higher resolutions, and no existing segmentation points can disappear.

• Fine details of the curve disappear in pairs with increasing size of the Gaussian smoothing kernel, and two segmentation points always merge to form a closed contour showing that any segmentation point existing in coarse resolution must also exist in finer resolution.

• Moreover, the position of a segmentation point is most accurate in finest resolution and this position can be traced from coarse to fine resolution using the scale-space image.

• A multiscale curve description can be represented by an interval tree.

Fig 15: Scale-space image (a) Varying number and locations of curve segmentation points as a function of scale. (b)Curve representation by an interval tree.