Representation and Description

I. Representation

  • Image can be segmented(represented) by boundaries (of regions).
  • These data can be used directly to describe the image
  • Question: More useful in the computation of descriptors?

I.1. Chain Codes

  • Chain codes are a classical type of computer program that can be used to represent the shape of objects.
  • The application fields: They can therefore be used in the vision system of a robot. Much computer vision is done with neural nets (a fundamentally different kind of computer program).

Fig. 1. Triangle and 8-directionalchain code

Chain codes for triangle are:NE, SE, W.

Chain codes for this figure are:

W, W, W, N, N, E, S, E, N, E, S, S

Using numbers in writing chain codes we have

4, 4, 4, 2, 2, 0, 6, 0, 2, 0, 6, 6

Fig. 2. Digital boundary with resampling grid superimposed and result of resampling

Fig. 3. 4-directional chain code and 8-directional chain code

Remark:For each starting point of a chain code we have other result sequence of numbers forms.

I.2. Skeleton

  • The skeleton of the plane region in image is using to (reduced) representing the structural shape of the region.
  • The technique usually used is a thinning algorithm.
  • Blum [1967] was proposed the skeleton technique via the medial axis transforms (MAT):

Let R is a region with border (boundary)B.

For each point p in R, if p has more than one closest neighbor in B, it is said to p belong to the medial axis (skeleton) of R.

Fig. 4. Medial axis of three simple regions

Remark:

The direct implementation of definition of skeleton typically is expensive computation.Here, implementation potentially involves calculating the distance from every interior point to every point on the boundary of a region.

The thinning algorithm: iteratively delete edge points of a region subject to the constraints that deletion of this points:

a)does not remove the end points

b) does not break connectivity

c)does not cause excessive crossing of the region.

Example:

  • Let R is binary region with value 1 and background have value 0.
  • Let p1 has 8-neighbors. Point p1 will be deleted if the following conditions are satisfied:

a)2  N(p1)  6

b)T(p1) = 1

c)p2.p4.p6 = 0

d)p4.p6.p8 = 0

where N(p1) = p2 + p3 + ...+p8+p9, is non-zero neighbors of p1,

and, T(p1) is the number of 0-1 transitions in the ordered sequence p2, p3,..,p8,p9, p2.

For example, N(p1) = 4,

T(p1) = 3

Condition c) and d) maybe changed to

c’) p2.p4.p8 = 0

d’) p2.p6.p8 = 0

If all conditions are satisfied the point is flagged for deletion. However, the point is not deleted until all border points have been processed.

II. Boundary Description

II.1. Some Simple Descriptors

  1. The length of a boundary is one of the simplest descriptors of region. For example, the number of pixels along a boundary gives a rough approximation of its length.
  1. The line conected two extreme points that comprise the diameter is called major axis. The minor axis of a boundary is difined as the line perpendicular to the major axis.
  2. The box passing through four points of intersection of the boundary with two axes is called the basic rectangle.
  3. The ratio of the major to the minor axis is called the eccentricity of the boundary.
  4. The curvature is defined as rate of the change of slope.

II.2. Fourier Descriptors

Fig. 5. Figure is given by K points

  1. Let K is some positive integer and figure is given by K points P0(x0,y0), P1(x1,y1), P2(x2,y2), ..., PK-2(xK-2,yK-2), PK-1(xK-1,yK-1).
  2. Define the sequence of a complex numbers:

s(k) = xk + i*yk, k = 0, 1, 2, ..., K-1(1)

we have its discrete Fourier transform (DFT):

for u = 0, 1, 2, ..., K-1.

  1. The complex coefficients a(u), u=0,1,2,...,K-1, are called Fourier descriptors.
  2. The inverse Fourier transform:

for n = 0, 1, 2, ...,K-1.

  1. Suppose that, a(u) = 0, for all u P. Then, the approximation to s(n) are:
  1. Properties

Transformation / Boundary / Fourier Descriptors
Identify / s(k) / a(u)
Rotation / sr(k) = s(k)ej / ar(u) = a(u)ej
Translation / st(k) = s(k) + xy / at(u) = a(u) + xy(u)
Scaling / ss(k) = s(k) / as(u) =  a(u)
Starting Point / sp(k) = s(k-h) / ap(u) = a(u)e-j2 h u / K

II.3. Statistical Descriptors

  1. Let vr = v(r), r=0,1,2,...,N-1 is a function, which describes a some boundary segment and p(vr) is an estimate of the probability of value vr occurring. The nth moment of v is
  1. The quantity m is average of v:
  1. In some case the probability of vr is used as p(vr) = 1/N.
  2. In some approach, the normalized histogram g(r) treated as the probability of value r:

and

  1. Properties:

Statistical descriptors are invariant for translation and starting point transformation.

III. Regional Descriptors

III.1. Some Simple Descriptors

  1. The area of a region (is defined as the number of pixels in the region).
  2. The perimeter of a region (is the length of its boundary).
  3. The compactness of a region (is defined as (perimeter)2/area).
  4. The mean, median of a region.
  5. The maximum and the minimum gray-level value

III.2. Topological Descriptors

  1. Example:Figure has two holes. The the number of holes in region is property, which is unaffected by any deformation.
  2. Another example: Figure has a fixed number of conected components by any deformations.
  3. The Euler number:

Define:

  • H is the number of holes in figure;
  • C is the number of conected components in the figure. then

E = C – H

is the Euler number of the figure.

For example, in the figure with two characters “A” and “B” have Euler numbers are 0 and -1.

Regions represented by straight-line segments (polygonal network) have a particular Euler number:

Define:

  • V is number of vertices
  • Q is number of edges
  • F is number of faces

Then, Euler formula:

V – Q + F = C – H

(H – number of holes, C – number of connected components). We have Euler number:

E= C – H = V – Q + F

For example, Euler number is -2:

V = 7;Q = 11;H = 3; F = 2; C = 1;

C – H = -2

V – Q + F=-2

III.3. Moments of two dimensional functions

The moment of order p+q is defined as:

and

The central moments are defined as:

Properties:

1)00= m00

2)10= 0

3)01= 0

4)11= m11 – m10= m11 – m01

5)20=m20 – m10

6)02=m02 – m01

7)30=m30 – 3m20 + 2m10

8)03=m03 – 3m02 + 2m01

9)21=m21 – 2m11 – m20 + 2m01

10)12=m12 – 2m11 – m02 + 2m10

The normalized central moments:

A set of seven moments is invariant totranslation, rotation, and scale change:

1=20 + 02

2=(20-02)2 + 4

3=(30-312)2 + (321-03)2

4=(30+312)2 + (21+03)2

1