Efficient Graph-Based Energy Minimization Methods in Computer Vision
Efficient Graph-Based Energy Minimization Methods in Computer Vision
复制标题
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
O. Veksler
中科院分区：
文献类型：
--
作者：
O. Veksler
能量最小化是计算机视觉的一种优雅方法。由于成像过程的不确定性和视觉解释的模糊性，视觉问题通常有多种解决方案。能量函数对问题约束进行编码，其最小值给出最优解。尽管有许多优点，但这种方法受到高计算成本的严重限制。我的论文的主要贡献在于为几类重要的能量函数开发了有效的组合优化算法，这些函数包含处处光滑、分段常数和分段光滑先验。这些先验分别假设待估计的量在其域内平滑变化，由若干恒定值的块组成，或由若干平滑变化值的块组成。该算法依赖于图切作为一种强大的优化技术。对于一定的处处平滑先验，我们提出了一种通过计算单个图割来求精确最小值的算法。这种方法最适合于无不连续的量的估计。但即使存在不连续，该方法在某些情况下也能产生良好的结果。运行时间为低阶多项式。对于几大类分段平滑先验，我们开发了两种近似算法（在这些情况下，我们证明了NP-hard的精确最小化）。这些算法在有趣的大移动空间中产生局部最小值。此外，其中一个算法在已知的最优因子范围内找到解。该算法是迭代的，每次迭代计算几个图切。由于特殊的图结构，每次迭代的运行时间是有效的线性。在实践中，只需要几次迭代就可以收敛。此外，大多数进展发生在第一次迭代中。对于一定的分段常数先验，我们采用了分段平滑先验的算法。其中一个在最优解的两倍范围内找到解。此外，我们还开发了第三种算法，该算法在另一个移动空间中找到局部最小值。我们证明了我们的方法在图像恢复、立体和运动方面的有效性。对于具有真实值的数据，我们的方法明显优于标准方法。
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.