Local Content Based Image Authentication for Tamper Localization

Published Online September 2012 in MECS

Digital multimedia plays a vital role in applications such as broadcast monitoring, gathering of intelligence information, criminal investigation, security, and medical care. This data can be vulnerable to several malicious modifications during its transfer over public network like internet and trustworthiness could no longer be guaranteed. Any tamper to an image could change the decisions based on that image. Recently, digital watermarking techniques have been considered as one of the promising techniques for multimedia authentication. It is the best way to certify the integrity and authenticity of the digital images. It is a complete solution for claiming legitimate usage, authentication of authorized users, and it is also possible to provide extra information along with the digital contents. The transfer of watermarked images can discourage unauthorized copying. This is because the owner can prove his ownership by extracting the watermark using some methods and security keys. Several approaches have been proposed for the image content authentication. These approaches can be classified into strict and selective authentication. Strict Authentication consists of conventional cryptography and fragile watermarking techniques; whereas semi fragile and digital signature based algorithms are classified as selective authentication. Several researches have used these image characteristics for image authentication. Typically the image characteristics include edges, colors or grey levels, histograms, DWT or DCT coefficients, textures , Statistical measurements form the image content. In signature based schemes [1-4], the signature is the hash of image contents or image characteristics computed and encoded via public key cryptosystem or signed value. These mechanisms can detect if an image has been changed; however, they cannot locate where the image was changed. Fragile watermarking schemes [5-10] for tamper proofing/authentication computes a keydependent function on the local areas of the image and embedded into the corresponding areas. Watermarking techniques are used to dissimulate the signature in the image. Some of the watermarking techniques which used image characteristics for computing image hash and embedded into the transform domain are discussed in this paper. In [11], an approach for still image digital watermarking is proposed in which the watermark embedding process employs the wavelet transform and incorporates Human Visual System (HVS) characteristics. In [12], a block level embedding in Discrete Hartley Transform (DHT) and the Discrete Cosine Transform (DCT) using the edges of the image block as the threshold is proposed. In [13], a feature based watermarking scheme which embeds in the selected subband coefficients of the image transformed by DFT is presented. In [14], a hybrid watermarking algorithm by combining fragile and robust watermarking is proposed. The watermark is a content hash generated from the host image. The watermark is embedded into the DWT Transform of the image. A tradeoff between the length of the hash and tamper localization was exploited and a robust image hashing method in which the hash is calculated from the features of the image is presented in [15]. In authenticating an image using the fragile watermark scheme, the watermark is extracted from the given image to verify its integrity. The local contentbased watermark considered usually extracts robust feature point, and then partitions the image into multiarea using the feature point as the centre; finally the watermark is repeatedly embedding into each area. The present paper is organized as follows, Section II discuss the related works. Section III illustrates the watermark embedding and an extraction method, Section IV describes the experimental results and gives a comparison between the proposed method and other existing methods. Conclusions are given in Section V.

• II.    Related Work

In [5], Walton proposed an authentication scheme using watermarking. A checksum is constructed out of the seven most significant bits of each pixel. The pixels for embedding are chosen pseudo randomly and the checksum bits are embedded in the LSB of the chosen pixel. In [16], Wong proposed a block based watermarking technique. The detailed process is described as follows: The original image is divided into non-overlapping blocks. The LSB’s of all the pixels in the block are modified to zero. Then a hash value is computed using the modified block and the image dimensions as given in below:

H =H(M,N,B ) (1)

Where H is the cryptographic hash function such as MD5, M and N are the image dimensions. The signature of the each block is obtained by XORing the computed hash with the watermark pattern. The signature is encrypted by a public key cryptosystem as given below:

C = E (H ⊕ Ԝ) (2)

Where C is the signature, ‘ ⊕ ’ is the XOR operation and E is the encryption function. The signature C is embedded into the LSBs of the pixels in block Bi.

In the verification process, the watermarked image is divided into non-overlapping blocks and the signature is calculated from the LSB of each pixel of the block. The hash H is computed using (1). The watermark is obtained by decrypting the signature C by

W =D (H ⊕ C )                        (3)

where D is the decryption function.

