Copy-move forgery detection based on local intensity order pattern and maximally stable extremal regions

Abstract

To abandon the use of overlapping block division and resist the tampering factor of illumination change, a novel copy-move forgery detection method is proposed based on Maximally Stable Extremal Regions (MSERs) and the Local Intensity Order Pattern (LIOP), that integrates block-based and keypoints-based methods. The method involves the following steps: first, affine transformation invariant MSERs are used to maintain the geometrical transformation invariance and reduce computational complexity; second, LIOP features are used to describe the texture and resist illumination change; and finally, RANdom SAmple Consensus is applied to remove false matches. The experiments indicate that the proposed method has great performance for scaling, rotation and illumination changes. Moreover, the method has the high robustness to Gaussian noise, Gaussian blur and JPEG compression.

Keywords

Image forensics copy-move forgery detection maximally stable extremal regions local intensity order pattern

1 Introduction

Due to the increasing ease of image forgeries in daily life, such as social networks, advertisements and court evidence, the authentication of images has become an important issue. Passive forgery detection, which analyses the content of an image, is an effective way to detect tampering without watermarking insertion. Copy-move forgery is an operation involving copying a region and pasting it in same image, where the illumination and compressed factor are the same.

The Copy-Move Forgery Detection (CMFD) methods could be divided into three classifications, namely, overlapping block-based, keypoints-based and non-overlapping irregular block-based.

In the overlapping block-based scheme, Fridrich first proposed a CMFD method based on Discrete Cosine Transform (DCT) [1]. Several improved DCT methods [2, 3] have focused on the robustness of noise and blur. Prakash applied overlapped circular blocks and DCT features than the prevalent methods, which had lower computational complexity [3]. Moreover, several features have been applied to CMFD block-based schemes, such as Non-negative Matrix Factorization (NMF) [4], Principal Component Analysis (PCA) [5], Dyadic Wavelet Transform (DyWT) [6] and Fourier-Mellin Transform (FMT) [7]. To solve the rotation transformation invariance, the Hu [8], Blur [9] and Zernike [10] moments are used as features in CMFD. However, the overlapping block-based CMFD scheme, in which the input image is divided into overlapping blocks, cannot address the geometrical transformation of the forgery regions and significantly increases the computational expense. In the keypoints-based schemes, Scale Invariant Feature Transform (SIFT) [11], improved SIFT [12, 13] and Speeded Up Robust Feature (SURF) [14] are widely used. A feature descriptor called DAISY [15] is used to resist contrast variation and scale changes. Because of the efficiency of the rapid extraction and high matching rate, a CMFD method based on scaled Oriented FAST and Rotated BRIEF (ORB) [16] was presented. Alfraih proposed the method based on MSER features and K-means Clustering [17], which had a great performance on removing false matching. Nonetheless, the keypoints-based CMFD scheme is not robust to smooth regions and performs unevenly in post-processing operations. Recently, several novel schemes based on non-overlapping irregular blocking, such as over-segmentation [18, 19], Dense-Field [20], hashing [21] and triangles of local keypoints [22], were presented. Zandi applied an iterative scheme to detect keypoints even in low contrast regions, which had better performance than state-of-the-art methods [23]. Abdel-Basset proposed 2-level clustering strategy based on spatial and transformation domains, able to individuate the altered areas, with had high reliability and could deal with multiple cloning [24].

Nonetheless, most of CMFD schemes are useless for copy-move with illumination change. Therefore, we propose a novel CMFD method to maintain the advantages of the block-based and keypoints-based schemes. The affine transformation invariance patches are used to maintain the geometrical transformation and reduce the computational complexity. The Local Intensity Order Pattern (LIOP) [25] features are used to effect illumination change.

The rest of this paper is organized as follows. In Section II, the proposed CMFD method is expounded, with each step described in detail. Then, the dataset, metrics and experiments on different tampering factors and types of post-processing are shown in Section III. Finally, Section IV presents the conclusions.

2 Overview of the proposed CMFD method

