article

Free access

Thinning algorithms on rectangular, hexagonal, and triangular arrays

Author:

E. S. DeutschAuthors Info & Claims

Communications of the ACM, Volume 15, Issue 9

Pages 827 - 837

https://doi.org/10.1145/361573.361583

Published: 01 September 1972 Publication History

PDF eReader

Abstract

In this report three thinning algorithms are developed: one each for use with rectangular, hexagonal, and triangular arrays. The approach to the development of each algorithm is the same. Pictorial results produced by each of the algorithms are presented and the relative performances of the algorithms are compared. It is found that the algorithm operating with the triangular array is the most sensitive to image irregularities and noise, yet it will yield a thinned image with an overall reduced number of points. It is concluded that the algorithm operating in conjunction with the hexagonal array has features which strike a balance between those of the other two arrays.

References

[1]

Rutovitz, D. Pattern recognition. J. Royal Statistical Society {A} 1291V, (1966), 504-530.

Google Scholar

[2]

Deutsch, E.S. Comments on a line thinning scheme. British Computer J. 12, 4 (Nov. 1969), 142.

Google Scholar

[3]

Hilditch, C.J. Linear skeletons from square cupboards. In Machine bltelligence 4, B. Meltzer and D. Michie (Eds), American Elsevier, New York, 1969, pp. 403-420.

Google Scholar

[4]

Deutsch, E.S. Towards isotropic image reductiam IFIP Congress 71, North Holland Pub. Co., Amsterdam; Booklet TA-2, pp. 75-85.

Google Scholar

[5]

Rosenfeld, A. Connectivity in digital pictures. J ACM 17, 1 (Jan. 1970), 146-160.

Digital Library

Google Scholar

[6]

Deutsch, E.S. Preprocessing for character recognition. I.E.E. Conf. on Pattern Recognition, July 1968, pp. 179-190.

Google Scholar

[7]

Golay, M.J.E. Hexagonal parallel pattern transformations. Trans IEEE Comput. C18, 8 (Aug. 1969).

Google Scholar

[8]

Freeman, H. On the encoding of arbitrary geometric configuration. IRE Trans E C (June 1961), 260-268.

Crossref

Google Scholar

[9]

Deutsch, E.S. On parallel operations on hexagonal arrays. Trans IEEE Comput. Cl9, 10 (Oct. 1970), 982-983.

Google Scholar

Cited By

View all

Wiederhold P(2025)Computing the minimal perimeter polygon for digital objects in the triangular tilingDiscrete Applied Mathematics10.1016/j.dam.2024.11.026363(27-44)Online publication date: Mar-2025
https://doi.org/10.1016/j.dam.2024.11.026
Magillo P(2025)Non-square grids: A new trend in imaging and modeling?Computer Science Review10.1016/j.cosrev.2024.10069556(100695)Online publication date: May-2025
https://doi.org/10.1016/j.cosrev.2024.100695
Liang QZhou JBen JChen YHuang XDing JDai J(2024)Precise hexagonal pixel modeling and an easy-sharing storage scheme for remote sensing images based on discrete global grid systemInternational Journal of Digital Earth10.1080/17538947.2024.232882417:1Online publication date: 12-Mar-2024
https://doi.org/10.1080/17538947.2024.2328824
Show More Cited By

Recommendations

Single-crystal hexagonal perovskite YAlO3 epitaxially on GaAs(111)A and (001) using atomic layer deposition

Hexagonal perovskite YAlO3 films were epitaxially grown on both GaAs(001) and GaAs(111)A substrates by utilizing sub-nano-laminated ALD-Y2O3/Al2O3 multilayers with a post-deposition rapid thermal annealing (RTA) to 900C in He ambience. The c-axis of the ...
Thinning algorithms based on quadtree and octree representations

Thinning is a critical pre-processing step to obtain skeletons for pattern analysis. Quadtree and octree are hierarchical data representations in image processing and computer graphics. In this paper, we present new 2-D area-based and 3-D surface-based ...
Rectangular Hexagonal Mesh Generation for Parametric Modeling
SIBGRAPI '09: Proceedings of the 2009 XXII Brazilian Symposium on Computer Graphics and Image Processing

This paper addresses the problem of rectangular hexagonal mesh generation for surface modeling. Hexagonal grids are important for several applications such as the simulation of carbon nanostructures. A fast and accurate method to obtain a rectangular ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 15, Issue 9

Sept. 1972

59 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/361573

Editor:
M. Stuart Lynn
Rice Univ., Houston, TX

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 1972

Published in CACM Volume 15, Issue 9

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

182
Total Citations
View Citations
1,284
Total Downloads

Downloads (Last 12 months)169
Downloads (Last 6 weeks)33

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wiederhold P(2025)Computing the minimal perimeter polygon for digital objects in the triangular tilingDiscrete Applied Mathematics10.1016/j.dam.2024.11.026363(27-44)Online publication date: Mar-2025
https://doi.org/10.1016/j.dam.2024.11.026
Magillo P(2025)Non-square grids: A new trend in imaging and modeling?Computer Science Review10.1016/j.cosrev.2024.10069556(100695)Online publication date: May-2025
https://doi.org/10.1016/j.cosrev.2024.100695
Liang QZhou JBen JChen YHuang XDing JDai J(2024)Precise hexagonal pixel modeling and an easy-sharing storage scheme for remote sensing images based on discrete global grid systemInternational Journal of Digital Earth10.1080/17538947.2024.232882417:1Online publication date: 12-Mar-2024
https://doi.org/10.1080/17538947.2024.2328824
Saadetoğlu MNagy BAvkan A(2024)Digital continuity of rotations in the 2D regular gridsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-023-09891-w92:1(115-137)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s10472-023-09891-w
Saadetoğlu MNagy BAvkan A(2024)Rotations on the triangular grid: angles of changes of the neighborhood motion mapAequationes mathematicae10.1007/s00010-024-01062-498:4(1053-1070)Online publication date: 2-May-2024
https://doi.org/10.1007/s00010-024-01062-4
Wiederhold P(2024)On the Minimal Perimeter Polygon for Digital Objects in the Triangular TilingPattern Recognition10.1007/978-3-031-62836-8_14(141-154)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62836-8_14
Palágyi K(2024)1-Attempt and Equivalent Thinning on the Hexagonal GridDiscrete Geometry and Mathematical Morphology10.1007/978-3-031-57793-2_30(390-401)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57793-2_30
Nagy B(2024)A Khalimsky-Like Topology on the Triangular GridDiscrete Geometry and Mathematical Morphology10.1007/978-3-031-57793-2_12(150-162)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57793-2_12
Nagy B(2023)Weighted distances and distance transforms on the triangular tilingTransactions in GIS10.1111/tgis.1311227:7(2042-2098)Online publication date: 17-Nov-2023
https://doi.org/10.1111/tgis.13112
Nagy B(2023)A digital geometry on the tetrakis square tiling—Distance and coarseningTransactions in GIS10.1111/tgis.13029Online publication date: 13-Feb-2023
https://doi.org/10.1111/tgis.13029
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.

Abstract

References

Cited By

Recommendations

Single-crystal hexagonal perovskite YAlO3 epitaxially on GaAs(111)A and (001) using atomic layer deposition

Thinning algorithms based on quadtree and octree representations

Rectangular Hexagonal Mesh Generation for Parametric Modeling

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations