Data structures for quadtree approximation and compression

ABSTRACT

A number of data structures for representing images by quadtrees without pointers are discussed. The image is treated as a collection of leaf nodes. Each leaf node is represented by use of a locational code corresponding to a sequence of directional codes that locate the leaf along a path from the root of the tree. Somewhat related is the concept of a forest which is a representation that consists of a collection of maximal blocks. It is reviewed and refined to enable the representation of a quadtree as a sequence of approximations. In essence, all BLACK and WHITE nodes are said to be of type GB and GW, respectively. GRAY nodes are of type GB if at least two of their sons are of type GB; otherwise, they are of type GW. Sequences of approximations using various combinations of locational codes of GB and GW nodes are proposed and shown to be superior to approximation methods based on truncation of nodes below a certain level in the tree. These approximations have two important properties. First, they are progressive in the sense that as more of the image is transmitted, the receiving device can construct a better approximation (contrast with facsimile methods which transmit the image one line at a time). Second, they are proved to lead to compression in the sense that they never require more than MIN(B, W) nodes where B and W correspond to the number of BLACK and WHITE nodes in the original quadtree. Algorithms are given for constructing the approximation sequences as well as decoding them to rebuild the original quadtree.

REFERENCES

• 1: Abel, D.J.. and Smith, J.L. A data structure and algorithm based on a linear key for a rectangle retrieval problem. Comput. Vision, Graphics, and tnrage Process. 24, 1 (Oct. 1983). 1-13.
• 2: Burton, F.W.. and Kollias, J.G. Comment on the explicit quadtree as a structure for computer graphics. Comput. 1. 26. 2 (May 1983). 188.
• 3: Cook, B.C. The structural and algorithmic basis of a geographic data base. In Proceedings of fhe first International Advanced Study Symposium on Topological Data Structures for Geographic Information Systems. G. Dutton. Ed., Harvard Papers on Geographic Information Systems, 1978.
• 4: 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]
• 5: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 6: Gregory Michael Hunter, Efficient computation and data structures for graphics., 1978
• 7: Hunter, G.M.. and Steiglitz. K. Operations on images using quad trees. IEEE Trans. Patfern Anal. Machine Intell. I, 2 (Apr. 1979), 145- 153.
• 8: Hunter, G.M., and Steiglitz. K. Linear transformation of pictures represented by quad trees. Comput. Graphics and Image Process. IO, 3 (July 1979). 289-296.
• 9: Jackins. C.L., and Tanimoto, S.L. Ott-trees and their use in representing three-dimensional objects. Comput. Graphics and Image Process. 14, 3 (Nov. 1980), 249-270.
• 10: Jones, L., and Iyengar, S.S. Representation of regions as a forest of quadtrees. In Proceedings of the IEEE Conference on Pattern Recognition and Image Processing, Dallas, Tex., 1981, pp. 57-59.
• 11: Kawaguchi, E., and Endo. T. On a method of binary picture representation and its application to data compression. IEEE Trans. Pattern Anal. Machine Intell. 2, 1 (Jan. 1980). 27-35.
• 12: Klinger, A. Patterns and search statistics. In Optimizing Methods in Stafistics. J.S. Rustagi, Ed., Academic Press, NY, 1971. pp. 303-337.
• 13: Klinger. A., and Rhodes, M.L. Organization and access of image data by areas. IEEE Trans. Paftern Anal. Machine Intell. 1. 1 (Jan. 1979). 50-60.
• 14: Knowlton, K. Progressive transmission of grey-scale and binary pictures by simple, efficient, and lossless encoding schemes. In Proceedings of the IEEE 68, 7 (July 19801, pp. 885-896.
• 15: Meagher, D. Geometric modeling using octree encoding. Compvf. Graphics and image Process. 19, 2 (June 1982), 129-147.
• 16: Morton, G.M. A computer oriented geodetic data base and a new technique in file sequencing, IBM Canada, 1966.
• 17: Oliver. M.A.. and Wiseman, N.E. Operations on quadtree-encoded images, Conrput. J. 26, 1 (Feb. 1983). 83-91.
• 18: Ranade. S., Rosenfeld. A., and Sam&, H. Shape approximation using quadtrees. Paftern Recognifion 15, 1 (1982), 31-40.
• 19: 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]
• 20: Samet. H. An algorithm for converting rasters to quadtrees. IEEE Trans. Pattern Anal. Machine Intell. 3, 1 (Jan. 1981). 93-95.
• 21: 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]
• 22: Sam&, H. Neighbor finding techniques for images represented by quadtrees. Comput. Graphics and Image Process. 18, 1 (Jan. 1982), 37-57.
• 23: Hanan Samet, A quadtree medial axis transform, Communications of the ACM, v.26 n.9, p.680-693, Sept. 1983 [doi>10.1145/358172.358409]
• 24: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 25: Sam&. H.. Rosenfeld, A., Shaffer. C., and Webber, R.E. Quadtree region representation in cartography: Experimental results. IEEE Trans. Syst., Man, Cybern. 13, 6 (Nov./Dee. 1983). 1148-1154.
• 26: Sloan, K.R.. Jr., and Tanimoto, S.L. Progressive refinement of raster images. IEEE Trans. Comput. 28, 11 (Nov. 1979), 871-874.
• 27: Tanimoto, S., and Pavlidis, T. A hierarchical data structure for picture processing. Comput. Graphics and Image Process. 4. 2 (June 1975). 104-119.
• 28: Weber, W. Three types of map data structures, their ANDs and NOTs, and a possible OR. In Proceedings of the First International Advartced Study Symposium on Topological Dafa Structures for Geographic hformtion Systems, G. Dutton. Ed., Harvard Papers on Geographic Information Systems, 1978.
• 29: Woodwark, J.R. The explicit quadtree as a structure for computer graphics. Comput. 1. 25, 2 (May 1982). 235-238.
• 30: Mann-May Yau , Sargur N. Srihari, A hierarchical data structure for multidimensional digital images, Communications of the ACM, v.26 n.7, p.504-515, July 1983 [doi>10.1145/358150.358158]

INDEX TERMS

Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)
          Subjects: Exact coding**; Approximate methods

General Terms:
Algorithms, Theory