MODULE 5

CHAPTER 9 - MORPHOLOGY IN IMAGE PROCESSING

Textbook

Mathematical Morphology and Set Theory:

Mathematical morphology is grounded in set theory and provides a unified framework for
solving various image processing problems. In this context, image components are treated as
sets, allowing for the application of set operations to manipulate and analyze image structures.

Representing Images as Sets:

.IN
In binary images, objects are modeled as sets of pixels within the 2D integer space Z2. Each set
element is a 2D coordinate (tuple) corresponding to a foreground pixel. For grayscale images,
sets are extended to Z3, where each element includes pixel coordinates and its intensity value.
C
Higher-dimensional sets can also incorporate other attributes like color or temporal changes.
N
SY

Objects and Structuring Elements (SEs):

Morphological operations rely on two types of sets: the object set and the structuring element
(SE). Objects are defined as collections of foreground pixels. Structuring elements, on the other
U

hand, can include both foreground and background pixels, and may contain "don’t care"
elements (denoted by ×). These elements can be ignored or dynamically assigned values during
VT

matching, depending on the application.

Embedding Sets in Arrays:

Since digital images are stored as rectangular arrays, sets used in morphological operations
must be embedded into such arrays. Background pixels are assigned default values to fill non-
object areas. This embedding helps bridge the gap between abstract set theory and practical
digital image representation. For instance, images typically show a border of background pixels
around objects, whereas structuring elements do not include such padding.

1
Morphological Operations and Convolution Similarity:
Though morphological operations differ from standard convolution, they share similar
processing steps like padding and sliding the structuring element across the image. Structuring
elements function in a way that resembles convolution kernels, particularly in how they are
applied over the image.

Set Reflection and Translation in Morphology:

Two essential concepts used with structuring elements are set reflection and translation. The
reflection of a structuring element, denoted as

is obtained by mirroring the element about its origin. This reflected version plays a key role in

.IN
operations like dilation and erosion, as it determines how the SE interacts with the image during
processing. C
N
SY
U
VT

Set Reflection in Morphology:

If BBB is a set of points in two-dimensional space, its reflection, denoted B^, is obtained by
replacing each point with coordinates (x,y) by its reflected coordinates (−x,−y). This reflection
is a fundamental operation in mathematical morphology and is visually represented in Figure
9.2. The origin of the structuring element (SE) is typically marked by a dot. Reflecting an SE
is equivalent to rotating it 180 degrees about its origin. This rotation applies to all parts of the

2
SE, including the foreground, background, and any “don’t care” elements (×), ensuring a
complete and consistent transformation.
Set Translation in Morphology:
Translation of a set BBB by a point z=(z1,z2) is denoted by B z. This operation shifts every
point in the set B by the vector z. In other words, each point (x,y) in B becomes (x+z1,y+z2).
Translation is essential for positioning the structuring element at various locations over the
image during morphological operations such as dilation and erosion.

That is, if B is a set of pixels in 2-D, then (B) z is the set of pixels in B whose (x ,y ) Coordinates
have been replaced by (x+ z1, y+ z2) .

.IN
C
N
SY
U
VT

INTRODUCTION TO MORPHOLOGICAL OPERATIONS

Morphological operations in image processing involve interactions between a binary image

and a structuring element (SE). Consider a binary image III, where the object of interest is
denoted as set A (shaded), and a 3×3 structuring element B, composed entirely of foreground
pixels (1s), is used.

3
To perform a morphological operation such as erosion, a new image of the same size as I is
initialized with background values (0s). The structuring element B is then translated across the
image. At every position, if the SE is entirely contained within the object A, the origin of B is
marked as a foreground pixel in the new image. If not, it remains a background point.

When the origin of B lies at the boundary of A, part of B falls outside A, causing erosion at
that location. The final image thus reflects a shrunk version of the original object,
demonstrating the erosion effect. To keep visual representations compact, the minimum
padding required for the SE is used—only one pixel wide in the case of a 3×3 SE.

In morphological terminology, saying "B is contained in A" specifically implies that all
foreground elements of B overlap only with foreground elements of A. This concept becomes
more nuanced when the SE includes background and “don’t care” (×) elements.

.IN
In upcoming sections (9.2 to 9.7), binary morphology will be explored in detail. Grayscale
morphological operations and structuring elements will be introduced in Section 9.8.
C
9.2 Erosion and Dilation – Introduction
N
SY

Morphological image processing begins with two basic operations: erosion and dilation. These
operations serve as the foundation for many advanced morphological techniques.
Morphological expressions are defined using a set of foreground pixels (A) and a structuring
U

element (B).
VT

Definition of Erosion

Erosion of a set A by a structuring element B, denoted by A∣B, is defined as the set of all points
z such that B, translated by z, is entirely contained within A. This operation removes boundary
pixels from objects, effectively shrinking them.

Erosion in Terms of Images

In practice, morphological operations are applied on full images, not just sets. A more complete
form of erosion, denoted I∣B, accounts for both foreground and background pixels. It states that
erosion includes only those positions where the translated structuring element lies completely
within the object set A embedded in image I.

4
Use of Notation

When using erosion:

 Use A∣B if only foreground elements are involved.

 Use I∣B only when background or “don’t care” elements are included.
 Avoid using ∣ with mixed-value SEs; alternate notations are used in such cases.

