Basarab MATEIMaitre de ConferencesUniversite Paris - Nord

Dossier de Candidature

Institut GalileeLAGA - LIPN

Table des matieres

1 Presentation 2

2 Travaux 3

3 Enseignement 5

4 Encadrement scientifique 6

5 Animation Scientifique 7

6 Recherche 8

7 Communications Orales. 25

8 Participations a des Colloques. 25

9 Perspectives 26

1 Presentation

Basarab MATEImarie, deux enfantsAdresse personnelle :

14, rue du General de Gaulle,Residence Voltaire, Bat.D., Esc 1.92290 Chatenay-Malabry.Tel. : (33)-9 51 33 72 59

Adresse professionnelle :

Lab. Analyse, Geometrie et Applications,Universite Paris Nord,99 Avenue Jean-Baptiste Clement,93430 VilletaneuseTel. : (33)-1 49 40 35 71.e-mail : matei@math.univ-paris13.fr

Themes de recherche

• Traitement du signal et de l’image.• Methodes Multi-echelles et Adaptatives.• Theorie de l’Approximation, Modelisation Geometrique des Images.• Developpement d’algorithmes de compression progressive d’images fixes ou animees (JPEG 2000).• Compressed Sensing - Parcimonie.• Echantillonnage Irregulier.

Position Actuelle : Maıtre de Conferences a l’Institut Galilee de l’Universite Paris Nord.

En decembre 2011, j’ai soutenu mon Habilitation a Diriger des Recherches ”Parcimonie et differentsproblemes dans les traitement d’images“, devant le jury compose de Andres Almansa, Antoine Ayache,Francoise Dibos, Dennis Gratias et Yves Meyer. Les rapporteurs sur mes travaux etant MM. KarlheinzGrochenig, Stephane Jaffard et Yves Meyer.

2

Formation

2004-2011 : Maıtre de Conferences a l’Institut Galilee.2003-2004 : PostDoc RMOD-collaboration INRIA-UMPC. Responsable Marc Thiriet.2001-2003 : ATER a l’Universite Paris–X (Nanterre).1998-2002 : Doctorat de Mathematiques appliquees a l’universite Paris VI.

Directeur de these : Albert Cohen.Sujet : Methodes multiresolutions non-lineaires : Applications au traitement d’image.soutenue le 20 novembre 2002.

1996-1997 : D.E.A. de Statistiques Appliquees et Optimisation a l’Universite de Bucarest Roumanie.Stage de D.E.A. a l’Universite Pierre et Marie Curie supervise par Albert Cohen.Sujet : Resolution numerique du bi-laplacien par une methode d’ondelettes interpolantes.Boursier Programme Europeen TEMPUS, admis sur concours.

1990-1996 : Diplome de fin d’etudes avec une double specialisation :Mathematiques Appliquees et Informatique,a la Faculte de Mathematiques de Bucarest

1989-1990 : Service Militaire.Juillet 1989 : Admis sur concours a la Faculte de Mathematiques de Bucarest.

2 Travaux

These de Doctorat

Methodes multiresolutions non-lineaires : Applications au traitement d’image.

Habilitation a Diriger de Recherches

Parcimonie et differents problemes dans les traitement d’images

Publications

A1 Quasilinear Subdivison Scheme with Applications to ENO interpolation, en collaboration avecA. Cohen et N. Dyn, Appl. Comput. Harmon. Anal. 15, pp. 89-116, 2003.

A2 Smoothness Characterization and Stability in Nonlinear Multiresolution Framework - TheoreticalResults, Asymptotic Analysis, vol. 46, pp. 277-309, 2005.

A3 Approximation of piecewise smooth images by edge-adapted techniques. en collaboration avec F.Arandiga, A. Cohen, R. Donat et N. Dyn, Appl. Comput. Harmon. Anal.vol. 24, pp. 225-250,2008.

A4 Edge detection insensitive to changes of illumination in image en collaboration avec F. Arandiga,A. Cohen, R. Donat, Journal Image and Vision Computing, Volume 28 Issue 4, April, 2010.

A5 A variant of compressed sensing en collaboration avec Y. Meyer Rev. Mat. IberoamericanaVolume 25, pp. 669-692, 2009.

A6 Quasicrystals are sets of stable sampling en collaboration avec Y. Meyer paru dans ComplexVariables and Elliptic Equations 55, 947-964, 2010.

A7 Smoothness of non-linear and non-separable subdivision schemes. en collaboration avec SylvainMeignen et Anastasia Zakharova, paru dans Asymptotic Anal. 74, No. 3-4, 229-247,2011.

3

A8 Smoothness Characterization and Stability in Nonlinear Multiresolution Framework - Applica-tions, a paraıtre dans Asymptotic Analysis.

A9 B. Matei et S. Meignen, Analysis of a class of nonlinear and non-separable multiscale repre-sentations, en collaboration avec Sylvain Meignen paru dans Numerical Algorithms, pp. 1-28,2011.

A10 Smoothness characterization and stability of nonlinear and non-separable multiscale represen-tations. en collaboration avec Sylvain Meignen et Anastasia Zakharova, paru dans J. Approx.Theory, 163, No. 11, 1707-1728, 2011.

Chapitres d’ouvrages

B1 Nonlinear Subdivison Schemes : Applications to Image processing, en collaboration avec A. Co-hen, paru dans Tutorials on Multiresolution in Geometric Modelling, A. Iske, E. Quak et M.S.Floater eds.,Springer Verlag, 93-97, 2002.

Articles soumis

S1 B. Matei et S. Meignen, A New Formalism for Nonlinear Multiscale Denoising, soumis au SignalProcessing en revision, hal-00529531.

S2 B. Matei et S. Meignen, A New Algorithm for Nonlinear and Non-Separable Multiscale Com-pression, soumis au Signal Processing en revision.

Actes des conferences internationales avec comite de lecture

C1 Compact representations of images by edge adapted multiscale transform, en collaboration avecA. Cohen, IEEE International Conference on Image Processing, Thessaloniki, Octobre 2001.

C2 Sparse representations of images by edge adapted non-linear multiscale transforms en collabora-tion avec F.Arandiga, A.Cohen, M.Doblas, R.Donat, IEEE International Conference on ImageProcessing, Barcelona, 2003.

C3 Nonlinear Multiscale Methods and theirs applications to homogenization accepte pour publicationdans International Conference : New Trends Continuum Mechanics, Constanta, Septembre 2003.

C4 Simultaneous edge and texture compression en collaboration avec J.F.Aujol, ICPR InternationalConference on Pattern Recognition, 2004.

C5 B. Matei et S. Meignen, A. Zakharova, On a (W)ENO-type multiscale representation based onquincunx refinement : Application to image compression. en collaboration avec Sylvain Meignenet Anastasia Zakharova, paru dans Boissonnat, Jean-Daniel (ed.) et al., Curves and surfaces.Revised selected papers. Berlin : Springer. Lecture Notes in Computer Science 6920, 473-487,2012.

Notes aux Comptes Rendus

N1 Smoothness Characterization and Stability in Nonlinear Multiresolution Framework.

N2 Denoising using Nonlinear Multiscale Transform.

N3 Optimal Compression Algorithms using Nonlinear Multiresolution Representations.

N4 Quasicrystals are sets of stable sampling avec Y. Meyer.

N5 Nonlinear and non-separable multiscale representations based on Lipschitz perturbation. C. R.,Math., Acad. Sci. Paris 349, No. 13-14, 741-744, 2011 , avec S. Meignen et C. Gerot.

4

Articles en preparation

P1 En collaboration avec S. Meignen Nonlinear Multiscale Representation for Stable Denoising.

3 Enseignement

Mon activite d’enseignement a commence en 1996 tout au long de la derniere annee d’etudes a Bu-carest et cela en qualite d’Assistant a l’Universite Polytechnique de Bucarest. Cette activite je l’aipoursuivie des le debut de la these en tant que vacataire a l’Universite Paris VI, puis pendant les deuxdernieres annees de these a l’Universite Paris X-Nanterre, comme ATER a temps complet. Depuisseptembre 2004, je suis maıtre de conferences a l’Institut Galilee, ou mon enseignement se concentreautour du laboratoire d’Informatique. (LIPN). L’essentiel de ces enseignements necessitait de four-nir, en interaction directe avec mes collegues enseignants, un contenu adapte au public qui puissecreer aux etudiants une relation decomplexee avec les disciplines scientifiques leur donnant ainsi l’en-vie de progresser et les outils pour y parvenir. Ce but est a la fois interessant et formateur, memes’il est parfois difficile a atteindre. La double specialisation acquise en mathematiques appliqueeset informatique m’a permis d’enseigner dans les deux domaines. Je mentionne que pour tous lesenseignements dont j’ai eu la charge, j’ai participe a la redaction des polycopies, a la preparation desexercices et du controle continu ainsi qu’a la correction des copies.

2006–2009Responsable L3 Informatique

2009–2010Responsable C2I

2010–Responsable Option CHMDE- Ecole d’Ingenieurs SUP Galillee

Voici une presentation detaillee de mes enseignements :

1996–1998 :En tant qu’Assistant a l’Universite Polytechnique de Bucarest, j’ai effectue des travaux diriges qui cor-respondent a la premiere annee de DEUG : bases de l’informatique, bases de donnees, logique pourl’informatique et aussi des travaux diriges qui correspondent a la Licence : theorie de files d’attente et lasimulation des reseaux et aussi la theorie des codes.

1999–2000 :Travaux pratiques de SCHEME et “C++” a l’Universite Paris VI en tant que vacataire.

2001–2002 et 2002–2003 :TD du cours de Statistiques pour les etudiants de Licence Sciences Economiques de l’Universite ParisX. Etude qualitative d’une variable aleatoire, moyenne, ecart-type, estimations de parametres, etude dedeux variables aleatoires, intervalles de confiance, tests statistiques parametriques et non-parametriques.

2001–2002 et 2002–2003 :TD des cours de Mathematiques pour les etudiants de deuxieme annee de DEUG MASS de l’UniversiteParis X. Espaces normes, series de Fourier, limites, continuite et differentiabilite pour les fonctions deplusieurs variables, equations differentielles du premier et second ordre.

2002–2003 :TD du cours de Mathematiques pour les etudiants de premiere annee de DEUG Sciences Economiques del’Universite Paris X. Nombres Complexes, suites, etude de fonctions, etude locale de fonctions et extrema.

5

2002–2003 :TD des cours de Mathematiques pour les etudiants de premiere annee de DEUG Sciences Economiquesde l’Universite Paris X. Algebre lineaire, espaces vectoriels, etude de fonctions, etude locale de fonctionset extrema, moindres carres, etude de fonctions de plusieurs variables, optimisation.

2004–2011 :Cours et TD de Traitement d’image avance pour les etudiants de troisieme annee INFO SUP Galilee.Echantillonnage et reconstruction. Convolution. Notation polaire. Transformees-Z et de Fourier. Analysespectrale. Filtrage numerique (FIR et IIR). Transformee en ondelettes. JPEG 2000.

2004–2011 :Cours et TD de Fouille de Donnees Visuelles pour les etudiants de deuxieme annee du Master ProfessionnelInformatique EID. Echantillonnage. Operations sur les images. Amelioration. Restauration. Compression.Realisation d’un projet applique.

2007–2010 :Cours et TD d’Infographie pour les etudiants de premiere annee du Master Informatique. Modelisationgeometrique. Courbes et surfaces. Visibilite. Lumiere et ombrage. Modeles de transparence, reflexion,refraction. Textures. Fractales et modeles stochastiques. Antialiasing. Lancer de rayons. Phenomenesnaturels.

2004–2011 :Cours, TD et TP de Theorie de Langages et Compilation pour les etudiants de troisieme annee de LicenceInformatique. Operations elementaires sur les automates finis. Passage d’un automate a une expressionrationnelle.Minimisation. Lemmes d’iterations : application des lemmes d’iterations, non-equivalence etnon-exhaustivite des lemmes d’iteration. Grammaires algebriques. Automates a pile : equivalence avecles grammaires algebriques. Langages algebriques. Hierarchie de Chomsky.

2011–2012 :Cours et TD de Traitement d’image et Ondelettes M2 SIM. Echantillonnage et reconstruction. Convolu-tion. Representations multi-echelles. Filtrage numerique (FIR et IIR). Transformee en ondelettes. JPEG2000.

2004–2011 :TD d’Elements d’Informatique en premiere annee de la Licence. Langage C

4 Encadrement scientifique

J’ai entrepris une activite d’encadrement institutionnelle des stages M2, theses et un stage post-doctoral.

1. 2002-2006, Co-direction de la these de G. Pau avec B. Presquet de l’ENST-Paris. Sujet : On-delettes et decompositions spatio-temporelles avancees ; application au codage video scalable.L’objectif de cette these consistait en l’etude et la construction de nouvelles transformees sca-lables mises en jeu dans le schema de codage video, afin d’ameliorer le gain en compression.L’utilisation du formalisme lifting lors de la construction de ces transformees spatio-temporellespermet l’introduction d’operateurs non-lineaires, particulierement utiles pour representer effica-cement les singularites et discontinuites presentes dans une sequence video. On s’est interesse enparticulier a :– l’optimisation et la construction de nouvelles transformees temporelles compensees en mou-

vement, afin d’augmenter l’efficacite de codage objective et subjective ;– l’elaboration et la mise en place de bancs de filtres M-bandes pour decomposer spatialement

les sous-bandes temporelles ;

6

– l’extension de proprietes de scalabilite du banc de synthese M-bandes a des facteurs rationnelsquelconques ;

– la construction de decompositions spatiales en ondelettes adaptatives, non-lineaires et inver-sibles, sans necessiter la transmission d’une carte de decisions. Cette these s’inscrit dans ledeveloppement de la norme de codage video scalable SVC conduite par le consortium jointMPEG/ITU.

2. Janvier 2009 - Septembre 2010, Co-encadrement du post-doctorat d’Anastasia Zakharova. Sujet :Compression d’images par box splines. Le sujet de post-doctorat etait de mettre en place destechniques non-lineaires et non-separables de decomposition d’image, dans le but d’ameliorer lesperformances des algorithmes de compresssion existants (type JPEG2000). Nous avons developpede telles techniques dans [A7,P2] ainsi qu’un algorithme de compression les utilisant [C5].

3. Depuis septembre 2010 collaboration sur : “Compressed sensing”.Il s’agit d’une collaboration en cours avec S. Meignen sur la direction de la these de T. Oberlinavec le titre “Compressed sensing : representations parcimonieuses, echantillonnage irregulieret decomposition modale empirique”. Etude prevue : l’idee originelle exploitee par le com-pressed sensing repose sur le fait que la plupart des signaux ou des images admettent unerepresentation parcimonieuse, c’est-a-dire que, representes dans une base adequate, les coeffi-cients de la decomposition sont proches de zero. En representant un signal comme une com-binaison lineaire d’echantillons bien choisis dans une base differente de celle pour laquelle lesignal donne une representation parcimonieuse, il a ete montre qu’avec tres peu d’echantillonsdu signal, on peut recuperer la plupart de l’information. Le probleme du choix des echantillonsest aussi celui de la reconstruction : comment choisir les echantillons de facon a avoir une bonnereconstruction ’ La reconstruction impose la resolution d’un systeme lineaire indetermine, car ona beaucoup moins d’echantillons selectionnes que de points dans l’image. Trouver les echantillonsqui minimisent la norme L2 du signal reconstruit, c’est-a -dire l’energie du systeme, n’est pasadapte et ne tient pas compte du fait que les donnees sont parcimonieuses. Les travaux de Taoet al. ont montre que la norme la plus adaptee pour le traitement des donnees parcimonieusesest la norme L1 et que la resolution du probleme de la recherche des echantillons est realisabledans ce cas. Ses methodes ont donne lieu a de tres importants developpements ces dernieresannees, ce qui a litteralement revolutionne le domaine du traitement de l’information. Le do-maine du compressed sensing est a l’heure actuelle l’un des plus competitifs des mathematiquesappliquees, mais presente encore des problemes ouverts. Ainsi, le travail de these s’interesseraa l’echantillonnage efficace sur des grilles non regulieres et a la recherche de points optimauxpour l’interpolation.

5 Animation Scientifique

Je me suis consacre a l’organisation de colloques, le plus important etant certainement le ColloqueFranco-Roumain de Mathematiques Appliquees (2002,2004,2006, 2008, 2012), et l’organisation d’ate-liers plus cibles, ayant toujours en tete la constitution d’une communaute traitement d’images. J’entre-tiens des collaborations nationales et internationales a travers des reseaux, programmes de cooperationet invitations.

1. 2008-2009 : Projet BQR INP-Grenoble : Representation des images geometriques par box splines.Dans ce projet finance par l’INP-Grenoble, il s’agissait de trouver des representations non-lineaires d’images en utilisant les box splines. Des algorithmes de compression ont ete mis enplace [C5].

2. 2004-2007 : Projet Europeen IHP-Breaking Complexity

7

6 Recherche

Mon travail de recherche porte essentiellement sur deux domaines. Le premier concerne les aspects ana-lytiques et numeriques de l’approximation des fonctions de plusieurs variables regulieres par morceauxpar des methodes multi-echelles non-lineaires. Le deuxieme concerne les problemes de l’echantillonnageirregulier des fonctions de plusieurs variables ayant comme spectre un ensemble compact dont seule-ment la dimension est connue, les representations parcimonieuses et leurs applications.

I. Methodes multi-echelles non-lineaires

Le choix d’une representation appropriee d’une fonction est souvent fondamental pour resoudreun probleme donne. En analyse harmonique, on peut decomposer une fonction arbitraire en unecombinaison de fonctions de base ψn,

f(x) = a0ψ0(x) + a1ψ1(x) + a2ψ2(x) + · · · + anψn(x) + · · · . (1)

L’exemple type est le developpement en serie de Fourier, ou les fonctions de base sont les fonctionstrigonometriques. On peut representer alors f par les coefficients a0, a1, a2, · · · . Si le nombre de co-efficients an non nuls est reduit, on parle d’une representation creuse de la fonction f . Dans lecas unidimensionnel, si la fonction f presente des discontinuites, on utilise plutot les bases d’onde-lettes (ψn sont les dilatees et translatees d’une seule fonction ψ). Introduites au milieu des annees 80par Y. Meyer, I. Daubechies et S. Mallat, les ondelettes ont apporte un cadre fonctionnel fecond audeveloppement et a l’analyse des representations creuses. Dans une base d’ondelettes, on a le resultatoptimal ‖f − fN‖L2 ∼ N−1, ou

fN :=∑

N plus grands |an|

anψn.

On relie ainsi la vitesse de convergence aux proprietes de decroissance de la suite (an). L’interetde l’approximation des fonctions regulieres par morceaux est majeur car elles interviennent dans denombreux problemes mathematiques : solutions des EDP (chocs) et traitement numerique de l’image.

Toutefois, les bases d’ondelettes sont mal adaptees pour decrire les fonctions bidimensionnellesregulieres en dehors des ”contours” (ou chocs) ; ceci est du au ”conflit” entre le caractere ”diffus-isotrope” des ondelettes et le caractere ”concentre-anisotrope” des courbes. Une bonne methoded’analyse devra integrer ce caractere globalement inhomogene de l’image par un traitement adaptedes contours.

I.1 Approximation non-lineaire par representations creuses

Pendant ma these, je me suis propose le defi de pallier a cet inconvenient, en remplacant lesrepresentations en bases d’ondelettes par de nouvelles representations, mieux adaptees a la representationde ces fonctions. En effet, ma these propose des nouvelles methodes qui sont mieux adaptees autraitement des fonctions regulieres par morceaux que les methodes preexistantes. J’ai fait une analysetheorique (convergence et stabilite) de ces methodes. Le fait remarquable est que celles-ci sont lesseules, parmi toutes les techniques non-lineaires existantes (shape preserving, convexity preserving,median imputation), pour lesquelles on arrive a prouver la stabilite.

Plusieurs approches avaient deja ete proposees. Elles consistent a adapter la base d’ondelettes a

8

la presence des contours : bases de ridgelets et curvelets [8] (on connaıt pour cette methode le com-portement asymptotique de l’erreur), triangulations anisotropes par des algorithmes de deraffinementiteratifs [20] (sans etude theorique), et les bandelettes [27] (pour laquelle on connaıt le comportementasymptotique de l’erreur sous reserve d’avoir un algorithme qui detecte les contours). Dans chacunedes approches decrites ci-dessus, la recherche de l’anisotropie conduit a ne pas tirer profit de la struc-ture hierarchique arborescente particulierement simple des bases d’ondelettes. Un aspect specifiquedes methodes que nous avons developpees et etudiees est la conservation de cette structurehierarchique.

La methode d’approximation non-lineaire (ENO-Edge Adapted, introduite dans ma these [35])est basee sur des operateurs d’interpolation polynomiale, capable de detecter les singularites desfonctions regulieres par morceaux. Ainsi, il est possible d’augmenter la qualite de l’approximation etde mieux reconstruire les images au voisinage des contours.

L’analyse theorique de ces representations non-lineaires a requis le developpement des nouveauxoutils analytiques. La methode ENO-EA est la generalisation bidimensionnelle du cadre propose parHarten [23] pour la representation des fonctions d’une variable. L’idee de Harten est de tenir compte,lorsqu’on calcule une approximation a l’echelle j, notee vj d’une fonction v des approximations dejacalculees

vj = S(vj−1)vj−1 (2)

ou S est un operateur depandant de donnees, donc non-lineaire. Si vJ est la discretisation (representationexacte) de v a l’echelle J , on peut retrouver vJ a partir du vecteur

MvJ = (v0, d0, · · · , dJ−1), (3)

oudj = vj − vj

est l’erreur d’approximation entre deux echelles succesives. Pratiquement, on ne retient de MvJ queles details dj numeriquement significatifs, et afin de reduire ceux-ci, l’operateur d’approximation S estdefini de sorte a reproduire les fonctions regulieres par morceaux.

Les proprietes theoriques d’approximation de cet operateur non-lineaire bidimensionnel ont eteobtenues apres la these et ont ete publiees dans :

Article : Approximation of piecewise smooth images by edge-adapted techniques. Il s’agit desresultats obtenus en collaboration avec F. Arandiga, A. Cohen, R. Donat et N. Dyn. Nous avonsprincipalement obtenu le

Theoreme d’approximationUne fonction v de classe W 2,∞ par morceaux de part et d’autre d’une union finie de courbes dediscontinuites de classe C2, peut etre approchee par vN calculee avec les N plus grands coefficientsmulti-echelles non-lineaires et l’erreur d’approximation verifie

‖v − vN‖L2 <∼ N−1. (4)

On remarque qu’une approximation avec les N plus grands coefficients d’ondelettes vN verifie

‖v − vN‖L2 <∼ N−1/2. (5)

Cela represente une amelioration significative par rapport aux methodes classiques des bases d’onde-lettes.

Voici une illustration simple des methodes ci-dessus : sur la figure 13, a gauche, nous presentonsune image geometrique et, a droite, ses moyennes locales a une resolution 16 fois plus grossiere. La

9

Fig. 1 – (a) image geometrique (b) basse resolution

Fig. 2 – (a) approximation lineaire (b) approximation non-lineaire

10

figure 14 compare l’approximation obtenue a partir de ces moyennes en utilisant d’abord une approxi-mation lineaire classique, ensuite l’approximation non-lineaire proposee. Le temps calcul est du memeordre dans les deux cas. Dans le premier cas, il est necessaire d’ajouter des coefficients d’ondelettesafin d’ameliorer la precision pres du contour. Dans le second cas, la precision est deja excellente. Cesresultats sont publies dans :

Article : Nonlinear subdivisions schemes : applications to image processing en collaboration avec Al-bert Cohen, paru dans : Tutorial on multiresolution in geometric modelling, A. Iske, E. Quack andM. Floater eds., Springer, 2002.

L’amelioration de la concentration est donc significative en utilisant les methodes non-lineaires.En ce qui concerne les applications pratiques, deux directions sont a privilegier : la compression et ledebruitage. Dans la compression, on cherche a reduire au maximum la taille memoire occupee par uneimage, tout en conservant au mieux sa qualite visuelle. Dans le debruitage, a partir de l’observationd’une image perturbee par un bruit parasite, on cherche a restaurer au mieux l’image source. Surla compression d’images, cette methode s’avere beaucoup plus performante que les methodes non-lineaires utilisees avant. Par ailleurs, cette methode semble avoir bien d’autres applications, notammenta la simulation numerique des EDP (ondes de chocs, elements finis hierarchiques), aux techniquesd’adaptation automatique de maillages ainsi qu’aux problemes d’homogeneisation. L’un de mes axesde recherche dans le futur proche consiste a adapter cette methode a ces problemes-la.

I.2 Analyse des proprietes des representations multi-echelles

non-lineaires