In [17], Chang et al. proposed an authentication method based on fragile watermarking. At first the image is divided into 3 x 3 overlapping blocks. The center pixel of each block is embedded with the cryptographic hash of the features of the corresponding block. The feature of a block consists of the eight neighboring pixels, the index of the block, the height and width of the image and the user’s secret key. A cryptographic hash of the feature of the block is calculated using MD5 as given in (4). In figure 1, X represents the center pixel in which the data is embedded. The 8-neighbors of the center pixel are P 1 , P 2 ,.., P 8 .

The cryptographic hash of the block is given by, H(B)=(P‖Р ‖…․․‖Р ‖і‖ID‖Κ)              (4)

where ‖∙‖ is the concatenation operator, B i is the i ^th block of the image, ‘i’ is the block number, ID is the image identity and K u is the user secret key. The hash of each is obtained, and is embedded into r least significant bits (LSBs) of the pixel X, where 2 ≤ r ≤ 4.

• III.    Proposed Method

• A.    Embedding

Step 1: Signature Generation

The proposed LECH authentication scheme generates the signature in the first step. Various low-level visual features (e.g. color, texture, shape, edges) can be extracted from the images. Edge aims at identifying points in a digital image at which the image brightness changes sharply or more formally and has discontinuities. Edge detection process detects and outlines the boundaries between objects and the background in the image. Edge features are useful to overcome the attacks generated by noise, edge strips and acuity. That’s why the proposed method evaluates edge features on the entire image. For this the canny edge operator is used. The canny edge detector finds the edges by looking for local maximum of the gradient of unprocessed input image. A simple hash is computed from the edge features of the original image (Let it be called Edge Image). The process of finding hash involves dividing the edge image into 4x4 non overlapping blocks. The present method is a localized method because the hash is basically derived on a local block size 4x4. By dividing the image in to non overlapping blocks, the proposed method achieves high security. This hash is embedded into the corresponding block of the original image. The steps for computing the simple hash of each block are:

Step i: Compute the edge coefficients of the original image by using Canny edge operator.

Step ii: Divide the image with the edge coefficients into non overlapping blocks of size 4 x 4 pixels.

Step iii: Calculate the simple hash for each block of size m x n as shown below.

b 11	b 12	b 13	b 14
b 21	b 22	b 23	b 24
b 31	b 32	b 33	b 34
b 41	b 42	b 43	b 44
h 1	h 2	h 3	h 4

h = b ⊕ b ⊕ b ⊕ b h = b ⊕ b ⊕ b ⊕ b h = b ⊕ b ⊕ b ⊕ b h = b ⊕ b ⊕ b ⊕ b

Hash code H = h h h h .

The Hash code H is called as the content watermark.

Step 2: Secret Data

A 128 bit secret key which is shared with the receiver is used to compute the secret data. The key is replicated to L bits. Here, L is the total length of hash code of all blocks. The proposed LECH method considers a test image of size 256 x 256, which gives 4096 non overlapping blocks of size 4x4. Each block results in a 4-bit hash code by which length of L is16384 bits (4 x 4096) can be obtained. By this mechanism the LECH method replicates 128 times to form 16384 bits. The proposed LECH uses a simple XOR operation to combine four bits of the key with four bit hash code of each block in the following way. Let H be the simple hash of all blocks. Let the sequence of watermark bits (B) is {b₁b₂… b_n}, where n =L. The secret data to be embedded into each block is calculated by the proposed LECH by (5).

S = b ⊕ һ b ⊕ һ b ⊕ һ b ⊕ h                 (5)

Step 3: Pixel Prediction Technique

In the third step the pixel locations are identified for inserting the data. The entire mechanism is explained below:

Using the JPEG-LS prediction technique [18] the local texture among three pixels can be analyzed. As shown in figure 2 the predictive pattern predicts pixel X from its three adjacent pixels Pc, Pa and Pb. The pixel X is tested whether it belongs to a horizontal edge or vertical edge or neither is performed. A vertical edge exists if Pc≥max (Pa, Pb) and max(Pa, Pb) = Pa; namely, the predictive value Х′ equals Pb. Otherwise, there is a horizontal edge, and the predictive value Х′ is equal to Pa such that Pc≥max(Pa, Pb) and max(Pa, Pb) = Pb. Similarly, in case that the predictive value Х′equals to either Pa or Pb when Pc ≤ min (Pa, Pb), there is a vertical or horizontal edge. However, when the pixel value Pc falls in neither the maximum nor the minimum value interval, then it indicates a non formation of an edge.

