Image unshredder by annealing

Live demo (JavaScript)

Description

On another page, I unleash the simulated annealing algorithm on a toy problem. It generates an image full of random colorful pixels, and rearranges the pixels so that similar colors are near each other.

Here I try to solve a more realistic problem. Suppose we took an ordinary image and scrambled it by rearranging the columns of pixels. This would be like shredding the image into vertical strips and shuffling them. Can we use simulated annealing to unscramble the image automatically without relying on human intelligence? The answer, pleasantly enough, is yes.

To operate this JavaScript demo, first choose an image or proceed with the default one. Next press the “Shuffle” button. Then check the settings for simulated annealing (the defaults are a good starting point), and press the “Anneal” button. Note that after shuffling, you anneal any number of times, and the annealing will start from the shuffled state (not from the most recently annealed state).

Source code

Download:

• Java: ShuffleImageColumns.java, AnnealImageColumns.java
• TypeScript: image-unshredder.ts / image-unshredder.js

The JavaScript version of the program is what powers this web page. The Java version of the annealer is much faster than the JavaScript version (about 4× faster on my machine), the code is cleaner, and it is suitable for headless and batch processing.

Notes

• The choice of starting temperature depends on the image height and image content. Taller images would require a higher temperature because they tend to have more energy (differences) in total. Images that are noisy will need a higher temperature, whereas smooth images need a lower temperature. So experiment with different values and see what produces the best results for your situation.

• Empirically speaking, it seems that for images about 600 pixels wide, it takes approximately 1 billion iterations to completely or nearly unscramble the whole image. With fewer iterations (like 100 million, 10 million, etc.), the final result will have more pieces.

  If the image isn’t fully unscrambled, it’s usually possible to open the image in an editor, manually pick up the large pieces, move them around, and horizontally flip some of them, in order to yield a complete image. One area for improvement is that the program can be made to automatically identify these good pieces and start annealing the pieces instead of annealing individual columns.

• The unscrambling problem being solved here is much harder than a typical unscrambling problem, because we are rearranging single columns of pixels. As a consequence of this design, it is impossible to resolve the horizontal reflection symmetry ambiguity – every image has exactly the same energy score as its mirror image.

  In a more typical problem, the image would be sliced into groups of columns, where each group moves as a unit. This situation would reduce the number of pieces to unscramble, and also make the arrangement be unambiguous to horizontal flips.

• In each iteration of this simulated annealing algorithm, the image is perturbed by removing one random column and inserting it back into a random position. It is not perturbed by swapping two random columns – I believe this would produce inferior results and slower convergence, because it would be very hard to shift a bunch of columns to insert one column in the correct place.

• In this demo, simulated annealing proves to be an effective strategy to manage a large search space. For example, an image 600 pixels wide can have its columns arranged in 600! ≅ 10¹⁴⁰⁸ ways. But we can run this program to effectively unscramble an image in roughly 10¹⁰ iterations, give or take a few orders of magnitude.