Revision as of 02:50, 20 March 2013

Back to Psych 221 Projects 2013

Background

Digital Image Forgery

Digital cameras have long since replaced traditional cameras as the dominant form of photography. Their practicality coupled with the combination of low cost and high performance have made them extremely popular. Additionally, with the advent of the camera phone, nearly every person now has a camera on them at all times. This has led to an explosion of images of nearly anything that can be easily found on the internet. Combined with very power photo editing software such as Photoshop, the amount of forged images has also dramatically increased. Images of a subject or event can longer be blindly taken at face value since it has become so easy to forge them. Because of this, it has become increasingly important to be able to discern legitimate images from forged ones. It is possible to leverage how digital camera sensors record images to determine if they have been altered and post-processed.

Digital Camera Image Sensors

Each pixel in a color digital image consists of three different values: its red, green, and blue intensity. Therefore, the entire image can be thought to have three separate channels--one for each color. However, each of the CMOS imaging chip's photosensors, which will record the light in the scene for a single pixel, can only detect light intensity without wavelength information. Therefore, they are unable to separate color information and record a separate value for each channel. To work around this limitation, image sensors typically employ a color filter array (CFA), which is a mosaic of tiny color filters placed on top of the image sensor, so that for each individual pixel, only a single band of light will pass through it and be recorded onto the pixel. Figure 1 depicts a common CFA known as a Bayer array, which employs a pattern of red, blue, and green color filters.

CFA Interpolation

In order to construct a complete image with RGB values for every pixel, we must estimate the two missing color values at each pixel by interpolating the values of neighboring pixels. There are numerous interpolation algorithms that can be used, which can vary between the make and model of the camera.

Camera Forensics using CFA Interpolation

A technique used to determine if an image has been altered leverages the properties of CFA interpolation. In an undoctored image, there will be a strong correlation between the estimated color values and its values of its neighbors. However, if an image has been digitally altered, these correlations will likely be destroyed. Even if an image has been created by combining two unaltered images together, the interpolation pattern will not remain the same across the subimage boundaries. Therefore, by measuring the strength of the periodic pattern of interpolated pixels in an image, we can tell if an image has been doctored or not.

Expectation Maximization

Given an image, we do not know both the exact parameters of the interpolation algorithm, nor which pixels are being estimated. Since we have two unknowns, we need to use an expectation/maximization (EM) algorithm to estimate both unknowns at the same time. We assume a simple linear model for the interpolation algorithm, which may not be exact, but is simple and will give a decent approximation of more complex CFA algorithms. We also assume each color channel is interpolated independently. Therefore, we run the EM algorithm for a single color channel at a time. Lastly, we assume each pixel belongs to one of two models: 1 if the pixel is estimated from its neighbors, and 2 if it is not.

E-Step

In the expectation step, we estimate the probability of each pixel belonging to a particular model. We can estimate the probability of a sample belonging to Model 1 using Bayes' Rule:

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. TeX parse error: Undefined control sequence \emph"): {\displaystyle \Pr\{{\emph {f(x,y)}}\in M_{1}\mid {\emph {f(x,y)}}\}={\frac {\Pr\{{\emph {f(x,y)}}\mid {\emph {f(x,y)}}\in M_{1}\}\Pr\{{\emph {f(x,y)}}\in M_{1}\}}{\sum _{i=1}^{2}{\Pr\{{\emph {f(x,y)}}\mid {\emph {f(x,y)}}\in M_{1}\}\Pr\{{\emph {f(x,y)}}\in M_{1}\}}}}}

where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. TeX parse error: Undefined control sequence \emph"): {\displaystyle \Pr\{{\emph {f(x,y)}}\mid {\emph {f(x,y)}}\in M_{1}\}\}={\frac {1}{\sigma {\sqrt {2\pi }}}}exp(-{\frac {[{\emph {f(x,y)}}-\sum _{u,v=-N}^{N}{\alpha _{u,v}f(x+u,y+v)}]^{2}}{2\sigma ^{2}}})}

The initial values of the variance is the inverse of the range of f(x,y). Random values between 0 and 1 are chosen to initialize all the $\alpha$ coefficients.

M-Step

The M-step minimizes the quadratic error function

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

To minimize this equation, the partial derivative with respect to each $\alpha _{s,t}$ is taken to form the equation:

$\sum _{u,v=-N}^{N}{\alpha _{u,v}\left(\sum _{x,y}w(x,y)f(x+s,y+t)f(x+u,y+v)\right)}=\sum _{x,y}{w(x,y)f(x+s,y+t)f(x,y)}$

When all partial derivatives of $\alpha _{s,t}$ are taken, then there will be $(2*n+1)^{2}-1$ unknowns and equations (because $\alpha _{0,0}$ is always 0). These linear set of equations and unknowns can be then solved using linear algebra to find new $\alpha 's$ . This was done using Matlab's linsolve() function. Each coefficient for the left hand side of the equation was put into its respective place in a matrix and a vector was created for the right hand side of the matrix. Matlab's linsolve() function could then take the matrix representing the coefficients of each $\alpha$ and the vector for values on the right hand side of the equation, and solve for all unknowns. The EM algorithm repeats until it converges. Convergence would be if the difference between the last iteration and the current iteration is less than $\epsilon$ .

