Probabilistic Models for Images and Quadtrees: Differences and Equivalences

In this paper we extensively compare from an analytical point of view two random models for binary images, namely the pixel-based model and the node-based model. In particular, we analyze the possibility of reducing the pixel-based model to the node-based model, and we show that this can be done only when we are interested in studying the expected node distribution on each quadtree level, or, in other words, only when the level-by-level expected storage utilization has to be studied. Furthermore, we give a proof that a random model introduced by Samet for images representing spatial data (H. Samet, Computing perimeters of images represented by quadtrees, IEEE Trans. on Pattern Analysis and Machine Intelligence PAMI3 (6) (1981) 683–687), is a particular instance of the node-based model.