BoinJou

Back to Psych 221 Projects 2013

Introduction

Motivation

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

Results

Localization: Clustering

Some text. Some analysis. Some figures.

Classification

Some text. Some analysis. Some figures.

References

References

Software

Appendix I - Code and Data

Code

File:CodeFile.zip

Data

zip file with my data