Procédé de codage de données représentatives d'une texture multidimensionnelle, dispositif de codage, procédé et dispositif de décodage, signal et programme correspondants

La présente invention se situe dans le domaine de l'informatique graphique, et plus précisément dans le domaine du codage et de la compression de données permettant de visualiser des scènes virtuelles. L'invention concerne en effet un procédé de codage de textures multidimensionnelles, servant à la transmission et à la génération d'images de synthèse photo-réalistes.

Représenter l'apparence des surfaces réelles est une des principales problématiques en informatique graphique. L'apparence globale d'une surface est souvent définie à différentes échelles.

La forme de la surface est placée au niveau le plus grossier, le niveau macroscopique, et correspond à la géométrie de l'objet dont on représente la surface. De par le mode de rendu actuel sur un matériel graphique, cette géométrie est le plus souvent exprimée par un maillage, c'est-à-dire un ensemble de polygones.

Le niveau le plus fin, correspondant à la micro-structure, détermine la manière dont la surface interagit avec son environnement. Elle exprime les propriétés d'un matériau : une surface en bois ne va pas réfléchir la lumière de la même manière qu'une surface métallique. Ces interactions sont représentées en informatique graphique par les Bilatéral Réflectance Distribution Functions (BRDF), fonctions en quatre dimensions dépendantes du point de vue et de la direction de la lumière.

Une couche intermédiaire, la méso-structure, encapsule les détails géométriques, tels que de petites bosses sur une surface granuleuse par exemple. D'un point de vue applicatif, on représente souvent cette couche par

une méthode dite de perturbations des normales ou "bump mapping", ou encore par une méthode de variation géométrique des points du maillage le long de leur normale, appelée méthode de "Displacement mapping". Ce niveau perturbe la couche supérieure car les variations locales de la surface entraînent une variation locale de l'intensité lumineuse, du fait de la création d'une occlusion ou d'une ombre par exemple.

En capturant le rendu de la surface, à l'aide d'un appareillage photonumérique, suivant plusieurs points de vue et plusieurs directions de la lumière, le calcul complexe des interactions entre méso-structure et micro- structure, nécessaire afin d'effectuer le rendu d'une surface, est contourné. On obtient ainsi des fonctions appelées "Bilatéral Texture Fonctions" (BTF), décrites dans l'article de KJ. Dana, B. van Ginneken, S. K. Nayar et JJ. Koenderink, intitulé "Réflectance and texture of real-world surfaces", et publié dans le journal " Association for Computer Machinery (ACM) Transactions On Graphics" en 1999. On exprime ces fonctions par exemple sous la forme:

BTF = BTF(x,y,θ _v ,φ _v ,θ _! ,φ _l ) où:

- x et y représentent des coordonnées spatiales exprimées en coordonnées paramétriques, - θ _v et φ _v définissent la direction d'un point de vue en coordonnées polaires,

- et θ, et φ _ι définissent une direction de la lumière en coordonnées polaires.

Une BTF correspond ainsi à un jeu d'images où chaque image est associée à un point de vue et à une direction de la lumière. Ce procédé de capture permet de modéliser à la fois la méso-structure, la micro-structure et toutes les interactions qui existent entre ces deux couches, pour un même matériau. Afin d'assurer une transition douce entre différents points de vue ou directions de la lumière, un échantillonnage fin est nécessaire, c'est-à-dire qu'une BTF correspond à un nombre d'images important.

Lors de la transmission des données correspondant à ces matériaux modélisés, aussi appelés textures ou textures multidimensionnelles, et lors du

rendu en temps réel de ces textures, l'information brute véhiculée par les BTF doit donc être exprimée différemment, afin de répondre aux contraintes de rapidité d'accès aux données, et de tailles de mémoire limitées.

D'autres procédés similaires à celui permettant d'obtenir des BTF existent, qui génèrent des textures multidimensionnelles en utilisant des dimensions en moins ou en plus par rapport aux BTF. Ainsi les "Polynomial Texture Map (PTM)" sont des textures où seule la direction de la lumière fait varier l'aspect de la surface associée. De même les "Time-Varying BTF" sont des BTF auxquelles une dimension est ajoutée, permettant de faire varier l'aspect d'une surface avec le temps. Ces textures sont elles aussi représentées par un nombre très important de données qui nécessitent un codage approprié.

Les techniques de codage existantes permettant de compresser les données de ces textures multidimensionnelles évoluent essentiellement suivant deux approches.

La première approche consiste à approximer une texture multidimensionnelle par des modèles de fonctions continues. Par exemple une texture exprimée sous la forme d'une BTF est approximée par des modèles de fonctions BRDF, ou par des polynômes bi-quadratiques. En effet cette BTF étant exprimée par un ensemble d'images, chacune étant la photographie de la surface d'un matériau correspondant à la texture selon un point de vue et une direction de la lumière donnés, en classant différemment ces données on obtient pour chaque pixel sa variation en fonction de la direction de la lumière considérée et en fonction du point de vue considéré. Autrement dit cette BTF est approximée par un ensemble de modèles de fonctions BRDF:

BTF(z,v,l) ≈ {BRDF _z (v,l)},\/z où

- z est la projection des coordonnées spatiales x et y définissant initialement un pixel dans la BTF, sur une seule dimension,

- v est la projection des coordonnées polaires initiales θ _v et φ _v définissant initialement la direction d'un point de vue dans la BTF, sur une seule dimension,

- / est la projection des coordonnées polaires initiales θ, et φ, définissant initialement une direction de la lumière dans la BTF, sur une seule dimension,

- et BRDF _z (v, I) est un modèle de fonction BRDF pour le pixel z, dans lequel la direction de la lumière et la direction d'un point de vue sont exprimées chacune sur une seule dimension. De telles méthodes d'approximation par des modèles de fonctions BRDF sont décrites notamment dans les articles suivants:

- "Réflectance field based real-time, high-quality rendering of bidirectional texture functions", de J. Meseth, G. Mϋller et R. Klein, publié en février 2004 dans le journal "Computers and Graphics", - "Efficient rendering of spatial bi-directional réflectance distribution functions", de D.K. McAllister, A. Lastra et W. Heidrich, publié à l'occasion d'une conférence "ACM SIGGRAPH/EUROGRAPHICS conférence on Graphics Hardware" de 2002,

- et "Non-linear réflectance model for bidirectional texture function synthesis", de J. Filip et M. Haindl, publié en 2004 à l'occasion d'une conférence "International Conférence on Pattern Récognition (ICPR)". Le modèle de fonction BRDF utilisé pour cette approximation est par exemple celui de E. P. F. Lafortune, S-C. Foo, K.E. Torrance et D.P. Greenberg décrit dans leur article "Non-linear approximation of réflectance functions" publié à l'occasion d'une conférence "ACM SIGGRAPH" de 1997.

De façon similaire, une BTF est parfois approximée par des polynômes bi-quadratiques:

BTF(z,v,θ _ι ,φ _ι ) ≈ {P _v {z,θ _ι ,φ _ι )}yv où

- z est la projection des coordonnées spatiales x et y définissant un pixel initialement dans la BTF, sur une seule dimension,

- v est la projection des coordonnées polaires θ _v et φ _v définissant initialement la direction d'un point de vue dans la BTF, sur une seule dimension,

- et P _x , (z, θ,, φ _t ) est un polynôme bi-quadratique d'approximation de la

BTF pour un point de vue donné.

Les méthodes basées approximation selon cette première approche permettent d'obtenir une représentation compacte et continue des textures, qui s'adapte bien aux algorithmes de rendu actuel, effectués en général directement sur des cartes graphiques programmables. Elles sont toutefois limitées par la complexité des calculs nécessaires. En effet, si une décomposition en valeur singulière d'une BTF suffit pour obtenir une approximation par des polynômes bi-quadratiques, l'approximation de la même fonction par des modèles de fonctions BRDF s'avère souvent de résolution très complexe. De plus, ces approximations ne permettent pas de rendre la variété des effets capturés lors de l'acquisition des BTF. Les effets liés aux déplacements du point de vue ou de la direction de la lumière nécessiteraient, pour être pris en compte, l'utilisation de modèles de fonctions BRDF encore plus complexes, ou de polynômes différents, tels que décrits dans les articles:

- "A réflectance model for computer graphies", de R.L. Cook et K.E. Torrance, publié en 1982 dans le magazine "ACM Transactions On Graphics", - ou "Measuring and modeling anisotropic reflection", de GJ. Ward, publié à l'occasion d'une conférence "ACM SIGGRAPH" de 1992. De plus les spéculantes et singularités, telles que des occlusions ou des ombrages, induites par la méso-structure des surfaces modélisées, sont évincées par ces méthodes basées approximation.

La seconde approche consiste à effectuer une décomposition en base linéaire d'une texture multidimensionnelle. Etant donnée une texture, exprimée par exemple sous la forme d'une BTF, cette BTF étant assimilable à un signal multidimensionnel, une analyse en composantes principales, ou décomposition en valeurs singulières, est appliquée. Cette méthode consiste à rechercher les directions dans l'espace qui représentent le mieux les corrélations du jeu de données constitué par la BTF. Une nouvelle base est alors définie, résultante de l'orthogonalisation du domaine d'analyse par une recherche des vecteurs propres et valeurs propres de la matrice de covariance associée à la BTF. Les axes du nouveau repère associé sont tels que la variance des échantillons initiaux de la BTF est maximale. Les vecteurs propres sont ensuite triés par ordre d'importance, en fonction de leurs valeurs propres correspondantes, par ordre décroissant. On garde ainsi uniquement les axes les plus influents. Les données initiales de la BTF sont ensuite projetées dans ce nouvel espace de dimensions réduites. On obtient donc, par combinaison linéaire, une approximation du signal original dans cette nouvelle base :

BTF{x,y,θ _v ,φ _v ,θ _ι ,φ _ι ) ≈ Y _j g _t {x,y) -h _ι {θ _v ,φ _v ,θ _ι ,φ ₁ ) où les fonctions g, représentent les poids issus de la projection dans la nouvelle base {h, } , composée de c vecteurs issus de la réduction de dimensionnalité.

Les méthodes existantes selon cette deuxième approche diffèrent par le choix des données à analyser ou sur l'organisation de la décomposition.

Ainsi, certaines méthodes utilisent l'ensemble des données de la BTF comme espace d'analyse, comme pour l'équation ci-dessus et comme décrit dans l'article de M. L. Koudelka, S. Magda, P.N. Belhumeu, et DJ. Kriegman, intitulé "Acquisition, compression and synthesis of bidirectional texture functions" et publié à l'occasion d'un atelier international "Texture Analysis and Synthesis" de 2003.

D'autres méthodes utilisent une représentation par point de vue afin d'exploiter la cohérence lors d'un changement de direction de la lumière, plus forte que lors d'un changement de point de vue:

BTF (z, v,l) = {BTF _v (z, l)}yv

avec BTF _v (z,l) ≈ ∑g _v Al) 'h _VJ (z) ,

où les fonctions g _{v ι} représentent les poids issus de la projection dans une nouvelle base |λ _V }, d'un échantillon BTF _v (z,l) correspondant aux données de la BTF BTF(z, v, I) pour un point de vue donné v . Ces méthodes de représentation par point de vue sont décrites dans les articles: - "Efficient and realistic visualization of cloth", de M. Sattler, R. Sarlette et

R. Klein, publié à l'occasion d'une conférence internationale "Eurographics Symposium on Rendering " de 2003, - et "Preserving realism in real-time rendering of bidirectional texture functions", de J. Meseth, G. Mϋller et R. Klein, publié à l'occasion d'une conférence internationale "OpenSG Symposium" de 2003.

Les mêmes auteurs, G. Mϋller, J. Meseth et R. Klein, dans leurs articles

"Compression and real-time rendering of measured BTFs using local Principal

Component Analysis (PCA)", présenté à l'atelier international "Vision,

Modeling and Visualisation" de 2003, et " Fast environmental lighting for local- PCA encoded BTFs", publié à l'occasion de la conférence internationale

"Computer Graphics International (CGI)" de 2004, proposent une représentation par bloc des textures multidimensionnelles en regroupant par paquets les données ayant le plus de vraisemblance. L'analyse est ensuite effectuée sur chaque bloc individuellement et l'approximation analytique de la BTF associée est :

5rF(z,v,/) ≈f (=l>, _ω >)A _ω >,0

