In this article, we present a graph-based method using a cubic template for volumetric segmentation of vertebrae in magnetic resonance imaging (MRI) acquisitions. The user can define the degree of deviation from a regular cube via a smoothness value Δ. The Cube-Cut algorithm generates a directed graph with two terminal nodes (s-t-network), where the nodes of the graph correspond to a cubic-shaped subset of the image’s voxels. The weightings of the graph’s terminal edges, which connect every node with a virtual source s or a virtual sink t, represent the affinity of a voxel to the vertebra (source) and to the background (sink). Furthermore, a set of infinite weighted and non-terminal edges implements the smoothness term. After graph construction, a minimal s-t-cut is calculated within polynomial computation time, which splits the nodes into two disjoint units. Subsequently, the segmentation result is determined out of the source-set. A quantitative evaluation of a C++ implementation of the algorithm resulted in an average Dice Similarity Coefficient (DSC) of 81.33% and a running time of less than a minute.
References
[1]
Joaquim AF, Sansur CA, Hamilton DK, Shaffrey CI (2009) Degenerative lumbar stenosis:update. Arquivos de Neuro-Psiquiatria, vol. 67(2B), 553–558.
[2]
Weinstein JN, Lurie JD, Tosteson TD, Hanscom B, Tosteson AN, et al. (2007) Surgical versus nonsurgical treatment for lumbar degenerative spondylolisthesis. N Engl J Med. 2007 May 31 356(22): 2257–70. doi: 10.1056/nejmoa070302
[3]
Miao J, Wang S, Wan Z, Park WM, Xia Q, et al. (2012) Motion characteristics of the vertebral segments with lumbar degenerative spondylolisthesis in elderly patients. Eur Spine J. 2013 Feb 22(2): 425–31 doi: –––10.1007/s00586–012–2428–3. Epub 2012 Aug 15.
[4]
Chen MYM, Pope TL, Ott DJ (2010) Basic Radiology. Trade paperback, McGraw-Hill Medical Publishing 2nd ed. 396 pages ISBN-13: 9780071627085.
[5]
Drake R, Vogl AW, Mitchell AWM (2009) Gray's Anatomy for Students. Churchill Livingstone, 2nd ed. 1136 pages, ISBN 9780443069529.
[6]
Michopoulou SK, Costaridou L, Panagiotopoulos E, Speller R, Panayiotakis G, et al. (2009) Atlas-based segmentation of degenerated lumbar intervertebral discs from MR images of the spine. IEEE Trans Biomed Eng 56(9): 2225–31. doi: 10.1109/tbme.2009.2019765
[7]
Shi R, Sun D, Qiu Z, Weiss KL (2007) An efficient method for segmentation of MRI spine images. IEEE/ICME International Conference on Complex Medical Engineering, CME, IEEE Press. 713–717.
[8]
Huang SH, Chu YH, Lai SH, Novak CL (2009) Learning-based vertebra detection and iterative normalized-cut segmentation for spinal MRI. IEEE Trans Med Imaging 28(10): 1595–605. doi: 10.1109/tmi.2009.2023362
[9]
Peng Z, Zhong J, Wee W, Lee JH (2005) Automated Vertebra Detection and Segmentation from the Whole Spine MR Images. Conf Proc IEEE Eng Med Biol Soc 3: 2527–30. doi: 10.1109/iembs.2005.1616983
[10]
Carballido-Gamio J, Belongie SJ, Majumdar S (2004) Normalized cuts in 3-D for spinal MRI segmentation. IEEE Trans Med Imaging 23(1): 36–44. doi: 10.1109/tmi.2003.819929
[11]
Egger J, Kapur T, Dukatz T, Kolodziej M, Zuki？ D, et al. (2012) Square-Cut: A Segmentation Algorithm on the Basis of a Rectangle Shape. PLoS ONE 7(2): e31064 doi:10.1371/journal.pone.0031064.
[12]
Klinder T, Wolz R, Lorenz C, Franz A, Ostermann J (2008) Spine segmentation using articulated shape models. Medical Image Computing and Computer- Assisted Intervention (MICCAI), Metaxas D, Axel L, Fichtinger G, Szekely G, eds. vol. 5241 of Lecture Notes in Computer Science, Springer Press. 227–234.
[13]
Hoad CL, Martel AL (2002) Segmentation of MR images for computer-assisted surgery of the lumbar spine. Physics in Medicine and Biology 47(19): 3503. doi: 10.1088/0031-9155/47/19/305
[14]
？tern D, Vrtovec T, Pernus F, Likar B (2011) Segmentation of vertebral bodies in CT and MR images based on 3D deterministic models. Proc SPIE Medical Imaging, Summers RM, van Ginneken B, eds. volume 7963.
[15]
Aslan MS, Ali A, Farag AA, Rara H, Arnold B, et al. (2010) 3D Vertebral Body Segmentation Using Shape Based Graph Cuts. Pattern Recognition (ICPR), 2010 20th International Conference on, 3951–3954.
[16]
Weese J, Kaus M, Lorenz C, Lobregt S, Truye R, et al. (2001) Shape constrained deformable models for 3D medical image segmentation. Information Processing in Medical Imaging, Insana M, Leahy R, eds. vol. 2082 of Lecture Notes in Computer Science, Springer Press. 380–387.
[17]
Yao J, O’Connor SD, Summers RM (2006) Automated spinal column extraction and partitioning. 3rd IEEE International Symposium on Biomedical Imaging: Nano to Macro, IEEE Press. 390–393.
[18]
Ghebreab S, Smeulders AW (2004) Combining strings and necklaces for interactive three-dimensional segmentation of spinal images using an integral deformable spine model. IEEE Transactions on Biomedical Engineering 51(10): 1821–1829. doi: 10.1109/tbme.2004.831540
[19]
Zuki？ D, Vlasák A, Dukatz T, Egger J, Horinek D, et al. (2012) Segmentation of Vertebral Bodies in MR Images. 17th International Workshop on Vision, Modeling and Visualization (VMV), The Eurographics Association, 135–142.
[20]
Zuki？ D, Vlasák A, Egger J, Ho？ínek D, Nimsky C, et al. (2014) Robust Detection and Segmentation for Diagnosis of Vertebral Diseases using Routine MR Images. Computer Graphics Forum, March 2014.
[21]
Kelm BM, Zhou SK, Suehling M, Zheng Y, Wels M, et al. (2010) Detection of 3D spinal geometry using iterated marginal space learning. MCV'10 Proceedings of the 2010 international MICCAI conference on Medical computer vision: recognition techniques and applications in medical imaging, Springer, ACM, 96–105.
[22]
Zou KH, Warfield SK, Bharatha A, Tempany CMC, Kaus MR, et al. (2004) Statistical Validation of Image Segmentation Quality Based on a Spatial Overlap Index: Scientific Reports. Academic Radiology 11(2): 178–189. doi: 10.1016/s1076-6332(03)00671-8
[23]
Sampat MP, Wang Z, Markey MK, Whitman GJ, Stephens TW, et al. (2006) Measuring intra- and inter-observer agreement in identifying and localizing structures in medical images. IEEE Inter Conf Image Processing, 4 pages.
[24]
Schwarzenberg R, Kapur T, Wells W, Nimsky C, Freisleben B, et al. (2012) Graph-Based Vertebra Segmentation Using a Cubic Template. In: 5th NCIGT and NIH Image Guided Therapy Workshop, Boston, page 44.
[25]
Schwarzenberg R, Freisleben B, Kikinis R, Nimsky C, Egger J (2013) [A Cube-Based Approach to Segment Vertebrae in MRI-Acquisitions]. In: Proceedings of Bildverarbeitung für die Medizin (BVM), Springer Press, 69–74, Heidelberg, Germany, March 2013.
[26]
Egger J, Freisleben B, Nimsky C, Kapur T (2012) Template cut: A Pattern-based Segmentation Paradigm. Scientic Reports, Nature Publishing Group (NPG), vol. 2(420), 1–8.
[27]
Egger J, Bauer MHA, Kuhnt D, Carl B, Kappus C, et al. (2010) Nugget-Cut: A Segmentation Scheme for Spherically- and Elliptically-Shaped 3D Objects. 32nd Annual Symposium of the German Association for Pattern Recognition (DAGM), LNCS 6376, Springer Press. 383–392.
[28]
Egger J, Freisleben B, Setser R, Renapuraar R, Biermann C, et al. (2009) Aorta Segmentation for Stent Simulation. 12th International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI), Cardiovascular Interventional Imaging and Biophysical Modelling Workshop, 10 pages.
[29]
Egger J, O’Donnell T, Hopfgartner C, Freisleben B (2008) Graph-Based Tracking Method for Aortic Thrombus Segmentation. Proceedings of 4th European Congress for Medical and Biomedical Engineering, Engineering for Health, Springer Press. 584–587.
[30]
Bauer MHA, Egger J, O’Donnell T, Freisleben B, Barbieri S, et al. (2010) A Fast and Robust Graph-based Approach for Boundary Estimation of Fiber Bundles Relying on Fractional Anisotropy Maps. In: 20th International Conference on Pattern Recognition (ICPR), Istanbul, Turkey, IEEE Computer Society, 4016–4019, August 2010.
[31]
Egger J, Penzkofer T, Kapur T, Tempany C (2012) Prostate Central Gland Segmentation Using a Spherical Template Driven Graph Approach. In: 5th NCIGT and NIH Image Guided Therapy Workshop, Boston, Page 43, September 2012.
[32]
Egger J (2013) PCG-Cut: Graph Driven Segmentation of the Prostate Central Gland. PLoS One. 2013; 8(10): e76645. Epub 2013 Oct 11.
[33]
Egger J, Lüddemann T, Schwarzenberg R, Freisleben B, Nimsky C (2014) Interactive-Cut: Real-Time Feedback Segmentation for Translational Research. Comput Med Imaging Graph. Available online 11 February 2014.
[34]
Egger J, Colen R, Freisleben B, Nimsky C (2011) Manual Refinement System for Graph-Based Segmentation Results in the Medical Domain. J Med Syst. 2012 Oct; 36(5):2829–39. Epub 2011 Aug 9.
[35]
Egger J, Kappus C, Freisleben B, Nimsky C (2011) A Medical Software System for Volumetric Analysis of Cerebral Pathologies in Magnetic Resonance Imaging (MRI) Data. J Med Syst. 2012 Aug; 36(4):2097–109. Epub 2011 Mar 8.
[36]
Boykov Y, Kolmogorov V (2004) An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. IEEE Transactions on Pattern Analysis and Machine Intelligence 26(9): 1124–1137. doi: 10.1109/tpami.2004.60
[37]
Greig D, Porteous B, Seheult A (1989) Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, Series B, vol. 51(2), 271–279.
[38]
Li K, Wu X, Chen DZ, Sonka M (2006) Optimal surface segmentation in volumetric images – a graph-theoretic approach. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 28, 119–134.
[39]
Veksler O (2008) Star Shape Prior for Graph-Cut Image Segmentation: European Conference on Computer Vision 2008, (ECCV'08).
[40]
Vezhnevets V, Konouchine V (2005) GrowCut - Interactive Multi-Label N-D Image Segmentation. Proc. Graphicon. 150–156.
[41]
Egger J, Kapur T, Nimsky C, Kikinis R (2012) Pituitary adenoma volumetry with 3DSlicer. PLoS ONE 2012 7(12): e51788. doi: 10.1371/journal.pone.0051788
[42]
Egger J, Kapur T, Fedorov A, Pieper S, Miller JV, et al. (2013) GBM Volumetry using the 3D Slicer Medical Image Computing Platform. Sci Rep., Nature Publishing Group (NPG), 2013; 3:1364. Epub 2013 March 4.
[43]
Egger J, Kappus C, Carl B, Nimsky C (2013) GrowCut-Based Vertebral Body Segmentation with 3D Slicer. In: Jahrestagung der Sektion Wirbels？ule der Deutschen Gesellschaft für Neurochirurgie (DGNC), Frankfurt am Main, Germany, Poster 24, September 2013.
