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. In this paper, we introduce an efficient algorithm for approximate decoding of 2-D HMMs, i.e., searching for the most likely state sequence. The basic idea is to approximate a 2-D HMM with a Turbo-HMM (T-HMM), which consists of horizontal and vertical 1-D 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 2-D HMMs: the Path Constrained Variable State Viterbi (PCVSV) algorithm [1]. Finally, we combine our approach with PCVSV and show that the combination outperforms each algorithm taken separately.