M2 SC - Usages du hasard l'échantillonnage compresséperso.ens-lyon.fr/pierre.borgnat/MASTER2/cours_M2SC_Bruit... · Théorème de Shannon-Nysquist: si x(t) ... ¥ Basis for JPEG2000

M2 SC - Usages du hasard– l’échantillonnage compressé –

Pierre BORGNAT

CNRS, Équipe Sisyphe (Signaux, Systèmes and Physique)

Laboratoire de Physique de l’ENS de Lyon, Université de Lyon

ECOLE NORMALE SUPERIEURE DE LYON

CENTRE NATIONAL

DE LA RECHERCHE

SCIENTIFIQUE

Acquisition de données numériques• Cadre Théorie classique de l’échantillonnage :

Théorème de Shannon :« En prenant des échantillons assez denses (à lafréquence de Shannon-Nyquist au moins), on peutreconstruire partaitement le signal (ou l’image) »

!"#"$%&'!%$%'()*+","$"-.

/ 0-+.1%$"-.2''Shannon sampling theorem

3"4'5-+',%67&8'18.,8&5'8.-+#9:%$'$98';5*+",$ <%$8=>'5-+')%.'78<48)$&5'<8)-.,$<+)$'$98'-<"#".%&'%.%&-#'1%$%?

$"68 ,7%)8

L’échantillonnage de Shannon-Nysquist• Soit x(t) un signal analogique à temps continu• L’échantillonnage régulier idéal consiste à retenir un

échantillon tous les τe pas de temps : xn := x(nτe), n ∈ Z• Théorème de Shannon-Nysquist : si x(t) est un signal à

bande limité, i.e., son spectre (par transformée de Fourier)est nul en dehors de [−B,B] et que

Fe = 1/τe > 2B

alors xn représente exactement x(t), au sens qu’on peutreconstruire x(t):

x(t) =∑n∈Z

xn sinc(π

τe(t − nτe)

)• Remarque : il est possible d’obtenir un signal bien

échantillonné conjointement en temps et en fréquenceavec N points.

Acquisition de données numériquesSchéma classique

!"#$%#&'()'Sampling

* +,#&-"$./(0%$1"2'3/4/2%&5'6,4'2%&%./0'2/./'/789%$%.%,#

: 9#%6,450)'sample 2/./'/.';)89%$. 4/."'<=>'?,94%"4'(/#2@%2.1A'

$/530" too

much

data!

• Une image classique : N = 2304× 3072 ' 7 · 106

échantillons.• De plus en plus (et beaucoup) de données numériques :

• Photos, vidéos, réseaux de capteurs, wifi,...• Augmentation des résolutions, des durées,...• Multiplication des modalités : sons, images, RF, IR, UV,...

• « Avalanche de données » !

Compressibilité des signaux, images,...(transformée en ondelettes, bases adaptées, DCT, Temps-fréquence,...)

Modern Image Representation: 2D Wavelets

• Sparse structure: few large coeffs, many small coeffs

• Basis for JPEG2000 image compression standard

• Wavelet approximations: smooths regions great, edges much sharper

• Fundamentally better than DCT for images with edges

!"#$%&'( )*+,-"$.%%&/&0&'(

"&1.0%0#$2.3#4.0.'5,.66&5&.7'%

8/09.*:*;<

3&=./#7=%&27#0%#-"0.%

0#$2.>#/,$*8?@<5,.66&5&.7'%

'&-.

