[image of digits]
The DARPA Challenge:

The $50,000 DARPA Shredder Challenge (archive)

WikiSource: Documents seized from the U.S. Embassy in Tehran/Shredded Documents
Ten revelations from the C.I.A.'s Tehran archives - the greatest loss of classified information since World War II.

If you were to solve these puzzles by hand, how would you go about it?

  1. Orient all shreds so that they are right side up (note the convex and concave arrow-shaped cross-cuts and the lines underneath the text).
  2. Arrange all the shreds parallel (in this instance, it is best to arrange the blue guide lines parallel).
  3. Set aside all the blank shreds (they may be useful later).
  4. Sort the shreds by the distance the writing is from the top, by large letters cut in half, and by any feature larger than shred width.
  5. Some large features to look for are the red ruling in puzzle 1, the red lettering and stains in puzzle 2, the heavy markings in puzzle 3, the stains in puzzles 4 and.
  6. Try to determine how the shredder cuts the shreds. In the case of puzzle 1, the long spaghetti-like shreds appear to be cut before the cross-cuts are made. Notice that the cross-cuts leave V-shaped ends which are useful in orienting the shreds right-side up. The V-shaped cross-cuts are not parallel, which was probably intended to add to the complexity of the reconstruction. In fact, this may have the opposite effect in providing overlapping information that can be used to grow the reconstruction.

Examples of the shreds of the five puzzles.

("Now translate these steps to pseudocode and then to valid computer code" is continued below the images.)

Puzzle 1: One image, approximately 192 pieces.

Puzzle 1: Solved by hand using PhotoShop.

Puzzle 2: Three images, approximately 396 pieces.

Puzzle 2: Solved by hand using PhotoShop.

Puzzle 3: Three images, approximately 1350 pieces.

Puzzle 4: Seven images, approximately 2016 pieces.

Puzzle 5: Twenty images, approximately 6600 pieces.

Evolutionary software to reconstruct a shredded image.

Now translate these steps to pseudocode and then to valid computer code.
Good luck! The shredded image descrambling application works with clean abstract data.
The DARPA problems require us to work with real world dirty data.

  1. Cut the individual sherds from the image.
  2. Turn them right-side up.
  3. Orient them carefully with the rulings on the paper.
  4. Characterize the shape of the top and bottom v-shaped cross-cuts.
  5. Characterize the shapes of the edges.
  6. Extract three lines of pixels representing the image of each edge and a vertical line down the center.
  7. Extract an image of the entire shred.
  8. Index each image on the basis of basis of the positio of the rulings and the lettering falling off each edge.
  9. Try a preliminary assembly on that basis.
  10. More advanced pattern & content (i.e. meaning) recognition would be required to assemble letters and words.
  11. I expect a hybrid approach using human supervised computational techniques would be the most effective..

A hybrid method using PhotoShop:

  1. Open the .tif image file in PhotoShop.
  2. It appears that the uniformity of the background can be enhanced by eliminating the blue channel.
  3. Us the selection tool to select the color in the background.
  4. Invert the selection to select only the sherds.
  5. Do a cut and paste, moving the sherds to layer 1..
  6. Select the magenta background layer and paint it all in the background color.
  7. On the sherds layer 1, you can cut and paste an individual sherd onto a new layer, e.g. layer 2,
  8. You can now move it around and merge it with other layers, thus building an assemblage of pieces.
  9. In the process, after you cut a sherd, you can do a file/new, paste it in and use the crop tool to orient it. Then using select/all, you can copy and paste it back into the main image.
  10. This is how the 14 sherds were assembled below...

A hybrid method using a laser-cutter:

  1. Open the .tif image file in Corel Draw.
  2. Outline the edges with a line of zero thickness.
  3. Place the image in the laser-cutter and send the outlined data to the laser-cutter as cut pattern.
  4. You now have a physical model of the individual sherds themselves.
  5. Could we solve some of these puzzles collectively in class?