Dissimulation de données par changement de connexité d’un maillage 3D - Data Hiding Based on Connectivity Modification of 3D Mesh

Dissimulation de données par changement de connexité d’un maillage 3D

Data Hiding Based on Connectivity Modification of 3D Mesh

P. Amat W. Puech  S. Druon  J.P. Pedeboy 

Laboratoire LIRMM, UMR CNRS 5506, Université de Montpellier II 161, rue Ada, 34392 MONTPELLIER CEDEX 05, FRANCE

Stratégies S.A., 41-43 rue de Villeneuve, Parc d’affaires SILIC - BP 80429 94583 Rungis cedex - France

Page: 
181-200
|
Received: 
29 March 2007
|
Accepted: 
N/A
|
Published: 
30 June 2008
| Citation

OPEN ACCESS

Abstract: 

Day by day, the amount of digital data has been rapidly increasing on the Internet. The size of 3D objects is very large and these objects need fast transmissions. Moreover, 3D data security becomes increasingly important for many applications, e.g., confidential transmission, video surveillance, military and medical applications. In this paper we present two new approaches of 3D object data hiding without changing the position of vertices in the 3D space. The main idea of the two proposed methods is to find and to synchronize particular areas of the 3D objects used to embed the message. The embedding is done by changing the connectivity of edges in the selected areas composed of quadrangles. The first proposed approach of data hiding in 3D objects is based on minimum spanning tree (MST) while the second approach is based on the projection on a secret axis of the quadrangle centers. These methods are lossless in the sense that the positions of the vertices are unchanged. Moreover they are blind and do not depend of the order of the data in the files. These two approaches are very interesting when the 3D objects have been digitalized with high precision.

Résumé

De nos jours, des visualisations ainsi que des transferts d’objets 3D sont couramment effectués pour de nombreuses applications allant du jeu vidéo à l’imagerie médicale en passant par l’industrie manufacturière. Dans cet article nous proposons deux nouvelles méthodes permettant de dissimuler des données dans des objets 3D sans modifier la position des sommets. L’idée principale des deux méthodes présentées est de trouver et de synchroniser des zones particulières dans l’objet 3D pouvant être utilisées pour insérer le message. L’insertion de données s’appuie sur la modification de la connexité des arêtes dans les zones sélectionnées composées de quadrangles. La différence entre les deux méthodes présentées est la manière de sélectionner et de synchroniser ces zones d’insertion. Alors que la première méthode s’appuie sur un arbre couvrant minimum (ACM), la seconde méthode utilise un axe sur lequel sont projetés les centres des zones d’insertion. Ces deux méthodes aveugles, protégées par utilisation de clefs secrètes, résistent à des transformations géométriques tels que les rotations, translations ou changement d’échelle et ne sont pas perturbées par des modifications directes de l’ordre des données dans les fichiers originaux. Ces approches trouvent un intérêt certain pour des objets 3D dont les sommets ont été acquis avec une grande précision et dont la modification n’est pas acceptable.

Keywords: 

Data hiding, Watermarking, 3D mesh, Quadrangle, Graph path, Minimum Spanning Tree, Principal component analysis, Data synchronization

Mots clés

Dissimulation de données, Tatouage, Maillage triangulaire 3D, Quadrangle, Parcours de graphe, Arbre couvrant minimum, Analyse en composante principale, Synchronisation des données

1. Introduction
2. État De L’art
3. Méthodes Proposées
4. Résultats Expérimentaux
5. Conclusions Et Perspectives
  References

[ALSS99] P. ALLIEZ, N. LAURENT, H. SANSON, and F. SCHMITT, Mesh Approximation Using a Volume-Based Metric. In PG ‘99: Proceedings of the 7th Pacific Conference on Computer Graphics and Applications, page 292, Washington, DC, USA, 1999. IEEE Computer Society.

[AMC07] P.R. ALFACE, B.MACQ, and F.CAYRE, Blind and Robust Watermarking of 3D Models: How to Withstand the Cropping Attack? In International Conference on Image Processing, IEEE ICIP07, San Antonio, Texas, USA, pages 465-468, 2007.

[BD07] J.BENNOUR and J.-L DUGELAY, Toward a 3D Watermarking Benchmark. In MMSP 2007, IEEE International workshop on multimedia signal processing, October 1-3, 2007, Chania, Greece, Oct 2007.

[Ben99a] O.BENEDENS, Geometry-Based Watermarking of 3D Models. IEEE Comput. Graph. Appl., 19(1):46-55, 1999.

[Ben99b] O.BENEDENS, Two High Capacity Methods for Embedding Public Watermarks into 3d Polygonal Models. Proceedings of the Multimedia and Security-Workshop at ACM Multimedia, pages 95-99, 1999.

[Ben00] O.BENEDENS, Affine Invariant Watermarks for 3D Polygonal and NURBS Based Models. In ISW ‘00: Proceedings of the Third International Workshop on Information Security, pages 15-29, London, UK, 2000, Springer-Verlag.

[Bor06] A.G. BORS, Watermarking Mesh-Based Representations of 3-D Objects Using Local Moments. IEEE Trans. on Image Processing, 15(3):687-701, mar 2006.

[CRS98] P. CIGNONI, C. ROCCHINI and R. SCOPIGNO, Metro: Measuring error on simplified surfaces. Computer Graphics Forum, 17(2):167-174, 1998.

