SchmittWerner

Back to Psych 221 Projects 2013

Introduction

Due to improvements in digital technologies, image forgeries are increasingly believable and easy to produce. There are some situations, including forensic settings, where it is necessary to detect and localize such manipulations in images. A robust technique to identify image forgeries on uncompressed images is presented in this paper.

Cameras introduce specific statistical correlations in images [1]. One such identifiable pattern is caused by color filter arrays (CFA). Typically, each pixel sensor only measures the value corresponding to one color channel. The most common mosaic arrangement is called the Bayer Filter, which is shown in Figure 1. To produce red, green, and blue (R,G,B) values at each pixel, demosaicing algorithms are used to interpolate missing color channel values by taking a combination of neighbor’s color channels [2]. The authors of [3] suggest that it is sufficient to treat the color channels independently and assume a linear combination is used for interpolation. While we assume the linear model in this paper, we show that considering the dependence between separate color channels produces more accurate results.

Figure 1. Color Filter Array technology [3]

In the seminal paper by Farid [4], the assumption of linearity allows an expectation maximization algorithm (EM) to be used. This predicts whether each pixel is likely to be a linear combination of its neighboring pixels in two-dimensions. Periodicities in this likelihood map appear as strong peaks in the Fourier magnitude spectrum. In regions where tampering is present, these peaks will appear in different locations, or not at all. A follow-up paper [3] expands this technique to look for the periodicities introduced by CFA demosaicing algorithms in particular. In regions where tampering is present, the correlations introduced by CFA are obscured. Our paper attempts to reproduce the results found in [3] and provide additional refinements to improve the efficacy of forgery detection.

Methods

Expectation Maximization

An EM algorithm is used for unsupervised clustering of a data set. The power of the EM algorithm derives from its iterative alternation between an expectation step (E) and a maximization step (M). In the E step, the likelihood of each data point belonging to each of the models is maximized given the parameters of the clustered models. In the M step, these parameters are recomputed given the likelihood that each data point belongs to each model.

As described in [3], in the case of detecting image forgeries, our aim is to determine the likelihood that each pixel in the image belongs to the sampled or unsampled clusters. Pixels belonging to the sampled cluster possess independent values that were measured by the camera’s sensors. However, pixels in the unsampled cluster are approximately a structured linear combination of their neighbors’ pixel values.

In this paper, a raw image of dimension [n x m x 3] is passed into the EM algorithm and the result is a likelihood map of dimension [n x m x 3] that each pixel in the given image is unsampled. An example of which is shown in Figure 2. As mentioned in the Introduction section, our method does not assume an independent model between the three color channels. As a result, although our method is more computationally intensive than that proposed in [3], it more accurately represents actual demosaicing algorithms. Although difficult to see in this representation, definitive periodicities exist in likelihood maps such as the one shown in Figure 2. However, due to details in the underlying image scene and noise effects, other artifacts are visible in the EM likelihood map.

Figure 2. EM algorithm likelihood map

Discrete Fourier Transform

To uncover the underlying periodicities located in the likelihood map, we utilize the two-dimensional discrete Fourier transform (FFT). The formula for the two-dimensional Fourier transform is

$F(u,v)=\frac{1}{MN}\sum _{x=0}^{M-1}\sum _{y=0}^{N-1}f(x,y)e^{-j2\pi (\frac{ux}{M}+\frac{vy}{N})}$

Different CFA demosaicing algorithms introduce telltale periodicities as shown in [3]. In the frequency domain, these periodicities appear as strong peaks in the magnitude spectrum. Typically, these peaks appear at predictable locations such as when one or both dimensions are at the Nyquist frequency. Figure 3 below shows an example of peaks occurring at Nyquist frequencies in the Fourier domain.

Figure 3. Magnitude Fourier spectrum showing peaks at Nyquist frequencies

Raster Scanner

A raster scanning approach of a window is developed to provide spatial resolution in an attempt to localize tampering in images. The window is scanned across the image to analyze the periodicities in the EM map at different locations. In this paper, we parameterize this square window by its length (window_size) and the amount by which successive windows shift in each dimension (hop_size).

At each window location, we extract a portion of the EM map of area window_size by window_size. We then follow the method described in [3] to compute the magnitude of the Fourier transform of the patch. First, we apply a radially-symmetric Hann windowing function to decrease the effects of edge artifacts on the patch. This windowing function is described by

