智能感知与计算研究中心知识库

Markov Random Field (MRF) is an important tool and has been widely used in many vision tasks. Thus, the optimization of MRFs is a problem of fundamental importance.

Recently, Veskler and Kumar et. al propose the range move algorithms, which are one of the most successful solvers to this problem. However, two problems have limited the

applicability of previous range move algorithms: 1) They are limited in the types of energies they can handle (i.e. only truncated convex functions); 2) These algorithms tend to be very slow compared to other graph-cut based algorithms (e.g. a-expansion and ab-swap). In this paper, we propose a generalized range swap algorithm (GRSA) for efficient

optimization of MRFs. To address the first problem, we extend the GRSA to arbitrary semimetric energies by restricting the chosen labels in each move so that the energy is

submodular on the chosen subset. Furthermore, to feasibly choose the labels satisfying the submodular condition, we provide a sufficient condition of the submodularity. For the second problem, unlike previous range move algorithms which execute the set of all possible range moves, we dynamically obtain the iterative moves by solving a set cover problem, which greatly reduces the number of moves during the optimization. Experiments show that the GRSA offers a

great speedup over previous range swap algorithms, while

it obtains competitive solutions.

基于马尔可夫随机场的结构建模研究在计算机视觉领域，尤其是物体识别任务中得到越来越多的关注，而随机场结构模型的快速推理对结构模型在实际问题中的广泛应用也有重要的作用。最近，Veskler 和 Kumar 等人提出了多标号移动（Range move）推理算法，并在随机场模型的推理上展现了很好的优化效果。和之前的标号移动算法只能考虑两个标号不同，Range move 算法在每次标号移动过程中可以考虑多个标号从而得到更大的搜索空间，因此，Range move 大大提高了算法的优化效果。然而，在多标号移动算法中仍有两个主要的问题限制了这类算法的应用性：1) 它们能够处理的能量函数非常有限（只能是截凸函数）；2) 和之前的基于标号移动的推理算法相比，他们的优化速度很慢。在本章中，我们提出两个广义的多标号移动算法（Generalized range move algorithms，GRMAs）来对随机场模型进行高效地推理。 为解决上述问题 1)，我们在每次的标号移动中限制所选取的标号集合满足子模条件，通过这种方法我们将 GRMAs 算法的应用范围扩展到任意能量函数的优化问题上。更为重要的，我们还提出了一个满足子模性质的充分条件来更为灵活地选取满足条件的标号集合。为了解决问题 2)，我们将动态标号移动问题转化为一个集合覆盖问题（Set cover problem），这样大大减少了优化过程中标号移动的个数。同时，我们在 GRMAs 算法的图割过程中也提出一个快速的构图方法。 实验表明 GRMAs 算法大大提高了之前多标号移动算法的推理速度，同时也得到了可观的推理效果。