https://github.com/robinhouston/image-unshredding Skip to content Sign up * Why GitHub? Features - + Mobile - + Actions - + Codespaces - + Packages - + Security - + Code review - + Issues - + Integrations - + GitHub Sponsors - + Customer stories- * Team * Enterprise * Explore + Explore GitHub - Learn and contribute + Topics - + Collections - + Trending - + Learning Lab - + Open source guides - Connect with others + The ReadME Project - + Events - + Community forum - + GitHub Education - + GitHub Stars program - * Marketplace * Pricing Plans - + Compare plans - + Contact Sales - + Education - [ ] [search-key] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this user All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up {{ message }} robinhouston / image-unshredding * Notifications * Star 467 * Fork 24 467 stars 24 forks Star Notifications * Code * Issues 0 * Pull requests 0 * Actions * Projects 0 * Wiki * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Wiki * Security * Insights master Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags 3 branches 0 tags Code Clone HTTPS GitHub CLI [https://github.com/r] Use Git or checkout with SVN using the web URL. [gh repo clone robinh] Work fast with our official CLI. Learn more. * Open with GitHub Desktop * Download ZIP Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Go back Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Go back Launching Xcode If nothing happens, download Xcode and try again. Go back Launching Visual Studio Code Your codespace will open once ready. There was a problem preparing your codespace, please try again. Latest commit @robinhouston robinhouston The word "perfectly" was used too many times ... 7fd60cd Oct 10, 2016 The word "perfectly" was used too many times 7fd60cd Git stats * 10 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time bin First commit Oct 9, 2016 images First commit Oct 9, 2016 nayuki First commit Oct 9, 2016 src First commit Oct 9, 2016 tsp First commit Oct 9, 2016 .gitignore First commit Oct 9, 2016 Makefile First commit Oct 9, 2016 README.md The word "perfectly" was used too many times Oct 10, 2016 View code Image unshredding using a TSP solver Introduction Image unshredding is an instance of the Travelling Salesman Problem This project The dissimilarity measure matters Running the code Prerequisites Double-shuffling README.md Image unshredding using a TSP solver Introduction Yesterday I saw a fun demo by Nayuki using simulated annealing to reconstruct photographs whose columns have been shuffled. For example, the photograph Blue Hour in Paris (CC licensed by Falcon(r) Photography): Blue hour in Paris is shuffled to produce: Blue hour in Paris, shuffled and the simulated annealing algorithm (starting temperature 4000, 1 billion iterations) reconstructs this: Blue hour in Paris, reconstructed using simulated annealing Subsequently Sangaline showed that the images can be reconstructed faster and more effectively using a simple greedy algorithm to pick the most-similar column at each step. The greedy algorithm produces this: Blue hour in Paris, reconstructed using a greedy algorithm which is quite close to the original, though you can see some misplaced columns in the sky at the right. Image unshredding is an instance of the Travelling Salesman Problem Our task is to piece the columns of pixels together so that, over all, adjacent columns are as similar as possible. Think of the columns as being nodes in a weighted graph, with the edge-weight between two columns being a dissimilarity measure. Then we are looking for a Hamiltonian path of minimum weight in the graph. So it is an instance of the Travelling Salesman Problem. (A small technical note: since we want a Hamiltonian path rather than a Hamiltonian cycle, we add a dummy node to the graph that has weight-0 edges to all the other nodes. If we can find a least-weight Hamiltonian cycle on this augmented graph, we remove the dummy node to obtain a least-weight Hamiltonian path on the original graph.) This project This project uses a fast approximate solver for the Travelling Salesman Problem to reconstruct the images quickly and perfectly. Blue hour in Paris, reconstructed using LKH You will notice that the image is flipped, but otherwise reconstructed perfectly. It is impossible in general to distinguish an image from its flipped version when the columns have been shuffled, and all the algorithms mentioned here produce flipped reconstructions half the time. Apart from that, I believe this algorithm can correctly reconstruct all the images in Nayuki's demo. The dissimilarity measure matters One interesting thing I found is that the result is sensitive to the dissimilarity measure used. I have used the same measure as the other projects mentioned here: the sum of the absolute values of the differences in the R/G/B channels, summed over all pixels in the column. If instead we use the square rather than the absolute value, the image is reconstructed incorrectly as follows: Blue hour in Paris, reconstructed using LKH This is not a failure of the TSP algorithm: in fact this mangled image has a better score than the original, using the sum-of-squares measure! Running the code * Clone the repository * Run make to download and shuffle the images, and download and compile LKH. * Now you can run make reconstruct to reconstruct the images from their shuffled versions using LKH. You can also run make nayuki to reconstruct the images using Nayuki's simulated annealing code. Prerequisites You will need a working build environment (Make and a C compiler), and curl is used to download files from the web. You also need libpng >= 1.6 (which the Makefile assumes to be in /usr/local, but that is easy to change). The simpler bits of image manipulation are done using Python 2 and require the Python Imaging Library or a compatible fork such as Pillow. Double-shuffling It is perhaps not surprising, but rather striking, that if we shuffle the columns and then the rows to obtain a really scrambled-looking image like this: Blue hour in Paris, shuffled by columns and then by rows that it can nevertheless be reconstructed perfectly by applying the algorithm twice, first to the rows and then to the columns. Of course now the result may be flipped vertically as well as horizontally, but in this case I happened to get lucky twice and it came out in the same orientation as the original: Blue hour in Paris, reconstructed from the double-shuffled version The code for the double-shuffling and reconstruction is in the branch double-shuffling. Switch to that branch and run make double_reconstruct to try it. About No description, website, or topics provided. Resources Readme Releases No releases published Packages 0 No packages published Languages * C 35.1% * Python 33.8% * Makefile 27.2% * Shell 3.9% * (c) 2021 GitHub, Inc. * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time. You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.