Wednesday, February 13, 2008

Tonight, I'm going to write myself an Aston Martin

This is the story of my attempt to 'cheat' in an on-line spot-the-ball competition to win an Aston Martin. It's also the story of my failure, but you get free source code that implements automatic detection of image alteration using copy/paste or tools like the Clone Tool in Photoshop.

First, take a look at this photo:



Notice anything strange? In fact this image has been tampered with to cover up a truck. The truck is completely hidden by foliage. Here's the original:



Wouldn't it be nice to be able to detect that automatically? It is possible. Here's an image automatically generated by my code showing what was moved. All of the red was moved to the blue (or the other way around).



I was motivated to work on this program by greed (or at least my never-ending love of having a little flutter on things). Best of the Best runs spot-the-ball competitions in airports to win very expensive cars. But they also run the same competition online. That meant I could get my hands on the actual image used... could I process it to discover where the ball had been removed? (In reality, this isn't the right way to win because the actual ball position is not governed by where it actually was, but where a judge thinks it was).

Would it be cheating if I could? Apparently not, the competition rules say I should use my skill and judgment in determining the ball position. Surely, skill covers my programming ability.

So, I went looking for tampering algorithms and eventually came across Detection of Copy-Move Forgery in Digital Images written by Jessica Fridrich at SUNY Binghamton. The paper describes an algorithm for detecting just the sort of changes I thought I was looking for.

Unfortunately, I know nothing about image processing. Fortunately, the paper is written in a very clear style and a bit of Internet research enabled me to track down the knowledge I didn't have. (Also, thanks to Jessica for sending me the original images she used to test my implementation).

In brief the algorithm does the following:
  1. Slide a 16x16 block across the entire image from left hand corner to bottom right hand corner. For each 16x16 block perform a discrete cosine transform (DCT) on it and then quantize the 16x16 block using an expanded version of the standard JPEG quantization matrix.

  2. Each quantized DCT transformed block is stored in a matrix with one row per (x,y) position in the original image (the (x,y) being the upper left hand corner of the 16x16 block being examined).

  3. The resulting matrix is lexicographically sorted and then rows that match in the matrix are identified. For each pair of matching rows (x1,y1) and (x2,y2) the shift vector (x1-x2,y1-y2) (normalized by swapping if necessary so that the first value is +ve) is computed and for each shift vector a count is kept of the number of times it is seen.

  4. Finally the shift vectors with a count > some threshold are examined, the corresponding pair of positions in the image are found and the 16x16 blocks they represent are highlighted.

Here's another picture showing a golfing image that's been touched up to remove something from the grass:






To get access to image data I used the FreeImage library and wrote a small C program that implements Jessica's algorithm. You can download the source here; it's released to you under the GNU GPL.

The program has two key parameters that affect how the image is processed: the quality factor and the threshold.

The quality factor is a number used to 'blur' the image (actually it changes the quantization): the higher the factor the more blurring and hence more 16x16 blocks are likely to seem the same to the algorithm. Increasing the quality factor will tend to increase the false matches.

The threshold is simply the number of blocks that have to appear to have been copied together. This prevents us from seeing a single 16x16 block as evidence of copying. Increasing the threshold means ever larger groups of blocks have to be identified together before they are identified as copying.

Back at Best of the Best I grabbed the image for Supercar Competition (SC-272), cut out a section that I thought the ball had to be in (just to speed up processing) and ran the algorithm. After some parameter tweaking the algorithm came up only with what look like false matches to me (along the bar where it's all one color):



And, of course, that's not where the judge thought the ball was. So, I guess I won't be driving home in the V8 Vantage, but what geek needs that when they've got a cool piece of software that detects copy/move forgery in images?

Which leaves me with one question: how are spot-the-ball images generated? Is this an algorithm problem, a problem because they use JPG (which is already transformed) for their images, or are these images generated in some other way?

Labels:

21 Comments:

Blogger Geoff said...

John,

Thanks for an entertaining article. I love image processing code, but I work mostly in c#. Would you mind sharing the steps (or command line) that you use to compile?

6:42 PM  
Blogger John Graham-Cumming said...

Here's the Makefile:

copymove: LDLIBS += -lfreeimage -lstdc++
copymove: copymove.o

6:49 PM  
Blogger Geoff said...

Thanks John. I am having trouble compiling. Any ideas?
gcc gives me:
cm.cpp: In function `int main(int, char**)':
cm.cpp:162: error: invalid conversion from `void*' to `BYTE*'
cm.cpp:250: error: invalid conversion from `void*' to `int*'
cm.cpp:253: error: invalid conversion from `void*' to `position*'
cm.cpp:364: error: invalid conversion from `void*' to `int (*)(const void*, const void*)'
cm.cpp:364: error: initializing argument 4 of `void qsort(void*, size_t, size_t, int (*)(const void*, const void*))'
cm.cpp:371: error: invalid conversion from `void*' to `int*'

8:38 PM  
Blogger Darren said...

When you load the image file with fopen, you should be using "rb" for a binary file instead of "r". It doesn't make much difference under Linux but on OSes which use CR/LF pairs, the load will fail.

2:37 PM  
Blogger jjwiseman said...

What quality and threshold settings did you use for your example images?

8:35 PM  
Blogger Darren said...

With a little bit of work, I've got it compiling on MSVC++ 2003, and it works great.

The inner loop during "Building DCT transformed matrix" is a bit slow. I was able to get a huge speedup by precalculating all the pixel values for the image beforehand (i.e. the values of variable "pixel"), thus eliminating a lot of calls to FreeImage_GetScanLine() and round(), which are quite expensive.

Altogether it's a very effective algorithm! I've been very impressed by the results.

For the record, the main changes required for MSVC are casting the void* values to the appropriate pointer types, and also implementing round(x) as floor(x+0.5).

10:14 PM  
Blogger John Graham-Cumming said...

@geoff: see darren's comments about getting it working with MSVC.

@darren: I wondered about optimizing that but ran out of time to work further on the code. Glad to know you've improved it.

11:14 PM  
Blogger Geoff said...

The changes Darrin suggested provide an error-free compile on MSVC 9.

The algorithm works well. My wife is a wedding photographer and she's always retouching blemishes in the images. I'm going through her portfolio looking for evidence.

Darrin, any chance you'd be willing to post your speedup code?

2:05 PM  
Blogger John Graham-Cumming said...

@geoff. If you find anything cool then let people know!

3:12 PM  
Blogger Gregory said...

I'm trying to implement your code in Python. I'm having trouble understanding how you're doing the DCT. Any advice?

I'm also not sure what the purpose of the standard JPEG chrominance quantization matrix is for?

6:48 AM  
Blogger Gregory said...

Well I tried implementing it in Python. I got to the point of calculating the DCT stuff for each block, but it seems to run forever. (Perhaps that's why you did it in C?)

Here's the half finished code if anyone is interested in picking up the torch.

3:01 AM  
Blogger jjwiseman said...

I've posted the code with Darren's speedup, and tried it out on some of the altered photos by ex-Reuters photographer Adnan Hajj.

12:14 AM  
Blogger John Graham-Cumming said...

I love the posting in the previous comment about the Reuters photos. Very neat!

6:06 AM  
Blogger Hypermechanic said...

Do you have a windows compiled version?

7:00 AM  
Blogger redeye said...

Wow, I love this. Would it be possible to have this running server side with an interface on the web for users to check photos?

We could do something similar to the guy who set up that site that showed you who updated Wikipedia...

This would scare a lot media companies... :)

8:08 AM  
Blogger John Graham-Cumming said...

Sorry Hypermechanic I don't have a Windows compiled version, but others have mentioned building this on Windows.

4:16 PM  
Blogger JL said...

"...changes required for MSVC are casting the void* values to the appropriate pointer types..."

I'm more photographer than C programmer - could someone expand a bit on this (or better yet explicitly list the changes required)?

4:53 PM  
Blogger Lars said...

I'm guessing they create the spot-the-ball photos by taking two photos, offset in time, with a static camera. Then a careful copy - paste with a soft edge from one image to the other to remove the ball. That wouldn't show up as a clone operation.

Recent versions of Photoshop have built-in tools to automatically merge multiple images. You load up a series of images and mask / mark areas to keep or remove in each, and it blends it all into one "seamless" image. It's a handy trick to get a clean image of something when you're in a crowd and people keep getting in your shot, for example.

Here's a free tool from MS to do it: http://research.microsoft.com/projects/GroupShot/
or http://www.snapmania.com/info/en/trm/index.html

2:34 PM  
Blogger FayedYousry said...

Darren You have said that you were able to run it on VS2003
I am using VS2005 over the dotnet framework 2.0/3.5 and this piece of code is driving me nuts.
I do confess that my C is very rusty i have migrated to c# 6 years go. i am facing problems with the "stat" function as it produces a compile time error stating that there is no overload that takes 2 parameters! whats crazy is that intellisence saais it needs to parameters so does MSDN. If it is not too much trouble help me out on this or better yet uplod the code you were able to run of MSVS.
thank you

4:17 PM  
Blogger Jonathan said...

I believe there's a very simple explanation - they didn't duplicate any part of that picture.

Your algorithm assumes that the image was made using the clone tool, rather than another image or any other technique.

6:04 AM  
Blogger Rajesh said...

i too was trying to implement the paper on matlab. could u help me to get those forged images on which i can work on.. that will be a great help to me.

2:04 PM  

Post a Comment

Links to this post:

Create a Link

<< Home