Anwendung von kombinatorischen Optimierungsmethoden zur Rekonstruktion von in Streifen geschnittenen Papierdokumenten

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 />

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.