Reformulating and Solving Continuous Functionals and PDEs on Graphs: Applications in Computer Vision

Leo Grady
Siemens Corporate Research, Inc.

The widespread variational methods of computer vision follow the pattern of establishing an energy for which the (local or global) minimum solution represents the desired segmentation, registration, filtering, etc. However, this energy is typically formulated in continuous space (with a continuous gradient), while the solving/testing operations are performed on a discrete computer. Ideally, we could reformulate our energy in terms of combinatorial operators that may be efficiently solved using combinatorial optimization techniques. The primary barrier to such a reformulation has not been the lack of established mathematics for translating between continuous and combinatorial operators, but rather a lack of familiarity in the computer vision community with the appropriate combinatorial operators corresponding to traditional continuous operators. The goal of this talk is to introduce these corresponding combinatorial operators to the computer vision community.
The talk will consist of two parts: 1) We begin with a review of the intertwined history of discrete/continuous calculus in space, naturally develop the corresponding combinatorial operators to their continuous counterparts and provide examples to firmly establish this connection.
2) The techniques of Section 1 will then be applied to solving real problems in computer vision, with an emphasis on recent image segmentation techniques that I have been developing, including discrete minimal surfaces and the random walker algorithm.

Presentation Files (Zip Archive)

Back to Graph Cuts and Related Discrete or Continuous Optimization Problems