Introduction to Pattern Recognition

Dokuz Eylül University Computer Engineering Department

(25 September, 2000 – 5 January, 2001)

□ Contents:

1. What is Pattern Recognition?

(Introduction to Pattern Recognition) 3

1 What is Pattern Recognition? 2 What for?

A typical example:

• character recognition characters as an example of patterns

But how?

• By taking all pixels as inputs?

• By some shape information? e.g.

∗ area within boundary;

∗ degree of how boundary curve. These are called features.

Feature space:

• l features forms feature vector x = (x_{1}, x_{2}, ⋯, x_{l})

for each object to be recognized.

• straight line separates the classes ⇓ in more general

separation by hyper-plane In short:

• pattern recognition is a classifier

Yet another example

• machine vision (robot eye);

• face recognition;

• speech recognition;

• computer-aided diagnosis;

• what else?

Problems:

• What features are to be used to classify?

• What is the optimum number of features?

• How is the classifier designed?

Keywords:

• features, feature-space, feature-vectors, hyperplane, classifiers,

(Introduction to Pattern Recognition) 5

3 supervised/unsupervised

Supervised pattern recognition

• classifies unknown data using a set of training data.

• Learning with teacher.

Unsupervised pattern recognition (clustering)

• unravel the underlying similarities and cluster similar vectors together using a set of feature vectors e.g.

– Assume we are interested in studying relations among a country’s GNP, the level of people’s illiteracy, and a children’s mortality rate. ⇓

three-dimensional feature vectors

• Learning without teacher.

(Introduction to Pattern Recognition) 6

4 Hand-written character recognition – revisit

What should be employed as features:

1. Pixels;

2. Geometric Features;

3. Fourier Features;

4. Chain Codes;

5. Moment-based Features;

6. Neural Networks.

Verify each technique by your own several handwriting figures, say, 1’s, 5’s, and 8’s, on a scale paper (with each character being on 1cm x 1cm = 100 pixels section for instance).

1. Each pixel’s state as a set of features:

• draw 20 different writings for each character;

• keep the pixel data for the future reference.

2. Geometric Features:

• Perimeter

P = N−1 ; ∑ ; i=1 ∥x_{i+1} − x_{i}∥ + ∥x_{N} − x_{1}∥  (1)

• Area

– Measure the area enclosed by a boundary by counting the number of pixels.

• roundness ratio

r = \frac{P^{2}}{4πA}  (2)

• Bending energy; (later in detail)

• The number of corners in the boundary; (later in detail)

• The number of holes.

3. Fourier Features:

Let

(x_{k}, y_{k}), k = 0, 1, ⋯, N − 1.  (3)

be the coordinates of N samples on the boundary of an image region. For each pair (x_{k}, y_{k}) we define the complex:

u_{k} = x_{k} + jy_{k}.  (4)

For the N u_{k} points we obtain the DFT f_{l}

f_{l} = N−1 ; ∑ ; k=0 u_{k} exp(−j2πlk/N), l = 0, 1, ⋯, N − 1. (5)

and call them l Fourier Descriptors of the boundary.

Another way is from curvature function of the boundary:

k(t) = \frac{dθ(t)}{dt}.  (6)

When we measure the length of the boundary at a point by the number of pixels n between this point and the origin of the curve, the curvature of the boundary is approximated by

θ_{n} = tan^{−1} \frac{y_{n+1} − y_{n}}{x_{n+1} − x_{n}}, n = 0, 1, ⋯, N − 1.  (7)
k_{n} = θ_{n+1} − θn, n = 0, 1, ⋯, N − 1.  (8)

(Introduction to Pattern Recognition) 9

Bending energy and number of corners revisited:

Then we can define

• bending energy at a point n as

E(n) = \frac{1}{P} n−1 ; ∑ ; i=0 |k_{i}|^{2}  (9)

and

• number of corners in the boundary contour as

– the number of points where the curvature k_{i} takes large values (infinity in theory)

(Introduction to Pattern Recognition) 10

4. Chain codes: □ Chain code (d_{1}, d_{2}, ⋯, d_{N}) is defined as:

a series of direction from pixel (x_{i}, y_{i}) to (x_{i+1}, y_{i+1}) on the boundary with, say, 8 possible directions.

• Direction and Direction-length Features:

\frac{the number of each direction}{the total number of chain codes}  (10)

or

\frac{the total length of the line segments in each direction}{the total length of the boundary line} (11)

⇒ 8 features

• Curvature Features:

– Is an external angle between adjacent two edges at a corner of the polygon that is formed by the line segments ∗ concave (smaller than 180^{∘}) or

∗ convex (larger than 180^{∘})? when the boundary is scanned in the clockwise sense.

– 48 possible cases

∗ Concave cases:

· 01 02 03 12 13 14 23 24 25 34 35 36 45 56 47 50 56 57 60 61 67 70 71 72

∗ Convex cases:

· 05 06 07 10 16 17 20 21 27 30 31 32 41 42 43 52 53 54 63 64 65 74 75 76