6$.A9.75(

Nombre depoints du sig-nal = N Knombre decoefficientssignificatifs

Compressibilité des signaux, images,...Wavelet Approximation

2 4 6 8 10

x 105

!5

!4

!3

!2

!1

0

1 megapixel image 25k term approx B-term approx error

• Within 2 digits (in MSE) with ! 2.5% of coeffs

• Original image = f , K-term approximation = fK

"f # fK"2 ! .01 · "f"2

1 megapixel 25 kpixel log(erreur) à K termes• Approximation à K termes xK , de l’image initiale x :

||x − xK ||2 ' 0.01||x ||2


!"#$%#&'()'Sampling

* +,#&-"$./(0%$1"2'3/4/2%&5'6,4'2%&%./0'2/./'/789%$%.%,#

: 9#%6,450)'sample 2/./'/.';)89%$. 4/."'<=>'?,94%"4'(/#2@%2.1A

: compress 2/./

compress .4/#$5%.B$.,4"

4"7"%C" 2"7,534"$$

$/530"

JPEG

JPEG2000

…


!"#$%#&'()'Sampling

* +,#&-"$./(0%$1"2'3/4/2%&5'6,4'2%&%./0'2/./'/789%$%.%,#

: 9#%6,450)'sample 2/./'/.';)89%$. 4/."'<=>'?,94%"4'(/#2@%2.1A

: compress 2/./

compress .4/#$5%.B$.,4"

4"7"%C" 2"7,534"$$

$/530"

JPEG

JPEG2000

…

!"#$%#&'()'Sampling

* +,#&-"$./(0%$1"2'3/4/2%&5'6,4'2%&%./0'2/./'/789%$%.%,#

: 9#%6,450)'sample 2/./'/.';)89%$. 4/."'<=>'?,94%"4'(/#2@%2.1A

: compress 2/./

compress .4/#$5%.B$.,4"

4"7"%C" 2"7,534"$$

$/530"

JPEG

JPEG2000

…






Questions sur le schéma d’acquisition usuel

• Pourquoi se fatiguer à acquérir (à haute fréquence) Npoints et en jetter le plus grand nombre pour n’en garderque K N ?

• Echantillonnage = opération linéaireCompression = opération non-linéaire

→ les regrouper en une seule ?• Proposition récente : l’echantillonnage compressé→ essayer d’acquérir directement des donnéescompressées ?→ généraliser l’opération de “mesure”

Acquisition de données numériques

• L’échantillonnage compressé (Compressed Sensing ouCompressive Sampling) renouvelle l’approche del’acquisition de données numériques.

• Proposition récente :• travaux précurseurs (et théoriques) : ∼2000 à 2005 ;• explosion du domaine : depuis 2006 ou 2007• en TSI ou en apprentissage en 2010 : ∼1/3 de articles de

conf. mentionnent ce sujet...

• Remarque : ici, formulation signaux discrets ; cf. travaux deVetterli et al. pour questions analogues en temps continu.

Acquisition en Compressed Sensing

!"#$%&''()&*+&,'(,-

. /(%&0123*4056(%&*7compressed8 9414

. :&$240&*'4#$2&'*;3*#"%&*-&,&%42*7#&4'6%&#&,1'8

compressive sensing 1%4,'#(1<'1"%&

%&0&()& %&0",'1%601






• Nombre initial de points : N x• Nombre de coefficients importants : K α

• Nombre de mesures : M y

K ≈ M N

Généraliser l’opération de mesure

• signal x• base ou dictionnaire de fonctions φi

• mesures linéaire : yi = 〈x , φi〉, i = 1, ...,M

y = Φx

• Exemple : moyenne sur un “gros” pixel

Coded Acquisition

• Instead of pixels, take linear measurements

y1 = !f, !1", y2 = !f, !2", . . . , yM = !f, !M"

y = !f

• Equivalent to transform domain sampling,!m = basis functions

• Example: big pixels

ym = !,

"




y = Φx

• Exemple : intégrale sur une ligne (tomographie)

Coded Acquisition


y1 = !f, !1", y2 = !f, !2", . . . , yM = !f, !M"

y = !f


• Example: line integrals (tomography)

ym = !,

"




y = Φx

• Exemple : acquisition dans l’espace de Fourier (sinusoïde)

Coded Acquisition


y1 = !f, !1", y2 = !f, !2", . . . , yM = !f, !M"

y = !f


• Example: sinusoids (MRI)

ym = !,

"

Généraliser l’opération de mesureSampling Domain

yk = !,

? "• Which !m should we use to minimize the number of samples?

• Say we use a sparsity basis for the !m:M measurements = M -term approximation

• So, should we measure wavelets?

• Quel choix de Φ pour minimiser le nombre de mesures M ?• La position des K coefficients dépend du signal !






Principe d’acquisition incohérente

• Idée : chaque mesure doit combiner plusieurs points, sanscohérence entre eux

• En statistique : group testing [Robert Dorfman, 1943]• Autre problème jeu : identifer le seau avec les fausses

pièces d’or

!"#$%&"'(&)%*+,-./001,2344,

.56789:,

!"#$%&'()*+,-.&+/)&0123)+&4,+/&-#3)&2",*56&&

;<=>"#:%& 7),8/&#&2",*&-9":&)#2/&0123)+& ;":<9)55,"*&

=123)+&>&

*1:0)95& ?&*1:0)9&