où les fonctions g _k(z) ,, représentent les poids issus de la projection dans de nouvelles bases de la BTF 57F(z,v,0dans laquelle les données ont été regroupées par blocs en fonction des pixels les plus corrélés, k(z) étant une fonction correspondant à une table de correspondance associant un pixel à un bloc de vraisemblance.

Toujours selon cette deuxième approche, une méthode multi-résolution est proposée par W. -C. Ma, S.-H. Chao, Y.-T. Tseng, Y.-Y. Chuang, C- F.Chang, B.-Y. Chen et M. Ouhyoung, dans leur article ^H Level-of-detail représentation of bidirectional texture functions for real-time rendering", publié en 2005 à l'occasion d'une conférence internationale "Symposium on Interactive 3D graphies and games". Ils réalisent tout d'abord une transformation du domaine initial en pyramide de Laplace pour chaque pixel. Cette pyramide, constituée de plusieurs niveaux, est construite en filtrant le niveau de détail le plus élevé pour obtenir une représentation de plus basse résolution. Les coefficients de la pyramide sont par la suite décomposés par une analyse en composantes principales.

Enfin M.A.O. Vasilescu et D. Terzopoulos, dans leur article "Tensortextures: multilinear image-based rendering", publié en 2004 dans le journal "ACM Transactions On Graphics", proposent une méthode multilinéaire: ils décomposent la BTF en produit de tenseurs. Chaque tenseur représente deux dimensions de la BTF :

- un tenseur spatial représente la projection des coordonnées spatiales JC et y sur une seule dimension,

- un tenseur lié au point de vue représente la projection des coordonnées polaires θ _v et φ _v sur une seule dimension,

- et un tenseur lié à la direction de la lumière représente la projection des coordonnées polaires θ, et φ, , sur une seule dimension.

Ces tenseurs sont calculés grâce à une décomposition en valeurs singulières en trois dimensions, chaque dimension représentant un doublet comme énoncé précédemment. Cette méthode permet donc une réduction de

dimension plus fine dans la mesure où elle permet de privilégier une dimension, c'est-à-dire un tenseur, individuellement. La décimation n'est donc pas totalement aléatoire sur l'ensemble de la BTF car l'erreur d'approximation peut être ciblée en fonction du nombre de composantes principales retenues pour chaque dimension.

Les méthodes basées décomposition selon cette deuxième approche améliorent les résultats qualitatifs par rapport aux méthodes basées approximation, le choix du nombre de composantes principales déterminant la qualité des textures compressées par de telles méthodes. Elles définissent de plus une représentation compacte et discrète des textures multidimensionnelles. Cette compacité est due au fait que les vecteurs issus de la décomposition sont classés par ordre d'importance et seuls les vecteurs les plus représentatifs sont pris en compte. Cependant cette décimation est aléatoire et ne permet pas de définir quels détails seront occultés lors de la transformation. Elle évince de plus certaines singularités capturées lors du processus d'acquisition, les axes substitués correspondant à des zones de faible corrélation. Ce manque d'information fréquentielle limite la flexibilité de ces méthodes: elles ne permettent pas de fournir directement une représentation suivant différents niveaux de détails, par un décodage progressif de l'information. Une représentation multi-résolution des textures compressées par ces méthodes nécessite, comme dans l'article "Level-of- detail représentation of bidirectional texture functions for real-time rendering", des transformations supplémentaires.

Il est d'ailleurs à noter que la méthode multi-résolution basée décomposition mentionnée dans cet article produit en fait une représentation de texture par résolution et ne correspond donc pas à une unique représentation multi-résolution permettant un décodage progressif de l'information en fonction d'un choix de résolution.

De plus, ces méthodes fournissant une représentation discrète, elles nécessitent, lorsqu'un niveau de détail élevé est nécessaire sur une zone d'une texture lors de son rendu, une interpolation sur l'ensemble des

dimensions de cette texture à l'aide d'échantillons voisins issus du processus d'acquisition.

Les méthodes existantes de compression de texture ne permettent donc pas de conserver l'ensemble des détails capturés d'une texture, ni de fournir un décodage progressif de l'information de texture afin de s'adapter aux contraintes matérielles lors de la transmission de cette information, liées par exemple à la puissance des cartes graphiques des récepteurs ou au débit du réseau utilisé. Cette faculté est cependant nécessaire pour généraliser l'utilisation des textures aux systèmes décentralisés ou à une plus grande gamme de périphériques, comme les terminaux mobiles.

La présente invention a pour but de résoudre les inconvénients de la technique antérieure en fournissant notamment un procédé et un dispositif de codage de données représentatives d'une texture multidimensionnelle, utilisant les propriétés de l'analyse en ondelettes sur toutes les dimensions de cette texture.

A cette fin, l'invention propose un procédé de codage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte les étapes de:

- analyse en ondelettes desdites données sur lesdites dimensions,

- et compression de données obtenues à partir du résultat de ladite analyse.

Grâce à l'invention, on obtient une représentation de texture multidimensionnelle efficacement compressée: le taux de compression obtenu est meilleur que dans l'art antérieur, tout en gardant un bon niveau de détail et en ne nécessitant qu'une faible complexité de calcul, ce qui permet de reconstruire en temps réel les données initiales lors du rendu. En effet, bien que l'algèbre multilinéaire s'avère parfois coûteux lors de la synthèse c'est-à-

dire lors du décodage, les tenseurs utilisés dans l'invention sont creux, c'est-à- dire que la plupart de leurs coefficients sont nuls, ce qui, dans la pratique, implique peu de calculs.

Le fort taux de compression obtenu par le procédé de codage selon l'invention permet de conserver une représentation de texture de très bonne qualité, qui conserve notamment tous les effets liés au déplacement du point de vue ou de la direction de la lumière.

Ces avantages sont liés aux propriétés de l'analyse en ondelettes, qui exploite la corrélation dimensionnelle et inter-dimensionnelle sans transformation préalable. De plus l'analyse en ondelettes correspond à une analyse fréquentielle d'un signal initial, qui est décomposé en bandes de fréquences. De ce fait, il est possible de cibler la décimation de manière fréquentielle et cela pour chaque dimension du signal. Cela permet de conserver toutes les singularités de la texture compressée selon l'invention. Cette analyse est en outre une analyse multi-résolution, elle produit une représentation du signal initial par échelle, dans laquelle on qualifie de niveau le plus grossier les coefficients basse-fréquence et de niveau le plus fin la reconstruction à partir des coefficients haute-fréquence. Cette caractéristique permet de définir différents niveaux de détails à partir d'une même représentation de texture. Elle permet également de représenter l'information de texture de manière progressive: dans une telle représentation, les données sont organisées par ordre d'importance, les coefficients minimisant l'erreur de reconstruction étant placés au début. Le principe de cette représentation consiste à ajouter des détails à l'approximation du signal d'origine. Ainsi, si la transmission sur un réseau ou vers un processeur de données de texture codées selon l'invention est interrompue, par exemple pour respecter certains critères tels que la taille des données reçues, l'information déjà transmise sera exploitable. Un autre avantage de cette représentation progressive est l'adaptation possible des données de texture codées selon l'invention à différents types de périphériques graphiques,

n'ayant pas les mêmes capacités en termes de calcul et de taille de mémoire, tels que des centres de réalité virtuelle, des ordinateurs de bureau ou des périphériques mobiles. Cette représentation progressive permet également l'adaptation des données au débit de transmission lors d'une application décentralisée.

Un autre avantage lié à l'analyse par ondelettes est de rendre le codage selon l'invention extrêmement configurable: suivant que l'on privilégie une représentation de la meilleure qualité possible ou une représentation la plus compacte possible, on choisit une compression sans pertes ou une compression avec pertes.

Il est en outre possible d'effectuer le codage selon l'invention sur des dispositifs ou systèmes à architecture parallèle, tels que les processeurs graphiques actuels appelés GPU, d'après l'anglais "Graphics Processing Unit", des processeurs multi-cœur ou une grappe d'ordinateurs personnels. Ii est à noter que de par ses avantages liés aux possibilités de représentation progressive des données de texture, et de parallélisme des calculs, le procédé de codage selon l'invention est compatible avec les systèmes de navigation virtuelle "peer-to-peer", qui nécessitent une résistance aux pannes et une grande flexibilité de transmission de l'information. Il permet notamment de transmettre en parallèle des données de texture depuis différents émetteurs, vers des récepteurs de capacités très différentes.

Enfin, le procédé de codage selon l'invention autorise un accès dynamique et rapide aux données de texture codées selon l'invention. En effet, il n'est pas nécessaire de reconstruire l'ensemble des données initiales à chaque nouvelle image d'une même texture lors de son rendu, car le codage des données selon l'invention permet une reconstruction locale de zones d'intérêt.

Selon une caractéristique préférée, le procédé de codage selon l'invention comporte une étape préalable de réorganisation desdites données représentatives d'une texture multidimensionnelle selon un nombre de dimensions prédéterminé.

Cette étape de réorganisation des données de texture permet de simplifier la décomposition en ondelettes, par réduction du nombre de dimensions notamment.

Selon une autre caractéristique préférée, dans ladite étape de réorganisation lesdites données sont rangées de manière à maximiser la corrélation entre deux échantillons successifs desdites données selon au moins une dimension.

Le fait de maximiser la corrélation entre échantillons avant la décomposition en ondelettes améliore la compression des données lors de leur codage.

Selon une autre caractéristique préférée, lesdites données représentatives d'une texture multidimensionnelle représentent des couleurs selon le système de codage couleur YUV.

L'utilisation du système de codage couleur YUV au lieu d'un système de codage classique Rouge/Vert/Bleu RVB, pour représenter les couleurs de la texture codée selon l'invention, permet d'obtenir, pour une qualité visuelle équivalente, de meilleurs taux de compression. En effet, l'œil humain étant moins sensible aux variations chromatiques et plus à la luminance, ce choix permet lors de l'étape de quantification associée au codage, de coder moins précisément les paramètres U et V représentatifs de la chromaticité, que le paramètre Y représentatif de la luminance.

Selon une autre caractéristique préférée, l'étape de compression du procédé de codage selon l'invention utilise un codage de type "zerotree".

Ce type de codage permet d'optimiser la compression des données de texture ayant été analysées en ondelettes.

L'invention concerne aussi un procédé de décodage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte les étapes de: - décompression desdites données,

- et synthèse en ondelettes sur lesdites dimensions de données obtenues à partir de ladite décompression.

L'invention concerne aussi un signal représentatif d'une texture multidimensionnelle initialement représentée par des données organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce que lesdites données ont été codées par analyse en ondelettes sur lesdites dimensions, puis par compression de données obtenues à partir du résultat de ladite analyse. L'invention concerne encore un dispositif de codage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte: - des moyens d'analyse en ondelettes desdites données sur lesdites dimensions,

- et des moyens de compression de données obtenues à partir desdits moyens d'analyse.

L'invention concerne également un dispositif de décodage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte:

- des moyens de décompression desdites données, - et des moyens de synthèse en ondelettes sur lesdites dimensions de données obtenues à partir desdits moyens de décompression. Le procédé de décodage, le signal, le dispositif de codage et le dispositif de décodage présentent des avantages analogues à ceux du procédé de codage selon l'invention.

1 0

L'invention concerne enfin un programme d'ordinateur comportant des instructions pour mettre en œuvre le procédé de codage selon l'invention ou le procédé de décodage selon l'invention, lorsqu'il est exécuté sur un ordinateur.

D'autres caractéristiques et avantages apparaîtront à la lecture d'un mode de réalisation préféré décrit en référence aux figures dans lesquelles :

- la figure 1 représente l'échantillonnage de l'acquisition d'une BTF modélisant une texture,

- la figure 2 est un tableau illustrant les valeurs de cet échantillonnage, - la figure 3 représente une interprétation de cette BTF,

- la figure 4 représente un mode de réalisation du procédé de codage et du procédé de décodage selon l'invention,

- la figure 5 représente des étapes du procédé de codage selon l'invention, tel que décrit dans ce mode de réalisation, - la figure 6 représente un niveau de décomposition en ondelettes de données de texture,

- la figure 7 représente une décomposition en ondelettes de données de texture,

- la figure 8 représente un arbre de décomposition en paquets d'ondelettes de données de texture,

- la figure 9 représente l'attribution de coûts aux éléments de cette décomposition en paquets d'ondelettes,

- la figure 10 représente un autre arbre de décomposition en paquets d'ondelettes de données de texture, - la figure 11 représente un format de représentation de données de texture codées selon l'invention,

- la figure 12 représente des étapes du procédé de décodage selon l'invention tel que décrit dans ce mode de réalisation.

Selon un mode préféré de réalisation de l'invention, on utilise le procédé de codage selon l'invention pour compresser une texture multidimensionnelle exprimée sous la forme d'une BTF en six dimensions. Cependant, la décomposition en ondelettes étant généralisable à un nombre quelconque de dimensions, le procédé selon l'invention est également applicable aux textures multidimensionnelles représentées différemment, par exemple sous forme de "Polynomial Texture Map" en quatre dimensions ou de "Time-varying BTF" en sept dimensions.

La BTF exprimant cette texture est le fruit d'un processus d'acquisition représenté à la figure 1. La BTF est échantillonnée selon un hémisphère de prises de vue. Dans le repère orthonormal d'origine O et d'axes X, Y et Z, chaque point de la texture est ainsi photographié sous une direction de point de vue de coordonnées polaires θ _v et φ _v , et selon une direction de la lumière de coordonnées polaires θι et φι.

Le tableau TAB de la figure 2 indique le nombre de photographies prises pour une latitude θ _v ou θι donnée. Ainsi pour une latitude θ _v égale à 15 degrés, l'angle φ _v varie de 72 degrés en 72 degrés, ce qui correspond à 5 photographies prises pour cette latitude. En sommant les valeurs du nombre d'échantillons sur la première colonne, il y a donc 80 valeurs de directions de point de vue et 80 valeurs de directions de la lumière utilisées pour l'échantillonnage, ce qui produit une BTF constituée de 6400 images.

La figure 3 illustre cette interprétation de la BTF: chacune des images I de ces 6400 images représente la texture en coordonnées paramétriques x et y, et correspond à une direction de point de vue (θ _Vl φ _v ) et une direction de la lumière (θι, q>ι).

Il est à noter que des données similaires de BTF sont téléchargeables sur le site de l'université de Bonn à l'adresse internet http://btf.cs.uni-

bonn.de/., le mode d'acquisition de ces données étant plus amplement détaillé dans l'article de G. Mϋller, G. H. Bendels et R. Klein intitulé "Rapid synchronous acquisition of geometry and BTF for cultural héritage artefacts", publié en novembre 2005 à l'occasion d'une conférence "6th International Symposium on Virtual Reality, Archaeology and Cultural Héritage (VAST)".

De plus, l'échantillonnage n'étant pas régulier et possédant des zones frontières, le procédé de codage selon l'invention utilise des ondelettes qui sont évidemment des ondelettes de type "seconde génération", car les ondelettes de première génération ne sont pas adaptées à ce type d'échantillonnage.

Les images I formant les données de la BTF sont stockées dans une base de données BDD représentée à la figure 4, le procédé de codage selon l'invention étant implémenté dans ce mode de réalisation de manière logicielle dans un ordinateur ORD ayant accès à cette base de données. Les calculs nécessaires au procédé de codage selon l'invention sont effectués dans le processeur CPU de l'ordinateur ORD. En variante, étant donnée l'importance de la taille des données sur lesquelles sont effectués les calculs nécessaires à leur codage, ces calculs sont effectués sur plusieurs ordinateurs fonctionnant en parallèle.

En référence à la figure 5, le procédé de codage selon l'invention est représenté sous la forme d'un algorithme comportant des étapes C1 à C3.

La première étape C1 est une réorganisation des données de la BTF dont les données sont initialement organisées suivant six dimensions, en un nombre de dimensions réduit, de manière à limiter la complexité des calculs.

Le choix de ce nombre de dimensions dépend des applications utilisant les données compressées, suivant que l'on privilégie des calculs moins complexes ou un taux de compression plus important. En effet plus on garde de dimensions plus on exploite la cohérence inter-dimensionnelle et plus le

1 es

taux de compression est important. Dans ce mode de réalisation, on choisit une réorganisation des données de la BTF en quatre dimensions, compromis entre rapidité et compression:

BTF(x, y, θ _v , φ _v , θ, , φ, ) = BTF(x, y, v, /) , où

- v est la projection des coordonnées polaires initiales θ _v et φ _v définissant initialement la direction d'un point de vue dans la BTF, sur une seule dimension,

- et / est la projection des coordonnées polaires initiales θ, et φ _t définissant initialement une direction de la lumière dans la BTF, sur une seule dimension.

En variante, les données de la BTF ne sont pas réorganisées, l'analyse en ondelettes se faisant alors sur six dimensions. Dans cette variante, on utilise par exemple deux types d'ondelettes: - des ondelettes en deux dimensions non-séparables afin d'adapter les filtres d'analyse à l'échantillonnage de la BTF suivant les directions de point de vue et de la lumière, - et des ondelettes en une dimension séparables pour l'analyse spatiale. Dans une autre variante de réalisation, les données initiales de la BTF sont réorganisées suivant trois dimensions suivant une décomposition appelée "réflectance field", c'est-à-dire qu'elle est exprimée par point de vue v et que la direction de la lumière est projetée sur une seule dimension:

BTF(x,y,θ _v ,φ _v ,θ _ι ,φ,) = {BTF _v (x,yJ)},Vv Dans une autre variante de réalisation, les données de la BTF sont réorganisées suivant cinq dimensions, la direction de la lumière étant projetée sur une seule dimension:

BTF(x,y,θ _v ,φ _v ,θ _ι ,φ _ι ) =BTF(x,y,θ _v ,φ _v ,l)

Cette dernière variante est intéressante par exemple lorsqu'on échantillonne plus la direction du point de vue que la direction de la lumière.

_{1 Q}

Lors de cette étape C1 de réorganisation des données de la BTF, la projection v correspondant au doublet (θ _v ,φ _v ) est classée par ordre croissant suivant θ _v et φ _v , c'est-à-dire que selon la dimension du point de vue v les images I sont classées dans l'ordre d'échantillonnage suivant: (0,0), (15,0),(15,72) _I ..., (75,345). De même la projection / correspondant au doublet (θ, ,φ _t ) est classée par ordre croissant suivant θ, et φ, .

En variante, les images I sont classées de manière à maximiser la corrélation entre deux images successives selon la direction de la lumière. Ce classement s'effectue par exemple de la manière suivante sur l'ensemble des images ayant en commun une même direction de point de vue:

- on choisit une image racine dans cet ensemble, par exemple l'image de projection / correspondant au doublet (0,0) en coordonnées polaires,

- on recherche ensuite itérativement l'image suivante à partir de l'image précédente, cette image correspondant à l'image minimisant la différence entre l'image précédente et l'ensemble des images non déjà classées.

Ce classement des images I par ordre de vraisemblance suivant l'axe correspondant à la projection /, permet dans la suite d'améliorer la compression lors de l'étape C3.

Il est de plus à noter que les données de la BTF sont codées à l'acquisition au format RVB. Or ce format de codage couleur ne permet pas d'exploiter le facteur perception à son maximum. En effet, l'œil humain étant particulièrement sensible au changement de luminance, on réalise de préférence dans cette étape C1 un changement d'espace de couleur RVB vers l'espace couleur YUV, où Y représente la luminance, et U et V la chrominance. Ce changement a un impact sur la suite du traitement car l'utilité d'une telle modification est de fournir une quantité d'information plus importante pour la luminance par rapport à la chrominance lors de la quantification à l'étape C3.

₂

La seconde étape C2 du procédé de codage est l'analyse en ondelettes des données ainsi réorganisées et reformatées, sur les quatre dimensions choisies à l'étape C1.

Il est à noter que l'expression "analyse en ondelettes" signifie que l'on décompose un signal en ondelettes ou en paquets d'ondelettes, par transformées successives en ondelettes. Une analyse en ondelettes recouvre donc au moins une décomposition en ondelettes.

Cette décomposition en ondelettes se fait suivant l'organisation choisie à l'étape C1. Comme indiqué plus haut, l'utilisation d'ondelettes de seconde génération est nécessaire du fait de l'irrégularité des intervalles d'échantillonnage et des zones frontières. Il est de plus à noter que même à supposer que l'on synthétise de nouveaux échantillons à l'étape C1 afin de régulariser ces intervalles, le domaine d'analyse restant toujours borné, les ondelettes de seconde génération restent nécessaires. Par simplicité dans ce mode de réalisation, on utilise une transformée en ondelettes simple de type "Unbalanced Haar Transform", d'ordre 1 , utilisant des ondelettes de seconde génération orthogonales, faciles à construire grâce à la méthode du "lifting scheme". Cette construction est détaillée dans un cours de W. Sweldens and P. Schrôder, intitulé "Building your own wavelets at home" et publié en 1996 par ACM SIGGRAPH dans "Wavelets in Computer Graphics". Ces ondelettes étant séparables, la décomposition est effectuée dimension par dimension ce qui permet de rester indépendant de l'organisation des données choisies à l'étape C1. De plus, en utilisant la base d'ondelettes de Haar, aucune adaptation aux frontières n'est nécessaire car la décomposition s'effectue sur deux échantillons successifs, autrement dit le calcul de la décomposition près des frontières ne nécessite pas l'ajout d'échantillons fictifs. Enfin, afin de simplifier cette décomposition et du fait de la réorganisation des données en quatre dimensions à l'étape C1 , on se permet de considérer dans cette étape C2 que les intervalles d'échantillonnage sont réguliers.

En variante, si les données de la BTF ont été réorganisées à l'étape C1 suivant un nombre de dimensions supérieur à quatre, on pondère les calculs lors de la décomposition en ondelettes afin de transformer un intervalle irrégulier en intervalle régulier et se ramener au cas de figure régulier. Cette pondération permet de rendre la décomposition en ondelettes plus fidèle à la réalité, c'est-à-dire que lors de la décompression les données décompressées permettent de synthétiser de nouvelles vues de texture très réalistes.

En variante, on utilise dans cette décomposition des ondelettes de base plus complexe, d'ordre supérieur. Cela permet, au prix cependant de calculs plus complexes et plus longs, de conserver malgré la compression une représentation de texture de très bonne résolution. On utilise par exemple des ondelettes bi-orthogonales, pratiques pour leur facilité de construction via la méthode du "lifting scheme", ou des ondelettes géométriques en considérant la configuration spatiale de la texture comme une géométrie dans un espace de même dimension. Par exemple, sur des données réorganisées à l'étape C1 sur trois dimensions, on utilise des ondelettes basées maillage utilisant comme primitive le quadrilatère, et en appliquant des techniques de subdivision classique telles que la technique "Butterfly". De manière générale, l'utilisation de base d'ondelettes ayant deux moments nuls est un bon compromis pour concilier qualité de restitution et vitesse de calcul.

Plus précisément, dans la variante principale de réalisation du procédé de codage selon l'invention, la décomposition en ondelettes à l'étape C2 se fait à chaque niveau j de décomposition selon le schéma de la figure 6. Soit S ^J le signal formé de l'ensemble des données {s^ ^J , _mn } du j-ième niveau de décomposition en ondelettes dans la base de Haar, des données réorganisées obtenues à la fin de l'étape C1 , et dans lequel:

- k est un indice représentant la k-ième valeur du signal selon l'axe de la coordonnée spatiale x ,

- p est un indice représentant la p-ième valeur du signal selon l'axe de la coordonnée spatiale y ,

- m est un indice représentant la m-ième valeur du signal selon l'axe de la projection / , - et n est un indice représentant la n-ième valeur du signal selon l'axe de la projection v .

La décomposition se fait dimension par dimension, par bloc de données correspondant chacun à l'ensemble des valeurs de la BTF selon une dimension, lorsqu'on fixe chacune des trois autres dimensions à une valeur donnée. L'ordre de traitement de ces dimensions est choisi en fonction de la corrélation des données de la BTF. La corrélation spatiale de la texture étant plus forte que sa corrélation lors d'un changement de direction de la lumière, elle même plus forte que lors d'un changement de direction de point de vue, on effectue la décomposition en ondelettes d'abord suivant l'indice k, puis suivant l'indice p, puis suivant l'indice m et enfin suivant l'indice n.

Ainsi lors de sa décomposition en ondelettes, le signal S ^J est soumis d'abord suivant l'axe de la coordonnée spatiale x , aux fonctions suivantes:

- l'opérateur s dit "split" sépare les données d'indice pair et les données d'indice impair dans la direction considérée, donc ici suivant l'indice k: j ' où k' est un indice entier défini par: k = 2k' lorsque k est pair et k ≈ 2k'+l lorsque k est impair,

- le filtre passe-bas h effectue les moyennes des données {s _k ^J _pmn } suivant la direction considérée, ce qui produit les données {s^ ^J _pmn } définies par:

CJ , OJ ç, _j h _ °(2k')pmn ^" * ^" {2k'+\)pmπ ^k'pnw ~ Z '

- et le filtre passe-haut g calcule les différences entre les données {s^ _mM } suivant la direction considérée, ce qui produit les données définies par:

J lS _ CJ _ CJ

" k'pmn ~~ ^Lj {2k'+l)pmn ^iJ (2k')pmn ^•

5 En réalité la décomposition s'effectue suivant la méthode du "lifting scheme", ce qui signifie pour la décomposition dans la base de Haar que l'on calcule d'abord la différence entre deux valeurs du signal S ^J puis on calcule la somme de ces deux valeurs à partir de cette différence:

i n A ^ιg — v ^j )pmn _ çJ

