I2200: Digital Image processing

Lecture 10: Image Descriptors

and Representation

Prof. YingLi Tian

Nov. 15, 2017
Department of Electrical Engineering
The City College of New York
The City University of New York (CUNY)
Thanks to G&W website, Dr. Shahram Ebadollahi for slide materials
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”

2
Outline
 Image Description
 Shape Descriptors
 Region Descriptors
 Texture & Texture Descriptors
Shape Description
 Shape Represented by its Boundary
 Shape Numbers,
 Fourier Descriptors,
 Statistical Moments
 Shape Represented by its Interior
 Topological Descriptors
 Moment Invariants

4
Boundary Representation: Chain Code
Why 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.

5
Boundary Representation: Chain Code

Object Boundary
boundary vertices
(resampling)

4-directional 8-directional
chain code chain code

6
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.

7
The First Difference of a Chain Codes:
Example
Example: Chain code : The first (counterclockwise)
difference
1 01 1
02 2
2 0 03 3
23 1
3 20 2
21 3
Example:
- a chain code: 10103322
- The first difference = 3133030 The first difference is
- Treating a chain code as a rotational invariant.
circular sequence, we get
the first difference = 33133030 8
Chain Code: example

(First difference of chain code) 9

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
Shape Numbers
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
Shape Numbers
Shape numbers of order
4, 6 and 8
 Example: Shape Numbers

2. Find the smallest rectangle

that fits the shape

1. Original boundary
Chain code:
000030032232221211

First difference:
300031033013003130

Shape No.
4. Find the nearest 000310330130031303
3. Create grid Grid.
 Boundary descriptor – Fourier
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
Boundary s(k ) 
K
 a
k 0
( u ) e 2uk / K

points
Fourier Descriptor Properties
 Boundary Reconstruction using
Fourier Descriptors

2868
descriptors

Only 8
descriptors

16
Polygon Approximation
Represent an object boundary by a polygon

Minimum perimeter polygon consists of line segments that

minimize distances between boundary pixels.
17
Polygon Approximation: Splitting Techniques

1. Find the line joining

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

3. Draw a polygon
18
Boundary Representation: Signatures
Represent 2-D boundary shape using 1-D signature signal

19
Boundary Representation: Signatures

20
 Boundary Segments
Concept: Partitioning an object boundary by using vertices
of a convex hull.

Partitioned boundary

Convex hull (gray color)

Object boundary
21
Skeletons
Obtained from thinning or skeletonizing processes

22
Region Descriptors - Simple

23
Region Descriptors - Example
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%

Infrared image of America at night 24

Topological Region Descriptors
Topological properties: Properties of image preserved under
rubber-sheet distortions

25
 Topological Descriptors: example
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)

26
Boundary Description: Statistical Moments
Definition: the nth moment Example of moment:
K 1
n (r)   (r
i0
i  m ) n g ( ri ) The first moment = mean
K 1
The second moment = variance
where m   r g (r ) i i
i0

Boundary
segment 1D graph

1. Convert a boundary segment into 1D graph

2. View a 1D graph as a PDF function
3. Compute the nth order moment of the graph
27
Geometric Moment Invariants

28
Central Moments

29
Moment Invariants (translation, scale,
mirroring, rotation)

30
Moment Invariants (translation, scale,
mirroring, rotation)

31
Affine Transform & Affine Moment
Invariants

32
Affine Transform & Affine Moment
Invariants

33
Elliptical Shape Descriptors

34
Texture - Definition
Purpose: to describe “pattern” of the region.

35
Texture – Quantification Methods

36
Statistical Texture Analysis 1st order statistics

37
Texture
Examples: optical microscope images:

B C
A

Superconductor Cholesterol Microprocessor

(smooth texture) (coarse texture) (regular texture)
38
 Texture

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

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

A
B
C

39
Statistical Texture Analysis:
1st order statistics

40
Statistical Texture Analysis:
2nd order statistics: Co-occurrence

41
Statistical Texture Analysis:
2nd order statistics: Co-occurrence

42
Statistical Texture Analysis:
2nd order statistics: Co-occurrence

43
Statistical Texture Analysis (Example)

44
Statistical Texture Analysis (Example)

45
Statistical Texture Analysis
2nd order statistics: Difference Statistics

46
Statistical Texture Analysis
2nd order statistics: Autocorrelation

47
48
49
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 ( )   S r ( )
r 1


Sum all pixels S ( r )   S ( r )
in each area  0
50
Fourier Approach for Texture Descriptor

Original 2D Spectrum
image (Fourier Tr.)

S(r) S()

Another Another
image S()

51
Which descriptors?
Image Feature Evaluation

52
Announcement
 Reading
 G&W Chapter 11
 Next lecture: Object Recognition (Chapter
12)

53