ECE 278 Final ReportNormalized Cuts and Image SegmentationAbstractIntroductionGraph PartitioningRelated ApproachesNormalized CutThe grouping algorithmExperiments and ResultsTexture Images - descriptors formed based on intensities



Gaussian noise, Color Images - descriptors formed based on HSV valuesConclusionReferencesECE 278 Final Report Normalized Cuts and Image Segmentation Baris Sumengen, Jelena Tešić Abstract Our project work includes the embedding of a normalized cuts algorithm and testing its application for image segmentation. Proposed solution minimizes a graph bi partitioning based on a modified cost function. Final result has a form of partition candidates based on a low-level image description. To increase the stability of the proposed method, algorithm has an iterative form. Computational complexity issues remain unsolved, even though the method performs well for a preprocessing. 1. Introduction The importance and difficulties of perceptual grouping have been very well studied in vision research and image processing literature. How to partition image to subsets, when there are many possible ways of doing it? The intuitive answer would be a partitioning based on the available prior knowledge. The difficulty is specifying the knowledge in a compact and useful way i.e. defining the descriptors of an image. It is clear that the use of low-level descriptors could not lead to a complete and correct final segmentation. Instead, image attributes should be used for obtaining candidate partitions. Higher-level descriptors can be used in decision process and “finer tuning” of the proposed segments. Over the decades, different scientific communities proposed various approaches to generalized image segmentation problem. Tree-based hierarchical clustering structures, region-based merge and split image processing algorithms and statistical approach to image segmentation introduced additional constraints on a possible solution. Before any algorithm implementation we have to determine what criterion we want to optimize and if there is an efficient algorithm for implementation method. We separate the proposed method from the ones mentioned above because it has a novel approach to an image. It is taking a global image feature descriptor as a weighted graph and reduces segmentation to an optimal graph partitioning. New optimization criterion - normalized cut - is used for finding the optimal partitioning. The graph partitioning approach and related work is explained in the section 2. Normalized cuts criterion and its justification are presented in the section 3. The algorithm and its properties are presented in the section 4. Conducted experiments and results are outlined in the section 5. Section 6 discusses the proposed approach and derives the project conclusion. 12. Graph Partitioning The set of points in an arbitrary feature space is presented as a weighted undirected graph G=(V,E). Nodes of the graph are the points in the feature space. An edge is formed between every pair of nodes and the weight on each edge W(i,j) is a function of the similarity between nodes i and j. A graph G=(V,E) is partitioned into two disjoint complementary sets A and B, B=V-A, by removing the edges connecting two parts. The degree of dissimilarity between two sets can be computed as a total weight of removed edges. That closely relates to a mathematical formulation of a cut (1): ,( , ) ( , ) (1)uAvBcut A B w u v∈∈=∑2.1. Related Approaches Problem formulation is to find an optimal bi partitioning of a graph G. The problem reduces to finding a cost function that will give us perceptually good results (since we’re dealing with feature descriptors of an image). Global optimum is achieved if we minimize the cut value. If N is cardinality of V, N =|V|, there is an exponential number of possible partitions 2N. This optimization is well studies and there is an efficient algorithm for finding a minimum cut [3]. Wu and Leahy proposed a clustering method based on the minimum cut criterion [5]. They are trying to partition the graph into k sub graphs so that the maximum cut across the partitions is minimized. They introduced an efficient way to obtain the solution by recursively finding the minimum cut that bisects the existing elements. This method produced some good segmentation results. Authors noticed that the performance is highly influenced by the graph outliers. From the definition of global optimum (1) , this is an expected outcome. The following example illustrates the bad partitioning case: Cox [r] proposed a modified cost function (2), where weight(A) is some function of set A, i.e. sum of elements in A. (, )( ) (2)()cut A V AWCut Aweight A−= 22.2. Normalized Cut Shi and Malik [1,2] propose a modified cost function, normalized cut, to overcome outliers. Instead of looking at the value of total edge weight connecting the two partitions, the proposed measure computes the cut cost as a fraction of the total edge connections to all nodes (3): ,(,) (,)( , ) , ( , ) ( , ) (3)(,) (, )uAtVcut A B cut A BNcut A B asso A V w u tasso A V asso B V∈∈=+ =∑ The association value, asso(A,V), is the total connection from nodes A to all nodes in the graph. Ncut value won’t be small for the cut that partitions isolating points, because the cut value will be a large percentage of the total connection from that set to the others. We present an efficient algorithm for graph partitioning using the normalized cut as an optimal criterion. Given a partition of a graph V into two disjoint complementary sets A and B, let x be an N=|V| dimensional indication vector, xi=1 if node i is in A, -1 otherwise. Let (, )ijdWi= j∑ be the total connection from node i to all other nodes. Ncuts can be rewritten as (4). 0, 0 0, 000(, ) (, )( , ) = + (4)(,) (,)jjiiiiijij ijijxx xxiixxwxx wxxcut A B cut A BNcut A Basso A V asso B V d d>< <>><−−=+∑∑∑∑ Let and W(i,j) =w12( , ..., )NDdiagdd d=ij. Finding global optimum reduces to (5): 100()min ( ) min , 1 , 0 (5) iiTixTxy iTixNddyDWyNcut x y yyDy dd><−−=∈∑∑= If y is relaxed to take on real values, we can minimize (5) by solving generalized eigenvalue system: ( ) (6)DWy Dyλ−= Constraints on y come from the condition on the corresponding indicator vector x. The second smallest