Abstract
Region representation is an important issue in image processing, cartography, and computer graphics. A wide number of representations is currently in use. Recently, there has been much interest in a hierarchical data structure termed the quadtree. It is compact and depending on the nature of the region saves space as well as time and also facilitates operations such as search. In this section we give a brief overview of the quadtree data structure and related research results.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Rutovitz: “Data structures for operations on digital images”, in Pictorial Pattern Recognition, ed. by G. C. Cheng et al. (Thompson Book CO., Washington, DC, 1968), pp. 105–133
H. Freeman: Computer processing of line-drawing images. Computing Surveys 6, 57–97 (1974)
D. H. Ballard: Strip trees: a hierarchical representation for curves, Comm. ACM 24 310–321 (1981)
H. Blum: “A transformation for extracting new descriptors of shape”, in Models for the Perception of Speech and Visual Form, ed. by W. Wathen-Dunn (M.I.T. Press, Cambridge, MA, 1967), pp. 362–380
J. L. Pfaltz, A. Rosenfeld: Computer representation of planar regions by their skeletons, Comm. ACM 10, 119–122 (1967)
R. A. Finkel, J. L. Bentley: Quad trees: a data structure for retrieval on composite keys. Acta Informatica 4, 1–9 (1974)
H. Samet: Deletion in two-dimensional quad trees, Comm. ACM 23 703–710 (1980)
D. T. Lee, C. K. Wong: Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees, Acta Informatica 9, 23–29 (1977)
Jo L. Bentley: Multidimensional binary search trees used for associative searching, Commo ACM 18, 509–517 (1975)
C. M. Eastman: Representations for space planning. Comm. ACM 13, 242–250 (1970)
J. E. Warnock: “A Hidden Surface Algorithm for Computer Generated Half Tone Pictures”, Computer Science Department TR 4–15, University of Utah (1969)
I. E. Sutherland, R. F. Sproull, R. A. Schumaeker: A characterization of ten hidden-surface algorithms, Computing Surveys 6 1–55 (1974)
W. M. Newman, R. F. Sproull: Principles of Interactive Computer Graphics, 2nd ed. (McGraw-Hill, New York, 1971)
A. Klinger: “Patterns and search statistics”, in Optimizing Methods in Statistics, ed. by J. S. Rustagi (Academic Press, New York, 1972) pp. 303–339
A. Klinger, C. R. Dyer: Experiments in picture representation using regular decomposition. Computer Graphics Image Processing 14, 68–105 (1975)
S. L. Tanimoto, T. Pavlidis: A hierarchical data structure for image processing, Computer Graphics Image Processing 4, 104–119 (1976)
S. L. Tanimoto: Pictorial feature distortion in a pyramid. Computer Graphics Image Processing 5, 333–352 (1976)
E. M. Riseman, M. A. Arbib: Computational techniques in the visual segmentation of static scenes, Computer Graphics Image Processing 6, 221–276 (1976)
A. Klinger, M. L. Rhodes: Organization and access of image data by areas, IEEE Trans. Pattern Analysis Machine Intelligence PAMI-1, 50–60 (1979)
N. Alexandridis, A. Klinger: Picture decomposition, tree data-structures, and identifying directional symmetries as node combinations. Computer Graphics Image Processing 8, 43–77 (1978)
G. M. Hunter: “Efficient Computation and Data Structures for Graphics”, Ph.D. dissertation. Department of Electrical Engineering and Computer Science, Princeton University (1978)
G. M. Hunter, K. Steiglitz: Operations on images using quad trees, IEEE Trans. Pattern Analysis Machine Intelligence PAMI-1, 145–153 (1979)
M. Shneier: Calculations of geometric properties using quadtrees, Computer Graphics Image Processing 16, 296–302 (1981)
G. M. Hunter, K. Steiglitz: Linear transformation of pictures represented by quad trees, Computer Graphics Image Processing 10, 289–296 (1979)
D. R. Reddy, S. Rubin: “Representation of Three-Dimensional Objects”, Department of Computer Science Technical Report 78–113, Carnegie-Mellon University (1978)
C. L. Jackins, S. L. Tanimoto: Oct-trees and their use in representing three-dimensional objects. Computer Graphics Image Processing 14, 249–270 (1980)
D. J. R. Meagher: “Octree Encoding: a New Technique for the Representation, Manipulation, and Display of Arbitrary 3-D Objects by Computer”, TR 80–111, Rensselaer Polytechnic Institute (1980)
S. N. Srihari, M. Yau: “A Hierarchical Data Structure for Multidimensional Digital Images”, Department of Computer Science Technical Report 185, State University of New York at Buffalo (1981)
H. Samet: Region representation: quadtrees from binary arrays. Computer Graphics Image Processing 13, 88–93 (1980)
H. Samet: An algorithm for converting rasters to quadtrees, IEEE Trans. Pattern Analysis Machine Intelligence PAMI-3, 93–95 (1981)
H. Samet: “Algorithms for the Conversion of Quadtrees to Rasters”, Computer Graphics Image Processing, to appear
H. Samet: Region representation: quadtrees from boundary codes. Comm. ACM 23, 163–170 (1980)
C. R. Dyer, A. Rosenfeld, H. Samet: Region representation: boundary codes from quadtrees, Comm. ACM 23, 171–179 (1980)
H. Samet: Connected component labeling using quadtrees, J. ACM 28, 487–501 (1981).
H. Samet: Computing perimeters of images represented by quadtrees, IEEE Trans. Pattern Analysis Machine Intelligence PAMI-3, 683–687 (1981)
C. R. Dyer: Computing the Euler number of an image from its quadtree, Computer Graphics image Processing 13, 270–276 (1980)
H. Samet: Distance transform for images represented by quadtrees, IEEE Trans. Pattern Analysis Machine Intelligence PAMI-4, 298–303 (1982)
M. Shneier: Path-length distances for quadtrees, Information Sciénces 23, 49–67 (1981)
S. Ranade, A. Rosenfeld, H. Samet: Shape approximation using quadtrees, Pattern Recognition 15, 31–40 (1982)
S. Ranade: Use of quadtrees for edge enhancement, IEEE Trans. Systems, Man, Cybernetics SMC-11, 370–373 (1981)
S. Ranade, A. Rosenfeld, J. M. S. Prewitt: “Use of Quadtrees for Image Segmentation”, Computer Science TR-878, University of Maryland (1980)
A. Y. Wu, T. H. Hong, A. Rosenfeld: Threshold selection using quadtrees, IEEE Trans. Pattern Analysis Machine Intelligence PAMI-4, 90–94 (1982)
S. Ranade M. Shneier: Using quadtrees to smooth images, IEEE Trans. Systems, Man, Cybernetics SMC-11, 373–376 (1981)
H. Samet: Neighbor finding techniques for images represented by quadtrees, Computer Graphics Image Processing 15, 37–57 (1982)
A. Rosenfeld, A. C. Kak: Digital Picture Processing (Academic Press, New York, 1976)
H. Samet: A quadtree medial axis transform. Comm. ACM, to appear.
C. Jackins, S. L. Tanimoto: “Quad-trees, Oct-trees, and K-trees: a Generalized Approach to Recursive Decomposition of Euclidean Space”, IEEE Trans. Pattern Analysis Machine Intelligence, to appear.
C. R. Dyer: The space efficiency of quadtrees. Computer Graphics Image Processing 19, 335–348 (1982)
W. I. Grosky, R. Jain: “Optimal Quadtrees for Image Segments”, IEEE Trans. Pattern Analysis Machine Intelligence PAMI-5, 1983, 77–83
M. Li, W. I. Grosky, R. Jain: Normalized quadtrees with respect to translations, Computer Graphics Image Processing 20, 72–81 (1982)
L. Jones, S. S. Iyengar: “Representation of regions as a forest of quadtrees”, in Proc. Pattern Recognition and Image Processing Conf., Dallas, TX, 1981, pp. 57–59
I. Gargantini: An effective way to represent quadrees, Comm. ACM 25, 905–910 (1982)
E. Kawaguchi, T. Endo, J. Matsunaga: “DF-Expression Viewed from Digital Picture Processing”, Department of Information Systems, Kyushu University (1982)
L. Gibson, D. Lucas: “Spatial data processing using generalized balanced ternary”, in Proc. Pattern Recognition and Image Processing Conf., Los Vegas, NV, 1982, pp. 566–571
N. Ahuja: “Approaches to recursive image decomposition”, in Proc. Pattern Recognition and Image Processing Conf., Dallas, TX, 1981, pp. 75–80
H. Samet, R. E. Webber: “On Encoding Boundaries with Quadtrees”, Computer Science TR-1162, University of Maryland (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1984 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Samet, H. (1984). A Tutorial on Quadtree Research. In: Rosenfeld, A. (eds) Multiresolution Image Processing and Analysis. Springer Series in Information Sciences, vol 12. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-51590-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-51590-3_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-51592-7
Online ISBN: 978-3-642-51590-3
eBook Packages: Springer Book Archive