| Energy minimization is an elegant approach to computer vision. Vision problems usually have many solutions due to uncertainties in the imaging process and ambiguities in visual interpretation. The energy function encodes the problem constraints, and its minimum gives the optimal solution. Despite numerous advantages, this approach is severely limited by the high computational cost.;The main contribution of my thesis lies in developing efficient combinatorial optimization algorithms for several important classes of energy functions which incorporate everywhere smooth, piecewise constant, and piecewise smooth priors. These priors assume, respectively, that the quantity to be estimated varies smoothly over its domain, consist of several pieces with constant values, or consist of several pieces with smoothly varying values. The algorithms rely on graph cuts as a powerful optimization technique.;For a certain everywhere smooth prior we develop an algorithm which finds the exact minimum by computing a single graph cut. This method is most suitable to estimate quantities without discontinuities. But even when discontinuities exist, the method produces good results in certain cases. The running time is low order polynomial.;For several wide classes of piecewise smooth priors we develop two approximation algorithms (we show that exact minimization in NP-hard in these cases). These algorithms produce a local minimum in interesting large move spaces. Furthermore, one of them finds a solution within a known factor from the optimum. The algorithms are iterative and compute several graph cuts at each iteration. The running time at each iteration is effectively linear due to the special graph structure. In practice it takes just a few iterations to converge. Moreover most of the progress happens during the first iteration.;For a certain piecewise constant prior we adapt the algorithms developed for the piecewise smooth prior. One of them finds a solution within a factor of two from the optimum. In addition we develop a third algorithm which finds a local minimum in yet another move space.;We demonstrate the effectiveness of our approach on image restoration, stereo, and motion. For the data with ground truth, our methods significantly outperform standard methods. |
