CORRESPONDANTS

Domaine de l'invention

La présente invention se rapporte de manière générale au domaine du codage et du décodage de signaux scalaires ou vectoriels en dimension arbitraire.

Plus précisément, l'invention concerne la technique du maillage qui est utilisée dans le cadre du codage et du décodage des signaux précités par projection sur des bases de fonction.

L'invention trouve des applications dans tous les domaines où il est souhaitable de réduire le nombre d'informations nécessaires pour représenter efficacement un tel signal, pour le stocker et/ou le transmettre, ainsi que pour le décompresser. Par exemple, l'invention peut être utilisée pour le codage/décodage d'images multi-vues (Multi View Video) ou d'une séquence de te))es images, une image multi-vues étant adaptée pour représenter un ou plusieurs objets en perspective dans une scène.

Art antérieur

A l'heure actuelle, plusieurs techniques de maillage ont déjà été proposées. L'une des plus connues est notamment celle décrite dans le document « Michael Lounsbery, Tony D. DeRose, and Joe Warren, « Multiresolution analysis for surfaces of arbitrary iopological type » (ACM Transaction on Graphics, Vol 16, N ° 1, pp. 34-73, Jaiuary 1997). Une telle technique utilise des transformations en ondelettes qui permettent de représenter un maillage comme une succession de détails ajoutés à un maillage de base. Plus précisément, cette technique de maillage consiste à :

- représenter une variété de dimension 2 ou 3 à l'aide d'une suite de maillages M ₀ , ΜΙ , .. . ΜΜ , M,, M _i+ , ..., M _s (0<i≤S) formés respectivement d'une pluralité de simplexes, un maillage courant considéré M, constituant une subdivision du maillage immédiatement précédent M , - appliquer une transformation en ondelettes à chaque subdivision, délivrant un ensemble de coefficients d'ondelettes D ₀ , D _; D _S -

1 -

De nombreuses stratégies de subdivision ont été proposées pour le maillage de variétés en dimension 2, c'est-à-dire lorsque le domaine est localement homéomorphe à une partie de E ² . Ces stratégies se généralisent rarement en dimension supérieure, ou, lorsque la généralisation est explicite, mènent souvent à des pertes de propriétés du maillage résultant.

Les simplexes qui forment un maillage considéré présentent une dimension n prédéterminée. Ainsi, un maillage considéré est subdivisé :

- en plusieurs segments en dimension 1 ,

- en plusieurs triangles en dimension 2,

- en plusieurs tétraèdres en dimension 3,

- en plusieurs pentatoptes en dimension 4,

- etc....

Dans le cas où le maillage est subdivisé en plusieurs triangles en dimension 2, la technique de subdivision la plus souvent utilisée est la quadrisection. Cette dernière consiste à partager chaque triangle formant un maillage considéré, en quatre nouveaux triangles, en créant une nouvelle arête reliant les milieux des trois arêtes originales. Un maillage de ce type est particulièrement stable notamment parce qu'il permet de :

- conserver les particularités de la face triangulaire mère sur les faces triangulaires filles,

- conserver le même nombre de nouvelles faces triangulaires à chaque subdivision.

Cette subdivision ne s'applique toutefois pas naturellement lorsqu'une subdivision du maillage en plusieurs simplexes de dimension supérieure à 2 est souhaitée.

Dans le cas par exemple d'une subdivision d'un maillage en plusieurs tétraèdres en dimension 3, telle que décrite dans le document Martin Bertram, « Biorthogonal wavelets for subdivision volumes », In Proceedings of the seventh ACM symposium on Solid modeling and applications (SMA Ό2), ACM, New York, NY, USA, pp 72-82, la quadrisection précitée est alors interprétée comme une insertion pour chaque face en dimension 2 de ce maillage, d'un nouveau sommet sur cette face et d'un nouveau sommet sur chacune des arêtes de cette face.

Un inconvénient de la technique décrite dans ce document est qu'il subsiste un hyper-polyèdre central qu'il est difficile de décomposer, et certainement pas de façon canonique comme c'est le cas pour le maillage triangulaire. Il en résulte que les simplexes créés à chaque subdivision dégénèrent au bout d'un nombre peu élevé de subdivisions, c'est-à-dire que les mailles s'aplatissent de plus en plus au fil des subdivisions entraînant une déformation trop importante du maillage.

Objet et résumé de l'invention

Un des buts de l'invention est de remédier à des inconvénients de l'état de la technique précité.

A cet effet, selon un premier aspect, la présente invention concerne un procédé de codage d'un signal défini sur une variété de dimension n (n>1 ), comprenant les étapes consistant à :

- représenter la variété précitée à l'aide d'une suite de maillages

Mo, Mi , ... Mi-i , M,, Mj+1 M _s (0<i≤S) formés respectivement d'une pluralité de simplexes de dimension n, un maillage courant considéré M, constituant une subdivision du maillage immédiatement précédent Μ _Μ ,

- appliquer une transformation en ondelettes à chaque subdivision, délivrant un ensemble de coefficients d'ondelettes D ₀ , D-i , D _S -

