ICCV Tutorial on Sparse Coding and Dictionary Learning for Image Analysis

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

September 28th, Morning

Duration

3 hours

Short Description

Sparse modeling calls for constructing efficient representations of data as a (often linear) combination of a few typical patterns (atoms) learned from the data itself. Significant contributions to the theory and practice of learning such collections of atoms (usually called dictionaries or codebooks), and of representing the actual data in terms of them, leading to state-of-the-art results in many signal and image processing and analysis tasks. The first critical component of this topic is how to sparsely encode a signal given the dictionary. After introducing the topic, the tutorial will describe the state-of-the-art approaches in this area, ranging from greedy algorithms to l1-optimization all the way 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 efficient optimization methods for learning dictionaries adapted for a reconstruction task, and image processing applications where it leads to state-of-the-art results such as image denoising, inpainting or demosaicking.

The third part of the tutorial will discuss numerous applications where the dictionary is not only adapted to reconstruct the data, but also learned for a specific task, such as classification, edge detection and compressed sensing. The last part presents recent new sparse models that go beyond classical sparse regularization. The tutorial concludes with the discussion of other frameworks closely related to sparse signal modeling and dictionary learning, as well as with a description of important open problems.

Preliminary Syllabus

• Introduction: What sparse coding and dictionary learning are about and why one should care?
• Part I:Optimization techniques for sparse coding.
  • Greedy algorithms
  • Lasso and LARS
  • Soft-thresholding based optimization
• Part II: Dictionary learning for reconstruction.
  • Efficient optimization
  • Image denoising
  • Image inpainting and demosaicking
• Part III: Learning for the task
  • Learning discriminative dictionaries
  • Patch classification, edge detection/classification
  • Learning for the sensing pipeline
• Part IV: New sparse models
  • Grouped sparsity
  • Structured sparsity
• Open questions and discussion

Course Material and Software

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

The slides are now available:

• Introduction
• Part I: Optimization Methods for Sparse Coding
• Part II: Dictionary Learning for Reconstruction
• Part III: Learning for the Task
• Part IV: New Sparse Models
• Guillermo Sapiro's slides

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, December 2006.
• J. Mairal, F. Bach, J. Ponce, and G. Sapiro. Online dictionary learning for sparse coding. In Proceedings of the International Conference on Machine Learning (ICML), 2009.
• J. Mairal, M. Elad and G. Sapiro. Sparse representation for color image restoration. IEEE Transactions on Image Processing 17(1):53--69. 2008.
• 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. M. Duarte-Carvajalino and G. Sapiro. Learning to sense sparse signals: Simultaneous sensing matrix and sparsifying dictionary optimization. IEEE Trans. Image Processing, 2009, to appear.
• B. A. Turlach, W. N. Venables, and S. J. Wright. Simultaneous variable selection. Technometrics, 47(3):349--363, 2005.
• J. A. Tropp, A. C. Gilbert, and M. J. Strauss. Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit Signal Processing, special issue "Sparse approximations in signal and image processing," 86:572--588, 2006.

Biographies

Sponsors