Abstract:
Compressing image data includes partitioning original image data into non-overlapping blocks, transforming the non-overlapping blocks into Discrete Cosine Transform (DCT) coefficient blocks, and quantizing the DCT coefficient blocks to generate the quantized DCT blocks. A block-classification strategy is used to classify DCT-blocks into the flat-block and the normal-block. The quantized DCT blocks are then embedded with watermarks. And the watermarks are checked to determine whether the image data is tampered. Thus, the damaging problem of clipping errors caused by normailization in spatial domain can be reduced significantly.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to a method for authenticating the compressed image data, and more specifically, to a method of watermarking for authenticating the compressed image data by embedding watermarks.  
         [0003]     2. Description of the Prior Art  
         [0004]     In recent years, more and more applications for tamper detection of image data have been proposed because the applications can be used in the court to detect tampered images or to prove the image data have not been tampered. With the rapid growth of digital image data processing techniques, image data could be maliciously tampered while transferring through network or storing into a database, and they could be embezzled maliciously and illegally. Generally speaking, image data compression is used to decrease the data size to ease its transfer or storage. However, the image data could be damaged by the compression, therefore image data compression needs to be considered as one kind of legal image attack.  
         [0005]     The prior art techniques for image data authentication are not very reliable, and there are two common types of authentication errors caused by the prior art techniques. The first type, false negative (missed detection), is the missed detection of tampered area in the tampered image, and we must detect it to guarantee the preciseness of authentication. It means that some actual detecting tampered areas in the tampered image will be likely missed. The second type, false positive (false alarm), is an incidental modification like the JPEG compression is a kind of “attack” that we would like to bypass. If an incidental attack is detected, it will cause a false positive type error. Therefore, it is important to judge whether the tampered image is resulted from the intentional action or the compression process.  
       SUMMARY OF THE INVENTION  
       [0006]     It is therefore an objective of the present invention to provide a compressed-image authentication method to solve the above problems.  
         [0007]     The method of watermarking for authenticating the compressed image data comprises partitioning original image data into non-overlapping blocks, transforming the non-overlapping blocks into Discrete Cosine Transform (DCT) coefficient blocks, and quantizing the DCT coefficient blocks to generate quantized DCT blocks. When a quantized DCT block is a flat block, a watermark is embedded into a coefficient of the quantized DCT block.  
         [0008]     These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]      FIG. 1  is a flow chart illustrating a method for compressing original image data of the present invention.  
         [0010]      FIG. 2  is a diagram for the probability of false positive by various authentication steps in the normal blocks.  
         [0011]      FIG. 3  is a diagram for the probability of false negative in the tampered image by various authentication strengths in the normal blocks.  
         [0012]      FIG. 4  is a diagram of a source 8-by-8 pixel block.  
         [0013]      FIG. 5  is a diagram of a quantized DCT block from  FIG. 4 .  
         [0014]      FIG. 6  is a diagram of normal block watermarking for  FIG. 5 .  
         [0015]      FIG. 7  is a diagram of a watermarked pixel block from  FIG. 6 .  
         [0016]      FIG. 8  is a diagram of a zigzag order of the 8-by-8 pixel blocks. 
     
    
     DETAILED DESCRIPTION  
       [0017]     Please refer to  FIG. 1 , which is a flow chart illustrating a method for compressing original image data of the present invention. The method comprises following steps but not limited to the following sequence.  
         [0018]     Step  100 : receiving a fast one-dimensional pseudorandom number;  
         [0019]     Step  101 : partitioning original image data into 8-by-8 non-overlapping blocks. The original image data is part of a complete image. Each non-overlapping block has 8-by-8 pixels or coefficients. If the complete image has 384-by-288 pixels or coefficients, the complete image can be divided into 27 original image data since (384*288)/[(8*8)*(8*8)]=27 or 1728 non-overlapping blocks since (384*288)/(8*8)=1728;  
         [0020]     Step  102 : transforming the non-overlapping blocks into 8-by-8 DCT coefficient blocks by performing Discrete Cosine Transformation (DCT) according to a JPEG lossy compression standard;  
         [0021]     Step  103 : quantizing the DCT coefficient blocks to generate quantized DCT blocks according to a JPEG lossy compression standard;  
         [0022]     Step  104 : detecting number of non-zero quantized AC (NQAC) coefficients and the NQAC coefficients for each quantized DCT block;  
         [0023]     Step  105 : checking if the number of NQAC coefficients of the quantized DCT block is greater than or equal to an authentication strength which is 6 in the present embodiment; if so, the quantized block is regarded as a normal block, and the process continue in step  107  for watermarking the normal block; if not, the quantized block is regarded as a flat block, and the process continue in step  113  for watermarking the flat block;  
         [0024]     Step  107 : normalizing coefficients of the quantized DCT block from between 0 and 255 in a spatial domain to between 5 and 250 to generate a normalized DCT block. The normalization is used to reduce clipping errors of Y components of the gray-level image. If a normal block contains pixels with coefficients of extreme values such as between 0 to 5 and 250 to 255, and the normal block undergoes a transformation in step  108 , the transformation will reduce the capability of the normal block to preserve watermarks which will be embedded in step  109 . Therefore, the normalization is performed to eliminate the extreme values;  
         [0025]     Step  108 : transforming the normalized coefficients of the normalized DCT block to generate a transformed DCT block. The transformation is an iteration procedure which comprises dequantization, Inverse Discrete Cosine Transform (IDCT), normalization, Discrete Cosine Transform (DCT), and quantization. This iteration procedure will enable the coefficients of the normalized DCT block to remain the same throughout the transformation;  
         [0026]     Step  109 : embedding original watermarks to LSBs of some of the transformed coefficients of the transformed DCT block determined by an authentication step with an authentication strength by performing a backward zigzag scan to generate a watermarked DCT block. The transformed coefficients embedded with watermarks are part of the coefficients generated from the NQAC coefficients detected in step  104 ;  
         [0027]     Step  110 : adjusting each coefficient of the watermarked DCT block according to a corresponding transformed coefficient and a corresponding normalized coefficient;  
         [0028]     Step  111 : detecting if a hamming distance between a watermark of an adjusted coefficient and a corresponding original watermark is within a predetermined value; if not, go to step  116 ;  
         [0029]     Step  113 : embedding a watermark into an LSB of an NQAC coefficient of the quantized DCT block according to the fast one-dimensional pseudorandom number;  
         [0030]     Step  114 : searching the quantized DCT block for the NQAC coefficient which contains a watermark;  
         [0031]     Step  115 : detecting if the LSB of the NQAC coefficient equals to 1; if not, go to step  116 ; and  
         [0032]     Step  116 : affirming the quantized DCT block is tampered.  
         [0033]     In Step  109 , the number of transformed coefficients of the transformed DCT block to be embedded with watermarks is determined according to the following formula: 
 
