在本論文中，我們提出了影像複製-移動偵測演算法與影像重新取樣偵測演算法。為了偵測影像複製-移動之造假，給定的影像將會分成重疊的區塊，再對每一個區塊抽取出一組特徵，以一向量表示之。接著對所有的特徵向量利用基數排序法進行排序，接著計算每一對相鄰的向量其相對區塊位置的差，稱之為位移向量。相同的位移向量累積量達一門檻值時，很可能就會存在著重複的區域。而這些向量所對應到的區塊就會被標示，而後再對這些標示的區塊進行中間值濾波及連通元件分析的處理，就能求出複製-移動的區域。在影像重新取樣之偵測的部分，我們提出了兩個偵測的方法：精確偵測法與近似偵測法。精確偵測法分為三個部分：對於一個重新取樣倍率，提出了一個建構重新取樣矩陣的演算法(RMC)；提出了一個對於一個重新取樣倍率，推導出其一零化濾鏡之演算法；提出了一個演算法(RD)，使用一組零化濾鏡來進行影像重新取樣偵測。此精確偵測法只能偵測出系統提供的零化濾鏡之相對取樣倍率，使用上較缺乏彈性，因而提出近似偵測法，來改善這樣的缺點。近似偵測法裡，當影像重新取樣倍率與使用的零化濾鏡的倍率很接近時，其倍率可以被近似估測出。此方法藉由檢查影像與零化濾鏡的旋積值之週期性，來推論出這張影像的重新取樣倍率。實驗結果可看出我們提出的兩種影像造假之偵測方法均具有極高偵測率與效率。

In this thesis, we propose a method to detect copy-move forgery of images and two methods to detect resampling of images. To detect copy-move forgery of an image, the given image is divided into overlapping blocks of equal size, features for each block are then extracted and represented as a vector, all the extracted feature vectors are then sorted using a radix sort. The difference of the positions of every pair of adjacent feature vectors, called shift vector, in the sorting list is computed. The accumulated number for each of the shift vectors is evaluated. A large accumulated number is considered as possible presence of a duplicated region, and thus all the feature vectors corresponding to the shift vectors with large accumulated numbers are detected, whose corresponding blocks are then marked to form a tentative detected result. Finally the medium filtering and connected component analysis are performed on the tentative detected result to obtain the final result. For resampling detection, two detection methods are proposed. The former method was exact detection which includes three steps: first, we present an algorithm Resampling Matrix Construction (RMC) that automatically derives the resampling matrix for any given factor. Second, we show an algorithm that constructs a zeroing mask for the resampling by a factor with the support of the corresponding resampling matrix produced by the proposed algorithm Zeroing Mask Derivation (ZMD). Lastly, we propose an algorithm RD that detects resampling on images using the zeroing masks in a specific order. The latter is an improved version of exact detection to detect a much wider range of resampling factors by checking some periodic repetition with an approximation detection mechanism. The experimental results have demonstrated that the proposed methods are indeed effective and efficient.

List of Figures	V
List of Tables	VII
Chapter 1 Introduction	1
Chapter 2 Copy-move detection	4
2.1 Existing methods	4
2.2 The proposed method for copy-move detection	7
2.3 The method for detecting rotated copy-move	10
Chapter 3 Resampling detection	12
3.1 Resampling	12
3.2 Constructing resampling matrices	16
3.3 Deriving zeroing masks	20
3.4 Detecting resampling with zeroing masks	30
3.5 Approximate resampling detection	33
Chapter 4 Experimental results	42
4.1 Results of copy-move detection	42
4.2 Results of exact resampling detection	49
4.3 Results of approximate resampling detection	52
Chapter 5 Conclusions and future works	58
References	59