Article : Smoothness Characterization and Stability in Nonlinear Multiresolution Framework : Theo-retical Results. Le resume de cet article est paru dans C. R. Acad. Sci. Paris Ser. I Math., 338, n.2, 2004, pages 1241-1246. La version complete a ete publiee dans la revue Asymptotic Analysis. Ceresultat a ete obtenu pendant ma these.

Apres la these je me suis interesse aux applications de ces resultats theoriques.

Article : Smoothness Characterization and Stability in Nonlinear Multiresolution Framework - Ap-plications, papier accepte pour publication dans la revue Asymptotic Analysis.

Toujours apres la these, j’ai developpe en collaboration avec S. Meignen et A. Zakharova les ou-tils theoriques necessaires a l’analyse des proprietes des r multi-echelles non-lineaires et non-separables.

Article : Smoothness Characterization and Stability of Nonlinear and Non-Separable MultiscaleRepresentations, parru dans Journal of Approximation Theory,

D’un point de vue mathematique, la regularite d’une fonction v se lit a travers les proprietesde decroissance des coefficients multi-echelles. Concretement, prouver la convergence des methodesnon-lineaires revient a etablir pour les erreurs dj une estimation du type

‖v‖Bsp,q

∼ ‖v0‖ℓp + ‖(2(s−d/p)j‖dj‖ℓp)j≥0‖ℓq , (6)

ou Bsp,q est un espace de Besov. Notons que ceci semble ne pas etre vrai dans le cas des ridgelets et

curvelets.La difficulte principale dans l’obtention du (6) est liee au caractere non-lineaire des operateurs

d’approximations S. La reconstruction de la fonction a partir de sa discretisation ne consiste pas en

11

son developpement dans une base bien definie (comme pour les ondelettes (1)). Ma contribution a etede fournir des outils qui permettent d’aboutir au resultat (6) pour des approximations non-lineaires.

La partie difficile est d’etudier la regularite de l’approximation de v de (6). Dans cette analyse,j’ai prouve que si les operateurs d’approximations non-lineaire S sont exacts pour les constantes,alors il existe des operateurs non-lineaires, notes S1, qui, aux differences finies a l’echelle grossiere,associent celles a l’echelle fine :

∆vj+1 = S1∆vj .

L’analyse des S est liee a la contractivite de l’operateur S1, que l’on mesure par son rayon spectraljoint defini par :

ρp(S1) := lim supk→∞

sup(w0,··· ,wk−1)∈(ℓ∞(ZZ))k

‖S1(wk−1) · · ·S1(w

0)‖1/kℓp . (7)

On note que si l’operateur S1 est lineaire alors ρp(S1) represente bien son rayon spectral. Ainsi, j’aiobtenu le resultat suivant :

Theoreme de regularite : cas des espaces de BesovSoit S un operateur d’approximation non-lineaire qui reproduit les constantes et verifiant ρp(S1) <21/p. Alors, pour toute donnee (v0, d0, d1, · · · ), la fonction reconstruite v appartient a Bs

p,q et

‖v‖Bsp,q

<∼ ‖v0‖ℓp + ‖(2(s−d/p)j‖dj‖ℓp)j≥0‖ℓq (8)

pour 0 < s < −log(ρp(S1))

log 2 + 1p et a condition que le membre de droite soit fini.

Ce resultat affirme qu’on peut controler la norme d’une fonction v par la norme discrete associeeaux coefficients multi-echelles et constituent ainsi une premiere etape vers la comprehension des pro-prietes d’approximation des operateurs d’approximation non-lineaires. L’inegalite inverse de (8) estune consequence du theoreme d’exactitude. Les theoremes obtenus s’appliquent aux representationsbasees sur les techniques ENO et ENO-SR, pour lesquelles on a ρp(S1) < 21/p.

Dans les applications telles que la compression et le debruitage, nous sommes amenes a perturberles coefficients de la representation multi-echelles du signal par des operations de seuillage ou dequantification. Il est important de savoir evaluer l’effet de telles perturbations lorsque l’on reconstruitle signal. Plus precisement, si d = Mv est la decomposition multi-echelle d’une fonction v, d est laversion perturbee et v = M−1d la reconstruction associee, on cherche a savoir si

‖v − v‖a <∼ ‖d− d‖b (9)

pour ‖·‖a et ‖·‖b deux normes prescrites. Dans le cas lineaire (9), est la consequence de (8). Dans le casnon-lineaire, (8) n’entraıne pas (9). Ainsi, nous avons ete amenes a fournir, la encore, un cadre generalqui permette l’obtention de la stabilite pour les representations non-lineaires. Le resultat obtenu est

Theoreme de stabilite : cas des espaces BesovOn suppose que S reproduit les constantes, depend de facon lipschitzienne des donnees dans Lp

et verifie ρp(S1) < 21/p. Alors, pour toutes donnees (v0, d0, d1, · · · ) et (v0, d0, d1, · · · ) telles quev, v ∈ Bs

p,q, on a

‖v − v‖Bsp,q

<∼ ‖v0 − v0‖ℓp + ‖(2(s−1/p)j‖dj − dj‖ℓp)j≥0‖ℓq (10)

pour 0 < s < −log(ρp(S1))

log 2 + 1p et sous la condition que le membre de droite soit fini.

L’estimation (10) est importante pour la comprehension des proprietes de precision de l’operateur

12

non-lineaire d’approximation ; cette inegalite donne plus d’informations que (8). Il s’agit des premiersresultats de stabilite pour les representations multi-echelles non-lineaires qui permettent le controlede l’erreur.

Dans le meme cadre, apres la these je me suis interesse au developpement d’un nouveau modele derepresentations multi-echelles non-lineaires. Dans des nombreuses applications, l’operateur de predictionnon-lineaire peut etre vu comme une version perturbee de l’operateur de prediction lineaire.

Article : A New Formalism for Nonlinear and Non-Separable Multiscale Representations, en colla-boration avec Sylvain Meignen, a parraıtre dans Numerical Algorithms. Ce resultat a ete obtenu apresla these.

Nous avons considere dans ce travail que la perturbation a un caractere lipschitzien. Cela nous apermis l’obtention des theoremes directes et inverses. Nous avons egalement prouve la caracterisationdes espaces de Besov.

I.3 Analyse des proprietes des schemas de subdivision quasi-

lineaires

Article : On the smoothness and stability of quasilinear subdivision schemes with application toENO interpolation, en collaboration avec Albert Cohen et Nira Dyn, paru dans Applied Computatio-nal Harmonical Analysis, sept. 2003. Ce resultat a ete obtenu pendant ma these.

Dans cet article on etudie des schemas de subdivision quasi-lineaires. Les schemas de subdivisioncorrespondent a l’iteration successive d’un operateur d’approximation a partir d’echelles grossieresvers des echelles de plus en plus fines. Les questions qui se posent naturellement sont : (a) un telschema converge-t-il vers une fonction limite ? et (b) quelles sont les proprietes de la fonction limite ?

Cette etude (convergence et regularite de la fonction limite) a fait l’objet de recherches actives,mais tous les travaux existant se situent dans le cadre ou l’operateur d’approximation est lineaire([9], [16], [17], [18], [19]). Une application classique des schemas de subdivision est la generation descourbes et surfaces regulieres dans la CAO. Je montre dans la figure (3) les fonctions limites dans lescas lineaire et non-lineaire pour les schemas d’intepolation a 4-points.

-0.5

0

0.5

1

1.5

-3 -2 -1 0 1 2 3

Fonction limite BW

-0.5

0

0.5

1

1.5

-3 -2 -1 0 1 2 3

Fonction limite ENO+SR

Fig. 3 – Fonctions limite cas lineaire et non-lineaire

Nos algorithmes de subdivision sont non-lineaires. Notre apport a ete l’introduction des outilsnecessaires a l’analyse de la convergence et de la regularite de la fonction limite dans le contextenon-lineaire.

13

Les proprietes de convergence, de regularite et de stabilite de la fonction limite, pour des algo-rithmes de subdivision non-lineaires, sont analysees a travers la contractivite de S1.

Theoreme de convergence et regulariteOn suppose que S reproduit les constantes et verifie ρp(S1) < 21/p. Alors le schema de subdivisionassocie est Lp-convergent. De plus, si v0 ∈ ℓp, la fonction limite v appartient a Bs

p,q pour tout 0 <

s < −log(ρp(S1))

log 2 + 1p , et

‖v‖Bsp,q

<∼ ‖v0‖ℓp . (11)

Theoreme de stabiliteSous les memes hypotheses, et si le schema depend continument des donnees, alors pour toutes v0, v0 ∈ℓp,

‖v − v‖Bsp,q

<∼ ‖v0 − v0‖ℓp . (12)

On note que (12) n’est pas la consequence directe de (11). Mentionnons enfin que ce cadre general detravail a deja ete repris par d’autres chercheurs (comme P. Oswald de l’Universite de Bremen, [47] et[48]) pour l’etude d’autres schemas de subdivision.

Toujours dans ce domaine je me suis interesse aux proprietes de convergence et de stabilite desschemas de subdivision multidimensionnelles et non-separables. Cette analyse s’avere cruciale dans lesapplications an traitement de l’image ou un traitement anisotrope des contours s’impose. Les resultatsobtenus ont ete publies dans :

Article : Smoothness of non-linear and non-separable subdivision schemes. en collaboration avecSylvain Meignen et Anastasia Zakharova, paru dans Asymptotic Analysis.

I.4 Homogeneisation et representations multi-echelles

Article : Homogenization and non-linear multiscale representations : A case study. Ce resultat a eteobtenu apres ma these et fait l’objet d’une prepublication et d’un article publie dans le volume “NewTrends in Continuum Mechanics”, Constanta, Septembre 2003.

Le but de ce travail est la simulation de l’ecoulement respiratoire dans l’arbre bronchique. L’aspectde la hierarchie de bifurcations de l’arbre bronchique evoque une repetition avec variation d’echelles.Si l’on veut decrire ses proprietes, on peut le faire a une echelle locale, en prenant en considerationchaque composante. Mais en pratique, il est beaucoup plus interessant de caracteriser cet arbre aune echelle globale, surtout si on a un tres grand nombre de composantes. On veut ainsi donnerun comportement global de l’arbre en negligeant les fluctuations dues aux heterogeneites. Ceci estprecisement le but de la theorie de l’homogeneisation : on remplace l’objet physique oscillant par unobjet “virtuel” non-oscillant dont les caracteristiques sont voisines du premier.

Les bases d’ondelettes ont ete utilisees dans le probleme d’homogeneisation dans le cas unidimen-sionnel par Beylkin, Dorobantu et Enquist. Une extension dans le cas bidimensionnel a ete recemmentobtenue dans les travaux de Capdebosq et Vogelius. L’interet de l’utilisation des representations multi-echelles non-lineaires pour l’homogeneisation est justifie par les faits suivants :

– la solution de l’equation homogeneisee est la moyenne L2 de la solution a l’echelle fine ;– l’operateur homogeneise herite des proprietes de l’operateur original, telle que l’ellipticite ;– un algorithme rapide qui decompose une fonction dans une partie reguliere et une partie oscil-

lante.

14

Le but de mon travail a ete de trouver et de verifier numeriquement la forme de l’operateurhomogeneise. J’ai obtenu que cet operateur peut etre approche de facon precise par un operateurlineaire, calcule a l’aide des differences finies.

Un autre interet des representations multi-echelles non-lineaires vient du fait qu’elles permettent untraitement adapte des singularites, appliquees a l’homogeneisation elles seront utiles dans le traitementdes problemes anisotropes.

I.5 Algorithmes adaptatifs pour la compression et le debruitage

Article : Denoising using non-linear multiscale representations, accepte dans Note aux ComptesRendus a l’Academie des Sciences, 2004. et Representations multi-echelles non-lineaires et la com-pression progressive, accepte dans Note aux Comptes Rendus a l’Academie des Sciences, 2004. Cesresultats ont ete obtenus pendant ma these.

Ces resultats concernent le developpement d’algorithmes adaptes aux representations non-lineaires.J’ai introduit un codeur adapte aux representations ENO-EA. Ce codeur tire parti des depen-dances statistiques des coefficients multi-echelles numeriquement significatifs associes aux contours.Dans le cas de la representation non-lineaire ENO-EA, nous avons constate que les approximationsdes contours geometriques sont precises meme si l’on n’utilise que l’information provenant des echellesgrossieres, et que les details associes a ces contours sont plus petits que dans les decompositions enondelettes.

Les resultats numeriques pour la compression de l’image reelle “les poivrons”, sont presentes surla figure 4, pour un debit moyen fixe a 0.25 bpp. Le choix de la representation EA contribue a unelegere amelioration visuelle en terme d’elimination des oscillations au voisinage des contours. Il est

Fig. 4 – Compression avec les algorithmes EBCOT-BW (PSNR 27.19) et EBCOT-EA (PSNR 26.21)

interessant d’examiner de plus pres la reconstruction des contours dans les resultats numeriques quenous avons presentes. Dans le cas du detail de l’image presente sur la figure 5 (a), la zone de flous’etale sur environ 6 pixels. La figure 5 (b) illustre le detail des images reconstruites et nous montreque la methode EA a tendance a reconstruire un contour “net”.

En ce qui concerne le debruitage, on peut chercher a utiliser au mieux les proprietes de l’approxi-mation non-lineaire. Cette approximation est concue de maniere a etre precise aux basses echellespour des fonctions regulieres par morceaux, les details aux echelles fines n’apportant plus d’informa-tion fondamentale pour la reconstruction. Elle suggere de facon naturelle une strategie modifiee de

15

Fig. 5 – (a) Contour et (b) Compression avec BW et EA

seuillage qui consiste a ignorer toute la descendance multi-echelle d’un coefficient lorsque celui-ci a eteobtenu par l’approximation non-lineaire.

La figure 6 illustre l’efficacite de cette approche pour un signal regulier par morceaux avec unbruit eleve de variance σ2 = 2. Les details conserves sont en nombre tres faible, ce qui permet dereduire tres fortement l’effet du bruit, tout en assurant une excellente reconstruction du signal gracea la procedure ENO-SR.

-20

-15

-10

-5

0

5

10

15

20

0 500 1000 1500 2000

sinestep+bruit (niveau=2)

-20

-15

-10

-5

0

5

10

15

20

0 500 1000 1500 2000

sinestep

-15

-10

-5

0

5

10

15

0 500 1000 1500 2000

Fig. 6 – Signal bruite et signal debruite en utilisant le seuillage invariant par translation dans unerepresentation en ondelettes (PSNR=41.78) et une strategie adaptative de seuillage (PSNR=45.87)

Au vu de nos experiences numeriques, on peut affirmer que les representations non-lineaires ap-portent des ameliorations significatives au debruitage dans au moins une situation : le debruitage desfonctions regulieres par morceaux en utilisant une procedure modifiee de seuillage dans la representationENO-SR. En revanche, les effets du bruit sur la detection des singularites dans les operateurs d’ap-proximation non-lineaire sont particulierement difficiles a apprehender.

I.6 Methodes variationnelles dans le traitement de l’image

Representations compactes des images par transformee multi-echelle non-

lineaires

Article : Compact representations of images by edge adapted multiscale transforms, en collaborationavec Albert Cohen paru et presente a la IEEE-ICIP Conference, Thessalonique (2001). Ce resultat aete obtenu pendant ma these.

16

Nous nous sommes interesses a une deuxieme approche pour les representations multi-echelles non-lineaires, fondee sur la detection des contours et l’obtention des parametres des contours par la mini-misation d’une fonctionnelle dependant continument des donnees. Nous avons prouve l’existence d’unminimum, mais pas son unicite. Ensuite, on utilise une reconstruction bidimensionnelle polynomialepar morceaux. Les problemes d’unicite du minimum et des proprietes d’approximation de l’operateurd’approximation ainsi construit sont des questions sur lesquelles nous travaillons actuellement.

La compression simultanee des contours et de la texture

Article : Edge and texture compression en collaboration avec Jean-Francois Aujol. Ce resultat a eteobtenu apres ma these et fait l’objet de deux prepublications et un papier a ete soumis pour publica-tion dans IEEE Image Processing, 2003.

Nous construisons un algorithme de compression d’images qui prend en compte la geometrie del’image tout en etant capable d’etre performant sur des images contenant a la fois des structures et dela texture. Pour cela, nous utilisons un algorithme de decomposition d’image recemment introduit parJ.F. Aujol. Cet algorithme permet de separer une image en deux composantes, une premiere contenantl’information geometrique de l’image, et une deuxieme contenant les elements oscillants de l’image.La decomposition se fait a l’aide du probleme de minimisation suivant :

inf|u|BV + α‖v‖G, f = u+ v, u ∈ BV (Ω), v ∈ G(Ω), (13)

L’espace G(Ω) contient les signaux ayant de grandes oscillations, en particulier la texture et le bruit.L’idee de notre methode de compression est la suivante : nous commencons par decomposer l’image

Fig. 7 – Compression en utilisant BW (L2 erreur : 9.96) et ENO-EA (L2 erreur : 9.14 )

a compresser en sa partie geometrique et sa partie oscillante. Nous effectuons ensuite la compressionde la partie geometrique a l’aide de l’algorithme adapte aux contours ENO-EA et pour la partieoscillante, nous utilisons l’algorithme classique de compression par ondelettes biorthogonales. Lesresultats obtenus montrent que les representations non-lineaires adaptees aux contours apportent desameliorations substantielles pour la compression des images (voir figure 7), tant du point de vue visuelque de celui du PSNR.

17

I.7 Une application

Dans cette section nous presentons de nouveaux algorithmes de detection de contours. Leurs mo-tivation vient des developpements recents dans le domaine des techniques de reconstruction adapteesaux contours [3]. Ce qui constitue la particularite de ces algorithmes est qu’ils sont bases sur la compa-raison des quantites locales plutot que sur le filtrage et le seuillage. D’une autre part, leur nouveauteconsiste dans l’invariabilite du processus de comparaison par rapport aux changements de l’illumina-tion de l’image. Par l’utilisation de cette propriete nous assurons des algorithmes de detection de bordinsensibles aux changements dans l’illumination.

La detection des contours est un processus essentiel dans l’analyse d’image avec de nombreusesapplications. Une variete de detecteurs de contours a ete proposee dans la litterature de specialite,y compris des methodes classiques comme les algorithmes de Prewitt et Sobel , aussi bien que desalgorithmes un peu plus sophistiques, comme ceux introduits par Canny et Marr-Hildreth . Differentesapproches fondees sur les bases d’ondelettes ont ete proposees. Par exemple, Mallat et Zhong ontpresente un detecteur des contours multiresolutions base sur la transformee en ondelettes. Tous cesdetecteurs sont bases dans une certaine mesure sur la reponse de l’image des lors qu’on lui appliqueun systeme plus ou moins sophistique de filtrage lineaire ou non-lineaire. Ces algorithmes impliquentd’ordinaire un parametre cache, un seuil. La detection des contours a son tour n’est generalement pasinvariable en ce qui concerne une variation de l’intensite lumineuse qui pourrait arriver au niveau localou global dans l’image.

Sans entrer dans les details, nous esquissons l’algorithme de detection de contours utilise dans [3].Celui-ci peut essentiellement etre divise en deux parties. Dans un premier lieu l’on detecte et marqueles cellules qui contiennent les contours de l’image. Ensuite nous entrons dans un processus de selectiondes cellules qui mene en fin de compte a la construction des deux fonctions polynomiales, basees surdes stencils qui ne croisent pas les contours. C’est une question fondamentale pour assurer par la suitel’exactitude et les proprietes d’approximation. Dans ce qui suit, nous presenterons une serie de testsnumeriques visant a demontrer la robustesse de la procedure proposee. A cette fin, nous consideronsles images tests sur l’image 8. L’image 8-(a) est purement geometrique et du bruit blanc a ete ajoutepour simuler la texture. L’image 8-(d), celle des poivrons, ”peppers”, est une image reelle dont lescaracteristiques dominantes sont les contours. Nous montrons sur l’image 8 - (b) et 8 - (e) les cellulesmauvaises. Comme attendu, apres ces deux etapes, tous les bords reels sont correctement detectes, maison constate aussi la presence ”de fausses alarmes”. L’image 8 - (c) et 8 - (f) confirment que la plupartde ces ”fausses alarmes” persistent. Dans [1] nous avons propose une variante de l’algorithme visanta reduire le nombre de fausses alarmes detectees .. Nous avons concu un nouveau test afin d’eviter ouau moins de reduire considerablement la detection de fausses alertes pour ameliorer l’efficacite.

Dans une premiere partie des tests numeriques nous utiliserons l’image geometrique bruitee montreesur l’image 8-(a), pour motiver les modifications et presenter les resultats des nouveaux mecanismesde detection de bord. Dans une deuxieme partie nous presenterons les tests numeriques en utilisantl’image peppers.

Sur l’image 9 nous presentons les resultats de cette strategie. Nous observons que tous les contoursreels ont ete correctement detectes, en reduisant au minimum le nombre de fausses alarmes. En ce quiconcerne les images reelles nous montrons sur la figure 10 le resultat final de la detection avec cettestrategie. Le lecteur interesse peut trouver dans [1] une description complete de plusieurs strategies dedetection de contours qui sont insensibles aux changements de l’illumination a l’interieur de l’image.

Nous avons presente un nouvel algorithme de detection de contour. Pour des images “regulieres”,les proprietes de detection de contours de ce nouveau type d’algorithme sont comparables avec cellesdes autres detecteurs de contours standard. En revanche des lors que les images ont trop de lumiere oubien sont assez sombres, nos algorithmes surpassent les algorithmes classiques. Concentrons-nous surla raison pour laquelle notre algorithme est insensible aux changements d’illumination. L’observation

18

Fig. 8 – Images tests et resultats des detections

Fig. 9 – Image tests geometrique et resultats des detections

19

Fig. 10 – Image peppers et resultats des detections

cle consiste en ce qu’il est uniquement base sur la comparaison des quantites par la detection etla procedure de selection ENO-EA, plutot que sur un filtrage et/ou un seuillage. Le processus decomparaison est invariable en multipliant l’image par une valeur constante ou en ajoutant une valeurconstante. Comme la methode est aussi locale, cette invariance est toujours valable si nous ajoutonset/ ou multiplions l’image localement avec des fonctions de changement lentes, puisque celles-ci sontlocalement proches d’une constante. Les experiences numeriques revelent que les nouveaux detecteursde bord possedent toutes les caracteristiques attendues pour construire des representations multi-echelles adaptees aux contours.

Ils peuvent aussi etre utilises dans le zoom anisotrope, afin d’attenuer les effets d’escalier qui sontobserves en utilisant les methodes d’approximation basees sur le produit tensoriel.

Les resultats obtenus dans la construction, l’analyse des methodes multi-echelles non-lineairesme semblent tres importants quant a leurs applications ou l’adaptativite joue un role crucial. Dansl’avenir proche je souhaite utiliser ces methodes non-lineaires pour la compression et le debruitagedans le traitement d’images.

II. Compressed Sensing

L’approche traditionnelle pour la reconstruction des signaux ou des images a partir de donneesmesurees suit le theoreme connu de Shannon, qui precise que la frequence d’echantillonnage doit etreegale a deux fois la plus grande frequence contenue dans le spectre. Dans le meme esprit, le theoremefondamental de l’algebre lineaire implique que le nombre des donnees mesurees sur un signal discret etde dimension finie doit etre au moins egal a sa longueur afin d’assurer la reconstruction. Ce principeregit toute la technologie moderne telle que la numerisation des signaux audio ou video. Le paradigmedu “compressed sensing” vient ecraser ce principe en fournissant une approche fondamentalementnouvelle pour l’acquisition ou la numerisation des donnees. L’approche proposee par le “compressedsensing”, permet tout simplement la reconstruction exacte (sic !) des signaux ou des images a partir dedonnees mesurees, mais incompletes en nombre, ceci a condition que le signal soit “parcimonieux” . Sil’on pense que l’approche initiale, basee sur la theorie de Shannon, considerait la reconstruction exactea partir des donnees incompletes comme impossible, l’essor du domaine “compressed sensing” ne faitaucun doute et il serait judicieux de preciser que le developpement de ses aspects fondamentaux

20

theoriques et algorithmiques constitue aujourd’hui un sujet central de la recherche scientifique. Ilest bien connu que l’etude de l’echantillonnage d’une image sur un reseau base sur le theoreme deShannon-Nyquist est loin de donner une reponse complete au probleme, surtout en vue des applicationspratiques ou les donnees peuvent etre manquantes ou bruitees. Pour cette raison, je me suis interesseaux problemes precises ci-dessous, qui admettent des solutions differentes ayant toutefois un pointcommun, a savoir, la notion de quasicristal. Pour la construction des quasicristaux, on utilise lamethode - “coupe et projection ” due a Yves Meyer.

Definition 1. Reseau et reseau dual Soit A une matrice inversible. Soit le reseau Γ = AZN+M ⊂

