Fast Detection of Copy-Move Forgery Image using DCT
Yong-Dal Shin†
ABSTRACT
In this paper, we proposed a fast detection method of copy-move forgery image based on low frequency coefficients of the DCT coefficients. We proposed a new matching criterion of copy-moved forgery image detection (MCD) using discrete cosine transform. For each 8×8 pixel block, the DCT transform is calculated. Our algorithm uses low frequency four (DC, 3 AC coefficient) and six coefficients (DC, 5 AC coefficients) of DCT per 8×8 pixel block. Our algorithm worked block matching for DCT coefficients of the 8×8 pixel block is slid by one pixel along the image from the upper left corner to the lower right corner. Our algorithm can reduce computational complexity more than conventional copy moved forgery detection algorithms.
Key words: DCT, copy-move forgery image, matching criterion
※ Corresponding Author : Yong-Dal Shin, Address : 12-1 Seolgye-ri Youngdong-eup Youngdong-gun Choongbuk Korea, TEL : +82-43-740-1145, FAX : +82- 43-740-1139, E-mail : [email protected]
Receipt date : Dec. 22, 2011, Revision date : Feb. 15, 2012 Approval date : Mar. 26, 2012
†Dept. of IT & Securities, Youngdong University, Korea
1. INTRODUCTION
Advanced digital cameras and photo-editing software packages (such as PhotoShop, Paintshop pro) make it relatively easy to create digital image forgeries [1-3]. There has been some effort in the digital signature or watermarking communities to detect and locate image manipulation. But the limi- tation in digital signature or watermarking tech- nology is that the media data must be pre-proc- essed when it is established, such as calculating hash values, or embedding watermark in the im- ages [4].
Recently, various techniques for tamper or for- gery detection or even recovery have been pro- posed in the literature [5,6]. Some techniques have been proposed for image tamper detection [7].
Various watermark techniques [8] have been pro- posed in recently years, which can be used not only for authentication, but also for being an evidence
for the tamper detection [5]. Watermark techniques embedded watermarks consisting of the authenti- cation data and the recovery data into image blocks for image tamper detection and recovery in the fu- ture [5].
A common form of digital tampering is Copy- Move forgery, in which a part of the image itself is copied and pasted into another part of the same image to conceal an important object [4]. Because the copied part come from the same image, its im- portant properties, such as noise, color and texture, will be compatible with the rest of the image and thus will be more difficult to distinguish and detect.
Several researchers have developed techniques for detection this form of image forgery [4]. Since the key characteristics of Copy-Move forgery is that the copied part and the pasted part are in the same image, a direct method, this forgery is exhaustive search [1], but it is computationally complex. J.
Fridrich [1] proposed exact match for detection and an effective blocking approach, in which the image blocks are represented by quantized DCT (discrete cosine transform) coefficients, and a lexicographic sort is adopted to detect the Copy-Move blocks [1,2]. A. C. Popescu [2] worked by applying a prin- cipal component analysis (PCA) on small fixed size image blocks to yield a reduced dimension repre-
sentation. Jeong [7] developed detection of copy- move forgery image in wavelet transform domain.
In most methods of copy-move forgery de- tection, the detected image is divided into over- lapping blocks, which are then represented as vec- tors, which are then lexicographically sorted for later detection. Suppose a detected image of size N×N is divided into (N-b+1)2 overlapping blocks of size b×b, which are represented as vectors of b2dimension, and sorted in a lexicographically or- der [5].
In this paper, we proposed a fast detection meth- od of copy-move forgery image based on low fre- quency coefficients of the DCT coefficients. We proposed a new fast detection algorithm using matching criterion of copy-moved forgery image detection (MCD). The proposed method used DCT (Discrete Cosine Transform) with 8×8 pixel block.
For each 8×8 pixel block, the DCT transform is calculated, DCT coefficients of the 8×8 pixel block is slid by one pixel along the image from the upper left corner to the lower right corner. MCD of our algorithm uses low frequency four (DC, 3 AC co- efficient) and six coefficients (DC, 5 AC coeffi- cients) of DCT per 8×8 pixel block. Our algorithm can reduced computational complexity more than conventional copy move forgery detection algo- rithms.
2. RELATED COPY-MOVE FORGERY [1,9]
In a Copy-Move forgery, a part of the image it- self is copied and pasted into another part of the same image. This is usually performed with the intention to make an object "disappear" from the image by covering it with a segment copied from another part of the image [1]. Textured areas, such as grass, foliage, gravel, or fabric with irregular patterns, are ideal for this propose because the cop- ied areas will likely blend with the background and the human eye cannot easily discern any suspi- cious artifacts [1]. Because the copied parts come from the same image, its noise component, color
palette, dynamic range, and most other important properties will be compatible with the rest of the image and thus will not be detectable using meth- ods that look for incompatibilities in statistical measures in different parts of the image [1]. To make the forgery even harder to detect, one can use the feathered crop or the retouch tool to further mask any traces of the copied-and-moved seg- ments [1].
Any Copy-Move forgery introduces a correla- tion the original image segment and the pasted one.
This correlation can be used as a basis for suc- cessful detection of this type of forgery. The algo- rithms for detection of the Copy-Move forgery are developed -one that uses an exact match for de- tection and one that is based on an approximate match [1].
Before describing the best approach based on approximate block matching that produced the best balance between performance and complexity, two other approaches were investigated-Exhaustive search and Autocorrelation [1].
The Exhausted search is most obvious approach method. In this method, the image and its circularly shifted version are overlaid looking for closely matching image segments. Let us assume that xij
is the pixel value of a gray scale image of size M× N at the position i, j. In the exhaustive search, the following difference are examined [1]:
m od m od k=0,1,….M-1, l=0,1,
….N-1 for all I, and j, (1)
The autocorrelation of the image xof the size M×N is defined by the formula [1] :
i,k=0,…M-1, j,l=0, … ,N-1. (2)
The correlation can be efficiently implemented using the Fourier transform utilizing the fact that
* , where =0,… , M-1,
0, …, N-1. Thus we have
(3)
where denotes the Fourier transform [1].
S. Kahn et. Al [9] proposed an efficient method for detection of copy-move forgery using discrete wavelet transform. The work on "Detection of copy-move forgery in digital images"is im- plemented in two phase as described below. The first phase deals with detection of reference and matching blocks on the lowest level of wavelet transform compressed image. The second phase deals with checking on different discrete wavelet transform (DWT) levels to produce more robust output. The first phase is expressed as described that [9].
Red Green Blue color input image, Gray scale conversion, Discrete Wavelet Transform, Overlap- ping block pixel into a matrix, Maximum contrast blocks selection, Matrix sorting, Phase correlation calculation between rows, Candidate block coor- dinates into a new matrix, Find Candidate blocks.
The second phase is expressed as described that [9]. Candidate block, Candidate blocks as regions in LLL-1 image, Region dividing into blocks and comparison, Region comparison directly on LLL-2
image, Region comparison directly on original im- age and duplicated blocks detection.
The related conventional algorithms [1,2,9] need more computational complexity.
3. THE PROPOSED METHOD
Any copy-moved forgery introduces a correla- tion between the original image segment and the pasted one. This can be used as a basis for a suc- cessful detection of this type of forgery.
Our algorithm is as follow. For each 8×8 pixel block, DCT transform is calculated. DCT coeffi- cients of the 8×8 pixel block are slid by one pixel along the image from the upper left corner to the lower right corner.
DCT algorithm [10] transforms signal/image data from the spatial/time domain to the frequency domain. For most images, much of the signal en-
ergy lies at low frequencies; these appear in the upper left corner of the DCT such as DCT six co- efficients of Fig. 1. Compression is achieved since the lower right values represent higher frequen- cies, and are often small - small enough to be ne- glected with little visible distortion. DCT transform algorithm is equation (4) [10].
cos cos
(4)
for
for , B is a block size of DCT.Inverse DCT (IDCT) is
cos cos
(5)
The Transform coefficients for U=0 is the aver- age value of the B×B pixel block. This value is the referred to as the DC coefficients. All other co- efficients are called the AC coefficients.
The matching criterion of copy-moved forgery image detection (MCD) using DCT coefficients for block image as follow.
, (6) is DCT coefficients, i=0,1, j=0,1. The i, j are DCT four coefficients of 8×8 pixel block. m, n=0,1,2
……(N-B+1) for N×N image. is DCT co- efficients, i=0,1, j=0,1 for low 4 coefficients and i=0,1,2, j=0,1,2, for 6 coefficients, except (2,1), (1,2), (2,2). The i, j are DCT six coefficients of 8×8 pixel block. m, n=0,1,2……(N-B+1) for N×N image.
The MCD is a matching criterion of copy-moved forgery image detection. is DCT coefficients of the 8×8 pixel block of full size image N×N at the position i, j.
Fig. 1 show DCT 4-low frequency (0,1,2,3) and DCT 6-low frequency (0,1,2,3,4,5) coefficients. Our
(a) Original Image (b) Copy-Move forgery (c) Detection Copy-Move forgery (Black box)
Fig. 2. Lena image algorithm use four(DC, 3AC, (0,1,2,3)) and six co-
efficients (DC, 5 AC ( 0,1,2,3,4,5)) of the DCT co- efficients for 8×8 block.
In order to compute MCD for full image (256×
256), DCT coefficients of the 8×8 pixel block is slid by one pixel along the image from the upper left corner to the lower right corner.
The proposed algorithm for detection of copy- moved forgery image is as follows:
If (MCD == 0.0) copy-move block
else (7)
not copy-move block
0 1 4
2 3
5
Fig. 1. DCT four (0,1,2,3) and six (0,1,2,3,4,5) low frequency coefficients for 8×8 pixel block.
From equation (7), if the value of MCD were 0.0, the block is a copy-move forgery block. Because the equation (6) is 0, copy block image is same moved block image. If the value of MCD were not 0.0, block is not copy-move forgery block. Because te equation (6) is not 0.0, the block image is not equal copy-moved block image.
4. EXPERIMENTAL RESULTS
We have implemented the detection algorithm in C language and tested copy-moved forged some test images. The size of test images [11] are 8 bits, 256×256 pixels. The test images were cropped. We have tampered Lena, Man, 3-Car, Tank images by copy-moved one image block over another, in the same image.
The images are scanned from the upper left cor- ner to the lower right corner while sliding a 8×8 block. For each block, the DCT transform is calcu- lated. The matching criterion of copy-moved for- gery image detection (MCD) used equation (7) based on DCT four coefficients and DCT six co- efficients (Fig. 1). From equation (7), if the value of MCD were 0.0, the block is a copy-move forgery block. Because sum of difference for block is 0, copy block image is same moved block image. If the value of MCD were not 0.0, the block is not copy-move forgery block. Because sum of differ- ence for block is not 0.0, the block image is not equal copy-moved block image.
In this paper, the computation number of the DCT coefficients need four and six, and the block computation number per one block in order to de- tect copy-move forgery block is (N-B+1)× (N-B+
1) for N×N image.
Fig. 2 and 3 show original Lena and Man original images, copy-move forgery image, detection of copy-move forgery image. From figure 2(c), 3(c), upper black rectangular (64×64) is copied block, the
(a) Original Image (b) Copy-Move forgery (c) Detection Copy-Move forgery (Black box)
Fig. 3. Man image
(a) Original Image (b) Copy-Move forgery (c) Detection Copy-Move forgery (Black box)
Fig. 4. 3-Car image
(a) Original Image (b) Copy-Move forgery (c) Detection Copy-Move forgery (Black box)
Fig. 5. Tank image other black rectangular (64×64) is a moved forgery
image. The figure 2(c) and 3(c) used four (01,2,3) low frequency DCT coefficients of 8×8 pixel block.
From figure 2(c), 3(c), the duplication image show copy-move forgery images perfectly (100% for- gery image detection).
Fig. 4 and 5 show original 3-Car and Tank orig- inal images, copy-move forgery image, detection of copy-move forgery image. From figure 4(c), 5(c), upper black rectangular is copied block, the lower black rectangular is a moved forgery image.
The figure 2(c), 3(c), 4(c), and 5(c) used four (0,1,2,3) low frequency DCT coefficients of 8×8 pixel block. From figure 2(c), 3(c), 4(c), and 5(c), the duplication images show copy-move forgery images perfectly (100% forgery image detection).
Because the proposed MCD used four (0,1,2,3 of Fig. 1, DCT-4 low frequency of Tab1e 1) and six (0,1,2,3,4,5 of Fig. 1, DCT-6 low frequency of Table 1) low frequency coefficients of DCT. If the value of 8×8 pixel block MCD was 0.0, the 8×8 pixel block is a copy-move forgery block. Because sum of dif-
Table 1. Comparison results of other methods for test images
Algorithms Image
representation Block size Block number Feature
dimension Computation complexity (reference [1])
Fridrich[1] DCT 8×8 (256-8+1) 2 64 100.0 %
Popescu[2] PCA 8×8 (256-8+1) 2 32 50.00%
Kahn[9] DWT 8×8 (128-8+1) 2 64 26.01%
Proposed-1 DCT-6 low
frequency 8×8 (256-8+1) 2 6 9.37%
Proposed-2 DCT-4 low
frequency 8×8 (256-8+1) 2 4 6.25 %
ference for 8×8 pixel block is 0, copy block image is same moved block image.
The discrete cosine transform (DCT) helps sep- arate the image into parts (or spectral sub-bands) of differing importance (with respect to the im- age's visual quality). The DCT transforms a signal or image from the spatial domain to the frequency domain. The criterion of detection of copy-moved forgery using DCT coefficients is sufficient by four and six coefficients instead of 64 coefficients for 8×8 pixel block to reduce computation complexity.
The table 1 shows computation complexity for test images (256×256) [5,9].
From Table 1, the computation complexity for the proposed method compared to Fridrich[1], Popescu[2], and Kahn[9].
Total Complexity for 256×256 image of the pro- posed method was reduced 93.75% than Fridrich [1]. Therefore, the computation complexity of our algorithm more efficient than conventional algo- rithms [1,2,9].
5. CONCLUSION
In this paper, we proposed a fast detection meth- od of copy-move forgery image based on low fre- quency coefficients of the DCT coefficients. We proposed a new matching criterion of copy-moved forgery image detection (MCD) using DCT. The proposed method used DCT (Discrete Cosine Transform) with 8×8 pixel block. For each 8×8 pixel block, the DCT transform is calculated. Our
algorithm uses low frequency four (DC, 3 AC co- efficient) and six coefficients(DC, 5 AC co- efficients) of DCT per 8×8 pixel block. Our algo- rithm worked block matching for DCT coefficients of the 8×8 pixel block is slid by one pixel along the image from the upper left corner to the lower right corner. Our algorithm can reduce computa- tional complexity more than conventional copy moved forgery detection algorithms.
6. REFERENCES
[ 1 ] J. Fridrich, D. Soukal, and J. Lukas “Detection of Copy-Move Forgery in Digital Images,”
Proc. of Digital Forensic Research Work- shop, pp. 55-61, 2003.
[ 2 ] A.C. Popescu and H. Farid, “Exposing Digital Forgeries by Detecting Duplicated Image Re- gions,” Dartmouth College, Hanover, New Hampshire, USA:TR2004-515, 2004.
[ 3 ] J. Zhang, Z. Feng, and Y. Su, “A New Appro- ach for Detecting Copy-Move Forgery in Dig- ital Images,” 11thIEEE Singapore Internatio- nal Conference on Communication Systems pp. 362-366, 2008.
[ 4 ] E.S. Khan and E.A. Kulkarni, “An Efficient Method for Detection of Copy-Move Forgery using Discrete Wavelet Transform,” Interna- tional J ournal of Computer Science and Engineering, Vol. 2, No. 5, pp. 1801-1806, 2010.
[ 5 ] H.J. Lin, C.W. Wang, and Y.T. Kao, “Fast
Copy-Move Forgery Detection,” WSEAS Transaction on Signal Processing, Vol. 5, Issue 5, pp. 188-197, 2009.
[ 6 ] Y.D. Shin, “Fast Detection of Copy-Move Forgery Image using Three Step Search Algorithm in the Spatial Domain,” ICHIT2012, Lecture Note in Compute Science 7425, pp.
389-395, 2012.
[ 7 ] B.G. Jeong and I.K. Eom, “Detection of Copy- Move Forgery Image Wavelet Domain,” Proc.
of the 23-th Korean Signal Processing Conference, Vol. 23, pp. 1-2, 2010.
[ 8 ] K.R. Kwon, B.H. Koo, and J.H. Kim,
“Multimedia Image Processing : Adaptive Digital Watermarking for Copyright Protection of CAD Data,”J ournal of Korea Multimedia Society, Vol. 9, No. 6, pp. 709-719, 2006.
[ 9 ] S. Kahn and A. Kulkarni, “Reduced Time Complexity for Detection of Copy-Move For- gery using Discrete Wavelet Transform,”
International Journal of Computer Applica- tions, Vol. 6, No. 7, pp. 31-36, 2010.
[10] P. Yip and K. Rao. Discrete Cosine Trans- form: Algorithms, and Applications, Academic press, Boston, 1990.
[11] SIPI Image Database http://sipi.usc.edu/data base.
Yong-Dal Shin
Yong-Dal Shin is a professor in department of IT & securities at Youngdong university, Choong- pook Korea. He received PH.D.
degree from Kyungpook na- tional university, Daegu Korea, 1994. He research areas include multimedia security, digital watermarking, digital forensics.