^{I KJ} " k'pmn ~ ° '(2k '+l °(2k')pmn <

J JS nι ιi<s V ^jh - <Z ^J | ^k 'P" ^m

P ^UIS ^ k'pmn ~ ^(2k')pm« ⁺ Z '

Cela permet au processeur CPU de stocker la valeur de d _k ^J f _pmn à l'endroit de la valeur de S( _2k , _+i)pmn , puis de stocker la valeur de S _k ^Jh _pmn à l'endroit de la valeur de S( _lk , _)pmn . Cela permet de sauver de la place mémoire au niveau du

15 processeur CPU. De plus le caractère local de la décomposition en ondelettes, ici sur deux échantillons successifs, permet à la décomposition d'être effectuée de manière "out of core", c'est-à-dire que l'ensemble des données à traiter n'est pas entièrement contenu dans la mémoire principale. Ce caractère permet également aux données d'être traitées en parallèle par 0 plusieurs processeurs. En outre, contrairement aux méthodes de l'art antérieur, le domaine d'analyse n'a pas besoin d'être segmenté pour être traité dans son entier.

Les données ) sont ensuite soumises aux mêmes fonctions mais suivant l'indice p: 5 - l'opérateur s sépare les données {s _k ^J ! _p ' _mn } et les données [d _k ^J ? _pnm } suivant leurs indices pairs ou impairs,

- le filtre h produit à partir des données {s _k ' _pmn } les données {s _k ^J ', _p . _mn } et à partir des données {d _k ^J f _pmπ } les données {d _k ^J f _p ', _mn },

- et le filtre g produit à partir des données \s^ ^J _pmn } les données ψ£ξ< _mn } et à partir des données les données où p' est un indice entier défini par: p = 2p' lorsque p est pair , et p = 2p'+l lorsque p est impair.

Puis l'ensemble des données {s#J, bfiJ.fa$J. et ^J obtenues sont à nouveau soumises aux mêmes fonctions, mais suivant l'indice m. Ainsi si l'on décrit seulement la décomposition des données

Ptyoui j ^'

- l'opérateur s sépare ces données suivant leurs indices pairs ou impairs: ) ' où m' est un indice entier défini par: m = 2m' lorsque m est pair , et m = 2m'+l lorsque m est impair,

- le filtre h produit à partir des données {s _k ^Jh _p , _mn }, les données {s _k ^J ! _p " ! _m ' , „} définies par:

- et le filtre g produit à partir des données définies par: _fj jhltg _ ςβh _ ςrjhh

"k'p'm n ~ °ty(2oi'+l>i -

Enfin l'ensemble des données ainsi obtenues par décomposition selon l'indice m sont décomposées suivant l'indice n. Si l'on décrit seulement la décomposition des données {s _k ^J _p ' ^h _m . _n }:

- l'opérateur s sépare les données d'indice pair et les données d'indice impair:

I ς jhhh \ _ lςjlιhh ςjhhh \

où «' est un indice entier défini par: n = 2n' lorsque n est pair et n = 2n'+l lorsque n est impair,

- le filtre h effectue les moyennes des données \S _k ^J _ym ' , _n } suivant l'indice n, ce qui produit les données {s/ _y ** _λ .} définies par: ojhhh , Qjhhh ς _j hhhh _ °k'p ^: mX2n') ^" * ^{" J} *',pW(2fl'+1) ^k'p'm'n' ~ j <

