|
通用削减：计算高阶MRF-MAP的一种有效的最优推理算法
Generic Cuts: An Efficient Algorithm for Optimal Inference in Higher Order MRF-MAP |
|
| |
| 课程网址: |
http://videolectures.net/eccv2012_arora_algorithm/
|
| 主讲教师: |
Laurent Itti, Chetan Arora, Ramin Zabih
|
| 开课单位: |
印度德里技术学院
|
| 开课时间: |
2012-11-12
|
| 课程语种: |
英语
|
| 中文简介: |
我们提出了一种名为Generic Cuts的新算法，用于计算2个标签MRF MAP问题的最优解，其中高阶clique势能满足子模块。该算法在最坏的情况下在timeO（2kn3）中运行（k是clique顺序，n是像素数）。引入了一个特殊的小工具来模拟高阶集团中的流程，并指定了构建流程图的技术。基于优化问题的原始对偶结构，边缘和切割的容量概念被概括为定义流动问题。我们证明在这个流程图中，最大流量等于最小切割，当电位是子模块时，这也是问题的最佳解决方案。这与优化涉及高阶势的布尔能量函数的所有流行技术形成对比，所述布尔能量函数包括基于对二次势函数的约简的那些，其甚至对于子模函数也仅提供近似解。我们通过实验证明，我们对Generic Cuts算法的实现比所有算法都要快一个数量级，包括基于减少的算法，其子模块电位的输出接近最优。
|
| 课程简介: |
We propose a new algorithm called Generic Cuts for computing optimal solutions to 2 label MRF-MAP problems with higher order clique potentials satisfying submodularity. The algorithm runs in time O(2kn3) in the worst case (k is clique order and n is the number of pixels). A special gadget is introduced to model flows in a high order clique and a technique for building a flow graph is specified. Based on the primal dual structure of the optimization problem the notions of capacity of an edge and cut are generalized to define a flow problem. We show that in this flow graph max flow is equal to min cut which also is the optimal solution to the problem when potentials are submodular. This is in contrast to all prevalent techniques of optimizing Boolean energy functions involving higher order potentials including those based on reductions to quadratic potential functions which provide only approximate solutions even for submodular functions. We show experimentally that our implementation of the Generic Cuts algorithm is more than an order of magnitude faster than all algorithms including reduction based whose outputs on submodular potentials are near optimal.
|
| 关 键 词: |
高阶集团; 流程图; 对偶结构
|
| 课程来源: |
视频讲座网
|
| 最后编审: |
2020-07-31：yumf
|
| 阅读次数: |
95
|
|
图 书 馆