[Zurück]


Diplom- und Master-Arbeiten (eigene und betreute):

T. Winkler:
"Anwendung von kombinatorischen Optimierungsmethoden zur Rekonstruktion von in Streifen geschnittenen Papierdokumenten";
Betreuer/in(nen): G. Raidl, C. Schauer; Institut für Computergraphik und Algorithmen, 2011; Abschlussprüfung: 07/2011.



Kurzfassung deutsch:
Diese Diplomarbeit behandelt das Thema der Rekonstruktion von in Streifen
geschnittenen Textdokumenten. Das Wiederherstellen solcher Seiten wird als
ein kombinatorisches Optimierungsproblem interpretiert, bei dem die einzelnen
Streifen in die ursprüngliche Reihenfolge gebracht werden müssen.
Zuerst werden einige Ansätze zur Behandlung des Problems der unbekannten
Orientierung der einzelnen Streifen vorgestellt. Anhand des Bereichs zwischen
den Textzeilen aber auch mit einer einfachen Erkennung von markanten
Buchstaben wird versucht eine Zuordnung der Orientierung zu bewerkstelligen.
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.
Im Zuge dieser Arbeit wird die Rekonstruktion mittels einer variablen Nachbarschaftssuche
durchgeführt. 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. Drei
unterschiedliche Ansätze werden beschrieben und getestet.
Als Testinstanzen werden zehn Dokumente mit je vier verschiedenen Streifenbreiten
zerschnitten und die drei Ansätze darauf getestet. 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.

Kurzfassung englisch:
This thesis addresses the issue of reconstructing strip shredded text documents.
This reconstruction process of such pages is interpreted as a combinatorial
optimization problem, whereat the individual strips must be placed
in their original order.
First, some approaches identifying the orientation of each strip will be presented.
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. 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.
In this work the reconstruction is performed by using a variable neighborhood
search. Additionally di erent methods will be discussed to further improve
the reconstruction process, like grouping strips into blocks that are already
in their correct order. Three di erent approaches are described and tested.
As benchmark instances ten documents each cut with four di erent strip
widths were used to test the three approaches. 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.


Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_200754.pdf


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.