From 7ab4a4d6f5575f114d16dc06cfa152b3b3a51db0 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Sun, 13 Nov 2011 19:47:28 -0500 Subject: Initial commit. --- TokyoPanoramaShredded.png | Bin 0 -> 617432 bytes bird-shred.png | Bin 0 -> 511265 bytes reshredded.png | Bin 0 -> 617339 bytes shred.py | 29 ++++++++++ unshred-binary-merge-failure.py | 81 ++++++++++++++++++++++++++++ unshred.py | 116 ++++++++++++++++++++++++++++++++++++++++ 6 files changed, 226 insertions(+) create mode 100644 TokyoPanoramaShredded.png create mode 100644 bird-shred.png create mode 100644 reshredded.png create mode 100755 shred.py create mode 100755 unshred-binary-merge-failure.py create mode 100755 unshred.py diff --git a/TokyoPanoramaShredded.png b/TokyoPanoramaShredded.png new file mode 100644 index 0000000..be74187 Binary files /dev/null and b/TokyoPanoramaShredded.png differ diff --git a/bird-shred.png b/bird-shred.png new file mode 100644 index 0000000..ab41cb8 Binary files /dev/null and b/bird-shred.png differ diff --git a/reshredded.png b/reshredded.png new file mode 100644 index 0000000..ec1e05f Binary files /dev/null and b/reshredded.png differ diff --git a/shred.py b/shred.py new file mode 100755 index 0000000..40face9 --- /dev/null +++ b/shred.py @@ -0,0 +1,29 @@ +#!/usr/bin/env python + +# Instagram Shredder +# by Jason A. Donenfeld +# for http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder + +from PIL import Image +from random import shuffle +from sys import argv, exit, stderr + +if len(argv) < 4: + print >> stderr, "Usage: %s columns input output" % argv[0] + exit(-1) + +columns = int(argv[1]) +image = Image.open(argv[2]) +shredded = Image.new("RGBA", image.size) +width, height = image.size +shred_width = width / columns +sequence = range(0, columns) +shuffle(sequence) + +for i, shred_index in enumerate(sequence): + shred_x1, shred_y1 = shred_width * shred_index, 0 + shred_x2, shred_y2 = shred_x1 + shred_width, height + region = image.crop((shred_x1, shred_y1, shred_x2, shred_y2)) + shredded.paste(region, (shred_width * i, 0)) + +shredded.save(argv[3]) diff --git a/unshred-binary-merge-failure.py b/unshred-binary-merge-failure.py new file mode 100755 index 0000000..abb19c5 --- /dev/null +++ b/unshred-binary-merge-failure.py @@ -0,0 +1,81 @@ +#!/usr/bin/env python + +# Instagram Unshredder -- Binary Simplify Failure +# by Jason A. Donenfeld +# for http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder + +from PIL import Image +from sys import argv, exit, stderr +from math import sqrt + +if len(argv) < 4: + print >> stderr, "Usage: %s columns input output" % argv[0] + exit(-1) + +image = Image.open(argv[2]) +data = image.getdata() +columns = int(argv[1]) +shred_width = image.size[0] / columns + +def pixel(x, y): + pixel = data[y * image.size[0] + x] + return pixel +def pixel_distance(a, b): + opacity_a = a[3] / 255 + opacity_b = b[3] / 255 + a_r, a_g, a_b = (a[0] * opacity_a, a[1] * opacity_a, a[2] * opacity_a) + b_r, b_g, b_b = (b[0] * opacity_b, b[1] * opacity_b, b[2] * opacity_b) + return sqrt((a_r - b_r) ** 2 + (a_g - b_g) ** 2 + (a_b - b_b) ** 2) +def match_score(left, right): + left = left[len(left) - 1] + right = right[0] + total = 0 + for i in xrange(0, image.size[1]): + total += pixel_distance(pixel((left + 1) * shred_width - 1, i), pixel(right * shred_width, i)) + return total +def binary_simplify(order_lists): + simplified = list() + blacklist = list() + for i in order_lists: + if i in blacklist: + continue; + minimum = image.size[1] * 442 # = sqrt(3) * 255 + value = None + right = False + for j in order_lists: + if i == j or j in blacklist: + continue + score = match_score(i, j) + if score < minimum: + minimum = score + value = j + right = True + score = match_score(j, i) + if score < minimum: + minimum = score + value = j + right = False + if value == None: + smushed = i[:] + elif right: + smushed = i[:] + smushed.extend(value) + else: + smushed = value[:] + smushed.extend(i) + simplified.append(smushed) + blacklist.append(i) + blacklist.append(value) + return simplified + +column_order = [[i] for i in xrange(0, columns)] +print column_order +while len(column_order) > 1: + column_order = binary_simplify(column_order) + print column_order +column_order = column_order[0] + +unshredded = Image.new("RGBA", image.size) +for destination, source in enumerate(column_order): + unshredded.paste(image.crop((shred_width * source, 0, shred_width * source + shred_width, unshredded.size[1])), (destination * shred_width, 0)) +unshredded.save(argv[3]) diff --git a/unshred.py b/unshred.py new file mode 100755 index 0000000..ea20810 --- /dev/null +++ b/unshred.py @@ -0,0 +1,116 @@ +#!/usr/bin/env python + +# Instagram Unshredder +# by Jason A. Donenfeld +# for http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder + + +from PIL import Image +from sys import argv, exit, stderr +from math import sqrt + +if len(argv) < 3: + print >> stderr, "Usage: %s input output" % argv[0] + exit(-1) + +image = Image.open(argv[1]) +data = image.getdata() + +def pixel(x, y): + pixel = data[y * image.size[0] + x] + return pixel +def pixel_distance(a, b): + opacity_a = a[3] / 255 + opacity_b = b[3] / 255 + a_r, a_g, a_b = (a[0] * opacity_a, a[1] * opacity_a, a[2] * opacity_a) + b_r, b_g, b_b = (b[0] * opacity_b, b[1] * opacity_b, b[2] * opacity_b) + return sqrt((a_r - b_r) ** 2 + (a_g - b_g) ** 2 + (a_b - b_b) ** 2) +columns = [] +for col in xrange(0, image.size[0] - 1): + columns.append(0) + for row in xrange(0, image.size[1]): + columns[col] += pixel_distance(pixel(col, row), pixel(col + 1, row)) +shred_width = -1 +for factor in xrange(2, image.size[0]): + if image.size[0] % factor != 0: # Poor man's factorization! R.I.P. Sieve. Sorry instagram. + continue # I'm also ignoring your guidelines about divisibility by 2. + last_col = 0 + success = True + for col in xrange(0, image.size[0], factor): + if col == 0: + continue + success = True + for prior in xrange(last_col, col - 1): + if columns[prior] > columns[col - 1]: + success = False + break + last_col = col + if not success: + break + if success: + shred_width = factor + break +if shred_width == -1: + print >> stderr, "Error: Couldn't determine shred width." + exit(-2) + +columns = image.size[0] / shred_width +print "The image has %d columns." % columns + +def match_score(left, right): + total = 0 + for i in xrange(0, image.size[1]): + total += pixel_distance(pixel((left + 1) * shred_width - 1, i), pixel(right * shred_width, i)) + return total + +column_matches = {} +for i in xrange(0, columns): + min_score = image.size[1] * 442 # = sqrt(3) * 255 + min_index = -1 + for j in xrange(0, columns): + if j == i: + continue; + score = match_score(i, j) + if score < min_score: + min_score = score + min_index = j + column_matches[i] = (min_index, min_score) + +last = -1 +# If the graph has any nodes that point to prior ones, let's find the last one this way. +for key, value in column_matches.iteritems(): + for key2, value2 in column_matches.iteritems(): + if key == key2: + continue + if value[0] == value2[0]: + if value[1] > value2[1]: + last = key + else: + last = key2 + break +# Otherwise, if it amazingly wraps around, let's just remove the weakest link. +if last == -1: + min_score = image.size[1] * 442 # = sqrt(3) * 255 + for key, value in column_matches.iteritems(): + if value[1] < min_score: + min_score = value[1] + last = value[0] +del column_matches[last] + +column_matches_reverse = {} +for key, value in column_matches.iteritems(): + column_matches_reverse[value[0]] = (key, value[1]) + +column_order = [] +i = last +while True: + column_order.append(i) + if i not in column_matches_reverse: + break + i = column_matches_reverse[i][0] +column_order.reverse() + +unshredded = Image.new("RGBA", image.size) +for destination, source in enumerate(column_order): + unshredded.paste(image.crop((shred_width * source, 0, shred_width * source + shred_width, unshredded.size[1])), (destination * shred_width, 0)) +unshredded.save(argv[2]) -- cgit v1.2.3-59-g8ed1b