Extensible, hierarchical, spatial databases: Variations on a theme of quadtrees

Quadtrees are well known data structures for handling images and image-like objects. They encode an image by recursively quartering it until each remaining region is uniform in color. They encode images hierarchically, so that coarse approximations can be extracted quickly, and they provide a high degree of compression of certain classes of images. Octrees provide similar benefits to three dimensional data. Hierarchical spatial decomposition can be extended to data with dimensionality greater than three. Quadtrees (and their higher dimensional cousins) suffer from shift variance, exhibited by wild changes to the tree structure when the objects within an image change position relative to each other and to the background sampling grid. Quadtrees are primarily used on bilevel images. Multilevel (gray scale) quadtrees tend not to save much storage because regions under consideration for quartering will be split unless all component pixels have precisely the same value. Any difference, no matter how slight, will cause the region to be subdivided. This research presents a new technique for handling image-like objects called the Quadtree Mesh. The quadtree mesh encodes each object within its own quadtree, then couples those quadtree objects together in a spatial network so that proximity queries can be carried out. The addition of a range-search tree to the structure, where the leaf-nodes of the search tree point to locations in the mesh, preserves the overall hierarchical nature of the database. Objects are allowed to move freely throughout the image space, maintaining their hierarchical structure all the while. A quadtree mesh can do no worse than an ordinary quadtree for representing an image, and where there is a high degree of coherence in the composition of the image objects quadtree meshes provides great savings in storage. Relaxing the definition of gray scale quadtrees to permit some error (a region is not quartered if its pixels differ by no more than a specified amount) realizes considerable storage savings, at some loss in image fidelity. A metric is presented for determining if a gray scale image benefits from the application of an error-quadtree