Digital Image Processing

Chapter 11:

Image Description and

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

chain code
Gonzalez and Richard E.

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

(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
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.
(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 (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 .

(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

(Images from Rafael C. Gonzalez and Richard E.

Wood, Digital Image Processing, 2nd Edition.
 Convex Hull Algorithm
nput : A set of points on a cornea boundary
utput: A set of points on a boundary of a convex hull of a cornea
Sort the points by x-coordinate to get a sequence p1, p2, … ,pn
or the upper side of a convex hull
Put the points p1 and p2 in a list Lupper with p1 as the first point
For i = 3 to n
Do append pi to Lupper
While Lupper contains more than 2 points and the last 3
points in Lupper do not make a right turn
Do delete the middle point of the last 3 points from Lupper
Turn
Turn Left
Turn
Right NOK!
Right
OK!
OK!
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
Turn
14. Return L Right
Turn
Right OK!
Turn
OK!
Left
NOK!
Skeletons
Obtained from thinning or skeletonizing processes

Medial axes (dash lines)

(Images from Rafael C. Gonzalez and Richard E.

Wood, Digital Image Processing, 2nd Edition.
 Thinning Algorithm
ncept: 1. Do not remove end points
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 p 8 p 1 p 4 =
for the thinning
p7 p6 p5 algorithm
Example
Let N ( p1 )  p2  p3    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) = 4
T(p ) = 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
p  p  p  0 p8 p1 p4
c) 2 4 6
p7 p6 p5
d) p4  p6  p8  0
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.
Example: Skeletons Obtained from the Thinning Alg.

Skeleton

(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
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

(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

(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. 000310330130031303
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.