Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Pattern Classification
Lecture 02: Feature Extraction

Kundan Kumar
[Link]

c 2020 Kundan Kumar, All Rights Reserved

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Topics to be covered
 Boundary Representation
 Boundary (Border) following
 Chain codes
 Polynomial Approximation
 Signatures
 Boundary Segments
 Skeletons
 Boundary Descriptors
 Some Simple Descriptors
 Shape Numbers
 Fourier Descriptors
 Statistical Moments
 Regional Descriptors
 Texture: Moment Invariants
 Texture: GLCM, LBP
 Transformed domain features
 2D-Gabor filter features
1/61 Kundan Kumar Pattern Classification
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Introduction to feature extraction

 Scale invariant
 Translation invariant
 Rotation invariant
 Luminance invariant

2/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Feature extraction from an ECG signal

3/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References
Speech Feature Models
Good features and Bad features Capture Extraction

 Extract features which are good for classification. Pattern

Matching
 Good features:
 Objects from the same class have similar feature values
 Objects from different classes have different values. Process
Text
Results
 Bad Features: features simply do not contain the information needed to separate
the classes, doesn’t matter how much effort you put into designing the classifier.

x x
x
xx x
x x x x
x xx
xx x x
x x
x

"Good" features "Bad" features

4/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Feature separability

x x
xx x x
x x x x
x xx
xx x x
x x
x

"Good" features "Bad" features

x x
x x x
xx xx xx
x x x
xx
x
x xx
xx x xx x xx
x x
x x x x x x
x x
Linear Non-linear Highly
Multi-modal
separability separability correlated

5/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Nature of separating plane?

 For 2 dimensional feature space – line
 For 3 dimensional feature space – plane
 For more than 3 dimensional feature space – hyperplane

6/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Labeled features


f1 
f2 ∈ C1
f3


f4 

f5

∈ C2
f6 

f7


 In general, we use labeled features for supervised learning.

7/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Some property of features

 The mapping from pattern to features that is unique whereas mapping from feature
vector to pattern is not immediate.
 So many patterns may be matched to the same feature of vector.
 In pattern recognition, we never talk about a single pattern. We always talk about
feature vector.

Types of Boundary Features:

1. Boundary features/Descriptors
2. Region features/Descriptors

8/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Boundary Representation

Memorially : This is the

testingpage
.

I I. il
FAX
''

n .

L l

9/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Binary Images

Figure: Binary Images

10/61 Kundan Kumar Pattern Classification
 border.
