Chi-Shiang Chan,Yuan-Yu Tsai,and Chao-Liang Liu

1.Introduction

The most important property of digital media is that it is easily tampered with.Consequently,media security and copyright protection mechanisms have developed quickly,and many image authentication schemes have been developed.Among these various image authentication schemes,some have been proposed to embed recovered data into the digital images[1]–[4]so that the tampered areas can be detected and recovered.It is trivial that the fineness of the recovered areas is related to the recover unit of the different methods.However,the recovery unit of Yang and Shen’s method[4]is just a block with 4×4 pixels,and that of Lee and Lin’s method[2]is just a block with 2×2 pixels.

In order to improve the fineness of the recovered areas,Chan and Chang’s method[1]produced parity check bits from each pixel through a hamming code technique[5].The recovery unit of Chan and Chang’s method becomes one pixel.Although Chan and Chang’s method can reduce the recovery unit to one pixel,there are some drawbacks in their method.Chan and Chang’s method must predict the most-significant bit of each tampered pixel first.The tampered pixel then can be recovered by referring to the predicted bit and the extracted parity check bits.However,once an incorrect prediction is made in the recovery procedure,the tampered pixel can not be recovered successfully.Furthermore,a pixel with an incorrect prediction may affect the prediction accuracy of the following pixels.On the contrary,in Chan’s method[6],the parity check bits are produced from pixels whose bits have been rearranged.The value of the most-significant bit of each tampered pixel can be determined according to its parity check bits.Therefore,the recovery procedure of the proposed method does not need to predict the most-significant bit of the pixel.Although the value of the most-significant bit can be known through the parity check bits,the method still has to predict pixels by selecting one from two candidates of(7,4)Hamming code words.However,if the distance between two Hamming code words is within a certain range,there is still the possibility of making incorrect predictions.In the new version of Chan’s method in [6],one additional bit was added to record the correct one from two candidates.

In this paper,we group four most-significant bits into different groups to form a mapping codebook.The mapping codebook has an important property in that the distance between two candidates in each group is always out of the mentioned range.The proposed method will produce authentication data through a mapping codebook instead of a(7,4)hamming codebook.The experimental results show that the proposed method has better ability to recover the tampered areas with good quality.

The rest of this paper is organized as follows.Chan’s method is reviewed in Section 2.The method proposed in this paper will then be presented in Section 3.In Section 4,the experimental results are offered to demonstrate the effectiveness of the proposed method.Finally,the conclusions will be made in Section 5.

2.Related Work

In this section,Chan’s method[6]is reviewed.Chan’s method contains three procedures:the embedding procedure,the detection procedure,and the recovery procedure.The embedding procedure produces parity check bits from the rearranged bits of the pixel,and the parity check bits are embedded into another pixel by using a modulus function[7].In the detection procedure,the extracted parity check bits are used to check whether the pixel has been tampered with.According to the indication of the tampered pixels,the tampered areas are also located in this procedure.The final procedure,the recovery procedure,recovers the tampered areas.The details of Chan’s method are described as follows.

2.1 Embedding Procedure

The embedding procedure contains three steps:Hamming code production,bit rotation,and Torus automorphism[8].In the first step,Hamming code production,parity check bits are produced from the rearranged four most-significant bits of each pixel.The relation between rearranged bits and parity check bits is shown in Fig.1.The values of the parity check bits(P1,P2,P3)can be decided by achieving the goal that the number of“1” in each circle should be even.According to the example in Fig.1,the values of the parity check bits P1,P2,and P3are 1,0,and 0,respectively.

It should be noticed that the parity check bits are generated from the reversed four most-significant bits.The reason why we reverse the bits is that by referring to Fig.2,the most significant bits of two original data bits are the same if the values of their parity check bits are the same.That means whether the value of the original data bits is larger than 128 or not can be decided according the value of the parity check bits.

In the second step the produced parity check bits are rotated.The purpose of bit rotation is to rotate the order of the parity check bits to increase security.This step first selects one secret key k1as a seed to generate a sequence of random numbers,R1,R2,…,RN×N,where N is the pixel number of the height and width of the cover image.For the ith pixel,its three parity check bits must be rotated according to the random number Rias follows.

Fig.1.Way to generate the parity check bits from the reversed data bits[6].

where J represents the original order of the parity check bits,and J′ denotes the new order of the parity check bits.The variables J and J′ are both in the range from 0 to 2.After going through(1),the bit at the Jth position will be rotated to the J′ th position

