Efficient Compression Efficient Compression of 3D Dynamic Mesh of 3D Dynamic Mesh SequencesSequences

Sequences Sequences

Rachida Amjoun Rachida Amjoun

Prof. Wolfgang Strasser Prof. Wolfgang Strasser

University of Tuebingen University of Tuebingen

W W ilhelm ilhelm Schickard S chickard I Institute for Computer Science (WSI) nstitute for Computer Science (WSI)

GRaphical- GR aphical- Interactive I nteractive Systems (GRIS) S ystems (GRIS)

Introduction Introduction

7. Results

8. Conclusion & future work

Connectivity (constant)

Geometry (dynamic) Wh y c om pre ssi on ?? ?

Why Compression ? Why Compression ?

We need compact representations that : We need compact representations that :

facilitate their transmission over facilitate their transmission over networks

networks

reduce storage space reduce storage space

keep a good visual fidelity keep a good visual fidelity

7. Results

8. Conclusion & future work

[Lengyle]

[Lengyle]

1999 1999

[Alexa &

[Alexa &

Müller] Müller]

2000 2000

[Ibarria &

Rossignac]

2003

………...

2004 2005 2006 2007

No Standard Yet

No Standard Yet   !! !!

Hopefully come soon

Hopefully come soon  

Previous Work Previous Work

 Clustering based approaches: Clustering based approaches:

Split the mesh into rigid parts. encode the residuals

Split the mesh into rigid parts. encode the residuals [Lengyle 99] [Lengyle 99]

 Predictive techniques: Predictive techniques : Dynapack

Dynapack [Ibarria.Rossignac 2003] [Ibarria.Rossignac 2003]

 Wavelet based techniques Wavelet based techniques

Spatial multiresolution analysis

Spatial multiresolution analysis [Guscov. al. 2004] [Guscov. al. 2004]

 PCA based approaches : PCA based approaches : - Standard PCA

- Standard PCA [Alexa & al. 2000] [Alexa & al. 2000]

- PCA + LPC

- PCA + LPC [Karni & al. 2004] [Karni & al. 2004]

- Clustered PCA

- Clustered PCA [Sattler et al. 2005] [Sattler et al. 2005]

 ^{ } 















V

1 1 0

1

1 0 0

0

ˆ ˆ









 







 









R m m

R

V V

diag A

A

A A

Affine Transformations

P~₀t P~₁^t P~₂t

t

P~₃pred

1 0

~t

P

1 1

~t

P

1 2

~t

P

1 3

~t

P

aA bB

C

D C D

B

A

A a  B

b 

C c 

cC

A B

U 3Nf 

ff V

ff

N N N

z z y y x x







1 1 1





















f







1 1

V

=

 And much more: And much more:

[Zhang & Owen 04]. [Zhang & Owen 04]. [Müller & Smolic 05]………… [Müller & Smolic 05]…………

7. Results

8. Conclusion & future work

1. Neighboring vertices have strong tendency to move in a similar way

2 .

nonlinear behavior of the trajectories

World coordinates Local coordinates

tendency of the trajectories to cluster

99 100 101 102

…………

144

local region move rigidly local region move rigidly

local region quite invariant local region quite invariant

1. Clustering based on Motion in local coordinate frames(LCF) 2. Principal component analysis relative to LCF

3. Rate-Distortion Optimization

1. Clustering based on Motion in local coordinate frames(LCF) 2. Principal component analysis relative to LCF

3. Rate-Distortion Optimization

Segmentation

LCF residuals

computation Quantization Geometry data

Connectivity

Static compression

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder

Compression Algorithm Compression Algorithm

7. Results

8. Conclusion & future work

Segmentation

LCF residuals

computation Quantization Geometry data

Connectivity

Static compression

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder

Segmentation

LCF residuals

computation Quantization

Connectivity

Static compression

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Compression Algorithm Compression Algorithm

Geometry data

7. Results

8. Conclusion & future work

Segmentation

LCF residuals

computation Quantization

Connectivity

Static compression

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Geometry data

Segmentation

LCF residuals

computation Quantization Geometry data

Connectivity

Static compression

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Compression Algorithm Compression Algorithm

7. Results

8. Conclusion & future work

Segmentation

LCF residuals

computation Quantization Geometry data

Connectivity

Static compression

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Clustering Clustering

1. 1. Seed Selection Seed Selection

2. 2. Local coordinate frames construction Local coordinate frames construction 3. 3. Vertex clustering: Vertex clustering:

 

 

 F

f

f i k f q

i k k q

i 1

1 ,

, ,



  _{k i}

N

k min :  arg min 1 _ k _  _,

