How fast is the linear chain trick? A rigorous analysis in the context of behavioral epidemiology

1.   Introduction

It is a significant task to identify the authenticity of an image in several scenarios, such as the media industry, digital image forensics and academic appraisal. It is important to know if an image was tampered because people need to ensure if a certain image can serve as effective evidence for a case or a real result of an experiment. There are different kinds of tampering processing including but not limited to copy-paste, blurring and scale transformation. We want to make a fast and reliable preliminary judgment on tampering. And the widely used JPEG compression algorithm gives us a good chance, we can design an algorithm based on it to achieve our goal. Identification of JPEG compression history has received more and more attention in recent years. When an image is saved in bitmap format but has been compressed by JPEG method, we can not access to the jpg file header which contains the information about compression but we still need to know its compression history sometimes.

Among all of the lossy compression algorithms, JPEG (Joint Photographic Experts Group) is one of the most popular and widely used standards. Almost all software provide JPEG compression operations choice when saving digital images. Sometimes images have been compressed by the JPEG method are saved into bitmaps. And we can not get the information whether images have been compressed from images files themselves directly because we do not have any access to the JPEG file headers after it has been saved as bitmaps.

However, this information may be crucial in some cases, in the field of digital image forensics for instance. If the JPEG compression history is efficiently exposed, we can make a preliminary judgment that the image may have been tampered. That is why we need to detect the compression history. Thus, methods for detecting the compression history of bitmaps has become an important issue and received widespread attention.

Many efforts have been attempted in this aspect, and many decent results have been achieved. Most of these works are related to JPEG coefficient, JPEG quantization table, DCT transformation and wavelet transformation. Based on these, different approaches were proposed.

Thanh et al. ^[1] has proposed a method based on the combination of the quantization effect and the statistics of discrete cosine transform coefficient characterized by the statistical model. Hernandez et al. ^[2] has proposed a method which can avoid giving false results. When their method can not get the quantization table, it means this bitmap may not be compressed or it is not compressed by the JPEG algorithm. These methods have shown some characters of JPEG coefficients which are very meaningful for further works in this aspect.

And there are some JPEG history detection methods which do not need to estimate the quantization table. Fan et al. ^[3] proposed a detection method based on the feature of block antifacts in the pixel domain, as the pixel values between the blocks should be inherent if an image was compressed before comparing with uncompressed images. But Fan's method ^[3] has a relatively high computational complexity. Yang et al. ^[4] used factor histogram to detect the JPEG compression history of bitmaps, because the decreasing values in factor histogram are observed with the increase of its bin index for uncompressed bitmaps, while no obvious decrease is found in uncompressed images. But Yang's method ^[4] gets a sudden drop in the accuracy when the compression quality factor is high because the block antifacts phenomenon is not obvious under such circumstances. Especially when the quality factor is 98 or higher the accuracy can go below 50%. Zhang et al. ^[5] found the tetrolet transformation proposed by Krommweh et al. ^[6] can be used to exploit the structure of images. Tetrolet transformation is a kind of Harr wavelet transformation which uses at most 177 different kinds of tetrolet as components to disassemble images. The authors proposed a detection method based on the tetrolet transformation to distinguish the uncompressed bitmap image from the decoded JPEG image. As far as we know, Zhang's method ^[5] has the highest accuracy until now.

Because JPEG compression algorithm is a kind of lossy compression, the compressed image will lose some kind of information after the compression. Proposed in ^[7], the number of zeros of the JPEG coefficient is a major factor affecting the compression quality of JPEG. For the same bitmap image, the image quality will continue to improve with the increase of JPEG compression quality factor, while the percentage of zeros of the 64 JPEG coefficients will decrease. And we present a method based on this observation.

