A new quadtree complexity theorem

Complexity of hierarchical representation of images is defined as the total number of nodes in the representation tree. An a priori knowledge of this quantity is of considerable interest in problems involving tree search, storage and transmission of imagery. This paper proposes a systematic approach for the evaluation of quadtree complexity that is based on a flexible linkage paradigm. It is further realized that a quadtree may undergo a complexity reduction through node condensation. This event is fully modeled and absorbed in the expected complexity expression through a multidimensional weighting function. Inspection of the weighting surface provides a more clear view of the interaction of quadtree complexity and the random image model