( NumNQAC −authentication strength)*authentication step  (1) 
 
         [0034]     wherein NumNQAC denotes the number of NQAC coefficients determined in step  104 ; an authentication step is a value between 0 and 1 and is specific to each transformed block; and the authentication strength is a reference number of transformed coefficients of a transformed DCT block to be embedded with watermarks. According to experiment results, the false positive, which is an incidental modification like the JPEG compression is a kind of “attack” that we would like to bypass of the color image. In other words, the degree of false positive of the color image will be decided by a reasonable trade-off choosing strategy of the authentication step; moreover, the larger authentication step results in higher quality of watermarked image. It&#39;s not suitable to embed obviously watermarks into the transformed coefficients in the higher frequency domain due to the effect of a quantization table of the JPEG lossy compression. However, while we embed watermarks into the transformed coefficients in the lower frequency domain, the watermarked coefficients will be easily changed due to the energy of image is more concentrated in the low frequency. Therefore, it is also not suitable to embed the watermark into the transformed coefficients in the low frequency domain. The probability of false positive can be calculated by the authentication step. For example, 8*8 blocks of source 352*288 image=1584 blocks since (352*288)/(8*8)=1584. If the authentication step is equal to “0.7” and the number of blocks of false positive in the image is 12, the probability of false positive will be calculated as (blocks of false positive)/(blocks of source image)=12/1584≈0.0075. According to our experimental results in the present embodiment, the probability of false positive will be almost zero when the value of the authentication step is under 0.5 and grow rapidly when the value of the authentication step is over 0.5, and the relationship between the probability of false positive and the authentication step will be illustrated and explained in  FIG. 2 . Therefore the optimal authentication step is “0.5” since it provides the best trade-off between the probability of false positive and the quality of watermarked image. In the present embodiment, we will reduce the false negative, which is the missed detection of tampered area in the tampered image, of image authentication by applying the authentication strength on the normal block. Regarding statistical experiments, we calculate the probability of false negative in the tampered image by the authentication strength. The probability becomes smaller with the rising of the authentication strength, and the relationship between the probability and the authentication strength will be illustrated and explained in  FIG. 3 . The value  6  of the authentication strength is applied for the proposed watermarking approach due to the best trade-off strategy, which is found in our experimental results of an embodiment of the present invention, between the probability of false negative and the quality of watermarked image. The backward zigzag order of scanning transformed coefficients of the transformed DCT block for generating a watermarked DCT block will be discussed in  FIG. 8 .  
         [0035]     In Step  110 , each coefficient of the watermarked DCT block is adjusted according to a corresponding coefficient and a corresponding coefficient of the watermarked DCT block. The formula of adjusting the coefficient, especially for the NQAC coefficient, of the watermarked DCT block, can be expressed as  
               NQAC   i   ′     =     {             sign   ⁢           ⁢     (     NQAC   i     )     *     NQAC   i       ,             if   ⁢           ⁢       Bit   0     ⁡     (          NQAC   i          )         =     w   i                   sign   ⁢           ⁢     (     NQAC   i     )     *     AF   ⁡     (     NQAC   i     )         ,             if   ⁢           ⁢       Bit   0     ⁡     (          NQAC   i          )         ≠     w   i                       (   2   )             
 
         [0036]     wherein an NQAC′ coefficient is the adjusted value of the NQAC coefficient of the adjusted DCT block, an NQAC′ i  coefficient is the value of the NQAC′ coefficient belonging to the i-th adjusted DCT block of the 8-by-8 adjusted DCT blocks, w i  is a watermark bit to be embedded into the i-th adjusted DCT block of the 8-by-8 adjusted DCT blocks, and AF is an adjustment function that adjusts the value of NQAC′ i . The 8-by-8 adjusted DCT blocks is assigned with various and unique serial numbers, which are in zigzag scan order of the adjusted DCT blocks, of between 0 and 63 so that the i-th adjusted DCT block of the 8-by-8 adjusted DCT blocks is the block with serial number i. The zigzag order of the 8-by-8 adjusted DCT blocks will be illustrated in  FIG. 8 .  
         [0037]     The value of sign (NQAC i ) is +1 or −1 and depends on the sign of NQAC i . The adjustment function AF has two features. The first feature, the NQAC i  “1” will be altered into “0” while w i  is “0”. This will generate an extracting fault of the embedded watermark bit due to the absence of the watermarked NQAC. The second feature is to transform the NQAC i  “2” or “−2” into “1” or “−1” while w i  is “1”. The definition of the adjustment function AF is as follows:  
               AF   ⁡     (     NQAC   i     )       ⇒     {               Bit   0     ⁡     (          NQAC   i          )       =     w   i                                   Bit   1     ⁡     (          NQAC   i          )       =       w   i     ⊕   1       ,             if   ⁢           ⁢          NQAC   i            =   1                     Bit   1     ⁡     (          NQAC   i          )       =       w   i     ⊕   1       ,             if   ⁢           ⁢          NQAC   i            =   2                     (   3   )             
 
         [0038]     wherein ⊕ denotes an XOR operation. For example, according to the results of the normal block watermarking, the NQAC i  “1” is “1”, “−2” is “−1”, “3” is “3”, “−4” is “−5” while w i  is “1”. The other NQAC i  “1” is “2”, “−2” is “−2”, “3” is “2”, “4” is “4” while w i  is “0”.  
         [0039]     Step  111  is performed for all of the watermarks of the adjusted DCT block in step  110 . When a hamming distance between a watermark of an adjusted coefficient and a corresponding original watermark is beyond the predetermined value, even if all other hamming distances are within the predetermined value for the same watermarked DCT block, step  116  will still affirm that the quantized DCT block is tampered.  
         [0040]     In Step  113 , a watermark is embedded into a Least Significant Bit (LSB) of a coefficient of the quantized DCT block. According to the characteristic of the few embedding capability in flat blocks, fewer watermarks are embedded into flat blocks than into normal blocks. Based on the robust of image authentication, we can find out the coefficients which can be safely embedded with watermarks by statistics. We count the existence probability of each NQAC coefficient by statistics for the flat blocks. Consequently, the absent positions of Quantized AC (QAC) coefficients, where the existence probability of NQAC is zero, are the safe watermarked points. Positions of the safe watermarked points with better quality are concentrated in middle-frequency region of the flat block according to frequency domain appearing in DCT of the JPEG lossy compression. We pick out four fixed watermarked points whose locations are (2, 6), (3,5), (5,3), and (6,1) in the 8-by-8 coefficient flat block and embed only one watermark bit into one of them, wherein the locations of the points in the northwest corner and the southeast corner of the 8-by-8 coefficient flat block are (1,1) and (8,8). To consider the security of image authentication, we use the fast one-dimensional pseudorandom number received in Step  100  to choose positions to be embedded by watermark bit “1”. We embed the watermark bit “1” into the LSB bit of the chosen i-th Quantized AC coefficient QAC i  in each flat block. The QAC i  will be altered to QAC i ′ as 
 
Bit 0 ( QAC   i ′)=Bit 0 ( QAC   i )⊕1, i=2*p k+1 +p k   (4) 
 
         [0041]     wherein the value of i is between 0 and 3, the value of k is between the value of 0 and length of the fast one-dimensional pseudorandom number p, p k  and p k+1  are the (k+1)-th and k-th bits of p, and the possible chosen locations of QAC i  in the 8-by-8 coefficient flat block can be represented as QAC i {0≦i≦3}={(2,6),(3,5),(5,3),(6,1)}. For the better trade-off between the robust of image authentication and the quality of watermarked image, we can replace the pseudorandom number p with the last bit Bit 0  and the first bit Bit 1  of the quantized DC coefficient in each flat blocks. We have three watermark bits comprising Bit 0 , Bit 1  of the pseudorandom number p and the embedded watermark bit to authenticate the tampered blocks in the flat blocks. It is very useful for the robust of image authentication and maintaining the quality of watermarked image.  
         [0042]     In Step  114 , the quantized DCT block is searched for the coefficient that contains a watermark. The previous fast one-dimensional pseudorandom number p in Step  113  is used to find out the watermarked coefficient by extracting the (k+1)th bit p k+1  and the kth bit p k  of the pseudorandom number p.  
         [0043]     In Step  116 , the quantized DCT block is considered as a tampered block, and the blocks which are not tampered are authenticated blocks.  
         [0044]     Please refer to  FIG. 2 , which is a diagram for the probability of false positive vs. authentication steps in the normal blocks. According to  FIG. 2 , the probability of false positive will be almost zero when the value of the authentication step is under 0.5 and grow rapidly when the value of the authentication step is over 0.5. A higher probability of false positive corresponds to a lower quality of watermarked image. And a higher authentication step corresponds to a higher quality of watermarked image. Therefore the optimal choice for the authentication step is “0.5” since it has the highest authentication step for all near zero probability of false positive.  
         [0045]     Please refer to  FIG. 3 , which is a diagram for the probability of false negative in the tampered image vs. authentication strengths in the normal blocks. According to  FIG. 3 , the probability becomes smaller with the rising of the authentication strength. A higher probability of false negative corresponds to a lower quality of watermarked image. And a lower authentication strength corresponds to a higher quality of watermarked image. Therefore the optimal choice for the authentication strength is “6” since it has the lowest authentication strength for all near zero probability of false negative.  
         [0046]     Please refer to  FIG. 4 , which is a diagram of an 8-by-8 non-overlapping block (corresponding to step  101 ). Each coefficient corresponds to the luminance of a corresponding pixel.  
         [0047]     Please refer to  FIG. 5 , which is a diagram of a transformed DCT block generated from  FIG. 4  (corresponding to step  108 ). When the authentication step equals 0.5, the chosen NQAC coefficients are {−2, −2, 4, 21, −6, 7}.  
         [0048]     Please refer to  FIG. 6 , which is a diagram of a watermarked DCT block generated from  FIG. 5  (corresponding to step  109 ). After watermarking the transformed DCT block, the NQAC coefficients become {−1, −2, 5, 20, −7, 6}.  
         [0049]     Please refer to  FIG. 7 , which is a diagram of an adjusted DCT block generated from  FIG. 6  (corresponding to step  110 ). As shown in  FIGS. 4 and 7 , the adjusted coefficients in  FIG. 7  are very close to the coefficients in  FIG. 4 . If the adjusted DCT block is determined as not tampered, the adjusted DCT block will be received as the restored non-overlapping block.  
         [0050]     Please refer to  FIG. 8 , which illustrates a zigzag sequence of the 8-by-8 transformed DCT blocks. All of the coefficients of the transformed DCT block are assigned with serial numbers between 0 and 63. The coefficients with serial numbers 10, 11, 12, 13, 14, 16 are selected for watermarking by performing a backward zigzag scan. In  FIG. 8 , watermarks can only be embedded into the coefficients in the left-upper portion because that portion is not of high frequencies.  
         [0051]     It is an advantage of the present invention that semi-fragile watermarking has excellent strength and sensitivity against tampering of image data, therefore semi-fragile watermarking is able to measure the degree of tampering of image data and distinguish malicious tampering of image data from legal image attacks.  
         [0052]     Therefore, the present invention can detect whether the image is tampered maliciously or tampered by image compression. The present invention can also decrease the probability of misjudging illegal tampering (i.e. false positive) and authentication (i.e. false negative).