Reconstructing borders of manually torn paper sheets using integer linear programming

Abstract

Diese Diplomarbeit behandelt die Zerstörung von Papierdokumenten durch manuelles Zerreißen und evaluiert zwei Verfahren zur Rekonstruktion solcher Dokumente basierend auf Methoden der ganzzahligen linearen Programmierung (ILP). Die vorgestellten Verfahren operieren ausschließlich auf der Form der Schnipsel und rekonstruieren die Ränder der zerstörten Dokumente. Für die Evaluierung wurde ein Modell für manuelles Zerreißen und eine C++ Bibliothek mit einem XML Datenformat entwickelt. Die Simulation des Zerreißprozesses berücksichtigt auch Schereffekte, die Papier beim Reißen - im Gegensatz zum Schneiden - plastisch so verformen, dass die Umrisse benachbarte Stücke nicht mehr exakt zusammenpassen.<br />Die ILP Formulierungen wurden durch umfangreiche empirische Tests mit der CPLEX Software untersucht. Die Performanz und Ergebnisqualität von mehreren Zielfunktionen wurde verglichen, insbesondere solcher die von der CPLEX-spezifischen IloAbs-Absolutwertsberechnung Gebrauch machen und solcher die dies nicht tun. Weiters wurde der sehr performancekritische MIPEmphasis Parameter und das Lazy Constraint Feature von CPLEX evaluiert. Die entwickelte Bibliothek und die Programmwerkzeuge haben sich in den Tests bewährt und eignen sich für weiterführende Untersuchungen innerhalb dieser Domäne.<br />Die ILP Formulierungen zeigen gute Performanz und gute Ergebnissgenauigkeit für Instanzen bestehend aus einer Papierseite und eignen sich deshalb für die Verwendung in Hybridalgorithmen.<br />

This thesis discusses the destruction of sheets of paper by manual tearing and evaluates two approaches for reconstruction of such pages by exact methods based on Integer Linear Programming. These methods operate solely on the shape of torn pieces of paper and reconstruct the borders of the paper sheets. For evaluation and tests within this problem domain, a tearing model of human paper tearing as well as a C++ library and an XML data interchange format were developed. The tearing simulation takes into regard shear effects which distort paper in a way that - opposed to cutting - the shapes of adjacent pieces will not prefectly fit together anymore. The ILP formulations were evaluated with extensive empirical tests using the CPLEX solver software. The performance and accuracy of several objective functions was compared, in particular functions using the CPLEX specific IloAbs absolute value calculation feature and formulations not using this feature. Further evaluation was performed on the very performance-relevant CPLEX parameters MIPEmphasis and on the CPLEX specific lazy constraints.<br />The developed library and tools were very useful for the evaluation in this problem domain and can be reused for further studies. The ILP models are fast and yield good accuracy results on single page instance sizes which makes them well suitable for usage in hybrid algorithms.