CMSC 828 J - Spring 2006Applications of Hidden Markov ModelsNarayanan RamanathanCMSC 828J - Spring 2006Outlinen A brief introduction to Hidden Markov Models n Three applications of HMMsq Human identification using Gait q Human action recognition from Time Sequential Imagesq Facial expression identification from videosn Discussions & ConclusionsCMSC 828J - Spring 2006Hidden Markov Models (HMMs) – A General Overviewn HMM : A statistical tool used for modeling generative sequences characterized by a set of observable sequences.n The HMM framework can be used to model stochastic processes whereq The non-observable state of the system is governed by a Markov process.q The observable sequences of system have an underlying probabilistic dependence.CMSC 828J - Spring 2006Hidden Markov ModelHMM Model ParametersState Transition MatrixObservation Probability MatrixInitial state probabilitiesCMSC 828J - Spring 2006Three Basic Problems in HMMsn Given a set of observation sequences and the HMM parameters , computing the probability n Given a set of observation sequences and the HMM parameters , computing the optimal state sequencesn Given a set of observation sequences adjusting the HMM parameters to maximize the probabilityCMSC 828J - Spring 2006Things you’ll need to be familiar with……n Forward Algorithm / Backward Algorithmn Viterbi Decoding n Baum Welch Algorithm (Expectation Maximization)n K-means clusteringn Vector Quantization etc.CMSC 828J - Spring 2006Human Identification using Gaitn USF Gait datasetq Dataset comprises of 122 individualsq 12 different Probe sets (different sessions, walking surfaces, shoe type, w/o briefcases, camera orientation)Can we characterize Human gait using Hidden Markov Models ?CMSC 828J - Spring 2006Human Identification using GaitTwo views : Camera L & RTwo different surfaces : Grass and ConcreteThe set-up environmentCMSC 828J - Spring 2006Motivationn Human Gait is often studied as a collection of gait cycles. A Gait cycle corresponds to : rest position – right foot forward – rest position – left foot forward – rest position.n The two inherent components of human gait : q Structural component : One’s physical featuresq Dynamic component : The body’s motion dynamics (the coordinated hand and leg movements)Can the structural and dynamical aspects of Human gait be captured using a Hidden Markov Model framework ?CMSC 828J - Spring 2006Motivation (contd)n From a human gait recognition perspective, what is the physical significance of the HMM parameters ?State Transition matrix Observation Probability matrixInitial state probabilitiesCMSC 828J - Spring 2006Silhouette Extraction : n For each frame in the gait video, a bounding box was defined manually.n A background model is built using statistics of pixels outside the bounding boxn Having learnt the background distribution, the pixels within the bounding box are classified as foreground or background pixels.Silhouette extraction results. The top row illustrates the bounding boxes defined over each frameCMSC 828J - Spring 2006HMM : Observation symbols n Using Background subtraction, the binarized video sequences are extracted This corresponds to a one half of a gait cycle : Rest position – right foot forward – rest position – left foot forward – rest positionThe observation symbols for the HMM problem : they are functions of such binarized silhouettes :CMSC 828J - Spring 2006HMM : Observation symbolsn Kale et al. 2004, define two interpretations to the observation symbols for the HMM framework :q In the first case, the entire background subtracted silhouette is taken as the observation symbol.q In the second case, the width vector is extracted from each frame. Frame-to-Exemplar distance (FED) is defined over each frame and this is taken as the observation symbol.CMSC 828J - Spring 2006HMM : System State identificationn System state identification is often seen analogous to the design of a code bookq Criterion : Minimizing the overall distortion in such a representationexemplar(system state)Vornoi cellsDistance measureModel order (no: of exemplars)is selected based on a plot of the overall distortionCMSC 828J - Spring 2006HMM : System State identificationA plot of sum of the foreground pixels across each frame. The boundaries of gait cycles can be identified. Kale et al (2004) define 6 states for the gait recognition systemCMSC 828J - Spring 2006HMM : System Staten The initial exemplars for a walking sequence are computed as follows :q The gait cycle boundaries are identified for a walking sequenceq Each gait cycle is partitioned in 6 groups of temporally adjancent stances.q The averages of all stances that belong to a particular partition is computed & hence exemplars (or system states) are identified.CMSC 828J - Spring 2006HMM : Parameter initializationCMSC 828J - Spring 2006HMM : Training Phasen Iterative refining is performed in two stages :q Using current values of Exemplars (Eo) and Transition Matrix (Ao) , Viterbi decoding is performed on the input sequence and the most probable sequence of states is obtained :q The corresponding observation index (set of all time instants when a particular state was observed) is provided by q The new set of exemplars are re-esimated using the above observation indicesCMSC 828J - Spring 2006HMM : Training Phaseq Using estimated exemplars E (at time t+1) and state transition matrix A (at time t), we estimate A (at time t+1) using Baum Welch algorithm. q Computing E (at t+1) => computing B (at t+1)q Kale et al (2000) re-initialize the initial state probabilities to 1/N at every time instant.CMSC 828J - Spring 2006HMM : Testing Phasen Given a test sequence, we compute the probability Test sequenceHMM parameters correspondingto the j’th individual in the galleryMatch IDCMSC 828J - Spring 2006Recognition results on USF datasetCMSC 828J - Spring 2006Recognizing Human Action using HMMsn Yamato et al (1992) use HMM to classify human actions in time-sequential images (in our case, sports activities).q Backhand volleyq Backhand strokeq Forehand volleyq Forehand strokeq Smashq ServiceWhat is the intuition behind usinga HMM framework to perform action classification ?Each of the aforementioned activitiescan be characterized by a set of stancesthat are temporally related.Further,