1 Réalisé par : M. Anis MEFTAH Encadré par : M. Marc Antonini 2005 -2006

1

Réalisé par :

M. Anis MEFTAH

Encadré par :

M. Marc Antonini2005 -2006

2

Plan

• Notions générales sur la 3D• Analyse multirésolution de maillages 3D• Compression au fil de l’eau• Résultats• Conclusion et perspectives

3

Notions générales sur la 3D

4

Domaines d’applications

I- Notions générales sur la 3D

Cinéma

Médecine

Conception Assisté par Ordinateur (CAO)

5

Les maillages 3D

2 informations : la géométrie (sommets) la topologie (Connectivité)

I- Notions générales sur la 3D

géométrie0.0 0.0 0.01.0 0.0 0.01.0 1.0 0.00.0 1.0 0.00.5 0.5 1.0

topologie0 1 22 3 00 1 41 2 42 3 43 0 4

[1]

[1] ALLIEZ P. and GOTSMAN C. Recent advances in compression of 3d meshes. In Proceedings of the symposium on multiresolution in Geometric Modeling, 2003.

6

Monorésolution Vs Multirésolution

• Un maillage peut être : Monorésolution Multirésolution

I- Notions générales sur la 3D

7

Les types de maillage

• Il existe trois types de maillage : Les maillages irréguliers  Les maillages réguliers  Les maillages semi-réguliers 

I- Notions générales sur la 3D

8

Analyse multirésolution de maillages 3D

9

Les méthodes de compression

• Les méthodes qui ne tirent pas profit de la structure maillée des objets 3D.

• Les méthodes qui tiennent compte de la structure de l’objet 3D : Les méthodes de compression monorésolution.

Les méthodes de compression multirésolution.

II- Analyse multirésolution de maillages 3D

10

L’analyse multirésolution

Analyse

Synthèse

II- Analyse multirésolution de maillages 3D

11

Schéma lifting à 2 canaux

• Le schéma lifting se compose de trois étapes : Transformée polyphase Prédiction Mise à jour

II- Analyse multirésolution de maillages 3D

12

Filtre Butterfly lifté

Les types de points :

Filtre de prédiction :

Filtre de mise à jour : Filtre Butterfly non lifté

II- Analyse multirésolution de maillages 3D

13

Compression « au fil de l’eau »

14

Maillages de très grandes tailles

Le développement spectaculaire des scanners 3D et des logiciels de CAO a permit l’acquisition et la création d’objets 3D de plus en plus détaillés.

Ces objets 3D ont des tailles énormes dépassant plusieurs millions de points.

III- Compression « au fil de l’eau »

15

Exemple d’objets très détaillés

scannage de la statue de David

Le modèle tridimensionnel comporte

plus de deux milliards de polygones. Modèle tridimensionnel final de la statue de Saint Matthieu (comportant plus de 380 millions de triangles).

III- Compression « au fil de l’eau »

Images propriété du projet Michelangelo

16

Problématique

• La transformée en ondelettes nécessite le chargement de la totalité de l’objet 3D en mémoire avant son traitement.

• Défi : concevoir une méthode au fil de l’eau qui va nous permettre de :– Avoir la même transformée en ondelettes;– Gagner de l’espace mémoire.

III- Compression « au fil de l’eau »

17

Principe de la méthode

18

Fin du codage du lot (demande d’envoi)

Objet 3DTransformée en ondelettes

Codeur TopologiqueMaillage de base

Q

Allocation Binaire

Codage Entropique

Débitcible

HF

1101

MULTIPLEXEUR

Schéma Générale sans fil de l’eau

III- Compression « au fil de l’eau »

19

Fin du codage du lot (demande d’envoi)

Acquisition Spirale

Objet 3D

Mémoire du traiteur

Transformée en ondelettes

Mémoire duCodeur

Codeur TopologiqueMaillage de base

Q

Allocation Binaire

Codage Entropique

Débitcible

HF

1101

Fin du calcul de la transformée (demande d’envoi du lot suivant)