In the third step,the rotated parity check bits are embedded into the three least-significant bits of another pixel indicated by the Torus automorphism.The formula of the Torus automorphism is shown as follows.

where the variable k2represents the second key.The symbol(xi,yi)denotes the position at where the ith pixel Piis located.On the other hand,the position(xi′,yi′)represents the new position in which the parity check bits of Piare going to be embedded and the symbol N is the pixel number of the height and the width of the cover image.

Once the embedded position for each Piis known,the parity check bits can be embedded by using a modulus function[7].Finally,the authenticated image can be obtained.

2.2 Detection and Recovery Procedures

The purpose of the detection procedure is to locate the tampered areas so that the recovery procedure has target areas to recover.In the detection procedure,the parity check bits for the pixel Piat(xi,yi)can be extracted from the pixel at(xi′,yi′)according to(2).Meantime,the parity check bits of the pixel Pican be produced through the four most-significant bits of the pixel Pi.Once the extracted parity check bits are not the same as the produced bits,both positions(xi,yi)and(xi′,yi′)are marked as the tampered pixels.After checking all pixels,morphological operations[9]are performed to eliminate the isolated faulty judgments.Finally,the tampered areas can be located through the detection procedure.

Fig.2.Original data bits and the parity check bits[6].

In the recovery procedure,if the parity check bits of the tampered pixel are not modified,these bits can be used to predict the value of the tampered pixel.According to the value of the parity check bits,the value of the mostsignificant bit,d4,can be known by referring to Fig.2.Moreover,the two candidates of the four most-significant bits can also be known according to Fig.2.The value of the most-significant bit of the pixel can help us to select the correct one from two candidates so as to recover the tampered pixel.

More precisely,in the detection procedure,the tampered area has been located.Chan’s method uses an indicated matrix M to indicate the number of the surrounding untampered pixels for each tampered pixels.It is obvious that the tampered pixels with a larger number at the corresponding positions of indicated matrix M have a better opportunity to select a correct one from two candidates because they have more untampered pixels for references.Therefore,only the pixels with the largest number of untampered pixels will be processed in each round.Because the most-significant bit of the predicted pixel can be known by referring to the parity check bits,the untampered pixels whose most-significant bit is the same as the predicted pixel are gathered to calculate their average value.The candidate that has the minimal distance with the average value is selected to recover this tampered pixel.After that,the recovered pixels are marked as untampered pixels,and the same procedures are performed to recover tampered pixels until all tampered pixels are marked as untampered pixels.The recovery procedure is shown in Fig.3.

3.Proposed Method

Fig.3.Recovery procedure[6].

In Chan’s method[6],although the value of the most-significant bit can be known through the parity check bits,the method still has to predict pixels by selecting one from two candidates.Most pixels can be predicted correctly by using the method described in Section 2.However,there is still the possibility of making incorrect predictions while two candidates are too close.In fact,if the distance between two candidates is small enough,selecting any one of two candidates to recover the pixel is acceptable.The quality of the recovered pixel is still good.However,by referring to the last column in Fig.2,it can be seen that the distance between two candidates becomes larger when the values of the parity check bits are 2,5,1 and 6.Their distances are 3 and 5.In the new version of Chan’s method in [6],one additional bit is added to record the correct one from two candidates whose parity check bits are 2,5,1,and 6.It is trivial that this may degrade the quality of the authenticated image.

In order to improve the quality,we propose grouping four most-significant bits into different groups to form a mapping codebook.There are two characteristics of the mapping codebooks.First,only the candidates with the same value of the most significant bit can be gathered in the same group.Second,all distances between two candidates are out of the range from 3 to 5.Recall that Chan’s method added one additional bit for the cases whose distances are in the range from 3 to 5.In our proposed method,however,there is no group with a distance in the range from 3 to 5 in Fig.4.

In the embedding procedure,the proposed method is almost the same as Chan’s method except for the Hamming code production step.Chan’s method obtained authentication data from four most-significant bits by producing parity check bits.On the contrary,our proposed method obtains authentication data from four mostsignificant bits through the Mapping Codebook.The mapping value can be decided by referring to the four most-significant bits and the Mapping Codebook.The role of the mapping value is treated as the parity bits in Chan’s method.This means that the mapping value will go through the steps of bit rotation and the rotated bits are embedded to the three least-significant bits of another pixel indicated by Torus automorphism.

Fig.4.Mapping Codebook.

4.Experimental Results

In this section,the experimental results are demonstrated.To begin with,the test image,Lena,with 512×512 pixels,is shown in Fig.5.

We first show the authenticated images and their PSNR values in Fig.6.Because both Chan’s method and the proposed method use a modulus function to embed data instead of least significant bit(LSB)replacement,the peak signal-to-noise ratio(PSNR)values of Chan’s method and the proposed method are higher than that of Chan and Chang’s method.

Next,we show the recovery ability for different methods in different areas.There are three areas,including a non-detailed area,a detailed area and a complex area(which includes a non-detailed area and a detailed area),used in our experimental procedures.These areas are shown in Figs.7(a),(b)and(c).The tampered areas are shown in Figs.7(d),(e),and(f).The size of the tampered area is 64×64 pixels.

Fig.5.Test image.

Fig.6.Authenticated images:(a)Chan and Chang’s method(PSNR:38.57),(b)Chan’s method(PSNR:40.02),and(c)proposed method(PSNR:40.07).

Fig,7.Experimental areas:(a)to(c):original areas,and(d)to(f):tampered areas.

Fig.8.Results of the recovered areas:(a)to(c):Chan and Chang’s method,(d)to(f):Chan’s method,and(g)to(i):proposed method.

In Fig.8 we demonstrate the experimental results of the related methods and our proposed method.Although the recovered areas of Chan and Chang’s method shown in Fig.8(a)and(b)have good results,the pixels in the recovered area in Fig.8(c)are different to the original area.On the other hand,Chan’s method[6]and the proposed method can recover the tampered areas successfully.Comparing the experimental results of the proposed method with those of Chan’s method,we can see that the recovered areas,by using our proposed method,have better image quality.

Because the distance of two candidates for some Hamming code words is in the mentioned range,it is hard for Chan’s method to judge which one is correct.Therefore,the recovered area in Fig.8(e)is not very good.On the contrary,because the distance of the two candidates of each group is out of the mentioned range,the recovered area in Fig.8(h)is better than that in Fig.8(e).It is trivial that the recovered areas of the proposed method are better than those of Chan’s method.

5.Conclusions

In this paper,we group four most-significant bits into different groups to form a mapping codebook.The mapping codebook is used to replace the role of(7,4)Hamming code book in Chan’s method.The mapping codebook has two important properties.First,only the candidates with the same value of the most significant bit can be gathered in the same group.This means the value of the most-significant bit of the predicted pixel can be determined according to its mapping values.Second,the distance between two candidates of each group is out of the range from 3 to 5.This means one additional bit for some pixels is not necessary in our method.According to the experimental results,the proposed method has a better ability to recover the tampered areas with good quality.

[1]C.-S.Chan and C.-C.Chang,“An efficient image authentication method based on hamming code,” Pattern Recognition,vol.40,no.2,pp.681-690,2007.

[2]T.-Y.Lee and S.-D.Lin,“Dual watermark for image tamper detection and recovery,” Pattern Recognition,vol.41,no.11,pp.3497-3506,2008.

[3]S.-S.Wang and S.-L.Tsai,“Automatic image authentication and recovery using fractal code embedding and image in painting,” Pattern Recognition,vol.41,no.2,pp.701-712,2008.

[4]C.-W.Yang and J.-J.Shen,“Recover the tampered image based on VQ indexing,” Signal Processing,vol.90,no.2,pp.331-343,2010.

[5]R.W.Hamming,“Error detecting and error correcting codes,” The Bell System Technical Journal,vol.26,no.2,pp.147-160,1950.

[6]C.-S.Chan,“An image authentication method by applying hamming code on rearranged bits,” Pattern Recognition Letter,vol.32,no.14,pp.1679-1690,2011.

[7]C.-C.Thien and J.-C.Lin,“A simple and high-hiding capacity method for hiding digit-by-digit data in images based on modulus function,” Pattern Recognition,vol.36,no.12,pp.2875-2881,2003.

[8]G.Voyatzis and I.Pitas,“Chaotic mixing of digital images and applications to watermarking,” in Proc.of European Conf.on Multimedia Applications,Louvain-la-Neuve,Belgium,1996,pp.687-695.

[9]J.Serra,Image Analysis and Mathematical Morphology,New York:Academic Press,1982.