GENERALIZED COMPARISON OF QUADTREE AND BINTREE STORAGE REQUIREMENTS

The quadtree and the bintree data structures are two variants on the p rinciple of hierarchical regular decomposition applied to image repres entation. A comparison of the storage requirements for images represen ted 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 representa tion. A probablistic model for images is developed to analyse the merg ing probability of quadtree leaf node pairs. The analysis reveals that exactly half of such pairs are expected to merge. Empirical results c losely match these calculations. The resulting storage efficiency for a number of representative implementations is discussed. Each of the d ata structures has implementations (and associated applications) for w hich it is more space efficient.