# UMass LIVING

## September 19, 2009

### (Sep 25 12-2pm) Pre-meeting Overview: Energy Minimization via Graph Cuts

Filed under: Uncategorized — umassliving @ 4:39 pm
Tags: ,

This week, continuing the theme of MAP inference, we’ll look at graph cut methods for energy minimization.

This will be the main paper: What Energy Functions Can Be Minimized via Graph Cuts? Komogorov, Zabih

This additional paper may help in understanding graph cuts: Fast Approximate Energy Minimization via Graph Cuts. Boykov, Veksler, Zabih.

There is no paper set yet for this week.  Some possibilities:

Variable Elimination, Constructing the Pseudo-tree, Min-fill, and Mini-bucket heuristic

A two week sequence of:

The first paper would be related to our previous reading, in that they do search with branch and bound.

Post your suggestions soon, with the aim of settling on a paper by mid-day Monday.

1. In “Fast Approximate Energy Minimization via Graph Cuts”, the authors at one point write, “these energy functions have many local minima (i.e. they are non-convex)”. While it doesn’t say this outright, this seems to suggest that to be able to find a global extremum, a function better be convex. I just wanted to point out that this is not the case. There are many many functions that are not convex but have a single global extremum.

Comment by Erik — September 22, 2009 @ 12:35 am

2. Again, in “Fast Approximate Energy Minimization via Graph Cuts”, the authors state that “In general, two-dimensional energy functions that arise in early vision cannot be solved efficiently via dynamic programming.”

I believe that with good heuristics and the proper dynamic programming techniques, many of these *can* be solved, even though it would be difficult or impossible to guarantee a polynomial runtime complexity.

Thus, it is important to realize that what the authors are saying is that in the worst case, dynamic programming will not work. That does not mean it is not an important tool to consider in practice, where, for some problems, one rarely or never encounters the worst case.

They also say that “dynamic programming is restricted essentially to energy functions in one-dimensional settings.”

This is also misleading. Dynamic programming can be used in multi-dimensional settings. See my 98-AAAI paper for an example in which we apply dynamic programming (A* search with stochastic context free grammars) to read math expressions.

Comment by Erik — September 22, 2009 @ 1:00 am

3. I think there is a typo in Table 13 on page 156 of the main paper. The equation holds for the (1,1) corner, but it doesn’t seem to hold for the other three corners. To make it hold, change the lead constant to $-\bar{E}(0,0)$, and then to the middle two terms, add $\bar{E}(0,0)$ to the non-zero terms.

Comment by Gary — September 24, 2009 @ 5:41 pm