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

  • OFC312 Administering Microsoft SharePoint Products and ...

    OFC312 Administering Microsoft SharePoint Products and ...

    May 11 Virtual Server hosted demo service specs due. May 21 FINAL PowerPoint due at . 5:00pm PST. Slide Design Resources. An event-approved graphics and images resources PowerPoint is located on the Speaker Portal. An event design guide is located...
  • Diapositiva 1 - WordPress.com

    Diapositiva 1 - WordPress.com

    Something that is abstract- basrteus Antonym of condemn- cecdae criticize hatefully- rbaete Synonym of apathetic- lacolsu A catastrophe- dbecael Besmirching something- fdeile Answers… Abstruse Accede Berate Callous Debacle Defile Identify the Synonyms…
  • He2 2011 - 2015

    He2 2011 - 2015

    Those that have already said farewell. Josh Martin. Lucy. Harris Smith. Triston Bosnjak. Bailey Casey
  • Not My Will, But Thine Be Done - Simple Bible Studies

    Not My Will, But Thine Be Done - Simple Bible Studies

    Not My Will, But Thine Be Done. God expects us to live by this same principle today. ... Their attitude was, "Not Thy Will, but mine, be done." ... that they that live should no longer live unto themselves, but...
  • Transfusion Medicine: Checklists and Challenges

    Transfusion Medicine: Checklists and Challenges

    Transfusion Medicine: Checklists and Challenges. LjiljanaPetkovic, MT(ASCP)SBBChecklist Technical Content Analyst. ... Defined responsibility of Laboratory Director and laboratory in perioperative and intraoperative programs. ... Checklist requirement now a Phase II.
  • Division Euglenophyta 1-Chlorophyll a , b ,carotene and

    Division Euglenophyta 1-Chlorophyll a , b ,carotene and

    Euglena. Euglenoids are typically elongate, spindle shaped organisms usually contain several chloroplasts per cell Which vary in appearance from discoid to star or ribbon-shaped . The presence of a surface pellicle, which gives the cell a striated appearance , In...
  • Using Quotations Within Quotations  When you use someone

    Using Quotations Within Quotations When you use someone

    quotation within a quotation. Let's take a look at some examples based on the quote below: Here's an example of a quotation within a quotation: In the sentence above, all of the copied words are in double quotation marks. The...
  • S T A P L E F O

    S T A P L E F O

    arrowroot, tapioca, sago. Look at Bacillus cereus. Have a chart of bacteria (we will add more to this in the meat unit). One bacteria has been done - add info for Bacillus cereus. Rest to be done later in the...