Title: Reconstructing cross-cut shredded documents by means of evolutionary algorithms
Language: English
Authors: Schauer, Christian
Qualification level: Diploma
Keywords: Genetischer Algorithmus; Cross Cut Schredder; Rekonstruktion; Metaheuristik
genetical algorithm; cross cut shredder; reconstruction; metaheuristic
Advisor: Raidl, Günther
Assisting Advisor: Prandtstetter, Matthias
Issue Date: 2010
Number of Pages: 85
Qualification level: Diploma
Abstract: 
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.

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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-36198
http://hdl.handle.net/20.500.12708/10572
Library ID: AC07807710
Organisation: E186 - Institut für Computergraphik und Algorithmen 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

11
checked on Feb 18, 2021

Download(s)

51
checked on Feb 18, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.