Back
 JCC  Vol.8 No.12 , December 2020
A Robust Digital Watermarking Algorithm Based on Finite-Set Discrete Radon Transform Tight Frame
Abstract: Digital watermarking technology plays a powerful role in the effective protection of digital media copyright, image authentication, image sharing, image information transmission and other fields. Driven by strong demand, digital image watermarking technology has aroused widespread research interest and has gradually developed into one of the most active research directions in information science. In this paper, we present a novel robust digital watermarking algorithm based on discrete radon transform tight frame in finite-set (FDRT). FDRT of the zero mean image is a tight frame, the frame boundary A = B = 1, the dual of the frame is itself. The decomposition and reconstruction of the FDRT tight frame will not cause the phenomenon of image distortion. The embedding of hidden watermark is to add a weak signal to the strong background of the original image. Watermark extraction is to effectively identify the embedded weak signal. The feasibility of the watermarking algorithm is analyzed from two aspects of information hiding and robustness. We select the independent Gaussian random vector as the watermark series, and the peak signal-to-noise ratio (PSNR) as the visual degradation criterion of the watermark image. Basing the FDRT compact stand dual operator, we derived the relationship among the strength parameter, square sum of watermark series, the PSNR. Using Checkmark system, the simulation results show that the algorithm is robust enough to some very important image processing attacks such as lossy compression, MAP, filtering, segmentation, edge enhancement, jitter, quadratic modulation and general geometric attack (scaling, rotation, shearing), etc.

1. Introduction

In recent years, the research activities in digital watermarking have increased rapidly, mainly because the Internet and digital technology have brought us rich online digital images, which need effective copyright protection, image authentication, image sharing, and image information transmission [1].

The embedding of image implicit watermark is to superimpose a weak signal on the strong background of the original image. Watermark extraction is to effectively identify embedded weak signals [2]. The current researches on digital image watermarking algorithms mainly focus on three directions: based on spatial domain, based on transform domain, and based on compressed domain [3]. The visual quality of the watermark embedded in the original image brings a certain degree of degradation, so that, a good watermarking algorithm must meet three requirements at the same time: the visual quality of the watermarked image is high and reversible [4], the embedding of the watermark is good, and the algorithm is robust [5].

The embedded watermark for protection should not degrade image quality. In addition, it must be robust to distortions caused by image processing algorithms. Image processing does not modify only the image but also the embedded watermark signal as well. Thus, the watermark may become undetectable after intentional or unintentional image processing attacks. A general watermarking framework for copyright protection has been described in [6].

Most watermarking techniques in the literature involve watermark signal detection based on similarity. However, the similarity detector is optimal only if the watermark series follows a Gaussian distribution and minimizes the error probability [7].

The direct discrete Radon transform in Euclidean geometry will introduce information redundancy when describing digital images [8]. Combined with masking characteristics of visual system, this paper proposes a new watermarking embedding robust algorithm based on discrete radon transform tight frame in finite set (FDRT). The reason of embedding watermark in FDRT domain is analyzed from two aspects of invisibility and robustness, and the embedding strategy and detection algorithm of FDRT domain watermark are realized. Using the peak signal-to-noise ratio (PSNR) as an objective criterion to evaluate the quality of the watermark image, the relationship among the watermark capacity, embedding depth and the PSNR of the watermark image is derived. According to this formula, the embedding parameters of watermark can be selected adaptively under the constraint of given image quality. The final numerical experiments effectively support the above conclusions.

2. Discrete Radon Transform Tight Frame in Finite Set

As defining continuous Radon transformations in Euclidean geometry, finite Radon transformations are defined in finite geometry set. The FDRT of a real function f defined on a finite set S is the real function on subset G (G Ì S), the values of which are obtained by summing f over the subset G. When set S is considered a special algebraic structure like image, subset G is the lattice points on a line, the FDRT of the image can be attained [9].

The FDRT of an image f [ i , j ] ( i , j Z p , Z p = { 1 , 2 , , p 1 } , p is a prime number) is defined as:

k [ l ] = FDRT( f [ k , l ] ) = 1 p ( i , j ) L k , l f [ i , j ] (1)

where, the factor 1 / p is introduced to normalize the l2-norm between the input and output of the FDRT, and ensure the energy matching between the original image and the reconstructed image. Lk,l denotes the point set that makes up a line on the lattice Z p 2 .

L k , l = {( i , j ): j = k i + l mod ( p ) , i Z p } , 0 k p 1 L p , l = {( l , j ): j Z p } k = p , l Z p (2)

