CS664 Lecture #8: Regularization, Annealing, Binary labeling problemsAnnouncementsRecapRobustness matters!Robustness matters RegularizationConvexityEnergy minimization for stereoSimulated annealingAnnealing schedulesIs it possible to do better?Binary labeling problemsBinary Labeling: MotivationBinary Labeling Problem : MotivationBinary Labeling ProblemBinary Labeling Problem: ConstraintsBinary Labeling Problem: Data Constraints Binary Labeling Problem: Data ConstraintsBinary Labeling Problem: Prior ConstraintsBinary Labeling: Data ConstraintsBinary Labeling Problem: Energy FormulationBinary Labeling Problem: Energy FormulationBinary Labeling Problem: Energy Formulations-t Graph Cuts for Binary Energy MinimizationMaximum flow problemMinimum cut problem Max flow/Min cut theoremFast algorithms for min cut“Augmenting Path” algorithms“Augmenting Path” algorithms“Augmenting Path” algorithmsImplementation notess-t Graph Cuts for Binary Energy Minimizations-t Graph Cuts for Binary Energy MinimizationExampleCS664 Lecture #8: Regularization, Annealing, Binary labeling problemsMuch material taken from:Olga Veksler, University of Western Ontariohttp://www.csd.uwo.ca/faculty/olga/2Announcements PS1 is on the web (finally!)– Efros & Leung only– Due on 10/6 Quiz 2 a week from today (Tuesday 9/27)– Coverage through today3 We want to minimize the energy E(f) If V increases too much we will over-smoothRecap4Robustness matters!linear Vtruncated linear V5Robustness matters6Regularization When the labels are numbers and the separation costs aren’t robust, this problem has been extensively studied– “Tikhonov regularization”7Convexity Why is this example “easy”?– The sum of convex functions is convex– What about the sum of non-convex functions? Most of optimization is convex– Numerical methods, conjugate gradient, etc8Energy minimization for stereo We can just throw Metropolis at this energy function with low temperature– Pick a non-convex V– Can even add more complex terms Why not?– Doesn’t work very well • Not in our lifetimes (or the Universe’s…) Is there anything better we can do?9Simulated annealing Start at a high T, run Metropolis– Starting at this answer, lower T– This is a continuation method (like GNC) Annealing had a big success for TSP– But for somewhat non-obvious reasons10Annealing schedules There are schedules that guarantee convergence– But, of course, they are very slow– Start at a high temperature– To divide the temperature at the 100thiteration by 2, wait to 10,000thiteration– Worse than exhaustive search?11Is it possible to do better? Energy minimization is now known to be NP-hard– Potts model energy, with >2 labels– Even holds on a grid12Binary labeling problems Consider the case of two labels only– Surprisingly important• Lots of nice applications• Same basic ideas used for more labels There is a fast exact solution!– Turn a problem you don’t know how to solve into a problem you do (reduction)– Originally done for job scheduling problems by Stone (1977)– First applied to images by Greig, Porteus & Seheult (1989)13Binary Labeling: Motivation Suppose we receive a noisy fax:– Some black pixels in the original image were flipped to white pixels, and some white pixels were flipped to black  We want to try to clean up (or restore) the original image:original imagerestored image This problem is called image restoration (denoising)14Binary Labeling Problem : Motivation Fax image is binary: each pixel is either– black (stored as 0)– or white (stored as 1) What we know:1) In the restored image, each pixels should also be either black (0) or white (1)2) Data Constraint: if a pixel is black in the original image, it is more likely to be black in the restored image; and a white pixel in the original image is more likely to be white in the restored image3) Prior Constraint: in the restored image, white pixels should form coherent groups, as should black pixelsoriginal imagerestored image15Binary Labeling Problem We can formulate our restoration problem as a labeling problem:– Labels: black (0) and white (1)– Set of sites: all image pixels• I will say set of “sites” or set of pixels interchangeablyoriginal imageset of sites P, and one possible labeling• Assign a label to each site (either the black or the white label) s.t.– If a pixel is black (white) in the original image, it is more likely to get the black (white) label– Black labeled pixels tend to group together, and white labeled pixels tend to group together16Binary Labeling Problem: Constraints Our Constraints:1. If a pixel is black (white) in the original image, it is more likely to get the black (white) label2. Black labeled pixels tend to group together, and white labeled pixels tend to group togetheroriginal imagegood labelingbad labeling(constraint 1)bad labeling(constraint 2)17Binary Labeling Problem: Data Constraints  How can we find a a good labeling (i.e., satisfying our constraints)?original imagea good labeling L Formulate and minimize an energy function on labelings L:•Let Lpbe the label assigned to pixel p– Lp= 0 or Lp= 1•Let I(p) be the intensity of pixel p in the original image• Data constraint is modeled by the Data Penalty DP(LP) – DP(0) < DP(1) if I(p) = 0– DP(0) > DP(1) if I(p) = 118Binary Labeling Problem: Data Constraints In our example, we can make– if I(p) = black thenDP(black) = 0 DP(white) = 4– if I(p) = white thenDP(black) = 4 DP(white) = 0original imagea good labeling L To figure out how well image as a whole satisfies the data constraint, sum up data terms over all image pixels: ()∑ppPLD19Binary Labeling Problem: Prior Constraints To model our prior constraints, simply count the number “discontinuities” in a labeling L:– There is a discontinuity between pixels p and q if labels pand q have different labels– The more pixels with equal labels group together in coherent groups, the less discontinuities there are31 discontinuitiessome discontinuitiesare marked8 discontinuitiesall discontinuitiesare marked20Binary Labeling: Data Constraints How to count the number of discontinuities in a labeling L?– Let N be the set of all adjacent pixels– Thus our N consists of edges between immediately adjacent pixels31 discontinuities•Let I(b) be the identity function•I(b) =1 when its argument