Image Representation

and Description
 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
Representation & Description
 Segmentation techniques yield raw data in the
form of pixels along a boundary or pixels
contained in a region.
 After segmentation, the image needs to be
described and interpreted.
 Representation: an object may be represented by its
boundary.
 Description: the object boundary may be described by
its length, orientation, or number of concavities...
Representation
 An object can be represented by:

 Its
external characteristics, such as its
boundary.

 Orits internal characteristics, such as its

texture.
These objects are recognized by...…
These objects are recognized by…
Texture Color Context Shape

X X

X X

X X
Description
 The features that represent the image are used
as descriptors.
 representation  boundary

 description  length of the boundary,

orientation of the straight line joining its
extreme points, and the number of concavities
in the boundary.
Description …
 Descriptors should not be sensitive to variations
like :
– Size Change
– Translation
– Rotation
What are invariants?
Invariants are functionals defined on the
image space such that

 I(f) = I(D(f)) for all admissible D

 I(f1), I(f2) “different enough“ for

different f1, f2
Discrimination power
 Boundary (Border) Following

Boundary as a sequence of connected points

The o/p of boundary (or border) following algorithm:

An ordered list of points representing the
boundary of an object

Consider an 8-connected image. The following

algorithm follows the boundary for any closed contour.
 Boundary (Border) Following …
Step 1: Start scanning row-wise from top left corner of the image
matrix.
Step 2: Mark the first object pixel obtained as the start pixel.
Step 3: Based on the previous pixel (p) visited & the currently pixel
(c) being visited, find the next pixel (n). n is found by
searching in the neighbourhood of c, clockwise starting
from position marked s up to the previous pixel p.
s p s p p s s
p c c c c c p c c c
s s s s p p p

Step 4: Mark the current pixel as previous pixel & the next pixel as
the current pixel.
Step 5: Go to step 3
Boundary (Border) Following …

S
P 1C 1 1 1
1 1
1 1
1 1
1 1 1 1
Boundary (Border) Following …

S
1P 1C 1 1
1 1
1 1
1 1
1 1 1 1
Boundary (Border) Following …

S
1 1P 1C 1
1 1
1 1
1 1
1 1 1 1
Boundary (Border) Following …

S
1 1 1P 1C
1 1
1 1
1 1
1 1 1 1
Boundary (Border) Following …

1 1 1 1P
1 1C
1 1 S

1 1
1 1 1 1
Boundary (Border) Following …

1 1 1 1
1 1P
1 1C
1 1 S
1 1 1 1
 Chain Codes
Represent a boundary of a connected region
Why focus on a boundary?
The boundary is a good representation of an object shape
and also requires less memory.
Chain codes: it represents an object boundary by a
connected sequence of straight line segments of specified
length and direction.
The direction of each segment is coded by using a
numbering scheme shown below

4-directional chain code 8-directional chain code

Chain Codes …
Trace the object outline -
follow pixels on boundary
Code directions of movement
Description is
position independent,
orientation dependent
Chain Codes …

Find the 4 directional Chain

Code

1101101030332330322212
Chain Codes …

Find the 8 directional

Chain Code

22120207656764443
Chain Codes …
Unacceptable because
 the resulting chain of codes tends to be quite long

 any small disturbances along the boundary due to

noise or imperfect segmentation cause changes in

the code that may not be related to the shape of
the boundary
Problems with the Chain Code
 Chain code representation is conceptually
appealing, yet has the following two problems
 Dependent on the starting point
 Dependent on the orientation

 To use boundary representation in object

recognition, we need to achieve invariance to
starting point and orientation
 Normalized codes
 Differential codes
 Normalization Strategy
to overcome the starting point problem

33001122

33001122 00112233
30011223 01122330
00112233 11223300 First row gives the
01122330 Sort 12233001 normalized chain code
11223300 rows 22330011 00112233
12233001 23300112
22330011 33001122
23300112 30011223
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:
difference - a chain code: 10103322
1 01 1 - The first difference = 3133030
02 2 - Treating a chain code as a
2 03 3
0 circular sequence, we get
23 1
20 2 the first difference = 31330303
3 21 3

The first difference is rotational invariant.

 Differential Strategy
Normalization for rotation
 Counting (counterclockwise) the number of direction changes
that separate two adjacent element of the code
 Assuming the first difference code represents 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.
90o

33001212 33010122
01011311
01011311 01131101
Shape Numbers

 The shape number of a boundary obtained from a

chain code is defined as the smallest magnitude of the
circular first difference.

 The order of the shape number is defined as the

number of digits in its representation.
Shape Numbers …
Find the shape number & order of the given boundary.

4-direction chain code :03032211

First difference :3133030

Circular first difference :31330303

Shape number :03033133

Order :8
Shape Number …
1
Shape number of the boundary definition:
the first difference of smallest magnitude
2 0
The order n of the shape number:
the number of digits in the sequence
3
Shape Number …
 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
Polygon Approximation
Represent an object boundary by a polygon

Minimum perimeter
Object boundary
polygon
Minimum perimeter polygon consists of line segments that
minimize distances between boundary pixels.
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
Distance-Versus-Angle Signatures

Represent an 2-D object boundary in term of a 1-D

function of radial distance with respect to q.

2D boundary ⇒ 1D function
Distance from centroid as function of angle
not applicable to all shapes
Distance-Versus-Angle Signatures
Represent an 2-D object boundary in term of a 1-D function
of radial distance with respect to q.
Distance-Versus-Angle Signatures

For Circle, Signature

r (q )  A
For Square, Signature

r(q )=Asec(q ) for 0<=q <=
4
 
r(q )=Acosec(q ) for <q <=
4 2
Fourier Descriptor
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 :
Fourier descriptor :

1 K 1
a (u )   s(k )e 2uk / K
K k 0
Reconstruction formula

1 K 1
Boundary s(k )   a (u )e2uk / K
points K k 0
Example: Fourier Descriptor
Examples of reconstruction from Fourier descriptors

1 P 1
sˆ( k )   a (u )e 2uk / K
K k 0

P is the number of
Fourier coefficients
used to reconstruct
the boundary
Eccentricity
 Ratio of the major to the minor axis
 Major axis = the line connecting the two extreme
points that comprise the diameter
 Minor axis = the line perpendicular to the major
axis
Statistical Moments
Definition: the nth moment
K 1
n ( r )   ( ri  m)n g ( ri )
i 0
Example of moment:
where K 1 The first moment = mean
m   ri g ( ri ) The second moment = variance
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
Regional Descriptors
Purpose: to describe regions or “areas”

 Area
 Perimeter
 Compactness
 Topological descriptors
 Texture
Regional Descriptors …
Regional Descriptors …
- Area of the region: the number of pixels in the region
- perimeter = length of its boundary
- Compactness
A( R) Example: a circle is the most
C 2 compact shape with C = 1/4
P ( R)
where A(R) and P(R) = area and perimeter of region R
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
Example: Euler number

E = -1

E=0
Any Questions ?