COPY-MOVE DETECTION ALGORITHM BASED ON LOCAL DERIVATIVE PATTERNS

Abstract

Copy-move forgery is one of most frequently used types of image forgery. During copy-move process a fragment of the image is copied and pasted to another location of the same image to hide some important area of the image. The purpose of copy-move forgery detection algorithm is to identify duplicated areas in the image. This method is based on the calculating features in a sliding or an overlapping window. In this paper, the copy-move detection algorithm using local derivative pattern is proposed. Experimental results show high detection accuracy when the proposed solution is used. Distinctive characteristics of the local derivative pattern based features are robustness to distortions of the duplicated area and low computational complexity.

Keywords

• copy-move
• forgery
• local derivative pattern
• local binary pattern
• hash value

-

At present, digital images and videos are the most common instruments of information transfer. For example, they are used to confirm an event in mass media. Wide software availability has led to the fact that the process of changing images becomes very simple. In the last 10-15 years, scientists developed algorithms of artificial forgery detection in digital images to provide data security [ 1-3 ]. These algorithms make possible to find image area modifications and define forgery characteristics made by criminals.

Embedding copy-move fragments is one of most frequently used methods of image forgery because its easy use. The process of embedding consists of three consecutive stages: copying of an image fragment, distortion of this fragment and pasting it in another area of the same image that has to be hidden. Despite the large number of existing solutions, many of them are not computationally efficient. That is the task of development of copy-move detection algorithms with high accuracy and low computational complexity is challenging.

This paper is organized as follows. The first section provides basic information about local binary pattern and local derivative pattern. The second section is dedicated to the copy-move forgery detection algorithm description. The third section contains the experimental results carried out using the set of images with copy-move forgery. 2 2.1

Local Patterns

Local Binary Pattern

The idea of local binary pattern (LBP) belongs to Wang [ 4 ]. In the original LBP variant, a 3  3 window is used. Eight neighborhood point values around a pixel are compared with central point value. Depending on the comparison result, the central pixel is labeled as 8-bit number. The process of LBP code calculation is presented in Fig. 1. (1) (2) The image can be formally represented as an intensity function of the pixel f (x, y) . LBP-code is computed for every pixel using pixel values from circular neighborhood fi  f (xi , yi ), i  1, P , where P is a number of equidistant neighbors of the central pixel located on a circle of radius R (Fig. 2) as follows:

N 1 LBP(N, R)   I1( fi  f0 )  2i ,

i0 where I1 is a predicate defined as follows:

0, m  0 I1(m)   1, m  0 . Also it should be noted that the LBP method is very effective because of its low computational complexity. The main disadvantage of this type of pattern is its sensitivity to noise distortions [ 5 ]. 2.2

Local Derivative Pattern

In fact, LBP code is a result of applying the first-order derivative of the neighborhood of the center pixel as shown in (1). For a more informative description of the image the operator LDP was proposed in [ 6 ]. This operator allows encoding the information obtained as a result of high-order derivatives calculation. n-order derivative along various directions that are used in this method are calculated using binary encoding function.

The first-order derivatives along 0,45,90 and 135 directions are denoted as f  (x0 , y0 ) , where   0,45,90,135 . The first-order derivatives at ( x0 , y0 ) position can be written as follows: f0 (x0 , y0 )  f0  f 4 , f90 (x0 , y0 )  f0  f 2 , f 45 (x0 , y0 )  f0  f3 , f135 (x0 , y0 )  f0  f1.

The second-order directional LDP along the  direction at ( x0 , y0 ) is defined as follows: LDP2 (x0 , y0 )  I 2 f  (x0 , y0 ), f  (x1, y1),

I 2 f  (x0 , y0 ), f  (x2 , y2 ), ...

I 2 f  (x0 , y0 ), f  (x8 , y8 ), where I 2 is a predicate defined as follows:

0, m  n  0 I 2 (m, n)   1, m  n  0

Finally, the second-order LDP is defined as the concatenation of the four 8-bit directional LDPs: LDP 2 (x, y)  {LDP2 (x, y) |   0,45,90,135}.

As it can be seen from the equations above, LDP operator assigns a code to each pixel of the image by comparing two derivatives along the same direction for two adjacent pixels. Then obtained codes are concatenated into a single sequence of 32 bits. Equations derivatives along  direction are performed using 16 primitive patterns [ 4 ] (see Fig. 3). These patterns characterize distinctive spatial relationships in the local area. (3) (4) (5) (6) Unlike LBP, the second-order LDP allows to encode the change of derivative value along a fixed direction. This change represents a characteristic of a local image area. a-1) b-1) c-1) d-1) a-2) b-2) c-2) d-2) a-3) b-3) c-3) d-3) a-4) b-4) c-4) d-4) When applying the pattern a-1 (Fig. 3a.) by superposition of  to f 0 , both directional derivatives increase monotonically as shown in Fig. 4(d-1). Thus, the primitive pattern corresponds to the value of ‘0’. Similarly, applying the patterns a-2, a-3 and a-4 (Fig. 3a.) by superposition of  to f 0 corresponds to the cases shown in Fig. 4(b-1), Fig. 4(d-1) and Fig. 4(a-2), correspondingly. As a result, the following three bits of directional LDP are calculated as ‘101’. We then repeat the above procedure with the same four patterns but now using superposition of  to f 0 . According to this we get a bit sequence ‘0100’ for the last four bits. As a result, the code ‘01010100’ is formed for directional LDP along   0 . In the same way, the codes of the primitive patterns shown in Fig. 3b-3d are formed along   45,90,135 directions, correspondingly. Finally, we get the following 32-bit code: ILmDagPe2P(rfo0c)essin0g1,0G10e1o0in0f0o0rm1a0ti1c1s1a1n1d1I0n1fo0rm00a0ti1o1n0S0e0c1ur1it0y, Evdokimova NI. et al… that is generated by concatenation of the four 8-bit LDP along   0,45,90,135 directions in accordance with (6).

a-1) a-2) b-1) b-2) c-1) c-2) d-1) d-2)

Fig. 4. Types of local transitions used for encoding primitive patterns of LDP Calculation of the n-order derivatives along directions   0,45,90,135 at the f 0 position provides n-order directional LDP that are defined as follows: LDPn x0 , y0   I 2  fn1 x0 , y0 , fn1 x1, y1 ,

I 2  fn1 x0 , y0 , fn1 x2 , y2 , ...

I 2  fn1 x0 , y0 , fn1 x8 , y8 , where fn1(x0 , y0 ) is the (n-1)-order derivative along the  direction at x0 , y0  . It represents the change of (n-1)-order gradient and provides additional information about the local neighborhood. Finally, the n-order LDP is determined by the following expression: LDP n (x, y)  {LDPn (x, y) |  0,45,90,135}.

Thus, n-order LDP is also based on derivatives along the four directions. High-order local derivative patterns allow to describe local neighborhood in a more detailed way than first-order local derivative pattern that is used in LBP. However, they become more sensitive to noise with derivative order increase. In the paper [ 6 ], the authors proposed that the LDP sensitivity to noise increases when the order n  4 . Given this constraint, we will use only second- and third-order LDP.

The advantages of LDP to LBP can be summarized as follows: ─ LBP is not able to provide a detailed description of the image features. n-order LDP allows forming a more detailed description of the image local area using (n1)-order directional derivatives. ─ LBP describes the relationship between the central pixel and its neighbors. LDP allows encoding various spatial relationships in the local area of the image and therefore represents more information about spatial features. (7) (8)

Copy-move Detection Algorithm

Most of existing solutions [ 1,7 ] use features extraction in overlapping blocks of an image and then nearest features search is applied. This approach definitely leads to missing duplicates increase due to overlapping blocks analysis.

