Gene Cheung, Xianming Liu
National Institute of Informatics
11th July, 2016

Graph Signal Processing for Image
Compression & Restoration(Part I).
ICME'16 Tutorial 07/11/2016

1

Biography• MS from UC Berkeley in EECS in 1998.
2D video• Thesis: Joint source / channel coding for wireless video.
Communication• PhD from UC Berkeley in EECS in 2000.
(12 years)• Thesis: Computation / memory / distortion tradeoff in signal compression.

• Senior researcher in HP Labs Japan from 2000 ~ 2009.
• Topic 1: 2D video coding & streaming (2000~2007).
• Topic 2: Multiview video, w/ Prof. Ortega (2007~).

• Associated professor in NII from 11/2009 to now.
3D video
Communication(8 yrs)• Topic 1: Image & video representation.
• Topic 2: Immersive visual communication.
• Topic 3: Graph signal processing.

• Adjunct associate professor in HKUST from 1/2015.

ICME'16 Tutorial 07/11/2016

2

Acknowledgement
Collaborators:• B. Motz, Y. Mao, Y. Ji (NII, Japan)• W. Hu, P. Wan, W. Dai, J. Pang, J. Zeng, A. Zheng,
O. Au (HKUST, HK)• Y.-H. Chao, A. Ortega (USC, USA)• D. Florencio, C. Zhang, P. Chou (MSR, USA)
• Y. Gao, J. Liang (SFU, Canada)• L. Toni, A. De Abreu, P. Frossard (EPFL, Switzerland)• C. Yang, V. Stankovic (U of Strathclyde, UK)• X. Wu (McMaster U, Canada)• P. Le Callet (U of Nantes, France)• H. Zheng, L. Fang (USTC, China)• C.-W. Lin (National Tsing Hua University, Taiwan)

ICME'16 Tutorial 07/11/2016

3

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 (Sokendai).
• 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.
ICME'16 Tutorial 07/11/2016

4

Outline (Part I)• Fundamental of Graph Signal Processing (GSP)• Spectral Graph Theory• Graph Fourier Transform (GFT)• Image Coding using GSP Tools• PWS Image Coding via Multi-resolution GFT• PWS Image Coding via Generalized GFT• Lifting Implementation of GFT

ICME'16 Tutorial 07/11/2016

5Outline (Part II)• Image Restoration using GSP Tools• Image Denoising• Soft Decoding of JPEG Compressed Images• (Presented by Prof. Xianming Liu)

ICME'16 Tutorial 07/11/2016

6Outline (Part I)• Fundamental of Graph Signal Processing (GSP)• Spectral Graph Theory• Graph Fourier Transform (GFT)• Image Coding using GSP Tools• PWS Image Coding via Multi-resolution GFT• PWS Image Coding via Generalized GFT• Lifting Implementation of GFT

ICME'16 Tutorial 07/11/20167

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, restoration, segmentation,
classification.
ICME'16 Tutorial 07/11/2016

8

Smoothness of Signals• Many known signals are smooth.
• Notion of frequency, band-limited.
N 1

1 
• Ex.1: DCT: X k   xn cos   n  k n 0

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

N

2 

a x

desired signaltransform

 a0 
a 
 1
a   0  Typical pixel blocks have  almost no high frequency  components.
Compact signal
representation 0transform coeff.

ICME'16 Tutorial 07/11/20169Sparsity of Signal Representations• “Everything should be made as simple as possible, but no simpler.”paraphrase of Albert Einstein• “Among competing hypotheses, the hypothesis with the fewest
assumptions should be selected (simplest explanation is usually thecorrect one).” Occam’s razor(over-complete) dictionary• Desirable signals are often sparse.
(sparse) code vectora  x• KLT: decorrelate input components.

desired signal

 

E xx  C• Eigen-decomposition of covariance matrix.

• DCT approximates KLT*.

covariance matrixTeigen-matrix

CQ  Q

diagonal matrixof eigen-values

Decorrelation leads tocompact signal representation
ICME'16 Tutorial 07/11/2016*Assuming simple AR process with same innovation variance.

10Graph Signal Processing

node
edge

• Signals live on graph.
• Graph is a collection 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.
[1] D. I. Shuman et al.,”The Emerging Field of Signal Processing on Graphs: Extending High-dimensional Data Analysis to Networks
and other Irregular Domains,” IEEE Signal Processing Magazine, vol.30, no.3, pp.83-98, 2013.

11

Graph Signal Processing
Research questions*:• Sampling: how to efficiently acquire /
sense a graph-signal?

node
edge

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

* Graph Signal Processing Workshop, Philadelphia, US, May 25-27, 2016.
https://alliance.seas.upenn.edu/~gsp16/wiki/index.php?n=Main.Program

12

undirected graph

Graph Fourier Transform (GFT)• Adjacency Matrix A: entry Ai,j has non-negativeedge weight wi,j connecting nodes i and j.

• Degree Matrix D: diagonal matrix w/ entry Di,i being
sum of column entries in row i of A.

Di ,i   Ai , jj• Combinatorial Graph Laplacian L: L = D-A• L is symmetric (graph undirected).
• L is a high-pass filter.
• L is related to 2nd derivative.

1

1

2

3

4

 0
w
A   1, 2
 0

 0

w1, 2

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

 w1, 2
 0
D
 0

 0

0 0
w1, 2  1 0 0
0
2 0

0
0 1

1

Graph Laplacian:w1, 2 w1, 2 w
L   1, 2
 0

 0

0
1
0
0

 w1, 20
w1, 2  1  1 0 
1
2  1
0
1 1 
0

L3,: x   x2  2 x3  x4
f x  h   2 f x   f x  h f  x   lim
h 0

h2

ICME'16 Tutorial 07/11/2016*https://en.wikipedia.org/wiki/Second_derivative

13

Graph Fourier Transform (GFT)• Graph Fourier Transform (GFT) is eigen-matrix of graph Laplacian L.
eigenvalue

L ui  i ui

eigenvector• Recall classical Fourier Transform: of function f is inner-product withcomplex exponentials:

inner-product of f and complex expf    f , e 2it   f t e 2it dt• Complex exponentials are eigen-functions of 1D Laplace operator:



 e

2it



 2 2it2
 2e 2  e 2itt• Analogously, GFT of graph-signal f is inner-product with eigenvectors ofgraph Laplacian L:

eigenvector of graph LaplacianN
f i   f , ui   f n  ui* n 
n 1

ICME'16 Tutorial 07/11/2016
14

Graph Fourier Transform (GFT)
1. Sum of columns in L = 0 → constanteigenvector assoc. with 0  0

1

w1, 2

1

2

1
3

4

…

1st AC eigenvector

2. Edge weights affect shapes of eigenvectors.
3. Eigenvalues (≥ 0) as graph frequencies.

• Constant eigenvector is DC component.
• # zero-crossings increases as λ increases.
4. GFT enables signal representation in graphfrequency domain.
GFT

α  x

5. “Smoothness”, “band-limited” defined w.r.t. tograph frequencies.
ICME'16 Tutorial 07/11/2016
15

8

1

1

Facts of Graph Laplacian & GFT

1

1

1
1

1
1

• x T Lx (graph Laplacian quadratic form) [2]) is one measure ofvariation in signal → graph-signal smoothness prior.

x T Lx 

1
2
2


w
x

x





i, j
i
j
i i
2 i, ji• Eigenvalues can be defined iteratively via Rayleigh quotient (CourantFischer Theorem):
T

0 

n 

f Lf minf Lf  n  1, 2,  , N  1



min
N

f R , f 2 1T

f R N , f 2 1, f  span u 0 ,,u n1• GFT defaults to DCT for un-weighted connected line.
• GFT defaults to DFT for un-weighted connected circle.

ICME'16 Tutorial 07/11/2016[2] D. Spielman, “Spectral Graph Theory,” Combinatorial Scientific Computing, Chapman and Hall / CRC Press, 2012.

16

Outline (Part I)• Fundamental of Graph Signal Processing (GSP)• Spectral Graph Theory• Graph Fourier Transform (GFT)• Image Coding using GSP Tools• PWS Image Coding via Multi-resolution GFT• PWS Image Coding via Generalized GFT• Lifting Implementation of GFT

ICME'16 Tutorial 07/11/2016

17

PWS Image Compression
using GFT
• DCT are fixed basis. Can we do better?

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

Assign edge weight 1 to adjacent pixel pairs.

2.

Assign edge weight 0 to sharp signal discontinuity.

3.

Compute GFT for transform coding, transmit coeff.

α  x
4.

GFT

Transmit bits (contour) to identify chosen GFT to
decoder (overhead of GFT).

[3] G. Shen et al., “Edge-adaptive Transforms for Efficient Depth Map Coding,”
IEEE Picture Coding Symposium, Nagoya, Japan, December 2010.
[4] 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.
18

PWS Image 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 [5].

Ans 2: Avoid filtering across sharp edges.
• Low-freq GFT basis are PWS for PWS signals (discussed later).

GFT

DCT

filtering
operationα  xa 4x4 block[5] 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.

19

Graph Fourier Transform (GFT)
for Block-based 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
ICME'16 Tutorial 07/11/2016[6] V. Goyal, “Theoretical foundations of transform coding,” in IEEE Signal Processing Magazine, vol. 18, no.5, September 2001, pp. 9–21.

20

Transform Comparison

Transform Representation

Transform Description

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

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

ICME'16 Tutorial 07/11/2016

21

GFT Comparison
HR-UGFT [3]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)[3] G. Shen et al., “Edge-adaptive Transforms for Efficient Depth Map Coding,”
IEEE Picture Coding Symposium, Nagoya, Japan, December 2010.

22

Search for Optimal GFT• Rate-distortion performance:• Assumption: high bit rate, uniform quantization
Distortion does not change when considering different transforms! [6]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

ICME'16 Tutorial 07/11/2016[7] Gray and Neuhoff, “Quantization,” IEEE Transactions on Information Theory, vol. 44, no. 6, Oct. 1998.

23

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

24
0
0

5

10

15

20

25

30

35

40

24
45

50

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?
ICME'16 Tutorial 07/11/2016

25

MR-GFT: Derivation of Optimal Edge Weights for
Weak Correlation•

Assume a 1D first-order autoregressive (AR) process

where,
smoothjump

non-zero mean random var.
•

Assuming the only weak correlation exists between

k-th

ICME'16 Tutorial 07/11/2016

wk 1,k

1
1

2

… k-1

k

…

and

26

N

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


0
T

E bb 
0

0


 0

 

0



0



1



0



0 

1

0



0 

0

0 

0



 g2  mg2  1 0 
0

1




0 

0

ICME'16 Tutorial 07/11/2016

0

0



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

k-th row27

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

ICME'16 Tutorial 07/11/2016

28

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

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

ICME'16 Tutorial 07/11/2016

29

WGFT
•

Cost function of transform coefficients

GFT coeff2Rˆ x, W   x T Lx  Wi,j xi  x j    k k2

i , j 

kgraph freq.

•

Cost function of transform description

costly if many weight changes•

Problem formulation for WGFT deviation

code only non-1’s
separation

orig graph•dual graph

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

[8] 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.

30

UGFT

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

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

31

MR-GFT: Adaptive Selection of Graph Fourier
Transforms•

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

32

MR-GFT: Adaptive Selection of Graph Fourier
Transforms

ICME'16 Tutorial 07/11/2016

33

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 in H.264.

•

Results

HR-DCT:
HR-SGFT:SAW:
MR-SGFT:ICME'16 Tutorial 07/11/2016

