A Two-Stage Approach for Reconstruction of Cross-Cut Shredded Text Documents

This paper presents a two-stage approach for reconstruction of cross-cut shredded text documents. Cross-cut shredding is used to mechanically cut a document into rectangular shreds of (almost) identical shapes. After pre-processing shreds with image-based techniques, we defined a cluster quality measure called "matching proportion" (MP), with which, shreds in the same rows were found by clustering. Then the shreds in each cluster (row) were aligned and the whole document was reconstructed by aligning all rows. All the alignments were done by a memetic algorithm which was extended from a genetic algorithm by embedding a probabilistic Kruskal based heuristic. Experiments were presented for two different instances. Results show that the two-stage approach is an appropriate reconstruction method which provides good solutions in a reasonable amount of time.