Iterative decoding of two-dimensional hidden Markov models

While the hidden Markov model (HMM) has been extensively applied to one-dimensional problems, the complexity of its extension to two-dimensions grows exponentially with the data size and is intractable in most cases of interest. We introduce an efficient algorithm for approximate decoding of 2D HMMs, i.e., searching for the most likely state sequence. The basic idea is to approximate a 2D HMM with a turbo-HMM (T-HMM), which consists of horizontal and vertical 1D HMMs that "communicate", and allow iterated decoding (ID) of rows and columns by a modified version of the forward-backward algorithm. We derive the approach and its re-estimation equations. We then compare its performance to another algorithm designed for decoding 2D HMMs: the path constrained variable state Viterbi (PCVSV) algorithm (Li, J. et al., IEEE Trans. on Sig. Processing, vol.48, no.2, 2000). Finally, we combine our approach with PCVSV and show that the combination outperforms each algorithm taken separately.