The random walks (RW) method, which was proposed by Grady [50] in 2006, represents a recent noteworthy development in graph-based image segmentation methods. RW is considered as a diffusion process. In this method, edge weights are considered the probabilities of a walker travelling the edge from one node to a neighbouring node. Given seeds, a pixel can be labelled by comparing the prob-abilities that a walker initiated at that pixel travels to foreground or background seed points.
RW [51, 52] algorithm treats a graph-based interactive image segmentation.
Here, the previously mentioned notation for a graph is also used. A weighted graph assigns a value, i.e., weightwij, to each edgeeij. It was shown in [50] that the random walk probability can be calculated by minimizing the following energy function:
D[p] = 1
2pTLp= 1 2
X
eij∈E
wij(pi −pj)2 (2.16) whereLis the Laplacian matrix that measures the normalized square gradients.
pc = [p1c, p2c, p3c, . . . , pnc], n is the number of pixels ( or nodes) in the image. pic denotes the probability of the pixel ( or node)vi belong to the c-th class.
Compared to the graph cut segmentation algorithm, the RW algorithm does not suffer from the ”small cut” problem because it does not look for the smallest boundary. The diffusion properties of RW avoid segmentation leaking and shrink-ing bias; however, the segmentation boundary may be more strongly affected by seed location than graph cuts. The RW algorithm is explained in detail in Chapter 3.
Bibliography
[1] N. Sharma, L.M. Aggarwal: Automated medical image segmentation tech-niques. Journal of Medical Physics, 35(1)(2010) 3-14.
[2] S.A. Salem, N.V. Kalyankar, S.D Khamitkar: Image Segmentation by Using Threshold Techniques. Journal of computing, 2(5)(2010) 83-85.
[3] J. Kittler, J. Illingworth: Minimum Error Thresholding. Pattern Recognition, 19(1)(1986) 41-47.
[4] F. Samopa, A. Asano: Hybrid Image Thresholding Method using Edge De-tection. International Journal of Computer Science and Network Security, 9(4)(2009) 292-299.
[5] C. Glasbey: An Analysis of Histogram-based Thresholding Algorithms. Graph-ical Models and Image Processing, 55(6)(1993) 532-537.
[6] P. Moallem, N. Razmjooy: Optimal Threshold Computing in Automatic Image Thresholding using Adaptive Particle Swarm Optimization. Journal of Applied Research and Technology, 10(2012) 703-712.
[7] S. Kamdi, R.K. Krishna: Image Segmentation and Region Growing Algorith-m. International Journal of Computer Technology and Electronics Engineering (IJCTEE), 2 (1)(2012) 103-107.
[8] D.M.N. Mubarak, M.M. Sathik, S.Z. Beevi, K. Revathy: A hybrid region grow-ing algorithm for Medical image segmentation. International Journal of Com-puter Science and Information Technology, 4(3)(2012) 61-70.
[9] R. Adams, L. Bischof: Seeded region growing. IEEE Transaction on Pattern Analysis and Machine Intelligence, 16(6)(1994) 641-647.
[10] R. Pohle, K. Toennies: Segmentation of medical images using adaptive region growing. Proc. SPIE on Medical Imaging 2001: Image Processing, 1337, (2001).
[11] V. Grau, A.U. Mewes, M. Alcaniz, R. Kikinis, S.K. Warfield: Improved water-shed transform for medical image segmentation using prior information. IEEE Transactions on Medical Imaging. 23(4) (2004) 447-458.
[12] S. Wegner, T. Harms, H. Oswald, E. Fleck: The watershed transformation on graphs for the segmentation of CT images. Proc. 13th International Conference on Pattern Recognition (ICPR 1996), (1996) 498-502.
[13] J. B. Roerdink, A. Meijster: The Watershed Transform: Definitions, Algo-rithms and Parallelization Strategies. Fundamenta Informaticae, 41(2001) 187-228.
[14] H. Frigui, R. Krishnapuram: A robust competitive clustering algorithm with application in computer vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(1999) 450-465.
[15] A.H. Foruzan, Y.W. Chen, R.A. Zoroofi, A. Furukawa, Y. Sato, M. Hori, N. Momiyama: Segmentation of Liver in Low-contrast Images Using K-Means Clustering and Geodesic Active Contour Algorithms. IEICE Transactions on Information and Systems, E96-D(2013) 798-807.
[16] H.P. Ng, S.H. Ong, K.W.C. Foong, P.S. Goh: Medical Image Segmenta-tion Using K-Means Clustering and Improved Watershed Algorithm. Proc. 2006 IEEE Southwest Symposium on Image Analysis and Interpretation, (2006) 61-65.
[17] Y.W. Chen, K. Tsubokawa, A.H. Foruzan: Liver Segmentation from Low Contrast Open MR Scans Using K-Means Clustering and Graph-Cuts. Lecture Notes in Computer Science, Springer, 6064(2010) 162-169.
[18] N. Sharma, A.K. Ray, S. Sharma, K.K. Shukla, S. Pradhan, L.M. Aggarwal:
Segmentation of medical images using simulated annealing based fuzzy C Mean-s algorithm. International Journal of Biomedical Engineering and Technology, 2(2009) 260-278.
[19] M.N. Ahmed, S.M. Yamany: A modified fuzzy C-means algorithm for bias field estimation and segmentation of MRI data. IEEE Transactions on Medical Imaging, 21(2002) 193-199.
[20] M. Tabakov: A fuzzy segmentation method for Computed Tomography im-ages. International Journal of Intelligent Information and Database Systems, 1(1)(2007) 79-89.
[21] A.P. Dempster, N.M. Laird, D.B. Rubin: Maximum likelihood from incom-plete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1)(1997) 1-38.
[22] O. Ronen, J.R. Rohlicek, M. Ostendorf: Parameter estimation of dependence tree models using the EM algorithm. IEEE Signal Processing Letters, 2(8)(1995) 157-159.
[23] M. Kass, A. Witkin, D. Terzopoulos: Snakes-Active Contour Models. Inter-national Journal of Computer Vision, 1(4)(1988) 321-331.
[24] J.M. Pardo, D. Cabello, J. Heras: A snake for model-based segmentation of biomedical images. Pattern Recognition Letters, 18(1997) 1529-1538.
[25] C. Xu, J.L. Prince: Snakes, Shapes, and Gradient Vector Flow. IEEE Trans-actions on Image Processing, 7(3)(1998) 359-369.
[26] S. Osher, J.A. Sethian: Fronts Propagating with Curvature Dependent Speed:
Algorithms Based on Hamilton-Jacobi Formulations, Journal of Computational Physics, 79(1988) 12-49.
[27] R. Malladi, J.A. Sethian, B.C. Vermuri, Shape modeling with front propa-gation: A level set approach. IEEE Trans. on Pattern Analysis and Machine Intelligence, 17(2)(1995) 158-174.
[28] J. A. Sethian: Level Set Methods and Fast Marching Methods. Department of Mathematics, Cambridge University, Berkeley, 1999.
[29] N. Paragios, R. Deriche: A PDE-based level set approach for detection and tracking of moving objects. Proc. 6th International Conference on Computer Vision, (1998) 1139-1145.
[30] V. Caselles: Geodesic Active Contours. International Journal of Computer Vision, 22(1)(1997) 61-79.
[31] V. Caselles, F. Catte, B. Coll, F. Dibos: A geometric model for active contours in image processing. Numerische Mathematik, 66(1993) 1-31.
[32] S. Kichenassamy, A. Kumar, P. Olver, A. Tannenbaum, A. Yezzi: Gradien-t Flows and GeomeGradien-tric AcGradien-tive ConGradien-tour Models. Proc. of IEEE InGradien-ternaGradien-tional Conference on Computer Vision (ICCV 1995), (1995) 20-23.
[33] N. Paragios, O. Mellina-Gottardo, V. Ramesh: Gradient Vector Flow Fast Geodesic Active Contours. Proc. of IEEE International Conference on Computer Vision (ICCV 2001), 1(2001) 67-73.
[34] R. Goldenberg, R. Kimmel, E. Rivlin, M. Rudzsky: Fast Geodesic Active Contours. IEEE Transactions on Image Processing, 10(10)(2001) 1467-1475.
[35] T. F. Cootes, A. Hill, C. J. Taylor, J.Haslam: The use of active shape mod-els for locating structures in medical images. Image and Vision Computing, 12(6)(1994) 355-366.
[36] T. F. Cootes, G. J. Edwards, C. J. Taylor: Active appearance models. Proc.
European Conference on Computer Vision (ECCV 1998), 2(1998) 484-498.
[37] M.G. Linguraru, J.K. Sandberg, Z. Li, F. Shah, R.M. Summers: Automated segmentation and quantification of liver and spleen from CT images using nor-malized probabilistic atlases and enhancement estimation. International Journal of Medical Physics, 37(2)(2010) 771-783.
[38] H. Park, P.H. Bland, C.R. Meyer: Construction of an abdominal probabilis-tic atlas and its application in segmentation. IEEE Transactions on Medical Imaging, 22(2003) 483-492.
[39] X. Zhou, T. Kitagawa, T. Hara, H. Fujita, X. Zhang, R. Yokoyama, H. Kondo, M. Kanematsu, H. Hoshi: Constructing a Probabilistic Model for Automated Liver Region Segmentation Using Non-contrast X-Ray Torso CT images. Proc.
IEEE International Conference on International Conference for Medical Image Computing and Computer-Assisted Intervention (MICCAI 2006), (2006) 856-863.
[40] T. Okada, R. Shimada, M. Hori, M. Nakamoto, Y.-W. Chen, H. Nakamau-ra, Y. Sato: Automated segmentation of the liver from 3D CT images using probabilistic atlas and multi-level statistical shape model. Journal of Academic Radiology, 63(2008) 1390-1403.
[41] E. Mortensen, W. Barrett. Interactive segmentation with intelligent scissors.
Graphical Models in Image Processing, 60(5)(1998) 349-384.
[42] A. Mishra, A. Wong, W. Zhang, D. Clausi, P. Fieguth: Improved interactive medical image segmentation using Enhanced Intelligent Scissors (EIS). Proc.
IEEE Conference on Engineering in Medicine and Biology Society (EMBC2008), (2008) 3083-3086.
[43] A.X. Falcao, J.K. Udupa, S. Samarasekera, S. Sharma, B.E. Hirsch, R.de A.
Lotufo: User-steered image segmentation paradigms: Live wire and live lane.
Graphical Models and Image Processing, 60(1998) 233-260.
[44] J. Shi, J. Malik: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8)(2000): 888-905.
[45] F. Sun, J.P. He: A Normalized Cuts Based Image Segmentation Method.
Proc. Second International Conference on Information and Computing Science, 2(2009) 333-336.
[46] E. Regentova, D.S. Yao, S. Latifi: Image segmentation using Ncut in the wavelet domain. International Journal of Image and Graphics, 6(4)(2006), 569-582.
[47] Y. Boykov, M.P. Jolly: Interactive graph cuts for optimal boundary and re-gion segmentation of objects in N-D images. IEEE International Conference on Computer Vision (ICCV 2001), 1(2001) 105-112.
[48] Y. Boykov: Graph Cuts and Efficient N-D Image Segmentation. International Journal of Computer Vision, 70(2)(2006) 109-131.
[49] A. Afifi, T. Nakaguchi: Liver Segmentation Approach Using Graph Cuts and Iteratively Estimated Shape and Intensity Constraints. IEEE International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI 2012), (2012) 396-403.
[50] L. Grady, G. Funka-Lea: Multi-Label Image Segmentation for Medical Ap-plications Based on Graph-Theoretic Electrical Potentials. IEEE International Conference on Computer Vision and Mathematical Methods in Medical and Biomedical Image Analysis (ECCV 2004), 3117(2004) 230-245.
[51] L. Grady: Random Walks for Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(11)(2006) 1768-1783.
[52] A.K. Sinop, L. Grady: A Seeded Image Segmentation Framework Unifying Graph Cuts And Random Walker Which Yields A New Algorithm. IEEE Inter-national Conference on Computer Vision (ICCV 2007), (2007) 1-8.
Chapter 3
Efficient Interactive Segmentation Algorithm of Multi-Organ based on Random Walks
3.1 Introduction
As described in Chapter 1, organ segmentation from CT volume is an important prerequisite for surgery planning, computer aided surgery, computer assisted in-tervention and image guided surgery. However, it is difficult to accurately segment the organ via a completely automatic method due to large shape variations, image modality, organ type and non-homogenous textures of abnormal organ. In recent years, interactive techniques have been gaining popularity for medical image seg-mentation because they permit the targeted extraction of objects of interest with minimal guidance. The popular interactive image segmentation is a graph cuts (GC) approach [1, 2, 3, 4, 5]. However, the most serious drawback with the GC method is the ”small cuts” behavior [6, 7] between user-specified seed groups. The reason is that graph cuts try to minimize the total edge weights in the cut, re-sulting in a tendency to find the minimum cut that barely encloses the seeds in situations where the desired boundary takes a ”shortcut” over a protruded section of the object with minimal boundary length.
The random walks (RW) algorithm [8, 9, 10, 11, 12] represents a recent note-worthy development in the graph-based interactive segmentation methods. Since the random walk algorithm is not seeking the smallest boundary, as noted in [11], it does not suffer from this ”small cuts” problem. Furthermore, the solution ob-tained by the random walks approach is guaranteed to be unique, by the uniqueness principle for harmonic functions [8], while the minimum boundary cost criterion of max-flow/min-cut may have multiple solutions. Grady et al. [8, 9] also have
proved that the random walks algorithm has a potential application in segment-ing 3D medical image. Most recently, a segmentation approach that combined RW and regional intensity priors was proposed in [11], the sparse linear equations can be addressed by the preconditioned conjugate gradient to achieve an accept-able memory consumption and easy parallelization. In [12], the computational demands with RW is alleviated by introducing an ”offline” precomputation before user interaction with RW in real-time (i.e., ”online”). Using a similar principle, an offline precomputation was used to further speed up the online segmentation in [13]. Both methods used the ”offline” and ”online” strategies to minimize the time spent waiting. On a different note, Lai et al. [14] extended a random walk method for 3D models by using a two-pass method (coarse-scale seeding and fine-scale seeding) to overcome the high computational requirements, while the computa-tion time increases linearly with the number of seeds. Wang et al. [15] presented a geometrical multigrid approach that efficiently reduces the calculation errors in all frequency ranges. However, whenever the image had large gray value differences on the object boundary, this multigrid method converged slowly with the basic configuration.
Applying the random walks algorithm directly to 3D medical image segmen-tations, we faced the following three problems: (1) Due to the larger number of voxels that exist in 3D medical images, the constructed graph became much larger than ones from 2D images, thus the computation time and memory usage would dramatically increase. (2) Since the number of unlabeled pixels or voxels in a 3D volume is very large compared with the limited number of seed points (boundary conditions), the solutions obtained by random walks will be unstable and the seg-mentation accuracy will be significantly decreased as the number of slices increase.
It is a challenge to use a RW-based algorithm to segment 3D medical images inter-actively. (3) Even though some extended technologies have already been proposed, most RW-based algorithms focused on the segmentation of a single organ.
Therefore, a knowledge-based framework for organ segmentation in a slice-by-slice manner is proposed based on random walks, has the benefits: (1) Small-scale graph; (2) Automation of slice segmentation according to the prior knowledge of already segmented slices. Our strategy is to employ the previous segmented slice to achieve a prior knowledge (shape and intensity knowledge) of the organ for automatic segmentation of the adjacent slice. With a small number of user-defined seed points, we can obtain the segmentation results of the start slice in the volume which can be used as the prior knowledge of the segmented organ. According to this intensity knowledge, the thresholded image can be generated by discarding some probability values in a Gaussian mixture model (GMM), which can remove the noise and non-object parts. Furthermore, the object/background seeds are automatically selected by integrating a narrow band threshold (NBT) method
with the shape knowledge. Finally, a combinatorial random walker algorithm is applied to automatically segment the whole volume in a slice-by-slice manner.
Meanwhile, we extended this proposed method to segment multiple organs si-multaneously. The main difference with previously proposed method is to select and segment two start slices interactively and then segment other remaining slices automatically based on the segmented two start slices. Compared with 3D seg-mentation methods using the conventional random walks, the advantages of our proposed method are summarized as following:
(1). By using a slice-by-slice manner, we can significantly reduce the graph scale, resulting in a significant reduction in computational.
(2). By using the prior knowledge (intensity and shape knowledge) of the segmented slice, we can significantly improve the segmentation accuracy and com-putation time using a limited number of seed points.
(3). By choosing two start slices: one slice in which the liver has the relative larger cross section and another slice in which the spleen has the relative larger cross section on the axial plane, we can segment multiple organs (liver and spleen) simultaneously.