Submodularization for Binary Pairwise Energies

Submodularization for Binary Pairwise Energies

Efficient Graph Cut Optimization for Full CRFs with Quantized Edges Olga Veksler Contents Introduction CRF with Potts pairwise potentials sparsely connected fully connected CRF (Full-CRF) Gaussian edge weights mean field optimization Quantized edge Full-CRF optimization two label case multi-label case connection to Gaussian Edge CRF application to semantic segmentation CRF Energy with Potts Potentials high energy

Find labeling x minimizing energy E x D p(xp ) p low energy w pq [ x p x q ] ( p , q ) N Optimization Solved exactly in binary label case with a graph cut NP hard in multi-label case expansion algorithm approximation (factor of 2) [Boykov et.al.TPAMI01] Sparse vs. Fully

Connected CRF Sparsely connected CRFs 4, 8, or small neighbourhood connected TRWS [Kolmogorov TPAMI2006] or expansion algorithms work well length regularization [Boykov&KolmogorovICCV2003] Fully connected CRFs [Krahenbul&KoltunNIPS2011] nave application of expansion all

pixels are neighbors, n pixels, O(n2) edges algorithm, TRWS, etc. is not efficient regularization properties? Full CRF with Uniform Weights Cardinality regularization labels in {0,1} n pixels in the image, k pixels assigned to label 1 w w Full CRF with Uniform Weights Cardinality regularization

labels in {0,1} n pixels in the image, k pixels assigned pairwise to label 1energy is w w Full CRF with Uniform Weights Cardinality regularization labels in {0,1} n pixels in the image, k pixels assigned pairwise to label 1energy is w

w(n - k) k n k same pairwise cost Efficient algorithm for each k find the k pixels with lowest cost for label 1 compute total energy chose k corresponding to the smallest energy w Fully Connected CRFs

Fully connected CRFs [Krahenbul&KoltunNIPS2011] assumes Gaussian edge weights w pq 1 exp d p dq 2 2 12 C p

Cq 2 22 2 exp 2 C p Cq 2 32 efficient mean field inference

approximate bilateral filter [Paris&Durand, IJCV2009] mean field is not a very effective optimization method [Weiss2001] 2 CRF+CNN Combination CNN can give blurred not pixel precise results Sharpen with CRF Chen et.al. ICLR2015 as post processing Or unified framework [Zheng et.al., ICCV2015]

Quantized Edge Fully Connected CRFs Gaussian Edge Weights [Krahenbul&KoltunNIPS2011] w pq exp exp d d Quantized edge weights w pq exp exp m m

superpixels Quantized Edge Fully Connected CRFs Edge weights depend on superpixel membership do not have to be Gaussian weighted superpixels Quantized Edge Fully Connected CRFs input image superpixels Interior/exterior weights interior weights exterior weights

Optimization for 2 labels: Superpixel Consider one superpixel internal edges weight w 0 n k pixels 0 0 1 k pixels 1 1 1 w w Internal pairwise cost is k(n - k) if vary green superpixel w labeling, cost changes

only with k Optimization for 2 labels: Two Superpixels Consider two superpixels external edge weight ww n k pixels k pixels 0 0 0 1 1 1 1 ww ww 0