In this paper, we propose a fast, and reliable method to detect the compression history of bitmaps based on image information loss. Our method is faster than most existing similar methods because we do not need to compress the test image in the processing. A lot of methods proposed contain the compression step because they need a comparison version for obtaining the results. Instead of making a compressed image with quality factor 100 in ^[5], we obtain an estimated original image which is firstly created based on the test image. This processing costs much less time than compression. Extensive experimental results have been achieved which demonstrate that our proposed method outperforms the state of art respect to the detection accuracy and computational complexity. And the accuracy of our method is relatively high, especially when the quality factor of the test images are below 97. Even when the quality factors are as high as 98 and 99, our method still gives acceptable results. What is more, the proposed method can be generally used no matter the test image uses standard or non-standard JPEG quantization table during the compression which means as long as the image was compressed by JPEG method our detection is effective.

The remaining of the paper is organized as follows. In Section 2, we introduce the relationship of the JPEG coefficients and the image information loss caused by JPEG compression. And the method to create the estimated original image is also described. The framework and the details of the algorithm are stated in Section 3. In Section 4, the experimental results are shown and discussed. And conclusions will be drawn in section 5.

2.   Theories about information loss and original images estimation

In this paper, the quality factor Q is an important factor that determines the quality of the JPEG image, and the DCT coefficient after quantization is called the JPEG coefficient, which can be read directly from the JPEG image file. The number of zero of the JPEG coefficient is a major factor affecting the compression quality of JPEG images. Through extensive experiments, we find that the proportion of zero JPEG coefficients on the 64 DCT positions show downward trends as the image compression quality factor increase. In other words, for the same bitmap image, the higher the compression quality is, the less the image information loss is and the lower the percentage of zero among 64 JPEG coefficients is. So, the percentage of zero JPEG coefficients on different frequencies can be defined as the index of the amount of information loss after bitmaps were compressed by the JPEG method.

When an image is compressed by JPEG, it will firstly be separated into several 8 $\times$ 8 blocks. Then each block is operated by DCT respectively. For each block, there are 64 positions. The first step of our method is doing statistics on the number of zero on 64 positions among all blocks. Note n(j) as the total number of zeros on jth position and m is the number of blocks. Then the amount of image information loss on the 64 DCT positions can be expressed as:

and the average image information loss is expressed as:

Figure 1 illustrates the result of the average information loss of a bitmap after compressed into JPEG images with the quality factor varying from 60 to 100. The average image information loss decreases as the growth of quality factor Q.

Figure 1.  The curve of average information loss with the increase of quality factor Q.

DownLoad: Full-Size Img PowerPoint

Respecting to this observation, we obtain JPEG images from an uncompressed image $I_{bmp}$ with different quality factors. And then the JPEG images are decoded to decompressed bitmap images. The uncompressed image and the decompressed images are JPEG compressed with the quality factor 100 to obtain $I_{JPEG1}$ and $I_{JPEG2}$ respectively. Obviously, the $I_{JPEG1}$ is a single JPEG compressed image and $I_{JPEG2}$ undergoes double JPEG compression. We can compare the amount of image information loss between $I_{JPEG1}$ and $I_{JPEG2}$ to achieve the goal of making a primary judge on compression. The higher difference between $I_{JPEG1}$ and $I_{JPEG2}$ means higher information loss.

But please notice that in the example there is an assumption that we have the original lossless image and then compress it. And we make the judgement according to the contrast. But in the real case, the original lossless image is usually unacquirable. Therefore, we have to estimate the original image first.

As proposed in ^[8,9], the image will be separated into blocks, when it undergoes JPEG compression. Then these blocks are operated separately. And to shrink the file size we tolerant some information loss during the quantization. Certain frequency signals are abandoned in quantization step especially for those high-frequency harmonics which only causes very little even no change for the human visual system (HVS). These signals mean redundancy to the human visual system, while they contain a lot of information. That is why they are important to the detection of compression. The image which has not been compressed or just been compressed with relatively high-quality factors remains more information which is a series of signals having different frequencies. Normally, a compressed image has lost a considerable amount of harmonics. Most high-frequency components are set to zero and some low-frequency components are also set to zero if they are small enough. It is true that we can not get what has been abandoned in the previous processing again because of the lossy JPEG compression. But it is still possible to estimate that information existing in the original image of the test image. During the JPEG compression, DCT and quantization are used on each block but not on the full image, which has been discussed in ^[10]. So, even those harmonics are lost in each separated 8 $\times$ 8 blocks but they are still existing among the full-size image. If we want to expose this information, we need to break the existing block artifacts. A method of cutting 4 rows and 4 columns of the test image widely used in image steganalysis ^[11] is employed to estimate the counterpart of the original image.

