5 ms·
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
by 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 agothe 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 agoNo. 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 agoAnother 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 agoYet 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 agoThanks! my mental model was incorrect.
- robinhouston 10y agoInterestingly 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