Feature For convenience,
Extraction Boundarywe limit the discussion
Representation to is
that single
Boundary regions.
labeled
Descriptors TheRegional
1. Denoteapproach
c0 theis west
byDescriptors neighbor of b0 [seeReferences
TD Features Fig. 11.1(
extended to multiple, disjoint regions by processing
Clearly, thec0regions
alwaysindividually.
is a background point. Examine the 8-neighbor
Boundary
Given a binary (Border)
region R or algorithm
its boundary, an
b0,algorithm
starting atfor c0following the bor-in a clockwise direction. Let b1 den
and proceeding
der of R, or the given boundary, consists of the the following steps:encountered whose value is 1, and let c1 be the (b
first neighbor
 Assume a binary image in which ground)
object point
andimmediately
background preceding
points areb1 inlabeled
the sequence.
1 and Store
0, the l
†
1. Let the starting point, b0, be the uppermost,tions ofleftmost
b0 andpoint in the
b1 for use in image
Step 5.
thatrespectively.
is labeled 1. Denote by c0 the west
2. Letneighbor
b = b1 of b0c[see
and = cFig. 11.1(b)].
1 [see Fig. 11.1(c)].
 Assume images is aare padded with the border of 0s
Clearly, c0 always background [Link].
Let Examine
the the
8-neighbors ofto avoid of
8-neighbors
b, starting object
at c andmerging
proceeding with in athe
clockwise di
b0, image at c0 and proceeding in a clockwise
startingborder direction.
tion, be denoted by n Let b denote
1, n2,1 Á , n8. Find the first nk labeled 1.
the first neighbor encountered whose value is 1, and let c1 be the (back-
ground) point immediately preceding b1 in the sequence. Store the loca- c c
tions of b0 and b1 for use in Step 5. 1 1 1 1 c0 b0 1 1 1 b 1 1 b 1
2. Let b = b1 and c = c1 [see Fig. 11.1(c)]. 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
3. Let the 8-neighbors of b, starting at c and1
proceeding
1
in
1
a clockwise
1
direc-
1 1 1 1
tion, be denoted by n1, n2, Á , n8. Find1the 1 nk labeled
1 1first 1 1 1.1 1 1 1 1 1 1 1 1 1 1

c c
1 1 1 1 c0 b0 1 1 1
a b c d e
b 1 1 b 1
1 1 1 1 1 FIGURE
1 11.11 Illustration
1 of the first few steps in the boundary-following algorithm
1 1 1 1 1 point
1 1
to be processed 1 next is labeled in black, the points yet to be processed are
1 1 1 1 1 1 the points
and 1 found 1by the algorithm are labeled as gray squares.
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

†
As you will see later in this chapter, the uppermost, leftmost point in a boundary has the impo
a b c d e property thatKumar
11/61
Figure: Illustration of the Kundan
first fewasteps
polygonal approximation to the boundary has a convex vertex
in the boundary-following algorithm at that
Pattern location. Als
Classification
left and north neighbors of the point are guaranteed to be background points. These properties m
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Boundary algorithm (Moore boundary tracking algorithm)

1. Let the starting point, b0 be the uppermost, leftmost point in the image that is labeled 1. Denote
by c0 the west neighbor of b0 . Clearly, c0 always is a background point. Examine the 8-neighbors
of b0 , starting at c0 and proceeding in a clockwise direction. Let b1 denote the first neighbor
encountered whose value is 1, and let c1 be the (back-ground) point immediately preceding b1 in
the sequence. Store the locations of b0 and b1 for use in Step 5.
2. Let b = b1 and c = c1 .
3. Let the 8-neighbors of b, starting at c and proceeding in a clockwise direction, be denoted by
n1 , n2 , . . . , n8 . Find the first nk labeled 1.
4. Let b = nk and c = nk−1
5. Repeat Step 3 and 4 until b = b0 and the next boundary point found in b1 . The sequence of b
points found when the algorithm stops constitutes the set of ordered boundary points.

12/61 Kundan Kumar Pattern Classification

 original region.
Feature Extraction
Boundary Representation Boundary Descriptors Regional Descriptors TD Features References
We could have stated the algorithm just as easily based on following a
Boundary
boundary inalgorithm - stoppingdirection.
the counterclockwise criterionIn fact, you will encounter algo-
rithms formulated on the assumption that boundary points are ordered in that

1 c0 b0 c
1 1 1 1 1 b
1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1

Figure:
a b cIllustration of an erroneous result when the stopping rule is such that boundary-following stops when the
starting point, b0 , is encountered again
FIGURE 11.2 Illustration of an erroneous result when the stopping rule is such that
boundary-following stops when the starting point, b0, is encountered again.

13/61 Kundan Kumar Pattern Classification

 theBoundary
sampling
Feature Extraction
grid.
Representation Boundary Descriptors Regional Descriptors TD Features References
The chain code of a boundary depends on the starting point. However, the
Boundarycoderepresentation:
can be normalized Chain Codesto the starting point by a straightfor-
with respect
ward procedure: We simply treat the chain code as a circular sequence of di-
rection
 In order numbersa boundary,
to represent and redefineit is the
useful starting point the
to compact so raw that data
the (list
resulting
of
sequence
boundary pixels) of numbers forms an integer of minimum magnitude. We can nor-
 Chainmalize
codes:also
list for rotation (in
of segments angles
with that are
defined integer
length and multiples
direction of the directions
in Fig. 11.3) by using
 4-directional chain codes the first difference of the chain code instead of the code
 8-directional chain codes
b 1 2
3 1
URE 11.3
ection
mbers for 2 0 4 0
4-directional
in code, and
8-directional 5 7
in code.
3 6

Figure: Direction numbers for (a) 4-directional chain code, and (b) 8-directional chain code

14/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation rection numbers
Boundary and redefineRegional
Descriptors the starting point so thatTDthe
Descriptors resulting
Features References
sequence of numbers forms an integer of minimum magnitude. We can nor-
malize also for rotation (in angles that are integer multiples of the directions
Boundary representation: Chain Codes in Fig. 11.3) by using the first difference of the chain code instead of the code

 It may be usefula bto downsample the data before

1 computing the
2 chain code
 to reduce theFIGURE
code dimension
11.3
3 1


Direction 11.1 ■ Representation 799
to remove small detail
numbers for along the boundary
2 0 4 0
(a) 4-directional
0 a b c
chain code, and
(b) 8-directional 2 5 7
7 FIGURE 11.4
chain code. 1 (a) Digital
3 66
boundary with
2 6
resampling grid
1 6 superimposed.
(b) Result of
2 6
resampling.
6 (c) 8-directional
3
chain-coded
3 5 4 boundary.

Figure: (a) Digital boundary with resampling grid superimposed, (b) Result of resampling, (c) 8-directional
chain-coded boundary.
itself. This difference is obtained by counting the number of direction
changes (in a counterclockwise direction in Fig. 11.3) that separate two adja-
 Can you draw cent elements of the
4-directional code. For instance,
chain-coded the first difference of the 4-direction
boundary?
chain code 10103322 is 3133030. If we treat the code as a circular sequence to
normalize with respect to the starting point, then the first element of the dif-
ference is computed by using the transition between the last and first com-
15/61 Kundan Kumar Pattern Classification
ponents of the chain. Here, the result is 33133030. Size normalization can be
sequence of numbers forms
Feature Extraction an integer
Boundary of minimum magnitude.
Representation Boundary We can nor-
Descriptors Regional Descriptors TD Features References
malize also for rotation (in angles that are integer multiples of the directions
Boundary representation: Chain Codes
in Fig. 11.3) by using the first difference of the chain code instead of the code
Digital Image Processing, 2nd ed. [Link]
1 2

Chapter 11
3 1

Chain code: 0033333323221211101101

Representation & Description
2 0 4 0

5 7
3 6

© 2002 R. C. Gonzalez & R. E. Woods

16/61 Kundan Kumar Pattern Classification
Feature Extraction large
Boundary grid, depending
Representation onBoundary
the proximity
Descriptorsof the original
Regional boundary
Descriptors to that node,
TD Features References
as in Fig. 11.4(b). The resampled boundary obtained in this way then can be
Boundary representation: Differential Chain Code
represented by a 4- or 8-code. Figure 11.4(c) shows the coarser boundary
points represented by an 8-directional chain code. It is a simple matter to
convert from an 8-code to a 4-code, and vice versa (see Problems 2.12 and 2.13).
 The chain code The of a boundary
starting point in [Link] on the starting
11.4(c) is (arbitrarily) [Link] point
at the topmost,
 normalize ofwith
the respect
boundary,to the gives
which starting point
the chain (circular
code 0766 Á sequence)
12. As might be expected,
the accuracy
 the new starting pointofisthethe
resulting
one who codegives
representation
a sequence depends on the spacing
of numbers givingofthe
the sampling grid.
smallest/largest integer.
The chain code of a boundary depends on the starting point. However, the
 Normalize with coderespect to rotation:
can be normalized with respect to the starting point by a straightfor-
 First difference can be used
ward procedure: We simply treat the chain code as a circular sequence of di-
rection⇒numbers
 E.g., 10103322 3133030and redefine CCW)
(counting the starting point sothe
and adding thatlastthetransition
resulting (circular
sequence: sequence
2 ⇒ 1) of numbers forms an integer of minimum magnitude. We can nor-
malize also for rotation (in angles that are integer multiples of the directions
⇒ 31330303 (Differential
in Fig. 11.3) by using Chain Code)
the first difference of the chain code instead of the code
⇒ 03033133 (Independent of starting point, i.e., rotation invariant)
a b 1 2
3 1
FIGURE 11.3
Direction
numbers for 2 0 4 0
(a) 4-directional
chain code, and
(b) 8-directional 5 7
chain code.
3 6
17/61 Kundan Kumar Pattern Classification
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Differential Chain Code 11.1 ■ Representation

0 a b c
2 7
FIGURE 11.4
1 6 (a) Digital
boundary wi
2 6
resampling g
1 6 superimpose
(b) Result of
2 6
resampling.
6 (c) 8-directio
3
chain-coded
3 5 4 boundary.

Can you write the Differential Chain Code?

 Chain code:
itself. This0766666453321212
difference is obtained by counting the number of direction
changes (in
 Differential a counterclockwise
chain direction in Fig. 11.3) that separate two adja-
code: 7700006160771716
cent elements of the code. For instance, the first difference of the 4-direction
 Differential chain code (rotation invariant): 0000616077171677
chain code 10103322 is 3133030. If we treat the code as a circular sequence to
normalize
18/61 with respect to the Kundan
starting
Kumarpoint, then the first element of the dif-
Pattern Classification
 References

Pattern Classification

11.1 ■ Representation 799

TD Features

a b c
Is the differential chain code is invariant to rotation at any angle? (HW)

FIGURE 11.4
(a) Digital
boundary with
resampling grid
superimposed.
(b) Result of
Regional Descriptors

resampling.
(c) 8-directional
chain-coded
Differential chain code: 0000616077171677 (validated)

boundary.11.1 ■ Repres
0 a
2 7
d by counting the number of direction FIG
1 6 (a
rection in Fig. 11.3) that separate two adja-
Boundary Descriptors

Differential chain code: 7171677000061607

bo
ance, the first difference of the 4-direction 2 6
re

Kundan Kumar
Can you write the Differential Chain Code?

we treat the code as a circular sequence 1 to

Differential Chain Code: Validation

6 su
ting point, then the first element of the dif- (b
2 6
transition between the last and first com- re
sult is 33133030. Size normalization can be 6 (c
Chain code: 0707065444442311
3
ch
e resampling grid. 3 5 4 bo
only if the boundaries themselves are in-
s that are integer multiples of the directions
Boundary Representation

hich seldom is the case in practice. For in- 2

erence is obtained by counting the number of direction 1
two different orientations will have differ-
,unterclockwise
with the degree direction in Fig. 11.3) being
of dissimilarity that separate two adja-
2
f theeffect
This [Link],
reducedthe by first difference
selecting chain of the 4-direction 1
3322 is 3133030. If we treat the code as dig-
on to the distance between pixels in the a circular sequence to

19/61
respect
he to the starting
resampling grid alongpoint,
the then the first
principal axeselement of the dif-
2
utedinby
sed using11.2.2,
Section the transition
or along between the last and first com-
its eigen axes, 3
hain. Here, the result is 33133030. Size normalization can be
3
ering the size of the resampling grid.
Feature Extraction

lizations are exact only if the boundaries themselves are in-

on570, 8-bitingray-scale
(again, angles thatimage of a multiples
are integer circular of EXAMPLE 11.1:
the directions


d fragments.
scale The which
change,
itself. This objective of this
seldom
difference example
the case isby
is isobtained Freeman
in practice.
countingFor chain
thein-numb
code and some of
e,object
thechanges
integer
digitizedof in
(in minimum magnitude,
two different
a counterclockwise and will
orientations
direction have11.3)
differ-
itsinvariations.
Fig. that se
undary
shapes centofelements
in the largest
general, object
with
of the the indegree
code. Fig.
For11.5(a).
of dissimilarity
instance, being
the first difference o
Feature Extraction Boundary Representation Boundary Descriptors
11.1.3 Polygonal Approximations Using Minimum-Perimeter
Regional Descriptors TD Features References
Polygons

Polygonal Approximation A digital boundary can be approximated with arbitrary accuracy by a polygon.
For a closed boundary, the approximation becomes exact when the number of
segments of the polygon is equal to the number of points in the boundary so that
each pair of adjacent points defines a segment of the polygon. The goal of a
polygonal approximation is to capture the essence of the shape in a given bound-
 A digital boundary can be approximated with arbitrary accuracy by a polygon.
ary using the fewest possible number of segments. This problem is not trivial in
general and can turn into a time-consuming iterative search. However, approxi-
mation techniques of modest complexity are well suited for image processing
 In practice, the goal of polygonal approximation is to capture the “essence” of the boundary
tasks. Among these, one of the most powerful is representing a boundary by a
minimum-perimeter polygon (MPP), as defined in the following discussion.
shape with the fewest Foundation
possible polygonal segments.
 Minimum-perimeter polygon
An intuitively appealing approach for generating an algorithm to compute
MPPs is to enclose a boundary [Fig. 11.6(a)] by a set of concatenated cells, as
 Splitting techniquein Fig. 11.6(b). Think of the boundary as a rubber band. As it is allowed to
shrink, the rubber band will be constrained by the inner and outer walls of

a b c

Figure: (a) An object boundaryFIGURE 11.6 (a) An object boundary (black curve). (b) Boundary enclosed by cells (in gray). (c) Minimum-
(black
perimeter polygoncurve). (b) theBoundary
obtained by allowing boundary to [Link]
The vertices of theby cells
polygon (inbygray). (c) Minimum-perimeter
are created
the corners of the inner and outer walls of the gray region.
polygon obtained by allowing the boundary to shrink. The vertices of the polygon are created by the corners of
the inner and outer walls of the gray region.

20/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation
will be Boundary
either a convex orDescriptors
a concave vertex,Regional
with theDescriptors TD Features
angle of a vertex being an References
interior angle of the 4-connected boundary. Convex and concave vertices are
Polygonal Approximation: Minimum-Perimeter Polygon

a b c
Figure: (a) Region (dark gray) resulting from enclosing the original boundary by cells. (b) Convex (white dots)
and concaveFIGURE
(black11.7 (a) Region
dots) vertices(dark gray) resulting
obtained from enclosing
by following the original
the boundary boundary
of the dark by cells
gray (see Fig.
region in 11.6).
the
(b) Convex (white dots) and concave (black dots) vertices obtained by following the boundary of the dark
counterclockwise direction.
gray region (c) Concave vertices
in the counterclockwise direction.(black dots)vertices
(c) Concave displaced todots)
(black theirdisplaced
diagonalto mirror locations in the
their diagonal
outer wall ofmirror
the bounding
locations inregion; the
the outer convex
wall of the vertices
bounding are notthe
region; changed. The MPP
convex vertices are not(black boundary)
changed. The MPP is
superimposed(black
for boundary)
[Link] superimposed for reference.

21/61 Kundan Kumar Pattern Classification

 dure terminates with the polygon in Fig. 11.9(d).
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References
11.1.5 Signatures
Polygonal Approximation: Splitting
A signature is a 1-D Technique
functional representation of a boundary and may be gen-
erated in various ways. One of the simplest is to plot the distance from the cen-
troid to the boundary as a function of angle, as illustrated in Fig. 11.10.
 One approach toRegardless
boundary of howsegment
a signaturesplitting
is generated,is to subdivide
however, a issegment
the basic idea to re- successively
duce the boundary representation to a 1-D function that presumably is easier
into two part until a specified
to describe criterion
than the original is satisfied.
2-D boundary.

a b c
a
c d
FIGURE 11.9
(a) Original
boundary. d b
(b) Boundary
divided into
segments based
on extreme c c
points. (c) Joining a a
of vertices.
(d) Resulting
polygon.
d b d b

Figure: (a) Original boundary, (b) Boundary divided into segments based on extreme points, (c) Joining of
vertices, (d) Resulting polygon

22/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Polygonal Approximation: Splitting Technique

 For a closed boundary, the best starting points usually are two farthest points in the
boundary.
 Farthest point can be obtained by Karhunen-Loeve transform (KLT).
 The maximum perpendicular distance from a boundary segment to the line joining
its two end points not exceed a preset threshold.
 Splitting procedure with a threshold equal to 0.25 times the length of line ab.

23/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Signatures
 A signature is a 1-D representation of a boundary (which is a 2-D thing): it should
be easier to describe.
e.g., distance form the centroid vs angle. 11.1 ■ Representation 809

a b
FIGURE 11.10
r r
u u Distance-versus-
angle signatures.
In (a) r(u) is
constant. In
(b), the signature
A A consists of
repetitions of the
r(u) r(u) pattern
r(u) = A sec u for
2A 0 … u … p>4 and
r(u) = A csc u for
A A
p>4 6 u … p>2.

0 p p 3p 5p 3p 7p p p 3p 5p 3p 7p
p 2p 0 p 2p
4 2 4 4 2 4 4 2 4 4 2 4
u u

Figure: Distance-versus-angle signatures.

Signatures (a)
generated by r(θ), is constant,
the approach (b)are
just described the signature
invariant consists of repetitions of
to trans-
the pattern r(θ) = Asec(θ) forbut
lation, 0≤theyθdo π/4 and
≤depend r(θ) and
on rotation = Acsc(θ) for π/4 <
scaling. Normalization ≤ π/2
withθ respect
24/61 to rotation can be achieved
Kundan by finding a way to select the same starting point
Kumar Pattern Classification
to generate the signature, regardless of the shape’s orientation. One way to do
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Signatures

 Signatures are invariant to translation, but variant to rotation.

 Invariant to rotation: depends on the starting point

 the starting point could be the farthest point from the centroid.

 Scaling varies the amplitude of the signature

 invariance can be obtained by normalizing between 0 and 1, or
 by dividing by the variance of the signature (does not work on circle)

25/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Boundary Segments

 Decomposing a boundary into segments often is useful.

 Decomposition reduces the boundary’s complexity and thus simplifies the
description process.
 In this case use of the convex hull of the region enclosed by the boundary is a
powerful tool for robust decomposition of the boundary.

26/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Boundary Segments
 Convex hull H of an arbitrary set S is the smallest convex set containing S.
segments of the boundary. A more rugged technique is to use a polygonal ap-
 The set difference
proximation S istocalled
H − prior theconvex
finding the convex deficiency
deficiency of a region.D of digital
Most the set S.
boundaries of interest are simple polygons (recall from Section 11.1.3 that
 Note that in principle, this scheme
these are polygons is independent
without self-intersection). Grahamof
andregion size
Yao [1983] give and
an orientation.
algorithm for finding the convex hull of such polygons.

a b
FIGURE 11.12
(a) A region, S,
and its convex
S deficiency
(shaded).
(b) Partitioned
boundary.

Figure: (a) A region, S, and its convex deficiency (shaded). (b) Partitioned boundary.

27/61 Kundan Kumar Pattern Classification

 follows. For each point p in R, we find its closest neighbor in B. Thus, p has
Ifone more
iteration of the thinning algorithm consists of (1) applying Step 1 to
Feature Extraction Boundary Representation
than one such neighbor, it is said toBoundary
belong toDescriptors Regional
the medial axisflag(skeleton)
border points for Descriptors
ofdeletion;
R. TD
(2) deleting the flagged points; (3) Features
applying Step 2 References
to flag the remaining border points for deletion; and (4) deleting the flagged
The concept of “closest” (and the resulting MAT) depend [Link] definition
basic procedure of is applied iteratively until no further points are delet-

Skeletonization a distance (see Section 2.5.3). Figure 11.13 shows some examples
clidean distance. The same results would be obtained with the
ed, at which
using
maximum
8-neighbors
timethethe algorithm
Eu- terminates, yielding the skeleton of the region.
Condition (a) is violated when contour point p1 has only one or seven
valued [Link] only one such neighbor implies that p1 is the end
of Section 9.5.7. point of a skeleton stroke and obviously should not be deleted. Deleting p1 if it
had seven such neighbors would cause erosion into the region. Condition (b) is
The MAT of a region has an intuitive definition based violated on the whenso-called
it is applied to points on a stroke 1 pixel thick. Hence this condi-
 One way to represent a shape is to reduce it to a graph, by obtaining its skeleton
“prairie fire concept.” Consider an image region as a prairie tionofprevents
uniform,breaking drysegments of a skeleton during the thinning operation.
Conditions (c) and (d) are satisfied simultaneously by the minimum set of val-
grass, and suppose that a fire is lit along its border. All fire fronts will advance
ues: (p4 = 0 or p6 = 0) or (p2 = 0 and p8 = 0). Thus with reference to the
via thinning (skeletonization)
into the region at the same speed. The MAT of the region isneighborhood
the set ofarrangement
points in Fig. 11.14, a point that satisfies these conditions,
as well as conditions (a) and (b), is an east or south boundary point or a north-
reached by more than one fire front at the same time. west corner point in the boundary. In either case, p1 is not part of the skeleton
 MAT (Medial axis transformation) is composed by all the points which have more and should
Although the MAT of a region yields an intuitively pleasing skeleton, di- be removed. Similarly, conditions (c¿) and (d¿) are satisfied simulta-
neously by the following minimum set of values: (p2 = 0 or p8 = 0) or
rect implementation of this definition is expensive computationally. Imple-
than one closest boundary points (“prairie fire concept”)
mentation potentially involves calculating the distance from
(p4 = 0 and p6 =
southeast
everycorner
0). These correspond to north or west boundary points, or a
point. Note that northeast corner points have p2 = 0 and
interior
p4 = 0 and thus satisfy conditions (c) and (d), as well as (c¿) and (d¿). The same
is true for southwest corner points, which have p6 = 0 and p8 = 0.

FIGURE 11.16
a b c Human leg bone
and skeleton of
the region shown
FIGURE 11.13 superimposed.
Medial axes
(dashed) of three
simple regions.

(a) (b)

Figure: (a) Medial axes (dashed) of three simple regions,(b) Human leg bone and skeleton of the region

28/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Boundary Features/Descriptors

29/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Simple descriptors
 length of a boundary is one of its simplest descriptors.
 The number of pixels along a boundary gives a rough approximation of its length.
 For a chain coded curve with unit spacing:
√
length = Horizontal + Vertical + 2 × Diagonal
 diameter (length of the major axis)

Diam(B) = max [D(pi , pj )]

i,j

 The minor axis of a boundary is defined as the line perpendicular to the major axis.
 Basic rectangle (formed by the major and the minor axis; encloses the boundary)
and its
major axis
eccentricity =
minor axis
30/61 Kundan Kumar Pattern Classification
 computed by treating the chain code as a circular sequence, as discussed in
Feature Extraction Boundary Representation principal shape Regional
Boundary Descriptors features Descriptors
of the boundary. TD Features References
Section 11.1.2. Although the first difference of a chain code is independent of
An approach frequently used to circumvent these problems is to resample
rotation, in general the coded boundary depends on the orientation of the
the boundary by selecting a larger grid spacing, as Fig. 11.4(a) shows. Then, as
Shape Number grid. One way to normalize the grid orientation is by aligning the chain-code
the boundary is traversed, a boundary point is assigned to each node of the
grid with the sides of the basic rectangle defined in the previous section.
large grid, depending on the proximity of the original boundary to that node,
In practice, for a desired shape order, we find the rectangle of order n
as in Fig. 11.4(b). The resampled boundary obtained in this way then can be
whose eccentricity (defined in the previous section) best approximates that of
 Shape number: the first difference as smallest magnitude (treating the chain code
represented by a 4- or 8-code. Figure 11.4(c) shows the coarser boundary
the basic rectangle and use this new rectangle to establish the grid size. For
points represented by an 8-directional chain code. It is a simple matter to
as a circular sequence) convert from an 8-code to a 4-code, and vice versa (see Problems 2.12 and 2.13).
The starting point in Fig. 11.4(c) is (arbitrarily) at the topmost, leftmost point
IGURE 11.17
 Order of a shape: the number of digits in Shape number.
Order 4 Order 6 of the boundary, which gives the chain code 0766 Á 12. As might be expected,
All shapes of the accuracy of the resulting code representation depends on the spacing of
rder 4, 6, and 8. the sampling grid.
The directions are
rom Fig. 11.3(a), The chain code of a boundary depends on the starting point. However, the
nd the dot Chain code: 0 3 2 1 0 0 3 2 2 1 code can be normalized with respect to the starting point by a straightfor-
ndicates the ward procedure: We simply treat the chain code as a circular sequence of di-
tarting point. Difference: 3 3 3 3 3 0 3 3 0 3
rection numbers and redefine the starting point so that the resulting
Shape no.: 3 3 3 3 0 3 3 0 3 3 sequence of numbers forms an integer of minimum magnitude. We can nor-
malize also for rotation (in angles that are integer multiples of the directions
in Fig. 11.3) by using the first difference of the chain code instead of the code
Order 8

a b 1 2
3 1
FIGURE 11.3
Direction
numbers for 2 0 4 0
Chain code: 0 0 3 3 2 2 1 1 0 3 0 3 (a)
2 24-directional
1 1 0 0 0 3 2 2 2 1
chain code, and
Difference: 3 0 3 0 3 0 3 0 3 3 1 3 (b)
3 0 8-directional
3 0 3 0 0 3 3 0 0 3 5 7
chain code.
Shape no.: 0 3 0 3 0 3 0 3 0 3 0 3 3 1 3 3 0 0 3 3 0 0 3 3 3 6

31/61 Kundan Kumar Pattern Classification

 ■ Suppose
codecode and that
usefirst
its n =difference
first 18 is to
specified forthe
to computetheshape
boundary
the shape in Fig.
as 11.18(a).
number, inToin
as shown ob- EXAMPLE 11.6: generationof aof a

osehe nucta ep le f o e r wn ce g

nust odr is o
of at pbefrerrelo rde
[Link] ar ligenctaitns fiirth t iffere
ohne b andalig(d).its f
conds a. 11n.d1 us ).
and use its difference compute number, shown

clo hesic ect ed gle st dhe

t e re 8 e

shasestfirsrecatng withas iffreesu ce to

generation

nu

shhm
r
o
o

hlos re c r se d w t d
cod . 11.1
chain code
gridgrid to the basic rectangle.

se
c s a asi u ne irs

ha thafirstmbngleis t as srde esu in togrid pute

. T pe re t st anlge o thsho renltin co
chain code to the basic rectangle.

Fige a 8(d
TD shape
Features number.

f
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors shape
dis- Computing References

Fig
tain
Fig. a shape
11.18(d). number of this order requires following ■ ■
the steps just

mb
pe t n st er o o f hor 1 ltinFig co . T
Fig. 11.18(d).

tha um=b 18 is ftothoirdderthne inis a 3gri1d1.1p8utefina shap

numbers. shape
shape number.
number.

id
cussed. The first step is to find the basic rectangle, as shown in Fig. 11.18(b).

f
er
t n er is s fi s o 18 ba ig * Th(c) thel st e n
n

e
ShapeTheNumber
closest rectangle of order 18 is a 3 * 6 rectangle, requiring subdivision

= 1 of tpecnd trde is asic . 11.6 ree fi, wh sheap i umb

of the basic rectangle as shown in Fig. 11.18(c), where the chain-code direc-

f
e
a b a b

o
p

8 i his ifiehe rb re 3 rect18( ctanal ere pes to er,

tions are aligned with the resulting grid. The final step is to obtain the chain
c d c d

ss
o
 Itcode
is advisable todifference
and use its first normalize the the
to compute gridshape
orientation by FIGURE
number, as shown aligning
in the chain code grid to

pe orddeforasiqc ui*r 6arngcl)e, wnglestepthenumobta as sh

f
FIGURE
11.1811.18
■ Steps

cif
Fig. 11.18(d).

i
in the

n
the basic rectangle. Steps in the

ied r rethqerbectsa foecta, nas es rereqius tohaibner,ina th own ■

generation
generation of a of a

fo
shapeshape number.
number.

8
n
1 a b1

F
g

ui ou ng llo gl ho the iri ob -co s s e c

2 2c 0d 0

e
Ch

m
3FIGURE
3 11.18

ChD

.
m
ain
ainif
Steps in the

Di

he the
cod
fSfeh

fceor
generation of a

Sh

raepne

denec

e:
shape number.

ap

h ,
: e0:
cen:o
en

0
1 1

o.:

0
30
.3:

0
00
00
2 0
00
0

0
2

0
00
11

00
0

0
Ch

c
3
ChD

03
3

00
1

0
ain

0
3
ainif

33

0 1
Di

3
33

0
1

0
cod

1 0
fSfeh

fceor

1
20 2
3

Sh

3
03
0 3
raepne

edne

0
120

e:
ap

2
32
1

Chain code: 0 0 0 0 3 0 0 3 2 2 3 2 2 2 1 2 1 1

:ce0:

3
3
cen:o
en

2
Chain code:
0 00 00 00 30 03 00 30 23 22 32 23 22 22 12 21 12 11 1

3
33

2 0
Chain code:

3
3
23

o.:

3
30
.3:

00

3 1
2

0
0

2
00
0

2
0 0
ChainChain code:
0 0 00 00 30 003 03 030 200 23 032 3
22 23122 0
12 223 11 312 10 1 1

1 3
0
Difference: 3 0 0 3 1 3 0

1
code:

2
00

32
33/61
01 3Prepared3by Dr.1 Kundan
00 3Kumar Pattern Classification
0 0
Difference:
3 03 00 00 30 13Prepared
0 3by
3 0Dr.10Kundan
3 03 Kumar 0 13 31 03 0

3
0
33/61 Pattern Classification

3
Difference:

in
3

2
03

02
00
0 3
0

0
Difference:
Difference: 3 0 03 00 30 10 03 31 30 03 13 30 01 03 30 10 33 01 3 0

1
3

0
0 1

00

1 3
3 1
3

0
Shape no.: 0 0 0 3 1 0 3 3 0 1 3 0 0 3 1 3 0 3

2
0

2 1
1 0

3 1
1

3
Shape 0 00 no.:
no.:Shape
no.: 30 010 0300310300 3
03 01313
30 00110330
30 3103 3303011330 3
3 0 1303 00 30 13 31 03 30

3
Shape 0no.:

1
03
0

Shape

1 3
0 3

1 3
0

1
1

1
32

1 0
3

3
3

3
2
3

a bd
33

2 0

00

a b UR
3
3

c
cF SdtepsEr
3
2

00

3 1

3
0

FIGge pas p

IG
2
1

Stesh e
Chain code: 0 0 0 0 3 0 0Kundan
3 2 2 Kumar
3 2 2 2 1 2 1 1
2 3
1 3
32/61 Pattern Classification
1

gen

UnRe
2
2 0
3 0

sha
3

E1
2
2
0
0

i
 Feature Extraction Boundary Representation P-1
Boundary Descriptors Regional Descriptors TD Features References
1
sN (k) = j2puk>P
P ua
a(u)e (11.2-5)
Fourier Descriptors =0

E 11.19 jy
tal
dary and its
sentation as
plex

Imaginary axis
nce. The
(x0, y0) and
) shown are
rarily) the y0
wo points in y1
quence.

x
x 0 x1
Real axis

Figure: A digital boundary and its representation as a complex sequence. The point (x0 , y0 ) and (x1 , y1 ) shown
are (arbitrarily) the first two points in the sequence.

33/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Fourier Descriptors

 Each coordinate pair treat as a complex number

s(k) = x(k) + jy(k)

for k = 0, 1, 2, . . . , N − 1.
 The discrete Fourier transform (DFT) of s(k) is

N
X −1
a(u) = s(k)e−j2πuk/N
k=0

for u = 0, 1, 2, . . . , N − 1
 a(u) are Fourier Descriptors.

34/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors
A-1 Regional Descriptors TD Features References
m = a vip(vi) (11.2-10)
Statistical moments i=0

g(r) a b
FIGURE 11.21
(a) Boundary
segment.
(b) Representation
as a 1-D function.
r

†
Recall from Chapter 4 that the Fourier transform of a constant is an impulse located at the origin.
 Once a boundaryRecallis
alsodescribed
that the impulse isas
zero a 1-D function,
everywhere else. statistical moments (mean,
variance, and a few higher-order central moments) can be used to describe it.
N
X −1
µn (z) = (zi − m)n p(zi )
i=0

N
X −1
m= zi p(zi )
i=0
35/61 Kundan Kumar Pattern Classification
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Regional Features/Descriptors

Liver
parenchyma

External
tissue

Liver
parenchyma

External
tissue

36/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Some simple Descriptors

 The area of a region is defined as the number of pixels in the region.

 The perimeter of a region is the length of its boundary.
 Compactness of a region, defined as (perimeter)2 /area, and is minimal for a
disk-shape region.
 A slightly different descriptor of compactness is the circularity ratio, defined as the
ratio of the area of a region to the area of a circle (the most compact shape).
 Region descriptors:
 mean and median of the gray levels,
 minimum and maximum gray-level values, and
 number of pixels with above and below the mean.

37/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Region Features

 There are following region features

 Colors, e.g., RGB values, HSV value, L*a*b
 Intensity, e.g. Gray Values
 Textures

 Further texture is divided into two classes:

 Spatial Domain Features
 Structural Features, e.g., LBP, Wavelets
 Statistical Features, e.g., GLCM, Orientation Histogram
 Transformed Domain Features
 Gabor Filters

38/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Texture
 An important
828 Chapter approach to and
11 ■ Representation region description is to quantify its texture content.
Description

a b c
FIGURE 11.28
The white squares
mark, from left to
right, smooth,
coarse, and
regular textures.
These are optical
microscope
images of a
superconductor,
human
cholesterol, and a
microprocessor.
(Courtesy of Dr.
Michael W.
Davidson, Florida
State University.)

Figure: The white squares mark, from left to right, smooth, coarse, and regular textures. These are optical
microscope images of a Statistical
superconductor,
approacheshuman cholesterol, and a microprocessor. (Courtesy of Dr. Michael
W. Davidson, Florida State
One ofUniversity.)
the simplest approaches for describing texture is to use statistical moments
of the intensity histogram of an image or region. Let z be a random variable de-
noting intensity and let p(zi), i = 0, 1, 2, Á , L - 1, be the corresponding his-
39/61 togram, where L is theKundan
numberKumar
of distinct intensity levels. From Eq. (3.3-17), the Pattern Classification
nth moment of z about the mean is
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Texture: Statistical approaches

 Compute the histogram of the area of interest.
 The nth moment of z about the mean is
L−1
X L−1
X
µn (z) = (zi − m)n p(zi ) m= zi p(zi )
i=0 i=0

 The second moment (n = 2) is of particular importance in texture description. It is

a measure of gray-level contrast that can be used to establish descriptors of relative
smoothness.
 For example, the texture measure, R, is 0 for areas of contrast intensity (the
variance is 0 here) and approaches 1 for large value of σ 2 (z)
1
R=1−
1 + σ 2 (z)

40/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Texture: Statistical approaches

 The third moment
L−1
X 3
µ3 (z) = (zi − m) p(zi )
i=0

is a measure of the skewness of the histogram while the fourth moment is a measure of its
relatives flatness.
 Some useful additional texture measures bases on histograms include a measure of
“uniformity”, given by
L−1
X
Uniformity = p2 (zi )
i=0

 Average entropy measure

L−1
X
Entropy = − p(zi )log2 p(zi )
i=0

41/61 Kundan Kumar Pattern Classification

Feature Extraction
(itBoundary
is smoother) than the other
Representation
two textures. The coarse
Boundary Descriptors
texture shows up clear-
Regional Descriptors TD Features References
ly in this measure. As expected, the same comments hold for R, because it
Texture: Statistical
measures essentiallyapproaches
the same thing as the standard deviation. The third mo-
ment generally is useful for determining the degree of symmetry of histograms
and whether they are skewed to the left (negative value) or the right (positive
value). This gives a rough idea of whether the intensity levels are biased to-
ward the dark or light side of the mean. In terms of texture, the information
derived from the third moment is useful only when variations between mea-
surements are large. Looking at the measure of uniformity, we again conclude
Figure: Texture measures for the subimages shown in previous slide

TABLE 11.2
Standard Third
Texture measures
Texture Mean deviation R (normalized) moment Uniformity Entropy
for the subimages
Smooth 82.64 11.79 0.002 -0.105 0.026 5.434 shown in Fig. 11.28
Coarse 143.56 74.63 0.079 -0.151 0.005 7.783
Regular 99.72 33.73 0.017 0.750 0.013 6.674

42/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Image Histograms

 The histogram of a digital image with intensity levels in the range [0, L − 1] is a
discrete function
h(rk ) = nk (1)
where, rk is the kth intensity value and nk is the number of pixels in the image
with intensity rk
 Normalized histogram
rk
p(rk ) = for k = 0, 1, 2, . . . , L − 1. (2)
MN
 p(rk ) is an estimate of the probability of occurrence of intensity level rk in an image.

43/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

0 0 0 1 2
Compute histogram
1 1 0 1 1

2 2 1 0 0

1 1 0 2 0
Compute the histogram of the given image. First find out the number graylevels in the
0 0 1 0 1
image (how many bit image?).
16
1 0 2 4 5 3 1
14

9 1 1 4 7 2 1 12

10 3 7 3 5 3 3 10

11 2 3 3 3 2 1
8

6
7 5 6 6 7 6 1
4

1 4 1 1 4 9 1 2

2 8 1 1 5 1 1 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

44/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary
thereRepresentation
is only one Boundary
occurrence in Descriptors Regional
f of a pixel valued Descriptorsa pixel valued
1 having TD Features
1 References

immediately to its right. Similarly, element (6, 2) of G is 3, because there are

Texture: Gray level co-occurrence matrix (GLCM)
three occurrences in f of a pixel with a value of 6 having a pixel valued 2 im-
mediately to its right. The other elements of G are computed in this manner.
 If we had defined
Gray Level Co-occurance Q as, say,
Matrix: Gl,θ“one pixel to the right and one pixel above,” then
(i, j)
where i = 0, 1, 2, . . . , L − 1, j = 0, 1, 2, . . . , L − 1, L is maximum intensity level.
FIGURE 11.29 1 2 3 4 5 6 7 8
How to generate 1 1 2 0 0 0 1 1 0
a co-occurrence
matrix. 1 1 7 5 3 2 2 0 0 0 0 1 1 0 0
5 1 6 1 2 5 3 0 1 0 1 0 0 0 0
8 8 6 8 1 2 4 0 0 1 0 1 0 0 0
4 3 4 5 5 1 5 2 0 1 0 1 0 0 0
8 7 8 7 6 2 6 1 3 0 0 0 0 0 1
7 8 6 2 6 2 7 0 0 0 0 1 1 0 2
8 1 0 0 0 0 2 2 1

Image f Co-occurrence matrix G

 Above calculation is just for demonstration. For real images, GLCM matrix dimension is
L × L, where index varies as i = 0, 1, 2, . . . , L − 1, j = 0, 1, 2, . . . , L − 1.
45/61 Kundan Kumar Pattern Classification
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

GLCM Features
 Maximum probability: Measure of the strongest response of G. The range of value is [0, 1].

Maximum probability = max pij

i,j

 Contrast: A measure of intensity contrast between a pixel and its neighbor over the entire image.
The range of values is 0 (When G is constant) to (L − 1)2 .

X L−1
L−1 X
Contrast = (i − j)2 pij
i=0 j=0

 Inverse Element Difference Moment: A measure of intensity contrast between a pixel and its
neighbor.
X L−1
L−1 X pij
k
for i 6= j
i=0 j=0 (i − j)

46/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

GLCM Features
 Uniformity/Energy: A measure of how intensities are uniformly distributed.

L−1
X L−1
X
Uniformity = pij 2
i=0 j=0

 Homogeneity: Measures the spatial closeness of the distribution of elements in G to the diagonal.
The range of values is [0,1], with the maximum being achieved when G is a diagonal matrix.

L−1
X L−1
X pij
Homogeneity =
i=0 j=0
1 + |i − j|

also defined as
L−1
X L−1
X pij
Homogeneity =
i=0 j=0
1 + (i − j)2

47/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

GLCM Features
 Entropy: Measures the randomness of the elements of G. The entropy is 0 when all pij ’s are 0 and
is maximum when all pij ’s are equal. The maximum value is 2 log2 L.
L−1
X L−1
X
Entropy = − pij log2 pij
i=0 j=0

 Correlation: A measure of how correlated a pixel is to its neighbor over the entire image. Range of
values is 1 to −1.
L−1
X L−1X (i − mr )(j − mc )pij
Correlation =
i=0 j=0
σr σc
L−1
X L−1
X L−1
X L−1
X
mr = i pij mr = j pij
i=0 j=0 j=0 i=0
L−1
X L−1
X L−1
X L−1
X
σr2 = (i − mr )2 pij σc2 = (j − mc )2 pij
i=0 j=0 j=0 i=0

48/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

GLCM feature Visualization 0.5

Grass
Sky

GLCM Correlation
0.4
0.3 Grass
0.5 Sky
0.2

GLCM Correlation
0.4
0.1
0.3
0.0
Original Image 0.2 2.5 5.0 7.5 10.0 12.5 15.0
0.1 GLCM Dissimilarity
0.0
Original Image 2.5 5.0 7.5 10.0 12.5 15.0
GLCM Dissimilarity

49/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Local Binary Pattern

 Basic Local Binary Pattern is governed by

1 if gk > g(x)
bk = and LBPri (x) = min {Pj }
0 otherwise

where Pj is decimal equivalent of binary sequence bj .

1 1 1 1 1 1 1 0 =254
10 12 9
6 7 19 1 1 1 1 1 1 0 1 =253
7 10 16 1 1 1 1 1 0 1 1 =251

am•FMqfMBdswod
LBP
1 1 1 1 0 1 1 1 =247

GEEZERS 1 1 1 0 1 1 1 1 =239

1 1 0 1 1 1 1 1 =223
6 10 12
1 0 1 1 1 1 1 1 =191
50/61 7 7 Kumar
Kundan 9 Pattern Classification
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Local Binary Pattern: Example

5 4 2 2 1 1 1 0 0 0 1 0 1
3 5 8 1 3 2
7
2
6
2
2 0
2 = 197

2 5 4 1 2 1 0 0 0 1 0 1 1
4 3 7 2 7 2
7
2
3
2
1 0
2 = 139

1 4 4 2 6 0 0 0 1 0 1 1 1
4 2 1 0
2 2 2 2 = 23

?
23
1 1 1 0 0 0 1 0
51/61 Kundan Kumar Pattern Classification
7 6 5 1
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Local Binary Pattern: Example

25000

20000

52/61 15000 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Transformed Domain Features

53/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

2D-Gabor filters

 Gabor filters are bandpass filters which are used in image processing for
 feature extraction,
 texture analysis, etc.
 In the spatial domain, a 2D Gabor filter is a Gaussian kernel function modulated by
a sinusoidal wave.
 02
x + γ 2 y 02 x0
   
gλ,θ,ϕ,σ,γ (x, y) = exp − exp i 2π + ϕ
2σ 2 λ

where x0 = x cos θ + y sin θ and y 0 = − sin θ + y cos θ.

 It has been shown by several researchers that the profile of simple-cell receptive
fields in the mammalian visual cortex can by described by oriented 2D-Gabor
functions.

54/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

2D-Gabor filters: Visual System

 Simple cells respond to bars and gratings of given orientation.

55/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

2D Gabor Functions
 Complex
 02
x + γ 2 y 02 x0
   
gλ,θ,ϕ,σ,γ (x, y) = exp − exp i 2π + ϕ
2σ 2 λ
 Real
x02 + γ 2 y 02 x0
   
gλ,θ,ϕ,σ,γ (x, y) = exp − cos 2π + ϕ
2σ 2 λ
 Imaginary
x02 + γ 2 y 02 x0
   
gλ,θ,ϕ,σ,γ (x, y) = exp − sin 2π + ϕ
2σ 2 λ
where
x0 =x cos θ + y sin θ
y 0 = − x sin θ + y cos θ

56/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

2D Gabor function parameters

 02
x + γ 2 y 02 x0
  
gλ,θ,ϕ,σ,γ (x, y) = exp − cos 2π + ϕ
2σ 2 λ
where

x0 =x cos θ + y sin θ
y 0 = − x sin θ + y cos θ

λ → wavelength of the sinusoidal factor,

θ → orientation of the normal to the parallel stripes of a Gabor function,
ϕ → phase offset,
σ → standard deviation of the Gaussian envelope,
γ → spatial aspect ratio, specifies the ellipticity of the support of the Gabor function.
57/61 Kundan Kumar Pattern Classification
 Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Feature Vector from spectral bands

0 + 0

ian

58/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

Feature Vector from spectral bands

11.4 ■ Use of Principal Components for Description

FIGURE 11.39
Formation of
vector from
corresponding
pixels in six
images.

Spectral band 6
x1
Spectral band 5
x2
x3 Spectral band 4
x 
x4 Spectral band 3
x5 Spectral band 2
x6
Spectral band 1

59/61 Kundan Kumar Pattern Classification

Organizing the images as in Fig. 11.39 leads to the formation of a six-element
Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References

References

[1] Rafael C Gonzalez, Richard E Woods, et al. Digital image processing. 2002.

60/61 Kundan Kumar Pattern Classification

Feature Extraction Boundary Representation Boundary Descriptors Regional Descriptors TD Features References