INTRODUCTION

The rapid growth of multimedia and Internet technologies has produced huge amount of audiovisual information in the digital format, resulting in information explosion and several serious issues. The first issue is how to protect intellectual property rights since digital multimedia can be losslessly copied and distributed over Internet. Copyright protection of digital images is defined as the process of proving the intellectual property rights to a court of law against the unauthorized reproduction, processing, transformation or broadcasting of a digital image (Herrigel et al., 1998). The second issue is how to authenticate the content of digital multimedia as it is easy to modify and forge multimedia data by widely available editing tools. The ability to detect changes in digital multimedia has been very important for many applications, content authentication has therefore been one of the most important issues in the digital world (Lv et al., 2007). The third issue is how to efficiently search desired multimedia content from the huge multimedia database and therefore content-based retrieval has been an interesting and rapid developing research area since the 1990’s. In general, techniques for content authentication and copyright protection can be classified into three categories: digital signature based, watermark based (Fiaidhi and Mohammed, 2003; Khan et al., 2008; Lu and Li, 2006; Lu et al., 2000, 2003, 2005; Lu and Sun, 2000; Qureshi and Tao, 2006) and perceptual hash based (Dittmann et al., 1999; Lei et al., 2010; Lu and Liao, 2003; Lv and Lu, 2011; Monga et al., 2006; Monga and Evans, 2006; Monga and Mhack, 2007; Venkatesan et al., 2000; Yu et al., 2010; Yu and Lu, 2009). A digital signature is a mathematical scheme used to demonstrate the authenticity of a digital message or document. Similar to handwritten signatures, digital signatures must fulfill the following characteristics: (1) they should be unforgeable; (2) recipients must be able to verify them; (3) signers must be unable to repudiate them later. In addition, digital signatures cannot be constant and must be a function of the entire document it signs. Digital watermarking is the process of embedding watermark into digital multimedia such that the watermark can be extracted or detected later for many purposes such as copy protection and content authentication. Digital watermarking has been an active and important research subject and development and commercialization of watermarking techniques is being deemed necessary to help address many challenges faced by the rapid proliferation of digital content. Perceptual image hashing is an effective technique for image indexing, watermarking and content authentication. A perceptual hash is a hash function designed for multimedia contents. Perceptual hash functions use fingerprinting techniques with cryptosystem-like constraints. The properties of a perceptual hash function are: easiness of computation, weak collision resistance and a fixed output bit length called perceptual digest. A small content change yields a small change of the perceptual digest. A large content change leads to a large change of the perceptual digest. An image hash function can be used as the robust feature of an image for image retrieval or copyright protection. An image hash function can be split into two stages. In the first step, a feature vector (or intermediate binary string) is extracted from the image to capture the important perceptual aspects of the image. In the second step, the feature vector (or the intermediate string) is securely transformed, compressed or quantized to obtain the final hash.

Most traditional image hashing methods are designed only for one purpose, e.g., content authentication or image retrieval. Technically, they can be roughly classified into following categories: statistics based (Venkatesan et al., 2000), relations based (Lu and Liao, 2003), low-level features based (Dittmann et al., 1999), feature points based (Monga and Evans, 2006), clustering based (Monga et al., 2006), non-negative matrix factorizations based (Monga and Mhack, 2007) and DCT-domain statistics based (Lei et al., 2010; Yu et al., 2010). Venkatesan et al. (2000). utilized randomized signal processing techniques to irreversibly transform an image into random binary strings that are robust against compression or geometric distortions. Lu and Liao (2003) proposed a structural digital signature for image authentication based on the fact that, in a subband wavelet decomposition, a parent node and its child nodes are uncorrelated, but they are statistically dependent. Dittman et al. (1999) proposed the application of feature points to perceptual hashing since they are sensitive to several perceptually insignificant modifications as well as content changing operations. Monga et al. (2006) proposed a wavelet based feature detector to extract significant image features based on the characteristics of the visual system. Monga et al. (2006) proposed the idea to divide image hashing into two steps, i.e., feature extraction (intermediate hash) followed by data clustering (final hash). For any perceptually significant feature extractor, they provided a polynomial-time heuristic clustering algorithm to automatically determine the final hash length needed with a specified distortion. Monga and Mhack (2007) proposed the non-negative matrix factorization (NMF) for image hashing, where they viewed an image as a matrix and the goal of hashing as a randomized dimensionality reduction operation that maintains the nature of the original image matrix against intentional attacks of guessing and forgery. Lei et al. (2010) proposed a new robust image hashing scheme based on the Discrete Cosine Transform (DCT) and Least-Squares Line (LSL) fitting of Discrete Wavelet Transform (DWT) coefficients. Recently, Yu et al. (2010) proposed a novel image hashing scheme based on the statistical invariance of DCT coefficients, where they extracted the invariant parameters with the modified ML principle.

