TMCnet News
A Detection Algorithm for Image Copy-move Forgery Based on Improved Circular Projection Matching and PCA [Sensors & Transducers (Canada)](Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: Because general algorithms seldom detect copy-move forgery with angle rotation and block matching algorithms are very time-consuming, this paper proposes a detection algorithm which is able to detect copymove forgery with rotation of certain angles by using the direction invariance of the circular projection vector. At the same time, considering the influence of random noise and brightness changes on the circular projection vector, circular projection vector is improved and becomes robust. In order to avoid the time-consuming, this algorithm also constructs a data matrix by using the circular projection vector of each image block to significantly reduce the dimensionality of the data requiring during principal component analysis. Its detection speed is obviously faster than general block matching algorithms. The experimental results show that the improved circular projection matching algorithm is less time consuming, able to resist a certain degree of angle rotation in copy-move operations, and relatively robust to the influence of random noise and illumination. Copyright © 2013 IFSA. Keywords: Circular projection matching, Rotation invariance, PCA, Image matching, Copy-move forgery. (ProQuest: ... denotes formulae omitted.) 1. Introduction Generally, a picture is used as the strong evidence for describing the occurrence of a thing. With the rapid development of image editing software, digital images are easily modified and it is becoming increasingly easier to generate vivid images. Forged images are more and more frequently found in tabloids, magazines and mainstream media or used as evidence submitted to courts. Some are even used in scientific frauds. Therefore, it is urgent to study image forgery detection algorithms so as to identify the authenticity and integrity of images. Detection algorithms for digital image forgery fall into two types. One includes the image authentication based on fragile watermarking and the image authentication based on digital signatures, both of which belong to the active algorithm. Watermark or auxiliary information is required to be added in advance. In the real world, however, this information cannot be added to all images in advance. Another type is the blind detection technique, a kind of passive authentication. The blind detection technique relies on the characteristics of images to authenticate them. However, due to the complex authentication method, it has become a more challenging subject and also has wider potential applications. There are a variety of methods for image forgery [9]. The copy-move forgery in the same image is common which copies and moves a portion of the image into another position so as to cover up persons or objects in the image. The detection algorithm for this kind of image forgery is a blind detection technique and has been proposed. Most of them judge the authenticity based on the characteristic that copy-move in images will result in large similar areas. Fridrich [1] first analyzed the exhaustive search algorithm and proposed a block matching detection method based on discrete cosine transform (DCT) which significantly improves the efficiency of the exhaustive search algorithm. Popescu [2] proposed a similar method which reduces the dimensionality of feature vectors by using principal component analysis (PCA) instead of discrete cosine transform. Experiments have shown that his algorithm is more efficient. Subsequently, many scholars carried out further studies on the basis of block matching algorithms. Wu Qiong [3] transformed the original image into a 1/4 similar image using discrete wavelets before partitioning, used singular value decomposition to reduce dimensionality and finally located according to the lexicographic order. Jing Li et al. [4, 10] proposed detection and location algorithm for image region duplication forgery based on phase correlation in order to overcome the low efficiency of block matching algorithms. In general, this class of algorithms does not resist rotation and noise and is time consuming. This paper mainly studies how to improve the anti-rotation and anti-noise of the algorithm and how to improve detection efficiency using grayscale information. This algorithm first divides the detected blocks by row and column, then calculates the improved circular projection vectors of the image blocks, constructs the projection data matrix of the image through the circular projection vectors of all image blocks, uses PCA to reduce the dimensionality of the matrix, sorts that matrix in the lexicographic order and finally judges whether the sorted adjacent image block is the image block that has been copied and moved by confidence distance. The flow chart of the algorithm is shown as Fig. 1 below. The reminder of this paper is organized as follows: section 2 introduces the improved circular projection matching algorithm. Application of PCA in the detection algorithm for image copy-move forgery is presented in Section 3. Experimental results and conclusion are described in Section 4 and 5 respectively. 2. The Improved Circular Projection Matching Algorithm 2.1. Conventional Pixel Matching Rotation Sensitivity Analysis Assume that f1 and f2 with the same size ofmx« are two moved image blocks in the forged image S shown as Fig. 2, where f is the copied image block and f2 is the moved and pasted image block. Conventional matching algorithms compare the copied image block fi and the pasted image block f2 in the similarity in the gray values of the corresponding pixels, and take similarity as the criterion for relevance. It is obvious that when relative rotation exists between fi and f2, corresponding pixels change. When the rotation angle is small, the algorithms can find correct matching positions due to the similarity between adjacent pixels. However, when the rotation angle is big, the difference of gray value increases and conventional matching algorithms do not work. The key to solving the angle matching problem that random angle rotation exists between the copied image fi and the pasted image f2 is to find a rotation invariant. The circular projection matching algorithm [5,6] was proposed based on the isotropy and projection features of a circle. With this algorithm, the sum of the pixels in the concentric circles with different radiuses in the circle is calculated and taken as the projection data at the radius. ... (1) where ... and R is the radius of the maximum inscribed circle of the image, shown as Fig. 3. When the image rotates, the pixels on the circle with any radius also rotate along with the radiuses of the concentric circles, so P(r) remains unchanged, which means that it is theoretically possible to realize matching of random angle rotation. 2.2. The Improved Circular Projection Matching Algorithm As a matter of fact, some problems will arise when the circular projection matching algorithm is used to detect the copy-move in the image, including changing the brightness of copied image and adding noise, which requires us to improve the circular projection matching algorithm. 2.2.1. Noise Impact Analysis and Improvement Images transmitted in channels are interfered by different kinds of noise, including the most common Gaussian impulsive noise. Gaussian impulsive noise refers to a noise signal whose frequency spectrum components are uniformly distributed (white noise) and whose amplitudes obey the Gaussian distribution. It is also addible and regarded as one kind of white noise. Literature [8] has proved that Gaussian impulsive noise does not change image gray values and it only affects the alternating current component of an image. At the same time, in analyzing each projection vector, it is found that the bigger the radius of the projection vector is, the greater the cumulative change is. In other words, the influence of the alternating current component on the image increases with the radius. Literatures [4,5] improve the algorithm by replacing the projection value with the grayscale average of each concentric circle. The component in the projection is ... (2) where S(r) is the number of pixels included in the concentric circle whose radius is r. 2.2.2. Brightness Impact Analysis and Improvement The gray value of each pixel of an image is mainly decided by the brightness of the light reflected by the surface of a scene, so light will brighten or darken the overall image, which is equivalent to adding a direct current component. Similarly, the grayscale and contrast changes can also be attributed to the influence of the direct current component or the alternating current component of an image. How to reduce the influence of the alternating current component has been discussed above. As to how to reduce the influence of the direct current component, it is required to reconstruct the circular projection vector and enable it to have grayscale translation invariance instead of averaging. The improvement made in literatures [5, 6] is: ... (3) According to Formula (3), changes in noise and light intensity will result in the changes in the alternating current component of a circular projection and as a result, the gray values P(r) at different radiuses increase as the radius increases. In this case, Literatures [5, 6] adopted the idea of normalization for processing. ... (4) At the same time, considering that the main characteristics of a scene are concentrated on the center, the variable weight is used. ... (5) where W(r) is the variable weight vector. This paper uses the inconsistency correction method to reduce the influence of brightness based on variable weights. ... (6) Equations (5) and (6) subtract an estimated direct current component. The difference is that Equation (5) directly estimates the projection of the original component while Equation (6) uses the projection data in which noise has been filtered out. 2.2.3. Analysis of the Experimental Results of the Improved Circular Projection Matching Algorithm The improved circular projection matching algorithm above is verified. A point whose coordinate is (148, 70) is located. After the image is rotated by 60 degrees, the coordinate of the point becomes (182, 118). For the point (148, 70), a circular projection is conducted according to Formula (1). The radius of the circular projection is 7. The projection vector of the original image is P\(r) = [43 24 18.634 16.012 14.357 13.975 13.994 13.943]. Gaussian noise (cr=0.01) is added to the point (182, 118). After brightness ^ is adjusted, a circular projection is conducted according to Formula (5) to obtain the new projection vector P4(r)= [0.2181 0.30401 0.32234 0.3046 0.27542 0.26652 0.26472 0.261870]. Similarly, Gaussian noise (cr =0.01) is added to the point (182,118). After brightness ^ is adjusted, a circular projection is conducted according to Formula (6) to obtain the new projection vector />j(r)= [0.14850 0.09486 0.01871 -0.00154 0.014067 - 0.00076 -0.00656 -0.00651]. After calculations, the correlation coefficient between P\(r) and P4(r) is 0.9487 and the correlation coefficient between Pi(r) and P5(r) is 0.9701. The results show that the new projection vector obtained according to Equation (6) has better performance in rotation, noise and brightness change resistance. 3. Application of PCA in the Detection Algorithm for Image Copy-Move Forgery PCA is a linear dimensionality reduction method based on one-dimensional vectors. It is used to find the best low-dimensional representation of the original high-dimensional data based on least meansquare error. It can transform multiple indicators into a few comprehensive indicators and select a few important variables from multiple variables through linear variation so as to reduce dimensionality. Therefore, the first step is to move the pixel one by one to divide the image whose size is m x n (512 x 512) into L image blocks whose sizes are 2kx2k. A circular projection is conducted for each image block. The grayscale function of the 2kx2k image blocks is / (x, y). The circular projection of a pixel is the one-dimensional vector PKP(0),P( l ).. .P(7Q]. L one-dimensional vectors are written into the projection feature matrix of the image U={P¿\) P¿2)...P¿L)f , where P^i) (¿=1,2..¿) is the row vector constituted by the circular projection of the image block. It can be seen that the size of U is L x K. Then PCA is used to reduce the dimensionality of the matrix U. The steps are as follows: Step 1 formalize the projection feature matrix U. The data in the matrix have different natures and different orders of magnitude. If no normalization is applied, the impact of high-value indicators will reduce the impact of low-value indicators in the analysis, so that small data are ignored. As a result, various data will participate in the operation at unequal weights. There are a great many methods for normalization. Here the standard normal distribution normalization is used: ... (7) where Pj(i) is the normalized row vector and Unew is the matrix composed of the normalized row vectors. Step 2: Obtain the covariance matrix V of Unew. ... (8) where ... is the correvlation coefficient between variables P-[(i) and P[(j) ' and is calculated according to the following formula. ... (9) Step 3: Obtain the feature value X i of V and the feature vector e,-(i=l, *** p) of the corresponding feature value. Step 4: Calculate the contribution and cumulative contribution of the principal component: The contribution of the principal component Wi is ... (10) and the cumulative contribution Qi is ... (1) Get the 1st, 2nd, h01 principal components corresponding to the feature values X X 2 * * * X h (h < p ) whose cumulative contribution is 85 %. Step 5: Construct the dimensionality reduction transformation matrix S with the feature vectors corresponding to the feature values X X2 *** Xh sorted in the descending order. Calculate U'=Unew * S and complete the transformation from the high-dimensional U into the low-dimensional U'. Finally sort U' according to the lexicographic order and seek out the copy-move area in combination with the offset confidence distance according to the sorted image. 4. Experimental Results and Analysis In order to verify the validity of this algorithm, this paper selects 150 natural images and use Photoshop for copy-move. The methods for copymove include rotation of 0°-30°(150 images), rotation of 30°-60°(150 images) and rotation of above 60° (150 images). For the above images, Gaussian noise (cr = 0.01) is added and brightness y =0.6 is adjusted. The computer configuration on which all experiments are conducted is CPU dual core (TM) 2.4 GHz, a memory of 2GB and the Windows XP operating system. The size of the image block is 16x16. Matlab 7 is used to program the algorithm in this paper and other relevant algorithms. First, the above forged image sample is used to test the resistance of the algorithm proposed in this paper against rotation angles. The test results are shown in Table 1. The data in the table show that the detection rate can exceed 93 % for copy-move forgery after rotation of 0°-60°. Fig. 4 and Fig. 5 are the detection results of a test image called "sunflower" which is copied and pasted after rotation of 30°and 60° respectively. It is shown that both can be detected correctly. However, when the rotation angle exceeds 60°, the detection rate of the algorithm proposed in this paper decreases sharply. The circular projection matching algorithm is theoretically rotation invariant. However, during its application on the computer, if the interpolation of the image block, whose rotation angle becomes bigger after copy, is greater when pasted, the projection difference between the original image block and that of the pasted image block will be greater and the detection will fail. Second, comparison is made with algorithms proposed in literatures [2-4] in timeliness. Because the number of blocks is a crucial factor that affects the detection speed of the block matching detection algorithm, the partitioning methods that will obtain the best detection effects are considered as the standards in our experiments. This paper takes the image with a size of 512^512 for example (the size of the sub-block is 16x16) and literatures [2-4] take the image with a size of 512x512 for example (the size of the sub-block is 8x8). The partitioning methods, number of blocks and detection time of the algorithms proposed in this paper and literatures [2-4] are listed in Table 2. According to the Table, detection time and number of blocks are closely related to the algorithms proposed in literatures [2-4]. In this paper, however, a data matrix is constructed by using circular projections before PCA is carried out which greatly reduces the dimensionality of the data requiring PCA, so that the computational speed of the algorithm proposed in this paper is much faster than the speed of general matching algorithms. 5. Conclusions Because general algorithms seldom study copymove operations with angle rotation and block matching algorithms are very time-consuming, this paper proposes a detection algorithm for image copymove forgery based on improved circular projection matching and PCA. This algorithm first partitions the detected image by line and row, calculate the circular projection vectors of the image blocks, uses the projection vectors of all image blocks to construct a data matrix, reduces the dimensionality of the data matrix, finally sorts that matrix in the lexicographic order and judges whether the adjacent image block has been copied and pasted according to confidence distance. The experimental results show that this algorithm is able to resist a certain degree of rotation while reducing the influence of random noise and brightness change. It locates accurately, reduces detection time and improves detection efficiency. However, this algorithm still comes with some disadvantages. For example, if a rotation exceeding 60°, scaling and other geometric transformation occur when the same image area is copied, this algorithm won't work. The next step is to improve the algorithm. In addition, content composition of different images is also a common form of forgery. How to detect and authenticate this kind of forgery is also one focus of our future study. References [1] . J. Fridrich, D. Soukal, J. Lukas, Detection of copymove forgery in digital images, in Proceedings of the IEEE Digital Forensic Research Workshop, Cleveland, OH, USA, August 2003, pp. 55-61. [2] . Alin C. Popescu and Hany Farid, Exposing digital forgeries by detecting duplicated image regions, TR2004-515, Department of Computer Science, Dartmouth College, September 2004. [3] . Qiong WU, Shao-Jie SUN, Wei ZHU, Guo-Hui LI, Dan TU, Chao-Sheng, A blind forensic algorithm for detecting doctored image region by application of exemplar-based image completion, Acta Automática Sínica, Vol. 35, No. 3 March 2009, pp. 239-243. [4] . Li Jing, Huijuan Zhang, Detection and location of image region duplication forgery based on phase correlation. Journal of Computer Applications, Vol. 33, Issue 3,2013, pp. 660-662, 687. [5] . Yibin Xu, Jingdong Wang, Peng Li, Research on scene matching method using circular projection, Systems Engineering and Electronics, Vol. 27, No. 10, Oct. 2005, pp. 1725-1728. [6] . Jingdong Wang, Yibin Xu, Chun-Lin Shen, New scene matching method for arbitrary rotation, Journal of Nanjing University of Aeronautics & Astronautics, Vol. 37, No. 1, February 2005, pp. 6-10. [7] . Yanjun Cao, Tiegang Gao, Li Fan, Qunting Yang, A robust detection algorithm for copy-move forgery in digital images, Forensic Science International, Vol. 214, 2012, pp. 33^13. [8] . Guoping Qiu, Functional optimization properties of median filtering, IEEE Signal Process Letter, Vol. 1, Issue 4, 1994, pp. 64-65. [9] . B. L. Shivakumar, S. Santhosh Baboo, Detecting copy-move forgery in digital images: a survey and analysis of current methods, Global Journal of Computer Science and Technology, Vol. 10, Issue 7, 2010, pp. 61-65. [10] . C. D. Kuglin, D. C. Hines, The phase correlation image alignment method, in Proceedings of the IEEE International Conference on Cybernetics and Society, New York, 1975,pp. 163-165. [11] . Guangjie Liu, Junwen Wang, Shiguo Lian, A passive image authentication scheme for detecting region-duplication forgery with rotation, Journal of Network and Computer Applications, Vol. 34, Issue 5, 2011, pp. 1557-1565. Yanfen GAN, Jing CANG Information science and technology department Guangdong University of Foreign Studies South China Business College, Guangzhou, 510545, China Tel:+8613751800978 E-mail: [email protected] Received: 19 August 2013 /Accepted: 25 October 2013 /Published: 25 November 2013 (c) 2013 International Frequency Sensor Association |