next up previous
Next: 3 Experiments Up: Comparison of Combined Shape Previous: 1 Introduction

2 Shape Coding Techniques

Three shape coding techniques are shortly introduced. All of them are computed from the contour of an object. The object is expected to be the ordered (x,y) presentation of the contour pixels.

2.1 The Chain Code Histogram

The chain code histogram (CCH) is meant to group together objects that look similar to a human observer [10]. It is not meant for exact detection and classification tasks. The CCH is calculated from the chain code presentation of a contour.

The Freeman chain code [6] is a compact way to represent a contour of an object. The chain code is an ordered sequence of n links tex2html_wrap_inline370 , where tex2html_wrap_inline372 is a vector connecting neighboring contour pixels. The directions of tex2html_wrap_inline372 are coded with integer values k=0,1,...,K-1 in a counterclockwise sense starting from the direction of the positive x-axis. The number of directions K takes integer values tex2html_wrap_inline382 where M is a positive integer. The chain codes where K>8 are called generalized chain codes [5].

The calculation of the chain code histogram is fast and simple. The CCH is a discrete function


where tex2html_wrap_inline388 is the number of chain code values k in a chain code, and n is the number of links in a chain code. A simple example is depicted in Figure 1. In Figure 1(a) are the directions of the eight connected chain code. In Figure 1(b) is a sample object, a square. The starting point for the chain coding is marked with a black circle, and the chain coding direction is clockwise. In Figures 1(c)-(d) are the chain code and the CCH of the contour of the square.

Figure 1: (a) The directions of the eight connected chain code (K=8). (b) A sample object, a square, (c) chain code presentation of the square, and (d) the chain code histogram of the square.

The CCH is a translation and scale invariant shape descriptor. It can be made invariant to rotations of tex2html_wrap_inline396 because the tex2html_wrap_inline396 rotation causes only a circular shift in the CCH. To achieve better rotation invariance the normalized chain code histogram (NCCH) should be used [10]. It takes into account the lengths of different directions.

2.2 The Pairwise Geometric Histogram

The pairwise geometric histogram (PGH) is a powerful shape descriptor that is applied to polygonal shapes [4, 2]. It can be applied also to an irregular shape if the shape is first approximated with a polygon. For a recent review of polygon approximation algorithms, see for example [19].

Consider a polygon defined by its edgepoints tex2html_wrap_inline408 . Now successive edgepoints define the line segments the polygon consists of. The PGH is calculated using the following strategy: Let each line segment be a reference line on its turn. Then the relative angle tex2html_wrap_inline410 and the perpendicular minimum and maximum distances ( tex2html_wrap_inline412 and tex2html_wrap_inline414 ) are calculated between the reference line and all the other lines, as shown in Figure 2(a). The histogram values are increased by one on the indexes corresponding to the angle tex2html_wrap_inline416 and the line segment from the tex2html_wrap_inline412 to tex2html_wrap_inline414 (Figure 2(b)).

Figure 2: (a) Relative angle and perpendicular distances between two lines, and (b) the pairwise geometric histogram.

A new scheme to reduce the size of the PGH is proposed. Conditional expectations of each row and column are calculated and collected into a feature vector. Let p(i,j) be the PGH value in the position (i,j). Then the feature vector tex2html_wrap_inline426 is given as


where N is the number of rows of the PGH, M is the number of columns of the PGH, tex2html_wrap_inline432 is the conditional expectation of the ith row,


and tex2html_wrap_inline436 is the conditional expectation of the jth column,


Thus the number of features is reduced from NM to N+M. This presents significant savings in calculation time and memory requirements, especially if N and M are large.

2.3 Combination of Simple Shape Descriptors

In this section, five simple shape descriptors are introduced (Figure 3). Variations of most of them have been widely used in object recognition [12, 17]. Each descriptor alone is insufficient for a complex recognition task, but the combination of them is shown to have good recognition capabilities (Section 3). All these shape descriptors require only tex2html_wrap_inline452 calculation steps expect convexity which requires tex2html_wrap_inline454 calculation steps. For a more profound discussion and definitions of these descriptors, see [15].

Figure 3: Five simple shape descriptors.

Convexity can be defined as the ratio of perimeters of the convex hull of the contour and the original contour. The convex hull is the minimal convex covering of an object. The algorithm for constructing a convex hull involves traversing the contour and minimizing turn angle in each step. Practically, dot product can be maximized instead.

Principal axes of an object can be uniquely defined as segments of lines crossing each other orthogonally in the centroid of the object and representing the directions with zero cross-correlation. This way, a contour is seen as an realization of a statistical distribution. The ratio of principal axis can be calculated from the covariance matrix of a contour. It is not necessary to calculate actual eigenvectors nor eigenvalues.

Compactness is often defined as the ratio of squared perimeter and the area of an object. It reaches the minimum in a circular object and approaches infinity in thin, complex objects. The measure applied in this paper is the ratio of the perimeter of a circle with equal area as the original object and the original perimeter.

Sometimes a shape should be compared against a template. A circle is an obvious and general template choice. The circular variance is the proportional mean-squared error with respect to solid circle. It gives zero for a perfect circle and increases along shape complexity and elongation.

Elliptic variance is defined similarly to the circular variance. An ellipse is fitted to the shape (instead of a circle) and the mean-squared error is measured.

next up previous
Next: 3 Experiments Up: Comparison of Combined Shape Previous: 1 Introduction

Jukka Iivarinen
Wed Jun 18 13:02:47 EET DST 1997