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.
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. In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. On the first glance spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does. The goal of this tutorial is to give some intuition on those questions. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.