A new variance estimate is also done in the M-step with the equation:

$\sigma _{n+1}=\left({\frac {\sum _{x,y}w(x,y)r^{2}(x,y)}{\sum _{x,y}w(x,y)}}\right)^{1/2}$

Probability Map

Here we display the probability map, which lists of the probability of each pixel being interpolated, as an image. The periodicity is not visible, likely due to the small size of each pixel.

2D FFT

If we take the two dimensional FFT of the probability map and plot it, then we can more clearly see the periodic patterns which manifests itself as peaks in the graph. In the figure below, the probability map is up-sampled by a factor of two in order to push the peaks towards the center for visibility reasons. The resulting FFT data is also shifted to move the zero peak to the center, as well as having the log() function and gamma correction applied to it to make the peaks more distinct. The peaks in the center of each quadrant represent the periodic pattern of the interpolated pixels.

Similarity Measure

A synthetically generated probability map was produced with the following definition for each color channel:

$s_{r}(x.y)={\begin{cases}0&{\mbox{if S(x,y) = r(x,y)}}\\1&{\mbox{otherwise}}\end{cases}}$ $s_{g}(x.y)={\begin{cases}0&{\mbox{if S(x,y) = g(x,y)}}\\1&{\mbox{otherwise}}\end{cases}}$ $s_{b}(x.y)={\begin{cases}0&{\mbox{if S(x,y) = b(x,y)}}\\1&{\mbox{otherwise}}\end{cases}}$

We assume a Bayer CFA was used to generate the images so in order to produce one in Matlab the synthetically generated maps followed this pattern:

$S_{2i+1,2j+1}=r(x,y)$ , $S_{2i+1,2j}=g(x,y)$ , $S_{2i,2j+1}=g(x,y)$ , and $S_{2i,2j}=b(x,y)$

We run a sliding 128px by 128px window with 64px stride (50% overlap) over the probability map of the image and synthetically generated probability map. We then take the 2D FFT of the subimage contained in the window and run the cosine similarity measure calculation against the corresponding subimage of the synthetically generated probability map.

The cosine similarity measure is defined as $M(p_{g},s_{g})={\frac {\sum _{w_{x},w_{y}}{\mid P_{g}(w_{x},w_{y})\mid \times \mid S_{g}(w_{x},w_{y})\mid }}{{\sqrt {\sum _{w_{x},w_{y}}{\mid P_{g}(w_{x},w_{y})\mid ^{2}}}}\times {\sqrt {\sum _{w_{x},w_{y}}{\mid S_{g}(w_{x},w_{y})\mid ^{2}}}}}}$

$P_{g}$ and $S_{g}$ are the Fourier transforms of the probability map and synthetic probability map of the green channel. Similar calculations are done for the red and blue channels.

note: Normalization is done by dividing each color channel's similarity measure by the respective maximum similarity measure for all blocks.

Thresholding

Threshold values were determined empirically from test image sets. An image is classified as being fake if all three color channels fall below their respective threshold value for any one subimage.

Other Methods Explored

To automatically classify images as altered or real, we explored different techniques as a possible classifier. The two main approaches we had were peak detection and a similarity measure proposed in Farid's paper.

Peak Detection