.5?9*8##8),086#"6@%& =123)+&>&

?&*1:0)9&

7),8/&#&&"68%*&2":0,*#+,"*&"-&2",*5&-9":&%&&&0123)+5&

!"#$%&"'(&)%*+,-./001,2344,

.56789:,

!"#$%&'()*+,-.&+/)&0123)+&4,+/&-#3)&2",*56&&

;<=>"#:%& 7),8/&#&2",*&-9":&)#2/&0123)+& ;":<9)55,"*&

=123)+&>&

*1:0)95& ?&*1:0)9&

.5?9*8##8),086#"6@%& =123)+&>&

?&*1:0)9&

7),8/&#&&"68%*&2":0,*#+,"*&"-&2",*5&-9":&%&&&0123)+5&

• Approche à la Shannon : peser 1 pièce par seau→ Nmesures→ Compression = 1 résultat

• Echantillonnage compressé : peser des combinaisons(linéaires) de pièces de tous les seaux→ peu de mesures

Principe d’acquisition incohérente

• En signal & images : principe d’incertitude généralisée• Rappel : incertitude à la Gabor-Heisenberg

∆t ∆f ≥ 4π

• Pour des séquences de N points [Donoho, Starck 1989] :on note Nt le nombre de points non nuls en temps, Nf enfréquence

Nt + Nf ≥ 2√

N

Csq : si x concentré en temps, il est étendu en fréquence• Pour d’autres bases orthonormale ϕi et ψj :

cohérence µϕ,ψ = maxi,j |〈ϕi , ψj〉| et on a

Nϕ + Nψ ≥ 2/µϕ,ψ

Principe d’acquisition incohérente• Utilisation : un signal parcimonieux (avec K coefficients

non nuls, K petit) dans un domaine est forcément étalédans un domaine peu cohérent avec le domaine deparcimonievoir [Donoho, 1999], [Candès, Romberg, 2004]→ on peutle retrouver avec peu de mesures ds ce 2e domaine

0 50 100 150 200 250 300 350 400 450 500

−1

−0.5

0

0.5

1

Signal original K−Parcimonieux

Espace / Temps0 50 100 150 200 250 300 350 400 450 500

−5

0

5

Fréquence

Signal dans Fourier

• En poussant au bout de cette logique :un domaine de représentation incohérent avec tous lesautres est de mesurer en combinant au hasard leséchantillons.→ idée de base de l’échantillonnage compressé

Comment peut marcher le Compressed Sensing ?

• Hypothèse x signal K -sparse (parcimonieux)(ou dans une base ou un dictionnaire Ψ,signal x = Ψα et α parcimonieux)

• Exemple minimal : signal 1D parcimonieux à K éléments,(Ψ = Id et x = α).

! "#$%&'((((((#)((((*sparse #%(+&)#),-#./#0%&12

3 4567(&))89:();&1):(#%();&.:(-09&#%

! Samples

);&1):)#$%&'

%0%<:10:%/1#:)

9:&)81:9:%/)

"&9;'#%$


• Objectif : mesure condensée du signal, avec seulement Mmesures linéaires

Compressive !"#$%&'(

) *+,'-."/"-&0-0$"10,234#$1,00&5%,6-3"'-.&1,3/%7-"389&1,-"-condensed representation :&/+-'42%&//%,-&';41#"/&4'-%400-/+149(+-%&',"1-dimensionality reduction

