7 ms·
Image unshredder by simulated annealing (2015)
- wwwtyro 10y agoWould like to see this applied to a page of text.
- smcmurtry 10y agoAnd to a bag of slices from multiple pages of text.
- sam4ritan 10y agothere are still a lot of destroyed documents being stored around the world (say, from the StaSi for example). I would love to see this applied on them. It migjt shed some light on things supposedly lost to history.
- yiyus 10y agoSome way to fix the image would certainly help, but you still need to find a way to scan all the parts and put them in the right direction. Moreover, some of those documents may have been destroyed for very valid reasons.
- diggan 10y agoSliding a bit off topic but what would be a valid reason for them to have been destroyed? Other than masking history, which I'm sure is valid for some, for most it's not a great thing.
- throwanem 10y agoThe internal security agencies of repressive governments are very good in general at collecting people's secrets for use as weapons. There's no potential for harm that I can see in destroying such information, and considerable potential for harm in recovering it.
- 08-15 10y agoDo you actually think these documents remain destroyed for technical reasons? Of 90.000 official and 200.000 unofficial employees of the Stasi (secret police of the German Democratic Republic), a whopping 20 have been convicted. Do you think that's because the powers that be couldn't do better? The official excuse is that whatever the Stasi did was lawful at the time. The same logic would have made the Nuremberg Trials impossible, but it wasn't applied. That's not an accident.
- catscratch 10y agoDidn't work for me either time I tried.
- mannk 10y agoAs stated in the "notes" section, you need to set the number of iterations to about 1 billion, and also adjust the temperature according to the picture's characteristics.
- nayuki 10y agoYou are right; with the current algorithm it is quite difficult to fully unscramble the image into one single strip. For now, the best you can do is get a bunch (~20) of strips after annealing, and manually flip and rearrange them (in an image editor) to get back the original image. The default temperature of 4000 is fine for all the example images at 600×400. The default 30 million iterations leads to a reasonable run time of about 10 seconds, but leaves many small strips after annealing. Bumping up the number of iterations to 300 million, 3000 million, etc. will take proportionally longer time, and give marginally better results.
- mdonahoe 10y agoBased on the description in the webpage, I expected it to work on the default image with default parameters
- retreatguru 10y agoIt looks like it might work best as a two step process. first pass to connect the major chunks, then find the edges and anneal those chunks.
- simcop2387 10y agoAlong with flipping chunks horizontally if no good solution is found. right now some chunks end up mirrored
- danbruc 10y agoWhy simulated annealing? Wouldn't it be much more efficient to just compare all pairs of columns and then sort them cording to similarity? That would take a 360,000 comparisons instead of about a billion iterations for an image 600 pixels width.
- re 10y agoA similarity score for a pair of columns doesn't give you an ordering that you can use for sorting.
- Houshalter 10y agoSure it does, just run it multiple times. First pick a random slice. Then find the most similar slice and place it next to it. Then find the most similar slice to that and place it next to that, and so on. (And do this in both directions from the starting slice to get both sides.) Eventually you will complete the whole image.
- contravariant 10y agoIf you have the similarity between pairs of columns and try to find an order such that the similarity between adjacent columns is minimal, you've basically got a version of the travelling salesman problem.
- highd 10y agoWhich is NP-Hard in general, but this instantiation of it can be made significantly easier than a random instantiation (in clock time, anyways). You could pick a similarity metric such that adjacent columns have some bound on worst-case similarity - this allows you to reject many adjacencies. This could be chosen empirically by analyzing other known images. You could additionally model the probability distributions of similarity for adjacent columns, thus allowing you to reject further adjacencies and sets of adjacencies. By using all this structure you should be able to do much better than this simulated annealing - which I have yet to see complete successfully on my machine, at any rate. Is the author here? What energy metric is this using? Total variation?
- jcoffland 10y agoYou could improve this greatly by adding another type of change to the annealing function. Instead of just swapping columns sometimes (I.e. at random) it should evaluate flips. A flip is performed by choosing two columns at random and then reversing the order of all the columns between them. Annealing algorithms in general benefit from a diverse set of change functions.
- deleted 10y ago[deleted]
- nayuki 10y agoI really like your idea of mirroring a random range of columns. I would consider implementing it the next time I have time to work on the code
- jaggederest 10y agoI think another optimization would be to 'grow' the regions considered. Instead of treating every column as a separate object, have the size of regions considered vary with the temperature. The metaphor would crystal formation within annealed metal.
- Retr0spectrum 10y agoThe image I tested seemed to fall into some kind of local maximum: http://i.imgur.com/miCDFOD.png http://i.imgur.com/miCDFOD.png As you can see, the left quarter of the image is reversed. I imagine the additional function you described would help with this.
- pablobaz 10y agoI'd be interested to see how a Genetic algorithm with carefully chosen mutation/recombination operators would suit this problem. Mutations could be flips and random swaps. Recombination would be combining chunks of already partially optimised solutions (breeding). Genetic algorithms do suffer a cost of having to keep a population of solutions in memory so it would be interesting to see how the end results compares in performance to annealing.
- jobigoud 10y ago> carefully chosen mutation/recombination operators A job for a meta-genetic algorithm maybe? Where the mutation operators are themselves evolved.
- nayuki 10y ago> The unscrambling problem being solved here is much harder than a typical unscrambling problem, because we are rearranging single columns of pixels. As a consequence of this design, it is impossible to resolve the horizontal reflection symmetry ambiguity – every image has exactly the same energy score as its mirror image. > In a more typical problem, the image would be sliced into groups of columns, where each group moves as a unit. This situation would reduce the number of pieces to unscramble, and also make the arrangement be unambiguous to horizontal flips.
- Beltiras 10y agoCouldn't you do some feature detection on the edges of the resulting columns and repeat the annealing to get a better end-product?
- ttul 10y agoSimulated annealing is super cool. Back at the dawn of time, my colleague and I used this technique to place and route transistors for a project in our VLSI course. It was the most fun.
- foob 10y agoThis is a fun demo but, as others have mentioned, simulated annealing really isn't necessary, or even that appropriate, for this specific problem. I threw together the same demo with a very trivial algorithm that I think does a more accurate job of reconstructing the same images in significantly less time than the simulated annealing [1]. The algorithm consists of first finding the closest matching pair of pixels as a seed. It then finds the remaining column that most closely matches one of the current edges and adds it to the reconstructed columns. This then repeats until there are no remaining columns. On a different note, if this quote: > The unscrambling problem being solved here is much harder than a typical unscrambling problem, because we are rearranging single columns of pixels. is referring to reconstructing shredded strips of paper then it is laughably false. The single columns of pixels are extremely clean and correspond very, very closely to their neighboring columns. In reality, the tearing of the paper makes the edges not match very well and it's just much noisier in general. I've worked on this problem before and it's many orders of magnitude more challenging than the reconstruction that is done in this demo. [1] http://sangaline.com/blog/image_unshredder/ http://sangaline.com/blog/image_unshredder/
- rosalinekarr 10y agoWait, you threw that demo together in under 20 minutes? Wow.
- maus42 10y ago>I've worked on this problem before I suppose it helps if you're already familiar with the problem domain. Nevertheless, it's very cool indeed.
- nayuki 10y agoThanks for the helpful critique. Your proposed algorithm is reasonable and much, much faster than simulated annealing, and I appreciate the live demo. It looks like your algorithm is deterministic (except for tie-breaking of a pair of columns that have the same difference?), so it doesn't matter which way the image is shuffled. You are also correct that I overstated how hard the problem is; in retrospect it isn't that hard at all to unshred clean digital images (as opposed to paper scans). On your web page: > It takes roughly the same amount of time to run but correctly reconstructs all of the images. This is not true, but is very close to correct. The image "Blue Hour in Paris" has some disturbances in the lower part of the sky, "Alaska Railroad" has a single wrong column on one side of the image, and "Abstract Light Painting" sometimes has a few incorrect columns on the edge. At least that's what I could spot by eye at a glance; I didn't rigorously compare them against the original images.
- code_sardaukar 10y agoAwesome, but please put the original energy somewhere. It's not clear whether the final configuration actually has a lower or higher energy that the original image, which would be interesting to know.
- Luc 10y agoSome real world unshredding by Fraunhofer Institue: http://www.ipk.fraunhofer.de/fileadmin/user_upload/IPK_FHG/publikationen/themenbroschueren/at_vReko_en.pdf http://www.ipk.fraunhofer.de/fileadmin/user_upload/IPK_FHG/p... Shredded secret service files, fragments of papyri or frescos...
- SyneRyder 10y agoThe BBC also did a good story on Fraunhofer's E-Puzzler being used to piece together shredded Stasi documents: http://www.bbc.com/news/magazine-19344978 http://www.bbc.com/news/magazine-19344978
- yincrash 10y agoIs there a definition of temperature that someone can share that would be relevant in this context?
- corpus 10y agoprobability of bouncing out of a local minimum
- 08-15 10y agoIt doesn't work, plain and simple. Never mind what many others have said, that a greedy algorithm might work, that you can reduce it to TSP and apply heuristics, etc. The application of simulated annealing is also crippled: Suppose you reconstructed two slices of the image. To improve it, you have to take a column from one slice and move it to the other---but that doesn't lower the energy! What would lower the energy is to take one of the slices and attach it to the other, possibly flipping it in the process. So while it says "simulated annealing" on the lid, it's a random walk for the most part. The idea is workable, but it needs a different primitive operation: pick a range of columns, attach it in a different spot, possibly flipping it.
- 45h34jh53k4j 10y agoThank you for the demo. This helped me understand the recent quantum computing (quantum annealing) process a little more concretely. What I saw here was a scrambled image being sorted to find a local minima of entropy in pixel color value between respective stripes. A quantum annealing computer is doing is, where the image is the problem space (scrambled because we dont have the solution), and the quantum computer rearranges this to find global minima/maxima. Where a QC is not useful would be when the problem space is too big (image too big), or it can only find a local minima that isn't the solution to the classical problem (picture is still objectively after annealing) please comment someone if my understanding is wrong
- bragh 10y agoIIRC, the best thing to do was to apply clustering to the rows/columns (k-means and hierarchical both worked, but I think it was hard to find the appropriate tree height for hierarchical clustering) and then to apply seriation: http://innar.com/Liiv_Seriation.pdf http://innar.com/Liiv_Seriation.pdf