Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

An optimizational approach for an algorithmic reassembly of fragmented objects

Schäfer, Anja

[img]
Preview
PDF, English - main document
Download (66MB) | Terms of use

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the DOI, URN or the persistent URL below, as we can guarantee their long-time accessibility.

Abstract

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 presents virtually puzzles digitized stones of fallen straight Khmer temple walls. It is able to virtually and correctly reasemble up to 42 digitized stones requiring a minimum of user-interaction.

Translation of abstract (German)

In Kambodscha nahe der thailändischen Grenze befindet sich die Tempelanlage von Banteay Chhmar, erbaut im Stile des besser bekannten Angkor Wat. Wie die meisten fast vergessenen Tempel zerfällt sie zusehends und ist heutzutage kaum mehr als ein großer Haufen Steine. Ein Wiederaufbau dieser zerfallenen Strukturen von Hand ist sehr komplex und fordernd: Ein Team aus Konservatoren und Archäologen steht vor einem Trümmerhaufen, bei dem die ursprüngliche Position der einzelnen Teile meist unbekannt ist. Generell wird diese Art von überdimensioniertem Puzzle gelöst, indem ein Team von Spezialisten jeden einzelnen Stein mit Hilfe von Erfahrung und Wissen über die Kultur der Khmer analysiert. Mögliche Lösungen werden solange ausprobiert, bis die richtige Zusammensetzung der Steine gefunden wurde. Die größten Nachteile dieser Methode bestehen darin, dass die Steine bei jeder Bewegung weiter besch ̈adigt werden und die Sicherheit der Arbeiter durch das Hantieren mit schweren Gewichten gefährdet ist. Darüber hinaus dauert diese Art des Wiederaufbaus aufgrund ihrer hohen Komplexit ̈at und Arbeitsintensität mehrere Monate oder Jahre.

Diese Bedingungen motivierten die Entwicklung eines virtuellen Ansatzes, um den Wiederaufbau zu unterstützen, da computerbasierte Algorithmen das Potential haben, die Lösung schneller zu finden und gleichzeitig den notwendigen Arbeitsaufwand reduzieren können. Desweiteren können die Kosten vor Ort gesenkt werden. Die Basis dieses virtuellen Puzzles sind hochaufl ̈osende 3D Modelle von mehr als hundert Steinen. Diese Steine können als annähernd quaderförmige Polyeder aufgefasst werden, häufig mit einer zusätzlichen Einkerbung versehen. Das Ausnutzen dieser Eigenschaft in Kombination mit Vorwissen über die Orientierung eines jeden Steins führt zu einem schnelleren Arbeitsablauf beim Zusammenfügen der Steine.

Das Ziel der vorliegenden Arbeit ist es dieses virtuelle 3D Puzzle zu lösen. Die zugrunde liegende Idee dabei ist 1) die hochauflösenden Modelle auf ihre charakteristischsten Eigenschaften zu vereinfachen, 2) eine ausgeklügelte Ähnlichkeitsanalyse anzuwenden und 3) die besten Kombinationen zusammenzusetzen sowie 4) die Ergebnisse zu validieren.

Der Vereinfachungsschritt ist notwendig, um mögliche Lösungen schnell zu testen und zusammenzusetzen. Hierbei kommt eine neue Art der Repräsentation von Khmer Tempelsteinen zum Einsatz, die minimale Volumen Box (MVB). Sie wurde entwickelt, um die Steine speichereffizient und trotzdem genau wiederzugeben und um die hochauflösenden Daten entsprechend der Seitenflächen zu segmentieren. Im zweiten Schritt wird eine neue Technik vorgestellt, die es ermöglicht, eine Ähnlichkeitsanalyse der Steine durchzuführen. Sie basiert auf verschiedenen geometrischen Abstandsmaßen, die Aussagen über die Zusammengehörigkeit eines möglichen Paares treffen. Die besondere Stärke dieser Analyse ist, dass unpassende Kombinationen aussortiert werden. Im dritten Schritt wird mit Hilfe von graphentheoretischen Methoden die korrekte Lösung des Puzzles gefunden. Abschließend wird die hohe Qualität und Stabilität dieses neuartigen Khmer 3D Puzzles präsentiert.

Der Arbeitsablauf, den diese Arbeit präsentiert, ist in der Lage, digitalisierte Steine von zerfallenen geraden Mauern von Khmer Tempeln zu puzzlen. Es ist nun möglich, bis zu 42 virtuelle Steine mit einem Minimum an Benutzeraufwand wieder zusammenzusetzen.

Item Type: Dissertation
Supervisor: Bock, Prof. Dr. Hans Georg
Date of thesis defense: 12 January 2015
Date Deposited: 21 Jan 2015 10:03
Date: 2015
Faculties / Institutes: Service facilities > Interdisciplinary Center for Scientific Computing
Subjects: 004 Data processing Computer science
510 Mathematics
Controlled Keywords: Optimierung, Kombinatorik, 3D Puzzle, Algorithmische Geometrie, Khmer, Tempel
About | FAQ | Contact | Imprint |
OA-LogoDINI certificate 2013Logo der Open-Archives-Initiative