Segmentations of medical images are required in a number of medical applications such as quantitative analyses and patient-specific orthotics, yet accurate segmentation without significant user attention remains a challenge. This work presents a novel segmentation algorithm combining the region-growing Seeded Cellular Automata with a boundary term based on an edge-detected image. Both single processor and parallel processor implementations are developed and the algorithm is shown to be suitable for quick segmentations (2.2？s for 2 5 6 × 2 5 6 × 1 2 4 voxel brain MRI) and interactive supervision (2–220？Hz). Furthermore, a method is described for generating appropriate edge-detected images without requiring additional user attention. Experiments demonstrate higher segmentation accuracy for the proposed algorithm compared with both Graphcut and Seeded Cellular Automata, particularly when provided minimal user attention. 1. Introduction Segmentation, also known as labeling, of medical images is an important task for quantitative analyses, custom intervention planning such as localized radiotherapy, and design of patient-specific tools such as orthotics or jigs for joint replacement. Manually labeling images takes a prohibitive amount of time due to the large number of voxels in most medical images, while autonomous segmentations can fail to reach the required accuracy due to interpatient morphological variability. Supervised segmentation algorithms are a promising solution because they allow the user to guide the segmentation without requiring the user’s attention for each voxel. Popular supervised segmentation algorithms include active contours (snakes) [1], Level Sets [2], intelligent scissors (live wire) [3, 4], Graphcut [5], and to some degree Seeded Cellular Automata (SCA) [6]. For active contours and Level Sets, the user initializes the boundary near the desired contour and the algorithm moves the boundary to a local minimum determined by an energy functional. This approach requires that the user solve two optimization problems: setting the impact of the terms in the functional, and placing the initial boundary such that the results settle into a desirable minimum [7]. Intelligent scissors connect-the-dots between user-placed boundary points, but either image noise or inaccurate placement of those points can generate inaccurate segmentations. Graphcut uses graph-based operations to separate user-placed “seeds” so as to satisfy the max-flow/min-cut theorem, but demonstrates a bias toward small segmentations and is inherently a two-label approach (with
References
[1]
M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: active contour models,” International Journal of Computer Vision, vol. 1, no. 4, pp. 321–331, 1988.
[2]
D. Cremers, M. Rousson, and R. Deriche, “A review of statistical approaches to level set segmentation: integrating color, texture, motion and shape,” International Journal of Computer Vision, vol. 72, no. 2, pp. 195–215, 2007.
[3]
E. N. Mortensen and W. A. Barrett, “Interactive segmentation with intelligent scissors,” Graphical Models and Image Processing, vol. 60, no. 5, pp. 349–384, 1998.
[4]
A. X. Falcao, J. K. Udupa, S. Samarasekera, S. Sharma, B. E. Hirsch, and R. D. A. Lotufo, “User-steered image segmentation paradigms: live wire and live lane,” Graphical Models and Image Processing, vol. 60, no. 4, pp. 233–260, 1998.
[5]
Y. Boykov and V. Kolmogorov, “An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124–1137, 2004.
[6]
C. Kauffmann and N. Piché, “Seeded ND medical image segmentation by cellular automaton on GPU,” International Journal of Computer Assisted Radiology and Surgery, vol. 5, no. 3, pp. 251–262, 2010.
[7]
S. K. Weeratunga and C. Kamath, “An investigation of implicit active contours for scientific image segmentation,” in Visual Communications and Image Processing 2004, vol. 5308 of Proceedings of SPIE, pp. 210–221, January 2004.
[8]
A. K. Sinop and L. Grady, “A seeded image segmentation framework unifying graph cuts and random Walker which yields a new algorithm,” in Proceedings of the 11th IEEE International Conference on Computer Vision (ICCV '07), pp. 1–8, October 2007.
[9]
E. Moschidis and J. Graham, “A systematic performance evaluation of interactive image segmentation methods based on simulated user interaction,” in Proceedings of the 7th IEEE International Symposium on Biomedical Imaging: From Nano to Macro (ISBI '10), pp. 928–931, April 2010.
[10]
R. Adams and L. Bischof, “Seeded region growing,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, no. 6, pp. 641–647, 1994.
[11]
J. Freixenet, X. Munoz, D. Raba, J. Mart, and X. Cuf, “Yet another survey on image segmentation: region and boundary information integration,” Computer Vision-ECCV, vol. 2002, pp. 21–25, 2002.
[12]
S. Even, Graph Algorithms, vol. 606, Computer Science Press, Rockville, Md, USA, 1979.
[13]
R. Bellman, “On a routing problem,” Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87–90, 1958.
[14]
M. Gardner, “Mathematical games: the fantastic combinations of John Conway's new solitaire game ‘life’,” Scientific American, vol. 223, no. 4, pp. 120–123, 1970.
[15]
V. Vezhnevets and V. Konouchine, “Growcut: interactive multi-label ND image segmentation by cellular automata,” in Proceedings of the Graphicon, pp. 150–156, 2005.
[16]
J. Yen, “Algorithm for finding shortest routes from all source nodes to a given destination in general networks,” Quarterly of Applied Mathematics, vol. 27, no. 4, pp. 526–530, 1970.
[17]
E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959.
[18]
U. Meyer and P. Sanders, “Δ-stepping: a parallelizable shortest path algorithm,” Journal of Algorithms, vol. 49, no. 1, pp. 114–152, 2003.
[19]
J. Canny, “A computational approach to edge detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679–698, 1986.
[20]
R. Beasley, “Finding the best edge image,” in Proceedings of the International Conference on Image Processing, Computer Vision, and Pattern Recognition, pp. 504–510, July 2011.
[21]
D. W. Shattuck, G. Prasad, M. Mirza, K. L. Narr, and A. W. Toga, “Online resource for validation of brain segmentation methods,” NeuroImage, vol. 45, no. 2, pp. 431–439, 2009.
[22]
L. Grady and M. Jolly, “Weights and topology: a study of the effects of graph construction on 3D image segmentation,” in Proceedings of the Medical Image Computing and Computer-Assisted Intervention (MICCAI '08), pp. 153–161, 2008.
[23]
J. Siek, L. Lee, and A. Lumsdaine, Boost Graph Library: User Guide and Reference Manual, Addison-Wesley Professional, 2001.