where, due to existing of the module operation, the line Lk,l exhibits a wrap-around effect. In other words, the FDRT treats the input image as a periodic image.

The line Lk,l on the finite set Z p 2 is uniquely represented by its slope or direction k Z p * ( Z p 2 = { 0 , 1 , 2 , , p 1 , p } ) and its intercept l Z p , where k = p corresponds to infinite slope or close to vertical lines. There are total lines p × ( p + 1) defined in this way and every line contains p points. Two lines of different slopes intersect at exactly one point, and any two distinct points on Z p 2 belong to just one line. For any given slope, there are p parallel lines that provide a complete cover on the lattice Z p 2 . Traversing all image Z p 2 , we have:

l Z p , k Z p * k [ l ] = 1 p l Z p , k Z p * ( i , j ) Z p 2 f [ i , j ] = E p (3)

where the constant E is the total energy of the original image f.

An inverse converter f ˜ is the sum of the finite Radon coefficients of all lines passing through a given point, that is,

f ˜ [ i , j ] = IFDRT( k [ l ]) = 1 p ( k , l ) P i , j k [ l ] , ( i , j ) Z p 2 (4)

where Pi,j denotes the set of indices of all the lines that go through a point, as

P i , j = {( k , l ) : l = j k i mod( p ) , k Z p } {( p , i )} (5)

so as

f ˜ [ i , j ] = IFDRT( k [ l ]) = 1 p ( k , l ) P i , j ( i , j ) L k , l f [ i , j ] = 1 p ( p f [ i , j ] + l Z p , k Z p * ( i , j ) L k , l f [ i , j ] ) = f [ i , j ] + E / p (6)

The constant E is the total energy of image f [ i , j ] . Equation (6) shows that the result of reconstructing f ˜ [ i , j ] can be completely reconstructed except for adding a constant E / p to each pixel.

If the total energy E = 0, let the matrix ψ [ i , j ] studied is a zero-mean image, then Equation (6) shows that there is no redundancy or loss of information/energy in the FDRT and IFDRT of ψ [ i , j ] .

Let the discrete Radon transform of ψ [ i , j ] be expressed as FDRT(ψ) = . The elements of matrix H(p+1)×p is

h k , l = p 1 / 2 δ L k , l ( i , j ) ,