This section explains the four steps of the proposed CMFD method. The framework is shown in Fig. 1. First, affine transformation invariance patches are extracted by applying Maximally Stable Extremal Regions (MSERs) [26], which have the advantage of affine transformation invariance. Second, each region is described by the LIOP features, which are invariance to illuminate change to make sure matching in copied and pasted regions. Third, LIOP features are matched by Euclidean distance. However, there have some dissonant false matches, as is shown in Fig. 1(c). Finally, false matches are removed through RANdom SAmple Consensus (RANSAC) [27].

Fig.1

The framework of the proposed CMFD method.

2.1 Affine transformation invariance patches

To abandon the use of traditional overlapping blocks division and to improve the computational efficiency, affine transformation invariance patches are extracted from the input image. The procedure is described in Fig. 2.

Fig.2

Procedure for affine transformation invariance patch extraction.

The Maximally Stable Extremal Regions (MSERs) approach, proposed by Matas, was evaluated as an excellent region extraction method in [28]. MSERs are invariant to affine transformation and image intensity, which ensures that the same regions are extracted when tampered areas are transformed and the illumination is changed. Moreover, the computational complexity of MSERs is almost linear with the number of pixels, which can improve the computational efficiency. Therefore, MSERs, which are stable over a large range of thresholds, are extracted first. A more detailed procedure can be found in [26].

Because the MSERs are irregular in shape, as shown in Fig. 2(c), they are usually fitted to ellipses using the covariance matrix C, which is defined as Equation (1): $C = [\begin{matrix} E (x^{2}) - {(E (x))}^{2} & E (xy) - E (x) E (y) \\ E (xy) - E (x) E (y) & E (y^{2}) - {(E (y))}^{2} \end{matrix}]$ (1) where E(x) and E(y) are the respective means of the x-coordinates and y-coordinates of all points in the MSERs. The semi-major axis (a), semi-minor axis (b) and orientation (θ) of the ellipse are computed as Equation (2): $a = \sqrt{λ_{1}} b = \sqrt{λ_{2}} θ = actan (\frac{V_{22}}{V_{21}})$ (2) where λ₁ and λ₂ are the eigenvalues of C, and $[\begin{matrix} V_{11} \\ V_{21} \end{matrix}]$ and $[\begin{matrix} V_{12} \\ V_{22} \end{matrix}]$ are the eigenvectors corresponding to λ₁ and λ₂. The fitted ellipses have varying sizes and orientations, as shown in Fig. 2(d). To extract the feature description in the next steps, each fitted ellipsis is normalized to circular patches of a fixed diameter (diameter is set as 41 according to the average size of ellipsis). The ith affine transformation invariance patch is recorded as patch(i) and is shown in Fig. 2(f).

2.2 Feature extraction

Since Local Intensity Order Pattern is invariant to rotation and illumination changes, which was applied to describe the patch texture in our method. The procedure for the LIOP features is explained as Fig. 3.

Fig.3

Procedure of LIOP descriptor extraction.

2.2.1 Region division

Region division is based on the intensity order, which is invariant to rotation and illumination changes and contains spatial information. For each affine transformation invariant patch, patch(i), the pixels in the patch are first sorted and divided equally to B bins (B = 6 according to [26]), where the number of pixels in each bins are the same. The ith bin is recorded as bin_i (), as is shown in Fig. 3(b).

2.2.2 LIOP descriptor

Assume that P(x₀)={I(x₁), I(x₂), I(x₃), ... , I(x _N)}, where P(x₀) is the set of grey values, I(x _i) is the grey value of point x _i and x _i is the ith neighbouring sample point of point x₀, as is shown in Fig. 4(a). Let P(x₀) be sorted in non-descending order. The index of the is recorded as γ (P (x₀)) = π = {i₁, i ₂, · · ·, i_N}, where π ∈ Π, Π is all of the possible permutations of {1, 2, …, N} (N = 4 according to [24]), and γ() is the function mapping π to ind (π), as is shown in Fig. 4(b). The feature descriptor φ (x₀) is defined as Equation (3): $φ (x_{0}) = {0, 0, 0, 0, 0, 0, \underset{ind (π)}{1}, 0, . . . 0, 0, 0}$ (3) where the function ind(π) is the index of π in the index table. Finally, the LIOP of bin_i could be defined as Equation (4) and shown in Fig. 4(c). ${LIOP}_{{bin}_{i}} = \sum_{x_{0} \in {bin}_{i}} φ (x_{0})$ (4)

