A 3D fully parallel surface-thinning algorithm. (English) Zbl 1160.68045
Summary: The thinning is an iterative layer by layer erosion until only the “skeletons” of the objects are left. This paper presents a thinning algorithm for extracting medial surfaces from 3D binary pictures. The strategy which is used is called fully parallel, which means that the same parallel operator is applied at each iteration. An efficient implementation of the proposed algorithm on conventional sequential computers is given and the topological correctness for (26, 6) binary pictures is proved.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68U10 | Computing methodologies for image processing |
References:
| [1] | Ahuja, N.; Chuang, J., Shape representation using a generalized potential field model, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19, 169-176 (1997) |
| [2] | Arcelli, C.; Sanniti di Baja, G.; Serino, L., New removal operators for surface skeletonization, (Kuba, A.; Nyúl, L. G.; Palágyi, K., Proc. 13th Int. Conf. Discrete Geometry for Computer Imagery. Proc. 13th Int. Conf. Discrete Geometry for Computer Imagery, DGCI 2006. Proc. 13th Int. Conf. Discrete Geometry for Computer Imagery. Proc. 13th Int. Conf. Discrete Geometry for Computer Imagery, DGCI 2006, Lecture Notes in Computer Science, vol. 4245 (2006), Springer: Springer Heidelberg), 555-566 · Zbl 1136.68545 |
| [3] | G. Bertrand, Z. Aktouf, A 3D thinning algorithm using subfields, in: Proc. SPIE Conf. on Vision Geometry III 2356, 1994, pp. 113-124; G. Bertrand, Z. Aktouf, A 3D thinning algorithm using subfields, in: Proc. SPIE Conf. on Vision Geometry III 2356, 1994, pp. 113-124 |
| [4] | Bertrand, G., A parallel thinning algorithm for medial surfaces, Pattern Recognition Letters, 16, 979-986 (1995) |
| [5] | Bertrand, G., On P-simple points, C. R. Acad. Sci. Paris, 321, 1077-1084 (1995) · Zbl 0843.68117 |
| [6] | G. Bertrand, P-simple points: A solution for parallel thinning, in: Proc. 5th Int. Conf. Discrete Geometry for Computer Imagery, DGCI’95, 1995, pp. 233-242; G. Bertrand, P-simple points: A solution for parallel thinning, in: Proc. 5th Int. Conf. Discrete Geometry for Computer Imagery, DGCI’95, 1995, pp. 233-242 |
| [7] | Bertrand, G.; Couprie, M., A new 3D parallel thinning scheme based on critical kernels, (Kuba, A.; Nyúl, L. G.; Palágyi, K., Proc. 13th Int. Conf. Discrete Geometry for Computer Imagery. Proc. 13th Int. Conf. Discrete Geometry for Computer Imagery, DGCI 2006. Proc. 13th Int. Conf. Discrete Geometry for Computer Imagery. Proc. 13th Int. Conf. Discrete Geometry for Computer Imagery, DGCI 2006, Lecture Notes in Computer Science, vol. 4245 (2006), Springer: Springer Heidelberg), 580-591 · Zbl 1136.68552 |
| [8] | Blum, H., A transformation for extracting new descriptors of shape, (Wathen-Dunn, W., Models for the Perception of Speech and Visual Form (1967), MIT Press), 362-380 |
| [9] | Borgefors, G.; Nyström, I.; Sanniti di Baja, G., Computing skeletons in three dimensions, Pattern Recognition, 32, 1225-1236 (1999) |
| [10] | Cousty, J.; Bertrand, G.; Couprie, M.; Najman, L., Fusion graphs: Merging properties and watersheds, Journal of Mathematical Imaging and Vision, 30, 87-104 (2008) · Zbl 1180.05117 |
| [11] | W.X. Gong, G. Bertrand, A simple parallel 3D thinning algorithm, in: Proc. 10th IEEE Internat. Conf. on Pattern Recognition, ICPR’90, 1990, pp. 188-190; W.X. Gong, G. Bertrand, A simple parallel 3D thinning algorithm, in: Proc. 10th IEEE Internat. Conf. on Pattern Recognition, ICPR’90, 1990, pp. 188-190 |
| [12] | R.W. Hall, Ş. Küçük, Parallel 3D shrinking algorithms using subfields notions, in: Proc. 11th IEEE Int. Conf. Pattern Recognition, ICPR’92, 1992, pp. 395-398; R.W. Hall, Ş. Küçük, Parallel 3D shrinking algorithms using subfields notions, in: Proc. 11th IEEE Int. Conf. Pattern Recognition, ICPR’92, 1992, pp. 395-398 |
| [13] | Hall, R. W., Parallel connectivity-preserving thinning algorithms, (Kong, T. Y.; Rosenfeld, A., Topological Algorithms for Digital Image Processing. Topological Algorithms for Digital Image Processing, Machine Intelligence and Pattern Recognition, vol. 19 (1996), Elsevier Science), 145-179 |
| [14] | Kong, T. Y.; Rosenfeld, A., Digital topology: Introduction and survey, Computer Vision, Graphics, and Image Processing, 48, 357-393 (1989) |
| [15] | Kong, T. Y., On topology preservation in 2-d and 3-d thinning, International Journal of Pattern Recognition and Artificial Intelligence, 9, 813-844 (1995) |
| [16] | Lee, T.; Kashyap, R. L.; Chu, C., Building skeleton models via 3-D medial surface/axis thinning algorithms, CVGIP: Graphical Models and Image Processing, 56, 462-478 (1994) |
| [17] | Lohou, C.; Bertrand, G., A new 3D 6-subiteration thinning algorithm based on P-simple points, (Proc. 10th Int. Conf. Discrete Geometry for Computer Imagery. Proc. 10th Int. Conf. Discrete Geometry for Computer Imagery, DGCI 2002. Proc. 10th Int. Conf. Discrete Geometry for Computer Imagery. Proc. 10th Int. Conf. Discrete Geometry for Computer Imagery, DGCI 2002, Lecture Notes in Computer Science, vol. 2301 (2002), Springer: Springer Heidelberg), 102-113 · Zbl 1055.68591 |
| [18] | Lohou, C.; Bertrand, G., A 3D 12-subiteration thinning algorithm based on P-simple points, Discrete Applied Mathematics, 139, 171-195 (2004) · Zbl 1072.68635 |
| [19] | Lohou, C.; Bertrand, G., Two symmetrical thinning algorithms for 3D binary images, based on P-simple points, Pattern Recognition, 40, 2301-2314 (2007) · Zbl 1115.68157 |
| [20] | Ma, C. M., A 3D fully parallel thinning algorithm for generating medial faces, Pattern Recognition Letters, 16, 83-87 (1995) |
| [21] | Ma, C. M.; Sonka, M., A fully parallel 3D thinning algorithm and its applications, Computer Vision and Image Understanding, 64, 420-433 (1996) |
| [22] | Ma, C. M.; Wan, S.-Y., Parallel thinning algorithms on 3D (18, 6) binary images, Computer Vision Image Understanding, 80, 364-378 (2000) · Zbl 1011.68535 |
| [23] | Ma, C. M.; Wan, S.-Y., A medial-surface oriented 3-d two-subfield thinning algorithm, Pattern Recognition Letters, 22, 1439-1446 (2001) · Zbl 0984.68681 |
| [24] | Ma, C. M.; Wan, S.-Y.; Chang, H.-K., Extracting medial curves on 3D images, Pattern Recognition Letters, 23, 895-904 (2002) · Zbl 1015.68216 |
| [25] | Ma, C. M.; Wan, S.-Y.; Lee, J.-D., Three-dimensional topology preserving reduction on the 4-subfields, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 1594-1604 (2002) |
| [26] | G. Malandain, G. Bertrand, Fast characterization of 3D simple points, in: Proc. 11th IEEE Internat. Conf. on Pattern Recognition, ICPR’92, 1992, pp. 232-235; G. Malandain, G. Bertrand, Fast characterization of 3D simple points, in: Proc. 11th IEEE Internat. Conf. on Pattern Recognition, ICPR’92, 1992, pp. 232-235 |
| [27] | A. Manzanera, T.M. Bernard, F. Pretêux, B. Longuet, Medial faces from a concise 3D thinning algorithm, in: Proc. 7th IEEE Internat. Conf. Computer Vision, ICCV’99, 1999, vol. 1, pp. 337-343; A. Manzanera, T.M. Bernard, F. Pretêux, B. Longuet, Medial faces from a concise 3D thinning algorithm, in: Proc. 7th IEEE Internat. Conf. Computer Vision, ICCV’99, 1999, vol. 1, pp. 337-343 |
| [28] | D.G. Morgenthaler, Three-dimensional simple points: Serial erosion, parallel thinning and skeletonization, TR-1005, Computer Vision Laboratory, Computer Science Center, Univ. of Maryland, College Park, MD. 1981; D.G. Morgenthaler, Three-dimensional simple points: Serial erosion, parallel thinning and skeletonization, TR-1005, Computer Vision Laboratory, Computer Science Center, Univ. of Maryland, College Park, MD. 1981 |
| [29] | Mukherjee, J.; Das, P. P.; Chatterjee, B. N., On connectivity issues of ESPTA, Pattern Recognition Letters, 11, 643-648 (1990) · Zbl 0800.68823 |
| [30] | Näf, M.; Szekely, G.; Kikinis, R.; Shenton, M. E.; Kübler, O., 3D Voronoi skeletons and their usage for the characterization and recognition of 3D organ shape, Computer Vision and Image Understanding, 66, 147-161 (1997) |
| [31] | Palágyi, K.; Kuba, A., A 3D 6-subiteration thinning algorithm for extracting medial lines, Pattern Recognition Letters, 19, 613-627 (1998) · Zbl 0907.68216 |
| [32] | Palágyi, K.; Kuba, A., A hybrid thinning algorithm for 3D medical images, Journal of Computing and Information Technology, 6, 149-164 (1998) |
| [33] | Palágyi, K.; Kuba, A., Directional 3D thinning using 8 subiterations, (Bertrand, G.; Couprie, M.; Perroton, L., Proc. 8th Int. Conf. Discrete Geometry for Computer Imagery. Proc. 8th Int. Conf. Discrete Geometry for Computer Imagery, DGCI’99. Proc. 8th Int. Conf. Discrete Geometry for Computer Imagery. Proc. 8th Int. Conf. Discrete Geometry for Computer Imagery, DGCI’99, Lecture Notes in Computer Science, vol. 1568 (1999), Springer: Springer Heidelberg), 325-336 |
| [34] | Palágyi, K.; Kuba, A., A parallel 3D 12-subiteration thinning algorithm, Graphical Models and Image Processing, 61, 199-221 (1999) |
| [35] | Palágyi, K., A 3-subiteration 3D thinning algorithm for extracting medial surfaces, Pattern Recognition Letters, 23, 663-675 (2002) · Zbl 1006.68119 |
| [36] | Palágyi, K., A 2-subfield 3D thinning algorithm for extracting medial curves, (Chetverikov, D.; Czúni, L.; Vincze, M., Proc. Joint Hungarian-Austrian Conference on Image Processing and Pattern Recognition HACIPPR 2005 (2005), Austrian Computer Society), 135-142 |
| [37] | Palágyi, K.; Tschirren, J.; Hoffman, E. A.; Sonka, M., Quantitative analysis of pulmonary airway tree structures, Computers in Biology and Medicine, 36, 974-996 (2006) |
| [38] | Palágyi, K., A 3-subiteration surface-thinning algorithm, (Kropatsch, W.; Kampel, M., Proc. 12th Int. Conf. Computer Analysis of Images and Patterns. Proc. 12th Int. Conf. Computer Analysis of Images and Patterns, CAIP 2007. Proc. 12th Int. Conf. Computer Analysis of Images and Patterns. Proc. 12th Int. Conf. Computer Analysis of Images and Patterns, CAIP 2007, Lecture Notes in Computer Science, vol. 4673 (2007), Springer: Springer Heidelberg), 628-635 |
| [39] | Palágyi, K., A subiteration-based surface-thinning algorithm with a period of three, (Hamprecht, F.; Jähne, B.; Schnörr, Ch., Lecture Notes in Computer Science, vol. 4713 (2007), Springer: Springer Heidelberg), 294-303 |
| [40] | Reniers, D.; van Wijk, J. J.; Telea, A., Computing multiscale curve and surface skeletons of genus 0 shapes using a global importance measure, IEEE Transactions on Visualization and Computer Graphics, 14, 355-368 (2008) |
| [41] | M. Rumpf, A. Telea, A continuous skeletonization method based on level sets, in: D. Ebert, P. Brunet, I. Navazo (Eds.), Proc. Joint EUROGRAPHICS-IEEE TCVG Symposium on Visualization, 2002, pp. 151-157; M. Rumpf, A. Telea, A continuous skeletonization method based on level sets, in: D. Ebert, P. Brunet, I. Navazo (Eds.), Proc. Joint EUROGRAPHICS-IEEE TCVG Symposium on Visualization, 2002, pp. 151-157 |
| [42] | Saha, P. K.; Chaudhuri, B. B.; Majumder, D. D., A new shape-preserving parallel thinning algorithm for 3D digital images, Pattern Recognition, 30, 1939-1955 (1997) |
| [43] | Shaked, D.; Bruckstein, A., Pruning medial axes, Computer Vision Image Understanding, 69, 156-169 (1998) |
| [44] | Svensson, S.; Sanniti di Baja, G., Simplifying curve skeletons in volume images, Computer Vision Image Understanding, 90, 242-257 (2003) · Zbl 1055.68145 |
| [45] | Toriwaki, J.; Mori, K., Distance transformation and skeletonization of 3D pictures and their applications to medical images, (Bertrand, G.; Imiya, A.; Klette, R., Digital and Image Geometry. Digital and Image Geometry, Lecture Notes in Computer Science, vol. 2243 (2001), Springer: Springer Heidelberg), 412-428 · Zbl 1052.68781 |
| [46] | Tsao, Y. F.; Fu, K. S., A parallel thinning algorithm for 3-D pictures, Computer Graphics and Image Processing, 17, 315-331 (1981) |
| [47] | Wang, T.; Basu, A., A note on ‘A fully parallel 3D thinning algorithm and its applications’, Pattern Recognition Letters, 28, 501-506 (2007) |
| [48] | Xie, W.; Thompson, R. P.; Perucchio, R., A topology-preserving parallel 3D thinning algorithm for extracting the curve skeleton, Pattern Recognition, 36, 1529-1544 (2003) · Zbl 1055.68148 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
