Cette journée sur les représentations parcimonieuses est la reconduction de la journée initialement programmée en novembre 2007 et annulée pour cause de grève des transports.
Elle est proposée par les thèmes A et B du GDR ISIS.

Les représentations parcimonieuses de signaux et d'images sont au coeur de beaucoup d'algorithmes de traitement du signal et de l'image : compression, débruitage, séparation aveugle de sources... Elles sont également l'outil fondamental de l'échantillonnage compressé (compressed sensing), aujourd'hui en pleine émergence, qui renouvelle la vision de Shannon de l'échantillonnage pour l'acquisition de signaux analogiques. Il existe enfin de forts liens, notamment algorithmiquess, entre ces modèles parcimonieux et les méthodes à noyau pour lesquelles la parcimonie assure une bonne tenue en charge.

Ces journées ont pour but de faire le point sur les différentes facettes des représentations parcimonieuses en général, leurs liens avec les méthodes à noyau et leurs applications en traitement du signal et de l'image.

10 -11h Exposé tutoriel - Rémi Gribonval, Projet METISS, IRISA-INRIA
Représentations parcimonieuses : de la séparation de sources à l’échantillonnage compressé.

11h - 11h30 C. Févotte, TSI ENST
Sparse linear regression with structured priors and application to denoising of musical audio.

11h30 - 12 h Caroline Chaux, Institut Gaspard Monge, Université Marne la vallée.
Représentations parcimonieuses et algorithmes itératifs pour la restauration d'images.

12h - 12h30 Jalal Fadili GREYC ENSICEAN
Représentations parcimonieuses pour les problèmes inverses en traitement d'images.

12h30  repas

14h - 14h30 Jean-Luc Starck, CEA
Représentation Parcimonieuse et Diversite Morphologique pour l'analyse de données multi et hyperspectrales.

14h30 - 15h Gabriel Peyré, CEREMADE
Représentation et synthèse de textures géométriques.

15h - 15h30 François Malgouyres, LAGA, Université Paris XIII
Résolution du Basis Pursuit avec un algorithme du Point Proximal.

15h30 - 16h Pause

16h - 16h30 Stéphane Canu, LITIS, INSA Rouen
Parcimonie, chemin de régularisation et méthodes à noyau (à confirmer).

16h30 - 17h Cédric Richard, UTT
Sur l’usage de critères de représentation parcimonieuse pour la RdF par méthodes à noyau.

17h - 17h30 Albert Bijaoui. Laboratoire Cassiopée, Observatoire de la Côte d’Azur.
Décomposition parcimonieuse associée à une analyse multiéchelle.

17h30 18h Emmanuel Ravelli, Université Pierre et Marie Curie et ENST.
Application des représentations parcimonieuses au codage audio progressif.

--------------- résumés ---------------

Rémi Gribonval, Projet METISS, IRISA-INRIA
Titre : Représentations parcimonieuses : de la séparation de sources à l’échantillonnage compressé.
Résumé : Cet exposé dressera un panorama des principales avancées théoriques, algorithmiques et applicatives récentes en modélisation parcimonieuse de signaux. L’exemple de la séparation aveugle de N sources à partir de M < N capteurs illustrera dans un premier temps l’apport des modèles parcimonieux pour la résolution de problèmes inverses. Je brosserai ensuite un tableau des avancées mathématiques qui ont progressivement démontré l’identifiabilité de ces modèles et expliqué les performances des algorithmes utilisés, au départ heuristiques. Pour conclure, je décrirai les promesses et les défis portés par l’échantillonnage compressé, cette application émergente des modèles parcimonieux qui vise à remplacer l’échantillonnage classique de Shannon.

C. Févotte, TSI ENST, B. Torrésani, L. Daudet, and S. J. Godsill
Titre : Sparse linear regression with structured priors and application to denoising of musical audio.
Résumé : In this presentation, we describe an audio denoising technique based on sparse linear regression with structured priors. The noisy signal is decomposed as a linear combination of atoms belonging to two Modified Discrete Cosine Transform (MDCT) bases, plus a residual part containing the noise. One MDCT basis has a long time resolution, and thus high frequency resolution, and is aimed at modeling tonal parts of the signal, while the other MDCT basis has short time resolution and is aimed at modeling transient parts (such as attacks of notes). The problem is formulated within a Bayesian setting. Conditionally upon an indicator variable which is either 0 or 1, one expansion coefficient is set to zero or given a hierarchical prior. Structured priors are employed for the indicator variables; using two types of Markov chains, persistency along the time axis is favored for expansion coefficients of the tonal layer, while persistency along the frequency axis is favored for the expansion coefficients of the transient layer. Inference about the denoised signal and model parameters is performed using a Gibbs sampler, a standard Markov chain Monte Carlo (MCMC) sampling technique. We present results for denoising of a short glockenspiel excerpt and a long polyphonic music excerpt. Our approach is compared with unstructured sparse regression and with structured sparse regression in a single resolution MDCT basis (no transient layer). The results show that better denoising is obtained, both from SNR measurements and from subjective criteria, when both a transient and tonal layer are used, in conjunction with our proposed structured prior framework.
Référence :
C. Févotte, B. Torrésani, L. Daudet, and S. J. Godsill. "Sparse linear regression with structured priors and application to denoising of musical audio," IEEE Trans. Audio, Speech and Language Processing, to appear.
http://www.tsi.enst.fr/~fevotte/Journals/ieee_asl_sparsereg_struc.pdf

Caroline Chaux1, Patrick L. Combettes2  et Jean-Christophe Pesquet1
1 IGM - UMR CNRS 8049, Université de Paris-Est Marne-la-Vallée
2 Laboratoire Jacques-Louis Lions - UMR CNRS 7598,Université Pierre et Marie Curie
Titre : Représentations parcimonieuses et algorithmes itératifs pour la restauration d'images.
Résumé : De nombreuses techniques récemment introduites en restauration d’images proposent de minimiser un critère composé de la somme de deux termes : (i) un terme de fidélité aux données (par exemple, une énergie résiduelle) et (ii) un terme de régularisation (pénalisation) opérant sur des coefficients de représentation et exploitant leur parcimonie.
On a tout d’abord considéré des coefficients de représentation sur une base (par exemple issus d’une transformée en ondelettes [4]) et plus récemment, la pénalisation a été appliquée sur des coefficients de représentation sur une trame (on peut, par exemple, utiliser des transformées directionnelles permettant de mieux représenter la géométrie contenue dans une image, comme la transformée en arbre dual [1] ou les curvelets). Dans le cadre de notre étude, nous avons proposé de minimiser un critère dans un cadre plus général, englobant ainsi de nombreux travaux existants [3, 1]. Nous avons montré, par la suite, que notre approche était directement liée aux approches bayésiennes et nous avons proposé l’utilisation de diverses fonctions de pénalisation introduisant ainsi de nouvelles fonctions de seuillage. Des algorithmes itératifs de type implicite-explicite (forward-backward) ont été mis en place, utilisant des outils récemment développés en analyse convexe; leur convergence a été démontrée sous divers jeux d’hypothèses [2, 3].
Références
[1] C. Chaux, P. L. Combettes, J.-C. Pesquet, and V. R. Wajs. A variational formulation for frame-based inverse problems. Inverse problems, 23 :1495–1518, June 2007.
[2] P. L. Combettes and J.-C. Pesquet. Proximal thresholding algorithm for minimization over orthonormal bases. SIAM Journal on Optimization, to appear., 2007.
[3] P. L. Combettes and V. R. Wajs. Signal recovery by proximal forward-backward splitting. SIAM J. on Mult. Model. Simul., 4 :1168–1200, Nov. 2005.
[4] I. Daubechies, M. Defrise, and C. De Mol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Comm. Pure Applied Math., 57 :1413–1457, 2004.

