Title: | Reconstructing borders of manually torn paper sheets using integer linear programming | Language: | English | Authors: | Schüller, Peter | Qualification level: | Diploma | Keywords: | Papier; zerreißen; Rekonstruktion; ILP; Lineare Programmierung; Ganzzahlig Lineare Programmierung; rekonstruieren; Puzzle; Dokumente; Papierdokumente torn; paper; reconstruction; reconstruct; ILP; Integer Linear Programming; puzzle; paper dokuments; documents |
Advisor: | Raidl, Günther | Assisting Advisor: | Prandtstetter, Matthias | Issue Date: | 2008 | Number of Pages: | 83 | Qualification level: | Diploma | 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. 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. 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. 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. 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. |
URI: | https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-15999 http://hdl.handle.net/20.500.12708/10902 |
Library ID: | AC05036527 | Organisation: | E186 - Institut für Computergraphik und Algorithmen | Publication Type: | Thesis Hochschulschrift |
Appears in Collections: | Thesis |
Files in this item:
File | Description | Size | Format | |
---|---|---|---|---|
Reconstructing borders of manually torn paper sheets using integer linear programming.pdf | 840.84 kB | Adobe PDF | ![]() View/Open |
Page view(s)
20
checked on Feb 19, 2021
Download(s)
66
checked on Feb 19, 2021

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