TRIDIMENSIONNEL

La présente invention relève du domaine du traitement d'images. Elle concerne plus particulièrement les procédés de compression et de décompression d'image nécessaires à leur transmission minimisant la bande passante nécessaire.

Contexte de l'invention et problèmes posés

Les dernières années ont vu une explosion du nombre d'applications logicielles utilisant des images 3D : jeux vidéo en ligne, télémédecine, systèmes d'information géographique, etc. Le traitement de ces applications est rendu possible par la généralisation de processeurs graphiques de plus en plus rapides, ainsi que par l'apparition d'outils puissants de modélisation en trois dimensions et de dispositifs de captation directe de formes tridimensionnelles d'objets. Les contenus 3D générés sont ainsi de plus en plus riches et détaillés.

Ces contenus sont généralement définis par un ensemble de points ou sommets ("vertex") connectés sous forme de facettes, elles-mêmes délimitées par des arêtes ("edges"). Un tel arrangement est dénommé maillage M ("mesh" en langue anglaise).

Vis-à-vis de ces données dont le volume évolue rapidement avec les nouvelles applications des images 3D, les réseaux de transmission d'information restent extrêmement hétérogènes et leur bande passante, quoique croissante, est faible au regard du nombre et du volume des fichiers qui doivent être transmis sur ces réseaux. Enfin, les plateformes destinées à recevoir des images d'objets tridimensionnels sont de plus en plus variées : téléphones mobiles, tablettes, micro-ordinateurs, assistants personnels etc.

On comprend donc que l'échange efficace de modèles tridimensionnels complexes sur ces réseaux et ces machines devient un enjeu crucial pour de nombreuses applications industrielles, dont par exemple le rendu photoréaliste, la visualisation médicale, et la simulation.

FEU I LLE DE REM PLACEM ENT (RÈG LE 26) Par ailleurs, certaines applications utilisant des modèles tridimensionnels, notamment dans le domaine médical et l'ingénierie, exigent une récupération sans perte de la connectivité (i.e. pas de re-maillage) du maillage M et un contrôle précis de l'erreur maximale ou moyenne induite par la compression de sa géométrie (i.e. positions et attributs associés aux sommets de M).

Ces considérations expliquent le besoin de procédés de compression de maillages tri-dimensionnels efficaces, adaptés particulièrement à des maillages très denses, avec un encodage du maillage M sans re-maillage et quasiment sans perte d'information ("near-lossiess" en langue anglaise), tout en fournissant des fonctions avancées telles que l'évolutivité ("scalability" en langue anglaise) spatiale et en qualité.

On définit ici l'évolutivité spatiale comme la capacité à adapter la résolution du maillage M aux performances de rendu du terminal de restitution de l'image et à la bande passante disponible pour la transmission.

De même, l'évolutivité en qualité est définie comme la capacité à raffiner progressivement la précision des attributs et des coordonnées, au fur et à mesure que le flux de données est décodé.

On rappelle que le codage de connectivité est dit sans perte s'il préserve la triangulation initiale du maillage M original.

Plusieurs techniques sont déjà connues dans le domaine de la compression de maillage tridimensionnel.

