What energy functions can be minimized via graph cuts?
What energy functions can be minimized via graph cuts?
复制标题
DOI：
10.1109/tpami.2004.1262177
复制
发表时间：
2004-02-01
影响因子：
23.6
通讯作者：
Zabih, R
中科院分区：
文献类型：
--
作者：
Kolmogorov, V;Zabih, R
在过去的几年里，一些基于图割的新算法被用来解决计算机视觉中的能量最小化问题。这些技术中的每一种都构建了一个图，使得图上的最小割也使能量最小化。然而，由于这些图的构造是复杂的，并且高度特定于特定的能量函数，所以到目前为止，图切割的应用有限。本文给出了可用图割最小化的能量函数的一个刻画。我们的结果仅限于二元变量函数。然而，我们的工作推广了许多前人的构造，很容易适用于涉及大量标签的视觉问题，如立体、运动、图像恢复和场景重建。在能量函数中，我们给出了使用图割可以最小化哪些能量函数的精确特征，这些能量函数可以写成包含三个或更少二元变量的项的和。我们还提供了一种通用结构来最小化这样的能量函数。最后，我们给出了用图割最小化二元变量能量函数的一个必要条件。正在考虑使用图形切割来优化特定能量函数的研究人员可以使用我们的结果来确定这是否可能，然后按照我们的结构来创建适当的图形。软件实现是免费提供的。
In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available.