Instagram Challenge (http://instagram-engineering.tumblr.com/)

unshred.py

#!/usr/bin/python

from PIL import Image
from math import sqrt
from numpy.fft import rfft
from collections import Counter

def computeContinuityScore(image, x1, x2):
  width, height = image.size
  data = image.getdata()
  score = 0
  for i in xrange(height):
    rgba1 = data[x1 + i * width]
    rgba2 = data[x2 + i * width]
    for j in xrange(4):
      score += (rgba1[j] - rgba2[j]) * (rgba1[j] - rgba2[j])
  return score

def mostSignificantFrequency(lst):
  # norm of fourier components
  frequencies = abs(rfft(lst))
  length = len(frequencies)
  avg = sum(frequencies) * 1. / length
  stdev = sqrt(sum([(x - avg) * (x - avg) for x in frequencies])) / length

  spikes= []
  for i, f in enumerate(frequencies):
    # if f is a local maximum and much larger than the average
    if ((i == 0 and frequencies[1] < f) or \
        (i == length - 1 and frequencies[-2] < f) or \
        (frequencies[i - 1] < f and frequencies[i + 1] < f)) and \
        f > avg + 2. * stdev:
      spikes.append(i)

  # calculate intervals between adjacent spike positions
  diffs = [x - spikes[i - 1] for i, x in enumerate(spikes) if i != 0]

  # neglect peaks near zero and find common intervals; that is,
  # there are pixel-to-pixel fluctuations whose sizes are comparable to
  # shred edges, but we only want to find repetitive pattern
  diff = Counter(diffs[len(diffs) // 2:]).most_common(1)[0][0]

  return diff

class CONTINUE: pass

def solve(scores):
  # It's a Traveling Salesman Problem
  # Given a path tail i, find j from subpath heads such that score[i][j] is the smallest
  # then for each k of all subpath tails, compare score[k][j] with score[i][j]
  # If score[i][j] is the smallest of all, then the path i -> j is confirmed
  # Otherwise start from another point

  paths = [[i] for i in xrange(len(scores))] # initially all paths are single

  while True:
    try:
      # take a subpath, call it the path
      #path = paths.pop()
      path = paths[0]
      del paths[0]

      while True:
        minScore = float('inf')

        for sub in paths:
          score = scores[path[-1]][sub[0]]
          if score < minScore:
            minScore = score
            joinTo = sub

        print path, joinTo, minScore

        for sub in paths:
          if sub == joinTo or scores[sub[-1]][joinTo[0]] > minScore: continue
          #paths.insert(0, path)
          paths.append(path)
          print paths
          raise CONTINUE # continue outer loop

        paths.remove(joinTo)
        path.extend(joinTo)

        if len(paths) == 0: return path

    except CONTINUE:
      pass

def main():
  image = Image.open('input.png')
  width, height = image.size

  scores = [computeContinuityScore(image, 0, width - 1)]
  for i in xrange(width - 1):
    scores.append(computeContinuityScore(image, i, i + 1))

  print scores

  numShreds = mostSignificantFrequency(scores)
  shredWidth = width // numShreds

  #print(numShreds, shredWidth)

  # calculate scores of j-th shred being next to the i-th shred (small = better)
  scores = []
  for i in xrange(numShreds):
    rightEdge = (i + 1) * shredWidth - 1
    _scores = []
    for j in xrange(numShreds):
      if i == j:
        _scores.append(float('inf'))
      else:
        leftEdge = j * shredWidth
        _scores.append(computeContinuityScore(image, rightEdge, leftEdge))
    scores.append(_scores)
    print _scores

  #print scores
  #order = solvePath(scores)
  order = solve(scores)
  print order

  unshredded = Image.new('RGBA', image.size)
  for i, n in enumerate(order):
    box = (n * shredWidth, 0, (n + 1) * shredWidth, height)
    unshredded.paste(image.crop(box), (i * shredWidth, 0))

  unshredded.save('output.png', 'PNG')

if __name__ == '__main__':
  main()

The first revision fails because the original photo becomes darker at both ends. The right-most shred joins to the left-most shred.
http://f.hatena.ne.jp/edvakf/20111120225419