Parmi celles-ci, on peut citer en particulier le procédé de maillage progressif ("progressive mesh" ou PM en langue anglaise) [Hoppe'96] (Hugues Hoppe, « Progressive meshes », International Conférence on Computer Graphics and Interactive Techniques, 99-108, 1996). Dans celui-ci, illustré par la figure 1 , le maillage M évolue par division d'un sommet en deux sommets ou fusion de deux sommets en un seul, et la modification conjointe des arêtes et facettes associées (ajout ou suppression de deux facettes). Ce procédé permet de générer un ensemble de maillages intermédiaires appelés niveaux de détail (en langue anglaise Level of Détails, LoD). Cette représentation est adaptée à une transmission progressive du modèle 3D ainsi qu'au rendu selon le point de vue (an langue anglaise « View dépendent rendering »). Cependant, les performances en compression de ce procédé sont limitées, et il ne s'applique qu'à des variétés orientées (« Oriented manifold » en anglais).

Dans un autre procédé connu sous le nom Progressive Forest Split (PFS) [Taubin'98] (G. Taubin,, A. Guéziec, W. Horn, F. Lazarus, « Progressive forest split compression », International Conférence on Computer Graphics and Interactive Techniques, 123-132, 1998), le maillage est raffiné en appliquant simultanément des opérations de division à un ensemble de sommets du maillage. Dans l'exemple illustré par la figure 2, un sommet est remplacé par un ensemble de trois sommets et quatre facettes nouvelles sont générées en conséquence. En regroupant les opérations de division de sommets, l'approche PFS permet de les coder de façon plus compacte au prix d'une granularité de niveaux de détails plus grossière. Ici encore, on atteint une transmission et un rendu progressif. La performance en compression est meilleure que l'algorithme de maillage progressif PM, mais la qualité des niveaux de détails des modèles intermédiaires est plus faible.

Une autre stratégie est connue sous le nom de colorisation de facettes ("Patch Coloring" PC) [Cohen-Or'99] (D. Cohen-Or, D. Levin, O. Remez , « Progressive Compression of Arbitrary Triangular Meshes », IEEE Visualization Conférence Proceedings, 67-72, 1999.). Dans ce procédé, on utilise une stratégie de simplification de facettes illustrée par la figure 3. Ce procédé offre de bonnes performances de compression et il est applicable à tous types de maillages. Cependant, ici encore la qualité des niveaux de détails des modèles intermédiaires est sous-optimale.

Encore une autre stratégie de simplification est connue sous le nom de méthode de décimation guidée par les valences ("Valence-based decimation approach") [Alliez'01 ] (P. Alliez, M. Desbrun, « Progressive encoding for lossless transmission of 3D meshes », ACM Siggraph Conférence Proceedings, 198-205, 2001 ). Dans cette approche, la stratégie de décimation des sommets exploite la connectivité des sommets, afin de minimiser, à chaque niveau de détails intermédiaire, la dispersion de la valence des sommets autour de la valeur six. Les performances en compression de cette méthode sont bonnes, mais elle génère des niveaux de détails de mauvaise qualité dans le cas de maillages échantillonnés de manière irrégulière. De plus, son application est limitée à des maillages particuliers dits variétés orientées.

On peut encore citer la compression par structure d'octree [Peng'05] (J. Peng, C.-C. J. Kuo, « Geometry-guided progressive lossless 3D mesh coding with octree (OT) décomposition », ACM Transactions on Graphics, Vol. 24(3), 609-616, 2005.) qui offre de bonnes performances de compression et qui est applicable à tout type de maillages. Cependant, cette méthode fournit des niveaux de détails de faible qualité dans le cas de maillages 3D lisses.

Enfin, le codage spectral [Karni'01] (Z. Karni, C. Gotsman, « Spectral compression of mesh geometry », International Conférence on Computer Graphics and Interactive Techniques, 279-286, 2000) compresse en monorésolution (de l'anglais "single rate") la connectivité du maillage. Cette information est ensuite exploitée afin de décomposer le signal de géométrie selon une base de fonctions adaptées au maillage. Les performances de compression du codage spectrale sont bonnes dans le cas de maillages 3D lisses. Cependant, sa complexité de calcul est élevée. De plus, ce procédé supporte uniquement une évolutivité en qualité (capacité à raffiner progressivement la précision des attributs et coordonnées, au fur et à mesure que le flux de données est décodé).

En résumé, les techniques de compression exploitant la connectivité

(i.e. PFS, PC et codage à base de valence) permettent des gains en compression par rapport à l'approche originale de maillage progressif au prix de niveaux de détails intermédiaires de qualité sous-optimale, La compression par structures d'octree utilise un critère de simplification qui n'est pas adapté aux maillages. Enfin, le codage spectral est complexe et ne permet pas une évolutivité spatiale.

Dans [Karni'01 ], les auteurs proposent d'exploiter la technique de Tourna et Gotsman (TG) [Touma'98] (C.Touma, C. Gotsman, « Triangle Mesh Compression », International Conférence on Graphics Interface, 24-34, 1998) afin de coder en mono-résolution (i.e. pas d'évolutivité) l'information de connectivité. Le codeur TG code la connectivité du maillage sous forme d'une séquence de valences. Ce codeur gère des variétés orientées. L'approche TFAN [Mammou'09] (K. Mamou, T. Zaharia, F. Prêteux, « TFAN: A low complexity 3D mesh compression algorithm », Computer Animation and Virtual Worlds, Vol. 20(2-3), 343-354,2009) généralise la technique TG à tout type de maillages 3D. Objectifs de l'invention

L'objectif de la présente invention est alors de proposer un procédé de compression permettant une évolutivité spatiale et en qualité, avec un codage sans perte de connectivité générique (i.e. variétés ou non, orientées ou non, ouvertes et fermées) et un codage quasiment sans perte (avec un taux d'erreur maximale/moyenne contrôlée) de la géométrie du maillage.

Exposé de l'invention

A cet effet, l'invention vise sous un premier aspect un procédé de codage / décodage de maillage tridimensionnel de points ou sommets connectés sous forme de facettes, délimitées par des arêtes, le maillage M étant défini par des données de connectivité T et des données de géométrie G, le procédé comportant :

- une étape de codage sans perte des données de connectivité T, en information de connectivité encodée Te,

- une étape de génération itérative d'une hiérarchie de maillage progressif, c'est-à-dire un ensemble de maillages de niveaux de détails progressifs, P (M ^* ),

- une étape de génération d'une approximation lisse par morceaux M ^* du maillage original M à partir de la connectivité T du maillage, cette approximation lisse M ^* étant décrite par :

a. l'information de connectivité encodée Te (la liste des triangles du maillage M),

b. un petit nombre N de points de contrôle c = (c _h ) _ksil , préalablement définis, et

c. un ensemble d'indices (leurs références dans le maillage) S d'arêtes dites arêtes saillantes du maillage M, préalablement identifiées. - la hiérarchie progressive de maillage, PM(M ^* ) étant utilisée pour calculer une prédiction des erreurs d'approximation de M ^* par rapport au maillage original M. Selon une mise en œuvre avantageuse, le maillage approximé M ^* est généré selon une technique par Laplacien, généralisée au cas de maillages comportant des arêtes saillantes, en ce qu'on définit une matrice Laplacienne L dans laquelle des poids (α , β) sont associés aux arêtes spéciales (saillantes ou de bord) et aux arêtes non spéciales, permettant de pondérer de façons différentes la contribution des sommets voisins d'un point selon leur appartenance aux deux ensembles des voisins topologiques spéciaux, définis comme partageant avec lui soit une arête de bord, soit une arête saillante, et normaux / _s ^* et /„ ^* . Avantageusement, dans ce cas, on choisit comme valeurs a=100 et β=1 .

Selon une mise en œuvre particulière, la hiérarchie de maillage progressif PM(M ^* ), est générée par décimation itérative du maillage approximé M ^* en n'autorisant que des opérations réversibles de contraction de demi- arêtes, jusqu'à aboutir à un maillage de base M ₀ , le maillage original M étant alors construit comme le maillage de base M ₀ associé à un ensemble d'opérations de raffinement par des divisions de sommets Selon une mise en œuvre avantageuse, le procédé comporte également une étape dans laquelle :

- les erreurs d'approximation prédites sont encodées dans l'ordre inverse de PM(M ^* ),

- l'erreur d'approximation e _v est décomposée en une composante normale au maillage M ^* : e _v ⁿ et deux composantes tangentielles e et e transmises progressivement au décodeur 200. - lors du décodage, les erreurs d'approximation prédites sont décodées progressivement à partir du niveau de détail le plus bas M ₀ vers le niveau de détail le plus élevé M,

- les positions décodées des sommets sont calculées.

Selon une autre mise en œuvre avantageuse, éventuellement utilisée conjointement, le procédé comporte en outre des étapes :

- de codage de versions de niveaux de détails intermédiaires de connectivité, et de leur transmission progressive,

- de transmission de la version la plus grossière M ₀ de la hiérarchie de maillage (avec connectivité et géométrie) en utilisant un codeur monorésolution de type TFAN,

- et, de façon itérative, de prédiction de la géométrie du niveau de détail suivant M _i+1 à partir des sommets de M,, les sommets de M, étant exploités comme points de contrôle pour M _i+1 ,

- la connectivité C(i+1) de M _i+1 et une information auxiliaire, notée Map(i→i+1), qui décrit les correspondances entre les sommets de M, et de M _i+1 , ayant été transmises préalablement,

- un calcul d'une version approximée de M _i+1 , notée M _i+1 ^* étant réalisée par le décodeur en exploitant M,, Map(i→i+1) et C(i+1),

- d'utilisation de M _i+1 ^* comme prédicteur pour M _i+1 , les erreurs de prédiction étant codées/décodées progressivement,

L'invention vise sous un second aspect un procédé de décodage pour procéder tel qu'exposé plus haut, tel que lors de la reconstruction des positions de tous les sommets, on fixe à zéro les erreurs d'approximation prédites non encore disponibles, et en ce qu'au fur et à mesure de l'interprétation du flux binaire, les erreurs de prédiction sont décodées et exploitées afin de corriger progressivement les positions des sommets du maillage.

L'invention vise sous encore un autre aspect un encodeur pour maillage tridimensionnel, comportant :

- des moyens de recevoir et de mémoriser : - des données de connectivité T,

- des données de géométrie G,

- des références de "points de contrôle" Cs sélectionnées par l'utilisateur (ces points permettent de générer une version approximée du maillage original M, un sous-ensemble représentant 1 % des sommets du maillage),

- un encodeur de connectivité de type mono-résolution, c'est-à-dire sans évolutivité, adapté pour l'encodage sans perte les données de connectivité T, en données de connectivité compressées Te,

- un module de quantification destiné à traiter les données de géométrie G, de manière à réduire le volume d'informations à transmettre par sommet,

- un module de sélection de points de contrôle utilisant les données de géométrie quantifiées GQ, ainsi que les données de connectivité compressées Te et les données de points de contrôle utilisateur Cs, pour fournir des points de contrôle sélectionnés C,

- un module de détection des arêtes saillantes adapté à utiliser les données de connectivité compressées Te et les données de géométrie,

- un module de binarisation pour produire les indices des arêtes saillantes compressés Se, et les indices et positions compressés des points de contrôle Ce,

- un module d'approximation de maillage adapté à intégrer les données de points de contrôle sélectionnés C et de données de connectivité compressées Te, ce module d'approximation de maillage générant un maillage approximé M*,

- un module de décimation de maillage, adapté à fournir un maillage progressif PM(M*) à partir du maillage approximé M* et les données de géométrie quantifiées GQ,

- un module de prédiction des erreurs d'approximation e _v , adapté à utiliser les données issues du module de décimation de maillage

dont sont issues après compression par un encodeur arithmétique des données compressées de prédiction d'erreurs e _vc ,

et des moyens de transmettre : - des données de connectivité compressées Te,

- des indices des arêtes saillantes compressés Se,

- des indices et positions compressés des points de contrôle Ce,

- et des données compressées de prédiction d'erreurs e _vc .

Selon un mode de réalisation avantageux, le module d'approximation de maillage est adapté à générer le maillage approximé M ^* selon une technique par laplacien, généralisée au cas de maillages comportant des arêtes saillantes.

Selon un mode de réalisation particulier, l'encodeur comporte des moyens de générer une matrice laplacienne L dans laquelle des poids (α , β) sont associés aux arêtes spéciales (saillantes ou de bordure) et aux arêtes non spéciales, permettant de pondérer de façons différentes la contribution des sommets voisins d'un point selon leur appartenance aux deux ensembles des voisins topologiques spéciaux, définis comme partageant avec lui soit une arête de bord, soit une arête saillante, et normaux / _s ^* et /„ ^* .

L'invention vise sous encore un autre aspect un décodeur pour maillage tridimensionnel, comportant :

- des moyens de recevoir et de mémoriser :

- des données de connectivité compressées Te,

- des indices des arêtes saillantes compressés Se,

- des indices et positions compressés des points de contrôle Ce, - et des données compressées de prédiction d'erreurs e _vc ,

- un décodeur de connectivité mono-résolution, adapté à fournir des données de connectivité reconstituées T à partir des données de connectivité compressées Te

- un module de binarisation inverse adapté à fournir des indices des arêtes saillantes S', des indices et positions des points de contrôle C, et des données de prédiction d'erreurs de compression e _v - un module d'approximation de maillage adapté à combiner des données de connectivité reconstituées T , des indices d'arêtes saillantes S', et des indices et positions des points de contrôle C,

- un module de décimation de maillage adapté à utiliser le maillage approximé M ^* pour obtenir un maillage progressif PM(M ^* )

- un module de prédiction inverse d'erreurs d'approximation adapté à combiner les données de maillage progressif PM(M ^* ) aux données de prédiction d'erreurs de compression e _v ' ,

- un module de quantification inverse adapté à fournir, sur la base des résultats du module de prédiction inverse d'erreurs d'approximation, des données de géométrie reconstituées G'.

Brève description des figures

La description qui va suivre, donnée uniquement à titre d'exemple d'un mode de réalisation de l'invention, est faite en se référant aux figures annexées qui représentent :

Figure 1 (déjà citée) : une représentation schématique d'un procédé de maillage progressif,

Figure 2 (également déjà citée) : une représentation schématique d'un procédé de maillage de type "Progressive Forest Split",

Figure 3 (également déjà citée) : une représentation schématique d'un procédé de maillage de type "Patch Coloring",

Figure 4 : un logigramme représentant un encodeur selon l'invention, Figure 5 : un logigramme représentant un décodeur selon l'invention, Figures 6 et 7 : des familles de courbes mettant en évidence le gain permis par l'utilisation d'un procédé selon l'invention,

Figure 8 : une représentation schématique des erreurs de prédiction entre le maillage original et le maillage approximé,

Figure 9 : un schéma de principe d'une variante de procédé utilisant des niveaux de détails intermédiaires de connectivité.

Description détaillée d'un mode de réalisation de l'invention Le procédé tel que décrit est destiné à être mis en œuvre par des moyens électroniques, que ce soit sous forme d'un composant dédié ou sous forme de logiciel exécuté par un processeur d'ordinateur de type classique connu de l'homme du métier.

On considère un maillage M destiné, dans le présent exemple, à permettre la représentation d'un personnage. Le procédé est ici appliqué à des maillages statiques ou à des trames particulières d'une séquence de maillages animés,

La figure 4 illustre les éléments logiques composant un encodeur 100 correspondant à une mise en œuvre non limitative de l'invention.

Trois types de données servent d'entrée à l'encodeur 100 :

- des données de connectivité T,

- des données de géométrie G,

- et éventuellement des références de "points de contrôle" Cs sélectionnées par l'utilisateur (ces points permettent de générer une version approximée du maillage original M).

Conformément au procédé décrit ici à titre d'exemple non limitatif, les données de connectivité T sont encodées en utilisant un encodeur de connectivité 1 1 de type mono-résolution _; connu de l'homme du métier et non détaillé ici. Il en résulte des données de connectivité compressées Te.

Les données de géométrie G sont traitées dans un module de quantification 12 ("quantization"). Le but de ce module de quantification est de réduire le volume d'informations à transmettre en diminuant le nombre de bits par sommet.

Puis les données de géométrie quantifiées GQ issues de ce module de quantification 12, ainsi que les données de connectivité compressées Te fournies par l'encodeur de connectivité 1 1 et les données de points de contrôle Cs sont traitées dans un module de sélection de points de contrôle 13 pour fournir des points de contrôle sélectionnés C.

Les données de connectivité compressées Te et les données de géométrie G sont fournies à un module de détection des arêtes saillantes 16, dont les résultats sont compressés au sein d'un encodeur arithmétique 17 pour produire les indices des arêtes saillantes compressés Se-

De même, les points de contrôle sélectionnés C sont compressés par ce même encodeur arithmétique 17 pour fournir les indices et positions compressés des points de contrôle Ce.

Un module d'approximation de maillage 21 intègre les données de points de contrôle sélectionnés C et de données de connectivité compressées Te. Ce module d'approximation de maillage 21 génère un maillage approximé M ^* .

Le maillage approximé M ^* alimente un module de décimation de maillage 22. Les données de géométrie quantifiées GQ ainsi que le maillage progressif PM(M ^* ) issu du module 22 servent d'entrée à un module de prédiction 23 des erreurs d'approximation e _v , dont sont issues après compression par un encodeur arithmétique (non illustré sur la figure 4) des données compressées de prédiction d'erreurs e _vc .

On comprend que quatre types de données sont fournis en sortie de l'encodeur 100 :

- des données de connectivité compressées Te,

- des indices des arêtes saillantes compressés Se,

- des indices et positions compressés des points de contrôle Ce,

- et des données de prédiction d'erreurs de compression e _vc .

Ces données sont transmises au fur et à mesure par un réseau de communication de type connu de l'homme de l'art, et non détaillé ici. Ce réseau de communication sort en tant que tel du cadre de l'invention.

La figure 5 illustre alors les éléments logiques constituant un décodeur 200 selon l'invention.

Ses données d'entrée sont les données de sortie de l'encodeur 100. Les données de connectivité compressées Te sont traitées dans un décodeur de connectivité mono-résolution 31 , qui fournit des données de connectivité reconstituées T. On note que T est identique à T à une permutation des sommets et des facettes de M près. Les indices des arêtes saillantes compressés Se, les indices et positions compressés des points de contrôle Ce, et les données compressées de prédiction d'erreurs e _vc sont traitées par un décodeur arithmétique 37 ce qui fournit des indices des arêtes saillantes S', des indices et positions des points de contrôle C', et des données de prédiction d'erreurs de compression e _v '.

Les données de connectivité reconstituées T sont combinées aux indices des arêtes saillantes S', et aux indices et positions des points de contrôle C', dans un module d'approximation de maillage 41 . Celui-ci fournit un maillage approximé M ^* qui alimente un module de décimation de maillage 42.

Les données PM(M ^* ) issues du module de décimation de maillage 42 sont à leur tour combinées aux données de prédiction d'erreurs de compression e _v ' dans un module de prédiction inverse d'erreurs d'approximation 43. Un module de quantification inverse 32 fournit finalement en sortie, sur la base des résultats du module de prédiction inverse d'erreurs d'approximation, des données de géométrie reconstituées G'.

Les données de sortie du décodeur 200 sont donc les données de connectivité reconstituées T et les données de géométrie reconstituées G'.

Mode de fonctionnement

Le procédé de compression-décompression selon l'invention tire profit du fait que l'information de connectivité T représente moins de 20% du flux complet de données compressées représentant le maillage M. De ce fait, il compresse cette information de connectivité T en mono-résolution en utilisant l'encodeur de connectivité 1 1 . La connectivité Te du maillage M, encodée sans perte, est alors utilisée pour compresser de façon évolutive l'information de géométrie G.

Plus précisément, le procédé, tel que décrit ici, exploite la connectivité T du maillage de manière à dériver une approximation lisse M ^* du maillage original M.

Cette approximation lisse M ^* est entièrement décrite par les trois entrées du module d'approximation de maillage 21 , à savoir : a. l'information de connectivité encodée Te (c'est à dire la liste des triangles du maillage M),

b. un petit nombre N de points de contrôle c = V^n. ₎ . et c. un ensemble d'indices (c'est-à-dire leurs références dans le maillage) S d'arêtes dites arêtes saillantes du maillage M (voir définition plus loin).

Rappelons que les points de contrôle sont choisis par l'utilisateur et/ou par une procédure automatique afin d'assurer que le maillage approximé M ^* soit le plus fidèle possible au maillage original M.

Plusieurs stratégies automatiques peuvent être adoptées afin de choisir l'ensemble des points de contrôle. A titre d'exemple de mise en œuvre, si aucun point de contrôle n'est fournit par l'utilisateur on choisi un premier point de contrôle au hasard. On approxime le maillage en utilisant les points de contrôle déjà définis (i.e. soit les points de contrôle définis par l'utilisateur soit le point de contrôle choisi au hasard). De façon itérative, de nouveaux points de contrôle sont ensuite sélectionné. Plus précisément, le sommet présentant une erreur d'approximation maximale est sélectionné à chaque itération. Ce processus est réitéré jusqu'à atteindre le nombre de points de contrôle souhaité. Il s'agit d'un paramètre de codage, qui est générale de l'ordre de 1 - 3% du nombre de sommets du maillage original M.

Le présent procédé de codage-décodage utilise, dans ce module d'approximation de maillage 21 , une technique d'approximation de maillage par laplacien, connue en soi et décrite notamment dans [Chen'05] (D. Chen, D. Cohen-Or, O. Sorkine, and S. Toledo, "Algebraic analysis of high-pass quantization," ACM Transactions on Graphics, vol. 24, pp. 1259-1282, 2005).

Cette technique est ici généralisée au cas de maillages comportant des arêtes saillantes. On définit une matrice laplacienne L comme suit :

v o .;5 e {i, ... _. , v + c} x {% ,. v}, i = dans laquelle :

- i _s ^* est l'ensemble des voisins topologiques spéciaux du sommet / ^' , définis comme partageant avec lui soit une arête de bord (c'est à dire adjacente à exactement un triangle), soit une arête saillante,

- /„ ^* est l'ensemble des voisins topologiques "normaux" du sommet / ^' définis comme les voisins topologiques n'appartenant pas à / _s ^* ,

- \i _n ^* \ et |/ _s ^* | désignent les nombres d'éléments de /„ ^* et / _s ^* respectivement,

- a et β sont des poids respectivement associés aux arêtes spéciales (saillantes ou de bordure) et aux arêtes non spéciales. Il est à noter que si les poids a et β sont égaux, ou si il n'y a pas d'arêtes saillantes, on obtient exactement la définition de la matrice laplacienne proposée par [Chen'05]. Dans le cas de maillage avec arêtes saillantes, les poids a et β permettent de pondérer de façons différentes la contribution des sommets voisins selon leur appartenance aux deux ensembles / _s ^* et /„ ^* .

Dans le présent exemple de mise en œuvre, un choix envisagé est de fixer a=100 et β=1 . Ceci implique qu'un sommet / ^' situé sur un bord du maillage ou sur une arête saillante est cent fois plus influencé par ses voisins spéciaux i _s ^* que par ses voisins non spéciaux i _n ^* .

Différentes procédures peuvent être envisagées pour la détection d'arêtes saillantes. Une solution possible est de définir comme arêtes saillantes toutes les arêtes présentant un angle de dièdre plus grand qu'une valeur seuil prédéterminée (par exemple ττ/6). Ces arrêtes résultent en général des discontinuités tangentielles de la surface. La technique [Chen'05] ne gère pas de façon efficace ce type de surfaces, étant donné que les arrêtes saillantes sont lissées. Le procédé ici proposé permet en revanche de mieux conserver ces caractéristiques. Comme dans [Chen'05], la matrice de taille (V x 3) des positions approximées des sommets, notée P ^:i = est calculée en résolvant le système linéaire suivant : ΐΤί }Ρ' = B. (2)

La matrice B de dimension (Vx 3) est donnée par :

(3)

où Pj(1), Pj(2) et Pj(3) représentent respectivement les coordonnées cartésiennes originelles x, y and z du sommet i.

Une hiérarchie de maillage progressif, notée PM(M*), est alors générée par décimation du maillage approximé M* en n'autorisant que des opérations de contraction de demi-arêtes (en langue anglaise « Half-edge collapse »). La technique de maillage progressif PM (déjà citée et illustrée par la figure 1 ), représente le maillage original M comme un maillage de base M ₀ associé à un ensemble d'opérations de raffinement par des divisions de sommets.

Le maillage de base M ₀ est obtenu par décimation successive du maillage M par des opérations de contraction d'arêtes. Le choix de la séquence d'opérations de contraction d'arêtes à appliquer au maillage M est guidé par une stratégie de préservation de forme.

Plus précisément, selon cette stratégie, à chaque étape du processus de décimation, une fonction de coût de l'application de chaque opération de contraction d'arête est évaluée de façon à choisir l'opération qui introduit la plus faible distorsion de forme comme décrit dans [Garland'97] (M. Garland, P. Heckbert. «Surface Simplification Using Quadric Error Metrics», International Conférence on Computer Graphics and Interactive Techniques, 209-216, 1997).

Comme discuté dans [Popovic'97] (J. Popovic, H. Hoppe, «Progressive simplicial complexes», ACM SIGGRAPH Conférence, 217-224, 1997.), chaque opération de contraction d'arête est réversible à condition de stocker :

- l'indexe du sommet à diviser,

- sa position et ses attributs, ainsi que - les modifications opérer sur les triangles/arrêtes qui lui sont incidentes topologiquement.

En exploitant ce fait, un ensemble d'opérations de raffinement, noté

(pspl iii) _&Î1

(K étant le nombre de niveaux de détails dans la hiérarchie de maillage, i.e. M=M _K ) peut être calculé et exploité pour régénérer progressivement le maillage M en partant du maillage de base M ₀ . Plus précisément, en appliquant l'opération vsplii^à M ₀ , on obtient le niveau de détail M?. En appliquant vsplit à M? on obtient M ₂ . Ainsi de suite jusqu'à reconstruire le maillage original M. A chaque étape ! e de ce processus de raffinement un nouveau sommet v _s (l) est rajouté au niveau de détail />·/;_ : et le voisinage du sommet est modifié (cf. figure 1 ). L'ordre d'insertion des sommets ¾(!} est appelé ordre du maillage progressif. Notons que la liste des voisins du sommet y-if» change entre les deux niveaux de détails ^et , (cf. figure 1 ). Dans, ce qui suit on parlera de voisins topologiques d'un sommet par rapport à un niveau de détail l

Le procédé proposé construit la hiérarchie de maillage progressif PM(M ^* ) en considérant M ^* (et non M). Ce choix est motivé par le fait que seule cette information est à la fois disponible au codeur 100 et au décodeur 200. Le maillage progressif PM(M ^* ) est ensuite exploité de manière à calculer une prédiction des erreurs d'approximation de M ^* par rapport à M. L'encodeur tel que décrit compresse les erreurs d'approximation prédites dans l'ordre inverse de PM(M ^* ),

À chaque étape, l'erreur d'approximation prédite e„ associée au sommet est calculée comme suit :

¾ = ίΛ - ∑, , · ) - ΙΛ ^" - ∑ _W e,' K (4) dans laquelle v* représente l'ensemble des voisins topologiques de v dans le niveau de détail courant de PM(M*), et (£ _. ,) _, sont les positions reconstruites par le décodeur 200 comme décrit ci-dessous (voir équation (7)). L'erreur d'approximation e _v obtenue est alors décomposée en une composante normale au maillage M* e _v ⁿ et deux composantes tangentielles e et eJdéfinies par:

e!f = e„ . ;,, e . = \. . ÷ ;;, εζ = s, _, . (5)

où n _v ^* est la normale du maillage M ^* au sommet v, et r et t sont deux vecteurs choisis pour former une base orthonormale directe avec n _v ^* .

Finalement, e _v ⁿ , e et e sont quantifiées et encodées arithmétiquement pour tous les sommets v du maillage. Les erreurs d'approximation compressées, notées e _vc , sont ensuite transmises de façon progressive au décodeur 200.

Le décodeur 200 décompresse progressivement les erreurs d'approximation prédites à partir du niveau de détail le plus bas (i.e. M ₀ ) vers le niveau de détail le plus élevé (i.e. M _K ). Ici, à chaque étape, les trois composantes e _v ⁿ , e et eJ sont arithmétiquement décodées (dans le module 37) et puis utilisées (dans le module 43) pour reconstruire l'erreur d'approximation comme suit :

Finalement, les positions décodées (c'est-à-dire la géométrie reconstituée G sont données par :

Il est à noter qu'en encodant et décodant les sommets en ordre inverse de la hiérarchie progressive de maillage PM(M*), le présent procédé d'encodage / décodage garantit que lors du traitement du sommet v, les positions de tous ses voisins ont déjà été reconstruites.

Par ailleurs, en utilisant la structure maillage progressif PM(M*), le codeur/décodeur tel que décrit ici permet directement d'assurer la fonctionnalité d'évolutivité spatiale (capacité à adapter la résolution du maillage M aux performances de rendu du terminal de restitution de l'image et à la bande passante disponible pour la transmission).

L'évolutivité spatiale est assurée en exploitant la structure de maillage progressif PM(M*) et le fait que les maillages M et M ^* ont la même connectivité. Grâce à cette dernière propriété, les opérations sont calculées sur M ^* et appliquées à M. Le décodeur procède comme suit. Tout d'abord, M ^* est simplifié comme décrit précédemment afin de générer PM(M ^* ) avec un maillage de base qui contient un seul sommet t¾ (dans le cas général un sommet par composante connexe). La position de s¾ est directement décodée en appliquant l'équation (7) et en supposant que -s.?* est vide (i.e. pas de voisin).

Ensuite, l'opération yspfi est appliquée. La position du nouveau sommet inséré ¾est reconstruite grâce à l'équation (7) et en considérant son voisinage topologique dans M . Ce processus est réitéré pour tous les sommets restant jusqu'à décodage de tout le maillage ou lorsque un seuil de qualité prédéfini est atteint.

L'évolutivité en qualité (raffinage progressif des positions au fur et à mesure du décodage du flux) est obtenue en reconstruisant les positions de tous les sommets, tout en fixant dans l'équation (7) à zéro les erreurs d'approximation prédites non encore disponibles. Au début du processus de décodage, aucune de ces erreurs de prédiction n'est disponible. En supposant ces erreurs nulles, le décodeur fait l'hypothèse que chaque sommet à décoder subi le même déplacement que celui calculé sur le maillage approximé M ^* (voir figure 8). Bien sûr une telle hypothèse introduit des erreurs de reconstruction. Au fur et à mesure du l'interprétation du flux binaire, les erreurs de prédiction sont décodées et exploitées (i.e. en appliquant l'équation (7)) afin de corriger progressivement les positions des sommets du maillage. A la fin de la transmission, toutes les positions ont été corrigées. A ce stade, seules les erreurs de quantification demeurent.

Avantages de l'invention

On comprend que le procédé selon l'invention transfère, du codeur vers le décodeur, une partie du calcul de géométrie du maillage, ce qui permet notamment une économie en bande passante. Le décodeur gère la simplification du maillage. Une idée clé du procédé est d'approximer l'objet par une faible proportion (typiquement 1 -3%) de points du maillage définis comme des points de contrôle.

Dans l'art antérieur, l'approximation de maillage par approche laplacienne repose sur un critère qui ramène chaque sommet le plus proche possible du barycentre de ses voisins. Cette pondération uniforme des contributions des voisins a pour inconvénient de lisser les formes saillantes. Dans le présent procédé, on utilise un barycentre pondéré des arêtes saillantes, ce qui retranscrit plus fidèlement la forme du modèle.

Tel qu'il a été décrit, le procédé de compression de maillage 3D multi- résolution utilise une stratégie basée sur une approximation de forme, de manière à compresser et transmettre progressivement l'information de géométrie, qui représente environ 80% du volume total d'informations à transmettre.

Cette stratégie permet en même temps un encodage sans perte de la connectivité, une compression quasiment sans perte de la géométrie et des attributs, et des évolutivités spatiale et en qualité.

Pour donner un ordre de grandeur des gains, la géométrie du maillage M définie par la position de chaque sommet est usuellement codée sur 15 à 20 bpv ("bits per vertex"), et la connectivité entre sommets, c'est-à-dire la liste des facettes, représente 1 à 4 bpv, soit moins de 20% du flux total de données représentant le maillage M.

Les figures 6 et 7 illustrent des erreurs de position (en ordonnées) en fonction de la taille du flux binaire compressé (exprimé en octets) pour divers pas de quantifiation, et qui comparent trois méthodes de codage/décodage dont une méthode TG [Touma'98], la méthode TFAN [Mammou'09] et le présent procédé. Comme on le voit sur ces figures, un gain de 20 à 70% en termes de volume de données est obtenu par utilisation du procédé décrit par rapport aux techniques antérieures. Dans le cadre des exigences actuelles en termes de qualité et de bande passante, un tel gain est extrêmement significatif. Variantes de l'invention

La portée de la présente invention ne se limite pas aux détails des formes de réalisation ci-dessus considérées à titre d'exemple, mais s'étend au contraire aux modifications à la portée de l'homme de l'art.

Le procédé précédemment décrit code en mono-résolution la connectivité du maillage original. Cela suppose que le décodeur doit reconstruire le maillage approximé M ^* en résolvant le système linéaire de taille (VxV) décrit par l'équation (2) (V êtant le nombre de sommet de M). Le coût de calcul induit peut alors être prohibitif dans le cas de maillages denses et pour des terminaux à capacités limitées. Afin de pallier cette limitation, une extension possible consiste à introduire des niveaux de détails intermédiaires de connectivité comme illustré figure 9. Ici, des versions intermédiaires sont calculées par le codeur puis transmises progressivement en exploitant l'approche décrite plus haut. Dans la figure 9, trois niveaux de détails M ₀ , M? et M ₂ sont considérés. La version la plus grossière M ₀ (avec connectivité et géométrie) est tout d'abord transmise en exploitant directement le codeur mono-résolution TFAN [Mammou'O ]. Les sommets de M ₀ sont ensuite exploités afin de prédire la géométrie du niveau de détails suivant M?. Plus précisément, les sommets de M ₀ sont exploités comme points de contrôle pour Μή. Cela nécessite également l'envoie de la connectivité C(1) de M? et d'une information auxiliaire, notée Map(0→1), qui décrit les correspondances entre les sommets de M ₀ et de M?. En exploitant M ₀ , Map(0→1) et C(1), le décodeur calcule (comme décrit précédemment) une version approximée de M _1t notée M . M est ensuite exploité comme prédicteur pour M?. Les erreurs d'approximation prédites sont codées/décodées progressivement comme décrit dans l'approche originale. La même approche est ensuite exploitée afin de coder/décoder M ₂ à partir de M _? .