This paper presents a novel multi-dimensional hidden Markov model approach to tackle the complex issue of image modeling. We propose a set of efficient algorithms that avoids the exponential complexity of regular multi-dimensional HMMs for the most frequent algorithms (Baum-Welch and Viterbi) due to the use of a random dependency tree (DT-HMM). We provide the theoretical basis for these algorithms, and we show that their complexity remains as small as in the uni-dimensional case. A number of possible applications are given to illustrate the genericity of the approach. Experimental results are also presented in order to demonstrate the potential of the proposed DT-HMM for common image analysis tasks such as object segmentation, and tracking.