A NOVEL GRAPH CUTS BASED LIVER SEGMENTATION METHOD

A NOVEL GRAPH CUTS BASED LIVER SEGMENTATION METHOD Hongzhe Yang, Yongtian Wang, Jian Yang, Yue Liu School of Optoelectronics, Beijing Institute of Technology, Beijing 100081, China ABSTRACT This paper presents a novel liver segmentation method based on the fast marching and graph cuts methods. The algorithm is composed of three main steps: first, rough edge of the liver is extracted from the CT image by fast marching method. Second, hard constrain of the foreground and background which is used for initial calculation of graph cut is obtained by mathematical morphology method. Third, based on the former calculation, the graph cuts are utilized to refine the segmentation boundary of the liver. The developed method greatly reduces the complexity of the commonly used graph cuts methods, which can obtain the hard constrains automatically. Also, the developed method reduces the dependence of empirical parameters of the fast marching based method. Experimental results show that the developed method is very effective for the segmentation of liver from CT images. 1. INTRODUCTION Medical image segmentation [1] is process of separating a given anatomical structure from medical images. Liver image segmentation is important for the diagnosis of liver. It is the basis of the liver image processing operations, and plays a significant role for the subsequent image matching, blood vessels and tumor model of three-dimensional reconstruction, model visualization, and diagnosis. Traditional method of using manual segmentation organ borders spends doctor a lot of time when dealing with a large number of medical images. And process is more complicated and inaccurate. Researchers carried out extensive research for medical image segmentation. Active contour model, regional-based and graph cuts are three representative technology of image segmentation. Snake method [2] of geometric active contour model and Level set method [3] of parameters of active contour model is the classical model-based approach. Elastic deformation force is used to initialize contour near to edges; it can reach the edges of detective objects when the energy gets minimum. Subsequently, many scholars propose various improved models, such as: balloon snake [4], Topology snake [5], Distance snake [6], Geodesic active contours [7], GVF [8], fast marching methods [9]. Graph cut segmentation [10, 11] using the theory of object / background segmentation. It attracts more attention for its user-interactive and more accurate than simply automatic segmentation. Blake etc. (Grab-cuts) [12] mixed Gaussian model based on clues with Graph cuts to improve the interaction region. Li etc. (Lazy snapping) view region as a node using watershed, and apply the super-pixel method of cutting and so on. Although these methods are powerful and effective in segmentation, they still have some shortcomings, and fail in some cases: (1) since the stopping term of the deformation evolution depends on the image gradient flow being approximately zero, this often forces the contours to stop several pixels away from desired boundary. Thus, the active contour sometimes does not match the boundary of the structure accurately; especially in regions steep curvature and low gradient values. (2) The choice of elastic parameters and energy function minimization with numbers of minimum (regional local minimum) are seriously affecting the accuracy of segmentation results. (3) The region-based segmentation detects edges by processing each pixel value. So results are usually accurate, but computational cost is great at the same time. (4) Currently, most of the methods require manual initialization. In the contour model and graph cut, when dealing with a large number of medical images, manual initialization is unrealistic; and manually initialization is cumbersome during processing close neighboring objects. In this paper, we propose a new segmentation method using mathematical morphology that combines fast marching and graph cuts algorithm. The main idea of semi-automatic liver segmentation algorithm is a combination of rapid effectiveness of fast marching method and accuracy of user interaction of graph cuts method. This improved algorithm reduces the attempt times of fast marching’s parameter settings and reduces tedious process of manually specify the hard constraints of the graph cuts segmentation. Implementation of the results indicates that the new segmentation method is relatively rapid and effective. Section Ⅱ describes the model of semi-automatic liver segmentation method which is combined with the fast marching and graph cuts by mathematical morphology. Experimental results and analysis are given in Section Ⅲ. Section Ⅳ contains conclusions. 2010 International Conference of Medical Image Analysis and Clinical Application (MIACA) 978-1-4244-8012-8/10/$26.00 ©2010 IEEE 50 2. DESCRIPTION OF THE MODEL Semi-automatic liver segmentation algorithm includes three stages: (1) the medical image anisotropic filtering to reduce image noise. Segmentation filtered image by fast marching to get the rough liver edge. (2) The rough edges changed by Mathematical morphology, will be the graph cut’s "hard constraints." (3) According to the selection of "hard constraint" of the "Foreground / background" and the energy function, the establishment of network flow model will be create to calculate cutting set. As Fig.1 shows. Fig1.Flowchart of Hybrid segmentation 2.1. Exact Fast Marching Rough Edges Pre-processing the original medical image should be used to filter noises and other high-frequency mutations in the region. Gradient anisotropic diffusion filtering is a good choice because it reduced noise and texture but preserves , and also enhance, edges. Fast marching method is a fast algorithm of level set. It’s employed a user-defined seed for initialization, instead of the user-defined hard constraints of graph cuts. And it has the advantages of speed which is suitable for extracting initial edge from the initial image. Thus, using fast marching extracted medical image ROI (liver area) edge. 2.2. Assign “Foreground/Background” with Mathematical Morphology Method Then using mathematical morphology to reduce connectivity between ROI and neighboring tissues. Recursively dilate the binary edge image which is created with fast marching method, using a structuring element set (eg: a 3*3 template), in order to reduce the ROI (liver) internal noise points and small blood vessels and ensure the dilated image include ROI (liver area) region. View anti-dilated image with the entire image as the "Background"; then, recursively erode the dilated image in order to reduce inaccurate edge which is extracted by fast marching , until the ROI is completely seperated from the neighboring tissues, assign it as "Foreground". We define 2-D image F as Fast Marching segmentation result. E()，D() is defined, respectively, as the image erosion and dilation operation. ， is the complement of cE cD erosion and dilation. For liver images, the set F of all pixels constitute a complete description of medical images, Define a structure element set S，move S in F. Corrosion operator E(F)for the contraction object boundary point， dilation operator D(F) for the expansion of object boundary. Recursive dilation and recursive erosion defined below are based on two basic operations. Recursive erosion ⎪⎩ ⎪⎨ ⎧ ≥⊗⊗ ==⊗= − 0 if ,)( 0 if , )( 1 iSSF iF SFFE i i (1) Recursive dilation ⎪⎩ ⎪⎨ ⎧ ≥⊕⊕ ==⊕= − 0 if ,)( 0 if , )( 1 iSSF iF SFFD i i (2) According to different circumstances of fast marching results, select different methods of mathematical patterns. "Hard constraints" of the “Foreground/ Background" selection patterns are based on the following modes TABLE I. SELECTION MODES case “Foreground” “Background” F is part of ROI ( )FE )(FEc is “uncertain”， “Background” belong to “uncertain” F include ROI & complement of ROI )(FD is “uncertain”, “Foreground” belong to “uncertain” complement of )(FDc F is similar with edge ( )FE complement of )(FDc F is similar with edge, but have noise& holes ))(( FDE complement of )(FDc 2.3. Graph cuts with Pre-segmentation Graph cuts segmentation need user to specify a small number of pixels as hard constraints by the user-interaction. “Object” as the “Foreground” of image segmentation and other specified parts of the image as a "Background." According to Section 3.2, assuming that Dilation / Erosion obtained, they are, respectively, defined the image "Foreground" and "Background" pixel subset. And, graph cut need to meet the hard constraints as follows: Foregroundp∈∀ , （3） ""objAp = Backgroundp∈∀ ， （4） ""bkgAp = An energy function E is defined so that its minimum should correspond to a good segmentation. Image segmentation turn to calculate the global minimum of energy function (8) satisfying the constraints. Gradient Anisotropic Diffusion Edge Dilation Construct Graph Assign “Foreground /Background” Edge Erosion Input image Fast marching Output Graph Cuts Segmentation Output image Fast Marching Segment 51 ( ) ( ) ( ) ( )∑∑ ∈∈ += Nqp qpqpPp pp LLVLDLE , , , (5) The data term D evaluates the fit of the opacity distribution Lp to the p, is defined to be: ( ) ( )pppp LIPLD |ln−= (6) The smoothness term can be written as ( ) ( )qpdis II V qpqp , 1 2 exp 2 2 , ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ −−∝ σ (7) According to (9), (10), Construct the graph G with weight. An s-t cut is subset edges C such that the “Foreground” and ”Background ” become completely separated on the induced graph G(C). 3. EXPERIMENTAL RESULTS We demonstrate our segmentation method on several generic examples. Images collected from the liver CT scan images of Beijing 301 Hospital. （a） （b） Fig2.（a）from left to right followed by results of Graph cuts exaction, Fast marching rough Segmentation and new method （b）shows details of (a) Experiments on actual medical images are carried to demonstrate the performance of the proposed segmentation method. An image of 512*512 pixels is taken. Segmentation result using Graph cuts for user interact twice is presented in Fig.2 (a) left, where bottom of live is exacted successfully while upper right is fuzzy, and white area is not exacted. (a) middle image shows the segmentation process of fast marching for evaluate parameters. Sigma is 0.1, Sigmoid Alpha is -0.1, Sigmoid Beta is 50, Time Threshold is 80, StoppingValue80. The bottom is not accurate because it is difficult to satisfy the upper right slim area and the bottom adhesion area at the same time. In (a) right, we can see that the new method obtain a relatively satisfactory segmentation result. Edge is smooth and the white area is removed. (b) shows the details of (a). To compare the hybrid method with the existing methods, we choice absolute error rate as comparison criteria. Ideally, the pixels number of the ROI N depends on manual segmentation result. In fig.2, liver of manual segmentation is 2828 pixels. Defined, ne represent wrong pixel numbers. Segmentation results regard it is ROI, but it is outside the ROI in fact. nm represent missing pixel numbers, which should be in the ROI. Absolute error rate of segmentation method is re, absolute missing rate is rm. %100×= N nr ee (8) %100×= N n r mm (9) TABLE II. WRONG PIXELS AND WRONG RATE COMPARISON USING DIFFERENT SEGMENTATION METHODS WITH FIG.2 Case Graph Cuts Fast Marching New method Error pixels 252 724 46 Missing pixels 0 16 0 Error rate 0.089 0.25 0.016 Missing rate 0 0.05 0 So, the numbers of wrong pixels and absolute wrong rate comparison using graph cuts, fast marching rough segmentation, and hybrid method shows in tableⅡ. (a) (b) (c) Fig.3 （a）from left to right followed by 37, 39, 43 slice of CT image（b）Fast marching rough segmentation （c）new method segmentation It was found that the fast marching algorithm is great influenced by parameters settings. In order to get the accurate results, we often try multiple times to get suitable parameters settings. In Fig.3, (a) shows original CT image. Example for 37 slices, the liver is similar with abdominal wall adhesion in intensity, and high junctions, so liver and abdominal wall is more difficult to segmentation accurately. (b) Fast marching can be segmented to be satisfactory results in other parts, but for in the bottom left corner there is excess part of the liver. This as a coarse fast marching segmentation for evaluate parameters, new method can effectively reduce the left connective part for only once segmentation. Times of user interaction are greatly reduced. 52 (c) shows a satisfied result of developed method, and effectively reduce the parameters for dependence of the experience. We analysis experimental results: the more accurate pre-segmentation by fast marching is, the more effective corresponding live segmentation received. In most case, connectivity between the ROI and the neighboring tissues may be heavily reduced by using recursive erosion and increased by using recursive dilation. However, in the case those large areas between ROI and the neighboring tissues are connected or disconnected, recursive erosion and dilation is ineffective. For (c) right, 43th slice, the liver has narrow part in the upper right corner, which is closely connected with the surrounding tissues. The edge coarse segmentation of fast marching method does not expand into the slit, during using the 3 * 3 templates corrosion circumstances. This part does not be assigned to the correct label (also not properly be designated in the future), so this part of the split did not accurately segmentation for the first segmentation. In order to deal with this problem, the template size of mathematical morphological operation can be increased to expand the dilated region, correspondingly, this process increase the operating costs; or increase the “uncertain” area; or increase user interaction during the Graph cut segmentation. 4. CONCLUSION Fast marching algorithm is fast and effective, but sometimes not accurate enough at the edges, and the parameter settings need to have some empirical. Graph cut has attracted the attention of many researchers in recent years, because of its algorithm combines hard constraints with soft constraints of image region and the edge. It maintains both the image edge and region information, allows user specifying the image interaction "Foreground/Background", and obtains more accurate segmentation results. We use mathematical morphology to combine two segmentation methods. Experimental results show that the developed method is very effective for the segmentation of liver from CT image. Fast marching is used as image preprocessing algorithm, so it doesn't need very accurate segmentation results, so long as they can specify "Foreground" and "Background". Thus, reduce the complication for setting parameters. At the same time, the method reduce manual specifies process of "hard constraints". Greatly reduce complexity of manual processing a large number of medical images during the actual medical diagnosis. And comparing with other relatively simple way to specify the initialization, it can get a more accurate initialization of hard constraints so that obtaining more accurate segmentation result, reduce interaction times. The limitation of the approach is that fast marching rough segmentation impacts the final image segmentation results. When the pre-segmentation image has a larger loss of some important parts, the final segmentation image will not come back up. For these shortcomings, future work will be further improved. ACKNOWLEDGMENT The authors would like to thank Dr. Tong Lu of the PLA Hospital, Beijing for providing the data sets used in the experiments. This work was supported in part by the National Basic Research Program of China (2010CB732505), in part by National Science Foundation Program of China (60902103) and in part by the Innovation Team Development Program of the Chinese Ministry of Education (IRT0606). REFERENCES [1] H.Zaidi, “Medical image segmentation: Quo Vadis”, Compt. Meth.Programs Biomedcine, Vol.84, pp 63-65, 2006. [2] M.Kass, A.Witkin, D.Terzopoulos, “Snakes:active contour models”, Int.J.Comput, Vol.1(4), pp.211-218, 1988. [3] R.Malladi, J.Sethian, B.Vemuri, “Shape modeling with front progagation”, IEEE Trans.Pattern Anal.Machine Intell, Vol.17(2), pp.158-171, 1995. [4] L.Cohen, “On active contour models and balloons”, CVGIP Image Understand, Vol.52(2), pp.211-218, 1991. [5] T. McInerney, D. Terzopoulos, “T-snakes: topologically adaptive snakes”, Med. Image Anal. Vol.4(2), pp.73–91, 2000. [6] L. Cohen, I. Cohen, “Finite element methods for active contour models and balloons for 2-D and 3-D images”, IEEE Trans. Pattern Anal. Machine Intell. Vol.15 (11), pp.1131–1147,1993. [7] V. Caselles, R. Kimmel, G. Sapiro, “Geodesic active contours”, Int. J. Comput. Vis, Vol. 22 (1), pp.61–79,1997. [8] C. Xu, J. Prince, “Snakes, shapes, and gradient vector flow”, IEEE Trans. Image Process, Vol.7 (3), pp.359–369,1998. Press, pp.65-72, 2003. [9] A.A. Farag, M.S.Hassouna, “Theoretical Foundations of Tracking Monotonically Advancing Fronts Using Fast Marching Level Set Method”, Technical Report, 2005. [10] Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts”, IEEE Trans. Pattern Anal. Machine Intell, Vol.23(11), pp.1222-1239,2001. [11] Y. Boykov, “Graph cuts and efficient N-D image segmentation”, Int. J. Comput. Vis, Vol.70(2), pp.109-131,2006. [12] C.Rother, V.Kolmogorov, A.Blake, ““GrabCut”-Interactive Foreground Extraction using iterated Graph Cuts”, ACM Trans on Graphics, pp.309-314, 2004. 53 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles false /AutoRotatePages /None /Binding /Left /CalGrayProfile (Gray Gamma 2.2) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Warning /CompatibilityLevel 1.7 /CompressObjects /Off /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /LeaveColorUnchanged /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams true /MaxSubsetPct 100 /Optimize true /OPM 0 /ParseDSCComments false /ParseDSCCommentsForDocInfo false /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo false /PreserveFlatness true /PreserveHalftoneInfo true /PreserveOPIComments false /PreserveOverprintSettings true /StartPage 1 /SubsetFonts false /TransferFunctionInfo /Remove /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true /Arial-Black /Arial-BoldItalicMT /Arial-BoldMT /Arial-ItalicMT /ArialMT /ArialNarrow /ArialNarrow-Bold /ArialNarrow-BoldItalic /ArialNarrow-Italic /ArialUnicodeMS /BookAntiqua /BookAntiqua-Bold /BookAntiqua-BoldItalic /BookAntiqua