A noniterative thinning algorithm

ABSTRACT

Thinning algorithms are applied in image processing to compute a skeleton of an image. In this paper a new thinning method is presented which differs in its approach from other thinning algorithms. In the presented algorithm the minimal distance of a pixel to the edge of the containing object is used to extract the skeleton. Given an n x n matrix of pixels, the algorithm runs in time O(n2). Our measurements show that it is faster than other known sequential algorithms. The mathematical background of the algorithm and the proof of essential features of the obtained skeleton are based on the consideration of the pattern as a directed graph.

REFERENCES

• 1: 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]
• 2: Jan Olszewski, A flexible thinning algorithm allowing parallel, sequential, and distributed application, ACM Transactions on Mathematical Software (TOMS), v.18 n.1, p.35-45, March 1992 [doi>10.1145/128745.128748]
• 3: Theo Pavlidis, Algorithms for Graphics and Imag, W. H. Freeman & Co., New York, NY, 1983
• 4: Azriel Rosenfeld , John L. Pfaltz, Sequential Operations in Digital Picture Processing, Journal of the ACM (JACM), v.13 n.4, p.471-494, Oct. 1966 [doi>10.1145/321356.321357]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

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

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
        I.4.10 Image Representation
            Subjects: Morphological
  I.5 PATTERN RECOGNITION

General Terms:
Algorithms, Design, Theory

Keywords:
skeletonization, thinning of digital patterns