#,"091,#,'/00$"10,0&('"%

'4'<,14,'/1&,0


• Projection Φ ne peut pas être de rang plein : M < N• ⇒ perte d’information en général (infinité de solutions à

y = Φx)• Cependant : on se limite à des vecteurs parcimonieux!"#$%&'$()$*"+,-

. /+"012)3"'$'")$4566$+&',7

7 &'8$9"$6"919$3'4"+:&)3"'$3'$;1'1+&6

. <5)$#1$&+1$"'6=$3')1+19)18$3'$sparse >12)"+9

2"65:'9

→

!"#$%&'$()$*"+,-

. /+"012)3"'$'")$4566$+&',7

7 &'8$9"$6"919$3'4"+:&)3"'$3'$;1'1+&6

. <5)$#1$&+1$"'6=$3')1+19)18$3'$sparse >12)"+9

. 39$14412)3>16=$M?K

2"65:'9


• Projection Φ doit être choisie telle que les sous-matrices

M × K sont de rang plein.

!"#$%&'$()$*"+,-

. Goal: /0123'$$$$$$1"$)4&)$2)1$M52K 1678&)+2901 &+0$:6;;$+&',

< =2::0+0'90$$$$$$$$$$$$$$$$$$70)#00'$)#"$K>1?&+10$@09)"+1$21$AK 1?&+10$2'$30'0+&;

< ?+010+@0$2':"+8&)2"'$2'$K>1?&+10$123'&;1

