COMPUTER VISION (Module-5)

●
Morphological Image Processing
●
Feature Extraction
●
Image pattern Classification
Dr. Ramesh Wadawadagi
Associate Professor
Department of CSE
SVIT, Bengaluru-560064
[Link]@[Link]
Morphological Image Processing
● Mathematical morphology:

 It is a useful tool for extracting image components

in the representation of region shape.
Vignetting
 Ex. Boundaries, object skeletons, and convex hull.

 Set Theory is usually used to describe mathematical

morphology.
 Sets represent objects in a binary image.

 Black pixel: representing object (foreground),

denoted by 1.
 White pixel: representing background, denoted by 0.
Preliminaries
●Our interest in this chapter is sets in Z2, where
each element denotes the coordinates of an
object pixel.
●If a=(a1, a2), we write a∈A,Vignetting
if a is an element
in A.
●If a is not an element in A, a∉A.
●The null or empty set is denoted by ∅.
●We use braces, {·}, to specify the content of a
set.
●For example, C={w| w=-d, for d∈D}.
Operations on Sets
● A subset of B: AB
● Union of A and B: C=AB

● Intersection of A and B: D=AB

Vignetting
● Disjoint sets: AB= ∅

● Complement of A: Ac = {x|xA}

● Difference of A and B:

 A-B = {x|x∈A, xB} = A∩Bc

Operations on Sets

Vignetting
Operations on Sets
●
Reflection and Translation by examples:
●
Need for a reference point.
●
Reflection of : B^= {x| x=-b, forVignetting
b∈B}
● Translation of A by x=(x1,x2), denoted by (A)x is
B^

defined as: (A)x = {c| c=a+x, for a∈A}

Operations on Sets
● Reflection of : B^= {x| x=-b, for b∈B}
● That is, if B is a set of points in 2-D, then B̂is
the set of points in B whose (x, y) coordinates
have been replaced by (−x, −y).
Vignetting
B^
Operations on Sets
● Translation of A by x=(x1,x2), denoted by (A)z is
defined as: (A)z = {c| c=a+z, for a∈A}
●
That is, if A is a set of pixelsVignetting
in 2-D, then (A)z is
the set of pixels in A whose (x, y) coordinates
B^

have been replaced by (x+z1, y+z2).

Logic Operations Involving Binary Images
●
The logic operations discussed in this section
involve binary images.
●
Black pixel: 1, White pixel: 0.
Vignetting

Note: Logical operations are restricted to binary variables,

which is not the case in general for set operations.
Logic Operations Involving Binary Images

Vignetting
Dilation and Erosion
●
These two operations are fundamental to
morphological processing.
●
Dilation: Expands the boundaries
Vignetting
of an object
in an image.
●
Erosion: Shrinks the boundaries of an object
in an image.
Dilation
●
With A and B are sets in Z2, the dilation of A by B,
denoted A B, is defined as:
●
A B= Vignetting
●
Other interpretation: A B =
●
B is commonly referred to as the structuring element.
●
The dilation of A by B is the set of all displacements z,
such that the reflection of B and intersection of A with at
least one element.
The Illustration of Dilation
The Implementation of Dilation
●
Given a binary image f and the structuring element
s, construct a duplicate of f, denoted by g.
●
For each pixel p = f(x, y), do the following:
Vignetting
●
If p is black pixel:
●
- If p is at the boundary (any of the 4-adjacent
neighbors is white) of the object, center the
origin of s at (x, y) in g, and fill the pixels black
on which s covers.
●
Return g.
Applications of Dilation
• One of the simplest applications of dilation is for
bridging gaps.
Vignetting
Erosion
With A and B are sets in Z2,
the dilation of A by B,
denoted A B, is defined as
A B=
The erosion of A by B is
the set of all points z such
that B, translated by z, is
contained in A.
The Implementation of Erosion
●
Given a binary image f and the structuring element
s, construct a duplicate of f, denoted by g.
●
For each pixel p = f(x, y), do the following:
Vignetting
●
If p is white pixel:
●
- If p is adjacent to the boundary of the object,
center the origin of s at (x, y) in g, and fill the
pixels with white on which s covers.
●
Return g.
Applications of Erosion
• One of the simplest uses of erosion is for eliminating
irrelevant detail (in terms of size) from a binary image.

Vignetting

Note that objects are represented by white pixels, rather than

by black pixels.
Opening and Closing
Opening: To break narrow isthmuses and to
eliminate thin protrusions.
Vignetting

