Generalized comparison of quadtree and bintree storage requirements

摘要

The quadtree and the bintree data structures are two variants on the principle of hierarchical regular decomposition applied to image representation. A comparison of the storage requirements for images represented by these two methods is presented. The relative storage efficiency of quad- and bintrees is determined by two factors: the relative node sizes for the two representations as determined by the data structure implementation; and the number of quadtree leaf node pairs that merge to form a single leaf node after conversion to the bintree representation. A probablistic model for images is developed to analyse the merging probability of quadtree leaf node pairs. The analysis reveals that exactly half of such pairs are expected to merge. Empirical results closely match these calculations. The resulting storage efficiency for a number of representative implementations is discussed. Each of the data structures has implementations (and associated applications) for which it is more space efficient.