< Restricted Isometry Property BC(DE$":$"+=0+$AK

9";68'1

• En fait : les sous-matrices M × 2K de rang plein.• la différence de 2 vecteurs parcimonieux est

2K -parcimonieuse ;• cela préserve l’information des vecteurs K -parcimonieux ;• c’est la Restricted Isometry Property (RIP) d’ordre 2K.

• Question : design ? → combinatoire, NP-complet,...


• Projection Φ doit prendre de l’information un peu partout etce, à chaque ligne, sans trop de spécificité.

0 50 100 150 200 250 300 350 400 450 500

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1


Espace / Temps

→ Φ matrice aléatoire !?

!"#$%&''()&*+,-,*./01('(-("2

3 4&,'1%&#&2-'******5* random linear combinations

"6*-7&*&2-%(&'*"6

3 89:*;"&'*2"-*;('-"%-*'-%1/-1%&*"6*'$,%'&*'(<2,='*

> 2"*(26"%#,-("2*="''

#&,'1%&#&2-''$,%'&'(<2,=

2"2?&%"&2-%(&'

Comment peut marcher le Compressed Sensing ?• Résultat des années 80 (Kashin, Gluskin) :

Si on tire Φ au hasard :• i.i.d. Gaussien,• i.i.d. Bernoulli (±1), ...

alors Φ a la RIP(2K) avec grande probabilité souscondition que

M = O(K log(N/K )) N

!"#$%&''()&*+,-,*./01('(-("2

3 4&,'1%&#&2-'******5* random linear combinations

"6*-7&*&2-%(&'*"6

3 89:*;"&'*2"-*;('-"%-*'-%1/-1%&*"6*'$,%'&*'(<2,='*

> 2"*(26"%#,-("2*="''

#&,'1%&#&2-''$,%'&'(<2,=

2"2?&%"&2-%(&'

Illustration du principe de Compressed Sensing

• Signal de N = 512 points, parcimonieux avec K = 10 pics.• Matrice aléatoire N par M = 128 mesures.

0 50 100 150 200 250 300 350 400 450 500

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1


Espace / Temps

Matrice de mesure aleatoire (gaussienne)

20 40 60 80 100 120

50

100

150

200

250

300

350

400

450

500

Illustration du principe de Compressed Sensing

• Signal de N = 512 points, parcimonieux avec K = 10 pics.• Matrice aléatoire N par M = 128 mesures

0 50 100 150 200 250 300 350 400 450 500

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1


Espace / Temps0 20 40 60 80 100 120

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

Signal mesure de DIMENSION reduite

Axe variable mesuree

• Question : retrouver x en pratique ?(P) Etant donné y = Φx (et Φ), trouver x ?

Reconstruction en Compressed Sensing• Φ n’est pas de rang plein (seules ses sous-matrices...)→ Inversion naïve par moindres carrés échoue :

(`2) x = arg minx :y=Φx

||x ||2(

ou arg minx||y − Φx ||22 + λ||x ||22

)

0 50 100 150 200 250 300 350 400 450 500

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

Reconstruction en Optimisation l2

Espace / Temps

• Exploiter la parcimonie (supposée) du signal et sagéométrie changer de norme de mesure !

Reconstruction en Compressed Sensing• Parcimonie = chercher les solutions avec le plus petit

nombre de coefficients non nuls.

||x ||0 = Card i : xi 6= 0 ; ||x ||1 =∑

i

|xi |

→ Inversion au min de `0 est exacte, mais combinatoire


||x ||0

→ Inversion au min de `1 est exacte si x est parcimonieux(i.e., ||x ||0 ≤ K )


||x ||1

• [Candès, Romberg, Tao (2004) ; Donoho (2001-2003)](aussi : `1 rend les solutions parcimonieuses [Fuchs 97])

Reconstruction en Compressed Sensing

• (`1) x = arg minx :y=Φx

||x ||1Ce problème se résout bien par Programmation linéaire.

0 20 40 60 80 100 120

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1



→

0 50 100 150 200 250 300 350 400 450 500

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

Reconstruction en Optimisation l1 avec égalité

Espace / Temps

Reconstruction en Compressed Sensing

• (`1), aussi appelé (BP) pour Basis Pursuit (Donoho 2000):

x = arg minx :y=Φx

||x ||1

• (`1) peut se réécrire en Programmation linéaire :

x = arg min(u,v):

u + vu, v ≥ 0(Φu − Φv) = y

• → cf. un cours d’optimisation...

Pourquoi reconstruction marche en `1 ?

• Théorèmes...cf. [Candès, Romberg, Tao; Donoho; Baraniuk, Wakin; ...]

• Regard géométrique!"#$L2 %&'()*+$!&,-$

.'/(+$(01/,'(234)4313$L5 (&.1+4&)4($/.3&(+$never sparse

!"#$L1 !%&'(

)*+*),)$L1 (%-,.*%+/$L0 (01&(2(.$(%-,.*%+$*3

random orientation

dimension N-M

Lien avec les problèmes inverses

• Problème inverse ' retrouver l’information (ou les sources)à partir des mesures

Lien avec les problèmes inversesTomographie à rayons X (imagerie médicale)

Lien avec les problèmes inversesReconstruction 2D à partir de projections

Lien avec les problèmes inversesAutre de problème inverse : déconvolution

Approche générale des problèmes inverses

• Modèle (direct) de mesure y à partir de la source x :

y = Φx+ bruit

• Φ = opérateur de convolution, de flou, de tomographie, etc.• En géneral, problème mal posé (plus de sources que de

mesures) ou au moins mal conditionné (bruit à la mesureest amplifié en un bruit très fort sur l’estimation de lasource).

• Stratégie usuelle : combiner une attache aux donnéesavec une régularisation, par exemple :

x = arg minx||y − Φx||22 + λ||x ||22

(moindre carré + régularisation de Tikhonov)

Lien avec les problèmes inversesExemple : sur-résolution

Image de Saturne par le Hubble Space Telescope (image EricThiébaut, CRAL)

Lien avec les problèmes inversesExemples : déconvolution aveugle

Image de microscopie confocale (algo. Eric Thiébaut, CRAL)

Données du Centre commun de Quantimétrie (Univ. Lyon 1)

Lien avec les problèmes inverses

• Problème initial du compressed sensing

x = arg minx :y=Φx

||x ||0

• Problème relâché : `1 est la relaxation convexe de `0

x = arg minx :y=Φx

||x ||1

• Problème inverse un peu plus général, avec attache auxdonnées moins contraignante

x = arg minx :y=Φx

||x ||1 + λ||y − Φx ||22

• Plus généralement : critère variationnel selon problèmedirect ou approche bayésienne

Traiter le bruit en Compressed Sensing• Résistance au bruit : (BPDN) pour Basis Pursuit

Denoising (Donoho 1998) :

(BPDN) arg minx

12||y − Φx ||2 + λ||x ||1

problème “dual” de celui à Contraintes Quadratiques :

(QC) arg minx :||y−Φx ||2<ε

||x ||1

0 20 40 60 80 100 120

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1



→

0 50 100 150 200 250 300 350 400 450 500

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

Reconstruction en Optimisation l1 avec QC

Espace / Temps

Ajouter la compressibilité en Compressed Sensing

• Résultats théoriques de Candès & Tao.• Reconstruction robuste : pour tout x ∈ Rn, soit x , solution

de (`1). Alors, on a

||x − x ||1 ≤ C||x − xK ||1 et ||x − x ||2 ≤ C||x − xK ||1

K 1/2

• Reconstruction stable : mesure de y = Φx + e où le bruitest t.q. ||e||2 < ε et retrouver x par (QC) . Alors, pour toutx ∈ Rn, on a

||x − x ||2 ≤ C1||x − xK ||1

K 1/2 + C2ε

Acquisition avec de l’aléatoire→ Universalité du CS

• Propriétés pour Φ : mesures globales, incohérentesOn vient de voir une solution : matrices aléatoires

• Adaptation à des signaux parcimonieux sur bases oudictionnaires (Ψ)

x = Ψα ou xi = 〈φi , α〉

!"#$%&'()#*+

, -("./010%('2&%0%"*'13("14%12'%.15/&1'#6"()'1'7(&'%1#"1any 4('#'

Acquisition avec de l’aléatoire→ Universalité du CS• Le schéma devient :

!"#$%&'()#*+

, -("./010%('2&%0%"*'13("14%12'%.15/&1'#6"()'1'7(&'%1#"1any 4('#'

!"#$%&'()#*+

, -("./010%('2&%0%"*'13("14%12'%.15/&1'#6"()'1'7(&'%1#"1any 4('#'

'7(&'%3/%55#3#%"*$%3*/&

"/"8%&/%"*&#%'

Acquisition avec de l’aléatoire→ Universalité du CS

• Propriété : Matrice aléatoire × Base ' Matrice aléatoire stratégie universelle d’encodage, Ψ précisé a posteriori

• Autres solutions : incohérence de Φ par rapport à Ψ• tirage aléatoire de coefficients de Fourier• fonctions de mesures à produit scalaire toujours non nul

avec tous les signaux parcimonieux

(→ cf. travaux sur la cohérence entre dictionnaires, enparticulier [Tropp & Gribonval])

• Sorte de Principe d’incertitude à vérifier entre la base demesure et la base de parcimonie.

Algorithmes de reconstruction• Le nombre d’algorithmes disponibles augmente.• Catégories d’algorithmes d’optimisation (convexe) pour

(BP) :y = arg min

x :y=Φx||x ||1

• méthodes de point intérieur (lent, très précis, analysesthéoriques)

• méthodes de gradient (1er ordre) (rapide, maisconvergence...)

• méthode d’homotopie (rapide, exact mais pour petitestailles)

• Domaine actif : trouver les bonnes méthodes pour pb degrande taille, résistantes au bruit, marchant pour signauxcompressibles (et non seulement parcimonieux),convergence prouvable, etc.

• Deux exemples : MP, IST

Algorithme de reconstruction : Matching Pursuit

• Algorithme itératif• 1) Retenir les composantes “actives”, en cherchant les

colonnes de Φ qui sont les plus corrélées avec y• 2) Soustraire ces composantes de y donne un résidu y ′

• 3) Itérer avec y ′

• Les composantes actives sont orthogonales d’une itérationà l’autre

• Très rapide pour pb de petite taille• Pas très précis si plus grande taille (images...) ou avec

bruit• Amélioration : Orthogonal Matching Pursuit

[Mallat & Zhang, 93; Gribonval & Tropp; ...]

Algorithme de reconstruction : Iterated Thresholding

• Algorithme itératif• 1) À l’étape k , projeter xk pour obtenir wk = ΦT Φxk

• 2) Seuillage de wk donne xk+1, par exemple par SoftThresholding

• Marche bien car, pour des signaux parcimonieux, wk grandsur les coefficients actifs, petit ailleurs

• Méthode de minimisation `1• Très rapide, très bon pour signaux parcimonieux, ok si

approximativement parcimonieux• Remarque : ouvre le chemin aux algorithmes proximaux

[Daubechies, DeFrise, DeMol 2004; Chambolle 2005;Combettes & Pesquet; Blumensath & Davies; ...]

Illustration 1 - exemple simulé[Candès, Romberg, Tao, IEEE Info. Theory, 2006]• Exemple en tomographie IRM : acquisition dans le

domaine fréquentrie, ici d’une image “fantôme”

Image originelle (lisse par morceaux)

20 40 60 80 100 120

20

40

60

80

100

120

Log de Norme des coefficients de Fourier

Axe variable mesuree20 40 60 80 100 120

20

40

60

80

100

120

Illustration 1 - exemple simulé

• Image (∼parcimonieuse) en espace ; donc incohérencevis-à-vis du domaine de Fourier

Masque de mesure dans plan de Fourier

20 40 60 80 100 120

20

40

60

80

100

120

Log de Norme des coefficients de Fourier mesures

Axe variable mesuree20 40 60 80 100 120

20

40

60

80

100

120


• Reconstruction par (BP) : x = arg minx :y=(Fx)|Ω ||x ||1


20 40 60 80 100 120

20

40

60

80

100

120

Reconstruction en Optimisation L1 avec egalite

20 40 60 80 100 120

20

40

60

80

100

120


• Reconstruction par (QC) : x = arg minx :||(y−Fx)|Ω||2<ε ||x ||1


20 40 60 80 100 120

20

40

60

80

100

120

Reconstruction en Optimisation L1 avec erreur

20 40 60 80 100 120

20

40

60

80

100

120


• Reconstruction en Variation Totale :(TV )x = arg minx :y=(Fx)|Ω TV (x) ≈ ||∇x ||1


20 40 60 80 100 120

20

40

60

80

100

120

Reconstruction en Optimisation TV

20 40 60 80 100 120

20

40

60

80

100

120

Illustration 2 - caméra à 1 pixel

[Duarte et al., “Single-Pixel Imaging via CompressiveSampling”, IEEE Signal Processing Mag., 83, 2008]

Rice Single-Pixel CS Camera

randompattern onDMD array

DMD DMD

single photon detector

imagereconstruction

orprocessing

Illustration 2 - caméra à 1 pixelSingle Pixel Camera

Object LED (light source)

DMD+ALP Board

Lens 1Lens 2Photodiode

circuit



DMD+ALP Board


circuit



DMD+ALP Board


circuit

Illustration 2 - caméra à 1 pixelFirst Image Acquisition

target 65536 pixels

1300 measurements (2%)

11000 measurements (16%)

Illustration 2 - caméra à 1 pixelSecond Image Acquisition

500 random measurements

4096 pixels

Illustration 2 - caméra à 1 pixelSingle-Pixel Camera

randompattern onDMD array

DMD DMD

single photon detector

imagereconstruction

orprocessing

Remarques finalesAutres exemples d’applications :• Echantillonnage sous-Nysquist• Tomographie à faible nombre de vue• Holographie numérique de particules• Astronomie, imagerie ultra-sonore, DNA-arrays,

multi-capteurs (dont réseaux de capteurs),...• Et bien d’autres,...

Page de ressource :• Pour trouver une bibliographie riche sur le sujet :

page CS de Rice Universityhttp://dsp.rice.edu/cs

Remerciements à R. Baraniuk, dont les images ont étéamplement empruntées pour ce cours

Documents

M2 SC - Usages du hasard l'échantillonnage compresséperso.ens-lyon.fr/pierre.borgnat/MASTER2/cours_M2SC_Bruit... · Théorème de Shannon-Nysquist: si x(t) ... ¥ Basis for JPEG2000