Gene Cheung
National Institute of Informatics
6th July, 2015

Depth Image Coding & Processing
Part 2: Depth Image Coding.
COST Training School 7/06/2015

1

Outline• Depth Image Coding• Graph Fourier Transform• Multi-resolution Graph Fourier Transform• Generalized Graph Fourier Transform• Graph based Representation (GBR)

COST Training School 7/06/2015

2

Outline• Depth Image Coding• Graph Fourier Transform• Multi-resolution Graph Fourier Transform• Generalized Graph Fourier Transform• Graph based Representation (GBR)

COST Training School 7/06/2015

3

Graph Fourier Transform (GFT)
for Graph-signals
Graph Fourier Transform:• Signal-adaptive transform:
1. If two connected pixels are “similar”, thenedge weight is large → adjacency matrix A.
2. Compute graph Laplacian L = D-A.
3. Perform eigen-decomposition on L for GFT.

x   ai ii• Intuition: Embed geometric structure ofsignal as edge weights in graph.
COST Training School 7/06/2015

4Depth Map Compression• DCT are fixed basis. Can we do better?

• Idea: use adaptive GFT to improve sparsity [1].
1.

Assign edge weight 1 to adjacent pixel pairs.

2.

Assign edge weight 0 to sharp depth discontinuity.

3.

Compute GFT for transform coding, transmit coeff.

α  x4.

GFTTransmit bits (contour) to identify chosen GFT todecoder (overhead of GFT).

[1] G. Shen et al., “Edge-adaptive Transforms for Efficient Depth Map Coding,”
IEEE Picture Coding Symposium, Nagoya, Japan, December 2010.
[2] M. Maitre et al., “Depth and depth-color Coding using Shape-adaptive Wavelets,”
Journal of Visual Communication and Image Representation, vol.21, July 2010, pp.513-522.

Shape-adaptive wavelets
can also be done.
5Depth Map Compression
Q: Why GFT leads to sparseness?
Ans 1: Capture statistical structure of signal in edge
weights of graph.
• Adjacent pixel correlation 0 or 1 for piecewise smooth (PWS)signal.
• Can be shown GFT approximates KLT given Gaussian Random
Markov Field (GRMF) model.

Ans 2: Avoid filtering across sharp edges.
GFTDCTfiltering
operationα  x

a 4x4 block[3] C. Zhang and D. Florencio, “Analyzing the optimality of predictive transform coding using graph-based models,” IEEE Signal
Processing Letters, vol. 20, NO. 1, January 2013, pp. 106–109.

6

Graph Fourier Transform (GFT)
for Image Coding• Block-based Transform coding of images*

Two things to transmit for adaptive transforms:- transform coefficients

 the cost of transform representation- adaptive transform itself  the cost of transform description• What’s a good transform?
- minimize the cost of transform representation & the cost of transform description
7[4] V. Goyal, “Theoretical foundations of transform coding,” in IEEE Signal Processing Magazine, vol. 18, no.5, September 2001, pp. 9–21.

Transform Comparison

Transform Representation

Transform Description

Karhunen-Loeve
Transform (KLT)“Sparsest” signal representation given
available data / statistical modelCan be expensive (ifunstructured)

Discrete Cosine
Transform (DCT)

non-sparse signal representation
across sharp boundaries

little (fixed transform)

Graph Fourier
Transform (GFT)

minimizes the total rate of signal’s transform representation &transform description

COST Training School 7/06/2015

8

GFT Comparison
HR-UGFT [1]

MR-GFT

unweighted graphs

unweighted & weighted graphs

no notion of optimality

define an optimality criterion

graphs are directly drawn from detectedboundaries

propose efficient algorithms to search forthe optimal GFT

Requires real-time eigen-decomposition

3 techniques to reduce computation
complexity (multi-resolution, graphisomorphism, table lookup)[1] G. Shen et al., “Edge-adaptive Transforms for Efficient Depth Map Coding,”
IEEE Picture Coding Symposium, Nagoya, Japan, December 2010.

9

