Titelaufnahme

Titel
Reconstructing cross-cut shredded documents by means of evolutionary algorithms / von Christian Schauer
VerfasserSchauer, Christian
Begutachter / BegutachterinRaidl, Günther ; Prandtstetter, Matthias
Erschienen2010
UmfangVII, 85 Bl. : Ill., graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2010
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)Genetischer Algorithmus, Cross Cut Schredder, Rekonstruktion, Metaheuristik
Schlagwörter (EN)genetical algorithm, cross cut shredder, reconstruction, metaheuristic
URNurn:nbn:at:at-ubtuw:1-36198 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Reconstructing cross-cut shredded documents by means of evolutionary algorithms [4.97 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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.

Zusammenfassung (Englisch)

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 fulfil 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 one-dimensional 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.