To achieve multiple purposes of copyright protection and content authentication simultaneously, several multipurpose image hashing schemes (Yu and Lu, 2009; Lv and Lu, 2011) have been proposed recently. They proposed a multipurpose image hashing scheme based on DCT-VQ, where two index tables are used to generate two fingerprints for authentication and copyright protection respectively. Similarly, Lv and Lu (2011) proposed a multipurpose image hashing scheme based on Mean-Removed VQ. In this study, we propose a new multipurpose image hashing scheme based on Block Truncation Coding (BTC). The advantages lie in three aspects. First, it is multipurpose. Second, the copyright protection and authentication can be performed visually other than conventional image hashing schemes. Last, the proposed method is fast. The experimental results demonstrate the effectiveness and efficiency of the proposed scheme.

BTC-BASED MULTIPURPOSE IMAGE HASHING SCHEME

Block truncation coding: Block Truncation Coding (BTC) (Delp and Mitchell, 1979) is a simple and fast lossy image coding technique, which has the advantage of being easy to implement compared to transform coding and Vector Quantization (VQ) (Linde et al., 1980; Gray, 1984). Its simplicity, performance and channel error resisting capability make it attractive in the real-time image transmission. BTC is a one-bit adaptive moment-preserving quantizer that preserves certain statistical moments of small blocks of the input image in the quantized output. The original BTC method preserves the block mean and the block standard deviation. Lema and Mitchell present a simple and fast variant of BTC named Absolute Moment BTC (AMBTC) (Lema and Mitchell, 1984) that preserves the higher mean and the lower mean of a block, which can be expressed as follows:

In the original AMBTC method, the image is divided into blocks of size k = 4x4. The mean value m of the pixels in each block x is taken as the one-bit quantizer threshold, i.e.,

(1)

The two output quantization level values are defined as:

(2)

(3)

where, L and H denote the lower mean and the higher mean respectively and q stands for the number of pixels whose values are larger than the mean value. If q = 0, then each pixel in the block has the same value, so we can define H = L = m for this case. Then a two-level quantization is performed for the pixels in the block to form a bit plane so that ‘0’ is stored for the pixels with values not larger than the mean and the rest of the pixels are presented by ‘1’. The image is re-constructed at the decoding phase from the bit plane by assigning the value L to ‘0’ and H to ‘1’. Thus a compressed block appears as a triple (L, H, P), where L, H and P denote the lower mean, the higher mean and the bit plane, respectively. Figure 1 gives an example of encoding and decoding an image block based on AMBTC. The advantages of AMBTC lie in four aspects, i.e., it is very fast, it is easy to implement, it has low computational demands and it preserves the quality of the reconstructed image and retains the edges. Obviously, in the AMBTC, the lower mean and the higher mean are coded separately with 8 bits each and the bit plane needs 16 bits, so the bit rate of AMBTC is (8+8+16)/16 = 2bits/pixel.

Proposed image hashing scheme: Our BTC-based multipurpose image hashing scheme is depicted in Fig. 2. The main idea is to obtain two intermediate binary images according to the number of ‘1’s in the bitplane and the relationship between the lower mean and high mean of each block and then perform the first XOR operation between one intermediate binary image and the permuted copyright logo and the second XOR operation between the other intermediate binary image and the authentication mark, respectively. The resulting two binary images can be finally served as the authentication and copyright fingerprints of the original gray-level image. Given the NxN sized input original image I_O, the N/4xN/4 sized input binary copyright logo I_L, the N/4xN/4 sized input binary authentication mark I_M, assume the output binary copyright fingerprint is denoted as F_C of size N/4xN/4 and the output binary authentication fingerprint is denoted as F_A of size N/4xN/4, then the whole multipurpose image hashing process can be illustrated as follows:

Step 1: Segment I_O into non-overlapping blocks B_ij of size 4x4, where i, j = 1, 2,…, N/4 and permute I_L with the key, Key0, to obtain the permuted logo I_L’.

