Iterative Decoding of Two-Dimensional Hidden Markov Models

While the hidden Markov model (HMM) has been extensively ap-plied to one-dimensionalproblems, the complexity of its extension to two-dimensions grows exponentially with the data size and is in-tractable 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 I-D HMMs that "communi-cate", 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) al-gorithm [I]. Finally, we combine our approach with PCVSV and show that the combination outperforms each algorithm taken sep-arately. 1