$W(r)=\frac{1}{2}(1+\cos \left(\pi \frac{r-\frac{3}{4}}{\sqrt{2}-\frac{3}{4}}\right))$

if $\frac{3}{4}<=r<=\sqrt{2}$

and $1$ otherwise. Where $r$ is the radial distance from the center of the patch as defined by

$r=\sqrt{x^2+y^2}$.

The FFT of the windowed patch is then computed and is resized to be fft_size by fft_size. A radially-symmetric high pass filter is applied in the frequency domain to attenuate the lowest frequency components of the Fourier transform. These components are superfluous and are not descriptive of the periodic nature of the patch. The DC component, in particular, is an artifact of the fact that the range of data values are not symmetric about zero. The high pass filter is the normailzed two-dimensional Gaussian, and is described by

$h(r)=\frac{1}{2\pi {\sigma }^2}{e}^{-\frac{r^2}{2{\sigma }^2}}$.

where $\sigma$ is the standard deviation of the two-dimensional Gaussian.

Lastly, we perform gamma correction using a factor of 2.0 on the high pass filtered spectrum and take its magnitude. Figure 4 displays a graphic with the raster scanner at a location in the image and the corresponding magnitude spectrum of the Fourier transform for each color channel of the window. In the figure below, the green box denotes the location of the tampered region, and the blue box denotes the current location of the raster scanner.

Figure 4. Raster scanning process across likelihood map and corresponding magnitude Fourier spectrums in all three color channels

The results of the forgery detection algorithm are highly sensitive to the window_size and hop_size parameters describing the raster scanning window. The hop_size parameter directly affects the resolution of the detection algorithm. Decreasing the hop_size will only improve the results at the expense of more computational intensity.

However, the window_size parameter should be carefully chosen to balance the trade-offs between spatial and frequency domain resolution. A window_size that is too large makes it difficult to localize tampered regions within the window. On the other hand, while a smaller window_size improves the spatial resolution, it suffers from more windowing in the spatial domain. As a result, Fourier transforms of small windows lack finer details.

PCA

It is often possible for a human to visually detect the difference of tampered and untampered regions by examining the magnitude of the Fourier transform. However, it is our goal in this paper to automate this detection process. To this end, we seek to identify features in the magnitude Fourier spectrum that distinguish a region as tampered or untampered.

It should be noted that CFA demosaicing algorithms introduce energy in only a subset of the frequency components of the magnitude spectrum. It is these frequency elements that we consider in determining the authenticity of a patch. For computational reasons, it is desirable to reduce the dimensionality of the magnitude Fourier spectrums before attempting classification.

Principal Component Analysis (PCA) was considered in an attempt to automatically identify the most important dimensions of the magnitude Fourier spectrum. In general, PCA is a procedure to convert a set of potentially correlated variables into a set of linearly uncorrelated variables.

Metrics

Theoretically, this procedure would have the desired effect of decomposing the magnitude Fourier spectrum into its most salient components. However, it was experimentally determined that the additional computational cost required to run the PCA algorithm outweighed its benefits. Instead, we developed a novel approach inspired by [3], where various metrics on the magnitude Fourier spectrum are designed to extract prominent features. These metrics involved peak-based, variance-based, and template-matching methods. It has been experimentally determined that these metrics are computed efficiently. Furthermore, they map the high-dimensional magnitude Fourier spectrum into a much lower-dimensional representation. For example, Figure 5 shows the template used in the template-matching metric. The intuition behind this particular metric is to expose patches whose Fourier transforms contain a large portion of their energy around the Nyquist frequencies.

Figure 5. Temple-matching metric

SVM

Having computed metrics that compactly represent the training patches, a predictive mechanism is necessary to classify a query patch as tampered or untampered. One popular binary classifier is Support Vector Machines (SVM). After training on a representative data set, an SVM builds a model to classify new data into one of two categories. Figure 6 illustrates an example of a trained SVM in a two-dimensional space, using two of our metrics to classify query patches. Green dots indicated patches labelled as untampered, red dots indicated patches labelled as tampered. Black circles surround data points that are used as support vectors in calculating the linear classifying hyper plane.

Figure 6. A trained SVM classifying query patches using a linear classifier

Support Vector Machines are designed to find an optimal distinguishing hyperplane between two clusters of data. However, this is not always the desirable functionality. For instance, in the case of tampering detection, false positives should be more penalized than false negatives. These penalties are difficult to build into an SVM framework.

