Detecting forged photos algorithmically

John Graham-Cumming posted an automated tool for detecting “Clone Tool” Photoshop forgeries. Photojournalism ethics issues (LInk, Link) aside, John had some ulterior motives:

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.

Essentially the algorithm cuts the image into a bunch of 16×16 chunks and runs each chunk through a discrete cosine transform. The DCTed chunks are compressed and sorted, and the algorithm looks for multiple matching chunks that were shifted the same direction and distance, highlighting the source image if a large number of matches are found.

Another blogger, jjwiseman, released a speed optimization for John’s code, which he successfully used on the infamous Adnan Hajj Reuters images. While the algorithm is able to detect this style of manipulation, it’s noted that it has a habit of returning false positives in images with a blurry background.

That said, it’d be pretty interesting to run this through a big database of news photos and see what turns up.

Detection of Copy-Move Forgery in Digital Images – Link (PDF)
John Graham-Cumming’s Clone Tool Detector – Link
Protecting Journalistic Integrity Algorithmically (jjwiseman’s update) – Link