In the first part, of this talk I'll give some sufficient and necessary conditions to optimize a MRF with pairwise interactions using a maximum-flow-based approach. Labels are assumed to be linearly ordered. It is shown that this approach is quite related to the two approaches of Hochbaum and Ishikawa.
In the second part, I'll focus on the minimization of the Variation with convex data fidelity terms both for a continuous and a discrete point of view. I'll briefly review existing minimization algorithms, and in particular the best one which is the parametric maximum-flow based one due to Hochbaum. Then I'll show how one can use it to efficiently perform crystalline mean curvature flow, solve deconvolution and compressive sensing problems.
The second part is a joint work with A. Chambolle (CMAP Polytechnique), D. Goldfarb (Columbia), S. Osher (UCLA), M. Sigelle (ENST) and W. Yin (Rice).
Back to Graph Cuts and Related Discrete or Continuous Optimization Problems