A Generalized Comparison of Quadtree and Bintree Storage Requirements
Files
TR Number
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.