图割理论在视觉能量最小化中的实验比较

需积分: 50 106 浏览量更新于2024-07-27 收藏 615KB PDF 举报

"这篇论文对比了图割理论在能量最小化中的应用，特别是在计算机视觉领域的实验比较，包括不同的最小割/最大流算法的效率。" 在计算机视觉领域，图割理论（Graph Cut Theory）已经成为精确近似能量最小化的重要工具。自[15, 31, 19, 8, 25, 5]这些文献以来，最小割/最大流算法在处理低级视觉任务时的效用不断提升。图割理论的核心是将复杂的优化问题转化为寻找图中的最小割或最大流，以此来分割图像或者进行像素分类。这篇发表在IEEE Transactions on PAMI (模式分析与机器智能)期刊2004年第26卷第9期的文章，由Yuri Boykov和Vladimir Kolmogorov撰写，对多种标准算法的运行时间进行了实验比较，同时也引入了他们新开发的一种算法。文中涉及的算法包括Goldberg-Tarjan风格的"push-relabel"方法和基于Ford-Fulkerson风格的"增广路径"算法。这两种类型的方法在多项式时间复杂性上有所不同，但在实际应用效率方面的研究主要集中在计算机视觉领域之外。作者们通过一系列典型图像恢复、立体视觉和分割问题的实例，对这些算法进行了基准测试。这种比较有助于理解在特定视觉任务中哪种算法更具优势，从而为实际应用提供指导。例如，在图像修复中，最小割算法可能用于找到最佳的像素连接以恢复损坏的图像部分；在立体视觉中，可以利用这些算法来估计场景的深度信息；而在图像分割中，它们可以帮助确定像素的类别归属。这篇论文是关于如何利用图割理论有效地解决能量最小化问题的重要资源，对于从事计算机视觉研究或相关应用开发的人员来说，它提供了一种评估和选择合适算法的依据。通过深入理解这些算法的性能特点，研究人员和工程师可以更好地优化他们的解决方案，提高算法的执行效率和视觉结果的质量。

In IEEE Transactions on PAMI, Vol. 26, No. 9, pp. 1124-1137, Sept. 2004 p.7

one terminal. Therefore, any cut corresponds to some assignment of pixels (nodes) to labels

(terminals). If edge weights are appropriately set based on parameters of an energy, a minimum

cost cut will corresp ond to a labeling with the minimum value of this energy.

2.2 Standard Algorithms in Combinatorial Optimization

An important fact in combinatorial optimization is that there are polynomial algorithms for min-

cut/max-ﬂow problems o n directed weighted graphs with two terminals. Most of the algorithms

belong to one of the following two groups: Goldberg-Tarjan style “push-relabel” methods [1 4]

and algorithms based on Ford-Fulkerson style “a ugmenting paths” [1 3].

Standard augmenting paths based algo r ithms, such as Dinic algorithm [12], work by pushing

ﬂow along non-saturated paths from the source to the sink until the maximum ﬂow in the graph

G is reached. A typical augmenting path algor ithm stores information about the distribution

of the current s → t ﬂow f among the edges of G using a residual graph G

. The topology

of G

is identical to G but capacity of an edge in G

reﬂects the r esidual capacity of the same

edge in G g iven the amount of ﬂow already in the edge. At the initialization there is no ﬂow

from the source to the sink (f=0) and edge capacities in the residual graph G

are equal to the

original capacities in G. At each new iteration the algorithm ﬁnds the shortest s → t path along

non-saturated edges of the residual g r aph. If a path is found then the algo rithm augments it by

pushing the maximum possible ﬂow df t hat saturates at least one of the edges in the path. The

residual capacities of edges in the path are reduced by df while the residual capacities of the

reverse edges are increased by df. Each augmentation increases the total ﬂow from the source

to the sink f = f + df. The maximum ﬂow is reached when any s → t path crosses at least one

saturated edge in the residual gr aph G

Dinic a lg orithm uses breadth-ﬁrst search to ﬁnd the shortest paths from s to t on the residual

graph G

. After all shortest paths of a ﬁxed length k are saturated, the algorithm starts the

breadth-ﬁrst search for s → t paths of length k + 1 f r om scratch. Note that the use of shortest

paths is an important factor that improves theoretical running time complexities for algorithms

Diﬀerent graph-based energy minimization methods may use diﬀerent graph constructions, as well as, diﬀerent

rules for converting graph cuts into image labelings. Details for each method are described in the original

publications.

剩余33页未读，继续阅读

ddd13659209327

粉丝: 0
资源: 2

图割理论在视觉能量最小化中的实验比较

AutoHex:使用能量最小化技术从geoJSON边界文件创建hexmaps

基于能量最小化和图割理论的虚拟机集群部署方法

虚拟机集群部署：能量最小化与图割理论结合的新策略

关于在FiWi增强型LTE-A HetNet中最小化能耗

多张图片的切割MATLAB程序 grabcut 图割

MRF+NC 图像切割

Ncut_multiscale,多尺度图切超像素

LMS理论背景

matlab代码专利软件著作权-bgs-gcut:基于图形切割的背景减法

denoisingWithGraphCuts:使用图形切割的图像去噪（使用 Fusion Moves 和 Min-Cut Max-Flow）。 这只是概念示例的证明

最新资源

denoisingWithGraphCuts:使用图形切割的图像去噪（使用 Fusion Moves 和 Min-Cut Max-Flow）。这只是概念示例的证明