Hacker News new | comments | show | ask | jobs | submit login

This is a fun demo but, as others have mentioned, simulated annealing really isn't necessary, or even that appropriate, for this specific problem. I threw together the same demo with a very trivial algorithm that I think does a more accurate job of reconstructing the same images in significantly less time than the simulated annealing [1]. The algorithm consists of first finding the closest matching pair of pixels as a seed. It then finds the remaining column that most closely matches one of the current edges and adds it to the reconstructed columns. This then repeats until there are no remaining columns.

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.

[1] http://sangaline.com/blog/image_unshredder/




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.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: