An effective way to represent quadtrees

ABSTRACT

A quadtree may be represented without pointers by encoding each black node with a quaternary integer whose digits reflect successive quadrant subdivisions. We refer to the sorted array of black nodes as the “linear quadtree” and show that it introduces a saving of at least 66 percent of the computer storage required by regular quadtrees. Some algorithms using linear quadtrees are presented, namely, (i) encoding a pixel from a 2n × 2>n array (or screen) into its quaternary code; (ii) finding adjacent nodes; (iii) determining the color of a node; (iv) superposing two images. It is shown that algorithms (i)-(iii) can be executed in logarithmic time, while superposition can be carried out in linear time with respect to the total number of black nodes. The paper also shows that the dynamic capability of a quadtree can be effectively simulated.

REFERENCES

• 1: Charles R. Dyer , Azriel Rosenfeld , Hanan Samet, Region representation: boundary codes from quadtrees, Communications of the ACM, v.23 n.3, p.171-179, March 1980 [doi>10.1145/358826.358838]
• 2: Hunter, G.M. and Steiglitz, K. Operations on images using quadtrees. IEEE Trans. on Pattern Analysis and Machine Intell. 1, 2 (April 1979), 145-153.
• 3: Hunter, G.M. and Steiglitz, K. Linear transformations of pictures represented by quadtrees. Comptr. Graphics and Image Processing 10, 3 (July 1979), 289-296.
• 4: Jackins, C.L. and Tanimoto, S.L. Oct-trees and their use in representing three-dimensional objects. Comptr. Graphics and Image Processing 14, 3 (Nov. 1980), 249-270.
• 5: Jones, L. and Iyengar, S.S. Representation of a region as a forest of quad-trees. Proc. IEEE-PR1P 81 Conference Dallas, TX, IEEE Publ. 81 CH1595-8, (1981), 57-59.
• 6: Kawaguchi, E. and Endo, T. On a method of binary-picture representation and its application to data compression. IEEE Trans. on Pattern Analysis and Machine Intell. 2, 1 (Jan. 1980), 27-35.
• 7: Klinger, A. Patterns and Search Statistics, Optimizing Methods in Statistics. Rustagi, J.D. (Ed.) Academic Press, New York, 1971.
• 8: Klinger, A. and Rhodes, M.L. Organization and access of image data by areas. 1EEE Trans. on Pattern Analysis and Machine lntell. 1, 1 (Jan. 1979), 50-60.
• 9: Samet, H. An algorithm for converting rasters to quadtrees. IEEE Trans. on Pattern Analysis and Machine lntell. 3, 1 (Jan. 1981) 93-95.
• 10: Hanan Samet, Connected Component Labeling Using Quadtrees, Journal of the ACM (JACM), v.28 n.3, p.487-501, July 1981 [doi>10.1145/322261.322267]
• 11: Hanan Samet, Region representation: quadtrees from boundary codes, Communications of the ACM, v.23 n.3, p.163-170, March 1980 [doi>10.1145/358826.358836]
• 12: Srihari, S.N. Representation of three-dimensional digital images. TR-162, Comptr. Sci. Dept. State Univ. of New York at Buffalo, July 1980.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Algorithms

Keywords:
digital images, image encoding