[Zurück]

W. Morandell:
"Evaluation and reconstruction of strip-shredded text documents";
Betreuer/in(nen): G. Raidl, M. Prandtstetter; Institut für Computergraphik und Algorithmen, 2008; Abschlussprüfung: 05/2008.

In my master's thesis I elaborate on strip-shredded text document
reconstruction. Contrary to conventional document reconstruction which
uses color or shape information of images text document reconstruction
has not been researched very well. Nowadays it is common to destroy
paper documents by shredding them, i.e. producing paper strips. This work
tries to nd ways to undo the process. First and foremost I describe the
problem formally. Next I de ne a way to evaluate problem instances. A set
of improvement strategies are introduced which help the evaluation process.
De ned construction heuristics yield good results in reasonable amount of
time. Then optimization algorithms try to nd a good arrangement of the
strips, ideally the correct one. A demo application simulates the shredding
process of a sample page. Then this page is reconstructed using the above
mentioned evaluation techniques and several optimization techniques like
multistart variable neighborhood search, simulated annealing and iterated
local search. Extensive tests were run with a 60 instance test set. The
implemented application reconstructed more than half of the problem
instances correctly and is also able to reconstruct several pages at once.