CASIA OpenIR  > 智能感知与计算研究中心
GRSA: Generalized Range Swap Algorithm for the Efficient Optimization of MRFs
Liu KW(刘康伟); Zhang JG(张俊格); Yang PP(杨沛沛); Huang KQ(黄凯奇); Huang KQ(黄凯奇)
2015-06
Conference Name2015 IEEE Conference on Computer Vision and Pattern Recognition
Source Publication2015 IEEE Conference on Computer Vision and Pattern Recognition
Conference Date2015-6
Conference Place美国
Abstract
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.
Other Abstract
基于马尔可夫随机场的结构建模研究在计算机视觉领域,尤其是物体识别任务中得到越来越多的关注,而随机场结构模型的快速推理对结构模型在实际问题中的广泛应用也有重要的作用。最近,Veskler 和 Kumar 等人提出了多标号移动(Range move)推理算法,并在随机场模型的推理上展现了很好的优化效果。和之前的标号移动算法只能考虑两个标号不同,Range move 算法在每次标号移动过程中可以考虑多个标号从而得到更大的搜索空间,因此,Range move 大大提高了算法的优化效果。然而,在多标号移动算法中仍有两个主要的问题限制了这类算法的应用性:1) 它们能够处理的能量函数非常有限(只能是截凸函数);2) 和之前的基于标号移动的推理算法相比,他们的优化速度很慢。在本章中,我们提出两个广义的多标号移动算法(Generalized range move algorithms,GRMAs)来对随机场模型进行高效地推理。 为解决上述问题 1),我们在每次的标号移动中限制所选取的标号集合满足子模条件,通过这种方法我们将 GRMAs 算法的应用范围扩展到任意能量函数的优化问题上。更为重要的,我们还提出了一个满足子模性质的充分条件来更为灵活地选取满足条件的标号集合。为了解决问题 2),我们将动态标号移动问题转化为一个集合覆盖问题(Set cover problem),这样大大减少了优化过程中标号移动的个数。同时,我们在 GRMAs 算法的图割过程中也提出一个快速的构图方法。 实验表明 GRMAs 算法大大提高了之前多标号移动算法的推理速度,同时也得到了可观的推理效果。
 
Keyword图割 马尔科夫随机场
Indexed ByEI
Document Type会议论文
Identifierhttp://ir.ia.ac.cn/handle/173211/11828
Collection智能感知与计算研究中心
Corresponding AuthorHuang KQ(黄凯奇)
Affiliation中国科学院自动化研究所
Recommended Citation
GB/T 7714
Liu KW,Zhang JG,Yang PP,et al. GRSA: Generalized Range Swap Algorithm for the Efficient Optimization of MRFs[C],2015.
Files in This Item: Download All
File Name/Size DocType Version Access License
Liu_GRSA_Generalized(2405KB)会议论文 开放获取CC BY-NC-SAView Download
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Liu KW(刘康伟)]'s Articles
[Zhang JG(张俊格)]'s Articles
[Yang PP(杨沛沛)]'s Articles
Baidu academic
Similar articles in Baidu academic
[Liu KW(刘康伟)]'s Articles
[Zhang JG(张俊格)]'s Articles
[Yang PP(杨沛沛)]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Liu KW(刘康伟)]'s Articles
[Zhang JG(张俊格)]'s Articles
[Yang PP(杨沛沛)]'s Articles
Terms of Use
No data!
Social Bookmark/Share
File name: Liu_GRSA_Generalized_Range_2015_CVPR_paper.pdf
Format: Adobe PDF
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.