f k

q

Is the local coordinates of vertex i in cluster k in frame f

7. Results

8. Conclusion & future work

The total deviation of the vertex between each two adjacent frames in the LCF :

The vertex i should belong to the cluster k for which the deviation is very small:

Clustering Clustering

7. Results

8. Conclusion & future work

Clustering

LCF residuals

computation Quantization Geometry data

Connectivity

Static compression

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Compression Algorithm Compression Algorithm

Connectivity

Static compression

Clustering

7. Results

8. Conclusion & future work

V k D k U k

A k 

U k  A k k t k U

C   

 



 



 



 















U N U

U

C N C

C

..., 2 ,

1 ,

..., 2 ,

1 ,

• Projection:

N coefficient matrices N sets of basis vectors

• Decomposition : For each cluster we do:



LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Compression Algorithm Compression Algorithm

Connectivity

Static compression

Clustering

7. Results

8. Conclusion & future work

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Connectivity

Static compression

Clustering

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder

Compression Algorithm Compression Algorithm



Connectivity

Static compression

Clustering

7. Results

8. Conclusion & future work

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Connectivity

Static compression

Clustering

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder

Compression Algorithm Compression Algorithm



Connectivity

Static compression

Clustering

7. Results

8. Conclusion & future work

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Connectivity

Static compression

Clustering

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder

Algorithm Algorithm



Connectivity

Static compression

Clustering

7. Results

8. Conclusion & future work

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Connectivity

Static compression

Clustering

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Algorithm Algorithm

Connectivity

Static compression

Clustering

7. Results

8. Conclusion & future work

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Connectivity

Static compression

Clustering

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Algorithm Algorithm

Connectivity

Static compression

Clustering

7. Results

8. Conclusion & future work

LCF residuals

computation Quantization Geometry data

Stream PCA

. PCA

.... PCA

. Input:

M

. M

...M

WCS to LCS

Transformation Local coordinates

reconstruction

Output:

Connectivity

Decoder

LCS to WCS Transformation PCA details + residuals

Stream

Encoder



Connectivity

Static compression

Clustering

Can we do better ? Can we do better ?

Problem:

Using a fixed number of basis vectors for each cluster lead to:

Nbr of vertices Budget

or nbr of coeff.

Solution: find the best tradeoff between the bitrate and the distortion of coordinates of the vertices using R-D optimization.

 Overfitting: too many eigenvectors

 Underfitting: too few eigenvectors to recover the vertices at a desired accuracy

7. Results

8. Conclusion & future work

 L 

l  1 , 2 , ....,

 

 



 l

D k l R k ,

Optimization problem :

find the best number of components l ^k for each cluster k that minimize

rate-distortion point for each number of components



 ^N

k

l k

D

D subject to the

constraint D   _k ^N  ₁ R _k ^l

 R _target

incremental computation of the convex hull

Solution :

Results Results

7. Results

8. Conclusion & future work

Original Optimized C10. N10

Using LCF C10. N10

Using WCF

C10. N10

Results Results

Models # vertices #triangles

#frames CPCA

bpvf d_KG t_enc(sec) t_FPS(sec)

RLPCA

bpvf d_KG

N L

Chicken 3030 5664

400 4.7 0.0076 206

214

2.8 0.139 395 215

2.8 0.139 395 215

3.5 0.003 20 20 120 69

2.2 0.043 20 10 115 69

1.5 0.057 10 10 110 47

cow 2904 5804

204 7.4 0.16 75 145

3.8 0.5 59 218

2.0 1.47 55 284

6.8 0.123 30 20 82 46

4.1 0.470 30 20 40 50

2.2 1.220 10 10 70 23

cow 6172 12337

101 7.1 0.024 -- -- 4.1 0.033 -- -- 2.1 0.168 -- --

3.9 0.016 20 10 74 40

2.1 0.018 20 5 78 32

1.9 0.066 10 5 39 25

7. Results

8. Conclusion & future work

Simple clustering based on motion in LCF Simple clustering based on motion in LCF LPCA performed in LCS

LPCA performed in LCS R-D optimization

R-D optimization

Fast and efficient compression for animated 3D models Fast and efficient compression for animated 3D models

Compression schemes is applicable to meshes and point-based models Compression schemes is applicable to meshes and point-based models

In future work we want to: In future work we want to:

 automatize the selection of the number of clusters. automatize the selection of the number of clusters.

 develop adaptive clustering over time develop adaptive clustering over time

 encode the clusters with different numbers of quantization encode the clusters with different numbers of quantization

 compression of animated object with variable number of vertices compression of animated object with variable number of vertices