Institut de la Francophonie Université Claude Bernard pour l’Informatique Lyon 1 MEMOIRE DE STAGE DE FIN D’ETUDES MASTER EN INFORMATIQUE SPECIALITE SYSTEMES ET RESEAUX TATOUAGE AVEUGLE ET ROBUSTE DE MAILLAGES 3D DANS LE DOMAINE SPECTRAL Stagiaire : HO Thi Phuong Responsables de stage : Florence DENIS Guillaume LAVOUE Kai WANG Ce stage a été réalisé au sein de l’équipe M2disco du laboratoire d'informatique en image et systèmes d'information Lyon, Mars – Novembre, 2009 TIEU LUAN MOI download : skknchat@gmail.com Table de matières 1 Introduction .5 Environnement de stage .6 Plan du rapport. 11 2 Etat de l’art.1 Principe et applications .2 Propriété du tatouage .2 Métriques de distorsion .3 Traitement des maillages – les attaques sur le tatouage .2 Attaques sur la connectivité : .4 Techniques de tatouage robuste de maillages 3D .2 Tatouage robuste de maillages .1 Harmoniques variétés et algorithme bande par bande .2 Calcul bande par bande .2 Amélioration de l’implémentation de l’algorithme bande par bande .1 Problème avec l’implémentation originale et amélioration .3 Exactitude des valeurs et vecteurs propres .1 Comparaison entre le résultat de MEPP et celui de Graphite .2 Comparaison entre le résultat de MEPP et celui de Matlab .3 Comparaison entre les résultats de MEPP. 39 2 TIEU LUAN MOI download : skknchat@gmail.4 Conclusion des comparaisons .4 Stabilité des valeurs et vecteurs propres .1 Cohérence entre une bande étroite et une bande large .2 Cohérence entre une bande entière et des bandes successives .5 Robustesse de la transformée .1 Comparaison entre les matrices de discrétisation. 42 4 Tatouage de maillages 3D dans le domaine spectral .1 Tatouage utilisant la technique d’étalement de spectre - généralités .1 Principe de tatouage sur des données audiovisuelles .2 Avantage et inconvénients .2 Tatouage utilisant l’étalement de spectre sur des maillages 3D .1 Difficultés et solutions .2 Application de différentes techniques de modulation .3 Identification du seuil de détection du tatouage.3 Méthode de Piva et col.
[35] sur des maillages 3D .1 Adaptation de méthode de Piva et col. [35] sur des maillages 3D .2 Temps de calcul.3 Analyse de l’imperceptibilité .4 Efficacité de l’algorithme .5 Analyse de la robustesse .1 Résumé des contributions. 68 3 TIEU LUAN MOI download : skknchat@gmail.com Remerciements Je tiens particulièrement à remercier professeurs Florence DENIS, Guillaume LAVOUE mes responsables de stage, pour l’encadrement, l’aide, les conseils précieux pendant 9 mois de mon stage. Je tiens également à remercier Kai WANG, un thésard dans l’équipe M2disco qui a travaillé avec moi pendant ce stage, et m’a beaucoup aidé non seulement dans la théorie mais aussi dans le développement grâce à ses explications, ses conseils utiles et les documents à consulter.
J’adresse mes sincères remerciements à tous les professeurs de l’Institut de la Francophonie pour l’Informatique (IFI) pour m’avoir enseigné et me donnée les cours intéressants pendant mes études au niveau master. Je profite de cette occasion pour dire remercier à tous les personnels de l’IFI qui m’ont apporté de l’aide. Finalement, je voudrais remercier ma famille, mes parents et mes amis qui sont toujours près de moi et m’ont apporté de courage dans les moments difficiles. 4 TIEU LUAN MOI download : skknchat@gmail.com Résumé Les progrès dans les technologies d’acquisition et de modélisation 3D permettent de produire facilement des objets 3D.
La représentation la plus utilisée pour modéliser un objet 3D est le maillage 3D, c’est-à-dire un ensemble de polygones permettant de représenter des portions d’une surface 3D. Il y a de plus en plus d’outils qui permettent de manipuler ces données. On a donc besoin d’une technique pour protéger le droit d’auteur de ces maillages 3D. Le tatouage est apparu comme une solution à cette demande.
La transformée en Harmoniques variétés est récemment apparue comme un outil efficace d’analyse spectrale des maillages. Elle commence à être utilisée dans quelques algorithmes de tatouage. L’objectif de ce travail est double. Il s’agit d’étudier, d’implémenter et d’évaluer la robustesse des Harmoniques variétés.
D’autre part, il vise à proposer un algorithme de tatouage aveugle et robuste de maillages 3D dans le domaine spectral en utilisant la technique d’étalement de spectre sur des amplitudes spectrales obtenues par ce type de décomposition. La robustesse des Harmoniques variétés a été démontrée mais celle de notre algorithme devra être améliorée dans le futur. 5 TIEU LUAN MOI download : skknchat@gmail.com Abstract 3D scanning and modeling technologies now allow to produce easily representations of 3D objects that use different structures. One of these structures is the 3D mesh that is a set of polygons which represent an appropriate approximation of a 3D surface.
There are more and more tools for manipulating these data. We therefore need a technique to protect the copyright of 3D meshes. Watermarking appears as a good candidate to solve this emerging problem. Manifold Harmonics transform has been recently introduced as an efficient spectral analysis tool of 3D meshes.
It begins to be used in some watermarking algorithms. This work has two objectives. The first objective is to study and implement the Manifold Harmonics transform, and evaluate its robustness. The second is to propose a blind and robust mesh watermarking algorithm in the spectral domain by applying the spread spectrum technique on the Manifold Harmonics spectral amplitudes.
The robustness of the Manifold Harmonics transform has been demonstrated but the robustness of our watermarking algorithm has to be improved in the future. 6 TIEU LUAN MOI download : skknchat@gmail.com Liste de figures Figure 1 : Exemple d’un maillage (extrait de [1]). 10 Figure 2 : Modèle général du système de tatouage (extrait de [4]). 13 Figure 3 : Compromis entre trois propriétés importantes du tatouage.
14 Figure 4 : Illustration des deux systèmes de décodeur du tatouage (extraite de [6]). 14 Figure 5 : Illustration des tatouages aveugle et non aveugle. 16 Figure 6 : Exemple illustrant la valence d’un sommet et le degré d’une facette (extrait de [15]). 17 Figure 7 : Illustration de l’analyse en ondelettes (extrait de [15]).
17 Figure 8 : Angles αij et βij opposés à l’arête (vi,vj). 19 Figure 9 : Exemple de quelques attaques sur la géométrie : (a) objet original, (b) après la transformation de similarité, (c) après l’ajout de bruit, (d) après le lissage, (e) après la quantification. 21 Figure 10 : Exemple de la déformation locale basant sur l’esquisse (a) et celle sur l’articulation (b). 21 Figure 11 : L’objet original et des objets obtenus après quelques attaques (coupe - résultat de Meshbenchmark [13] d’autres attaques - extrait de [1]).
22 Figure 12 : Illustration de la méthode de Cho et col. 24 Figure 13 : Les sous maillages générés grâce aux méthodes. (a) de Ohbuchi et col. [21], (b) Cayre et col.
[22], (c) Alface et Macq [27], (d) Cotting et col. 25 Figure 14 : Etapes du tatouage en divisant l’objet en plusieurs patchs (extraite de [21]). 26 Figure 15 : Insérer bit 0 dans (xi, yi, zi) dans la méthode de Cayre et col. 27 Figure 16 : Choix des amplitudes spectrales de Wang et col.
30 Figure 17 : Représentation des bases de la transformée en Harmoniques variétés (extrait de [10]). 33 Figure 18 : Géométries reconstruites à partir d’une surface avec le nombre différent m des coefficients Harmoniques variétés (extrait de [9]). 33 Figure 19 : Illustration de l’algorithme bande par bande. 34 Figure 20 : Illustration des deux problèmes de l’implémentation : la répétition et la perte des valeurs propres.
35 Figure 21 : Illustration du changement de l’implémentation. 36 Figure 22 : Objet Bunny original et objet Bunny bruité avec l’intensité 0. 43 Figure 23 : Corrélation entre les amplitudes spectrales de l’objet original et celles de l’objet attaqué par l’ajout de bruit intensité k (k ∈ {0. 43 Figure 24 : Objet Bunny original et objet Bunny simplifié avec un taux de 97,5%.
43 Figure 25 : Corrélation entre les amplitudes spectrales de l’objet original et celles de l’objet simplifié. 44 Figure 26 : Objet Bunny original et objet Bunny lissé en 50 itérations en fixant le taux de déformation à 0,03. 44 Figure 27 : Corrélation entre les amplitudes spectrales de l’objet original et celles de l’objet lissé. 44 Figure 28 : Objet Bunny original et objet Bunny attaqué par la transformation de similarité.
45 Figure 29 : Corrélation entre les amplitudes spectrales de l’objet original et celles de l’objet attaqué par la transformation de similarité. 45 Figure 30 : Objet Bunny original et trois objets Bunny coupés avec un taux de 50%. 45 Figure 31 : Corrélation entre les amplitudes spectrales de l’objet original et celles de l’objet coupé. 46 Figure 32 : Corrélation entre n amplitudes spectrales de l’objet Bunny d’origine et celles de l’objet attaqué par l’ajout de bruit intensité k (n < 3000, k ∈ {0.
47 Figure 33 : Corrélation entre les amplitudes spectrales de l’objet Bunny d’origine et celles de l’objet simplifié. 47 Figure 34 : Corrélation entre les amplitudes spectrales de l’objet Bunny d’origine et celles de l’objet lissé. 48 7 TIEU LUAN MOI download : skknchat@gmail.com Figure 35 : Corrélation entre les amplitudes spectrales de l’objet Bunny d’origine et celles de l’objet attaqué par la transformation de similarité. 48 Figure 36 : Corrélation entre les amplitudes spectrales de l’objet Bunny d’origine et celles de l’objet coupé.
49 Figure 37 : Tatouage aveugle des données audiovisuelles. 50 Figure 38 : Première idée de l’insertion du tatouage basé sur la corrélation pour les maillages 3D. 53 Figure 39 : Détection du tatouage aveugle basé sur la corrélation pour les maillages 3D. 53 Figure 40 : Insertion itérative du tatouage basée sur la corrélation pour les maillages 3D.
54 Figure 41 : Taux de modification des amplitudes spectrales k=a'[i]/a[i] causée par la transformation de similarité sur l'objet Bunny (i=1. 55 Figure 42 : Corrélation entre une image tatouée et de différents tatouages aléatoires (extrait de [69]). 56 Figure 43 : Corrélation entre l’objet Bunny tatoué par notre algorithme et simplifié avec le taux de 10% et les 30. 56 Figure 44 : Corrélation entre l’objet Bunny tatoué par notre algorithme et ajouté du bruit avec l’intensité de 0,40% et les 30.
57 Figure 45 : Modification de la corrélation entre l’objet et le tatouage à chaque itération de modulation de notre méthode sur l’objet Bunny. 60 Figure 46 : Corrélation entre l’objet Bunny tatoué et les 30000 aléatoires tatouages (tatouage exact numéro 42). 64 Figure 47 : Corrélation entre l’objet Rabbit tatoué et les 30000 aléatoires tatouages (tatouage exact numéro 42). 64 8 TIEU LUAN MOI download : skknchat@gmail.com Listes de tableaux Tableau 1 : Comparaison des propriétés de quelques algorithmes (en bleu : extrait de [15], en blanc : des comparaisons ajoutées).
31 Tableau 2 : Comparaison de la robustesse de quelques algorithmes (en bleu : extrait de [15], en blanc : des comparaisons ajoutées). 31 Tableau 3 : Algorithme bande par bande d’origine. 35 Tableau 4 : La répétition de valeur propre 332.8754 dans le résultat obtenu par l’implémentation originale (une bande contient 100 valeurs propres sous MEPP). 35 Tableau 5 : Perte de valeur propre -1259.0661 dans le calcul sous MEPP.
36 Tableau 6 : Implémentation améliorée de l’algorithme bande par bande. 37 Tableau 7 : Comparaison entre des valeurs propres calculées sous Graphite et MEPP (N. signifie non- applicable). 38 Tableau 8 : Comparaison entre des vecteurs propres calculés sous Graphite et MEPP (N.
signifie non- applicable). 38 Tableau 9: Comparaison entre le résultat de MEPP et celui de Matlab. 39 Tableau 10 : Comparaison entre les vecteurs propres obtenus entre le calcul des bandes étroites et celui de la bande large. 40 Tableau 11 : Comparaison entre les vecteurs propres obtenus entre le calcul des bandes étroites et celui de la bande large.
40 Tableau 12 : Les RMS des amplitudes spectrales obtenues dans tests sur l’objet Bunny avec le solveur Taucs. 42 Tableau 13 : Corrélation entre des objets originaux et 60000 tatouages aléatoires. 61 Tableau 14 : Algorithme d’insertion .