Daofu Gong , Yan Chen , Haoyu Lu , Zhenyu Li and Yibing Han

Abstract: To detect and recover random tampering areas, a combined-decision-based self-embedding watermarking scheme is proposed herein. In this scheme, the image is first partitioned into 2×2 size blocks. Next, the high 5 bits of a block’s average value is embedded into its offset block. The tampering type of block is detected by comparing the watermarks of its pre-offset and post-offset blocks. The theoretical analysis and experiments demonstrate that the proposed scheme not only has a lower ratio of false detection but also better performance with regard to avoiding random tampering.

Keywords: Fragile watermarking, self-embedding, offset block, tamper recovery, random tampering.

1 Introduction

Digital images, one of the main carriers for obtaining and disseminating information, are of great convenience to mankind. However, their feature of being easily edited and modified introduces several security risks. Therefore, authenticity verification, locating tampered areas, and tamper recovery, all constitute important research branches of information security.

Self-embedding watermarking as a branch of information hiding is a technique of encoding the image itself as watermark information. It evaluates the change in the watermark extracted from the tampered image to verify its integrity and recovers the tampered image area using the self-encoding image information. The block-based method is one of the research focuses in self-embedding image authentication technology. The method divides the image into blocks, and for each block, it generates an authentication watermark and a restoration watermark to locate the tampering and restore the image at the block level. Hence, locating accuracy and algorithm security can be balanced by the size of the block.

Lin et al. [Lin, Hsieh and Huang (2005)] proposed a block-based multi-level fragile watermarking algorithm. The algorithm first divides the original image into 4×4 and selects the offset blocks of each block. Then, each block is further divided into 2×2 blocks, and the authentication and restoration watermarks are calculated. Finally, the watermarks are embedded in the offset blocks of the 4×4 blocks.

However, He et al. [He and Chen (2007); Chang, Fan and Tai (2008)] pointed out a security risk due to the small mapped key space, and proposes a forgery attack against the method proposed by Lin et al. [Lin, Hsieh and Huang (2005)]. Wang et al. [Wang, Liu,Liu et al. (2008)] proposed a fragile watermarking algorithm, which can examine the tampering and recover the tampered area under certain conditions. First, the image is divided into 8×8 blocks, and the corresponding offset sub-block is determined using chaotic mapping. Then, the recovery watermark is generated from the DCT coefficients of the sub-block and embedded in the sub-lowest bit of the offset block. Finally, the authentication watermark is embedded in the lowest bit of the sub-block.

Duan et al. [Duan, Zhao, Li et al. (2010)] proposed a recoverable fragile watermarking algorithm based on the Slant transform. Based on the independent blocking technique,this algorithm embeds the watermark bits for authentication into the mid-frequency region of the Slant transform domain of each block. The compressed image data is embedded as the restoration watermark in the lowest bit of the pixel. The tamper localization and restoration accuracy are all at 8×8 block level.

In Yang et al. [Yang and Cai (2011)], a fragile watermarking algorithm based on block recovery is proposed, which first divides the image into 2×2 blocks and performs singular value decomposition on the highest 6 bits of each block. Then, after chaos scrambling (as in Wang et al. [Wang, Liu, Liu et al. (2008)]) is performed on the block, it embeds the restoration watermark in the second lowest position of the image block and embeds the authentication watermark in the least significant bit of the image block. The accuracy of the tamper localization and recovery is at 2×2 block level. In Chang et al. [Chang and Tai(2013)], authentication and restoration watermarks were generated for each image block and used for the detection of the image block neighborhood, as well as the hierarchical structure, to detect the tampering of the image block.