Fig.4

The procedure of LIOP descriptor conduction.

Finally, for each affine transformation invariant patch in Section 2.2.1, the LIOP descriptor of patch(i) is defined as Equation (5): $LIOP (i) = [{LIOP}_{{bin}_{1}}, {LIOP}_{{bin}_{2}}, . . ., {LIOP}_{{bin}_{B}}]$ (5)

2.3 Matching

In the matching process, the Euclidean distance is used to describe the similarity of the LIOP features, which indicate the similarity of patches. Mathematically, the Euclidean distance between patch(a) and patch(b) is defined as Equation (6): $dis (a, b) = sqrt (\sum_{1 ⩽ i ⩽ n} (LIOP (a)_{i} - LIOP (b)_{i})^{2})$ (6) where n is the dimension of the LIOP feature. The two affine transformation invariance patches, patch(a) and patch(b), are considered as matches only if they satisfy the condition defined in Equation (7): $dis (a, b) / dis (a, i) < th; 1 < i < n$ (7) where i is the ith patch, n is the number of patches, th is the matching threshold, which could get best performance by th = 0.75.

As shown in Fig. 1(c), there are several false matches. Therefore, RANSAC, proposed by Fischler [27], was applied to evaluate the affine transformation model through iteration to maintain the inliers (correct matches) and remove the outliers (false matches) that do not fit the model. After a certain number of iterations, the affine transformation model has the greatest number of correct matches. The false match removal result after RANSAC is shown in Fig. 1(d).

3 Experiments and evaluation

3.1 Dataset

In order to evaluate the efficiency of the algorithm, the original images are the format of TIFF and PNG, which are constructed by Christlei [29], CoMoFoD [30], COVERAGE [31] and total have 348 images. Then, the copy-move forged regions are transformed using 4 tampering factors: naive, rotation, scaling and illumination. As a result, the number of tampered images are 4176.

naive: The copied regions are pasted in the same image with no geometric transformation.

rotation: The copied regions are rotated by 5 different angles {2°, 10°, 45°, 90°, 180°}.

scaling: We scale the copied regions by 4 different scaling factors {0.7, 0.9, 1.1, 1.2}.

illumination: To perfectly adapted to background, two different settings, namely, uniform illumination and non-uniform illumination, are applied to the forged regions. The uniform illumination is that forged regions are operated through directional light and non-uniform illumination is that forged regions are operated through omni light in Photoshop CS4.

3.2 Metrics

The performance of the proposed CMFD method is evaluated at the image level, measured by the ratio of the number of correctly detected images to the number of tampered images (True positive rate, T_PR) and the ratio of the number of falsely detected images to the number of original images (False positive rate, F_PR), which are defined by Equation (8)–(9). $T_{PR} = \frac{{no . tampered images detected as forgery}}{{no . tampered images}}$ (8) $F_{PR} = \frac{{no . original images detected as forgery}}{{no . original images}}$ (9)

3.3 Experimental results

3.3.1 Experiments on tampering factors

To evaluate the performance of the proposed method, the 4 tampering factors in our dataset were estimated. Example results are shown in Fig. 5. As shown in the third and fourth columns of Fig. 5, CMFD-SIFT [13] and ORB [16] almost could detect the copy-move forgery in 4 tampering factors, but it could not cover full tampered regions. As shown in the fifth column of Fig. 5, Dense-field [20] accurately identifies the tampering location for the naïve and scaling, however, it is ineffective for rotation and illumination. In contrast, according to the last column of Fig. 5, our proposed method performs well on naïve images, rotation, scaling, illumination, and achieves the accurate tampering location with no false matches.

Fig.5