Search for Optimal GFT• Rate-distortion performance:• Assumption: high bit rate, uniform quantization
Distortion does not change when considering different transforms! [5]Consider Rate only!

• For a given image block

under fixed uniform quantization at high rate,

the optimal GFT is the one that minimizes the total rate:

Rate of transform coefficient vector

Rate of transform description T

COST Training School 7/06/2015[5] Gray and Neuhoff, “Quantization,” IEEE Transactions on Information Theory, vol. 44, no. 6, Oct. 1998.

10

MR-GFT: Definition of the Search Space forGraph Fourier Transforms••

In general, weights could be any number in [0,1]To limit the description cost
•Restrict weights to a small discrete set

3500

3000

- "1": strong correlation in smooth regions- "0": zero correlation in sharp boundaries- "c": weak correlation in slowly-varying parts

2500

2000

1500

1000

500

110051015202530

35

40

114550MR-GFT: Definition of the Search Space forGraph Fourier Transforms• For ease of computation, divide the optimization into two sub-problems
1. Weighted GFT (WGFT):
2. Unweighted GFT (UGFT):
Strong correlation only? Default to the DCT♦ What is the optimal c?
COST Training School 7/06/2015

12

MR-GFT: Derivation of Optimal Edge Weights for
Weak Correlation•Assume a 1D first-order autoregressive (AR) process

where,smoothjumpnon-zero mean random var.
•Assuming the only weak correlation exists between

k-th

COST Training School 7/06/2015

and13

MR-GFT: Derivation of Optimal
Edge Weights for Weak Correlation (cont’d)• Covariance matrix
k-th

 0   
 e  0
 2     b    ek   g        eN   0 

 21

0

0T

E bb 00
 0 0

0

1

0

0 10



0 00 0 g2  mg2  1 0 010 0COST Training School 7/06/2015

00



0
0

0
0
0

1

k-th row

14

MR-GFT: Derivation of Optimal
Edge Weights for Weak Correlation (cont’d)•Precision matrix (tri-diagonal)
Graph Laplacian matrix!

(k-1)-th row
k-th row1•the KLT basis =of the covariance matrix =1

1of the precision matrixof the Laplacian matrix

15

MR-GFT: Adaptive Selection of Graph FourierTransforms• Two sub-problems with two corresponding non-overlapping search spaces
1. Weighted GFT (WGFT):(weighted & connected graphs)

2. Unweighted GFT (UGFT):(unweighted & disconnected graphs)

COST Training School 7/06/2015

16

WGFT
•

Cost function of transform coefficients
2Rˆ x, W   x T Lx  Wi,j xi  x j    k k2

i , j 

GFT coeff

kgraph freq.

•Cost function of transform description

costly if many weight changes•

code only non-1’s

Problem formulation for WGFT

orig graph•dual graph

Separation-Deviation (SD) problem, solvable in polynomial time [6].

[6] D. S. Hochbaum, “An Efficient and Effective Tool for Image Segmentation, Total Variations and Regularization,” SSVM’11
Proceedings of the Third International Conference on Scale Space and Variational Methods in Computer Vision, 2011, pp.338-349.

17

UGFT

• A greedy algorithm• Divide graph into disconnected sub-graphs via spectral clustering [7].
• Check objective function, further sub-divide if cost decreases.

[7] J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 22, no. 8, August 2000.

18

MR-GFT: Adaptive Selection of Graph FourierTransforms•

Online eigen-decomposition: a hurdle to practical implementation•Pre-compute and store GFTs in a table for simple lookups- Perform GFT on a small block- Store the most frequently used GFTs
- Exploit graph isomorphism•Graph isomorphism

19

MR-GFT: Adaptive Selection of Graph Fourier
Transforms

COST Training School 7/06/201520

Experimentation•Setup- Test images: depth maps of Teddy and Cones, and graphics images of Dude and Tsukuba.
- Compare against: HR-DCT, HR-SGFT, SAW, MR-SGFT•Results

HR-DCT:
HR-SGFT:SAW:
MR-SGFT:COST Training School 7/06/2015

6.8dB
5.9dB
2.5dB
1.2dB

