Gene Cheung
National Institute of Informatics
21st May, 2015

Graph-based Depth Image
Processing.
DJI visit 05/2015

1

NII Overview• National Institute of Informatics• Chiyoda-ku, Tokyo, Japan.
• Government-funded research lab.

• Offers graduate courses & degrees
through The Graduate University for
Advanced Studies.
• 60+ faculty in “informatics”:
quantum computing, discretealgorithms, database, machinelearning, computer vision, speech &audio, image & video processing.

• Get involved!
• 2-6 month Internships.
• Short-term visits via
MOU grant.
• Lecture series,Sabbatical.
2Outline• Traditional vs. Graph Signal Processing• Graph Fourier Transform (GFT)• Depth Map Compression• Depth Map Denoising• Depth Map Interpolation

DJI visit 05/2015

3

Traditional Signal Processingx(t)• Traditional discrete signals live on regular
data kernels (unstructured).

t• Ex.1: audio / music / speech on regularly
sampled timeline.
• Ex.2: image on 2D grid.
• Ex.3: video on 3D grid.

• Wealth of SP tools (transforms, wavelets,dictionaries, etc) for tasks such as:• compression, denoising, classification.

DJI visit 05/2015

4Graph Signal Processing

nodeedge• Signals live on graph.
• Graph is sets of nodes and edges.
• Edges reveals node-to-node relationships.

• Data kernel itself is structured.
1. Data domain is naturally a graph.
• Ex.1: posts on social networks.
• Ex.2: temperatures on sensor networks.

2. Embed signal structure in graph.
•Ex.1: images: 2D grid → structured graph.

Graph Signal Processing (GSP) addresses the problem ofprocessing signals that live on graphs.
5Graph Signal Processing
Research questions:• Sampling: how to efficiently acquire /sense a graph-signal?

nodeedge• Graph sampling theorems.

• Representation: Given graph signal, how
to compactly represent it?
• Transforms, wavelets, dictionaries.

• Signal restoration: Given noisy and/or
partial graph-signal, how to recover it?
• Graph-signal priors.

DJI visit 05/2015

6Outline• Traditional vs. Graph Signal Processing• Graph Fourier Transform (GFT)• Depth Map Compression• Depth Map Denoising• Depth Map Interpolation

DJI visit 05/2015

7

Transforms for Signals• Transform: Set of orthogonal basis.
• Notion of frequency.

• Ex.1: DCT: 1 X k   xn cos  n  k 2 n 0N
N 1

2D DCT basis is set of outer-product of
1D DCT basis in x- and y-dimension.

a xdesired signaltransform

transform coeff.

x  a11  a22  x   aiii
DJI visit 05/2015

Typical pixel blocks havealmost no high frequency
components.
8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.
DJI visit 05/2015

9

1

1

1

Facts of Graph Laplacian & GFT• L is a high-pass filter.

0 1 1 0
 1 2  1 0 L 0  1 2  1
0 1 1 0• x T Lx is one measure of variation in signal.
x T Lx 122wx
x
i, jiji
2 i, ji

L for 4-node unweighted line graph• L is positive semi-definite; eigenvalues λ’s ≥ 0 →eigenvalues are graph frequencies.
• L = D – A; λ = 0 must be eigenvalue w/ vector [1 … 1]T.
• Use eigenvectors for spectral decomposition of signal.
1
1

1• GFT defaults to DCT for un-weighted connected line.

1• GFT defaults to DFT for un-weighted connected circle.

1

Usage Example: first non-zero eigenvalue → spectral clustering (Shi& Malik’00).

DJI visit 05/201510Outline• Traditional vs. Graph Signal Processing• Graph Fourier Transform (GFT)• Depth Map Compression• Depth Map Denoising• Depth Map Interpolation

DJI visit 05/201511

Depth Map Compression• DCT are fixed basis. Can we do better?
• Idea: use adaptive GFT to improve sparsity.
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).
DJI visit 05/2015

12

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.
GFT

DCT

filtering
operationα  x

a 4x4 block

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.

13

Depth Map Compression
using Multi-resolution GFT• Idea:• LP-filter & down-sample signal before GFT.
DCTLP & down-sampley  DHxoperators• GFT on LR block.
LR-GFT  y• Details:
GFT 1. Enc: Detect & encode HR edges (structure).
synthesized view PSNR in dB

PSNR vs. Coded Depth Map Size for Teddy
31

2. Enc: Encode down-sampled LR block using GFT (texture).

30

3. Dec: Deduce LR edges from HR edges (structure).

4. Dec: Decode LR block in GFT, up-sample & interpolateusing HR edges (smooth texture).

29282726
10HR-DCT
LR-DCT
HR-GBT
MR-GBT• Results: up to 68% bitrate reduction compared to HR-DCT.

2030
405060coded depth map size in kbits

70Wei Hu, Gene Cheung, Antonio Ortega, Oscar Au, "Multiresolution Graph Fourier Transformfor Compression of Piecewise Smooth Images," IEEE Transactions on Image Processing, vol.24,no.1, pp.419-433, January 2015.

14

Outline• Traditional vs. Graph Signal Processing• Graph Fourier Transform (GFT)• Depth Map Compression• Depth Map Denoising• Depth Map Interpolation

DJI visit 05/201515

Depth Image Denoising• Problem:• Acquired depth images are noisy.
observationy  xv

desired signal
noise• Strong signal prior: piecewise smooth (sparsity in GFT).
• Self-similarity in images (non-local means#).

• Our algorithm (in a nutshell):
1. Identify similar patches (same structure).
2. Compute average patch for cluster, compute GFT.

3. Denoise patches in cluster via group sparsification.
Intuition:
Sparsely represented signal = Denoised signal# A. Buades, B. Coll, J. M. Morel, “A review of image denoising algorithms, with a new one,” Multiscale
Modeling Simulation (SIAM Interdisciplinary J.), vol.4., no.2, pp.490-530, 2005.

16

Denoising Algorithm
common GFT from avg. patch
observation i
NNmin  yi  U i 2    i 0U ,i 1Algorithm:

2i 1

code vector for observation i

1. Identify similar patches, compute average
patch.（self-similarity）
2. Given average patch, compute “similarity”
between adjacent pixels. Construct graph.
3. Compute graph transform (GFT).
4. Given GFT, seek sparse representation.
*Wei Hu, Xin Li, Gene Cheung, Oscar Au, "Depth Map Denoising using Graph-based Transform and Group Sparsity," IEEE International
Workshop on Multimedia Signal Processing, Pula (Sardinia), Italy, October, 2013. (Top 10% paper award.)

17

Depth Image Denoising• Experimental Setup:• Test Middleburry depth maps: Sawtooth• Additive White Gaussian Noise (AWGN)• Compare to: Bilateral Filtering (BF), Non-Local Means Denoising, (NLM),Block-Matching 3D (BM3D).

• Results: 2.28dB improvement over BM3D.

NLGBT

NLM

BM3D
DJI visit 05/2015

BF18

Outline• Traditional vs. Graph Signal Processing• Graph Fourier Transform (GFT)• Depth Map Compression• Depth Map Denoising• Depth Map Interpolation

DJI visit 05/2015

19

Depth Image Interpolation• Problem:• Fill holes in sparsely sampled depth images.

• Idea:*1. Find right graph for missing pixels.
Depth image missing 85% pixels•

Adaptive kernel

2. Compute edge weights using initial values.
 y  y 2ij w i, j  exp 2
3. Find smooth graph-signal given observations.

2Intuition:tt
minux
y
xLxii 2smooth signal = interpolated
signalxi*Yu Mao, Gene Cheung, Yusheng Ji, "Image Interpolation During DIBR View Synthesis Using Graph Fourier Transform," 3DTV-Conference 2014,
Budapest, Hungary, July, 2014.

20

Denoising Results
Original

Noised(theta = 20)

LARK(26.99dB)

Our Proposal(27.36dB)

21

Interpolation Results
Original

Partial sample

LARK(34.82dB)

Our Proposal(35.31dB)

22

Summary & Open Problems• By embedding image structure onto a graph, signal issmooth wrt graph.
• Current Work:• GSP for joint denoising / SR of GPWS images (ICIP’14).
• GSP for bit-depth enhancement in images (ICIP’14).
• Variants of graph transforms (in submitted SPL).

• Open Questions:• Appropriate graph?
• Optimize desired signal and graph simultaneously.

• Given graph, appropriate set of basis?
• Other transforms, (biorthogonal) wavelets, dictionaries.
DJI visit 05/2015

23

Acknowledgement
Collaborators:• Y. Mao, Prof. Yusheng Ji (NII, Japan)• W. Sun, W. Hu, P. Wan, W. Dai, J. Pang, J. Zeng, A.
Zheng, Prof O. Au (HKUST, HK)• Y.-H. Chao, Prof. A. Ortega (USC, USA)• D. Florencio, C. Zhang, P. Chou (MSR, USA)

• Y. Gao, Prof. J. Liang (SFU, Canada)• T. Maugey, L. Toni, B. Motz, A. De Abreu, P. Frossard(EPFL, Switzerland)• B. Machiavello, C. Dorea, M. Hung (University ofBrasilia, Brazil)• W.-t. Tan (formerly HP Labs, now Cisco, USA)
• C. Yang, V. Stankovic (U of Strathclyde, UK)
DJI visit 05/201524