Closing: To fuse narrow breaks and long thin

gulfs, to eliminate small holes, and to fill gaps in
the contour.
Opening and Closing

Vignetting
Illustration of Opening and Closing

Vignetting
Applications of Opening and Closing

Vignetting
The Hit-or-Miss Transform
●
The morphological Hit-or-Miss Transform (HMT)
is a basic tool for shape detection.
●
Let I be a binary image composed
Vignettingof foreground

(A) and background pixels (Ac), respectively.

●
The HMT identifies specific shapes (patterns) in I.
●
The HMT utilizes two structuring elements: B1 for
detecting shapes in the foreground, and B2 for
detecting shapes in the background.
The Hit-or-Miss Transform
●
The HMT of image I is defined as:

Vignetting

●
The morphological HMT is the set of translations,
z, of structuring elements B1 and B2 such that,
simultaneously, B1 found a match in the foreground
(i.e., B1 is contained in A) and B2 found a match in
the background (i.e., B2 is contained in Ac).
The Hit-or-Miss Transform
●
The word “simultaneous” implies that z is the same
translation of both structuring elements.
●
The word “hit” in the HMT Vignetting
arises from the fact
that B1 finding a match in A (hitting).
●
The word “miss” in the HMT arises from the fact
that B2 finding a match in Ac is the same as B2 not
finding (missing) a match in A.
The Hit-or-Miss Transform
●
The Hit-or-Miss transform comprises three steps:
1) Apply Erosion to image A with structuring
element B1.
Vignetting
2) Apply Erosion to the complement of image A,
(Ac) with structuring element B2.
3) Perform AND resulting from step 1 and step 2.
4) The structuring elements B1 and B2 can be
combined into a single element B.
The Hit-or-Miss Transform

Vignetting
The Hit-or-Miss Transform

Vignetting

The location of the origin of D, as desired. The dots indicate

the origin of their respective components. Each dot is a single
pixel.
The Hit-or-Miss Transform
●
Figure 9.12(a) shows that I is composed of foreground
(A) and background pixels.
●
Figure 9.12(b) is Ic, the complement of I. The
foreground of Ic is defined as the set of pixels in Ac,
Vignetting
and the background is the union of the complement of
the three objects.
●
Figure 9.12(c) shows the two structuring elements
needed to detect D. Element B1 is equal to D itself. As
Fig. 9.12(d) shows, the erosion of A by B1 contains a
single point: the origin of D, as desired, but it also
contains parts of object C.
The Hit-or-Miss Transform
●
Structuring element B2 is designed to detect D in Ic.
Because D is composed of background elements in Ic,
and erosion works with foreground elements, B2 has to
be designed to detect the border of D, which is
Vignetting
composed of foreground pixels in Ic.
●
The SE in Fig. 9.12(c) does precisely this. It consists of
a rectangle of foreground elements one pixel thick.
●
The size of the rectangle is such that is encloses the
size of D.
The Hit-or-Miss Transform
●
Figure 9.12(e) shows (shaded) the erosion of the
foreground of Ic by B2.
●
It contains the origin of D, but is also contains parts of
sets Ac and C. (The outer shadedVignetting
area in Fig. 9.12(e) is
larger than shown; the result was cropped to the same
size as image I for consistency.)
●
The only elements that are common in Figs. 9.12(d)
and (e) is the origin of D, so the intersection of these
two sets of elements gives the location of that point, as
desired. Figure 9.12(f) shows the final result.
The HMT: Example

Vignetting
The HMT: Example

Vignetting
The HMT: Example

Vignetting
Some Basic Morphological Algorithms
●
Boundary Extraction
●
Region Filling
●
Extraction of connected components
Vignetting
●
Convex Hull
●
Thinning
●
Skeletons
●
Pruning
Boundary Extraction
●
The boundary of a set A, denoted by β(A), can be
obtained by first eroding A by B and then
performing the set difference between A and its
erosion. Vignetting
Boundary Extraction
●
Binary 1’s are shown in white and 0’s in black.
●
Using 5x5 structuring element would result in a boundary
between 2 and 3 pixels thick.

Vignetting

●
The structuring element in this example is 3x3; therefore,
the boundary is one pixel thick.
Region Filling
●
Goal: given a point p inside the boundary, fill the
entire region with 1’s.
● Let X = p. The filled set X can be obtained by:
0 k
Vignetting
The Procedure of Region Filling
● The algorithm terminates at iteration step k if Xk=Xk-1.
● The result is obtained from the union of Xk and the
boundary in A.
Vignetting
Extraction of Connected Components
●
Goal: given a point p, find the component that
connects to p.
● Let X = p. The set X can be obtained by
0 k
Vignetting