The 2D FFT of the probability map of a real image showed strong peaks in certain locations [( ${\frac {PictureWidth}{4}}$ , ${\frac {PictureHeight}{4}}$ ),(( ${\frac {3\times PictureWidth}{4}}$ , ${\frac {PictureHeight}{4}}$ ), ( ${\frac {PictureWidth}{4}}$ , ${\frac {3\times PictureHeight}{4}}$ ), and ( ${\frac {3\times PictureWidth}{4}}$ , ${\frac {3\times PictureHeight}{4}}$ )] since a periodic interpolation was detected. Tampered pictures usually did not show peaks in those areas. We tried to take advantage of this property and determine if an image is fake or real by detecting a peak around those locations mentioned earlier. However many of the tampered images were very similar to their real image counterparts, they still exhibited peaks in the 2D FFT image.

Sectioning of Images

Because many altered images were only distorted minimally in certain small sections of the picture, we decided to use a method of partitioning the picture first into many subimages. This method was done by initially sectioning the entire image to 9 roughly equal sized small images and running the EM algorithm on each subimage. Afterwards, we tried to use peak detection on each subimage's 2D FFT and classify an image as real if all subimages showed a periodic interpolation property. We explored this technique with different sizes of subimages, partitioning the original image into 9, 16 or 36 smaller subimages. However, this method was not promising as many of the smaller subimages still showed no real distinct difference between altered and real image pairs.

Similarity Measure

After our peak detection technique proved to be not promising we then explored Farid's similarity measure as described in his paper. The similarity measure calculation that was proposed in the paper used the equation:

$M(p_{g},s_{g})=\sum _{w_{x},w_{y}}{\mid P_{g}(w_{x},w_{y})\mid \times \mid S_{g}(w_{x},w_{y})\mid }$

We explored this measurement on 100 test images to try to empirically find thresholds for each channel of the image. This again was done on the full image as well as subimages of the original picture. 128x128 sliding windows with 50% overlap were also tested with this calculation. The results of the test data results were not promising because the amount of variance from different pairs of picture was much greater than the variance between a real picture and its tampered counterpart. No distinct threshold was found to have separated real and altered images nicely. This classification method instead classified pairs of images as fake, so the number of false positives was equal to the number of true positives.

This failure caused us to explore other methods to try to normalize pairs of images so the similarity measure between pairs would not effect the threshold values. We came to the conclusion of using cosine similarity as it resembled the original similarity measure proposed in the paper, but had less variation between pairs of images.

Results

Uncompressed Images

Figure 5 is the similarity measures for each channel for each window of the original image. The similarity measures in Figure 5 are quite a bit higher than the ones in Figure 6, which are the similarity measures the corresponding altered image.

Figure 5: Normalized Similarity Measure for Original Image

Figure 6: Normalized Similarity Measure for Tampered Image

On our test set we had 20% False Positive and 40% Sensitivity. This test was done over 20 randomly chosen images.

$Sensitivity={\frac {\#TruePositives}{\#TruePositives+\#FalseNegatives}}$

$FalsePositiveRate={\frac {\#FalsePositives}{\#FalsePositives+\#TrueNegatives}}$

JPEG Images

On our test set of jpg images, our classifier could not handle jpeg compression and classified all images as fake images regardless of Q factor.

Figure 7: 2D FFT of Probability Map of JPEG image with Q-factor = 70

As seen in this 2D FFT plot, jpeg images did not show any periodic interpolation as there are no visible peaks in Figure 7. This would correlate to a low similarity measure score and thus our classifier would classify all jpeg images as fake.

Test Images

tp3f84b1d8_60eb_4254_9dbe_657421e27500.fake.png true picture

tp3f84b1d8_60eb_4254_9dbe_657421e27500.real.png true picture

tp501a096a_72e7_4c96_989f_3bedf5b928db.fake.png true picture

tp501a096a_72e7_4c96_989f_3bedf5b928db.real.png true picture

tp8ba7ba67_d78a_4b01_bd41_c6440a7c69c6.fake.png true picture

tp8ba7ba67_d78a_4b01_bd41_c6440a7c69c6.real.png true picture

tpc69b985f_2cd4_4fd8_89ef_08acae1f754c.fake.png true picture

tpc69b985f_2cd4_4fd8_89ef_08acae1f754c.real.png true picture

tpcb9fdff3_ca6d_4786_8763_2014a920d19e.fake.png true picture

tpcb9fdff3_ca6d_4786_8763_2014a920d19e.real.png true picture

tpd4e65e8d_7310_43ab_98f8_a9e1d9a7e40f.fake.png FALSE PICTURE

tpd4e65e8d_7310_43ab_98f8_a9e1d9a7e40f.real.png true picture

JPEGQ100fake.png true picture

JPEGQ100real.png true picture

JPEGQ30fake.png true picture

JPEGQ30real.png true picture

JPEGQ60fake.png FALSE PICTURE

JPEGQ60real.png FALSE PICTURE

Resized066.fake.png true picture

Resized066.real.png true picture

False Positive Rate = 10%, Sensitivity = 20%

Conclusions

Camera forensics using CFA interpolation detection can be a very powerful and useful technique for determining the authenticity of a photo since it does not rely on any special watermarking technique. However, it is not necessarily a foolproof method, since it would be possible for a sophisticated attacker to alter an image and reapply a CFA interpolation pattern back onto the image. There will constantly be a back and forth battle to create techniques to defeat camera forensics as well as techniques to defeat these attackers.

Our results show that we were able to detect tampered images using the CFA interpolation detection technique, although our sensitivity and false positive rates leave much room for improvement. It is possible and running a much larger data set with many different types of images will allow us to find a better threshold to use when analyzing the similarity measure an image. Another possible idea is to use a supervised learning model such as an SVM to help us find a more exact threshold to use in our classifier.

References - Resources and related work

[1] Farid, H. Exposing Digital Forgeries in Color Filter Array Interpolated Images. Signal Processing, IEEE Transactions. Vol. 53, Issue 10. October 2005.

[2] Wikipedia "Bayer Filter" http://en.wikipedia.org/wiki/Bayer_filter

[3] Wikipedia "Cosine Similarity" http://en.wikipedia.org/wiki/Cosine_similarity

Appendix I - Code and Data

Code

File:CodeFile.zip

Data

zip file with my data

Appendix II - Work partition (if a group project)

Side by side work was done for the entire project

@@ Line 126: / Line 126: @@
 == Uncompressed Images ==
+Figure 5 is the similarity measures for each channel for each window of the original image. The similarity measures in Figure 5 are quite a bit higher than the ones in Figure 6, which are the similarity measures the corresponding altered image.
 [[File:RealPlot.png |thumb|center|500px|Figure 5: Normalized Similarity Measure for Original Image]] [[File:FakePlot.png|thumb|center|500px|Figure 6: Normalized Similarity Measure for Tampered Image]]