Representation and Description in Image processing

Representing the boundary of a region enables efficient shape analysis, storage, and comparison, which are critical for tasks like object recognition, tracking, and classification. Here, we discuss key techniques for representing boundaries, including Boundary Following, Chain Codes, Polygonal Approximations, Other Polygonal Approximations, and Signatures. Each topic is detailed with mathematical concepts and examples to illustrate the techniques.

1. Boundary (Border) Following

Boundary following, also known as border tracking or boundary extraction, is the process of identifying and recording the coordinates of pixels that make up the boundary of a shape in a binary image. For simplicity, binary images are used, where object pixels are labeled as 1 (foreground) and background pixels as 0.

Moore’s Boundary Tracing Algorithm

Moore’s algorithm is commonly used for boundary following due to its simplicity and effectiveness. It works as follows:

1. Starting Point: Locate the first foreground pixel (labeled as 1) by scanning the image from the top-left corner. This becomes the initial boundary point.
2. Neighbor Check: Starting from this point, check the 8-neighbors of the current pixel in a clockwise (or counterclockwise) order to find the next boundary pixel.
3. Continue Until Loop Completes: Move to the next boundary pixel and repeat the process until the starting pixel is encountered again.

Mathematically, for a pixel at $(x, y)$, if the neighbors are checked in clockwise order, the first neighboring pixel labeled 1 is added to the boundary sequence. This sequence of boundary points can be denoted as:

where $(x_0, y_0)$ is the starting point and each consecutive point $(x_i, y_i)$ belongs to the boundary of the shape.

Example: In a binary image with a square object, boundary following will produce an ordered list of points around the perimeter of the square. For a simple square with vertices at $(1,1), (1,3), (3,3), (3,1)$, boundary following would yield a sequence tracing around these points in order.

2. Chain Codes

Chain codes are a way to represent a boundary by encoding its direction of movement at each step. Typically, chain codes use either a 4-directional or 8-directional system to represent movement.

4-Directional and 8-Directional Chain Codes

1. 4-Directional Chain Code: Uses directions {0, 1, 2, 3} to represent movement right, up, left, and down, respectively.
2. 8-Directional Chain Code: Uses directions {0 to 7}, where each code represents one of eight possible moves around a pixel (right, up-right, up, up-left, left, down-left, down, down-right).

The chain code sequence for a boundary can be represented as:

where $d_i$ represents the direction of movement from one boundary point to the next.

Normalization of Chain Codes

Chain codes are sensitive to the starting point, so the first difference (difference between successive directions) is often used for rotation invariance. For example, given an 8-directional chain code, $D = \{d_1, d_2, \ldots, d_n\}$, the first difference is:

This difference is computed modulo 8 to ensure direction consistency, providing a rotation-invariant representation.

Example: For a square with vertices represented by movements: $0 \rightarrow 2 \rightarrow 4 \rightarrow 6$, the chain code is $\{0, 2, 4, 6\}$. The first difference for rotation invariance is $\{2, 2, 2, 2\}$, highlighting the repetitive and symmetrical nature of the square boundary.

3. Polygonal Approximations Using Minimum-Perimeter Polygons

Polygonal approximation aims to simplify complex boundaries by representing them with a minimum number of straight-line segments, ideally preserving the essential shape. The goal of Minimum-Perimeter Polygon (MPP) approximation is to capture the shape while reducing the number of points in the boundary.

Minimum-Perimeter Polygon (MPP) Algorithm

The MPP algorithm works by:

1. Enclosing the Shape: Create a bounding box or set of cells around the shape boundary.
2. Shrinking Boundary Points: “Shrink” or compress the boundary until a polygon with the smallest perimeter that encloses the shape is obtained.
3. Selecting Vertices: Only keep boundary points that contribute to the shape’s essential features, minimizing the perimeter by using fewer points.

Mathematically, for a boundary $B = \{p_1, p_2, \ldots, p_n\}$, an MPP approximation minimizes the sum of distances between adjacent vertices:

where $m \leq n$ and $p_i$ are the points in the polygonal approximation of $B$.

Example: For a complex shape like a star, the MPP will result in a polygon with vertices at the star’s tips and inner corners, approximating the shape while omitting intermediate points along each segment.

