Développement de la transformée en ondelettes

Rendu multirésolution

Une idée pour accélérer le rendu est d’utiliser une représentation multirésolution des données. Une basse résolution peut être utilisée lorsque le point de vue est déplacé et une haute résolution dès que le point de vue est stabilisé (Guthe et Strasser, 2004 ; Lippert et Gross, 1995). Le rendu peut également être effectué à haute résolution sur une région d’intérêt et à basse résolution sur le contexte (Krishnan et al., 2004; LaMar et al., 2000). Les ondelettes sont souvent utilisées (Guthe et Strasser, 2004; Krishnan et al., 2004; Lippert et Gross, 1995) car elles permettent une représentation multirésolution compacte des données. Lorsque les ondelettes sont utilisées, il est nécessaire de reconstruire le volume avant d’utiliser une des méthodes précédente. Lippert (Lippert et Gross, 1995) propose toutefois une méthode, dite de projection d’empreintes d’ondelettes, permettant d’effectuer un rendu directement à partir des coefficients d’ondelette. La reconstruction s’effectue lors du rendu proprement dit. Au lieu de projeter des voxels sur le plan de projection, des empreintes d’ondelettes pondérées, sortes de textures, sont accumulées sur le plan de projection.

De la transformée de Fourier à la transformée de Fourier à fenêtre

En 1807, Fourier propose une méthode de décomposition orthogonale de signaux périodiques. Il s’agit de la série de Fourier, plus tard étendue à la transformée de Fourier (Ff pour Fourier Transform en anglais). On notera qu’en 1910, Haar propose une autre base orthonormale pour décomposer les signaux. Le nom d’ondelettes apparaît pour la première fois dans une annexe à la thèse de Haar. La transformée de Fourier n’est pas toujours adaptée à l’analyse de signaux. En effet, si une haute fréquence apparaît seulement à un moment bref dans un signal, la Ff pourra seulement indiquer qu’elle est présente, mais ne pourra pas indiquer le moment auquel elle apparaît. Ainsi en 1946, Gabor propose la transformée de Fourier à fenêtre (WFf pour Windowed Fourier Transform en anglais).

Il s’agit de faire glisser une fenêtre (typiquement une gaussienne) sur le signal avant de lui appliquer une Ff. On obtiendra ainsi la Ff de la partie du signal située au centre de la fenêtre. Ainsi si une haute fréquence est présente à un moment donné, celle-ci sera détectée uniquement lorsque la fenêtre sera positionnée autour de ce moment; ce que l’on cherchait à obtenir.

De la transformée de Fourier à fenêtre à la transformée en ondelettes

À la fin des années 1970, le géophysicien Morlet a des besoins plus précis pour analyser des signaux sismiques. Il voudrait une bonne localisation temporelle des hautes fréquences mais également une bonne résolution fréquentielle dans les basses fréquences. Il pense à utiliser une WFf dont on pourrait modifier la largeur de la fenêtre en la contractant ou en la dilatant. C’est ainsi que naît la transformée en ondelettes (WT pour Wavelet Transform en anglais). Par la suite, Morlet a pris contact avec Grossman, un physicien plus théorique. Ils parviennent à construire une formule d’inversion à la transformée de Morlet en 1984. Ce qui est étonnant, c’est que cette formule semble avoir été élaborée plus tôt par Alasken et Klauder dans le domaine de la mécanique quantique. Grossman ayant été le directeur de thèse de Daubechies, c’est naturellement qu’elle est venue à travailler sur le sujet dès 1985.

D’autre part, Meyer, un pure mathématicien, apprend en 1985 les travaux de Morlet et Grossman et y reconnaît une formule introduite par Calderon dans les années 1960 dans le domaine de l’analyse harmonique. Il s’intéresse aux séries d’ondelettes et construit une base orthonormale d’ondelettes. Cette construction est par la suite généralisée à N dimensions avec l’aide de Lemarié. Lemarié à son tour conçoit une base d’ondelettes à partir de fonctions splines. Là encore ce qui est étonnant, c’est qu’une autre base orthonormale d’ondelettes est développée par Stromberg (un mathématicien dans le domaine de l’analyse harmonique) légèrement avant et que Battle (un physicien intéressé par la théorie quantique) réalise lui aussi une base d’ondelettes à partir de fonctions spline au même moment que Lemarié.

Développement de la transformée en ondelettes

En 1986, Mallat, spécialisé en vision par ordinateur et analyse d’images, reconnaît l’intéret des bases d’ondelettes pour son domaine. En effet en analyse d’images les structures pyramidales sont utilisées pour analyser une image à différents niveaux de résolution. Il contacte ainsi Meyer et ensemble, ils définissent les principes mathématiques de l’ analyse multirésolution. Ils en arrivent également à l’élaboration d’une méthode de calcul rapide de la transformée en ondelettes à l’aide de bancs de filtres. Malheureusement avec les bases connues (Meyer, Battle-Lemarié), les filtres sont infinis et doivent être tronqués. Ainsi en 1987, Daubechies décide de raisonner dans l’autre sens. Les bases d’ondelettes sont générées en partant de filtres. Elle réalise ainsi des bases orthonormales d’ondelettes à support compact. Or, ces filtres présentent de fortes similarités avec des filtres (QMF pour Quadrature Mirror Filters en anglais) utilisés pour la décomposition en sous-bandes en génie électrique.

Notamment, Smith et Barnwell en 1983 et Vetterli un peu plus tard, construisent de tels filtres permettant une reconstruction exacte du signal. Ensuite, bénéficiant des approches plus théoriques (issues des mathématiques) et des approches plus pratiques (issues du génie électrique), la conception de bases ondelettes a été améliorée et étendue à d’autres domaines comme l’analyse numérique, l’approximation ou les statistiques. Ainsi, la transformée en ondelettes a étonnament été le fruit de plusieurs années de collaboration entre des chercheurs de domaine assez variés. Par la suite, quelques points de cette histoire seront plus détaillés.

Cas multidimensionnel

Dans le cas où on désire effectuer une transformée en ondelettes d’un signal multidimensionnel, typiquement une image ou un volume, des ondelettes séparables sont utilisées 1. Cela revient à effectuer des transformées en ondelettes successivement sur chacune des dimensions. Pour une image, après une étape de décomposition, quatre sous-images sont donc obtenues. Une est obtenue en passant le filtre passe-bas selon les deux directions. Deux sont obtenues en passant le filtre passe-bas selon une direction et le filtre passe-haut selon l’autre direction. La dernière est obtenue en passant le filtre passe-haut selon les deux directions. De façon similaire avec la décomposition d’une image est utilisée pour la décomposition d’un volume. Huit sous volumes sont alors obtenus. La décomposition peut ensuite être poursuivie sur les voxels de basse fréquence.

Lancé de rayon

La première méthode, proposée par Kajiya (Kajiya et Herzen, 1984) et améliorée par Levoy (Levoy, 1988, 1990), consiste à parcourir les données du plan de projection à l’objet. À partir de chaque pixel du plan de projection, un rayon est lancé en direction de l’objet. Le volume est échantillonné à intervalle régulier le long de ce rayon et les voxels du volume sont interpolés pour obtenir la valeur aux points d’échantillonnages. Ceux-ci sont alors assemblés selon le modèle d’illumination choisi. Le fait de partir de l’image pour parcourir le volume permet de terminer plus tôt l’intégration des échantillons, lorsque cette intégration ne varie plus à cause de l’ opacité. Cette technique est mieux connue sous son terme anglais early ray termination. En contre partie il est assez difficile de gérer les zones creuses du volume qui ne contribuent pas à l’image finale. Des techniques ont été proposées pour gérer ces espaces creux, comme l’utilisation de boîtes, d’arbres octales ou des approches multirésolutions.

Une autre amélioration possible est l’utilisation de la cohérence spatiale dans l’espace image. En effet, Ihm (Ihm et Lee, 1995) a constaté qu’il est statistiquement fort probable que si deux pixels ont la même couleur, les pixels se situant entre les deux auront également cette couleur. Ceci permet de sous-échantillonner notre espace image et de ne calculer les pixels intermédiaires qu’en cas de non cohérence. Moins de rayons sont ainsi lancés. Dans la même idée, on peut utiliser la cohérence spatiale dans l’ espace objet (Ihm et Lee, 1995). Une décomposition hiérarchique du volume permet alors de réduire le nombre d’échantillons à calculer le long des rayons, les parties homogènes étant traversées d’une traite.

Projection de voxels sur le plan de projection

Plus connue sous son terme anglais, splatting, cette seconde méthode très simple consiste à projeter les voxels du volume sur le plan de projection, c’est à dire de parcourir les données depuis le volume jusqu’au plan de projection. Les voxels sont au préalable convolués par des empreintes qui permettent de faire leur interpolation. Une première évaluation de cesempreintes a été proposée par Westover (Westover, 1990). Il a montré que des empreintes gaussiennes permettaient d’éviter des artefacts car les gaussiennes se chevauchent de façon douce. Des améliorations ont bien entendu été proposées pour améliorer la qualité et la rapidité du rendu. La qualité peut être améliorée en utilisant des empreintes différentes selon la direction de projection. Zwicker (Zwicker et al., 2002) propose ainsi d’utiliser des empreintes gaussiennes elliptiques. De même, Swan (Swan et al., 1997) propose une méthode pour limiter le crénelage. Une autre façon d’améliorer la qualité du rendu et d’utiliser cette technique conjointement avec une autre. Cai (Cai et Sakas, 2000) et Mora (Mora et al.,2002) proposent ainsi de l’utiliser avec la méthode du lancé de rayon, tandis que Muel1er (Mueller et Yagel, 1996) l’utilise conjointement avec la technique Shear-Wmp. En ce qui concerne la rapidité, on peut utiliser les capacités des cartes graphiques (Chen et al., 2004) ainsi que des structure adéquates pour traiter rapidement le volume (en occultant entre autres les espaces vides) (Ihm et Lee, 1995; Kilthau et Müller, 2001 ; Orchard et Moller, 2001).