- et le filtre g calcule les différences entre les données {s^,.} suivant l'indice n, ce qui produit les données définies par:

7 jhhhg o jhhh rr jhhh ^a k'p'm'ri ~ °4>'m'(2n'+l) ~ °tym'(2n') ^•

L'ensemble des données produites lors de cette dernière décomposition suivant l'indice n forme le résultat de la décomposition en ondelettes du signal S ^J , soit les données du j moins unième niveau de décomposition en ondelettes des données obtenues à la fin de l'étape C1. On distingue dans ce résultat les données basse fréquence de basse résolution, et les autres données qui forment un signal d ^J~ι de plus haute fréquence.

Dans une variante de réalisation, la décomposition détaillée ci-dessus est une décomposition en ondelettes classique du signal initial S ^J formé des données obtenues à l'étape C1. Dans cette décomposition représentée à la figure 7, seul le signal de basse fréquence S ^J~ι est re-décomposé au prochain niveau de décomposition, le signal de détail d ^J~ι étant conservé. Ainsi au J moins unième niveau de décomposition, le signal S ^{J "x} est décomposé en ondelettes et produit un signal S ^J~2 de plus basse fréquence

que le signal S ^J ' , et un signal d ^J~2 de plus basse fréquence que le signal d ^J~ \ puis au niveau de décomposition suivant le signal S ^J~2 est lui-même décomposé en ondelettes et ainsi de suite. La dernière décomposition en ondelettes sur le signal S ¹ produit les signaux d° et S ⁰ . Les données obtenues à la fin de l'étape C1 étant les images I codées suivant le format YUV et classées suivant 80 directions de point de vue et 80 directions de la lumière, en supposant que ces images sont de résolution 256*256, on s'arrête par exemple au bout de trois niveaux de décomposition en ondelettes. Le résultat de l'analyse en ondelettes est alors formé des signaux S ⁰ , et d° à d ^J~ \ où J vaut trois. Le signal 5° de basse fréquence contient 10*10*32*32 couleurs codées dans l'espace couleur YUV.

