Reminds me nagravision decoders (if i recall correctly), one of the first pay tv protection algorithms
Image unshredding using a TSP solver
11–20 of 56 posts
Re: Image unshredding using a TSP solver
#12The 2D shuffling result is a bit surprising at first glance, but less so when you think about it - row comparison doesn't care about the order of the pixels in each row as long as the order is the same in both, and the shuffling mechanism guarantees that.
the important bit is you have to unscramble in reverse order of the scrambling. Unscrambling the columns and then unscrambling the rows would lead to smooth gibberish.
No. Column scrambling doesn't affect row ordering and row scrambling doesn't affect column ordering. They are literally orthogonal. You can't tell, from a scrambled matrix, whether the rows or the columns were scrambled first.
Here's a more explicit breakdown:
(0,0) (1,0) (2,0)
(0,1) (1,1) (2,1)
(0,2) (1,2) (2,2)
(0,0) (2,0) (1,0)
(0,1) (2,1) (1,1)
(0,2) (2,2) (1,2)
(0,1) (2,1) (1,1)
(0,0) (2,0) (1,0)
(0,2) (2,2) (1,2)
Let's try it in the other order, row first:
(0,1) (1,1) (2,1)
(0,0) (1,0) (2,0)
(0,2) (1,2) (2,2)
(0,1) (2,1) (1,1)
(0,0) (2,0) (1,0)
(0,2) (2,2) (1,2)
Re: Image unshredding using a TSP solver
#13The 2D shuffling result is a bit surprising at first glance, but less so when you think about it - row comparison doesn't care about the order of the pixels in each row as long as the order is the same in both, and the shuffling mechanism guarantees that.
the important bit is you have to unscramble in reverse order of the scrambling. Unscrambling the columns and then unscrambling the rows would lead to smooth gibberish.
Interestingly enough, that isn’t true. The operations of row-shuffling and column-shuffling commute, so you can do them in either order.
You can try it yourself, if you’ve cloned the repo. Here are the commands to reconstruct first by columns and then by rows:
git checkout double-shuffling
make images/double_shuffled/blue-hour-paris.png bin/compute_scores
mkdir tmp
bin/compute_scores --cols images/double_shuffled/blue-hour-paris.png > tmp/cols.tsp
bin/lkh.sh tmp/cols.tsp tmp/cols.tour
bin/reconstruct_image.py --cols tmp/cols.tour images/double_shuffled/blue-hour-paris.png > tmp/cols-unshuffled.png
bin/compute_scores --rows tmp/cols-unshuffled.png > tmp/rows.tsp
bin/lkh.sh tmp/rows.tsp tmp/rows.tour
bin/reconstruct_image.py --rows tmp/rows.tour tmp/cols-unshuffled.png > tmp/reverse-unshuffled.pngRe: Image unshredding using a TSP solver
#14I'm really surprised by double-shuffling can actually be solved. https://github.com/robinhouston/image-unshredding/#double-sh... It looks very unintuitive.
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.
Re: Image unshredding using a TSP solver
#15I'm really surprised by double-shuffling can actually be solved. https://github.com/robinhouston/image-unshredding/#double-sh... It looks very unintuitive.
Isn't the definition of insanity something about doing the same thing and expecting different results.
Re: Image unshredding using a TSP solver
#16Re: Image unshredding using a TSP solver
#17Now 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.
Seems like with a high resolution enough image, some of these effects may actually make the problem easier.
Re: Image unshredding using a TSP solver
#18Earlier quoted context omitted.
the important bit is you have to unscramble in reverse order of the scrambling. Unscrambling the columns and then unscrambling the rows would lead to smooth gibberish.
No. Column scrambling doesn't affect row ordering and row scrambling doesn't affect column ordering. They are literally orthogonal. You can't tell, from a scrambled matrix, whether the rows or the columns were scrambled first. Here's a more explicit breakdown: (0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) Column scrambling: swap 1&2: (0,0) (2,0) (1,0) (0,1) (2,1) (1,1) (0,2) (2,2) (1,2) Now row scrambling: sw…
Another way to think of it is that permuting rows corresponds to multiplying a matrix on the left by a permutation matrix, and permuting columns, on the right. Since matrix multiplication is associative, they commute!
Re: Image unshredding using a TSP solver
#19Could 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.
Re: Image unshredding using a TSP solver
#20I'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.