Region-based shape representation and description

• A large group of shape description techniques is represented by heuristic approaches which yield acceptable results in description of simple shapes.

• Heuristic region descriptors: area, rectangularity, elongatedness, direction, compactness, etc.

• These descriptors cannot be used for region reconstruction and do not work for more complex shapes.

• Procedures based on region decomposition into smaller and simpler subregions must be applied to describe more complicated regions, and then sub regions can be described separately using heuristic approaches.

Simple scalar region descriptors

• Area

• Area is given by the number of pixels of which the region consists.

• The real area of each pixel may be taken into consideration to get the real

size of a region.

• If an image is represented as a rectangular raster, simple counting of region pixels will provide its area.

• If the image is represented by a quad tree, then:

Algorithm: Calculating area in quad trees

1. Set all region area variables to zero, and determine the global quad tree depth H; for example, the global quad tree depth is H=8 for a 256x256 image.

2. Search the tree in a systematic way. If a leaf node at a depth H has a non-zero label, proceed to step 3.

3. Compute:

area[region_label] = area[region_label] + 4(H-h)

4. The region areas are stored in variables area[region_label].

• The region can also be represented by n polygon vertices (ik, jk ), and (i0, j0) = (in, jn). The area is given by

the sign of the sum represents the polygon orientation.

• If the region is represented by the (anti-clockwise) Freeman chain code the following algorithm provides the area

Algorithm: Region area calculation from Freeman 4-connectivity chain code representation.

1. Set the region area to zero. Assign the value of the starting point i co- ordinate to the variable vertical_position.

2. For each element of the chain code (values 0,1,2,3) do

3. If all boundary chain elements have been processed, the region area is stored in the variable area.

• Euler's number

• (Sometimes called Genus or the Euler-Poincare characteristic) describes a simple topologically invariant property of the object.

o S is the number of contiguous parts of an object and N is the number of holes in the object (an object can consist of more than one region).

• Projections

Horizontal and vertical region projections P_h (i) and P_v(j) are defined as

Region description by projections is connected to binary image processing. Projections can serve as a basis for definition of related region descriptors.

• Eccentricity

The simplest is the ratio of major and minor axes of an object. Another approximate eccentricity measure is based on a ratio of main region axes of inertia.

• Elongatedness

A ratio between the length and width of the region bounding rectangle. This is the rectangle of minimum area that bounds the shape, which is located by turning in discrete steps until a minimum is located (Fig 2(a)).

Fig 21: Elongatedness: (a) Bounding rectangle gives acceptable results; (b) Bounding rectangle cannot represent elongatedness

This criterion cannot succeed in curved regions (Fig 2(b)), for which the evaluation of elongatedness must be based on maximum region thickness. Elongatedness can be evaluated as a ratio of the region area and the square of its thickness. The maximum region thickness (holes must be filled if present) can be determined as the number d of erosion steps that may be applied before the region totally disappears.

• Rectangularity

Let Fk be the ratio of region area and the area of a bounding rectangle, the rectangle having the direction k. The rectangle direction is

turned in discrete steps as before, and rectangularity measured as a maximum of this ratio Fk

• Direction

Direction is a property which makes sense in elongated regions only. If the region is elongated, direction is the direction of the longer side of a minimum bounding rectangle. If the shape moments are known, the direction e can be computed as

Elongatedness and rectangularity are independent of linear transformations – translation, rotation, and scaling. Direction is independent on all linear transformations which do not include rotation. Mutual direction of two rotating objects is rotation invariant.

• Compactness

Compactness is independent of linear transformations

The most compact region in a Euclidean space is a circle.

Compactness assumes values in the interval [1,∞] in digital images if the boundary is defined as an inner boundary, while using the outer boundary, compactness assumes values in the interval [16, ∞].

Independence from linear transformations is gained only if an outer boundary representation is used.

Fig 22: Compactness: (a) Compact; (b) Non-compact.

Moments

• Region moment representations interpret a normalized gray level image function as a probability density of a 2D random variable.

• Properties of this random variable can be described using statistical characteristics - moments.

• Assuming that non-zero pixel values represent regions, moments can be used for binary or gray level region description.

• A moment of order (p+q) is dependent on scaling, translation, rotation, and even on gray level transformations and is given by

Where x, y, i, j are the region point co-ordinates (pixel co-ordinates in digitized images). Translation invariance can be achieved if we use the central moments

• Rotation invariance can be achieved if the co-ordinate system is chosen such that

• A less general form of invariance is given by seven rotation, translation, and scale invariant moment characteristics

• While the seven moment characteristics presented above were shown to be useful, they are only invariant to translation, rotation, and scaling.

• A complete set of four affine moment invariants derived from second- and third-order moments is

• All moment characteristics are dependent on the linear gray level transformations of regions; to describe region shape properties, we work with binary image data (f (i, j) =1 in region pixels) and dependence on the linear gray level transform disappears.

• Moment characteristics can be used in shape description even if the region is represented by its boundary.

• A closed boundary is characterized by an ordered sequence z(i) that represents the Euclidean distance between the centroid and all N boundary pixels of the digitized shape.

• No extra processing is required for shapes having spiral or concave contours.

• Translation, rotation, and scale invariant one-dimensional normalized contour sequence moments can be estimated as

• The r-th normalized contour sequence moment and normalized central contour sequence moment are defined as

• Less noise-sensitive results can be obtained from the following shape descriptors