.IN
C
N
Visual Interpretation
SY

In a binary image, erosion results in the inner region of the object, where the structuring
element fits entirely. The result of erosion is influenced by the shape and size of the structuring
U

element. A larger or differently shaped SE can erode objects into thinner or differently shaped
remnants.
VT

Practical Considerations

To apply erosion correctly:

 Ensure the image is padded to accommodate the full movement of the structuring
element.
 Crop the output to match the size of the original image.
 This is similar to padding and cropping in spatial convolution.

5
 DILATION
VT
U
SY
N
C
.IN

6
Dilation is the second fundamental morphological operation. It is based on reflecting the structuring
element BBB about its origin and translating it by a vector zzz, similar to the process in erosion.

Definition of Dilation

The dilation of a set A by a structuring element BBB, denoted as A⊕B, is defined as the set of all points
z such that the reflected and translated structuring element B^z overlaps at least one foreground
pixel in set A.

Mathematical Expression

This can be expressed as:

.IN
Here, z represents the displacement of the origin of the reflected structuring element B^. The dilation
includes all such positions where there is any intersection between B^ and A.
C
Interpretation
N
SY

While erosion requires the structuring element to fit completely inside the object, dilation is more
inclusive, allowing partial overlap. This causes the object to grow or expand, depending on the size
and shape of the structuring element.
U

Dilation is the opposite of erosion. Instead of shrinking objects, dilation grows or thickens them. This
VT

growth is controlled by the size and shape of the structuring element (SE) used. In the dilation process,
the background of the image is often expanded to accommodate the object’s growth. When using a
symmetric structuring element, reflection has no effect. As the structuring element slides over the
image, all locations where any part of it overlaps the object lead to the addition of foreground pixels in
the output.
The shape of the structuring element determines the direction and extent of dilation. For example, a
vertically elongated SE leads to more vertical expansion, as seen in the illustrative results. The dilation
includes all points where the origin of the SE is within a region that causes non-empty intersection
with the object.

7
 VT
U
SY
N
C
.IN

8
 .IN
C
N
SY
U
VT

Ac by B^ and vice versa.

9
 .IN
C
N
9.3 Opening and Closing – Combined Morphological Operations
SY

Opening and closing are two essential operations in morphological image processing that are built upon
erosion and dilation.
U

Opening involves an erosion followed by a dilation using the same structuring element. It is primarily
VT

used to smooth object contours, remove thin protrusions, and break narrow connections (called
isthmuses) between objects. This operation is particularly useful in eliminating small noise while
preserving the overall shape and size of larger objects.

Closing, on the other hand, consists of a dilation followed by an erosion. It tends to fill small holes,
close small gaps, and connect nearby objects. This makes closing effective for strengthening object
boundaries and fusing narrow breaks.

Both operations maintain the general structure of objects but are applied in opposite contexts — opening
removes small foreground features, while closing removes small background features.

10
 VT
U
SY
N
C
.IN

11
Closing is conceptually similar to dilation but involves translating the structuring element B
outside the set A. The closing of A by B is defined as the complement of the union of all
translations of B that do not overlap with A.

This means the boundary of the closing is determined by the furthest extent that BBB can
reach without intersecting A. Visually, this operation tends to fill small holes and connect
nearby objects by expanding A and then restoring its original shape.

Mathematically, the closing can be written as:

.IN
C
N
SY
U
VT

12
 VT
U
SY
N
C
.IN

13
9.4 Hit-or-Miss Transform (HMT)

The Hit-or-Miss Transform (HMT) is a fundamental morphological operation used primarily for
shape detection in binary images. In this context, a binary image III is composed of foreground pixels
represented by a set A, and background pixels. Unlike previous morphological operations that focus
only on foreground structures, HMT employs two structuring elements simultaneously—one that
matches the foreground and another that corresponds to the background. This dual-element approach
enables precise identification of specific configurations or patterns within the image, making HMT
particularly effective for detecting shapes such as corners, line endings, or other defined structures.

.IN
C
N
SY
U
VT

The morphological Hit-or-Miss Transform (HMT) is mathematically defined using erosion

operations, where one structuring element B1 is matched with the foreground pixels A, and a second
element B2 is matched with the background, or the complement of A, denoted Ac. The transform
identifies positions z where both conditions are met simultaneously—B1is fully contained within A,

14
and B2 is fully contained within Ac. The use of the word "miss" highlights that B2matching the
background is equivalent to missing the foreground. This concept is illustrated by detecting the specific
position of an object D, a subset of the foreground set A, in an image III, using an appropriately designed
pair of structuring elements to match both the object and its surrounding background.

.IN
C
N
SY
U
VT

The Hit-or-Miss Transform (HMT) is a morphological technique used for shape detection in binary
images by identifying specific patterns through a pair of structuring elements. One structuring
element, B1, matches a shape within the foreground (set A), while the other, B2, matches its
corresponding configuration in the background (Ac). This dual approach is necessary because the
geometric context of an object is defined not only by its shape but also by the background surrounding
it. In Fig. 9.12, B1 is designed to match the object D, while B2 detects the border around D within the
background of the complement image Ic. The intersection of the results of erosions with B1 and B2
yields the precise location of D. To simplify this, a single composite structuring element B, containing
foreground, background, and "don’t care" pixels (×), can be used in Eq. (9-17) to match patterns directly
in III. This approach allows processing of foreground and background pixels simultaneously,
enhancing pattern detection. Figures 9.13 and 9.14 demonstrate this using SEs designed for tasks such