In this paper we use the algorithm proposed in the papers of Kuznetsov AV, Myasnikov VV and Glumov NI [ 8-10 ]. The algorithm consists of the following main steps: 1. Calculation of the values of local pattern codes (LBP or LDP) using the sliding the sliding window of the size 5  5 . The values are put in the code matrix. 2. Hash values calculation [ 9 ] based on the code matrix data using the sliding window. 3. Putting hash values into the hash value matrix. 4. Construction hash values histogram. 5. Analysis of the hash value histogram. Hash values frequency exceeding ‘1’ are searched in the histogram. 6. Output binary image generation which shows the places of potential duplicates. The hash function of an image fragment is defined as a transform that puts each value of the code matrix in correspondence with a non-negative integer value (hash value) [ 8-10 ]. The histogram of hash values stores hash values frequency appearance in the image. The frequency value characterizes potential copy-move forgery regions. 4

Experiments

The experiments were carried out on a desktop PC with Intel Core i5-3470 processor and 8 GB RAM using MATLAB R2014a software.

Ten gray-scale digital images with dimensions 512  512 were chosen as the objects of experiments. The authors developed a copy-move generation procedure which enables to add distortions and control their parameters (linear contrast enhancement and Gaussian noise).

We used F1_Score value as a quality measure. It combines detection accuracy value and false positive and false negative errors to estimate the quality of the proposed solution. F1_Score is defined as follows: F1 

2  tp 2  tp  fp  fn . (9) The results of experiments that were carried out on the set of generated images are showed in Table 1 and Table 2.

Linear Contrast

Gaussian Noise

Linear Contrast

Gaussian Noise

5

Conclusion

During the described research the algorithm that based on LDP was developed. It allows to detect distorted copy-move forgeries in digital images. Due to the specifics of local patterns, the algorithm has low computational complexity so it can be used to analyze large images (e.g. remote sensing data). Research of copy-move forgery detection with geometric distortions and compression is not presented in this study and will be done further. We also plan to compare the quality of the proposed copy-move forgery detection algorithm with existing solutions based on the features calculation in future works.

Acknowledgements

This work was supported by Samara National Research University State contract №2014/198 (project code 2298) and the Russian Foundation for Basic Research (RFBR) grant № 16-37-00056 мол_а.

References

1. Christlein V , Riess C , Jordan J , Angelopoulou E. An evaluation of popular copy-move forgery detection approaches . IEEE Trans. Inf. Forensic Secur , 2012 ; 7 ( 6 ): 1841 - 1854 .

2. Popescu A , Farid H . Exposing digital forgeries by detecting duplicated image regions . URL: http://www.ists.dartmouth.edu/library/102.pdf

3. Fridrich J , Soukal D , Lukas J . Detection of copy-move forgery in digital images . URL: http://www.ws.binghamton.edu/fridrich/Research/copymove.pdf

4. Wang L , He D-C. Texture classification using texture spectrum . Pattern Recognition , 1990 ; 23 ( 8 ): 905 - 910 .

5. Ren J , Jiang X , Yuan J . Noise-Resistant Local Binary Pattern With an Embedded ErrorCorrection Mechanism . IEEE Trans. Im. Proc. , 2013 ; 22 ( 10 ): 4049 - 4060 .

6. Zhang B , Gao Y , Zhao S , Liu J . Local derivative pattern versus local binary pattern: face recognition with high-order local pattern descriptor . IEEE Trans. Im. Proc. , 2010 ; 19 ( 2 ): 533 - 544 .

7. Kuznetsov AV , Myasnikov VV . A copy-move detection algorithm based on binary gradient contours . Computer Optics , 2016 ; 40 ( 2 ): 284 - 293 . DOI: 10 .18287/ 2412 -6179-2016-40- 2- 284 -293.

8. Glumov N , Kuznetsov A , Myasnikov V. The algorithm for copy-move detection on digital images . Computer Optics , 2013 ; 37 ( 3 ): 360 - 367 .

9. Kuznetsov A , Myasnikov V. A fast plain copy-move detection algorithm based on structural pattern and 2D Rabin-Karp rolling hash . In: Campilho A , Kamel M . (eds.) ICIAR 2014 , Springer, Heidelberg. Part I. LNCS , 8814 : 461 - 468 .

10. Kuznetsov AV , Myasnikov VV . Efficient linear local features based copy-move detection algorithm . Computer Optics , 2013 ; 37 ( 4 ): 489 - 495 .