Dans la variante principale de réalisation du procédé de codage selon l'invention, afin de coder la texture de manière optimale, on décompose en fait dans cette étape C2 les données obtenues à la fin de l'étape C1 en paquets d'ondelettes. Une telle décomposition permet de décomposer non seulement récursivement les signaux S ^J de basse fréquence, mais aussi les signaux d ^J de haute fréquence. Cette décomposition est représentée sur l'arbre de la figure 8. La racine de l'arbre correspond au signal S ^J initial contenant les données obtenues à la fin de l'étape C1. Le niveau suivant est le résultat d'une itération de transformation en ondelettes, c'est-à-dire le signal S ^J~ï de basse fréquence et le signal d ^J'x de haute fréquence. Puis la décomposition récursive de ces signaux complète les niveaux inférieurs de l'arbre. Ainsi la décomposition du signal S ^J~X donne deux signaux S ^J~2 et d ^J~2 , tandis que la décomposition du signal d ^J'x donne également deux signaux Sύ ^J \ et d^ .

Cette décomposition en paquets d'ondelettes permet de choisir un arbre de décomposition optimal suivant un critère donné, tel que l'entropie du codage, un seuil prédéterminé, ou la distorsion générée par le codage. Pour cela on attribue une fonction de coût à chaque décomposition en ondelettes, c'est-à-

dire à chaque nœud de l'arbre représenté à la figure 8. Cette fonction de coût correspond au critère choisi pour optimiser l'arbre.

Par exemple, si on choisit de privilégier les décompositions par rapport au nombre de valeurs en dessous d'un seuil, la valeur de la fonction coût au nœud de décomposition correspondant au signal S ^J vaut:

