Fast Approximate Energy Minimization via Graph Cuts

1 Fast Approximate Energy Minimization via Graph CutsYuri BoykovOlga VekslerRamin ZabihComputer Science DepartmentCornell UniversityIthaca, NY 14853 AbstractIn this paper we address the problem of minimizinga large class of Energy functions that occur in earlyvision. The major restriction is that the Energy func-tion's smoothness term must only involve pairs of pix-els. We propose two algorithms that use Graph cuts tocompute a local minimum even when very large movesare allowed. The rst move we consider is an - -swap: for a pair of labels ; , this move exchangesthe labels between an arbitrary set of pixels labeled and another arbitrary set labeled .Our rstalgo-rithm generates a labeling such that there is no swapmove that decreases the Energy . The second move weconsider is an -expansion: for a label , this moveassigns an arbitrary set of pixels the label.

2 Oursec-ond algorithm, which requires the smoothness term tobe a metric, generates a labeling such that there is noexpansion move that decreases the Energy . Moreover,this solution is within a known factor of the global min-imum. We experimentally demonstrate the e ective-ness of our approach on image restoration, stereo Energy Minimization in early visionMany early vision problems require estimatingsome spatially varying quantity (such as intensity ordisparity) from noisy measurements. Such quantitiestend to be piecewise smooth; they vary smoothly atmost points, but change dramatically at object bound-aries. Every pixelp2 Pmust be assigned a label insome setL; for motion or stereo, the labels are dispar-ities, while for image restoration they represent inten-sities.

3 The goal is to nd a labelingfthat assigns eachpixelp2 Palabelfp2L,wherefis both piecewisesmooth and consistent with the observed vision problems can be naturally formulatedin terms of Energy Minimization . In this framework,one seeks the labelingfthat minimizes the energyE(f)=Esmooth(f)+Edata(f):HereEsmoo thmeasures the extent to whichfis notpiecewise smooth, whileEdatameasures the disagree-ment betweenfand the observed data. Many di er-ent Energy functions have been proposed in the liter-ature. The form ofEdatais typicallyEdata(f)=Xp2 PDp(fp);whereDpmeasures how appropriate a label is for thepixelpgiven the observed data. In image restoration,for example,Dp(fp) is typically (fp ip)2,whereipisthe observed intensity of the choice ofEsmoothis a critical issue, and manydi erent functions have been proposed.

4 For exam-ple, in regularization-based vision [6],Esmoothmakesfsmooth everywhere. This leads to poor results atobject boundaries. Energy functions that do not havethis problem are number of discontinuity-preserving Energy func-tions have been proposed (see for example [7]). Gemanand Geman's seminal paper [3] gave a Bayesian in-terpretation of many Energy functions, and proposeda discontinuity-preserving Energy function based onMarkov Random Fields (MRF's).The major di culty with Energy Minimization forearly vision lies in the enormous computational these Energy functions have many local min-ima ( , they are non-convex). Worse still, the spaceof possible labelings has dimensionjPj, which is manythousands. There have been numerous attempts todesign fast algorithms for Energy Minimization .

5 Simu-lated annealing was popularized in computer vision by[3], and is widely used since it can optimize an arbi-trary Energy function. Unfortunately, minimizing anarbitrary Energy function requires exponential time,and as a consequence simulated annealing is very practice, annealing is ine cient partly because ateach step it changes the value of a single Energy functions that we consider in this pa-per arise in a variety of di erent contexts, includingthe Bayesian labeling of MRF's. We allowDpto bearbitrary, and consider smoothing terms of the formEsmooth=Xfp;qg2 NVfp;qg(fp;fq);(1)whereNis the set of pairs of adjacent pixels. In spe-cial cases such energies can be minimized exactly. Ifthe number of possible labels isjLj= 2 then the exactsolution can be found in polinomial time by comput-ing a minimum cost cut on a certain Graph [4].