Jalal Fadili, GREYC ENSICEAN
Titre : Représentations parcimonieuses pour les problèmes inverses en traitement d'images.
Résumé : Overcomplete representations are attracting interest in signal and image processing theory, particularly due to their potential to generate sparse representations of data, hence allowing more flexibility in signal representation and effectiveness at many signal processing tasks such as restoration, separation, compression, estimation etc. In recent years, we have witnessed a flurry of research activity on this area, with researchers spanning a diverse range of viewpoints, all advocating the use of sparsity and overcomplete image representations.
In this presentation, we consider the scenario of linear inverse problems. Combining elements from modern computational harmonic analysis and Bayesian theory, The deconvolution problem is formulated as the (MAP) minimization of an energy functional with a sparsity-promoting penalty. Several fast algorithms for solving such problems either based on Iterative Shrinkage or Stagewise Variable Selection, are proposed to solve the optimization problem. Some theoretical aspects as well as computational and practical issues are discussed. Experimental results show that sparsity and overcompletness lead to striking benefits in a wide range of signal/image processing applications such as inpainting, component separation and deconvolution.

Jean-Luc Starck, Jérome Bobin, Yassir Moudden, CEA Saclay
Jalal Fadili, Greyc-Caen
Titre : Représentation Parcimonieuse et Diversite Morphologique pour l'analyse de données multi et hyperspectrales
Résumé : The Morphological Component Analysis (MCA) is a new method which allows us to separate features contained in an image when these features present different morphological aspects.  MCA can be very useful for decomposing images into texture and piecewise smooth (cartoon) parts or for inpainting applications. MCA can also be extended to multichannel data (GMCA) and we show that GMCA is a very interesting alternative to standard blind source separation techniques. Finally we will see how GMCA can be used for different astronomical applications, especially for recovering the Cosmic Microwave Background from multichannel observations.

Gabriel Peyré, CEREMADE.
Titre : Représentation et synthèse de textures géométriques.
Résumé : Les textures naturelles contiennent des structures complexes, souvent turbulentes. Les outils classiques de l'approximation d'images ne sont pas assez efficaces pour compresser ce type de régularité longue portée. L'obtention de représentations adaptées pour les textures géométriques est capitale pour traiter efficacement ce type d'images ainsi que pour synthétiser de nouvelles images ayant les mêmes caractéristiques.
Dans cet exposé, je vais présenter plusieurs types de représentations capables de tirer partie de l'information géométrique. Les bases orthogonales de bandelettes représentent de façon optimale les images de type "dessin animé". La géométrie des textures ne se restreint cependant pas à un ensemble de contours et les bandelettes ne sont pas un outil efficace pour les textures. Il faut une approche plus souple pour capturer les chocs et les croisements engendrés par la turbulence de ces textures. Les familles redondantes de grouplettes utilisent un champ d'association multiéchelles qui permet de suivre les structures fines d'une texture. Ces grouplettes peuvent être utilisées pour modifier la géométrie des textures ainsi que pour réaliser de l'inpainting d'images. Une autre approche consiste à apprendre une base adaptée aux structures locales d'une texture. Le problème d'optimisation sous-jacent consiste à chercher un dictionnaire maximisant la parcimonie de la représentation, mesurée par la norme L1 des coefficients. Une telle base adaptée permet de synthétiser de façon réaliste des textures naturelles et réalise un pont entre la théorie de l'approximation et la synthèse de textures en informatique graphique.
Plutôt que d'utiliser un modèle had-oc de contraintes géométriques, il est possible d'inférer ce modèle à partir d'un jeu de textures données comme exemples. Une façon d'effectuer cet apprentissage consiste à imposer une représentation parcimonieuse dans un dictionnaire optimisé à la volée. Le modèle sous-jacent recouvre des algorithmes tels que le débruitage par moyennes non-locales et les méthodes de synthèse de textures par recopie. On peut ensuite appliquer ce modèle à des problèmes de synthèse et mixage de textures, de segmentation d'images ou de séparation en structure+texture.

François Malgouyres, LAGA, Université Paris XIII
Titre : Résolution du Basis Pursuit avec un algorithme du Point Proximal.
Résumé : On applique un algorithme du Point Proximal au prédual d'une variante du Basis Pursuit. Ce faisant, on transforme une minimisation l1 (difficile) en une suite (convergent rapidement) de maximisation de fonctions dont le gradient est Lipschitz (ces maximisations sont faciles). On obtient un algorithme facile à implémenter, dont la convergence est prouvée. Expérimentalement, l'algorithme obtenu converge plus rapidement que les algorithmes de seuillages itératifs et de Parallel Coordinate Descent.