Thresholding

We develop an alternate framework in one dimension, using our highest-performing metric. This framework allows for direct tuning of the number of false positives allowed. In [3], the authors recommend allowing a 1% false positive rate. To achieve the desired false positive rate, we design a thresholding algorithm. This algorithm maximizes the amount of fake values correctly classified by the threshold while maintaining the specified misclassification ratio of real values. Figure 7 shows an example of a one-dimensional spread of metric scores, their classification labels, and the result of the thresholding algorithm. Note that, for robustness, we develop a continuous-valued classification strategy based on the proportion of each training patch that encompasses a tampered region. This continuum of labels is demonstrated by a continuum of color in Figure 7.

Figure 7. Thresholding algorithm in one-dimensional space

Results

The efficacy of the method discussed in this paper can be visualized using a confusion matrix. Such a matrix indicates the number of true positives, false positives, true negatives, and false negatives in a tabular format. Figure 8 shows the confusion matrix computed from training on 90% of the images given, and testing on 20 of the remaining images.

Figure 8. The confusion matrix

True Positives 6/20	False Negatives 4/20
False Positives 2/20	True Negatives 8/20

The reader should note that both the false positive and false negative rates are smaller than the true positive and true negative rates, which is an indication of acceptable performance of the algorithm. Furthermore, the false positive limitation requirement manifests itself in a very low value in the confusion matrix. We should point at that the false positive rate requirement was set per patch, not for the overall image. And an image is declared as false if just one of its patches is declared as fake. Therefore, the 10% false positive rate shown in the confusion matrix does not contradict the 1% false positive condition posited in the thresholding section. Because there was no limitation placed on the false negative rate, this score is approximately twice as high.

Our algorithm performs well when the tampered region has dimensions of approximately window_size by window_size. In general, the smaller the tampered region is in comparison to the raster scanning window, the worse the algorithm performs. Figures 9 and 10 shows a case where our algorithm correctly identifies a tampered region in an image, and does not falsely identify any tampered regions in the untampered counterpart image. Figure 11 and 12, on the other hand, shows a case where a small tampered region cannot be detected by our algorithm. In these figures, tampered regions are denoted by a green rectangle, and tampering detection is denoted by black regions.

Figure 9. Correctly identified tampered region

Figure 10. Untampered counterpart image

Figure 11. Undetected small tampered region

Figure 12. Untampered counterpart image

Conclusions

Our method is primarily rooted in the assumption that cameras employ Color Filter Array demosaicing algorithms. These algorithms introduce specific detectable statistical correlations into the pixel values of the image. Tampering will often lead to discrepancies in these correlation patterns. Using the methods outlined above, we have had success in detecting various types of tampering in images.

It should be noted that this technique is not a panacea. It is recommended that this method be employed in conjunction with other techniques to expose digital forgeries. In fact, in [3], the authors mention a specific vulnerability of this family of methods. Namely, an attacker could resample a tampered image onto a known color filter array lattice and perform demosaicing to conceal the forgery. However, such an attacker would need considerable knowledge of the minutia of color filter array demosaicing algorithms to produce an undetectable cover-up.

Future Work

Future research should focus on abstracting the metric thresholding method into a higher dimensional space. Additional reasonably orthogonal high-performing metrics allowed SVM to perform better than our proposed approach. However, the lack of direct tuning of the false positive rate kept this method from being a useful technique. If the false positive rate could be controlled in an SVM setting, it is theorized that the classification results would improve considerably.

References - Resources and related work

[1] Farid, H. Image Forgery Detection: A Survey. IEEE Signal Processing Magazine. March 2009.

[2] Farid, H., Popescu, A.C. Statistical Tools for Digital Forensics. 6th International Workshop on Information Hiding. Toronto, Candada. 2004.

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

[4] Farid, H., Popescu, A.C. Exposing Digital Forgeries by Detecting Traces of Resampling. Signal Processing IEEE Transactions. Vol. 53, Issue 2. February 2005.

[5] DigitalFilms. Photo. digitalfilms.wordpress.com. 16 March 2013.

Appendix I - Code

Code

File:SchmittWerner.zip

Appendix II - Work partition (if a group project)

Kurt: raster scanner, fft, metrics, pca

Drew: fft, svm, metrics, thresholding