15
as detecting holes, corners, and edges. The inclusion of don’t care elements allows a structuring
element to flexibly adapt, matching multiple configurations without the need for multiple SEs, thereby
increasing its versatility in morphological image analysis.
We can use a structuring element formed in such a way to restate the HMT as

.IN
C
9.5 SOME BASIC MORPHOLOGICAL ALGORITHMS
N
The field of morphological image processing offers a variety of practical techniques, especially when
working with binary images. These techniques are essential for extracting and analyzing components
SY

within an image that contribute to the representation and description of shape. This section builds
upon previously discussed morphological concepts to introduce several key algorithms. Specifically, it
addresses methods for boundary extraction, connected component labeling, convex hull
U

computation, and skeletonization of regions. Additionally, the section presents useful operations such
as region filling, thinning, thickening, and pruning, which are commonly applied during pre- or post-
VT

processing stages. To enhance clarity, the explanations include simplified mini-images that visually
illustrate the function and effect of each algorithm. These binary visuals maintain a consistent
representation, with foreground pixels (1’s) shaded and background pixels (0’s) left white, providing

16
an intuitive understanding of the morphological transformations involved.

.IN
BOUNDARY EXTRACTION: is a fundamental morphological operation used to identify the
border of objects in binary images. Given a set AAA of foreground pixels, its boundary, denoted b(A),
C
is computed by first performing erosion on AAA using a suitable structuring element BBB, and then
taking the set difference between AAA and its erosion. Mathematically, this is represented as
N
SY

where ⊖ denotes the erosion operation. The idea is to shrink the object slightly and subtract the result
from the original to leave behind only the pixels at the edge. Commonly, a 3×3 structuring element is
used, but larger elements like a 5×5 matrix of 1’s can produce thicker boundaries. During the
U

implementation, the image is typically padded with background pixels to accommodate the erosion
process, and the final result is then cropped back to the original image size. This method is particularly
VT

useful for shape analysis and feature extraction in image processing tasks.

HOLE FILLING:
In morphological image processing, a hole is defined as a background region completely surrounded
by connected foreground pixels. The objective of hole filling is to convert these enclosed background
areas into foreground pixels (1’s). The process is based on an iterative morphological dilation
technique conditioned by complementation and intersection operations. Let A represent the
foreground object boundaries, and assume that a starting point (or seed) within each hole is known.
An initial image X₀ is formed, consisting of all zeros except at the seed points, which are set to one.
Then, the iterative process

is applied, where B is a symmetric structuring element, and Ac is

the complement of the original image. This operation continues until convergence, that is, when

17
The result, Xk, represents the filled hole regions, and the union of Xk with the original image yields
the final image with holes filled. This approach, known as conditional dilation, ensures that dilation
occurs only within the background regions bounded by the object. Although the example provided in
the figure illustrates a single hole, the algorithm can be applied to multiple holes, provided that a seed
point is identified within each. This method serves as an effective demonstration of how morphological
operations can be controlled to satisfy specific image-processing objectives.

.IN
C
N
SY
U
VT

18
 .IN
C
EXTRACTION OF CONNECTED COMPONENTS: The extraction of connected components is
a key task in binary image analysis, forming the basis of many automated image interpretation
N
techniques. Given a binary image III, let A denote the set of foreground pixels which may contain
SY

multiple connected components. To begin the extraction process, an initial image X0 is created with
all zero (background) values, except at known seed points, each corresponding to a foreground pixel
within a connected component. The objective is to iteratively grow these seed points until the entire
U

connected component is recovered. This is achieved using the following iterative formula:
VT

where B is a structuring element that reflects the chosen pixel connectivity—typically 8-connected
for generality. The operation continues until convergence, that is, when

The final set Xk then contains all foreground pixels that are connected to the original seed points,
effectively extracting the connected components. This process employs conditional dilation, which
restricts growth to the foreground region of III, contrasting with the hole-filling algorithm, which
operates within the image complement Ic to find enclosed background regions. While the described
method requires at least one initial pixel per component, completely automated techniques that
eliminate this requirement are discussed elsewhere, such as in Problem 9.37.

19
 VT
U
SY
N
C
.IN

20
 CHAPTER 11
FEATURE EXTRACTION

11.1 Background
In image processing, although there’s no strict definition of what an “image feature” is, we
generally understand a feature as a distinctive attribute that helps us label or differentiate
objects. The key purposes of features are to help us identify (label) and distinguish
(differentiate) between image elements. These features may refer to specific objects within an
image or to entire images themselves. Essentially, features are important properties or
descriptors that help us tell images or image parts apart.
Feature extraction in images has two main components: feature detection and feature
description. Detection refers to the process of locating the features in an image, while

.IN
description refers to assigning values or attributes to those features. For example, if we consider
corners of objects as features, then detection means finding those corners, and description
involves measuring their orientation, location, or relation to other corners. Simply detecting a
C
feature isn’t enough; we also need descriptive information to help compare and classify objects
N
or images.
To be effective in differentiating between image elements or full images, the features we extract
SY

must have certain important characteristics. Ideally, features should be independent of

