Advanced
Approximate Detection Method for Image Up-Sampling
Approximate Detection Method for Image Up-Sampling
KSII Transactions on Internet and Information Systems (TIIS). 2014. Feb, 8(2): 462-482
Copyright © 2014, Korean Society For Internet Information
  • Received : July 04, 2013
  • Accepted : January 23, 2014
  • Published : February 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Ching-Ting Tu
Department of Computer Science and Information Engineering Tamkang University Taipei, Taiwan, 25137 ROC
Hwei-Jen Lin
Department of Computer Science and Information Engineering Tamkang University Taipei, Taiwan, 25137 ROC
Fu-Wen Yang
Department of Computer Science and Information Engineering Tamkang University Taipei, Taiwan, 25137 ROC
Hsiao-Wei Chang
Department of Computer Science and Information Engineering China University of Science of Technology Taipei, Taiwan, 11581 ROC

Abstract
This paper proposes a new resampling detection method for images that detects whether an image has been resampled and recovers the corresponding resampling rate. The proposed method uses a given set of zeroing masks for various resampling factors to evaluate the convolution values of the input image with the zeroing masks. Improving upon our previous work, the proposed method detects more resampling factors by checking for some periodicity with an approximate detection mechanism. The experimental results demonstrate that the proposed method is effective and efficient.
Keywords
1. Introduction
R apid development of techniques over the past decades have enabled people to easily acquire images and share or transfer them through the Internet. These images are easily modified or further synthesized by existing image-processing software for certain purposes. Such image manipulation might violate the copyright or illegitimately cause a bad result. To combat these illegitimate practices, we urgently need algorithms that can detect such forgeries.
In recent years, many forgery-detection methods have been proposed. Popescu et al. [1] and Kirchner [2] detected forgeries with resampling or rotation by checking for some periodicity in the images. Nillius et al. [3] and Johnson et al. [4] detected digital forgeries by detecting the lighting consistencies. Li et al. [5] detected tampered watermarked images with the embedded information and recovered the images using methods that are similar to those in [6 , 7] . Camera defects such as chromatic aberration [8] and sensor pattern noise [9 - 12] , as well as the color filter arrays [1] that cameras use to interpolate colors, can be used to detect forgeries. Copy-move images are easily made by copying certain regions and pasting them on some other regions. Some methods have been proposed to detect these types of forged images [13 - 18] .
Resampling is frequently involved in image forgeries, which motivates us to study the detection of such image manipulation. Most existing resampling-detection methods [1 , 2] can detect resampling but cannot recover the resampling factors (or resampling rates). The method proposed by Lien et al. [19] addresses the recovery of the resampling rates, but it can only recover the resampling factors with the provided corresponding weighting tables and must use weighting tables to recover the possible original image and examine the periodicity. Furthermoer, their work is notably time-consuming, and false positive may be caused when the set of weighting tables is not sorted in specific orders.
We have previously proposed an algorithm [20] to detect a wider range of resampling factors in less time by providing a set of zeroing masks. However, the detectable resampling factor must correspond to a zeroing mask in the provided set. In other words, the amount of detectable resampling factors is exactly identical to the number of zeroing masks that are provided for detection. The objective of this paper is to overcome this limitation of our previous work and detect many more factors than the number of provided zeroing masks. If an image is resampled by a factor that corresponds to a provided zeroing mask, then the exact resampling factor can be detected; otherwise, the image will be further detected using an approximate detection mechanism. Therefore, the proposed method is more applicable.
The remainder of this paper is organized as follows. The basic concept of resampling and a review of our previous work are introduced in Section 2. In Section 3, the proposed method of approximate resampling detection is described. Section 4 presents some experimental results, and Section 5 concludes.
2. Overview of Exact Resampling Detection
In this section, we will briefly introduce the basic concept of resampling and the exact resampling detection that was proposed in our previous work [20] .
- 2.1 Resampling
Resampling is the mathematical technique to create a new version of the image with a different width and/or height in pixels. Increasing the image size is called upsampling; reducing its size is called downsampling.
Resampling of a 2-D image can be broken down into two 1-D resampling passes. In one pass, horizontal resampling is performed by producing an image with a different width but the same height. In the next pass, this intermediate image is resampled vertically to change its height while maintaining the width. This process is much more computationally efficient than combining the work into one pass. Upsampling involves interpolating among the existing pixels to estimate their values at the new pixel locations. Downsampling involves computing the weighted average of the original pixels that overlap each new pixel. Color images are treated like three grey-scaled images which are separated from the original image, individually resampled, and finally recombined to create the final image.
For 2-D resampling, each dimension can be separately resampled and detected. To easily explain, we will first describe one-dimensional resampling [1] .
Let x [ t ] be a 1-D discrete signal with n samples to be sampled. The number of samples in signal x [ t ] can be resampled using a factor of p / q to create a new sample y [ t ] with m samples as follows:
  • 1.Up-sample: Create a new signalxu[pt] =x[t], wheret= 1, 2, …,n, andxu[pt] = 0 otherwise.
  • 2.Interpolate: Convolvexu[t] with a low-pass filterh[t]:xi[t] =xu[t]*h[t].
  • 3.Down-sample: Create a new signalxd[t] withmsamples, wherexd[t] =xi[qt], andt= 1, 2, …,m. Denote the resampled signal asy[t] =xd[t].
