Two Properties of SVD and Its Application in Data Hiding[共11頁]

1、Two Properties of SVD and Its Application in DataHidingYun-xia Li and Hong-bin ZhangCollege of Computer Science, Beijing Universily of Technology, Beijing, Chinayunxiall6gmail com, Abstract. In this paper, two new properties of singular value decomposition (SVD) on images are prove

2、d The first property demonstrates (he quaniiiaiive relationship between singular values and power specirum. The second one proves that under the condition of losing equal power spectrum, the squaie- error of the reconstructed image is much smaller when we reduce all singular values proportionally in

3、stead of neglect the smaller ones Based on the two properties, a new data-hiding scheme is proposed It performs well as for robustness, for it satisfies power-spectrum condition (PSC)、and PSC-compliant watermarks are proven to be most robust. Besides, the proposed scheme has a good performance as fo

4、r capacity and adaptability.Keywords: information hiding, SVD, MR-SVD1 IntroductionSingular value decomposition (SVD) was introduced by Eckart and Young 11 and has become one of the most widely used techniques. In computational algebra, SVD is an efficient way of Matrix Analysis 2, and it has been u

5、sed to solve linear least squares problems, inverse problems of matrix, and calculate matrixes range, null space and rank, etc. SVD is also one of the most basic and important tools in pattern recognition 3, practical data visualization 4, multidimensional scaling and cluster analysis 5、and so on.In

6、 image processing, singular values specify the luminance of the SVD image layer, which have very good stability. That is, adding slight perturbation to an image does not change its singular values significantly, and slight variations of singular values cannot affect image quality significantly. As a

7、 con sequence, SVD has become widely used in data hiding 6-15.In this paper, on the bases of two new properties of SVD on images proved in this paper, a new data hiding scheme is proposed. It has following virtues:First, the scheme performs well as for robustness. For it satisfies power-spectrum con

8、dition 16, which states that the watermarks power spectrum should be directly proportional to the original signafs, PSC-compliant watermarks are proven to be most robust.Sec ond, the scheme has high capacit y. In formation embedded in the scheme can be as large as the cover, and robustness is kept a

9、t the same time.D.S Huang, L. Heutte, and M. Loog (Eds.): ICIC 2007, LNCS 4681, pp. 679-689, 2007. Springcr-Vcrlag Berlin Heidelberg 2007#Y.-x. Li and H.-b. ZhangThird, the scheme has good adaptability. For the proposed algorithm just depends on covers singular values, covers of the scheme are not l

10、imited to gray images, signals that can be expressed by matrix, like document, video, etc. are also feasible as covers of the schemeAt last, employing multi-resolution singular value decomposition (MR-SVD) get approximated components of the information embedded, then mapping it into singular values

11、of the cover image. At information extracted end, the approximated components are reconstructed to verify weather the data extracted is exactly the data embedded, so the problem of some SVD-based algorithms pointed out in 17 can be avoided And the problem is, for the detection stage makes use of inf

12、ormation that is dependent on the information embedded, as a result, any reference information can appears at detection stage as information embeddedThe rest of the paper is organized as follows. In Section 2, two properties of SVD on images are proved In Section 3, the new data-hiding scheme is pro

13、posed. Experimental results are given in Section 4. Finally, the whole paper is concluded in Section 5.2 SVD on Image and Proof of Its Two New PropertiesIn this section, we first introduce SVD and multi-resolution form of the SVD (MR- SVD). Then, we proved two new properties about SVD on images, whi

14、ch are essential to improve performance of the algorithm we proposed21 SVD and MR-SVDLet 才be an arbitrary matrix of size nixn. SVD of can be represented as follows:R-X = USV =工i=0Where U and V are unitary mxm and nxn matrices, Columns of Uggum.)and vb ,matrices are called left and right singular vec

15、tors respectively. S is a diagonal matrix with R (R is the rank of matrix X non-negative elements: called singular values of matrix X.Similar to wavelet decomposition, SVD also exist its multi-resolution form, which is proposed by Kakarala and Ogunbona 18. If we perform MR-SVD on the above matrix X9

16、 the procedure can be described as following:First, we decompose X into pxq blocks, where p. q may be chosen arbitrarily. Here, we divide 才 into 2x2 non-overlapping blocks for convenience Then we arrange each block into a 4x1 vector, and stack these columns to form the data matrix X .x(lj)X2J)Xh2)x(

17、3,l)兀(加一 1,一 1)、 x(4J)-1) x(3,2)x(m -1, n)x(4,2) x(m, n)Second, X is centered by removing the mean in each row from elements of that row, which results in X .Two Properties of SVD and Its Application in Data Hiding681Third, eigen-decomposition of the 4x4 matrix T = XX1 = USV is computed. Let X = X ,

18、 the top row of X is rearranged to form a matrix Y (tn/2xn/2) that corresponds to the largest eigenvalue and is considered as the smooth (approximated) components of the image, the remaining rows are rearranged to form matrices containing the detail components, corresponding to edges in an image At

19、the next level, Y replaces X and the transform proceeds as mentioned above.As an example, the result of two levels MR-SVD on image Lena (256x256) is described in Fig. 1.(a)(b)1Fig. L (a) Original image (b) Two levels MR-SVD of the image2.2 The Two New Proved Properties of SVD on ImageProperty 1: Giv

20、en an image 人 performing SVD on it, denoting its singular values and power spectrum as 6(i=0, 1,n-) and E respectively, thenProof: For an image I. its discrete Fourier transform F can be expressed as: F=PIPy where the element of matrix P satisfies:u.v = 0,1,2,丿 一 1 _ 2 j 兀u/ p(Uyv)= e /n and P can b

21、e proved to be a unitary matrix.Discrete Fourier transform on I also can be defined as:F(u, v)=血 Z1 E 2 必-2/(% + 吆).x=0 v=0And its total power spectrum E is defined as:2 2 2 2Eg v) = R 厶(m) + / (w.v) =1 FS v)E =11 F II：where R(x, y) and I(x, y) are real part and imaginary part of F(u, v) respectivel

22、y. In algebra, given A g C mx, Frobenius norm of A is defined as:Two Properties of SVD and Its Application in Data Hiding691For a unitary matrix U of rank m and unitary matrix V of rank n9 Frobenius norm of a matrix has the following properties: II A llF =11 UAV llF .Since the transposition of a uni

