AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Computational Visual Media Article
PDF (5.6 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

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

School of Engineering, The University of Tokyo, 7–3–1,Hongo, Bunkyo-ku, Tokyo, Japan
Show Author Information

Graphical Abstract

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 segmentationgraph matchingnon-destructive inspection

References

[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.
[2]
Rosenfield, A.; Vanderbrug, G. J. Coarse-fine template matching. IEEE Transactions on Systems, Man, and Cybernetics Vol. 7, No. 2, 104–107, 1977.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
[7]
Ullmann, J. R. An algorithm for subgraph isomorphism. Journal of the ACM Vol. 23, No. 1, 31–42, 1976.
Crossref 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.
Crossref 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.
Crossref 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.
[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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref Google Scholar
[18]
Soille, P.; Vogt, P. Morphological segmentation of binary patterns. Pattern Recognition Letters Vol. 30, No. 4, 456–459, 2009.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref Google Scholar
[23]
Caselles, V.; Kimmel, R.; Sapiro, G. Geodesic active contours. International Journal of Computer Vision Vol. 22, 61–79, 1997.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref Google Scholar
[30]
Comaniciu, D. Image segmentation using clustering with saddle point detection. In: Proceedings of the International Conference on Image Processing, III, 2002.
[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.
Crossref
[32]
Lowe, D. G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision Vol. 60, No. 2, 91–110, 2004.
Crossref 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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref 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.
[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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[61]
Zhao, H. K. A fast sweeping method for Eikonal equations. Mathematics of Computation Vol. 74, No. 250, 603–627, 2005.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[65]
Barrett, J. F.; Keat, N. Artifacts in CT: Recognition and avoidance. Radiographics Vol. 24, No. 6, 1679–1691, 2004.
Crossref 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.
Crossref 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.
Computational Visual Media
Volume 9 Issue 2,
June 2023
Pages 319-333
DOI: 10.1007/s41095-022-0296-2
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

8393

Views

84

Downloads

1

Crossref

2

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 16 March 2022
Accepted: 28 May 2022
Published: 03 January 2023
© The Author(s) 2022.

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