12 ms·
Image unshredding using a TSP solver
- jdthedisciple 5y agoWhat would be an exemplary use case for this? Like, when do you ever have images in front of you that are shuffled in this way?
- tylfin 5y agoI could imagine a civil or criminal case relying on shredded documents as a source of evidence.
- klyrs 5y agoWhen you dumpster dive your competitor looking for trade secrets?
- IncRnd 5y agoWe don't shred digital images in RAM in that way, but we can scan & reconstruct physical images that have been shredded or torn. You can paste together possible scenes to construct side-scrolling game scenery in realtime. By applying a few insights we can phase one image into a hole that is in another image. This is similar to randomizing an array by creating a second array with random values, then sorting them in tandem, except we use the TSP with expected weightings. There are lots of use cases for this.
- est31 5y agoIn the virtual RAM accessible to the process the image might be continuous, but its physical representation could be different, as the operating system might use different areas from the physical RAM to expose it to the process. If you dump a computer's RAM e.g. in a forensic setting, you might attain such a state. Same goes for file systems as well as the wear leveling layer of SSDs.
- IncRnd 5y agoexactly!
- clipradiowallet 5y agoWell, imagine someone dumpster diving at a bank/clinic/insurance provider that doesn't use a document destruction service. Probably plenty of PII/PHI could be reconstructed once the shredded fragments were singulated and scanned.
- the8472 5y agoIn the 90s and 00s analog pay tv used to be "encrypted" like this. IIRC software decryption relied on deriving the weak shuffling key by manually reordering image rows and then using that to reverse the key so the next frames could be decrypted more reliably. Doing that kind of video processing in realtime and in software was close to CPU limits. https://en.wikipedia.org/wiki/Nagravision https://en.wikipedia.org/wiki/Nagravision
- aliasEli 5y agoThis might even have an application for real documents. There are police cases where some suspects have tried to destroy evidence. Manually reconstructing the original takes a lot of effort. I expect that the CIA and NSA already have software for it, but I have never heard of it being used in a police case.
- perihelions 5y agoGermany has run a program for decades to recover the Stasi's paper documents, the bulk of which it shredded at the fall of the GDR. People can sometimes get their own Stasi files, if they're recovered. https://www.dw.com/en/how-ai-could-solve-a-600-million-piece-puzzle/av-55130523 https://www.dw.com/en/how-ai-could-solve-a-600-million-piece... https://www.wired.com/2008/01/ff-stasi/ https://www.wired.com/2008/01/ff-stasi/ https://boingboing.net/2018/01/09/truth-reconciliation-and-tape.html https://boingboing.net/2018/01/09/truth-reconciliation-and-t... Surprisingly, there's never been an HN thread about this (as far as I can tell). From the Wired link: "Today, the study in Poppe's Berlin apartment is lined floor to 12-foot ceiling with bookshelves full of volumes on art, literature, and political science. But one shelf, just to the left of her desk, is special. It holds a pair of 3-inch-thick black binders — copies of the most important documents in Poppe's secret police files. This is her Stasi shelf."
- odysseus 5y agoThe painstaking process to put back together shredded Stasi documents is mentioned at the end of The Lives of Others: https://www.imdb.com/title/tt0405094/ https://www.imdb.com/title/tt0405094/ Great movie, by the way.
- airstrike 5y ago_Fantastic_ movie, I just wanted to add.
- einpoklum 5y agoI really didn't like that movie, focusing on people who are wholly uninteresting politically; presenting a sort of a "shocked and chagrined" attitude to people being spied on by the government; and treating West Germany as some sort of paradise. I would recommend Ken Loach's Fatherland instead; but - only until when Dritterman arrives in the UK (the end of the film is kind of messed up).
- whazor 5y agoI used TSP to optimally stack different types of bowls. I measured all the different pairs of bowls and searched for the shortest route through all the bowls we have. I found that you can split the stacks however you want, I also had an algorithm for that.
- Conlectus 5y agoIs the algorithm different from a simple sorted order in this case? The difficulty with TSP is that you have to return to the start, which wouldn't seek to be the case with stacled bowls, unless you're stacking them in a ring somehow.
- thaumasiotes 5y ago> The difficulty with TSP is that you have to return to the start That is not the difficulty with TSP. The problem doesn't get any easier if you can end wherever you please.
- Conlectus 5y agoYes, you're right. I misremembered the problem and thought a greedy algorithm would work in that case. It still seems to me that bowl-stacking is solved by sorting alone, though, which is of course much simpler.
- thaumasiotes 5y agoI tend to agree as to bowl-stacking.
- SavantIdiot 5y agoI wrote a program to do this two decades ago. I shredded a black and white text document (long shreds, not the new shredders that cut into confetti), scanned all the strips, front and back, and created a lookup value for each edge based on the pixel position. The biggest problem I had was the shredder blade removed too much material. This caused a continuous stroke to be fatter on one side than the other (imagine if the descender in a lowercase "p" was on the blade's path).
- hackcasual 5y agoDARPA had a challenge for this 10 years ago https://gizmodo.com/darpas-almost-impossible-challenge-to-reconstruct-shred-5865025 https://gizmodo.com/darpas-almost-impossible-challenge-to-re...
- SavantIdiot 5y agoThat's awesome! I had no idea it existed. Too bad the top level URL no longer exists, but now I'm eager to see if there are solutions online today.
- nielsbot 5y agoI wonder if a high resolution photo of all the shreds (flattened out) would also work and be easier?
- SavantIdiot 5y agoThat's exactly what I started with. Well, not a scan but rather a digital picture since I didn't have a scanner (also my camera sucked). I also didn't do a very good job with boundary detection so I ended up snapping rectangles and extracting the 1-bit pixmaps manually.
- sgk284 5y agoThis was a hiring puzzle from the Instagram team in 2012, from back before Facebook acquired them: https://instagram-engineering.com/instagram-engineering-challenge-the-unshredder-7ef3f7323ab1 https://instagram-engineering.com/instagram-engineering-chal... I remember having a lot of fun solving it, in Coffeescript (which was all the rage at the time), also with TSP but using the Pearson correlation coefficient as the similarity metric: https://gist.github.com/stevekrenzel/1505619 https://gist.github.com/stevekrenzel/1505619 Here's a little demo of it in action: http://krenzel.org/files/insta/ http://krenzel.org/files/insta/
- speedgoose 5y agoI like how unicorns can do such hiring challenges while normal companies are desperate for people to apply. I think my current company would hire anyone who can breath and write 3 lines of code per month, but no one fitting these criteria applies.
- onion2k 5y agoI can write 4 lines of code per month, so I guess I'm overqualified.
- speedgoose 5y agoDo they work ?
- reificator 5y agoOh, now we're moving the goalposts eh?
- malux85 5y agoOn my machine, yes
- kevin_thibedeau 5y agoThey've got +3 on StackOverflow so fully peer reviewed.
- sllabres 5y agoThis is quite similar to the early decryption of the analog Nagravision TV encryption system https://en.wikipedia.org/wiki/Nagravision https://en.wikipedia.org/wiki/Nagravision worked. Did it myself at the time, but on to slow hardware/to little optimized software. The decryption took much to long to be usable, but it was fun to see that it worked quite fine
- einpoklum 5y agoThe author's latest commit: @robinhouston The word “perfectly” was used too many times :-P
- nayuki 5y agoDiscussions back in 2016: https://news.ycombinator.com/item?id=12670997 https://news.ycombinator.com/item?id=12670997 ; https://news.ycombinator.com/item?id=12667611 https://news.ycombinator.com/item?id=12667611
- hinkley 5y agoI don't suppose there's a way to process paper into 'pellets' fit for recycling that make this whole process untenable. Paper fiber length dictates a lot about its reuse. The bigger the chunks the smaller the combinatorics for reversing the 'algorithm'. Big paper mache blobs might fare better. From a recycling standpoint a machine that tears the paper instead of cutting it would do better, but the uniqueness of the edges probably reduces the problem space. If someone invents a fast paper pulping machine that can mount on a small truck that doesn't require a commercial vehicle license, I bet you could sell loads of them. Whatever happened to that team who used microcavitation to blast the ink off of paper for reuse? Probably enough solvents left behind to read the text like invisible ink, but as a first pass it might be good.
- magnimeelcul 5y agoCool read! Though ordering the columns such that the cumulative cobsecutive dissimilaritiea are minimized is not what you really want. Think of a shredded image of a checkerboard: with this objective you would not obtain the original but rather a version where there are contigous black/white steps on the left and on the right, with a discontinuity in the middle. That is to say: by reducing the objective to this you are assuming the image is continuous on the horizzontal axis, while in image processing images are usually supposed to be only piecewise continuous.
- stavros 5y agoBut there's no way to reconstruct a checkerboard image without knowing what it represented originally.
- magnimeelcul 5y agoWithout any a-priori I guess that's true, i.e. the problem they want to solve isn't guaranteed to have a solution
- ivanpondal 5y agoI really liked the TSP approach when this came out. Turns out it works pretty well on text too: https://github.com/ivanpondal/text-unshredding https://github.com/ivanpondal/text-unshredding
- deleted 5y ago[deleted]
- WalterBright 5y agoIf you're going to use a shredder: 1. use a cross-cut shredder 2. mix many different shred jobs in the same bag 3. mix the contents of multiple bags 4. deposit different bags in different trash runs 5. just burn it
- deleted 5y ago[deleted]
- jhncls 5y agoWould this algorithm allow for an image version of the Burrows-Wheeler transform? So, sorting image rows and columns using a compressibility criterion. [0] https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...
- nullc 5y agoIf you took a relatively smooth image like a picture of a sky with a lot of high frequency (e.g. sensor) noise I'd expect this method to fail to be exact. Having a sparse representation in a DCT basis would be an even better metric. You want the unshredding which makes the (e.g.) 8-pixel wide horizontal DCT's have the lowest norm. Because this metric depends on more than just pairs of lines though it's not obvious how to construct an efficient TSP out of it. One could easily take a TSP solution and post process using the DCT metric, testing out all possible swaps (or near ties in the TSP solution).