Tutorial 3 : Convex Optimization Methods for Image Processing

Presenters:

Xavier Bresson, City University of Hong Kong
Thomas Pock, Graz University of Technology

Abstract

The goal of this tutorial is to introduce efficient optimization methods to compute solutions of fundamental problems in image processing (IP). Most of these problems can be cast as energy minimization problems such as image denoising (removes noise in images), image segmentation (partitions the image into meaningful parts), image registration (used for object tracking or medical imaging), and 3D surface reconstruction (from a set of data points, a set of images or stereo images). Most IP problems are defined as non-convex minimization problems, often depending on latent variables, which make them difficult and slow to minimize. The main state-of-the-art approaches to solve these problems are the level set and the graph-cuts methods. The level set method [Osher-Sethian-88] has been proved to be accurate and flexible to solve problems in a large variety of applications ranging from physics to computer vision, but this method does not provide global solutions or fast algorithms. Graph-cuts methods [Boykov-Kolmogorov-04] are not as flexible and accurate as the level set method and may require important memory allocation in 3D, but they guarantee global solutions and fast results. Recently, new optimization algorithms have been developed to overcome the shortcomings of the level set and the graph-cuts methods. These algorithms are based on convex relaxation techniques, which aim at “convexifying” the original non-convex problems to find exact global solutions. This relaxation techniques are very promising because they can guarantee global solutions (independently of the initialization), fast algorithms (based on convex optimization and easy parallelization), accurate solutions (sub-pixel precision) and low memory allocation. Hence, convex relaxation techniques combine many desirable advantages in a unified framework. Currently, there is a new and growing literature about convex relaxation techniques and it can be expected that these methods will become one of the leading mathematical tools in IP. The proposed tutorial will be divided into three parts. In the first part, we will introduce the background in image processing and mathematics needed to set the general context of these new algorithms. In the second and third part, we will present the convex optimization algorithms to efficiently solve the problems of image segmentation, image registration, stereo depth map estimation, and 3D surface reconstruction from multi-view or data points. We will also introduce the recent promising developments of this framework including some extensions to machine learning problems.

Outline

Part 1 - Background

• Introduction to image segmentation, image registration, stereo depth problem, 3D surface reconstruction
• Energy minimization models for image processing (Markov Random Fields & graph cuts, variational models & level set method)
• Geometry and energy minimization (Total Variation energy)
• Convex Optimization and fast minimization algorithms related with l1-norm

Part 2 - Convex Optimization Algorithms for Image Segmentation

• Image segmentation with Mumford-Shah energy
• 2-phase segmentation (exact solutions)
• Multi-phase segmentation (NP-hard - approximate solutions)
• Piecewise-smooth segmentation (relation to calibration theory)
• Convex formulation of the geodesic active contour model
• Interactive segmentation
• Simultaneous segmentation & feature estimation (Expectation-Maximization method)

Part 3 - Convex Optimization Algorithms for Optical Flow and 3D Problems

• Optical flow estimation and tracking
• Stereo depth reconstruction problem (functional lifting method)
• 3D Surface reconstruction from multi-view or unorganized data points
• Recent developments and extension to machine learning problems

Biography of the presenters

Xavier Bresson received a B.A. in Theoretical Physics in 1998, a M.Sc. in Electrical Engineering from Ecole Superieure d'Electricite, Paris, and a M.Sc. in Signal Processing from University of Paris XI in 2000. In 2005, he completed a PhD at the Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland, with Jean-Philippe Thiran. In 2006-2010, he was a Postdoc scholar in the Department of Mathematics at University of California, Los Angeles (UCLA) with Tony Chan and Stanley Osher. In 2010, he joined the Department of Computer Science at City University of Hong Kong as assistant professor. He has published 35 papers in international journals and conferences. His current research works are focused on continuous convex relaxation techniques to find global solutions of non-convex problems in image processing and graph-based problems in machine learning, and a unified geometric framework for energy minimization models in image processing. (See http://www.cs.cityu.edu.hk/~xbresson)

Thomas Pock received a MSc and a PhD degree in computer science from Graz University of Technology in 2004 and 2008, respectively. He is currently employed as an assistant professor at the Institute for Computer Graphics and Vision at Graz University of Technology and he is the leader of the "variational methods" working group (see www.gpu4ision.org). His research interests include convex optimization and in particular variational methods with application to segmentation, optical flow, stereo, registration as well as its efficient implementation on graphics processing units.