3 ms·

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

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.)
  - inimino 10y ago
    I can see making a heuristic assessment that says "based on the blues and greens there is probably a large expanse of sky and some trees in the original image" but getting from there to where the trees are and putting the leaves back on the trees in the right places, I can't see that being even mathematically possible. It's a million-piece jigsaw puzzle where each piece is square and monochromatic. If enhancing a low-resolution image to regain lost information is basically impossible, getting back a picture from a color histogram would surely be much more impossible.

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.)
- inimino 10y ago
  I can see making a heuristic assessment that says "based on the blues and greens there is probably a large expanse of sky and some trees in the original image" but getting from there to where the trees are and putting the leaves back on the trees in the right places, I can't see that being even mathematically possible. It's a million-piece jigsaw puzzle where each piece is square and monochromatic. If enhancing a low-resolution image to regain lost information is basically impossible, getting back a picture from a color histogram would surely be much more impossible.