List of Figures
Figure 1. (a). An original image; (b). Three pairs of identical blocks are enclosed by blue squares; (c). Sorted list of feature vectors, in which identical vectors are grouped together................................5
Figure 2. A block B is divided into four equal-sized sub-blocks S1, S2, S3, and S4.............................................................................................7
Figure 3. Duplicated regions form several identical shift vector u............9
Figure 4. (a). Corner points of detected blocks are marked according to the accumulated numbers of shift vectors for the tampered image given in Figure 1(b); (b). final detected result.............................11
Figure 5. A region is copied, rotated by angle 90 degrees, and pasted to another region..............................................................................11
Figure 6. (a) The tampered image; (b) the extended image from (a); (c) the detecting result.......................................................................11
Figure 7. The relation between the original signal x and resampled signal y by a factor of 5/3.......................................................................14
Figure 8. Table T shows if a zeroing mask for factor f(j) is also one for f(i).................................................................................................31
Figure 9. An ideal sketch of cs(M p/q, z, i).................................................40
Figure 10. (a) & (b) The original images; (c) & (d) the tampered images; (e) & (f) the detecting results.......................................................43
Figure 11. (a) & (b) The original images; (c) & (d) the tampered images; (e) & (f) the detecting results.......................................................44
Figure 12. Detected results over compressed versions of the image given in Figure 1(a), with various quality factors (QFs): (a) QF = 90; (c) QF = 70; (e) QF = 50...................................................................45
Figure 13. Detected results for the image given in Figure 1(a) with Gaussian noise at various SNRs: (a). SNR = 10db; (c). SNR = 20db; (e). SNR = 35db.................................................................46
Figure 14. The detecting results for rotated copy-move regions..............48
Figure 15. (a) Original image, (b) & (c) resampled images by factors 5/4 and 4/3, respectively. (d)~(f) scores for images in (a)~(c) with the sequence of 45 masks, where each of the green bars indicates a detection result.............................................................................50
Figure 16. detection rates v.s tolerance of error rates...............................54
Figure 17. (a)~(c) detection results of using 45 zeroing masks (d)~(f) detection results of using 57 zeroing masks................................56
Figure 18. Comparison of running time of our method and Popescus et al.’s method..................................................................................57

