Journal Home >

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.

Abstract
Full text
Outline

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

Show Author's information 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.
[2]
Rosenfield, A.; Vanderbrug, G. J. Coarse-fine template matching. IEEE Transactions on Systems, Man, and Cybernetics Vol. 7, No. 2, 104–107, 1977.
[3]
Yoo, J. C.; Han, T. H. Fast normalized cross-correlation. Circuits, Systems and Signal Processing Vol. 28, No. 6, 819–843, 2009.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[18]
Soille, P.; Vogt, P. Morphological segmentation of binary patterns. Pattern Recognition Letters Vol. 30, No. 4, 456–459, 2009.
[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.
[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.
[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.
[22]
Kass, M.; Witkin, A.; Terzopoulos, D. Snakes: Active contour models. International Journal of Computer Vision Vol. 1, No. 4, 321–331, 1988.
[23]
Caselles, V.; Kimmel, R.; Sapiro, G. Geodesic active contours. International Journal of Computer Vision Vol. 22, 61–79, 1997.
[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.
[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.
[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.
[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.
[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.
[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.
[32]
Lowe, D. G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision Vol. 60, No. 2, 91–110, 2004.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[48]
Januszewski, M.; Maitin-Shepard, J.; Li, P.; Kornfeld, J.; Denk, W.; Jain, V. Flood-filling networks. arXiv preprint arXiv:1611.00421, 2016.
[49]
Forman, R. Morse theory for cell complexes. Advances in Mathematics Vol. 134, No. 1, 90–145, 1998.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[61]
Zhao, H. K. A fast sweeping method for Eikonal equations. Mathematics of Computation Vol. 74, No. 250, 603–627, 2005.
[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.
[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.
[65]
Barrett, J. F.; Keat, N. Artifacts in CT: Recognition and avoidance. Radiographics Vol. 24, No. 6, 1679–1691, 2004.
[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.
[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.
Publication history
Acknowledgements
Rights and permissions

## Publication history

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

© 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.