Instagram recently released a challenge to create an algorithm that reconstructs a “shredded” photograph into its original form. You can read more about the challenge on their blog. You can also jump to my solution or read on for how I decided to solve the problem.
Meanwhile, here’s an example image they provided.
There was also a “bonus” component… auto-detect the width of the strips.
I chose to use Processing because I could visually work out my approach which was…generally… find the left-most strip… then recursively work out which strips best matched the right edge of that strip using the average RGB value of their left edge.
Here it is in detail.
Bonus – find the strip interval:
1. Iterate over every column of pixels, create an Object representing the column, determine an average RGB value for the column and assign it as a property.
2. Compare each column’s RGB value to the column to its left and save the difference as a property.
3. Sort the columns by the difference.
4. Do some crazy shit to find a list of the lowest common multipliers between the position of the last two columns. The lowest value that represents a strip edge is the strip width.
Now that we have the strip width:
1. Iterate over the strips and create Objects representing the strips in an ArrayList.
2. Iterate over the strips’ left and right edges and assign the average RGB value as properties.
3. Find the left-most strip by finding the left edge with the largest difference in average RGB value from all the right edges.
4. Start placing strips by finding the left edges that most closely match the average RGB value of the right edge of the last strip placed… gasp…
Anyway, check out my solution. Processing turned out to be a good choice for prototyping the solution… and once I had it, why not publish as a java applet?
While we’re talking about Instagram, check out my cat.
