Normalized cuts and image segmentation - Pattern Analysis ...

1 Normalized Cuts and image SegmentationJianbo Shi and Jitendra Malik,Member,IEEEA bstract We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local featuresand their consistencies in the image data, our approach aims at extracting the global impression of an image . We treat imagesegmentation as a graph partitioning problem and propose a novel global criterion, thenormalized cut, for segmenting the graph. Thenormalized cutcriterion measures both the total dissimilarity between the different groups as well as the total similarity within thegroups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize thiscriterion. We have applied this approach to segmenting static images, as well as motion sequences, and found the results to be Terms Grouping, image segmentation , graph partitioning. 1 INTRODUCTIONNEARLY75 years ago, Wertheimer [24] pointed out theimportance of perceptual grouping and organizationin vision and listed several key factors, such as similarity,proximity, and good continuation, which lead to visualgrouping.

2 However, even to this day, many of thecomputational issues of perceptual grouping have re-mained unresolved. In this paper, we present a generalframework for this problem, focusing specifically on thecase of image there are many possible partitions of the domainIof an image into subsets, how do we pick the right one?There are two aspects to be considered here. The first is thatthere may not be a single correct answer. A Bayesian view isappropriate there are several possible interpretations inthe context of prior world knowledge. The difficulty, ofcourse, is in specifying the prior world knowledge. Some ofit 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 objectmodels. The second aspect is that the partitioning isinherently hierarchical. Therefore, it is more appropriateto think of returning a tree structure corresponding to ahierarchical partition instead of a single flat suggests that image segmentation based on low-level cues cannot and should not aim to produce a completefinal correct segmentation .

3 The objective should insteadbe touse the low-level coherence of brightness, color, texture, ormotion attributes to sequentially come up with hierarchicalpartitions. Mid- and high-level knowledge can be used toeither confirm these groups or select some for furtherattention. This attention could result in further repartition-ing or grouping. The key point is that image partitioning isto be done from the big picture downward, rather like apainter first marking out the major areas and then filling inthe literature on the related problems of clustering,grouping and image segmentation is huge. The clusteringcommunity [12] has offered us agglomerative and divisivealgorithms; in image segmentation , we have region-basedmerge and split algorithms. The hierarchical divisiveapproach that we advocate produces a tree, most of these ideas go back to the 1970s (and earlier),the 1980s brought in the use of Markov Random Fields [10]and variational formulations [17], [2], [14].

4 The MRF andvariational formulations also exposed two basic is the criterion that one wants to optimize? there an efficient algorithm for carrying out theoptimization?Many an attractive criterion has been doomed by theinability to find an effective algorithm to find its mini-mum greedy or gradient descent type approaches fail tofind global optima for these high-dimensional, approach is most related to the graph theoreticformulation of grouping. The set of points in an arbitraryfeature space are represented as a weighted undirectedgraphGG VV;EE , where the nodes of the graph are thepoints in the feature space, and an edge is formed betweenevery pair of nodes. The weight on each edge,w ii;jj ,isafunction of the similarity between grouping, we seek to partition the set of vertices intodisjoint setsV1;V2;..;Vm, where by some measure thesimilarity among the vertices in a setViis high and, acrossdifferent setsVi,Vjis partition a graph, we need to also ask the is the precise criterion for a good partition?

5 Can such a partition be computed efficiently?In the image segmentation and data clustering commu-nity, there has been much previous work using variations ofthe minimal spanning tree or limited neighborhood setapproaches. Although those use efficient computational888 IEEE TRANSACTIONS ON Pattern Analysis AND MACHINE INTELLIGENCE, VOL. 22, NO. 8, AUGUST Shi is with the Robotics Institute, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213. E-mail: Malik is with the Electrical Engineering and Computer Science Division,University of California at Berkeley, Berkeley, CA : received 4 Feb. 1998; accepted 16 Nov. for acceptance by M. information on obtaining reprints of this article, please send e-mail and reference IEEECS Log Number $ IEEE methods, the segmentation criteria used in most of them arebased on local properties of the graph. Because perceptualgrouping is about extracting the global impressions of ascene, as we saw earlier, this partitioning criterion oftenfalls short of this main this paper, we propose a new graph-theoretic criterionfor measuring the goodness of an image partition thenormalized cut.

6 We introduce and justify this criterion inSection 2. The minimization of this criterion can beformulated as a generalized eigenvalue problem. Theeigenvectors can be used to construct good partitions ofthe image and the process can be continued recursively asdesired (Section ). Section 3 gives a detailed explanationof the steps of our grouping algorithm. In Section 4, weshow experimental results. The formulation and minimiza-tion of the Normalized cut criterion draws on a body ofresults from the field of spectral graph theory (Section 5).Relationship to work in computer vision is discussed inSection 6 and comparison with related eigenvector basedsegmentation methods is represented in Section Weconclude in Section main results in this paper were first presented in [20].2 GROUPING ASGRAPHPARTITIONINGA graphG V;E can be partitioned into two disjointsets,A;B,A[B V,A\B ;, by simply removing edgesconnecting the two parts.]

