\documentstyle[12pt,eclepsf]{article}

\textheight 260mm
\topmargin -10mm
\textwidth 180mm
\oddsidemargin -7mm

\pagestyle{myheadings}
\markright{(Introduction to Pattern Recognition)}

\begin{document}
\begin{LARGE}

\begin{center}
\begin{Huge}
\noindent
{\bf Introduction to Pattern Recognition}\\
\end{Huge}

\vspace{1in}
Dokuz Eyl\"{u}l University \\
Computer Engineering Department \\
\hspace*{1in}\\
\begin{large}
(25 September, 2000 -- 5 January, 2001)\\
\end{large}
\end{center}

\clearpage
%---------------------------------------------------------------------

\noindent
$\Box$ {\bf Contents:}\\

\begin{itemize}
\item [ 1.] What is Pattern Recognition?
\end{itemize}


\clearpage
%---------------------------------------------------------------------
\section{What is Pattern Recognition?}

\section{What for?}

\noindent
{\bf A typical example:}

\begin{itemize}
\item character recognition
   \begin{itemize}
   \item[] characters as an example of patterns\\
   \end{itemize}
\end{itemize}

\noindent
{\bf But how?}

\begin{itemize}
\item By taking all pixels as inputs?
\item By some shape information?
   \begin{itemize}
   \item[]e.g.
      \begin{itemize}
      \item area within boundary;
      \item degree of how boundary curve.
      \end{itemize}
   \end{itemize}
\item[]These are called {\it features}.\\
\end{itemize}

\noindent
{\bf Feature space:}

\begin{itemize}
\item $l$ features forms {\it feature vector} 
\item[] \hspace*{1in} $\mbox{\bf x} = (x_1, x_2, \cdots, x_l)$
\item[] for each object to be recognized.
\item straight line separates the classes
\item[] \hspace*{1in} $\Downarrow$ in more general
\item[] separation by {\it hyper-plane}\\
\end{itemize}

\noindent
{\bf In short:}

\begin{itemize}
\item pattern recognition is a {\it classifier}\\
\end{itemize}

\hspace{1in}\\
\noindent
{\bf Yet another example}
\begin{itemize}
\item machine vision (robot eye);
\item face recognition;
\item speech recognition;
\item computer-aided diagnosis;
\item what else?\\
\end{itemize}

\noindent
{\bf Problems:}
\begin{itemize}
\item What features are to be used to classify?
\item What is the optimum number of features?
\item How is the classifier designed?
\end{itemize}

\vfill
\noindent
{\bf Keywords:
\begin{itemize}
\item features, feature-space, feature-vectors, hyper-plane,
      classifiers, 
\end{itemize}}
\clearpage




\section{supervised/unsupervised}

\noindent
{\bf Supervised pattern recognition}
\begin{itemize}
\item classifies unknown data using a set of training data.
\item Learning with teacher.\\
\end{itemize}

\noindent
{\bf Unsupervised pattern recognition (clustering)}
\begin{itemize}
\item unravel the underlying similarities
and cluster similar vectors together using a set of feature vectors 
\item[]e.g.
   \begin{itemize}
   \item Assume we are interested in studying relations among
         a country's GNP, the level of people's illiteracy, 
         and a children's mortality rate.
   \item[]\hspace*{1in} $\Downarrow$
   \item[]three-dimensional feature vectors
   \end{itemize}
\item Learning without teacher.
\end{itemize}

\clearpage
\section{Hand-written character recognition -- revisit}

\noindent
{\bf What should be employed as features:}
\begin{itemize}
\item[1.] Pixels;
\item[2.] Geometric Features;
\item[3.] Fourier Features;
\item[4.] Chain Codes;
\item[5.] Moment-based Features;
\item[6.] Neural Networks.\\
\end{itemize}

\noindent
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).\\

\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\

\noindent
{\bf 1. Each pixel's state as a set of features:}\\

\begin{itemize}
\item draw 20 different writings for each character;
\item keep the pixel data for the future reference.
\end{itemize}

\clearpage
\noindent
{\bf 2. Geometric Features:}\\

\begin{itemize}
\item Perimeter
\end{itemize}
\begin{equation}
   P = \sum_{i=1}^{N-1} 
         {\| {\mbox{\bf x}}_{i+1} - {\mbox{\bf x}}_{i} \|
       + \| {\mbox{\bf x}}_{N} - {\mbox{\bf x}}_{1} \|} \\
\end{equation}
\begin{itemize}
\item Area
   \begin{itemize}
   \item Measure the area enclosed by a boundary 
         by counting the number of pixels. \\
   \end{itemize}
\end{itemize}

\begin{itemize}
\item roundness ratio
\end{itemize}
\begin{equation}
r = \frac { P^2}{4 \pi A} \\
\end{equation}

\begin{itemize}
\item Bending energy;\\
(later in detail)\\
\item The number of corners in the boundary; \\
(later in detail)\\
\item The number of holes.
\end{itemize}


\clearpage
\noindent
{\bf 3. Fourier Features:}\\

\noindent
Let
\begin{equation}
(x_k, y_k), \hspace{.2in} k = 0, 1, \cdots, N-1. 
\end{equation}
\noindent
be the coordinates of $N$ samples on the boundary of an image region.
For each pair $(x_k, y_k)$ we define the complex:
\begin{equation}
u_k = x_k + jy_k.
\end{equation}
For the $N$ $u_k$ points we obtain the DFT $f_l$
\begin{equation}
f_l = \sum_{k=0}^{N-1} { 
   u_k \exp (-j2 \pi lk /N)
}, \hspace{.2in} l = 0, 1, \cdots, N-1.\\  
\end{equation}
and call them $l$ Fourier Descriptors of the boundary.\\

\hspace*{1in}\\

\noindent
Another way is from curvature function of the boundary:
\begin{equation}
k(t) = \frac {d \theta (t)}{dt}.\\
\end{equation}

\noindent
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
\begin{equation}
\theta_n = \tan^{-1} \frac {y_{n+1} - y_{n}}{x_{n+1} - x_{n}}, \hspace{.2in}
n = 0, 1, \cdots, N-1.
\end{equation}
\begin{equation}
k_n = \theta_{n+1} - \theta{n}, \hspace{.2in}
n = 0, 1, \cdots, N-1.
\end{equation}

\clearpage
\noindent
{\bf Bending energy and number of corners revisited:}\\

\noindent 
Then we can define 
\begin{itemize}
\item bending energy at a point $n$ as
\end{itemize}

\begin{equation}
E(n) = \frac{1}{P} \sum_{i=0}^{n-1} {\vert k_i \vert ^2} \\
\end{equation}

\noindent
and \\
\begin{itemize}
\item number of corners in the boundary contour as
   \begin{itemize}
   \item the number of points where the curvature $k_i$ takes large values
         (infinity in theory)
   \end{itemize}
\end{itemize}


\clearpage
\noindent
{\bf 4. Chain codes:}\\

\noindent
$\Box$ Chain code $(d_1, d_2, \cdots, d_{N})$ is defined as:

\begin{itemize}
\item[] 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.
\end{itemize}

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=chain-code.eps,width=16cm,height=10cm}
 \end{center}
\end{figure}


\clearpage
\begin{itemize}
\item Direction and Direction-length Features: \\
\end{itemize}
\begin{equation}
\frac{\mbox{the number of each direction}}
     {\mbox{the total number of chain codes}}
\end{equation}

or\\
\begin{equation}
\frac{\mbox{the total length of the line segments in each direction}}
     {\mbox{the total length of the boundary line}}\\
\end{equation}

%%\hspace*{1in}\\

\hfill
$\Rightarrow$ 8 features

