article

Free access

Data structures for quadtree approximation and compression

Author:

Hanan SametAuthors Info & Claims

Communications of the ACM, Volume 28, Issue 9

Pages 973 - 993

https://doi.org/10.1145/4284.4290

Published: 01 September 1985 Publication History

PDF eReader

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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[4]

Dyer, C.R. Rosenfeld. A. and Sam&, H. Region representation: Boundary codes from quadtrees. Commun. ACM 23, 3 (Mar. 1980), 171-179.

Digital Library

Google Scholar

[5]

Gargantini. 1. An effective way to represent quadtrees. Commun. ACM 25,lZ (Dec. 1982). 905-910.

Digital Library

Google Scholar

[6]

Hunter, GM. Efficient computation and data structures for graphics. Ph.D. dissertation, Dept. of Electrical Engineering and Computer Science, Princeton Univ., N.J. 1978.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[12]

Klinger, A. Patterns and search statistics. In Optimizing Methods in Stafistics. J.S. Rustagi, Ed., Academic Press, NY, 1971. pp. 303-337.

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[15]

Meagher, D. Geometric modeling using octree encoding. Compvf. Graphics and image Process. 19, 2 (June 1982), 129-147.

Google Scholar

[16]

Morton, G.M. A computer oriented geodetic data base and a new technique in file sequencing, IBM Canada, 1966.

Google Scholar

[17]

Oliver. M.A. and Wiseman, N.E. Operations on quadtree-encoded images, Conrput. J. 26, 1 (Feb. 1983). 83-91.

Google Scholar

[18]

Ranade. S., Rosenfeld. A., and Sam&, H. Shape approximation using quadtrees. Paftern Recognifion 15, 1 (1982), 31-40.

Google Scholar

[19]

Samet, H. Region representation: Quadtrees from boundary codes. Conmur~. ACM 23, 3 (Mar. 19801, 163-170.

Digital Library

Google Scholar

[20]

Samet. H. An algorithm for converting rasters to quadtrees. IEEE Trans. Pattern Anal. Machine Intell. 3, 1 (Jan. 1981). 93-95.

Google Scholar

[21]

Sam&, H. Connected component labeling using quadtrees. I, ACM 28,3 (July1981) 487-501.

Digital Library

Google Scholar

[22]

Sam&, H. Neighbor finding techniques for images represented by quadtrees. Comput. Graphics and Image Process. 18, 1 (Jan. 1982), 37-57.

Google Scholar

[23]

Samet. H. A quadtree medial axis transform. Commun. ACM 26, 9 (Sept. 1983). 680-693.

Digital Library

Google Scholar

[24]

Samet, H. The quadtree and related hierarchical data structures. ACM Comput. Sure. 162 (June 1984), 187-260.

Digital Library

Google Scholar

[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.

Google Scholar

[26]

Sloan, K.R. Jr., and Tanimoto, S.L. Progressive refinement of raster images. IEEE Trans. Comput. 28, 11 (Nov. 1979), 871-874.

Google Scholar

[27]

Tanimoto, S., and Pavlidis, T. A hierarchical data structure for picture processing. Comput. Graphics and Image Process. 4. 2 (June 1975). 104-119.

Crossref

Google Scholar

[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.

Google Scholar

[29]

Woodwark, J.R. The explicit quadtree as a structure for computer graphics. Comput. 1. 25, 2 (May 1982). 235-238.

Google Scholar

[30]

Yau. M. and Srihari. S.N. A hierarchical data structure for multidimensional digital images. Commun. ACM 26, 7 (July 1983), 504-515.

Digital Library

Google Scholar

Cited By

View all

Erb W(2023)Graph Wedgelets: Adaptive Data Compression on Graphs Based on Binary Wedge Partitioning Trees and Geometric WaveletsIEEE Transactions on Signal and Information Processing over Networks10.1109/TSIPN.2023.32408999(24-34)Online publication date: 2023
https://doi.org/10.1109/TSIPN.2023.3240899
Ondov BSamet H(2023)An efficient region expansion algorithm for regular triangulated meshesPattern Recognition Letters10.1016/j.patrec.2023.02.014168:C(1-7)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.patrec.2023.02.014
Silva-Coira FParamá Jde Bernardo GSeco D(2021)Space-efficient representations of raster time seriesInformation Sciences: an International Journal10.1016/j.ins.2021.03.035566:C(300-325)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1016/j.ins.2021.03.035
Show More Cited By

Recommendations

Quadtree representation and compression of spatial data
Transactions on rough sets XIII

Granular computing is closely related to the depth of the detail of information with which we are presented, or choose to process. In spatial cognition and image processing such detail is given by the resolution of a picture. The quadtree representation ...
Quadtree based JBIG compression
DCC '95: Proceedings of the Conference on Data Compression

A JBIG compliant, quadtree based, lossless image compression algorithm is described. In terms of the number of arithmetic coding operations required to code an image, this algorithm is significantly faster than previous JBIG algorithm variations. Based ...
Lossless Data Compression: Data compression, Algorithm, Lossy compression, Bit rate, ZIP (file format), Unix, Gzip, Portable Network Graphics, Graphics Interchange Format, Tagged Image File Format

Reviews

Reviewer: Sally L. Harris

This paper presents a thorough explanation of many pointerless quadtree representations for black and white images. The pointerless approach is chosen because pointers cause an inherently high overhead. A quadtree is constructed by repeatedly dividing an image into four quadrants, then into subquadrants, until blocks of a single value (gray level) are obtained. Terminal nodes are those blocks which require no further subdivision. Terminal nodes can be either black or white. Parental (gray) nodes are called black if at least two sons are black; otherwise they are white. In the pointerless representation, each terminal node is represented by use of a locational code corresponding to a sequence of directions that indicate a path from the root. The smallest terminal nodes are at level k and are of size (2 2* 2* k×2 2* 2* k). The root node is at level 0. An approximation is obtained by representing the tree only to the required level, which corresponds to the clarity of the resulting image. The concept of a forest is introduced as a method of approximation. A forest is a collection of black parental nodes and black terminal nodes having no black parent. This is referred to as the “minimal set of maximal blocks” of a certain node type. Two distinct advantages of this method over facsimile encoding are that this is a progressive image representation (i.e., as more of an image is transmitted, clarity increases), and that this method never requires more than MIN(black,white) nodes to represent the image. Even further compression is obtained by alternating between black and white forests. After a black recording is obtained, the next recording will have fewer white than black maximal blocks. This paper is quite thorough, but somewhat lacking in clarity and simplicity. Definitions should have been emphasized. Both the Abstract and Introduction are not well organized. However, it is very helpful that the author uses a single example throughout much of the paper.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

Communications of the ACM Volume 28, Issue 9

Sept. 1985

118 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/4284

Editor:
Peter J. Denning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1985

Published in CACM Volume 28, Issue 9

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
5,035
Total Downloads

Downloads (Last 12 months)197
Downloads (Last 6 weeks)26

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Erb W(2023)Graph Wedgelets: Adaptive Data Compression on Graphs Based on Binary Wedge Partitioning Trees and Geometric WaveletsIEEE Transactions on Signal and Information Processing over Networks10.1109/TSIPN.2023.32408999(24-34)Online publication date: 2023
https://doi.org/10.1109/TSIPN.2023.3240899
Ondov BSamet H(2023)An efficient region expansion algorithm for regular triangulated meshesPattern Recognition Letters10.1016/j.patrec.2023.02.014168:C(1-7)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.patrec.2023.02.014
Silva-Coira FParamá Jde Bernardo GSeco D(2021)Space-efficient representations of raster time seriesInformation Sciences: an International Journal10.1016/j.ins.2021.03.035566:C(300-325)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1016/j.ins.2021.03.035
Li HKwong SChen CJia YCong R(2019)Superpixel Segmentation Based on Square-Wise Asymmetric Partition and Structural ApproximationIEEE Transactions on Multimedia10.1109/TMM.2019.290704721:10(2625-2637)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1109/TMM.2019.2907047
Liang HZhao SChen CSarem M(2017)The NAMlet transformSignal Processing10.1016/j.sigpro.2017.01.018137:C(251-263)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1016/j.sigpro.2017.01.018
Ladra SParam JSilva-Coira F(2017)Scalable and queryable compressed storage structure for raster dataInformation Systems10.1016/j.is.2017.10.00772:C(179-204)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1016/j.is.2017.10.007
Scandolo LBauszat PEisemann EGomes APurgathofer WJorge JLin M(2016)Compressed multiresolution hierarchies for high-quality precomputed shadowsProceedings of the 37th Annual Conference of the European Association for Computer Graphics10.5555/3058909.3058953(331-340)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3058909.3058953
Scandolo LBauszat PEisemann E(2016)Compressed Multiresolution Hierarchies for High‐Quality Precomputed ShadowsComputer Graphics Forum10.1111/cgf.1283535:2(331-340)Online publication date: 27-May-2016
https://doi.org/10.1111/cgf.12835
Yin QQin LLiu XZha Y(2014)Incremental Construction of Generalized Voronoi Diagrams on Pointerless QuadtreesMathematical Problems in Engineering10.1155/2014/4567392014(1-14)Online publication date: 2014
https://doi.org/10.1155/2014/456739
Wang CWu SChan YChang R(2013)Quadtree and statistical model-based lossless binary image compression methodThe Imaging Science Journal10.1179/136821905X4392753:2(95-103)Online publication date: 18-Jul-2013
https://doi.org/10.1179/136821905X43927
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Quadtree representation and compression of spatial data

Quadtree based JBIG compression

Lossless Data Compression: Data compression, Algorithm, Lossy compression, Bit rate, ZIP (file format), Unix, Gzip, Portable Network Graphics, Graphics Interchange Format, Tagged Image File Format

Reviews

Access critical reviews of Computing literature here