Journal Home > Volume 9 , Issue 2
Computational Visual Media 2023, 9(2): 319-333 https://doi.org/10.1007/s41095-022-0296-2
Research Article | Open Access | Issue | Published: 03 January 2023

Bin-scanning: Segmentation of X-ray CT volume of binned parts using Morse skeleton graph of distance transform

Show Author's Information Yuta Yamauchi1,  Tatsuya Yatagawa1,  Yutaka Ohtake1,  Hiromasa Suzuki1( )
School of Engineering, The University of Tokyo, 7–3–1,Hongo, Bunkyo-ku, Tokyo, Japan
Keywords:
X-ray computed tomography (CT), volume segmentation, graph matching, non-destructive inspection
Cite this article:
Yamauchi Y, Yatagawa T, Ohtake Y, et al. Bin-scanning: Segmentation of X-ray CT volume of binned parts using Morse skeleton graph of distance transform. Computational Visual Media, 2023, 9(2): 319-333. https://doi.org/10.1007/s41095-022-0296-2
Download citation
EndNote(RIS)
BibTeX

3430

Views

12

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

Abstract Full text About this article

X-ray CT scanners, due to the transmissive nature of X-rays, have enabled the non-destructive evaluation of industrial products, even inside their bodies. In light of its effectiveness, this study intro-duces a new approach to accelerate the inspection of many mechanical parts with the same shape in a bin. The input to this problem is a volumetric image (i.e., CT volume) of many parts obtained by a single CT scan. We need to segment the parts in the volume to inspect each of them; however, random postures and dense contacts of the parts prohibit part segmentation using traditional template matching. To address this problem, we convert both the scanned volumetric images of the template and the binned parts to simpler graph structures and solve a subgraph matching problem to segment the parts. We perform a distance transform to convert the CT volume into a distance field. Then, we construct a graph based on Morse theory, in which graph nodes are located at the extremum points of the distance field. The experimental evaluation demonstrates that our fully automatic approach can detect target parts appropriately, even for a heap of 50 parts. Moreover, the overall com-putation can be performed in approximately 30 min for a large CT volume of approximately 2000×2000×1000 voxels.


menu
Abstract
Full text
Outline
About this article

Bin-scanning: Segmentation of X-ray CT volume of binned parts using Morse skeleton graph of distance transform

Show Author's information Yuta Yamauchi1, Tatsuya Yatagawa1, Yutaka Ohtake1, Hiromasa Suzuki1( )
School of Engineering, The University of Tokyo, 7–3–1,Hongo, Bunkyo-ku, Tokyo, Japan

Abstract

X-ray CT scanners, due to the transmissive nature of X-rays, have enabled the non-destructive evaluation of industrial products, even inside their bodies. In light of its effectiveness, this study intro-duces a new approach to accelerate the inspection of many mechanical parts with the same shape in a bin. The input to this problem is a volumetric image (i.e., CT volume) of many parts obtained by a single CT scan. We need to segment the parts in the volume to inspect each of them; however, random postures and dense contacts of the parts prohibit part segmentation using traditional template matching. To address this problem, we convert both the scanned volumetric images of the template and the binned parts to simpler graph structures and solve a subgraph matching problem to segment the parts. We perform a distance transform to convert the CT volume into a distance field. Then, we construct a graph based on Morse theory, in which graph nodes are located at the extremum points of the distance field. The experimental evaluation demonstrates that our fully automatic approach can detect target parts appropriately, even for a heap of 50 parts. Moreover, the overall com-putation can be performed in approximately 30 min for a large CT volume of approximately 2000×2000×1000 voxels.

Keywords:

