Overview of Digital Cloning

Introduction

The growth of the image processing and editing software availability has made it easy to manipulate digital images.
With the amount of digital content being generated nowadays, developing  techniques to verify the authenticity and integrity of digital content might be essential to provide truthful evidences in a forensics case.
In this context, copy-move is a type of forgery in which a part of an image is copied and pasted somewhere else in the same image. This forgery might be particularly challenging to discover due to properties like illumination  and noise matching on the source and the tampered regions. An example of copy-move forgery can be seen in picture 1. First we can see the original image, followed by the tampered one, and then a picture with the indication of the cloned areas.

Several techniques have been proposed to solve this problem. The Block-based methods [1] divide an image in blocks of pixels and compare them to find a forgery.

Keypoint-based methods [2] on the other hand extract keypoints of an image  and use these to find tampered regions.

While keypoints might generate better and computationally efficient detectors [3]  they also present difficulty in finding tampering in homogeneous regions.

State-of-the-Art

Many block-based algorithms have been proposed over the years. Involving mainly dividing the image in a fixed size b of pixels, they differ on how they compare the blocks.
Once blocks are extracted from a NxM image, they are usually inserted  lexicographically in a M - b + 1 x N - b + 1 matrix. This matrix is latter on analysed to see if any two lines match as a cloned region. Authors have proposed ways to improve this method such as using PCA to reduce the blocks dimensions.

Among several approaches in the literature, the cloning detection via multiscale analysis and voting method can be highlighted, proposed by Ewerton Silva et al. The first step on the process here is to extract keypoints of interest in an image using SURF, robust to scaling and rotating, and then match such points between themselves. These points are then grouped based on their physic distance, to limit the search space. The image is then redimensioned,
creating a type of pyramid of images, representing the several scales of the image. In each level of the pyramid, a search is made for possible duplicated regions. This search only occurs in the point groups discovered. The final decision is made based on a voting process, if a certain region is considered cloned in more than a threshold of levels of the pyramid.

Another work worth mentioning is an evaluation made on copy-move forgery approaches, by Christlein et al. 15 different copy-move detection approaches were compared in their work such as SIFT, SURF, PCA, KPCA, Zerkine,
DCT and DWT. They aimed to answer which algorithm performed best against realistic scenarios like different compressions and noise. Results showed that keypoints methods (SIFT and SURF) had clear computational complexity advantage, but other block based methods like Zernike achieved quite precise results.

References

[1] Connelly Barnes, Eli Shechtman, Adam Finkelstein, and
Dan B. Goldman. The generalized patchmatch correspon-
dence algorithm. 2010.
[2] Ewerton Silva and Anderson Rocha. Cloning detection. In
Elsevier JVCI 2013 (Submited).
[3] Christian Riess Johannes Jordan Corinna Riess Elli An-
gelopoulou Vincent Christlein. Evaluation of popular copy-
move forgery detection approaches. In IEEE Transactions on
Information Forensics and Security (TIFS) 2012, pages 015–
021, Graz, Austria, 2010.
[4] Andrea Vedaldi. An implementation of multi-dimensional
maximally stable extremal regions. 2007.

This topic was inspired from a class I took with Anderson Rocha. See his publications on digital forensics here: http://www.ic.unicamp.br/~rocha/pub/index.html.