Graph Cuts Segmentation Approach Using a Patch-Based Similarity Measure Applied for Interactive CT Lung Image Segmentation

Lung CT image segmentation is a prerequisite in lung
CT image analysis. Most of the conventional methods need a
post-processing to deal with the abnormal lung CT scans such as
lung nodules or other lesions. The simplest similarity measure in
the standard Graph Cuts Algorithm consists of directly comparing
the pixel values of the two neighboring regions, which is not
accurate because this kind of metrics is extremely sensitive to minor
transformations such as noise or other artifacts problems. In this work,
we propose an improved version of the standard graph cuts algorithm
based on the Patch-Based similarity metric. The boundary penalty
term in the graph cut algorithm is defined Based on Patch-Based
similarity measurement instead of the simple intensity measurement
in the standard method. The weights between each pixel and its
neighboring pixels are Based on the obtained new term. The graph
is then created using theses weights between its nodes. Finally,
the segmentation is completed with the minimum cut/Max-Flow
algorithm. Experimental results show that the proposed method is
very accurate and efficient, and can directly provide explicit lung
regions without any post-processing operations compared to the
standard method.

Authors:

• Aicha Majda
• Abdelhamid El Hassani

Keywords:

• Graph cuts
• lung CT scan
• lung parenchyma segmentation
• patch based similarity metric.

References:

