Based Ncut To Image Segmentation Algorithm

Image segmentation refers to partition the image into non-overlapping meaningful area, as a key part of the later image processing, analysis and application, Image segmentation plays a very important role in the industrial, military, medical images and robot vision. So far, there are many image segmentation algorithm based on graph theory, which normalized cut algorithm is the most widely used one. The algorithm criterion is a global optimization criterion, its research is to be directly applied to the pixel to carry out the image segmentation, the computation is so large that not suitable for real time image processing.Mean-Shift algorithm is a non-supervised clustering image segmentation algorithm, which has the convergence speed and robustness of the noise. However, it has a shortcoming that is prone to over segmentation.In view of the above algorithms characteristics, this paper proposes an image segmentation algorithm based on Mean-Shift and Ncut image segmentation algorithm, it uses Mean-Shift for image preprocessing, and then applys Ncut algorithm for regional clustering. This algorithm can reduce computation and noise interference, and is conducive to real-time image processing.The main research contents are as follows:1. Introduced the principle of mean-Shift algorithm, including its basic form, expanded form, steps of the algorithm, and discussing the convergence of the algorithm, analysing the image segmentation based on Mean-Shift algorithm. Finally, simulation results show that the select of the three parameters ( hr , hs ,M ) in the algorithm has great impact on segmentation results.2. Introduced the relevant basic theory of graph, two kinds of image segmentation criteria (cut and Ncut), which based on graph theory, and Solution of normalized cut algorithm (Ncut). Then this chapter introduced the 2-way Ncut and K-way Ncut algorithm, which based on graph theory. Finally, simulation results show that the select of parameters K and the weight matrix W in the K-way Ncut algorithm is very important. 3. After analysing Mean-Shift algorithm and Ncut algorithm, in order to improve the speed and the effects of the Ncut segmentation, the paper design of a segmentation algorithm based on region Ncut, Firstly the algorithm use Mean-Shift algorithm to preprocess the image, as the image processed by Mean-Shift Algorithm will be divided into many over-segmentation regions, if we use some representative point instead of these regions, we can construct an undirected weighted graph to describe the relationship of these point, unlike the traditional Ncut algorithm used in image pixels, we directly applied Ncut algorithm to these areas for regional clustering. Experimental results demonstrate the feasibility and superiority of the algorithm.4. The paper improves the weight matrix W as well, the weight matrix W in the traditional Ncut algorithm has two parameters of sensitivity(σI ,σX), which control node range differences and Spatial differences. The selection of these two parameters is very important, it needs to manually adjust to obtain good segmentation results, thus it limit the generality of the algorithm. To solve this issue, the paper designs a new adaptive weight matrix to improve the algorithm's versatility, and the simulation results prove that using this weight matrix, the algorithm not only obtains good segmentation effect but also acquires high stability.