Example results for different tampering factors with respect to naïve images, rotation, scaling and illumination from top to bottom. Column 1 shows the original images. Column 2 shows the tampered images, where red solid lines are the copied regions and red dashed lines are the pasted regions. Column 3 shows the results based on CMFD-SIFT [13], where the green lines are the matching regions. Column 4 shows the results based on ORB [16], where the red lines are the matching regions. Column 5 shows the results based on Dense-field [20], where the black regions are the tampered regions. Column 6 shows the results based on the proposed method, where the red ellipses are MSERs and the green lines are the matching regions.

As is shown in Fig. 6, the statistical results are analysed through ROC curves, where indicate that our proposed method has better performance than CMFD-SIFT [13], ORB [16] and Dense-field [20].

Fig.6

ROC curve comparison results based on CMFD-SIFT [13], ORB [16], Dense-field [20] and our proposed method.

3.3.2 Experiments on post-processing

In this section, we evaluate the robustness of our proposed CMFD method against three types of post-processing attacks, namely, Gaussian white noise, Gaussian blur and JPEG compression, on applied to the tampered images mentioned in Section 3.3.1.

Gaussian white noise: Forged images are processed by Gaussian noise through the Matlab function imnoise, with the parameters mean m = 0 and variance v = [0.00005, 0.0001, 0.0002].

Gaussian blur: Gaussian blur is added to the forged images, with the same window size, (w = 3) but different sigma (σ= 1, 3, 5).

JPEG compression: Tampered images are re-compressed with different JPEG quality factors, varying from 100 to 40, in steps of – 20.

Some examples of the results are shown in Fig. 7. As shown in the second and third column of Fig. 7, CMFD-SIFT [13] and ORB [16] only locate parts of tampered region on Gaussian blur, JPEG compression and fail to locate tampered region on Gaussian noise. On the contrary, Dense-field [20] detectstampered regions in Gaussian blur but has false detection on JPEG compression and Gaussian noise from the forth column of Fig. 7. Moreover, as shown in the last column of Fig. 7, the proposed method exhibits the best robustness to noise, blur and JPEG compression. From a statistical analysis of the ROC curves, which are shown in Fig. 8, our proposed method has higher TPR at the same FPR than CMFD-SIFT [13], ORB [16], Dense-field [20] for different degrees of Gaussian noise, Gaussian blur and JPEGcompression.

Fig.7

Example results for post-processing with Gaussian noise, Gaussian blur and JPEG compression from top to bottom. Column 1 shows the results of the tampered images, where red solid lines are the copied regions and red dashed lines are the pasted regions. Column 2 shows the results based on CMFD-SIFT [13], where the green lines are the matching regions. Column 3 shows the results based on ORB [16], where the red lines are the matching regions. Column 4 shows the results based on Dense-field [20], where the black regions are the tampered regions. Column 5 shows the results based on the proposed method, where the red ellipses are MSERs and the green lines are the matching regions.

Fig.8

ROC curve comparison of post-processing results based on CMFD-SIFT [13], ORB [16], Dense-field [20] and the proposed method.

3.3.3 Analysis of running time

In this section, time-consuming is recorded through testing CoMoFoD database. Since the image size of CoMoFoD are all 512*512, which would compare equally with CMFD-SIFT [13], ORB [16], Dense-field [20]. The hardware environment of the experiments is a 2.8 GHz Intel Core i5 processor; the software used is Matlab R2014b. In order to clearly analyse, the frame is divided into feature extraction and matching. The result is shown in Table 1. It’s obvious that the block-based method Dense-field [20] has the highest time-consuming. CMFD-SIFT [13] applied Agglomerative hierarchical clustering (AHC) to match, which consumes more on matching. ORB [16] extra needs to build pyramid scale space. Our proposed method perform better than CMFD-SIFT [13] and ORB [16], since we use MSERs to extract affine invariance regions.

Table 1
The comparison of time-consuming

Methods Respective time-consuming (average) Total time-consuming

Feature extraction Matching

CMFD-SIFT [13] 2.5 s 2.8 s 5.3 s

ORB [16] 3.5 s 1.7 s 5.2 s

