Title: Anwendung von kombinatorischen Optimierungsmethoden zur Rekonstruktion von in Streifen geschnittenen Papierdokumenten
Other Titles: Application of combinatorial optimization methods for the reconstruction of strip-shredded paper documents
Language: Deutsch
Authors: Winkler, Thomas 
Qualification level: Diploma
Advisor: Raidl, Günther
Assisting Advisor: Schauer, Christian 
Prandtstetter, Matthias  
Issue Date: 2011
Number of Pages: 97
Qualification level: Diploma
Abstract: 
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.

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.
Keywords: Rekonstruktion; kombinatorische Optimierung; Variable Nachbarschaftssuche; Blockbildung; Orientierungserkennung; Schredder
Reconstruction; combinatorial optimization; variable neighborhood search; block building; orientation detection; shredder
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-38069
http://hdl.handle.net/20.500.12708/9421
Library ID: AC07811095
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)

15
checked on May 3, 2021

Download(s)

61
checked on May 3, 2021

Google ScholarTM

Check


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