RN × R

M = RN+M (sous-groupe de R

N+M). On note p1 et p2 les deux projections canoniques. Onsuppose que p1 Γ et p2 Γ sont injectives. On suppose que p1(Γ) est dense en R

N et p2(Γ) est dense enR

M .Le reseau dual de Γ ⊂ R

N est note Γ∗ et il est defini par

Γ∗ = γ∗ ∈ RN ; γ∗ · γ ∈ Z , γ ∈ Γ.

Definition 2. Quasicristal Soit Q ⊂ RM un ensemble compact. Alors le quasicristal ΛQ ⊂ R

N estdefini par

ΛQ = p1(γ); γ ∈ Γ, p2(γ) ∈ Q.

Un quasicristal est simple si M = 1 et Q = I : ΛI = p1(γ); γ ∈ Γ, p2(γ) ∈ I.

Le but etant donc de reconstruire d’une maniere exacte un signal ou une image quand les conditionsde Shannon ne sont pas satisfaites. Il s’agit d’un probleme inverse mal pose et il est indispensabled’ajouter une connaissance a priori sur le spectre pour pouvoir y repondre. Plus precisement, onutilisera le fait que le support S de la transformee de Fourier de f est petit en mesure, n’occupe que peude place sur l’axe ou le plan des frequences. Autrement dit on doit adapter l’ensemble d’echantillonnagea la geometrie du spectre. Cela est crucial dans certaines applications. Un exemple est le satelliteSPOT5 est construit par le CNES (B. Rouge). La transformee de Fourier de l’image acquise estnulle hors de K ⊂ Mr = (ξ1, ξ2); |ξ1| + |ξ2| ≤ r ou r est determine par l’optique. En faisant leminimum de mesures, le CNES souhaite tirer le maximum d’information. Le probleme est d’adapterl’echantillonnage a la geometrie de K.

Trois problemes

Pour fixer les idees, soit K un compact de RN . Si f ∈ L2(RN ) et si sa transformee de Fourier f

est portee par K nous ecrirons f ∈ EK . Les problemes auxquels je me suis interesse sont :– Probleme A. Le compact K ⊂ R

n est donne et l’on cherche a echantillonner de la facon la pluseconomique possible les fonctions f ∈ EK . Il s’agit donc de faire le moins possible de mesurespour recuperer f . En d’autres termes, on veut que la densite d’echantillonnage soit minimale.

– Probleme B. L’ensemble Λ ⊂ Rn est donne et l’on cherche a savoir si Λ peut etre utilise pour

echantillonner toutes les fonctions de tous les espaces EK . sous la seule condition que la mesuredu compact K soit inferieure a densΛ. On dira alors que Λ est un ensemble d’echantillonnageuniversel.

– Probleme C. L’ensemble Λ ⊂ Rn est donne tandis que K et f ∈ EK sont inconnus. L’ensemble

K est inconnu, mais de petite mesure. On veut retrouver f et K a partir des donnees a(λ) =f(λ), λ ∈ Λ. Cela revient a recontruire une fonction inconnue F, portee par un ensemble inconnumais de petite mesure, a l’aide de quelques coefficients de Fourier

Nous verrons que ces trois problemes differents admettent des solutions differentes.

21

Probleme A

Soit la fonction f ∈ EK . Les questions que l’on se pose naturellement sont :– 1 : Est-elle completement determinee par ses echantillons sur Λ ?– 2 : La reconstruction est-elle unique ?

La reponse a la premiere question est affirmative si Λ ⊂ RN est un ensemble d’echantillonnage stable.

Cette notion a ete introduite par H.J. Landau.

Definition 3. Un ensemble Λ ⊂ RN est un ensemble d’echantillonnage stable pour EK s’il existe une

constante C > 0 telle que

‖f‖22 ≤ C

∑

λ∈Λ

|f(λ)|2,

pour toute f ∈ EK .

La reponse a la deuxieme question est egalement affirmative si Λ ⊂ RN est un ensemble d’echantillonnage

stable et aussi d’interpolation stable pour EK . A nouveau cette notion a ete introduite par H.J. Lan-dau.

Definition 4. Soit K ⊂ RN un ensemble borelien. Nous disons que Λ est un ensemble d’interpolation

stable pour EK si pour chaque (a(λ))λ∈Λ ∈ ℓ2(Λ) il existe un f ∈ EK tels que f(λ) = a(λ), λ ∈ Λ.

H.J. Landau a aussi etabli des conditions necessaires pour l’echantillonnage et l’interpolation, quicomparent la densite superieure ou inferieure de Λ a la mesure de K.

Theoreme de Landau

– Si Λ est un ensemble d’echantillonnage stable pour EK , alors

densΛ ≥ |K|.

– Si Λ est un ensemble d’interpolation stable pour EK , alors

densΛ ≤ |K|.

On a designe par |E| la mesure de Lebesgue de l’ensemble borelien E ⊂ RN . La densite d’un ensemble

de points Λ ⊂ RN est definie comme suit. Soient Bx,R la boule centree a x de rayon R, cn l’inverse

du volume de la boule d’unite et #E la cardinalite de E.Densite superieure de Λest definie par :

densΛ = limR→∞cnR−n sup

x∈RN

#Λ ∩Bx,R

Densite inferieure de Λest definie par :

densΛ = limR→∞cnR−n inf

x∈RN#Λ ∩Bx,R

On dit qu’un ensemble Λ de points a une densite uniforme (note par dens Λ) si la densite superieureet la densite inferieure de Λ coıncident.

Dans le cadre d’un travail en collaboration avec Yves Meyer, j’ai etabli le theoreme suivant, quirepond d’une maniere optimale au probleme A.

Theoreme APour tout compact K ⊂ R

n et tout ε positif, il existe un reseau Γ ⊂ Rn et un ensemble fini F ⊂ R

n

tels que l’ensemble Λ = Γ + F ait les deux proprietes suivantes :

22

– (a) la densite de Λ est inferieure a |K| + ε– (b) Λ est un ensemble d’echantillonnage stable pour EK .

Notons que la borne |K| + ε est donnee par le theoreme de Landau et donc le theoreme est doncoptimal. Dans ce cadre l’ensemble compact K est donne et que l’on souhaite construire un reseauΛ de densite minimale, ensemble d’echantillonnage stable pour EK . Cela revient a faire le moins demesures possibles ou equivalent revient a trouver les pavages du plan ou de l’espace les plus densespossibles par des translates de K. Ainsi, si n = 2 et K est un disque de centre 0 et de rayon R.Soit f ∈ EK . En utilisant un l’echantillonnage regulier sur un reseau on a que le reseau hexagonal de

densite√

32π2R

2 est optimal. En utilisant un l’echantillonnage irregulier a l’aide d’un quasicristal fournipar le theoreme A on peut descendre jusqu’a une densite 1

4πR2. Cela est la densite optimale donnee

par le theoreme de Landau. La demonstration du resultat se trouve dans Simple quasicrystals are setsof stable sampling, Complex Var. Elliptic. Equ. 55 (2010), 947-964.

Probleme B :

Des le depart, je mentionne deux resultats negatifs : le premier du a A. Olevskii et A. Ulanovskiimontre qu’un reseau n’est pas un ensemble d’echantillonnage universel. Le deuxieme du a R. Bass et K.Groechenig montre que l’echantillonnage aleatoire ne fournit pas un ensemble d’echantillonnage uni-versel. En utilisant les quasicristaux simples, j’ai demontre le resultat suivant qui repond completementau probleme B.

Theoreme BSoit Λ ⊂ R

N un quasicristal simple et soit K ⊂ RN un ensemble compact. Alors

(a) |K| < densΛ implique que Λ est un ensemble d’echantillonnage stable pour EK .(b) si K est Riemann integrable, alors |K| > densΛ implique que Λ est un ensemble d’interpolation

stable pour EK .Ce theoreme a ete demontre dans : Quasicrystals are sets of stable sampling, C. R. Acad. Sci.

Paris, Ser. I,vol. 346, pp. 1235-1238, 2008.

Probleme C

La reponse du probleme a ete donnee dans A variant of compressed sensing, Rev. Mat. Iberoame-ricana Volume 25, pp. 669-692, (2009).

Peut-on reconstruire f sans connaıtre completement son spectre ? La reponse est affirmative !Le “compressed sensing” d’Emmanuel Candes nous montre la voie. Au debut de leurs recherches,Candes, Romberg et Tao se sont interesses au probleme tomographique classique en imagerie medicale :reconstruire une image a partir de la connaissance de sa transformee de Fourier sur un domaine etoileΩ.

L’image tres simple f qui sert a faire le test est un ensemble des zones delimitees par des contours,voir la figure 11 (a). L’eclairement est constant a l’interieur de chaque zone. L’IRM fournit la trans-formee de Fourier de f sur un ensemble S de 22 lignes, voir la figure 11 (b).

Bien que l’on ne dispose que de peu de donnees (de l’ordre de 2 % du necessaire), la techniquedu “compressed sensing” permet de retrouver exactement ladite image. La premiere approche pour lareconstruction de l’image, dite classique, est basee sur la minimisation de la norme L2 du gradient def . Le resultat de cette approche est montre sur la figure 12 (a). L’approche “compressed sensing” estbasee sur la minimisation de la variation totale de l’image qui est egale a la norme L1 du gradient del’image f . Le resultat en utilisant l’approche nouvelle du “compressed sensing” est montre sur la figure

23

Fig. 11 – (a) Image originale et (b) 22 lignes de sa transformee de Fourier

Fig. 12 – Reconstruction par minimisation (a) ‖∇f‖L2 et (b) ‖∇f‖L1

12 (b). Nous pouvons constater que l’approche classique ne permet pas une bonne reconstruction del’image de depart, alors que l’approche “compressed sensing” reconstruit exactement l’image initiale.

Toujours en collaboration avec Yves Meyer, j’ai propose une version continue du ”compressed sen-sing” en utilisant les quasicristaux. On cherche donc a recontruire une fonction F = f , portee par unensemble de petite mesure, a l’aide de quelques-uns de ses coefficients de Fourier. Pour fixer les idees,soit un parametre β ∈ (0, 1/2) et Mβ = f ∈ L2(RN ); support f ⊂ K ⊂ R

N , |K| < β. L’ensemblecompact K depend de f . Notons que Mβ n’est pas un espace lineaire. En effet si, f, g ∈ Mβ, alorsf + g ∈ M2β . Le theoreme principal que j’ai obtenu est le suivant :

Theoreme CSoit Λ un quasicristal symetrique simple de densite d.

(a) soit f ∈ Mβ avec β < d/2 et F = f ≥ 0. Alors si une fonction g ∈ L2(RN ) satisfait g ≥ 0 etg(λ) = f(λ), λ ∈ Λ, alors g = f.

(b) soit f ∈ Mβ avec β < d/2 et F = f ≥ 0. Alors F est la solution unique u du problemevariationnel suivant :

inf‖u‖1;u ∈ L1(RN ), u(λ) = F (λ), λ ∈ Λ.

Notons que dans (a) nous ne supposons pas g ∈ Mβ , que dans (b) il n’y a pas de restriction sur lesigne de u et que dans (b) nous ne supposons pas non plus u ∈ Mβ. Nous avons aussi prouve que cetheoreme est optimal.

Les resultats obtenus dans le domaine du ”compressed sensing” ouvrent des nouvelles voies derecherches tant du point de vue theorique que du point de vue des applications. Il me semble importantde noter que les algorithmes de compression embarques sur la mission Herschel lancee en mai 2010,utilisent une version du ”compressed sensing”. L’approche que je propose, en collaboration avec Yves

24

Meyer, sur le compressed sensing, est essentiellement deterministe et continue. Il reste a en comprendrel’utilisation dans des applications concretes, ce qui constitue une priorite dans mon projet de recherche.

7 Communications Orales.

– Novembre 2010 : Seminaire Image LAGA-L2TI-LIPN :Probleme de l’echantillonnage stable : contre-exemple.

– Octobre 2010 : Seminaire Quasicristaux CreteilUn contre-exemple dans le probleme d’echatillonnage.

– Novembre 2009 : Seminaire Journees SMAI–AFAApproximation et Modelisation Geometrique – Marseille Empirical Modal Decomposition.

– Janvier 2009 : Seminaire au LJK–Grenoble :Resultats theoriques sur une variante du compressed sensing.

– Novembre 2008 : Seminaire Journees SMAI–AFA Approximation et Modelisation GeometriqueResultats theoriques sur une variante du compressed sensing.

– Janvier 2005 : Seminaire au CMAP–Ecole Polytechnique :Resultats theoriques sur les methodes geometriques d’approximation des images.

– Janvier 2005 : Seminaire d’Analyse Appliquee LAGA :Resultats theoriques sur les methodes ENO.

– Novembre 2004 : Workshop “Contenu Informatif des Images Numeriques”Multiresolution Adaptee aux Contours.

– Avril 2004 : Seminaire ENSPS Universite L. Pasteur StrasbourgApproximation et Modelisation Geometrique des Images

– Janvier 2004 :Seminaire IPGM AachenOptimal Compression Algorithms using Nonlinear Multiresolution Representations.

– Septembre 2003 : Conference Internationale : New Trends Continuum MechanicsNonlinear Multiscale Methods and theirs applications to homogenization, Constanta (Roumanie),Septembre 2003.

– Mars 2003 : Seminaire Journees SMAI–AFA Approximation et Modelisation Geometrique – Aix-en–Provence : Multiresolution Adaptee aux Contours et Compression des images geometriques

– Fevrier 2003 : Seminaire de l’equipe MOSAIC de l’INPG – Grenoble :Methodes multiresolutions non-lineaires – Applications.

– Mars 2002 : Seminaire Image au Laboratoire Jacques-Louis Lions, Paris–VI :Methodes multiresolution adaptees aux contours.

– Janvier 2002 : Seminaire au CMAP–Ecole Polytechnique :Resultats theoriques sur les methodes multi-resolution non-lineaires.

– Octobre 2001 : Seminaire a la Conference Internationale IEEE, Thessaloniki (Grece) :Compact representations of images by edge adapted multiscale transforms.

– Juillet 2000 : Seminaire a la “International Summer School : Wavelets and Applications”, Va-lencia (Espagne) : Stability in Nonlinear Subdivision Schemes–Applications to image processing.

– Fevrier 2000 : Seminaire a l’Universite de Tel-Aviv (Israel) : Convergence and Stability for ENOschemes.

8 Participations a des Colloques.

– Juillet 2010 : Curves et Surfaces Avignon : Convergence des Algorithmes de Subdivision Non-lineaires et Non-separable.

25

– Novembre 2009 : Journees SMAI AFA Marseille : Methodes adaptees aux contours.– Juillet–Aout 2002 : CEMRACS 2002 : Projet – Methodes adaptees aux contours.– Aout 2001 : “International Summer School : Multiresolution in Geometric Modelling”,

Munchen, Allemagne.– Juillet 2000 : “Multiscale Approaches in the Numerical Solution of P.D.E ”, Valencia, Espagne.– Juillet 1998 : “International Summer School : Wavelets and Applications”, Orsay, France.

Stages de recherche

– Fevrier 1998–Septembre 1998 Stage de recherche a la CISI.Sujet : Compression video en utilisant les bases d’ondelettes. Application a la video–surveillance.

– Octobre –Decembre 1998 Semestre IHP – Methodes Mathematiques dans le traitement del’image.

– Fevrier–Juin 1997 : Admis sur concours au programme europeen de bourses TEMPUS.Laboratoire Jacques–Louis Lions. Stage de DEA supervise par Albert Cohen.Sujet : Resolution numerique du bi-laplacien par une methode d’ondelettes interpolantes.

– 1996 : Stage de fin d’etudes a la Faculte de Mathematiques de Bucarest.Sujet : Resultats sur la decomposition en valeurs singulieres : Traitement stochastique de donnees.

9 Perspectives

Compression et debruitage d’images

Dans [38], nous avons montre dans un premier temps des resultats de convergence et de stabilitequi portent principalement sur des operateurs de subdivision reproduisant exactement les polynomes.Nous avons ensuite montre des preuves de stabilite pour des representations multi- echelles se fondantsur des operateurs de subdivision qui ne reproduisent pas exactement les polynomes. Les applica-tions naturelles de ce type de representations multi-echelles concernent principalement la compressiond’images pour laquelle les representations non-interpolantes (de type cell-average) sont reputees plusperformantes. Cependant il n’existe pas, a ma connaissance, de representations de ce type qui soientstables et convergentes en meme temps qu’efficaces pour la compression. Nous souhaitons travaillerdans cette direction dans un proche avenir. Une autre perspective dans ce domaine consisterait a chan-ger l’ordre d’approximation des schemas de subdivision au voisinage des singularites. Par exemple, sil’on considere le schema PPH, au niveau des singularites la prediction s’effectue a l’aide d’un polynomede degre 1, alors que l’ordre d’approximation est polynomial de degre 3 loin des singularites. Danscette derniere approche, l’etude de la stabilite est reliee a une strategie dite de ”controle de l’erreur”(en considerant que les perturbations pouvant rendre la representation instable proviennent unique-ment des erreurs de quantification) qui semble trop reductrice. Par ailleurs, l’operateur de subdivisionpour les images est toujours obtenu par produit tensoriel d’un operateur uni-dimensionnel. Nous pen-sons donc qu’il existe une ouverture d’un champ de recherche particulierement riche pour construiredes representations multi-echelles qui soient non separables, stables et convergentes, tout en etantpertinentes pour la compression d’image. Notre travail actuel se focalise dans cette direction. Nousmentionnons que nos premiers resultats sur le debruitage sont deja en voie de parution. Pour illustrertout cela et conclure a la fois, voici quelques uns des premiers resultats dans les figures ci-contre.

26

Fig. 13 – (a)signal original (b) signal bruite

Fig. 14 – (a) comparaison des methodes (b) rapport SNR avant et apres debruitage

Sur la construction des bases de Riesz...

Soit S l’union finie de plusieurs intervalles de R. On suppose qu’il existe deux nombres reels α, βtels que la longueur de chaque intervalle appartienne a Zα + Zβ. En utilisant les quasicristaux, N.Lev a construit dans [26] un ensemble discret Λ ⊂ R tel que le systeme des fonctions exponentiellesexp(2πiλx), λ ∈ Λ soit une base de Riesz de l’espace L2(S). Nous suivons [26] pour la presentation.Soit S l’union finie de plusieurs intervalles bornes de R. On note par PWS (d’apres Paley et Wiener)l’espace de toutes les fonctions f ∈ L2(R) dont la transformee de Fourier definie toujours comme

f(ξ) =

∫

R

f(x) exp(2πixξ)dx,

s’annule presque partout en dehors de S. Un ensemble discret Λ ⊂ R s’appelle ensemble completd’interpolation pour PWS si la restriction de l’operateur f → f |Λ est un operateur borne et inversiblede PWS sur ℓ2(Λ). En termes de theorie de l’information cela veut dire que Λ permet l’echantillonnage“stable et non-redondant” des signaux dont le spectre est inclus dans S. Il est connu que la proprietede l’interpolation complete de Λ est equivalente a la propriete de la base Riesz pour le systemecorrespondant des fonctions exponentielles

E(Λ) = exp(2πiλx), λ ∈ Λ,

dans l’espace L2(S).Notons que si S est un seul intervalle, alors la description complete des bases de Riesz E(Λ) dans

L2(S) est donnee par B.S.Pavlov (1979). Dans le cas ou S est l’union finie de plusieurs intervallesbornes de R, il n’existe pas de caracterisation aussi simple pour la description complete des basesde Riesz E(Λ) dans L2(S). En realite, l’on ignore completement si une base Riesz des fonctions

27

exponentielles existe dans L2(S).En revanche l’existence a ete etablie dans les cas suivants :

1. S est l’union finie de plusieurs intervalles disjoints ayant des longueurs commensurables [7], [51].

2. S est l’union de deux intervalles [59].

Pour d’autres resultats a ce sujet, le lecteur interesse peut trouver un expose complet dans [51]. N.Lev a encore prouve le theoreme suivant [26] :

Theoreme 1. Soit S l’union finie de plusieurs intervalles disjoints de R. On suppose qu’il existe deuxnombres reels α, β tels que la longueur de chaque intervalle appartient a Zα + Zβ. Alors il existe Λdans R tel que E(Λ) est une base de Riesz de L2(S).

Ici Zα+ Zβ represente l’ensemble des nombres reels de forme nα+mβ, (n,m) ∈ Z. Ce resultat esten realite la consequence directe du theoreme suivant :

Theoreme 2. On suppose que la fonction indicatrice d’un ensemble S ⊂ R peut etre ecrite commela combinaison lineaire des fonctions indicatrices des intervalles I1, ..., IN dont les longueurs appar-tiennent a Zα+ Zβ, c’est-a-dire

1S(x) =

N∑

j=1

cj1Ij(x), |Ij | ∈ Zα+ Zβ, (1 ≤ j ≤ N), (14)

ou α, β ∈ R. Alors il existe Λ dans R tel que E(Λ) est une base de Riesz de L2(S).

Les ensembles ayant la structure (14) forment une classe plus grande que la classe des unionsdes intervalles disjonts dont les longueurs appartiennent a Zα+ Zβ. Par exemple, on peut prendre unintervalle avec des “trous”, obtenu par l’elimination des sous-intervalles disjoints, ou autant l’intervalleque ses sous-intervalles ont des longueurs appartenant a a Zα+ Zβ.

La strategie de la demonstration suit de pres nos resultats, en utilisant les “quasicristaux simples”pour construire des ensembles d’interpolation et d’echantillonnage “universels” pour les espaces PWS .L’idee est d’utiliser les “quasicristaux simples” pour la construction des ensembles d’interpolationcomplete pour des spectres S ayant la structure (14).

Plus precisement, soit Γ ⊂ R2 un reseau. On considere les deux projections p1(x, y) = x et

p2(x, y) = y, et on suppose que les restrictions de p1 et p2 a Γ sont injectives. Soit Γ∗ le reseau dual,defini comme l’ensemble de tous les vecteurs γ∗ ∈ R2 tels que (γ, γ∗) ∈ Z pour tout γ ∈ Γ.Soit S l’union disjointe des intervalles demi-fermes,

S =

r⋃

j=1

[aj , bj [, a1 < b1 < ... < ar < br,

etI = [a, b[

un seul intervalle demi-ferme. On definit

Λ(Γ, I) = p1(γ); γ ∈ Γ, p2(γ) ∈ I

etΛ∗(Γ, S) = p2(γ

∗); γ∗ ∈ Γ∗, p2(γ∗) ∈ S

Dans un certain sens, les quasicristaux Λ(Γ, I) et Λ∗(Γ, S) sont duaux. Cette dualite est a la foisobservee et demontree dans nos resultats concernant l’echantillonnage et l’interpolation. On peutreformuler cette dualite dans le contexte des bases de Riesz des fonctions exponentielles de la manieresuivante :

28

Theoreme 3. Les deux proprietes suivantes sont equivalentes :

1. E(Λ(Γ, I)) est une base de Riesz de L2(S).

2. E(Λ∗(Γ∗, S)) est une base de Riesz de L2(I).

Le preuve de ce theoreme nous est entierement due, voir [40]. Nous connaissons donc les basesde Riesz des exponentielles ayant des frequences reelles et les spectres remplissant la condition dio-phantienne (14). Dans le papier [26] l’existence de telles bases de Riesz a ete prouvee sous certainesconditions non-discretes sur la longueur des “gaps” entre les intervalles. D’une part, bien qu’elle consti-tue un important pas en avant, la restriction obtenue par N. Lev demeure assez severe : les resultats de[59] indiquent que les restrictions diophantiennes du type (14) ne sont pas necessairement naturelles.Il devient donc interessant de trouver les conditions naturelles qui assurent l’existence de telles basesde Riesz et cela fait l’objet de notre travail. D’autre part, les resultats de [26] sont unidimensionnelsalors que l’ensemble de nos resultats sont independants de la dimension ; il serait donc necessaire parla suite de se poser le probleme de l’obtention de resultats similaires sur l’existence de bases de Rieszen plusieurs dimensions.

Echantillonnage efficace et decomposition modale empirique

Une autre question naturelle que l’on se pose face a un signal est de savoir comment l’echantillonnerde facon a avoir une reconstruction exacte. On est donc amene a se poser la question suivante : etantdonne le compact K correspondant au support de la transformee de Fourier de s, comment peut-onechantillonner de la maniere la plus efficace possible un signal s appartenant a EK , ensemble desfonctions de L2(Rn) dont la transformee de Fourier est a support dans K. La reponse a ce problemefait appel a la notion d’echantillonnage stable qui correspond a la definition suivante :

Definition 5. Un ensemble Λ ⊂ Rn est un ensemble d’echantillonnage stable pour EK , s’il existe une

constante C telle que, pour tout s ∈ EK , on ait :

‖s‖2 ≤ C∑

λ∈Λ

|s(λ)|2.(15)

Grace a une variante d’un theoreme du a Tao, Matei et Meyer [36] ont montre que l’on pouvaitconstruire des ensembles d’echantillonnage stable de densite minimale pour reconstruire le signal. Ilest important de remarquer que la construction d’un tel ensemble necessite la connaissance du supportK de la transformee de Fourier du signal s et que l’ensemble d’echantillonnage depend de la mesureK. Nos resultats recents [37] montrent que l’on peut toujours trouver un echantillonnage stable Λ (enutilisant la notion de “quasicristal”) tel que la mesure de K soit inferieure a la densite de Λ. Enfin,si l’on cherche a reconstruire un signal, on peut le faire en utilisant des techniques de “compressedsensing”.

La decomposition modale empirique (EMD), introduite pour la premiere fois dans [62], est unedecomposition non -lineaire particulierement efficace pour l’etude des signaux non stationnaires.Brievement, cette decomposition permet le calcul, de maniere adaptative, de modes dk de frequencemoyenne de plus en plus basse lorsque k augmente :

s(t) =

N∑

k=1

dk(t) + r(t),

et ou r est un residu monotone. Les caracteristiques essentielles de cette decomposition sont l’adap-tativite, la bonne separation frequentielle des modes et leur quasi-orthogonalite.

29

Partant d’un signal s, le principe de la decomposition est l’obtention d’un premier mode de ce signalpar le calcul de l’enveloppe moyenne de s puis par sa soustraction a ce dernier, selon le procede :

Φ(s)(t) = s(t) −1

2(s(t) + s(t))(16)

ou s (respectivement s) correspond a l’enveloppe des maxima obtenue par l’interpolation des splinedes maxima (resp. minima), l’enveloppe moyenne de s etant definie comme la moyenne de s et s.

Le premier mode d1 est alors defini par d1(t) = Φn(t), ou le nombre n d’iterations de Φ est fixepar un certain critere d’arret.

L’idee de base de cette decomposition repose sur le fait que les extrema sont caracteristiques dusignal, c’est-a-dire ils forment un echantillonnage stable pour s. Nous nous proposons dans un premiertemps de proceder a l’etude de ce postulat qui conditionne le bon fonctionnement de l’EMD.

Lorsque les extrema du signal s sont proches de ceux du mode d1 que l’on cherche a calculer etque ce dernier est a bande limitee, l’echantillonnage defini par les extrema peut etre vu comme uneperturbation de l’echantillonnage a la frequence de Nyquist. Dans un tel cas, l’on peut a juste titrese demander si l’echantillonnage est stable. A ce propos, nous avons a notre disposition plusieursresultats theoriques, dont le premier, du a Grochenig et Bass [6], montre que si la perturbation estaleatoire et telle que :

tk = kT + rk(17)

avec 1T > 2λc, ou λc est la frequence de Nyquist, et rk sont des variables independantes equireparties

sur [0, T ], alors l’echantillonnage n’est pas stable. Plus recemment, Thakur et Wu [63] ont montre quesi

supk

|tk − kT | <T

2,(18)

alors l’echantillonnage est stable. Il est donc manifeste que pour esperer avoir une reconstructioncorrecte a l’aide d’extrema, ceux-ci doivent correspondre a une perturbation bien controlee de lafrequence de Nyquist.

Cependant, l’interet de l’EMD repose sur le fait qu’elle permet la decomposition de s en signauxdk modules a la fois en amplitude et en frequence, ce qui induit que les extrema de tels modes (et afortiori de s) ne sont pas repartis autour de la frequence de Nyquist. Pour de tels signaux, il n’existepas de resultats theoriques prouvant la stabilite de l’echantillonnage fonde sur les extrema, ce quiconstituera une de nos pistes de recherche. Nous chercherons, en outre, a comprendre pourquoi lesextrema seraient a privilegier pour la definition d’un echantillonnage stable.

Calcul de l’enveloppe moyenne d’un signal et decomposition modale empirique

Un autre probleme qui rejoint celui de l’echantillonnage d’un signal concerne le calcul de sonenveloppe moyenne. L’enveloppe moyenne d’un signal est par definition moins oscillante que le signallui-meme, mais des simulations numeriques montrent que l’approximation de l’enveloppe moyennecalculee comme demi-somme des enveloppes des maxima et des minima proposee dans l’EMD generedes oscillations importantes en presence de bruit. Dans un tel cas, ces oscillations sont responsablesde la production de nombreux modes sans grande signification physique, qui ne sont generalement pasanalyses a la sortie de l’algorithme.

La encore, il serait judicieux de considerer un echantillonnage du signal permettant de definirles enveloppes superieure et inferieure moins oscillante. De nombreuses approches ont ete proposeespour le calcul de l’enveloppe moyenne [61][65], en utilisant des criteres integraux, parmi lesquelles

30

l’enveloppe interpolant les moyennes locales du signal. Ces approches sont, par nature, plus stablesque celles fondees sur l’interpolation des extrema. Neanmoins, ces approches se fondent toujours surdes moyennes locales calculees entre deux extrema du signal, ce qui ne nous semble pas pertinentpour l’objectif fixe, a savoir la definition de l’enveloppe moyenne peu oscillante. Nous etudierons donccomment definir des enveloppes moyennes sans utiliser directement les extrema du signal.

Une autre partie de notre travail dans ce domaine consistera a essayer de mieux comprendre lecomportement de la fonction Φ definie en (16). A titre d’illustration, considerons l’approche par B-spline proposee dans [55] pour representer l’enveloppe moyenne. Si l’on appelle τ les extrema de s, onrecherche l’enveloppe moyenne de s sous la forme (en posant sj = s(τj) :

Vτ,ks =∑

j∈Z

∆k−2sjBj,k,τ (t)

ou ∆ksj est la difference divisee d’ordre k et Bj,k,τ est la B-spline d’ordre k construite sur la subdivisionτ .

Le lien avec le calcul de l’enveloppe moyenne au sens de l’EMD peut etre etabli dans certains cassimples. Par exemple, si l’on considere des enveloppes superieure et inferieure affines et si les extremade s sont repartis sur une grille reguliere, on constate que l’enveloppe moyenne s’ecrit (en posantsj = s(τj)) :

Vτ,ks =∑

j∈Z

∆2sj−1Bj,1,τ .

L’ordre des coefficients utilises avec l’algorithme originel n’est donc pas le meme que celui des coeffi-cients utilises avec l’algorithme propose dans [55]. Par ailleurs, une extension simple dans le cas affineet en supposant que les extrema ne sont pas uniformement repartis donne la formule suivante :

Vτ,ks =∑

j∈Z

1

2

(

τj+1 − τjτj+2 − τj

s(τj+2) + s(τj+1) +τj+2 − τj+1

τj+2 − τjs(τj)

)

Bj,1,τ (t).

Cela montre que, meme dans un cas simple, les poids de la decomposition de l’enveloppe dans la base deB-spline dependent de la repartition des extrema. L’influence de la definition de ces poids sur les modesobtenus n’a jamais ete etudiee. Un premier element de reponse consiste en ce que la decompositionproposee dans [55] est adaptative et preserve la quasi-orthogonalite des modes obtenus. Ce point estassez troublant et suggere de s’interroger si le fait que les poids dependent non-lineairement de larepartition des extrema est crucial ou non dans l’EMD.

L’interet commun pour l’EMD et les problemes d’echantillonnage de l’equipe MGMI du LaboratoireJean Kuntzmann de Grenoble et de l’ IDCOM (Institute for Digital Communication) d’Edimbourg[46] [39] montre l’importance du projet propose.

Echantillonnage et representation non lineaire des images

La compression des images numeriques haut debit est un domaine de recherche tres actif ayant denombreuses applications : citons, par exemple, le stockage des photos numeriques sur un telephoneportable, la television haute definition, ou encore le stockage d’une photo d’identite sur un code barre(500 octets !). Pour cette derniere application par exemple, le format classique de compression JPEG,encore d’actualite pour les applications grand public, est incapable de repondre au probleme : eneffet, les taux de compression des images numeriques sous JPEG sont tres moyens. En revanche, dansdes applications plus pointues ou les taux de compression doivent etre superieurs a 80 %, c’est leformat JPEG2000 qui est devenu le standard. Ce format, developpe a la fin des annees 90 par le

31

”Joint Photographic Experts Group” (qui avait cree le format JPEG) comporte schematiquementdeux etapes : “une etape de decomposition de l’image sur bases d’ondelettes, une etape de codagedes coefficients d’ondelettes” par un codeur tres efficace, car base sur les proprietes des coefficientsd’ondelettes et le fonctionnement de la vision humaine. Outre la qualite globale de l’image, le rendudes contours est meilleur avec JPEG2000 qu’avec JPEG.

Neanmoins, les mathematiciens savaient au depart que les ondelettes 2D “classiques” (produits ten-soriels d’ondelettes 1D) ne sont pas optimales pour la compression d’images presentant des contoursgeometriques. Ainsi, depuis le debut des annees 2000, de nombreuses familles d’ondelettes dites“geometriques” sont apparues pour approcher les contours de maniere optimale et finalement detronerle format JPEG2000 dans la course a la compression des images numeriques : citons par exemple lesCurvelettes de Candes et Donoho [56][57] (Standford), les contourlettes de Do et Vetterli (EPFL,Lausanne) ou encore les bandelettes de Le Pennec et Mallat [66](Ecole Polytechnique). Ces approchesne sont pas stricto sensu multi-resolution, car il s’agit de trouver localement la meilleure fonction pourrepresenter l’image. Une derniere approche, qui s’inscrit dans le cadre des analyses multi-resolution,est la methode “ ENO-EA ” (EA pour ”edge adapted”) de Matei et Cohen (Paris VI).

L’idee des methodes ENO, initialement developpees par Harten [23] puis reprises par Chan et Zhou[52] dans le cadre des decompositions en ondelettes orthogonales, est d’identifier une echelle assez fine(appelee echelle de contours) correspondant a des petits carres de l’espace ou sont localises les pointsde contour et d’utiliser uniquement l’information aux echelles plus grandes pour approcher les contoursen mettant en place des schemas dits de “subdivision”. Ceux-ci sont evidemment non-lineaires car lasubdivision n’est pas la meme en fonction du point de l’image considere. Ils correspondent, la plupartdu temps, a des filtres permettant le calcul approche des coefficients d’ondelettes a une echelle fineen utilisant l’echelle immediatement superieure. Un point important dans la subdivision est de rendrel’approche compatible avec une bonne compression de l’image. Les methodes de subdivision utilisantdes bases orthonormees d’ondelettes [52] ne sont, de ce point de vue, pas optimales en termes decompression. Des methodes de type ENO fondees sur des decompositions non orthogonales existent,a ce sujet citons notre travail dans [36].

Un aspect important, mais rarement aborde, consiste en ce que les schemas de subdivision multi-dimensionnels non lineaires utilises en traitement d’images sont obtenus par produit tensoriel et,de ce fait, ne sont pas intrinsequement bidimensionnels. Depuis 2008, nous avons travaille sur desrepresentations multi-echelles non-separables en suivant une approche de type ENO-EA. Nous avonsmontre que la plupart des resultats de convergence et de stabilite des schemas de subdivision s’etendentau cas non-separable [36]. L’etude des schemas de subdivision non lineaires est une thematique centralede plusieurs equipes de par le monde : on peut citer par exemple N. Dyn (Technion, Israel), P. Oswald(Bremen, Allemagne) ou P. Grohs (Linz, Autriche). Nous avons ensuite etudie les representationsmulti-echelles non separables associees a ces schemas de subdivision pour lesquels nous avons montrede nouveaux resultats de convergence et de stabilite [37][38]. La encore, le sujet interesse de nombreusesequipes en France et a l’etranger, on peut citer par exemple l’equipe de J. Liandrat (LATP, Marseille)ou F. Arandiga et R. Donat (Valencia, Espagne).

Bien que les theoremes de stabilite que nous avons prouves dans [38] soient valables pour desschemas non interpolants, les exemples illustratifs simples pour lesquels on peut prouver convergenceet stabilite sont des schemas interpolants. Ceux-ci sont reputes non optimaux pour les applications encompression d’images. En ce qui concerne les aspects pratiques, nous sommes actuellement en trainde reflechir a la definition de representations multi-echelles non-separables et non-interpolantes quisoient a la fois stables et convergentes tout en fournissant de bons resultats en termes de compressiond’images. D’un point de vue plus theorique, nous souhaitons reflechir a un moyen de tenir compte dufait que, la plupart du temps, les modeles non-lineaires peuvent etre consideres comme des modeleslineaires localement perturbes. Cette vision des choses changerait beaucoup l’ecriture des theoremesde convergence et de stabilite et permettrait aussi la definition d’un spectre d’application plus vaste.

32

De maniere plus generale, les problemes de compression rejoignent ceux de l’echantillonnage surdes grilles non regulieres. En effet, l’information pertinente dans les images se trouve au voisinage desbords pour lesquels la resolution la plus fine est souhaitee. On pourra alors se poser la question dela construction d’un echantillonnage stable qui prenne en compte ce type de consideration. Commenous l’avons vu plus haut, la plupart des echantillonnages stables existants supposent une certaineregularite spatiale et ne sont en general pas adaptes au contours.

Il me semble important de preciser que ces perspectives de travail se situent actuellement ausommet de la recherche scientifique concernant le traitement des images et des signaux. Il faut direque ce domaine de recherche se trouve enrichi tous les jours de resultats importants et je suis persuadeque les resultats attendus dans mon programme de recherche constituent une ouverture vers desactivites de recherches interessantes et motivantes pour la communaute scientifique. Pour preuve, jementionne l’utilisation des algorithmes du compressed sensing dans la derniere mission Herschel, ainsique l’utilisation des methodes adaptatives de compression dans le dernier standard JPEG2000.

33

References

[1] Arandiga, F., A. Cohen,R. Donat et B. Matei Edge detection insensitive to changes of illuminationin the image, Journal Image and Vision Computing, Volume 28 Issue 4, April, 2010

[2] Aujol J.F et B. Matei Simultaneous edge and texture compression, ICPR ACIVS, 2004.

[3] Arandiga, F., A. Cohen,R. Donat, N. Dyn et B. Matei Approximation of Piecewise Smooth Func-tions and Images by edge-adapted (ENO-EA) Multiresolution Techniques, ACHA, vol. 24, pp.225-250, 2008.

[4] F.Arandiga, A.Cohen, M.Doblas, R.Donat et B. Matei Sparse representations of images by edgeadapted non-linear multiscale transforms. IEEE International Conference on Image Processing,Barcelona, 2003,

[5] Bass, R.F. et K. Grochenig, Random Sampling of Entire Functions of Exponential Type in SeveralVariables To appear in Israel J. Math.

[6] Bass, R.F. et K. Grochenig, Random Sampling of Multivariate Trigonometric Polynomials ,SIAM J. Math. Anal. 36, pp. 773-795, (2004)

[7] Bezuglaya, L., V. Katsnelson, The sampling theorem for functions with limited multi-band spec-trum, Z. Anal. Anwendungen 12 (1993), 511-534.

[8] Candes, E. et D. Donoho (1999), Ridgelets : a key to higher-dimensional intermittency ’, a paraıtredans Phil. Trans. Roy. Soc.

[9] Cavaretta, A.S., W. Dahmen et C.A. Michelli (1991), Stationary Subdivision, Memoirs of Amer.Math. Soc., Volume 93.

[10] Cohen, A. (1999) Wavelets in numerical analysis, Handbook of Numerical Analysis, vol. VII,P.G. Ciarlet et J.L. Lions, eds., Elsevier, Amsterdam.

[11] Cohen, A., N. Dyn et B. Matei (2000) On the smoothness and stability of quasilinear subdivisionschemes with application to ENO interpolation, Applied and Computational Harmonical Analysis,15, 89-116, 2003. .

[12] Cohen, A. et B. Matei (2001) Compact representations of images by edge adapted multiscaletransforms, IEEE-ICIP Conference, Tessaloniki.

[13] Cohen, A. et B. Matei (2002) Nonlinear subdivisions schemes : applications to image proces-sing, Tutorial on multiresolution in geometric modelling, A. Iske, E. Quack and M. Floater eds.,Springer, 2002.

[14] Coifman, R.R. et D. Donoho (1995) Translation Invariant Denosing, preprint.

[15] Daubechies, I., O Runborg et W. Sweldens Normal Multiresolution Approximation of Curves,(submitted).

[16] Daubechies, I. et J. Lagarias (1991)Two Scale differences Equations : I.Existence and globalregularity of solutions, SIAM J. Math. Anal. 22, 1388-1410.

[17] Daubechies, I. et J. Lagarias, (1992)Two Scale differences Equations II.Local Regularity, infiniteproducts of matrices and fractals, SIAM J. Math. Anal. 23, 1031-1079.

[18] Deslaurier, G. et S. Dubuc (1989) Symmetric Iterative Interpolation Scheme, Constr. Approx. 5 :49-68.

[19] Dyn, N.(1992) Subdivision Schemes in computer aided geometric design, Advances in NumericalAnalysis II., Subdivision algorithms and radial functions, W.A. Light (ed.), Oxford UniversityPress, 36-104.

34

[20] Dyn, N., M. Floater, et A. Iske (2002) Adaptive Thinning for Bivariate Scattered Data, a paraıtredans le Journal of Computational and Applied Mathematics.

[21] Falzon, F. et S. Mallat(1998) Analysis of low bit rate image transform coding, IEEE Trans.SignalProcessing, 4.

[22] Jiang, G. et C.-W. Shu (1996), Efficient implementation of weighted ENO schemes, Journal ofComput. Phys., 126 :202-228.

[23] Harten, A.(1993) Discrete multiresolution analysis and generalized wavelets, Journal of AppliedNumerical Mathematics, 12 : 153-193.

[24] Harten, A.(1995) ENO Schemes with Subcell Resolution, Journal Computaional Physics, 23 :53-71.

[25] Harten, A., B. Enquist, S. Osher and S. Chakravarthy (1987). Uniformly high order accurateessentially non-oscillatory schemes III, Journal of Comput. Phys., 71 :231-303.

[26] Lev, N., Riesz bases of exponentials on multiband spectra soumis a Proceedings of the AmericanMathematical Society.

[27] Lepennec E. et S. Mallat (2001) Bandelet representation for image compression, IEEE-ICIPConference, Tessaloniki.

[28] Mallat, S. (1998), A wavelet tour of signal processing, Academic Press, New York.

[29] Matei, B. (2003) Smoothness characterization and stability in non-linear multiscale representa-tion : Theoretical Results, (soumis pour publication dans Asymptotic Analysis).

[30] Matei, B. (2003) Smoothness characterization and stability in non-linear multiscale representa-tion : Applications , (soumis pour publication dans Asymptotic Analysis).

[31] Matei, B. (2003) Smoothness characterization and stability in non-linear multiscale representation, Comptes Rendus Mathematique Volume 338, Issue 4 , Pages 321-326 .

[32] Matei, B. (2003) Denoising using Nonlinear Multiscale Transform, Comptes Rendus Mathema-tique, acceptee.

[33] Matei, B. (2003) Optimal Compression Algorithms using Nonlinear Multiresolution Representa-tions, Comptes Rendus Mathematique, acceptee.

[34] Matei B. Nonlinear Multiscale Methods and their applications to homogenization, InternationalConference : New Trends in Continuum Mechanics, Constanta, Septembre 2003,

[35] Matei, B. (2002) Methodes multi-echelles non-lineaires–Applications au traitement d’image, Ph.D.Thesis, Universite Pierre et Marie Curie (Paris VI).

[36] Matei, B. et S. Meignen, A. Zakharova, Smoothness of Nonlinear and Non-separable SubdivisionSchemes , accepted for publication in Asymptotic Analysis.

[37] Matei, B. et S. Meignen, A. Zakharova, Smoothness Characterization and Stability of Nonlinearand Non-Separable Multiscale Representations , submitted to Journal of Approximation Theory,in revision.

[38] Matei, B. et S. Meignen, A New Formalism for Non-Linear and Non-Separable Multiscale Repre-sentation , submitted to Numerical Algorithms.

[39] Meignen, S. et V. Perrier, A New Formulation for Empirical Mode Decomposition Based onConstrained Optimization , IEEE Signal Processing Letters, vol. 14,no. 12,pp. 932-935, 2007.

[40] Matei, B. et Y. Meyer, A variant of compressed sensing Rev. Mat. Iberoamericana Volume 25,pp. 669-692, (2009).

[41] Matei, B. et Y.Meyer, Quasicrystals are sets of stable sampling C. R. Acad. Sci. Paris, Ser. I,vol.346, pp. 1235-1238, 2008.

35

[42] Matei, B. et Y.Meyer, Simple quasicrystals are sets of stable sampling, Complex Var. Elliptic.Equ. 55 (2010), 947-964.

[43] Meyer, Y. Nombres de Pisot, nombres de Salem et Analyse Harmonique, Lecture Notes in Ma-thematics, 117, (1970).

[44] Meyer, Y. Quasicrystals, Diophantine approximations and algebraic numbers, nouvelle version ,(2011).

[45] Meyer, Y. Algebraic Numbers and Harmonic Analysis. 1970. North Holland.

[46] Meyer, Y. (1990)Ondelettes et Operateurs 1 : Ondelettes. Paris : Hermann.

[47] Oswald P.Smoothness of non-linear median-interpolation subdivision (submitted).

[48] Oswald P. Smoothness of non-linear subdivision schemes. Int. Conf. Curves and Surfaces, St.Malo, France, 2003 (submitted).

[49] Pearlman, W.A, et A.Said (1996), An image multiresolution representation for lossless and lossycompression, IEEE Trans. Image Proc., vol. 5, no. 9, 1303-1310.

[50] Taubman, David. (1998), Embedded Block Coding with Optimized Truncation, Signal Processing :Image Communication, vol. 17, Elseviers.

[51] Lyubarskii, Yu. et K.Seip, Sampling and interpolating sequences for multiband-limited functionsand exponential bases on disconnected sets, J. Fourier Anal. Appl. 3 (1997), 597-615.

[52] Chan T., H.M. Zhou, ENO-Wavelet Transforms for Piecewise Smooth Functions, SIAM J. Numer.Anal. 40 (2002) 1369-1404.

[53] Chan T., X.-D Liu et S. Osher (1994) Weighted essentially non-oscillatory schemes, Journal ofComput. Phys., 115 :200-212.

[54] Chappelier, V. et C. Guillemot, Oriented Wavelet for Image Compression and Denoising, IEEETransactions on Image Processing, vol. 15, pp. 2892-2903, 2006.

[55] Chen, Q., N. Huang, S. Riemenschneider et Y. Xu, A B-spline Approach for Empirical ModeDecompositions , Advances in Computational Mathematics, vol. 24, pp. 171-195, 2006

[56] Candes, E. et D. L. Donoho, Continuous curvelet transform : I. Resolution of the wavefront set, Appl. Comput. Harmon. Anal. 19,pp. 162-197, 2003

[57] Candes, E. et D. L. Donoho, Continuous curvelet transform : II. Discretization and frames ,Appl. Comput. Harmon. Anal. 19 198-222, 2003

[58] Candes, E. et D. L. Donoho, New Tight Frames of Curvelets and Optimal Representations ofObjects with Piecewise-C2 Singularities, Comm. Pure Appl. Math.,vol. 57,pp. 219-266, 2002.

[59] Seip, K. A simple construction of exponential bases in L2 of the union of several intervals , Proc.Edinburgh Math.

[60] Harizanov, S. et P. Oswald, Stability of Nonlinear Subdivision and Multiscale Transforms, Constr.Approx., to appear.

[61] Hong, H. et X. Wang, et Z. Tao, Local Integral Mean-Based Sifting for Empirical Mode Decom-position , IEEE Signal Process. Lett., vol. 16, no. 10, p. 841, 2009

[62] Huang, N., Z. Shen, S. Long, M. Wu, H. Shih, Q. Zheng, N. Yen, C. Tung, et H. Liu, Theempirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary timeseries analysis , Proceedings of the Royal Society : Mathematical, Physical and EngineeringSciences, vol. 454, no. 1971, pp. 903- 995, 1998

[63] Thakur, G. et H.T. Wu Synchrosqueezing-based Recovery of Instantaneous Frequency from No-nuniform Samples , Submitted 2010.

36

[64] Traub, J. et G. Wasilkowski, et H. Wozniakowski. Information-based complexity. ComputerScience and Scientific Computing. Academic Press Inc., 1988.

[65] Peng , S. et W. Hwang, Adaptive Signal Decomposition Based on Local Narrow Band Signals ,IEEE Trans. Signal Process., vol. 56, no. 7, pp. 2669–2676, 2008.

[66] Peyre, G. et Mallat, S., Surface compression with geometric bandelets, ACM Transactions onGraphics, 24 (3) , pp.601–608, 2005.

37