The quadcode and its arithmetic

ABSTRACT

The quadcode is a hierarchical data structure for describing digital images. It has the following properties: (1) straightforward representation of dimension, size, and the relationship between an image and its subsets; (2) explicit description of geometric properties, such as location, distance, and adjacency; and (3) ease of conversion from and to raster representation. The quadcode has applications to computer graphics and image processing because of its ability to focus on selected subsets of the data and to allow utilization of multiple resolutions in different parts of the image. A related approach is the quadtree. Samet recently presented a thorough survey of the literature in that field [7]. Gargantini [2] and Abel and Smith [1] presented linear quadtrees and linear locational keys that are efficient labeling techniques for quadtrees. In those papers the geometric concepts of the image are discussed by using the tree as an interpretive medium, and the approaches and procedures are based on traversal of the nodes in the tree. In this paper we present the quadcode system, which is a direct description of the image, and discuss the geometric concepts in terms of the coded images themselves.

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. Graph. Image Process. 24, 1 (Oct. 1983). l-13.
• 2: 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]
• 3: Li. S.X., and Loew, M.H. Quadcodes and their application in image processing. GWU/IIST Rep. 83-15, Dept. of Electrical Engineering and Computer Science, George Washington Univ., Washington, D.C., Oct. 1983.
• 4: Li. S.X., and Loew. M.H. Boundarv chain codes from auadcode trees. In Proceedings of the IEEE 1984 Computer Vision Confertke (Annapolis, Md.. Mar.). IEEE Press, New York, 1984, pp. 178-182.
• 5: Li, S.X., and Loew, M.H. The quadcode and its application. In Proceedings of the 7th lnternationnl Conference on Pattern Recognition (Montreal, Canada, July JO-Aug. 2). IEEE Press, New York, 1984. pp. 227-229.
• 6: Shu-Xiang Li , Murray H. Loew, Adjacency detection using quadcodes, Communications of the ACM, v.30 n.7, p.627-631, July 1987 [doi>10.1145/28569.28574]
• 7: 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]

INDEX TERMS

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

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)
          Subjects: Exact coding**
      I.4.6 Segmentation
          Subjects: Pixel classification; Region growing, partitioning

General Terms:
Algorithms, Performance, Theory