The removal of left-top 4 rows and columns has been approved as an excellent way to estimate the counterpart of the original image from compression, which means similar statistic features, as the cut destroys the block-based structure of JPEG. The row and column cutting are illustrated in Figure 2.

Figure 2.  Original image estimation.

DownLoad: Full-Size Img PowerPoint

3.   The compression detection method

3.1.   The framework of algorithm based on information loss

Based on the image information loss, we propose a novel algorithm to detect the JPEG compression history as Figure 3 illustrated. The idea of extracting feature from the JPEG file is based on ^[12].

Figure 3.  The framework of algorithm based on image information loss.

DownLoad: Full-Size Img PowerPoint

The whole processing is as following:

ⅰ. To obtain $I_{JPEG1}$, the test bitmap image is JPEG compressed with quality factor Q = 100.

ⅱ. The counterpart of the original image is estimated by cutting 4 rows and 4 columns from the test image. The $I_{JPEG2}$ is acquired by compressing the counterpart with quality factor Q = 100 as well.

ⅲ. The features related to the image information loss are extracted from the two JPEG images, and then fed into the classifier to detect whether the test bitmap image has been compressed.

3.2.   Feature extraction

Considering the test image as a decomposed JPEG image, as Figure 4 illustrated. $I_{JPEG1}$ actually undergoes double JPEG compression with an unknown previous quality factor and the latter quality factor of 100. And because of the counterpart estimated by cutting rows and columns, the $I_{JPEG2}$ could be considered as a single JPEG compressed image with the quality factor of 100. For the percentage of zero of JPEG coefficients among the 64 DCT positions are defined as the indexes of the amount of information loss after the bitmap image is JPEG compressed, there are disparities between the corresponding indexes $I_{JPEG1}$ of $I_{JPEG2}$ and on the 64 DCT positions, as shown in Figure 5. A higher information loss is expected for a JPEG compressed test image. On the contrary, if the test image is uncompressed, there should be no obvious differences between indexes on corresponding positions, as shown in Figure 6.

Figure 4.  The original decompressed image.

DownLoad: Full-Size Img PowerPoint

Figure 5.  The comparison of testing image and estimated original image in the case that the test image is decompressed from the JPEG image with quality factor Q = 90.

DownLoad: Full-Size Img PowerPoint

Figure 6.  The comparison of testing image and estimated original image in the case that the test image is uncompressed.

DownLoad: Full-Size Img PowerPoint

$p_1(j)$ denotes the indexes of the image information loss of $I_{JPEG1}$. $p_2(j)$ denotes the indexes of the image information loss of $I_{JPEG2}$. Then we describe the difference of information loss as

$p_{dif\_average}$ indicates how much details are found in the estimation counterpart comparing with the test image. If the testing image is uncompressed, the value of $p_{dif\_average}$ will be close to 1 which means there is no obvious difference between the test image and the estimation original image. If the test image was compressed, this value will be much greater than 1 which means the bias is observed between the $I_{JPEG1}$ and $I_{JPEG2}$ after breaking the 8 $\times$ 8 blocks in the test image by cutting. After extracting this feature of images, an SVM classifier is trained. And then we can detect the bitmap JPEG compression history with this model.

4.   Experiments

Two image databases are used in our experiments to evaluate the performance of the proposed method. Firstly, 1338 uncompressed images from the UCID image database are used in our experiments. These images are saved in Tif format with the resolution of 512 $\times$ 384. And a series of standard JPEG quality factors (60, 70, 75, 80, 85, 90, 95, 96, 97, 98, 99) are applied to the images to obtain JPEG compression images of different qualities. The JPEG images with different quality are resaved in Tif format for evaluating the proposed algorithm. In the following, this image dataset is named as dataset1.

The other 480 images come from the well-known Dresden database. Different from the UCID database, the images from the Dresden database are captured by consumer cameras and saved as JPEG image originally. In our experiments, we use 480 JPEG images from 4 different cameras, which are Agfa DC-830i, Canon PowerShotA640, Nikon D200 and Sony DSC-W170, 120 images from each camera. Different from the JPEG images obtained in dataset1, these images are compressed with different consumer-defined JPEG quantization tables with various camera models. Also, the images, named as dataset2 with the resolution of 3872 $\times$ 2592, are resaved as bitmap images for the experiments.

We take 500 uncompressed images and 11 $\times$ 500 decompressed JPEG images from dataset1as the labeled samples to train the SVM classifier with RBF kernel. After we get the model we use it to test the rest images with different quality factors (60, 70, 75, 80, 85, 90, 95, 96, 97, 98, 99). We also compare our proposed method with Yang's ^[4], Fan's ^[3] and Zhang's ^[5] methods in terms of detection accuracy and algorithm complexity respectively. The results are shown in Table 1 to Table 3.

Table 1.  Identification accuracy (%) of the proposed method and baselines for dataset1.

Methods	Q										original
	60	70	80	85	90	95	96	97	98	99
Fan's	97.10	96.68	96.00	95.14	89.78	69.14	59.80	48.33	25.53	17.27	84.10
Yang's	99.90	100	100	100	99.80	98.69	96.58	88.74	78.16	39.79	96.59
Zhang's	100	100	100	100	100	100	100	99.93	99.10	95.65	99.88
Proposed	100	100	100	100	100	100	99.93	99.48	99.03	89.31	99.92

---

 | Show Table

DownLoad: CSV

Table 2.  Identification accuracy (%) of the proposed method and the baseline for images in dataset2.

Method	Accuracy(%)
Zhangs	34.08
Proposed	100

---

 | Show Table

DownLoad: CSV

Table 3.  Average time cost.

Method	Time cost(s) (image with resolution of 384 $\times$ 512)
Fans	2.73
Yangs	0.91
Zhangs	9.64
Proposed	0.60

---

 | Show Table

DownLoad: CSV

As shown in Table 1, Fan's method can give relatively good results when the quality factor is less than 85. The detection accuracy goes below 90% when the quality factors are greater than 90. Yang's method has a similar shortcoming. It performs well when the quality is 96 but the accuracy goes below 90% when the quality factors are greater. Zhang's method has a really good result. The detection accuracy is 95.65% when the quality factor is as high as 99. Our method outperforms Fan's and Yang's methods. And similar detection results are observed between Zhang's and the proposed method. While Zhang's method works better when the quality factor is 99, our method can give results in the shortest time, as shown in Table 3. Also, it can be proved that average cost time for each pixel is stable by simple computation. Time cost may be not the most important index in this aspect. But we can get reliable results within less time indeed. This may have a great advantage in some cases.

Another comparison experiment is implemented between the proposed and Zhang's methods ^[5]. We take 480 compressed images from dataset2 to prove that our method can work on all JPEG compressed images. All of these bitmap images are not compressed using standard JPEG quantization but took by cameras which means they were compressed using customer-defined JPEG quantization tables. The results are shown in Table 2. Zhang's method is found only effective to images compressed using the standard JPEG quantization tables. And the proposed method still performs well.

5.   Conclusion

The issue of detecting the compression history of images receives more and more attention in recent years. In this paper, we propose a novel and fast detecting method based on novel feature respect to image information loss. According to this, the proportion of zero JPEG coefficients on 64 DCT positions falls down as well. We estimate the image counterpart by cutting 4 rows and 4 columns from the original image and calculate the differences between the values of the 64 DCT positions respectively. The feature extracted from the differences is fed into the SVM to train a mode to classify the test bitmap images. Extensive experiments and the results demonstrate that our proposed method outperforms the state of art, especially in the cases of high compression quality factors and customer-defined quality factors. And also the proposed algorithm indicates a lower computational complexity compared to the previous works.

Acknowledgments

This work is supported by the National Science Foundation of China (No. 61502076, No. 61772111).

Conflict of interest

All authors declare no conflicts of interest in this paper.