193 
of label. Let P x (j^) be the prior probability of label X s , 
and p (y | x s ) be the probability function which tells us how 
well any occurrence of X s fits / , and P F (f) be the 
probability of the original image. Bayesian theorem gives us the 
posterior distribution: 
p ( x I P F\x(f \ x s)Px( x s) 
WI/, ‘ Pjj) 
(2) 
Since P p (/) is a constant, thus: 
Px\F {■X,\f) 00 Pf\x Cf\x s )PAx s ) (3) 
Our goal is to find an optimal label which maximizes the 
posterior probability, that is the maximum a posterior (MAP) 
estimate: 
y = arg max P X]F (x s | /) (4) 
The key step is to define p(f) and P(F \ X) ■ 
Given p(f | x ) follows Gauss distribution, the distribution is 
represented by its mean u and variance cr . 
x s x s 
Thus energy function is as follows: 
U(X,F) = ^[lnJ(5) 
xeS 2<J X ^ 
Based on Hammersley-Clifford theorem, the joint distribution 
of these conditional prior probabilities modeled by MRFs is 
equivalent to a joint prior probability characterized by a Gibbs 
distribution (Li, 2001). This MRFs-Gibbs equivalence allows us 
to model the complex global contextual relationship of an entire 
image by using MRFs of local pixel neighborhoods, which 
makes MRF computationally tractable and as a very popular 
contextual model. 
P(X) follows a Gibbs distribution: 
P(X) = fxp(-U(X)) < 6 > 
where, Z = yexp(—U(X)) is the normalizing constant. 
x 
U(X) = ^V(X) i s energy function. V C (X) is the clique 
ceC 
potential of clique c eC ■ 
In our case, C is the set of spatial second order cliques 
(doubletons). Each clique corresponds to a pair of neighboring 
pixels. The P(X) will represent the simple fact that 
segmentations should be locally homogeneous. Therefore, these 
potentials favor similar classes in neighboring pixels: 
K( X ) = V ( X ,> X r) = 
+ 1 if x s *x r 
-1 otherwise 
(7) 
There are four different optimization algorithms to find the 
global optimum including Simulated Annealing using 
Metropolis dynamics (Metropolis), Gibbs sampler (Gibbs), 
Iterated Conditional Modes (ICM), and Modified Metropolis 
Dynamics (MMD). 
2.2 SVM Classification Method 
SVM is a classification technique developed by Vapnik and his 
group at AT&T Bell Laboratories. It is based on Vapnik- 
Chervonenkis (VC) dimension theory and Structural Risk 
Minimization (SRM) rule. SVM can solve sparse sampling, 
non-linear, high-dimensional data, and global optimum 
problems. The performance of SVM has been proved as good as 
or significantly better than that of other competing methods in 
most cases (Burges, C. J. C., 1998. Zhang, X. G., 2000).The 
SVM method separates the classes with a hyperplane surface to 
maximize the margin among them (see figure 1), and m is the 
distance between H1 and H 2 , and H is the optimum 
separation plane which is defined as: 
w-x + b = 0, (8) 
where A is a point on the hyperplane, W is a n-dimensional 
vector perpendicular to the hyperplane, and b is the distance of 
the closest point on the hyperplane to the origin. It can be found 
as: 
w-X;+b<-1, fory.=-1 (9) 
w-x i +b> 1, for y. =+l (10) 
These two inequalities can be combined into: 
y,[(u>-x ( )+6]-l>0 V/. (11) 
The SVM attempts to find a hyperplane (8) with minimum 
|| W || 2 that is subject to constraint (11). 
Fig. 1. Optimum separation plane. 
The processing of finding optimum hyperplane is equivalent to 
solve quadratic programming problems: 
mini || w|| 2 + c££ 
2 ,=i 
S.t. yi [w^( Xi ) + b]> l-£. (12) 
4i - o,/ = 1,2,...,/ 
where C is penalty parameter, which is used to control the edge 
balance of the error ^. Again, using the technique of Lagrange 
Multipliers, the optimization problem becomes: 
1 / / / 
min X Z Z a i a jyiyj K ( x i. yj) ~ Z a i 
^ /=1 j=i i=i 
i=i 
0<«,. <C,I = 1,2,...,/ (13) 
where K{x i ,y j ) = ^(x,) • <j)(y } J is kernel function. There are 
three major kernel functions including Gaussian Radius Basis 
Function (RBF), Polynomial, and Sigmoid function. The 
optimum classification plane is solved through chunking, Osuna, 
and SMO algorithms, and then we will only need to compute 
K(x i ,y j ) 1° the training process. The final decision function is: 
f(x) = sgn(Y J y i a i K (x,x i ) + b) O 4 ) 
sv 
When multi-class SVM is concerned, three basic methods are 
available to solve the classification: One-Against-All (OAA), 
One-Against-One (OAO), and Directed-Acyclic-Graph (DAG).