\begin{itemize}
\item Curvature Features:
   \begin{itemize}
   \item Is an external angle between adjacent two edges at a corner
         of the polygon that is formed by the line segments 
      \begin{itemize}
      \item concave (smaller than $180^{\circ}$) or
      \item convex  (larger than $180^{\circ}$)?
      \end{itemize}
   \item[] when the boundary is scanned in the clockwise sense.
   \item 48 possible cases     
      \begin{itemize}
      \item Concave cases:
         \begin{itemize}
         \item 01 02 03 12 13 14 23 24 25 34 35 36 \\
               45 56 47 50 56 57 60 61 67 70 71 72
         \end{itemize}
      \item Convex cases:
         \begin{itemize}
         \item 05 06 07 10 16 17 20 21 27 30 31 32 \\
               41 42 43 52 53 54 63 64 65 74 75 76
         \end{itemize}
      \end{itemize}   
   \item Occurrence percentage of each of these cases.
   \end{itemize}	
\end{itemize}   
\hfill
$\Rightarrow$ 48 features

\clearpage
\noindent
$\Box$ {\bf Summary:}\\

\noindent
{\bf What features can be used\\
\hspace*{1in}to recognize hand-written characters?}\\

\begin{itemize}
\item Boundary-based: 
   \begin{itemize}
   \item Single feature:
      \begin{itemize}
      \item Perimeter of the boundary;;
      \item Area inside the boundary;
      \item Roundness ratio;
      \item Number of corners in the boundary;
      \item Number of holes.
      \end{itemize}
   \item Multiple features:
      \begin{itemize}
      \item Fourier features;
      \item Chain codes.
      \end{itemize}
   \end{itemize}
\item Pixel-based:
   \begin{itemize}
   \item Neural-networks
      \begin{itemize}
      \item Perceptron learning
      \item Genetic algorithm
      \end{itemize}
  \end{itemize}
\end{itemize}

\clearpage
\noindent
{\bf Genetic Algorithm (GA)}\\

\noindent
$\Box$ An example:
\begin{itemize}
\item Neural network with 100 input neurons and 10 output neurons 
      with no hidden layer:
   \begin{itemize}
   \item hand-written-characters of the figures from zero to nine
           drawn on the 10x10 pixels are to be recognized 
   \item by activating only the $i$-th neuron of the output
         remaining other neurons not activated.\\
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ From a biological analogy, the followings are defined.\\

\begin{description}
\item {\it Chromosome:}\\ 
      Each chromosome is comprised of 1000 {\it genes},
      representing 1000 weights of one {\it individual} neural network.
\item {\it Population:}\\
      A number of individuals, say 100, create a population.
\item {\it Initialization:}\\
      All genes of all chromosomes are initialized at random, taking a value
      ranging from zero to one. This construct the first {\it generation}.
