BoinJou

Back to Psych 221 Projects 2013

Introduction

Motivation Goal

Background

CFA Interpolation

A color filter array is an array of color filters placed on top of a camera sensor to capture color information which can then be interpolated to produce color information for neighboring pixels. Different cameras can have different patterns for this CFA color sampling. The most common pattern used is the Bayer pattern.

In Camera Forensics, often, the periodicity of the Color Filter Array is exploited to detect possible tampering in images. But, often when given an image, we don’t know the sampling lattice, and also we don’t know how the interpolation was done. We can use the Expectation-Maximization (EM) algorithm to estimate both of these.

Expectation/Maximization Algorithm

We assume that each pixel (sample) in an image belongs to one of two models: either the pixel was interpolated with weights ($\alpha$) by neighboring pixels (model $M_1$), or the pixel was indeed "sampled" during the image formation process (model $M_2$). The EM algorithm is a two-step iterative algorithm that we can use to estimate the probability of each pixel being physically sampled (Estimation step), and also to estimate the specific interpolation coefficients for the pixels that were not (Maximization step).

Here, f(x,y) is the CFA image of one color channel. If the pixel is produced from interpolation by its neighborhood of N, we can denote f(x,y) by:

$f(x,y)=\sum _{u,v=-N}^N{\alpha }_{u,v}f(x+u,y+v)+n(x,y)$

where ${\alpha }_{u,v}$ are the interpolation coefficients and n(x,y) is the residual error of a Gaussian distribution with zero mean. The probability of observing a sample f(x,y) given that it was generated from model $M_1$ is given by the equation, which is estimated in the E-step:

$Pr\{f(x,y)|f(x,y)\in M_1\}=\frac{1}{\sigma \sqrt{2\pi }}exp[-\frac{1}{2{\sigma }^2}{(f(x,y)-\sum _{u,v=-N}^N{\alpha }_{u,v}f(x+u,y+v))}^2]$

The variance, σ2, of this Gaussian distribution is estimated in the M-step. In the E-step, the initial $\overrightarrow{\alpha }$ is randomly chosen. In the M-step, a new estimate of $\overrightarrow{\alpha }$ is computed by minimizing this equation:

$E(\overrightarrow{\alpha })=\sum _{x,y}w(x,y){(f(x,y)-\sum _{u,v=-N}^N{\alpha }_{u,v}f(x+u,y+v))}^2$

where $w(x,y)\equiv Pr\{f(x,y)\in M_1|f(x,y)\}$

The two steps are executed iteratively until ...

Methods

Here is a brief outline of our algorithm.

We use a sliding window of size 64x64 to traverse the image with 32 pixel increments. We run the EM algorithm on every block. Then we have a clustering step to localize tampered region using the EM outputs. Finally, we use the cluster maps to classify our image as real or fake.

Localization: Clustering

After running EM on a block, we get two set of useful outputs. First of all, we get a probability map showing which pixels were sampled and which were not, which we take a Fourier Transform of. We also get the estimated alpha values which describe the interpolation weights of neighboring pixels. There is useful information in both of these outputs at different degrees for different images. Our algorithm uses both set of data.

Fourier Transform data

File:Fft min flat.png File:Fft min.png

Alpha vectors

File:Alphas flat.png File:Alphas.png

Clustering Algorithm

27-dim vector per block
2-cluster k-means, but force one cluster to be smaller than the other
initialization of cluster centroids: - -
cost function:
- force one cluster to be smaller than the other
- different weight sequences between FFT peaks portion and alphas portion of the 27-dim vector in cost function.

Classification

For a given image, we generate 5 different maps for the blocks, each of those corresponding to the relative importance we give to the data from the peaks and the data from the components of alpha. Ideally, for a tampered image the clusters would perfectly subdivide the blocks in two categories: the ones tampered and the ones not. For a real image, there would not be a clear distinction between these clusters and the blocks of a cluster would not be as localized.

In practice, there can be noise even on tampered images (blocks out of the tampered zone that are considered as fake as we can see in figure 7) so our goal for this part is to draw a clear line between typical maps of tampered images or of untampered images.

Figure 7: Example of not ideal map. Although the tampered region is clearly identifiable, there are still some blocks out of it that are considered as fake.

Because of the assumptions we stated above, we can expect that on a map corresponding to a fake image there should be a group of fake blocks of moderate size, so we can use as a heuristic the number of pixels in each connected component on this image, noticing that:

• A very small one very likely corresponds to noise (figure 8)
• A big one that is greater than a certain portion of the total number of blocks is unlikely to be a tampered region (figure 9)
• A connected component of moderate size surrounded by a lot of noise is unlikely to be a tampered region (figure 10)

Figure 8: Example of an untampered image block map containing many small connected components

Figure 9: Example of an untampered image block map containing one big connected components that is not a tampered region

