3
$\begingroup$

I am not certain this is the proper site for this question however I am mainly looking for resources on this topic (perhaps code). I was watching TV and one of the characters had a lawyer who destroyed his documents using a paper shredder. A lab tech said that the shredder was special.

I am not familiar with this area of computer science/ mathematics but I am looking for information on efficient algorithms to reconstruct destroyed documents. I can come up with a naive approach that is brute force fairly easily I imagine but just going through all the pieces and looking for edges that are the same but this doesn't sound feasible as the number of combinations will explode.

Note: By destroyed documents I am talking about taking a document (printed out) and then shredding it into small pieces and reassembling it by determining which pieces fit together.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Can you edit your question to define "destroyed documents"? $\endgroup$
    – lox
    Commented May 19, 2019 at 22:49
  • 2
    $\begingroup$ You should look at the methods used to recover the Stasi (East German secret police) archives that were shredded or mostly -- oops all the shredders are broken from over use -- torn up after the fall of the Berlin Wall. The BBC has a very high-level summary. $\endgroup$
    – David Richerby
    Commented May 19, 2019 at 22:59

1 Answer 1

Reset to default
3
$\begingroup$

Your problem is NP-Complete, even for strips (n strips yields (2n)!) used, so people use heuristics, transforms like Hough and morphological filters (to match continuity of text, but this heavily increases complexity for matching) or any kind of genetic / NN search, Ants Colony Optimization.

For summary of consecutive steps and various algorithm I recommend An Investigation into Automated Shredded Document Reconstruction using Heuristic Search Algorithms.

The problem itself may end up in nasty cases, when document is not fully sharp (blurred, printed with low resolution) and strips width is small and cut by physical cutter with dulled edges, because standard merging methods like panorama photo sticher gets lost and yield improper results. This is due to lost information by missing small strips, otherwise if you have full digital image cut into pieces, it is as hard as Jigsaw puzzle, non-digital image falls into approximate search.

To make algorithm automatic another problem is pieces feeding, rarely you can give axis aligned strips, so to start process it is nice to input all stripes as one picture with pieces lay by hand, this imposes another problem (this one is easy) to detect blobs and rotate them.

By special shredder instead of stripes yield very small rectangles. For comparison, P-1 class shredder gives stripes 6-12mm wide of any length (about 1800mm^2), class P-7 gives rectangles with area less than 5mm^2. When you get rectangles instead of stripes, problem yields (4n)! permutations, assuming one one-sided document, if there are lots of shreds from unrelated documents (no pictures, text only) in one bag, problem is not really tractable.

Improve this answer
$\endgroup$
3
  • $\begingroup$ There may be (2n)! arrangements of the shredded strips, but does that still determine the time complexity? Whenever you find "matches" you can "group" them together, behaving as a "thick strip", where only the first and last edge matter for the sake of comparison against other strips. This "clumping" should reduce the search space hugely, but IDK if it will still be O(n!) $\endgroup$
    – Alexander
    Commented May 20, 2019 at 1:24
  • $\begingroup$ @Alexander This is not the complexity per se. The true hardness comes from the fact, that you are not fully sure, whether your match is really good. If you take a look at the pdf, figure 6.1 page 69, the tigers picture and all consecutive pictures, there are errors. You still have to check fitness of all edges pairwise , take for example several pieces, "grouping them" seems nice, but by choosing elements you prevent some other matches, which may get lower fit but MSE is lower. If exact matching of the edges is viable option, it will be blazingly fast, in my answer I assume it is not possible. $\endgroup$
    – Evil
    Commented May 20, 2019 at 1:41
  • $\begingroup$ You may not be fully sure that a reasonably good match is really correct, but when you encounter a match that's bad you can prune the search space. $\endgroup$
    – Ben Voigt
    Commented May 20, 2019 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.