\item {\it 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.
\item {\it 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: {\it crossover} and
      {\it mutation}
\item {\it Crossover:}\\
      A same position of the two parent chromosomes are determined at
      random (each time when they are selected), and cross them over.
\item {\it 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.
\end{description}



\clearpage
\noindent
$\Box$ Algorithm:\\

\begin{enumerate}
\item {\it Initialization:}
  Initialize all the weight values of all the individuals in the first 
  generation at random so that it lies on  $\left[ 0, 1 \right] $.
\item {\it Evaluation:}
  Evaluate fitness of all the individuals of the population.
\item {\it Reproduction:}
  \begin{enumerate}
  \item[(1)] Select two parents from the population.
  \item[(2)] Crossover the two parents and produce one offspring.
  \item[(3)] Mutate the offspring.
  \item[(4)] Repeat (1) to (3) above until new generation of same size 
             is obtained.
  \end{enumerate}
\item Repeat 2. to 3. above until the perfect solution is obtained or 
      prespecified generations is reached.
\end{enumerate}

%%========================================================================
\clearpage
\begin{Huge}
{\bf
\noindent
Chapter 2.\\
\hspace*{1in}\\
\indent
Features based on Linear Transformation.
}
\end{Huge}

\begin{itemize}
\item Generation of features using linear transforms of the input samples.
\item Appropriate transform removes information redundancy and 
      reduce feature space dimension, leading to information packing.
\item[] e.g.,
   \begin{itemize}
   \item Fourier coefficients as features:
      \begin{itemize}
      \item most of the energy lies in the low-frequency components due 
            to the high correlation between pixels and 
      \item we can neglect low-energy, high-frequency coefficient 
            with little loss of information.
      \end{itemize}
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ Fourier Coefficient (revisit). \\

\noindent
We can expand any continuous function $f(x)$ as:
\begin{equation}
f(x) \simeq \sum_{k=1}^{\infty} a_k \cos kx + b_k sin kx
\end{equation}

\noindent
where we can calculate the Fourier coefficient $a_k$ and $b_k$ as
\begin{eqnarray}
a_k &=& \int_{- \pi}^{\pi} f(x) \cos kx \,dx\\
b_k &=& \int_{- \pi}^{\pi} f(x) \sin kx \,dx\\
\end{eqnarray}

\noindent
($a_k$ and $b_k$ are called higher frequency component for larger $k$ 
and vice versa.)


\begin{itemize}
\item Exercise
   \begin{itemize}
   \item[]Obtain the Fourier expansion of the followings.
      \begin{itemize}
      \item[](1) \hspace{.1in} $y = x$
      \item[](2) \hspace{.1in} $y = x^2$\\
      \end{itemize}
   \end{itemize}
\end{itemize}

\noindent
The other formulation\\
\begin{equation}
f(x) \simeq \sum_{k=- \infty}^{\infty} c_k \exp (-jkx)
\end{equation}
where
\begin{equation}
c_k = \int_{- \pi}^{\pi} f(x) \exp (jkx) \,dx\\
\end{equation}

\begin{itemize}
\item Exercise
   \begin{itemize}
   \item[]Verify this employing the relations
      \begin{itemize}
      \item[] $ \exp(-jkx) = \cos kx + j \sin kx $
      \end{itemize}
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ 1-D Discrete Fourier Transform. \\

\noindent
$\bullet$ DFT:
\begin{equation}
y(k) = \frac {1}{\sqrt N} \sum_{n=0}^{N-1} x(n) 
                 \exp (-j \frac {2 \pi}{N}kn), \hspace{.2in}
                 k = 0, 1, \cdots, N-1.\\
\end{equation}

\hspace*{1in}\\
\noindent
$\bullet$ Inverse-DFT:
\begin{equation}
x(n) = \frac {1}{\sqrt N} \sum_{k=0}^{N-1} y(k) 
                 \exp (j \frac {2 \pi}{N}kn), \hspace{.2in}
                 n = 0, 1, \cdots, N-1.\\
\end{equation}

\hspace*{1in}\\
\noindent
$\bullet$ An example of $N=4$: DFT of $x(0), x(1), x(2), x(3)$


e.g.
\begin{eqnarray}
y(1) &=& \frac{1}{2} \{ x(0) \exp(0) 
                   + x(1) \exp (-j \frac{\pi}{2}) \nonumber \\
     & &           + x(2) (-j \frac{2 \pi}{2}) 
                   + x(3) \exp (-j \frac{3 \pi}{2}) \}    
\end{eqnarray}

\begin{eqnarray}
\left(
\begin{array}{c}
y(0)\\
y(1)\\
y(2)\\
y(3)\\
\end{array}
\right)
=
\left(
\begin{array}{rrrr}
1 &  1 &  1 &  1\\
1 &  j & -1 & -j\\
1 & -1 &  1 & -1\\
1 & -j & -1 &  j\\
\end{array}
\right)
\left(
\begin{array}{c}
x(0)\\
x(1)\\
x(2)\\
x(3)\\
\end{array}
\right)
\end{eqnarray}

\noindent
Or
\begin{eqnarray}
\mbox{\bf y} = A \mbox{\bf x}
\end{eqnarray}

\noindent
where
\begin{eqnarray}
A_{mn} = \exp (-j \frac {2 \pi}{N})(m-1)(n-1)
\end{eqnarray}

\noindent
$\bullet$ Inverse Transformation
\begin{eqnarray}
A^{-1} =
\left(
\begin{array}{rrrr}
1 &  1 &  1 &  1\\
1 & -j & -1 &  j\\
1 & -1 &  1 & -1\\
1 &  j & -1 & -j\\
\end{array}
\right)
\end{eqnarray}

\noindent
$\bullet$ Orthogonal linear transformation\\

\noindent
In a linear transform\\

\begin{equation}
y(k) = \sum_{n=0}^{N-1} x(n)a_n(k),\\
\end{equation}
\noindent
if 
\begin{equation}
a_m(k)a_n(k) = \delta_{mn}\\
\end{equation}
\noindent
holds, then the linear transformation is called {\it unitary}
({\it orthogonal} in real variables).

\clearpage
\noindent
$\Box$ 2-D DFT\\
\begin{equation}
Y(k,l) = \frac{1}{N} \sum_{m=0}^{N-1} \sum_{n=0}^{N-1}
         X(m,n) \exp (-j \frac {2\pi}{N}km)\exp (-j \frac {2\pi}{N}ln)\\
\end{equation}
\begin{equation}
X(m,n) = \frac{1}{N} \sum_{m=0}^{N-1} \sum_{n=0}^{N-1}
         Y(k,l) \exp (j \frac {2\pi}{N}km)\exp (j \frac {2\pi}{N}ln)
\end{equation}

\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\


\noindent
$\Box$ Other Linear Transformation\\
\begin{itemize}
\item HAAR
\item HADAMAR
\item WAVELET
   \begin{itemize}
   \item[](Though this won't be studied in this course.)
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf Hadamar Transform:}\\

\noindent
For a vector $\mbox{\bf x}$ of $N$ samples where $N=2^n$, 
the transform and its inverse transform are:
\begin{equation}
\mbox{\bf y} = H_n \mbox{\bf x}, \hspace{.3in} 
\mbox{\bf x} = H_n \mbox{\bf y}
\end{equation}

\noindent
where
\begin{equation}
H_n = H_1 \otimes H_{n-1}
\end{equation}
and
\begin{eqnarray}
H_1 = \frac{1}{\sqrt 2} \left(
\begin{array}{rr}
1 &  1 \\
1 & -1 \\
\end{array}
\right)
\end{eqnarray}

\noindent
Here $\otimes$ denotes the Kronecker product 
for two matrices:\footnote{\noindent for example, if
\begin{eqnarray}
A = \left(
\begin{array}{cc}
1 &  2 \\
3 &  4 \\
\end{array}
\right)
\end{eqnarray}
and
\begin{eqnarray}
B = \left(
\begin{array}{cc}
5 &  6 \\
7 &  8 \\
\end{array}
\right)
\end{eqnarray}
then we define
\begin{eqnarray}
A \otimes B = \left(
\begin{array}{cccc}
 5 &  6  & 10 & 12\\
 7 &  8  & 14 & 16\\
15 & 18  & 20 & 24\\
21 & 24  & 28 & 32\\
\end{array}
\right)
\end{eqnarray}
}
\begin{equation}
[A \otimes B]_{ij} = A_{ij}B
\end{equation}

\clearpage
\noindent
$\Box$ {\bf Haar Transform:}\\

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

\begin{itemize}
\item[(1)] Decomposition of the order $k$ into two integers $p$ and $q$.
\begin{equation}
k=2^p+q-1, \hspace{.3in} k=0,1, \cdots, L-1.
\end{equation}
The decomposition is unique when
\begin{eqnarray}
\left\{
\begin{array}{ll}
q=0 \hspace{.2in} \mbox{or} \hspace{.2in} 1        
                          & \hspace{.2in}\mbox{if}\hspace{.2in}p=0\\
0 \le p \le n-1, \hspace{.2in} 0 < q \le 2^p    
                          & \hspace{.2in}\mbox{if}\hspace{.2in}p \ne 0\\
\end{array}
\right.
\end{eqnarray}
\item[(2)] Haar functions are
\begin{equation}
h_0(z) \equiv h_{00}(z) = \frac{1}{\sqrt L}
\end{equation}
and
\begin{eqnarray}
h_k(z) \equiv h_{pq}(z) = \frac{1}{\sqrt L} \left\{ 
\begin{array}{cl}
2^{\frac{p}{2}} & 
   \mbox{if } \frac {q-1}{2^p}         \le z < \frac{q-\frac{1}{2}}{2^p}\\
- 2^{\frac{p}{2}} & 
   \mbox{if } \frac{q-\frac{1}{2}}{2^p} \le z < \frac{q}{2^p}   \\
0                 &
   \mbox{otherwise in } [0,1]
\end{array}
\right.
\end{eqnarray}
\item[(3)] Then the Haar transform matrix of order $L$ consists of rows 
of the Haar function computed at 
\begin{displaymath}
z=\frac{m}{L}, \hspace{.3in} m=0,1,2, \cdots L-1.
\end{displaymath}
\end{itemize}

\begin{itemize}
\item Exercise
   \begin{itemize}
   \item[] Obtain the 8 $\times$ 8 transform matrix.
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\bullet$ An example of $n=3$, that is, $L=8$.
\begin{equation}
k=2^p+q-1, \hspace{.3in} k=0,1, \cdots, 7
\end{equation}

where
\begin{eqnarray}
\left\{
\begin{array}{ll}
q=0 \hspace{.2in} \mbox{or} \hspace{.2in} 1        
                          & \hspace{.2in}\mbox{if}\hspace{.2in}p=0\\
0 \le p \le 2, \hspace{.2in} 0 < q \le 2^p    
                          & \hspace{.2in}\mbox{if}\hspace{.2in}p \ne 0.\\
\end{array}
\right.
\end{eqnarray}

So,
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c} \hline \hline
p=0           & q=0         & k=0      \\
\hspace{.1in} & q=1         & k=1      \\ \hline
\hspace{.1in} & $(0<q\le2)$ & $(k=1+q)$\\
p=1           & q=1         & k=2      \\
\hspace{.1in} & q=2         & k=3      \\ \hline
\hspace{.1in} & $(0<q\le4)$ & $(k=3+q)$\\
p=2           & q=1         & k=4      \\
\hspace{.1in} & q=2         & k=5      \\
\hspace{.1in} & q=3         & k=6      \\
\hspace{.1in} & q=4         & k=7      \\ \hline \hline
\end{tabular} 
\end{center}
\end{table}

Hence,
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c c c c c c c}   \hline \hline
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 \\ \hline \hline
\end{tabular} 
\end{center}
\end{table}

\clearpage

Then the Haar functions are:
\begin{eqnarray}
h_1(z) \equiv h_{01}(z) = \frac{1}{\sqrt 8} \left\{ 
\begin{array}{rlc}
 1 & \hspace{.2in}\mbox{if } & -1         \le z < \frac{1}{2}\\
-1 & \hspace{.2in}\mbox{if } & \frac{1}{2}\le z < 1          \\
\end{array}
\right.
\end{eqnarray}
\begin{eqnarray}
h_2(z) \equiv h_{11}(z) = \frac{1}{\sqrt 8} \left\{ 
\begin{array}{rlc}
 \sqrt 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} 0          \le z < \frac{1}{4}\\
-\sqrt 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{1}{4}\le z < \frac{1}{2}\\
       0 & \hspace{.2in}\mbox{otherwise in } [0,1]
\end{array}
\right.
\end{eqnarray}
\begin{eqnarray}
h_3(z) \equiv h_{12}(z) = \frac{1}{\sqrt 8} \left\{ 
\begin{array}{rlc}
 \sqrt 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{1}{2} \le z < \frac{3}{4}\\
-\sqrt 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{3}{4} \le z < 1          \\
       0 & \hspace{.2in}\mbox{otherwise in } [0,1]
\end{array}
\right.
\end{eqnarray}
\begin{center}{\Huge $\cdots\cdots$}\end{center}
\begin{eqnarray}
h_7(z) \equiv h_{24}(z) = \frac{1}{\sqrt 8} \left\{ 
\begin{array}{rlc}
 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{3}{4} \le z < \frac{7}{8}\\
-2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{7}{8} \le z < 1          \\
 0 & \hspace{.2in}\mbox{otherwise in } [0,1]
\end{array}
\right.
\end{eqnarray}

and
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c c c c c c c}   \hline \hline
$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          \\ \hline \hline
\end{tabular} 
\end{center}
\end{table}

\clearpage

Since
\begin{equation}
H_{ij}=\frac{1}{\sqrt L}h_j(\frac{j}{L}),
\end{equation}

we obtain
\begin{eqnarray}
H =
\left(
\begin{array}{cccccccc}
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{array}
\right)
\end{eqnarray}

\clearpage
\noindent
$\Box$ {\bf Features for Texture Recognitions:}\\

\noindent
To describe an image by {\it fine} or {\it coarse}, {\it smooth} or 
{\it irregular}, {\it homogeneous} or {\it inhomogeneous} and so forth
 
\begin{itemize}
\item First-order Statistics Features
\item Second-order Statistics Features
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf First-order Statistics Features:}\\

\noindent
Let
\begin{equation}
P(I) = \frac {\mbox{number of pixels with gray level } I}
             {\mbox{total number of pixels in the region}}\\
\end{equation}
\noindent
Assume that we have $N_g$ gray levels.

\noindent
$\bullet$ Then, the {\it moments}
\begin{equation}
m_i=E[I^i] = \sum_{I=0}^{N_g-1} I^i P(I)\\
\end{equation}

\noindent
$\bullet$ and the {central moment}
\begin{equation}
\mu_i=E[(I - E[I])^i] = \sum_{I=0}^{N_g-1} (I-m_I)^i P(I)\\
\end{equation}

\begin{itemize}
\item[$\star$] The most frequently used central moments:
   \begin{itemize}
   \item[$\cdot$] $\mu_2 = \sigma^2$ $\cdots$ {\it variance}
      \begin{itemize}
      \item[] a measure of the histogram width: \\
              how much the gray levels differ from the mean
      \end{itemize}
   \item[$\cdot$] $\mu_3$ $\cdots$ {\it skewness}
      \begin{itemize}
      \item[] the degree of histogram asymmetry around the mean
      \end{itemize}
   \item[$\cdot$] $\mu_4$ $\cdots$ {\it kurtosis}
      \begin{itemize}
      \item[] a measure of the histogram sharpness
         \begin{itemize}
         \item[-] {\it platykurtic} (sharp);
         \item[-] {\it mesokurtic} (medium);
         \item[-] {\it leptokurtic} (dull).
         \end{itemize}
      \end{itemize}
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\bullet$ {\it Entropy}
\begin{equation}
H = -E[\log_2 P(I)] = - \sum_{I=0}^{{N_g}-1} P(I)\log_2 P(I)
\end{equation}
\begin{itemize}
\item[] a measure of histogram uniformity:
   \begin{itemize}
   \item[]The closer to the uniform distribution ($P(I)=\mbox{const.}$),
          the higher the $H$. 
   \end{itemize}
\end{itemize}

\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\
\begin{itemize}
\item Exercise
   \begin{itemize}
   \item[] Calculate $\mu_1$, $\mu_2$, $\mu_3$ and $H$ 
           of the four histograms bellow.
   \end{itemize}
\end{itemize}
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c c c c c c c}   \hline \hline
\hspace*{.1in} & histgram-1 & histgram-2 & histgram-3 & histgram-4 \\ \hline
$P(0)$         & 5          &  1          & 7          & 5   \\
$P(1)$         & 6          & 14          & 8          & 5   \\
$P(2)$         & 5          &  1          & 1          & 5   \\ \hline
broad?         & yes        & no          & medium     & yes \\
symmetric?     & yes        & yes         & no         & yes \\
sharp?         & no         & yes         & medium     & no  \\
uniform?       & medium     & no          & no         & yes \\ 
\hline \hline
\end{tabular} 
\end{center}
\end{table}

\clearpage
\noindent
$\Box$ {\bf Second-order Statistics Features:}\\
\noindent
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
\begin{itemize}
\item[-] Are all low-value gray levels positioned together?
\item[-] Are they interchanged with the high-value ones?
\end{itemize}
\noindent
That is, the second-order statistics indicate how two specific level $I_1$
and $I_2$ occupy pixels in a line of slope $\phi$ separating with 
a distance $d$.
\noindent
Then, a two-dimensional histogram:
\begin{equation}
P(I_1, I_2) = 
   \frac{\mbox{number of pairs of pixels with values } (I_1, I_2)}
        {\mbox{total number of possible pairs}}
\end{equation}
\noindent
with respect to
\begin{itemize}
\item[$\star$] the relative distance $d$ measured in pixel numbers 
   \begin{itemize}
   \item[] e.g., $d=1$ for neighboring pixels.
   \end{itemize}
\item[$\star$] the orientation $\phi$ quantized in for directions: 
               horizontal, diagonal, vertical, and anti-diagonal 
               $(0^{\circ}, 45^{\circ}, 90^{\circ}, 135^{\circ})$.
\end{itemize}

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=two-d-histgrm.eps,width=10cm,height=6cm}
 \end{center}
\end{figure}

\clearpage
\noindent
For each of the histograms the {\it co-occurrence matrix} is defined as:

\begin{equation}
A^{\phi}(d) = P (I_1, I_2)
\end{equation}
\noindent
Take for example the image with four gray levels bellow:

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=a-gray-image.eps,width=8cm,height=4.8cm}
 \end{center}
\end{figure}

\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c c}   \hline \hline
\hspace*{.1in} & $d=1$ & $d=1$ & $d=2$\\
\hspace*{.1in} & $\phi=0^\circ$ & $\phi=45^\circ$ & $\phi=135^\circ$\\
\hline
$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               \\ 
\hline
total sum      & 12              & 9               & 4               \\
\hline \hline
\end{tabular} 
\end{center}
\end{table}

\clearpage
\noindent
\begin{itemize}
\item The first one may be denoted as:
\end{itemize}
\begin{eqnarray}
\frac{1}{12}\left(
\begin{array}{rrrr}
2 & 1 & 1 & 0\\
\star & 1 & 0 & 0\\
\star & \star & 3 & 3\\
\star & \star & \star & 1\\
\end{array}
\right).
\end{eqnarray}

\begin{itemize}
\item[] However we usually adopt the way:
\end{itemize}
\begin{eqnarray}
A^0(1) = \frac{1}{24}\left(
\begin{array}{rrrr}
4 & 1 & 1 & 0\\
1 & 2 & 0 & 0\\
1 & 0 & 6 & 3\\
0 & 0 & 3 & 2\\
\end{array}
\right),
\end{eqnarray}
\begin{itemize}
\item[] by making every $i$-$j$ entry identical to $j$-$i$ entry 
        for $i \ne j$, and multiplying diagonal element by two 
        for compensation. 
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf Features for texture recognition}\\

