7 ms·

Image unshredding using a TSP solver

205 points by robinhouston 10y ago

barrkel 10y ago
The 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.
- dastbe 10y ago
  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.
  - barrkel 10y ago
    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: swap 0&1: (0,1) (2,1) (1,1) (0,0) (2,0) (1,0) (0,2) (2,2) (1,2) Notice how the x coordinates still all match along the vertical, and y coordinates still all match along the horizontal. 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) And columns: (0,1) (2,1) (1,1) (0,0) (2,0) (1,0) (0,2) (2,2) (1,2) It's the same result irrespective of the order.
    - kmill 10y ago
      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!
      - evincarofautumn 10y ago
        Yet another way to think of it is that a matrix is an encoding of a linear (or affine) function, matrix multiplication is composition of such functions, and since composition is associative, they commute. :)
    - dastbe 10y ago
      Thanks! my mental model was incorrect.
  - robinhouston 10y ago
    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.png
Retr0spectrum 10y ago
Roughly how long does this algorithm take to run?
- robinhouston 10y ago
  On my laptop (real times for a single run): 1.6 seconds to make the TSPLIB2 file representing the dissimilarity graph. (time make tsp/instances/blue-hour-paris.tsp) 0.3 seconds to run the solver and produce the optimal tour. (time make tsp/tours/blue-hour-paris.tour) 0.4 seconds to reconstruct the image from the shuffled version using the tour. (time make images/reconstructed/blue-hour-paris.png)