4. Other Polygonal Approximation Approaches

While MPP is effective, alternative methods for polygonal approximation also exist, such as merging and splitting techniques.

4.1 Merging Techniques

Merging techniques work by fitting lines to groups of boundary points, minimizing error iteratively:

1. Error Minimization: Merge boundary points until the least-square error of the line fit exceeds a threshold.
2. Segment Definition: Store each segment as part of the polygon approximation when it surpasses the error threshold.

Mathematically, the merging criterion involves finding line parameters $a$ and $b$ to minimize:

4.2 Splitting Techniques

Splitting methods subdivide a segment repeatedly until an error threshold is met:

1. Initial Segments: Start with the longest segment between two extreme boundary points.
2. Distance Threshold: If any intermediate point exceeds the perpendicular distance threshold from the segment, subdivide at that point.

Example: For an irregular shape, splitting may start with a segment connecting the two farthest boundary points, breaking it down iteratively to capture significant turns and corners.

5. Signatures

A signature is a one-dimensional (1D) representation of a boundary, which provides a compact form for comparison and analysis.

Centroid Distance Signature

One of the simplest forms is the centroid distance signature, where the distance from each boundary point to the centroid is computed and plotted as a function of the angle.

1. Centroid Calculation: For a boundary $B = \{ (x_i, y_i) \}$, the centroid $(x_c, y_c)$ is: $$x_c = \frac{1}{N} \sum_{i=1}^{N} x_i, \quad y_c = \frac{1}{N} \sum_{i=1}^{N} y_i$$
2. Distance Calculation: The distance from each boundary point $(x_i, y_i)$ to the centroid is: $$r(\theta) = \sqrt{(x_i – x_c)^2 + (y_i – y_c)^2}$$
3. Signature Plot: Plot $r(\theta)$ versus $\theta$, the angle with respect to a reference direction.

Tangent Angle Signature

Another form of signature is the tangent angle signature, where the tangent angle at each point is plotted as a function of arc length along the boundary. If $t$ represents the arc length:

Example: For a circular boundary, the centroid distance signature is constant, while for an elongated ellipse, it shows a sinusoidal pattern, with peaks and troughs corresponding to the major and minor axes.

Regional Descriptors provide quantitative information about the internal properties of a region, beyond the boundary, enabling detailed analysis in applications like object recognition, image classification, and texture analysis. Here, we delve into four main types of regional descriptors: Simple Descriptors, Topological Descriptors, Texture, and Moment Invariants. Each section explores the relevant mathematical concepts and provides examples to illustrate the techniques.

1. Simple Descriptors

Simple descriptors summarize basic properties of a region, such as its area, center, orientation, and eccentricity. These descriptors are straightforward but form the foundation for more complex analysis.

1.1 Area

The area of a region represents the number of pixels within its boundary. For a binary image where the object pixels are labeled as 1 and the background as 0, the area $A$ can be calculated by summing the pixels inside the region:

where $f(x, y)$ is 1 for object pixels and 0 for background pixels.

Example: In a binary image of a circle with radius $r$, the area $A$ is approximately $\pi r^2$, assuming pixel resolution approximates the shape.

1.2 Centroid

The centroid (or center of mass) of a region is the average position of all its pixels and is given by:

where $(x_c, y_c)$ are the coordinates of the centroid.

Example: For a rectangular region, the centroid is located at the geometric center of the rectangle, at $(x_{\text{center}}, y_{\text{center}})$.

1.3 Eccentricity

Eccentricity is a measure of how elongated a region is. It is defined as the ratio of the distance between the foci of the ellipse that approximates the region to the length of its major axis. For an ellipse with semi-major axis $a$ and semi-minor axis $b$, eccentricity $e$ is:

A circle has an eccentricity of 0, while a highly elongated shape has an eccentricity close to 1.

Example: A perfect circle has $e = 0$, and an elongated ellipse has $e$ approaching 1.

2. Topological Descriptors

Topological descriptors characterize the structural properties of a region that remain unchanged under continuous transformations (like stretching or bending). Common topological descriptors include connectivity, the Euler number, and the number of holes.

2.1 Connectivity