\hspace*{1in}--- 1. Features using {\it occurrence matrix.}\\

\noindent
$\bullet$ Angular second moment:
\begin{equation}
X_{\mbox{asm}}=\sum_{i=0}^{N_g-1} \sum_{j=0}^{N_g-1} (P(i,j))^2
\end{equation}
\begin{itemize}
\item[$\star$] A measure of the smoothness.
   \begin{itemize}
   \item[$\cdot$] If indeed all pixels are of the same gray level $I=k$, 
                  then $P(k,k)=1$ and P(i,j)=0 for $i\ne k$ or $j\ne k$;
   \item[$\cdot$] Or, if we have all possible pairs of gray levels with 
                  equal probability $1/R$, then $X_{\mbox{asm}}= R/R^2=1/R$
   \end{itemize}
\item[$\star$] The less smooth the region is, the more uniformly 
               distributed $P(i,j)$ and the lower the $X_{\mbox{asm}}$.\\
\end{itemize}

\hspace*{1in}\\
\noindent
$\bullet$ Contrast:
\begin{equation}
X_{\mbox{con}}=\sum_{n=0}^{N_g-1} n^2 \Biggl(
\sum_{\scriptstyle j=0 \atop \scriptstyle \mid j-i \mid =n}^{N_g-1} 
\sum_{i=0}^{N_g-1} 
P(i,j) \Biggr)
\end{equation}
\begin{itemize}
\item[$\star$] A measure of the image contrast.
   \begin{itemize}
   \item[$\cdot$] $\sum_i \sum_j P(i,j)$ is the percentage of pixel pairs 
                  whose intensity differs by $n$.
   \item[$\cdot$] The $n^2$ dependence weights the big differences more.
   \end{itemize}
