Compression of static and dynamic three-dimensional meshes [Elektronische Ressource] / vorgelegt von Rachida Amjoun

Sujets

• Informatik

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2009
• Nombre de lectures: 26
• Langue: Deutsch
• Poids de l'ouvrage: 8 Mo

Extrait

Compression of Static and Dynamic
Three-Dimensional Meshes
Dissertation
der Fakultät für Informations- und Kognitionswissenschaften
der Eberhard-Karls-Universität Tübingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Rachida Amjoun
Tübingen
2009Tag der mündlichen Qualifikation: 21.07.2009
Dekan: Prof. Dr. Oliver Kohlbacher
1. Berichterstatter: Prof. Dr.-Ing. Dr.-Ing. E.h. Wolfgang Straßer
2. Berichterstatter: Prof. Dr. Andreas SchillingZusammenfassung
Mit den wachsenden Möglichkeiten von Modellierungssoftware und 3D Scannern ist
die Anzahl verfügbarer 3D Modelle stetig gewachsen. Animationen von 3D Modellen sind
weltweit verbreitet und bilden heute eine der größten Anwendungen digitaler Medientech-
nologie. Um einen hohen Realitätsgrad zu erreichen, werden komplexe und hochdetail-
lierte 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 Haupt-
ziel dieser Dissertation ist das Entwickeln neuer Verfahren für die Komprimierung sta-
tischer 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, traditio-
nelle 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 Kompo-
nenten. Neue Vorhersagetechniken werden eingeführt, welche das Normalenkodieren ver-
bessern.
Der dritte Teil behandelt Segmentierungen von sich zeitlich verändernder Meshgeo-
metrie. Drei neue Verfahren werden hier vorgestellt: Ein Region Growing Verfahren, ein
statisches Clustering und ein adaptives Clustering. Diese zerteilen die dynamischen Mes-
hes in quasi-rigide Bereiche unter Verwendung einer lokalen Charakteristik.
Der vierte Teil stellt Verfahren für sich zeitlich verändernde Meshgeometrie mit kon-
stanter 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 Mes-
hgeometrie. Er zeigt, dass die lokalen Koordinatensysteme ein größeres zeitliches und
räumliches Clustering-Verhalten aufweisen als das Weltkoordinatensystem. Die Kombi-ii
nation beider Clustering-Verfahren führt zu einer erheblichen Reduktion der Bitrate. Ver-
schiedene Prediktoren werden vorgestellt für tangentiale Komponenten und Normalen-
komponenten.
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 Ab-
bildung der originalen Koordinaten in ein lokales Koordinatensystem jede Region quasi-
invariant über die Zeit und damit sehr gut komprimierbar mit PCA macht. Um den Algo-
rithmus 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 im lokalen Koordinatensystem jedes 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 visu-
eller Qualität.
Abschließend diskutiert der fünfte Teil die Ergebnisse und stellt experimentelle Er-
gebnisse vor. Es wird gezeigt, dass die vorgestellten Verfahren den Vergleich mit anderen
aktuellen Arbeiten standhalten.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. An-
imation 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 se-
quences 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 encod-
ing 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 com-
pression 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 com-iv
bination 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 lo-
cal 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 Trans-
form 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 sig-
nificant 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.Acknowledgements
I would like to express my gratitude and sincere appreciation to my advisor Prof.
Wolfgang Straßer for his guidance, help and continuous support throughout the course of
my doctoral studies.
I also want to express my appreciation to Prof. Andreas Schilling for the valuable
support and the fruitful discussions.
I would like to thank Prof. Stefan Gumhold from university of Dresden, who directly
contributed to the work presented in the third chapter.
I would like to express my gratitude and thanks to PD. Dr. Douglas W. Cunningham
from Max Planck Institute of Tuebingen, and Dr. Ralf Sondershaus from Automotive
Lighting Reutlingen GmbH, for the proof-reading, valuable advice and helpful discus-
sions, and to Dr. Zein Salah from University of Magdeburg for useful discussions and
advice.
Sincere thanks are extended to GRIS’s office Manager Ms. Christ Constance who
provided help and assistance in numerous ways. Also, my thanks go to all my colleagues
at WSI/GRIS for the friendly environment and discussions that helped me complete the
present work.
Finally, I would like to thank my family and friends for their complete and unwave