P c	P b
P a	X

Figure 2. JPEG-LS prediction

By applying JPEG-LS prediction for X, its predictive value Х′ is computed by (6), mіn(Р ,Р )  іf Р ≥ max(Р ,Р )

Х′ = max(Р ,Р )  іf Р ≤ mіn(Р ,Р )

Р + Р - Р        otherwіѕе

The present paper considers the embedding pixel based on the JPEG-LS prediction technique. The pixels in a block are scanned in rastar scan order. The decision to find a pixel for embedding is based on the variance of its three neighboring pixels. The three neighboring pixels can be any one of the eight occurrences of figure 3. This occurrence is based on the variance of the three neighboring pixels. If the variance falls within a predefined threshold, then the corresponding pixel is selected for embedding. This process is continued in the entire block for finding the embedding pixel.

(e)

	P b	P c
	X	P a

P b	X
P c	P a

	X	P b
	P a	P c

(d)

Figure 3.  (a),(b),(c),(d),(e),(f),(g) and (h) are the patterns of finding embedding pixels in a 3x3 block.

	P b
	X	P c
	P a

(h)

Step 4: Embedding

The embedding mechanism of secret data is derived in the fourth step. For this the proposed LECH computes the difference value d i between the selected pixel and the predicted pixel by (7) and (8)

d =Р -Р .(7)

Embed a bit b into the difference as, d = 2∗ԁ +b .(8)

Using (9), the watermarked pixel is obtained,

Р =Р +d

• B.    Extraction

The steps needed to perform for extracting the secret data from the watermarked image and to recover the original pixel from the cover image is described as follows.

Step 1:The watermarked image is divided into 4x4 non overlapping blocks. In each block, the stego pixel р" is found from the variance of the three neighboring pixels.

Step 2:compute the difference by d =Р -Р . The watermark bit is computed by b=d mod 2 . To get the content watermark the extracted bits are XORed with the secret key. The original difference value d =⌊ ⌋.

Step 3: Extract the original pixel by

Р= Р + d                             (10)

Thus, an exact copy of the original pixel is obtained.

• C.    Tamper Detection and Localization

The proposed LECH method can be used to detect the tampered locations. The tampered locations are found by the following algorithm.

Algorithm: Tamper detection and localization by the proposed LECH method.

Begin

Step 1. From the recovered image, find the edge coefficients (edge image).

Step 2. Divide the edge image into 4×4 blocks.

Step 3. Find the simple hash of each block. Compute the secret data as per (5). Fold the secret data into one bit (w).

Step 4. Compare w with the extracted watermark bit b.

Authеntіс     іf w=b

Tamреrеd othеrwіѕе

End

The block = {

• IV.    Experimental Results

The present paper displayed eight original images of resolution 512x512 as shown in figure.4, to evaluate and compare the performance. Figure 5 shows the resultant watermarked images. To test the efficacy of the proposed LECH method, PSNR and NCC values are evaluated. The larger the PSNR value, the higher the image quality. This is due the fact that stego image is inverted to its original image after the data extraction, and the embedding capacity is increased to a significant factor when the visual quality of the stego image does not decline to an unacceptable degree, e.g., PSNR>30 dB. The Peak Signal to Noise Ratio (PSNR) in decibel (dB) between the original image (I) and its watermarked version image (W) is expressed by (11) and (12)

PSNR (I, W) = 10 * Log10 [(2552/ MSE]          (11)

Mean Square Error (MSE) =     ∑i^Q1 ∑ "V (I(і,ј)-

W(і,ј))                                          (12)

Where I (i, j) is the original image and W (i, j) is the watermarked image.

To verify the robustness of the digital watermarking method, Normalized Cross Correlation (NCC) is used, which is defined by (13).

NCC=∑ W(і) x W′(і)/∑ W(і) x W(і)    (13)

where W(i) is the original watermark and W ′ (i) is the extracted watermark.

(a)                  (b)                (c)

(d)

(e)                (f)                (g)

(h)

Figure 4. Test Images- a) Lena, b)Baboon, c)Cameraman, d)Peppers, e)Tiffany, f)Walk bridge, g)Living room, h)House.