\item[$\star$] $X_{\mbox{con}}$ 
               takes high values for images of high contrast.
\end{itemize}

\clearpage
\noindent
$\bullet$ Inverse difference moment:
\begin{equation}
X_{\mbox{idm}} = \sum_{i=0}^{N_g-1} \sum_{j=0}^{N_g-1} 
\frac{P(i,j)}{1+(i-j)^2}
\end{equation}
\begin{itemize}
\item[$\star$] This feature takes high values for low-contrast images 
               due to the inverse $(i-j)^2$ dependence.
\end{itemize}

\hspace*{1in}\\
\noindent
$\bullet$ Entropy:
\begin{equation}
X_{\mbox{entropy}} = - \sum_{i=0}^{N_g-1} \sum_{j=0}^{N_g-1} 
P(i,j)\log_2 P(i,j)
\end{equation}
\begin{itemize}
\item[$\star$] A measure of randomness.
\item[$\star$] Higher values for more random images.
\end{itemize}

%%\hspace*{1in}\\
%%\noindent
%%$\bullet$ Variance:
%%\begin{equation}
%%X_{\mbox{var}} = \sum_{i=0}^{N_g-1} \sum_{j=0}^{N_g-1} (i-\mu)^2 P(i,j)
%%\end{equation}
%%
%%\hspace*{1in}\\
%%\noindent
%%$\bullet$ Correlation:
%%\begin{equation}
%%X_{\mbox{cor}} = \frac 
%%{\Biggl(\displaystyle \sum_{i=0}^{N_g-1} \displaystyle \sum_{j=0}^{N_g-1} 
%%ij P(i,j) \Biggr ) - \mu_x \mu_y } 
%%{\sigma_x \sigma_y}
%%\end{equation}

\clearpage
\noindent
$\Box$ {\bf Run Length Features}\\

\hspace*{1in}--- 2. Features using {\it gray level run lengths.}\\

\begin{itemize}
\item Gray Level Run:
   \begin{itemize}
   \item a set of consecutive pixels having the same gray level.
   \end{itemize}
\item Run Length Features:
   \begin{itemize}
   \item an information related to the number of each gray level
         appears in the image by itself, in pairs, and so on.
   \end{itemize}
\item Run Length Matrix $Q^\phi$:
   \begin{itemize}
   \item the ($i$-$j$) element is the number of times a gray level ($i-1$)
         appears in the image with run length $j$.
   \item the mesearment is along the line whose angle is $\phi$ from
         the horizontal line.
   \end{itemize}
\end{itemize}

In the example we used before, i.e.
\begin{eqnarray}
I =
\left(
\begin{array}{rrrr}
0 & 0 & 2 & 2\\
1 & 1 & 0 & 0\\
3 & 2 & 3 & 3\\
3 & 2 & 2 & 2\\
\end{array}
\right)
\end{eqnarray}

\begin{eqnarray} \label{eq:zero-degree}
Q^{0^{\circ}} =
\left(
\begin{array}{rrrr}
0 & 2 & 0 & 0\\
0 & 1 & 0 & 0\\
1 & 1 & 1 & 0\\
2 & 1 & 0 & 0\\
\end{array}
\right)
\hspace{.1in} \mbox{ or } \hspace{.1in}
Q^{45^{\circ}} =
\left(
\begin{array}{rrrr}
4 & 0 & 0 & 0\\
2 & 0 & 0 & 0\\
6 & 0 & 0 & 0\\
4 & 0 & 0 & 0\\
\end{array}
\right)
\end{eqnarray}

\clearpage
\noindent
$\Box$ {\bf Five Run Length Features:}\\

\noindent
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:\\


\noindent
$\bullet$ Short run emphasis:
\begin{equation} 
Y_{\mbox{sre}} = \frac
{\displaystyle \sum_{i=1}^{N_g}{\sum_{j=1}^{N_r} (Q(i,j)/j^2 )}}
{\mbox{total number of run length}}
\end{equation}

\noindent
$\bullet$ Long run emphasis:
\begin{equation}
Y_{\mbox{lre}} = \frac
{\displaystyle \sum_{i=1}^{N_g}{\sum_{j=1}^{N_r} (Q(i,j)j^2 )}}
{\mbox{total number of run length}}
\end{equation}

\noindent
$\bullet$ Gray level non-uniformity:
\begin{equation}
Y_{\mbox{gln}} = \frac
{\displaystyle 
\sum_{i=1}^{N_g} \Biggl( \sum_{j=1}^{N_r} Q(i,j) \Biggr)^2} 
{\mbox{total number of run length}}
\end{equation}

\noindent
$\bullet$ Run length non-uniformity:
\begin{equation}
Y_{\mbox{gln}} = \frac
{\displaystyle 
\sum_{j=1}^{N_r} \Biggl( \sum_{i=1}^{N_g} Q(i,j) \Biggr)^2} 
{\mbox{total number of run length}}
\end{equation}

\noindent
$\bullet$ Run percentage:
\begin{equation}
Y_{\mbox{rp}} = \frac
{\displaystyle \sum_{i=1}^{N_g}{\sum_{j=1}^{N_r} Q(i,j)}}
{\mbox{total possible runs in the image}}
\end{equation}

\clearpage
\noindent
$\Box$ Some remarks:\\
\begin{itemize}
\item The total number of run lengths in the matrix is 
\begin{equation}
\sum_{i=1}^{N_g} \sum_{j=1}^{N_r} Q(i,j)
\end{equation}
which takes the value 9 for $\phi=0^{\circ}$, and 16 for $\phi=45^{\circ}$
in the equation (\ref{eq:zero-degree}).
\item Short run emphasis:
   \begin{itemize}
   \item $Y_{\mbox{sre}}$ emphasizes small run lengths 
         due to the division by $j^2$; 
   \item Thus $Y_{\mbox{sre}}$ is expect to be large for coarser image.
   \end{itemize}
