Saul "Shredded" Man!

Inspiration

Our Story: Anver, our lead backend developer, was watching the hit show "Better Call Saul" and stumbled upon an interesting problem. Saul had to reconstruct hundreds of shredded documents by hand. Work like that takes long, painstaking hours of manual reconstruction. He came to us with a simple question; What if we could help Saul?

What it does

Solving the Problem: Our reconstruction technology identifies each individual strip of paper within one or more images of your shredded document. Using a combination of edge comparison, Gaussian blurring, and optical character recognition our software can rebuild a shredded document with ease.

How we built it

Identification: Photos are handled vertically, and are rotated as such if seen to be horizontal. From this rotated image photos are converted to greyscale, where a detection mask is used to separate white and black pixels using specific thresholds. White regions are traced, with each being analyzed to find objects that fit within a known range of strips areas.

Normalization: Each strip must be straightened for ease of comparison. With transparency masking, strips are resampled. This removes any empty space above or below the strip, and straightens curves by estimation of right and left limits.

The Sort: Three signals are made for each strip's text pattern: left edge, right edge, and cross-body. All possible left-right pairs are compared to one another, with initial weighting on how text aligns cross-strip. Vertical shifts are attempted, along with smaller local corrections to accommodate for imperfect shredding and photography. Optical character recognition (OCR) is used to examine text across a join when it is present. If a split word is rejoined and is recognized, the confidence level for the strip pair rises. After ranking, pairs of strips are assembled in to a working order. OCR will then iterate over three strips, checking for potential swaps to reveal text that could not be determined in a comparison of two strips. A last run is done across each potential reconstructed group to determine final ordering.

Reconstruction: With strips having concrete order, strips are placed side-by-side and vertically aligned. The reconstructed document is available to the user as a .png file.

Challenges we ran into

Image Quality: Quality of images heavily weighs into whether the algorithm can discern text and accurately assess edge signals. There are multiple sources of error here, with lighting, background and image quality enhancing the difficulty of an accurate sort.

Accuracy of Sorting: The sorting algorithm is complicated, and unfortunately not optimized. Especially when image quality falters, strip permutations can be scored inaccurately to their actual pairing. Weights are added to compensate for this fact, but for now produce imperfect scoring. A paper from the Imperial College of London concerning this topic is linked below for additional reading:

Automatic Reconstruction of Images from Shredded Paper

What we learned

Lessons for the Future: The group has learned a lot about harnessing the power of image recognition and computer vision software! The implementation of this rigorous sort has pushed the boundaries of all of our knowledge, requiring extensive discussion, research and inquiry into new spaces.

What's next for Saul "Shredded" Man!

Looking Ahead: To improve on our software, the accuracy of the sorting algorithm must be improved. Continuing to tweak weights and processes within it can yield results, but it will take time! From there, launching of an official webpage along with services for documents shredded in different fashions are on the horizon. We aim to keep improving our product to give the user a fast and reliable method for document reconstruction.