The Relationship Between Wavelets and Quadtrees for Global Grids

Robert Raskin

Jet Propulsion Lab, 300-320
Pasadena, CA 91109

Email: rob.raskin@jpl.nasa.gov


Quadtrees and wavelets have in common the ability to represent and store data in hierarchical form. The connection between these two representations in the context of global grids is explored in this presentation. Wavelets are ordinarily thought of as a spectral representation and quadtrees as a data structure. However, wavelets and quadtrees can be made to have identical reconstruction algorithms. For this case, the Haar wavelet is used and the quadtree stores only differences from the parent value at any given level; the reconstruction involves summing the values of each node from root to terminating leaf. For global grid schemes that use triangular decomposition, this would enable applications to control the resolution at which retrieval and analysis operations are performed. This feature may be of advantage in massively large, high resolution, global datasets. The isomorphism between wavelets and quadtrees suggests that a quadtree can be further generalized in the same way that the Haar wavelet is generalized to other "mother" wavelets. These other wavelets may represent a closer fit to the variations inherent in the data, as an appropriate wavelet choice can capture most of the spatial variations at levels closer to the root of the tree. Also discussed will be some extensions to the concept of wavelets that have been proposed for the sphere and how these might be represented.