●
The algorithm terminates at iteration step k if
Xk=Xk-1.
● The result Y is obtained from Xk.
The Procedure of Finding Connected Components

Vignetting
Finding Connected Components: Example

Vignetting
Convex Hull
● The Convex Hull is the outer boundary of a
shape, where any straight line connecting two
points on the boundary lies entirely within the
shape.
● The Convex Hull operation creates a convex

polygon that completely encloses a given set of

points or pixels. Examples:

Convex Hull Not Convex Hull

Convex Hull
● The convex hull of a set of points S is the
smallest convex polygon H that encloses all
the points.
● Convex Hull of S is then:

● The smallest convex set H, containing S.

● H = {q1, q2…..q7} in the below example.

Convex Hull: Procedure
● Define Four basic structural elements,
Bi, i=1, 2, 3, 4

 X 0i  A (Original Image) Hit-or-Miss Transform

 X ki  X ki  B i   A i 1, 2, 3, 4 and k 1, 2, 3,
4
 C  A  D i , D i  X converged
i

i 1
Convex Hull
Convex Hull
● Shortcoming of above algorithm:
• - Grows more than minimum required

convex size.
• - Limit to vertical-horizontal expansion.
Thinning
● Thinning reduces a binary image to a
simplified, topologically equivalent
representation of given image, often resembling
a skeleton or a set of lines following the medial
axis of the original objects.
 A * B   A  A * B 
c
A  B A 
Another approach:
 B  B1 2
, B , , B n

A   B      A  B1
  B 2
 
  B n

Repeat until convergence
Thinning
Thickening
Thickening expands objects in a binary image
by adding pixels to their boundaries.
Skeletonization
● Skeletonization of A with notation S(A):
● If z be a point belong to S(A) and (D) the largest size
z
disk centered at z and contained in A, one cannot find
a larger disk containing (D)z and included in A.
● A disk (D)z satisfying these conditions is called a

maximum disk.
● If disk (D) touches the boundary of A at two or more
z
different points.
Skeletonization: Example
Skeletonization: Example

Skeleton
Skeletonization: Example
Skeletonization: Formulation
K
S  A  S k  A  k successive erosions
k 0

S k  A   AkB  
 AkB   B,  : Opening
 AkB    AB B B  : k times
K=max  k  AkB  
Reconstruction:
K
A=S k  A   kB 
k=0

 A  kB    A  B   B   B  : k times

Skeletonization: Formulation
Pruning
● Removes unwanted branches or spurs from
lines objects in an image.

Thinning for edge

removal
HMT for end point
detection

Dilation
Pruning
Pruning
Iteratively prune an image:
Pruning
Solve a maze puzzle by thinning all paths and pruning dead ends:
Feature Extraction
● Feature extraction in Image Processing is the process by
which certain features of interest within an image are
detected and represented for further processing.
● It is a critical step in most computer vision and image
processing solutions, because it marks the transition from
pictorial to non-pictorial (alphanumerical, usually
quantitative) data representation.
● The resulting representation can be subsequently used as an
input to a number of pattern recognition and classification
tasks, which will then label, classify, or recognize the
semantic contents of the image or its objects.
Feature Extraction
● Feature Extraction is the process of identifying and
extracting key information, from an image to be used in
further analysis or tasks like classification, recognition, or
object detection.
● These features can represent various aspects of an image,

such as edges, shapes, textures, or colors.

● Feature extraction consists of feature detection and feature

description.
● Feature detection refers to finding the features in an

image, region, or boundary.

● Feature description assigns quantitative attributes to the

detected features.
● For example, we might detect corners in a region boundary,

and describe those corners by their orientation and

location, both of which are quantitative attributes.
Feature Description
●
Feature Description means quantifying the representation of an
object.
●
Boundary Descriptors

Use geometrical descriptors: Diameter, Perimeter, Eccentricity,
Curvature

Shape Numbers

Fourier Descriptors

Statistical Moments
●
Regional Descriptors

Use geometrical descriptors: Area, Compactness, Euler number

Texture

Moments of 2D Functions
Desirable properties of descriptors
●
They should define a complete set:

Two objects must have the same descriptors if and only if they have
the same shape.
●
They should be invariant to Rotation, Scaling and Translation (RST)
●
They should be a compact set (Feature Selection):

