LamTangYu

Back to Psych 221 Projects 2013

Introduction

The purpose of the camera forensics project is to automatically detect whether an image, that was produced by CFA interpolation, was tampered with. CFA interpolation is used by digital camera to generate digital images. The interpolation will result in specific statistical patterns in the pixels of an image, which and then be utilized to determined whether or not an image has been altered.

Background

What is CFA Interpolation?

When digital cameras capture images, it saves the output of a single sensor after passing through a color filter array (CFA). Every single pixel of a color image is composed of three color channels, red, green, and blue. However, the camera is only able to sample a single color channel per pixel, so to fully form a colored image, the values of the other two colors will have to be estimated. Various interpolation techniques are used to estimate the missing samples.

Different Types of CFA Interpolation Techniques

Figure 1. The Bayer Array

A common CFA is the Bayer Array. Colors are sampled according to the pattern in Fig. 1. As shown, the green color channel is sampled at twice the rate of the red and blue channels. All of the interpolation methods below assume that the image was captured through a Bayer Array.
Let $\tilde{R}(x,y)$, $\tilde{G}(x,y)$, and $\tilde{B}(x,y)$ represent the CFA sampled versions of the three color channels.

Bilinear/Bicubic

Bilinear and bicubic are the simplest interpolation algorithms. Each color channel is interpolated independently by using a 2D linear filter $h(x,y)$ on $\tilde{R}(x,y)$, $\tilde{G}(x,y)$, and $\tilde{B}(x,y)$.
$R(x,y)=\tilde{R}(x,y)$ for $x,y$ such that $\tilde{R}(x,y)\ne 0$. Otherwise, $R(x,y)=h*\tilde{R}(x,y)$. The same is done for the green and blue channels. For bilinear interpolation, a 3 by 3 filter is used and for bicubic interpolation, a 7 by 7 filter is used.

Smooth Hue Transition

One downfall of bilinear/bicubic interpolation is that neighboring pixels may differ significantly in value, which is unlikely in natural images.
Since there are twice as many green samples as red and blue, the missing samples in the green color channel are first bilinearly interpolated as described above. After interpolating the green channel, the red and blue channels can be estimated by bilinearly interpolating the ratio $\tilde{R}(x,y)/G(x,y)$ and $\tilde{B}(x,y)/G(x,y)$ respectively.

Median Filter

$\tilde{R}(x,y)$, $\tilde{G}(x,y)$, and $\tilde{B}(x,y)$ are first interpolated. Then $M_{rg}(x,y)$, $M_{rb}(x,y)$, and $M_{gb}(x,y)$ are computed by taking pairwise differences of the interpolated color channels and filtering with a median filter.
At each pixel, only one color channel was originally sampled. To obtain the estimates for the other two channels, we look at the sum or difference between the original color sample and the corresponding median filtered point. For example, if at pixel $(x,y)$, the green channel was sampled with a value of $g_{x,y}$. Then we can estimate the red channel by $R(x,y)=g_{x,y}+M_{rg}(x,y)$ and the blue channel by $B(x,y)=g_{x,y}-M_{gb}(x,y)$. The missing values are estimated similarly for pixels where the red or blue channel was sampled.

Gradient Based

This method attempts to preserve edges by preventing interpolation across edges. First, the horizontal and vertical derivates estimates for each pixel is computed and used in conjunction with the green color channel samples to estimate $G(x,y)$ by adaptively interpolating. Then the red color channel is then estimated by bilinearly interpolating the difference between red color channel samples and the green color channel estimates. The same can be done to estimate the blue color channel.

Adaptive Color Plane

The adaptive color plane is a modification of the gradient based interpolation method. It uses information from both the first and second derivatives.

Threshold-Based Variable Number of Gradients

The gradient estimates are calculated in eight different directions (N,E, S, W, NE, NW, SE, SW). Depending on whether the gradient value is above or below a threshold, the missing color samples are estimated based on a linear combination of its neighboring values given by equations described here.

Methods

EM Algorithm

Since all digital images are CFA interpolated, neighboring pixels are highly correlated.

Probability Map and Its Fourier Transform

From the EM algorithm, we can compute the probability map of each block of the image. Taking the Fourier transform of the probability map, we can more easily visualize any periodicities in the probability map. CFA interpolated images that have not gone through tampering will have visible peaks in the Fourier transform of the probability map, result of the correlation between pixels.

Thresholding for Determining Fake Images

After computing the probability map for each block over the image, we compute the cosine similarity between the fourier transform of the probability map and the fourier transform of the synthetic probability map. We do this for each of the three color channels.

Before we apply thresholding, we try to normalize the data by using two different normalization techniques:

1. Normalize by the max similarity value in each block.
2. Normalize by the mean similarity value in each block.

After acquiring the normalized similarity values, the threshold for each channel is determined empirically by iterating over different combinations of $thres{h}_r$, $thres{h}_g$, and $thres{h}_b$ to minimize the error defined by: $Error=\left[\mathrm{\#}falsepositive\right]+\alpha \left[\mathrm{\#}falsenegative\right]$, where a false positives is defined as a fake image wrongly labeled as real and a false negative is a real image wrongly labeled as fake. The term $\alpha$ is used to weigh the contribution of the number of false positive and false negative in our error sum term. For $\alpha$ greater than 1, false positives are penalized more than false negatives. Vice versa is true for $\alpha$ smaller than 1.

An image is labeled as fake if there exists a block such that the normalized similarity value for all three channels is below the corresponding threshold value. The image is labeled as real if for all blocks, there is at least one color channel such that the similarity value is above the corresponding threshold. This thresholding method helps reduce the number false positives.

Results

Running the algorithm on an image, we obtain the following similarity scores. Figure 1. is the similarity scores for RGB channels for a fake image.

Figure 1. Similarity values of a fake image using 256 x 256 windows

Figure 2. Similarity values of a real image using 256 x 256 windows

Data Set

Given a set of 70 pairs of images (real images and their corresponding fakes), we used 50 pairs of images as training data, to find the threshold values for each channel. The remaining 20 pairs are used to test the performance of the algorithm.

Error Rates

Thresholds used $thres{h}_r=.105$, $thres{h}_g=.11$, and $thres{h}_b=.115$.
Block size = 64x64

Absolute Value

Error Rates

	True	False
Positive	95.71%	4.29%
Negative	88.57%	11.43%

Max Normalized

Thresholds used $thres{h}_r=.18$, $thres{h}_g=.16$, and $thres{h}_b=.15$. Block size of 64x64.

Error Rates

	True	False
Positive	0	0
Negative	0	0

Mean Normalized

Error Rates

	True	False
Positive	0	0
Negative	0	0

Varying Block Size

Error Rates

	256x256	128x128	64x64
True Positive	0	0	95.71%
True Negative	0	0	88.57%
False Positive	0	0	4.29%
False Negative	0	0	11.43%
Total Error	0	0	7.86%

As seen above, using smaller block sizes improves the performance of the detection algorithm.

JPEG Compressed

Error Rates

	Quality 100	Quality 90	Quality 75	Quality 50
True Positive	0	0	0	0
True Negative	0	0	0	0
False Positive	0	0	0	0
False Negative	0	0	0	0
Total Error	0	0	0	0

References - Resources and related work

References

Software

Appendix I - Code and Data

Code

File:CodeFile.zip

Data

zip file with my data

Appendix II - Work partition (if a group project)

Brian and Bob gave the lectures. Jon mucked around on the wiki.