Region representation: boundary codes from quadtrees

ABSTRACT

There has been recent interest in the use of quadtrees to represent regions in an image. It thus becomes desirable to develop efficient methods of conversion between quadtrees and other types of region representations. This paper presents an algorithm for converting from quadtrees to a simple class of boundary codes. The algorithm is shown to have an execution time proportional to the perimeter of the region.

REFERENCES

• 1: Alexandridis, N., and Klinger, A. Picture decomposition, tree data-structures, and identifying directional symmetries as node combinations. Comptr. Graphics and Image Processing 8 (1978), 43- 77.
• 2: Blum, H. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Form, W. Wathen-Dunn, Ed., M.I.T. Press, Cambridge, Mass., 1967, pp. 362- 380.
• 3: Finkel, R.A., and Bentley, J.L. Quadtrees: A data structure for retrieval on composite keys. Acta Informatica 4 (1974), 1-9.
• 4: Herbert Freeman, Computer Processing of Line-Drawing Images, ACM Computing Surveys (CSUR), v.6 n.1, p.57-97, March 1974 [doi>10.1145/356625.356627]
• 5: Steven L. Horowitz , Theodosios Pavlidis, Picture Segmentation by a Tree Traversal Algorithm, Journal of the ACM (JACM), v.23 n.2, p.368-388, April 1976 [doi>10.1145/321941.321956]
• 6: Gregory Michael Hunter, Efficient computation and data structures for graphics., 1978
• 7: Hunter, G.M., and Steiglitz, K. Operations on images using quadtrees. 1EEE Trans. on Pattern Analysis and Machine Intell. 1 (1979), 145-153.
• 8: Hunter, G.M., and Steiglitz, K. Linear transformation of pictures represented by quadtrees. Comptr. Graphics and Image Processing 10 (1979), 289-296.
• 9: Klinger, A., and Dyer, C.R. Experiments in picture representation using regular decomposition. Comptr. Graphics and Image Processing 5 (1976), 68-105.
• 10: Klinger, A., and Rhodes, M.L. Organization and access of image data by areas. IEEE Trans. on Pattern Analysis and Machine lntell. 1 (1979), 50-60.
• 11: 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]
• 12: 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]
• 13: Riseman, E.M., and Arbib, M.A. Computational techniques in the visual segmentation of static scenes. Comptr. Graphics and Image Processing 6 (1977), 221-276.
• 14: Azriel Rosenfeld , John L. Pfaltz, Sequential Operations in Digital Picture Processing, Journal of the ACM (JACM), v.13 n.4, p.471-494, Oct. 1966 [doi>10.1145/321356.321357]
• 15: Rutovitz, D. Data structures for operations on digital images. In Pictorial Pattern Recognition, G.C. Cheng et al., Eds., Thompson Book Co., Washington, D.C., 1968, pp. 105-133.
• 16: 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]
• 17: Samet, H. Computing perimeters of images represented by quadtrees. Comptr. Sci. TR-755, Univ. of Maryland, College Park, Md., April 1979.
• 18: Samet, H. Connected component labeling using quadtrees. Comptr. Sci. TR-756, Univ. of Maryland, College Park, Md., April 1979.
• 19: Tanimoto, S.L. Pictorial feature distortion in a pyramid. Comptr. Graphics and Image Processing 5 (1976), 333-352.
• 20: Tanimoto, S.L., and Pavlidis, T. A hierarchical data structure for picture processing. Comptr. Graphics and Image Processing 4 (1975), 104-119.

INDEX TERMS

Keywords:
borders, chain codes, data structures, quadtrees, regions