21

Subjective Results

HR-DCT

HR-SGFTCOST Training School 7/06/2015

MR-GFT

22

Mode Selection

red: WGFT
blue: UGFTCOST Training School 7/06/2015

23

Summary for Multi-resolution Graph FourierTransform•

A multi-resolution (MR) graph Fourier transform (GFT) coding scheme for compression ofpiecewise smooth images.

•Minimize transform representation cost + transform description cost given weight {0, 1, c}.

•Solve for optimal c, show optimality of GFT.

•WGFT {1, c}: formulate a separation-deviation (SD) problem.

•

UGFT {1, 0}: greedy algorithm via spectral clustering.

•

Practical implementation via multi-resolution, graph isomorphism and lookup tables.

•Excellent experimental results!

COST Training School 7/06/2015

24

Edge Coding for PWS
Image Compression• Arithmetic Edge Coding [8]:• Coding of sequence of between-pixel edges, orchain code with symbols {L, S, R}.
• Design a context to compute symbol probabilities forarithmetic coding.
• Extension: better context based purely on symbol
statistics analysis.

• Contour Approximation & Depth Image Coding [9]:orig

Λ=800

Λ=3000• Approximate contour while maintaining edge sharpness.

• Edge-adaptive blocked-based image coding (GFT).
• Average 1.68dB over GFT coding original contours at lowbitrate regions.
[8] I. Daribo, G. Cheung, D. Florencio, “Arbitrarily Shaped Sub-block Motion Prediction in Depth VideoCompression using Arithmetic Edge Coding," IEEE Trans on Image Processing, Nov 2014.
[9] Y. Yuan G Cheung, P. Frossard, P. Le Callet, V. Zhao, “Contour Approximation & Depth Image Codingfor Virtual View Synthesis,” submitted to IEEE MMSP, October, 2015.

25

Outline• Depth Image Coding• Graph Fourier Transform• Multi-resolution Graph Fourier Transform• Generalized Graph Fourier Transform• Graph based Representation (GBR)

COST Training School 7/06/2015

26

Motivation• Intra-prediction

𝑥0 𝑥1 𝑥2 𝑥3 𝑥4
Boundary pixel(predictor)

Predicted pixels 𝑥𝑖: prediction residuals• Discontinuities at block boundaries

Intra-prediction in H.264- intra-prediction will not be chosen or bad prediction[10] W. Hu et al., “Intra-Prediction and Generalized Graph Fourier Transform for Image Coding,” accepted toIEEE Signal Processing Letters, June, 2015.

27

Contributions• Clustered-based intra-prediction- cluster discontinuities at block boundaries-: shift by cluster mean 𝜇 (side information)• Generalized Graph Fourier Transform (GGFT)- optimized for intra-prediction residuals- generalized graph Laplacian: extra weight added at block boundaries- default to the DCT and ADST in some cases

COST Training School 7/06/2015

28

Related Work• Zhang et al, graph-based predictive transform coding, GMRF [3]• Assume given model. No discussion on how to derive model parameters.

• Wang et al, intra predictive graph transform coding [11]• Intra-prediction plus KLT, optional graph sparsification.

• Ye et al, MDDT [12]• Completely data-driven resulting in unstructured transform.
[3] C. Zhang and D. Florencio, “Analyzing the optimality of predictive transform coding using graph-based models,” in IEEE Signal
Processing Letters, vol. 20, NO. 1, January 2013, pp. 106–109.
[11] Y. Wang, A. Ortega, and G. Cheung, “Intra predictive transform coding based on predictive graph transform,” ICIP, September
2013.
[12] Y. Ye and M. Karczewicz, “Improved H.264 intra coding based on bidirectional intra prediction, directional transform, andadaptive coefficient scanning,” ICIP, October 2008.

COST Training School 7/06/2015

29

1D Signal Modeling- Inter-pixel differences are concentrated around 0, occasionally large.
- Quantize inter-pixel differences into K bins, leveraging on Lloyd algorithm

bin averageapproximation error
COST Training School 7/06/2015

30

