Globally consistent reconstruction of ripped-up documents

One of the most crucial steps for automatically reconstructing ripped-up documents is to find a globally consistent solution from the ambiguous candidate matches. However, little work has been done so far to solve this problem in a general computational framework without using application-specific features. In this paper, we propose a global approach for reconstructing ripped-up documents by first finding candidate matches from document fragments using curve matching and then disambiguating these candidates through a relaxation process to reconstruct the original document. The candidate disambiguation problem is formulated in a relaxation scheme, in which the definition of compatibility between neighboring matches is proposed and global consistency is defined as the global criterion. Initially, global match confidences are assigned to each of the candidate matches. After that, the overall local relationships among neighboring matches are evaluated by computing their global consistency. Then these confidences are iteratively updated using the gradient projection method to maximize the criterion. This leads to a globally consistent solution and thus provides a sound document reconstruction. The overall performance of our approach in several practical experiments is illustrated. The results indicate that the reconstruction of ripped-up documents up to fifty pieces is possibly accomplished automatically.