[Back]

C. Schauer:
"Reconstructing cross-cut shredded documents by means of evolutionary algorithms";
Supervisor: G. Raidl, M. Prandtstetter; Institut für Computergraphik und Algorithmen, 2010; final examination: 2010-05.

This master thesis focuses on the reconstruction of destroyed text documents, which were mechanically destructed with the help of so-called cross-cut shredders. These machines cut a piece of paper into equally sized, usually rectangular, slices, which
leads to the fact that these shreds are indistinguishable on the basis of their shape.
The ambition of this master thesis is to automatically reconstruct cross-cut shredded text documents true to original. To fulfill this aim a genetic algorithm (GA) has been
developed, implemented and tested.
At the beginning a formal definition of this problem and references to related work
will be given. While there are some approaches published dealing with the reconstruction
of destroyed paper in general, there is barely work done in the field of cross-cut shredding. An introduction to the working principle of GAs as well as other mainstreams of evolutionary computation will be given.
The considered problem obviously also has two-dimensional geometric aspects. Due to the fact that the most popular GA operators were designed to work on onedimensional
solution representations, some proved operators were adapted and others newly created to match the needs of this master thesis.
To further improve the GA a local search phase based on variable neighbourhood search (VNS) is embedded.
Finally computational results for ninety instances based on ten different documents are presented, which were used for evaluating the designed operators. It could be shown that one of the presented approaches outperforms previously described
methods based on ant colony optimisation and VNS only.

Der Fokus dieser Masterarbeit liegt auf der Rekonstruktion von zerstörten Textdokumenten, die durch den maschinellen Einsatz von sogenannten Cross-Cut Schreddern vernichtet wurden. Diese Geräte schneiden das Papier in regelmäßige, gleichgroße -
bevorzugterweise rechteckige - Teile, was dazu führt, dass diese Schnipsel anhand ihrer Form nicht mehr unterscheidbar sind. Das Bestreben dieser Masterarbeit ist nun maschinell durch Cross-Cut Schredder vernichtete Dokumente originalgetreu
wiederherzustellen. Hierfür wurde ein Genetischer Algorithmus (GA) entwickelt, implementiert und getestet um sich dieser Herausforderung zu stellen.
Zu allererst wird aber eine formale Definition dieses Problems gegeben und auf verwandte Themen verwiesen. Während nämlich für die Papierrekonstruktion an sich ein paar wenige Ansätze bereits publiziert wurden, ist das Gebiet rund um
den Cross-Cut Schredder noch kaum erschlossen. Weiters wird eine Einführung in das Funktionsprinzip von GAs und darüber hinaus in die anderen Gebiete der Evolutionären Algorithmen gegeben.
Das behandelte Problem bezieht sich, im geometrischen Sinne, auf einen zweidimensional
Raum. Da die ausgereiften GA Operatoren aber auf eindimensionalen
Lösungsrepräsentationen arbeiten, mussten für diese Masterarbeit bewährte Operatoren adaptiert und neue entworfen werden.
Um den GA noch weiter zu verbessern wurde eine lokale Suche mittels variabler Nachbarschaftssuche (VNS) eingebunden.
Schlussendlich werden die Testergebnisse von neunzig Instanzen basierend auf zehn Dokumenten präsentiert, wobei diese Resultate zur Evaluation der erstellten Operatoren dienen. Einer dieser Ansätze war nachweisbar im Stande die bisherigen Methoden aufbauend auf Ameisenkolonie Optimierung und alleiniger VNS zu schlagen.

http://publik.tuwien.ac.at/files/PubDat_188786.pdf