Cyclic Interlaced Quadtree Algorithms for Quincunx Multiresolution
✍ Scribed by D.J. Hebert
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 317 KB
- Volume
- 27
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
Recent advances in wavelet theory and in finite element computations draw attention to a well-known, simple, and computationally efficient triangulation method. We take a new look at this triangulation, which is obtained by repeated symmetric bisection, starting with a half square. The cells form the leaves of a binary tree and the nodes of a directed graph consisting of a single simple cycle. Computational speed is facilitated by the binary and quad-digit expression of triangle vertices, which reduce all vertex calculations to simple integer and logical operations. The leaf cycle interlaces a pair of quadtrees whose orientations differ by r4. Detailed analysis leads to algorithms which exploit the structure and computational efficiencies in calculations such as pyramid algorithms for image processing with non-separable wavelets.