Recently Instagram openned a little challenge, the goal of which was to reassemble an image that had been “shredded”.
All the details of the challenge can be found here : Instagram Engineering Challenge: The Unshredder.
The basic idea is to take an image that has been shredded, i.e. where the image has been cut up into vertical stripes of equal width and rearranged in random order. (The image above was the one proposed by Instagram as an example).
I first tried a Python version, which was the first time I played with Python. I also thought it could be a good way to play around with the canvas element.
What I have come up with for the canvas version is here (you can have a look at the JS source, uses a few Mootools shortcuts).
In a few words, the idea is to take advantage of the symmetry of the shreds. That is, determine the vertical lines where the colors in the picture, on average, change “unnaturally” quickly. This is done by looking at the cartesian distance on the RGB color space between two adjacent pixels of a same row and summing over the columns. This gives us a one dimensional array which can in turn be processed to augment unnatural peaks. By looking at the distances between the biggest peaks it is possible to determine the width of the shreds.
Once this is done, we need to reorder the shreds, again, using the cartesian distance. Two shreds are set to be congruant when the distance is minimized between adjacent borders.
Remember, the code is deliberately kept really small. Also all images cannot be completely recovered this way, at least not the way I decide adjacency and where to start. I may try to think up better ways to do this.
I like these little challenges, especially since I have very little experience playing around with images.
(Also, on a side note, I wanted to share my absolute favorite version of the solutions I’ve seen out there : Solving Instagram’s Unshredder with Mechanical Turk and $0.50).