6.8dB
5.9dB
2.5dB
1.2dB

34

Subjective Results

HR-DCT

HR-SGFTICME'16 Tutorial 07/11/2016

MR-GFT

35

Mode Selection

red: WGFT
blue: UGFTICME'16 Tutorial 07/11/2016

36

Edge Coding for PWS
Image Compression• Arithmetic Edge Coding [10]:• Coding of sequence of between-pixel edges, or
chain 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 [11]:

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.
[10] I. Daribo, G. Cheung, D. Florencio, “Arbitrarily Shaped Sub-block Motion Prediction in Depth Video
Compression using Arithmetic Edge Coding," IEEE Trans on Image Processing, Nov 2014.
[11] Y. Yuan G Cheung, P. Frossard, P. Le Callet, V. Zhao, “Contour Approximation & Depth Image
Coding for Virtual View Synthesis,” IEEE MMSP, October, 2015.

37

Experimentation• Setup- AEC for contour coding plus MR-GFT.

- Compare against: native HEVC•

Results

ICME'16 Tutorial 07/11/2016

38

Summary for Multi-resolution Graph Fourier
Transform•

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!

ICME'16 Tutorial 07/11/2016

39

Outline (Part I)• Fundamental of Graph Signal Processing (GSP)• Spectral Graph Theory• Graph Fourier Transform (GFT)• Image Coding using GSP Tools• PWS Image Coding via Multi-resolution GFT• PWS Image Coding via Generalized GFT• Lifting Implementation of GFT

ICME'16 Tutorial 07/11/2016

40

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[12] W. Hu et al., “Intra-Prediction and Generalized Graph Fourier Transform for Image Coding,” IEEE
Signal Processing Letters, vol.22, no.11, pp. 1913-1917, November, 2015.

41

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

ICME'16 Tutorial 07/11/2016

42

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

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

• Ye et al, MDDT [14]• Completely data-driven resulting in unstructured transform.
[5] 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.
[13] Y. Wang, A. Ortega, and G. Cheung, “Intra predictive transform coding based on predictive graph transform,” ICIP, September
2013.
[14] Y. Ye and M. Karczewicz, “Improved H.264 intra coding based on bidirectional intra prediction, directional transform, andadaptive coefficient scanning,” ICIP, October 2008.

ICME'16 Tutorial 07/11/2016

43

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
ICME'16 Tutorial 07/11/2016

44

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.,ICME'16 Tutorial 07/11/2016

45

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

ICME'16 Tutorial 07/11/2016

46

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

Generalized Laplacian+=
Combinatorial Laplacian

Degree matrix for boundary vertices

ICME'16 Tutorial 07/11/2016

47

Generalized Graph Fourier Transform• The precision matrix of the prediction residual• Default to the DCT if• Default to the ADST [15] if

and
and

[15] 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.

48

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
ICME'16 Tutorial 07/11/2016

49

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

ICME'16 Tutorial 07/11/2016

50

Experimental Results

ICME'16 Tutorial 07/11/2016

51

Subjective Quality

eIntra + DCT

eIntra + GFT

ICME'16 Tutorial 07/11/2016

pIntra + GGFT

52

Outline (Part I)• Fundamental of Graph Signal Processing (GSP)• Spectral Graph Theory• Graph Fourier Transform (GFT)• Image Coding using GSP Tools• PWS Image Coding via Multi-resolution GFT• PWS Image Coding via Generalized GFT• Lifting Implementation of GFT

ICME'16 Tutorial 07/11/2016

53Motivation• Complexity of GFT• Transform matrices are dense with floating point values• Complexity of transform operation: O(N2), N : number of nodes• Contribution• Design low complexity transform w/ graph-based lifting O(N log N)• Novel bipartition approach in the lifting transform• Novel multi-level lifting filterbanks design• Performance approximates the GFT for intra-predicted videocoding[16] Yung-Hsuan Chao, Antonio Ortega, and Sehoon Yea, "Graph-based lifting transform for intra-predicted video coding",
IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2016, pp. 1140-1144