Avec P(S^ _n ) = 1 si I S _U ^J _mn |> t et P(Sh _1n J = 0 sinon, où t correspond à ce seuil.

Puis on compare la somme des coûts des enfants de chaque parent de l'arbre avec le coût de ce parent. Si cette somme est moins élevée que le coût du parent, on garde les décompositions des enfants, sinon s'arrête à la décomposition parentale dans la suite du procédé de codage.

Par exemple sur l'arbre de la figure 9, où l'on a remplacé chaque nœud de la figure 8 par le coût de sa décomposition, la décomposition en paquets d'ondelettes s'arrêtera sur la branche gauche de l'arbre aux signaux S ^J~2 et d ^J~2 , qui ne seront pas décomposés, car la somme de leurs coûts est supérieure ou égale au coût de leur signal parent S ^J~ι .

Dans ce mode de réalisation de l'invention, on choisit d'utiliser un critère d'entropie pour pondérer l'arbre des décompositions: la valeur de la fonction coût au nœud de décomposition correspondant au signal S ^J vaut:

Cette fonction coût définit l'entropie de Shannon, qui mesure la quantité d'information, c'est-à-dire de coefficients différents dans une décomposition. Ce critère est utile au procédé de codage selon l'invention car on garde ainsi la décomposition de plus faible coût entropique.

En variante, dans le cas où la BTF codée selon l'invention est initialement exprimée sur des nombres entiers, l'analyse en ondelettes

effectuée à cette étape C2 est une décomposition entière en ondelettes ou une décomposition entière en paquets d'ondelettes. Une telle méthode est décrite dans l'article "Réversible image compression via multi-resolution représentation and prédictive coding", de A. Said et W. Pearlman, publié en 1993 à l'occasion d'une conférence internationale "Visual Communications and Image Processing". Cela optimise encore l'analyse en ondelettes en limitant la taille du résultat de cette analyse. En effet, les données issues de l'analyse sont ainsi représentées avec moins de ressources, la taille en octets d'un entier étant inférieure à celle d'un nombre décimal. Il est à noter que toute base d'ondelettes est modifiable pour effectuer une telle décomposition entière. Par exemple, la transformation par rondelette de Haar du signal S ^J suivant l'indice k devient :

JiZ _ C J _ CJ ^u k'lmn ~ °(2k'+\)lmn °(2k')lmn ' d ^Jg puis S 'k*'imn — = O S (L2k',) _] b _lm r, _n + "**""

2 où [uj désigne la valeur entière d'une division u par défaut.

Enfin l'étape C3 du procédé de codage selon l'invention est la compression des données obtenues à la fin de l'étape C2, résultat de l'analyse en ondelettes des données de la BTF réorganisées et reformatées à l'étape C1. Dans ce mode de réalisation, cette compression utilise un codage dit

"zerotree", qui exploite la structure arborescente de la décomposition en ondelettes. Cette technique de codage connue de l'Homme du métier est par exemple détaillée dans les articles suivants:

- "An embedded wavelet video coder using three-dimensional set partitioning in hierarchical trees (SPIHT)" de B.-J. Kim et W.A.

Pearlman, publié en 1997 à l'occasion d'une conférence internationale "Data Compression Conférence",

_2Q

- et "An embedded hierarchical image coder using zerotrees of wavelet coefficients", de J. M. Shapiro, publié en 1993 à l'occasion d'une autre conférence internationale "Data Compression Conférence". Le principe de cette technique de codage est de considérer que les coefficients basse-résolution contenus dans les signaux S ^J sont grands par rapport aux coefficients de détail contenus dans les signaux d ^J , et que plus j est petit, plus les coefficients de détail sont grands. Cela permet d'utiliser la dépendance inter-échelles de ces coefficients, c'est-à-dire entre deux niveaux de décomposition, pour effectuer le codage des données. Plus précisément, on lie un coefficient de détail au niveau le plus grossier à un nombre de coefficients situés au niveau supérieur dans une même direction, puis ces coefficients sont à leur tour liés au niveau suivant et ainsi de suite. Ce nombre est égal à une puissance de deux, cette puissance étant égale à la dimension de l'espace d'analyse.

Par exemple, si la décomposition en paquets d'ondelettes retenue est celle présentée sur la figure 10, c'est-à-dire que les données obtenues à la fin de l'étape C2 sont celles des signaux S ^J' \ d ^J' \ d ^J~2 , S^ _x , dû ^J l _x et </£?, , un coefficient du signal ύ? ^J~3 est lié à 16 coefficients du signal d ^J~2 . II est à noter que la méthode de codage "zerotree" étant usuellement appliquée aux décompositions en ondelettes, quelques adaptations sont nécessaires pour l'appliquer à une décomposition en paquets d'ondelettes, comme détaillé dans l'article "Adaptive wavelet packet basis sélection for zerotree image coding", de N. Rajpoot, R. Wilson, F. Meyer et R. Coifman, publié en 2003 dans la revue "Institute of Electrical and Electronics Engineers (IEEE) Transactions on image processing".

En effet la hiérarchie au sens du codage « zerotree », n'est plus la même que dans une décomposition classique en ondelettes. Certaines règles pour le rattachement des coefficients d'un niveau à un autre doivent donc être

₃ Q

ajoutées pour conserver une réelle décroissance des coefficients au fur et à mesure des niveaux de décomposition.

Ainsi sur la figure 10, si le signal d ^J~2 avait été re-décomposé sur un dernier niveau J-3, on lierait un coefficient du signal d ^J' ^ non pas à 16 coefficients du signal d ^J~2 , lequel ne serait pas conservé à la fin de l'étape

C2, mais à un coefficient dans chacun des 16 signaux issus de la décomposition du signal d ^J~2 .

De même, en appliquant la même règle que ci-dessus pour le signal d ^J~2 , un coefficient du signal d ^J~2 devrait être liée à un coefficient dans chacun des 16 signaux issus de la décomposition du signal d ^J~ι . Or le signal S^ ₁ issu de cette décomposition est lui-même re-décomposé, notamment en un signal Si _/ ^~ -ι de niveau plus grossier que celui du signal d ^J~2 . Afin de respecter le principe du codage "zerotree", on lie les coefficients des signaux S^ ₁ et d^ , non pas aux coefficients du signal d ^J~2 , mais aux coefficients du signal d ^J~% . Les valeurs des coefficients des signaux S^ ₁ et dû ^J \ seront ainsi codées en fonction de celles, théoriquement plus grandes, des coefficients du signal d ^J~3 . Cette quantification intrinsèque réalisée par le codage "zerotree" est aussi appelée "quantification par approximation successive".

A l'issue de ce codage par "zerotree", on obtient à la fin de l'étape C3 un flux de bits qui code la décomposition en paquets d'ondelettes effectuée à l'étape C2. Les données ainsi obtenues sont de taille beaucoup moins importante qu'à la fin de l'étape C2. En effet, le fait d'exploiter la décroissance des coefficients à travers les échelles, ajouté au fait que l'analyse en ondelettes produit de nombreux coefficients proches de zéro, permet à la méthode de codage "zerotree" d'obtenir un fort taux de compression. De plus, les données obtenues sont organisées par ordre d'importance, comme représenté à la figure 11. Les données ZTO codent des coefficients correspondant au niveau le plus grossier de détail, tandis que les données

ZT 1 codent des coefficients de détail à un niveau un peu moins grossier, les données ZT2 des coefficients de détail à un niveau encore plus fin, et ainsi de suite. Les données ZTO correspondent à des informations qui décrivent le plus les données originales. On dispose donc d'une représentation progressive de la texture dans la mesure où les données situées après les données ZTO permettent de raffiner progressivement la représentation grossière de la texture contenue dans ces données ZTO. Ainsi, lorsqu'on transmet seulement les premières données de cette représentation obtenue à la fin de l'étape C3, on obtient une représentation grossière de la texture. En variante, dans cette étape C3, au lieu d'utiliser un codage "zerotree" on utilise un codage de type "Huffman ¹¹ dynamique combiné à une quantification scalaire non-uniforme. Notamment la composante Y des données issues de l'étape C2 est moins quantifiée que les composantes U et V. Le pas de cette quantification est par exemple fixé de manière adéquate pour une taille des données compressées fixées. Ce procédé, appelé "Rate Allocation", est utilisé dans la norme "Joint Photographie Experts Group (JPEG) 2000". Pour cela, on calcule par exemple le pas de quantification itérativement jusqu'à atteindre le taux de compression voulu. Ce posttraitement s'avère utile par exemple lors de la transmission des données compressées sur un réseau à un débit fixé. De plus, une telle quantification est adaptable afin de quantifier moins certaines zones d'intérêt de la texture, si de telles zones sont identifiées, par rapport aux autres zones de moindre intérêt.

Cette variante permet de diminuer la complexité des calculs lors de la décompression, mais est beaucoup moins efficace en termes de taux de compression que la variante principale de réalisation de l'invention. Il est à noter qu'il est aussi possible de coupler le codage "zerotree" de la variante principale de l'invention avec un codage de type "Huffman" dynamique, mais cela n'améliorerait que très peu le taux de compression des données obtenues.

Le procédé de décodage selon l'invention est maintenant décrit en liaison avec les figures 4 et 12. Les données obtenues à la fin de l'étape C3 sont envoyées par l'ordinateur ORD à un terminal distant T sur un réseau de communication RES. Le flux de données F correspondant contient la représentation des données codées par "zerotree" et organisées par ordre d'importance telle que décrite plus haut en relation avec la figure 11.

A la réception du flux de données F, le terminal T stocke en mémoire toutes les données reçues, ou seulement les premières données, par exemple les données ZTO, ZT 1 et ZT2 si le terminal T a une capacité mémoire limitée, ou si une panne de communication interrompt l'envoi des données juste après l'envoi des données ZT2.

Le terminal T, après décodage canal du signal transportant le flux de données F, décode les données reçues suivant les étapes D1 à D3 représentées à la figure 12. L'étape D1 est la décompression des données reçues. Pour cela le terminal T utilise un algorithme de décodage "zerotree" inverse de celui utilisé à l'étape C3 pour le codage, c'est-à-dire qu'il utilise les mêmes règles d'association des coefficients d'un niveau de résolution à un autre pour retrouver les données issues de la décomposition en paquets d'ondelettes. Si seules les données ZTO, ZT1 et ZT2 sont décompressées, seuls les coefficients des premiers niveaux de résolution de la décomposition en paquets d'ondelettes de l'étape C2 sont obtenus.

Par ailleurs, lors du codage "zerotree", le caractère local de l'analyse en ondelettes est conservé. Ainsi lors du décodage, le terminal T est en mesure de ne décoder qu'une partie des données reçues, afin par exemple de ne rendre la texture que sous certaines directions de points de vue ou certaines directions de la lumière.

L'étape D2 est la synthèse en ondelettes des données décompressées à l'étape D1. Le codage "zerotree" étant fonction de la structure de l'arbre de décomposition en paquets d'ondelettes retenu à l'étape C2, le terminal T reconstitue aisément tout ou partie des données de texture réorganisées et

reformatées obtenues à la fin de l'étape C1. Il suffit pour cela d'effectuer des transformées de Haar inverses dans l'ordre de la décomposition en paquets d'ondelettes, dimension par dimension.

Enfin l'étape D3 est la réorganisation en six dimensions des données obtenues à la fin de l'étape D2. Le terminal T obtient ainsi une texture exprimée sous la forme d'une BTF ₁ utilisable directement pour effectuer son rendu sur un écran. Si seules les données ZTO, ZT1 et ZT2 ont été synthétisées à l'étape D2, cette BTF est en fait une représentation grossière de la texture compressée selon l'invention.