51–56 of 56 posts
Now I'd like to see this run on a more realisticly shredded image. A real paper shredder creates strips that are more than one pixel thick are not straight on (I.e. the pixels don't necessarily align with the cuts) and possibly have cutting defects such as ragged edges or nicks.
I'm really surprised by double-shuffling can actually be solved. https://github.com/robinhouston/image-unshredding/#double-sh... It looks very unintuitive.
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.
Could be used to compress images? Perhaps instead of shuffling the columns and rows randomly they could be ordered in ways that are better suited for compression.
That's what the Burrows–Wheeler transform does for text. A similar approach could work for images.
Earlier quoted context omitted.
I always thought "NP-complete/NP-hard" metaphor only meaningful in theoretical work. In practice, it does not make much sense in guiding what/how the real world problem is to be solved.
I don't know. I find it useful in practice. Apart from anything else it means there's (probably) no point looking for an exact polynomial-time algorithm, which can save a lot of wasted effort. But it also gives useful clues about what sort of algorithmic approaches might be useful, and allows you to relate your problem to a huge amount of existing research. It's really basic taxonomy: what sort of problem are we deal…
Do you know of any image compression technique that would drop information that we expect to be redeemable in a reasonable time using a solver of this sort?
Since the shuffling adds information, it seems unlikely.
Earlier quoted context omitted.
Since the shuffling adds information, it seems unlikely.
Don't you think that for any image there exist a shuffled version that compress better?
In cases where there is a version that compresses better, unshuffling might not work. If you had an "pinstripe" image consisting of alternating black and white columns of pixels, obviously it could compress better after being "shuffled" with all the similarly colored columns together. But then this algorithm would be unable to get the original image back.