A novel reduced-complexity approach to hidden Markov modeling of two-dimensional processes with application to face recognition

The 2-D Hidden Markov Model (HMM) is an extension of the traditional 1-D HMM that has shown distinctive efficiency in modeling 1-D signals. Unlike 1-D HMMs, 2-D HMMs are known for their prohibitively high complexity. This encouraged many researchers to work on alternatives such as Pseudo 2-D HMM and Embedded HMM for 2-D recognition applications to avoid the complexity problem. Those applications include, but are not limited to, Face Recognition, Optical Character Recognition, Face Detection, Image Retrieval, and Object Recognition. The Hidden Layer's complexity of a typical second-order 2-D HMM is normally in the order of (N3). The term "Hidden Layer" refers to the computations of the probabilities of state transition and N is the number of states in the model.; In this thesis, a low complexity high performance 2-D Hidden Markov Model (HMM) is proposed and is applied to the problem of Face Recognition. The proposed model is a true 2-D HMM. The complexity of the Hidden Layer is brought down to the order of (2N2) using a basic assumption of conditional independence between vertical and horizontal state transitions. This assumption allows replacing the 3-D state transition matrix with two 2-D transition matrices.; HMM complexity is always addressed in the literature from the Hidden Layer perspective, yet the complexity of the observation layer is not trivial. The mixtures of the proposed model are tied for lower observation layer complexity. The performance and the complexity of the proposed model with tied mixtures are investigated while applied to the problem of face recognition. The proposed face recognition system achieves recognition rates up to 100% on the AT&T facial database with complexity that is comparable to that of 1-D HMM.