DOC PREVIEW
U of U CS 7960 - Normalized Cuts and Image Segmentation

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Normalized Cuts and Image Segmentation Jianbo Shi and Jitendra Malik Computer Science Division University of California at Berkeley, Berkeley, CA 94720 {j shi,malik}@cs.berkeley.edu Abstract we propose Q novel approach for solving the per- ceptual grouping problem in vision. Rather than fo- cusing on local features and their consistencies in the amage data, our approach aims at extracting the global impression of an image. We treat image segmenta- tion QS (I graph partitioning problem and propose Q novel global criterion, the normalized cut, for segment- ing the graph. The normalized cut craterion measures both the total dissimilarity between the different groups QS well as the total similarity within the groups. We show that an eficient computational technique based on a generaked eigenvalue problem can be used to op- timize this criterion. we have applied this approach to segmenting static images and found results very en- co u raging. 1 Introduction Nearly 75 years ago, Wertheimer[l7] launched the Gestalt approach which laid out the importance of perceptual grouping and organization in visual per- ception. For our purposes, the problem of grouping can be well motivated by considering the set of points shown in the figure (1). Typically a human observer will perceive four ob- jects in the image-acircular ring with a cloud of points inside it, and two loosely connected clumps of points on its right. However this is not the unique parti- tioning of the scene. One can argue that there are three objects-the two clumps on the right constitute one dumbbell shaped object. Or there are only two objects, a dumb bell shaped object on the right, and a circular galaxy like structure on the left. If one were perverse, one could argue that in fact every point was a distinct object. This may seem to be an artificial example, but ev- ery attempt at image segmentation ultimately has to confront a similar question-there are many possible partitions of the domain D of an image into subsets Di (including the extreme one of every pixel being a separate entity). How do we pick the "right" one? We believe the Bayesian view is appropriate- one wants to find the most probable interpretation in the context of prior world knowledge. The difficulty, of course, is in specifying the prior world knowledge-some of it is low level such as coherence of brightness, color, texture, or motion, but equally important is mid- or high- level knowledge about symmetries of objects or object mod- els. 1063-6919197 $10.00 0 1997 IEEE Figure 1: How many groups? This suggests to us that image segmentation based on low level cues can not and should not aim to pro- duce a complete final "correct" segmentation. The objective should instead be to use the low-level coher- ence of brightness, color, texture or motion attributes to sequentially come up with candidate partitions. Mid and high level knowledge can be used to either con- firm these groups or select some for further attention. This attention could result in further repartitioning or grouping. The key point is that image partitioning is to be done from the big picture downwards, rather like a painter first marking out the major areas and then filling in the details. Prior literature on the related problems of cluster- ing, grouping and ima e segmentation is huge. The clustering community[i has offered us agglomerative and divisive algorithms; in image segmentation we have region-based merge and split algorithms. The hierarchical divisive approach that we are advocat- ing produces a tree, the dendrogram. While most of these ideas go back to the 70s (and earlier), the 1980s brought in the use of Markov Random Fields[7] and variational formulations[ 13, 2, 111. The MRF and vari- ational formulations also exposed two basic questions (1) What is the criterion that one wants to optimize? and (2) Is there an efficient algorithm for carrying out the optimization? Many an attractive criterion has been doomed by the inability to find an effective algo- rithm to find its minimum-greedy or gradient descent type approaches fail to find global optima for these high dimensional, nonlinear problems. Our approach is most related to the graph theo- retic formulation of grouping. The set of points in an arbitrary feature space are represented as a weighted 73 1 Authorized licensed use limited to: The University of Utah. Downloaded on April 12,2010 at 20:46:48 UTC from IEEE Xplore. Restrictions apply.undirected graph G = (V, E), where the nodes of the graph are the points in the feature space, and an edge is formed between every pair of nodes. The weight on each edge, w(i,j), is a function of the similarity between nodes i and j. In grouping, we seek to partition the set of vertices into disjoint sets VI, VI, ..., V,, where by some mea- sure the similarity among the vertices in a set Vi is high and across different sets Vi,Vj is low. To partition a graph, we need to also ask the fol- lowing questions: 1. What is the precise criterion for a good partition? 2. How can such a partition be computed efficiently? In the image segmentation and data clustering com- munity, there has been much previous work using variations of the minimal spanning tree or limited neighborhood set approaches. Although those use effi- cient computational methods, the segmentation crite- ria used in most of them are based on local properties of the graph. Because perceptual grouping is about extracting the global impressions of a scene, as we saw earlier, this partitioning criterion often falls short of this main goal. In this paper we propose a new graph-theoretic criterion for measuring the goodness of an image partition- the normalized cut. We introduce and jus- tify this criterion in section 2. The minimization of this criterion can be formulated as a generalized eigen- value problem; the eigenvectors of this problem can be used to construct good partitions of the image and the process can be continued recursively as desired(section 3). In section 4 we show experimental results. The formulation and minimization of the normalized cut criterion draws on a body of results, theoretical and practical, from the numerical analysis and theoretical computer science communities-section 5 discusses pre- vious work on the


View Full Document
Download Normalized Cuts and Image Segmentation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Normalized Cuts and Image Segmentation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Normalized Cuts and Image Segmentation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?