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.
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 imageprocessing 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 forgerydetection 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. Copymove 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 resamplingdetection 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 timeconsuming, 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 2D image can be broken down into two 1D 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 greyscaled images which are separated from the original image, individually resampled, and finally recombined to create the final image.
For 2D resampling, each dimension can be separately resampled and detected. To easily explain, we will first describe onedimensional resampling
[1]
.
Let
x
[
t
] be a 1D 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.Upsample: Create a new signalxu[pt] =x[t], wheret= 1, 2, …,n, andxu[pt] = 0 otherwise.

2.Interpolate: Convolvexu[t] with a lowpass filterh[t]:xi[t] =xu[t]*h[t].

3.Downsample: 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).
where
A_{p/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:
Here, the odd samples of the resampled signal
y
= [
y
_{1}
y
_{2}
…
y_{m}
]
^{t}
take on the values of the original signal
x
= [
x
_{1}
x
_{2}
…
x_{n}
]
^{t}
; i.e.,
y
_{2i1}
=
x_{i}
, i = 1, 2, …,
n
, where
y_{j}
=
y
[
j
] and
x_{j}
=
x
[
j
]. The even samples are the averages of the adjacent neighbors of the original signal:
where
i
= 1, 2, …,
n
1. Because
x_{i}
=
y
_{2i1}
and
x_{i}
_{+1}
=
y
_{2i+1}
, the above relationship can be expressed in terms of only the resampled samples:
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 submatrix 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
A_{p/q}
is periodically composed of its submatrix
A_{p/q}
[1..
p
, 1..
q
+1]. For example, the matrix A
_{4/3}
is periodically composed of the submatrix
A
_{4/3}
[1..4, 1..4]. This result can be described as follows.
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
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) submatrix
A_{p/q}
[1..
p
+1, 1..
q
+1] for any resampling matrix
A_{p/q}
. We called the submatrix
A_{p/q}
[1..
p
+1, 1..
q
+1] the primary submatrix of
A_{p/q}
. For simplicity, when we refer to a resampling matrix
A_{p/q}
, we mean its primary submatrix. (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,
A_{p/q}
[
i
,
j
] =
A_{p/q}
[
p
+2
i
,
q
+2
j
] for
i
= 1, 2, …,
p
+1 and
j
= 1, 2, …,
q
+1.
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
A_{p/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
A_{p/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
A_{p/q}
. Let
β_{r}
be in column
c
(
r
) of
A_{p/q}
then
A_{p/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.
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
A_{p/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−
β
_{p1i}
for
i
= 1, 2, …, ⎿(
p
−1)/2⏌.
With the above observation, we may determine the content of any resampling matrix
A_{p/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
if (
p

iq
)mod
p
˂ (
p
(
i
+1)
q
)mod
p
then
j
←
j
+1;
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:
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
F_{p/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.
which is equivalent to the convolution of
y
with
F_{p/q}
:
where
F_{p/q}
*
y
=
F_{p/q}
y
if
y
is of size (
p
+1)×1 and
F_{p/q}
y^{t}
if
y
is of size 1×(
p
+1). Assuming that
y
is of size (
p
+1)×1, substituting (1) in (12) yields:
Because the relation in (13) holds for every vector
x
,
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.
As an example, considering the resampling by a fraction of 5/3; then, (11) becomes
Substituting
y
=
A
_{5/3}
x
in (15) yields
which is equivalent to
Because (17) holds for any signal
x
, the coefficient for each
x_{i}
in (17) must be zero, i.e.,
(18) forms a system of 4 linear equations with 6 unknowns to solve the zeroing filter
F_{p/q}
and is equivalent to the relation
or the matrix equation:
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}
⋯
m_{k}
] and
M
’ = [
m
_{1}
'
m
_{2}
' ⋯
m_{k}
'] are considered equivalent if
M
=
cM
’ (or
m_{i}
/
m_{i}
' =
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 1D 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
F_{p/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).
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
F_{p/q}
for the resample factor
p
/
q
can be obtained by solving the following nonhomogeneous linear system.
where
denotes a unit column matrix with a size of
k
×1, and
F_{p/q}
= [
α
_{1}
α
_{2}
⋯
α_{p}
_{+1}
] is a row matrix of size 1×(
p
+1) that consists of
p
+1 variables. Therefore,
E_{p/q}
is a matrix of size (
q
+2)×(
p
+1) with the submatrix
at its top row, i.e.,
and
The general form of
A_{p/q}
, which is given in (9), yields the expanded form of
E_{p/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
(
upsampling 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
B_{ij}
is considered resampled by factor
p
/
q
if the convolution value
M_{p/q}
*
B_{ij}
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.
 Algorithm ZMD
Input : two positive coprime integers
p
and
q
with
p
˃
q
Output; coefficients
a
_{1}
,
a
_{2}
, …,
a_{p}
_{+1}
a
_{1}
← 1
Δ ← 1 −
β
_{1}
i
← 2
while
i
≤ ⎿(
p
+2) / 2⏌
do
k
← 1
α
←
β_{i}
while
β
_{i+k1}
≥
β
_{i+k}
do
α
←
α
+
β
_{i+k}
k
←
k
+1
a_{i}
← (−Δ) /
α
ℓ
← 1
while
ℓ
≤
k
−1
do
a_{i}
_{+ℓ}
←
a_{i}
_{+ℓ1}
ℓ
←
ℓ
+1
Δ ← ℓ
a_{i}
⋅ (
k
−
α
)
i
←
i
+
k
if
p
is odd &
i
−1 = ⎿(
p
+2) / 2⏌
then
while
i
≤
p
+1
do
a_{i}
← −
a_{p}
_{+2i}
i
←
i
−1
else
while
i
≤
p
+1 do
a_{i}
← −
a_{p}
_{+2i}
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
=
A_{p/q}
x
. Let
y
[
α
..
β
] denotes the subsignal (
y_{α}
,
y_{α}
_{+1}
,
y_{α}
_{+2}
, …,
y_{β}
) of y. Then, by (23), for any nonzero integer
k
, the convolution value Conv(
M_{p/q}
,
y
, 1+
kp
), which is defined in (24), of a subsignal
y
[1+
kp
..1+(
k
+1)
p
] with the zeroing mask
M_{p/q}
must be zero.
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 subsignals 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,
but
Table 1
(d) provides more values for more subsequences.
(a) signalx; (b) signaly; (c) zeroing maskM4/3; (d) convolution values ofywithM4/3
(a) signal x; (b) signal y; (c) zeroing mask M_{4/3}; (d) convolution values of y with M_{4/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
(a) signal z; (b) convolution values of z with M_{4/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
(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
y_{i}
=
a_{i}x_{r}
_{(i)}
+ (1
a_{i}
)
x
_{r(i)+1}
and
z_{i}
=
b_{i}x_{s}
_{(i)}
+ (1
b_{i}
)
x
_{s(i)+1}
, then
a_{i}
≒
b_{i}
for
i
= 1, 2, …, 5 and
a_{i}
≒
b_{i}
_{+9}
,
i
= 1, 2, …, 5. The prefix subsignal
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 subsignal
z
[1+13
k
..5+13
k
] and the postfix subsignal
z
[10+13
k
..14+13
k
] of each subsignal
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
M_{p/q}
, where
p
’ ˃
p
, the small convolution values Conv(
M_{p/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
M_{p/q}
.
convolution values and the corresponding scores.
convolution values and the corresponding scores.
An ideal sketch of cs(M_{p/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.
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
M_{p/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.
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.
(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).
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).
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 timeconsuming, 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
ChingTing 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, humancomputer interaction, and multimedia information analysis and retrieval.
HweiJen 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.
FuWen 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 TamShui Vocational High School, and a parttime 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.
HsiaoWei Chang received the B.S. degree in Applied Mathematics from FuJen 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.
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 JanOlof
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 KwangFu
,
Chen TungShou
,
Wu SengCheng
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 ChungKai
,
Huang PoWhei
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 MingShi
,
Chen WeiChe
2007
“A majorityvoting 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 1620, 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 710, 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, TR2004515
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 25, 2007
Article (CrossRef Link)
1750 
1753
Luo Weiqi
,
Huang Jiwu
,
Qiu Guiping
2006
“Robust detection of regionduplication forgery in digital image”
in Proc. of the 18th International Conference on Pattern Recognition
Vol. 4, Article (CrossRef Link)
746 
749
Lin HweiJen
,
Wang ChunWei
,
Kao YangTa
2009
“Fast copymove 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 LogPolar Mapping”
in Proc. of the International Conference on Computational Intelligence and Multimedia Applications (ICCIMA 2007)
December 1315, 2007
Article (CrossRef Link)
371 
377
Lien ChengChang
,
Shih ChengLun
,
Chou ChihHsun
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 UpResampling by Factor of Fraction”
IEEE Transactions on Image Processing
Article (CrossRef Link)
21
(8)
3443 
3453
DOI : 10.1109/TIP.2012.2191562