Bayes formula: P(x|y) = P(y|x)P(x) / å_xÎX P(y|x)P(x) = P(y|x)P(x) / P(y)

Bayes decision rule:

To minimize the overall risk(R=ò R(a(x)|x) p(x)dx ), compute the conditional risk R(a_i|x) = åλ(a_i|w_j)P(w_j|x) for each i, and then select the action a_i for which R(a_i|x) is minimum. The resulting minimum overall risk is called the Bayes risk, R*, and is the best performance that can be achieved.

(λ(a_i|w_j) is loss function )

Tow category classification

Let λ_ij = λ(a_i|w_j)

We decide w₁ if

(λ₂₁ – λ₁₁) P(x|w₁)P(w₁) > (λ₁₂ – λ₂₂) P(x|w₂)P(w₂)

Assume λ₂₁ > λ₁₁

To decide w₁ if

P(x|w₁) / P(x|w₂) > (λ₁₂ – λ₂₂)P(w₂) / (λ₂₁ – λ₁₁)P(w₁)

Thus the Bayes decision rule can be interpreted as calling for deciding w₁ if the likelihood ratio (P(x|w₁) / P(x|w₂)) exceeds a threshold value that is independent of x.

Minimum-error-rate classification

If true state of nature is w_j, decision is correct if i=j.

Zero-one loss: when i=j λ(a_i|w_j)=0

                                  i¹j λ(a_i|w_j)=1

then when i¹j  R(a_i|x) = åλ(a_i|w_j)P(w_j|x)= R(a_i|x) = åP(w_j|x) =1- P(w_i|x)

P(w_i|x) is the conditional probability that action a_i is correct.

For minimum error rate:

Decide w_i if P(w_i|x) > P(w_j|x)

Classifiers, discriminant functions, and decision surfaces

The multicategory case

The classifier is said to assign a feature vector x to class w_i if

g_i(x) > g_j(x)

g(x) is discriminant function

A network representation of a classifier: with d inputs and c g(x)s, then it determines which of the discriminant values is the maximum, and categorizes the input pattern accordingly.

Bayes classifier:

g_i(x) = -R(a_i|x) g_i(x) is maximum when conditional risk is minimum

Minimum-error-rate classifier:

g_i(x) = P(w_i|x)  g_i(x) is maximum when P(w_i|x)   is minimum

g_i(x) can be replaced by f(g(x)) when f is a monotonically increasing function, the result  is unchanged.

The effect of any decision rule is to divide the feature space in to c decision regions, R₁,…, R_c. If g_i(x) > g_j(x) for all i¹j, then x is in R_i.

The tow-category case

Dichotomizer (tow-category classifier) use single discriminant function

g(x) = g₁(x) – g₂(x)

Decide w₁ if g(x)>0; otherwise decide w₂

For minimum-error-rate classification:

g(x)= P(w₁|x) - P(w_i|x)

