Compression of Static and Dynamic Three-Dimensional Meshes

Abstract

With the advancements and variety of sources to model 3D objects such as scanning technologies and modelling softwares, 3D models are becoming widely available. Animation also attracted worldwide attention and has become one of the most successful application of digital media technology. As a result, it is also becoming easier to acquire animated models. In order to achieve a higher degree of realism, more complex and highly detailed three-dimensional objects – possibly out of millions of vertices and polygons – are created with large sequences. When storing, downloading, or uploading these 3D sequences of objects in their standard forms over a network, large data rows consume large amounts of storage space and network bandwidth. This problem of storage and transmission has been widely studied for static meshes and wealth of successful compression schemes have been proposed. The main goal of this thesis is to develop new powerful compression techniques to reduce storage requirements and transmission times of static and dynamic 3D models represented by triangulated mesh and introduce new and efficient animation segmentation approaches that are very useful for different purposes, typically 3D dynamic mesh compression. This work covers five main parts. The first part presents definitions, traditional data compression techniques and reviews the existing techniques in the fields of static and dynamic mesh compression and segmentation. The second part introduces a new algorithm for static geometry data. Instead of encoding the three coordinates of a vertex, its tangential and normal components are encoded. New advanced prediction techniques are proposed to improve the normal encoding. The third part concerns segmentation of time varying mesh geometry. Three new approaches have been developed: A region growing based approach as well as static and adaptive clustering based methods. These break down the dynamic meshes into quasi rigid parts using local characteristic. The fourth part presents successive contributions to time varying mesh geometry compression where the connectivity remains constant over time. The first new algorithm is a single rate near-lossless compression for animated meshes. It generalizes the proposed static mesh geometry coding. It shows that the local spaces exhibit higher temporal and spatial clustering behavior than the world space, and the combination of both clusterings yield significant reduction in bit-rates. Different predictors are proposed for tangential and normal components. The second novel algorithm is a Relative Local Principal Component Analysis (RLPCA) based-compression. It combines the proposed clustering with LPCA, performed in the local space. We will show that simply mapping the original coordinates into local space makes each region quasi-invariant over time and well-compressible by using PCA. To further enhance this algorithm, a rate-distortion optimization is introduced. The third compression algorithm is based on Predictive and Discrete Cosine Transform coders (PDCT). After, clustering process, predictive coding is performed in the local space of each cluster resulting in very small delta vectors (prediction errors). The delta vectors are then transformed into the frequency domain using DCT. The resulting DCT coefficients are more compressible than the vector coordinates and the original sequence of meshes can be reconstructed from only a few non-zero DCT coefficients without significant loss in visual quality. Finally, the fifth part discusses and provides the experimental results. We will show that our methods are competitive when compared to the state-of-the-art techniques.

Mit den wachsenden Möglichkeiten von Modellierungssoftware und 3D Scannern ist die Anzahl verfügbarer 3DModelle stetig gewachsen. Animationen von 3DModellen sind weltweit verbreitet und bilden heute eine der größten Anwendungen digitalerMedientechnologie. Um einen hohen Realitätsgrad zu erreichen, werden komplexe und hochdetaillierte 3D Objekte verwendet - möglicherweise mit Millionen von Polygonen und Punkten - für lange Sequenzen. Die Ursprungsformate solch großer 3D Modelle benötigen viel Speicherplatz und Bandbreite. Das Problem des Speicherns und Übertragens ist gut untersucht für statische Meshes. Hierfür gibt es eine große Anzahl an erfolgreichen Kompressionsverfahren. Das Hauptziel dieser Dissertation ist das Entwickeln neuer Verfahren für die Komprimierung statischer und dynamischer 3D Modelle, welche durch Dreiecksnetze repräsentiert werden, und neuer Segmentierungsverfahren, welche notwendig für das effiziente Komprimieren animierter 3D Modelle sind. Die Arbeit gliedert sich in fünf Teile. Der erste Teil behandelt Definitionen, traditionelle Kompressionsverfahren und Vorarbeiten auf dem Gebiet der Kompression statischer und dynamischer Meshes sowie ihrer Segmentierung. Der zweite Teil stellt ein Verfahren für statische Geometrie vor. Es werden nicht die drei Koordinaten eines Punktes kodiert, sondern seine tangentiale und normale Komponenten. Neue Vorhersagetechniken werden eingeführt, welche das Normalenkodieren verbessern. Der dritte Teil behandelt Segmentierungen von sich zeitlich verändernder Meshgeometrie. Drei neue Verfahren werden hier vorgestellt: Ein Region Growing Verfahren, ein statisches Clustering und ein adaptives Clustering. Diese zerteilen die dynamischen Meshes in quasi-rigide Bereiche unter Verwendung einer lokalen Charakteristik. Der vierte Teil stellt Verfahren für sich zeitlich verändernde Meshgeometrie mit konstanter Konnektivität vor. Der erste Algorithmus ist eine fast verlustlose Single-Rate Kompression für animierte Meshes. Er verallgemeinert das vorgestellte Verfahren für die Kodierung statischer Meshgeometrie. Er zeigt, dass die lokalen Koordinatensysteme ein größeres zeitliches und räumliches Clustering-Verhalten aufweisen als das Weltkoordinatensystem. Die Kombination beider Clustering-Verfahren führt zu einer erheblichen Reduktion der Bitrate. Verschiedene Prediktoren werden vorgestellt für tangentiale Komponenten und Normalenkomponenten. Der zweite neue Algorithmus ist eine auf der Relative-Local-Principal-Component- Analysis (RLPCA) basierende Kompression. Er verbindet das vorgestellte Clustern mit LPCA, ausgeführt im lokalen Koordinatensystem. Es wird gezeigt, dass eine einfache Abbildung der originalen Koordinaten in ein lokales Koordinatensystem jede Region quasiinvariant über die Zeit und damit sehr gut komprimierbar mit PCA macht. Um den Algorithmus weiter zu verbessern, wird eine Rate-Distortion Optimierung eingeführt. Der dritte Kompressionsalgorithmus basiert auf prediktiven Codern und Discrete- Cosinus-Transform-Codern (PDCT). Nach dem Clustern wird ein prediktives Kodieren durchgeführt imlokalen Koordinatensystemjedes Clusters, welches zu sehr kleinen Delta-Vektoren führt (prediktive Fehler). Die Delta-Vektoren werden dann in den Frequenzraum transformiert mit DCT. Die resultierenden DCT Koeffizienten sind besser komprimierbar als die Vektorkoordinaten. Die originale Mesh-Sequenz kann rekonstruiert werden von nur wenigen DCT Koeffizienten, welche ungleich Null sind, ohne großen Verlust an visueller Qualität. Abschließend diskutiert der fünfte Teil die Ergebnisse und stellt experimentelle Ergebnisse vor. Es wird gezeigt, dass die vorgestellten Verfahren den Vergleich mit anderen aktuellen Arbeiten standhalten.