position (location), size (scale), and orientation (rotation). Additionally, features should be
robust against changes in lighting or the viewpoint from which the image was captured. This
U

means a good feature should remain consistent even if the image is taken from a different angle
VT

or under different lighting conditions.

Preprocessing plays a crucial role in improving feature extraction. By using techniques like
histogram equalization, we can adjust the brightness and contrast of an image to minimize
the effects of lighting changes, making it easier to detect and describe features accurately.
Using known information about the images in advance (a priori information) can help us apply
appropriate preprocessing before extracting features.
Finally, when we say a feature is independent, it usually means it is either invariant or
covariant under certain transformations. A feature descriptor is invariant if its value does not
change after a transformation (like rotation, translation, or reflection). It is covariant if the
transformation applied to the object also reflects similarly in the feature’s description. For
example, the area of an elliptical region remains the same under rotation, reflection, or
translation—making area an invariant feature with respect to those transformations.

21
Feature Descriptors
One of the key ideas in image analysis is the use of features to describe image content. A
commonly used feature descriptor is area. It is invariant with respect to some transformations,
meaning its value does not change when those transformations are applied. However, when we
introduce scaling, the area becomes covariant. This means the descriptor value changes
proportionally with the transformation. For example, scaling a region increases its area, and
thus the area descriptor scales accordingly.
Similarly, the direction of the principal axis of a region is also a covariant feature. When the
region is rotated, the direction value also rotates by the same angle.
Most feature descriptors are generally covariant — they might be invariant to certain
transformations but sensitive to others. To handle this, we often apply normalization
techniques to eliminate as many covariances as possible. For instance, to make features

.IN
rotation-invariant, we can calculate the actual direction of each region and rotate the region
so that its principal axis aligns with a predefined direction.
C
Local vs. Global Features
N
Features are also categorized as local or global. However, this classification depends heavily
on the application context.
SY

Consider the example of a production line that checks how full bottles are. Images of 10
bottles are captured, where the liquid appears bright, and the background is dark. The area
U

of the bright region in each bottle directly reflects the amount of liquid, making it a local
feature, as it applies to individual regions in an image.
VT

Now, if we change the problem to computing the total amount of liquid in one image, area
becomes a global feature because it applies to the entire image.
Taking it further, suppose the task now is to compute the total liquid per day. In this case, the
area per image is treated as a local feature, and the total across all images becomes a global
descriptor. This can go on indefinitely, depending on how we define the “member” and
“set.”
So, in these notes:
 A local feature applies to a member of a set (e.g., one bottle in an image).
 A global feature applies to the whole set (e.g., all bottles or all images in a day).
— Purpose of Feature Descriptors

22
Feature descriptors are rarely intended for direct human interpretation, except in specialized
cases like interactive image processing. Often, feature extraction methods generate dozens
to thousands of descriptors, which may seem meaningless if viewed individually.
Instead, feature descriptors are used as a preprocessing step in more advanced image
processing tasks, such as:
 Image registration
 Object recognition
 Scene understanding
These features allow machines to understand visual data and make intelligent decisions based
on them.
In various computer vision tasks like automated inspection, pattern recognition (such as
detecting faces or fingerprints in image databases), and autonomous systems (including

.IN
robotic and vehicle navigation), it is essential to describe image content numerically. This is
usually done using a feature vector, which is essentially a 1 × n or n × 1 matrix where each
element represents a specific descriptor.
C
A basic example is an RGB image, where each pixel is described using a 3-dimensional
N
vector:
x = [x₁, x₂, x₃]
SY

Here, x₁ represents the red intensity, x₂ the green intensity, and x₃ the blue intensity at a
given point. When using color as a feature, a particular region in an RGB image can be viewed
as a group of these vectors positioned in a 3D feature space.
U

If we use n descriptors, then our feature vector becomes n-dimensional, and the collection of
VT

all such vectors lies in an n-dimensional feature space. You can imagine these vectors as
forming a “hypercloud” of points in n-dimensional Euclidean space, which gives a spatial
perspective to complex data.
The features are broadly classified into three major categories: boundary features, region
features, and whole image features. This classification helps in logically grouping features
based on the image property they describe. For instance, when referring to the “length of a
boundary,” it makes sense only when talking about a region’s boundary, not the entire image.
On the other hand, some features may apply to both boundaries and regions, and a few can
even describe whole images.
The classification is not about limitations of the techniques, but about the meaningful
application of features to specific aspects of an image. This approach will help us better
understand and analyze various image characteristics in the following sections.

23
11.2 BOUNDARY PREPROCESSING
In image segmentation, the output often consists of raw data in the form of pixels located along
object boundaries or within segmented regions. To make the computation of descriptors
more efficient and structured, it is a common practice to compress this data into more compact
and useful representations. This section introduces several boundary preprocessing
techniques that help in achieving this goal.
One fundamental approach is called Boundary Following (or Tracing). Many algorithms
require the boundary points of a region to be in a specific order—either clockwise or
counterclockwise. Thus, it is essential to use an algorithm that produces an ordered sequence
of boundary points. The method discussed here operates under the assumptions that the image
is binary (with object pixels labeled as 1 and background pixels as 0) and that the image has
been padded with a border of 0s. This padding ensures that objects do not merge with the

