Academic
Publications
Higher-order clique reduction in binary graph cut

Higher-order clique reduction in binary graph cut,10.1109/CVPRW.2009.5206689,Hiroshi Ishikawa

Higher-order clique reduction in binary graph cut   (Citations: 28)
BibTex | RIS | RefWorks Download
We introduce a new technique that can reduce any higher-order Markov random field with binary labels into a first-order one that has the same minima as the original. Moreover, we combine the reduction with the fusion-move and QPBO algorithms to optimize higher-order multi-label problems. While many vision problems today are formu- lated as energy minimization problems, they have mostly been limited to using first-order energies, which consist of unary and pairwise clique potentials, with a few exceptions that consider triples. This is because of the lack of efficient algorithms to optimize energies with higher-order interac- tions. Our algorithm challenges this restriction that limits the representational power of the models, so that higher- order energies can be used to capture the rich statistics of natural scenes. To demonstrate the algorithm, we minimize a third-order energy, which allows clique potentials with up to four pixels, in an image restoration problem. The prob- lem uses the Fields of Experts model, a learned spatial prior of natural images that has been used to test two belief prop- agation algorithms capable of optimizing higher-order en- ergies. The results show that the algorithm exceeds the BP algorithms in both optimization performance and speed.
Conference: Computer Vision and Pattern Recognition - CVPR , pp. 2993-3000, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...convert them into order two cliques by the introduction of new variables (Ramalingam et al. 2008; Rother et al. 2009; Ishikawa 2009; Kohli and Kumar 2010)...

    Xavier Boixet al. Harmony Potentials

    • ...A representative example of current research is provided by [49], which draws on several important developments in graph cuts...
    • ...The main result of [49] is a transformation of this more complex binary problem into the form of (13), at the price of introducing additional binary variables...
    • ...There are two additional challenges that [49] addresses...
    • ...Ishikawa [49] relies on a relaxation technique originally invented by Boros and Hammer [12], which was introduced into computer vision by Kolmogorov and Rother [66]...
    • ...The second challenge that [49] addresses is that for some applications, a better move-making algorithm is needed than expansion moves or swap moves...
    • ...By relying on roof duality and fusion moves, the main result of [49] can be applied to several applications with higher order cliques...

    Pedro F. Felzenszwalbet al. Dynamic Programming and Graph Algorithms in Computer Vision

    • ...Other modifications of MRF approaches include algorithms that extend the MRF objective from single and pairwise cliques to triplewise [2] and higher order ones [42]...
    • ...Since graph-cut algorithms cannot be straightforwardly extended to optimally solve MRFs that include priors on these higher order dependencies [19], methods [2] and [42] are based on the QPBO [43] optimization algorithm...

    Ivana Tosicet al. Learning Sparse Representations of Depth

    • ...The problem of inference in the presence of higher-order cliques has been given a lot of attention recently [9, 13]...
    • ...The most straightforward manner to minimize the model energy is the high-order clique reduction technique proposed in [9], while a more promising alternative given the...
    • ...[9] performs inference in a higher-order MRF with binary labels by reducing any pseudo-Boolean function to an equivalent quadratic one while keeping the minima of the resulting function the same as the original...
    • ...Like [9], we employ the fusion-move [16] and QPBO [6, 12] algorithms to extend this method to deal with multi-label MRFs: During energy minimization, a number of iterations is performed, and for each iteration, the algorithm fuses the current labeling Lcur and a proposed labeling Lprop by minimizing a pseudo-Boolean energy [9]...
    • ...Like [9], we employ the fusion-move [16] and QPBO [6, 12] algorithms to extend this method to deal with multi-label MRFs: During energy minimization, a number of iterations is performed, and for each iteration, the algorithm fuses the current labeling Lcur and a proposed labeling Lprop by minimizing a pseudo-Boolean energy [9]...

    Alexandros Panagopouloset al. Illumination estimation and cast shadow detection through a higher-ord...

Sort by: