Reconstruction de données compressées (traitements d'images)
Concernant la décomposition et la reconstruction de données, on utilise une analyse multirésolution généralisée [Har94,ADH99a,ADH99b] permmetant de travailler avec des schémas non-linéaires, contrairement aux analyses multiésolutions ondelettes [Daub92,Mal89,Mal00].Ces analyses multirésolutions permettent de définir deux algorithmes multiéchelles. Ils sont composés de:
• un algorithme de décomposition: partant d'un échantillonage sur une grille fine d'une fonction f, f J, on décompose les données au moyen d'un échantillonage sur une grille large f J0 et de détails aux échelles intermédiaires (d J0+1, . . . ,d J ),
• un algorithme de reconstruction: à partir de la donnée des détails et d'un échantillonage sur une grille large f J0, on reconstruit une approximation de f J.
On utilise un schéma de sudbivision dans chacun des deux algorithmes pour passer d'une grille à une autre.
La compression d'une image consiste alors à effectuer une décomposition, en gardant les détails supérieur à un certain seuil, et à reconstruire à partir des détails seuillés. Notamment, les détails les plus importants sont localisés près des discontinuités qui correspondent, par exemple, aux contours ou aux zones de textures.
Nos travaux ont notamment porté sur l'atténuation de phénomènes de flous causés par l'utilisation d'un schéma linéaire, et l'étude de la stabilité de ces deux algorithmes dans le but de controler la différence entre les données f J et les données approchées par le coefficient de troncature des détails.
Dans les figures suivantes (figures 1 et figures 2), on s'est proposé de comparer l'utilisation de schémas de subdivision dans les analyses multirésolutions. Pour cela, on effectue les étapes suivantes:
1. partir d'une image décomposée en 2 8 x2 8 pixels
2. effectuer une décomposition jusqu'à une résolution de 2 4 x2 4 pixels
en utilisant un schéma de subdivision
3. conserver les détails supérieurs à un seuil égal à 10
4. appliquer un algorithme de reconstruction à partir des détails tronqués en utilisant le meme schéma de subdivision
On construit ainsi une approximation de l'image initale contenant 2 8 x2 8 pixels.
Concernant la stabilité des analyses multirésolutions suivantes, il a été prouvé que les analyses multirésolutions associées à un schéma linéaire et celle associée au schéma pph [AL05] sont stables.
Nos travaux ont consisté à prouver la stabilité de l'analyse multirésolution associée au schéma [MDL05], et à construire des schémas non-linéaires en base 3 dont l'analyse multirésolution est stable [ADL].
Figure 1: Comparaison des analyses multirésolutions sur une image classique (compression-reconstruction)
|
|
|
| image originale (2 8 x28 pixels) | algorithme utilisant le schéma linéaire de Lagrange centrés 4 points [DD87] | |
|
|
|
| algorithme utilisant le schéma non-linéaire weno [CDM03] | algorithme utilisant le schéma non-linéaire pph [ADLT06] | algorithme utilisant le schéma [MDL05] |
Figure 2: Comparaison des analyses multirésolutions sur une image géométrique (compression-reconstruction)
|
|
|
| image originale (2 8 x28 pixels) | algorithme utilisant le schéma linéaire de Lagrange centrés 4 points [DD87] | |
|
|
|
| algorithme utilisant le schéma non-linéaire weno [CDM03] | algorithme utilisant le schéma non-linéaire pph [ADLT06] | algorithme utilisant le schéma [MDL05] |
Quelques Références
[ADH99a] F. Aràndiga, R. Donat, and A. Harten. Multiresolution based on weighted averages of the hat function i: Linear reconstruction techniques. SIAM J. Numer. Anal., 36:160-203, 1999[ADH99b] F. Aràndiga, R. Donat, and A. Harten. Multiresolution based on weighted averages of the hat function ii: Non-linear reconstruction techniques. SIAM J. Numer. Anal., 20:1053-1093, 1999
[AL05] S. Amat and J. Liandrat. On the stability of pph nonlinear multi-resolution. Applied and Computational Harmonic Analysis, 18(2):198-206, 2005
[Dau92] I. Daubechies. Ten lectures on wavelets. SIAM, Philadelphia, PA, 1992
[Har94] A. Harten. Adaptive multiresolution schemes for shock computations. Journal of Computational Physics, 115:319-338, 1994
[Mal89] S. Mallat. A theory for multiresolution signal decomposition : the wavelet representation. IEEE Transaction on Pattern Analysis and Machine Intelligence, 11:674-693, 1989
[Mal00] S. Mallat. A Wavelet Tour of Signal Processing. Academic Pres, 2000
Construction de Courbes (CAO)
Le principe est de partir de points initiaux et de doubler le nombres de points à chaque itération dans le but, après un grand nombre d'itérations, d'obtenir des points permettant de définir courbe. L'opérateur permettant de passer d'une itération à une autre est appelé schéma de subidvision.Les schémas de subdivisions (f->S(f)) ont été introduits pour la construction de courbes ou de surfaces. Quand on les itère (f j = S jf), on construit un algorithme multiéchelle, qui permet de définir une courbe ou une surface à partir de points initiaux, appelés aussi points de contrôle. Initialement, la notion a été introduite pour accélerer la construction de courbes splines [Cha74]. La courbe obtenue est alors définie aux points dyadiques.
Diverses propriétés sont intéressantes à étudier. D'abord, la convergence définie comme l'existence d'une fonction continue vers laquelle "converge" les itérés du schéma S jf et la régularité de cette fonction limite. On souhaite aussi contrôler des erreurs: la stabilité du schéma, pour contrôler des petites perturbations aux points initiaux, et l'ordre d'approximation, pour contrôler l'erreur pour des points initiaux provenant de l'échantillonage d'une fonction.
Historiquement, deux grandes familles de schémas linéaires ont été développées: les schémas interpolants de Lagrange [DD89] et les schémas approximants splines [Cha74].
Malgré les nombreux avantages que présentent les schémas linéaires [CDM91, Dyn92], ils font apparaître d'mportants défauts dont la présence d'oscillations dans les fonctions limites (phénomène de Gibbs) ou un ordre d'approximation trop faible (figure 3). On se propose d'utiliser des schémas non-linéaires. On trouve différents schémas non-linéaires, qui répondent à différents problèmes. Ainsi, on trouve dans la littérature des schémas permettant de préserver des propriétés géométriques [Kui98, FM98], de reproduire des fonctions particulières [MeHW01, BCR07b], de travailler sur des grilles non-uniformes [DGS99] ou finalement, d'éliminer le phénomène de Gibbs [CDM03, ADLT06] (figure 4).
C'est dans cette dernière optique que se situe nos traveaux, à savoir l'étude théorique et la construction permettant d'éviter les oscillations et d'avoir des "bonnes" propriétés (temps de calcul, régularité de la fonction limite, stabilité du schéma...) (figure 2).
Figure 3: Comparaison des fonctions limites des différents schémas linéaires
|
|
| schéma approximant spline degré 2 [Cha74] | schéma interpolant de Lagrange centrés utilisant 4 points [DD87] |
Figure 4: Comparaison des fonctions limites de différents schémas non-linéaires
|
|
| schéma weno [CDM03] | schéma pph [ADLT06] |
|
|
| schéma [MDL05] (schéma C 1) | schéma PPHA [ADL] (schéma C 2) |
Quelques Références
[ADLT06] S. Amat, R. Donat, J. Liandrat, and J. C. Trillo. Analysis of a new non-linear subdivision scheme. applications in image processing. Foundadtions of Computational Mathematics, 6(2):193-226, 2006.[BCR07b] C. Beccari, G. Casciola, and L. Romani. A non-stationary uniform tension controlled interpolating 4-point scheme reproducing conics. Computer Aided Geometric Design, 1:1-9, 2007.
[CDM91] A. S. Cavaretta, W. Dahmen, and C. A. Micchelli. Stationary subdivision. Memoirs of the American Mathematical Society, 93(453):346-349, 1991.
[CDM03] A. Cohen, N. Dyn, and B. Matei. Quasi-linear subdivision schemes with applications to eno interpolation. Applied and Computational Harmonic Analysis, 15:89-116, 2003.
[Cha74] G. Chaikin. An algorithm for high speed curve generation. Computer Grpahics and Image Processing, 3:346-349, 1974.
[DD89]G. Delauriers and S. Dubuc. Symmetric iterative interpolation processes. Constructive Appoximation, 5:49?68, 1989.
[DGS99] I. Daubechies, I. Guskov, and W. Sweldens. Regularity of iregular subdivision. Constructive Appoximation, 15:381-426, 1999.
[Dyn92] N. Dyn. Subdivision schemes in computer aided geometric design. Computer Aided Geometric Design, 20(4):36-104, 1992.
[FM98] M. S. Floater and C. A. Micchelli. Nonlinear stationary subdivision. Approximation Theory, 212:214-224, 1998.
[Kui98]F. Kuijt. Convexity Preserving Interpolation. Stationary Nonlinear Subdivision and Splines. PhD thesis, University of Twente (The Netherlands), 1998.
[MeHW01] G. Morin and J. Warren et H. Weimer. A subdivision scheme for surfaces of revolution. Computer Aided Geometric Design, 18:483-502, 2001.
[MDL05] M. Marinov, N. Dyn, and D. Levin. Geometrically controlled 4-point interpolatory schemes. In A. Le Mehaute P.J. Laurent and L.L. Schumaker eds., editors, Advances in multiresolution for geometric modelling, pages 301-315. Springer, 2005.
Construction d'opérateurs aux différences finies sur une grille non-uniforme
A partir d'un opérateur aux différences finies, on se propose de le modifier pour que sur une grille adaptée don non-uniforme, l'erreur de consistance est uniforme et optimale. On combine le schéma de subdivision qui sert à construire la grille adaptée [BH95,Sjo95,CD01] et l'opérateur classique aux différences finies.L'idée de couplage schémas différences finies/schémas de subdivision n'est pas nouvelle [CKMP02,GG02]. Mais, nos travaux sont originaux au sens où en partant d'un opérateur classique, on obtient une expression analytique de ce nouvel opérateur. Pour ce nouvel opérateur, on obtient une erreur en 2 J0 (oss-r) + 2 J ofd où oss est l'ordre du schéma de subdivision, ofd l'ordre de l'opérateur aux différences, r l'ordre de la dérivée que l'on approche, 2 -J le pas du maillage le plus fin et 2 -J0 le pas du maillage le plus large. En prenant un schéma de subdivision convenablement choisi, il est possible d'avoir une erreur homogène en 2 -J sur une grille non-uniforme.
Ces travaux peuvent etre utiliser par exemple, pour remplacer un rafinement de maillages.
Quelques Références
[BH95] B. L. Bihari and A. Harten. Application of generalized wavelets: an adaptive multiresolution scheme. Journal of Computational Applied Mathematics, 61:275-321, 1995.[CD01] G. Chiavassa and R. Donat. Point value multiscale algorithms for 2d compressible flows. SIAM Journal on Scientific Computing, 23(3):805-823, 2001.
[CKMP02] A. Cohen, S. M. Kaber, S. Muller, and M. Postel. Fully adaptive multiresolution finite volume schemes for conservation laws. Mathematics of Computations, 73:183- 225, 2002.
[GG02] S. Gomez and B. Gustafasson. Combinig wavelets with finite differences: a consistence analysis. Technical report, 2002.
[Sjo95] B. Sjogreen. Numerical experiments with the multiresolution scheme for the compressible euler equations. Journal of Computational Physics, 117:251-261, 1995.
Retourner au début
