A flexible thinning algorithm allowing parallel, sequential, and distributed application

ABSTRACT

A parallel thinning algorithm for digital patterns is presented. This algorithm can also be used for sequential thinning without the simulation of parallel computation. The mathematical background of the algorithm bases on the notion of the Euler characteristic. The proposed algorithm is simple and particularly faster than other parallel algorithms.

REFERENCES

• 1: L. Gerlach , K. T. Malowaniec , H. Scheidig , R. Spurk, The distributed system POOL, Proceedings of the International Workshop on Experiences with Distributed Systems, p.124-161, May 1988, Kaiserslautern, Germany
• 2: GOLDBERG, S.I. Curvature and Homology. Academic Press, San Diego, Calif., 1962, 60-61.
• 3: HmDITC~, C. J. Linear skeletons from square cupboards. In Machine Intelligence IV, B. Meltzer and D. Michie, Eds., American Elsevier, New York, 1969, 403-420.
• 4: Christopher M. Holt , Alan Stewart , Maurice Clint , Ronald H. Perrott, An improved parallel thinning algorithm, Communications of the ACM, v.30 n.2, p.156-160, Feb. 1987 [doi>10.1145/12527.12531]
• 5: Paul Kwok, A thinning algorithm by contour generation, Communications of the ACM, v.31 n.11, p.1314-1324, Nov. 1988 [doi>10.1145/50087.50092]
• 6: DE LOTTO, I. Un inseguitore di contorno. Alta Frequenza 32 (Oct. 1963), 703-705.
• 7: H. E. Lü , P. S. P. Wang, A comment on “a fast parallel algorithm for thinning digital patterns”, Communications of the ACM, v.29 n.3, p.239-242, March 1986 [doi>10.1145/5666.5670]
• 8: Nabil Jean Naccache , Rajjan Shinghal, An investigation into the skeletonization approach of Hilditch, Pattern Recognition, v.17 n.3, p.279-284, 1984 [doi>10.1016/0031-3203(84)90077-3]
• 9: NEustus, C., OLSZ~WSKL J., ANn SCHEERER, D. An efficient distributed thinning algorithm. To appear in Parallel CompuL
• 10: PAVHDtS, T. Algorithms for ,Graphics and Image Processing. Springer-Verlag, New York, 1982, 195-214.
• 11: R. Stefanelli , A. Rosenfeld, Some Parallel Thinning Algorithms for Digital Pictures, Journal of the ACM (JACM), v.18 n.2, p.255-264, April 1971 [doi>10.1145/321637.321646]
• 12: T. Y. Zhang , C. Y. Suen, A fast parallel algorithm for thinning digital patterns, Communications of the ACM, v.27 n.3, p.236-239, March 1984 [doi>10.1145/357994.358023]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.1 Digitization and Image Capture
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms, Design, Theory

Keywords:
applications, distributed computation, parallel algorithms, skeletonization, thinning of digital patterns