[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article
Free access

A quadtree medial axis transform

Published: 01 September 1983 Publication History

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.

Supplementary Material

CORRIGENDA (p151-samet.pdf)
A Corrigenda for this article was issued by the authors for this article in Communications of the ACM volume 27, issue 2 (February 1984), page 151.

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]
Dyer. C.R. Rosenfeld, A., and Samet, H. Region representation: Boundary codes from quadtrees, Commun. ACM 23, 3 (March 1980), 171-179.
[5]
Hunter. G.M. Efficient computation and data structures for graphics, Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Princeton University. Princeton, New lersey, 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]
Naur, P. (ed.), Revised report on the algorithmic language ALGOL 60, Commun. ACM, (May 1960), 299-314.
[13]
Newman, W.M. and Sproull, R.F. Principles oflnteractive Computer Graphics, 2nd ed., McGraw-Hill, New York, 1971.
[14]
Pfaltz. J.L. and Rosenfeld, A. Computer representation of planar regions by their skeletons, Commun. ACM 10, 2 (February 1967), 119- 122.
[15]
Rosenfeld, A. and Kak, A.C. Digital Picture Processing, Academic Press, New York, 1976.
[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]
Samet, H. Region representation: Quadtrees from boundary codes, Commun. ACM, 23.2 (March 1980), 163-170.
[18]
Samet, H. Computing perimeters of images represented by quadtrees, IEEE Trans. Pattern Anal. Machine lntell. 3, 6 1981, 683-687.
[19]
Samet, H. Connected component labeling using quadtrees, J. ACM 28, (July 1981), 487-501.
[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]
Sutherland, I.E., Sproull, R.F., and Schumaker, R.A. A characterization of ten hidden surface algorithms, ACM Comput. Surv. 6, 1 (1974), 1-55.
[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.

Cited By

View all
  • (2024)Safety-Aware Route Navigation: Driving with Less Sun GlareProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3691225(497-500)Online publication date: 29-Oct-2024
  • (2024)On Efficient Shortest Path Computation on Terrain Surface: A Direction-Oriented ApproachIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336314736:8(4129-4143)Online publication date: 1-Aug-2024
  • (2023)Metric Indexing for the Earth Mover's DistanceProceedings of the 2nd ACM SIGSPATIAL International Workshop on Searching and Mining Large Collections of Geospatial Data10.1145/3615890.3628531(1-8)Online publication date: 13-Nov-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM
Communications of the ACM  Volume 26, Issue 9
Sept. 1983
76 pages
ISSN:0001-0782
EISSN:1557-7317
DOI:10.1145/358172
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 1983
Published in CACM Volume 26, Issue 9

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. medial axis transforms
  2. quadtrees
  3. shape
  4. size
  5. skeletons

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)93
  • Downloads (Last 6 weeks)10
Reflects downloads up to 13 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Safety-Aware Route Navigation: Driving with Less Sun GlareProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3691225(497-500)Online publication date: 29-Oct-2024
  • (2024)On Efficient Shortest Path Computation on Terrain Surface: A Direction-Oriented ApproachIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336314736:8(4129-4143)Online publication date: 1-Aug-2024
  • (2023)Metric Indexing for the Earth Mover's DistanceProceedings of the 2nd ACM SIGSPATIAL International Workshop on Searching and Mining Large Collections of Geospatial Data10.1145/3615890.3628531(1-8)Online publication date: 13-Nov-2023
  • (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
  • (2021)TrajDistLearnProceedings of the 14th ACM SIGSPATIAL International Workshop on Computational Transportation Science10.1145/3486629.3490693(1-9)Online publication date: 2-Nov-2021
  • (2021)Visualizing accessibility with choropleth mapsProceedings of the 5th ACM SIGSPATIAL International Workshop on Location-based Recommendations, Geosocial Networks and Geoadvertising10.1145/3486183.3492801(1-4)Online publication date: 2-Nov-2021
  • (2019)A Data-driven Framework for Long-Range Aircraft Conflict Detection and ResolutionACM Transactions on Spatial Algorithms and Systems10.1145/33288325:4(1-23)Online publication date: 12-Sep-2019
  • (2018)Sorting in Space and Words2018 IEEE 34th International Conference on Data Engineering (ICDE)10.1109/ICDE.2018.00222(1719-1722)Online publication date: Apr-2018
  • (2015)Location Specification and Representation in Multimedia Databases2015 IEEE International Symposium on Multimedia (ISM)10.1109/ISM.2015.128(615-619)Online publication date: Dec-2015
  • (2014)Viewing streaming spatially-referenced data at interactive ratesProceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2666310.2666432(409-412)Online publication date: 4-Nov-2014
  • 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

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media