Robust Image Watermarking on Triangle Grid of Feature Points

Abstract

The paper presents a digital image watermarking technique robust to geometric distortions. This technique is based on a novel procedure of building a set of primitives for embedding using Delaunay triangulation on a set of feature points, and uses additive embedding method with linear correlation detector. Much attention is paid to the problem of choosing the most appropriate feature points detector. Conducted experiments demonstrate robustness of the proposed method to a range of geometric distortions.

1 Introduction

One of the most advanced techniques for copyright protection of digital images is robust watermarking. The major issue concerning this technique is achieving robustness to various geometrical distortions of an image being protected. There are two commonly used methods to solve this problem. The first approach suggests embedding a watermark into coefficients of an invariant to geometrical distortions transform. The most widely used is Fourier-Mellin transform [1, 2], since it is invariant to the most common distortions: rotation, scale and translation, usually abbreviated as RST. Such methods are described in [3–5]. The second approach uses so-called feature, or interest points robust to geometrical transformations, which define regions for embedding in spatial domain. In this paper we call these regions primitives for embedding. The second approach potentially allows constructing a watermarking system robust to a wider range of geometrical distortions than RST.

Bas et al. in [6] proposed a rather promising method which uses feature points. In their algorithm, a set of feature points is used to build a Delaunay triangulation and a watermark is embedded in each of the triangles independently. It is possible to identify locations of the watermark primitives at the extraction stage with high accuracy, provided the image didn’t undergo any non-affine transformation and a large number of the source feature points were detected.

However, the suggested system has several drawbacks. First and foremost, embedding in triangles demands usage of a triangular-shaped reference watermark pattern, forcing a stair-step border of the reference pattern due to discrete nature of digital images as well as leading to potential problems with the mapping of the pattern to a particular triangle in the image. Moreover, Harris corner detector used in [6] to find a set of feature points might not be the most suitable for the task.

This paper describes a digital watermarking system that achieves robustness to geometrical distortions by means of feature points. Following the same lines of Bas’ method, we only left the triangulation step unchanged and enhanced all the others. In Sect. 2 we describe the procedure of choosing the most appropriate feature points detector and present the corresponding results. In Sect. 3 we propose a method of building a set of primitives for embedding as well as a procedure of forming a signal to be embedded. Section 4 describes embedding and detection procedures. Finally, in Sect. 5 we show some results of experimental research of the developed system.

2 Feature Points Extraction

In our search for the most suitable detector for the watermarking system we investigated three feature point detectors: Achard-Rouquet et al. [7], Harris and Stephens [8] and Scale Invariant Feature Transform (SIFT) [9]. To do this we calculated the performance quality measure for each of them using the following steps:

• 1. Searching for a set of feature points $P_{orig}$ on the source image.

• 2. Altering the image by i ^th transformation (listed below).

• 3. Searching for a set of feature points $P_{dist,i}$ on the altered image.

• 4. Building Delaunay triangulation $Tri_{dist,i}$ using the set $P_{dist,i}$.

• 5. Calculating $S_{dist,i}$:

  $$ S_{dist,i} = \frac{{TP_{i} }}{{N_{i} }}, $$

  (1)

  where $TP_{i}$ denotes the number of triangles in $Tri_{dist,i}$ such that all of their vertices belong to the set $P_{orig}$, $N_{i}$ is the number of triangles in $Tri_{dist,i}$.

• 6. Obtaining the overall quality measure S:

  $$ S = \frac{1}{M}\mathop \sum \limits_{i} S_{dist,i} , $$

  (2)

  where M is the number of applied distortions.

The distortions used in the experiment:

• Rotation (angles ranging from 20° to 220° with step 20°) followed by the subsequent inverse rotation by the same angle.

• Scaling (factors ranging from 0.9 down to 0.5 with step 0.1).

• JPEG compression (ratios ranging from 90 down to 50 with step 10).

• Noise addition (a uniform noise with absolute peak values ranging from 50 down to 10 with step 10 for 256 grayscale image levels).

For the present and all the following experiments we used seven images from the well-known Waterloo test set [10] (cf. Fig. 1). The results are presented in Fig. 2. It is clear that SIFT detector in most cases shows superior performance compared to the other detectors on all test images, which suggests that the most appropriate detector is SIFT. Consequently, we decided to choose it for our system.

Fig. 1.

Test images: barb, boat, bridge, goldhill, lena, mandrill, peppers

Fig. 2.

Values of quality measure S for three feature point detectors on test images. Grey bar denote Harris detector, black – Achard-Rouquet, white – SIFT

3 Building a Set of Primitives for Embedding

Having found a set of highly repeatable feature points, we can build areas for embedding a watermark pattern, called primitives for embedding. First, a Delaunay triangulation is built over the set of the feature points. It has several valuable properties: it is uniquely defined for a given set of points, it maximizes the sum of the minimum angles of triangles hence it consists of triangles that are close to equilateral [11]. In addition, there exist efficient algorithms for building Delaunay triangulation.

