Color Image Segmentation Based On The Second Watershed And Normalized Cut

Image segmentation is a technology that can divide an acquired image into a number of significant areas, and also, the areas are not overlapped.In recent years, graph theory is a hot research area of image segmentation. It transforms image segmentation into a flexible graph partitioning problem that selects information form the global graph. Ncut (Normalized cut) based on graph theory is one of the image segmentation methods. It is a standardized criterion. It can merge the different characteristics of the input images, and calculate the difference of the nodes among different small areas and similarity of the nodes within the same target region. However, there are still some problems of Ncut. For instance, it has large computation, over-segmentation and under segmentation. Large computation will affect the application of Ncut in reality.The watershed is a well developed algorithm which has the advantages of fast computing speed, and closed outline of objects. It also can accurately position and get a good response of the weak edge. However, it has a drawback of over-segmentation.In this paper, a method combining second watershed and Ncut algorithm is proposed to make use of their advantages and overcome their shortcomings. The second watershed is used to preprocess the input image. In this case, small areas are got and set as the input of Ncut algorithm, so the computing time of the method is greatly reduced.The main contents of this paper are as follows.Firstly, we combine the second watershed and Ncut algorithm by considering each micro segment after the second watershed as a node in the graph. Since the number of nodes in the graph is reduced, the total running time of the segmentation is greatly reduced. In addition, experiments also show that the combined method also obtains better partitioning results compared with the Ncut algorithm.Secondly, to solve the problem of border line (labeled by zeros) generated by the second watershed, several methods are proposed and fully discussed. We first look for the maximal similar pixel among the neighboring pixels (eight-neighborhood) of the zero's corresponding pixel, and then the zeros are classified as the areas which the maximal similar pixels belong to. Thirdly, we construct the weight matrix based on the color information of LUV system and distance information. Moreover, the partitioning differences caused by existing weight matrix methods are analyzed and tested.Fourthly, the combined scheme proposed in this paper is campared with the traditional Ncut algorithm and the mean shift Ncut method separately. Simulation results prove that our scheme not only greatly reduces the running time but also acquires good segmentation effect campared with the traditional Ncut algorithm. And our plan runs faster than the mean shift Ncut method as well.