Connectivity refers to how pixels within a region are connected to each other. In binary images, pixels can be either 4-connected or 8-connected:

• 4-connected: A pixel is connected to its horizontal and vertical neighbors.
• 8-connected: A pixel is connected to its horizontal, vertical, and diagonal neighbors.

Connectivity is useful for identifying separate regions in an image.

2.2 Euler Number

The Euler number $E$ is a topological descriptor that quantifies the structure of a region by counting its connected components and holes:

where $C$ is the number of connected components, and $H$ is the number of holes.

Example: For an image with one solid object (C = 1) and no holes (H = 0), the Euler number $E = 1$. If the object has two holes, $E = 1 – 2 = -1$.

2.3 Number of Holes

The number of holes within a region is simply $H$ in the Euler formula. It represents internal areas not connected to the outer boundary, such as gaps or voids within an object.

Example: A ring-shaped object in a binary image has one connected component and one hole, giving $E = 1 – 1 = 0$.

3. Texture

Texture describes the spatial distribution of pixel intensities within a region, capturing patterns that can help differentiate objects. Various methods analyze texture, such as the Gray Level Co-occurrence Matrix (GLCM), statistical measures, and frequency-based methods.

3.1 Gray Level Co-occurrence Matrix (GLCM)

The GLCM captures how frequently pairs of pixel intensities (gray levels) occur at a specific spatial relationship within a region. Each element $\text{GLCM}(i, j)$ represents the frequency of pixel $i$ occurring adjacent to pixel $j$. Common GLCM-based texture measures include:

1. Contrast: Measures the intensity contrast between a pixel and its neighbor over the whole image. $$\text{Contrast} = \sum_{i,j} (i – j)^2 \cdot \text{GLCM}(i, j)$$
2. Homogeneity: Measures the closeness of the distribution of elements in the GLCM to the GLCM diagonal. $$\text{Homogeneity} = \sum_{i,j} \frac{\text{GLCM}(i, j)}{1 + |i – j|}$$
3. Entropy: Measures the randomness of intensity distribution, higher for more complex textures. $$\text{Entropy} = -\sum_{i,j} \text{GLCM}(i, j) \log(\text{GLCM}(i, j))$$

Example: For a uniformly textured region, contrast and entropy are low, while homogeneity is high. A region with high variations in gray levels has high contrast and entropy.

3.2 Statistical Texture Measures

Statistical measures evaluate texture based on pixel intensity distributions:

1. Mean $\mu$: The average intensity of pixels in the region. $$\mu = \frac{1}{N} \sum_{i=1}^{N} I(i)$$
2. Variance $\sigma^2$: Measures the spread of pixel intensities. $$\sigma^2 = \frac{1}{N} \sum_{i=1}^{N} (I(i) – \mu)^2$$
3. Skewness: Indicates asymmetry in the pixel intensity distribution.

Example: A region with uniform pixel values has low variance, while a region with significant intensity changes has high variance.

4. Moment Invariants

Moment invariants are descriptors based on the spatial moments of a region, designed to be invariant to translation, rotation, and scaling, making them ideal for shape recognition.

4.1 Spatial Moments

For a 2D region represented by a binary image, the spatial moment of order $p+q$ is defined as:

where $f(x, y)$ is 1 for pixels inside the region and 0 elsewhere.

Example: The zeroth moment $M_{00}$ gives the area of the region, and the first moments $M_{10}$ and $M_{01}$ help find the centroid.

4.2 Central Moments

Central moments $\mu_{pq}$ are calculated relative to the centroid $(x_c, y_c)$, making them translation-invariant:

where $(x_c, y_c)$ is given by:

4.3 Hu’s Moment Invariants

Hu’s moment invariants are specific combinations of central moments that remain constant under translation, scaling, and rotation. The first few Hu moment invariants are:

1. $I_1 = \mu_{20} + \mu_{02}$
2. $I_2 = (\mu_{20} – \mu_{02})^2 + 4 \mu_{11}^2$

These invariants are calculated from normalized central moments, ensuring consistency regardless of object orientation or size.

Example: For a circle, Hu’s invariants yield specific values. When the circle is scaled, rotated, or shifted, the invariants remain unchanged, allowing it to be recognized across transformations.