X-ray computed tomography (CT), volume segmentation, graph matching, non-destructive inspection
Received: 16 March 2022 Accepted: 28 May 2022 Published: 03 January 2023 Issue date: June 2023
References(67)
[1]
Barrow, H. G.; Tenenbaum, J. M.; Bolles, R. C.; Wolf, H. C. Parametric correspondence and chamfer matching: Two new techniques for image matching. In: Proceedings of the 5th International Joint Conference on Artificial Intelligence, Vol. 2, 659–663, 1977.
Google Scholar
[2]
Rosenfield, A.; Vanderbrug, G. J. Coarse-fine template matching. IEEE Transactions on Systems, Man, and Cybernetics Vol. 7, No. 2, 104–107, 1977.
DOI Google Scholar
[3]
Yoo, J. C.; Han, T. H. Fast normalized cross-correlation. Circuits, Systems and Signal Processing Vol. 28, No. 6, 819–843, 2009.
DOI Google Scholar
[4]
Besl, P. J.; McKay, N. D. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 14, No. 2, 239–256, 1992.
DOI Google Scholar
[5]
Rusu, R. B.; Blodow, N.; Beetz, M. Fast point feature histograms (FPFH) for 3D registration. In: Proceedings of the IEEE International Conference on Robotics and Automation, 3212–3217, 2009.
DOI Google Scholar
[6]
Berg, A. C.; Berg, T. L.; Malik, J. Shape matching and object recognition using low distortion correspondences. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 26–33, 2005.
Google Scholar
[7]
Ullmann, J. R. An algorithm for subgraph isomorphism. Journal of the ACM Vol. 23, No. 1, 31–42, 1976.
DOI Google Scholar
[8]
Cordella, L. P.; Foggia, P.; Sansone, C.; Vento, M. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 26, No. 10, 1367–1372, 2004.
DOI Google Scholar
[9]
Zhou, F.; de la Torre, F. Factorized graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 38, No. 9, 1774–1789, 2016.
DOI Google Scholar
[10]
Yu, T. S.; Wang, R. S. Graph matching with low-rank regularization. In: Proceedings of the IEEE Winter Conference on Applications of Computer Vision, 1–9, 2016.
Google Scholar
[11]
Rolínek, M.; Swoboda, P.; Zietlow, D.; Paulus, A.; Musil, V.; Martius, G. Deep graph matching via blackbox differentiation of combinatorial solvers. In: Computer Vision – ECCV 2020. Lecture Notes in Computer Science, Vol. 12373. Vedaldi, A.; Bischof, H.; Brox, T.; Frahm, J. M. Eds. Springer Cham, 407–424, 2020.
DOI
[12]
Wang, R. Z.; Yan, J. C.; Yang, X. K. Neural graph matching network: Learning lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 44, No. 9, 5261–5279, 2022.
DOI Google Scholar
[13]
Sarlin, P. E.; DeTone, D.; Malisiewicz, T.; Rabinovich, A. SuperGlue: Learning feature matching with graph neural networks. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 4937–4946, 2020.
DOI Google Scholar
[14]
Milnor, J. Morse Theory. Princeton University Press, 1963.
[15]
Westin, C. F.; Warfield, S.; Bhalerao, A.; Mui, L.; Richolt, J.; Kikinis, R. Tensor controlled local structure enhancement of CT images for bone segmentation. In: Medical Image Computing and Computer-Assis-ted Intervention — MICCAI’98. Lecture Notes in Computer Science, Vol. 1496. Wells, W. M.; Colchester, A.; Delp, S. Eds. Springer Berlin Heidelberg, 1205–1212, 1998.
[16]
Kang, Y.; Engelke, K.; Kalender, W. A. A new accurate and precise 3-D segmentation method for skeletal structures in volumetric CT data. IEEE Transactions on Medical Imaging Vol. 22, No. 5, 586–598, 2003.
DOI Google Scholar
[17]
Otsu, N. A threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man, and Cybernetics Vol. 9, No. 1, 62–66, 1979.
DOI Google Scholar
[18]
Soille, P.; Vogt, P. Morphological segmentation of binary patterns. Pattern Recognition Letters Vol. 30, No. 4, 456–459, 2009.
DOI Google Scholar
[19]
Fukunaga, K.; Hostetler, L. The estimation of the gradient of a density function, with applications in pattern recognition. IEEE Transactions on Information Theory Vol. 21, No. 1, 32–40, 1975.
DOI Google Scholar
[20]
Carreira-Perpiñán, M. Á. Fast nonparametric clustering with Gaussian blurring mean-shift. In: Proceedings of the 23rd International Conference on Machine Learning, 153–160, 2006.
DOI Google Scholar
[21]
Comaniciu, D.; Meer, P. Mean shift: A robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 24, No. 5, 603–619, 2002.
DOI Google Scholar
[22]
Kass, M.; Witkin, A.; Terzopoulos, D. Snakes: Active contour models. International Journal of Computer Vision Vol. 1, No. 4, 321–331, 1988.
DOI Google Scholar
[23]
Caselles, V.; Kimmel, R.; Sapiro, G. Geodesic active contours. International Journal of Computer Vision Vol. 22, 61–79, 1997.
DOI Google Scholar
[24]
Pardo, X. M.; Carreira, M. J.; Mosquera, A.; Cabello, D. A snake for CT image segmentation integrating region and edge information. Image and Vision Computing Vol. 19, No. 7, 461–475, 2001.
DOI Google Scholar
[25]
Taud, H.; Martinez-Angeles, R.; Parrot, J. F.; Hernandez-Escobedo, L. Porosity estimation method by X-ray computed tomography. Journal of Petroleum Science and Engineering Vol. 47, Nos. 3–4, 209–217, 2005.
DOI Google Scholar
[26]
Boykov, Y. Y.; Jolly, M. P. Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In: Proceedings of the 8th IEEE International Conference on Computer Vision, 105–112, 2001.
[27]
Felzenszwalb, P. F.; Huttenlocher, D. P. Efficient graph-based image segmentation. International Journal of Computer Vision Vol. 59, No. 2, 167–181, 2004.
DOI Google Scholar
[28]
Liu, L.; Raber, D.; Nopachai, D.; Commean, P.; Sinacore, D.; Prior, F.; Pless, R.; Ju, T. Interactive separation of segmented bones in CT volumes using graph cut. In: Medical Image Computing and Computer-Assisted Intervention – MICCAI 2008. Lecture Notes in Computer Science, Vol. 5241. Metaxas, D.; Axel, L.; Fichtinger, G.; Székely, G. Eds. Springer Berlin Heidelberg, 296–304, 2008.
DOI
[29]
Vincent, L.; Soille, P. Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 13, No. 6, 583–598, 1991.
DOI Google Scholar
[30]
Comaniciu, D. Image segmentation using clustering with saddle point detection. In: Proceedings of the International Conference on Image Processing, III, 2002.
Google Scholar
[31]
Flitton, G.; Breckon, T.; Megherbi Bouallagu, N. Object recognition using 3D SIFT in complex CT volumes. In: Proceedings of the British Machine Vision Conference, 11.1–11.12, 2010.
DOI Google Scholar
[32]
Lowe, D. G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision Vol. 60, No. 2, 91–110, 2004.
DOI Google Scholar
[33]
Papazov, C.; Burschka, D. An efficient RANSAC for 3D object recognition in noisy and occluded scenes. In: Computer Vision – ACCV 2010. Lecture Notes in Computer Science, Vol. 6492. Kimmel, R.; Klette, R.; Sugimoto, A. Eds. Springer Berlin Heidelberg, 135–148, 2011.
[34]
Drost, B.; Ulrich, M.; Navab, N.; Ilic, S. Model globally, match locally: Efficient and robust 3D object recognition. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 998–1005, 2010.
DOI Google Scholar
[35]
Vock, R.; Dieckmann, A.; Ochmann, S.; Klein, R. Fast template matching and pose estimation in 3D point clouds. Computers & Graphics Vol. 79, 36–45, 2019.
DOI
[36]
Mian, A. S.; Bennamoun, M.; Owens, R. Three-dimensional model-based object recognition and segmentation in cluttered scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 28, No. 10, 1584–1601, 2006.
DOI Google Scholar
[37]
Lorensen, W. E.; Cline, H. E. Marching cubes: A high resolution 3D surface construction algorithm. ACM SIGGRAPH Computer Graphics Vol. 21, No. 4, 163–169, 1987.
DOI Google Scholar
[38]
Long, J.; Shelhamer, E.; Darrell, T. Fully convolutional networks for semantic segmentation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 3431–3440, 2015.
DOI Google Scholar
[39]
Ronneberger, O.; Fischer, P.; Brox, T. U-Net: Convolutional networks for biomedical image segmentation. In: Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015. Lecture Notes in Computer Science, Vol. 9351. Navab, N.; Hornegger, J.; Wells, W.; Frangi, A. Eds. Springer Cham, 234–241, 2015.
DOI
[40]
Çiçek, Ö.; Abdulkadir, A.; Lienkamp, S. S.; Brox, T.; Ronneberger, O. 3D U-Net: Learning dense volumetric segmentation from sparse annotation. In: Medical Image Computing and Computer-Assisted Intervention – MICCAI 2016. Lecture Notes in Computer Science, Vol. 9901. Ourselin, S.; Joskowicz, L.; Sabuncu, M.; Unal, G.; Wells, W. Eds. Springer Cham, 424–432, 2016.
[41]
Lin, T. Y.; Dollár, P.; Girshick, R.; He, K. M.; Hariharan, B.; Belongie, S. Feature pyramid networks for object detection. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 936–944, 2017.
DOI Google Scholar
[42]
Zhou, X.; Takayama, R.; Wang, S.; Hara, T.; Fujita, H. Deep learning of the sectional appearances of 3D CT images for anatomical structure segmentation based on an FCN voting method. Medical Physics Vol. 44, No. 10, 5221–5233, 2017.
DOI Google Scholar
[43]
Zhou, Y. Y.; Xie, L. X.; Shen, W.; Wang, Y.; Fishman, E. K.; Yuille, A. L. A fixed-point model for pancreas segmentation in abdominal CT scans. In: Medical Image Computing and Computer Assisted Intervention - MICCAI 2017. Lecture Notes in Computer Science, Vol. 10433. Descoteaux, M.; Maier-Hein, L.; Franz, A.; Jannin, P.; Collins, D.; Duchesne, S. Eds. Springer Cham, 693–701, 2017.
[44]
Li, P. C.; Zhou, X. Y.; Wang, Z. Y.; Yang, G. Z. Z-Net: An anisotropic 3D DCNN for medical CT volume segmentation. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2906–2913, 2020.
Google Scholar
[45]
Dou, Q.; Yu, L. Q.; Chen, H.; Jin, Y. M.; Yang, X.; Qin, J.; Heng, P. A. 3D deeply supervised network for automated segmentation of volumetric medical images. Medical Image Analysis Vol. 41, 40–54, 2017.
DOI Google Scholar
[46]
Cui, Z. M.; Li, C. J.; Wang, W. P. ToothNet: Automatic tooth instance segmentation and iden-tification from cone beam CT images. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 6361–6370, 2019.
DOI Google Scholar
[47]
Gruber, R.; Gerth, S.; Claußen, J.; Wörlein, N.; Uhlmann, N.; Wittenberg, T. Exploring flood filling networks for instance segmentation of XXL-volumetric and bulk material CT data. Journal of Nondestructive Evaluation Vol. 40, No. 1, Article No. 1, 2020.
DOI Google Scholar
[48]
Januszewski, M.; Maitin-Shepard, J.; Li, P.; Kornfeld, J.; Denk, W.; Jain, V. Flood-filling networks. arXiv preprint arXiv:1611.00421, 2016.
Google Scholar
[49]
Forman, R. Morse theory for cell complexes. Advances in Mathematics Vol. 134, No. 1, 90–145, 1998.
DOI Google Scholar
[50]
Edelsbrunner, H.; Harer, J.; Zomorodian, A. Hierarchical morse complexes for piecewise linear 2-manifolds. In: Proceedings of the 17th Annual Symposium on Computational Geometry, 70–79, 2001.
DOI Google Scholar
[51]
Bremer, P. T.; Hamann, B.; Edelsbrunner, H.; Pascucci, V. A topological hierarchy for functions on triangulated surfaces. IEEE Transactions on Visualization and Computer Graphics Vol. 10, No. 4, 385–396, 2004.
DOI Google Scholar
[52]
Paris, S.; Durand, F. A topological approach to hierarchical segmentation using mean shift. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1–8, 2007.
DOI Google Scholar
[53]
Robins, V.; Wood, P. J.; Sheppard, A. P. Theory and algorithms for constructing discrete morse complexes from grayscale digital images. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 33, No. 8, 1646–1658, 2011.
DOI Google Scholar
[54]
Shivashankar, N.; Pranav, P.; Natarajan, V.; van de Weygaert, R.; Bos, E. G. P.; Rieder, S. Felix: A topology based framework for visual exploration of cosmic filaments. IEEE Transactions on Visualization and Computer Graphics Vol. 22, No. 6, 1745–1759, 2016.
DOI Google Scholar
[55]
Günther, D.; Boto, R. A.; Contreras-Garcia, J.; Piquemal, J. P.; Tierny, J. Characterizing molecular interactions in chemical systems. IEEE Transactions on Visualization and Computer Graphics Vol. 20, No. 12, 2476–2485, 2014.
DOI Google Scholar
[56]
Dong, S.; Bremer, P. T.; Garland, M.; Pascucci, V.; Hart, J. C. Spectral surface quadrangulation. In: Proceedings of the ACM SIGGRAPH 2006 Papers, 1057–1066, 2006.
DOI Google Scholar
[57]
Fang, X. Z.; Bao, H. J.; Tong, Y. Y.; Desbrun, M.; Huang, J. Quadrangulation through morse-parameterization hybridization. ACM Transactions on Graphics Vol. 37, No. 4, Article No. 92, 2018.
DOI Google Scholar
[58]
De Floriani, L.; Fugacci, U.; Iuricich, F.; Magillo, P. Morse complexes for shape segmentation and homological analysis: Discrete models and algorithms. Computer Graphics Forum Vol. 34, No. 2, 761–785, 2015.
DOI Google Scholar
[59]
Heine, C.; Leitte, H.; Hlawitschka, M.; Iuricich, F.; de Floriani, L.; Scheuermann, G.; Hagen, H.; Garth, C. A survey of topology-based methods in visualization. Computer Graphics Forum Vol. 35, No. 3, 643–667, 2016.
DOI Google Scholar
[60]
Nagai, Y.; Ohtake, Y.; Suzuki, H. SegMo: CT volume segmentation using a multi-level Morse complex. Computer-Aided Design Vol. 107, 23–36, 2019.
DOI Google Scholar
[61]
Zhao, H. K. A fast sweeping method for Eikonal equations. Mathematics of Computation Vol. 74, No. 250, 603–627, 2005.
DOI Google Scholar
[62]
Ni, X. L.; Garland, M.; Hart, J. C. Fair morse functions for extracting the topological structure of a surface mesh. ACM Transactions on Graphics Vol. 23, No. 3, 613–622, 2004.
DOI Google Scholar
[63]
Čomić L.; de Floriani, L. Cancellation of critical points in 2D and 3D morse and morse-Smale complexes. In: Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, Vol. 4992. Coeurjolly, D.; Sivignon, I.; Tougne, L.; Dupont, F. Eds. Springer Berlin Heidelberg, 117–128, 2008.
[64]
Umeyama, S. Least-squares estimation of trans-formation parameters between two point patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 13, No. 4, 376–380, 1991.
DOI Google Scholar
[65]
Barrett, J. F.; Keat, N. Artifacts in CT: Recognition and avoidance. Radiographics Vol. 24, No. 6, 1679–1691, 2004.
DOI Google Scholar
[66]
Reddy, P.; Guerrero, P.; Fisher, M.; Li, W.; Mitra, N. J. Discovering pattern structure using differentiable compositing. ACM Transactions on Graphics Vol. 39, No. 6, Article No. 262, 2020.
DOI Google Scholar
[67]
Gelfand, N.; Ikemoto, L.; Rusinkiewicz, S.; Levoy, M. Geometrically stable sampling for the ICP algorithm. In: Proceedings of the 4th International Conference on 3-D Digital Imaging and Modeling, 260–267, 2003.
Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 16 March 2022
Accepted: 28 May 2022
Published: 03 January 2023
Issue date: June 2023

Copyright

© The Author(s) 2022.

Acknowledgements

We thank Dr. Katsuaki Kawachi for conducting the rigid body simulations of teapots. We also thank Dr. Takashi Michikawa at RIKEN for helpful discussions on distance transformation.

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduc-tion in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.

Return