Image unshredder by simulated annealing (2015)
nayuki.io
nayuki.io
On a different note, if this quote:
> The unscrambling problem being solved here is much harder than a typical unscrambling problem, because we are rearranging single columns of pixels.
is referring to reconstructing shredded strips of paper then it is laughably false. The single columns of pixels are extremely clean and correspond very, very closely to their neighboring columns. In reality, the tearing of the paper makes the edges not match very well and it's just much noisier in general. I've worked on this problem before and it's many orders of magnitude more challenging than the reconstruction that is done in this demo.
You are also correct that I overstated how hard the problem is; in retrospect it isn't that hard at all to unshred clean digital images (as opposed to paper scans).
On your web page:
> It takes roughly the same amount of time to run but correctly reconstructs all of the images.
This is not true, but is very close to correct. The image "Blue Hour in Paris" has some disturbances in the lower part of the sky, "Alaska Railroad" has a single wrong column on one side of the image, and "Abstract Light Painting" sometimes has a few incorrect columns on the edge. At least that's what I could spot by eye at a glance; I didn't rigorously compare them against the original images.
You're right about them not matching exactly; I did it in a hurry and wasn't looking closely enough. I removed that incorrect statement (though it does seem to generally outperform the simulated annealing).
The tie breaking for pairs with equal differences and the parity of the image is essentially random. It is deterministic in the code, because it won't replace a candidate unless it's strictly better, but it's totally arbitrary which is found first.
I suppose it helps if you're already familiar with the problem domain. Nevertheless, it's very cool indeed.
Interestingly, it occasionally flips the picture horizontally (I only saw it with Blue Hour in Paris).
Maybe that's why you don't use Javascript Math.Random() for cryptographic purposes? :-)
Shuffle function:
function doShuffle() {
var startTime = Date.now();
var pixels = shuffledImage.data;
while (shuffleStartColumn < width) {
// Pick a random column j in the range [i, width) and move it to position i.
// This Fisher-Yates shuffle is the less efficient than the Durstenfeld shuffle but more animatedly appealing.
var i = shuffleStartColumn;
var j = i + Math.floor(Math.random() * (width - i));
for (var y = 0; y < height; y++) {
for (var x = j - 1; x >= i; x--) {
var off = (y * width + x) * 4;
for (var k = 0; k < 4; k++) {
var temp = pixels[off + k];
pixels[off + k] = pixels[off + 4 + k];
pixels[off + 4 + k] = temp;
}
}
}
shuffleStartColumn++;
if (Date.now() - startTime > YIELD_AFTER_TIME)
break;
}http://i.imgur.com/miCDFOD.png
As you can see, the left quarter of the image is reversed. I imagine the additional function you described would help with this.
You could pick a similarity metric such that adjacent columns have some bound on worst-case similarity - this allows you to reject many adjacencies. This could be chosen empirically by analyzing other known images. You could additionally model the probability distributions of similarity for adjacent columns, thus allowing you to reject further adjacencies and sets of adjacencies.
By using all this structure you should be able to do much better than this simulated annealing - which I have yet to see complete successfully on my machine, at any rate.
Is the author here? What energy metric is this using? Total variation?
The energy metric being used is simply the sum of absolute differences across all 3 channels for all horizontal adjacent pairs of pixels.
In pseudo-Python notation: sum(abs(pix[x,y,ch] - pix[x+1,y,ch]) for x in range(width-1) for y in range(height) for ch in range(3))
Also you could apply some nonlinear function to calculated TV to reflect your rejection penalties - i.e. if it's greater than x make the energy arbitrarily high. The thing is you would like to then reject the whole family of solutions that had that adjacency in your annealing, which doesn't seem super straightforward to me.
The other thing I see at the end is that it hits a local optima of multiple subsets of correct adjacencies (up to reflection) but there's no way to permute those subsets to get a better solution, as the temperature is too low. You'd almost want to "group" those subsets and then rerun on the 8 or so segments just over permutation and reflection. On the other hand, it does suggest that a "greedy" approach gets you pretty close - finding a locally optimal solution solves part of the global optimization. Then you can reduce the final problem to an exhaustive search of a much smaller space.
One quick test for this would be to make the strips 2 pixels wide.
It's interesting to watch the random walk that it does, and I think that problem would remain. Once it has made some wider strips that should be adjacent but aren't, the strips tend to randomly move between them, but there is no reason to prefer progress in one direction or the other.
I'd be interested to see what happens if you only allowed moves in one direction, e.g. only allowed a column to be inserted to tbe right of where it was.
I just tried using LKH[0] to reconstruct these scrambled images, and it does it perfectly in a fraction of a second.
Anyway, I only mentioned it to point out it wasn't a simple matter of calculating the similarities between columns and 'sorting' them, you need a more sophisticated algorithm.
Never mind what many others have said, that a greedy algorithm might work, that you can reduce it to TSP and apply heuristics, etc. The application of simulated annealing is also crippled: Suppose you reconstructed two slices of the image. To improve it, you have to take a column from one slice and move it to the other---but that doesn't lower the energy! What would lower the energy is to take one of the slices and attach it to the other, possibly flipping it in the process. So while it says "simulated annealing" on the lid, it's a random walk for the most part.
The idea is workable, but it needs a different primitive operation: pick a range of columns, attach it in a different spot, possibly flipping it.
Mutations could be flips and random swaps. Recombination would be combining chunks of already partially optimised solutions (breeding).
Genetic algorithms do suffer a cost of having to keep a population of solutions in memory so it would be interesting to see how the end results compares in performance to annealing.
A job for a meta-genetic algorithm maybe? Where the mutation operators are themselves evolved.
http://www.ipk.fraunhofer.de/fileadmin/user_upload/IPK_FHG/p...
Shredded secret service files, fragments of papyri or frescos...
The official excuse is that whatever the Stasi did was lawful at the time. The same logic would have made the Nuremberg Trials impossible, but it wasn't applied. That's not an accident.
Moreover, some of those documents may have been destroyed for very valid reasons.
The default temperature of 4000 is fine for all the example images at 600×400.
The default 30 million iterations leads to a reasonable run time of about 10 seconds, but leaves many small strips after annealing. Bumping up the number of iterations to 300 million, 3000 million, etc. will take proportionally longer time, and give marginally better results.
What I saw here was a scrambled image being sorted to find a local minima of entropy in pixel color value between respective stripes. A quantum annealing computer is doing is, where the image is the problem space (scrambled because we dont have the solution), and the quantum computer rearranges this to find global minima/maxima.
Where a QC is not useful would be when the problem space is too big (image too big), or it can only find a local minima that isn't the solution to the classical problem (picture is still objectively after annealing)
please comment someone if my understanding is wrong
> 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.