or g(x)=  ln(P(x|w₁) / P(x|w₂)) + ln (P(w₁)/ P(w₂)

The normal density

Multivariate density

p(x) = 1 / (2π)^d/2|S|^1/2 exp[-1/2(x-m)^t S ^-1(x-m)]

p(x) ~ N(m, S).

x is d-component column vector, m is the d-component mean vector(m=òxp(x)dx), S is the d-by-d covariance matrix(S=ò (x-m) (m- x)^t p(x)dx)

σ _ij = e[(x_i-m_i)(x_j-m_j)]

Linear combination: p(x) ~ N(m, S), y=A^tx, then p(y) ~ N(A^tm, A^tSA)

The multivariate normal density is completely specified by the elements of the mean vector m and the independent elements of the covariance matrix S. (m determine the centre and S determine the shape)

Discriminant functions for normal density

If  P(x|w_i) ~ N(m_i, S_i)

Discriminant function g_i(x) = -1/2(x-m_i)^t S_i ^-1(x-m_i) – d/2 ln2π – 1/2ln|S_i| + lnP(w_i)

Case 1: S_i = σ²I

g_i(x) = -|| x-m_i ||² /2 σ² + lnP(w_i)

|| x-m_i ||² = (x-m_i)^t(x-m_i) which is Euclidean norm

g_i(x) = -[x^tx - 2m_i^tx + m_i^tm_i]/2 σ² + lnP(w_i)

x^tx is the same for all i, making it an ignorable additive constant, so we get the equivalent linear discriminant function :

g_i(x) = w_i^tx + w_i0

w_i= m_i/ σ²  

w_i0 = -m_i^tm_i /2 σ² + lnP(w_i) which is called threshold for the ith category

A classifier uses linear discriminant function is called a linear machine.

Because the discriminants are linear the resulting decision boundary are hyperplanes, defined by g_i(x) = g_j(x). In this case, w^t(x-x₀) = 0;

Where w = m_i  - m_j

            x₀ = (m_i  + m_j) - σ²/||m_i  - m_j ||² ln P(w_i)/ P(w_j) (m_i  - m_j)

If  P(w_i) = P(w_j), x₀ is halfway between the means, and the hyperplane is the perpendicular bisector of the line between the means.

If  P(w_i) = P(w_j), x₀ shifts away from the more likely mean.

If P(w_i) are the same for all c classes the lnP(w_i) term can be ignored. So the decision rule is measure the Euclidean distance || x-m_i ||, assign x to the nearest mean. Such classifier is called a minimum distance classifier.

Case 2: S_i = S

g_i(x) = -1/2(x-m_i)^t S_i ^-1(x-m_i) + lnP(w_i)

If P(w_i) are the same for all c classes the lnP(w_i) term can be ignored. So the decision rule is measure the Mahalanobis distance (x-m_i)^t S_i ^-1(x-m_i),  assign x to the nearest mean.

Ignore the quadratic term x^tS^-1x, we get the linear discriminant function again:

g_i(x) = w_i^tx + w_i0

w_i = S^-1m_i

w_i0 = -1/2m_i^t S_i ^-1m_i  + lnP(w_i)                                                                                                                                                                         

The resulting decision boundaries are hyperplanes, same as case 1, but  are generally not orthogonal to the line between the means.

Case 3: S_i = arbitrary

g_i(x) = x^tW_ix + w_i^tx + w_i0

W_i = -1/2S_i ^-1

w_i = S_i ^-1m_i

w_i0 = -1/2m_i^tS_i ^-1m_i – 1/2ln|S_i| + lnP(w_i)

In the tow category case, the decision surfaces are hyperquadrics. Even in one dimensional, the decision regions need not be connected.

Bayes decision theory- discrete features

x can assume only one of m discrete values v₁…,v_m. So the probability density function P(x|w_j) becomes singular. Then Bayes formula involves probabilities rather than probability density.

P(w_j|x) = P(x|w_j) P(w_j) / P(x) where P(x) = å_w P(x|w_j) P(w_j)

The conditional risk is unchanged in the discrete case, and the Bayes rule remains the same: select the action a_i for which R(a_i|x) is minimum.

Independent binary features

For tow category problem

Let x = (x₁,…, x_d), x_i are either 0 or 1, and conditionally independent.

p_i = Pr [x_i = 1 |w₁], so 1- p_i  = Pr [x_i = 0 |w₁]

q_i = Pr [x_i = 1 |w₂], so 1- q_i  = Pr [x_i = 0 |w₂]

For conditionally independence,

P(x|w₁) = P_i p_i^xi(1- p_i )^{1- xi}

P(x|w₂) = P_i q_i^xi(1- q_i )^{1- xi}

For The tow-category case:

g(x) =  ln(P(x|w₁) / P(x|w₂)) + ln (P(w₁)/ P(w₂)

Then we get

g(x) = å_i w_i x_i + w₀

w_i =ln [p_i(1- q_i )/ q_i(1- p_i )]

w₀ = å_i ln (1- p_i )/ q_i(1- q_i ) + ln (P(w₁)/ P(w₂)

We decide w₁ if g(x)>0, otherwise decide w₂

The magnitude of w_i indicates the revalence of  a “yes”(1) answer for x_i

If p_i = q_i, x_i gives no information, w_i =0

If p_i > q_i, 1- q_i > 1- p_i,  w_i >0, and w_i gets larger as p_i gets larger.

If p_i > q_i, w_i < 0 and |w_i| gets larger as p_i gets larger

P(w_j) appear only through the threshold w₀ increasing P(w₁) increases w₀ biases the decision in favour of  w₁.

The University of Wollongong’s status as one of Australia’s top research and teaching institutions has been confirmed today (August 3) with five-star ratings across key categories in the nation’s authoritative guide to choice of university.

The 2006 Australian Good Universities Guide is now being launched in newsagents and bookshops in Australia and overseas, and the University of Wollongong has achieved an impressive maximum five stars in six of the key categories in the independent Guide. Only the top 20 per cent of universities can be awarded a five-star rating in any one category.

Elements of visual perception

Image formation in the eye:

The lens of eye is just like an optical lens, but is more flexible. When we see an object, we get a retinal image primarily in the area of the fovea. Perception then takes place by the relative excitation of light receptors, which transform radiant energy into electrical impulses that are ultimately decoded by the brain.

Brightness adaptation

The range of light intensity levels to which the human visual system can adapt is enormous. But the visual system cannot operate over such a range simultaneously. Rather, it accomplishes this large variation by change in its overall sensitivity. So the total range of distinct intensity levels it can discriminate simultaneously is rather small when compared with the total adaptation range. For any given set of conditions, the current sensitivity level of the visual system is called the brightness adaptation level.

At any specific adaptation level, brightness discrimination is poor at low levels of illumination, and it improves significantly as background illumination increases.

Light and the electromagnetic spectrum

Spectrum (wavelength from short to long, energy from high to low):

Gamma rays, Hard X rays, Soft X rays, Ultraviolet, Visible spectrum, Infrared, Microwaves, Radio waves.

λ=c/ν; E=h ν;

A body that reflects light and is relatively balanced in all visible wavelengths appears white to the observer. However, a body that favors reflectance in a limited range of the visible spectrum exhibits some shades of colour.

The term gray level generally is used to describe monochromatic intensity because it ranges black to grays, and finally to white.

Image sensing and acquisition

We use sensors to transform illumination energy into digital image. The idea is simple:

Incoming energy transformed into a voltage by the combination of input electrical power and sensor material that is responsive to the particular type of energy being detected. The output voltage waveform is the response of the sensor, and a digital quantity is obtained from each sensor by digitizing its response.

There are three principal sensor arrangements:

Using a single sensor:

Images are generated by a single sensor combined with mechanical motion.

Using sensor strips:

The strip provides imaging elements in one direction. Motion perpendicular to the strip provides imaging in the other direction.

Using sensor arrays:

The arrays are tow dimensional. A complete image can be obtained by focusing the energy pattern onto the surface of the array.

Simple image formation model

We denote image by two-dimensional functions of the form f(x, y). The value of f at spatial coordinates (x, y) is a positive scalar quantity.

f(x, y)=i(x, y) r(x, y)

i(x, y) is illumination components, 0 < i(x, y)< ∞.

r(x, y) is reflectance components, 0 < r(x, y)< 1.

We call the intensity of a monochrome image at any coordinates (x₀, y₀) the gray level (l) of the image at that point. That is: l=f (x₀, y₀)

lÎ[0, L-1]

l = 0 is considered black and L-1 is considered white (L=2^k). All intermediate values are shades of gray varying from black to white.

Image sampling and quantization

To create a digital image, we need to convert the continuous sensed data into digital form. This involves two processes: sampling and quantization. Digitizing the coordinate values is called sampling (divide the image). Digitizing the amplitude values is called quantization (divide the gray level value).

The quality of a digital image is determined to a large degree by the number of samples and discrete gray levels used in sampling and quantization. When using a single sensor to get images, practical limits are established by imperfections in the optical devices. And when a sensing strip or a sensing array is used for image acquisition, the number of sensors establishes the limits of sampling.

Expressing sampling and quantization in formal mathematical terms: Let Z and R demote the set of real integers and the set of real numbers, respectively. The sampling process can be viewed as partitioning the xy plane into a grid, with the coordinates of the centrer of each grid being a pair of elements from the Cartesian product Z²,which is the set of all ordered pairs of elements (z_i,z_j),with z_i and z_j being integers from Z. Hence, f(x, y) is a digital image if f(x, y) are integers from Z² and f is a function that assigns a gray-level value to each distinct pair of coordinates (x, y). This functional assignment is the quantization process. If the gray level also are integers, Z replace R, and a digital image then becomes a 2-D function whose coordinates and amplitude values are integers.

Representing digital image

Assume that an image f(x, y) is sampled so that the resulting digital image has M rows and N columns. So the values of the coordinates (x, y) now become discrete quantities. We use integer values for these discrete coordinates. Thus, the values of the coordinates at the origin are (x, y) = (0, 0). The next coordinate values along the first row of the image are represented as (x, y) = (0, 1). So we can use an M*N matrix to represent the image. Each element of this matrix array is called pixel, which represent a pair of coordinates and the correspondent gray-level value.

The number of gray levels typically is an integer power of 2: L=2^k

The number b is the bits required to store a digitized image. b=M*N*k

When M=n, b=N²k.

When an image can have 2^k gray levels, it is common practice to refer to the image as a “k bit image”.

Spatial and gray-level resolution

Spatial resolution is the smallest discernible detail in an image.

It is common to refer to an L-level digital image of size M*N as having a spatial resolution of M*N pixel and a gray-level resolution of L.

Basically, decreases in k and n will reduce the quality of an image.

Zooming and shrinking digital images

Zooming requires tow steps: the creation of two pixel location, and the assignment of gray-level to those new locations.

First, lay an imaginary new grid over the original image. Then, we look for the closest pixel in the original image and assign its gray level to the new pixel in the grid. Finally, expand it to the specified size to obtain the zoomed image.

A more sophisticated way of accomplishing gray-level assignment is bilinear interpolation using the four nearest neighbours of a point. Let (x’, y’) denote the coordinates of a point in the zoomed image, and let v (x’, y’) denote the gray-level assigned to it. The assigned gray level is given by:  v (x’, y’)=ax’+by’+cx’y’+d

The four coefficients are determined from the four equations in four unknowns that can be written using the four nearest neighbours of point (x’, y’).

Image shrinking is done in a similar manner as zooming. The equivalent process of pixel replication is now column deletion.

Some basic relationships between pixels

For a pixel p(x, y):

4-neighbors of p, N₄(p): (x+1, y), (x-1, y), (x, y+1), (x, y-1)  (horizontal and vertical neighbours)

Diagonal neighbours of p, N_d(p): (x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1) 

8-neighbors of p, N₈(p): N₄(p)+ N_d(p)

Let V be the set of gray-level values used to define adjacency

4-adjacency: two pixels p and q with values from V are 4-adjacent if q is in the set N₄(p).

8-adjacency: two pixels p and q with values from V are 4-adjacent if q is in the set N₈(p).