Digital Image Processing, 2nd ed. www.imageprocessingbook.

com

Chapter 12
Object Recognition

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Patterns and Pattern Classes

• Patterns and features

• Pattern classes: a pattern class is a family of patterns
that share some common properties
• Pattern recognition: to assign patterns to their
respective classes
• Three common pattern arrangements used in practices
are
– Vectors
– Strings
– Trees

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Patterns and Pattern Classes

Vector Example

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Patterns and Pattern Classes

Another Vector Example

• Here is another example of pattern vector generation.

• In this case, we are interested in different types of noisy
shapes.

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Patterns and Pattern Classes

String Example

• String descriptions adequately generate patterns of objects and

other entities whose structure is based on relatively simple
connectivity of primitives, usually associated with boundary
shape.

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Patterns and Pattern Classes

Tree Example

• Tree descriptions is more powerful than string ones.

• Most hierarchical ordering schemes lead to tree structure.

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Patterns and Pattern Classes

Tree Example

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on
Decision-Theoretic Methods

• Decision-theoretic approaches to recognition are based on the

use decision functions.
• Let x = ( x1 , x2 ,..., xn )Trepresent an n-dimensional pattern vector.
For W pattern classes ω1 , ω2 ,..., ωW , we want to find W decision
functions d1 (x), d 2 (x),..., dW (x) with the property that, if a pattern x
belongs to class ωi , then
d i ( x) > d j ( x) j = 1,2,...,W ; j ≠ i
• The decision boundary separating class ωi and ω j is given by
d i (x) = d j (x) or d i (x) − d j (x) = 0

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Matching

• Minimum distance classifier

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Matching by Correlation

• The correlation between f(x,y) and w(x,y) is

c( x, y ) = ∑∑ f ( s, t ) w( x + s, y + t )
s t

for x = 0,1,2,..., M − 1,
y = 0,1,2,..., N − 1

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Matching by Correlation

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Optimum Statistical Classifiers

• Bayes classifier for Gaussian pattern classes

( x−m j )2
−
1 2σ 2j
d j ( x) = p ( x | ω j ) p (ω j ) = e p (ω j )
2π σ j

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Optimum Statistical Classifiers

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Optimum Statistical Classifiers

• Classification of multi-spectral data using the Bayes classifier

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Optimum Statistical Classifiers

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Neural Networks

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Neural Networks

• Illustration of the perceptron algorithms

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Multilayer Feedforward Neural Networks

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Multilayer Feedforward Neural Networks

• The activation function: a sigmoid function

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Multilayer Feedforward Neural Networks

Pattern vectors were generated by computing the normalized

signatures of the shapes (see Section 11.1.3)
© 2002 R. C. Gonzalez & R. E. Woods
 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Multilayer Feedforward Neural Networks

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Multilayer Feedforward Neural Networks

Rt denote a value of R
used to generate
training data.
Rt =0 implies noise-free
training.

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Multilayer Feedforward Neural Networks

N: the number of
training patterns

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Multilayer Feedforward Neural Networks

• Complexity of decision surface

– Two input, tow-layer, feedforward neural networks

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Recognition Based on Decision-Theoretic Methods

Multilayer Feedforward Neural Networks

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Matching Shape Number

• Let a and b denote shape numbers of closed boundaries

represented by 4-directional chain codes. There two shapes
have a degree of similarity k if
s j (a ) = s j (b), for j = 4,6,8,..., k
s j (a ) ≠ s j (b), for j = k + 2, k + 4,...

where s indicates shape number and the subscript indicates

order (see Section 11.2.2)
• The distance between two shapes a and b defined as
1
D ( a, b) =
k

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Matching Shape Number

Shape no. order

Similarity tree
© 2002 R. C. Gonzalez & R. E. Woods
 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Matching Shape Number

Similarity tree Similarity matrix

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
String Matching

• Suppose that two region boundaries, a and b, are coded into

strings (see Section 11.5) denoted a1, a2, …, an and b1, b2,
…,bm, respectively.
• Let α represent the number of matches between the two
strings, where a match occurs in the kth position if ak = bk .
• The number of symbols that do not match is
β = max( a , b ) − α
• A simple measure of similarity between a and b is the ratio
α α
R= =
β max( a , b ) − α

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
String Matching

• Strings were formed from the polygons by

computing the interior angle, θ , between segments
as each polygon was traversed clockwise.
• Angles were coded into one of eight possible
symbols, corresponding to 45o increments.
α1 : 0 < θ ≤ 45o ;α 2 : 45o < θ ≤ 90o ;...
© 2002 R. C. Gonzalez & R. E. Woods
 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
String Matching

• Figure 12.25(e) shows the results of computing the measure R

for six samples of object 1 against themselves.
• The notation 1.c refers to the third string from object class 1.

Figure 12.25 (e) Figure 12.25 (f)

© 2002 R. C. Gonzalez & R. E. Woods
 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
String Matching

• Figure 12.25(g) shows a tabulation of R values obtained by

comparing strings of one class against the other.
• Note that all R values are considerable smaller than any entry in
the two preceding tabulations.
• The R measure achieved a
high degree of discrimination
between the two classes of
objects.

Figure 12.25 (g)

© 2002 R. C. Gonzalez & R. E. Woods
 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Syntactic Recognition of Strings

• String grammars
– Step1: Object class
generation using a
regular string
grammar
– For example:
the srting of Fig.
12.26(c) is abbbbbc.

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Syntactic Recognition of Strings

• String grammars
– Step 2: use of semantics (production rules)

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Syntactic Recognition of Strings

• String grammars
– Step 3: automata as string recognizers

String: abbbbbc

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Syntactic Recognition of Trees

• Tree grammars
• Production rules
– Example
S→a
|
X1

X1 → c
/ \
X2 X3
• Tree automata

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Syntactic Recognition of Trees

• Processing stages of a tree automata

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Syntactic Recognition of Trees

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

 Digital Image Processing, 2nd ed. www.imageprocessingbook.com

Structural Methods
Syntactic Recognition of Trees

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

Digital Image Processing
Chapter 11:

Image Description and

Representation

1
Image Representation and Description?
Objective:
To represent and describe information embedded in
an image in other forms that are more suitable than the
image itself.
Benefits:
- Easier to understand
- Require fewer memory, faster to be processed
- More “ready to be used”
What kind of information we can use?
- Boundary, shape
- Region
- Texture
- Relation between regions 2
Shape Representation by Using Chain Codes
Why we focus on a boundary?
The boundary is a good representation of an object shape
and also requires a few memory.
Chain codes: represent an object boundary by a connected
sequence of straight line segments of specified length
and direction.