[GSS99] I.GUSKOV, W.SWELDENS and P.SCHRÖDER, Multiresolution signal processing for meshes. In SIGGRAPH ‘99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques, pages 325-334, New York, NY, USA, 1999, ACM Press/Addison-Wesley Publishing Co.

[ICA02] S.ICHIKAWA, H.CHIYAMA and K.AKABANE, Redundancy in 3D Polygon Models and Its Application to Digital Signature. In WSCG, pages 225-232, 2002.

[KDK98] S.KANAI, H.DATE and T.KISHINAMI, Digital Watermarking for 3D Polygons using Multiresolution Wavelet Decomposition. Proc. int. Workshop Gemetric Modeling : Fondamentals and Applications, pages 296-307, Decembre 1998.

[Ker83] A. KERCKHOFFS, La cryptographie militaire. Journal des sciences militaires, 9:5-38, 1883.

[KKK02] S.-J KIM, S.-K KIM and C.-H KIM, Discrete Differential Error Metric for Surface Simplification. In PG ‘02: Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, page 276, Washington, DC, USA, 2002, IEEE Computer Society.

[Kru56] J.B. KRUSKAL, On the Shortest Spanning Tree of a Graph and the Traveling Saleman Problem. Proc of the American Mathematical Society, 7:48-50, 1956.

[LCK02] J.J. LEE, N.I. CHO and J.-W KIM, Watermarking for 3D NURBS graphic data. In Proceedings of 2002 IEEE Workshop on Multimedia Signal Processing, 9-11 December 2002, St. Thomas, Virgin Islands, USA, pages 304-307, 2002.

[LDGD+06] G. LAVOUÉ, E. DRELIE GELASCA, F. DUPONT, A.BASKURT and T.EBRAHIMI, Perceptually driven 3D distance metrics with application to watermarking. In SPIE Applications of Digital Image Processing XXIX, San Diego, august 2006.

[MC03] B.MACQ and F.CAYRE. Data Hiding on 3D Triangle Meshes. IEEE Transactions on Signal Processing, 51(4):939-949, 2003.

[MSI01] X.MAO, M.SHIBA and A.IMAMIYA, Watermarking 3D geometric models through triangle subdivision. In P.W. Wong and E.J. Delp, editors, Proc. SPIE Vol. 4314, p. 253-260, Security and Watermarking of Multimedia Contents III, Ping Wah Wong; Edward J. Delp; Eds., volume 4314 of Presented at the Society of Photo-Optical Instrumentation Engineers (SPIE) Conference, pages 253-260, August 2001.

[OMA97] R. OHBUCHI, H. MASUDA and M. AONO, Watermaking Three-Dimensional Polygonal Models. In MULTIMEDIA ‘97: Proceedings of the fifth ACM international conference on Multimedia, pages 261-272, New York, NY, USA, 1997, ACM Press.

[OMT02] R. OHBUCHI, A. MUKAIYAMA and S. TAKAHASHI. A Frequency-Domain Approach to Watermarking 3D Shapes. Computer Graphics Forum, 21(3):373-382, 2002.

[PHF99] E.PRAUN, H.HOPPE and A.FINKELSTEIN, Robust Mesh Watermarking. In Alyn Rockwood, editor, Siggraph 1999, Computer Graphics Proceedings, pages 49-56, Los Angeles, 1999. Addison Wesley Longman.

[Pri57] R. C. PRIM, Shortest Connection Networks and some Generalisations. In : Bell System Technical Journal, 36:1389-1401,1957.

[RAM06] P.RONDAO-ALFACE and B.MACQ, Shape quality measurement for 3D watermarking schemes. In E.J. Delp, III and P.W. Wong, editors, Security, Steganography, and Watermarking of Multimedia Contents VIII. Edited by Delp, Edward J., III; Wong, Ping Wah. Proceedings of the SPIE, Volume 6072, pp. 622-634 (2006), volume 6072 of Presented at the Society of Photo-Optical Instrumentation Engineers (SPIE) Conference, pages 622-634, February 2006.

[RAM07] P.RONDAO-ALFACE and B.MACQ, From 3D Mesh Data Hiding to 3D Shape Blind and Robust Watermarking: A Survey. LNCS Transactions on Data Hiding and Multimedia Security, 2:99-115, 2007.

[Wag00] M.G WAGNER, Robust Watermarking of Polygonal Meshes. In GMP ‘00: Proceedings of the Geometric Modeling and Processing 2000, pages 201-208, Washington, DC, USA, 2000, IEEE Computer Society.

[WLDB07a] K. WANG, G. LAVOUÉ, F. DENIS and A. BASKURT, Hierarchical Blind Watermarking of 3D Triangular Meshes. In Proc. of the IEEE International Conference on Multimedia & Expo, pages 1235-1238, IEEE, July 2007.

[WLDB07b] K.WANG, G.LAVOUÉ, F.DENIS and A.BASKURT. ThreeDimensional Meshes Watermarking : Review and Attack-Centric Investigation. In 9th International Workshop on Information Hiding, pages 50-64, Saint Malo, France, 2007.

[YPSZ01] K.YIN, Z.PAN, J.SHI and D.ZHANG. Robust mesh watermarking based on multiresolution processing. Computers and Graphics, 25:409-420, June 2001.