- coder les coefficients d'ondelettes délivrés.

Le procédé de codage selon l'invention est remarquable en ce que l'étape de représentation précitée est mise en œuvre de la façon suivante :

- dans le cas où i est pair, la subdivision du maillage M, pour obtenir le maillage M _i+ est effectuée selon une première règle de subdivision prédéterminée,

- dans le cas où i est impair, la subdivision du maillage M, pour obtenir le maillage M _i+ i est effectuée selon une deuxième règle de subdivision prédéterminée.

Une telle disposition permet avantageusement de proposer un schéma d'ondelettes qui est basé sur une stratégie de subdivision qui soit simple et qui procure une hiérarchie de maillage stable et générique, indépendamment de la dimension de la variété dans laquelle sont définis les signaux à coder.

Dans le cas par exemple où le signal à coder représente la géométrie d'un objet en perspective dans une scène, le procédé selon l'invention permet avantageusement de coder le signal selon une meilleure fidélité géométrique ou visuelle avec cet objet, compte tenu du fait que le maillage de l'objet obtenu subit moins de déformations que dans le cas de l'art antérieur précité.

Selon un autre mode de réalisation particulier :

- la première règle de subdivision consiste à ajouter un sommet à l'intérieur de chaque simplexe du maillage M,,

- la deuxième règle de subdivision consiste, pour chaque simplexe du maillage M,, à :

• déterminer une face dudit simplexe qui est commune à un autre simplexe,

· supprimer la face déterminée de façon à obtenir un nouveau simplexe,

• ajouter un sommet à l'intérieur du nouveau simplexe obtenu.

Une telle disposition permet une reproductibilité aisée du maillage au fil des subdivisions successives, sans déformation du maillage et tout en créant le même nombre de mailles à chaque subdivision.

De par la simplicité des règles de subdivision utilisées, l'implantation du procédé de codage selon l'invention est très facile à mettre en œuvre et les temps de calcul sont beaucoup moins lourds que dans l'art antérieur précité.

Selon un autre mode de réalisation particulier, le sommet ajouté conformément à la première règle de subdivision est le barycentre des sommets du simplexe considéré.

Selon un autre mode de réalisation particulier, le sommet ajouté conformément à la deuxième règle de subdivision est le barycentre des sommets de la face commune entre deux simplexes.

Une telle disposition permet une simplification des calculs, ce qui permet d'accélérer notablement le procédé de codage selon l'invention. Selon un autre mode de réalisation particulier, l'étape d'application d'une transformation en ondelettes à chaque subdivision consiste à appliquer un filtre sur un maillage courant M, à subdiviser, un tel filtre étant défini à partir d'une matrice A ¹ qui est la concaténation de deux matrices P ¹ et Q ¹ , telles que :

- un élément a _k, i (k>0 et l>0) considéré de la matrice P ¹ a pour valeur :

• 1/b _k si les sommets sk, et si, du maillage M, d'indices respectifs k et I, avec 0<k≤Ni 0≤Ι≤Ν,, sont reliés par une arête du maillage M,, b _k étant le nombre de sommets partageant une arête avec le sommet sk, du maillage M,,

• 0 sinon, un élément a' _k ,i (k>0 et l>0) considéré de la matrice Q' a pour valeur :

• 1 si k=l,

u(s/ )

, . si les sommets sk, et si, du maillage M, d'indices respectifs k et I sont reliés par une arête du maillage M,,

• 0 sinon, ou :

- u est une fonction qui associe à un sommet sk, du maillage M, le nombre de simplexes auxquels il appartient, et

- v est une fonction qui associe à un sommet sk, du maillage M, l'ensemble des sommets du maillage M, qui partagent une arête avec ledit sommet sk,.

Une telle disposition permet d'obtenir un schéma d'ondelettes ayant de bonnes propriétés puisqu'il contient au moins un moment nul.

Les différents modes ou caractéristiques de réalisation précités peuvent être ajoutés, indépendamment ou en combinaison les uns avec les autres, aux étapes du procédé de codage tel que défini ci-dessus.

De façon correspondante, l'invention concerne un dispositif de codage d'un signal défini sur une variété de dimension n (n>1 ), comprenant : - un module adapté pour représenter la variété précitée à l'aide d'une suite de maillages M ₀ , M-i, ...Mj-i , M,, M _i+ , ..., M _s (0<i≤S) formés respectivement d'une pluralité de simplexes de dimension n, un maillage courant considéré M, constituant une subdivision du maillage immédiatement précédent Μ _Μ ,

- un module adapté pour appliquer une transformation en ondelettes à chaque subdivision, délivrant un ensemble de coefficients d'ondelettes D ₀ , D-i , D _S -i ,

- un module adapté pour coder les coefficients d'ondelettes délivrés.

Un tel dispositif de codage est remarquable en ce que le module de représentation est adapté pour :

- dans le cas où i est pair, mettre en œuvre la subdivision du maillage M, pour obtenir le maillage M _i+ selon une première règle de subdivision prédéterminée,