List of Tables
Table 1. (a) signal x; (b) signal y; (c) zeroing mask M4/3; (d) the convolution values of y with M4/3................................................34
Table 2. (a) signal z (b) the convolution values of z with M4/3.................36
Table 3. (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.............................................................................................38
Table 4. The convolution values and the corresponding scores...............40
Table 5. Detection rates for copy-move images with modification..........47
Table 6. Detection rates for copy-move images with rotation and some other modification........................................................................47
Table 7. The detection rates v.s tolerance of different error rates (11100 test images) .................................................................................56

[1] C. T. Hsieh and Y. K. Wu, “Geometric Invariant Semi-fragile Image Watermarking Using Real Symmetric Matrix,” WSEAS Transactions on Signal Processing, Vol. 2, No. 5, May 2006, pp. 612-618.
[2] C. T. Hsieh, Y. K. Wu, and K. M. Hung, “An Adaptive Image Watermarking System Using Complementary Quantization,” WSEAS Transactions on Information Science and Applications, Vol. 3, No. 12, 2006, pp. 2392-2397.
[3] K. M. Hung, C. T. Hsieh, and Y. K. Wu, “Multi-Purpose Watermarking Schemes for Color Halftone Image Based on Wavelet and Zernike Transform,” WSEAS Transactions on Computer, Vol. 6, No. 1, 2007, pp. 9-14.
[4] F. Hartung and M. Kutter, “Multimedia Watermarking Techniques,” Proceedings of the IEEE, Vol. 87, No. 7, July 1999, pp. 1079-1107.
[5] P. Meerwald and A. Uhl, “A Survey of Wavelet-Domain Watermarking Algorithms,” Proceedings of SPIE, Electronic Imaging, Security and Watermarking of Multimedia Contents, Vol. 4314, 2001, pp. 505-516.
[6] W. Lu, F. L. Chung, and H. Lu, “Blind Fake Image Detection Scheme Using SVD,” IEICE Transactions on Communications, Vol. E89-B, No. 5, May 2006, pp. 1726-1728.
[7] M. S. Wang and W. C. Chen, “A Majority-Voting based Watermarking Scheme for Color Image Tamper Detection and Recovery”, Computer Standards & Interfaces, Vol. 29, No. 5, 2007, pp. 561-570.
[8] P. L. Lin, C. K. Hsieh, and P. W. Huang, “A Hierarchical Digital Watermarking Method for Image Tamper Detection and Recovery, Pattern Recognition, Vol. 38, No. 12, 2005, pp. 2519-2529.
[9] K. F. Li, T. S. Chen, and S. C. Wu, “Image Tamper Detection and Recovery System Based on Discrete Wavelet Transformation,” International Conference Communications, Computers and Signal Processing, Vol. 1, 2001, pp. 26-28.
[10] M. K. Johnson and H. Farid, “Exposing Digital Forgeries by Detecting Inconsistencies in Lighting,” Proceedings of ACM Multimedia and Security Workshop, New York, 2005, pp. 1-9.
[11] R. Brunelli, “Estimation of Pose and Illuminant Direction for Face Processing,” Image and Vision Computing, Vol. 15, No. 10, 1 October 1997, pp. 741-748.
[12] A. P. Pentland, “Finding the illuminant direction,” Journal of the Optical Society of America, Vol. 72, No. 4, 1982, pp. 448-455.
[13] W. Zhou and C. Kambhamettu, “Estimation of Illuminant Direction and Intensity of Multiple Light Sources,” Proceedings of the 7th European Conference on Computer Vision-Part IV, 2002, pp. 206-220.
[14] P. Nillius and J. O. Eklundh, “Automatic Estimation of the Projected Light Source Direction,” Proceedings of 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 1, 2001, pp. 1076- 1083.
[15] T. E. Boult and G. Wolberg, “Correcting Chromatic Aberrations Using Image Warping,” Proceedings of Computer Vision and Pattern Recognition, 1992, pp. 684-687.
[16] M. K. Johnson and H. Farid, “Exposing digital forgeries through chromatic aberration,” Proceedings of the 8th workshop on Multimedia and security, 2006, pp. 48-55.
[17] J. Lukas, J. Fridich, and M. Goljan, “Detecting Digital Image Forgeries Using Sensor Pattern Noise,” Proceedings of the SPIE Conference on Security, Steganography, and Watermarking of Multimedia Contents, Vol. 6072, January 2006, pp. 362-372.
[18] N. Khanna, A. K. Mikkilineni, G. T. C. Chiu, J. P. Allebach, and E. J. Delp, “Scanner Identification Using Sensor Pattern Noise,” Proceedings of the SPIE International Conference on Security, Steganography, and Watermarking of Multimedia Contents IX, Vol. 6505, No. 1, 2007, pp. 65051K.
[19] J. Lukas, J. Fridrich and M. Goljan, “Determining Digital Image Origin Using Sensor Imperfections,” Proceedings of SPIE Electronic Imaging, Image and Video Communication and Processing, January 16-20, 2005, pp. 249-260.
[20] A. C. Popescu and H. Farid, “Exposing Digital Forgeries in Color Filter Array Interpolated Images,” IEEE Transactions on Signal Processing, Vol. 53, 2005, pp. 3948–3959.
[21] A. C. Popescu and H. Farid, “Exposing Digital Forgeries by Detecting Duplicated Image Regions,” Technical Report, TR2004-515, Department of Computer Science, Dartmouth College, 2004.
[22] G. Li, Q. Wu, D. Tu, and S. Sun, “A Sorted Neighborhood Approach for Detecting Duplicated Regions in Image Forgeries based on DWT and SVD,” Proceedings of IEEE International Conference on Multimedia and Expo, Beijing China, July 2-5, 2007, pp. 1750-1753.
[23] W. Luo, J. Huang, and G. Qiu, “Robust Detection of Region Duplication Forgery in Digital Image,” Proceedings of the 18th International Conference on Pattern Recognition, Vol. 4, 2006, pp. 746-749.
[24] A. N. Myna, M. G. Venkateshmurthy, and C .G Patil, “Detection of Region Duplication Forgery in Digital Images Using Wavelets and Log-Polar Mapping,” Proceedings of the International Conference on Computational Intelligence and Multimedia Applications (ICCIMA 2007), Vol. 3, 2007, pp. 371-377.
[25] H. Huang, W. Guo, and Y. Zhang, “Detection of Copy-Move Forgery in Digital Images Using SIFT Algorithm,” IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application, Vol. 2, 2008, pp. 272-276.
[26] A. C. Popescu and H. Farid, “Exposing Digital Forgeries by Detecting Traces of Resampling,” IEEE Transactions on Signal Processing, Vol. 53, 2005, pp. 758-767.
[27] M. Kirchner, “Fast and reliable resampling detection by spectral analysis of fixed linear predictor residue,” ACM Multimedia and Security Workshop (ACM MM&Sec), 2008, pp. 11-20.
[28] B. Mahdian and S. Saic, “Detection of Resampling Sup-plemented with Noise Inconsistencies Analysis for Image Forensics,” International Conference on Computational Sciences and its Applications, Vol. 81, No. 4, 2008, pp. 546-556.
[29] C. C. Lien, C. L. Shih, and C. H. Chou, ”Fast Forgery Detection with the Intrinsic Resampling Properties,” IIH-MSP '10 Proceedings of the 2010 Sixth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, 2010, pp. 232-235.
[30] Howard Anton and Chris Rorres, “Elementary linear algebra,” 9th edition, WILEY, 2005.