7 The degree of dissimilaritybetween these two pieces can be computed as total weightof the edges that have been removed. In graph theoreticlanguage, it is called thecut:cut A;B Xu2A;v2Bw u;v : 1 The optimal bipartitioning of a graph is the one thatminimizes thiscutvalue. Although there are an exponentialnumber of such partitions, finding theminimum cutof agraph is a well-studied problem and there exist efficientalgorithms for solving and Leahy [25] proposed a clustering method basedon this minimum cut criterion. In particular, they seek topartition a graph into k-subgraphs such that the maximumcut across the subgroups is minimized. This problem can beefficiently solved by recursively finding the minimum cutsthat bisect the existing segments. As shown in Wu andLeahy's work, this globally optimal criterion can be used toproduce good segmentation on some of the , as Wu and Leahy also noticed in their work,the minimum cut criteria favors cutting small sets ofisolated nodes in the graph.

8 This is not surprising sincethe cut defined in (1) increases with the number of edgesgoing across the two partitioned parts. Fig. 1 illustrates onesuch case. Assuming the edge weights are inverselyproportional to the distance between the two nodes, wesee the cut that partitions out noden1orn2will have a verysmall value. In fact, any cut that partitions out individualnodes on the right half will have smaller cut value than thecut that partitions the nodes into the left and right avoid this unnatural bias for partitioning out smallsets of points, we propose a new measure of disassociationbetween two groups. Instead of looking at the value of totaledge weight connecting the two partitions, our measurecomputes the cut cost as a fraction of the total edgeconnections to all the nodes in the graph. We call thisdisassociation measure thenormalized cut(Ncut):Ncut A;B cut A;B assoc A;V cut A;B assoc B;V ; 2 whereassoc A;V Pu2A;t2Vw u;t is the total connectionfrom nodes in A to all nodes in the graph andassoc B;V issimilarly defined.

9 With this definition of the disassociationbetween the groups, the cut that partitions out smallisolated points will no longer have smallNcutvalue, sincethecutvalue will almost certainly be a large percentage ofthe total connection from that small set to all other nodes. Inthe case illustrated in Fig. 1, we see that thecut1valueacross noden1will be 100 percent of the total connectionfrom that the same spirit, we can define a measure for totalnormalized association within groups for a given partition:Nassoc A;B assoc A;A assoc A;V assoc B;B assoc B;V ; 3 whereassoc A;A andassoc B;B are total weights ofedges connecting nodes withinAandB, respectively. Wesee again this is an unbiased measure, which reflects howtightly on average nodes within the group are connected toeach important property of this definition of associa-tion and disassociation of a partition is that they arenaturally related:Ncut A;B cut A;B assoc A;V cut A;B assoc B;V assoc A;V assoc A;A assoc A;V assoc B;V assoc B;B assoc B;V 2 assoc A;A assoc A;V assoc B;B assoc B;V 2 Nassoc A;B :Hence, the two partition criteria that we seek in ourgrouping algorithm, minimizing the disassociation betweenthe groups and maximizing the association within theSHI AND MALIK: Normalized CUTS AND image SEGMENTATION889 Fig.

10 1. A case where minimum cut gives a bad , are in fact identical and can be satisfied simulta-neously. In our algorithm, we will use this Normalized cutas the partition , minimizing Normalized cut exactly is NP-complete, even for the special case of graphs on grids. Theproof, due to Papadimitriou, can be found in Appendix , we will show that, when we embed the normal-ized cut problem in the real value domain, an approximatediscrete solution can be found Computing the Optimal PartitionGiven a partition of nodes of a graph, V, into two sets A andB, letxxbe anN jVVjdimensional indicator vector,xi 1ifnodeiis in A and 1, otherwise. Letdd i Pjw i;j be thetotal connection from nodeiito all other nodes. With thedefinitionsxxanddd, we can rewriteNcut A;B as:Ncut A;B cut A;B assoc A;V cut B;A assoc B;V P xxi>0;xxj<0 wijxxixxjPxxi>0ddi P xxi<0;xxj>0 wijxxixxjPxxi<0ddi:LetDbe anN Ndiagonal matrix withddon its diagonal,Wbe anN Nsymmetrical matrix withW i;j wij,k Pxi>0ddiPiddi;and1be anN 1vector of all ones.