- dans le cas où i est impair, mettre en œuvre la subdivision du maillage M, pour obtenir le maillage M _i+ selon une deuxième règle de subdivision prédéterminée.

Un tel dispositif de codage est notamment apte à mettre en œuvre le procédé de codage précité.

Selon un deuxième aspect, l'invention concerne un procédé de décodage d'un flux de données représentatif d'un signal défini sur une variété de dimension n (n>1 ) qui a été précédemment codé, comprenant les étapes consistant à :

- décoder les données du flux, délivrant un ensemble de coefficients d'ondelettes,

- reconstruire la variété précitée par application d'une transformée inverse en ondelettes aux coefficients en ondelettes décodés dudit ensemble, à l'aide d'une suite de maillages M ₀ , Mi ,...Mj-i , M _j , M _j+ ,..., M _s (0<i≤S) formés respectivement d'une pluralité de simplexes de dimension n, un maillage courant considéré M _j constituant une subdivision du maillage immédiatement précédent M i .

Un tel procédé de décodage est remarquable en ce que l'étape de reconstruction est mise en œuvre de la façon suivante : - dans le cas où i est pair, la subdivision du maillage M, pour obtenir le maillage M _i+ est effectuée selon une première règle de subdivision prédéterminée,

- dans le cas où i est impair, la subdivision du maillage M, pour obtenir le maillage M _i+ est effectuée selon une deuxième règle de subdivision prédéterminée.

Selon un mode de réalisation particulier :

- la première règle de subdivision consiste à ajouter un sommet à l'intérieur de chaque simplexe du maillage M,,

- la deuxième règle de subdivision consiste, pour chaque simplexe du maillage M,, à :

• déterminer une face du simplexe qui est commune à un autre simplexe,

• supprimer la face déterminée de façon à obtenir un nouveau simplexe,

• ajouter un sommet à l'intérieur du nouveau simplexe obtenu.

Selon un autre mode de réalisation particulier, le sommet ajouté conformément à la première règle de subdivision est le barycentre des sommets du simplexe considéré.

Selon un autre mode de réalisation particulier, le sommet ajouté conformément à la deuxième règle de subdivision est le barycentre des sommets de ladite face commune entre deux simplexes.

Selon un autre mode de réalisation particulier, l'étape d'application d'une transformation inverse en ondelettes consiste à appliquer un filtre sur un maillage courant M, à subdiviser, un tel filtre étant défini à partir d'une matrice A' qui est la concaténation de deux matrices P' et Q', telles que :

- un élément (k>0 et l>0) considéré de la matrice P' a pour valeur :

· 1 /bk si les sommets sk, et si, du maillage M, d'indices respectifs k et I, avec 0<k≤Ni 0≤Ι≤Ν,, sont reliés par une arête du maillage M,, b _k étant le nombre de sommets partageant une arête avec le sommet sk, du maillage M,, • 0 sinon,

- un élément a' _k ,i (k>0 et l>0) considéré de la matrice Q ¹ a pour valeur :

• 1 si k=l,

