Research On Image Segmentation Based On Normalized Cuts

Image segmentation refers to partition the image into independent and meaningfularea, as an important technology of the computer vision and image processing, Imagesegmentation widely used in the industrial, military, medical and so on. The imagesegmentation algorithm based on graph theory is developed in recent years as a newimage segmentation technique, which normalized cuts algorithm is the hottest one.Normalized cuts algorithms is a kind of method based on global optimization criterion,not easy to produce small area. But it is directly applied to the pixel to carry out theimage segmentation, so the computational complexity is larger, and it is a NP hardproblem to calculate the minimum of the normalized criterion.For the shortcomings of the normalized cuts algorithm, this paper proposes animage segmentation algorithm that is composed of the fuzzy C-means algorithm basedon the division of the minimum spanning tree and the normalized criterion of theadaptive genetic algorithms, as following:1) The fuzzy C-means algorithm based on the division of the minimum spanningtree was used to cluster the original image and to get the maximum likelihood areas. Ithas solved the disadvantage of normalized cuts algorithm that computationalcomplexity increases with the increasing of pixels. The fuzzy C-means algorithm basedon the division of the minimum spanning tree convert the original image into figure andcreate the minimum spanning tree by Kruskal algorithm, then divide the minimumspanning tree into some subtrees by the density, Finally used the number and the centerof the subtree as the cluster number and initial cluster centers to obtain the maximumlikelihood areas by the fuzzy C-means algorithm.2) The normalized criterion of the adaptive genetic algorithms was used to geneticiterative operation on the maximum likelihood areas, looking for the optimalchromosome that has the smallest value of the normalized criterion.It has solved the theNP hard problem to calculate the minimum of the normalized criterion. The normalizedcriterion of the adaptive genetic algorithms is coding for the chromosome on themaximum likelihood areas, using the number of the maximum likelihood areas as thesize of the population, generatting initial population randomly and employing thenormalized criterion as fitness function. Then bengin to selection, crossover andmutation of population until satisfying some condition.Finally mapping the optimal chromosome which has the minimum value of the the normalized criterion back to theoriginal image and obtaining the image segmentation results.The fuzzy C-means algorithm based on the division of the minimum spanning treeprovide the maximum likelihood areas that is far less than the number of pixels for theimage segmentation, reducing the computational complexity of the algorithm andimproving the efficiency of the algorithm. The normalized criterion of the adaptivegenetic algorithms has been achieved the better segmentation results, and which don’tneed the user to set any parameters, improving the adaptive ability of the algorithm. Theexperimental results show that fuzzy C-means algorithm based on the division of theminimum spanning tree and the normalized criterion of the adaptive genetic algorithmsis feasible and effective.