xchip 10y ago
Shuffling lines was the scrambling algorithm used in nagravision a while back... https://www.youtube.com/watch?v=gFAinn6sddQ https://www.youtube.com/watch?v=gFAinn6sddQ there was a software that could descramble the video using a similar technique
syphilis2 10y ago
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.
- wlievens 10y ago
  IIRC the HDF5 data storage format compresses per-bit (e.g. all LSB's together) instead of per pixel when compressing image data, and tests on our data sets have shown tvis significantly improves compared to ZIP compression for instance.
- gpderetta 10y ago
  That's what the Burrows–Wheeler transform does for text. A similar approach could work for images.
  - OskarS 10y ago
    It's a good point. PNG uses DEFLATE internally for the compression, it would be interesting to see what would happen if you used bzip2 instead, which uses the Burrows-Wheeler transform.
- szemet 10y ago
  To me the whole experiment suggests otherwise: it shows that naturally occurring images are organized by having similar rows and columns close to each other, which is - by default - good for most compression algorithms that prefer regularities/similarities to be as local as possible. edit: but it can be good for other cases, where there are no good-enough default orders. For example "customer - product bought" matrix (binary matrix, customer rows, product columns: X customer bought Y product = 1, otherwise =0 ). Here the order of rows/columns are not predefined, and ordering by similar customers and products the compression of the matrix could be improved. Finding these similarities also can be a good starting point for some recommendation/collaborative filtering engine.
alpb 10y ago
I'm really surprised by double-shuffling can actually be solved. https://github.com/robinhouston/image-unshredding/#double-shuffling https://github.com/robinhouston/image-unshredding/#double-sh... It looks very unintuitive.
- 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.
jcoffland 10y ago
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.
- foota 10y ago
  Seems like with a high resolution enough image, some of these effects may actually make the problem easier.
  - jcoffland 10y ago
    Perhaps, but you would have to look at more than just neighboring pixel color to take advantage.
- deleted 10y ago
  [deleted]
- wtbob 10y ago
  The big difference is that this actually preserves a lot of structure, due to being oriented to columns (and/or rows): a real shredder produces chads without any of that, and would presumably be a much harder problem to solve.
- gergoerdi 10y ago
  Sounds like the DARPA Shredder Challenge from 2011: https://en.wikipedia.org/wiki/DARPA_Shredder_Challenge_2011 https://en.wikipedia.org/wiki/DARPA_Shredder_Challenge_2011
bluesign 10y ago
Reminds me nagravision decoders (if i recall correctly), one of the first pay tv protection algorithms Edit: https://en.m.wikipedia.org/wiki/Nagravision https://en.m.wikipedia.org/wiki/Nagravision
preygel 10y ago
A bit tangentially, this is also a great display of just how good readily available approximate solvers have gotten for a wide range of combinatorial optimization problems (like TSP). The LKH solver used here has rather impressive performance. From http://webhotel4.ruc.dk/~keld/research/LKH/ http://webhotel4.ruc.dk/~keld/research/LKH/: "LKH has produced optimal solutions for all solved problems we have been able to obtain," and the studies linked there show that it really does find optimal solutions "with an impressively high frequency." While the point here is to use an off-the-shelf solver, it can be nice to have visibility into what's actually happening: - This is a reasonable example for explaining some of the local search TSP heuristics. For instance a "2-opt" move corresponds to picking a contiguous range of columns and flipping them. - The previous HN post used simulated annealing, which would not be an outright terrible approach to TSP itself -- were it not for the better Lin-Kernighan-based approaches (like LKH). - If we want, we can tell LKH to start from Sangaline's "nearest-neighbor" approach ("INITIAL_TOUR_ALGORITHM = NEAREST-NEIGHBOR"). This does not make a difference here though.
- robinhouston 10y ago
  Not so long ago, we’d say “That’s an NP-complete problem” with the implication that it was hopeless to expect an efficient solution. Now (to exaggerate a little) it’s more like a sign that there probably is an efficient solution using some powerful solver. LKH is a lovely piece of work. I used it a couple of years ago to find a counterexample to an unimportant but fairly long-standing conjecture in combinatorics[0], and the list of scientific applications[1] is impressively diverse. The best SMT solvers are also hugely impressive. Z3 has an excellent interactive tutorial and online solver.[2] [0] https://arxiv.org/abs/1408.5108 https://arxiv.org/abs/1408.5108 [1] http://webhotel4.ruc.dk/~keld/research/LKH/ScientificApplications.html http://webhotel4.ruc.dk/~keld/research/LKH/ScientificApplica... [2] http://rise4fun.com/z3/tutorial http://rise4fun.com/z3/tutorial
  - preygel 10y ago
    Absolutely! Not to mention the often impressive performance of "general" MIP solvers. It is only a shame that the best ones there are commercial (Gurobi followed by Cplex). That said, Cbc is lovely in a wide range of cases, and is open-source.
emmelaich 10y ago
I guess this could be used to reassemble images corrupted in other ways (other than shuffling). I have a disk image of jpegs and other data I'd like recovered. It was Windows formatted a few different ways but any blocks that format didn't touch are still there. There's other data there of course as well, so there would be lot of blocks that aren't part of images so would need to be ignored when reassembling the images.
- taeric 10y ago
  I'd guess not, actually. In this a lot of the information is there. Just in a different order. Corrupting data is a different problem. That said, I'm sure I could be surprised by what is possible.
aratno 10y ago
I wonder how well this would work with some image pre-processing. Wouldn't something like supersampling improve the speed per-pixel? Of course, it would require more pixels to be sorted, so I doubt it's any more optimal.
LolWolf 10y ago
This is super interesting; how does it compare to other sampling algorithms? While the problem is indeed reducible; it also has a lot more structure than TSP, especially if we note that natural images are forced to come from some nice, underlying manifold which is probably very well-behaved. I'd be inclined to believe that with some assumptions on the problem itself (e.g. the images satisfy some smoothness assumptions and of course, assumptions on the objective, itself), we can always come up with a PTAS for this particular instance for any accuracy, ε>0.
microcolonel 10y ago
Looks like it's time to go back to burning.
rixed 10y ago
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?
- inimino 10y ago
  Since the shuffling adds information, it seems unlikely.
  - rixed 10y ago
    Don't you think that for any image there exist a shuffled version that compress better?
    - inimino 10y ago
      I don't see any reason why there necessarily would be. Generally speaking, compression algorithms do better when adjacent pixels have similar colors, which is the unshuffled state. 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.
askee 10y ago
How good does it work with non-natural images where rows/columns are not similar to each other? White noise for example should prove rather difficult.
botw 10y ago
I guess the difference with the simulated annealing approach would be that this approach(and the simple picking-the-most-similar-column approach) assumes you know the particular shredding method in advance, whereas the simulated annealing does not have this requirement. For example, does this still work out for shredding diagonally in some unknown degree?

205 points by robinhouston 10y ago

The 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.

dastbe 10y ago
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.
- barrkel 10y ago
  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: swap 0&1: (0,1) (2,1) (1,1) (0,0) (2,0) (1,0) (0,2) (2,2) (1,2) Notice how the x coordinates still all match along the vertical, and y coordinates still all match along the horizontal. 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) And columns: (0,1) (2,1) (1,1) (0,0) (2,0) (1,0) (0,2) (2,2) (1,2) It's the same result irrespective of the order.
  - kmill 10y ago
    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!
    - evincarofautumn 10y ago
      Yet another way to think of it is that a matrix is an encoding of a linear (or affine) function, matrix multiplication is composition of such functions, and since composition is associative, they commute. :)
  - dastbe 10y ago
    Thanks! my mental model was incorrect.