.IN
image borders. Although the explanation is limited to a single region, the method can be
extended to handle multiple disjoint regions by processing each region separately.
The algorithm, commonly known as the Moore Boundary Tracing Algorithm, follows these
C
steps:
N
1. Identify the starting point, denoted as b₀, which is the uppermost-leftmost pixel in the
image labeled 1. Let c₀ be the west neighbor of b₀. Since c₀ lies outside the object, it
SY

will always be a background pixel. Starting at c₀, examine the 8-neighbors of b₀ in a

clockwise direction. The first neighbor encountered with a value of 1 is labeled as b₁,
and the preceding pixel in this scan (a background pixel) is labeled as c₁. The
U

coordinates of b₀ are stored for use in a later step.

VT

2. Set b = b₀ and c = c₀.

3. Again, examine the 8-neighbors of b, beginning at c and scanning clockwise. Let n₁,
n₂, ..., n₈ represent these neighbors. Find the first pixel labeled 1 and denote it as nₖ.
4. Set b = nₖ and let c be the pixel immediately preceding nₖ in the clockwise scan.
5. Repeat steps 3 and 4 until b equals b₀. The sequence of points collected during this
process represents the ordered boundary points of the object.
An important detail is that c, the background pixel in each step, always precedes the newly
found object pixel. This method effectively traces the outer boundary of a region and is reliable
for complex shapes, including branched or self-intersecting boundaries. It can also be
applied to images with multiple regions, processing one boundary at a time.
If the input is a binary region (as opposed to a boundary), the algorithm extracts the outer
boundary. While the result is usually a one-pixel-wide boundary, it may vary in some cases.

24
To trace interior boundaries (such as holes within regions), these holes must be extracted and
treated as separate 1-valued regions against a 0-valued background. Applying the same
algorithm will then yield the inner boundaries of the original region.
Although this tracing process can be defined in either the clockwise or counterclockwise
direction, it is typically simpler to use one consistent direction and reverse the result when
needed. In later discussions, both directions will be used interchangeably to help students
become familiar with each approach.

.IN
C
N
SY
U
VT

11.2.2 CHAIN CODES

Chain codes are used to describe a boundary through a connected sequence of straight-line
segments of defined length and direction. In this context, we typically assume that all curves
are simple and closed—meaning they form a loop without self-intersection.
One of the most well-known chain code methods is the Freeman Chain Code, which
represents direction based on 4-connectivity or 8-connectivity. Each segment's direction is
encoded using a specific numbering scheme, such as the one shown in standard figures like
Fig. 11.3. The resulting boundary code—a sequence of these numbers—is known as the
Freeman chain code.

25
Since digital images are generally arranged in a grid format with equal spacing along both x
and y axes, a chain code can be generated by following the boundary of an object, usually in a
clockwise direction, and assigning a directional number to each segment between pixel pairs.

However, using the full pixel-level detail often leads to two main issues:
(1) The resulting chain becomes excessively long, and
(2) Minor disturbances or noise can cause unnecessary changes in the code that do not reflect

.IN
the actual shape of the object.
To overcome these challenges, a common strategy is to resample the boundary using a
coarser grid (as shown in Fig. 11.4(a)). During traversal, each boundary point is mapped to
C
the nearest grid node (as seen in Fig. 11.4(b)). This simplified representation can be encoded
N
using either a 4-directional or 8-directional chain code. For instance, Fig. 11.4(c) shows how
this is applied using the 8-directional scheme. Converting between 4-code and 8-code is
SY

straightforward.
To maintain consistency in representation, the starting point for chain code generation is
U

typically chosen as the uppermost-leftmost point on the boundary. For example, in Fig.
11.4(c), this results in a chain code sequence like 0766…1212. The spacing of the resampling
VT

grid is application-specific and must be selected accordingly.

When the sampling grid is a uniform quadrilateral, as illustrated in standard references (e.g.,
Fig. 2.19), the resulting Freeman chain code aligns precisely with the digital curve. Similarly,
when using a resampling approach with the same type of grid, all points in the code remain
reachable, preserving accuracy in representation.
The numerical values in a chain code are dependent on the chosen starting point, but this
dependency can be removed through a simple normalization process. By treating the chain
code as a circular sequence, we can rotate the sequence to start from the point that yields the
lowest possible integer value. Additionally, rotation normalization can be achieved using
the first difference of the chain code. This is calculated by counting the number of direction

26
changes, in a counterclockwise manner, between each pair of adjacent elements in the code.
For example, the first difference of the 4-directional chain code 10103322 is 3133030.
We can also perform size normalization by modifying the spacing of the resampling grid.
However, it is important to note that all the normalization techniques discussed are exact only
under ideal conditions, i.e., when the object’s boundaries remain unchanged under rotation
(in fixed-angle increments) and scaling. In practice, this is rarely the case, as even the same
object captured from different angles or at different resolutions will produce distinct boundary
shapes. The extent of variation increases with image resolution.
To minimize these effects, one can use longer chain elements relative to the distance between
pixels and align the resampling grid along the principal axes of the object being analyzed.

.IN
C
N
SY

FREEMAN CHAIN CODE AND BOUNDARY REPRESENTATION:

Figure 11.5(a) presents a 570 × 570-pixel, 8-bit grayscale image containing a circular stroke
U

