Minimizing Dynamic and Higher Order Energy Functions using Graph Cuts

Over the last few years energy minimization has emerged as an indispensable tool in computer vision. The primary reason for this rising popularity has been the successes of efficient graph cut based minimization algorithms in solving many low level vision problems such as image segmentation, object reconstruction, image restoration and disparity estimation. The scale and form of computer vision problems introduce many challenges in energy minimization. In this dissertation, I will focus on some aspects of these problems.

The first problem I address relates to the efficient and exact minimization of groups of similar functions which are known to be solvable in polynomial time. I will present a novel dynamic algorithm for minimizing such functions. This algorithm reuses computation from previous problem instances to solve new instances resulting in a substantial improvement in the running time. I will present the results of using this approach on the problems of interactive image segmentation, image segmentation in video, human pose estimation and segmentation, and measuring uncertainty of solutions obtained by minimizing energy functions.

The second part of my dissertation will deal with the minimization of multilabel higher order functions which are np-hard to minimize. These functions are able to model interactions among groups of random variables and can be used to formulate many vision problems. The runtime complexity of commonly used algorithms for approximate energy minimization such as Max-product Belief Propagation or Tree-reweighted message passing grows exponentially with the clique size, which makes them inapplicable to problems with even moderate sized cliques. I will show how certain higher order energy functions can be minimized using the graph cut based expansion and swap move algorithms. This method is extremely efficient and is able to handle cliques involving thousands of variables. I will use these higher order energy functions to model the problems of object segmentation and recognition, and texture segmentation. The results of this approach will be compared with those obtained using conventional methods which model these problems using second order energy functions.