Solved: DARPA’s Challenge To Reconstruct Shredded Documents

It sounds insane, but DARPA recently laid down a challenge to computer scientists: work out how to reconstruct shredded pages of paper. The winning team has finished — two days ahead of schedule.

The competition was launched at the end of October, and the idea was to develop software capable of piecing together documents that had been passed through a shredder, reports New Scientist. To prove they’d completed the task, participants were required to provide the answer to puzzles embedded in the content of the reconstructed document.

The winning team, called “All Your Shreds Are Belong To U.S.”, completed the task on December 2, 2011, and walk away with a $US50,000 prize in the process. The team comprised three programmers based in San Francisco: Otavio Good, creator of the visual translation tool Word Lens, Luke Alonso, a mobile phone software developer, and Keith Walker, who works on satellite software at Lockheed Martin. Seems they’re quite good.

Though there isn’t much information available about the tools they used to solve the problems, it is known that their winning algorithm automatically pieced together matching scraps based on factors like the shape of the rip or the marks on the paper. There was an element of human intervention involved too, and solutions were tried out by hand some of the time.

Does this all mean that shredding document is a complete waste of time, then? Not according to Otavio Good, from the team, who told New Scientist:

“The challenges that DARPA gave us were actually simple compared to if you have a bin full of lots of shredded pieces of paper. Reconstructing these documents was not easy at all. I don’t think you have much to worry about with your shredded documents.”

So, all those paranoid folks who shred anything with their name on may as well keep at it for now. [New Scientist]

Image: iowa_spirit_walker