0 0 0 1 1 External pairwise cost is m h pixels h pixels wwk(m [- h) + (n - k) h if vary green superpixel labeling, cost changes If k pixels onlyinwith k superpixel are assigned to label 1, they green must be those that have the smallest cost for label 1 Optimization for 2 labels: Overview Convert binary energy in pixel domain to multilabel energy in smaller superpixel domain

new variables are the superpixels new cardinality labels are 0,1,,superpixelSize assume unary cost for label 0 is 0 4 pixels 8 pixels new variables 10 pixels 11 pixels old labels {0,1} new labels {0,..., 4} {0,...,1 {0,...,8 {0,...,1 0} } Optimization for 2 labels: Conversion Sort

pixels in each superpixel by increasing cost of being assigned to label 1 New variables are the superpixels New labels are 0,1,,superpixelSize Label k assigned to superpixel means k smallest cost pixels in that superpixel are assigned to label 1 in original problem 1 2 3 4 sort pixels in each superpixel by cost of being assigned to label 1 0 0 1 1 0 0 0

0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 s1=2 s2=3 s3=6s4=11 Unary Cost for Transformed Problem Unary cost for green superpixel to have label k account for unary terms of the original binary problem n k pixels k pixels 0 0 w 0 1 1 1

1 Unary Cost for Transformed Problem Unary cost for green superpixel to have label k account for unary terms of the original binary problem account for internal pairwise terms of original binary problem n k pixels k pixels 0 0 w 0 cost of 1 cost of 1 cost of 1 cost of 1 + wk(n - k)

Pairwise Cost for Transformed Problem Pairwise cost for green superpixel to have label k, purple superpixel to have label h models external pairwise cost 0 n k pixels 0 0 1 1 k pixels 1 1 ww ww 0 0 0 0

1 1 m h pixels h pixels ww k(m [ - h) + (n - k) h ] Optimization for Transformed Problem Pairwise cost for green superpixel to have label k, purple superpixel to have label h ww k(m [ - h) + (n - k) h Can be rewritten as unary terms + (h - k)2 Can optimize exactly with [IshikawaTPAMI04]

number of edges is quadratic in the number of labels memory inefficient, time complexity almost as bad as the original binary problem Or with [AjanthanCVPR2016] Memory efficient, but time complexity almost as bad as the original binary problem ] Optimization: Jump Moves Pairwise cost is quadratic (h - k)2 5 34 5 34 5 23 4 22 5 22 5 21 7 1 3 +1 jump7 2 4 -1 jump 7 2 4

Jump moves [Veksler99, Kolmogorov &Shioura09] each move is optimization of binary energy efficient: number of edges is linear in the number of pixels give exact minimum efficiently if unary terms are also convex Our unary terms are not convex jump moves do not work well in practice Optmization: Expansion Moves 5 34 5 34 5 11 4 22 2 22

2 21 7 1 3 2-expansion 7 2 2 1 - expansion 7 2 2 Expansion moves [Boykov et.al., PAMI2001] each expansion move is optimization of binary energy efficient: number of edges is linear in the number of pixels Not submodular for quadratic potential but does find the optimum in the overwhelming majority of cases Multi-Label Quantized FullCRF Apply expansion algorithm

each expansion step is optimization of binary energy already know how to optimize 2-label Edge Quantized Full CRF problem meaning of label 0 is not fixed for expansion algorithm solution construct new superpixels according to the current labeling

old superpixels new superpixels Final Algorithm, Multi-Label Case for each LL perform -expansion 1. compute new superpixels 2. transform binary expansion energy from pixel domain to multi-label energy in superpixel domain 3. for each LLtransformed perform -expansion until convergence until convergence

Connection to Gaussian FullCRF Quantized edge CRF gets close to Gaussian edge CRF as number of superpixels increases as beta increases Connection to Gaussian FullCRF Regularization properties of full Gaussian CRF not well understood all pixels connected, preserves fine structure ground truth Gaussian Full-CRF resul Quantized Edge CRF model helps to understand Gaussian CRF If k pixels in a superpixel split from the rest, shape of the split

does not matter equal cost labelings Optimization Results: FullCRF, 2 labels validation fold of Pascal 2012 dataset reduced to 70x70 pixels 2 most likely labels global optimum with a graph cut our method is exact in 89% of cases running time in seconds Optimization Results: Full-CRF, multilabel validation fold of Pascal 2012 dataset 21 labels our method is always better than

mean-field, ICM running seconds time in Full CRFs :Semantic Segmentaiton Test fold of Pascal 2012 dataset 21 labels Overall IOU Unary 67.143 Superpixels Mean Field Ours 67.75 65.89 67.3 Full CRFs :Semantic

Segmentaiton (a) Input image (b) superpixels (c) unary terms (d) our result (e) ground truth Summary Quantized Edge Full CRF model Approximation to Gaussian Edge CRF Helps to understand properties of Gaussian Edge CRF Efficient optimization of Quantized Edge full CRF with graph cuts Transform the original problem to a smaller domain Optimization quality significantly better than mean field inference

Recently Viewed Presentations

  • Using Peer Mentors to Promote Information Fluency Washington

    Using Peer Mentors to Promote Information Fluency Washington

    Background Roundtable discussions including faculty, IT staff, librarians Peer Mentors Program ACS grant Components of the Program Peer Mentors Components of the Program Equipping and leadership from faculty member, librarian, technologist Components of the Program Web Resources: Peer Mentors Held...
  • MRI 2315 Warehousing and Distribution 18 Jan 2016

    MRI 2315 Warehousing and Distribution 18 Jan 2016

    Stuart Emmett Excellence in Warehouse Management: How to minimize Costs and Maximise Value ( June 13, 2005) Assessment Methods and Types . Quiz 10% - written (week 3) Mid Term Test 15% - written (Week 7) Assignment 35% - written...
  • Visualization of Heterogeneous Data Mike Cammarano Xin (Luna)

    Visualization of Heterogeneous Data Mike Cammarano Xin (Luna)

    Visualization of Heterogeneous Data. Mike Cammarano. Xin (Luna) Dong. Bryan Chan. Jeff Klingner. Justin Talbot. Alon Halevy. Pat Hanrahan. Good morning, all. My name is Mike Cammarano, and I'm pleased to present this work on behalf of multiple collaborators at...
  • Android GUI - dforeman.cs.binghamton.edu

    Android GUI - dforeman.cs.binghamton.edu

    Android Developer Tools. To add the ADT plugin to Eclipse: Start Eclipse, then select Help > Install New Software.. Click . Add, in the top-right corner. In the Add Repository dialog that appears
  • TYPES OF WHITETOPPING - Delhi Development Authority

    TYPES OF WHITETOPPING - Delhi Development Authority

    central road research institute 22-Jun-16 White Topping is defined as a Portland Cement Concrete (PCC) overlay constructed on the top of the existing distressed bituminous pavement
  • Professionalism Lapses as Medical Errors - Wiki@UCSF

    Professionalism Lapses as Medical Errors - [email protected]

    Dealing with Professionalism Lapses: Beyond "he said, she said" Catherine Lucey MD UCSF December 18, 2012 A common scenario A nurse files a complaint through the incident report system about a resident, stating that he is rude and arrogant and...
  • A Tale of Two Proposals - ICTR

    A Tale of Two Proposals - ICTR

    Characterization of retinal thickness in children with neurofibromatosis type 1 and optic pathway gliomas using optical coherence tomography ... on one machine Complete retinal thickness measured in each eye once Average retinal thickness will be used in analysis Additional Testing...
  • Decolonization in Asia - scott.k12.ky.us

    Decolonization in Asia - scott.k12.ky.us

    Asian Tigers Hong Kong and Singapore Huge financial centers South Korea and Taiwan. hubs of global manufacturing in automobile/electronic components and information