We could use the triangles as possible primitives but, unfortunately, there are problems associated with the mapping of a triangular-shaped reference pattern to a particular triangle. Specifically, consider one possible approach suggested in [6]. A reference mark has the shape of a right-angled triangle; the mapping is done based on the angles of the two triangles such that the right angle of the reference pattern is mapped to the largest angle of the extracted triangle (as illustrated in Fig. 3). However, such an approach may lead to numerous errors while working with triangles which are close to equilateral (recall that Delaunay triangulation tends to build such triangles). In addition, we have to deal with the already mentioned problem of approximating a stair-step border of a reference triangle.

Fig. 3.

Mapping of reference pattern (a right-angled triangle) to arbitrary triangle, as suggested in [6]

To alleviate these issues we decided to use quadrangles as primitives for embedding. To obtain the new primitives every triangle is split into three quadrangles by the point of intersection of the medians (as illustrated in Fig. 4). In that case the reference pattern is a matrix (square or rectangular) of values ±1. To map it to an arbitrary quadrangle, the quadrangle is first split into regular grid with the number of rows and columns matching the number of rows and columns of the reference matrix. Then each element of the reference matrix is mapped to the corresponding cell of the grid (cf. Fig. 5). This way two of the four vertices can always be identified as being a feature point and the point of intersection of the medians (points A and D in Fig. 4, respectively), so the mapping can always be defined uniquely.

Fig. 4.

Splitting of triangle ABC into three quadrangles: AEDG, BEDF, CGDF

Fig. 5.

Splitting of a quadrangle into regular grid and mapping reference pattern (a matrix of ±1) to the cells of the grid

Mapping the reference pattern to every quadrangle we obtain an image $w\left( {n_{1} ,n_{2} } \right)$ that consists of the values ±1 or 0 and which size is equal to the size of the image being processed. The left of the Fig. 6 illustrates an example of $w\left( {n_{1} ,n_{2} } \right)$ for a reference pattern of the size 8 × 8. We call $w\left( {n_{1} ,n_{2} } \right)$ the embedded signal since it is the entity that we actually embed in the image.

Fig. 6.

Example of embedded signal $w\left( {n_{1} ,n_{2} } \right)$ and result of embedding in mandrill test image. Black, grey and white pixels denote −1, 0 and 1

4 Embedding and Detection Algorithms

4.1 Embedding Algorithm

The embedding begins with forming an embedded signal $w\left( {n_{1} ,n_{2} } \right)$. A reference pattern is mapped to every quadrangle; therefore the procedure is redundant which results in an increase of the system’s robustness. The embedding of the obtained embedded signal is done according to the additive model:

$$ C^{W} \left( {n_{1} ,n_{2} } \right) = C\left( {n_{1} ,n_{2} } \right) + \alpha \left( {n_{1} ,n_{2} } \right) *w\left( {n_{1} ,n_{2} } \right), $$

(3)

where $C\left( {n_{1} ,n_{2} } \right)$ is the source image, $C^{W} \left( {n_{1} ,n_{2} } \right)$ is the watermarked image, $w\left( {n_{1} ,n_{2} } \right)$ is the embedded signal, and $\alpha \left( {n_{1} ,n_{2} } \right)$ denotes coefficients that shape the embedded signal according to the characteristics of the human visual system. In our research we used the following mask proposed by Piva et al. [12]:

$$ \alpha \left( {n_{1} ,n_{2} } \right) = D \cdot \frac{{\sigma_{C, R \times R}^{2} \left( {n_{1} ,n_{2} } \right)}}{{\max_{{n_{1} ,n_{2} }} \sigma_{C, R \times R}^{2} \left( {n_{1} ,n_{2} } \right)}} , $$

(4)

where $\sigma_{C, R \times R}^{2} \left( {n_{1} ,n_{2} } \right)$ is the field of local variance of C calculated in the square window $R \times R$; and $D > 0$ is a factor.

4.2 Detection Algorithm

Our goal is to find out whether or not a given image $C^{W}$ has a watermark W embedded. First of all, we find feature points, build a grid of triangles and split each of them into quadrangles $Q_{i}$. Then, using the set of $Q_{i}$ the embedded signal $w\left( {n_{1} ,n_{2} } \right)$ is formed. Better results are obtained by preprocessing $C^{W}$ using Wiener filter. To do this, masking coefficients $\hat{\alpha }\left( {n_{1} ,n_{2} } \right)$ are estimated using the image $C^{W}$ in the same way the coefficients $\alpha \left( {n_{1} ,n_{2} } \right)$ were estimated using the source image C. This allows estimating the modulated embedded signal:

$$ \hat{w}\left( {n_{1} ,n_{2} } \right) = \hat{\alpha }\left( {n_{1} ,n_{2} } \right) *w\left( {n_{1} ,n_{2} } \right). $$

(5)

Now we can apply Wiener filter as follows:

$$ \tilde{C}^{W} \left( {n_{1} ,n_{2} } \right) = \frac{{\sigma_{{\hat{w}}}^{2} \left( {n_{1} ,n_{2} } \right)}}{{\sigma_{{\hat{w}}}^{2} \left( {n_{1} ,n_{2} } \right) + \sigma_{{C^{W} }}^{2} \left( {n_{1} ,n_{2} } \right)}}\left( {C^{W} \left( {n_{1} ,n_{2} } \right) - E_{{C^{W} }} \left( {n_{1} ,n_{2} } \right)} \right), $$