Deng et al. [Deng, Chen, Zeng et al. (2013)] proposed a tamper detection and recovery algorithm for medical images. The algorithm divides the image layer by layer using a quadtree, then generates restoration and certification watermarks for each block and embeds them in the LSB of the image. In Chen et al. [Chen, He, Huo et al. (2011)] a variable-capacity self-recovery watermarking algorithm is proposed. The watermark of the algorithm consists of a 24-bit basic watermark and a variable-length restoration watermark. In Kiatpapan et al. [Kiatpapan and Kondo (2015)], a dual watermark algorithm is proposed for the authentication and restoration of color images. In Dhole et al. [Dhole and Patil (2015)], a self-embedding watermarking algorithm based on blockchain is proposed for authentication and recovery of 8×8 image blocks. In Singh et al. [Singh and Singh (2016)], a self-recovery fragile watermark based on the DCT coefficients of a 2×2 image block is proposed. It generates a 2-bit authentication watermark and a 10-bit restoration watermark for each image block, which should be embedded in the lowest 3 bits of the offset blocks. For this reason, such watermark embedding significantly affects image quality. Qin et al. [Qin, Ji, Wang et al. (2017)]proposed a self-recovery fragile watermark based on vector quantization. Using vector quantization to generate image content information and reference watermark information,this method implements authentication and recovery of an 8×8 image block. In Cao et al.[Cao, An, Wang et al. (2017)], a sub-embedded watermarking algorithm based on hierarchical recovery is proposed; it determines which content information to be restored first according to the importance of the image MSBs.

The self-embedding fragile watermarking algorithms mentioned above generate an authentication watermark and a restoration watermark for each block of the image, while He et al. [He, Zhang and Chen (2008); Chen, He and Wang (2012); He, Chen, Tai et al.(2012)] use the image content feature as a watermark for both authentication and recovery, causing the length of the watermark to be reduced. He et al. [He, Zhang and Chen (2008); Chen, He and Wang (2012)] proposed a self-embedding watermarking algorithm based on the Chinese Remainder Theorem. In this algorithm, a DCT transform is first performed on each 8×8 block, and DCT coefficients are quantized to generate restoration watermark information, which is embedded in the lower bits of the offset blocks. Then the authentication is performed by comparing the mean error between the reconstructed image blocks and the compressed image blocks. However, the algorithm’s authentication and recovery accuracy is only at the 8×8 block level and has a higher misjudgment rate. In He et al. [He, Zhang and Chen (2008)], the content information of each 2×2 image block is quantized into 5 bits as a watermark. Tamper detection is performed by comparing the match/matching degree of eight neighborhood characteristics of each block and the watermark. This paper has improved the methods described in Chen et al. [Chen, He and Wang (2012); He, Chen, Tai et al. (2012)]. In Chen et al. [Chen, He and Wang (2012)], a variable-capacity self-embedding watermarking algorithm is proposed, which enables resistance against constant mean attacks. In He et al. [He, Chen, Tai et al. (2012)], a variety of optimizations has been carried out on tamper detection, boosting the performance of the algorithm for area tampering. However, the algorithms in He et al. [He, Zhang and Chen (2008); Chen, He and Wang (2012); He, Chen, Tai et al. (2012)] have a high false negative rate and poor performance in detecting random tampered images.

To solve the problem of detection and recovery of random tampering, as well as the credibility of the recovery, this paper proposes a self-embedding fragile watermarking algorithm based on the combined decision of pre-offset and post-offset blocks. The algorithm utilizes the matching of the feature watermark and extracted watermark of its pre-offset and post-offset blocks to determine tampering. It judges if the post-offset block is tampered with to determine whether it can be recovered. Theoretical analysis and experiments show that the proposed algorithm effectively reduces the false detection rate and can accurately locate and recover the random tampering of the image.

2 The proposal of the idea

In the neighborhood-based self-recovery watermarking method proposed in He et al. [He,Zhang and Chen (2008); Chen, He and Wang (2012); He, Chen, Tai et al. (2012)], the image is first divided into 2×2 blocks, and the content information of the block is quantized by 5 bits and embedded as watermark information into its offset sub-block. The basic principle of judging if an image block has been tampered with is shown in Fig. 1,assuming that the watermark information of 16 image blocks in area A is randomly embedded in 16 gray image blocks (noted as set B). Correspondingly, the watermark information of the 16 black image blocks (noted as set C) is embedded in area A. Since the watermark information corresponding to the image blocks in set C will be changed once area A is tampered with, the image blocks in area A and set C will be detected rather than set B. Therefore, tampered area A must be distinguished from the untampered set C. As can be seen from Fig. 1, the number of tampered image blocks around the image block in area A is greater than the number of tampered image blocks around the image block in set C. Then by comparing the number of detected image blocks in the 8-neighborhood of the measured image block and its offset block, the detected image blocks in area A and set C can be distinguished, thereby reducing the probability of false alarms. Afterwards, the watermark information of area A embedded in set B will be used for recovery.

