Report

Biased Normalized Cuts IEEE Conference on Computer Vision and Pattern Recognition (IEEE CVPR 2011) Poster Subhransu Maji and Jithndra Malik University of California, Berkeley Nisheeth K. Vishnoi Miscrosoft Research India, Bangalore 1 Outline • Review of ‘Normalized Cuts’ • Introduction to ‘Biased Normalized Cuts’ • Biased Graph Partitioning • Algorithm • Qualitative Evaluation 2 Review of Normalized Cuts • Original cut definition: cut(A,B)= ∈,∈ (, ) • Goal: minimize the cut value • New cut definition: Normalized Cut: , = (,) (,) (,) + (,) v: the vertex in the graph , = ∈,∈ (, ) 3 Shi and Malik, Normalized Cuts and Image Segmentation, PAMI, 2000 Review of Normalized Cuts • Normalized Cut: , = (,) (,) (,) + (,) • Goal: minimize Normalized Cut ⟹ min () = ⋯ (the details seen in ‘Normalized Cuts’ ) = − min • Symbols: x: the = dimensional indicator vector with = D: the × matrix with = 1, ℎ ∈ −1, ℎ ∈ , = 0, ≠ d(i): the total connection from node i to all other node with = (, ) W: the symmetrical matrix with W(i, j)= = + − − where 1: the × 1 vector of all ones and = and = >0 1− 4 Review of Normalized Cuts • min () = − min • The above is the Rayliegh quotient and minimize it by solving the generalized eigenvalue system − = [Golub and Van Loan,John Hopkins Press,1988] • Rewrite the above equation as − • − − 1 −2 − = ℎ = − − is the symmetric positive semidefinite • − : also symmetric positive semidefinite and Laplacian Matrix 5 Review of Normalized Cuts 6 Introduction to ‘Biased Normalized Cuts’ • Incorporate the both bottom-up and top-down work • \ • Bottom-up: detect contours corresponding to significant changes in brightness, color or texture • Top-down: look for strong activation 7 Introduction to ‘Biased Normalized Cuts’ • Not only minimize the normalized cut value, but also one of two partitions is required to have a sufficient overlap with a “bias” or a “prior guess” • The users specify the bias by indicating various point set T with a seed-vector 8 Introduction to ‘Biased Normalized Cuts’ • Two advantages: 1. Solutions which are sufficiently “correlated” with priors which allows us to use noisy top-down information 2. Given the spectral solution of the unconstrained problem, the solution of the constrained one can be computed in small additional time, which allows to run the algorithm in an interactive mode 9 Weighted Graph and Normalized Cuts • Symbol: 1. = (, ) where v: the nodes ate the points in the feature space and E: the edge between every pair of the points 2. Weight : ↦ ℝ≥0 is a function 3. For ⊆ , = \S, , ≝ 4. ∈,∈ (, ) The volume of a set of vertices S is the total weight of the edges () ≝ ∈,∈ (, ) and () ≝ ∈,∈ (, ) and + = () 5. The normalized cut value: , ≝ (,) () + (,) () 6. The traditional graph conductance defined for a set S ≝ ⋅ (,) ()⋅() 7. The conductance of the graph G: () ≝ min ⊆ 10 Weighted Graph and Normalized Cuts • : × adjacency matrix with , = , • : diagonal degree matrix of G ∈ (, ) , = (, ) = 0, ≠ • : the Laplacian of G with ≝ − 1 1 −2 −2 • ℒ : the normalized Laplacian of G with ℒ ≝ and symmetric positive semidefinite with eigenvlaues 0 = 1 < 2 ≤ ⋯ ≤ • (): the ℎ eigenvalues of ℒ • : the eigenvector corresponding to the ℎ eigenvalues of ℒ • : the associated eigenvector corresponding to the ℎ eigenvalues of 1 −2 , ≝ = 11 The Spectral Relaxation to Computing Normalized Cuts • Approximate the solution by minimizing subject to ,∈ ( − )2 = () • 1 1 = • ∈ , (1 − 1 ())2 = (, ) 2 (1 − 1 ()) = ()() ,∈ • , = , = ⋅ = + , = ⋅ , ⋅ 1 1 2 ,∈ (1 −1 ()) ,∈ ( − )2 ⋅ 1 1 2 ,∈ (1 −1 ()) = 12 Biased Normalized Cuts • Given a region of interest, segment the image so that the segment is biased towards the specified • A region is modeled as a subset ⊆ , = \ • Not only minimize the cut value, but have sufficient correlation with the region specified by T • A vector responding to the region T: ≝ () 1 () () − • Defined it in a way such that 2 = 1 () ∈ 1 () ∈ = 0 and • The above notion is quite motivated from the theory of local graph partitioning [R. Andersen et al., Local graph partitioning using PageRank vectors, FOCS,2006] • The goal is to find a low-conductance cut well correlated with a specified input set 13 Biased Normalized Cuts The prior information Solve the normalized cut problem 14 Algorithm 26 in the paper − × 15 Qualitative Evaluation • Use the PASCAL VOC 2010 dataset • Weight matrix: use the intervening contour cue [M. Maire et al., Using contours to detect and localize junctions in natural images, CVPR, 2008] 16 Effect of • Increase the correlation parameter 17 Result • Pb: probability of boundary map [M. Maire et al., Using contours to detect and localize junctions in natural images, CVPR, 2008] 18 Result • Use the probability estimates by an object detector as a bias • The object detector used as a seed vector [L. Bourdev et al., Detecting people using mutually consistent poselet activations, ECCV, 2010] 19