· ^— ^u ( ^sk 0 _S j | _es sommets sk, et si, du maillage M, d'indices respectifs k et I sont reliés par une arête du maillage M,,

• 0 sinon, où :

- u est une fonction qui associe à un sommet sk, du maillage M, le nombre de simplexes auxquels il appartient, et

- v est une fonction qui associe à un sommet sk, du maillage M, l'ensemble des sommets du maillage M, qui partagent une arête avec ledit sommet sk,.

Les différents modes ou caractéristiques de réalisation précités peuvent être ajoutés, indépendamment ou en combinaison les uns avec les autres, aux étapes du procédé de décodage tel que défini ci-dessus.

De façon correspondante, l'invention concerne un dispositif de décodage d'un flux de données représentatif d'un signal défini sur une variété de dimension n (n>1 ) qui a été précédemment codé, comprenant :

- un module adapté pour décoder les données du flux, délivrant un ensemble de coefficients d'ondelettes,

- un module adapté pour reconstruire la variété précitée par application d'une transformée inverse en ondelettes aux coefficients en ondelettes décodés dudit ensemble, à l'aide d'une suite de maillages M ₀ , M-ι , ...Μ _ΐ , M,, M _i+ i , ... , M _S (0<i≤S) formés respectivement d'une pluralité de simplexes de dimension n, un maillage courant considéré M, constituant une subdivision du maillage immédiatement précédent MM .

Un tel dispositif de décodage est remarquable en ce que ledit module de reconstruction est adapté pour : - dans le cas où i est pair, mettre en œuvre la subdivision du maillage M, pour obtenir le maillage M _i+ selon une première règle de subdivision prédéterminée,

- dans le cas où i est impair, mettre en œuvre la subdivision du maillage M, pour obtenir le maillage M _i+ selon une deuxième règle de subdivision prédéterminée.

Un tel dispositif de décodage est notamment apte à mettre en œuvre le procédé de décodage précité.

Selon un troisième aspect, l'invention concerne un programme d'ordinateur comportant des instructions pour mettre en œuvre :

- le procédé de codage selon l'invention, lorsqu'il est exécuté sur un ordinateur,

- le procédé de décodage selon l'invention, lorsqu'il est exécuté sur un ordinateur.

Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable.

L'invention vise également un support d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre de l'un des procédés de codage ou de décodage selon l'invention, tels que décrits ci- dessus.

L'invention vise également un support d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre du procédé de codage ou de décodage selon l'invention, tels que décrits ci- dessus.

Le support d'enregistrement peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une clé USB ou un disque dur. D'autre part, le support d'enregistrement peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet.

Alternativement, le support d'enregistrement peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé de codage ou de décodage précité.

Le procédé de décodage, le dispositif de codage, le dispositif de décodage, les programmes d'ordinateur et les supports d'enregistrement correspondants précités présentent au moins les mêmes avantages que ceux conférés par le procédé de codage selon la présente invention.

Brève description des dessins

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 des étapes du procédé de codage selon l'invention,

- la figure 2 représente un mode de réalisation d'un dispositif de codage selon l'invention,

- les figures 3A et 3B représentent respectivement une opération de synthèse permettant le passage du maillage M ₀ de granularité la plus grossière au maillage M _s de granularité la plus fine et une opération d'analyse permettant le passage du maillage M _s de granularité la plus fine au maillage Mo de granularité la plus grossière,

- les figures 4A et 4B représentent un exemple de subdivision permettant le passage d'un maillage d'indice pair à un maillage suivant d'indice impair, le maillage étant formé de simplexes de dimension 3,

- les figures 5A à 5C représentent un exemple de subdivision permettant le passage d'un maillage d'indice impair à un maillage suivant d'indice pair, le maillage étant formé de simplexes de dimension 3,

- la figure 6 représente un dispositif de décodage selon l'invention, - la figure 7 représente des étapes du procédé de décodage selon l'invention,

- la figure 8 représente un exemple d'image multi-vues pouvant être codée/décodée selon l'invention.

Description détaillée d'un mode de réalisation de la partie codage

Un mode de réalisation de l'invention va maintenant être décrit, dans lequel le procédé de codage selon l'invention est utilisé pour coder un signal f défini sur une variété de dimension quelconque n (n>1 ).

De façon connue en tant que telle, une variété de dimension n est un espace qui ressemble localement à R ⁿ .

Le procédé de codage selon l'invention est représenté sous la forme d'un algorithme comportant des étapes C1 à C6 représentées à la figure 1.

Selon le mode de réalisation de l'invention, le procédé de codage selon l'invention est implémenté dans un dispositif de codage CO représenté à la figure 2.

Comme illustré en figure 2, un tel dispositif de codage comprend une mémoire MEM_CO, une unité de traitement UT_CO équipée par exemple d'un microprocesseur μΡ et pilotée par un programme d'ordinateur PG_CO qui met en œuvre le procédé de codage selon l'invention. A l'initialisation, les instructions de code du programme d'ordinateur PG_CO sont par exemple chargées dans une mémoire RAM (non représentée) avant d'être exécutées par le processeur de l'unité de traitement UT_CO.

Au cours d'une étape C1 représentée à la figure 1 , il est procédé à la représentation de ladite variété à l'aide d'une suite de maillages M ₀ , Μι, ...Μμι , M,, M _i+ , ..., M _s (0<i≤S) formés respectivement d'une pluralité de simplexes de dimension n, un maillage courant considéré M, constituant une subdivision du maillage immédiatement précédent Μ _Μ .

Le maillage M ₀ est appelé classiquement maillage de base et comprend une pluralité de sommets s0 ₀ , s1 ₀ , ..., sN ₀ , avec N ₀ ≥1 .

Le maillage M _s constitue le maillage présentant la granularité la plus fine obtenue après S-1 subdivisions. Un tel maillage comprend une pluralité de sommets sOs, si s, - - -, sN _s , avec N _s ≥1 . Le maillage M, constitue un maillage de granularité intermédiaire et comprend une pluralité de sommets sO,, si ,,..., sN,, avec Ν,>1 .

Une telle étape de représentation C1 est effectuée par un module logiciel de calcul CAL1_CO représenté à la figure 2, lequel module est piloté par le microprocesseur μΡ de l'unité de traitement UT_CO.

Un exemple d'une telle représentation de ladite variété est illustré sur la figure 3A avec n=2, les simplexes de dimension 2 étant représentés respectivement par des triangles. Sur la figure 3A sont représentés successivement le maillage de base M ₀ , le maillage de granularité intermédiaire M, et le maillage M _s de granularité la plus fine.

Selon l'invention, la procédure de représentation est mise en œuvre de la façon suivante.

Au cours d'une sous-étape C1 1 représentée à la figure 1 , il est procédé à un test de parité de l'indice i.

Dans le cas où i est pair, la subdivision du maillage M, pour obtenir le maillage M _i+ i est effectuée selon une première règle de subdivision prédéterminée.

Selon cette première règle de subdivision, pour chaque simplexe du maillage M,, il est procédé :

- au cours d'une sous-étape C12a) représentée à la figure 1 , à l'insertion d'un nouveau sommet qui est par exemple le barycentre des sommets du simplexe considéré,

- au cours d'une sous-étape C13a) représentée à la figure 1 , à l'affectation aux coordonnées dudit nouveau sommet inséré, de la valeur du signal f.

Les figures 4A et 4B représentent un exemple d'une telle subdivision dans le cas d'un simplexe de dimension 3. La figure 4A représente le maillage M, avant subdivision. La figure 4B représente le maillage M _i+ i obtenu après subdivision, où le nouveau sommet inséré ns _i+ i est représenté par un point. L'insertion de ce nouveau point engendre la création de nouvelles arêtes représentées en trait mixte. Ces nouvelles arêtes délimitent quatre nouveaux simplexes. Dans le cas où i est impair, la subdivision du maillage M, pour obtenir le maillage M _i+ est effectuée selon une deuxième règle de subdivision prédéterminée.

Selon cette deuxième règle de subdivision, pour chaque simplexe du maillage M, _, il est procédé :

- au cours d'une sous-étape C12b) représentée à la figure 1 , à la détermination d'une face du simplexe considéré qui est commune à celle d'un autre simplexe du maillage M,,

- au cours d'une sous-étape C13b) représentée à la figure 1 , à la suppression de ladite face commune déterminée de façon à obtenir un nouveau simplexe,

- au cours d'une sous-étape C14b) représentée à la figure 1 , à l'insertion d'un nouveau sommet à l'intérieur dudit nouveau simplexe obtenu, ledit nouveau sommet étant par exemple le barycentre des sommets de ladite face commune déterminée,

- au cours d'une sous-étape C15b) représentée à la figure 1 , à l'affectation aux coordonnées dudit nouveau sommet inséré, de la valeur du signal f.

Les figures 5A à 5C représentent un exemple d'une telle subdivision dans le cas d'un simplexe de dimension 3.

La figure 5A représente deux maillages voisins M, et M', avant subdivision selon la deuxième règle de subdivision et ayant chacun été obtenus comme représenté sur la figure 4B. A cet effet, le nouveau sommet inséré à l'étape de subdivision précédente est désigné par ns, pour le maillage M, et ns'i pour le maillage M',.

La figure 5B représente deux nouveaux simplexes T, et T, résultant respectivement de l'insertion des nouveaux sommets ns, et ns Les deux nouveaux simplexes ont une face commune FC représentée par des hachures sur la figure 5B et forment ensemble une bi-pyramide.

La figure 5C représente le maillage M _i+ obtenu après subdivision, où le nouveau sommet inséré nsi ₊ i est représenté par une croix. L'insertion de ce nouveau sommet engendre la création de nouvelles arêtes représentées en trait gras. Ces nouvelles arêtes délimitent cinq nouveaux simplexes. Une telle hiérarchie de maillage basée simplement sur deux règles de subdivision, peu coûteuse en calculs et facilement implémentable au codage est ainsi destinée à servir de base à la définition d'ondelettes selon la méthode « lifting scheme » telle que décrite dans le document « Michael Lounsbery, Tony D. DeRose, and Joe Warren, « Multiresolution analysis for surfaces of arbitrary topological type » (ACM Transaction on Graphics, Vol 16, N° 1, pp. 34-73, January 1997)

A cet effet, au cours d'une étape C2 représentée à la figure 1 , il est procédé à la projection du signal f à coder dans une base d'ondelettes, par exemple de deuxième génération.

Au cours d'une sous-étape C21 représentée à la figure 1 , pour un maillage M, considéré, une fonction f, est définie comme la fonction affine sur chaque simplexe du maillage M,, ladite fonction f, ayant comme valeur f(sOj), f(s1 i), ..., f(sNj) respectivement en chaque sommet sO,, si ,,..., sN,, du maillage Mi.

Au cours d'une sous-étape C22 représentée à la figure 1 , le niveau de subdivision maximal S du maillage de base M ₀ précité est fixé par exemple de la façon suivante :

S = min{i G N: \\f -f _t \\ < ε} où ε désigne un seuil prédéterminé.

Selon un autre exemple, le niveau de subdivision maximal S du maillage M ₀ précité est fixé comme le plus petit entier positif tel que le maillage M _s contienne un simplexe pour lequel la plus grande distance entre deux de ses points soit inférieure à un seuil prédéterminé.

Une telle étape de projection C2 est effectuée par un module logiciel de calcul CAL2_CO représenté à la figure 2, lequel module est piloté par le microprocesseur μΡ de l'unité de traitement UT_CO.

Au cours d'une étape C3 représentée à la figure 1 , il est procédé à l'application d'une transformation en ondelettes à chaque subdivision du maillage M ₀ , M-,, ..., M,, ..., M _s- i , délivrant un ensemble de coefficients d'ondelettes D ₀ , D-i , D _S -i . Une telle étape C3 est effectuée par un module logiciel de calcul CAL3_CO représenté à la figure 2, lequel module est piloté par le microprocesseur μΡ de l'unité de traitement UT_CO.

De façon connue en soi, ladite étape d'application C3 consiste, au cours d'une sous-étape C31 représentée à la figure 1 , à appliquer un filtre sur un maillage courant M, à subdiviser, ledit filtre étant défini à partir d'une matrice A' qui est la concaténation de deux matrices P' et Q'.

Conformément à l'invention, les matrices P' et Q' sont telles que :

- un élément a _k, i (k>0 et l>0) considéré de la matrice P' a pour valeur :

• 1 /b _k si les sommets sk, et si, du maillage M, d'indices respectifs k et I, avec 0<k≤Ni 0≤Ι≤Ν, sont reliés par une arête du maillage M,, b _k étant le nombre de sommets partageant une arête avec le sommet sk, du maillage M,,

• 0 sinon, un élément a' _k ,i (k>0 et l>0) considéré de la matrice Q' a pour valeur :

• 1 si k=l,

• ^— ^u(sk 0 _S j | _es sommets sk, et si, du maillage M, d'indices respectifs k et I sont reliés par une arête du maillage M,,

• 0 sinon, ou :

- u est une fonction qui associe à un sommet sk, du maillage M, le nombre de simplexes auxquels il appartient, et

- v est une fonction qui associe à un sommet sk, du maillage M, l'ensemble des sommets du maillage M, qui partagent une arête avec ledit sommet sk,.

Ladite étape d'application est itérée pour chacune des S-1 subdivisions du maillage M ₀ délivrant S-1 matrices A ⁰ , A ¹ , A ^s"1 . Au cours d'une sous-étape C32 représentée à la figure 1 , une matrice de synthèse X=A°A ¹ ....A ^S"1 est définie comme la concaténation des matrices A ⁰ , A ¹ , A ^s"1 obtenues à la sous-étape C31 précitée.

Au cours d'une sous-étape C33 représentée à la figure 1 , il est procédé au calcul d'une matrice d'analyse Y à partir de la matrice de synthèse X de façon à obtenir une succession de maillages M _s , M _s- i , . . . , Mj,...M ₀ qui représente le passage du maillage M _s de granularité la plus fine au maillage Mo de granularité la plus grossière. Une telle représentation est illustrée sur la figure 3B.

De façon connue en soi, la matrice d'analyse Y est l'inverse de la matrice de synthèse X, soit Y=X ^"1 . La matrice d'analyse Y est par exemple calculée au moyen d'un algorithme classique d'élimination de Gauss.

Au cours d'une sous-étape C34 représentée à la figure 1 , la matrice d'analyse Y est alors appliquée au maillage M _s , délivrant un ensemble de coefficients d'ondelettes D ₀ , D-i , D,, D _S -i tels que représentés sur la figure 3B et correspondant respectivement à chaque niveau de détail de subdivision.

Au cours d'une étape C4 représentée à la figure 1 , il est procédé à la quantification des coefficients d'ondelettes D ₀ , D-i , D,, D _S -i selon une opération classique de quantification, telle que par exemple une quantification scalaire. Une séquence de coefficients quantifiés Sq est alors obtenue.

Une telle étape est mise en œuvre par un module de quantification MQ_CO représenté sur la figure 2, lequel module est piloté par le microprocesseur μΡ de l'unité de traitement UT_CO.

Au cours d'une étape C5 représentée à la figure 1 , il est procédé au codage entropique de la séquence de coefficients quantifiés Sq.

Une telle étape est mise en œuvre par un module MCE de codage entropique représenté sur la figure 2, lequel module est piloté par le microprocesseur μΡ de l'unité de traitement UT_CO. Le module MCE est par exemple de type CABAC.

Les coefficients ainsi codés sont alors disponibles pour être inscrits, au cours d'une étape C6, dans un flux F destiné à être transmis à un décodeur tel que le décodeur DO représenté sur la figure 6. En fonction du contexte de codage, la totalité ou une partie seulement des coefficients sont inscrits dans le flux F.

L'étape de production d'un tel flux est mise en œuvre par un module logiciel MGF de génération de flux de données, telles que des bits par exemple, ledit module étant représenté sur la figure 2. Le module MGF est piloté par le microprocesseur μΡ de l'unité de traitement UT_CO.

Description détaillée d'un mode de réalisation de la partie décodage

On va maintenant décrire à la figure 7 le procédé de décodage selon l'invention mis en œuvre dans le décodeur DO de la figure 6. Comme illustré en figure 6, un tel dispositif de décodage DO comprend une mémoire

MEM_DO, une unité de traitement UT_DO équipée par exemple d'un microprocesseur μΡ et pilotée par un programme d'ordinateur PG_DO qui met en œuvre le procédé de décodage selon l'invention. A l'initialisation, les instructions de code du programme d'ordinateur PG_DO sont par exemple chargées dans une mémoire RAM (non représentée) avant d'être exécutées par le processeur de l'unité de traitement UT_DO.

Le procédé de décodage selon l'invention est représenté sous la forme d'un algorithme comportant les étapes D1 à D5, représentées à la figure 7.

Au cours d'une étape D1 représentée sur la figure 7, il est procédé au décodage entropique de la séquence courante S _q de coefficients codés précédemment au cours de l'étape C5 précitée _.

Une telle étape est mise en œuvre par un module MDE de décodage entropique représenté sur la figure 6, lequel module est piloté par le microprocesseur μΡ de l'unité de traitement UT_DO. Le module MDE est par exemple de type CABAC.

Au cours d'une étape D2 représentée sur la figure 7, il est procédé à la déquantification de la séquence de coefficients quantifiée Sq selon une opération classique de déquantification qui est l'opération inverse de la quantification effectuée à l'étape C4 précitée, pour produire une séquence de coefficients déquantifiée décodée SDt contenant les coefficients Dt ₀ , Dt-i ,

Au cours d'une étape D3 représentée sur la figure 7, il est procédé à l'application d'une transformée inverse en ondelettes aux coefficients Dt ₀ , Dt-i , Dts-i de ladite séquence SDt, à l'aide d'une suite de maillages M ₀ , Μι , ...Μ ι , M,, M _i+ i , ... , M _S (0<i≤S) formés respectivement d'une pluralité de simplexes de dimension n, un maillage courant considéré M, constituant une subdivision du maillage immédiatement précédent MM ,

Le maillage M ₀ est appelé classiquement maillage de base et comprend une pluralité de sommets s0 ₀ , s1 ₀ , ..., sN ₀ , avec N ₀ ≥1 .

Le maillage M _S constitue le maillage présentant la granularité la plus fine obtenue après S-1 subdivisions. Un tel maillage comprend une pluralité de sommets s0 _s , s1 _s , - - -, sN _s , avec N _s ≥1 .

Le maillage M, constitue un maillage de granularité intermédiaire et comprend une pluralité de sommets sO,, si ,, ... , sN,, avec Ν,≥1 .

Une telle étape D3 est effectuée par un module logiciel de calcul CAL1 _DO représenté à la figure 6, lequel module est piloté par le microprocesseur μΡ de l'unité de traitement UT_DO.

De façon connue en soi, ladite étape d'application D3 consiste, au cours d'une sous-étape D31 représentée à la figure 7, à appliquer un filtre sur un maillage courant M, à subdiviser, ledit filtre étant défini à partir d'une matrice A' qui est la concaténation de deux matrices P' et Q'.

Conformément à l'invention, les matrices P' et Q' sont telles que :

- un élément (k>0 et l>0) considéré de la matrice P' a pour valeur :

• 1 /bk si les sommets sk, et si, du maillage M, d'indices respectifs k et I, avec 0<k≤Ni 0<l≤Ni sont reliés par une arête du maillage M,, b _k étant le nombre de sommets partageant une arête avec le sommet sk, du maillage M,,

• 0 sinon, un élément a'ig (k>0 et l>0) considéré de la matrice Q' a pour valeur :

• 1 si k=l,

— - si les sommets sk, et si, du maillage M, d'indices respectifs k et I sont reliés par une arête du maillage M,, • 0 sinon, où :

- u est une fonction qui associe à un sommet sk, du maillage M, le nombre de simplexes auxquels il appartient, et

- v est une fonction qui associe à un sommet sk, du maillage M, l'ensemble des sommets du maillage M, qui partagent une arête avec ledit sommet sk,.

Ladite étape d'application est itérée pour chacune des S-1 subdivisions du maillage M ₀ délivrant S-1 matrices A ⁰ , A ¹ , A ^s"1 .

Au cours d'une sous-étape D32 représentée à la figure 7, de façon similaire à l'étape C32 précitée, une matrice de synthèse X=A°A ¹ ....A ^S"1 est définie comme la concaténation des matrices A ⁰ , A ¹ , A ^s"1 obtenues à la sous-étape D31 précitée.

Au cours d'une sous-étape D33 représentée à la figure 7, la matrice de synthèse X est alors appliquée au maillage de base M ₀ , délivrant un ensemble de coefficients d'ondelettes D ₀ , D-i , D,, D _S -i tels que représentés sur la figure 3B et correspondant respectivement à chaque niveau de détail de subdivision.

Selon l'invention, il est procédé, au cours d'une étape D4 représentée à la figure 7, à la reconstruction du signal f dans la base d'ondelettes définie par les coefficients d'ondelettes D ₀ , D-i , D,, D _S -i qui ont été délivrés à l'issue de l'étape D3 précitée.

Une telle étape D4 est effectuée par un module logiciel de calcul CAL2_DO représenté à la figure 6, lequel module est piloté par le microprocesseur μΡ de l'unité de traitement UT_DO.

Ladite étape D4 comprend les sous-étapes suivantes.

Au cours d'une sous-étape D41 représentée à la figure 7, pour un maillage M, considéré, une fonction f, est reconstruite à partir du coefficient D, (0<i≤S-1 ) en tant que fonction affine sur chaque simplexe du maillage M,. Ladite fonction f, a comme valeur f (sO,), f(s1 ,), ..., f(sNj) respectivement en chaque sommet sO,, si ,, ..., sN,, du maillage M,. Au cours d'une sous-étape D42 représentée à la figure 7, le niveau de subdivision maximal S du maillage de base M ₀ précité est reconstruit par exemple de la façon suivante :

S = min{i G N: \\f -f _t \\ < ε} où ε désigne un seuil prédéterminé.

Selon un autre exemple, le niveau de subdivision maximal S du maillage M ₀ précité est reconstruit comme étant le plus petit entier positif tel que le maillage M _s contienne un simplexe pour lequel la plus grande distance entre deux de ses points soit inférieure à un seuil prédéterminé.

Au cours d'une étape D5 représentée à la figure 7, il est procédé à une reconstruction de ladite variété de dimension n dans lequel est défini le signal f.

Une telle étape D5 est effectuée par un module logiciel de calcul CAL3_DO représenté à la figure 6, lequel module est piloté par le microprocesseur μΡ de l'unité de traitement UT_DO.

Au cours de l'étape D5 précitée, les sous-étapes suivantes sont mises en œuvre de façon similaire à ce qui a été décrit au codage.

Au cours d'une sous-étape D51 représentée à la figure 7, il est procédé à un test de parité de l'indice i.

Dans le cas où i est pair, la subdivision du maillage M, pour obtenir le maillage M _i+ est effectuée selon une première règle de subdivision prédéterminée.

Selon cette première règle de subdivision, pour chaque simplexe du maillage M, _, il est procédé :

- au cours d'une sous-étape D52a) représentée à la figure 7, à l'insertion d'un nouveau sommet qui est par exemple le barycentre des sommets du simplexe considéré,

- au cours d'une sous-étape D53a) représentée à la figure 7, à l'affectation aux coordonnées dudit nouveau sommet inséré, de la valeur du signal f. Dans le cas où i est impair, la subdivision du maillage M, pour obtenir le maillage M _i+ est effectuée selon une deuxième règle de subdivision prédéterminée.

Selon cette deuxième règle de subdivision, pour chaque simplexe du maillage M, _, il est procédé :

- au cours d'une sous-étape D52b) représentée à la figure 7, à la détermination d'une face du simplexe considéré qui est commune à celle d'un autre simplexe du maillage M,,

- au cours d'une sous-étape D53b) représentée à la figure 7, à la suppression de ladite face commune déterminée de façon à obtenir un nouveau simplexe,

- au cours d'une sous-étape D54b) représentée à la figure 7, à l'insertion d'un nouveau sommet à l'intérieur dudit nouveau simplexe obtenu, ledit nouveau sommet étant par exemple le barycentre des sommets de ladite face commune déterminée,

- au cours d'une sous-étape D55b) représentée à la figure 7, à l'affectation aux coordonnées dudit nouveau sommet inséré, de la valeur du signal f.

A l'issue de l'étape D5, est obtenu un signal fd défini sur la variété de dimension n, le signal fd étant la version décodée du signal f qui a été codée précédemment.

Exemple d'application

Selon un exemple d'application possible non limitatif, l'invention peut être appliquée pour coder (respectivement décoder) une image multi-vues ou une séquence d'images multi-vues au format MVV (pour « Multiview Video » en anglais). De façon connue en soi, comme représenté sur la figure 8, une image multi-vues courante IMV _C contient une pluralité de K vues V-i , V ₂ , ....V _m , ..., V _K (K>1 ), lesdites K vues représentant la même scène selon K points de vue différents à un même instant courant t _c .

Dans le cas du codage/décodage d'une image multi-vues fixe, pour une vue V _m considérée, un pixel p _m considéré dans cette vue est pourvu de quatre coordonnées x _m , y _m , w _m , z _m où x _m et y _m représentent les coordonnées du pixel considéré dans la vue V _m et où w _m , z _m représentent les coordonnées de la vue V _m dans l'image multi-vues IMV _C . A cet effet, la variété à coder est de dimension n=4.

Dans le cas du codage/décodage d'une séquence d'images multi-vues, pour une vue V _m considérée, un pixel p _m considéré dans cette vue est pourvu de cinq coordonnées x _m , y _m , w _m , z _m , t _c , où x _m et y _m représentent les coordonnées du pixel considéré dans la vue V _m , où w _m , z _m représentent les coordonnées de la vue V _m dans l'image multi-vues IMV _C et où tc est l'instant courant.

Le signal est alors défini comme un quadruplet (x _m , y _m , w _m , z _m ) ou un quintuplet (x _m , y _m , w _m , z _m , t _c ) qui associe une intensité lumineuse pour chacune des couleurs (par exemple rouge, vert, bleu, etc ..) prise par un pixel considéré. Au décodage, l'image multi-vues IMV _C est alors reconstruite à partir d'une pluralité de signaux, un pour chaque couleur.

Il va de soi que le mode de réalisation qui a été décrit ci-dessus a été donné à titre purement indicatif et nullement limitatif, et que de nombreuses modifications peuvent être facilement apportées par l'homme de l'art sans pour autant sortir du cadre de l'invention.