embedded within small, randomly scattered specular fragments. The primary goal of this
VT

example is to derive the Freeman chain code, determine the corresponding integer of
minimum magnitude, and compute the first difference for the outer boundary of the stroke.
Due to the presence of noise in the form of small fragments, directly extracting the object's
boundary would result in a noisy curve that poorly represents the actual shape. As previously
discussed, smoothing is an essential step when dealing with such noisy boundaries. Figure
11.5(b) illustrates the image after it has been smoothed using a 9 × 9 pixel box filter. (Refer to
Section 3.5 for details on spatial smoothing.)

Following the smoothing step, Figure 11.5(c) shows the result of applying Otsu’s
thresholding method, which significantly simplifies the image by reducing it to two regions
(one being just a dot). This reduction in complexity aids in isolating the stroke more effectively.

27
In Figure 11.5(d), we observe the outer boundary of the region identified in the previous step.
If we were to extract the chain code from this boundary directly, the outcome would be a long
sequence with minor variations that fail to capture the overall shape. To address this, we
perform resampling before computing the chain code, thereby reducing unnecessary
variations.
Figure 11.5(e) demonstrates the result of using a resampling grid with nodes spaced 50 pixels
apart (approximately 10% of the image width). In Figure 11.5(f), these sample points are
joined by straight lines, producing a simplified approximation that retains the main structure
of the original boundary.
The 8-directional Freeman chain code of the simplified boundary is:
00006066666666444444242222202 202
The starting point of the boundary is at coordinates (2, 5) in the subsampled grid. As noted

.IN
in Figure 2.19, the origin of an image is located at the top-left corner, making this the
uppermost-leftmost point in Figure 11.5(f).
In this case, the integer of minimum magnitude derived from the code is the same as the
C
chain code itself: 0 0 0 0 6 0 6 6 6 6 6 6 6 6 4 4 4 4 4 4 2 4 2 2 2 2 2 0 2 2 0 2
N
The first difference of the code, which helps reduce redundancy and enables efficient analysis,
is: 0 0 0 6 2 6 0 0 0 0 0 0 0 6 0 0 0 0 0 6 2 6 0 0 0 0 6 2 0 6 2 6
SY

Using this coding method offers a substantial reduction in the amount of data required to
represent the boundary.
U
VT

28
SLOPE CHAIN CODES (SCCS):
An alternative to the traditional Freeman chain codes for boundary representation is the use of
Slope Chain Codes (SCCs), as proposed by Bribiesca (1992, 2013). Freeman chain codes
typically require a resampling of the boundary by defining a grid structure, where boundary
points are assigned to their nearest grid neighbors to minimize small variations. In contrast,
SCCs approach the problem by placing equal-length straight-line segments along the
boundary of a 2D curve. These segments touch the curve at their endpoints, forming a
simplified geometric representation.
The key step in generating an SCC is to compute the slope changes between consecutive line
segments. These slope changes are then normalized into the continuous open interval (−1,
1). Unlike Freeman codes, SCCs do not require grid alignment, simplifying the
implementation. Additionally, SCCs offer better rotation invariance because they are not

.IN
limited to the eight directional codes used by Freeman’s approach. They also share
translation invariance and can be normalized to account for scaling effects.
To begin generating an SCC, the length of the line segment must be chosen. Next, a starting
C
point is defined—typically one of the endpoints of the curve in the case of an open shape. A
N
segment is placed such that one of its ends is at this origin point, and the other touches the
curve. This touched point becomes the starting position for the next segment. The process
SY

continues until the other end of the open curve is reached. This method can be visualized as
using identical circles, where the radius equals the length of the segment, moving along the
curve. The intersection points between these circles and the curve define the points of
U

connection for the line segments.

VT

After establishing the points of intersection, the slope changes between consecutive segments
are calculated. These changes are normalized such that positive and zero values fall within
[0, 1) and negative changes fall within (−1, 0). Importantly, slope values of ±1 are excluded
to avoid ambiguities arising from segments of the same slope but in opposite directions.
The resulting series of normalized slope changes forms the SCC, which represents the
approximation of the curve. For instance, a curve might be encoded with the sequence: 0.12,
0.20, 0.21, 0.11, −0.11, −0.12, −0.21, −0.22, −0.24, −0.28, −0.28, −0.31, −0.30. The accuracy
of slope measurements determines the size of the symbol alphabet. In the example shown in
Fig. 11.6(d), an accuracy of 10⁻² produces 199 possible slope values, while an accuracy of 10⁻¹
would produce 19 symbols.
One limitation of SCCs is that the final point of the encoded curve may not exactly coincide
with the curve’s true end point. This discrepancy can often be reduced by either decreasing

29
the segment length or increasing the angular resolution, though computations are still
constrained by rounding to integer coordinates.
The inverse of an SCC is created by reversing the order and signs of the slope values. To
obtain a mirror image, one simply reverses the signs while keeping the order from the origin.
These principles apply equally to closed curves, where one may start at any arbitrary point
(often the top-leftmost point) and proceed around the curve in either a clockwise or
counterclockwise direction until returning to the starting point.

.IN
C
N
SY
U
VT

30
 Chapter 12