Figure 1: Watermark embedding position diagram in He et al. [He,Chen, Tai et al. (2012)]

Figure 2: Watermark embedding position diagram in this paper

This idea can effectively detect area tampering, but a single image block being modified(i.e. random tampering), is difficult. For example, if area A is a single image block, the number of detected blocks of image block A and neighboring area C is 0, so that the tampering of A and C cannot be distinguished. At the same time, if the watermark information contained in set B is tampered with while the image block in the area A is still being used to recover, an erroneous, and therefore unreliable recovery, will occur.

To solve this problem, this paper carries out tamper detection and recovery using an offset block combined decision. To illustrate the basic principles of the algorithm, a single image block is adopted as an example. As shown in Fig. 2, the watermark of image block A is embedded in image block B, and the watermark of image block C is embedded in image block A. Image block B is herein referred to as the “pre-offset block” of image block A, and image block C is called the “post-offset block” of image block A. The watermark generated by the higher bits information of the image block is referred to as a“feature watermark”, and the watermark information extracted from the lower bits of the pre-offset block is referred to as “extracted watermark”.

In fact, simply comparing the feature watermark with the extracted watermark will result in set A and set C being indistinguishable. This is because the content of the image block in set A has been tampered, thereby causing its feature watermark to change and as a result, the feature watermark and the extracted watermark cannot be matched. For the image block in set C, the extracted watermark contained in set changes with the

tampering of set A, so that the feature watermark and the extracted watermark cannot be matched. Therefore, for situations in which the extracted watermark of the image block and of the content feature being tampered can be distinguished, the distinction of sets A and C can be completed, and the problem of false recovery caused by a misused watermark can be avoided.

For image block A, when its feature watermark matches the extracted watermark, it is considered to have not been tampered. When the feature watermark and the extracted watermark do not match, image block A or B are considered to have been tampered. If image block A is tampered with, it will cause abnormal behavior of the extracted watermark of image block C, with the result that the features of image blocks A and C cannot be matched with the extracted watermark information. On the other hand, if image block A has not been tampered with, the features of image block C and the watermark information can be matched. Thus, by judging the matching of the feature watermark and the extracted watermark of post-offset block C, it is possible to distinguish the tampering condition of image block A. In addition, when it is determined that A is tampered with and image block B is authenticated, the extracted watermark is considered to not have been tampered with, and a restoration can be performed. Otherwise, it is considered that the extracted watermark is not authentic and cannot be restored. The paper is based on this idea of tamper detection and recovery.

3 The algorithm description

3.1 Watermark generation and embedding

Assume the original image as X with size of M×N. Divide it into non-overlapping blocks with size of2×2, which can be expressed as X=(B1,B2,…,Br), whereis a 2×2size image block, and r= M×N4. The process of watermark generation and embedding can be described as:

Step1. For image block Bi, generate content information BCibased on key K1. The specific method is: Random binary sequences Z=(z1,z2,…,z2r)are generated based on K1. According to the sequences, the 2LSB position of pixel bi(2z2i+z2i-1)is set to zero, and the LSBs of all pixels are set to zero.

Step2. Based on keyK2, the feature watermark Wiof the image block Biis generated.The specific method is to encrypt the 5 MSBs of the block content BCiusing key K2, and generate the feature watermark Wi=(wi1,wi2,wi3,wi4,wi5).

Step3. DefineBσ(i)as the offset block of Bi, where mapping function σ(i)needs to meet the following conditions: 1)σ(i )∈{1,2,…,r}, 2)σ(i)≠i, and 3) For any i, j∈{1,2,…,r}，when i≠jthere is σ( i)≠σ(j)。

Step4. Embed the watermark informationWiinto the zero setting bits of block Bσ(i)to generate the watermarked image block

