Tutorial on Sparse Coding and Dictionary Learning for Image Analysis, CVPR 2010

General Information

Note

A few years after this tutorial was given, the following monograph was published. It contains most of the material of the tutorial and is self-content.

J. Mairal, F. Bach and J. Ponce. Sparse Modeling for Image and Vision Processing. Foundations and Trends in Computer Graphics and Vision. vol 8. number 2-3. pages 85--283. 2014

Organizers

Francis Bach (INRIA)

Julien Mairal (INRIA)

Jean Ponce (Ecole Normale Supérieure)

Guillermo Sapiro (University of Minnesota)

Time

Monday 14th, June 2010, Afternoon

Duration

4 hours

Short Description

Sparse coding calls for modelling data vectors as a linear combination of a few elements from a dictionary. Whereas the question of -designing- the best dictionary adapted to natural signals has been the topic of much research in the past, this tutorial focuses on recent techniques that -learn- the basis set from training data. This has already proven very effective for signal reconstruction, leading to state-of-the-art results for many signal or image processing tasks, as well as advances in computer vision tasks such as object recognition.

A critical component in this approach is how to sparsely encode a signal given the dictionary. The tutorial will describe the state of the art in this area, ranging from greedy algorithms and l1-optimization to simultaneous sparse coding of collections of signals. The actual dictionary plays a critical role, and it has been shown once and again that learned dictionaries significantly outperforms off-the-shelf ones such as wavelets. The second part of this tutorial will present the dictionary learning formulation and its links with existing matrix factorization techniques, as well as state-of-the-art applications to image processing tasks. The third part of the tutorial will be devoted to the most recent advances in the field, starting from learning dictionaries of image descriptors, a strategy used by the latest PASCAL VOC'09 challenge winners, to task-driven dictionaries and structured sparsity.

A similar tutorial was given at ICCV'09 in Kyoto, and its success prompts us to hold a second tutorial at CVPR'2010, with updates and new material.

Preliminary Syllabus

• Introduction: What sparse coding and dictionary learning are about and why one should care?
• Part I:Sparse Models in Machine Learning.
  • Sparse Models
  • Dictionary Learning, Vector Quantization and Matrix Factorization
  • Grouped Sparsity
• Part II:Applications in Image Processing
  • Dictionary Learning for Image Denoising and Inpainting
  • Learning Dictionaries for Compressed Sensing
  • Alternative Models
• Part III:Optimization Techniques for Sparse Coding
  • Greedy Approaches
  • Convex Optimization
  • Optimization for Dictionary Learning
• Part IV: Recent advances in Computer Vision and New Models
  • Discriminative Dictionaries for Patch Classification
  • Learning Codebooks for Image Classification
  • Structured Sparse Models
• Open questions and discussion

Course Material and Software

A Matlab toolbox for sparse decomposition and dictionary learning is available here.

The slides will all be available soon.

• Introduction
• Part I: Sparse Models in Machine Learning (by Francis Bach)
• Part II: Dictionary Learning in Image Processing (by Guillermo Sapiro)
• Part III: Optimization Techniques for Sparse Coding (by Julien Mairal)
• Part IV: Recent advances in Computer Vision and New Models (by Jean Ponce)

Relevant References

Among the vast literature on sparse coding, here are a few selected publications. The list is preliminary and subject to modifications:

• B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. Annals of statistics, 32(2):407--499, 2004.
• J. Friedman, T. Hastie, H. Hölfling, and R. Tibshirani. Pathwise coordinate optimization. Annals of statistics, 1(2):302--332, 2007.
• B. A. Olshausen and D. J. Field. Sparse coding with an overcomplete basis set: A strategy employed by V1? Vision Research, 37:3311--3325, 1997.
• M. Elad and M. Aharon. Image denoising via sparse and redundant representations over learned dictionaries.IEEE Transactions on Image Processing, 54(12):3736--3745, 2006.
• R Jenatton, JY Audibert, F Bach. Structured variable selection with sparsity-inducing norms. arXiv:0904.3523 . 2009.
• J. Mairal, F. Bach, J. Ponce and G. Sapiro. Online Learning for Matrix Factorization and Sparse Coding. Journal of Machine Learning Research, 11:19--60, 2010
• J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman. Non-Local Sparse Models for Image Restoration. International Conference on Computer Vision. 2009.
• J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman. Discriminative Learned Dictionaries for Local Image Analysis. IEEE Conference on Computer Vision and Pattern Recognition, 2008.
• J. Yang, K. Yu, Y. Gong, and T. Huang. Linear Spatial Pyramid Matching Using Sparse Coding for Image Classification. IEEE Conference on Computer Vision and Pattern Recognition. 2009.

Biographies