A quadtree medial axis transform

ABSTRACT

As printed

Quadtree skeletons are exact representations of the image and are used because they are observed to yield space efficiently and a decreased sensitivity to shifts in contrast with the quadtree. The QMAT can be used as the underlying representation when solving most problems that can be solved by using a quadtree. An algorithm is presented for the computation of the QMAT of a given quadtree by only examining each BLACK node's adjacent and abutting neighbors.

Corrected Abstract (published as corrigendum in CACM 27, 2 (February 1984) p. 151)

The skeletal and medial axis transform concepts used in traditional image processing representations are adapted to the quadtree representation. The result is the definition of of a new data structure termed the Quadtree Medial Axis Transform (QMAT). A QMAT results in a partition of the image into a set of nondisjoint squares having sides whose lengths are sums of powers of 2 rather than, as is the case with quadtrees, a set of disjoint squares having sides of lengths which are powers of 2. The motivation is not to study skeletons for the usual purpose of obtainings approximations of the image. Instead, quadtree skeletons are exact representations of the image and are used because they are observed to yield space efficiency and a decreased sensitvity to shifts in contrast with the quadtree. The QMAT can be used as the underlying representation when solving most problems that can be solved by using a quadtree. An algorithm is presented for the computation of the QMAT of a given quadtree by only examining each BLACK node's adjacent and abutting neighbors. Analysis of the algorithm reveals an average execution time proportional to the complexity of the image, i.e., the number of BLACK blocks.

REFERENCES

• 1: Blum, H. A transformation for extracting new descriptors of shape. In Wathen-Dunn. W., ed.. Models for the Perception of Speech and Visual Form. M.I.T. Press, Cambridge. Massachusetts, 1967. pp. 362-380.
• 2: Duda, R.O. and Hart, P.E. Pattern Classification and Scene Analysis, Wiley-lnterscience, New York, 1973.
• 3: Dyer, C.R. Computing the Euler number of an image from its quadtree, Comput. Gr. Image Process. 13, 3 (1981). 270-276.
• 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: Gregory Michael Hunter, Efficient computation and data structures for graphics., 1978
• 6: Hunter, G.M. and Steiglitz. K. Operations on images using quadtrees, IEEE Trans. Pattern Anal. Machine lntell. 1, 2 (1979}, 145-153.
• 7: Hunter, G.M., and Steiglitz, K. Linear transformation of pictures represented by quadtrees, Comput. Gr. Image Process. 10, 3 (1979), 289- 296.
• 8: Jackins, C.L. and Tanimoto, S.L. Octrees and their use in representing three-dimensional objects, Comput. Gr. Image Process. 14, 3 (1980), 249-270.
• 9: Klinger, A. Patterns and search statistics. In Optimizing Methods in Statistics, J. S. Rustagi, ed., Academic Press, New York, 1971.
• 10: Klinger, A. and Dyer, C.R. Experiments in picture representation" using regular decomposition. Comput. Gr. Image Process. 5, I (1976), 68-105.
• 11: Meagher, D. Geometric modeling using octree encoding, Comput. Gr. Image Process. 19, 2 (1982), 129-147.
• 12: Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
• 13: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 14: John L. Pfaltz , Azriel Rosenfeld, Computer representation of planar regions by their skeletons, Communications of the ACM, v.10 n.2, p.119-122, Feb. 1967 [doi>10.1145/363067.363120]
• 15: Azriel Rosenfeld , Avinash C. Kak, Digital Picture Processing, Academic Press, Inc., Orlando, FL, 1982
• 16: Rutovitz, D. Data structures for operations on digital images. In Pictorial Pattern Recognition. G. C. Cheng et al., eds., Thompson Book Co., Washington, DC, 1968, 105-133.
• 17: 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]
• 18: Samet, H. Computing perimeters of images represented by quadtrees, IEEE Trans. Pattern Anal. Machine lntell. 3, 6 1981, 683-687.
• 19: 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]
• 20: Samet, H. An algorithm for converting rasters to quadtrees, IEEE Trans. Pattern Anal. Machine Intell. 3, (1981), 93-95.
• 21: Samet, H. Region representation: quadtrees from binary arrays, Cornput. Gr. Image Process. 13, 1980.88-93.
• 22: Samet, H. Algorithms for the conversion of quadtrees to rasters, Computer Science TR 979, University of Maryland, College Park, Maryland, November 1980.
• 23: Samet, H. Distance transform for images represented by quadtrees, IEEE Trans. Pattern Anal. Machine lntell. 4, 3 (1982), 298-303.
• 24: Samet, H. A quadtree medial axis transform, Computer Science TR- 803. University of Maryland, College Park, Maryland, August 1979.
• 25: Samet. H. Reconstruction of quadtrees from quadtree medial axis transforms, Computer Science TR-1224, University of Maryland College Park, Maryland, October 1982.
• 26: Shneier. M. Path-length distances for quadtrees, Inf. Sci. 23, 1 1981, 49-67.
• 27: Shneier, M. Calculations of geometricproperties using quadtrees, Comp. Gr. Image Process. 16, 3 (1981), 296-302.
• 28: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• 29: Warnock, J.E. A hidden surface algorithm for computer generated halftone pictures, Computer Science Department, TR 4-15, University of Utah, June 1969.
• 30: Yau, M. and Srihari, S.N. Recursive generation of hierarchical data structures for multidimensional digital images, Proceedings IEEE PRIP 81, Dallas, Texas, 1981, 42-44.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms; Shape; Motion
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems; Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)
          Subjects: Exact coding**
      I.4.7 Feature Measurement
          Subjects: Size and shape

General Terms:
Algorithms

Keywords:
medial axis transforms, quadtrees, shape, size, skeletons