Image Unscrambler challenge: http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder

.gitignore

*.swp

readme.markdown

Unscrambler

http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder

##Problem: Take the scrambled image, and try to reconstruct it

Assumptions: shreds are vertical, complete, and uniform in width

shreds are 32px wide

goal.png

shredded.png

unshredder.py

#!/bin/python
# conrad dean
# http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder
#
# Problem:
# Take the scrambled image, and try to reconstruct it
# Assumptions: shreds are vertical, complete, and uniform in width
# shreds are 32px wide

import Image,ImageChops

class Shredded:

    def __init__(self,file_path):
        self.original = Image.open(file_path)
        self.shred_count = 20 
        self.shred_width = self.original.size[0]/self.shred_count
        self.skip = 10 # shave time by only doing every nth row in an image

    def shred_zone(self,i):
        """ returns the shred rectangle region by index """
        if not 0 <= i <= self.shred_count:
            print i, "is not a propershred with", self.shred_count
            raise Exception
        x1, y1 = self.shred_width * i, 0
        x2, y2 = x1 + self.shred_width, self.original.size[1]
        return (x1, y1, x2, y2)

    def shred(self,i):
        """ returns the shred by index as an image """
        rectangle = self.shred_zone(i)
        return self.original.crop(rectangle)
        
    def compare_shreds_pixelbypixel_sum(self,left,right):
        left = self.shred(left)
        right = self.shred(right)
        #for rightmost col in left, and leftmost col in right, zip down and add up how nice those pixels are

        # get your columns of pixels
        # only look at some of the pixels
        rightmost_pixels = [left.getpixel((left.size[0]-1,y)) for y in range(left.size[1])]
        leftmost_pixels = [right.getpixel((0,y)) for y in range(right.size[1])]

        return sum(self.pixel_diff(r,l)**2 for r,l in zip(leftmost_pixels,rightmost_pixels))

    def compare_shreds_edgebinary(self,left,right):
        """
        Uses a binary-based pixel comparison instead of a distance metric
        """
        left = self.shred(left)
        right = self.shred(right)
        #for rightmost col in left, and leftmost col in right, zip down and add up how nice those pixels are

        # get your columns of pixels
        # only look at some of the pixels
        rightmost_pixels = [left.getpixel((left.size[0]-1,y)) for y in range(left.size[1])[::self.skip]]
        leftmost_pixels = [right.getpixel((0,y)) for y in range(right.size[1])[::self.skip]]

        return sum(self.pixel_diff_binary(r,l) for r,l in zip(leftmost_pixels,rightmost_pixels))

    def compare_shreds(self,left,right):
        """ returns a score of how good the shreds would feel
        if placed next to eachother.  smaller == better"""
        #return self.compare_shreds_pixelbypixel_sum(left,right)
        return self.compare_shreds_edgebinary(left,right)

    def pixel_diff(self,a,b):
        """ return a score of how different one pixel is from another """
        return max(abs(channelA - channelB) for channelA , channelB in zip(a,b))

    def pixel_diff_binary(self,a,b):
        diff = self.pixel_diff(a,b)
        threshold = 20
        return 1 if diff > threshold else 0

    def guess(self,shred_list):
        """
        feed it a list of indexes, and it returns a construction of the
        shreds in that order
        """
        #assert len(shred_list) == self.shred_count
        output = Image.new("RGBA", self.original.size)
        shreds = [self.shred(i) for i in shred_list]
        for s,i in zip(shreds,range(len(shreds))):
            destination_point = (self.shred_width*i,0)
            output.paste(s,destination_point)
        return output

    def best_on_right(self, anchor, possible_shreds):
        """
        pass it the index to one shred, and a list of many shreds and it'll
        decide the best matching shred if placed to the right of the anchor
        shred
        """
        # to do: if the best is not much better than the worst, or within a set threshold, return None to imply Anchor might be the rightmost shred
        guys = []
        for i in possible_shreds:
            guys.append((shredded.compare_shreds(anchor,i),i))
        return sorted(guys)[0][1]

    def best_on_left(self, anchor, possible_shreds):
        """pass it the index to one shred, and a list of many shreds and it'll decide
        the best matching shred if placed to the left of the anchor shred"""
        # to do: if the best is not much better than the worst, or within a set threshold, return None to imply Anchor might be the leftmost shred
        guys = []
        for i in possible_shreds:
            guys.append((shredded.compare_shreds(i,anchor),i))
        return sorted(guys)[0][1]

    def build_outward(self):
        """
        start with a shred, find the best match on the left and right sides,
        and choose the best from those two then treat the merged shred as
        the anchor and continue
        """
        remaining = range(self.shred_count)
        anchor = [remaining.pop()]
        while remaining:
            anchor_left_edge = anchor[0]
            anchor_right_edge = anchor[-1]

            on_left = self.best_on_left(anchor_left_edge,remaining)
            on_right = self.best_on_right(anchor_right_edge,remaining)

            if self.compare_shreds(on_left,anchor_left_edge) > self.compare_shreds(anchor_right_edge,on_right):
                anchor.append(on_right)
                #TODO remove()?
                remaining.pop(remaining.index(on_right))
            else:
                anchor.insert(0,on_left)
                remaining.pop(remaining.index(on_left))


        return anchor

    def show_pair(self,left,right):
        height = self.original.size[1]
        new = Image.new("RGBA",(self.shred_width*2, height))
        new.paste(self.shred(left),(0,0,self.shred_width,height))
        new.paste(self.shred(right),(self.shred_width,0,self.shred_width*2,height))
        new.show( title=str( self.compare_shreds(left,right),left , right))
        return ( self.compare_shreds(left,right),left , right)

def sameImage(i,j):
    """ returns True if image i and j match """
    return ImageChops.difference(i,j).getbbox() is None

shredded = Image.open("shredded.png")
goal = Image.open("goal.png")
goal_copy = Image.new("RGBA", goal.size)
goal_copy.paste(goal)

# naiive test of sameImage function against exact same data
assert sameImage(goal, goal)
# against different data copied over
assert sameImage(goal_copy, goal)
# make sure it can actually tell two different images apart
assert not sameImage(shredded, goal)

# tests
shredded = Shredded("shredded.png")
# assert that these pixels are different
assert 0 != shredded.pixel_diff(goal.getpixel((0,0)),goal.getpixel((24,88)))
# that these are the same
assert 0 == shredded.pixel_diff(goal.getpixel((24,88)),goal.getpixel((24,88)))
# make sure the .guess() can reconstruct the original
assert sameImage(shredded.original,shredded.guess(range(20)))
# make sure reversing the input list reverses the shred order
assert not sameImage(shredded.original,shredded.guess(range(20)[::-1]))

def fib(n):
    #for baseline time units
    if n in (0,1):
        return 1
    else:
        return fib(n-1) + fib(n-2)

from time import time
start = time()
fib(30)
fib30 = time() - start


start = time()
test = shredded.build_outward()
build = time() - start
print build, "seconds"
print build/fib30, "fib30's"

goal.show()
shredded.guess(test).show()
print "check if they're the samee"
assert sameImage(goal,shredded.guess(test))