Silly solution to instagrams Tokyo stitching challenge

gistfile1.py

import numpy as np
from PIL import Image

# Hacky solution to the reassemble-Tokyo challenge:
# http://instagram-engineering.tumblr.com/

image = np.asarray(Image.open('/tmp/tokyo.png'))

# Auto-detect step size
guesses = np.arange(2, 200)
delta = np.array([np.mean((image[:,step-1:-1:step,:] - image[:,step::step,:])**2) for step in guesses])
step = np.min(guesses[np.argsort(delta)][-5:])

# Store seams to make indexing a bit easier
left_seams = image[:,0::step,:]
right_seams = image[:,step-1::step,:]

result = set()
for i in range(left_seams.shape[1]):
    result.add(min(
        (np.mean((left_seams[:,i,:] - right_seams[:,j,:])**2), i, j)
        for j in range(right_seams.shape[1])
    ))

# Build a chain but remove leftmost element because we know that
# no right seam points to it.
leftmost = max(result)
result.remove(leftmost)
chain = dict((x[2], x[1]) for x in result)

# Traverse pointers to build the original order
order = []
v = leftmost[1]
while v is not None:
    order.append(v)
    v = chain.get(v)

# Rearrange stripes
out_image = np.zeros_like(image)
for i, o in enumerate(order):
    out_image[:,i*step:i*step+step,:] = image[:,o*step:o*step+step,:]

Image.fromarray(out_image).save('/tmp/tokyo2.png')