Figure 10: Example of an untampered image block map containing one connected component of a moderate size, but which is still not a tampered region because of the noise around.

For each of these criteria, we can associate a quantitative threshold that would allow us to do the classification. These thresholds are parameters that we can modify in order to achieve the best performances, performances that we could judge by using our algorithm on the 140 test images that we were given (70 tampered, 70 untampered). By trying different sets of parameters, we realized that we could either have a higher rate of false positives (untampered images classified as fake) or a higher rate of false negatives (tampered images classified as real). When we plot each of these on a 2-dimensional plan corresponding to the proportion of false positives and the proportion of false negatives, we can highlight some sets of parameters that are better than the others: they are situated on a Pareto optimality curve (figure 11).

Figure 11:Pareto optimality curve between the proportion of false positives and the proportion of false negatives.

The two main points of interest are the ones in red: they (and all the points on the line between them) minimize the sum of these two proportions. Depending on our goal, it made more sense to use one or the other. In our tests, we actually used the red point one on the right, which achieved the following performances on our training images:

• 4.29 % of false positives
• 28.57 % of false negatives

In real life, we judged that it made more sense to minimize the false positives if we want to prove an image is tampered. If our test turns out positive, then we have a rather good certainty that the image is tapered. If the test turns out negative, we cannot say anything for sure. NB : It is important to note that we did not use as an assumption the fact that the tampered zone is a rectangle, although it is the case for training and test images. It would have made our work much easier but unlike the other assumptions we made, this one was totally unjustified in the case of a really tampered picture, so we did not limit ourselves to detecting rectangular tamperings.

Results on actual test images

We ran our test on the 20 test images that were given to us. Here are the results of their processing through our algorithm, as well as an analysis of these results.

Uncompressed / not resized images (12 images)

These are the images we trained our classifier on, so it is where we expect to achieve good results.

• 4 tampered images were detected out of 6, with the right tampered zone. This gives a proportion of 33% of false negatives (to compare with the 28.57% we had on our training images)
• 6 untampered images were detected out of 6. This gives a proportion of 0% of false negatives (to compare with the 4.29% we had on our training images)

Of course, it is not very accurate to make statistics on such a small set of data, but we can see that the results we get are what we expected with the training images. We can also notice that the 2 tampered images that we did not detect as such have either a small tampered zone (69x69 pixels, which is the order of magnitude of the smallest zone we can detect) or have a very large uniform zone (black bands on the sides of the image). It can be understood that our algorithm does not perform well on these images, since they violate the assumptions we made for the working images of our algorithm.

JPEG compressed images (6 images)

For these images, we detected correctly:

• 0 tampered images out of 3
• 3 untampered images out of 3

There are two reasons of this result. In fact, our classifier does not perform well even on most of the high quality JPEG images partly because we did not train it on JPEG images. Indeed, these images would introduce a lot of additional noise on our block maps (cf figure 11), and then it will classify tampered images as untampered because there is too much surrounding noise. However, if we trained our classifier in the same way we did, but using JPEG lightly compressed images, it would be able to take into account this surrounding noise. So, in this case, the part that broke in our pipeline is the interpretation of the map, not its synthesis. But if we look at it, we can visually see where the tampered zone is. This means that it is possible to improve our classifier with minimal work so that it could work on lightly compressed JPEG images. We did not do it here because we wanted to see how the same algorithm would work on different kinds of images.

Figure 11 : Map in the case of a lightly compressed image. We can see that the amount of noise is much higher than in the uncompressed case. However, our algorithm still worked properly because we can identify that the fake zone is on the upper left corner.

For more heavily compressed images, we do not expect the EM and clustering part to work because the correlations between pixels and their neighbors will be destroyed.

Resized images (2 images)

For these images, we detected correctly:

• 0 tampered image out of 1
• 1 untampered image out of 1

These images are out of the scope of our classifier: we based partly our analysis on the peaks of the Fourier transform, which occur in the case of a Bayer pattern. If the image is resized or rotated, the “peaks” data are useless, and classifying the image properly becomes almost impossible.

Conclusions

We made a classifier that could work on images that verify a few assumptions. We also showed that it worked well if the images verify these constraints: we could detect tampered images and even show exactly where they were tampered. Some constraints are not such a problem. For example, we could also adapt it easily for high quality JPEG images, although we would need to use a different version of our algorithm (with modified parameters). But some constraints are more limiting, and are linked to the nature of our algorithm. Thus, it is for instance very difficult to notice a tampered zone of very small size, and it is probably impossible to be able to detect arbitrary small tampered zones. But getting a perfect classification with a camera forensic method is an illusion, and this method can be used with others in order to have a better way of detecting tampered parts of it.

References

References

Software

Appendix I - Code and Data

Code

File:CodeFile.zip

Data

zip file with my data