[1] C. A. Ridge, A. M. McErlean, and M. S. Ginsberg, “Epidemiology
of lung cancer,” in Seminars in interventional radiology, vol. 30,
pp. 093–098, Thieme Medical Publishers, 2013.
[2] C. E. DeSantis, C. C. Lin, A. B. Mariotto, R. L. Siegel, K. D. Stein,
J. L. Kramer, R. Alteri, A. S. Robbins, and A. Jemal, “Cancer treatment
and survivorship statistics, 2014,” CA: a cancer journal for clinicians,
vol. 64, no. 4, pp. 252–271, 2014.
[3] L. Tsochatzidis, K. Zagoris, N. Arikidis, A. Karahaliou, L. Costaridou,
and I. Pratikakis, “Computer-aided diagnosis of mammographic masses
based on a supervised content-based image retrieval approach,” Pattern
Recognition, 2017.
[4] J. won Cha, M. M. Farhangi, N. Dunlap, and A. Amini, “Volumetric
analysis of respiratory gated whole lung and liver ct data with
motion-constrained graph cuts segmentation,” in Engineering in
Medicine and Biology Society (EMBC), 2017 39th Annual International
Conference of the IEEE, pp. 3405–3408, IEEE, 2017.
[5] W. Zhang, X. Wang, P. Zhang, and J. Chen, “Global optimal hybrid
geometric active contour for automated lung segmentation on ct images,”
Computers in biology and medicine, vol. 91, pp. 168–180, 2017.
[6] P. P. Rebouc¸as Filho, P. C. Cortez, A. C. da Silva Barros, V. H. C.
Albuquerque, and J. M. R. Tavares, “Novel and powerful 3d adaptive
crisp active contour method applied in the segmentation of ct lung
images,” Medical image analysis, vol. 35, pp. 503–516, 2017.
[7] I. Sluimer, A. Schilham, M. Prokop, and B. van Ginneken, “Computer
analysis of computed tomography scans of the lung: a survey,” IEEE
transactions on medical imaging, vol. 25, no. 4, pp. 385–405, 2006.
[8] S. Hu, E. A. Hoffman, and J. M. Reinhardt, “Automatic lung
segmentation for accurate quantitation of volumetric x-ray ct images,”
IEEE transactions on medical imaging, vol. 20, no. 6, pp. 490–498,
2001.
[9] S. G. Armato and W. F. Sensakovic, “Automated lung segmentation for
thoracic ct: Impact on computer-aided diagnosis1,” Academic Radiology,
vol. 11, no. 9, pp. 1011–1021, 2004.
[10] D. Mahapatra, “Semi-supervised learning and graph cuts for consensus
based medical image segmentation,” Pattern Recognition, vol. 63,
pp. 700–709, 2017.
[11] W. Sun, X. Huang, T.-L. B. Tseng, and W. Qian, “Automatic lung nodule
graph cuts segmentation with deep learning false positive reduction,” in
SPIE Medical Imaging, pp. 101343M–101343M, International Society
for Optics and Photonics, 2017.
[12] Y. Y. Boykov and M.-P. Jolly, “Interactive graph cuts for optimal
boundary & region segmentation of objects in nd images,” in Computer
Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International
Conference on, vol. 1, pp. 105–112, IEEE, 2001.
[13] C. Rother, V. Kolmogorov, and A. Blake, “Grabcut: Interactive
foreground extraction using iterated graph cuts,” in ACM transactions
on graphics (TOG), vol. 23, pp. 309–314, ACM, 2004.
[14] S. Vicente, V. Kolmogorov, and C. Rother, “Graph cut based image
segmentation with connectivity priors,” in Computer vision and pattern
recognition, 2008. CVPR 2008. IEEE conference on, pp. 1–8, IEEE,
2008.
[15] K. Nakagomi, A. Shimizu, H. Kobatake, M. Yakami, K. Fujimoto, and
K. Togashi, “Multi-shape graph cuts with neighbor prior constraints and
its application to lung segmentation from a chest ct volume,” Medical
image analysis, vol. 17, no. 1, pp. 62–77, 2013.
[16] S. Dai, K. Lu, J. Dong, Y. Zhang, and Y. Chen, “A novel
approach of lung segmentation on chest ct images using graph cuts,”
Neurocomputing, vol. 168, pp. 799–807, 2015.
[17] S. G. Armato, G. McLennan, L. Bidaut, M. F. McNitt-Gray, C. R. Meyer,
A. P. Reeves, B. Zhao, D. R. Aberle, C. I. Henschke, E. A. Hoffman,
et al., “The lung image database consortium (lidc) and image database
resource initiative (idri): a completed reference database of lung nodules
on ct scans,” Medical physics, vol. 38, no. 2, pp. 915–931, 2011.
[18] B. N. Narayanan, R. C. Hardie, T. M. Kebede, and M. J.
Sprague, “Optimized feature selection-based clustering approach for
computer-aided detection of lung nodules in different modalities,”
Pattern Analysis and Applications, pp. 1–13, 2017.
[19] A. Buades, B. Coll, and J.-M. Morel, “A review of image denoising
algorithms, with a new one,” Multiscale Modeling & Simulation, vol. 4,
no. 2, pp. 490–530, 2005.
[20] H. Jomaa, R. Mabrouk, N. Khlifa, and F. Morain-Nicolier, “Denoising of
dynamic pet images using a multi-scale transform and non-local means
filter,” Biomedical Signal Processing and Control, vol. 41, pp. 69–80,
2018.
[21] A. El Hassani and A. Majda, “Efficient image denoising method based
on mathematical morphology reconstruction and the non-local means
filter for the mri of the head,” in Information Science and Technology
(CiSt), 2016 4th IEEE International Colloquium on, pp. 422–427, IEEE,
2016.
[22] N. Deo, Graph theory with applications to engineering and computer
science. Courier Dover Publications, 2017.
[23] H. Lin, C. Huang, W. Wang, J. Luo, X. Yang, and Y. Liu, “Measuring
interobserver disagreement in rating diagnostic characteristics of
pulmonary nodule using the lung imaging database consortium and
image database resource initiative,” Academic Radiology, vol. 24, no. 4,
pp. 401–410, 2017.
[24] S. Jeevakala et al., “Sharpening enhancement technique for mr images to
enhance the segmentation,” Biomedical Signal Processing and Control,
vol. 41, pp. 21–30, 2018.