##Problem: Take the scrambled image, and try to reconstruct it
Assumptions: shreds are vertical, complete, and uniform in width
shreds are 32px wide
*.swp |
##Problem: Take the scrambled image, and try to reconstruct it
Assumptions: shreds are vertical, complete, and uniform in width
shreds are 32px wide
#!/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)) |