23、tary matrix is still a unitary matrix, so we get:E =11 F II； =11 PIP II： =11111=11 USV1 |；=(弓f .Property 2: Given an image I. its power spectrum can be decreased either by reducing all singular values proportionally or neglecting parts of smaller singular values The former square error between the o

24、riginal image and the reconstructed image is smaller than that of the latter oneProof: The SVD on image I is:l =(1)/=0If we neglect parts of its smaller singular values, just reserve the first K (0KN) larger values, and replace the other singular values by zero, then we have the reconstructed image

25、I and square error 11|11 between I and I as follows:k_tHI=n rZ1 = E 6 U：V： =/-/= (7： UjV： , II Ey 11= z If we reduce all singular values proportionally by scale factor a (0 1), under the condition that image I loses equivalent power spectrum as above, according to property 1, the following equation

26、should be satisfied:n- c .oZ (1一力)0=(2)i=0i=kSimilarly, we get the reconstructed image A and the square error IIE2II：I2 = i (aq )爐:,II E, 11= (J： _2土 (o-夕Q：.Z=1i=k+/=1for 0a , 夕IE2H-Under extreme condition, a=. then E= E, there is no change to image /Besides, the reconstructed image keep phase spect

27、rum of image I without any change, which can be easily proved Here the prove is omittedProperty 2 just show the superiority of reducing all singular values proporti on ally, when image lose equal power spectrum, comparing to neglecting parts of smaller singular values Next, we illustrate it by exper

28、iment results in Fig. 2 Where (a) is the original image Lena (256x256,256 gray-level), under condition (2), (d) and (g) respectively are the images reconstructed by neglecting parts of smaller singular values of (a) and by reducing all singular values proportionally of (a), (b) and (c), (e) and (f),

29、 (h) and (i) are amplitude spectrum and phase spectrum of (a), (d), and (g) respectively. From these results we can see that, under condition (2), first, visual quality of the original image is seriously damaged after neglecting parts of smaller singular values; but reducing all singular values prop

30、ortionally keep good visual quality of the original image Results show in Fig. 2 (d) and Fig. 2 (g) respectively.Second, after neglecting parts of smaller singular values, spectrum information of the original image, especially phase spectrum is changed; but, reducing all singular values proportional

31、ly keep the phase spectrum information of the original image without any changes The corresponding experiment result presents in fig. 2 (f) and fig. 2 (i) respectively. From the work 19 of Oppenheim and Lim, we know that the phase spectrum is vital to visual systems, which contain important shape an

32、d structure information of image, and should not be changed Recent paper 20, from a statistical perspective, also gives an interpretation of the importance of phase information in signal/image reconstructions So, comparing to neglecting parts of smaller singular values, proportionally reducing all s

33、ingular values is a more reasonable way.(a)(d)(0(i)Fig. 2. Comparis on between the images modified by reduci ng all singular values proporti on ally and by ncglccting parts of smaller singular valuesBesides, there is another misunderstanding about the largest singular value of an image, which is oft

34、en thought containing the most important lower frequency in formation of image and should keep without any cha ng es. However, the fact may not be the same Experiment results shown in Fig 3, (a) is the original image Lena (256x256, 256 gray-level), (b) is the image reconstructed by reducing all sing

35、ular values proportionally by a scale factor 0.1, (c) is also the image reconstructed by reducing all singular values proportionally by a scale factor 0.1 except for the largestsingular value If knowledge mentioned above about the largest singular value is correct, clearly, (c) should have better qu

36、ality, for the largest singular value without any changes and smaller distortion. However, experiment results show visual quality of image (b) is much better than that of image (c), so, although the largest singular value of an image is important, proper change is feasible.(a)(b)(c)Fig. 3. Compariso

37、n under lhe condition that whether if the largest singular value is changed or notIn a word, the two properties and experiment results express that proportionally reducing all singular values is a more reasonable way than neglecting parts of smaller singular values The most important is, power spect

38、rum of the original image keeps proportional to the reconstructed image after reducing all singular values proportionally. The algorithm proposed next which could satisfy power-spectrum condition is just based on this point.3 Data Hiding AlgorithmThe algorithm we proposed is one of data hiding schem

39、es in transform domain based on SVD. The details as follows:Procedure of embedding informationStep 1: Performing SVD on cover image (MxN): A=USV , reducing singular values of A | by scale factor a (0a28, the deterioration of images visual quality is unnoticeable. In the following experiment we set a

40、=l/!6, PSNR =28.5In fact, if we give quality requirement, that is we set a value of PSNR, the following equation can calculate the corresponding a we should takePSNR = -20xlg(l-a) + 10xlgaw S 工 M(x,y)rx=0y=0Step 2: Let W (MxN) be the embedding image Encrypting W with secret key K、 denoting results a

41、s then performing SVD on A2+Wi=UwSy Let Wi (MxN) be the embedding image. Performing SVD on A2+Wi=UwSwVv-Step 3: Least square method is used to construct function F fitting pair data like (S2 譏,S沁,M)Step 4: According to keep Sw i. i without change, calculating S2 /, / and denoting the result as S2 /,

42、 i. Then, image A2 =U SV1 will be transmitted as the cover with information embedded.Step 5: First, MR-SVD is performed on to get its approximated image W2*(M/8xN/8). Second, A2 is divided into 8x8 blocks, then, performing SVD on the blocks, and the largest singular values of every block is written

43、in corresponding position of matrix 必勺 Obviously, element numbers of matrix W2 and VV3 are equal. At last, employing least square method, mapping F2 is constructed to fit points likeTo help understand the algorithm, embedding procedure is described as following:encryptingS2=aSVMR-SVD onZ2+ W=LvSwVwT

44、l2=UxS2Vi(S2 卩 4Sw“J)V(W品幾W3 i- 刀)2 JSVD on blocks057Output Fh Fr g Vw J3Fig. 4. Embedding procedure of the algorithm proposed in this paperProcedure of extracting information:Given Uw. Vw K、and the received image 1which is possiblydistorted due to various noises.First, we use S3, F to reconstruct S

45、w as Sw , employing 心 the information embedded can be extracted by M 二UwSwW- /3*.Second, similar to step 5 in embedding procedure, MR-SVD is performed on VV| to get its approximated image W2 Then, dividing /3 into 8x8 blocks, performing SVD on the blocks to get matrix with the largest singular value

46、s of every block,*窗employing to reconstruct approximated image W2 of the embedded image. According to the correlation between IV2 and W2 , we verify the extracted image VVi whether is exactly the image embedded4 Experiment ResultsIn this part, to dem on strate n ecessity of reducing all singular val

47、ues proportionally in embedding procedure with proper scale factor a, experiment results with a in different value are compared. And to test robustness of the scheme, the image with information embedded was attacked by additive Gaussian noise, JPEG compression, low-pass filtering, Rotation and Cropp

48、ing.First of all, experiment results about reducing all singular values proportionally in scale factor a present in Fig. 5, Fig. 6, and Fig. 7, when a=l, a=1/16, and a=l/64 respective!y. Where Fig. 5(a), Fig. 6(a), and Fig. 7(a) are the cover image Lena (256x256, 256 gray-level), Fig. 5(g), Fig. 6(g

49、), and Fig. 7(g) are the embedding image Camera (256x256, 256 gray-level), Fig. 5 (b)-(f), Fig.6 (b)-(f), and Fig. 7 (b)- (f) are the covers with image embedded after the following distortion: adding Gaussian noise (the mean is zero, variance is 0.001), JPEG compression (compression ratio is 20), lo

50、w-pass filter (Gaussian low-pass filter with critical frequency by radius 30), rotation (anti-clockwise rotation by an angle 45 ), and image cropping, when a=l, gc=1/I6, and a二 1/64 respectively. Fig. 5(h) - (1), Fig. 6(h) - (I); and Fig. 7(h) - (1) are the extracted images under every condition. Fr

51、om experiment results we can see that: for the images extracted, especially when the covers suffer distortion like rotatio n and croppi ng, contain a great quantity of structure in formation of the cover, which damage the visual quality of the extracted images seriously. For a=1/16, after the cover

52、suffer the same distortions mentioned above, the extracted images and the covers keep high quality simultaneously. For a= 1/64, after the cover image suffer the same distortions, the extracted image also keep high quality. But now visual qualities of the covers with information embedded are damaged

53、seriously.Comparing results in Fig. 5, Fig. 6 and Fig. 7. we conclude the following points about a. In the algorithm, reducing singular values by a proper scale factor a is importanl to the algorithm performance. And the advantages can be summarized in following several aspects: First, after reducin

54、g sing ular values proporti on ally, Uw, Vw contain more detailed geometry structure information of (he embedded information. Second, at extracting stage, affects of covers distortion diminish. Finally, the robustness of the algorithm is improvedPaper 16 states that PSC-compliawatermarks are the mos

55、t robust. From the above properties we illustrated, we conclude that our scheme satisfy power spectrum(d)_(e) (D(g)raI1LaJ(h)(i)(b)(c)(J)(k)(g)(h)(J)(k)Fig. 5. Algorithm performance test(a)a=lFig. 6. Algorithm performanee lest when(b)(d)1/16(e)(0X17 1z(JZFig. 7. Algorithm performance test when a= 1/

56、64condilion. So, the proposed scheme is robust according (o (his point. The following experiment will show how it performs in robustness and capacity.For a=l/16, experiment results of robustness test are shown in Fig. 8, where (a) is the cover image Lena (256x256, 256 gray-level), (gj, (g2) and (g3)

57、 are the embedded image Camera, Baboon, Couple respectively, which are 256 gray-level of 256x256. Fig. 8 (b) - (f) are the covers with image embedded after the following distortion: adding Gaussian noise (the mean is zero, varianee is 0.001), JPEG compression (compression ratio is 1:20), low-pass filter (Gaussian low-pass filter with critical frequency by radius 30), and rotation (anti-clockwise rota