Research On Random Walk Algorithm Based Graph Theory On The Application Of Medical Image Segmentation

Radiation therapy(Radiotherapy) is one of the three main methods of tumor therapy. The basic goal of radiation therapy is to improve the radiation therapeutic gain ratio, that means to maximize the radiation dose to lesions (target area), and kill tumor cells, then the surrounding normal tissues and organs have little or unnecessary of irradiation. The segmentation of tumor target volume and organs at risk(oars) directly impact on the efficacy of radiation therapy. In clinical application, doctors mainly outline the target volume and oars by hand, which adds a larger workload. It’s quite different when different doctors in the same time or the same doctor in different time outline the target volume and oars. Therefore, it is particularly important to automatic sketch the target volume and organs at risk, which can be solved using automatic segmentation of medical images.Image segmentation technology has experienced three processes:manual segmentation, semi-automatic segmentation and automatic segmentation. The accuracy of manual segmentation is very high, but time-consuming. The main method is the manual segmentation when doctors use; Automatic segmentation is out for intervention, entirely depending on the computer intelligent to segment the target area. In fact, the automatic segmentation is the ultimate goal of image segmentation algorithms, while today the accuracy related to the automatic segmentation algorithm is not high. But clinical application needs high precision and efficient algorithms to solve practical problems. Therefore, the development of semi-automatic segmentation algorithm is more and more to meet the needs of clinical application. Semi-automatic segmentation algorithm combined computer intelligent with the clinical knowledge which can guarantee results.Interactive image segmentation algorithm is the one type of the semi-automatic image segmentation algorithm. Since the Graph Cuts is proposed, the interactive algorithm is of great concern, which has widely used in the field of medical image processing, image synthesis, film and television technology, motion tracking et.al. In fact, interactive image segmentation algorithm is based on the idea of graph theory: graph optimization to solve the problem of segmentation. A medical image can be considered as a graph composed of points and edges. An image is mapped to a weighted graphG=(V,E) with vertices (nodes)vi∈Vand edgese∈E(?)V×V.An edge, e,spanning vertices, viand vj,is denoted by eij.A weighted graph assigns a value to each edge called a weigh. The weight of an edge eij, is denoted by w(eij)or Wij.The weight means similarity or vi and vj.In this way the graph transformation is completed, and then use the segmentation algorithm to segment and combine images. From the usage of graph theory, the segmentation algorithm based on graph theory is divided into four categories respectively:the Watershed, Graph-cut, Random Walk and Geodesic. In2011, Camille Couprie and Leo Grady et al proposed that Graph Cuts, Random Walker, Geodesic algorithm reduced to the same frame. Although the four algorithms belong to the same family, they have their own different characteristics when solving the problems. The random walk is characterized by only the existence and uniqueness of solution, and belongs to the soft segmentation, which can solve the problem of fuzzy definition of interactive segmentation algorithm. So the random walk algorithm is the main object of study.Random walk theory is one of the earliest stochastic processes which people study. Although it is the special form of the Brown motion, it is more widely used than Brownian motion. At present there are many random walk models used to simulate various physical phenomena, social phenomena and the economic phenomenon. The basic idea of random walk method is:the image is viewed as a pure discrete object, namely a fixed number of the edges and vertices (nodes) of the graph. Pixel corresponds to nodes on the graph and each edge is assigned a real-valued weight corresponding to the likelihood that a random walker will cross that edge and a weight of zero means that the walker may not move along that edge. Literatures have shown, that one or two dimensions of random walker can be simulated the circuit diagram, and then it can be transformed into Dirichlet problem solving harmonic functions to solve random walk process. This conversion is a good solution to solve the problem of random walk, but also produces a problem difficult to solve: the solving process of Dirichlet problems arise in a huge sparse linear equation which needs to spend a lot of time and memory.The process of random walk requires the user to define the two seed points: choosing in the object region called foreground seed points and choosing in the background region called background seed points. Of course the superiority of the algorithm is linked with people’s subjective consciousness.In this paper, the random walk algorithm is applied to the medical MR images and CT images:(a) The random walk algorithm is applied to segment MR images, using the obvious tumor regional seed points and non-tumor regional seed points selected in the TIC image to random walk on the TIC, T2and FLAIR images, then the image segmentation results of three modes is obtained. While the result in TIC image is accurate, but the results of T2and FLAIR images have bad accurate. The main reason is that the random walk algorithm just uses the spatial information of the seed points in T1C image and without uses the information of T2and FLAIR image.Based on the above defects, this paper uses a joint histogram between T2and FLAIR image to create the feature space and selects the seed points in the TIC images for the first random walk, which can get the segmentation result of the feature space.Then the result is mapped back to the original image space for second random walk. Finally the segmentation result is obtained. This process uses random walk algorithm twice respectively in the feature space and image space. The benefit of doing so is to make full use of three kinds of modes of image information and spatial information. In this paper, in order to prove the effectiveness of the improved algorithm, we use three groups of glioma MR image from the accuracy of the algorithm (the correct rate and error rate) and the influence of the seed points (coverage) to compare the segmentation results. First from the accuracy of the algorithm, the improved algorithm has higher accuracy than random walk algorithm, mainly in the T2and FLAIR image segmentation results. Because when random walk algorithm uses in T2and FLAIR image, the correct rate is greatly reduced, while the improved algorithm overcomes the problem, improving accuracy, thus improving the segmentation accuracy; Second from the influence of the seed points, the improved algorithm uses spatial information of the three modes of the image, which weakens the degree of dependence on seed points, while the random walk just uses the image information of TIC image and the seed points, once the seed point selection does not meet the requirements, it will lead to the uncertainty of the result. The most important thing is that in the allowable error range, the number and location of the seed points selection does not affect the final segmentation result in the improved algorithm. (b) The random walk algorithm is applied in medical CT images. This paper selects the lung CT image, and it has to select more enough number of seed points in the random walk to accurately segment the image of lung cancer, but if doctors select more enough seed points in each image every time, it will also increase the workload of doctors, at the same time it will consume the running time of algorithm.Based on the above defects, this paper innovatively adds morphological transform and watershed transform to the random walk algorithm to weaken the dependent on the seed points. Morphological transform is expansion and corrosion operation on the image to strengthen the image boundary. The watershed transform often considers gray-scale image as topographic reliefs. Every minimal value contained in the region is called the catchment basins and the boundary between two adjacent catchment basins is called watershed line. After a watershed transform, an image is composed of catchment basins and watershed lines. If using the watershed algorithm for image segmentation alone, it will produce over-segmentation phenomenon. Because there are as much minma as the catchment basins. So in order to avoid the over segmentation phenomenon the watershed algorithm will be combined with other algorithms. If using catchment basins to denote the vertices of a graph will greatly reduce the amount of data needed to be processed in random walk algorithm. The improved algorithm is used to segment two groups of lung CT images. The experiment conclusion is that the speed of the improved algorithm is faster than that of random walk algorithm and the memory of the improved algorithm consumes less than that of random walk algorithm in the same seed points.In this paper, according to the different characteristics of MR image and CT image, the random walk algorithm is improved respectively, and the experiments are carried out in glioma MR image and lung cancer CT image. The improved algorithm in MR image is improved in the higher accuracy of the result、the less dependence on seed points and the higher flexibility of algorithm; The improved algorithm in CT image is improved in the faster speed and the less memory. But there are still lots of problems which need to solve:(a) Due to defects of random walk itself, it requires to solve a large sparse matrix. When dealing with large data, it is time consuming. If we can find a new method to calculate the large-scale sparse matrix, it will greatly speed up the overall running speed of random walk algorithm, which is also a key point of the next research.(b) Due to the random walk algorithm be an interactive algorithm, a problem that all the interactive algorithm has is the affected by user subjective. Therefore, how to make the semi-automatic segmentation algorithm becomes to automatic segmentation, will be the next research focus.In this paper, through the research on medical image segmentation algorithm, the random walk algorithm based on graph theory is applied to segment medical tumor image of MR and CT. The improved algorithm in MR image is improved in the higher accuracy of the result、the less dependence on seed points and the higher flexibility of algorithm; The improved algorithm in CT image is improved in the faster speed and the less memory.