Lidu

Background

With the development of digital image processing in recent years， numerous image editing techniques have been developed so that realistic synthetic images can be produced conveniently without leaving noticeable visual artifacts. Although these image editing technologies can enrich the user experience, they also cause the problem for people to trust the authenticity of the images. JPEG is the most popular image format for cameras, and the modification of JPEG images may be re-saved to generate a new image, which would cause the double compression of the image. This project focuses on the detection of double compression and single compression to verify the authenticity of the image.

Introduction

JPEG Principle

JPEG (Joint Photographic Experts Group) is one of the most widely used standards for compressing image data. It is a lossy compression scheme. The procedure of the JPEG compression is like follows:

1. Given a three channel color image (RGB), convert it to YCbCr (luminance/chrominance) space.
2. The two chrominance channels (CbCr) are subsampled by a factor of two relative to the luminance channel (Y).
3. Each channel is divided into many 8*8 blocks, and all unsigned integers (range from 0 to 255) are converted to signed integers (range from -128 to 127).
4. DCT (Discrete Cosine Transform) is applied to each block in each channel, the lowest frequency resides in the upper-left corner, and the highest frequency resides in the lower-right corner of each block.The same position in each block is called a mode. The mode table is shown below.
5. For a pre-defined quantization table (also of the size 8*8), each DCT coefficient is quantized by the corresponding the step in the quantization table, and then rounded to the nearest integer. Usually, the steps for low frequencies are small and steps for high frequencies are big, so the high frequency can be removed without much effect on human vision.
6. Encode the quantized coefficients in zig-zag order and the compression is completed.

Table 1

Table 1

Double JPEG Compression

Double Compression can be regarded as a compression of a compressed image. For a compressed image, inverse quantization and inverse DCT are applied to decompress. After rounding all the values to integers, JPEG compression procedure is applied again, usually with different quantization steps. The flow of double compression of one channel is shown below.

Figure 2

Method

AC Coefficients Histogram

Usually, in the process of double compression, the two quantization steps are different, which may cause a different histogram distribution in doubly compressed images. Some people did research on the distribution of AC coefficients, and found that the distributions satisfy a Laplacian distribution, which is centered at 0, and decreases in each side. Furthermore, the distribution of the difference of nearby values also satisfy a Laplacian distribution. So this method applies this pattern to detect double compression.Since the upperleft coefficients contains the information of low frequencies, they are more sensitive to high frequencies, I choose the first 20 modes in zig-zag order, and draw the histogram of values from 2 to 10 in these modes. Here are two examples, the left one is the histogram of a singly compressed image with quality factor 80, and right one is of a doubly compressed image with quality 65 and 95 separately.

From the two histograms, we can see that the difference is obvious. By calculating the ratio of negative values in the histogram, it is easy to distinguish singly compressed image and doubly compressed image with Q1 < Q2.

First Digit Histogram

This method is based on Benford's Law. Benford's Law is also known as first digit law and is an empirical law. It was first discovered by Newcomb in 1881 and rediscovered by Benford in 1938. This law states that the probability distribution of the first digit, x (x = 1, 2, 3, ..., 9), in a set of natural numbers is logarithmic. To be specific, the distribution can be written as

math 1

Some researches were conducted on applying Benford's Law to image processing, and it was found that the distribution of the most significant digit(first digit) of the block DCT coefficients follows Benford's Law quite well and the quantized coefficients follow a Benford-like logarithmic law when the image is compressed once in JPEG format. The following two histograms verify this. They are the distributions of first digit in the first nine mode for an image compressed with quality factor 80 and an image doubly compressed with quality factor 65 and 95.

hist 1

hist 2

From the two histograms, we can see that the Benford's Law can be applied to detect doubly compressed image by testing the distribution of the first digits.

Factor Histogram

This method is based on a series of mathematical derivations. Suppose for a doubly compressed image, the quantization steps are q1 and q2 separately, and the quantized coefficients are c1 and c2 separately. According to the procedure of double compression, we have the formula (1). The term e stands for the rounding or truncation error. In order to get a relationship for q1, q2, c1 and c2, we can ignore e here. It is obvious that formula (2) and (3) can be obtained from (1).