Pseudo one pass thinning algorithm

Abstract

A One Pass Thinning Algorithm (OPTA) and a Pseudo One Pass Thinning Algorithm (POPTA) are proposed in this paper. The one pass thinning algorithm uses the concept of thinning and restoring. The OPTA deletes pixels from North, South, East, and West in one pass. The POPTA uses an additional concept of corner pixels, which detects the corner pixels and deletes them to yield better skeletons with little or no distortion. Experimental results show that each of the patterns is thinned to a skeleton of unit pixel width, with no loss of connectivity or distortion. The algorithms are width independent and work for both even pixel wide and odd pixel wide images.

References

1. [1] Naccache, N.J. and Shingal, R., An investigation into the skeletonization approach of Hilditch. Pattern Recognition. v17. 279-284.
2. [2] Arcelli, C., Pattern thinning by contour tracing. Computer Graphics and Image Processing. v13. 130-144.
3. [3] Pavlidis, T., Thinning algorithm for discrete binary images. Computer Graphics and Image Processing. v13. 142-157.
4. [4] Arcelli, C. and di Baja, G. Sanniti, On the sequential approach to medial line transformation. IEEE Trans. Syst. Man Cybernet. v8. 139-144.
5. [5] Rosenfeld, A., A characterization of parallel thinning algorithms. Information and Control. v29. 286-291.
6. [6] Rosenfeld, A., Connectivity of digital pictures. J. ACM. v17. 146-160.
7. [7] Stefanelli, R. and Rosenfeld, A., Some parallel thinning algorithms for digital pictures. J. ACM. v18. 255-264.
8. [8] Rosenfeld, A. and Pfaltz, J.L., Sequential operations in digital picture processing. J. ACM. v13. 471-494.
9. [9] Pavlidis, T., Algorithms for Graphics and Image Processing. 1982. Computer Science Press, Reading, MA.
10. [10] Rosenfeld, A. and Davis, L.S., A note on thinning. IEEE Trans. Syst. Man Cybernet. v25. 226-228.
11. [11] Duetsch, E.S., Thinning algorithms in rectangular, hexagonal, and triangular arrays. Comm. ACM. v15. 827-837.
12. [12] Arcelli, G. and di Baja, G. Sanniti, A width independent fast thinning algorithm. IEEE Trans. Pattern Anal. Machine Intell. v7. 463-474.
13. [13] Pavlidis, T., An asynchronous thinning algorithm. Computer Graphics and Image Processing. v20. 133-157.
14. [14] Stentiford, F.W.M. and Montimer, R.G., Some new heuristics for thinning binary handprinted characters for OCR. IEEE Trans. Syst. Man Cybernet. v13. 81-84.
15. [15] Naccache, N.J. and Shingal, R., SPTA: a proposed algorithm for thinning binary patterns. IEEE Trans. Syst. Man Cybernet. v14. 409-418.
16. [16] Montanari, U., Continues skeletons from digital images. J. ACM. v16. 534-549.
17. [17] Lu, H.E. and Wang, P.S.P., An improved fast thinning algorithm for digital patterns. In: Proc. CVPR '85, pp. 364-367.
18. [18] Govindham, V.K. and Shivaprasad, A.P., A pattern adaptive thinning algorithm. Pattern Recognition. v20 i6. 623-637.
19. [19] Zhang, T.Y. and Suen, C.Y., A fast parallel algorithm for thinning digital patterns. Comm. ACM. v27. 236-239.
20. [20] Chen, Y.S. and Hsu, W.H., A modified fast parallel thinning algorithm for digital patterns. Pattern Recognition Letters. v7. 99-106.

Index Terms

• Applied computing

  • Document management and text processing

    • Document capture

      • Document scanning

      • Graphics recognition and interpretation

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision problems

        • Interest point and salient region detections

  • Computer graphics

    • Image manipulation