IMAGE PATTERN CLASSIFICATION
12.1 Background
Humans possess the most advanced pattern recognition abilities in the known biological world.
In contrast, machine recognition systems still fall short when compared to routine human tasks,
such as interpreting complex visual information or generalizing from past experiences.
Nonetheless, these machines play a vital role in daily life. Consider the importance of systems
that can read barcodes, process bank checks, inspect manufacturing quality, read fingerprints,
sort mail, and recognize speech—all examples of pattern recognition in action.
In image pattern recognition, a pattern is defined as a spatial arrangement of features, and a
pattern class is a collection of patterns that share similar characteristics. Pattern recognition by
machine involves techniques for automatically assigning patterns to their respective classes. In

.IN
simple terms, the goal is to assign a class label to each input pattern based on its characteristics.
There are four fundamental stages in the pattern recognition process:
1. Sensing – Capturing data in a spatial (2-D) or higher-dimensional format.
C
2. Preprocessing – Performing tasks such as noise reduction, image enhancement,
N
restoration, and segmentation.
3. Feature Extraction – Identifying and isolating important attributes from the image.
SY

4. Classification – Using the extracted features to assign class labels to unknown image
patterns.
U

This chapter focuses primarily on classification, the final step in the recognition process. We
will explore three main approaches to image pattern classification:
VT

1. Prototype-based classification – Matching unknown patterns with predefined

prototypes.
2. Statistical classification – Using decision-theoretic models, such as the Bayes classifier,
to optimize classification.
3. Neural networks – Employing systems that can learn features and patterns from raw
data, sometimes even without manual feature design.
The difference between these approaches lies in the amount of engineering effort required to
prepare the data. In prototype-based classification, the features are designed to be so distinctive
that classification becomes straightforward. For example, bank-check processors use specific
font styles to enhance recognition accuracy.

31
In statistical classification, the problem is framed using probability and statistics, and the goal
is to identify parameters that offer the best classification performance. This approach gives
equal importance to both feature selection and classifier design.
In the case of neural networks, especially deep learning models, the system can automatically
learn feature representations from raw data. These models do not require manually designed
features and can perform highly accurate classification based solely on training data.
All three approaches rely on parameters that must be either predefined or learned from
examples. Data used for this purpose can be labeled (where class labels are known) or unlabeled
(where the goal is to discover patterns without prior labels). A classic example of labeled data
is character recognition, where each character is tagged with a label (e.g., ‘a’ to ‘z’ or ‘0’ to
‘9’). Unlabeled data is often used for tasks like clustering, where the system identifies groups
or patterns without prior knowledge.

.IN
When working with labeled data, the dataset is usually split into three parts:
 A training set (typically 50%) for adjusting model parameters.
 A validation set (about 25%) for tuning and comparing model designs.
C
 A test set (about 25%) for evaluating performance on unseen data.
N
If the system performs well during training and validation but fails on the test set, it may be
overfitted—meaning the model learned the training data too well and cannot generalize to new
SY

data. This signals the need to rethink the model architecture or the data used.
When a system is trained using labeled data, the process is called supervised learning. If the
system learns from unlabeled data, it undergoes unsupervised learning. This chapter deals
U

primarily with supervised learning, which includes methods ranging from models with fixed
VT

features designed by humans, to advanced deep learning systems that automatically learn
features from large datasets.

12.2 Classes and Pattern Vectors

In image pattern classification, patterns are generally divided into two main types: quantitative
and structural.
 Quantitative patterns are represented using pattern vectors, which are arrays of
numerical feature values.
 Structural patterns consist of symbols and are arranged as strings, trees, or
sometimes graphs. While this chapter primarily focuses on pattern vectors, structural
patterns will be discussed briefly at the end of this section and in Section 12.3.

32
  Pattern Vectors
Pattern vectors are typically denoted by lowercase letters such as x, y, or z. These vectors take
the form:

This format is known as a column vector, where each element xᵢ represents a specific feature
descriptor, and n is the total number of such descriptors. The same vector can also be written
as a row vector:
x = (x₁, x₂, …, xₙ)ᵗ

.IN
Here, the superscript T denotes the transpose operation, converting the row vector into a
column vector.
C
N
SY
U

A pattern vector can be imagined as a point in n-dimensional space, where each axis
VT

represents a feature. A pattern class is then a cluster or “hypercloud” of these points in this
space. Ideally, we want the clusters to be tight (intra-class similarity) and well-separated
(inter-class distinction).
 Creating Pattern Vectors
Pattern vectors can be formed directly from pixel values of an image by converting the 2D
image into a 1D vector using linear indexing. However, a more common and efficient
approach is to use image features as vector components.
One historical example is the work of R. A. Fisher in 1936, where he used discriminant
analysis to classify three species of iris flowers (setosa, versicolor, and virginica). Each flower
was described using four features: petal length and width, and sepal length and width. This
resulted in 4-dimensional vectors for classification.

33
High-Level Feature-Based Vectors
Features extracted from image boundaries, regions, or both can also form pattern vectors. For
instance:
 Boundary signatures (1D curves representing shape outlines) can be sampled at
regular intervals to form vectors.
 Instead of raw samples, feature functions like statistical moments (as introduced in
Chapter 11) are often computed and used in the vectors.
 Objects with both boundary and region properties can be represented by 3D or higher-
dimensional vectors.
For example, in binary images, objects can be represented by features like compactness,
elongation, and area, forming compact pattern vectors.
 Texture and Invariant Features

