Hallucination: A mixed-initiative approach for efficient document reconstruction

(a) A piece of a shredded document with cut off letters ‘N ’ and ‘T ’ written in black ink is displayed. We use human-drawn templates (in red, (b)) to find the best matching neighbor (c) using a standard computer vision algorithm. This approach, which we call hallucination, significantly outperforms humans and computers working in isolation. We introduce a mixed-initiative approach for document re-construction that can significantly reduce the amount of time and effort required to reassemble a document from shredded pieces or an artifact from broken fragments. We focus in par-ticular on the hardest subproblem, which is the problem of identifying a matching neighbor for any given piece. Our ap-proach, called hallucination, combines human and machine intelligence by leveraging people’s ability to draw what a neighboring piece may look like, and then using the drawing as a template based on which the computer computes likely matches. Experiments on a puzzle from the DARPA Shredder Challenge demonstrate that the hallucination approach sig-nificantly reduces the search space for identifying a match, outperforming humans and computers working in isolation