4 ms·

I'm really surprised by double-shuffling can actually be solved. https://github.com/robinhouston/image-unshredding/#double-shuffling https://github.com/robinhou

• svantana 10y ago
  if you think about it, the row-comparing algo basically boils down to a sum of differences. As summation is independent of the order of its terms, it can be done in arbitrary order, and thus the (orthogonal) shuffling makes no difference.
• jcoffland 10y ago
  Isn't the definition of insanity something about doing the same thing and expecting different results.
  • solipsism 10y ago
    No.
  • jcoffland 10y ago
    Funny, I thought more people would have gotten what I was saying here.
    • touch_o_goof 10y ago
      You're forgetting HN is serious discussion for serious people or something like that. Humour in a substantive post seems fine, but usually any humour on its own doesn't fare well here.
• petters 10y ago
  Think about it like this: for a 100x100 image, there are 100!*100! ways to double-shuffle. But there are 10000! ways to shuffle the pixel. So a lot of structure remains in the double-shuffled image.
  • OskarS 10y ago
    In case your point is not obvious to someone, 10000! is FAR larger than 100!*100! (by something like 350,000 orders of magnitude), so the possibility space is vastly bigger if you shuffle the pixels individually than if you shuffle columns first, then rows.
• Xcelerate 10y ago
  I wouldn't be surprised if a complete shuffling could be solved — i.e., every pixel is given a new random location. (Source: I do research involving stuff like this.)
  • inimino 10y ago
    How could that be possible? Wouldn't that literally throw away everything but the distribution of colors in the image?
    • LolWolf 10y ago
      Pretty much, but if you have some good knowledge of what the distributions of neighboring pixels must look like (e.g. the l1 norm error used here wouldn't be enough, I believe) then I think you'd be surprised at the outcome.
    • Houshalter 10y ago
      You could constrain it so the pixels are only shuffled within a set distance of their origin. Still sounds very hard to solve, but would leave a lot more information.
    • Xcelerate 10y ago
      An error function against neighboring pixels alone probably would not be enough to reconstruct the image (there are information theoretic limitations on how much noise can exist for a certain model before ground truth recovery becomes impossible); however, depending on the type of image, additional information could be gleaned from images that fall into the same category. For instance, if I assign each pixel a random color and call that my "image", and then scramble all of the pixels, it is easy to see that recovery of the original image is mathematically impossible. However, if I use a photograph of a person standing in front of a car, information gleaned from similar types of photos could be sufficient to allow complete recovery given only the exact distribution of pixel colors. I don't know whether this is true, but I wouldn't be surprised if it is. (Actually, this seems like a fun hobby project. I may give it a shot.)