(e)                (f)

(g)                (h)

Figure 5. Watermarked Images- a)Lena, b)Baboon, c)Cameraman, d)Peppers, e)Tiffany, f)Walk bridge, g)Living room, h)House.

Table I shows the performance results of the proposed LECH scheme on eight test images. The results show that the PSNR values are high for the proposed LECH method. Higher value of PSNR and NCC indicates good embedding quality and imperceptibility. Based on the simulation results, the quality of every embedded image is observed to be greater than 47 dB for all original images. As a result, the difference between the original and embedded images is unnoticeable in vision.

TABLE I. THE PERFORMANCE OF THE PROPOSED LECH SCHEME ON EIGHT TEST IMAGES.

Quality Factors	Lena	Baboon	Camera man	Peppers
PSNR(dB)	48.30	48.57	48.36	48.33
NCC	1.0	1.0	1.0	1.0

Quality Factors	Tiffany	Walk Bridge	Living room	House
PSNR(dB)	48.37	48.57	48.42	48.35
NCC	1.0	1.0	1.0	1.0

The proposed LECH method is compared with some of the existing fragile watermarking schemes for image authentication. Table II. Shows a comparison of the proposed LECH method with other methods presented in [19]-[22]. Table II gives the average of the PSNR values of these methods applied on several test images. It can be seen that the proposed LECH method yields better performance than the other competing schemes in terms of PSNR and the tamper detection rate is close 100%. The reason is that the LECH scheme embeds the block hash in to the same block. Further the hash is computed with the edges of the corresponding to that block. Hence if any pixel is changed it results in a wrong hash and hence the block can be identified as tampered.

TABLE II. A COMPARISON BETWEEN THE PROPOSED LECH SCHEME AND OTHER METHODS.

Method	Block Size	Payload (bits)	PSNR (dB)	Missing rate of Tampering
X. T. Zeng et al.[19]	8×8	4096	38.60	0.37%
Z.C. Ni et al. [20]	8×8	729	40.10	NA
X. Zhang et al. [21]	8×8	131012	37.9	0.13%
P. L. Lin et al.[22]	4×4	131072	44.37	0.39%
Proposed LECH Scheme	4×4	4096	48.93	0.10%

For tamper detection a region of pixel intensities in the watermarked image is tampered and replaced with the pixel intensities same as in the original image. The Algorithm Tamper detection and localization by the proposed LECH method is used to find the tampered locations. The extracted watermark clearly shows the tampered region. This attack, called copy attack is shown in figure 6. According to the simulation results, the positions of the tampered areas are marked correctly. For more applications, our proposed image authentication scheme also can be extended to dealing with color images and compressed images using similar methods in different domains, even though it is for grayscale and uncompressed images in the spatial domain. The proposed method can detect any tampering of size 4×4 pixels with a missing rate less than 0.10%.

(a)

(b)              (c)             (d)

Figure 6. Watermarked Image b) Tampered Region c) Binary Logo d) Extracted Logo with tampered region.

• V.    Conclusions

This paper proposed an efficient image authentication method LECH by embedding the content of the image into itself. The present study found that edges are relatively a good choice for image content authentication and hence the hash of the edge image block is computed and embedded into the corresponding block itself. With this the tampered blocks can be identified and localized. Further the proposed LECH method uses reversible data hiding scheme that makes use of the JPEG-LS predictive technique to predict the pixels for embedding. Unlike the LSB embedding technique which can be removed easily, LECH method used the Difference expansion method to embed bit of information into the predicted pixel. This improves the stego-image quality. Hence the experimental results show that the performance of the proposed scheme is better than those of some well-accepted schemes in terms of payload and stego-image quality and successfully identifies the tampering of the image content. It also accurately localizes maliciously tampered regions. Thus it can be concluded that this scheme is more fragile to malicious distortions.

Acknowledgment