Two Dimensional HiddenMarkovModels (2D-HMMs) provide substantial benefits for many computer vision and image analysis applications. Many fundamental image analysis problems, including segmentation and classification, are target applications for the 2DHMMs. As opposed to the i.i.d. assumption of the image observations, the naturally existing spatial correlations can be readily modeled by solving the 2D-HMM decoding problem. However, computational complexity of the 2D-HMM decoding grows exponentially with the image size and is known to be NP-hard. In this paper, we present a Conditional Iterative Decoding (CID) algorithm for the approximate decoding of 2D-HMMs. We compare the performance of the CID algorithm to the Turbo-HMM (T-HMM) decoding algorithm and show that CID gives promising results. We demonstrate the proposed algorithm on modeling spatial deformations of human faces in recognizing people across their different facial expressions.