Dense-field [20] 6.5 s 10.3 s 16.8 s

ours 2.4 s 2.5 s 4.9 s

Methods	Respective time-consuming (average)	Total time-consuming
CMFD-SIFT [13]	2.5 s	2.8 s	5.3 s
ORB [16]	3.5 s	1.7 s	5.2 s
Dense-field [20]	6.5 s	10.3 s	16.8 s
ours	2.4 s	2.5 s	4.9 s

4 Conclusions

This paper presents a novel CMFD method based on MSERs and LIOP, integrating block-based and keypoints-based methods. Our proposed method abandons the traditional block-based scheme that divides the image into overlapping blocks and maintains the superiority of the keypoints-based scheme, which is effective for rotation and scale geometric transforms. Moreover, our method performs well on the tampering factor of illumination change and is robust against Gaussian noise, Gaussian blur and JPEG compression. However, our proposed method is still not effective for some degrees of rotation and scaling, which will be improved in future research.

References

Fridrich

A.J.

, Soukal

B.D.

, Lukáš

A.J.

, Detection of copy-move forgery in digital images, Digital Forensic Research Workshop (2003).

Prakash

C.S.

, Maheshkar

, Detection of copy-move image forgery with efficient block representation and discrete cosine transform, Journal of Intelligent & Fuzzy Systems (2017), 1–13.

Alkawaz

M.H.

, Sulong

, Saba

, Rehman

, Detection of copy-move image forgery based on discrete cosine transform, Neural Computing and Applications 30(1) (2018), 183–192.

Yao

, Qiao

, Tang

, et al., Detecting Copy-move Forgery Using Non-negative Matrix Factorization, International Conference on Multimedia Information Networking and Security (MINES) (2011), 591–594.

Farid

A.P.

, Popescu

A.C.

, Exposing digital forgeries by detecting duplicated image regions, Computer Science, Dartmouth College (2004), TR2004–515.

Muhammad

, Hussain

, Bebis

, Passive Copy Move Image Forgery Detection Using Undecimated Dyadic Wavelet Transform, Digital Investigation 9(1) (2012), 49–57.

Bayram

, Sencar

H.T.

, Memon

, An efficient and robust method for detecting copy-move forgery, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2009), 1053–1056.

Liu

, Wang

, Lian

, A passive image authentication scheme for detecting region-duplication forgery with rotation, Journal of Network and Computer Applications 34(5) (2011), 1557–1565.

Mahdian

, Saic

, Detection of copy-move forgery using a method based on blur moment invariants, Forensic science international 171(2) (2007), 180–189.

10.

Chen

, Yu

, Su

, Shim

H.J.

, Shi

, Fractional Quaternion Zernike Moments for Robust Color Image Copy-Move Forgery Detection, IEEE Access 6 (2018), 56637–56646.

11.

Huang

, Guo

, Zhang

, Detection of copy-move forgery in digital images using SIFT algorithm, IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application (PACIIA) (2) (2008), 272–276.

12.

Amerini

, Ballan

, Caldelli

, Bimboa

A.D.

, Tongoa

L.D.

, Serraab

, Copy-move forgery detection and localization by means of robust clustering with J-Linkage, Signal Processing: Image Communication 28(6) (2013), 659–669.

13.

Yang

, Sun

, Guo

, Xia

, Chen.

, A copy-move forgery detection method based on CMFD-SIFT, Multimedia Tools and Applications 77(1) (2018), 837–855.

14.

, Wang

, Liu

, Image Copy-move Forgery Detection Based on SURF, IEEE International onMultimedia Information Networking and Security (MINES) (2010), 889–892.

15.

Guo

J.M.

, Liu

Y.F.

, Wu

Z.J.

, Duplication forgery detection using improved DAISY descriptor, Expert Systems with Application 40(2) (2013), 707–714.

16.

Zhu

, Shen

, Chen

, Copy-move forgery detection based on scaled ORB, Multimedia Tools and Applications 75(6) (2016), 3221–3233.

17.

Alfraih

A.S.