\item Long run emphasis:
   \begin{itemize}
   \item $Y_{\mbox{lre}}$ gives emphasis to long run lengths 
         due to the division by $j^2$; 
   \item Thus $Y_{\mbox{lre}}$ is expect to be large for smoother image.
   \end{itemize}
\item Gray level non-uniformity:
   \begin{itemize}
   \item The term $\sum_j^{N_r}Q(i,j)$ is the total number of run length 
         for each gray level.
   \item Large run length values contribute a great deal 
         becaus of the square.
   \item When runs are uniformly distributed among the gray levels,
         $Y_{\mbox{gln}}$ takes small values.
   \end{itemize}
\item Run length non-uniformity:
   \begin{itemize}
   \item In a similar way as $Y_{\mbox{gln}}$, $Y_{\mbox{rln}}$ is
         a measure of run length nonuniformity. 
   \end{itemize}
\item Run percentage:
   \begin{itemize}
   \item If all runs had length equal to one, that is, the total number 
         of pixels $Y_{\mbox{rp}}$ takes low values for smooth images.
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ Examples:\\

For an image:
\begin{eqnarray}
I = \left(
\begin{array}{rrrr}
0 & 0 & 2 & 2\\
1 & 1 & 0 & 0\\
3 & 2 & 3 & 3\\
3 & 2 & 2 & 2\\
\end{array}
\right)
\end{eqnarray}

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

\begin{eqnarray}
Q^0 = \left(
\begin{array}{rrrr}
0 & 2 & 0 & 0\\
0 & 1 & 0 & 0\\
1 & 1 & 1 & 0\\
2 & 1 & 0 & 0\\
\end{array}
\right)
\end{eqnarray}

and 

\begin{eqnarray}
\nonumber
Y_{\mbox{sre}} &=& \frac{2/4+1/4+\{1+1/4+1/9\}+\{2+1/4\}}{9}\\
\nonumber
Y_{\mbox{lre}} &=& \frac{\{2\cdot4\}+\{1\cdot4\}+\{1+1\cdot4+1\cdot9\}
                         \{2+1\cdot4\}}{9}\\
\nonumber
Y_{\mbox{gln}} &=& \frac{4+1+9+9}{9}\\
\nonumber
Y_{\mbox{rln}} &=& \frac{9+25+1+0}{9}\\
\nonumber
Y_{\mbox{rp}} &=& \frac{9}{16}\\
\end{eqnarray}

\clearpage
\noindent
$\Box$ Coarse, smooth, uniform?:\\

An example of $N_g=2$:
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=coarse-smooth.eps,width=14cm,height=14cm}
 \end{center}
\end{figure}

\clearpage
\noindent
$\Box$ {\bf Bayes Decision Theory}\\
\hspace*{2in}--- for the design of classifiers.

\begin{itemize}
\item[]As we have learned so far,
   \begin{itemize}
   \item[] classifiers classify unknown patterns into the {\it most
           probable class.}\\
   \end{itemize}
\item[]Then
   \begin{itemize}
   \item[] what ``most probable'' means?\\
   \end{itemize}
\item Moreover
   \begin{itemize}
   \item[]Pattern Recognition is more or less statistical due to:
      \begin{itemize}
      \item statistic nature of feature selection;
      \item statistic variation of patterns;
      \item noise in employing sensors.\\
      \end{itemize}
   \end{itemize}
\item[]Hence
   \begin{itemize}
   \item[]we study here the Baysean Statistical Theory.
   \end{itemize}
\end{itemize}

\clearpage
\begin{itemize}
\item When we classify an unknown pattern which is represented by a feature
vector {\bf x}, we consider $M$ conditional probability
\begin{equation}
p(\omega_i \vert \mbox{\bf x}) \hspace{.2in} i=1, \cdots, M
\end{equation}
\item[]called {\it a posteriori probability}.\\
\item Then we define ``the most probable class'' as $\omega_i$ with
the highest $p(\omega_i \vert \mbox{\bf x})$.\\
\item The other statistical quantities:
   \begin{itemize}
   \item {\it a priori} probability $p(\omega_i)$;
   \item {\it likelihood} function of $\omega_i$ w.r.t. {\bf x};
   \item probability distribution function (pdf) of {\bf x}.\\
   \end{itemize}
\item Baysian rule is
\begin{equation}
p(\omega_i \vert \mbox{\bf x}) = \frac
{p(\mbox{\bf x} \vert \omega_i) p(\omega_i)}
{\displaystyle \sum_{k=1}^M p(\mbox{\bf x} \vert \omega_k) p(\omega_k)}
\end{equation}
\item[]where the denominator
\begin{equation}
\sum_{k=1}^M p(\mbox{\bf x} \vert \omega_k) p(\omega_k) = p(\mbox{\bf x}).
\end{equation}
\end{itemize}

\clearpage
\noindent
$\bullet$ Example-1:
\begin{itemize}
\item[$\cdot$] We have two bags which we can not tell 
               the difference from outside.
\item[$\cdot$] One bag called R includes 70 red balls and 30 blue balls.
\item[$\cdot$] The other bag called B includes 30 red balls and 70 blue 
               balls.
\item[$\cdot$] When we take one bag at random and pick up 12 balls
               returning it to the bag at each time.
\item[$\cdot$] The result is the number of red balls was 8 and blue one
               was 4.
\item[$\cdot$] Then was the bag estimated to be R or B, and how probable
               the estimate is?\\
\end{itemize}
\begin{center} \underline{\hspace*{7in}} \\ \end{center}
Clearly,
\begin{displaymath}
p(R)=p(B)=1/2
\end{displaymath}
\begin{eqnarray}
\nonumber
p(D \vert R) &=& _{12}C_{8}(0.7)^8(0.3)^4\\
\nonumber
p(D \vert B) &=& _{12}C_{8}(0.3)^8(0.7)^4
\end{eqnarray}
So we obtain
\begin{displaymath}
p(R \vert D)=\frac{(0.7)^8(0.3)^4}{(0.7)^8(0.3)^4+(0.3)^8(0.7)^4}
\end{displaymath}
(How big it is compared to our intuitive estimation!)

\clearpage
\noindent
$\bullet$ Example-2:
\begin{itemize}
\item[$\cdot$] Three prisoners ({\bf A}, {\bf B}, and {\bf C}) are 
               in a prison.
\item[$\cdot$] {\bf A} knows the fact two out of three are to be 
               executed tomorrow, and the rest becomes free.
\item[$\cdot$] {\bf A} thought either one of {\bf B} or {\bf C} is sure
               to be executed. 
\item[$\cdot$] Then, {\bf A} asked a guard ``even if you tell me
               which of {\bf B} and {\bf C} is executed, that will not give
               me any information aboutme. So please tell that.'' 
\item[$\cdot$] The guard answers {\bf C}. $\Rightarrow$ data $D$
\item[$\cdot$] Now, {\bf A} knows one of {\bf A} or {\bf B} is sure to be
               free.
\end{itemize}
\begin{center} 
\underline{\hspace*{7in}} \\ 
\hspace*{1in}\\
So you guess {\it a posteriori} probability $p(A \vert D) = 1/2$?\\
\hspace*{1in}\\
If this is correct, then the answer of the guard had given an information 
about {\bf A}, since {\it a priori} probability $p(A)=1/3$.\\

\hspace*{1in}\\
\underline{\hspace*{7in}} \\ 
\hspace*{1in}\\

Try to apply Baysean rule, if you agree
\begin{displaymath}
p(A) = p(B) = p(C) = 1/3
\end{displaymath}
\begin{eqnarray}
p(D \vert A) &=& 1/2 \\
p(D \vert B) &=& 1   \\
p(D \vert C) &=& 0
\end{eqnarray}
\end{center}


