Graph-based Variational Optimization and Applications in Computer Vision

by Camille Couprie (Courant Institute)
February 7th at 11 am in Byron beige

Many computer vision applications such as image filtering, segmentation and stereo-vision reconstruction may be formulated as optimization problems. Recently discrete, convex, globally optimal methods have received a lot of attention. However, a drawback of several graph-based methods is the presence of blockiness artifacts. Segmented contours are blocky in areas where contour information is lacking. In the first part of this work, we develop a discrete yet isotropic energy minimization formulation for the continuous maximum flow problem that prevents metrication errors. This new convex formulation leads us to a provably globally optimal solution. The energy formulation is then adapted and extended to multi-label problems, and shows improvements over classical weighted total variation methods. Fast parallel proximal optimization tools have been tested and adapted for the optimization of restoration problems.

In the second part of this work, we introduce a framework that generalizes several state-of-the-art graph-based segmentation algorithms, namely graph cuts, random walker, shortest paths, and watershed. This generalization allows us to exhibit a new case, for which we develop a globally optimal optimization method: “power watershed”.  Our proposed power watershed algorithm computes a unique global solution to multi-label problems, and is very fast. We further generalize and extend the framework to applications beyond image segmentation, for example image filtering optimizing an L0 norm energy, stereo-vision and fast and smooth surface reconstruction from a noisy cloud of 3D points.

Comments are closed.