summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJason A. Donenfeld <Jason@zx2c4.com>2011-11-13 19:47:28 -0500
committerJason A. Donenfeld <Jason@zx2c4.com>2011-11-13 19:47:28 -0500
commit7ab4a4d6f5575f114d16dc06cfa152b3b3a51db0 (patch)
treed67965427270fb71962b6f57a3a90f90e32cbcc1
downloadinstagram-unshredder-7ab4a4d6f5575f114d16dc06cfa152b3b3a51db0.tar.xz
instagram-unshredder-7ab4a4d6f5575f114d16dc06cfa152b3b3a51db0.zip
Initial commit.
-rw-r--r--TokyoPanoramaShredded.pngbin0 -> 617432 bytes
-rw-r--r--bird-shred.pngbin0 -> 511265 bytes
-rw-r--r--reshredded.pngbin0 -> 617339 bytes
-rwxr-xr-xshred.py29
-rwxr-xr-xunshred-binary-merge-failure.py81
-rwxr-xr-xunshred.py116
6 files changed, 226 insertions, 0 deletions
diff --git a/TokyoPanoramaShredded.png b/TokyoPanoramaShredded.png
new file mode 100644
index 0000000..be74187
--- /dev/null
+++ b/TokyoPanoramaShredded.png
Binary files differ
diff --git a/bird-shred.png b/bird-shred.png
new file mode 100644
index 0000000..ab41cb8
--- /dev/null
+++ b/bird-shred.png
Binary files differ
diff --git a/reshredded.png b/reshredded.png
new file mode 100644
index 0000000..ec1e05f
--- /dev/null
+++ b/reshredded.png
Binary files 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 <Jason@zx2c4.com>
+# 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 <Jason@zx2c4.com>
+# 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 <Jason@zx2c4.com>
+# 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])