A descriptor should contain only information about what makes an
object unique, or different from the other objects.

The quantity of information used to describe this characterization
should be less than the information necessary to have a complete
description of the object itself.
●
They should be robust:

Work well against Noise and Distortion

They should have low computational complexity
Feature Representation
● The common goal of feature extraction and representation
techniques is to convert the segmented objects into
representations that better describe their features and attributes.
● The Type and Complexity of the resulting representation depend
on many factors, such as:
 The type of image (e.g., binary, gray-scale, or color),
 The level of granularity (entire image or individual regions)
desired, and
 The context of the application that uses the results (e.g., a two-
class pattern classifier that tells circular objects from noncircular
ones or an image retrieval system that retrieves images judged to
be similar to an example image).
Feature Representation
●
Feature Representation means that we make the
object information more accessible for computer-
interpretation and Processing.
●
Two types of representation
●
Using boundary (External characteristics)
●
Using pixels of region (Internal characteristics)
Feature Vectors & Vector Spaces
● A feature vector is a n × 1 array that encodes the n features
(or measurements) of an image or object.
● The array contents may be symbolic (e.g., a string containing
the name of the predominant color in the image), numerical
(e.g., an integer expressing the area of an object, in pixels), or
both.
● Mathematically, a numerical feature vector x is given by:

● where n is the total number of features.

Feature Vectors & Vector Spaces
● The feature vector is a compact
representation of an image (or
object within the image), which
can be associated with:
● The notion of a feature space,
● An n-dimensional hyperspace
that allows the visualization (for
n < 4) and
● Interpretation of the feature
vectors’ contents, their relative
distances, and so on.
Invariance & Robustness
● A common requirement for feature extraction and
representation techniques is that the features used to
represent an image be invariant to Rotation, Scaling,
and Translation, collectively known as RST.
● RST invariance ensures that a machine vision system
will still be able to recognize objects even when they
appear at different size, position within the image,
and angle (relative to a horizontal reference).
Boundary Descriptors
● In this section, we will look at Contour-based
representation and description techniques.
● They are also called as External Descriptors.
● These techniques assume that the contour (or boundary) of
an object can be represented in a convenient coordinate
system (Cartesian-the most common, polar, or tangential)
and rely exclusively on boundary pixels to describe the
region or object.
● Object boundaries can be represented by different
techniques, ranging from simple polygonal approximation
methods to more elaborated techniques involving piecewise
polynomial interpolations such as B-spline curves.
Boundary Following (Tracing)
● The techniques described in this section assume that the
pixels belonging to the boundary of the object (or region) can
be traced, starting from any background pixel, using an
algorithm known as bug tracing that works as follows:
 As soon as the conceptual bug crosses into a boundary
pixel, it makes a left turn and moves to the next pixel.
 If that pixel is a boundary pixel, the bug makes another left
turn, otherwise it turns right; the process is repeated until
the bug is back to the starting point.
 As the conceptual bug follows the contour, it builds a list of