6 IfLis a nite 1D set and the interaction potential isV(fp;fq)=jfp fqjthen the exact minimum can alsobe found e ciently via Graph cuts [5, 2]. In general,however, the problem is NP-hard [8].In this paper we develop algorithms that approx-imately minimize energyE(f) for an arbitrary niteset of labelsLunder two fairly general classes of in-teraction potentialsV: semi-metric and asemi-metricon the space of labelsLif forany pair of labels ; 2 Lit satis es two properties:V( ; )=V( ; ) 0andV( ; )=0, = .IfValso satis es the triangle inequalityV( ; ) V( ; )+V( ; )(2)for any ; ; inLthenVis called both semi-metric and metric include impor-tant cases of discontinuity-preserving interaction po-tentials. For example, the truncatedL2distanceV( ; )=min(K;jj jj) and the Potts interactionpenaltyV= (fp6=fq) are both algorithms described in this paper generalizethe approach that we originally developed for the caseof the Potts model [2].

7 In particular, we compute a la-beling which is a local minimum even when very largemoves are allowed. We begin with an overview of ourenergy Minimization algorithms, which are based ongraph cuts. Our rst algorithm, described in section 3,is based on - -swap moves and works for any semi-metricVfp;qg's. Our second algorithm, described insection 4, is based on more interesting -expansionmoves but works only for metricVfp;qg's ( , the addi-tional triangle inequality constraint is required). Notethat -expansion moves produce a solution within aknown factor of the global minimum can be found in [8].2 Energy Minimization via Graph cutsThe most important property of these methods isthat they produce a local minimum even when largemoves are allowed. In this section, we discuss themoves we allow, which are best described in terms ofpartitions.

8 We sketch the algorithms and list their ba-sic properties. We then formally introduce the notionof a Graph cut, which is the basis for our Start with an arbitrary labelingf2. Set success := 03. For each pair of labelsf ; g Find^f= arg minE(f0)amongf0withinone - swap off(Section 3) IfE(^f)<E(f), setf:=^fand success := 14. If success = 1 goto 25. Returnf1. Start with an arbitrary labelingf2. Set success := 03. For each label Find^f= arg minE(f0)amongf0withinone -expansion off(Section 4) IfE(^f)<E(f), setf:=^fand success := 14. If success = 1 goto 25. ReturnfFigure 1: Our swap move algorithm (top) and expan-sion move algorithm (bottom). Partitions and move spacesAny labelingfcan be uniquely represented by apartition of image pixelsP=fPljl2 LgwherePl=fp2 Pjfp=lgis a subset of pixels assigned there is an obvious one to one correspondencebetween labelingsfand partitionsP, we can use thesenotions a pair of labels ; , a move from a partitionP(labelingf) to a new partitionP0(labelingf0)iscalled an - swapifPl=P0lfor any labell6=.

9 This means that the only di erence betweenPandP0is that some pixels that were labeled inPare nowlabeled inP0, and some pixels that were labeled inPare now labeled a label , a move from a partitionP(labelingf) to a new partitionP0(labelingf0) is called an -expansionifP P0 andP0l Plfor any labell6= .In other words, an -expansion move allows any set ofimage pixels to change their labels to .Note that a move which gives an arbitrary label toa single pixel is both an - swap and an a consequence, the standard move space used inannealing is a special case of our move Algorithms and propertiesWe have developed two Energy Minimization algo-rithms, which are shown in gure 1. The structure ofthe algorithms is quite similar. We will call a singleexecution of steps { aniteration, and an execu-tion of steps 2{4 acycle.}}

10 In each cycle, the algorithmperforms an iteration for every label (expansion movealgorithm) or for every pair of labels (swap move al-gorithm), in a certain order that can be xed or ran-dom. A cycle is successful if a strictly better labelingis found at any iteration. The algorithm stops afterthe rst unsuccessful cycle since no further improve-ment is possible. Obviously, a cycle in the swap movealgorithm takesjLj2iterations, and a cycle in the ex-pansion move algorithm algorithms have several important proper-ties. First, the algorithms are guaranteed to ter-minate in a nite number of cycles; in fact, underfairly general assumptions we can prove terminationinO(jPj) cycles [8]. However, in the experimentswe report in section 5, the algorithm stops after afew cycles and most of the improvements occur dur-ing the rst cycle.