Normalized cut (Ncut) is one of the popular image segmentation models in which the parametric similarity matrix should be given in advance. In this paper, we propose a normalized cut segmentation algorithm with an adaptive similarity measure and spatial regularization. The statistical Parzen-Rosenblatt window, expectation maximum (EM) method and the regularization technique in partial differential equation (PDE) are unified in a proposed variational framework. The introduced EM strategy makes our method can adaptively update the similarity matrix, and it can produce a better classification criterion than the existing Ncut based methods. While the regularization can guarantee the proposed algorithm has a robust performance under noise and it can also rectify the similarity measure with a priori spatial location. In addition, the existence theorem of the proposed model is given in the paper. Compared with some existing spectral clustering methods such as the traditional Ncut algorithm and the variational based Chan-Vese model, the numerical experiments show that our methods can provide promising segmentation results.
The segmentation models based on min-cut criterion @cite_13 have been demonstrated good performance on some natural images. However, as the researchers noticed in their works, the above cut criteria favors cutting small sets of isolated nodes in the graph, which is not desirable in real applications. To solve this bias problem existing in cut based models, Shi and Malik @cite_55 presented the well-known normalized cut where @math
@cite_55 @cite_13
2121947440 2132603077
We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We applied this approach to segmenting static images, as well as motion sequences, and found the results to be very encouraging. A novel graph theoretic approach for data clustering is presented and its application to the image segmentation problem is demonstrated. The data to be clustered are represented by an undirected adjacency graph G with arc capacities assigned to reflect the similarity between the linked vertices. Clustering is achieved by removing arcs of G to form mutually exclusive subgraphs such that the largest inter-subgraph maximum flow is minimized. For graphs of moderate size ( approximately 2000 vertices), the optimal solution is obtained through partitioning a flow and cut equivalent tree of G, which can be efficiently constructed using the Gomory-Hu algorithm (1961). However for larger graphs this approach is impractical. New theorems for subgraph condensation are derived and are then used to develop a fast algorithm which hierarchically constructs and partitions a partially equivalent tree of much reduced size. This algorithm results in an optimal solution equivalent to that obtained by partitioning the complete equivalent tree and is able to handle very large graphs with several hundred thousand vertices. The new clustering algorithm is applied to the image segmentation problem. The segmentation is achieved by effectively searching for closed contours of edge elements (equivalent to minimum cuts in G), which consist mostly of strong edges, while rejecting contours containing isolated strong edges. This method is able to accurately locate region boundaries and at the same time guarantees the formation of closed edge contours. >