An optimizational approach for an algorithmic reassembly of fragmented objects

by Anja Schäfer

Institution: Universität Heidelberg
Department: The Faculty of Mathematics and Computer Science
Degree: PhD
Year: 2015
Record ID: 1104013
Full text PDF: http://www.ub.uni-heidelberg.de/archiv/18008


In Cambodia close to the Thai border, lies the Angkor-style temple of Banteay Chhmar. Like all nearly forgotten temples in remote places, it crumbles under the ages. By today most of it is only a heap of stones. Manually reconstructing these temples is both complex and challenging: The conservation team is confronted with a pile of stones, the original position of which is generally unkown. This reassembly task resembles a large-scale 3D puzzle. Usually, it is resolved by a team of specialists who analyze each stone, using their experience and knowledge of Khmer culture. Possible solutions are tried and retried and the stones are placed in different locations until the correct one is found. The major drawbacks of this technique are: First, since the stones are moved continuously they are further damaged, second, there is a threat to the safety of the workers due to handling very heavy weights, and third because of the high complexity and labour-intensity of the work it takes several months up to several years to solve even a small part of the puzzle. These risks and conditions motivated the development of a virtual approach to reassemble the stones, as computer algorithms are theoretically capable of enumerating all potential solutions in less time, thereby drastically reducing the amount of work required for handling the stones. Furthermore the virtual approach has the potential to reduce the on-site costs of in-situ analysis. The basis for this virtual puzzle algorithm are high-resolution 3D models of more than one hundred stones. The stones can be viewed as polytopes with approximately cuboidal form although some of them contain additional indentations. Exploiting these and related geometric features and using a priori knowledge of the orientation of each stone speeds up the process of matching the stones. The aim of the current thesis is to solve this complex large-scale virtual 3D puzzle. In order to achieve this, a general workflow is developed which involves 1) to simplify the high-resolution models to their most characteristic features, 2) apply an advanced similarity analysis and 3) to match best combinations as well as 4) validate the results. The simplification step is necessary to be able to quickly match potential side-surfaces. It introduces the new concept of a minimal volume box (MVB) designed to closely and storage efficiently resemble Khmer stones.Additionally, this reduced edge-based model is used to segment the high-resolution data according to each side-surface. The second step presents a novel technique allowing to conduct a similarity analysis of virtual temple stones. It is based on several geometric distance functions which determine the relatedness of a potential match and is capable of sorting out unlikely ones. The third step employs graph theoretical methods to combine the similarity values into a correct solution of this large-scale 3D puzzle. The validation demonstrates the high quality and robustness of this newly constructed puzzle workflow. The workflow this thesis…