Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(9)
Efficient Algorithm
Energy Minimization
Graph Cut
Image Restoration
Natural Images
Natural Scenes
First Order
Higher Order
Markov Random Field
Related Publications
(3)
PseudoBoolean optimization
Energy Minimization via Graph Cuts: Settling What is Possible
Minimizing sparse higher order energy functions of discrete variables
Subscribe
Academic
Publications
Higherorder clique reduction in binary graph cut
Higherorder clique reduction in binary graph cut,10.1109/CVPRW.2009.5206689,Hiroshi Ishikawa
Edit
Higherorder clique reduction in binary graph cut
(
Citations: 28
)
BibTex

RIS

RefWorks
Download
Hiroshi Ishikawa
We introduce a new technique that can reduce any higherorder
Markov random field
with binary labels into a firstorder one that has the same minima as the original. Moreover, we combine the reduction with the fusionmove and QPBO algorithms to optimize higherorder multilabel problems. While many vision problems today are formu lated as
energy minimization
problems, they have mostly been limited to using firstorder 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 higherorder 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 thirdorder 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 higherorder 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. 29933000, 2009
DOI:
10.1109/CVPRW.2009.5206689
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.
(
cv.snu.ac.kr
)
(
www.informatik.unitrier.de
)
(
doi.ieeecomputersociety.org
)
Citation Context
(25)
...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 Boix
,
et 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 movemaking 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. Felzenszwalb
,
et al.
Dynamic Programming and Graph Algorithms in Computer Vision
...Part of this paper previously appeared as [
11
]...
Hiroshi Ishikawa
.
Transformation of General Binary MRF Minimization to the FirstOrder C...
...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 graphcut 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 Tosic
,
et al.
Learning Sparse Representations of Depth
...The problem of inference in the presence of higherorder cliques has been given a lot of attention recently [
9
, 13]...
...The most straightforward manner to minimize the model energy is the highorder clique reduction technique proposed in [
9
], while a more promising alternative given the...
...[
9
] performs inference in a higherorder MRF with binary labels by reducing any pseudoBoolean function to an equivalent quadratic one while keeping the minima of the resulting function the same as the original...
...Like [
9
], we employ the fusionmove [16] and QPBO [6, 12] algorithms to extend this method to deal with multilabel 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 pseudoBoolean energy [9]...
...Like [9], we employ the fusionmove [16] and QPBO [6, 12] algorithms to extend this method to deal with multilabel 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 pseudoBoolean energy [
9
]...
Alexandros Panagopoulos
,
et al.
Illumination estimation and cast shadow detection through a higherord...
References
(29)
PseudoBoolean optimization
(
Citations: 193
)
Endre Boros
,
Peter L. Hammer
Journal:
Discrete Applied Mathematics  DAM
, vol. 123, no. 13, pp. 155225, 2002
Preprocessing of unconstrained quadratic binary optimization
(
Citations: 22
)
E. Boros
,
P. L. Hammer
,
G. Tavares
Published in 2006.
Fast Approximate Energy Minimization via Graph Cuts
(
Citations: 1587
)
Yuri Boykov
,
Olga Veksler
,
Ramin Zabih
Conference:
International Conference on Computer Vision  ICCV
, pp. 377384, 1999
Efficient Belief Propagation for Early Vision
(
Citations: 257
)
Pedro F. Felzenszwalb
,
Daniel P. Huttenlocher
Journal:
International Journal of Computer Vision  IJCV
, vol. 70, no. 1, pp. 4154, 2006
Roof duality, complementation and persistency in quadratic 0–1 optimization
(
Citations: 125
)
P. L. Hammer
,
P. Hansen
,
B. Simeone
Journal:
Mathematical Programming
, vol. 28, no. 2, pp. 121155, 1984
Sort by:
Citations
(28)
Harmony Potentials
Xavier Boix
,
Josep M. Gonfaus
,
Andrew D. Bagdanov
,
Joost Van De Weijer
,
Jordi Gonzalez (Jordi Gonzàlez)
,
Joan Serrat
Journal:
International Journal of Computer Vision  IJCV
, pp. 120, 2012
Dynamic Programming and Graph Algorithms in Computer Vision
(
Citations: 3
)
Pedro F. Felzenszwalb
,
Ramin Zabih
Journal:
IEEE Transactions on Pattern Analysis and Machine Intelligence  PAMI
, vol. 33, no. 4, pp. 721740, 2011
Transformation of General Binary MRF Minimization to the FirstOrder Case
(
Citations: 3
)
Hiroshi Ishikawa
Journal:
IEEE Transactions on Pattern Analysis and Machine Intelligence  PAMI
, vol. 33, no. 6, pp. 12341249, 2011
Learning Sparse Representations of Depth
Ivana Tosic
,
Bruno A. Olshausen
,
Benjamin J. Culpepper
Journal:
IEEE Journal of Selected Topics in Signal Processing  IEEE J SEL TOP SIGNAL PROCESS
, vol. 5, no. 5, pp. 941952, 2011
Illumination estimation and cast shadow detection through a higherorder graphical model
Alexandros Panagopoulos
,
Chaohui Wang
,
Dimitris Samaras
,
Nikos Paragios
Conference:
Computer Vision and Pattern Recognition  CVPR
, pp. 673680, 2011