Hacker News Reader

Thanks for the helpful critique. Your proposed algorithm is reasonable and much, much faster than simulated annealing, and I appreciate the live demo. It looks like your algorithm is deterministic (except for tie-breaking of a pair of columns that have the same difference?), so it doesn't matter which way the image is shuffled.

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.

First off, thanks a lot for posting this and you did a great job with it! It was fun to play around with and it obviously inspired me enough to dig into the code and try my own variation.

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.

Wait, you threw that demo together in under 20 minutes? Wow.

>I've worked on this problem before

I suppose it helps if you're already familiar with the problem domain. Nevertheless, it's very cool indeed.

Very cool. Also remarkably fast response.

Interestingly, it occasionally flips the picture horizontally (I only saw it with Blue Hour in Paris).

There's really no way to preferentially differentiate between the image being flipped one way or the other once the one pixel wide columns have been shuffled. The order of the first pair that you put together determines which orientation you end up with and this is totally arbitrary. The reason that it flips sometimes is because the shuffling of the columns is random and the order of the initial pair of seed columns depends on their original order in the shuffled image.

Why on my machine does your unshredded version come out flipped? Pretty reliably, actually.

There's no way for the computer to know which way is correct and which way is a mirror image.

Yes, but it comes out flipped 100% of the time. I ran the train image 10 times and it was backwards (you can tell from the numbers) every single time. This is more than just chance.

Whether it is flipped or not seems to depend entirely on how it ended up being shuffled.

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;
    }

The algorithm isn't random -- every time you run your image through it, it's doing the same exact maths, and getting the same exact result. It's random whether or not any image you might pick will be flipped, but for a given image, the result will always be the same.