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