where δ L k , l ( i , j ) = { 1 , ( i , j ) L k , l 0 , o t h e r w i s e . If ψ [ i , j ] the zero-mean image as a set of column vectors, then the matrix H reduced to H = p 1 / 2 R , where R is the correlation matrix between the set H and its subset ( R L k , l ) ( i , j ) = { 1 , ( i , j ) L k , l 0 , o t h e r w i s e .

The FDRT of the zero-mean image ψ [ i , j ] satisfies the frame condition, and the frame { h k , l : k Z p * , l Z p } is a tight frame, the frame boundary A = B = 1. i.e. the dual frame { h ^ k , l : k Z p * , l Z p } is itself [10], which has:

ψ ˜ = l Z p k Z p * ψ ˜ , h k , l h k , l , f Z p * (7)

Therefore, the decomposition and reconstruction of the FDRT tight frame for zero mean images ψ [ i , j ] is a reversible operation. That is, the FDRT and IFDRT of the frame have the same algorithm structure. The decomposition and reconstruction of the FDRT tight frame will not cause the phenomenon of image distortion.

3. Watermark Embedding and Detection

Watermark embedding can be seen as a weak signal superimposed on the strong background of the original image. According to the masking characteristics of the vision system, only when the superimposed signal exceeds certain intensity can it be detected by the vision system. In the image domain, the strength of the watermark can’t cause changes in the objective quality of the original image (such as PSNR) and visual effects. The watermark can be better hidden in the original image, making it lossless information [11] [12] [13].

3.1. Watermark Embedding

In the FDRT domain, the energy of image is best compacted on the projections with different slops. That is to say, the projection matrix Q is composed of p + 1 projection vectors. The watermark which is unchangeable and decipherable consists of a real series W = { ω i , i = 1 , , N } , where each value ωi is chosen independently according to N ( 0 , 1 ) [14].

We select l = 0 on the k'-th ( k < p int ( N / p ) ) projection embedding the watermark W. By Zigzag scanning, we have the watermarked matrix Wmk is

W [ k , l ] = k [ l ] + α W m k [ l ] k Z p 2 (8)

where, α is strength factor of the watermark, so

W m k [ l ] = { W { k k int( N / p ) , l Z p } { k = int( N / p ) + 1 0 < l ( N p int( N / p ))} 0 o t h e r w i s e (9)

Considering the equality (6), the watermarked image f [ i , j ] is:

f [ i , j ] = IFDRT( W [ k , l ]) = f [ i , j ] + α p ( k , l ) P i , j W m k [ l ] = f [ i , j ] + α W [ i , j ] (10)

The first item is reconstructed image f [ i , j ] , and the second item is the inverse projection of the embedded watermark in FDRT domain. The pixels W [ i , j ] which satisfies the wrap around stack path Lk,l in Equation (4) are defined over the entire image domain, viz, the Equation (10) shows that the energy of the embedded watermark uniformity distributes on all pixels of the image.

If the strength factor α is chosen suitably, the watermark signal W [ i , j ] in space domain is very weak, so that the degradation of the watermark image is very small. The embedded watermark signal is invisibility, i.e. the visual quality of the watermarked image is not debased.

In the image domain, the watermark embedding process shown in Equation (10) actually introduces noise pollution. The PSNR of the watermarked image is

PSNR = 10 lg 255 p ( i , j ) Z p ( α W ( i , j )) 2 (11)

Due to the quadratic sum of watermark signal W [ i , j ] in image domain equal to the quadratic sum of the watermark series { α ω i , i = 1 , 2 , , N } embedded in FDRT domain, viz. ( i , j ) Z p ( α W ( i , j )) 2 = i = 1 N ( α ω i ) 2 . The watermark series elements ωi are independent random variables, let E ω = i = 1 N ( ω i ) 2 . We have

PSNR = 10 lg ( p ) 10 lg α 5 lg ( E ω ) (12)

The PSNR is only related to the strength parameter α, square sum Eω of watermark series. For a given watermark series W = { ω i , i = 1 , , N } , the smaller the strength parameter α of the watermark, the lower the visibility of the embedded watermark, the smaller the quality of the watermark image is better; otherwise, the quality of the watermark image is more reduced. This conforms to the masking characteristics of the visual system. Figure 1, the relationship among the PSNR, the strength parameter α, shows the relationship among the PSNR, the strength parameter α, Square sum Eω of watermark series, p = 257.

3.2. Watermark Detection

The watermark extraction is essentially the reverse of the insertion process. The FDRT of the original and watermarked image is first performed. The watermark

Figure 1. The relationship among the PSNR, the strength parameter α, Square sum Eω of watermark series, p = 257.

matrix C* is then obtained by subtracting the original image projections from the watermarked image projections. We have

C * = FRAT f [ k , l ] FRAT f [ k , l ] = { W m k [ l ] { k k int( N / p ) , l Z p } { k = int( N / p ) + 1,0 < l ( N p int( N / p ))} 0 k k , l Z p (13)

After extracting the sub-matrix W*mk from the matrix C*, the one-dimensional series W* is restored by Zigzag scanning.

The presence of the watermark is then evaluated based on the similarity between the extracted W* and original watermark W. The similarity detector is given by

K ( W * , W ) = i = 1 N ( W * ( i ) W ( i )) / i = 1 N ( W * ( i )) 2 (14)

A threshold T is selected previously. If K ( W * , W ) > T one can determine that the image f [ i , j ] has been inserted watermark W. The similarity measure depends on N, the length of the watermark series. Larger values of N tend to cause larger similarity values when W* and W are genuinely related, without causing larger similarity values when W* and W are independent. For the smaller number N, setting the threshold at bigger value will not cause spurious matching. We should select the T basing on the length of the original watermark series. For example, N = 1024, then T = 6.

3.3. Watermark Robustness

Using the FDRT, the energy or information of the watermarked signal which is uniformly incumbent on the image is congregated renewed on the correspondence projections in FDRT domain. Even if the watermarked image is exposed to attack, this energy or information can be yet collected on the exactitude projections, and can be detected by the similarity detector. The proposed watermarking algorithm has stronger robustness.

Since the watermark is Gaussian random series with zero-mean and is a full frequency domain signal, the FDRT and IFDRT do not change the frequency features of the watermark. The watermark signal is covered in the whole image space in full frequency band, this watermark embedding and extraction detection algorithm can resist the attack of various types of convolution filtering (low pass filter, band pass filter, high pass filter, notch filter, etc. in Table 1.

Table 1. The Various types of attack using checkmark system in [15].

Note: [a] The parameters (a, b), reducing the size to the original 1/a according to the nearest neighbor method, and then zooming in b times; [b] “Lana”, “Baboon”, the maximum variance method calculates the gray threshold value. “Head”, The image gray threshold is the average value of the image; [c] The lower bound frequency is 3/4 of the highest frequency; [d] The notch frequency band is the highest frequency 1/4 - 2/4.

For various types of shear, edge enhancement, contrast adjust, segmentation, geometrical attacks, FDRT can aggregate the remaining watermark information in the original embedded position of the watermark in the Radon domain, the existence of the watermark can still be detected. That is, the correlation between the watermark to be tested and the original watermark is still high (in Table 1). At the premise of ensuring the objective quality of the watermark image, the watermark series can be embedded in the original image by adjusting the embedding strength α in equality (10), the embedding algorithm has a large capacity.

4. Experimental Results

In order to estimate the watermarking scheme, we subjected the watermarked image to a series of image processing and collusion style attacks. In these experiments, the length of the Gaussian white noise series is N = 1024. The strength parameter is a = 0.1. The origin point is chosen at the first element of the projection with slope k = 30.

Experiment 1: The original image is 256 × 256 × 8 bit “Lena” images with High and low frequency information rich, as shown in Figure 2(a). The watermark image is shown in Figure 2(b), PSNR = 43.172 dB, the original image is less polluted by the watermark signal. Visually, the watermark image is basically consistent with the original image and achieves an invisible purpose. The statistical technique used for watermark detection, i.e. 1000 Gaussian random white noise series with different normal distributions are randomly generated, and the 500th series is embedded in the original image. The watermark extracted according to equality (14) is correlated with the 1000 random series, the 500th is an obvious response (Similarity = 31.689) in the corresponding position of the watermark series, as shown in Figure 2(c). This experiment exhibits that the algorithm has very high definition.

Experiment 2: Noise pollution and compression. The original images selected are 256 × 256 × 8 bit “Lena”, “Baboon”, “Brain” images. The “Baboon” has the complex texture areas. The medical image contains large dark or bright areas; the “Brain” is the human brain MR image.

Because of the diversity of noise sources, digital images are easily polluted. The watermarked image was polluted by Gaussian white noise. Figure 3(a)

(a) (b) (c)

Figure 2. (a) original image. (b) watermarked image (PSNR = 43.172 dB).

(a) (b)

Figure 3. (a) Robustness against noise pollution; (b) Robustness against JPEG.

shows the relationship between the correlation detection and the degree of pollution (PSNR) of the watermark image. As the PSNR is reduced to 26.61 dB, the visual quality of watermark image has become very poor. But the correlation degree of watermark detection is still more than the threshold T = 6.

Compression of is very important for image transmission and storage, the robustness of anti-compression is one of the important indexes of watermarking algorithm. Figure 3(b) shows the relationship between the correlation detector and the image quality (PSNR) after JPEG lossy compression. When the compression ratio increases, the visual quality of the image also decreases, and the correlation detector decreases. When the PSNR = 26.12 dB, the compression ratio is 10.4, and the correlation detector drops near the threshold value of 6, but the watermark can still be detected.

Experiment 3, the robustness of watermarking scheme must be tested and evaluated by various attack. This paper uses attack methods and strategies proposed in [15] to evaluate the robustness. The test images are “Lena”, “Baboon”, “Head”. The same watermark series is embedded in each standard test image in the same attack method (PSNR ≈ 43 dB). Various types of attack methods and parameters are shown in Table 1. The correlation degree is detected from the attacked watermark image. The watermark algorithms in this paper can be detected the presence of watermark under noise pollution, JPEG compression, wavelet lossy compression, MAP, filtering, segmentation, edge enhancement, contrast change, jitter, template removal, secondary modulation, and general geometric attacks (scaling, rotation, shear). But for random-geometric attacks such as stirmark-attack, algorithm in this paper can’t detect the existence of watermark.

5. Conclusion

A novel watermark algorithm based on the finite Radon transform tight frame has been presented. We derived the relationship among the PSNR, the strength parameter, quadratic sum of watermark series. According to the assigned image quality, the strength parameter α and Square sum of watermark series can be estimated. Experimental results reveal that the proposed watermarking algorithm yields watermarked images with superior imperceptibility and robustness to common attacks, such as removal/interference (filtering, MAP, JPEG, dithering, segmentation, noise pollution) and geometrical attacks (translation, cropping, rotation).

Cite this paper: Zhang, J. and Qi, H. (2020) A Robust Digital Watermarking Algorithm Based on Finite-Set Discrete Radon Transform Tight Frame. Journal of Computer and Communications, 8, 123-133. doi: 10.4236/jcc.2020.812012.
References

[1]   Jemila, R. (2018) A Survey on Recent Reversible Watermarking Techniques. International Journal on Recent and Innovation Trends in Computing and Communication, 6, 27-31. https://doi.org/10.17762/ijritcc.v6i10.5190

[2]   Yahya, A.N., Hamid, A.J., Ainuddin, W. and Rafidah, M.N. (2015) Robust Watermarking Algorithm for Digital Images Using Discrete Wavelet and Probabilistic Neural Network. Journal of King Saud University—Computer and Information Sciences, 27, 393-401. https://doi.org/10.1016/j.jksuci.2015.02.002

[3]   Lu, Z.-M. and Guo, S.-Z. (2017) Lossless Information Hiding in Images on Transform Domains. In: Lossless Information Hiding in Images, Zhejiang University Press, Hangzhou, 143-204. https://doi.org/10.1016/B978-0-12-812006-4.00003-6

[4]   Asifullah, K., Ayesha, S., Summuyya, M. and Sana, A.M. (2014) A Recent Survey of Reversible Watermarking Techniques. Information Sciences, 279, 251-272. https://doi.org/10.1016/j.ins.2014.03.118

[5]   Reem, A.A. and Lamiaa, A.E. (2019) Text-Image Watermarking Based on Integer Wavelet Transform (IWT) and Discrete Cosine Transform (DCT). Applied Computing and Informatics, 15, 191-202. https://doi.org/10.1016/j.aci.2018.06.003

[6]   Jun, Y.W., Wei, L.H., Wei, M., Xia, H., Wei, P.Z. and Li, H.G. (2020) Imperceptible Digital Watermarking Scheme Combining 4-Level Discrete Wavelet Transform with Singular Value Decomposition. Multimedia Tools and Applications, 79, 22727-22747. https://doi.org/10.1007/s11042-020-08987-3

[7]   Ingemar, J.C., Joe, K., Thomson, L. and Talal, S. (1997) Secure Spread Spectrum Watermarking for Multimedia. IEEE Transactions on Image Processing, 6, 1673-1687. https://doi.org/10.1109/83.650120

[8]   Matus, F. and Flusser, J. (1993) Image Representation via a Finite Radon Transform. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15, 996-1006. https://doi.org/10.1109/34.254058

[9]   Do, M.N. and Vetterli, M. (2003) The Finite Ridgelet Transform for Image Representation. IEEE Transactions on Image Processing, 12, 16-28. https://doi.org/10.1109/TIP.2002.806252

[10]   Mallat, S. (2009) Frames. In: A Wavelet Tour of Signal Processing, Academic Press, London, 155-204. https://doi.org/10.1016/B978-0-12-374370-1.00009-4

[11]   Martin, K. and Fabien, A.P.P. (1999) Fair Benchmark for Image Watermarking Systems. Proceedings of Electronic Imaging: The Security and Watermarking of Multimedia Contents, San Jose, 25-27 January 1999, Vol. 3657, 226-239. https://doi.org/10.1117/12.344672

[12]   Xiaoyan, Y., Chengyou, W. and Xiao, Z. (2019) A Hybrid Transforms-Based Robust Video Zero-Watermarking Algorithm for Resisting High Efficiency Video Coding Compression. IEEE Access, 7, 115708-115724. https://doi.org/10.1109/ACCESS.2019.2936134

[13]   Feng, B., Li, X.L., Jie, Y.M., Guo, C. and Fu, H.J. (2020) A Novel Semi-Fragile Digital Watermarking Scheme for Scrambled Image Authentication and Restoration. Mobile Networks and Applications, 25, 82-94. https://doi.org/10.1007/s11036-018-1186-9

[14]   Stankovic, S., Djurovic, I. and Pitas, L. (2001) Watermarking in the Space/Spatial- Frequency Domain Using Two-Dimensional Radon-Wigner Distribution. IEEE Trans Image Process, 10, 650-658. https://doi.org/10.1109/83.913599

[15]   Peter, M. and Shelby, P. (2002) Attacks, Applications, and Evaluation of Known Watermarking Algorithms with Checkmark. Proceedings of Electronic Imaging: Security and Watermarking of Multimedia Contents, San Jose, 21-24 January 2002, Vol. 4675, 293-304. https://doi.org/10.1117/12.465287

 
 
Top