A Greedy Image Unshredder

, CC license


A blogpost by Nayuki about unshredding images using simulated annealing was just posted on Hacker News. This is just a simple demo to support my comment on the article and illustrate that a much simpler greedy algorithm is both faster and more effective for this specific problem. The algorithm consists of simply to find the closest matching pair of columns and then build up the image column by column from that by adding the best matching column out of all those remaining. It takes less time to run and more accurately reconstructs the images (though there are a couple of remaining seams). Both algorithms currently use the sum of the absolute values of the differences between RGB value in the adjacent pixels. The performance could be improved by finding a better comparison function for the columns of pixels.

Evan Sangaline
Evan Sangaline
Vice President of Artificial Intelligence

My interests include web development, machine learning, and technical writing