Step 2: Calculate the lower mean L_ij, the higher mean H_ij and the bitplane P_ij for each block B_ij as shown in Eq.1-3 and Fig. 1.

Step 3: Map the mean matrices L = {L_ij} and H = {H_ij} to the binary image I_C based on the mapping function MF1, which can be described as follows:

(4)

Fig. 1:	AMBTC by the triple (L, H, P)

Fig. 2:	BTC-based image hashing process

where, T₀ is a threshold and we set T₀ = 20 in this study.

Step 4: Map the bitplane sequence {P_ij} to the binary image I_A based on the mapping function MF2, which can described as follows:

(5)

where, n_ij denotes the number of ‘1’s in P_ij and T₁ is a threshold. This paper sets T₁ = 8.

Step 5: Perform the XOR operation between I_C and I_L’ to obtain the final copyright fingerprint F_C. Similarly, perform the XOR operation between I_A and I_M to obtain the final authentication fingerprint F_A.

The authentication process: The authentication process is shown in Fig. 3, which can be briefly expressed as follows:

Inputs: The suspect image I_O’, the registered copyright fingerprint F_C and the registered authentication fingerprint F_A, the original copyright logo I_L and the original authentication mark I_M.

Outputs: The binary decision result of the copyright existence and the binary decision result of the authenticity.

Step 1: Using the same steps 1-4 in the hashing process to obtain the binary images I_C’ and I_A’ from the suspect image I_O’.

Step 2: Perform the XOR operation between I_C’ and F_C to obtain the suspect permuted logo I_PL and perform the XOR operation between I_A’ and F_A to obtain the suspect mark I_M’. Then, the suspect permuted logo I_PL is further inversely permuted with the key, Key0, to obtain the suspect logo I_L’.

Step 3: Calculate the Hamming Similarity (i.e., the percentage of identical bits when comparing two binary strings) between the suspect logo I_L’ and the original logo I_L. If the similarity is larger than the threshold TH₁, then the copyright exists; otherwise, the copyright doesn’t exist. Similarly, compare the suspect mark I_M’ with the original mark I_M. If the similarity is larger than the threshold TH₂, then the suspect image I_O’ is authentic; otherwise, it is not authentic.

EXPERIMENTAL RESULTS

To demonstrate the effectiveness of our scheme, the 256 gray-level 512x512 Woman image is used as the test image, as shown in Fig. 4a. The Woman image is segmented into 16384 blocks of size 4x4 for BTC encoding. The original copyright logo, the permuted copyright logo and the original authentication mark are given in Fig. 5a-c, respectively. The two binary images of size 128x128 obtained with the mapping functions MF1 and MF2 are shown in Fig. 5d, e and the final obtained two fingerprints are shown in Fig. 5f, g. The copyright logo and authentication mark extracted from the image without any attack are shown in Fig. 5h, i. To check the robustness and authentication ability of our algorithm, we perform several attacks on the original image, including JPEG compression with QF = 50, cropping in the middle part of the image, rotation by angle 1°, median filtering with the radius of 3 pixels and sharpening.

Fig. 3:	The authentication process

Fig. 4:	The original and attacked Woman images

The attacked images are shown in Fig. 4b-f. The extracted logos and marks against these attacks are shown in Fig. 5 j-s. Here, the similarity between the extracted mark M’ = {M’_ij}and the original mark M = {M_ij} is defined as follows:

(6)

We also test the complexity of our scheme and the VQ based multipurpose image hashing scheme presented (Lv and Lu, 2011), we find that the complexity of our algorithm is only one tenth that of the algorithm by Lv and Lu (2011). The reason is that VQ should perform the time-consuming codeword search algorithm during image encoding.

Fig. 5:

Performance testing results; (a-c) Original copyright logo, permuted logo and original authentication mark; (d-g) Obtained binary image IC, binary image IA, copyright fingerprint and authentication fingerprint; (h-i) Extracted copyright logo and authentication mark without any attack; (j-s) Extracted 5 copyright logos and 5 authentication marks under 5 attacks, i.e., JPEG compression with QF = 50, cropping in the middle part of the image, rotation by angle 1°, median filtering with the radius of 3 pixels and sharpening, respectively

From these results, we can easily see that the proposed method is both effective and efficient.