.IN
Pattern vectors may also include texture measures (e.g., coarseness, contrast) or
transformation-invariant features. These features are especially helpful when dealing with
varying scales, rotations, or illumination conditions, ensuring the classifier remains robust.
C
N
SY
U
VT

 Multispectral and High-Dimensional Applications

When working with registered image sequences, such as in multispectral imaging, pattern
vectors are formed from corresponding pixels across images. This enables consistent
recognition based on the same spatial locations across different spectral bands.
In cases where entire images are used, much higher-dimensional vectors are necessary.
Traditional methods like SIFT rely on engineered features, but deep convolutional neural
networks (CNNs) now offer more powerful alternatives by learning relevant features directly
from raw image data.

34
STRUCTURAL PATTERNS:
While most pattern classification in image processing uses pattern vectors, structural patterns
are essential for applications where shape and relational features dominate.
What Are Structural Patterns?
Unlike pattern vectors that rely on numerical feature descriptors, structural patterns use

.IN
symbolic representations—often in the form of strings, trees, or occasionally graphs. These
representations are particularly useful for describing object shapes, hierarchical
C
relationships, or compositions.
N
SY
U

 String-Based Structural Patterns

An example of a structural pattern is illustrated in Fig. 12.8. In this example, the boundary of
VT

a bottle is approximated using a polygon. The process involves:

 Subdividing the boundary into line segments.
 Calculating the interior angle (denoted as u) at each junction between segments.
 Encoding the boundary traversal as a sequence of symbols, forming a string.
The string describes how the shape changes as the boundary is followed in a counterclockwise
direction. These symbol strings can be matched to predefined prototype strings, allowing
classification based on shape structure. This approach is especially useful when geometric
precision is difficult but symbolic patterns can be reliably matched.
 Tree-Based Structural Patterns

35
Another common structural representation is the tree, which is suitable for hierarchical image
descriptions. A tree structure allows for a top-down decomposition of an image into its
component regions.
Consider the satellite image in Fig. 12.9. A possible hierarchical breakdown might look like:
 Root node ($): Represents the entire image.
 First-level branches: Classify the image into downtown and residential areas.
 Subsequent levels:
o Residential areas are further broken down into housing, highways, and
shopping malls.
o Housing might include apartments, single-family homes, etc.
o Highways might include overpasses, intersections, and feeder roads.
Each node in the tree represents a component of the image, and each branching reflects the

.IN
"composed of" relationship. This type of representation is powerful for applications in scene
understanding, object hierarchy, or semantic segmentation.
 Applications of Structural Patterns
C
Structural approaches are particularly relevant in:
N
 Shape recognition (e.g., industrial inspection)
 Scene analysis (e.g., satellite imagery)
SY

 Document layout understanding

 Biological structure modelling (e.g., anatomical trees in medical imaging)
Although less common in general-purpose image classification tasks, structural patterns offer
U

rich descriptive power where relationships between parts are as important as the parts
VT

themselves.

12.3 – PATTERN CLASSIFICATION BY PROTOTYPE MATCHING

Pattern classification by prototype matching is a fundamental approach in pattern recognition.
It involves comparing an unknown pattern with a set of known prototypes, then assigning
the unknown to the class of the most similar prototype.
Each prototype corresponds to a pattern class, and there may be multiple prototypes per
class to better capture class variability. The key factor that differentiates various matching
techniques is the similarity (or distance) measure used.

🔹 Minimum-Distance Classifier

36
One of the most commonly used methods for prototype matching is the Minimum-Distance
Classifier. This approach operates as follows:
1. Each pattern class cj is represented by a prototype vector mj, typically the mean
vector of all training samples from that class:

.IN
C
N
SY
U
VT

37
 VT
U
SY
N
C
.IN

38
 .IN
C
PATTERN CLASSIFICATION USING MINIMUM-DISTANCE CLASSIFIER
N
The minimum-distance classifier performs effectively when the distance between the mean
SY

vectors of pattern classes is significantly greater than the variation or spread within each
class around its mean. This implies that the classes are tightly clustered and well separated,
leading to improved recognition accuracy.
U

In cases where each class's distribution forms a spherical "hypercloud" in an n-dimensional

pattern space, the classifier achieves optimal performance. This means that under such
VT

conditions, the average misclassification loss is minimized, making this method particularly
suitable for pattern recognition tasks.
A critical factor influencing the classifier’s success is the quality of the features used for
classification. Well-chosen features that offer high discrimination between classes
significantly enhance the classifier’s accuracy. For the minimum-distance method, this
specifically translates to having clearly separated class means and minimal within-class
variation.
A classic application of effective feature engineering with a simple classifier is demonstrated
by the Banker’s Association E-13B font system. In the 1940s, bank checks were processed
manually, which was inefficient and error-prone. With rising volumes in the 1950s, banks
sought automation. The E-13B font, developed in the mid-1950s, became the standard solution.

39
This font consists of 14 stylized characters arranged in a 9 × 7 grid, designed specifically to
maximize inter-character differences. While being compact and human-readable, the
primary goal was machine readability with high speed and accuracy. The success of this
system illustrates how engineered features, even with a simple classifier, can lead to high-
performance recognition systems.

.IN
C
N
SY
U
VT

40
 VT
U
SY
N
C
.IN

41