N. Werghi, N. Medimegh and S. Gazzah
Watermarking of 3D Triangular Mesh Models Using Ordered Ring Facets
N. Werghi: Department of Electrical and Computer Engineering, Khalifa University, Sharjah UAE, email: [email protected].
N. Medimegh and S. Gazzah: Research unit on Advanced Systems in Electrical Engineering(SAGE), National Engineering School of Sousse University of Sousse, Tunisia, emails: [email protected]; [email protected]
Abstract: In this paper we propose fragile and robust methods for watermarking binary data in triangular mesh models. Contrary to digital images and audio which benefit from the intrinsically ordered structure of the matrix and the array, 3D triangular mesh model lacks this capital property even though it can be encoded in an array date structure. Such a lack often complicates the different aspects of data embedding, like model traversal, data insertion, and synchronization. We address this problem with a mesh data representation which encodes the mesh data into a novel ordered structure, dubbed, the Ordered Rings Facets (ORF). This structure is composed of concentric rings in which the triangles are arranged in a circular fashion. This representation exhibits several interesting features that include a systematic traversing of the whole mesh model, simple mechanisms for avoiding the causality problem, and an efficient computation of the embedding distortion. Our fragile method can be also adapted to different scenarios of data embedding, which includes stenography and fragile watermarking. To maximize robustness of our robust method, we embed the signatures in stable regions where we have the minimum variance of spherical coordinates φ detected using ORF. Experimental results show that this new approach is robust against numerous attacks.
Keywords: 3D triangular mesh watermarking, Robust watermarking, Fragile water-marking, Ordered Ring Facets.
1Introduction
Data embedding refers to the process of inserting data into digital contents such as images, videos and 3D models. This process is referred to by different terms depending on the context, the scope and the aim of the data insertion. For example, for copyright protection, we refer to it by digital watermarking. Here the embedded data, called also the watermark, is meant to prove the ownership of the digital content and prevent its illegal use. Moreover, it is designed to resist and survive against malicious alterations (attacks). In such scenarios, the watermarking is labelled by the term robust. The term fragile watermarking is employed when the goal is to protect the integrity of the digital content from an unauthorized processing and to detect an eventual local or global manipulation. In fragile watermarking data is embedded globally (e.g. across the whole model surface), whereas in robust watermarking data is often locally embedded. Data embedding falls under the stenography scope when the digital content is used as a medium for carrying hidden information.
Within each of these applications, data embedding can be applied in the spatial or the spectral domain. In the former, the data is embedded by altering locally or globally the geometry or the topology of the model surface. Whereas the latter involves the modification of a certain components of a spectral transform coefficients. Data embedding can also be qualified to be blind or non-blind, depending on whether or not the original digital content is required to extract the embedded data.
With the recent advances of 3D shape acquisition and the CAD technology and the rapid evolution of network bandwidths, data embedding witnessed a new trend towards the use of 3D triangular mesh models. This fueled the need for new approaches and paradigms that can address the problematic aspects of embedding 3D models, and 3D triangular mesh models in particular.
A triangular mesh is a group of connected triangular facets that encode a given surface in terms of geometry and connectivity. The geometry defines the location of the triangular facets’ vertices in the Euclidean space. The connectivity defines the sets of vertices that are connected to form the triangles or the facets of the mesh. Each triangular facet is referenced by an index value that points to the three vertices bounding the triangle. As has been mentioned by Wang et al. [34], there is no simple robust intrinsic ordering the mesh elements, e.g. facets and the vertices, which often constitute the carrier of the embedded data. Some intuitive orders, such as the order of the vertices and facets in the mesh file, and the order of vertices obtained by ranking their projections on an axis of the objective Cartesian coordinate system, are easy to be altered.
To address this lack of order and its consequent issues in data embedding, we propose to use a novel paradigm, dubbed the Ordered Ring Facets (ORF). The paradigm has been firstly introduced in [1, 2] in the context of 3D facial surface analysis. In this paper we showcase the adaptability of this paradigm to data embedding for 3D mesh models and its distinguished features.
The rest of the paper will be organized as follows: Section 2 reviews part of the literature work. Section 3 describes the ORF concept and the related algorithms. Section 4 exposes the different aspects of our watermarking methods. Some experimental results are also presented and discussed. Finally we draw some concluding remarks in Section 5.
2Watermarking methods
As we mentioned in the literature, watermarking methods can be segmented into robust methods and fragile methods. These can be also classified into different sub-categories depending on the nature of the model alterations.
2.1Robust methods
These methods can be classified into spatial methods and spectral methods. The spatial methods act either on the geometry or the topology of the model. The elementary entity carrying the watermark data is referred by the watermark primitive. Many methods operate on the triangular facet as a watermark primitive. Benedens [3] proposed a technique based on the Extended Gaussian Image, which is a kind of orientations histogram employed here for embedding data. The EGI has been augmented by an imaginary component by Lee and Kwon [4, 5], and dubbed it, the CEGI. They claimed the same level of impercibility than Benedens’s methods, in addition to its robustness against remeshing, simplification, cropping and noising.
In another method, Benedens [6] proposed algorithm, dubbed vertex flood, whereby the distance to the center of mass of reference triangles is changed to encode the watermark bits.
Kuo et al. [7] introduced the moment-preserving method , in which groups of neighboring facets are selected and classified using some specific geometric moments in order to hold the embedded bits. Other type of methods used particular special volumes for inserting data bits. Harte et al. [8] presented a blind watermarking scheme in which the embedded vertices are confined within ellipsoid or rectangular volumes.
Some works performed data embedding using spherical coordinates (r,θ,φ) as was firstly proposed by Zafeiriou et al. [9]. In this work, he restricted the displacements to set vertices having the coordinate θ within specific ranges in order to achieve robustness against mesh simplifications.
Topological methods proceed with data embedding by altering the connectivity and other topologic features of the mesh. Mao et al. [10] suggested subdividing triangles and inserting the data in the newly formed vertices. This method is robust to affine transformation. The triangle flood algorithm [6] of Benedens generates a unique path in the mesh, based on topological and geometric information, along which the data is inserted.
Basically, spectral methods embed the data in certain coefficients of harmonic or multi-scale transform. Inspired by the Laplacian matrix-based mesh compression of Karni and Gotsman [11], several methods used the Laplacian coefficients for data embedding in different variants. Ohbuchi et al. [12] applied this paradigm to mesh model. They applied eigenvalue decomposition of a Laplacian matrix derived from mesh connectivity. Cayre et al. [13] developed a blind method employing piece-wise Laplacian decomposition.
Wu and Kobbelt [14] proposed a robust and fast spectral watermarking scheme for large meshes using a new orthogonal basis functions based on radial basis function. In order to enhance further the robustness against attacks, Praun et al. [15] developed a method based on the principles of spread-spectrum watermarking, previously employed in images, sound, and video. Yan Liu et al. [16] proposed the use of the Fourier-Like Manifold Harmonics Transform (MHT).
Multi-scale methods used mostly the wavelet transform (WT). Here data bits are inserted in the WT coefficients. Kanai et al. [17] non-blind method was among the first attempts in this category. They used the multi-resolution decomposition of Eck and al [18].
Ucchedu et al. [19] presented a novel algorithm whereby the vertices at a given resolution-level and the related coefficients at the same level are used for bit insertion. Yin et al. [20] rather employed Burt-Adelson pyramid decomposition . Hoppe et al. [24] proposed a multi-resolution framework based on the edge-collapsing operator.
Other authors such as [21–23] found advantages (increasing the capacity and enhancing the robustness) in using the spherical variants of the multi-resolution analysis such as [23] with its spherical parameterization, [21, 22] which proposed the use of spherical wavelet transform and [25] whom proposed the concept of Oblate Spheroidal Harmonics.
2.2Fragile methods
Fragile watermarking is used for checking the authenticity and the integrity of 3D mesh model. In this context the watermark is meant to be sensitive to the least amount of mesh modifications as well as to indicate the locations of such modification in the mesh. As for robust watermarking, methods in the category can be segmented into spatial and spectral methods.
Yeung and Yeo [26, 27] pioneered fragile watermarking of 3D models for verification purposes by extending a 2D image watermarking to 3D. They proposed the idea of moving the vertices to new positions so that each vertex would have the same value for two different and predefined hash functions. Attacks can then be revealed by the presence of vertices that do not comply with aforementioned condition. In this method the hash function requires a predefined order of the vertices within the 1-ring neighborhood, otherwise the scheme becomes vulnerable to the causality problem. Ohbuchi et al. [28] method imbeds the data on a facet quadruples (a facet and its three adjacents) across the whole mesh. The quadruple facets must satisfy similarity conditions, dubbed, Triangle Similarity Quadruple (TSQ), that is used to recall them when the embedded information is retrieved. Each quadruple stores four symbols composed of marker, subscript and two information data. These are embedded in the dimensionless features of the triangles (e.g. edge ratios), modifying the vertices’ positions. To avoid the causality problem the facet quadruples should not be connected to each other.
Lin et al. [29] approached the causality problem by proposing a rearrangement of the pixels harmless to the embedded watermark and making the two hash functions depending only on the position of the current vertex. Chou et al. [30] proposed a watermarking mechanism in which one of the hash functions is dependent on the mean of the 1-ring vertex neighborhood. This mean is kept stable after watermarking by adjusting a vertex associated to the watermarked vertex.
High capacity steganographic methods, where the integrity of the hidden data is a requirement, can be also classified as fragile. In these methods too, vertices are altered to embed data bits. The larger the number of bits, the higher will be the capacity of the method. Cayre and Macq [31] proposed a two-stage blind method where, at first they select a candidate stripe of triangles, and then perform a bit embedding by projecting a triangle summit on the opposite edge segmented into two equal intervals. A facet is assigned the bit 0 or 1 depending on in which segment the projection occurred. The synchronization used some local (e.g. largest facet) or global (e.g. facet intersecting the largest principal axes) geometrical features. Bors [32] proposed a blind watermarking method that locally embeds a string of bits on a set of vertices selected and ordered based on a certain distortion visibility criterion. The vertices associated to 0 (respectively 1) are shifted outside (respectively inside) a bounding volume. He proposed two variants, in the first one, the bounding volume is an ellipsoid defined by the principal axes of the covariance matrix computed over the set 1-ring neighborhood, whereas in the second, bounded parallel planes are used. Here the vertex is moved along or opposite to the plane’s normal depending on the bit value assigned to it.
A fragile method acting on the mesh connectivity, dubbed Triangle Strip Peeling Symbol Sequence, was also introduced by Ohbuchi et al. in [28]. The method consists in cutting out a stripe from the mesh except the attaching edge that marks the start of the stripe. The stripe is formed by repeatedly appending adjacent facets through a path encoded in the message data. The stripe can be shaped as a meaningful pattern that becomes visible when the mesh undergoes global connectivity alteration. However, in this method the watermark cannot spread over the whole mesh, and therefore it cannot be employed for integrity authentication.
In the frequency space, geometrical wavelet transform has been an attractive tool. Here the watermark is inserted by altering the wavelet-transform coefficients computed at each facet or by altering the facets at a given wavelet transform resolution to equate a predefined function. Cho et al. [33] followed the latter paradigm by embedding the watermark data in facets of the lower resolution of the wavelet transform. This method suffers, however, from the causality problem. The method of Wang et al. [34] alters rather the module and the orientation of the one-level WT coefficients to keep a same watermark symbol across the whole facets. This scheme has been also extended to multi-resolution levels in [35].
3ORF representation
The ORF representation is a structure in which triangular facets are arranged and ordered in a sequence of concentric rings that emanates from a root or seed facet. This representation has been inspired from the observation of the arrangement of triangular facets lying on a closed contour of edges (Fig. 1.a). We classify these facets into two groups: 1) the Fout facets, comprising facets having an edge on the contour and pointing outside the area delimited by the contour, and 2) the Fin facets, comprising facets having a vertex on the contour and that point inside the area delimited by the contour. We also notice that the Fgap facets seem to fill the gaps between the Fout facets. Together, these two groups form a kind of ring structure. From this ring, we can derive a new group of Fout facets that are one-to-one adjacent with their Fgap facets. These new Fout facets will, in their turn, form the basis of the subsequent rings (Fig 1.b). By iterating this process, we obtain a group of concentric rings. These rings can be centered on a specific facet by setting the closed ring to the edges of that facet (Fig 1.c). Moreover, the sequence of facets across each rings can be ordered clock-wise or anti-clockwise (Fig 1.d).
The algorithm ORF_Rings has a computational complexity of O(n) where n is the number of facets in the rings. The function GetRing extracts the sequences of Fgap facets across the pairs of consecutive Fout facets, constructs the new ring and derives the Fout facets for the subsequent ring. The circular arrangement within one ring implicitly produces a spiral-wise ordering of the facets across the concentric rings.
The algorithm for constructing the ORF rings is as follows:
Algorithm ORF_Rings
Rings ←ConcentricRings(Fin_root, Fout_root)
Rings←[ ]; Fgap ←Fin_root ; Fout←Fout_root
For i = 1:NumberOfRings
(Ring, NewFout, NewFgap)←GetRing(Fout, Fgap)
Append Ring to Rings
Fout ←NewFout
Fgap←NewFgap
End For
End ORF_Rings
4Applications
This section exhibits the generality of the ORF framework by adapting it to 3D mesh watermarking. Section “Data embedding of 3D triangular mesh models using ordered ring facets” describes a novel fragile method for embedding binary data in triangular mesh models based on the ORF rings. Section “A Robust 3D Triangular Mesh Watermarking using ordered ring facets” exposes the watermarking process in 3D mesh model of a new robust method employing also the ORF structure.
4.1Data embedding of 3D triangular mesh models using ordered ring facets
In this section we will describe the data embedding process in 3D mesh model employing the ORF structure and we will discuss its features and properties with respect to different data embedding scenarios. In the rest of the paper, we will refer to the embedded data by the term “payload” employed in stenography context.
4.1.1Selection of the root facet
Usually, the choice of the first triangle is based on either local properties, e.g. the largest/smallest facet areas or global properties, e.g. the facet intersecting the major axis of the object principal axes. The method we propose exploits the ORF structure to set a secure starting facet that can be identified using a secret key, which we refer to by key 0. The key is a specific sequence of bits embedded in the 2nd and the 4th ring of the ORF. Therefore any facet can serve as a first key, provided it is marked by the secret key with which it can be identified. This secret key will be then part of the embedded data.
4.1.2ORF bit embedding
The data embedding process uniformly spread the payload across the 3D mesh model by following the traversal path implicitly defined in the ORF rings. Indeed, the facets within the ORF rings are arranged in a kind of a spiral path that spans the whole model starting at the first facet. This ordering aspect allows data embedding in different ways depending on the nature of the application. For example, for model integrity verification, the payload can be inserted at equally spaced and ordered locations within this path. Integrity checking can then be easily and efficiently performed by parsing the path, retrieving and checking the payload at each specific location. For stenography applications, where the 3D mesh model is used to hide a secret data, the payload can also be spread across the whole path. Moreover, the ordered structure of the ORF allows different encrypting scenarios. In this paper, we will showcase a data embedding process within this latter scope.
Figure 2 depicts the different stages of the embedding process, illustrated over a sphere mesh model. First the ORF rings are extracted from the mesh model then they are sampled (sampling parameter τ). The sampling aims to avoid having adjacent rings. Afterwards the rings’ indexes are scrambled. This ring sampling and scrambling compose the first layer of encryption. Their related parameters (e.g τ and the scrambling code are stored in the encryption key labeled key 1. Afterwards a second layer of encryption is applied using a circular shifting of the facets in each ring followed by a sampling of order ρ. Each ring will have its own shifting value. The groups of shift values and the sampling parameter ρ constitute the third encryption key (key 2), to be used, together with the key 0 and key 1, for retrieving the embedded data. Assuming a reasonably tessellated mesh, the set of facets that come out from stage 2 are uniformly spread over the mesh model surface. In the last stage the payload is embedded in this set at the cadence of one bit per facet. Here we employed the embedding technique of Cayre and Macq [31], but other bit embedding techniques can be used as well. In Cayre and Macq method, basically, one vertex is projected into its opposite edge, which is divided in two equal intervals, coded 1 and 0. If the projection falls in the interval that matches the embedded bit (for instance, it falls in the interval 1 and the bit to be embedded is 1), then the vertex is kept unchanged. Otherwise it is shifted collinearly with that edge, and within the facet’s plane, to a new location for which the projection meets the good match.
The sampling performed in stages 1 and 2, aims to ensure isolation between the tampered, that carry the payload, so that they cannot share an edge or a vertex. The appropriate values of τ and ρ depend on the regularity of the mesh. For a uniform mesh, τ = 2 and ρ = 3 can guarantee compliance with the aforementioned condition.
The uniform sphere mesh model depicted in Fig. 2 is an example of this case. When the mesh exhibits some irregularities, larger values might be needed.
4.1.3Data extraction
The data extraction process is virtually similar to the embedding process. The starting facet should be firstly detected. Here the key 0 is used to inspect the four rings around the candidate facet. Afterwards, the rest of the ORF are extracted then browsed in the order and at the sampling rate encoded in Key 1. Then the facets in each ring are parsed according to the parameters encoded in key 2.
4.1.4Causality problem
Our method offers control mechanism allowing data embedding free from the causality problem. Such a problem happens when an anterior tampered facet (e.g. already carried a bit) is to be affected by a posterior one (e.g a newly tampered). This might corrupt the content of the former facet. Usually this problem occurs between neighbouring facets. The size of the neighbourhood depends on the embedding technique and on how many facets surrounding the tampered one can be affected. This problem is addressed by inserting a flag data in or around the tampered facets so that these will not be embedded again when revisited during the mesh traversing. In our method, a proper setting of the sampling parameters τ and ρ ensures sufficient spaces between the tampered facets preventing any mutual alteration, avoiding therefore the need for flagging and checking procedures. In the technique of Cayre and Macq [31], which we have used, only facets sharing the displaced vertex of the tampered facet are affected. Therefore, for a regular mesh, setting the sampling parameters τ and ρ to 2 and 3, respectively, any triangles connected to the tampered facet, either by an edge or a vertex, cannot be the subsequent tampered one. However, depending on the state of the mesh, τ and ρ might need to be increased.
4.1.5Capacity
The total number of facets N can be expressed by where M is the number of ORF rings and mi is the number of facets in the ith ring. Considering the sampling parameters τ and ρ, the number of facets can be expressed by The number of tampered facets can be evaluated in average to N /(τ × ρ) bits. Assuming a uniform mesh in which the facets have close area and edge values, τ = and ρ can be set to 2 and 3, respectively, the number of embedded facets can reach N /6.
4.1.6Security
Accessing the payload requires addressing three challenges in our algorithm, namely, finding the root facet, finding the ring sampling rate τ and the correct combination of ring order, and finally finding the facet sampling rate ρ and the facet shifting value at each ring. These three cascading stages of encryption give our scheme a high level of security. Exhaustive search is virtually out of reach, indeed the number of encryption combination in our scheme is evaluated to
Where N is the number of facets in the mesh, M is the number of rings, nτ and nρ are the numbers of possible values of the sampling parameters τ and ρ, and mi is the number of facets in the ith ring. Such a number makes the extraction of the payload without the encryption code nearly impossible.
4.1.7Mesh distortion
For mesh models with a single topology, Haussdorff distance has been adopted as an objective metric for evaluating the mesh distortion inferred by the data embedding. The computation of the Haussdorff distance is time demanding because of its quadratic complexity (O(n2)). In our method, the computation of the mesh distortion is brought down to a linear complexity O(n). In effect, the linear traversal path embedded in the ORF structure allows a one-to-one mapping between the original model and the embedded model facets. Based on this mapping, we can simply express the mesh distortion with the following formula
where u and v form the pair of corresponding facet edges in the original and embedded model respectively, ¯u is the mean of facet edge in the original model, and N is the number of facets.
4.1.8Integrity checking
As the embedding is uniformly spread over the whole model, our method can be used for checking the integrity of the mesh model by comparing the extracted payload (formatted as a string of bits), and matching it with its reference counterpart. A mismatch indicates that the model has been altered. The indexes of the mismatches in the string of bits can be easily mapped to the facets’ indexes, and thus used to trace the locations of the attacked areas. Moreover, the global mesh alteration can be evaluated using the following simple formula
where Ω and Υ are the original and the retrieved strings and M is their length.
4.1.9Robustness
Being dedicated to stenography applications, the method is robust to affine and similarity transforms, namely, translation, rotation, uniform scaling, and affine transforms. It is also resistant to vertices and facets reordering. It is not robust against geometrical or topological transformation such as cropping, simplification, and mesh resembling. These kind of attacks corrupt the message content.
4.1.10Experiments
We applied on several mesh models collected from the 3D mesh watermarking benchmark [36]. The models are bunny, horse, rabbit, and venus. We used a PC-based 2.93 GHz, 8 GB RAM. The implementation was performed under Matlab. Table 1 depicts the list of the models, their corresponding sampling parameters, and the related performance measures. The embedding capacity represents the number of bits embedded in the model, which is also equal to the number of tampered triangles, since the embedding technique inserts one bit per triangle. The distortion is computed using equation 2. The different models show a capacity in the range of 7%–14%. However this could be further increased by inspecting further each ORF ring to locate other free facets. The distortion shows quite low values. It seems inversely proportional with the sampling parameters. This is expected as the number of tampered facets increases as the sampling decreases. The processing time seems to increase at a fair rate because of the linear complexity of our method. This aspect is confirmed in another experiment, performed with the horse model, in which we computed the embedding time for increasing sizes of the payload (Fig. 4). The growth rate of the processing time confirms clearly the linear complexity property of our method.
Tab. 1. Results obtained for the tested models.
4.2A robust 3D triangular mesh watermarking using ordered ring facets
The proposed method embeds watermark into 3D triangular mesh model by modifying the component spherical φ of some vertex according to assigned watermark bit and distribution of φ. The watermark embedding process is illustrated in Fig. 5.
4.2.1Watermark embedding process
The general algorithm of embedding decomposes into several steps. We embed the watermark by altering vertex position. The signature can be destroyed before extraction by the affine transformation (rotation, translation or scaling) which displaces the vertex from their original coordinate. To address this problem we normalized the mesh by translating the mesh from its center to the center of gravity. Then, we align the principal components of the mesh with the standard axes given by principal component analysis PCA. Second, Cartesian coordinates of a vertex vi=(xi, yi, zi) (for 1 ≤ i ≤ N where N is the number of the vertex) are converted into spherical coordinates (ri, θi, φi). The proposed method uses only the radial distance φ for watermarking. Note that we have verified that φ is the most invariant to attacks. Third, we select a region where we have the minimum variance of spherical coordinate’s φ. From this region, we choose the embedded vertex uniformly spread over the whole selected region using the ordered ring facets. As facets of each ORF ring are arranged in order, we have followed a defined path for insertion. This aspect facilitates also the recovery of signature embedded at spaced locations. For each facet, we generate a set of 10 rings. Then, we select the ring 1, 3, 5, 7 and 9 to be watermarked, in order to avoid having adjacent rings and facets. The ORF ring is formed by two groups of facets: Fout facets and Fgap facets. As the sequence of facets across each ring is ordered, we choose to embed a signature into Fout facets. This type of facets has an edge on the contour and a vertex V pointing outside the area delimited by the contour. Only several selected V vertices will be affected. The next step of the proposed watermark embedding is to insert signature (one bit per facet). The basic idea is to modify the component spherical φ of this vertex function of the bit to be inserted and an interval I defined as follows
Where μ is the mean and σ2 is the variance of the components φ of the vertices of each ring selected excluded the watermarking vertices. To embed a watermark bit of 1, vertex component φ is transformed in order to be in the interval I. alternatively, to embed 0, vertex component φ is transformed in order to move outside I. Finally, the watermark embedding process is completed by converting the spherical coordinates to Cartesian coordinates and by mesh renormalization.
4.2.2Watermark extraction process
The algorithm of detection is similar to the watermark embedding process. The watermarked mesh model is first normalized and converted to spherical coordinates. After finding the region of minimum variance of φ, we exploit the ORF rings to detect the watermarked vertex. Then, we calculate the interval I. The watermark hidden W’ is extracted finally by means of:
4.2.3Experimental results and evaluations
To evaluate the proposed approach, it is applied on a different mesh models used usually in 3D watermarking application. Only four examples are presented here: Bunny (12942 vertices, 25736 facets), Horse (7377 vertices, 14750 facets), Elephant (12471 vertices, 24950 facets), David_head(12865 vertices, 25640 facets). Naturally, the watermarking process should verify a good visual imperceptibility of the watermark. To measure the quality distortion, we used Metro [37]. This method consists to calculate the Hausdorff Distance HD between the original mesh model and watermarked one. To measure the HD the following formula is used:
Where M1= (V, V’) and M2 = (V’, V), (V and V’ represent respectively the original mesh and watermarked mesh).
h(M1)= max{min(d(a,V’))}, a in V,
h(M2)= max{min(d(b,V))}, b in V’.
The robustness is measured by calculating the correlation between the original and the extracted signature.
Where 
is the average of the signature and corr in [−1,1].
In the simulation, we embedded between 15 and 20 bits of watermark depending on the number of selected facet. The performance in term of HD and correlation are listed in Tab. 2 when no attack. Here, the number of initial facet and the value of variance of the selected region before and after watermarking are also listed. It shows that we obtained the same region. So we can conclude about the stability of the selected region. The low result of HD proves the good invisibility.
To evaluate the robustness, many attacks are tested. First, we have tested the watermark against the affine transformations (rotation, translation or scaling). We succeed to recover the signature after these three attacks. This is obtained through to normalization of the mesh. The next step, we evaluate the resistance to smoothing with different number of iteration. The watermark resists, if the parameter of smoothing is lower than 30 iterations. After that, we studied the robustness against noise attack by adding binary random noise to each vertex coordinates in the watermarked model. For the models tested, we can detect the signature after adding noise with different percentages. In the last step, we tested our method against simplification and subdivision attacks. However, we have a difficulty to detect the signature due to the adding or the simplification of the number of facet.
Tab. 2. Evaluation of watermarked meshes when no attack.
5Conclusion
In the paper, we have showcased new paradigms for embedding data in 3D triangular mesh model, based on Ordered Rings Facets. This representation is characterized by the innovative aspect of intrinsically embedding a structured and ordered arrangement of the triangular facets of the mesh surface. Our methods benefit from the advantages of this structure. Compared to other embedding methods, our methods are distinguished by an automatic traversal of the mesh model, an immunity mechanism against causality problem.
We applied this embedding paradigm to stenography and robust watermarking scenarios. The stenography method presents a linear complexity of the embedding process and a high encrypting power. It is also robust against translation, rotation, scaling, vertex and facets reordering. In addition to stenography, our paradigm can be easily adapted to fragile watermarking and authentication. The robustness of our robust watermarking method was verified after application of various types of attacks such as affine transformations (rotation, scaling and translation), smoothing and random noise added to vertex coordinates.
For the moment our watermarking scheme is not robust against sever topologic attacks. This is a point which we will address in a future work. Also, the embedding capacity is one of the aspects that deserves some improvements. At the current state, our paradigm ensures an embedding automatically free of the causality problem, but seemingly at the expense of the embedding capacity. We plan to further investigate this issue so that we can reach a better compromise. One technique which we are currently studying is replacing the fixed-rate sampling at the ring level, with a kind of adaptative sampling whereby the sampling step is adjusted according to the facet’s neighbourhood in the ring. Finally our fragile approach is not qualified to deal with the genius 2 models, exhibiting holes and gaps.
Bibliography
[1]N. Werghi, M. Rahayem, J. Kjellander. An ordered topological representation of 3D triangular mesh facial surface: Concept and applications. EURASIP Journal on Advances in Signal Processing, 144, 2012.
[2]N. Werghi, M. K. Naqbi. A novel surface pattern for 3D facial surface encoding and alignment. Proc. IEEE SMC, 902–908, 2011.
[3]O. Benedens. Geometry-Based Watermarking of 3D Models. IEEE Computer Graphics and Applications, 46–55, January 1999.
[4]J. W. Lee, S. H. Lee, K. R. Kwon, K. I. Lee. Complex EGI Based 3D Mesh Watermarking. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 88(6): 1512–1519, 2005.
[5]S.H. Lee, K.R. Kwon. A Watermarking for 3D Mesh Using the Patch CEGIs. Digital Signal Processing, 17(2):396–413, March 2007.
[6]O. Benedens. Two High Capacity Methods for Embedding Public Watermarks into 3D Polygonal Models. In Proc. Of the Multimedia and Security Workshop at ACM Multimedia , Orlando, FL, 95–96, 1999.
[7]C.T. Kuo, D.C. Wu and S.C. Cheng. 3D Triangular Mesh Watermarking for Copyright Protection Using Moment-Preserving. 2009 Fifth Int Conf on Intelligent Information Hiding and Multimedia Signal Processing, 136–139, 2009.
[8]T. Harte and A. Bors. Watermarking 3d models. In Proc. of Int Conf on Image Processing (ICIP), Rochester, NY, USA, 3:661–664, Sep 2002.
[9]S. Zafeiriou, A. Tefas, and I. Pitas. Blind Robust Watermarking Schemes for Copyright Protection of 3D Mesh Objects. IEEE Transactions on Visualization and Computer Graphics,11:596–607, 2005.
[10]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 Security and Watermarking of Multimedia Contents III, 253–260, 2001.
[11]Z. Karni and C. Gotsman. Spectral compression of mesh geometry. Proc. SIG-GRAPH, 279–286, 2000.
[12]R. Ohbuchi, A. Mukaiyama, S. Takahashi. A Frequency-Domain Approach to Watermarking 3D Shapes. Computer Graphics Forum 21(3): 373–382, Sep 2002.
[13]F. Cayre, P.R. Alface, F. Schmitt, B. Macq, H. Maitre. Application of Spectral Decomposition to Compression and Watermarking of 3D Triangle Mesh Geometry. Signal Processing 18(4):309–319, Apr 2003.
[14]J. Wu, L. Kobbelt. Efficient Spectral Watermarking of Large Meshes with Orthogonal Basis Functions. Visual Computer 21: 848–857, 2005.
[15]E. Praun, H. Hoppe and A. Finkelstein. Robust Mesh Watermarking. ACM SIGGRAPH’99 Conference Proceedings, 1999.
[16]Y. Liu, B. Prabhakaran, and X. Guo. A Robust Spectral Approach for Blind Watermarking of Manifold Surfaces. The 10th ACM Workshop on Multimedia and Security, 43–52, 2008.
[17]S. Kanai, H. Date, T. Kishinami. Digital Watermarking for 3D Polygons Using Multiresolution Wavelet Decomposition. In Proc of the International Workshop on Geometric Modeling, 296–307, 1998.
[18]M. Eck, T. D. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle. Multiresolution Analysis of Arbitrary Meshes. in Proc. of the ACM SIGGRAPH Conference on Computer Graphics’95, 173–180, 1995.
[19]F. Uccheddu, M. Corsini, and M. Barni. Wavelet based Blind Watermarking of 3D Models. In MM & Sec Proceedings of the 2004 workshop on Multimedia and security, New York, NY, USA, 143–154, 2004.
[20]K. Yin, Z. Pan, J. Shi, D. Zhang. Robust Mesh Watermarking Based on Multiresolution Processing. Computers and Graphics 25:409–420, 2001.
[21]J. Q. Jin, M. Y. Dai, H. J. Bao, Q. S. Peng, Watermarking on 3D Mesh Based on Spherical Wavelet Transform, J.Zhejiang Univ, 5:251–258, 2004.
[22]J.J. Qiu, D.M. Ya, B.H. Jun, and P.Q. Sheng,Watermarking on 3D mesh based on spherical wavelet transform, J. Zhejiang Univ. 5:251–258, 2004.
[23]L. Li, D. Zhang, Z. Pan, J. Shi, K. Zhou, K. Ye, Watermarking 3D Mesh by Spherical Parameterization, Computers and Graphics 28:981–989, 2004.
[24]H. Hoppe. Progressive Mesh. in Proc. of the ACM SIGGRAPH Conference on Computer Graphics’96, 99–108, 1996.
[25]J.M. Konstantinides, A. Mademlis, and P. Daras. Blind Robust 3D Mesh Watermarking Based on Oblate Spheroidal Harmonics. IEEE Transactions on Multimedia, 23–38, 2009.
[26]M.M. Yeung, B.L. Yeo. Fragile watermarking of three dimensional objects. Proc.IEEE Int. Conf. Image Processing, ICIP98, 2:442–446, 1998.
[27]B. Yeo and M. M. Yeung. Watermarking 3D objects for verification. IEEE Computer Graphics and Applications, 19(1):36–45, Jan.-Feb. 1999.
[28]R. Ohbuchi, H. Masuda, and M. Aono. Data Embedding Algorithms for geometrical and non-geometrical targets in three-dimensional polygonal models. Computer Communications archive 21(15):1344–1354, 1998.
[29]H.S. Lin, H. M. Liao, C. Lu, and J. Lin. Fragile watermarking for authenticating 3-D polygonal meshes. IEEE Transactions on Multimedia, 7:997–1006, 2005.
[30]C.M. Chou and D.C. Tseng. A public fragile watermarking scheme for 3D model authentication. Computer-Aided Design, 38:1154–1165, 2006.
[31]F. Cayre and B. Macq. Data hiding on 3-D triangle meshes. IEEE Transactions on Signal Processing, 51(4):939–949, April, 2003.
[32]A.G. Bors. Watermarking mesh based representations of 3D objects using local moments. IEEE Transactions on Image Processing, 15:687–701, 2006.
[33]W.H. Cho, M.E. Lee, H. Lim, and S.Y. Park. Watermarking technique for authentication of 3D polygonal meshes. Proc. of the International Workshop on Digital Watermarking, 259–270, 2005.
[34]K. Wang, G. Lavoue, F. Denis, and A. Baskurt. A fragile watermarking scheme for authentication of semi-regular meshes. in Proc. of the Eurographics Short Papers, 2008.
[35]K. Wang, G. Lavoue, F. Denis, and A. Baskurt. Hierarchical blind watermarking of 3D triangular meshes. in Proc. of the IEEE International Conference on Multimedia and Expo, 1235–1238, 2007.
[36]K. Wang and G. Lavoue, F. Denis, A. Baskurt, X. He. A benchmark for 3D mesh watermarking. Proc. of the IEEE International Conference on Shape Modeling and Applications, 231–235, 2010.
[37]P.Cignoni, C. Rocchini, R. Scopigno. Metro: Measuring error on simplified surfaces. Computer Graphic Forum, 17(2):167–174, 1998.
Biographies
Naoufel Werghi received PhD in Computer Vision from the University of Strasbourg. He has been a Research Fellow at the Division of Informatics in the University of Edinburgh, Lecturer at Department of Computer Sciences in the University of Glasgow. Currently, he is Associate Professor at the Electrical and Computer Engineering Department in Khalifa University, UAE. His main research area is image analysis and interpretation where he has been leading several funded projects in the areas of biometrics, medical imaging, geometrical reverse engineering, and intelligent systems. He published more than 70 journal and conference papers.
Nassima Medimegh received her research masters in Intelligent and communicating systems; option Signals and Communicating Systems in 2013 and diploma informatics engineering from national school of Sousse, Tunisia in 2011. Her research interests are in the general areas of image processing, 2D and 3D watermarking.
Sami Gazzah is an Assistant Professor in the Department of Telecommunication at the Higher Institute of Computer Sciences and Communication Techniques of Hammam Sousse from University of Sousse. He received the engineering degree and the Ph.D degree both in electrical Engineering from National Engineering School of Sfax/Tunisia. His research interests include intelligent Systems and computer vision.