Sunday, March 15, 2009

Detecting copy-move forgery in images

This time I`ll talk about digital image forensic and how to detect copy-move forgery in images. I`ve implemented some ad-hoc algorithm for detection of this kind of forgeries. Algorithm is robust, so it can detect forgeries in lossy image formats- such as JPEG. Please keep in mind - this algorithm is experimental toy, if you want more general solutions - you should read this paper or maybe this to get some ideas in the field. BTW, this algorithm is only tested with Python 2.6, so you better install Python 2.6.

Robust detection algorithm steps
1. Blur image for eliminating image details
2. Convert image to degraded palette
3. Decompose image into small NxN pixel blocks
4. Alphabetically order these blocks by their pixel values
5. Extract only these adjacent blocks which have small absolute color difference
6. Cluster these blocks into clusters by intersection area among blocks
7. Extract only these clusters which are bigger than block size
8. Extract only these clusters which have similar cluster, by using some sort of similarity function (in this case Hausdorff distance between clusters)
9. Draw discovered similar clusters on image

Copy-move detection script usage instructions
Run script from the command line - cmd in Windows or terminal in Linux.
1. At first try to execute script with default parameters-
python detect_copymove.py image_file.jpg

2. Then try to lower block color deviation threshold-
python detect_copymove.py image_file.jpg --blcoldev=0.05

3. Finally - run script in manual mode and try to spot similar regions by eyes-
python detect_copymove.py image_file.jpg --blcoldev=0.05 --imauto=0

If by trying all 3 steps - no copy-move tamperings revealed - there is a good chance that really there are no such tamperings in image. BTW, script has more parameters, full list of them -
python detect_copymove.py --help

Experiments - object cloning forgery
This type of forgery tries to deceive viewer that there were more objects than really was.
Original picture:

Doctored image:

Copy-move script output:

As you see script detected cloning of one tank, but did not detected cloning of tank in further row. This can be because of small size of that tank and because that tank is on boundary of image.

Experiments - object hiding forgery
In this type of forgery viewer is deceived that there were less objects than in reality was.
Original image:

Doctored image:

Copy-move script output:


Experiments - mixed type forgery
In this type of forgery some objects was hidden, some - cloned.
Original picture:

Doctored image:

Copy-move script output:

As you see script detected 2 forgeries - cloning of dog, and cloning of background (which was done with intention to hide other dog)

Conclusions
Copy-move forgery detection script works not bad. However it is also not perfect of course (may not detect all tamperings, so called false negative rate is not zero of course). And I`ve not tested very well, but I suppose script also have false positive rate - i.e. can detect areas which actually was not tampered. But all in all - I think this algorithm is pretty obvious and can be simply implemented and used as first line of defense against copy-move forgeries.

Have fun in copy-move forgeries hunting !!

12 comments:

  1. I have an error:
    File "C:\detect_copymove.py", line 15, in
    from PIL import Image, ImageFilter, ImageDraw
    ImportError: No module named PIL

    Can you help me?

    ReplyDelete
  2. You need to install Python image processing library. You can get it from here-

    http://www.pythonware.com/products/pil/

    Good luck!

    ReplyDelete
  3. Hi,
    very nice script! But I have a little problem testing it on some images, it quits processing after a few seconds with the following error message:

    Analyzing image, please wait... (can take some minutes)
    Traceback (most recent call last):
    File "detect_copymove.py", line 229, in
    dparts = similarparts(lparts)
    File "detect_copymove.py", line 131, in similarparts
    if dev/mean >= float(opt.blcoldev):
    ZeroDivisionError: float division

    But great tool though ;-)

    ReplyDelete
  4. Hi, I've uploaded the picture occuring the error described above on the following webpage:
    http://www.dj9kw.de/Cherries.jpg

    Best regards,

    Thomas

    ReplyDelete
  5. Ha changing the background color from white to dark seems to fix the problem

    ReplyDelete
  6. Hi Thomas !

    That error now is fixed. Error was related with image conversion to custom color palette :-)

    BTW, it is interesting to note that script with default parameter set doesn`t reveals tamperings in your given image.
    But these parameters reveals ! =>

    python detect_copymove.py Cherries.jpg --blcoldev=0.05 --impalred=30 --blsim=100 --rgsim=2

    Good luck
    and thanks for testing ! :-)

    ReplyDelete
  7. i too am working on the detection of copy move. can u plz tell me where i could get those images to work on.

    ReplyDelete
  8. @Rajesh

    If you are asking about test images,- you can use doctored images from this blog post. Or you can search other doctored images on net. Or make your own ;)

    Good luck!

    ReplyDelete
  9. how long did it take for your code to execute completely?

    ReplyDelete
  10. @sneha

    Hm. Depends on image size and script input parameters. On 400px × 300px image with default parameters it may run under several minutes.
    It would be good one day to measure time complexity of script - assuming all parameters set to default values. (But this doesn't make any sense for images which tamperings isn't detected with default parameters...)

    ReplyDelete
  11. Hi, your tools is great. It's not just a toy since the idea of several papers about copy-move detection is based on the same idea (they just use different features for their approach: DCT, SVD, wavelet coefficient, PCA,..)
    However I run your script with several combinations of option, it can only detect the parade_doc.jpg. Dogs and dunes failed. What's the parameter to get the result like the given result here?

    ReplyDelete
  12. @langthangtrenmang

    Thanks !
    Try such option:

    detect_copymove.py dune_doc.jpg --blcoldev=0.05

    ReplyDelete

Comment will be posted after comment moderation.
Thank you for your appreciation.