4-directional 8-directional (Images from Rafael C.

3 Richard E.
Gonzalez and
chain code chain code Wood, Digital Image
Processing, 2nd Edition.
Examples of Chain Codes

Object Boundary
boundary vertices
(resampling)

4-directional 8-directional
chain code chain code

4
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
The First Difference of a Chain Codes
Problem of a chain code:
a chain code sequence depends on a starting point.
Solution: treat a chain code as a circular sequence and redefine the
starting point so that the resulting sequence of numbers forms an
integer of minimum magnitude.
The first difference of a chain code: counting the number of direction
change (in counterclockwise) between 2 adjacent elements of the code.
Example: Chain code : The first Example:
1 difference - a chain code: 10103322
0 1 1 - The first difference = 3133030
2 0 0 2 2 - Treating a chain code as a
0 3 3 circular sequence, we get
3 2 3 1 the first difference = 33133030
2 0 2
2 1 3 The first difference is rotational
5
invariant.
Polygon Approximation

Represent an object boundary by a polygon

Object boundary Minimum perimeter

polygon

Minimum perimeter polygon consists of line segments that

minimize distances between boundary pixels. 6
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Polygon Approximation:Splitting Techniques

1. Find the line joining

two extreme points
0. Object boundary 2. Find the
farthest points
from the line

3. Draw a polygon 7
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Distance-Versus-Angle Signatures
Represent an 2-D object boundary in term of a 1-D function
of radial distance with respect to θ.

8
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Boundary Segments
Concept: Partitioning an object boundary by using vertices
of a convex hull.

Partitioned boundary

Convex hull (gray color)

Object boundary

9
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Convex Hull Algorithm
Input : A set of points on a cornea boundary
Output: A set of points on a boundary of a convex hull of a cornea
1. Sort the points by x-coordinate to get a sequence p1, p2, … ,pn
For the upper side of a convex hull
2. Put the points p1 and p2 in a list Lupper with p1 as the first point
3. For i = 3 to n
4. Do append pi to Lupper
5. While Lupper contains more than 2 points and the last 3
points in Lupper do not make a right turn
6. Do delete the middle point of the last 3 points from Lupper
Turn
Turn Left
Turn
Right NOK!
Right
OK!
OK! 10
Convex Hull Algorithm (cont.)
For the lower side of a convex hull
7. Put the points pn and pn-1 in a list Llower with pn as the first point
8. For i = n-2 down to 1
9. Do append pi to Llower
10. While Llower contains more than 2 points and the last 3 points
in Llower do not make a right turn
11. Do delete the middle point of the last 3 points from Llower
12. Remove the first and the last points from Llower
13. Append Llower to Lupper resulting in the list L
14. Return L
Turn
Turn Right
Right OK!
Turn
OK!
Left 11
NOK!
Skeletons
Obtained from thinning or skeletonizing processes

Medial axes (dash lines)

12
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Thinning Algorithm
Concept: 1. Do not remove end points
“Prairie fire” 2. Do not break connectivity
3. Do not cause excessive erosion
Apply only to contour pixels: pixels “1” having at least one of its 8
neighbor pixels valued “0”
Notation:
p9 p2 p3 Neighborhood
arrangement
Let p8 p1 p4 =
for the thinning
p7 p6 p5 algorithm
Example
Let N ( p1 ) = p2 + p3 + K + p8 + p9 0 0 1
T(p1) = the number of transition 0-1 in 1 p1 0
the ordered sequence p2, p3, … 1 0 1
, p8, p9, p2.
N(p1) =134
T(p1) = 3
Thinning Algorithm (cont.)

Step 1. Mark pixels for deletion if the following conditions are true.
a) 2 ≤ N ( p1 ) ≤ 6
(Apply to all border pixels) p9 p2 p3
b) T(p1) =1
c) p2 ⋅ p4 ⋅ p6 = 0 p8 p1 p4
d) p4 ⋅ p6 ⋅ p8 = 0 p7 p6 p5
Step 2. Delete marked pixels and go to Step 3.
Step 3. Mark pixels for deletion if the following conditions are true.
a) 2 ≤ N ( p1 ) ≤ 6
(Apply to all border pixels)
b) T(p1) =1
c) p2 ⋅ p4 ⋅ p8 = 0
d) p2 ⋅ p6 ⋅ p8 = 0
Step 4. Delete marked pixels and repeat Step 1 until no change
occurs. 14
Example: Skeletons Obtained from the Thinning Alg.

Skeleton

15
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Boundary Descriptors
1. Simple boundary descriptors:
we can use
- Length of the boundary
- The size of smallest circle or box that can totally
enclosing the object

2. Shape number

3. Fourier descriptor

4. Statistical moments

16
Shape Number
Shape number of the boundary definition: 1
the first difference of smallest magnitude
The order n of the shape number: 2 0
the number of digits in the sequence
3

17
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Shape Number (cont.)

Shape numbers of order

4, 6 and 8

18
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Example: Shape Number

2. Find the smallest rectangle

that fits the shape
1. Original boundary

Chain code:
000030032232221211

First difference:
300031033013003130

4. Find the nearest Shape No.

3. Create grid Grid. 0 0 0 3 1 0 3 3 0 1 3 0 0 3 1193 0 3
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Fourier Descriptor
Fourier descriptor: view a coordinate (x,y) as a complex number
(x = real part and y = imaginary part) then apply the Fourier
transform to a sequence of boundary points.
Let s(k) be a coordinate s ( k ) = x ( k ) + jy ( k )
of a boundary point k :

