Acquisition comprimée

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'acquisition comprimée (en anglais compressed sensing) est une technique permettant de trouver la solution la plus parcimonieuse d'un système linéaire sous-déterminé. Elle englobe non seulement les moyens pour trouver cette solution mais aussi les systèmes linéaires qui sont admissibles. Elle est également appelée Compressive sensing, Compressed Sampling ou Sparse Sampling en anglais.

Histoire[modifier | modifier le code]

Plusieurs disciplines scientifiques utilisent les techniques d'acquisition comprimée depuis très longtemps[réf. souhaitée], mais ce n'est que grâce aux papiers de Emmanuel Candès (en), Justin Romberg, Terence Tao et David Donoho (en) que l'on a commencé à comprendre quels étaient les ensembles de mesures qui étaient admissibles. En particulier, on s'est aperçu que l'un des moyens de retrouver des signaux parcimonieux était la résolution de programmes linéaires faisant intervenir la normeL_1[1]. En statistique, la méthode des moindres carrés a été complétée par la norme L_1 introduite par Laplace. Après l'introduction de la programmation linéaire et de l'algorithme du simplexe de George Dantzig, la norme L_1 a été utilisée en statistique numérique. En théorie statistique la norme L_1 a été utilisée par George Brown et plus tard elle servit à définir des estimateurs non-biaisés de la médiane. Elle a été utilisée par Peter Huber et d'autres dans leurs travaux sur les statistiques robustes. Dans les années 1970, la norme L_1 a été utilisée par les sismologues pour analyser les données de réflexions d'ondes entre les couches de l'écorce terrestre lorsqu'elles ne semblaient pas respecter les conditions du théorème d'échantillonnage de Nyquist-Shannon[2]. Toujours en traitement du signal, elle a été introduite en 1993 dans l'algorithme « Matching Pursuit » et dans l'estimateur LASSO par Robert Tibshirani en 1996[3] et « Basis Pursuit » en 1998[4]. Des résultats théoriques permettaient de savoir quand ces algorithmes permettaient de retrouver des solutions éparses, mais le type et le nombre de mesures requis pour cela étaient sous-optimaux et l'algorithme d'acquisition comprimée a permis une amélioration sensible de ce domaine du traitement du signal. Vers 2004, Emmanuel Candès (en), Terence Tao et David Donoho (en) découvrirent des résultats importants sur le nombre minimum de données nécessaires à la reconstruction d'une image qui apparut plus petit que le nombre minimum déterminé par le critère de Nyquist-Shannon[5],[6].

Principes[modifier | modifier le code]

On considère un signal à valeur réelle, à une dimension et de longueur finie x, que l’on notera sous la forme d’un vecteur colonne de longueur N. Dans le cas d’images, ou de signaux de plus grande dimension, on peut agencer les données pour former un long vecteur.

On exprime ce signal dans une base ψ tel que x=\psi s. On souhaite choisir la base telle que la majorité des coefficients de s soient nuls, c'est-à-dire que x est parcimonieux dans la base ψ. Ces bases sont connues et habituellement utilisées pour comprimer le signal de départ. L’acquisition comprimée propose de directement acquérir la version compressée du signal ce qui évite de traiter les échantillons inutiles[7].

Le processus de mesure linéaire utilisé consiste à faire M produits scalaires, avec M<N, entre x et une collection de vecteurs \{\phi_j\} j allant de 1 à M. On obtient ainsi les échantillons de mesures y_j=\langle x|\phi_j\rangle . Considérant la matrice de mesure φ ayant pour colonne les \phi_j , on peut alors écrire y comme :  y=\phi x = \phi \psi s=\Theta s (avec \Theta=\phi \psi).

La conception de la matrice de mesure doit permettre de pouvoir retrouver les signaux les plus parcimonieux. Pour cela, ces matrices de mesure doivent suivre certaines propriétés dont l'une est appelé RIP (Restricted Isometry Property). De plus φ doit être incohérente par rapport à ψ. Il s’avère que ces propriétés sont satisfaites avec une grande probabilité simplement en choisissant aléatoirement φ, par exemple en utilisant une distribution gaussienne. Bien que ces conditions RIP ou d’incohérence soient satisfaites pour certains ensemble de mesures, ce ne sont que des conditions nécessaires et non suffisantes. Il existe d'autre propriétés, aussi non suffisantes, qui permettent d'avoir besoin d'encore moins échantillons pour garantir une reconstruction de signal parcimonieux Big Picture in Compressive Sensing[8].

La dernière étape du processus d’acquisition comprimée est la reconstruction du signal de départ. On connaît pour cela les M valeurs de y, la matrice de mesure utilisée ainsi que la base ψ. L’algorithme de reconstruction cherche à retrouver les coefficients de s, il est ensuite simple grâce à la connaissance de ψ de retrouver x, le signal de départ.

Il existe une infinité de solution s' à l’équation \Theta s'=y , cependant on cherche la solution minimisant une certaine norme. La L_2 norme mesure l’énergie du signal, c’est pourquoi en faisant une L_2-minimisation, on ne retrouvera quasiment jamais un résultat qui est K-parcimonieux. La norme L_0 mesure la parcimonie du signal (on compte le nombre d’éléments non nuls), l’optimisation \hat{s} =argmin \| s'\|_0 tel que \Theta s'=y donne un bon résultat. L’inconvénient est que ce problème n’est pas calculable numériquement. Il a été démontré que l’optimisation basé sur la norme L_1 permet de retrouver exactement un signal K-parcimonieux, de plus le problème de la L_1-minimisation est convexe[9].

Sa résolution peut se réduire en un programme linéaire, plus connu sous le nom de basis pursuit.

Applications[modifier | modifier le code]

Une première application importante est en tomographie, en particulier pour l'IRM et la tomodensitométrie [10],[11].

Il est également envisagé d'appliquer l'acquisition comprimée pour le radar[12] et l'imagerie radar[13]

Nuit Blanche[14], un blog spécialiste sur le compressed sensing, montre diverses utilisations de l'acquisition comprimée dans divers types de détecteurs[15]

En 2013, les laboratoires Bell annoncent avoir conçu une caméra sans lentilles, fonctionnant selon le principe de l'acquisition comprimée, avec un capteur ponctuel unique placé derrière un réseau d'orifices programmables[16].

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Compressed sensing » (voir la liste des auteurs)

  1. List of L1 regularization ideas from Vivek Goyal, Alyson Fletcher, Sundeep Rangan, The Optimistic Bayesian: Replica Method Analysis of Compressed Sensing
  2. Hayes, Brian, The Best Bits, American Scientist, July 2009
  3. The Lasso page, at Robert Tibshirani's homepage. "Regression shrinkage and selection via the lasso". J. Royal. Statist. Soc B., Vol. 58, No. 1, pages 267-288
  4. "Atomic decomposition by basis pursuit", by Scott Shaobing Chen, David L. Donoho, Michael, A. Saunders. SIAM Journal on Scientific Computing
  5. E. J. Candès, J. Romberg and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math., 59 1207-1223 (www-stat.stanford.edu) [PDF]
  6. Donoho, D. L., Compressed Sensing, IEEE Transactions on Information Theory, V. 52(4), 1289–1306, 2006 (ieeexplore.ieee.org)
  7. Holtz, Olga V. An Introduction to Compressive Sensing. Stanford : s.n., 2009
  8. Measurement matrices and admissibility conjditioons in compressive sensing - a comprehensive list - - en anglais-
  9. Baraniuk, R.G., "Compressive Sensing [Lecture Notes]," Signal Processing Magazine, IEEE , vol.24, no.4, pp.118,121, July 2007
  10. Compressive sampling makes medical imaging safer
  11. [1]
  12. High-Resolution Radar via Compressed Sensing. Herman, M.A. et Strohmer, T. 6, Juin 2009, IEEE Transactions on Signal Processing, Vol. 57, pp. 2275-2284
  13. Sparsity and Compressed Sensing in Radar Imaging. Potter, L.C., et al., et al. 6, Juin 2010, Proceedings of the IEEE, Vol. 98, pp. 1006-1020
  14. Un Blog sur le Compressive Sensing - en anglais-
  15. List of compressive sensing sensors
  16. (en)Bell labs invents lensless camera

Lien externe[modifier | modifier le code]

http://dsp.rice.edu/cs liste des articles sur le sujet, allant des tutoriels généraux aux applications, en passant par les différents algorithmes de reconstruction