Image classification by a Two Dimensional Hidden Markov ModelAuthor: Jia Li, Amir Najmi and Robert M. GrayPresenter: Tzung-Hsien HoHidden Markov ChainGoal: To implement a novel classifier for image segmentationWhat’s over there? LVQ (Learning vector quantization) BVQ (Bayes vector quantization) CART (Classification and regression trees ) Pseudo-2D HMM Others… (PCA, LDA, neural networks, …)Pseudo 2D HMM Extension of 1D case Not real 2D model since it does not connect all the possible states There is a “superstate” existing in the first element of each row. All the superstates consist of a markov chain. Each row consists of an independent markov chain.Pseudo 2D HMMMarkov Random Field (MRF) A tool to encode contextual constraints into the prior probability.Define (1) neighbors (2) cliques (3) prior clique potentialDerive (4) likelihood energy (5) posterior energyAssumptions in the paper Causal Markov Random FieldMainframe of the paper 2D HMM Model1. Expectation Maximum (EM)2. Viterbi Algorithm for 2D case Feature Selections:1. DCT coefficients & spatial derivatives of the average intensity value of blocks2. Wavelets & Laplacian Measurement2D HMM 1. Training:(a) Divide training images into non-overlapping blocks(b) Extract the features of each block(c) Select the number of states for the 2D-HMM(d) Estimate model parameters based on the feature vectors (v) and their hand-labeled class (c)Training Process Expectation Maximization  Known: Mapping function from S and CE-Step: Compute Q(Φ| Φp)whereTraining Process (cont.) Expectation MaximizationM-Step: Choose Φ to maximize Q(Φ| Φp)Compute it? Thank for diagonal Forward:  Bakward:Where Td: state sequences at dth diagonalSimple example1. Define # of states2. Divided the image into sub-blocks and extract the features (U)of each block.3. Given C(i,j) and random assign 4. Use the parameters to find forward and backward probability based on each diagonal5. Calculate 6. Use L and H to update 7. Go back to step 4mmln,m,Σ and µ , aj)(i,H and j)(i,Lln,m,mmmln,m,Σ and µ , a2D HMM Recognition(a) Generate feature vectors for the testing image(b) Search for the set of classes with maximum a posteriori probability given the feature vectors according to the trained 2D HMM2D Viterbi algorithm The computational complexity is (NxM-1)mo Any way to simplify? Using forward probabilities and applying the blocks of the diagonal to create markovian isolation sequence2D Viterbi algorithm Reminder Viterbi is used to maximize P(I,O| Φ) For 2D, maximize Each point here infers a state sequence at Td2D Viterbi Algorithm (cont.) It is infeasible. NP completeness Proposition: path-constrained Viterbi algorithmEach point here infers a state sequence at Td2D Viterbi Algorithm (cont.) In each diagonal, find the best N routes based on where v is the number of diagonal terms.  We can simplify the constraints above by finding  Best route searching Not a precise model. Two improvements1. Choose large N2. Divide original image into sub-imagesSimple Example 1. Image input 2. Extract the features 3. In each diagonals, pick the best N sequences.  4. Use the normal viterbi to calculate Now Ti is limited by the local maximizor5. Find the highest score of S and C(s)=CAerial Image Segmentation Goal: Try to differentiate the man-made or nature scenes from the aerial image # of states: 5 (3~6 are all available) for nature scene. 9 (7~10 are all available) for man-made scene Size of N: 32 Block size: 4x4Aerial Image Segmentation Feature selection:1. Intra-block feature: DCT coefficients 2.Inter-block feature: Average intensity difference between neighbors (U,L)Results Man-made scene as targets Compared with three other methods(CART, LVQ (learning vector quantization) and BVQ)ResultsHMMCART1 LVQ1SourceDocumentation segmentation Goal: Segmentation of document images into text and photograph # of states: 4 (2~5 are available) Block size: 8x8 Features:Wavelet coefficients (Haar wavelet)(1) Measure the goodness of match between the observed distribution and the Laplacian distribution. (χ2)(2) Measure the likelihood of the wavelet coefficients being composed by highly concentrated values. (L)Documentation segmentation How the hell does it work? (LH HL HH)χ2: Divide the histogram of the wavelet coefficients into bins. fi: relative frequency of bin i and Fi: probability of the Laplacian distribution.L : the weight sum of the concentration level βi.βi is defined as the percentage of the data in a narrow neighborhood based on the total number of data in the zone.∑=−=kiFiFifi122/)(χResultsError rate: fewer than 2% for HMM and CARTSource HMM CARTConclusion 2D HMM takes the inter-blocks relationship into account. That’s why it stands out in most of the current classifier. 2D HMM is still limited by the computational power of the machine. This paper provides a roughly correct version.Questions The computational cost of this algorithm is still high. Maybe not a good real-time processing algorithm. Parallel computing can be applied. Multi-scale (pyramid) processing may be able to assist the inter-block relations we lost in path-constrained viterbi algorithm.Reference1.Rakesh Dugad, U.B Desai, “A tutorial on hidden markov models”, Technical Report No. SPANN-96.1, Bombay Powai, India May, 1996.2. Jeff A. Bilmes, “A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models”, Technical Report 97-021, International Computer Science Institute Berkley CA, April, 1998.3. J. Li and R.M. Gray, “Text and Picture Segmentation by the Distribution Analysis of Wavelet coefficients,” Proceedings of International Conference on Image Processing, Chicago, Oct. 19984. L. Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, Proceedings of the IEEE, vol. 77, pp. 257-286, 1989 5. S.Z. Li, “Markov Random Field Models in Computer Vision”, ICCV 19946. JiangSheng Yu, “Expectation Maximization, An approach to parameter estimation”, Class note, Peking University, China.Your