\clearpage
\newtheorem{bayes}{Theorem}%%[section]
\begin{bayes}[Bayes Decision Theory]
A pattern which has {\bf x} should be classified so that
$p(\omega_i \vert {\bf x})$ takes the maximum value, where \\
\begin{equation}\label{eq:bayes}
p(\omega_i \vert \mbox{\bf x}) = \frac
{p(\mbox{\bf x} \vert \omega_i) p(\omega_i)}
{\displaystyle \sum_{k=1}^M p(\mbox{\bf x} \vert \omega_k) p(\omega_k)}
\end{equation}
\end{bayes}

\hspace*{1in}\\
\underline{\hspace*{7in}} \\ 
\hspace*{1in}\\

\begin{itemize}
\item $p(\omega_i)$ are usually, known or if not it can be estimate from 
      the training sample, i.e.,
   \begin{itemize} 
   \item if $N_i$ patterns out of $N$ test samples are classified to
           $\omega_i$ then
              \begin{equation}
              p(\omega_i)=\frac{N_i}{N}\\
              \end{equation} 
   \end{itemize}
\item $p(\mbox{\bf x} \vert \omega_i)$ can be also estimated from 
      the training samples (later in detail.)
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf To summarize}
\begin{itemize}
\item Bayes classifier is:
   \begin{itemize}
   \item[] If $p(\omega_i \vert \mbox{\bf x})$ is greater than
         any $p(\omega_j \vert \mbox{\bf x}) \hspace{.2in}
         j = 1, \cdots,M j \ne i$, then classify {\bf x} 
         in class $\omega_i$
   \end{itemize}
\item If $\omega_i$ is adjacent to $\omega_j$
   \begin{itemize}
   \item[] $p(\omega_i \vert \mbox{\bf x}) 
              - p(\omega_j \vert \mbox{\bf x}) = 0$ 
           is called a {\it decision surface}
   \end{itemize}