Transformée en ondelettes au fil de l’eau Codage au fil de l’eau

MULTIPLEXEUR

Schéma global de la méthode au fil de l’eau proposée

Schéma global de la méthode proposée

III- Compression « au fil de l’eau »

20

Chargement des triangles (1ère étape)

Une réduction de la taille mémoire nécessaire pour le calcul de la transformée en ondelettes de 44% par rapport au cas lifté.

L’objet venus

Niveau le moins détaillé Zoom de la partie à charger

10 triangle BF + leur détails (Triangle L0) à charger quelque soit la topologie de l’objet 3D au lieu de 17.

III- Compression « au fil de l’eau »

21

Chargement des triangles (2ème étape)

L’objet venus

Niveau le moins détaillé Zoom de la partie à charger

Utilisation de 28 % de la mémoire nécessaire dans le cas lifté.

Un seuil maximal de 19 triangle L1 à charger quelque soit la topologie de l’objet 3D au lieu de 40. Ce qui à peu prés équivalent à 5 triangles L0

III- Compression « au fil de l’eau »

22

Chargement des triangles (3ème étape)

L’objet venus

Niveau le moins détaillé Zoom de la partie à charger

Nous allons charger dans la mémoire seulement 43 triangles L2 au lieu de 272, ce qui correspond a peu prés à 2,6 L0.

Utilisation de 15,8 % de la mémoire nécessaire dans le cas lifté.

III- Compression « au fil de l’eau »

23

Calcul de la taille mémoire nécessaire pour appliquer la T.O

• S est donné par la formule suivante :

S= 43*T2

• avec T2 la taille d’un triangle L2 donnée par la formule :

T2= G + T + V

G = 3 * sizeOf(float) * nombre de sommets ; T= 3 * sizeOf(int) * nombre de trinagles ; V= 3 * sizeOf(int) * nombre de trinagles ;

24

Décompression

III- Compression « au fil de l’eau »

25

Calcul du bord

III- Compression « au fil de l’eau »

26

Calcul du bord

III- Compression « au fil de l’eau »

27

Résultats

28

• Le critère de qualité utilisé pour évaluer la qualité des maillages compressés est le :– PSNR : Peak Signal Noise Ratio (PRSB en

français, Pic du rapport signal à bruit) exprimé en décibels (dB).

PSNR = 20 * log2(BB/ ds)

Le critère de qualité utilisé

Avec BB est la longueur de la boite englobante de l’objet, et ds est la distance surface-surface entre le maillage d’entrée et le maillage de sortie.

IV- Résultats

29

Taille mémoire nécessaire

IV- Résultats

30

PSNR vs débit (Venus)

IV- Résultats

31

PSNR vs débit (Horse)

IV- Résultats

32

Comparatif Visuel

1 bit/vertex avec 25% de mémoire

1 bit/vertex avec 5% de mémoire.

1 bit/vertex sans fil de l’eau.

IV- Résultats

33

Conclusion et perspectives

34

Conclusion• Nous avons proposé une nouvelle transformée en

ondelettes «au fil de l’eau» utilisant le filtre Butterfly non lifté.

• Les expériences ont montré que notre méthode est très efficace en terme de coût mémoire : jusqu’à 99 % de gain mémoire.

• Taille mémoire nécessaire, fixe et constante quel que soit l’objet : Possibilité d’implémentation matériel.

V- Conclusion et perspectives

35

Perspectives (Thèse)

• Codage conjoint : répartir de façon optimale les bits entre les différentes informations

• Optimiser le compromis entre la taille de la trame et la qualité visuelle du maillage reconstruit

Sommets (géométrie) arrêtes (topologie)

Texture

Images extraite du cours de Mr George Drettakis et Nicolas Tsingos

36

Article Accepté

• Conférence internationale IEEE ISIVC 2006 ( 13-14-15 Septembre)– “Low memory cost scan-based wavelet

transform for 3D multiresolution meshes using the unlifted Butterfly filter”

– A. MEFTAH, A. ELKEFI, M. ANTONINI, C. BEN AMAR

37

Merci de votre attention