Foundations and Trends® in Computer Graphics and Vision > Vol 10 > Issue 1

(Hyper)-Graphs Inference through Convex Relaxations and Move Making Algorithms: Contributions and Applications in Artificial Vision

Nikos Komodakis, Ecole des Ponts ParisTech, France, nikos.komodakis@enpc.fr M. Pawan Kumar, University of Oxford, UK, pawan@robots.ox.ac.uk Nikos Paragios, Universite Paris-Saclay, France, nikos.paragios@ecp.fr
 
Suggested Citation
Nikos Komodakis, M. Pawan Kumar and Nikos Paragios (2016), "(Hyper)-Graphs Inference through Convex Relaxations and Move Making Algorithms: Contributions and Applications in Artificial Vision", Foundations and TrendsĀ® in Computer Graphics and Vision: Vol. 10: No. 1, pp 1-102. http://dx.doi.org/10.1561/0600000066

Published: 31 May 2016
© 2016 N. Komodakis, M. Pawan Kumar, N. Paragios
 
Subjects
Graphical models,  Optimization,  Design and analysis of algorithms
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
2. Mathematical background: basic tools for MRF inference
3. Move-making algorithms
4. MRF inference based on the primal-dual schema
5. MRF inference based on dual-decomposition
Acknowledgements
References

Abstract

Computational visual perception seeks to reproduce human vision through the combination of visual sensors, artificial intelligence and computing. To this end, computer vision tasks are often reformulated as mathematical inference problems where the objective is to determine the set of parameters corresponding to the lowest potential of a taskspecific objective function. Graphical models have been the most popular formulation in the field over the past two decades where the problem is viewed as a discrete assignment labeling one. Modularity, scalability and portability are the main strengths of these methods which once combined with efficient inference algorithms they could lead to state of the art results. In this tutorial we focus on the inference component of the problem and in particular we discuss in a systematic manner the most commonly used optimization principles in the context of graphical models. Our study concerns inference over low rank models (interactions between variables are constrained to pairs) as well as higher order ones (arbitrary set of variables determine hyper-cliques on which constraints are introduced) and seeks a concise, self-contained presentation of prior art as well as the presentation of the current state of the art methods in the field.

DOI:10.1561/0600000066
ISBN: 978-1-68083-138-2
114 pp. $80.00
Buy book
 
ISBN: 978-1-68083-139-9
114 pp. $130.00
Buy E-book
Table of contents:
1. Introduction
2. Mathematical background: basic tools for MRF inference
3. Move-making algorithms
4. MRF inference based on the primal-dual schema
5. MRF inference based on dual-decomposition
Acknowledgements
References

(Hyper)-Graphs Inference through Convex Relaxations and Move Making Algorithms: Contributions and Applications in Artificial Vision

Computational visual perception seeks to reproduce human vision through the combination of visual sensors, artificial intelligence, and computing. To this end, computer vision tasks are often reformulated as mathematical inference problems where the objective is to determine the set of parameters corresponding to the lowest potential of a task-specific objective function. Graphical models have been the most popular formulation in the field over the past two decades where the problem is viewed as a discrete assignment labeling one. Modularity, scalability, and portability are the main strengths of these methods which once combined with efficient inference algorithms they could lead to state of the art results.

This monograph focuses on the inference component of the problem and in particular discusses in a systematic manner the most commonly used optimization principles in the context of graphical models. It looks at inference over low rank models (interactions between variables are constrained to pairs) as well as higher order ones (arbitrary set of variables determine hyper-cliques on which constraints are introduced) and seeks a concise, self-contained presentation of prior art as well as the presentation of the current state of the art methods in the field.

 
CGV-066