Titelaufnahme

Titel
Anwendung von kombinatorischen Optimierungsmethoden zur Rekonstruktion von in Streifen geschnittenen Papierdokumenten / von Thomas Winkler
VerfasserWinkler, Thomas
Begutachter / BegutachterinRaidl, Günther ; Schauer, Christian ; Prandtstetter, Matthias
Erschienen2011
UmfangIII, 97 Bl. : Ill., graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2011
Anmerkung
Zsfassung in engl. Sprache
SpracheDeutsch
DokumenttypDiplomarbeit
Schlagwörter (DE)Rekonstruktion / kombinatorische Optimierung / Variable Nachbarschaftssuche / Blockbildung / Orientierungserkennung / Schredder
Schlagwörter (EN)Reconstruction / combinatorial optimization / variable neighborhood search / block building / orientation detection / shredder
URNurn:nbn:at:at-ubtuw:1-38069 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Anwendung von kombinatorischen Optimierungsmethoden zur Rekonstruktion von in Streifen geschnittenen Papierdokumenten [3.13 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (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.

Zusammenfassung (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 different methods will be discussed to further improve the reconstruction process, like grouping strips into blocks that are already in their correct order.

Three different approaches are described and tested.

As benchmark instances ten documents each cut with four different 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.