CS664 Lecture 10 Graph cuts for more than two labels Some material taken from Olga Veksler University of Western Ontario http www csd uwo ca faculty olga Recap of recap Markov chains allow you to sample from a high dimensional distribution Biased walk on a graph Metropolis Consider all possible binary images The distribution we want makes the low energy solutions have high probability In an unbiased walk we get everywhere equally often So we use Metropolis intead Graph cuts do this better 2 Recap We want to minimize the energy E f Binary labeling problem can be solved exactly with graph cuts Lots of cool applications 3 Non binary Labeling Problem In many problems the number of labels is larger than 2 General image restoration stereo correspondence motion etc Everything else stays the same Each pixel site has preferences for some labels over the others We seek a solution where nearby sites pixels are assigned the same label as much as possible 4 Example Image Denoising restored image noisy image restore This is basically same problem as fax image restoration only for non binary image The number of labels is 256 all grayscale values Labels are integers in the range 0 1 255 In restored image pixels should be close to original intensity DP label abs label I p Pixels with similar intensity should group together 5 Example Stereo Matching Left image Right image x1 y x2 y Disparity is x1 x2 Can make this non negative in a limited range Labels All possible disparities 0 1 max 6 Example Stereo Matching Left image Disparity map Depth map Here Disparity map is colored for visibility Right image Dark red 14 medium red 10 medium green 6 dark green 5 A possible data term Corresponding pixels are expected to have similar colors For disparity d DP d abs LeftImage p RightImage p d If p x y p d x d y 7 Multi label Energy Many different energy functions in multi label case Our old energy function still makes sense E L DP Lp p w L pq N pq p Lq It still says the same thing except that the number of labels that can be assigned to a pixel is more than 2 Find a labeling of pixels s t each pixel is assigned a label it likes as much as possible and nearby pixels are assigned the same label as much as possible Unfortunately minimizing this energy in case of more than 2 labels is NP hard 8 Multi label Energy Linear Interactions The following energy can be minimized exactly with an s t graph cut E L DP Lp p w pq N pq Lp Lq Data term is as before Penalty for discontinuity is now proportional to the discontinuity size If neighboring pixels p and q do not have the same label penalty is the absolute difference between the labels multiplied by wpq Thus the larger is the difference between their labels Lp and Lq the more costly is it assigning label Lp to pixel p and label Lq to pixel q Energy function with such prior term is said to have linear interactions 9 Multi label Energy E L D L w L L P p p pq N pq p Suppose there are d 1 labels 0 1 d For each pixel p create d vertices named p1 p2 pd Create d 1 t links for each pixel p t link 1 goes between source s and p1 and has weight Dp 0 K t link 2 goes between vertices p1 and p2 and has weight Dp 1 K t link d 1 goes between source pd and p2 and has weight Dp 1 K q Dp 0 p1 Dp 1 p2 p6 For neighboring pixels p and q for all i pi is connected Dp 6 to qi by an n link of weight wpq If t link i is cut then pixel p is assigned disparity i K is large enough to ensure that only one t link per pixel is in a minimum cut for example K sum of all n links wpq wpq wpq Dq 0 q1 q2 Dq 1 q6 Dq 6 10 Multi label Energy E L D L w L L P p p pq N pq p The mincut severs only one t link per pixel If a cut severs t link i for pixel p and t link j for pixel q it must sever all n links between pi and qj 1 If a cut severs t link i for pixel p and t link j for pixel q it must sever all n links between pi and qj 1 Thus the cost of the severed n links is exactly as required by the energy function q Dp 0 p1 Dp 1 p2 p6 wpq wpq wpq Dp 6 Dq 0 q1 q2 Dq 1 q6 Dq 6 Notice that the cost of severed t links contributes to the data term the cost of severed n links contributes to the prior term 11 Over smoothing E L D L w L L P p p pq N pq p q Above energy can be minimized exactly but there are serious problems with it The problem is that it is not discontinuity preserving Sharp large Lp Lq discontinuities are penalized too much Instead of one large discontinuity it is cheaper to create a few smaller discontinuities restoration with linear interactions 12 Discontinuity Preserving Interactions V E L D L w L L P p p pq N pq p q In order to be discontinuity preserving pixel interaction function V Lp Lq should not grow to large At some point we decide that there is a discontinuity between neighboring pixels and assign a fixed penalty for this discontinuity independent of the size of this discontinuity V dL dL Lp Lq 13 Generalization Ishikawa 03 showed how to handle any convex function V Add diagonal n links between pixel nodes With the right choice of edge weights Labels must be 0 1 2 Graph has P L nodes Space is more expensive than time Linear model is the most robust nonrobust solution Clear line between easy and NP hard 14 Handling robust V How do we handle the problem we really want to solve Multiple labels Discontinuity preserving robust V Can we generalize the binary construction Initially we will focus on the Potts model Raises all the major issues Surprisingly important and flexible 15 Min cost multiway cut problem Graphs with a set of terminal nodes Multiway cut is a set of edges that separates all terminals Cost of a cut is the sum of edge weights 16 Potts model result Theorem BVZ98 Minimizing E f D p f p p w pq T f p f q pq N is equivalent to finding a minimum cost multiway cut on a certain graph Note we will construct graphs where all terminals are connected to all non terminals Some of these links will not be shown for legibility 17 Multiway cuts are labelings 18 t link p l1 K Dp l1 n link q l2 …