\item or
   \begin{itemize}
   \item[] if $f(\cdot)$ exists such that
   \begin{equation}\label{eq:mif}
   g_i(x) \equiv f(p(\omega_j \vert \mbox{\bf x})
   \end{equation}
           where $f(\cdot)$ is a  monotonically increasing function,
           then $f$ is called a discriminant function.
   \end{itemize}
\item Then
   \begin{itemize}
   \item[] if $g_i (\mbox{\bf x}) > g_j(\mbox{\bf x})$ 
           for $\forall j \ne i$ then classify {\bf x} to $\omega_i$,
   \end{itemize}
\item and
   \begin{itemize}
   \item[] decision surface is determined by
   \begin{equation}        
          g_{ij}(\mbox{\bf x}) \equiv 
          g_i(\mbox{\bf x}) - g_j(\mbox{\bf x}) = 0,
          \hspace{.2in}  i,j = 1,2,\cdots, M.
   \end{equation}
   \end{itemize}
\item But usually
   \begin{itemize}
   \item[] we know or can obtain $p(\mbox{\bf x}\vert \omega_j)$
           rather than $p(\omega_j \vert \mbox{\bf x})$
   \end{itemize}
\item and 
   \begin{itemize}
   \item[] in most cases $p(\mbox{\bf x}\vert \omega_j)$ is Gaussian
           distribution.
   \end{itemize}
\clearpage
\item Therefore
   \begin{itemize}
   \item[] if we use the equation (\ref{eq:bayes})
           under an assamption of $p(\omega_1)=p(\omega_2)=\cdots
           =p(\omega_N)=1/N$ we can use $p(\mbox{\bf x}\vert \omega_j)$.
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ An example for $i=2$.
\begin{eqnarray}
\left\{
\begin{array}{lll}
\mbox{if} & p(\omega_1 \vert \mbox{\bf x}) > p(\omega_2 \vert \mbox{\bf x})
   & {\bf x} \mbox{ is classified to } \omega_1.\\
\mbox{if} & p(\omega_2 \vert \mbox{\bf x}) > p(\omega_1 \vert \mbox{\bf x})
   & {\bf x} \mbox{ is classified to } \omega_2.\\
\end{array}
\right.
\end{eqnarray}
\hspace*{1in}\\
\noindent
where
\begin{displaymath}
p(\omega_i \vert \mbox{\bf x}) = \frac
{p(\mbox{\bf x} \vert \omega_i) p(\omega_i)}
{p(\mbox{\bf x} \vert \omega_1) p(\omega_1) +
 p(\mbox{\bf x} \vert \omega_2) p(\omega_2)}
\end{displaymath}
\hspace*{1in}\\
\noindent
so, if $p(\omega_1)=p(\omega_2)=1/2$
\begin{eqnarray}
\left\{
\begin{array}{lll}
\mbox{if} & p(\mbox{\bf x} \vert \omega_1)>p(\mbox{\bf x} \vert \omega_2)  
   & {\bf x} \mbox{ is classified to } \omega_1.\\
\mbox{if} & p(\mbox{\bf x} \vert \omega_2)>p(\mbox{\bf x} \vert \omega_1)  
   & {\bf x} \mbox{ is classified to } \omega_2.\\
\end{array}
\right.
\end{eqnarray}
\hspace*{1in}\\
\noindent
where $p(\mbox{\bf x} \vert \omega_i)$ is a probability density function.

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=two-gaussian.eps,width=16cm,height=10cm}
 \end{center}
\end{figure}

\noindent
Classification Error Probability in this case
\begin{equation} \label{eq:error-prob}
p_e=\int_{-\infty}^{x_0} p(\mbox{\bf x} \vert \omega_2) dx +
\int_{x_0}^{\infty} p(\mbox{\bf x} \vert \omega_1) dx
\end{equation}

\clearpage
\begin{itemize}
\item The equation (\ref{eq:error-prob}) is also expressed as:
\begin{equation}
p_e=\int_{R_1} p(\mbox{\bf x} \vert \omega_2) dx +
\int_{R_2} p(\mbox{\bf x} \vert \omega_1) dx
\end{equation}
where $R_i$, \hspace{.1in} $i=1,2$ \hspace{.1in}
are regions shown in the Figure.\\
\item By generalizing this, we obtain {\it} the probability of misclassify
$\omega_k$ to $\omega_i$ as:
\begin{equation}
p_k= \sum_{i=1}^M \int_{R_i} p(\mbox{\bf x} \vert \omega_k) dx \\
\end{equation}
\item If $\lambda_{ki}$, the importance of misclassification 
of $\omega_k$ to $\omega_i$, is taken into consideration, then
the {\it total risk} are defined as:
\begin{equation}
p_k=\sum_{i=1}^M \lambda_{ki} \int_{R_i} p(\mbox{\bf x} \vert \omega_k)dx\\
\end{equation}
\item And $\displaystyle p=\sum_{k=1}^M r_k p(\omega_k)$ 
should be minimized.\\
\item This is achieved when each integral is minimized. \\
\item So, {\bf x} should be classified to $\omega_i$, that is, 
$\mbox{\bf x} \in R_i$ \hspace{.2in} if
\begin{equation}
\sum_{k=1}^M \lambda_{ki} p(\mbox{\bf x} \vert \omega_k) p(\omega_k) <
\sum_{k=1}^M \lambda_{kj} p(\mbox{\bf x} \vert \omega_k) p(\omega_k)
\end{equation}
\item[]for $\forall j \ne i$.
\end{itemize}

\clearpage
\begin{itemize}
\item In a two-class case example:
   \begin{itemize}
   \item assign {\bf x} to $\omega_1$ if
   \begin{equation}
   (\lambda_{21}-\lambda_{22})p(\mbox{\bf x} \vert \omega_2) p(\omega_2) <
   (\lambda_{12}-\lambda_{11})p(\mbox{\bf x} \vert \omega_1) p(\omega_1)
   \end{equation}
   \item Therefore, assign {\bf x} to $\omega_1$ if
   \begin{equation}
   \frac{p(\mbox{\bf x} \vert \omega_1)}{p(\mbox{\bf x} \vert \omega_2)} >
   \frac{p(\omega_1)}{p(\omega_2)} 
   \frac{\lambda_{21}-\lambda_{22}}{\lambda_{12}-\lambda_{11}}\\
   \end{equation}
   \item[]
   \item In the special case where
   \begin{displaymath}
   \lambda_{11}=\lambda_{22}=0, \hspace{.2in} \lambda_{21}>\lambda_{12},
   \hspace{.2in} \mbox{and} p(\omega_1)=p(\omega_2)=1/2
   \end{displaymath}
   \item[] assign {\bf x} to $\omega_2$ if
   \begin{equation}\label{eq:just-above}
   p(\mbox{\bf x} \vert \omega_2) > p(\mbox{\bf x} \vert \omega_1) 
   \frac{\lambda_{12}}{\lambda_{21}}\\
   \end{equation}
   \item What is the implication of equation (\ref{eq:just-above})?
   \end{itemize}
\end{itemize}

\clearpage
\begin{itemize}
\item Example
   \begin{itemize}
   \item[$\star$] $p(\mbox{\bf x} \vert \omega_1)$ and 
                  $p(\mbox{\bf x} \vert \omega_1)$
                  follows a Gaussian distribution 
                  whose mean and standard deviation are:
   \begin{displaymath}
   \mu_1 = 0, \hspace{.2in}\mu_2=1, \hspace{.2in} \mbox{and} 
   \sigma_1=\sigma_2 =1/2.
   \end{displaymath}
   \item[] that is,
   \begin{eqnarray}
   \nonumber
   p(\mbox{\bf x} \vert \omega_1) &=& \frac{1}{\sqrt \pi} \exp (- x ^2)\\
   \nonumber
   p(\mbox{\bf x} \vert \omega_1) &=& \frac{1}{\sqrt \pi} \exp (- x ^2)
   \end{eqnarray}
   \item[(1)] Obtain $x_0$.
   \item[(2)] When
\begin{eqnarray}
\nonumber
[\lambda_{ik}]=
\left(
\begin{array}{cc}
0   & 0.5 \\
1.0 & 0   \\
\end{array}
\right)
\end{eqnarray}
   \item[] how $x_0$ will be affected?   
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf Multi-dimensional Gaussian distribution}\\

\noindent
Classifications in real-world problems, however, 
might be in a multi-dimensional space, not 1-D space.\\

\noindent
So, we must be familiar with multi-dimensional Gaussian distribution.\\

\noindent
The one-dimensional version
\begin{equation}
p(x)= \frac{1}{\sqrt {2\pi} \sigma} \exp (- \frac{(x-\mu)^2}{2 \sigma^2})
\end{equation}

\noindent
is expanded for $\mbox{\bf x} = (x_1, x_2, \cdots, x_l)$ to the form:
\begin{equation}
p(x)= \frac{1}{\sqrt {2\pi} {\vert S \vert}^{1/2}}
\exp (- \frac{1}{2}\Bigl(\mbox{\bf x}-\mbox{\bf m})^T S^{-1}
(\mbox{\bf x}-\mbox{\bf m})\Bigr)
\end{equation}

\noindent
where the components of {\bf m} are the mean of 
$x_i \hspace{.2in} i=1,\cdots, l)$, that is,
\begin{equation}
m_i = E [ x_i ]
\end{equation}
and $S$ is called a {\it covariance matrix} and the components are
\begin{eqnarray}
\left\{
\begin{array}{lll}
\sigma_{ii} &=& \sigma_i^2 = E[(x_i - m_i)^2] \\
\sigma_{ij} &=& E[(x_i - m_i)(x_j - m_j)] \hspace{.2in} \mbox{if}
\hspace{.2in} i \ne j\\
\end{array}
\right.
\end{eqnarray}

\clearpage
\begin{itemize}
\item If we use here $ln$ as $f(\cdot)$ in the equation (\ref{eq:mif})
\begin{eqnarray}
\nonumber
g_i(\mbox{\bf x}) 
 &=& \ln (p(\mbox{\bf x} \vert \omega_i)p(\omega_i))\\
\nonumber
 &=& \ln p(\mbox{\bf x} \vert \omega_i) + \ln p(\omega_i)\\
\nonumber
 &=& - \frac{1}{2} (\mbox{\bf x}-\mbox{\bf m}_i)^T
            S_i^{-1}(\mbox{\bf x}-\mbox{\bf m}_i) + \ln p(\omega_i) + c_i\\
\nonumber
 &=& -\frac{1}{2} \mbox{\bf x}^T S_i^{-1}\mbox{\bf x}
     +\frac{1}{2} \mbox{\bf x}^T S_i^{-1}\mbox{\bf m}_i
     -\frac{1}{2} \mbox{\bf m}_i^T S_i^{-1}\mbox{\bf m}_i\\
\nonumber
  && \hspace{1in} +\frac{1}{2} \mbox{\bf m}_i^T S_i^{-1}\mbox{\bf x}
     + \ln p(\omega_i) + c_i\\
\end{eqnarray}
\item[]where
\begin{equation}
c_i = - \frac{l}{2} \ln 2\pi - \frac{1}{2} \ln \vert S_i \vert
\end{equation}
\item If for instance
\begin{eqnarray}
l=2, \hspace{.2in} \mbox{and} \hspace{.2in} S_i = 
\left(
\begin{array}{cc}
\sigma_1^2 & 0          \\
0          & \sigma_2^2 \\
\end{array}
\right)
\end{eqnarray}
then
\begin{eqnarray}
\nonumber
g_i(\mbox{\bf x}) 
  &=& - \frac{1}{2\sigma_i^2}(x_1^2+x_2^2)
      + \frac{1}{\sigma_i^2} (\mu_{i1}x_1 + \mu_{i2}x_2) \\
\nonumber
   &&\hspace{1in} - \frac{1}{2\sigma_i^2}(\mu_{i1}^2 + \mu_{i2}x^2) 
                  + \ln p(\omega_i) + c_i\\
\end{eqnarray}
\item This is a {\it quadric} form of $x_i$ and $x_2$, that is,
        the classification space is either of 
   \begin{itemize}
   \item[$\star$]{\it ellipsoids}
   \item[$\star$]{\it parabola}
   \item[$\star$]{\it hyperbola}
   \item[$\star$]{\it pair of lines}
   \end{itemize}
\clearpage
\item Two examples:
\begin{eqnarray}
\nonumber
\mbox{1)} \hspace{.2in} S_1 = 
\left(
\begin{array}{cc}
0.10 & 0        \\
0    & 0.15     \\
\end{array}
\right)
%%\end{eqnarray}
%%\begin{eqnarray}
\hspace{.5in} S_2 = 
\left(
\begin{array}{cc}
0.20 & 0        \\
0    & 0.25     \\
\end{array}
\right)
\end{eqnarray}
\begin{eqnarray}
\nonumber
\mbox{2)} \hspace{.2in} S_1 = 
\left(
\begin{array}{cc}
0.10 & 0        \\
0    & 0.15     \\
\end{array}
\right)
\hspace{.5in} S_2 = 
\left(
\begin{array}{cc}
0.15 & 0        \\
0    & 0.10     \\
\end{array}
\right)
\end{eqnarray}
\end{itemize}

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=separation.eps,width=18cm,height=8cm}
 \end{center}
\end{figure}

\end{LARGE}
\end{document}
