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.

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 _______), 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 9 : 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.

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.

References

References

Software

Appendix I - Code and Data

Code

File:CodeFile.zip

Data

zip file with my data