Optimal 1D Intra prediction

Class kClass l• Optimal in terms of resulting in a zeromean prediction residual• Default to conventional intra-prediction
when, i.e.,

COST Training School 7/06/2015

31

Generalized Graph Fourier Transform• The precision matrix of the prediction residual(inaccuracy of intra-prediction)(discontinuities within signal)
Variance of approximation error

COST Training School 7/06/2015

32

Generalized Graph Fourier Transform• The precision matrix of the prediction residual

Generalized Laplacian+=Combinatorial Laplacian

Degree matrix for boundary vertices

COST Training School 7/06/2015

33

Generalized Graph Fourier Transform• The precision matrix of the prediction residual• Default to the DCT if• Default to the ADST [13] ifandand[13] J. Han et al., “Jointly Optimized Spatial Prediction and Block Transform for video and Image Coding,”
IEEE Transactions on Image Processing, vol.21, no.4, April 2012, pp.1874-1884.

34

Proposed Coding System• Four clusters:- Strong correlation:- Weak correlations:- Zero correlation

Verticalpredictor• Side information:- contours: arithmetic edge coding- cluster indicator: arithmetic coding• 2D prediction and transform

Horizontal predictor
COST Training School 7/06/2015

35

Experimental Results•

Test images: PWS images and natural images•

Compare proposed intra-prediction (pIntra) + GGFT against:- edge-aware intra-prediction (eIntra) + DCT- eIntra + ADST
- eIntra + GFT

COST Training School 7/06/2015

36

Experimental Results

COST Training School 7/06/2015

37

Subjective Quality

eIntra + DCT

eIntra + GFT

COST Training School 7/06/2015

pIntra + GGFT

38

Outline• Depth Image Coding• Graph Fourier Transform• Multi-resolution Graph Fourier Transform• Generalized Graph Fourier Transform• Graph based Representation (GBR)

COST Training School 7/06/2015

39

Motivations• All depth-based representation methods for multiview images
share the following drawback:• Observation: consequences of lossy depth compression are notwell controlled.
• Analogy: Motion vectors (MV) can be coarse (e.g., 16x16), but
is always losslessly coded.
COST Training School 7/06/2015*Slides courtesy of T. Maugey of INRIA.

40

Intuitions• (a) – appearing pixels• (b) – disoccluded pixels• (c) – occluded pixels• (d) – disappearing pixels• Replace depth by connections between pixels, for geometry
representation• Build a lossy representation followed by a lossless coding instead of
directly lossy coding the depth

T. Maugey et al., “Graph-Based Representation for Multiview Image Geometry,” IEEE Transactions on Image
Processing, vol.24, no.5, Feb, 2015.

41

Graph construction rules

Concatenated rows
Background disparity

level index

Foreground disparity

54

foreground object

Graph construction

background32
1
1

17 18 19column index c of row r

row r
Graph Representationlevel 1level 2level 3

image 1

image 2

image 3clevel 4level 5

image 4

image 5level index
5a4

b3
c2

d1
123

4

5

6

78910 11 12 13 14 15 16 17 18 19column index c of row r

View reconstructionlevel index
5Reconstructionof level 243123456789 10 11 12 13 14 15 16 17 18 192112534678910 11 12 13 14 15 16 17 18 19column index c of row r

column index c of row r
COST Training School 7/06/2015- 42

Graph coding
Lossless

Color component
Geometry component
GBR construction

Connection values
Extract appearing
Connection positions
connections

diff +
arithm coder
JBIG2 coder
diff +
arithm coder

N ColorExtract disocclusion Connection values
connections
Connection positions
merge

N Depthmerging vector

pred +
arithm coder
diff +arithm coder

Extract occlusion
connections

COST Training School 7/06/2015

Connection values

JBIG2 coder- 43

Compression results- 44Naturally keeping the scene structure
orig

EAW

GBR

- 45

Summary• Depth Image Coding• Graph Fourier Transform• Multi-resolution Graph Fourier Transform• Generalized Graph Fourier Transform• Graph based Representation (GBR)

COST Training School 7/06/2015

46