The reading group will cover theory and numerical methods for variational and level set methods applied to computer vision. The main topics we will cover are : image segmentation, motion flow and shape estimation. At each meeting 1, 2 papers will be presented and discussed. Anyone who is interested is welcome to attend. Send me an e-mail (dana[at]cs) if you are like to attend and I will include you on the list.
Reading group on level set methods
Meetings : Wednesdays at 1pm, CSC 349
Contact : Dana Cobzas, dana[at]cs.ualberta.ca
Here are some general references:
Intro
- Variational calculus
- Basic notion of differential geometry for curves (tangent, normal, curvature definitions)
- Curve evolution
- Level set representation
- Curve evolution in the context of level set representation
A very general intro for level sets
[Sethian 97] J.A. Sethian: Level Set Method: An Act of Violance, 1997
Image segmentation
Active contours and geodesic active contours
The techniques in this section are sometimes referred as "edge based segmentation". They will evolve a curve until a contour is detected under some smoothness control. The classical explicit snake model was first proposed by [Kass et al. IJCV87]. However the explicit implementation causes difficulties with respect to topological changes and numerical implementations. Instead, an implicit level set representation prevents these difficulties. The first geometric active contour model was developed by [Caselles et al.93]. Later, the implicit geodesic active contour was proposed simultaneously by [Caselles et al. IJCV97] and [Kichenassamy et al. 96]. Here the level set function is embedded into an energy functional that can be related to the initial snake model.
The main disadvantage of the implicit active contours is their efficiency. First in the naive implementation the resulting PDE has to be evaluated for the entire image domain. Second, most approaches are based on explicit updated schemes that require small time steps. The first numerical issue is solved by narrow-band and/or multi-scale techniques (see Numerical methods). The second problem was addressed by [Weickert 02] and [Goldenberg et al. 01]. They use a semi-implicit scheme based on additive operator splitting (AOS).
Active contours (snakes)
[Kass et al. IJCV87] Kass, M. and Witkin, A. and Terzopolous, D.: Snakes: Active Contour Models, IJCV 1987
Geometric active contours
[Caselles et al.93] V. Caselles, F. Catte, T. Coll, and F. Dibos: A geometric model for active contours in image processing. Numerische Mathematik, 66:1-31, 1993
Geodesic active contours
[Caselles et al. IJCV97] V. Caselles and R. Kimmel and G. Sapiro: Geodesic Active Contours, IJCV 1997
[Kichenassamy et al. 96] S. Kichenassamy and A. Kumar and P. Olver and A. Tannenbaum and A. Yezzi: Conformal curvature flows: From phase transitions to active vision, Archive for Rational Mechanics and Analysis, 1996
Fast numerical implementation
[Weickert 02] Joachim Weickert and Gerald Kuhne: Fast Methods for Implicit Active Contours, Technical report, University of Saarland, 2002
[Goldenberg et al. 01] R. Goldenberg and R. Kimmel and E. Rivlin and M. Rudzsky: Fast Geodesic Active Contours, IEEE Trans. on Image Processing, 10, 2001.
Active regions
While the edge detector ensures that the information on both sides of the edge is dissimilar it does not deal with the problem that the interior of the region has to be homogeneous. A solution to this shortcoming is to incorporate region information in the curve evolution. [Paragios,Deriche 02 reg] developed the geodesic active regions model based on the geodesic active contour model. [Chan,Vese 01] proposed a model that completely neglects edges based on the level set formulation of the Mumford-Shah functional.
One important aspect in region-based segmentation is how to model the interior of the regions. The original [Chan,Vese 01] model assumed piecewise constant regions. One way to address the problem is to consider more complex region statistics. Simple model based on parametric (e.g. Gaussian) color distributions have been considered in [Paragios,Deriche 02 reg]. [Rousson et al. 03] considered a more complex, non-parametric Parzen density.
The active region segmentation model has been extended also to texture-based segmentation. One way to address the problem is to use Gabor features that discriminates texture by mean of their magnitude, orientation and scale (e.g the supervised segmentation method proposed by [Paragios,Deriche 02 tex] or [Sagiv et al. 01]). Unfortunately, Gabor filters introduce a lot of redundancy and thus lots of feature channels. The work of [Rousson et al. 03] show how a small set of good features for unsupervised texture segmentation can be extracted using the structure tensor and nonlinear diffusion.
One other extension to the original active region model is to consider multiple region segmentation. [Chung,Vese 05] proposed a generalization of the active region model to a multiphase model. [Brox,Weickert 06] proposed minimization strategy based on level sets where the optimized energy include also the number of regions.
[Cremers et al. 02] introduced a modification of the Mumford-Shah functional and its cartoon limit which facilitates the incorporation of statistical prior on the shape of the segmenting contour. As a consequence the evolving contour is restricted to a subspace of familiar shapes while being entirely free to translate, rotate and scale. The shape prior significantly improve the robustness of the segmentation algorithm to noise, occlusion or strongly cluttered background.
Active regions
[Chan,Vese 01] T. Chan and L. Vese: Active contours without edges, IEEE Trans. Image Processing, 2001
[Paragios,Deriche 02 reg] N. Paragios and R. Deriche:Geodesic Active Regions: A New Paradigm to Deal with Frame Partition Problems in Computer Vision,Visual Communication and Image Representation,2002
Region statistics (parametric and non-parametric) and texture segmentation
[Rousson et al. 03] M. Rousson and T. Brox and R. Deriche: Active unsupervised texture segmentation on a diffusion based feature space, CVPR 2003 (non-parametric model)
[Paragios,Deriche 02 tex] N. Paragios and R. Deriche: Geodesic Active Regions and Level Set Methods for Supervised Texture Segmentation, IJCV 2002
[Sagiv et al. 01] C. Sagiv, N. Sochen and Y.Y. Zeevi: Geodesic Active Contours Applied to Texture Feature Space, Scale Space 2001
Multiple regions
[Brox,Weickert 06] T. Brox and J. Weickert: Level Set Segmentation with Multiple Regions, IEEE Transactions on Image Processing, 2006
[Chung,Vese 05] Ginmo Chung and Luminita A. Vese: Energy Minimization Based Segmentation and. Denoising Using a Multilayer Level Set Approach, EMMCVPR 2005
Statistical shape priors in image segmentation
[Cremers et al. 02] D. Cremers, F. Tischhe, J. Weickert & C. Schnorr: Diffusion Snakes: Introducing Statistical Shape Knowledge into the Mumford-Shah Functional, IJCV 50(3): 295-313; Dec 2002
Variational Motion Flow
Motion flow estimation
Motion flow estimation is one of the most important topics in computer vision. The problem consists of finding the pixel displacement between two images at consecutive time instances in a video sequence.
The formulation is based on image constancy assumption and linearization (assuming small motion). It is referred as motion flow constraint and it is known to be ill-posed. Researchers have address this limitation in two ways: (1) Using local methods where a local window regularizes the flow. The flow inside the window is modeled by a parametric model. These techniques were first developed by [Lucas and Kanade 81]. (2) Using global methods originally proposed by [Horn and Schunck 81]. Here a global regularizer (smoothness on the flow vectors) is added to the classical motion flow constraint resulting in minimizing a global energy function. The minimization is performed using variational calculus. [Bruhn et al. 05] proposed a combination of local and global techniques. The paper also presents a summary of the two classes of motion flow estimation techniques.
Different extensions have been added to the original original variational motion flow estimation algorithm. The isotropic regularizer proposed by Horn and Schunck does not preserve discontinuities. It is also quadratic and thus gives significant influence to outliers. [Aubert et al. 99] proposed a non-quadratic regularization term that preserved discontinuities. The paper gives also a nice overview of different choices of regularization terms. [Weickert and Brox 02] present a more theoretical but quite good paper on different regularization approaches for vector valued data (linear/non-linear, isotropic/anisotropic). They also show the connection between diffusion and regularization. Other extensions to the original variational motion flow formulation include spatio-temporal smoothness terms, coarse-to-fine strategies etc.
One of the most accurate algorithms for computing the motion flow is proposed by [Brox et al. 04]. To preserve accuracy they avoid linearization and present a solid numerical method based on two nested fixed point iterations. Also they implement a coarse-to-fine strategy using warping.
Efficient algorithm
[Brox et al. 04] T. Brox and A. Bruhn and N. Papenberg and J. Weickert: High accuracy optical flow estimation based on a theory for warping, ECCV 2004
[Papenberg et al.] N. Papenberg and A. Bruhn and T. Brox and S. Didas and J. Weickert: Highly accurate optic flow computation with theoretically justified warping, IJCV, 2006
Regularization
[Weickert and Brox 02] J. Weickert and T. Brox: Diffusion and regularization of vector and matrix-valued images. Technical report, Universitat des Saarlandes, 2002
[Aubert et al. 99] G. Aubert and R. Deriche and P. Kornprobst: Computing optical flow via variational techniques, SIAM Journal on Applied Mathematics, 1999
Combination of local and global techniques (also summary of the two approaches)
[Bruhn et al. 05] Bruhn, A. and Weickert, J. and Schnorr, C.: Lucas/Kanade Meets Horn/Schunck: Combining Local and Global Optic Flow Methods, IJCV 2005
Motion flow segmentation
Motion flow estimation and segmentation are related topics. Motion information gives information on how to partition an image while segmented regions solves the problem of regularization allowing discontinuities across object boundaries.
A simple way to solve the motion flow segmentation problem is to first estimate the motion and then segment or cluster regions with consistent flow. In contrast, more recent approaches simultaneously solve the two problems by minimizing a single energy functional. [Cremers and Soatto 05] estimate a parametric optic flow for each region and evolve the region contour directly from the flow fitting error. [Brox et al. 06] extend the approach to multiple regions. They also propose an automatic initialization procedure that determines the number of regions.
Motion flow segmentation
[Brox et al. 06] T. Brox and A. Bruhn and J. Weickert: Variational motion segmentation with level sets, ECCV 2006
[Cremers and Soatto 05] Daniel Cremers and Stefano Soatto: Motion Competition: A Variational Approach to Piecewise Parametric Motion Segmentation, IJCV 2005
Variational 3D shape estimation
The problem of 3D shape estimation consists of reconstructing the 3D shape of a scene from a collection of images. The variational formulation of the problem estimates a smooth surface by evolving an initial surface based on a photoconsistency functional (defined from the original images). [Faugeras and Keriven 98] were the first to pose the stereo problem in the variational level set framework. Their method is extended from the traditional stereo image-to-image matching and therefore works only for textured Lambertian scenes. A sligtly different approach is formulayed by [Soatto et al. 03] that explicitly model the image formation and reconstruct both the shape and the reflectance by matching images with the underlying model. Recently, [Pons et al. 05] derived a better matching functional than the original stereo one and apply it to variational multi-view stereo and non-rigid 3D motion estimation (scene flow).
One interesting paper that extends the idea of image segmentation and active regions in 3D is proposed by [Yezzi and Soatto IJCV03]. They formulate the problem of multiview reconstruction as a global region segmentation. They assume piecewise constant radiance that applies to uniform Lambertian objects or fine homogeneous textured objects. These type of objects are in general difficult to reconstruct for a stereo algorithms based on local correspondences.
The idea of combining 3D motion segmentation and shape estimation is addressed by [Sekkati and Mitiche 06]. They propose a variational formulation for joint multiregion 3D motion segmentation and dense recovery of 3D structure and motion of temporal sequences. The segmentation is solved by curve evolution and alternated with depth recovery by gradient descent and 3D motion estimation by least square within each segmented region. The motion estimation is linearized up to a first order approximation in a similar way to visual tracking.
Variational stereo
[Faugeras and Keriven 98] O. Faugeras and R. Keriven: Variational principles, surface evolution, PDEs, level set methods and the stereo problem, IEEE Trans. Image Processing, 1998
[Faugeras and Keriven 96TR] O. Faugeras and R. Keriven: Variational principles, surface evolution, PDEs, level set methods and the stereo problem, RR-3021 INRIA, 1996
Variational multi-view stereo and 3D scene flow (better matching functional)
[Pons et al. 05] J.-P. Pons, R. Keriven, and O. Faugeras: Modelling Dynamic Scenes by Registering Multi-View Image Sequences, CVPR 2005
Multi-view stereo with general reflectance
[Soatto et al. 03] S. Soatto and A. Yezzi and H. Jin: Tales of Shape and Radiance in Multi-view Stereo, ICCV 2003
[Jin et al. 05] H. Jin, S. Soatto and A. Yezzi: Multi-view Stereo Reconstruction of Dense Shape and Complex Appearance, IJCV 2005
Combining shape estimation and segmentation
[Yezzi and Soatto IJCV03] Anthony Yezzi and Stefano Soatto: Stereoscopic Segmentation, IJCV 2003
Combining 3D motion segmentation and shape estimation
[Sekkati and Mitiche 06] Hicham Sekkati and Amar Mitiche: Concurrent 3-D motion segmentation and 3-D interpretation of temporal sequences of monocular images, IEEE Transactions on Image Processing, 2006
Level set: numerical methods
Narrow band, fast matching method
[Peng et al. 99 fast] Danping Peng and Barry Merriman and Stanley Osher and Hongkai Zhao and Myungjoo Kang: A PDE-based fast local level set method, J. Comput. Phys., 1999
General numerical issues
[Osher,Fedkiw 01] Stanley Osher and Ronald P. Fedkiw: Level Set Methods: An Overview and Some Recent Results, Journal of Computational Physics, 2001