54

Preliminaries - Lifting transform• 1-level lifting transform• The transform consists of 3 steps:• (1) Bipartition into two disjoint sets SU and SP (signal fU and fP )• (2) Predict signal fP in SP with nodes in SU• (3) Update signal fU in SU with the prediction residue stores in SP[17] W. Sweldens, “The lifting scheme: A construction of second generation wavelets,” Technical report 1995:6, Industrial
Mathematics Initiative, Department of Mathematics, University of South Carolina.

55

Preliminaries - Lifting transform• Multi-level lifting transform:• Dyadic decomposition for SU in each level

ICME'16 Tutorial 07/11/2016

56

Bipartition Algorithm• Goal: minimize energy of prediction residue (high frequency) stored in SP→ increase energy compaction• Applied signal modelf ~ N 0,   Q 1 
Q   L   L   L • Gaussian Markov Random Field (GMRF):• Inverse covariance matrix• Proposed bipartitionS  arg min E f P  μ P|U
*
U

SU

2



• Where μ P|U is the MAP predictor of f P | fU
• NP hard → greedy approximation

SU  0 and S P  V
2*• Select node v  S P  arg min E f P  μ P|U v • Initialization:vICME'16 Tutorial 07/11/2016



iteratively
57

Bipartite Graph Formulation• Proposed method
1. Connecting nodes in SP using Kron reduction* → bipartite graph ABP• Procedure

1. For each node v in SP

2. Remove nodes in S P /v
3. Apply Kron reduction on the resulting subgraph1.

derive connection from v to S

U

4. Prune the links of v by keeping the 4 links with largest weights
5. Repeat the same procedure for all the nodes in SP* Dorfler, Florian and Bullo, Francesco, “Kron reduction of graphs with applications to electrical networks,” IEEE Transactions on
Circuits and Systems I 2013

58

Filterbanks Design59* Shen, Godwin, and Antonio Ortega. Tree-based wavelets for image coding: Orthogonalization and tree selection. PCS 2009

Experimental Results - Simulation Setup Test
• Test Sequences: Foreman, Mobile, Silent, Deadline• Extract intra-predicted residual blocks from HEVC (HM-14) encoder• Fixed block size as 8 x 8• Transform coefficients are uniformly quantized and then encoded• using a symbol grouping-based arithmetic entropy encoder (AGP*)• Edge Map is encoded using arithmetic edge coding (AEC**)*A. Said and W. A. Pearlman, Low-complexity waveform coding via alphabet and sample-set partitioning, SPIE Visual
Communications and Image Processing (1997)** Daribo, Ismael and Cheung, Gene and Florencio, Dinei, Arithmetic edge coding for arbitrarily shaped sub-block motion
prediction in depth video compression, ICIP 201260

Experimental Results• Hybrid mode between proposed lifting and DCT:

• based on RD cost SSE + λ Bitrate• Bjontegaard Distortion-Rate against DCT

ICME'16 Tutorial 07/11/2016

61

Summary (Part I)• GFT is signal-adaptive transform.
• Adaptive transform → energy compaction.
• Adaptive transform → signal overhead.
• GFT approx. KLT assuming 1D AR model.
• GGFT approx. KLT for prediction residual.

• PWS signal, signaling can be coded contour via AEC.
• Lifting Implementation of GFT.

ICME'16 Tutorial 07/11/2016

62

Open Questions• Coding of Natural images:• What is optimal clustering?
• What is optimal graph, optimal transform?
• Joint intra-prediction / transform design?

• Coding of 3D data:• How to use GSP tools to code dynamic 3D geometry?
• How to use GSP tools to code light field data?

ICME'16 Tutorial 07/11/2016

63

Q&A

• Email: cheung@nii.ac.jp• Homepage: http://research.nii.ac.jp/~cheung/

ICME'16 Tutorial 07/11/201664