Image unshredding using a TSP solver
github.com
Image unshredding using a TSP solver
1–10 of 56 posts
Re: Image unshredding using a TSP solver
#2Roughly how long does this algorithm take to run?
Re: Image unshredding using a TSP solver
#3Shuffling lines was the scrambling algorithm used in nagravision a while back... https://www.youtube.com/watch?v=gFAinn6sddQ there was a software that could descramble the video using a similar technique
Re: Image unshredding using a TSP solver
#4The 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.
Re: Image unshredding using a TSP solver
#5Could 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.
Re: Image unshredding using a TSP solver
#6The 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.
Re: Image unshredding using a TSP solver
#7Could 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.
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.
Re: Image unshredding using a TSP solver
#8I'm really surprised by double-shuffling can actually be solved. https://github.com/robinhouston/image-unshredding/#double-sh... It looks very unintuitive.
Re: Image unshredding using a TSP solver
#9Now 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.
Re: Image unshredding using a TSP solver
#10Roughly how long does this algorithm take to run?
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)