A Generalized Comparison of Quadtree and Bintree Storage Requirements
Shaffer, Clifford A.
Heath, Lenwood S.
MetadataShow full item record
The quadtree and 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 quadtrees and bintrees is determined by two factors: the relative mode size 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. The merging probability is analyzed, and found to be close to 0.5 for most images. The resulting storage efficiency for a number for representative implementations is discussed. Each of the data structures has implementations (and associated applications) for which it is more space efficient.