- robinhouston 10y ago
  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.png

Retr0spectrum 10y ago

Roughly how long does this algorithm take to run?

robinhouston 10y ago
On my laptop (real times for a single run): 1.6 seconds to make the TSPLIB2 file representing the dissimilarity graph. (time make tsp/instances/blue-hour-paris.tsp) 0.3 seconds to run the solver and produce the optimal tour. (time make tsp/tours/blue-hour-paris.tour) 0.4 seconds to reconstruct the image from the shuffled version using the tour. (time make images/reconstructed/blue-hour-paris.png)

xchip 10y ago

Shuffling lines was the scrambling algorithm used in nagravision a while back... https://www.youtube.com/watch?v=gFAinn6sddQ https://www.youtube.com/watch?v=gFAinn6sddQ there was a software that could descramble the video using a similar technique

syphilis2 10y ago

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.

wlievens 10y ago
IIRC the HDF5 data storage format compresses per-bit (e.g. all LSB's together) instead of per pixel when compressing image data, and tests on our data sets have shown tvis significantly improves compared to ZIP compression for instance.
gpderetta 10y ago
That's what the Burrows–Wheeler transform does for text. A similar approach could work for images.
- OskarS 10y ago
  It's a good point. PNG uses DEFLATE internally for the compression, it would be interesting to see what would happen if you used bzip2 instead, which uses the Burrows-Wheeler transform.
szemet 10y ago
To me the whole experiment suggests otherwise: it shows that naturally occurring images are organized by having similar rows and columns close to each other, which is - by default - good for most compression algorithms that prefer regularities/similarities to be as local as possible. edit: but it can be good for other cases, where there are no good-enough default orders. For example "customer - product bought" matrix (binary matrix, customer rows, product columns: X customer bought Y product = 1, otherwise =0 ). Here the order of rows/columns are not predefined, and ordering by similar customers and products the compression of the matrix could be improved. Finding these similarities also can be a good starting point for some recommendation/collaborative filtering engine.

alpb 10y ago

I'm really surprised by double-shuffling can actually be solved. https://github.com/robinhouston/image-unshredding/#double-shuffling https://github.com/robinhouston/image-unshredding/#double-sh... It looks very unintuitive.

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.

jcoffland 10y ago

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.

foota 10y ago
Seems like with a high resolution enough image, some of these effects may actually make the problem easier.
- jcoffland 10y ago
  Perhaps, but you would have to look at more than just neighboring pixel color to take advantage.
deleted 10y ago
[deleted]
wtbob 10y ago
The big difference is that this actually preserves a lot of structure, due to being oriented to columns (and/or rows): a real shredder produces chads without any of that, and would presumably be a much harder problem to solve.
gergoerdi 10y ago
Sounds like the DARPA Shredder Challenge from 2011: https://en.wikipedia.org/wiki/DARPA_Shredder_Challenge_2011 https://en.wikipedia.org/wiki/DARPA_Shredder_Challenge_2011

bluesign 10y ago

Reminds me nagravision decoders (if i recall correctly), one of the first pay tv protection algorithms Edit: https://en.m.wikipedia.org/wiki/Nagravision https://en.m.wikipedia.org/wiki/Nagravision

preygel 10y ago

A bit tangentially, this is also a great display of just how good readily available approximate solvers have gotten for a wide range of combinatorial optimization problems (like TSP). The LKH solver used here has rather impressive performance. From http://webhotel4.ruc.dk/~keld/research/LKH/ http://webhotel4.ruc.dk/~keld/research/LKH/: "LKH has produced optimal solutions for all solved problems we have been able to obtain," and the studies linked there show that it really does find optimal solutions "with an impressively high frequency." While the point here is to use an off-the-shelf solver, it can be nice to have visibility into what's actually happening: - This is a reasonable example for explaining some of the local search TSP heuristics. For instance a "2-opt" move corresponds to picking a contiguous range of columns and flipping them. - The previous HN post used simulated annealing, which would not be an outright terrible approach to TSP itself -- were it not for the better Lin-Kernighan-based approaches (like LKH). - If we want, we can tell LKH to start from Sangaline's "nearest-neighbor" approach ("INITIAL_TOUR_ALGORITHM = NEAREST-NEIGHBOR"). This does not make a difference here though.

robinhouston 10y ago
Not so long ago, we’d say “That’s an NP-complete problem” with the implication that it was hopeless to expect an efficient solution. Now (to exaggerate a little) it’s more like a sign that there probably is an efficient solution using some powerful solver. LKH is a lovely piece of work. I used it a couple of years ago to find a counterexample to an unimportant but fairly long-standing conjecture in combinatorics[0], and the list of scientific applications[1] is impressively diverse. The best SMT solvers are also hugely impressive. Z3 has an excellent interactive tutorial and online solver.[2] [0] https://arxiv.org/abs/1408.5108 https://arxiv.org/abs/1408.5108 [1] http://webhotel4.ruc.dk/~keld/research/LKH/ScientificApplications.html http://webhotel4.ruc.dk/~keld/research/LKH/ScientificApplica... [2] http://rise4fun.com/z3/tutorial http://rise4fun.com/z3/tutorial
- preygel 10y ago
  Absolutely! Not to mention the often impressive performance of "general" MIP solvers. It is only a shame that the best ones there are commercial (Gurobi followed by Cplex). That said, Cbc is lovely in a wide range of cases, and is open-source.

emmelaich 10y ago

I guess this could be used to reassemble images corrupted in other ways (other than shuffling). I have a disk image of jpegs and other data I'd like recovered. It was Windows formatted a few different ways but any blocks that format didn't touch are still there. There's other data there of course as well, so there would be lot of blocks that aren't part of images so would need to be ignored when reassembling the images.

taeric 10y ago
I'd guess not, actually. In this a lot of the information is there. Just in a different order. Corrupting data is a different problem. That said, I'm sure I could be surprised by what is possible.

aratno 10y ago

I wonder how well this would work with some image pre-processing. Wouldn't something like supersampling improve the speed per-pixel? Of course, it would require more pixels to be sorted, so I doubt it's any more optimal.

LolWolf 10y ago

This is super interesting; how does it compare to other sampling algorithms? While the problem is indeed reducible; it also has a lot more structure than TSP, especially if we note that natural images are forced to come from some nice, underlying manifold which is probably very well-behaved. I'd be inclined to believe that with some assumptions on the problem itself (e.g. the images satisfy some smoothness assumptions and of course, assumptions on the objective, itself), we can always come up with a PTAS for this particular instance for any accuracy, ε>0.

microcolonel 10y ago

Looks like it's time to go back to burning.

rixed 10y ago

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?

inimino 10y ago
Since the shuffling adds information, it seems unlikely.
- rixed 10y ago
  Don't you think that for any image there exist a shuffled version that compress better?
  - inimino 10y ago
    I don't see any reason why there necessarily would be. Generally speaking, compression algorithms do better when adjacent pixels have similar colors, which is the unshuffled state. 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.

askee 10y ago

How good does it work with non-natural images where rows/columns are not similar to each other? White noise for example should prove rather difficult.

botw 10y ago

I guess the difference with the simulated annealing approach would be that this approach(and the simple picking-the-most-similar-column approach) assumes you know the particular shredding method in advance, whereas the simulated annealing does not have this requirement. For example, does this still work out for shredding diagonally in some unknown degree?