Different types of resampling algorithms (e.g., linear cubic) differ in the form of the interpolation filter in Step 2. In this study, we assume that the linear interpolation filter is used. Because all three steps in the signal resampling are linear, this process can be described with a linear transformation as shown in (1).
PPT Slide
Lager Image
where Ap/q is the transformation matrix of size m × n . Depending on the resampling fraction, the resampling process introduces correlations of varying degrees among the neighboring samples. For example, consider the upsampling of a signal by a factor of two. In this case, the resampling matrix takes the following form:
PPT Slide
Lager Image
Here, the odd samples of the resampled signal y = [ y 1 y 2 ym ] t take on the values of the original signal x = [ x 1 x 2 xn ] t ; i.e., y 2i-1 = xi , i = 1, 2, …, n , where yj = y [ j ] and xj = x [ j ]. The even samples are the averages of the adjacent neighbors of the original signal:
PPT Slide
Lager Image
where i = 1, 2, …, n -1. Because xi = y 2i-1 and xi +1 = y 2i+1 , the above relationship can be expressed in terms of only the resampled samples:
PPT Slide
Lager Image
In other words, across the entire resampled signal, each even sample is precisely the same linear combination of its adjacent neighbors. According to this description, we will use the relation among the pixels and their neighbors to detect resampling.
- 2.2 Constructing Resampling Matrices
In this subsection, we describe how our previous work [20] constructed the resampling matrices. For a matrix A , let A [ r 1 .. r 2 , c 1 .. c 2 ] denote the sub-matrix of A that is formed with the entries between rows r 1 and r 2 , and between columns c 1 and c 2 . It can be observed that the matrix Ap/q is periodically composed of its sub-matrix Ap/q [1.. p , 1.. q +1]. For example, the matrix A 4/3 is periodically composed of the sub-matrix A 4/3 [1..4, 1..4]. This result can be described as follows.
PPT Slide
Lager Image
for every integer k with 0 ˂ 4 k ˂ m and 0 ˂ 3 k ˂ n , or 0 ˂ k ˂ min{ m /4, n /3}.To be more general, we have
PPT Slide
Lager Image
for every integer k with 0 ˂ pk ˂ m and 0 ˂ qk ˂ n , or 0 ˂ k ˂ min{ m / p , n / q }.
Because of the periodicity, it is sufficient to consider only the ( p +1)×( q +1) sub-matrix Ap/q [1.. p +1, 1.. q +1] for any resampling matrix Ap/q . We called the sub-matrix Ap/q [1.. p +1, 1.. q +1] the primary sub-matrix of Ap/q . For simplicity, when we refer to a resampling matrix Ap/q , we mean its primary sub-matrix. (7) and (8) show the newly defined matrices A 2/1 and A 5/3 , respectively, from each of which we can see that the entries are symmetric to the center of the matrix; in other words, Ap/q [ i , j ] = Ap/q [ p +2- i , q +2- j ] for i = 1, 2, …, p +1 and j = 1, 2, …, q +1.
PPT Slide
Lager Image
PPT Slide
Lager Image
Again, for simplicity, we assume that q = 1 or p and q are coprime (or relatively prime) positive integers. For 1≤ q ˂ p ≤12, there are 45 factors p / q , which are composed as listed below:
p = 2, q = 1;
p = 3, q = 1, 2;
p = 4, q = 1, 3;
p = 5, q = 1~4;
p = 6, q = 1, 5;
p = 7, q = 1~6;
p = 8, q = 1, 3, 5, 7;
p = 9, q = 1, 2, 4, 5, 7, 8;
p = 10, q = 1, 3, 7, 9;
p = 11, q = 1~10;
p = 12, q = 1, 5, 7, 11.
It can be further observed from (7) and (8) that every row except the top row and the bottom row in a resampling matrix Ap/q has exactly two nonzero entries, which are adjacent in the row. The nonzero entries in row i are (( p −( i +1)⋅ q )mod p )/ p and ((( i +1)⋅ q )mod p )/ p . Assume that the nonzero entries in row i (2≤ i p −1) are located in the j th and ( j +1)th columns. Then, the nonzero entries in row i + 1 are in the ( j +1)th and ( j +2)th columns if( p −( i +1)⋅ q )mod p ˂( p −( i +2)⋅ q )mod p ; and in the j th and ( j +1)th columns otherwise. The general form of the resampling matrix Ap/q is given in (9), where βi = (( p i q )mod p )/ p , i = 1, 2, …, p -2, denotes the first nonzero entry in the ( i +1)th row of Ap/q . Let βr be in column c ( r ) of Ap/q then Ap/q [( r +1), c ( r )] = βr . If βr ˃ βr +1 (or ( p r q )mod p ˃ ( p −( r +1)⋅ q )mod p ), then βr and βr +1` must be in the same column, i.e., c ( r +1) = c ( r ); otherwise, c ( r +1) = c ( r ) + 1.
PPT Slide
Lager Image
As shown in (9), assume that βi ˃ βi +1 (or ( p r q )mod p ˃ ( p −( r +1)⋅ q )mod p ), for i = r +1, r +2, … r + k , and β r+k ˂ β r+k+1` (or ( p −( r + k )⋅ q )mod p ) ˂ p −( r + k +1)⋅ q )mod p ), then c ( r ) +1 = c ( r +1) = c ( r +2) = ...= c ( r + k ) = c ( r + k + 1 ) - 1. For each row between the 3rd row and the ( p -1)th row where its first nonzero entry is located at the same column as the first nonzero entry in the preceding row, we called it the following row . It can be observed that the matrix Ap/q possesses a following row only when p ˃ q +1. For instance, the 4 th row of the matrix A 5/3 is a following row .
The sequence of the entry pairs (( β 1 ,1− β 1 ), ( β 2 ,1− β 2 ), ⋯,( βp -2 ,1− βp -2 )) is symmetric, i.e., βi = 1− β p-1-i for i = 1, 2, …, ⎿( p −1)/2⏌.
With the above observation, we may determine the content of any resampling matrix Ap/q . The algorithm Resampling Matrix Construction ( RMC ) [20] that derives the resampling matrices is given as follows.
- Algorithm RMC
Input : two positive coprime integers p and q with p ˃ q
Output : Matrix A [1..1+ p , 1.. q +1]
for i ← 1 to p +1
for j ← 1 to q +1
A [ i , j ] ← 0;
A [1,1] ←1 A [ p +1, q +1] ←1; j ←1;
for
PPT Slide
Lager Image
if ( p - iq )mod p ˂ ( p -( i +1) q )mod p
then j j +1;
PPT Slide
Lager Image
A [ i , j +1] ←1− A [ i , j ];
A [ p +2− i , q +2− j ] ← A [ i , j ];
A [ p +2− i , q +1− j ] ← A [ i , j +1]
- 2.3 Deriving Zeroing Masks
With the above assumption for resampling matrices, we consider only the first q + 1 samples of the signal x to be resampled, say x [ t ], t = 1, 2, …, q + 1, and the first p + 1 samples of the resampled signal y , say y [ t ], t = 1, 2, …, p + 1. As a result, we write the relationship in (4) (with i = 1) for the signal that is resampled by a fraction of 2/1 to:
PPT Slide
Lager Image
which indicates that the convolution of signal y with the 3×1 filter F 2/1 = [-0.5 1 -0.5] zeroes the samples of y . We call this filter a zeroing mask for the resampling factor 2/1. Of course, any resampled signal can be zeroed using a zero filter (a zero vector), which cannot be used to detect resampling. From now on, we are only interested in nonzero zeroing filters.
We have proved in our work that there is a nonzero zeroing mask for any resample factor p / q , where p and q are coprime positive integers and p ˃ q , or that there is a ( p +1)×1 zeroing filter Fp/q = [ α 1 α 2 ... αp +1 ], where αi ’s are not all zeros, such that for any resampled signal y by factor p / q , the following relation holds.
PPT Slide
Lager Image
which is equivalent to the convolution of y with Fp/q :
PPT Slide
Lager Image
where Fp/q * y = Fp/q y if y is of size ( p +1)×1 and Fp/q yt if y is of size 1×( p +1). Assuming that y is of size ( p +1)×1, substituting (1) in (12) yields:
PPT Slide
Lager Image
Because the relation in (13) holds for every vector x ,
PPT Slide
Lager Image
must be a zero vector, as shown in (14), which can be regarded as a linear system of q + 1 equations with p + 1 unknowns.
PPT Slide
Lager Image
As an example, considering the resampling by a fraction of 5/3; then, (11) becomes
PPT Slide
Lager Image
Substituting y = A 5/3 x in (15) yields
PPT Slide
Lager Image
which is equivalent to
PPT Slide
Lager Image
Because (17) holds for any signal x , the coefficient for each xi in (17) must be zero, i.e.,
PPT Slide
Lager Image
(18) forms a system of 4 linear equations with 6 unknowns to solve the zeroing filter Fp/q and is equivalent to the relation
PPT Slide
Lager Image
or the matrix equation:
PPT Slide
Lager Image
Thus, the matrix equation that corresponds to the fraction p / q , as shown in (14), represents a system of q +1 linear equations with p +1 unknowns.
Two masks M = [ m 1 m 2 mk ] and M ’ = [ m 1 ' m 2 ' ⋯ mk '] are considered equivalent if M = cM ’ (or mi / mi ' = c for i = 1, 2, …, K ) for some constant c . Two equivalent masks zero the same set of signals. Hence, a solution for a zeroing mask corresponds to a set of parallel vectors ( M and M ’ are considered two parallel vectors), which can be considered a 1-D vector space. Therefore, for p q +2 (or p - q ≥2), there is an infinite amount of nonequivalent zeroing masks for the resample fraction p / q . To unify equivalent zeroing masks and exclude the zero zeroing mask, we fix the first element α 1 = 1 for every mask Fp/q = [ α 1 α 2 αp +1 ]. This action is equivalent to adding the equation α 1 = 1 in each of the aforementioned systems. This setting can also avoid trivial solutions or the solution of the zero filter. For example, adding the equation α 1 = 1 into (18) forms a nonhomogeneous linear system, as shown in (20), which is equivalent to the matrix form in (21).
PPT Slide
Lager Image
PPT Slide
Lager Image
The zeroing masks for the resample factor 5/3 can be obtained by solving the nonhomogeneous linear system in (20) or (21). In general, the zeroing mask Fp/q for the resample factor p / q can be obtained by solving the following nonhomogeneous linear system.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
denotes a unit column matrix with a size of k ×1, and Fp/q = [ α 1 α 2 αp +1 ] is a row matrix of size 1×( p +1) that consists of p +1 variables. Therefore, Ep/q is a matrix of size ( q +2)×( p +1) with the submatrix
PPT Slide
Lager Image
at its top row, i.e.,
PPT Slide
Lager Image
and
PPT Slide
Lager Image
The general form of Ap/q , which is given in (9), yields the expanded form of Ep/q .
- 2.4 Detecting Resampling with Zeroing Masks
Image resampling by any factor can be detected by evaluating the convolution of the image with a sequence of zeroing masks. As follows, the algorithm ZMD ( zeroing mask derivation ) [20] generates a zeroing mask that corresponds to any resampling factor p / q and the algorithm UD ( up-sampling detection ) [20] detects resampling with a set of provided zeroing masks. To detect resampling by factor p / q on an image region I , we use a resampling score function rs , as provided in (23), to evaluate the confidence value of resampling, where B ( I ) is the set of divided blocks of the image region I , and * denotes the convolution operator. Block Bij is considered resampled by factor p / q if the convolution value Mp/q * Bij is sufficiently small. The number of resampled blocks is counted using the function h : h ( x ) = 1 if x s , and 0 otherwise, where s is a given threshold. If the resampling score value rs ( I , p / q ) is greater than a threshold t , we consider the image region I as having been resampled by fraction p / q . The score value rs falls between 0 and 100.
PPT Slide
Lager Image
- Algorithm ZMD
Input : two positive coprime integers p and q with p ˃ q
Output; coefficients a 1 , a 2 , …, ap +1
a 1 ← 1
Δ ← 1 − β 1
i ← 2
while i ≤ ⎿( p +2) / 2⏌ do
k ← 1
α βi
while β i+k-1 β i+k do
α α + β i+k
k k +1
ai ← (−Δ) / α
← 1
while k −1 do
ai + ai +-1
+1
Δ ← ℓ ai ⋅ ( k α )
i i + k
if p is odd & i −1 = ⎿( p +2) / 2⏌
then
while i p +1 do
ai ← − ap +2-i
i i −1
else
while i p +1 do
ai ← − ap +2-i
i i −1
- Algorithm UD
k ← 1; resampled false ;
while ( k K ) and ( not resampled ) do
if rs ( I , p [ k ]/ q [ k ]) ˃ t 2
then resampled true
else k k +1;
if resampled
then return p [ k ] & q [ k ]
else return "not resampled"
3. Recovery of Approximate Resampling Rates
Our previous method can detect only the resampling factors that corresponds to the provided zeroing masks. To detect more resampling factors, one must provide more zeroing masks; thus, the required detection time is proportional to the number of provided zeroing masks. As a result, the detectable resampling factors are limited. In this section, we present an approximate detection method that can detect many more resampling factors than the previous method using the same set of zeroing masks.
Assume that y = ( y 1 , y 2 , y 3 , …) is a resampled signal of the origin signal x = ( x 1 , x 2 , x 3 ,…) with the resampling factor p / q ; thus, y = Ap/q x . Let y [ α .. β ] denotes the sub-signal ( yα , yα +1 , yα +2 , …, yβ ) of y. Then, by (23), for any nonzero integer k , the convolution value Conv( Mp/q , y , 1+ kp ), which is defined in (24), of a sub-signal y [1+ kp ..1+( k +1) p ] with the zeroing mask Mp/q must be zero.
PPT Slide
Lager Image
Table 1 (a) shows an original signal x , and Table 1 (b) shows a resampled signal y of x with factor 4/3. The convolution value Conv ( M 4/3 , y, 1+4 k ) of the sub-signals y[1+4 k .. 5+4 k ] (or y [1..5], y [5..9], y [9..13],…) with the zeroing mask M 4/3 shown in Table 1 (c) must be zero. In this example,
PPT Slide
Lager Image
but
PPT Slide
Lager Image
Table 1 (d) provides more values for more sub-sequences.
(a) signalx; (b) signaly; (c) zeroing maskM4/3; (d) convolution values ofywithM4/3
PPT Slide
Lager Image
(a) signal x; (b) signal y; (c) zeroing mask M4/3; (d) convolution values of y with M4/3
Table 1 (d) shows that Conv ( M 4/3 , y , i ) = 0 for only i = 1+ 4 k , i.e., the convolution value of zero appears periodically. Therefore, the previously proposed method can detect an image if it is resampled by a factor that corresponds to a provided zeroing mask for detection, and simultaneously, it can correctly detect the resampling factor. The recovery rate approaches 99%. In our experiment, we follow our previous work [20] with the considered factors p / q , where 1 ≤ q ˂ p ≤ 12, such that q = 1 or p and q are coprime (or relatively prime) positive integers. Thus, there are 45 zeroing masks for the 45 provided factors for detection. As previously mentioned, this method is limited. It can only detect a provided fixed set of resampling factors. To overcome this limitation, we propose an approximate detection mechanism to detect many more resampling factors than those whose zeroing masks are provided. First, we will describe how to use the 45 zeroing masks to detect a wider range of resampling factors.
For example, the signal z shown in Table 2 (a) is a resampled signal of the original signal x in Table 1 (a) with the resampling factor 13/10, whose resampling rate can be successfully detected if the zeroing mask M 13/10 is provided. However, the detection will fail because the zeroing mask M 13/10 is not included in the set of zeroing masks.
(a) signalz; (b) convolution values ofzwithM4/3
PPT Slide
Lager Image
(a) signal z; (b) convolution values of z with M4/3
The resampled signals y and z are shown in Table 3 ( x 0 is a dummy signal). The composition coefficients are periodic and symmetric in each period, such as those of y [1..5], y [5..9], and z [1..14]. Although y [1..5] and y [5..9] are compositions of different portions of the original signal x , they can both be zeroed using the zeroing mask M 4/3 . It can be further observed that the composition coefficients in a prefix and a postfix of a period of z are near those in each period of y. For example, the composition coefficients in z [1..5] (a prefix of z [1..14]) and those in z [10..14] (a postfix of z [1..14]) are near those in y [1..5].
(a) relations of the resampled signalyand the original signalxthrough the resampling factor 4/3; (b) relations of the resampled signalzand the original signalxthrough the resampling factor 13/10
PPT Slide
Lager Image
(a) relations of the resampled signal y and the original signal x through the resampling factor 4/3; (b) relations of the resampled signal z and the original signal x through the resampling factor 13/10
Thus, if we let yi = aixr (i) + (1- ai ) x r(i)+1 and zi = bixs (i) + (1- bi ) x s(i)+1 , then ai bi for i = 1, 2, …, 5 and ai bi +9 , i = 1, 2, …, 5. The prefix sub-signal z [1..5] has a similar composition relation to y [1..5]. In other words, z [1..5] and y [1..5] have notably similar sets of coefficients. Because the set of coefficients for z [10..14] is symmetric to the set of coefficients for z [1..5] and the coefficients in each set are symmetric, z [10..14] and y [1..5] also have similar sets of coefficients. Therefore, the convolution values of z [1..5] and z [10..14] with the zeroing mask M 4/3 are near zero. In general, the convolution values of the prefix sub-signal z [1+13 k ..5+13 k ] and the postfix sub-signal z [10+13 k ..14+13 k ] of each sub-signal z [1+13 k ..14+13 k ] can be approximately zeroed using the zeroing mask M 4/3 .
According to the above observation, we expect that the resampled signal z can be approximately zeroed periodically. For example, the small convolution values Conv( M 4/3 , z , i ) would appear for i = 1, 10, 14, 23, …, 1+13 k , 10+13 k , …, as shown in Table 2 (b). This fact can be used for the approximate resampling detection. In general, we assume that the signal z is the resampled signal of x with a resampling factor p ’/ q ’. When detecting signal z using the zeroing mask Mp/q , where p ’ ˃ p , the small convolution values Conv( Mp/q , z , i ) will appear for i = 1, p ’ – p , p ’, 2 p ’ – p , …, kp ’, ( k +1) p ’ – p , …. We define a convolution score cs in (25). Here, we set t = 4, so that the convolution score is 1 for a small convolution value and 0 otherwise. Table 4 shows the convolution scores of a sequence of samples in the resampled signal z with the zeroing mask M 4/3 . Fig. 1 illustrates an ideal sketch of cs of a signal that is resampled using factor p ’/ q ’ and the zeroing mask Mp/q .
convolution values and the corresponding scores.
PPT Slide
Lager Image
convolution values and the corresponding scores.
PPT Slide
Lager Image
An ideal sketch of cs(Mp/q, z, i).
If we calculate the difference of the consecutive indices i ’ s where the scores of 1 (or small convolution values) appear, we can obtain the sequence p ’- p , p , p ’- p , p , p ’- p , p , … Moreover the values p ’- p and p can be extracted. Because p and q are known, and p ’ can be calculated using p ’ = ( p ’- p ) + p , q ’ can be approximately calculated using q ’ = round ( p ’( q / p )) because of the assumption of p ’/ q ’ ≒ p / q . For example, if p / q = 4/3 and p ’/ q ’ = 13/10 (initially, the factor p ’/ q ’ is unknown), the scores of 1 will appear in i = 0, 9, 13, 22, 26, 35, 39, …, and the differences of two consecutive indices are 9, 4, 9, 4, 9, 4, …. We can obtain p ’ = 13 for p = 4 and p ’- p = 9. Then, q ’ = round ( p ’( q / p )) = round (13(3/4)) = round(9.75) = 10. Therefore, we have the detected resampling factor p ’/ q ’ = 13/10.
PPT Slide
Lager Image
The proposed method to detect the approximate factor is as follows. We assume that the desired detected image is resampled using some unknown factor f = p ’/ q ’, whose corresponding zeroing mask is not included in the provided set and f satisfies 12/11 ˂ f ˂ 12, where 12/11 and 12 are the minimum and maximum values, respectively, of the factors that correspond to the 45 provided zeroing masks. The detections for horizontal resampling and vertical resampling are similar. Here, we only discuss the former. When the zeroing mask Mp/q is used to detect an image I , the scores are evaluated, and the positions where 1s occur are extracted. The detection method is successful if the resampling factor is near one in the set of 45 factors; otherwise it tends to fail. In fact, the 45 factors are unevenly distributed on the interval [1, 12]. If we plot the factor values on the real line, and if f falls in a sparse region, the detection tends to fail. Half of the factors are in the subinterval [1, 2], and only 11 factors fall in [4, 12]. For f = 1.82, because it is in a dense region, where the two factors 9/5 and 11/6 are notably near it, it can be successfully detected. For f = 6.5, because it is in a sparse region and neither of the closest factors (6 and 7) is sufficiently near it, the detection will fail. To address this problem, we add two zeroing masks, M 19/3 and M 20/3 , for detection, the factors of which are both near 6.5. Similarly, in other sparse regions, we add some more corresponding zeroing masks, to raise the detection rate. For each sparse region [ j , j +1], j = 6, 7, …, 11, we add two factors j + 1/3 and j + 2/3. Thus, 12 zeroing masks are derived and added to the set of zeroing masks for detection. As a result, there are 57 (= 45 + 12) provided zeroing masks for detection, so that the resampling factors between 12/11 and 12 can be detected. This set is sufficient for practical use.
4. Experimental Results
In our experiments, 100 natural images were used for testing. Each of these 100 images was first resampled using one of 110 different resampling factors, which rangd from 1.1 to 12 with a step size of 0.1. As a result, there were 11,000 resampled test images. The exact detection is always performed first. If the exact detection fails, the approximate detection is performed. If an image is resampled using a factor that corresponds to one of the provided zeroing masks, it can be 100% successfully detected in the first stage. Otherwise, it would be successfully approximately detected in the second stage if its resampling rate is near one of the factors that correspond to the provided zeroing masks. As defined in (26), the error rate of the detected factor in this example is 10%. The recovery rates of the factors vs. the tolerance of error rates, which ranged from 1.1 to 3.0, are illustrated in Fig. 2 . We can observe that a higher error rate for tolerance corresponds to a higher recovery rate.
PPT Slide
Lager Image
PPT Slide
Lager Image
Recovery rates vs. tolerance of error rates.
For a resampled image whose resampling factor is not sufficiently near the factor of any provided zeroing mask, the approximate detection tends to fail. This problem can be addressed by providing more zeroing masks so that the resampling factors of all provided masks are distributed over the specific interval with no sparse portions. Because 1 ≤ q ˂ p ≤ 12, the minimum and maximum values of the provided p / q are 12/11 and 12, respectively, and there are 45 factors in the interval [1, 12]. More than half of the provided factors are in the interval [1, 3], and the remainder is sparsely distributed in the interval [3, 12]. A factor in [3, 12] is likely far from all provided factors and may be more difficult to detect. To address this problem, we provide some more zeroing masks for the factors in the interval [3, 12], as follows. In the interval [ k , k +1], 6 ≤ k ≤ 11, zeroing masks are added for factors k +1/3 and k + 2/3. As a result, 12 zeroing masks are added, and the total number of zeroing masks for detection is increased to 57.
After adding 12 more zeroing masks to eliminate the sparse regions in the interval [1.1, 12], any resampling factor in the interval [1.1, 12] is near at least one of the factors that correspond to the provided zeroing masks, so that it can be detected.
Figs. 3 (a)-(c) and 3(d)-(f) show the recovery rates for the resampling factors in [6, 12] using the set of 45 zeroing masks and the increased set of 57 zeroing masks, respectively. The use of more zeroing masks indeed improves the recovery rates. As shown in Fig. 3 (a), with 45 zeroing masks, the recovery rates with a tolerance of 0% error rate for the resampling factors 6.3 and 6.6 are 0% and 1%, respectively. As shown in Fig. 3 (d), with 57 zeroing masks, the detection rates with a tolerance of 0% error rate for the resampling factors 6.3 and 6.6 are increased to 35% and 22%, respectively.
PPT Slide
Lager Image
(a)-(c) detection results with 45 zeroing masks (d)-(f) detection results with 57 zeroing masks.
As shown in Table 5 , the recovery rate for the resampling factors is up to 97.74%, with a tolerance of error rate of 20%. However, the detection rate of resampling without any tolerance is 100%.
Recovery rates of resampling factors vs. tolerance of error rates (11100 test images).
PPT Slide
Lager Image
Recovery rates of resampling factors vs. tolerance of error rates (11100 test images).
In most cases, the errors are produced by the “round” operation. For example, when performing the approximate detection on an image that was resampled using a factor of 2.1 (= 21/10) with the zeroing mask of factor 2, which is near 2.1, the periodicity of p ’ = 21 is found, and q ’ is evaluated as round (21/2) = round (10.5) = 11 to yield the approximate factor 21/11 (≒1.9).
PPT Slide
Lager Image
Sketch of recovery rates of resampling factors vs. tolerance of error rates
5. Conclusion and Future Work
Improving upon our previous work, we have presented a new method to detect image resampling and recover the resampling factors, which detects many more resampling factors using the same set of zeroing masks. This improved method detects image resampling by checking for some periodicity that is generated by convolution with zeroing masks using an approximate mechanism. The proposed method detects whether an image has been resampled and recovers an approximate corresponding resampling factor.
Although the method that was proposed by Lien et al. [19] can recover the resampling factors, it can only recover the resampling factors whose weighting tables are provided, and it must use weighting tables to recover the possible original image and examine the periodicity. Furthermore, their work is notably time-consuming, and false positives may occur when the set of weighting tables is not sorted in specific orders.
Although our previous work is much more efficient and effective than the method proposed by Popescu and Farid [1] , it can only detect the resampling factors that correspond to the factors of the provided zeroing masks. For example, 57 factors in the interval [1.1, 12] were used in the experiment. Associated with the approximation detection mechanism, the proposed method in this paper can detect all resampling factors in the interval [1.1, 12]. Theoretically, there is an infinite number, many more than 57, of factors in the interval [1.1, 12]. The experimental results have demonstrated that the proposed method is indeed effective and efficient. The accuracy rate for resampling detection is 100%. The recovery rates for the resampling factors are 46.31%, 59.13 %, 82.58 %, 92.17 %, and 97.74% for tolerance of error rates of 0%, 5%, 10%, 15%, and 20% respectively. Many false positives are generated for the test images that are too smooth because the resampling score for a smooth region with a zeroing mask tends to be high. Thus, images that are too smooth are likely to be zeroed using any zeroing mask. The average time required to detect an image is 0.52 seconds. In the future, we would like to improve our method to combat other types of modifications, such as rotation, Gaussian noise, and gamma correction.
BIO
Ching-Ting Tu received her B.S. and Ph.D. degrees in computer science and information engineering from National Cheng Kung University, Tainan, Taiwan, in 2004 and 2010. In 2011, she joined the department of computer science and information engineering at Tamkang University, Taiwan, as an assistant professor. Her research interests include computer vision and pattern recognition, human-computer interaction, and multimedia information analysis and retrieval.
Hwei-Jen Lin received the B.S. degree in Applied Mathematics from National Chiao Tung University, Hsinchu, Taiwan in 1981 and the M.S. and the Ph.D. degrees in Mathematics from Northeastern University, Boston, U.S.A. in 1983 and 1989, respectively. She is currently a professor at the department of computer science and information engineering of Tamkang University. Her current research interests include Pattern Recognition, Image Processing, and Computer Algorithms.
Fu-Wen Yang received the B.S. degree in Industrial Education from National Taiwan Normal University, Taipei, Taiwan in 1988 and the M.S. and the Ph.D. degrees in Information Engineering from Tamkang University, Taipei, Taiwan in 1998 and 2005, respectively. He is currently a teacher at the Department of Information Engineering of New Taipei Municipal Tam-Shui Vocational High School, and a part-time assistant professor at the department of computer science and information engineering of Tamkang University as well. His research interests include image processing, pattern recognition and computational intelligence.
Hsiao-Wei Chang received the B.S. degree in Applied Mathematics from Fu-Jen Catholic University, Taipei, Taiwan in 1980, the M.S. degree in Computer Science from Texas A&I University, Texas, U.S.A. in 1986 and the Ph.D. degree in Computer Science and Information Engineering from Tamkang University, Taipei, Taiwan, R.O.C. in 2011. He is currently an associate professor at the department of computer science and information engineering of China University of Science and Technology, Taipei, Taiwan. His current research interests include Pattern Recognition, Image Processing and Logic Design.
References
Popescu A. C. , Farid H. 2005 “Exposing digital forgeries by detecting traces of resampling” IEEE Transactions on Signal Processing Article (CrossRef Link) 53 758 - 767    DOI : 10.1109/TSP.2004.839932
Kirchner M. 2008 “Fast and reliable resampling detection by spectral analysis of fixed linear predictor residue” in Proc. of ACM Multimedia and Security Workshop Article (CrossRef Link) 11 - 20
Nillius Peter , Eklundh Jan-Olof 2001 “Automatic estimation of the projected light source direction” in Proc. of 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Vol. 1, Article (CrossRef Link) 1076 - 1083
Johnson M. K. , Farid H. 2005 “Exposing digital forgeries by detecting inconsistencies in lighting” in Proc. of ACM Multimedia and Security Workshop, New York Article (CrossRef Link) 1 - 9
Li Kwang-Fu , Chen Tung-Shou , Wu Seng-Cheng 2001 “Image tamper detection and recovery system based on Discrete Wavelet Transformation” in Proc. of 2001 IEEE Pacific Rim Conference on Intelligent Conference Communications, Computers and Signal Processing Vol. 1, Article (CrossRef Link) 26 - 28
Lin Phen Lan , Hsieh Chung-Kai , Huang Po-Whei 2005 “A hierarchical digital watermarking method for image tamper detection and recovery” Pattern Recognition Article (CrossRef Link) 38 (12) 2519 - 2529    DOI : 10.1016/j.patcog.2005.02.007
Wang Ming-Shi , Chen Wei-Che 2007 “A majority-voting based watermarking scheme for color image tamper detection and recovery” Computer Standards & Interfaces Article (CrossRef Link) 29 (5) 561 - 570    DOI : 10.1016/j.csi.2006.11.009
Johnson M. K. , Farid H. 2006 “Exposing digital forgeries through chromatic aberration” in Proc. of ACM Multimedia and Security Workshop New York Article (CrossRef Link) 48 - 55
Khanna N. , Mikkilineni A. K. , Chiu G. T. C. , Allebach J. P. , Delp E. J. 2007 “Scanner identification using sensor pattern noise” in Proc. of the SPIE International Conference on Security, Steganography, and Watermarking of Multimedia Contents IX Vol. 6505, No. 1, Article (CrossRef Link) 65051K -
Lukas J. , Fridich J. , Goljan M. 2006 “Detecting digital image forgeries using sensor pattern noise” in Proc. of the SPIE Conference on Security, Steganography, and Watermarking of Multimedia Contents Vol. 6072, Article (CrossRef Link) 362 - 372
Lukas J. , Fridrich J. , Goljan M. “Determining digital image origin using sensor imperfections” in Proc. of SPIE Electronic Imaging, Image and Video Communication and Processing January 16-20, 2005 Article (CrossRef Link) 249 - 260
Khanna N. , Chiu G. T. C. , Allebach J. P. , Delp E. J. 2008 “Scanner identification with extension to forgery detection” in Proc. of SPIE Electronic Imaging San Jose, CA Vol. 6819, Article (CrossRef Link)
Gopi E. S. , Lakshmanan N. , Gokul T. , KumaraGanesh S. , Shah P. R. “Digital Image Forgery Detection using Artificial Neural Network and Auto Regressive Coefficients” in Proc. of Electrical and Computer Engineering, 2006 Canadian Conference (CCECE’06) May 7-10, 2006 Article (CrossRef Link) 194 - 197
Popescu A. C. , Farid H. 2004 “Exposing digital forgeries by detecting duplicated image regions” Dartmouth College, Computer Science Technical Report, TR2004-515 Article (CrossRef Link)
Li Guohui , Wu Qiong , Tu Dan , Sun Shaojie “A sorted neighborhood approach for detecting duplicated regions in image forgeries based on DWT and SVD” in Proc. of IEEE International Conference on Multimedia and Expo. Beijing China July 2-5, 2007 Article (CrossRef Link) 1750 - 1753
Luo Weiqi , Huang Jiwu , Qiu Guiping 2006 “Robust detection of region-duplication forgery in digital image” in Proc. of the 18th International Conference on Pattern Recognition Vol. 4, Article (CrossRef Link) 746 - 749
Lin Hwei-Jen , Wang Chun-Wei , Kao Yang-Ta 2009 “Fast copy-move forgery detection” WSEAS Transactions on Signal Processing Article (CrossRef Link) 5 (5) 188 - 197
Myna A. N. , Venkateshmurthy M. G. , Patil C. G. “Detection of region duplication forgery in digital images using Wavelets and Log-Polar Mapping” in Proc. of the International Conference on Computational Intelligence and Multimedia Applications (ICCIMA 2007) December 13-15, 2007 Article (CrossRef Link) 371 - 377
Lien Cheng-Chang , Shih Cheng-Lun , Chou Chih-Hsun 2010 “Fast Forgery Detection with the Intrinsic Resampling Properties” Journal of Information Security Article (CrossRef Link) 1 11 - 22    DOI : 10.4236/jis.2010.11002
Kao Y. T. , Lin H. J. , Wang C. W. , Pai Y. C. 2012 “Effective Detection for Linear Up-Resampling by Factor of Fraction” IEEE Transactions on Image Processing Article (CrossRef Link) 21 (8) 3443 - 3453    DOI : 10.1109/TIP.2012.2191562