<div class="csl-bib-body">
<div class="csl-entry">Schauer, C. (2010). <i>Reconstructing cross-cut shredded documents by means of evolutionary algorithms</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-36198</div>
</div>
Der Fokus dieser Masterarbeit liegt auf der Rekonstruktion von zerstörten Textdokumenten, die durch den maschinellen Einsatz von sogenannten Cross-Cut Schreddern vernichtet wurden.<br />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.<br />Das Bestreben dieser Masterarbeit ist nun maschinell durch Cross-Cut Schredder vernichtete Dokumente originalgetreu wiederherzustellen.<br />Hierfür wurde ein Genetischer Algorithmus (GA) entwickelt, implementiert und getestet um sich dieser Herausforderung zu stellen.<br />Zu allererst wird aber eine formale Definition dieses Problems gegeben und auf verwandte Themen verwiesen.<br />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.<br />Weiters wird eine Einführung in das Funktionsprinzip von GAs und darüber hinaus in die anderen Gebiete der Evolutionären Algorithmen gegeben.<br />Das behandelte Problem bezieht sich, im geometrischen Sinne, auf einen zweidimensional Raum.<br />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.<br />Um den GA noch weiter zu verbessern wurde eine lokale Suche mittels variabler Nachbarschaftssuche (VNS) eingebunden.<br />Schlussendlich werden die Testergebnisse von neunzig Instanzen basierend auf zehn Dokumenten präsentiert, wobei diese Resultate zur Evaluation der erstellten Operatoren dienen.<br />Einer dieser Ansätze war nachweisbar im Stande die bisherigen Methoden aufbauend auf Ameisenkolonie Optimierung und alleiniger VNS zu schlagen.<br />
de
dc.description.abstract
This master thesis focuses on the reconstruction of destroyed text documents, which were mechanically destructed with the help of so-called cross-cut shredders.<br />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.<br />The ambition of this master thesis is to automatically reconstruct cross-cut shredded text documents true to original.<br />To fulfil this aim a genetic algorithm (GA) has been developed, implemented and tested.<br />At the beginning a formal definition of this problem and references to related work will be given.<br />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.<br />An introduction to the working principle of GAs as well as other mainstreams of evolutionary computation will be given.<br />The considered problem obviously also has two-dimensional geometric aspects.<br />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.<br />To further improve the GA a local search phase based on variable neighbourhood search (VNS) is embedded.<br />Finally computational results for ninety instances based on ten different documents are presented, which were used for evaluating the designed operators.<br />It could be shown that one of the presented approaches outperforms previously described methods based on ant colony optimisation and VNS only.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Genetischer Algorithmus
de
dc.subject
Cross Cut Schredder
de
dc.subject
Rekonstruktion
de
dc.subject
Metaheuristik
de
dc.subject
genetical algorithm
en
dc.subject
cross cut shredder
en
dc.subject
reconstruction
en
dc.subject
metaheuristic
en
dc.title
Reconstructing cross-cut shredded documents by means of evolutionary algorithms
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Christian Schauer
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Prandtstetter, Matthias
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC07807710
-
dc.description.numberOfPages
85
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-36198
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.assistant.staffStatus
external
-
tuw.advisor.orcid
0000-0002-3293-177X
-
item.languageiso639-1
en
-
item.fulltext
with Fulltext
-
item.openaccessfulltext
Open Access
-
item.mimetype
application/pdf
-
item.openairetype
master thesis
-
item.grantfulltext
open
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E186 - Institut für Computergraphik und Algorithmen