K −1
1
Fourier descriptor : a (u ) =
K
∑ s
k =0
( k ) e − 2πuk / K

Reconstruction formula
K −1
1
s(k ) =
K
∑ a (
k =0
u ) e 2πuk / K

Boundary
20
points (Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Example: Fourier Descriptor
Examples of reconstruction from Fourier descriptors
P −1
1
sˆ( k ) =
K
∑ a (
k =0
u ) e 2πuk / K

P is the number of
Fourier coefficients
used to reconstruct
the boundary

21
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Fourier Descriptor Properties

Some properties of Fourier descriptors

22
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Statistical Moments
Definition: the nth moment Example of moment:
K −1 The first moment = mean
µn ( r ) = ∑ ( ri − m) n g ( ri ) The second moment = variance
i =0

where K −1 Adv:
m = ∑ ri g ( ri ) •Straight forward
i =0
•Physical interpretation of
boundary shape.
Boundary •Insensitivity to rotation
segment 1D graph

1. Convert a boundary segment into 1D graph

2. View a 1D graph as a PDF function (Images from Rafael C.
3. Compute the nth order moment of the graph 23 Richard E.
Gonzalez and
Wood, Digital Image
Processing, 2nd Edition.
Regional Descriptors
Purpose: to describe regions or “areas”
1. Some simple regional descriptors
- area of the region
- length of the boundary (perimeter) of the region
- Compactness
A( R )
C= 2
P ( R)
where A(R) and P(R) = area and perimeter of region R
Example: a circle is the most compact shape with C = 1/4π

2. Topological Descriptors
3. Texture
4. Moments of 2D Functions
24
 Regional Descriptors
• Area: # of pixels within the boundary
• Perimeter: length of boundary

– Can be used with area to measure compactness

(perimeter2/area)

– Compactness is:
• Dimensionless, and thus insensitive to scale changes
• Insensitive to orientation
25
 Regional Descriptors
• Principal axes:

– Eigenvectors of the covariance matrix

– Ratio of large to small eigenvalue: insensitive
to scale and rotation

26
 Regional Descriptors
• Other descriptors:

– Mean and median of gray levels

– Min. and max. gray-level values
– # pixels with values above and below the mean

27
Example: Regional Descriptors

White pixels represent

“light of the cities”

% of white pixels
Region no. compared to the
total white pixels

1 20.4%
2 64.0%
3 4.9%
4 10.7%

28
Infrared image of America at night (Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Topological Descriptors
Use to describe holes and connected components of the region

Euler number (E):

E =C−H

C = the number of connected

components
H = the number of holes

29
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Topological Descriptors (cont.)

E = -1

E=0 Euler Formula

V −Q + F = C − H = E

V = the number of vertices

Q = the number of edges
F = the number of faces

E = -2 30
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Example: Topological Descriptors
Original image:
Infrared image After intensity
Of Washington Thresholding
D.C. area (1591 connected
components
with 39 holes)
Euler no. = 1552

The largest
After thinning
connected
area
(8479 Pixels)
(Hudson river)

31
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Texture Descriptors
Purpose: to describe “texture” of the region.
Examples: optical microscope images:

B C

Superconductor Cholesterol Microprocessor

(smooth texture) (coarse texture) (regular texture) 32
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
33
34
35
36
37
38
Statistical Approaches for Texture Descriptors
We can use statistical moments computed from an image histogram:
K −1
z = intensity
µn ( z ) = ∑ ( zi − m) p( zi )
n
p(z) = PDF or histogram of z
i =0

where K −1
m = ∑ zi p( zi )
i =0

Example: The 2nd moment = variance measure “smoothness”

The 3rd moment measure “skewness”
The 4th moment measure “uniformity” (flatness)

A
B
C
39
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Fourier Approach for Texture Descriptor
Concept: convert 2D spectrum into 1D graphs

Fourier
Original FFT2D coefficient Divide into areas
image +FFTSHIFT by angles
image

Divide into areas Sum all pixels

by radius in each area

R0
S (θ ) = ∑ Sr (θ )
r =1

π
Sum all pixels
S ( r ) = ∑ Sθ ( r ) 40
in each area θ =0
Fourier Approach for Texture Descriptor

Original 2D Spectrum
image (Fourier Tr.)

S(r) S(θ)

Another Another S(θ)

image
(Images from Rafael C.
Gonzalez41
and Richard E.
Wood, Digital Image
Processing, 2nd Edition.
Moments of Two-D Functions
The moment of order p + q
m pq = ∑∑ x p y q f ( x, y ) x=
m10
y=
m01
x y m00 m00
The central moments of order p + q
µ pq = ∑∑ ( x − x ) p ( y − y ) q f ( x, y )
x y

µ00 = m00 µ01 = µ10 = 0

µ11 = m11 − x m01 = m11 − ym10
µ20 = m20 − x m10 µ02 = m02 − ym01
µ21 = m21 − 2 x m11 − ym20 + 2 x 2m01 µ30 = m30 − 3x m20 + 2 x 2m10
µ12 = m12 − 2 ym11 − x m02 + 2 y 2m10 µ03 = m03 − 3 ym02 + 2 y 242m01
Invariant Moments of Two-D Functions
The normalized central moments of order p + q
µ pq p+q
η pq = γ where γ = +1
µ00 2

Invariant moments: independent of rotation, translation, scaling,

and reflection
φ1 = η20 + η02 φ2 = (η20 − η02 )2 + 4η112
φ3 = (η30 − 3η12 )2 + (3η21 − η03 )2 φ4 = (η30 + η12 )2 + (η21 + η03 )2

φ5 = η30 − 3η12 η30 + η12 η30 + η12 − 3 η21 + η03 ]+

( )( )[( )2
( )2

(3η21 − η03 )(η21 + η03 )[3(η30 + η12 )2 − (η21 + η03 )2 ]

φ6 = η20 − η02 η30 + η12 − η21 + η03 ]+
( )[( )2
( )2

4η11 (η30 + η12 )(η21 + η03 ) 43

Example: Invariant Moments of Two-D Functions

1. Original image 2. Half size 3. Mirrored

4. Rotated 2 degree 5. Rotated 45 degree

44
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Example: Invariant Moments of Two-D Functions

Invariant moments of images in the previous slide

Invariant moments are independent of rotation, translation,

scaling, and reflection

45
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Principal Components for Description
Purpose: to reduce dimensionality of a vector image while maintaining
information as much as possible.

Let x = [ x1 x2 ... xn ]T

K
1
Mean: m x = E{x} =
K
∑x
k =1
k

K
Covariance matrix C x = E{(x − m x )( x − m x )T } = 1 ∑ k k x x
x x T
− m mT

K k =1 46
Hotelling transformation

Let y = A(x − m x )

Where A is created from eigenvectors of Cx as follows

Row 1 contain the 1st eigenvector with the largest eigenvalue.
Row 2 contain the 2nd eigenvector with the 2nd largest eigenvalue.
….
Then we get
λ1 0 ... 0 
m y = E{y} = 0  0 λ ... 0 
and C =  1 
 ... ... ... ... 
y
C y = AC x A T  
 0 ... ... λ 1

Then elements of y = A ( x − m x ) are uncorrelated. The

component of y with the largest λ is called the principal
component. 47
Eigenvector and Eigenvalue

Eigenvector and eigenvalue of Matrix C are defined as

Let C be a matrix of size NxN and e be a vector of size Nx1.

If
Ce = λe

Where λ is a constant

We call e as an eigenvector and λ as eigenvalue of C

48
Example: Principal Components

6 spectral images
from an airborne
Scanner.

49
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Example: Principal Components (cont.)

Component λ
1 3210
2 931.4
3 118.5
4 83.88
5 64.00
6 13.40
50
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Example: Principal Components (cont.)

Original image After Hotelling transform51

Principal Components for Description

52
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Relational Descriptors

53
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Relational Descriptors

54
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Relational Descriptors

55
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Relational Descriptors

56
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Relational Descriptors

57
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Structural Approach for Texture Descriptor

58
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.