De même des méthodes de rendu progressif permettent également d’avoir un rendu plus rapide (Laur et Hanrahan, 1991). Dans certains cas, l’utilisation d’une postconvolution peut également accélérer le rendu (Neophytou et Mueller, 2003).

Méthode Shear-Warp

Il s’agit d’une méthode astucieuse proposée par Lacroute (Lacroute et Levoy, 1994) pour profiter des avantages des deux méthodes précédentes. Elle consiste à décaler au préalable les images puis de faire la composition directement sur ces images. Une opération 2D est finalement appliquée pour rétablir un système de coordonnées cohérent. Le fait de faire le rendu sur les images décalées permet de n’effectuer que des interpolations bilinéaires dans l’image comme dans le cas de la projection de voxels plutôt que trilinéaires dans le volume comme dans le tracé de rayon. D’autre part elle permet un encodage efficace des données de type run-length. Il est également facile d’implémenter la terminaison rapide de l’intégration de l’opacité (early ray termination). Cette méthode est réputée pour être la plus rapide à s’exécuter de façon logicielle.

Pour améliorer la qualité du rendu Sweeney (Sweeney et Mueller, 2002) propose d’utiliser une classification et une  illumination après l’interpolation des données alors qu’à la base celle-ci se fait avant et peut entraîner des artefacts. Il propose également d’ajuster le pas d’intégration selon la résolution désirée et d’utiliser des tranches intermédiaires dans certains cas pour éliminer des effets de crénelage. De même Schulze (Schulze et al., 2003) propose une méthode pour utiliser cette technique avec une pré-intégration du volume en minimisant la perte de qualité.

Table des matières

ABSTRACT
REMERCIEMENTS
TABLE DES MATIÈRES
LISTE DES TABLEAUX
LISTE DES FIGURES
LISTE DES ALGORITHMES
LISTE DES ABRÉVIATIONS ET SIGLES
INTRODUCTION
CHAPITRE 1 LES ONDELETTES
1.1 Un peu d’histoire 
1.1.1 De la transformée de Fourier à la transformée de Fourier à fenêtre
1.1.2 De la transformée de Fourier à fenêtre à la transformée en ondelettes
1.1.3 Développement de la transformée en ondelettes
1.2 La transformée de Fourier à fenêtre 
1.3 La transformée en ondelettes 
1.3.1 Transformée en ondelette discrète
1.4 L’analyse multiré solution 
1.5 Génération des bancs de filtre 
1.5 .1 Relations entre échelles
1.6 Propriétés des filtres obtenus
1. 7 Quelques familles d’ondelettes 
1. 7.1 Ondelette de Haar
1. 7.2 Autres ondelettes
1.7.2.1 Ondelette de Shannon
1.7.2.2 Ondelettes de Daubechies
1.7.2.3 Ondelettes biorthogonales
1.7.2.4 Ondelettes de Battle-Lemarié
1.7.3 Ondelettes générées par la méthode du lissage
1.8 Cas multidimensionnel
1.9 Résumé 
CHAPITRE 2 ÉTAT DE L’ART
2.1 Modèles de rendu
2.1.1 Rendu de volume direct
2.1.2 Rendu radiographique
2.1.3 Projection du maximum d’intensité
2.2 Techniques de rendu de volume
2.2.1 Lancé de rayon
2.2.2 Projection de voxels sur le plan de projection
2.2.3 Méthode Shear-Warp
2.2.4 Utilisation du matériel graphique
2.2.4.1 Textures 2D
2.2.4.2 Textures 3D
2.2.5 Techniques à base d’ondelettes
2.2.6 Techniques hybrides
2.3 Représentation du volume avec volume d’intérêt
2.3.1 Codage par blocs
2.3.2 Codage par arbres
2.4 Travaux proches 
2.5 Résumé
CHAPITRE 3 MÉTHODE PROPOSÉE
3.1 Calculs préliminaires pour le rendu
3.1.1 Illumination
3.1.2 Classification
3.1.3 Ombrage
3.2 Projection des empreintes d’ondelettes
3.2.1 Avantages de la technique
3.2.2 Choix de l’ ondelette
3.2.3 Projection utilisée
3.2.4 Génération des empreintes d’ondelettes
3.2.4.1 Méthode d’origine
3.2.4.2 Modifications
3.2.5 Projection des empreintes
3.2.5.1 Matrice de passage
3.2.5.2 Influence de l’interpolation
3.3 Région d’intérêt
3.3.1 Région d’intérêt dans le volume transformé
3.3.2 Structure d’arbres
3.4 Résumé
CHAPITRE 4 RÉSULTATS ET DISCUSSIONS
4.1 Données utilisées
4.2 Interface utilisateur
4.2.1 Chargement des données
4.2.2 Modification des modes de rendu
4.2.3 Sélection de la région d’intérêt
4.2.4 Visualisation des données
4.3 Influence de la fonction d’opacité sur le rendu final 
4.4 Utilisation d’une post-convolution
4.5 Apport de la structure hiérarchique des coefficients
4.6 Influence de la taille de la région d’intérêt 
4.7 Résumé
CONCLUSION
ANNEXE
Implémentation
BIBLIOGRAPHIE

Télécharger le rapport complet