– Occurrence percentage of each of these cases.

⇒ 48 features □ Summary:

What features can be used to recognize hand-written characters?

• Boundary-based:

– Single feature:

∗ Perimeter of the boundary;;

∗ Area inside the boundary;

∗ Roundness ratio;

∗ Number of corners in the boundary;

∗ Number of holes.

– Multiple features: ∗ Fourier features;

∗ Chain codes.

• Pixel-based:

– Neural-networks ∗ Perceptron learning

∗ Genetic algorithm Genetic Algorithm (GA)

□ An example:

• Neural network with 100 input neurons and 10 output neurons with no hidden layer:

– hand-written-characters of the figures from zero to nine drawn on the 10x10 pixels are to be recognized

– by activating only the i-th neuron of the output remaining other neurons not activated.

□ From a biological analogy, the followings are defined.

Chromosome: Each chromosome is comprised of 1000 genes, representing 1000 weights of one individual neural network.

Population:

A number of individuals, say 100, create a population.

Initialization: All genes of all chromosomes are initialized at random, taking a value ranging from zero to one. This construct the first generation.

Fitness:

The ability of each individual is evaluated and assigned its fitness value. In our current problem, for example, each individual given a set of weights is evaluated by giving each output neuron 0.1 if the output is correct and 0 otherwise. Note that in the first generation, every individual performs rather badly but diferrently, since weights are determined at random.

Selection:

Two parents are selected to produce one offspring. Individuals of better performance should be more likely to be selected. For example, (1) selection is always from upper half of the population in which individuals have been sorted with an order of their fitness, or (2) selection is made sot that the probability is proportional to the fitness value. The production of an offspring is by employing the following two operations: crossover and mutation Crossover:

A same position of the two parent chromosomes are determined at random (each time when they are selected), and cross them over.

Mutation: For each gene of the offspring chromosome, produce one integer random number from 0 to 99. If the value is zero, then the gene is replaced with the other weight value also created at random each time.

□ Algorithm:

1. Initialization: Initialize all the weight values of all the individuals in the first generation at random so that it lies on [0, 1].

2. Evaluation: Evaluate fitness of all the individuals of the population.

3. Reproduction:

(1) Select two parents from the population.

(2) Crossover the two parents and produce one offspring.

(3) Mutate the offspring.

(4) Repeat (1) to (3) above until new generation of same size is obtained.

4. Repeat 2. to 3. above until the perfect solution is obtained or prespecified generations is reached.

Chapter 2.

Features based on Linear Transformation.

• Generation of features using linear transforms of the input samples.

• Appropriate transform removes information redundancy and reduce feature space dimension, leading to information packing.

e.g.,

– Fourier coefficients as features: ∗ most of the energy lies in the low-frequency components due to the high correlation between pixels and ∗ we can neglect low-energy, high-frequency coefficient with little loss of information.

(Introduction to Pattern Recognition) 18

□ Fourier Coefficient (revisit).

We can expand any continuous function f(x) as:

f(x) ≃ ∞ ; ∑ ; k=1 a_{k} cos kx + b_{k}sinkx  (12)

where we can calculate the Fourier coefficient a_{k} and b_{k} as

a_{k} = ∫_{−π}^{π} f(x) cos kx dx  (13)
b_{k} = ∫_{−π}^{π} f(x) sin kx dx  (14)

(15)

(a_{k} and b_{k} are called higher frequency component for larger k and vice versa.)

• Exercise

Obtain the Fourier expansion of the followings. (1) y = x

(2) y = x^{2}

The other formulation

f(x) ≃ ∞ ; ∑ ; k=−∞ c_{k} exp(−jkx)  (16)

where

c_{k} = ∫_{−π}^{π} f(x) exp(jkx) dx  (17)

• Exercise

Verify this employing the relations exp(−jkx) = cos kx + j sin kx

(Introduction to Pattern Recognition) 19

□ 1-D Discrete Fourier Transform.

• DFT:

y(k) = \frac{1}{\sqrt{N}} N−1 ; ∑ ; n=0 x(n) exp(−j\frac{2π}{N}kn), k = 0, 1, ⋯, N − 1.

(18)

• Inverse-DFT:

x(n) = \frac{1}{\sqrt{N}} N−1 ; ∑ ; k=0 y(k) exp(j\frac{2π}{N}kn), n = 0, 1, ⋯, N − 1.

(19)

• An example of N = 4: DFT of x(0), x(1), x(2), x(3)

e.g.

y(1) = \frac{1}{2}\{x(0) exp(0) + x(1) exp(−j\frac{π}{2})
+x(2)(−j\frac{2π}{2}) + x(3) exp(−j\frac{3π}{2})\}  (20)
( \begin{matrix}y(0) \\ y(1) \\ y(2) \\ y(3) \end{matrix} ) = ( \begin{matrix}1 & 1 & 1 & 1 \\ 1 & j & −1 & −j \\ 1 & −1 & 1 & −1 \\ 1 & −j & −1 & j \end{matrix} ) ( \begin{matrix}x(0) \\ x(1) \\ x(2) \\ x(3) \end{matrix} )  (21)

Or

y = Ax  (22)

where

A_{mn} = exp(−j\frac{2π}{N})(m − 1)(n − 1)  (23)

• Inverse Transformation

A^{−1} = ( \begin{matrix}1 & 1 & 1 & 1 \\ 1 & −j & −1 & j \\ 1 & −1 & 1 & −1 \\ 1 & j & −1 & −j \end{matrix} )  (24)

• Orthogonal linear transformation In a linear transform

y(k) = N−1 ; ∑ ; n=0 x(n)a_{n}(k),  (25)

if

a_{m}(k)a_{n}(k) = δ_{mn}  (26)

holds, then the linear transformation is called unitary (orthogonal in real variables).

□ 2-D DFT

Y (k, l) = \frac{1}{N} N−1 ; ∑ ; m=0 N−1 ; ∑ ; n=0 X(m, n) exp(−j\frac{2π}{N}km) exp(−j\frac{2π}{N}ln)

(27)

X(m, n) = \frac{1}{N} N−1 ; ∑ ; m=0 N−1 ; ∑ ; n=0 Y (k, l) exp(j\frac{2π}{N}km) exp(j\frac{2π}{N}ln)

(28)

□ Other Linear Transformation

• HAAR

• HADAMAR

• WAVELET (Though this won’t be studied in this course.)

(Introduction to Pattern Recognition) 22

□ Hadamar Transform: For a vector x of N samples where N = 2^{n}, the transform and its inverse transform are:

y = H_{n}x, x = H_{n}y  (29)

where

H_{n} = H_{1} ⊗ H_{n−1}  (30)

and

H_{1} = \frac{1}{\sqrt{2}} ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} )  (31)

Here ⊗ denotes the Kronecker product for two matrices:^{1}

[A ⊗ B]_{ij} = A_{ij}B  (35)
A = ( \begin{matrix}1 & 2 \\ 3 & 4 \end{matrix} )  (32)
B = ( \begin{matrix}5 & 6 \\ 7 & 8 \end{matrix} )  (33)
A ⊗ B = ( \begin{matrix}5 & 6 & 10 & 12 \\ 7 & 8 & 14 & 16 \\ 15 & 18 & 20 & 24 \\ 21 & 24 & 28 & 32 \end{matrix} )  (34)

1 for example, if and then we define

□ Haar Transform:

Haar function h_{k}(z), which is continuous and are defined in [0, 1], for the transform of L = 2^{n} dimensional vector x:

(1) Decomposition of the order k into two integers p and q.

k = 2^{p} + q − 1, k = 0, 1, ⋯, L − 1.  (36)

The decomposition is unique when

\{ \begin{matrix}q = 0 or 1 & if p = 0 \\ 0 ≤ p ≤ n − 1, 0 < q ≤ 2^{p} & if p ≠ 0 \end{matrix}  (37)

(2) Haar functions are

h_{0}(z) ≡ h_{00}(z) = \frac{1}{\sqrt{L}}  (38)

and

h_{k}(z) ≡ h_{pq}(z) = \frac{1}{\sqrt{L}} \{ \begin{matrix}2^{\frac{p}{2}} & if \frac{q−1}{2^{p}} ≤ z < \frac{q−\frac{1}{2}}{2^{p}} \\ −2^{\frac{p}{2}} & if \frac{q−\frac{1}{2}}{2^{p}} ≤ z < \frac{q}{2^{p}} \\ 0 & otherwise in [0, 1] \end{matrix} (39)

(3) Then the Haar transform matrix of order L consists of rows of the Haar function computed at

z = \frac{m}{L}, m = 0, 1, 2, ⋯ L − 1.

• Exercise

Obtain the 8 × 8 transform matrix.

(Introduction to Pattern Recognition) 24

• An example of n = 3, that is, L = 8.

k = 2^{p} + q − 1, k = 0, 1, ⋯, 7  (40)

where

\{ \begin{matrix}q = 0 or 1 & if p = 0 \\ 0 ≤ p ≤ 2, 0 < q ≤ 2^{p} & if p ≠ 0. \end{matrix}  (41)

So,

p=0 q=0 k=0
q=1  k=1
(0 < q ≤ 2) (k = 1 + q)
p=1 q=1 k=2
q=2  k=3
(0 < q ≤ 4) (k = 3 + q)
p=2 q=1 k=4
q=2  k=5
q=3  k=6
q=4  k=7

Hence,

k 0 1 2 3 4 5 6 7
p 0 0 1 1 2 2 2 2
k 0 1 1 2 1 2 3 4

(Introduction to Pattern Recognition) 25

Then the Haar functions are:

h_{1}(z) ≡ h_{01}(z) = \frac{1}{\sqrt{8}} \{ \begin{matrix}1 & if & −1 ≤ z < \frac{1}{2} \\ −1 & if & \frac{1}{2} ≤ z < 1 \end{matrix}  (42)
h_{2}(z) ≡ h_{11}(z) = \frac{1}{\sqrt{8}} \{ \begin{matrix}\sqrt{2} & if 0 ≤ z < \frac{1}{4} \\ −\sqrt{2} & if \frac{1}{4} ≤ z < \frac{1}{2} \\ 0 & otherwise in [0, 1] \end{matrix} (43)

h_{3}(z) ≡ h_{12}(z) = \frac{1}{\sqrt{8}} \{ \begin{matrix}\sqrt{2} & if \frac{1}{2} ≤ z < \frac{3}{4} \\ −\sqrt{2} & if \frac{3}{4} ≤ z < 1 \\ 0 & otherwise in [0, 1] \end{matrix} (44)
· · · · · ·
h_{7}(z) ≡ h_{24}(z) = \frac{1}{\sqrt{8}} \{ \begin{matrix}2 & if \frac{3}{4} ≤ z < \frac{7}{8} \\ −2 & if \frac{7}{8} ≤ z < 1 \\ 0 & otherwise in [0, 1] \end{matrix} (45)

and

\begin{matrix}h_{0}(z) & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ h_{1}(z) & 1 & 1 & 1 & 1 & –1 & –1 & –1 & –1 \\ h_{2}(z) & \sqrt{2} & \sqrt{2} & −\sqrt{2} & −\sqrt{2} & 0 & 0 & 0 & 0 \\ h_{3}(z) & 0 & 0 & 0 & 0 & \sqrt{2} & \sqrt{2} & −\sqrt{2} & −\sqrt{2} \\ h_{4}(z) & 2 & –2 & 0 & 0 & 0 & 0 & 0 & 0 \\ h_{5}(z) & 0 & 0 & 2 & –2 & 0 & 0 & 0 & 0 \\ h_{6}(z) & 0 & 0 & 0 & 0 & 2 & –2 & 0 & 0 \\ h_{7}(z) & 0 & 0 & 0 & 0 & 0 & 0 & 2 & –2 \end{matrix}

(Introduction to Pattern Recognition) 26

Since

H_{ij} = \frac{1}{\sqrt{L}}h_{j}(\frac{j}{L}),  (46)

we obtain

H = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & −1 & −1 & −1 & −1 \\ \sqrt{2} & \sqrt{2} & −\sqrt{2} & −\sqrt{2} & & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \sqrt{2} & \sqrt{2} & −\sqrt{2} & −\sqrt{2} \\ 2 & −2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & −2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & −2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & −2 \end{matrix} ) (47)

(Introduction to Pattern Recognition) 27

□ Features for Texture Recognitions: To describe an image by fine or coarse, smooth or irregular, homogeneous or inhomogeneous and so forth

• First-order Statistics Features

• Second-order Statistics Features □ First-order Statistics Features:

Let

P (I) = \frac{number of pixels with gray level I}{total number of pixels in the region} (48)

Assume that we have N_{g} gray levels.

• Then, the moments

m_{i} = E[I^{i}] = N_{g}−1 ; ∑ ; I=0 I^{i}P (I)  (49)

• and the central moment

μ_{i} = E[(I − E[I])^{i}] = N_{g}−1 ; ∑ ; I=0(I − m_{I})^{i}P (I)  (50)

⋆ The most frequently used central moments:

· μ_{2} = σ^{2} ⋯ variance a measure of the histogram width: how much the gray levels differ from the mean

· μ_{3} ⋯ skewness

the degree of histogram asymmetry around the mean · μ_{4} ⋯ kurtosis

a measure of the histogram sharpness

- platykurtic (sharp);

- mesokurtic (medium);

- leptokurtic (dull).

(Introduction to Pattern Recognition) 29

• Entropy

H = −E[log_{2} P (I)] = − N_{g}−1 ; ∑ ; I=0 P (I) log_{2} P (I) (51)

a measure of histogram uniformity: The closer to the uniform distribution (P (I) = const.), the higher the H.

• Exercise Calculate μ_{1}, μ_{2}, μ_{3} and H of the four histograms bellow.

histgram-1 histgram-2 histgram-3 histgram-4
P (0)  5  1  7  5
P (1)  6  14  8  5
P (2)  5  1  1  5
broad?  yes  no  medium  yes
symmetric?  yes  yes  no  yes
sharp?  no  yes  medium  no
uniform? medium  no  no  yes

□ Second-order Statistics Features: The first-order statistics provide information as for the gray level distribution of the image, but do not give any information about the relative positions of the gray levels within the image, such as

- Are all low-value gray levels positioned together?

- Are they interchanged with the high-value ones?

That is, the second-order statistics indicate how two specific level I_{1} and I_{2} occupy pixels in a line of slope ϕ separating with a distance d. Then, a two-dimensional histogram:

P (I_{1}, I_{2}) = \frac{number of pairs of pixels with values (I_{1}, I_{2})}{total number of possible pairs}

(52)

with respect to

⋆ the relative distance d measured in pixel numbers

e.g., d = 1 for neighboring pixels.

⋆ the orientation ϕ quantized in for directions: horizontal, diagonal, vertical, and anti-diagonal (0^{∘}, 45^{∘}, 90^{∘}, 135^{∘}).

(Introduction to Pattern Recognition) 31

For each of the histograms the co-occurrence matrix is defined as:

A^{ϕ}(d) = P (I_{1}, I_{2})  (53)

Take for example the image with four gray levels bellow:

d = 1 d = 1 d = 2
ϕ = 0^{∘} ϕ = 45^{∘} ϕ = 135^{∘}
P (0, 0)  2  0  2
P (0, 1)  1  1  0
P (0, 2)  1  2  0
P (0, 3)  0  1  0
P (1, 1)  1  0  2
P (1, 2)  0  1  0
P (1, 3)  0  1  2
P (2, 2)  3  0  0
P (2, 3)  3  3  0
P (3, 3)  1  0  0
total sum 12  9  4

• The first one may be denoted as:

\frac{1}{12} ( \begin{matrix}2 & 1 & 1 & 0 \\ ⋆ & 1 & 0 & 0 \\ ⋆ & ⋆ & 3 & 3 \\ ⋆ & ⋆ & ⋆ & 1 \end{matrix} ) .  (54)

However we usually adopt the way:

A^{0}(1) = \frac{1}{24} ( \begin{matrix}4 & 1 & 1 & 0 \\ 1 & 2 & 0 & 0 \\ 1 & 0 & 6 & 3 \\ 0 & 0 & 3 & 2 \end{matrix} ) ,  (55)

by making every i-j entry identical to j-i entry for i ≠ j, and multiplying diagonal element by two for compensation.

(Introduction to Pattern Recognition) 33

□ Features for texture recognition

— 1. Features using occurrence matrix.

• Angular second moment:

Xasm = N_{g}−1 ; ∑ ; i=0 N_{g}−1 ; ∑ ; j=0(P (i, j))^{2}  (56)

⋆ A measure of the smoothness.

· If indeed all pixels are of the same gray level I = k, then P (k, k) = 1 and P(i,j)=0 for i ≠ k or j ≠ k; · Or, if we have all possible pairs of gray levels with equal probability 1/R, then Xasm = R/R^{2} = 1/R

⋆ The less smooth the region is, the more uniformly distributed P (i, j) and the lower the Xasm.

• Contrast:

Xcon = N_{g}−1 ; ∑ ; n=0 n^{2}( N_{g}−1 ; ∑ ; {j=0 \atop |j−i|=n} N_{g}−1 ; ∑ ; i=0 P (i, j))  (57)

⋆ A measure of the image contrast.

· ∑_{i} ∑_{j} P (i, j) is the percentage of pixel pairs whose intensity differs by n. · The n^{2} dependence weights the big differences more.

⋆ Xcon takes high values for images of high contrast.

(Introduction to Pattern Recognition) 34

• Inverse difference moment:

Xidm = N_{g}−1 ; ∑ ; i=0 N_{g}−1 ; ∑ ; j=0 \frac{P (i, j)}{1 + (i − j)^{2}}  (58)

⋆ This feature takes high values for low-contrast images due to the inverse (i − j)^{2} dependence.

• Entropy:

Xentropy = − N_{g}−1 ; ∑ ; i=0 N_{g}−1 ; ∑ ; j=0 P (i, j) log_{2} P (i, j)  (59)

⋆ A measure of randomness. ⋆ Higher values for more random images.

□ Run Length Features

— 2. Features using gray level run lengths.

• Gray Level Run:

– a set of consecutive pixels having the same gray level.

• Run Length Features:

– an information related to the number of each gray level

appears in the image by itself, in pairs, and so on.

• Run Length Matrix Q^{ϕ}:

– the (i-j) element is the number of times a gray level (i − 1) appears in the image with run length j.

– the mesearment is along the line whose angle is ϕ from

the horizontal line. In the example we used before, i.e.

I = ( \begin{matrix}0 & 0 & 2 & 2 \\ 1 & 1 & 0 & 0 \\ 3 & 2 & 3 & 3 \\ 3 & 2 & 2 & 2 \end{matrix} )  (60)

Q^{0^{∘}} = ( \begin{matrix}0 & 2 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 0 \end{matrix} ) or Q^{45^{∘}} = ( \begin{matrix}4 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 \end{matrix} )  (61)

(Introduction to Pattern Recognition) 36

□ Five Run Length Features: Under the assumption that we have N_{g} gray levels and the largest possible run length in the image is N_{r}, we define them as follows:

• Short run emphasis:

Ysre = \frac{N_{g} ; ∑ ; i=1 N_{r} ; ∑ ; j=1(Q(i, j)/j^{2})}{total number of run length}  (62)

• Long run emphasis:

Ylre = \frac{N_{g} ; ∑ ; i=1 N_{r} ; ∑ ; j=1(Q(i, j)j^{2})}{total number of run length}  (63)

• Gray level non-uniformity:

Ygln = \frac{N_{g} ; ∑ ; i=1( N_{r} ; ∑ ; j=1 Q(i, j))^{2}}{total number of run length}  (64)

• Run length non-uniformity:

Ygln = \frac{N_{r} ; ∑ ; j=1( N_{g} ; ∑ ; i=1 Q(i, j))^{2}}{total number of run length}  (65)

• Run percentage:

Yrp = \frac{N_{g} ; ∑ ; i=1 N_{r} ; ∑ ; j=1 Q(i, j)}{total possible runs in the image}  (66)

□ Some remarks:

• The total number of run lengths in the matrix is

N_{g} ; ∑ ; i=1 N_{r} ; ∑ ; j=1 Q(i, j)  (67)

which takes the value 9 for ϕ = 0^{∘}, and 16 for ϕ = 45^{∘} in the equation (61).

• Short run emphasis:

– Ysre emphasizes small run lengths due to the division by j^{2};

– Thus Ysre is expect to be large for coarser image.

• Long run emphasis:

– Ylre gives emphasis to long run lengths due to the division by j^{2};

– Thus Ylre is expect to be large for smoother image.

• Gray level non-uniformity:

– The term ∑_{j}^{N_{r}} Q(i, j) is the total number of run length for each gray level.

– Large run length values contribute a great deal becaus of the square.

– When runs are uniformly distributed among the gray

levels, Ygln takes small values.

• Run length non-uniformity:

– In a similar way as Ygln, Yrln is a measure of run length nonuniformity.

• Run percentage:

– If all runs had length equal to one, that is, the total number of pixels Yrp takes low values for smooth images.

□ Examples:

For an image:

I = ( \begin{matrix}0 & 0 & 2 & 2 \\ 1 & 1 & 0 & 0 \\ 3 & 2 & 3 & 3 \\ 3 & 2 & 2 & 2 \end{matrix} )  (68)

we have^{2}

Q^{0} = ( \begin{matrix}0 & 2 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 0 \end{matrix} )  (69)

and

Ysre = \frac{2/4 + 1/4 + \{1 + 1/4 + 1/9\} + \{2 + 1/4\}}{9}
Ylre = \frac{\{2 · 4\} + \{1 · 4\} + \{1 + 1 · 4 + 1 · 9\}\{2 + 1 · 4\}}{9}
Ygln = \frac{4 + 1 + 9 + 9}{9}
Yrln = \frac{9 + 25 + 1 + 0}{9}
Yrp = \frac{9}{16}

(70)

2 Here we calculate with Q^{0}, but usually we use {Q^{0} + Q^{45} + Q^{90} + Q^{135}}/4. Guess the reason.

(Introduction to Pattern Recognition) 40

□ Coarse, smooth, uniform?:

An example of N_{g} = 2:

(Introduction to Pattern Recognition) 41

□ Bayes Decision Theory

— for the design of classifiers.

As we have learned so far, classifiers classify unknown patterns into the most probable class.

Then what “most probable” means?

• Moreover Pattern Recognition is more or less statistical due to:

∗ statistic nature of feature selection;

∗ statistic variation of patterns;

∗ noise in employing sensors.

Hence we study here the Baysean Statistical Theory.

• When we classify an unknown pattern which is represented by a feature vector x, we consider M conditional probability

p(ω_{i}|x) i = 1, ⋯, M  (71)

called a posteriori probability.

• Then we define “the most probable class” as ω_{i} with the highest p(ω_{i}|x).

• The other statistical quantities:

– a priori probability p(ω_{i});

– likelihood function of ω_{i} w.r.t. x;

– probability distribution function (pdf) of x.

• Baysian rule is

p(ω_{i}|x) = \frac{p(x|ω_{i})p(ω_{i})}{M ; ∑ ; k=1 p(x|ω_{k})p(ω_{k})}  (72)

where the denominator

M ; ∑ ; k=1 p(x|ω_{k})p(ω_{k}) = p(x).  (73)

(Introduction to Pattern Recognition) 43

• Example-1:

· We have two bags which we can not tell the difference from outside. · One bag called R includes 70 red balls and 30 blue balls. · The other bag called B includes 30 red balls and 70 blue balls. · When we take one bag at random and pick up 12 balls returning it to the bag at each time. · The result is the number of red balls was 8 and blue one was 4. · Then was the bag estimated to be R or B, and how probable the estimate is?

Clearly,

p(R) = p(B) = 1/2
p(D|R) = _{12}C_{8}(0.7)^{8}(0.3)^{4}
p(D|B) = _{12}C_{8}(0.3)^{8}(0.7)^{4}

So we obtain

p(R|D) = \frac{(0.7)^{8}(0.3)^{4}}{(0.7)^{8}(0.3)^{4} + (0.3)^{8}(0.7)^{4}}

(How big it is compared to our intuitive estimation!)

(Introduction to Pattern Recognition) 44

• Example-2:

· Three prisoners (A, B, and C) are in a prison. · A knows the fact two out of three are to be executed tomorrow, and the rest becomes free. · A thought either one of B or C is sure to be executed. · Then, A asked a guard “even if you tell me which of B and C is executed, that will not give me any information aboutme. So please tell that.” · The guard answers C. ⇒ data D · Now, A knows one of A or B is sure to be free.

So you guess a posteriori probability p(A|D) = 1/2?

If this is correct, then the answer of the guard had given an information about A, since a priori probability p(A) = 1/3.

Try to apply Baysean rule, if you agree p(A) = p(B) = p(C) = 1/3

p(D|A) = 1/2  (74)
p(D|B) = 1  (75)
p(D|C) = 0  (76)

Theorem 1 (Bayes Decision Theory) A pattern which has x should be classified so that p(ω_{i}|x) takes the maximum value, where

p(ω_{i}|x) = \frac{p(x|ω_{i})p(ω_{i})}{M ; ∑ ; k=1 p(x|ω_{k})p(ω_{k})}  (77)

• p(ω_{i}) are usually, known or if not it can be estimate from the training sample, i.e.,

– if N_{i} patterns out of N test samples are classified to ω_{i}

then

p(ω_{i}) = \frac{N_{i}}{N}  (78)

• p(x|ω_{i}) can be also estimated from the training samples (later in detail.)

(Introduction to Pattern Recognition) 46

□ To summarize

• Bayes classifier is:

If p(ω_{i}|x) is greater than any p(ω_{j}|x) j = 1, ⋯, Mj ≠ i, then classify x in class ω_{i}

• If ω_{i} is adjacent to ω_{j} p(ω_{i}|x) − p(ω_{j}|x) = 0 is called a decision surface

• or

if f(·) exists such that

g_{i}(x) ≡ f(p(ω_{j}|x)  (79)

where f(·) is a monotonically increasing function, then f is called a discriminant function.

• Then if g_{i}(x) > g_{j}(x) for ∀j ≠ i then classify x to ω_{i},

• and decision surface is determined by

g_{ij}(x) ≡ g_{i}(x) − g_{j}(x) = 0, i, j = 1, 2, ⋯, M. (80)

• But usually we know or can obtain p(x|ω_{j}) rather than p(ω_{j}|x)

• and in most cases p(x|ω_{j}) is Gaussian distribution.

• Therefore

if we use the equation (77) under an assamption of p(ω_{1}) = p(ω_{2}) = ⋯ = p(ω_{N}) = 1/N we can use p(x|ω_{j}).

□ An example for i = 2.

\{ \begin{matrix}if & p(ω_{1}|x) > p(ω_{2}|x) & x is classified to ω_{1}. \\ if & p(ω_{2}|x) > p(ω_{1}|x) & x is classified to ω_{2}. \end{matrix}  (81)

where

p(ω_{i}|x) = \frac{p(x|ω_{i})p(ω_{i})}{p(x|ω_{1})p(ω_{1}) + p(x|ω_{2})p(ω_{2})}

so, if p(ω_{1}) = p(ω_{2}) = 1/2

\{ \begin{matrix}if & p(x|ω_{1}) > p(x|ω_{2}) & x is classified to ω_{1}. \\ if & p(x|ω_{2}) > p(x|ω_{1}) & x is classified to ω_{2}. \end{matrix}  (82)

where p(x|ω_{i}) is a probability density function.

Classification Error Probability in this case

p_{e} = ∫_{−∞}^{x_{0}} p(x|ω_{2})dx + ∫_{x_{0}}^{∞} p(x|ω_{1})dx  (83)

(Introduction to Pattern Recognition) 49

• The equation (83) is also expressed as:

p_{e} = ∫_{R_{1}} p(x|ω_{2})dx + ∫_{R_{2}} p(x|ω_{1})dx  (84)

where R_{i}, i = 1, 2 are regions shown in the Figure.

• By generalizing this, we obtain the probability of misclassify ω_{k} to ω_{i} as:

p_{k} = M ; ∑ ; i=1 ∫_{R_{i}} p(x|ω_{k})dx  (85)

• If λ_{ki}, the importance of misclassification of ω_{k} to ω_{i}, is taken into consideration, then the total risk are defined as:

p_{k} = M ; ∑ ; i=1 λ_{ki} ∫_{R_{i}} p(x|ω_{k})dx  (86)

• And p = M ; ∑ ; k=1 r_{k}p(ω_{k}) should be minimized.

• This is achieved when each integral is minimized.

• So, x should be classified to ω_{i}, that is, x ∈ R_{i} if

M ; ∑ ; k=1 λ_{ki}p(x|ω_{k})p(ω_{k}) < M ; ∑ ; k=1 λ_{kj}p(x|ω_{k})p(ω_{k})  (87)

for ∀j ≠ i.

(Introduction to Pattern Recognition) 50

• In a two-class case example:

– assign x to ω_{1} if

(λ_{21} − λ_{22})p(x|ω_{2})p(ω_{2}) < (λ_{12} − λ_{11})p(x|ω_{1})p(ω_{1})

(88)

– Therefore, assign x to ω_{1} if

\frac{p(x|ω_{1})}{p(x|ω_{2})} > \frac{p(ω_{1})}{p(ω_{2})}\frac{λ_{21} − λ_{22}}{λ_{12} − λ_{11}}  (89)

– In the special case where λ_{11} = λ_{22} = 0, λ_{21} > λ_{12}, andp(ω_{1}) = p(ω_{2}) = 1/2 assign x to ω_{2} if

p(x|ω_{2}) > p(x|ω_{1})\frac{λ_{12}}{λ_{21}}  (90)

– What is the implication of equation (90)?

(Introduction to Pattern Recognition) 51

• Example ⋆ p(x|ω_{1}) and p(x|ω_{1}) follows a Gaussian distribution whose mean and standard deviation are:

μ_{1} = 0, μ_{2} = 1, andσ_{1} = σ_{2} = 1/2. that is,

p(x|ω_{1}) = \frac{1}{\sqrt{π}} exp(−x^{2})
p(x|ω_{1}) = \frac{1}{\sqrt{π}} exp(−x^{2})

(1) Obtain x_{0}.

(2) When

[λ_{ik}] = ( \begin{matrix}0 & 0.5 \\ 1.0 & 0 \end{matrix} )

how x_{0} will be affected?

(Introduction to Pattern Recognition) 52

□ Multi-dimensional Gaussian distribution Classifications in real-world problems, however, might be in a multi-dimensional space, not 1-D space. So, we must be familiar with multi-dimensional Gaussian distribution. The one-dimensional version

p(x) = \frac{1}{\sqrt{2π}σ} exp(−\frac{(x − μ)^{2}}{2σ^{2}})  (91)

is expanded for x = (x_{1}, x_{2}, ⋯, x_{l}) to the form:

p(x) = \frac{1}{\sqrt{2π}|S|^{1/2}} exp(−\frac{1}{2}(x − m)^{T}S^{−1}(x − m)) (92)

where the components of m are the mean of x_{i} i = 1, ⋯, l), that is,

m_{i} = E[x_{i}]  (93)

and S is called a covariance matrix and the components are

\{ \begin{matrix}σ_{ii} & = & σ_{i}^{2} = E[(x_{i} − m_{i})^{2}] \\ σ_{ij} & = & E[(x_{i} − m_{i})(x_{j} − m_{j})] if i ≠ j \end{matrix}  (94)

(Introduction to Pattern Recognition) 53

• If we use here ln as f(·) in the equation (79)

g_{i}(x) = ln(p(x|ω_{i})p(ω_{i}))
= ln p(x|ω_{i}) + ln p(ω_{i})
= −\frac{1}{2}(x − m_{i})^{T}S_{i}^{−1}(x − m_{i}) + ln p(ω_{i}) + c_{i}
= −\frac{1}{2}x^{T}S_{i}^{−1}x + \frac{1}{2}x^{T}S_{i}^{−1}m_{i} − \frac{1}{2}m_{i}^{T}S_{i}^{−1}m_{i}

+\frac{1}{2}m_{i}^{T}S_{i}^{−1}x + ln p(ω_{i}) + c_{i}

(95)

where

c_{i} = −\frac{l}{2} ln 2π − \frac{1}{2} ln |S_{i}|  (96)

• If for instance

l = 2, and S_{i} = ( \begin{matrix}σ_{1}^{2} & 0 \\ 0 & σ_{2}^{2} \end{matrix} )  (97)

then

g_{i}(x) = −\frac{1}{2σ_{i}^{2}}(x_{1}^{2} + x_{2}^{2}) + \frac{1}{σ_{i}^{2}}(μ_{i1}x_{1} + μ_{i2}x_{2})

−\frac{1}{2σ_{i}^{2}}(μ_{i1}^{2} + μ_{i2}x^{2}) + ln p(ω_{i}) + c_{i}

(98)

• This is a quadric form of x_{i} and x_{2}, that is, the classification space is either of ⋆ ellipsoids ⋆ parabola ⋆ hyperbola ⋆ pair of lines

(Introduction to Pattern Recognition) 54

• Two examples:

1) S_{1} = ( \begin{matrix}0.10 & 0 \\ 0 & 0.15 \end{matrix} ) S_{2} = ( \begin{matrix}0.20 & 0 \\ 0 & 0.25 \end{matrix} )

2) S_{1} = ( \begin{matrix}0.10 & 0 \\ 0 & 0.15 \end{matrix} ) S_{2} = ( \begin{matrix}0.15 & 0 \\ 0 & 0.10 \end{matrix} )