Stéphane Canu, LITIS, INSA Rouen
Titre : Parcimonie, chemin de régularisation et méthodes à noyau (à confirmer).
Résumé :

Cédric Richard, UTT
Titre : Sur l’usage de critères de représentation parcimonieuse pour la RdF par méthodes à noyau.
Résumé : Les méthodes à noyau offrent aujourd’hui une multitude d’outils efficaces et élégants pour la résolution de problèmes non-linéaires en analyse de données, reconnaissance des formes, traitement du signal, etc. L’une des difficultés récurrentes à laquelle on se trouve cependant confronté lors de leur mise en œuvre réside dans la dimension des problèmes à résoudre et de leurs solutions. Dans le cadre de cet exposé, on aborde cette question par le biais de critères classiquement utilisés par la communauté « sparse » pour la caractérisation de dictionnaires, que l’on étudie au jour des méthodes à noyau. Des exemples de mise en œuvre sont présentés dans le cadre de problèmes classiques de traitement du signal.

Albert Bijaoui, Laboratoire Cassiopée, Observatoire de la Côte d’Azur.
Titre : Décomposition parcimonieuse associée à une analyse multiéchelle.
Résumé : Un nouvel algorithme glouton (greedy) de représentation parcimonieuse est proposé. Il est basé sur un dictionnaire de type échelette (scalet). L'identification des éléments du dictionnaire, appelés pyrels en raison de la nature pyramidale de leur construction, est effectuée via les extrema
d'une transformée en ondelettes redondante (à trous ou pyramidale). Les amplitudes des éléments du dictionnaire sont ajustées de manière à minimiser la norme, échelle par échelle. On procède de manière itérative en réduisant le résidu jusqu'à ne plus pouvoir identifier de structures significatives à chaque échelle. L'algorithme reconstruit d'une manière parcimonieuse les signaux et les images à une ligne de base (ou un fond) près. Il est facile de la(le) déterminer pour contrôler la qualité de la reconstruction.
Contrairement aux algorithmes déjà publiés la transformée en ondelettes est utilisée non pour la représentation mais pour l'identification. En raison de l’utilisation des échelettes dans la reconstruction il n'y pas d'artéfacts de type anneau, coûteux à éliminer. Cet algorithme glouton vient de l'idée d'éliminer un fond, ce qui est typique de l'analyse des images
astronomiques, le fond n’étant pas porteur d’informations pertinentes.
À chaque itération l'algorithme identifie tous les suprema de la transformée en ondelettes, ce qui permet, contrairement au matching pursuit (orthogonal ou pas), à être rapide. Une correction est faite pour tenir compte de la non orthogonalité des échelettes. Cet algorithme permet aussi de décomposer un signal en éléments d'amplitude positive (ou négative), ce qui est très utile pour le traitement des images.
La version pyramidale est rapide. Elle permet de traiter des images 2000x2000 sans difficulté sur une station de base. Cet algorithme a été développé dans le cadre d'un outil pour l'analyse multibande en astronomie. Il conduit ainsi à une transformation adaptée à la décomposition d’un
ensemble d’images.

Emmanuel Ravelli, Université Pierre et Marie Curie et ENST.
Titre : Application des représentations parcimonieuses au codage audio progressif.
Résumé : Signal representations in overcomplete dictionaries are considered as an alternative to the traditional transform representations for fine-grain scalable audio coding. Such representations produce sparser  decompositions and thus allow better
coding efficiency than transform coding at very low bitrates. Moreover, the decomposition algorithms are intrinsically progressive, and flexible enough to allow an efficient transient modeling. We propose in this paper a fine-grain scalable audio coder which works on a large range of bitrates (2kbs to 128kbs). Objective measures as well as informal subjective evaluation show that this coder outperforms a comparable transform-based coder at very low bitrates.