, Briffa

J.A.

, Wesemeyer

, Cloning localization based on feature extraction and k-means clustering, International Workshop on Digital Watermarking (2014), 410–419.

18.

Pun

C.M.

, Yuan

X.C.

, Bi

X.L.

, Image Forgery Detection Using Adaptive Over-Segmentation and Feature Points Matching, IEEE Transactions on Information Forensics and Security 10(8) (2015), 1705–1716.

19.

, Li

, Yang

, Sun

, Segmentation-based Image Copy-move Forgery Detection Scheme, IEEE Transactions on Information Forensics and Security 10(3) (2015), 507–518.

20.

Cozzolino

, Poggi

, Verdoliva

, Efficient Dense-Field Copy–Move Forgery Detection, IEEE Transactions on Information Forensics and Security 10(11) (2015), 2284–2297.

21.

Tang

, Zhang

, Li

, Zhang

, Robust image hashing with ring partition and invariant vector distance, IEEE transactions on information forensics and security 11(1) (2015), 200–214.

22.

Ardizzone

, Bruno

, Mazzola

, Copy–Move Forgery Detection by Matching Triangles of Keypoints, IEEE Transactions on Information Forensics and Security 10(10) (2015), 2084–2094.

23.

Zandi

, Mahmoudi-Aznaveh

, Talebpour

, Iterative copy-move forgery detection based on a new interest point detector, IEEE Transactions on Information Forensics and Security 11(11) (2016), 2499–2512.

24.

Abdel-Basset

, Manogaran

, Fakhry

A.E.

, El-Henawy

, 2-Levels of clustering strategy to detect and locate copy-move forgery in digital images, Multimedia Tools and Applications (2018), 1–19.

25.

Wang

, Fan

, Wang

, Wu

, Exploring local and overall ordinal information for robust feature description, IEEE transactions on pattern analysis and machine intelligence 38(11) (2016), 2198–2211.

26.

Matas

, Chum

, Urban

, et al., Robust wide-baseline stereo from maximally stable extremal regions, Image and Vision computing 20(10) (2004), 761–767.

27.

Fischler

M.A.

, Bolles

R.C.

, Random sample consensus, a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM 24(6) (1981), 381–395.

28.

Mikolajczyk

, Tuytelaars

, Schmid

, et al., A Comparison of Affine Region Detectors, International Journal of Computer Vision 60(1) (2005), 43–72.

29.

Christlein

, Riess

, Jordan

, et al., An evaluation of popular copy-move forgery detection approaches, IEEE Transactions on Information Forensics and Security 7(6) (2012), 1841–1854.

30.

Tralic

, Zupancic

, Grgic

, et al., CoMoFoD—New database for copy-move forgery detection, IEEE 55th international symposium on ELMAR (2013), 49–54.

31.

Wen

, Zhu

, Subramanian

, Ng

T.T.

, Shen

, Winkler

, COVERAGE—A novel database for copy-move forgery detection, IEEE International Conference on Image Processing (ICIP) (2016), 161–165.

Copy-move forgery detection based on local intensity order pattern and maximally stable extremal regions

Abstract

Keywords

1 Introduction

2 Overview of the proposed CMFD method

2.2.2 LIOP descriptor

3.1 Dataset

3.2 Metrics

3.3.1 Experiments on tampering factors

Table 1 The comparison of time-consuming Methods Respective time-consuming (average) Total time-consuming Feature extraction Matching CMFD-SIFT [13] 2.5 s 2.8 s 5.3 s ORB [16] 3.5 s 1.7 s 5.2 s Dense-field [20] 6.5 s 10.3 s 16.8 s ours 2.4 s 2.5 s 4.9 s

References

Table 1
The comparison of time-consuming

Methods Respective time-consuming (average) Total time-consuming

Feature extraction Matching

CMFD-SIFT [13] 2.5 s 2.8 s 5.3 s

ORB [16] 3.5 s 1.7 s 5.2 s

Dense-field [20] 6.5 s 10.3 s 16.8 s

ours 2.4 s 2.5 s 4.9 s