(6)

where $\sigma_{{\hat{w}}}^{2} \left( {n_{1} ,n_{2} } \right)$ and $\sigma_{{C^{W} }}^{2} \left( {n_{1} ,n_{2} } \right)$ are the local variances of $\hat{w}$ and $C^{W}$, respectively, $E_{{C^{W} }} \left( {n_{1} ,n_{2} } \right)$ is the local mean of the image $C^{W}$. All these quantities are calculated in the $9 \times 9$ local neighborhood of each point $\left( {n_{1} ,n_{2} } \right)$. The filtered image $\tilde{C}^{W} \left( {n_{1} ,n_{2} } \right)$ is used to calculate correlation values $z_{i}$:

$$ z_{i} = \frac{1}{{\mu \left( {Q_{i} } \right)}}\sum\nolimits_{{n_{1} ,n_{2} \in Q_{i} }} {\tilde{C}^{W} \left( {n_{1} ,n_{2} } \right) *w_{i} \left( {n_{1} ,n_{2} } \right)} , $$

(7)

where $\mu \left( {Q_{i} } \right)$ is the area of $Q_{i}$, and $w_{i} \left( {n_{1} ,n_{2} } \right)$ is defined as

$$ w_{i} \left( {n_{1} ,n_{2} } \right) = \left\{ {\begin{array}{*{20}l} {w\left( {n_{1} ,n_{2} } \right),} \hfill & {\left( {n_{1} ,n_{2} } \right) \in Q_{i} ,} \hfill \\ 0 \hfill & {otherwise ,} \hfill \\ \end{array} } \right. $$

(8)

i.e. its elements are equal to the corresponding elements of the embedded signal for pixels that belong to $Q_{i}$ and are zero elsewhere.

Finally, we decide that the watermark W was embedded in $C^{W}$ if

$$ Z = \frac{1}{{N_{Q} }}\Sigma _{{i = 1}}^{{N_{Q} }} z_{i} > \tau , $$

(9)

where $N_{Q}$ is the number of the primitives and $\tau$ is an adaptive threshold found as follows. Using $C^{W}$ we perform detection of a set of different from W watermarks $\left\{ {W_{j} } \right\}$ and applying (8) obtain the correlation values Z _j . Assuming Z _j are normally distributed (evidence of which are given in [6]) we calculate the sufficient statistics m and s ². Since an event $\left\{ {Z_{j} > \tau } \right\}$ results in wrong detection of the watermark W _j it is effectively a false alarm; choosing a particular acceptable value of $Pr\left( {Z_{j} > \tau } \right)$ we can find $\tau$ from this equation:

$$ Pr\left( {Z_{i} > \tau } \right) = \int_{\uptau}^{\infty } {\frac{1}{{\sqrt {2\pi s^{2} } }}e^{{ - \frac{{\left( {x - m} \right)^{2} }}{{2s^{2} }}}} dx} . $$

(10)

5 Experimental Research

5.1 Robustness to Misdetection

To assess the robustness to misdetection (when the system can’t tell the true watermark from some other and detects the latter instead of the former) we conducted an experiment. First, 100 test watermark patterns were generated and the 40th was embedded into the barb test image. Then we calculated the correlation values Z of this image and each of the test patterns using (8). As can be seen in Fig. 7, the correlation value for the true pattern is significantly greater than for any other, so it is possible to effectively distinguish between different watermarks.

Fig. 7.

Correlation values of the extracted watermark with 100 watermark patterns (barb image)

5.2 Robustness to Geometrical Distortions

To investigate the robustness of the proposed system to rotation and scaling transformations we conducted another experiment. A watermark was embedded in every test image and each of the following transformations were applied: rotation of the watermarked image by the angles ranging from 5° to 40° with step 5°, and scaling with scale factor ranging from 0.5 to 1.7 with step 0.2. Then we performed detection of the embedded watermark.

The results are presented in Tables 1 and 2. They lead us to the conclusion that the proposed system is robust to rotations by rather large angles – up to 20°–25°. As for robustness to scaling operations, it can be considered acceptable – generally a watermark withstands scaling with factors ranging from 0.9 to 1.5; it worth noting that the distortions introduced by scaling with factors less than one affect the embedded watermark more, since such transformations result in the loss of some information.

Table 1. Results of watermark detection after rotation; + indicates success

Table 2. Results of watermark detection after scaling; + indicates success

6 Conclusion

In this paper a modified version of the digital watermarking technique [6] is proposed. It uses a grid of quadrangles built on a set of feature points of an image for embedding watermarks robust to geometrical distortions. The best detector was chosen and the new method of mapping a reference pattern to the grid of the primitives for embedding was suggested. A revised algorithm for embedding a watermark into primitives aided by applying modulation of the embedded signal was developed. The experiments showed that the system achieves an acceptable level of robustness while maintaining imperceptibility of the embedded watermark.