<div class="csl-bib-body">
<div class="csl-entry">Schüller, P. (2008). <i>Reconstructing borders of manually torn paper sheets using integer linear programming</i> [Master Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-15999</div>
</div>
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 />
de
dc.description.abstract
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.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Papier
de
dc.subject
zerreißen
de
dc.subject
Rekonstruktion
de
dc.subject
ILP
de
dc.subject
Lineare Programmierung
de
dc.subject
Ganzzahlig Lineare Programmierung
de
dc.subject
rekonstruieren
de
dc.subject
Puzzle
de
dc.subject
Dokumente
de
dc.subject
Papierdokumente
de
dc.subject
torn
en
dc.subject
paper
en
dc.subject
reconstruction
en
dc.subject
reconstruct
en
dc.subject
ILP
en
dc.subject
Integer Linear Programming
en
dc.subject
puzzle
en
dc.subject
paper dokuments
en
dc.subject
documents
en
dc.title
Reconstructing borders of manually torn paper sheets using integer linear programming
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Peter Schüller
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Prandtstetter, Matthias
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC05036527
-
dc.description.numberOfPages
83
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-15999
-
dc.thesistype
Masterarbeit
de
dc.thesistype
Master Thesis
en
tuw.author.orcid
0000-0002-1837-126X
-
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.assistant.staffStatus
external
-
tuw.advisor.orcid
0000-0002-3293-177X
-
item.languageiso639-1
en
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.fulltext
with Fulltext
-
item.openairetype
master thesis
-
item.grantfulltext
open
-
item.openaccessfulltext
Open Access
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E192-03 - Forschungsbereich Knowledge Based Systems