Digital Image Processing, 2nd ed. [Link].

com

Chapter 11
Representation & Description

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

 Digital Image Processing, 2nd ed. [Link]

Representation

• Image regions (including segments) can be represented by

either the border or the pixels of the region. These can be
viewed as external or internal characteristics, respectively.
• Chain codes: represent a boundary of a connected region.

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Chain Codes

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Chain Codes

• Chain codes can be based on either 4-connectedness

or 8-connectedness.
• The first difference of the chain code:
– This difference is obtained by counting the number of
direction changes (in a counterclockwise direction)
– For example, the first difference of the 4-direction chain
code 10103322 is 3133030.
• Assuming the first difference code represent a closed
path, rotation normalization can be achieved by
circularly shifting the number of the code so that the
list of numbers forms the smallest possible integer.
• Size normalization can be achieved by adjusting the
size of the resampling grid.
© 2002 R. C. Gonzalez & R. E. Woods
 Digital Image Processing, 2nd ed. [Link]

Representation
Polygonal Approximations
• Polygonal approximations: to represent a boundary by straight line
segments, and a closed path becomes a polygon.
• The number of straight line segments used determines the accuracy of the
approximation.
• Only the minimum required number of sides necessary to preserve the
needed shape information should be used (Minimum perimeter polygons).
• A larger number of sides will only add noise to the model.

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Polygonal Approximations

• Minimum perimeter polygons: (Merging and splitting)

– Merging and splitting are often used together to ensure that
vertices appear where they would naturally in the boundary.
– A least squares criterion to a straight line is used to stop the
processing.

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Signature

• The idea behind a signature is to convert a two dimensional

boundary into a representative one dimensional function.

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Signature

• Signatures are invariant to location, but will

depend on rotation and scaling.
– Starting at the point farthest from the reference
point or using the major axis of the region can be
used to decrease dependence on rotation.
– Scale invariance can be achieved by either scaling
the signature function to fixed amplitude or by
dividing the function values by the standard
deviation of the function.

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Boundary Segments

• Boundary segments: decompose a boundary into segments.

• Use of the convex hull of the region enclosed by the boundary
is a powerful tool for robust decomposition of the boundary.

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Skeletons

• Skeletons: produce a one pixel wide graph that has the same
basic shape of the region, like a stick figure of a human. It can
be used to analyze the geometric structure of a region which
has bumps and “arms”.

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Skeletons

• Before a thinning algorithm:

– A contour point is any pixel with value 1 and having at least
one 8-neighbor valued 0.
– Let
N ( p1 )  p2  p3  ...  p8  p9
T ( p1 ) : the number of 0 - 1 transitio ns
in the ordered sequence
p2 , p3 ,..., p8 , p9 , p2

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Skeletons

• Step 1: Flag a contour point p1 for deletion if the

following conditions are satisfied
(a) 2  N ( p1 )  6 (c) p2  p4  p6  0
(b) T ( p1 )  1 (d) p4  p6  p8  0

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Skeletons

• Step 2: Flag a contour point p1 for deletion again.

However, conditions (a) and (b) remain the same,
but conditions (c) and (d) are changed to
(d' ) p2  p6  p8  0
(c' ) p2  p4  p8  0

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Skeletons

• A thinning algorithm:
– (1) applying step 1 to flag border points for
deletion
– (2) deleting the flagged points
– (3) applying step 2 to flag the remaining border
points for deletion
– (4) deleting the flagged points
– This procedure is applied iteratively until no
further points are deleted.

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

 Digital Image Processing, 2nd ed. [Link]

Representation
Skeletons: Example

• One application of
skeletonization is for
character recognition.
• A letter or character is
determined by the
center-line of its
strokes, and is unrelated
to the width of the
stroke lines.

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

 Digital Image Processing, 2nd ed. [Link]

Boundary Descriptors

• There are several simple geometric measures

that can be useful for describing a boundary.
– The length of a boundary: the number of pixels
along a boundary gives a rough approximation of
its length.
– Curvature: the rate of change of slope
• To measure a curvature accurately at a point in a digital
boundary is difficult
• The difference between the slops of adjacent boundary
segments is used as a descriptor of curvature at the point
of intersection of segments

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

 Digital Image Processing, 2nd ed. [Link]

Boundary Descriptors
Shape Numbers

First
difference
• The shape number of a boundary is defined as the first
difference of smallest magnitude.
• The order n of a shape number is defined as the number of
digits in its representation.

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

 Digital Image Processing, 2nd ed. [Link]

Boundary Descriptors
Shape Numbers

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

 Digital Image Processing, 2nd ed. [Link]

Boundary Descriptors
Shape Numbers

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

 Digital Image Processing, 2nd ed. [Link]

Boundary Descriptors
Fourier Descriptors

• This is a way of using the Fourier transform to

analyze the shape of a boundary.
– The x-y coordinates of the boundary are treated as the real
and imaginary parts of a complex number.
– Then the list of coordinates is Fourier transformed using
the DFT (chapter 4).
– The Fourier coefficients are called the Fourier descriptors.
– The basic shape of the region is determined by the first
several coefficients, which represent lower frequencies.
– Higher frequency terms provide information on the fine
detail of the boundary.

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

 Digital Image Processing, 2nd ed. [Link]

Boundary Descriptors
Fourier Descriptors

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

 Digital Image Processing, 2nd ed. [Link]

Boundary Descriptors
Statistical Moments

• Moments are statistical measures of data.

– They come in integer orders.
– Order 0 is just the number of points in the data.
– Order 1 is the sum and is used to find the average.
– Order 2 is related to the variance, and order 3 to the skew
of the data.
– Higher orders can also be used, but don’t have simple
meanings.

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

 Digital Image Processing, 2nd ed. [Link]

Boundary Descriptors
Statistical Moments

• Let r be a random variable, and g(ri) be normalized (as the

probability of value ri occurring), then the moments are
K 1
 n (r )   (ri  m) n g (ri )
k 0
K 1
where m   ri g (ri )
i 0

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors

• Some simple descriptors

– The area of a region: the number of pixels in the
region
– The perimeter of a region: the length of its
boundary
– The compactness of a region: (perimeter)2/area
– The mean and median of the gray levels
– The minimum and maximum gray-level values
– The number of pixels with values above and below
the mean

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Example

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Topological Descriptors

Topological property 1:
the number of holes (H)

Topological property 2:
the number of connected
components (C)

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Topological Descriptors

Topological property 3:
Euler number: the number of connected components subtract
the number of holes
E=C-H

E=0 E= -1

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Topological Descriptors

Topological
property 4:
the largest
connected
component.

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Texture

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Texture

• Texture is usually defined as the smoothness or roughness of a

surface.
• In computer vision, it is the visual appearance of the
uniformity or lack of uniformity of brightness and color.
• There are two types of texture: random and regular.
– Random texture cannot be exactly described by words or
equations; it must be described statistically. The surface of
a pile of dirt or rocks of many sizes would be random.
– Regular texture can be described by words or equations or
repeating pattern primitives. Clothes are frequently made
with regularly repeating patterns.
– Random texture is analyzed by statistical methods.
– Regular texture is analyzed by structural or spectral
(Fourier) methods.

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Statistical Approaches

• Let z be a random variable denoting gray levels and let p(zi),

i=0,1,…,L-1, be the corresponding histogram, where L is the
number of distinct gray levels.
– The nth moment of z:
L 1
 n ( z )   ( zi  m) p( zi ) where m   zi p( zi )
L 1
n

k 0 i 0
1
– The measure R: R  1
1   2 ( z)
L 1
– The uniformity: U   p 2 ( zi )
i 0
L 1
– The average entropy: e    p( z ) log
i 0
i 2 p ( zi )
© 2002 R. C. Gonzalez & R. E. Woods
 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Statistical Approaches

Smooth Coarse Regular

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Structural Approaches

• Structural concepts:
– Suppose that we have a
rule of the form S→aS,
which indicates that the
symbol S may be
rewritten as aS.
– If a represents a circle
[Fig. 11.23(a)] and the
meaning of “circle to the
right” is assigned to a
string of the form
aaaa… [Fig. 11.23(b)] .

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Spectral Approaches

• For non-random primitive spatial patterns, the 2-dimensional

Fourier transform allows the patterns to be analyzed in terms of
spatial frequency components and direction.
• It may be more useful to express the spectrum in terms of polar
coordinates, which directly give direction as well as frequency.
• Let S (r , ) is the spectrum function, and r and  are the
variables in this coordinate system.
– For each direction  , S (r , ) may be considered a 1-D
function S (r ).
– For each frequency r, Sr ( ) is a 1-D function.
– A global description: S (r )   S (r )
R

  S ( )   S r ( )
0

 0 r 1

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Spectral Approaches

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Spectral Approaches

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Moments of Two-Dimensional Functions

• For a 2-D continuous function f(x,y), the moment of

order (p+q) is defined as
 
mpq    x p y q f ( x, y)dxdy for p, q  1,2,3,...
 

• The central moments are defined as

 
 pq    ( x  x ) ( y  y ) f ( x, y)dxdy
p q
  
m10 m01
where x  and y 
m00 m00

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Moments of Two-Dimensional Functions

• If f(x,y) is a digital image, then

 pq   ( x  x ) p ( y  y ) q f ( x, y )
x y
• The central moments of order up to 3 are
00   ( x  x ) 0 ( y  y ) 0 f ( x, y )   f ( x, y )  m00
x y x y
m10
10   ( x  x )1 ( y  y ) 0 f ( x, y )  m10  (m00 )  0
x y m00
m01
01   ( x  x ) ( y  y ) f ( x, y )  m01 
0 1
(m00 )  0
x y m00
m10m01
11   ( x  x ) ( y  y ) f ( x, y )  m11 
1 1

x y m00
 m11  x m01  m11  ym10
© 2002 R. C. Gonzalez & R. E. Woods
 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Moments of Two-Dimensional Functions

• The central moments of order up to 3 are

 20   ( x  x ) 2 ( y  y ) 0 f ( x, y )  m20  x m10
x y
02   ( x  x ) 0 ( y  y ) 2 f ( x, y )  m02  ym01
x y

 21   ( x  x ) 2 ( y  y )1 f ( x, y )  m21  2 x m11  ym20  2 x m01

x y

12   ( x  x )1 ( y  y ) 2 f ( x, y )  m12  2 ym11  x m02  2 ym10

x y

30   ( x  x )3 ( y  y ) 0 f ( x, y )  m30  3x m20  2 x 2 m10

x y

03   ( x  x ) 0 ( y  y )3 f ( x, y )  m03  3 ym02  2 y 2 m01

x y

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Moments of Two-Dimensional Functions

• The normalized central moments are defined as

 pq
 pq  
 00
pq
where   1 for p  q  2,3,....
2

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Moments of Two-Dimensional Functions

• A seven invariant moments can be derived from the

second and third moments:
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 ) 2  3( 21  03 ) 2 
 (3 21  03 )( 21  03 )3( 30  12 )  ( 21  03 )
2 2

© 2002 R. C. Gonzalez & R. E. Woods
 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Moments of Two-Dimensional Functions

•
6  ( 20   02 )(30  12 ) 2  ( 21  03 ) 2 
 411 (30  12 )( 21   03 )
7  (3 21   03 )(30  12 )(30  12 )  3( 21   03 )
2 2


 (312  30 )( 21   03 ) 3(30  12 ) 2  ( 21   03 ) 2 
• This set of moments is invariant to translation,
rotation, and scale change.

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Moments of Two-Dimensional Functions

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

 Digital Image Processing, 2nd ed. [Link]

Regional Descriptors
Moments of Two-Dimensional Functions

Table 11.3 Moment invariants for the images in Figs. 11.25(a)-(e).

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