3.2 Temper detection and recovery

Assume the tampered watermarked image to be. Divide it into non-overlapping blocks of size 2×2, represented as. The specific steps of tamper detection and recovery can be described as:

Step1. Based on keysK1and K2, the feature watermarkof blockis generated according to the Step1 and Step 2 mentioned above in Section 3.1.

Step3. After obtaining the feature watermark and extracted watermark of all blocks, for a block, setas the pre-offset block. That is, mean i=σ(k). According to the matching condition the of feature watermark and extracted watermark, it determines whether the image blocktampered with. It can be divided into four cases as follows:

4 Performance analysis

4.1 Correlation definitions

Definition 1. AssumeH0as a set of tampered image blocks, and H1as a set of untempered image blocks. For any block, defineandas probabilities of∈H0and∈H1, respectively.

According to this definition, there areH0∪H1=，H0∩H1=φ. In the case of area tampering, it is considered that all pixels in a block are modified, so

However, in the case of random tampering, the tampered probability of each pixel is p.An image block is considered as tampered if one pixel in it is tampered with, so in this case:

Definition 2. Define PC|Has the probability that feature watermark informationis

0 changed and PL|H0as the probability that watermark information contained in the LSBs of(i.e. the extracting watermarkof block) in the case of∈H0. It is clear that PC|H0=1. For PC|H0, we need to analyze two cases of area tampering and random tampering:

1) In the case of area tampering, the changed probability of each watermark bit in the LSBs is 1/2,

2) In the case of random tampering, the probability that x pixels in blockare tampered with is

Because the watermark information is embedded in the LSBs and one of the 2LSBs, the probability of the lowest position ofchanged is:

So, in case of random tampering:

0

0

1

4.2 Ability of tamper detection

In this section, we will analyze the ability to detect tampering by analyzing the false positive rate of the four cases in Section 3.2.

For Case 1, it is false positive ifwhenis a tampered block, and its false positive rate is:

For Case 2, it is false positive ifwhenis an un-tampered block, and its false positive rate is:

For Case 3, it is false positive iftampered block, and its false positive rate is:

For Case 4, it is false positive ifis an untampered block, and its false positive rate is:

Figure 3: False positive rate with tamper rate in various cases under area tampering

Figure 4: False positive rate with tamper rate in various cases under random tampering

Fig. 3 shows the values of Pf1,Pf2,Pf3and Pf4with the rate of tampering pfrom 0-30% under the area tampering. The false positive rates of all kinds of cases are below 10%, indicating that the tamper situation can be accurately determined under the area tampering. Fig. 4 gives the values ofPf1,Pf2,Pf3and Pf4with the rate of tampering pfrom 0-15%, under random tampering. It can be seen from the figure that the false positive rate of Case 3 is maximum, while the other three cases put up smaller false positive rate. This indicates that these three cases can accurately determine whether the tampered image blocks under random tampering.

4.3 Missing detection rate and false detection rate

According to Section 3.2, it is missing detection when Case 1 and Case 3 are false positive:

The missing detection rate (the missing detected blocks account for the proportion of all image blocks) and false detection rate (the false detected blocks account for the proportion of all image blocks) are, respectively:

Figure 5: Missing detection rate and false detection rate with tamper rate under area tampering

Figure 6: Missing detection rate and false detection rate with tamper rate under random tampering

Fig. 5 shows the missing detection rate and false detection rate comparison of proposed algorithm and the algorithm of He et al. [He, Chen, Tai et al. (2012)] (named He-Rfa and He-Rfr respectively) under area tampering. Under area tampering, the false detection rate of the proposed algorithm is higher than that of He et al. [He, Chen, Tai et al. (2012)], but the missing detection rate is obviously lower than that of [He, Chen, Tai et al. (2012)].Fig. 6 shows the missing detection rate and false detection rate comparison of the proposed algorithm and the algorithm of He et al. [He, Chen, Tai et al. (2012)] under random tampering. Under random tampering, the false detection rate and missing detection rate of the proposed algorithm are both lower than that of He et al. [He, Chen,Tai et al. (2012)]. This indicates that the proposed algorithm can detect the random tampered image blocks more accurately.

5 Experiments and analysis

We used the 256×256 grayscale images shown in Fig. 7 as the test, with pixels between[0~255]. The chaotic scrambling method is used to select the offset blocks. In the authentication results, the non-tampered image blocks are represented by black (gray value: 0), and the tampered image blocks are represented by white (gray value: 255). The validity of the proposed algorithm is verified from two aspects: Tamper detection and recovery capability, resistance to random tamper ability test.

Figure 7: Test images

5.1 Tamper detection and recovery capability

To verify the tamper detection and recovery abilities of the proposed algorithm, we verify its effectiveness in a clipping attack, image collage attack, intra-image collage attack, and so on.

Figure 8: Temper detection and recovery results for clipping attack

Figure 9: Tamper detection and recovery results for collage attack between images

Fig. 8 shows the temper detection and recovery result images for a clipping attack. The single region and multiple regions of the clipping image are tested. From the experimental results, we can see that the algorithm can detect the clipping area accurately and carry out a high-quality recovery.

Fig. 9 shows the tamper detection and recovery result images for a collage attack between images. The collage attack of two images and the collage attack in the same region of the two images are tested. From the experimental results, we can see that the algorithm can not only detect the collage area accurately, but also detect and recover the collage attack in the same region.

Fig. 10 shows the temper detection and recovery result images for a collage attack inside an image. In it, the first letter “W” of the license plate is copied onto the second letter “E”,and the second number “2” is copied to the first number “0”, so that the license plate number is modified to “WWE 220”. It can be seen from the experimental results that the proposed algorithm can accurately detect the tampered regions of intra-image collage and carry out high-quality recovery.

Figure 10: Temper detection and recovery results for a collage attack internal an image

Figure 11: Detection and recovery results under random tampering with “spray gun”

5.2 Detection ability to random tampering

For random tamper attacks, the “Pepper” image is random tampered with a “spray gun”image and “pencil” tools in Windows Drawing. To verify the effectiveness of the proposed algorithm, it is compared with the neighborhood-based authentication algorithm(see He et al. [He, Zhang and Chen (2008); He, Chen, Tai et al. (2012)]). Fig. 11 shows the result of detection and recovery for the image tampered by the “spray gun” tool. Fig.12 uses the “pencil” tool to make random single pixel tampering of the watermarked image, and its authentication and recovery results. From the experimental results, we can see that, compared with the algorithms of He et al. [He, Zhang and Chen (2008); He,Chen, Tai et al. (2012)], the proposed algorithm can detect the areas of random tampering and even single pixel tampering accurately, and achieve high-quality recovery.

Figure 12: Detection and recovery results under random tampering with “pencil”

6 Conclusions

Self-embedded fragile watermarking technology can detect and recover the tampered regions of an image and has received extensive attention and research. In this paper, a self-embedding fragile watermarking algorithm based on combined decision using offset blocks is proposed to solve the problem of accurate detection and recovery under random tampering. The main contributions of this article include the following:

1. In this paper, the feature of the image block is generated as the watermark, and is used not only for tamper detection, but also for recovery. Thus, the length of watermark is reduced.

2. Image block tampering detection is done by matching the feature watermark and extracted watermark from the pre-offset and post-offset blocks. This makes it avoid the false detection caused by the extracted watermark being tampered with and does not need the neighborhood image block which can effectively detect randomly tampered image.3. When the tampering is reversed, the recovery is improved by judging whether the postoffset block is tampered with or not, and the credibility of the recovery is improved.

However, the proposed algorithm is only applicable to the authentication and recovery of space image. How to adapt the fragile watermarking algorithm for compressed image is the main research direction of this paper.

Acknowledgment:This work was supported in part by the National Natural Science Foundation of China (No. 61401512，61602508, 61772549, 6141512 and U1636219), the National Key R&D Program of China (No. 2016YFB0801303 and 2016QY01W0105), the Key Technologies R&D Program of Henan Province (No. 162102210032), and the Key Science and Technology Research Project of Henan Province (No. 152102210005).