<div class="csl-bib-body">
<div class="csl-entry">Winkler, T. (2011). <i>Anwendung von kombinatorischen Optimierungsmethoden zur Rekonstruktion von in Streifen geschnittenen Papierdokumenten</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-38069</div>
</div>
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
-
dc.description
Zsfassung in engl. Sprache
-
dc.description.abstract
Diese Diplomarbeit behandelt das Thema der Rekonstruktion von in Streifen geschnittenen Textdokumenten.<br />Das Wiederherstellen solcher Seiten wird als ein kombinatorisches Optimierungsproblem interpretiert, bei dem die einzelnen Streifen in die ursprüngliche Reihenfolge gebracht werden müssen.<br />Zuerst werden einige Ansätze zur Behandlung des Problems der unbekannten Orientierung der einzelnen Streifen vorgestellt.<br />Anhand des Bereichs zwischen den Textzeilen aber auch mit einer einfachen Erkennung von markanten Buchstaben wird versucht eine Zuordnung der Orientierung zu bewerkstelligen.<br />Weiters wird eine Methode zur Erkennung der Randstücke - also jene beiden Streifen, die sich im Original links und rechts auf der Seite befunden haben - angewandt, um die Lesbarkeit und die Qualität der Lösung zu erhöhen.<br />Im Zuge dieser Arbeit wird die Rekonstruktion mittels einer variablen Nachbarschaftssuche durchgeführt.<br />Es werden zusätzlich unterschiedliche Methoden gezeigt, wie man bei der Rekonstruktion eine Verbesserung erhält, indem man die bereits richtig angeordneten Streifen zu Blöcken zusammenfasst.<br />Drei unterschiedliche Ansätze werden beschrieben und getestet.<br />Als Testinstanzen werden zehn Dokumente mit je vier verschiedenen Streifenbreiten zerschnitten und die drei Ansätze darauf getestet.<br />Es zeigt sich, dass bei einem Viertel aller Testinstanzen eine vollständige und bei mehr als der Hälfte der Testinstanzen eine lesbare Rekonstruktion möglich ist.<br />
de
dc.description.abstract
This thesis addresses the issue of reconstructing strip shredded text documents.<br />This reconstruction process of such pages is interpreted as a combinatorial optimization problem, whereat the individual strips must be placed in their original order.<br />First, some approaches identifying the orientation of each strip will be presented.<br />Based on the area between lines of text but also with a simple recognition technique for some distinctive characters it is tried to assign the correct orientation.<br />Furthermore, a method for detecting the margin - i.e., those two strips on the left and right side of the original document - is applied for better readability and to increase the quality of the solution.<br /> In this work the reconstruction is performed by using a variable neighborhood search.<br />Additionally different methods will be discussed to further improve the reconstruction process, like grouping strips into blocks that are already in their correct order.<br />Three different approaches are described and tested.<br />As benchmark instances ten documents each cut with four different strip widths were used to test the three approaches.<br />It turns out that with more than a quarter of the test instances a complete and with more than half of the instances a readable reconstruction was possible.
en
dc.language
Deutsch
-
dc.language.iso
de
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Rekonstruktion
de
dc.subject
kombinatorische Optimierung
de
dc.subject
Variable Nachbarschaftssuche
de
dc.subject
Blockbildung
de
dc.subject
Orientierungserkennung
de
dc.subject
Schredder
de
dc.subject
Reconstruction
en
dc.subject
combinatorial optimization
en
dc.subject
variable neighborhood search
en
dc.subject
block building
en
dc.subject
orientation detection
en
dc.subject
shredder
en
dc.title
Anwendung von kombinatorischen Optimierungsmethoden zur Rekonstruktion von in Streifen geschnittenen Papierdokumenten
de
dc.title.alternative
Application of combinatorial optimization methods for the reconstruction of strip-shredded paper documents
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
Thomas Winkler
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Schauer, Christian
-
dc.contributor.assistant
Prandtstetter, Matthias
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen