LIU Xin，ZHAO Kang

(Institute of Graphics and Image，Hangzhou Dianzi University，Hangzhou Zhejiang 310018，China)

0 Introduction

With the rapid development of the communication technology and the computer network，digital media such as image，video，audio，get a wide range of applications．The digital information provides significant convenient for information sharing and using，but subsequent digital media information security，intellectual property protection and authentication problem has become increasingly prominent．The traditional encryption technology is unable to solve all problems effectively，the digital watermarking technology，which is considered as an effective complementmeans for traditional encryption method，has shown tremendous potential in these aspects and has become an effective way of protecting copyright，demonstrating source and integrity in the open network environment［1］．The so－called image authentication refers to the detection of modification to image data．Semi-fragile watermarking is used for selective authentication，it can bear a certain degree of some conventional signal processing，but should be sensitive to malicious tampering［2］．In recent years，wavelet transform，for its good time－frequency and multi－resolution analysis characteristics，is widely used in digital image processing and has become one of the main directions of the signal research．Digital watermarking algorithms based on wavelet transform decide to embed watermarking whether or not mainly in accordance with the amplitude of wavelet coefficients in frequency domain．That is，to set a threshold value，if the frequency coefficient is larger than it，then embed watermarking，otherwise，no change to the coefficient．This kind of algorithm is stronger in robust，but transparency is not very good［3］．The algorithm in the paper will use parity of wavelet coefficients to embed watermarking．

1 Principle of lifting wavelet transform s

Lifting Wavelet Transform(LWT)was proposed by Sweldens in 1995．The traditional wavelet transform is realized through convolution with complex computation，slow speed and large demand for memory．The coefficients generated by traditional wavelet transform are floating point number，you can＇t accurately reconstruct the original signal due to the limited computer word length．While LWT analysis problems in space domain directly，and make them more simple．Moreover，lifting has no limitation to the length of input sequence．Wavelet transform using lifting keep the advantages of the traditional wavelet，as well as overcome its limitations．So these characteristics can be applied to digital watermarking technique［4］．

There are three typical steps in lifting process named Split，Predict and Update［5］．(1)Split is to divide original signal into two subsets without intersection in theory，while in practical application，original signal is usually split into even sample and odd sample;(2)Predict refers to using predictor to forecast odd sample according to even sample，its error is called wavelet coefficients;(3)Update refers to applying update operator to wavelet coefficients，and then add odd sample to obtain corresponding scale coefficients，so that we can get an approximation to original signal in the low resolution．

2 Watermarking Algorithm

2．1 Watermarking embedding algorithm

(1)Apply the 2 level LWT decomposition to the original image．

(2)Suppose the size of the low frequency sub－bands LL2is M×N，then set K=(M×N)/4，using secret key k1to generate a one－dimension binary random sequence A with length K．

(3)Apply 2 ×2 block to LL2，and calculate the sum of wavelet coefficients in each block，named Sum(i)，i=1，2，3，…，K．

(4)For each block of LL2，using the following formula to generate S(i):

Here，letParity(Sum(i))represent that which first convert Sum(i)to its two’s complement format，and then returns 1 or 0 as output to indicate that the number of‘l’bits is odd or even［6］．

(5)For each block of LL2，using the following formula to generate a bit of watermark W(i):

Here，i=1，2，3，…，K，and⊕ stands for Exclusive－OR operation．

(6)Generate four binary random sequences R1，R2of length K/2 with secret keys k2，k3separately，sort R1and R2with stable sorting algorithm，obtain the sorted sequence and index sequences L1and L2，here L1=(a1，a2，a3，…，aK/2)，L2=(b1，b2，b3，…，bK/2)．Then embed the front K/2 watermarks ofwatermarking sequence to the coefficients of HL2sub－band［7］，the embedding position is:f1(j)=aj，j=1，2，3，…，K/2．And the remaining K/2 watermarks are embedded to coefficients of LH2sub band［7］，the embedding position is:f2(j)=bj，j=1，2，3，…，K/2．

(7)For each watermark，we first use fi(i=1，2)to find the coefficients in corresponding sub－band in which the watermark to be embedded，then modulate the selected coefficient，so that:

where the meanings of Parity are described in step(4)，and X is the selected coefficient．

(8)Applying ILWT on the coefficient matrix to get the watermarked image．

2．2 Authentication algorithm steps

(1)Apply the 2 level LWT decomposition to the original image．

(2)Generate binary random sequence A with secret key k1as described in Step(2)of the watermarking embedding algorithm．Then generate the watermark sequence Was described in Step(3)，(4)，(5)of thewa-termarking embedding algorithm．Generate position sequences fi(i=1，2)with secret keys k2，k3separately as done in Step(6)of the watermarking embedding algorithm．

(3)As for the front K/2 watermark of watermarking sequence，find the coefficient in HL2that has been embedded watermark according to position sequence，then verify whether formula(3)holds．If formula(3)does not hold，the block which generates the watermark is shaded to indicate the occurrence of tampering．

(4)As for the remaining watermark，do the same thing as step(3)．

3 Experimental results and algorithm com parison

In this paper，we use 512×512 standard Lena image as the original image，as is shown in Figure 1．The experiment choose Le Gall5/3 filter to apply LWT and ILWT to Lena．Embedding watermarking to the original image according to the algorithm in this paper，the watermarked image is shown in Figure 2 and its Peak Signal－to－Noise Ratio(PSNR)is 52．791 3．The PSNR and visual effect express that this algorithm performs well on imperceptibility and invisibility．

Using collage to attack the watermarked image，the image after attacking is shown in Figure 3．The authentication result for collage attack is shown in Figure 4．

Figure 1 Original image

Figure 2 Watermarked image

Figure 3 Collage attack

Using shifting to attack the watermarked image，the image after attacking is shown in Figure 5．The authentication result for shifting attack is shown in Figure 6．

Figure 4 Authenticationfor collage

Figure 5 Shifting attack

Figure 6 Authentication for shifting

Figure 3－6 show that the algorithm has resistance to both malicious collage attack and shifting attack．If the watermarked image suffers from collage attack and shifting attack，the algorithm proposed in the paper can accurately locate the illegal position．

In order to test the performance of this algorithm，in spite of PSNR，correlation sim is used to evaluate the performance．Suppose the watermark generated by the receiving image isW(i)，while the watermark extracted from the receiving image isW'(i)，so the formulas for correlation is:

sim can be used for testing the correlation for extracted watermark and embedded watermark，the higher sim is，the better the performance of the algorithm．In order to test the robustness of this algorithm，several at-tacks are used and comparison with paper 3 is conducted too．The results are shown in Table 1．

Table 1 Robustness attack test results and algorithm comparison

From the data in Table 1，we can see that the proposed algorithm has stronger robustness than paper 3 in low pass filtering，add noise，compression and etc．a(chǎn)ttack．

4 Conclusions

In this paper，we propose a blind watermarking algorithm based on lifting wavelet transform，using the low frequency coefficients to generate watermarks．Then the watermarks are encrypted by a random sequence with secret key to improve its security．Using coefficient’s parity to embed watermarks into the high frequency wavelet coefficients，not only to ensure the invisible of the watermarks，but also to improve the robustness of the algorithm．The experimental results show that the proposed semi－fragile watermarking algorithm is able to resist some of conventional signal processing，while is sensitive to malicious tampering．The algorithm can also realize accurate malicious tamper localization．At the same time，this algorithm is realized without the source file，so it is a kind of blind watermarking algorithm．

［1］ LIShu yun，ZHU Gui bin，YANGWan．An Image Watermarking Algorithm Based on Lifting Wavelet Transform［J］．Communications Technology，2007，40(12):277 －278．

［2］ YI Liu，YIZhao shi，CHEN Guang xi．Design and Implementation of Semi-Fragile Watermark for Image Authentication［J］．Computer Systems＆ Applications，2009，(4):144－145．

［3］ JIA Zhu zhi，ZHU Hong yu ，HOUWei gang，et al．A blind watermarking algorithm based on lifting wavelet transform［J］．Information Technology，2009，(12):21 －23．

［4］ GAOShiwei，GUO Lei，YANG Ning，et al．Lifting Wavelet Transform and Its Application in Digital Water marking［J］．Application Research of Computers，2007，24(6):201 －202．

［5］ CHEN Dong fang，ZHANG You qing．Blind watermarking algorithm based on lifting scheme wavelet and chaoticmapping［J］．Computer Engineering and Design，2008 ，29(20):5 372－5 373．

［6］ YU Miao，HEHong Jie，ZHANG Jia Shu．A digital authentication watermarking scheme for JPEG images with superior localization and security［J］．Science in China Series F:Information Sciences，2007，50(3):496 －497．

［7］ LIChun yang．Research on Semi-fragile Watermarking Technology Based on JPEG2000［D］．Chang chun:jilin university，2009．