Reading Group on Discrete (and maybe continuous) Optimization


The course will explore the known literature on Pseudo-Boolean Optimization.  Pseudo-boolean optimization deals with the problem of minimizing functions f: B^n -> R, where B = {0, 1} and R is the real numbers.  In recent years there has been a lot of interest in this topic, and its application in Computer Vision.  The topic is related to Markov Random Fields, and in many cases of interest, the minimization problem may be solved using graph-cuts.  However, this topic has a long history with many interesting results, many of which have been rediscovered by Computer Vision researchers.   We will give a survey of some results in this field.  It is hoped that the format of this course will be somewhat interactive.

Although this is advertised as a reading group, I (Richard Hartley) intend to discuss most of the papers myself, possibly with help from Fredrik Kahl, who will be visiting.  Other people may volunteer.

I want this to take place during the time that Fredrik Kahl is visiting ANU (Most of April 2008, with a gap in the middle from April 12 - 19).  So as to cover all this material, I will schedule 3 lectures per week (I think) - time and place to be determined.

Among others, the following papers will be considered.

  1. Boros and Hammer, Pseudo-Boolean Optimization.
  2. Kolmogorov and Zabih,  What energy functions can be minimized via graph cuts (PAMI 2004)
  3. Freedman and Drineas, Energy Minimization via Graph Cuts: Settling What is Possible (CVPR 2005)
  4. Rother, Kolmogorov, Lempitsky and Szummer.  Optimizing binary MRFs via extended roof duality
  5. Kolmogorov and Rother.  Minimizing non-submodular functions with graph-cuts - a review
  6. Boykov, Veksler and Zabih.  Fast Approximate Energy minimization via graph cuts.
  7. Geman and Geman.  Stochastic Relaxation, Gibbs distributions and the Bayesian restoration of images.
  8. Pawan Mudigonda, Combinatorial and Convex Optimization for probabilistic models in Computer Vision (PhD thesis, Oxford Brookes, 2007)
  9. Pushmeet Kohli, Minimizing Dynamic and higher order energy functions using graph cuts.
  10. Ishikawa, Exact Optimization for Markov random fields with convex priors.
  11. Kolmogorov, Boykov, Rother, Applications of parametric maxflow in computer vision.
  12. P. Kohli and P.H.S. Torr. Dynamic Graph Cuts for Efficient Inference in Markov Random Fields.
  13. P. Kohli, P. Kumar, and P.H.S. Torr, P3 & Beyond: Solving Energies with Higher Order Cliques, ICCV 2007.
  14. Wainwright and Jordan: "Graphical Models, Exponential Families, and Variational Inference" (possibly)