Research Of Tumor Image Segmentation Based On Graph Cuts

Medical image segmentation is the technique that divides the image into different regions which have different characteristics or extracts the interested objects from the image. The different regions or objects should be identity with the anatomical structure. Medical image segmentation is a significant and difficult problem in image processing and analyzing.Based on medical image segmentation, the image contents can be better analyzed, which will assist doctors to diagnose correctly. There are a number of factors that cause current segmentation algorithms fail to satisfy the need of clinical practice, including the individual differences in the tissue anatomy; slow calculating speed and inaccuracy; and poor image quality affected by noise, intensive inhomogeneity and partial volume effect(PVE) etc. So the research on medical image segmentation has been an important field in medical image processing and analysis.By far, the field of medical image analysis has developed a variety of automatic segmentation methods to fulfill the difficult problem of medical segmentation. However, the current medical segmentation algorithms still can't satisfy the various demands in clinic and research completely. The reasons causing the above deficient state of the field include poor mathematic model for describing the problem faced in practice, significant difference between different targets to be segmented, degraded medical images due to the imperfectness of the imaging devices, random and complex change of pathological tissue, diverse expectances of the result, and so on. So, there is no such an algorithm of segmentation which is competent for all kinds of the problems. What we can do is to develop different algorithms of segmentation for different problems.Cancer is one of common malignant disease in our country, seriously endangering people's health. As the edge contour of tumor includes abounding characteristic information of tumor pathological changes, clinicians always determine the nature of disease by analyzing the characteristic information of tumor contour. Physicians can make right diagnosis, work out and modify the therapeutic strategy by measuring the shape of the lesion, border, cross-sectional area and volume and analysising these indicators between before and after treatment. So accurate segmentation of tumor has important sense for tumor diagnosis and treatment.However, tumor segmentation is generally considered as a difficult problem, because the tumor has the following characteristics:size, position and shape changed greatly; density may overlap with normal tissues; may has duty effect and penetration effect etc. Analysing of the tumor images characteristics, we can know that it may have complex and fuzzy boundaries, or empty in-house, so the segmentation method is proposed for higher requirements.At present, a number of automatic segmentation techniques for tumor based on image gray level information have been proposed, such as fuzzy clustering, statistical classification, level sets. For the overlap between tumor and normal tissue in the image gray distribution, fuzzy clustering and statistical classification methods based on gray level information can not be always satisfactory. Level set methods have some shortcomings, such as easily falling into local minimum, high requirements on the initialization and sensitivity to the choice of parameters. It is difficult to segment tumor automatically, some interaction information between doctors and segmentation algorithm will greatly improve pertinence and the segmentation accuracy. At present, the semi-automatic tumor segmentation algorithm is given more and more recognition, simple interactive can help segment the tumor quickly and accurately.Graph cut supplies a global optimization strategy, and the graph cut has been given extensive attention in recent years. In the field of computer vision, many problems can be expressed as minimizing the energy function. minimizing the energy function, many of the existing numerical solution algorithm restrained by adjustable parameters only get the local optimal solution. Graph cut provide a better solution ideas for optimization technology. Greig, who first uses graph cut techniques to solve the minimizing energy function problems in computer vision, the basic idea is that each of image pixel is seen as a node of the graph, the graph edges represent the adjacency relationship between image pixels, minimizing the energy function problem is turned into finding the minimum cut of the graph. Graph cut optimization technique can overcome the local minimum shortcoming, in recent years, has been widely used to minimize the energy function in low vision problems, such as image segmentation, image restoration, texture synthesis, image extraction, multi-camera scene rehabilitation etc.According the graph cuts-based image segmentation techniques, an image can be mapped into a weighted undirected graph, image pixels are treated as the graph vertices the visual properties similarity between the adjacent pixels (such as gray level, color or texture) are seen as the corresponding edge weights, so the image segmentation result can be obtained through finding the graph minimal cut. Minimum cut can be obtained by finding the graph maximum flow based on the maximum flow and minimum cut demonstration of Ford and FulkersonIn the past few decades, many new algorithms have been proposed to improve the graph cuts computing performance and reduce the computational complexity, but they still can not reach the requirements of real-time processing. The hardware acceleration is applicated too, a shader based early implementation of graph cuts on the GPU firstly reported by Hussein et al was even slower than the CPU implementation.Compute unified device architecture (CUDA) has freed Computation on the graphic processing unit (GPGPU) technology from the graphics fixed pipeline and high-level shader language, allowing the design and implementation of SIMD(single instruction and multiple data) parallel algorithms on a much more simple way than previous method based on texture rendering. The GPGPU computing architecture provids a similar C language development environment, allows designers direct use the GPU computing resources through C and CUDA programming language to reduce the development complexity and enhance the development efficiency.In this paper, the core concept of CUDA was first studied, then the graph cuts algorithm was redesigned into parallel model and achieved on CUDA to segment tumors. Then the shortcomings using graph cut algorithm to segment tumor are intensive studied and a novel interactive segmentation method which is based on the optimal distance learning is presented. Allowing to this algorthm, we firstly extract the high dimensional image features and modify the traditional graph cut algorithm based on image gray level information, a new cost function is proposed. Finally, a graph cut optimal framework is used to get the solution of the cost function. This novel algorthm achieves the accurate segmentation of the tumor images. 1. Parallel Graph Cut Algorithm Based On CUDACompute unified device architecture (CUDA) has freed Computation on the graphic processing unit (GPGPU) technology from the graphics fixed pipeline and high-level shader language, allowing the design and implementation of SIMD (single instruction and multiple data) parallel algorithms on a much more simple way than previous method based on texture rendering. In this paper, the core concept of CUDA was first studied, then the graph cuts algorithm was redesigned into parallel model, in implementations, the algorithm is optimized combined with the impact on the computing performance of the CUDA global memory access, thread shared memory allocation block size and allocation of shared memory, comparing with the traditional CPU serial algorithm, computing speed has been significantly improved, Based on the characteristics of tumors, the region of interest was introduced to improve interactive methods and then achieve the segmentation of tumors. The experiments showed that the new approach was quite accurate and robust. Besides, the proposed algorithm is easy in interacting and extending.2. Tumor Segmentation Using Optimal Distance LearningCurrently, segmentation methods based on graph cuts have been widely used. However, these methods adopt histogram or gaussian mixture model to estimate gray level distribution function of the target and background in images gray space, they only get good segmentation results when the target and background are obviously different in gray level distribution. Actually, the intensity distribution of tumors in CT or MR images usually has the large overlap with that of its surrounding tissues, moreover, tumor tissue is always with extremely complex gray distribution in itself. For the accurate segmentation of the tumor images, this paper presents a novel interactive segmentation method which is based on the optimal distance learning. In this method, we firstly extract the high dimensional image features, and obtain the optimal distance metric in the features space by using Neighborhood Components Analysis. Then for each pixel, the probabilities of which belongs to the tumor and the background regions are estimated respectively by exploiting the K-Nearest Neighborhood classifier, based on these probabilities, a new cost function is proposed. Finally, a graph cut optimal framework is used to get the solution of the cost function. The proposed method was evaluated on the liver tumor CT images and brain tumor MR images respectively, the experimental result shows that for 58 images with large intensity variation in their tumor regions, comparing the traditional intensity histogram based graph cut method, proposed method improve the segmentation accuracy significantly, the average overlap ratio against the manual segmentation rises from 78% to 87% with 9% increase.