coordinates of the boundary pixels being visited.
Boundary Following (Assumptions)
We assume:
● (1) That we are working with binary images in which object
and background points are labeled 1 and 0, respectively; and
● (2) That images are padded with a border of 0’s to eliminate
the possibility of an object merging with the image border.
● For clarity, we limit the discussion to single regions.
● The approach is extended to multiple, disjoint regions by
processing the regions individually.
● The following algorithm traces the boundary of a 1-valued
region, R, in a binary image.
Boundary Following (Algorithm)
Boundary Following (Algorithm)
Chain Codes
● Chain codes are used to represent a boundary by a connected
sequence of straightline segments of specified length and
direction.
● We assume that all curves are closed, simple curves.
● In this subsection, we discuss the following two chain-code
techniques.
● Freeman Chain Codes
● Slope Chain Codes
Freeman Chain Codes
● Typically, a chain code representation is based on 4- or 8-
connectivity of the segments.
● The direction of each segment is coded by using a numbering
scheme, as in figure below.
● A boundary code formed as a sequence of such directional
numbers is referred to as a Freeman chain code.
Freeman Chain Codes
● Digital images usually are acquired and processed in a small
grid format with equal spacing in the x- and y-directions.
● A chain code is generated by following a boundary in, say, a
clockwise direction and assigning a direction to the
segments connecting every pair of pixels.
● This level of detail generally is not used for two principal
reasons:
● (1) The resulting chain would be quite long and
● (2) Any small disturbances along the boundary due to noise
or imperfect segmentation would cause changes in the code
that may not be related to the principal shape features of the
boundary.
Freeman Chain Codes
● An approach used to address these problems is to resample
the boundary by selecting a larger grid spacing, as in figure
below.
● Then, as the boundary is traversed, a boundary point is
assigned to a node of the larger grid, depending on the
proximity of the original boundary point to that node.
Freeman Chain Codes
● The resampled boundary obtained in this way can be
represented by a 4- or 8-code.
● Figure 11.4(c) shows the larger boundary points represented
by an 8-directional chain code.
● The numerical value of a chain code depends on the starting
point.
● Treat the chain code as a circular sequence of direction
numbers and redefine the starting point so that the resulting
sequence of numbers forms an integer of minimum
magnitude.
Freeman Chain Codes Example
Freeman Chain Codes Example
● Figure 11.5(d) is the outer boundary of the region in Fig.
11.5(c).
● Obtaining the chain code of this boundary directly would
result in a long sequence with small variations that are not
representative of the global shape of the boundary, so we
resample it before obtaining its chain code.
● This reduces insignificant variability.
● Figure 11.5(e) is the result of using a resampling grid with
nodes 50 pixels apart (approximately 10% of the image
width) and Fig. 11.5(f) is the result of joining the sample
points by straight lines.
● The 8-directional Freeman chain code of the simplified
boundary is: 00006066666666444444242222202202
Normalized Freeman Chain Codes
● We can normalize also for rotation by using the first
difference of the chain code instead of the code itself.
● This difference is obtained by counting the number of
direction changes (in a counterclockwise direction in Fig.
11.3) that separate two adjacent elements of the code.
● If we treat the code as a circular sequence to normalize it
with respect to the starting point, then the first element of the
difference is computed by using the transition between the
last and first components of the chain.
● The 8-directional Freeman chain code of the simplified
boundary is: 00062600000006000006260000620626
Steps used in Normalized Chain Codes
● Calculate the chain code
● Calculate the circular first difference
● Calculate normalized chain code by using the transition
between the last and first components of the chain.
● Example:
0

2 6
0

2 6

4 4
Step 1. Chain Code: 06064422
Steps used in Normalized Chain Codes
0

2 6
0

2 6

4 4

Step 2: Chain Code: 06064422

Circular first difference: 62660616

Step 3: Normalized circular first difference: 06166266

Exercise Normalized Chain Codes

Step 2: Chain Code:

Circular first difference:
Step 3: Normalized circular first difference:
Slope Chain Codes
● Using Freeman chain codes generally requires resampling a
boundary to smooth small variations, a process that implies
defining a grid and subsequently assigning all boundary
points to their closest neighbors in the grid.
● An alternative to this approach is to use slope chain codes
(SCCs).
● The SCC of a 2-D curve is obtained by placing straight-line
segments of equal length around the curve, with the end
points of the segments touching the curve.
● Obtaining an SSC requires calculating the slope changes
between contiguous line segments, and normalizing the
changes to the continuous (open) interval (−1, 1).
Slope Chain Codes
● This approach requires defining the length of the line
segments, as opposed to Freeman codes, which require
defining a grid and assigning curve points to it—a much
more elaborate procedure.
● Like Freeman codes, SCCs are independent of rotation, but a
larger range of possible slope changes provides a more
accurate representation under rotation than the rotational
independence of the Freeman codes, which is limited to the
eight directions in Fig. 11.3(b).
● As with Freeman codes, SCCs are independent of
translation, and can be normalized for scale changes.
Slope Chain Codes
● Figure 11.6 illustrates how an SCC is generated.
● The first step is to select the length of the line segment to use
in generating the code [see Fig. 11.6(b)].
● Next, a starting point (the origin) is specified (for an open
curve, the logical starting point is one of its end points).
● As Fig. 11.6(c) shows, once the origin has been selected, one
end of a line segment is placed at the origin and the other
end of the segment is set to coincide with the curve.
● This point becomes the starting point of the next line
segment, and we repeat this procedure until the starting point
(or end point in the case of an open curve) is reached.
Slope Chain Codes
Slope Chain Codes
● Once the intersections of the circles are known, we
determine the slope changes between contiguous line
segments.
● Positive and zero slope changes are normalized to the open
half interval [0, 1), while negative slope changes are
normalized to the open interval (−1, 0).
● The sequence of slope changes is the chain that defines the
SCC approximation to the original curve.
● For example, the code for the curve in Fig. 11.6(e) is 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.