Ein hybrides Verfahren zur automatischen Rekonstruktion von handzerrissenen Dokumentenseiten mittels geometrischer Informationen

Abstract

Diese Diplomarbeit ist dem großen Gebiet der Rekonstruktion von zerstörten Papierdokumenten zuzuordnen. Ziel dieser Arbeit ist die Zuweisung verschiedener durch manuelles Zerreißen erzeugter Schnipsel auf einzelne Seiten, sodass im Weiteren eine vollständige Rekonstruktion der originalen Dokumente vorgenommen werden kann. Alle in dieser Arbeit entwickelten Ansätze basieren auf der Idee als zusätzliche, sozusagen komplementäre Methoden zu Ansätzen aus dem Bereich der Bildverarbeitung zu fungieren. In dieser Arbeit werden drei Ansätze genauer betrachtet:<br />Eine Lokale Suche soll im Wesentlichen in möglichst kurzer Zeit mit Hilfe einfacher Strategien gute Lösungen liefern. Weiters wird basierend auf dieser lokalen Suche ein Variable Neighborhood Descent (VND) Ansatz definiert, bei dem nicht im klassischen Sinn Nachbarschaften sondern die Schrittfunktionen systematisch ausgetauscht werden. Letztlich wird noch eine hybride Methode vorgestellt, die eine lokale Suche mit einem exakten Verfahren basierend auf ganzzahliger linearer Programmierung kombiniert. Dabei wird versucht die Abweichung von " optimalen" Seiten nach der Rekonstruktion anhand unterschiedlicher Merkmale zu messen und möglichst zu minimieren. Alle drei Ansätze werden durch die Anwendung einer für die Problemstellung entwickelten Datenstruktur effizient implementiert. Anhand ausführlicher Testergebnisse wird die Qualität der in dieser Arbeit vorgestellten Methoden miteinander verglichen und im Weiteren detailliert diskutiert. Zusammenfasssend kann gesagt werden, dass die Kombination von VND zum Berechnen von Ausgangslösungen mit der hybriden Methoden zum Verfeinern dieser Startlösung angewandt auf Seiten mit jeweils zwei Rissen (entspricht vier Schnipseln) am erfolgversprechendsten ist. Erwartungsgemäß nimmt die Lösungsqualität mit zunehmender Schnipselzahl pro Seite und zunehmender Seitenanzahl ab.<br />

This thesis focuses on the field of the reconstruction of manually destroyed paper documents. The goal of this work is the assignment of different manually destroyed snippets to single pages in such a way, that afterwards a complete reconstruction of the original documents can be carried out. All approaches developed in this thesis are based on the idea that they act as a complementary approach on the field of image processing. In this thesis three approaches are examined:<br />A \Local Search should essentially yield good solutions in the shortest possible time with the help of simple strategies. Furthermore, based on the local search, a Variable Neighborhood Descent (VND) approach is defined which does not interchange neighborhoods in the common sense.<br />Instead a systematic exchange of different step functions is performed.<br />Finally, a hybrid method is presented, which combines local search with an exact algorithm based on integer linear programming. Thereby it is attempted to measure the deviation from "optimal" pages after the reconstruction by means of different features and minimize this deviation as much as possible. All three approaches are implemented efficiently by using a data structure which has been developed for the problem. Based on detailed test results the quality of the presented methods are checked against each other and discussed in detail. To sum it up, it can be concluded that the combination of VND for the calculation of a start solution and the hybrid method to improve this solution applied on pages which are shredded twice (equates four snippets) are most promising. As expected, the quality of the solutions decreases with increasing number of snippets per page and increasing number of pages.