Zicheng Guo
Editorial Notes
A corrigendum was issued for this paper on June 1, 1989 in the CACM 32:6 issue. You can download the corrigendum from the supplemental material section of this citation page.
Abstract
Two parallel thinning algorithms are presented and evaluated in this article. The two algorithms use two-subiteration approaches: (1) alternatively deleting north and east and then south and west boundary pixels and (2) alternately applying a thinning operator to one of two subfields. Image connectivities are proven to be preserved and the algorithms' speed and medial curve thinness are compared to other two-subiteration approaches and a fully parallel approach. Both approaches produce very thin medial curves and the second achieves the fastest overall parallel thinning.
Supplemental Material
Available for Download
Corrigendum to "Parallel thinning with two-subiteration algorithms" by Guo and Hall, Communications of the ACM, Volume 32, Issue 3, March 1989.
- 1 Arcelli, C., and Di Baja, G.S. A width-independent fast thinning algorithm. IEEE Trans. Patt. Anal. and Mach. lntell. PAMI-7, 4 (July 1985), 463-474.Google Scholar
Digital Library
- 2 Arcelli, C., Cordelia, L., and Levialdi, S. Parallel thinning of binary pictures. Electronics Letters 11, 7 (Apr. 1975), 148-149.Google ScholarCross Ref
- 3 Arcelli, C., Cordelia, L.P., and Levialdi, S. From local maxima to connected skeleton. IEEE Trans. Patt. Anal. and Mach. Intell. PAMI-3, 2 (Mar. 1981), 134-143.Google ScholarDigital Library
- 4 Chin, R.T., Wan, H-K., Stover, D.L., and Iverson, R.D. A one-pass thinning algorithm and its parallel implementation. Comp. Vis. Graphics Image Process 40 (1987), 30-40. Google ScholarDigital Library
- 5 Goetcherian, V. From binary to grey tone image processing using fuzzy logic concepts. Patt. Recognition 12 (1980}, 7-15.Google ScholarCross Ref
- 6 Golay, M.J.E. Hexagonal parallel pattern transformations. IEEE Trans. on Computers C-18, 8 (Aug. 1969), 733-740.Google ScholarDigital Library
- 7 Hall, R.W. Fast parallel thinning algorithms: Parallel speed and connectivity preservation. Commun. ACM 32, 1 (Jan. 1989), 124-131. Google ScholarDigital Library
- 8 Hilditch, C.J. Linear skeletons from square cupboards. In Machine Intelligence 4, B. Meltzer and D. Michie, Eds. American Elsevier, New York, 1969, 403-420.Google Scholar
- 9 Holt, C.M., Stewart, A., Clint, M., and Perrott, R.H. An improved parallel thinning algorithm. Commun. ACM 30, 2 (Feb. 1987}, 156-160. Google ScholarDigital Library
- 10 Lii, H.E., and Wang, P.S.P. A comment on A fast parallel algorithm for thinning digital patterns. Commun. ACM 29, 3 (Mar. 1986), 239-242. Google ScholarDigital Library
- 11 Pavlidis, T. A flexible parallel thinning algorithm. In Proceedings of the Conference on Pattern Recognition and Image Processing (Dallas, Texas, Aug. 3-5, 1981), IEEE, New York, 1981, pp. 162-167.Google Scholar
- 12 Pavlidis, T. Algorithms for Graphics and Image Processing. Springer- Verlag, Berlin, 1982. Google ScholarCross Ref
- 13 Preston, K., and Duff, M.J.B. Modern Cellular Automata. Plenum, New York, 1984.Google ScholarCross Ref
- 14 Rosenfeld, A. Connectivity in digital pictures. JACM 17, 1 {Jan. 1970), 146-160. Google ScholarDigital Library
- 15 Rosenfeld, A. A characterization of parallel thinning algorithms. Information and Control 29 (1975), 286-291.Google ScholarCross Ref
- 16 Rosenfeld, A., and Kak, A. Digital Picture Processing. Academic Press, New York, 1976. Google ScholarDigital Library
- 17 Rosenfeld, A., and Kak, A. Digital Picture Processing Vol. 2. Academic Press, New York, 1982. Google ScholarDigital Library
- 18 Rutovitz, D. Pattern recognition. J. Royal Statist. Soc. 129, (1966), 504-530.Google ScholarCross Ref
- 19 Stefanelli, R., and Rosenfeld, A. Some parallel thinning algorithms for digital pictures. JACM 18, 2 (Apr. 1971), 255-264. Google ScholarDigital Library
- 20 Tamura, H. A comparison of line thinning algorithms from digital geometry viewpoint. In Proceedings of the International Conference on Pattern Recognition (Kyoto, Japan, Nov. 7-10, 1978). IEEE, New York, 1979, pp. 715-719.Google Scholar
- 21 Zhang, T.Y., and Suen, C.Y. A fast thinning algorithm for thinning digital patterns. Commun. ACM 27, 3 (Mar. 1984), 236-239. Google ScholarDigital Library
Index Terms
- Parallel thinning with two-subiteration algorithms
Recommendations
Equivalent Sequential and Parallel Subiteration-Based Surface-Thinning Algorithms
IWCIA 2015: Proceedings of the 17th International Workshop on Combinatorial Image Analysis - Volume 9448Thinning is a frequently applied technique for extracting skeletons or medial surfaces from volumetric binary objects. It is an iterative object reduction: border points that satisfy certainï źtopological and geometric constraints are deleted in a ...
Parallel 3D 12-Subiteration Thinning Algorithms Based on Isthmuses
Proceedings, Part I, of the 9th International Symposium on Advances in Visual Computing - Volume 8033Thinning is an iterative object reduction to obtain skeleton-like shape features of volumetric binary objects. Conventional thinning algorithms preserve endpoints to provide important geometric information relative to the object to be represented. An ...
Optimization and performance analysis of thinning algorithms on parallel computers
This paper presents a concept for an implementation of different parallel thinning algorithms on parallel processors. The emphasis is put on a good parallelization using fine granularity and the simultaneous usage of vectorization. Results and ...
Reviews
Grigore Albeanu
Thinning is an important preprocessing step for many image analysis operations. The goal of this paper is to present and evaluate two parallel thinning algorithms. The authors define these algorithms over binary-valued images digitized in a rectangular tessellation, as two-subiteration algorithms restricted to 3 × 3 thinning operators. These two algorithms are compared with other two-subiteration algorithms and with a fully parallel thinner considered in the literature. The comparison criteria are (1) the minimum number of iterations necessary to reach the skeleton, (2) the minimum percentage of redundant pixels left in the skeleton, and (3) the satisfiability of the specific goals of any thinning algorithms extended in this paper for parallel thinners. The first algorithm modifies the algorithms of Zhang and Suen [1] and Lu¨ and Wang [2] in order to produce thin results and to preserve all connectivity properties. The second algorithm is defined on an image that is divided into two subfields in a checkerboard pattern; it is an adaptation of the classical thinning algorithm of Rosenfeld and Kak. It achieves the best overall parallel speed and minimizes the number of redundant pixels. For both algorithms, the connectivity properties of the image are proved in two appendices. The reader needs no special background. The clarity and the complete presentation of the algorithm and their performance define this paper. All included references are good and recent.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments