Gene Cheung
National Institute of Informatics
26th November, 2017

Graph Signal Processing for
Image Coding & Restoration.
BJTU 11/25/2017

1

Acknowledgement
Collaborators:• M. Kaneko (NII, Japan)• A. Ortega (USC, USA)• D. Florencio (MSR, USA)
• P. Frossard (EPFL, Switzerland)• J. Liang, I. Bajic (SFU, Canada)• V. Stankovic (U of Strathclyde, UK)• X. Wu (McMaster U, Canada)• P. Le Callet (U of Nantes, France)• X. Liu (HIT, China)• W. Hu, J. Liu, Z. Guo (Peking U., China)• L. Fang (Tsinghua, HK)• C.-W. Lin (National Tsing Hua University, Taiwan)
BJTU 11/25/2017

2

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.

BJTU 11/25/20173

Introduction to APSIPA and APSIPA DL

APSIPA Mission: To promote broad spectrum of research and education
activities in signal and information processing in Asia Pacific
APSIPA Conferences: ASPIPA Annual Summit and Conference
APSIPA Publications: Transactions on Signal and Information Processingin partnership with Cambridge Journals since 2012; APSIPA Newsletters
APSIPA Social Network: To link members together and to disseminate
valuable information more effectively
APSIPA Distinguished Lectures: An APSIPA educational initiative to reachout to the community

APSIPA Distinguished Lecture Series
www.apsipa.org

4Outline• Graph Signal Processing• Graph spectrum, GFT• PWS Image Coding using GFT• Prediction Residual Coding using GGFT
• Image Denoising using Graph Laplacian Regularizer• Soft Decoding of JPEG Images w/ LERaG• GSP for 3D Imaging• Summary & Ongoing WorkBJTU 11/25/20175Outline• Graph Signal Processing• Graph spectrum, GFT• PWS Image Coding using GFT• Prediction Residual Coding using GGFT
• Image Denoising using Graph Laplacian Regularizer• Soft Decoding of JPEG Images w/ LERaG• GSP for 3D Imaging• Summary & Ongoing WorkBJTU 11/25/2017

6Digital Signal Processing• Discrete signals on regular data kernels.
• Ex.1: audio on regularly sampled timeline.

• Ex.2: image on 2D grid.

• Harmonic analysis tools (transforms,
wavelets) for diff. tasks:• Compression.
• Restoration.

• Segmentation, classification.

BJTU 11/25/2017

7

Smoothness of Signals• Signals are often smooth.
• Notion of frequency, band-limited.
• Ex.: 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

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

BJTU 11/25/2017

8

Graph Signal Processing• Signals on irregular data kernels described bygraphs.
• Graph: nodes and edges.
• Edges reveals node-to-node relationships.

example graph-signal

1. Data domain is naturally a graph.
• Ex: ages of users on social networks.

2. Underlying data structure unknown.
• Ex: 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.

9

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, 2016. https://alliance.seas.upenn.edu/~gsp16/wiki/index.php?n=Main.Program*Graph Signal Processing Workshop, Pittsburgh, US, May, 2017. https://gsp17.ece.cmu.edu/

10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

BJTU 11/25/2017*https://en.wikipedia.org/wiki/Second_derivative11

Graph Spectrum from GFT• Graph Fourier Transform (GFT) is eigen-matrix of graph Laplacian L.
w1, 2 11
eigenvalue

L ui  i ui

1

2

3

4

…

8

eigenvector
1st AC eigenvector

1. Edge weights affect shapes of eigenvectors.
2. Eigenvalues (≥ 0) as graph frequencies.
• Constant eigenvector is DC.
• # zero-crossings increases as λ increases.
• GFT defaults to DCT for un-weighted connected line.
• GFT defaults to DFT for un-weighted connected circle.
BJTU 11/25/2017
12Variants of Graph Laplacians• Graph Fourier Transform (GFT) is eigen-matrix of graph Laplacian L.

L ui  i ui

eigenvalue
eigenvector• Other definitions of graph Laplacians:• Normalized graph Laplacian:Ln  D 1 / 2 LD 1 / 2  I  D 1 / 2 AD 1 / 2• Random walk graph Laplacian:1

1

Lrw  D L  I  D A• Generalized graph Laplacian [1]:Lg  L  D*Characteristics:• Normalized.
• Symmetric.
• No DC component.
• Normalized.
• Asymmetric.
• Eigenvectors not orthog.
• Symmetric.
• L plus self loops.
• Defaults to DST, ADST.

[1] Wei Hu, Gene Cheung, Antonio Ortega, "Intra-Prediction and Generalized Graph Fourier Transform for Image Coding," IEEE
Signal Processing Letters, vol.22, no.11, pp. 1913-1917, November 2015.

13

GSP and Graph-related Research
GSP: SP framework that unifies concepts from multiple fields.

Partial Differential
Eq’ns

MachineLearning

Laplaceequationgraphical model,
manifold learning,classifier learning

LaplaceBeltrami
operator

Computer Graphics

Graph Signal
Processing* (GSP)
DSP

spectralclustering

Computer
VisionMax cut, graphtransformation

eigen-analysis ofgraph Laplacian,adjacency matrices

Combinatorial
Graph Theory

SpectralGraph Theory
BJTU 11/25/201714

Outline• Graph Signal Processing• Graph spectrum, GFT• PWS Image Coding using GFT• Prediction Residual Coding using GGFT
• Image Denoising using Graph Laplacian Regularizer• Soft Decoding of JPEG Images w/ LERaG• GSP for 3D Imaging• Summary & Ongoing WorkBJTU 11/25/2017

15

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

[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.
16Transform Comparison

Transform Representation

Transform Description

Karhunen-Loeve
Transform (KLT)“Sparsest” signal representation given
available 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[1] Wei Hu, Gene Cheung, Antonio Ortega, Oscar Au, "Multiresolution Graph Fourier Transform for Compression of
Piecewise Smooth Images," IEEE Transactions on Image Processing, vol.24, no.1, pp.419-433, January 2015.

17

MR-GFT: Definition of the Search Space forGraph Fourier Transforms
Rate of transform coefficient vector

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

strong Histogram of inter-pixel difference3500- "1": strong correlation in smooth regions

3000- "0": zero correlation in sharp boundaries

2500- "c": weak correlation in slowly-varying parts

2000

zero

1500

1000

weak

500

18
0
0

5

10

15

20

25

30

35

40

18
45

50

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

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

where,

smoothjump•

Assuming the only weak correlation exists between

wk 1,k1

non-zero mean random var.

1

non-zero mean RV

2

… k-1

k

…

N

and

kth rowmean
vectork-th

BJTU 11/25/201719

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

 21

0


0
E bbT  
0

0


 0

 

• Precision matrix (tri-diagonal)

0



0



1



0



0 

1

0



0 

0

0 

0



 g2  mg2  1 0 
0



1


0 

0

0



0

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

k-th row

Graph Laplacian matrix!

(k-1)-th row
k-th row

1
BJTU 11/25/2017

1

1
20

MR-GFT: Adaptive Selection of Graph Fourier
Transforms

AEC

AEC-1

BJTU 11/25/201721

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:

6.8dB
5.9dB
2.5dB
1.2dB

22

Subjective Results

HR-DCT

HR-SGFTBJTU 11/25/2017

MR-GFT

23

Mode Selection

red: WGFT
blue: UGFTBJTU 11/25/201724

Edge Coding for PWS
Image Compression• Arithmetic Edge Coding [1,2]:• Coding of sequence of between-pixel edges, or
chain code with symbols {l, s, r}.
• Design a variable-length context tree (VCT) to
compute symbol probabilities for arithmetic coding.

[1] 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.
[2] Amin Zheng, Gene Cheung, Dinei Florencio, "Context Tree based Image Contour Coding using A
Geometric Prior," IEEE Transactions on Image Processing, vol.26, no.2, pp.574-589, February 2017.

25

Outline• Graph Signal Processing• Graph spectrum, GFT• PWS Image Coding using GFT• Prediction Residual Coding using GGFT
• Image Denoising using Graph Laplacian Regularizer• Soft Decoding of JPEG Images w/ LERaG• GSP for 3D Imaging• Summary & Ongoing WorkBJTU 11/25/2017

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

27

Histogram of inter-pixel difference

Optimal 1D Intra prediction

class0class0class1class3class2

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

bin average

Class kClass lapproximation error• Optimal prediction in terms of resulting
in a zero-mean prediction residual• Default to conventional intra-prediction
when, i.e.,BJTU 11/25/2017

28

Generalized Graph Fourier Transform• The precision matrix of the prediction residual+=
Generalized Laplacian• Default to the DCT if• Default to the ADST [1] if

Combinatorial LaplacianandDegree matrix forboundary vertices

inaccuracy of intra-prediction

anddiscontinuities within signal

Variance of approx. error[1] 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.

29

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

BJTU 11/25/201730

Spectral Folding & Critical Sampling• Spectral Folding:• (Sub)sampling a bandlimited signal at freq. fs→ freq. content replication at fs.
• Nyquist Sampling Theorem:• To avoid aliasing, sample at 2x max. freq. of
bandlimited signal.
• Multirate Wavelet Filterbank:• System of “perfect reconstruction” bandpass filters

analysis filter

BJTU 11/25/2017

synthesis filter

31

Bipartite Graph Approximation• Problem: GraphBior [1,2] (critically sampled,
perfect reconst. wavelet) for bipartite graph only!
• Idea [3]:• Successively find bipartite graph approximation.

• Criteria for graph approx [1]:bipartite
graph
Laplacian

b
b



min
D
L
||
L


rank
L
KL
1, 2 b
L

KL divergence

sub-matrix for 2
partitions• Preserve graph structure, minimize eigenvalue=1.

[1] S. Narang and A. Ortega, “Perfect reconstruction two-channel wavelet filter banks for graphstructured data,” IEEE Transactions on Signal Processing, vol. 60, no. 6,pp. 2786–2799, June 2012.
[2] S. Narang and A. Ortega, “Compact support biorthogonal wavelet filterbanks for arbitrary undirected
graphs,” IEEE Transactions on Signal Processing, vol. 61, no. 19, pp. 4673–4685, Oct 2013.
[3] Jin Zeng, Gene Cheung, Antonio Ortega, "Bipartite Subgraph Decomposition for Critically Sampled Wavelet Filterbanks on
Arbitrary Graphs," IEEE International Conference on Acoustics, Speech and Signal Processing, Shanghai, China, March, 2016.

32

Outline• Graph Signal Processing• Graph spectrum, GFT• PWS Image Coding using GFT• Prediction Residual Coding using GGFT
• Image Denoising using Graph Laplacian Regularizer• Soft Decoding of JPEG Images w/ LERaG• GSP for 3D Imaging• Summary & Ongoing WorkBJTU 11/25/2017

33

Graph Laplacian Regularizer

1

w1, 2

1
2

1
3

4

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

1
2
x Lx   wi , j xi  x j    k k2
2 i, jkT• Signal Denoising:

signal smooth innodal domain

signal contains
mostly low graph freq.

desired signaly  xv

observation

noise• MAP formulation:

min y  x 2   x T L x
2x

smoothness priorfidelity term
[1] P. Milanfar, “A Tour of Modern Image Filtering: New Insights and Methods, Both Practical and Theoretical,” IEEE Signal
Processing Magazine, vol.30, no.1, pp.106-128, January 2013.

34

Graph Laplacian Regularizer for Denoising
1. Choose graph:• Connect neighborhood graph.

• Assign edge weight:

pixel intensity difference
pixel location difference x x 2
 l l 2 
i
j 2 

 i j 2wi , j  expexp  2

 12

2





2. Solve obj. in closed form:

min y  x 2   x T L x
2x• Iterate until convergence.

[1] W. Hu, G. Cheung, M. Kazui, "Graph-based Dequantization of Block-Compressed Piecewise Smooth Images," IEEE Signal
Processing Letters, vol.23, no.2, pp.242-246, February 2016.

35

Analysis of Graph Laplacian Regularizer• Show SG (u)  u T Lu converges to continuous functional S ,analysis of S  explains how u T Lu penalizes candidates:

prior ( x )  x L x  S  x    x G x
T

T



1

 det G  ds2 1

feature function vectorv i  [f1 (i ) f 2 (i )  f N (i)]T• Derive optimal SG (u)  u T Lu for denoising: graph is
discriminant for small noise, robust when very noisy.

distance

dij2  v i  v j2
2edge weight
Non-local self-similarity and
MMSE formulationwij  ( i  j )   (dij )obtainOptimal regularizer SG

metricN
T
space G   f n ·f nn 1• We interpret graph Laplacian regularization as anisotropic
diffusion, show that it not only smooths but may also
sharpens the image, promote piecewise smooth images[1] J. Pang, G. Cheung, "Graph Laplacian Regularization for Inverse Imaging: Analysis in the Continuous Domain," IEEE
Transactions on Image Processing, vol. 26, no.4, pp.1770-1785, April 2017.

36

Denoising Experiments (natural images)• Subjective comparisons (  I  40 )Original

Noisy, 16.48 dB

K-SVD, 26.84 dB

BM3D, 27.99 dB

PLOW, 28.11 dB

OGLR, 28.35 dB

BJTU 11/25/2017

37

Denoising Experiments (depth images)• Subjective comparisons (  I  30 )Original

Noisy, 18.66 dB

BM3D, 33.26 dB NLGBT, 33.41dB OGLR, 34.32 dB[1] W. Hu et al., "Depth Map Denoising using Graph-based Transform and Group Sparsity," IEEE International Workshop on
Multimedia Signal Processing, Pula (Sardinia), Italy, October, 2013.

38

Outline• Graph Signal Processing• Graph spectrum, GFT• PWS Image Coding using GFT• Prediction Residual Coding using GGFT
• Image Denoising using Graph Laplacian Regularizer• Soft Decoding of JPEG Images w/ LERaG• GSP for 3D Imaging• Summary & Ongoing WorkBJTU 11/25/201739

Soft Decoding of JPEG Images• Setting: JPEG compresses natural images:
1. Divide image into 8x8 blocks, DCT.
2. Perform DCT transform per block and quantize:
DCTqi  round (Yi / Qi ), Y =Ty
quantization parameter

8x8 pixel block

DCT Coefficients

3. Quantized DCT coeff entropy coded.
• Decoder: uncertainty in signal reconstruction:qi Qi  Yi  (qi  1) Qi , i  1, 2,, 64.

[1] A. Zakhor, “Iterative procedures for reduction of blocking effects in transform image coding,” IEEE Transactions on Circuits andSystems for Video Technology,, vol. 2, no. 1, pp. 91–95, Mar 1992.
[2] K. Bredies and M. Holler, “A total variation-based JPEG decompression model,” SIAM J. Img. Sci., vol. 5, no. 1, pp. 366–393, Mar. 2012.
[3] H. Chang, M. Ng, and T. Zeng, “Reducing artifacts in jpeg decompression via a learned dictionary,” IEEE Transactions on Signal
Processing,,vol. 62, no. 3, pp. 718–728, Feb 2014.

40

Graph Laplacian Regularizer for Denoising
1. Choose graph:• Connect neighborhood graph.

• Assign edge weight:

pixel intensity difference
pixel location difference x x 2
 l l 2 
i
j 2 

 i j 2wi , j  expexp  2

 12

2





2. Solve obj. in closed form:

min y  x 2   x T L x
2x• Iterate until convergence.
Comments:
1. L is NOT normalized.
2. Why works well for PWS signals?
[1] W. Hu, G. Cheung, M. Kazui, "Graph-based Dequantization of Block-Compressed Piecewise Smooth Images," IEEE Signal
Processing Letters, vol.23, no.2, pp.242-246, February 2016.

41

Spectral Clustering• Normalized Cut [1]:





min Ncut A, B : cut A, B 
A, B

1
1 


 vol  A vol B  

cut  A, B  WiA, jBi, jvol  A   Di ,iiA• Problem is NP-hard, so:

min normalized cut

1. Rewrite as:

f T Lf
min T
f
f Df

 1
 vol  A if i  A
s.t. f i  1

if i  B vol B 

2. Relax to:f T Lf
min T
f
f Df

s.t. f T D1  0[1] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888–905,
Aug. 2000.

min cut42~ 

Eigenvectors of Normalized graph Laplaciankk

min y  x 2   x T L n x
2• Define:v : D f
1/ 2

xv1 : D 1
1/ 2

• Problem rewritten as:
T
v
Ln v
*
v  arg min T
v
v v

2
k

candidate objective

Rayleigh quotient

1st AC eigenvector

s.t. v T v1  0• v1 minimizes obj → Sol’n is 2nd eigenvector of Ln.

• If f* optimal to norm. cut, v* is PWS → well rep. PWS signals!
• f* optimal when nodes easy to cluster:• Easy-to-cluster graph has small Fiedler number.

• Disadvantage:• v1 not constant vector (DC) → cannot well rep. smooth patch.

43

Left E-vector random walk graph Laplacian(LERaG)• Disadvantage:• Lrw is asymmetric → no orthogonal e-vectors w/ real e-values.

• So, left Eigenvector Random Walk Graph Laplacian (LERaG) [1]:projection of signal x
to D1/2, then Ln[1] Xianming Liu, Gene Cheung, Xiaolin Wu, Debin Zhao, "Random Walk Graph Laplacian based Smoothness Prior for Soft Decodingof JPEG Images," accepted to IEEE Transactions on Image Processing, October 2016.

44

Comparison of Graph-signal Smoothness Priors• Different graph Laplacian matrices• Combinatorial graph Laplacian:• Symmetrically normalized graph Laplacian:• Random walk graph Laplacian:• Doubly stochastic graph Laplacian [1]:Graph Laplacian

Symmetric

Normalized

DC e-vector

Combinatorial

Yes

No

Yes

Symmetrically Normalized

Yes

Yes

No

Random Walk

No

Yes

Yes

Doubly Stochastic [1]

Yes

Yes

Yes

[1] A. Kheradmand and P. Milanfar, “A general framework for regularized, similarity-based image restoration,” IEEE Transactions on
Image Processing, vol. 23, no. 12, pp. 5136–5151, Dec 2014.

45

LERaG for Soft Decoding of JPEG Images• Problem: reconstruct image given indexed quant. bin in 8x8 DCT.

• Procedure:
1. Initialize per-block
MMSE sol’n via
Laplacian prior.

1 T
d min
   ~k2  k2  0k

2. Solve per-patch signal
restoration problem w/
2 priors:
1. Sparsity prior
2. Graph-signal
smoothness prior[1] Xianming Liu, Gene Cheung, Xiaolin Wu, Debin Zhao, "Random Walk Graph Laplacian based Smoothness Prior for Soft Decodingof JPEG Images," IEEE Transactions on Image Processing, vol.26, no.2, pp.509-524, February 2017.

46

Soft Decoding Algorithm w/ Prior Mixture• Objective:

fidelity termsparsity priorgraph-signal smoothness
prior

graph-signal,
code vector

quantization bin constraint• Optimization:
1. Laplacian prior provides an initial estimation;
2. Fix x and solve for α;

3. Fix α and solve for x.

BJTU 11/25/201747

Evolution of 2nd Eigenvector• 2nd Eigenvector becomes more PWS:

• PWS means:
1. better pixel clusters,
2. smaller Fidler number (2nd eigenvalue),
3. Smaller smoothness penalty term.
BJTU 11/25/201748

Experimental Setup• Compared methods• BM3D: well-known denoising algorithm• KSVD: with a large enough over-complete dictionary (100x4000); ourmethod uses a much smaller one (100x400).
• ANCE: non-local self similarity [Zhang et al. TIP14]• DicTV: Sparsity + TV

[Chang et al, TSP15]• SSRQC: Low rank + Quantization constraint [Zhao et al. TCSVT16]BJTU 11/25/2017

49

PSNR / SSIM Comparison

BJTU 11/25/2017

50

Subjective Quality Evaluation

BJTU 11/25/2017

51

Subjective Quality Evaluation

BJTU 11/25/2017

52

Other Comparisons• Computation complexity:• Comparisons w/ other graph regularizers:

53

Outline• Graph Signal Processing• Graph spectrum, GFT• PWS Image Coding using GFT• Prediction Residual Coding using GGFT
• Image Denoising using Graph Laplacian Regularizer• Soft Decoding of JPEG Images w/ LERaG• GSP for 3D Imaging• Summary & Ongoing WorkBJTU 11/25/2017

54

Graph-Signal Sampling / Encoding for 3D
Point Cloud• Problem: Point clouds require encoding specific 3D coordinates.
• Assumption: smooth 2D manifold in 3D space.

• Proposal: progressive 3D geometry rep. as series of graph-signals.

MIT 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 ∗1. adaptively identifies new samples on the manifold surface, and
2. encodes them efficiently as graph-signals.

• Example:
1.

Interpolate 𝑖𝑡ℎ iteration samples (black circles) to a continuous kernel (mesh),an approximation of the target surface S.

2.

New sample locations, knots (squares), are located on the kernel surface.

3.

Signed distances between knots and S are recorded as sample values.

4.

Sample values (green circles) are encoded as a graph-signal via GFT.
BJTU 11/25/2017

55

Graph-Signal Sampling / Encoding for 3D
Point Cloud• Experimental Results:(a) Dataset1(b) Dataset2[1] Mingyuan Zhao, Gene Cheung, Dinei Florencio, Xiangyang Ji, "Progressive Graph-Signal Sampling and Encoding for Static 3D
Geometry Representation," IEEE International Conference on Image Processing, Beijing, China, September, 2017.

56

Pre-Demosiac Light Field Image
Compression Using Graph Lifting Transform• Problem: Sub-aperture images in Light field data are huge.
Raw Lenselet
Image

Demosaiced
Image

Calibrated Color
Image

Sub-apertureB B B B Images

GBGBGBGB
RGR
RGRG
BGR
BBB
RGR
G GRG
RRRR

BBBBBBBBBBBBBB
RB
RB
RB
RB
RB
RB
RB
RB
RG
RBG
RBG
RBG
RRG
RB
B
B
B
B
B
G
G
G
G
G
G
G
G
G
R
GB
GB
GB
GB
GB
GB B BGRGRGR
GRGG
GBG
GBG
RGBG
R
R
RG
RB
G
B
B
B
R
B
B
GB
GB
G
G
G
G
G
G
RB
G
G
G
G
G
G
G
BGBGBGBBBBB
GGRGGRGGRGGR
GRGG
R
B
B
B
B
B
B
G
G
G
G
G
G
G
G
GB
RB
GB
GB
GB
GB
GB
GB
GRGRGRGRGRGRGRGRGR
G
G
G
G
G
G
G
G
R
BGBGBGG G G G G G Calibration
GGGGGGGG(Scaling,
Demosaicing
Transition,
Rotation)×3

BBBB
GBGBGBGBRGRGRGRG
BR
BBB
RGR
G GRG
RRRR

BBBB
GBGBGBGBRGRGRGRG
BR
BBB
RGR
G GRG
RRRR

× ≈ 1.5• Proposal: postpone demosiacking to decoder.
Raw Lenselet
Image

Calibrated LenseletImageG

G R G R G R
B G B G B G
G R G R G R
B G B G B G

GR
BG

GRG
BGB

R
G

GR
Re-arranged on B G

GRG
BGB

R Re-arrangedG
G

Calibrated Image

Image
CodingB

in 4D space

Sub-aperture
space

graph-based
lifting transform

G

R
G
RG
B R
RGB

G

RR
GB
R B GG
57

Pre-Demosiac Light Field Image
Compression Using Graph Lifting Transform• Experimental Results:
Dataset: EPFL light field image dataset
Baseline: All-intra HEVC coding in YUV4:2:0 and RGB 4:4:4[1] Y.-H. Chao, G. Cheung, A. Ortega, "Pre-Demosiac Light Field Image Compression Using Graph Lifting

Transform," IEEE Int’l Conf. on Image Processing, Beijing, China, September, 2017. (Best student paper award)

58

Outline• Graph Signal Processing• Graph spectrum, GFT• PWS Image Coding using GFT• Prediction Residual Coding using GGFT
• Image Denoising using Graph Laplacian Regularizer• Soft Decoding of JPEG Images w/ LERaG• GSP for 3D Imaging• Summary & Ongoing WorkBJTU 11/25/201759Summary• Graph Signal Processing (GSP)• Spectral analysis tools to process signals on graphs.

• PWS Image Compression• Graph Fourier Transform• Generalized GFT• Arithmetic Edge Coding• Graph-signal Smoothness for Inverse Problems• Image denoising w/ graph Laplacian regularizer• New regularizer LERaG soft decoding of JPEG Images• GSP for 3D Imaging• 3D point cloud compression, light field image compression
BJTU 11/25/2017

60

Other GSP Works:
Semi-Supervised Graph Classifier Learning• Binary Classifier: given feature vector xi ofdimension K, compute f(xi) ∊ {0,1}.
• Classifier Learning: given partial / noisy labels(xi, yi), train classifier f(xi).

• GSP Approach [1]:example graph-based classifier

1. Construct similarity graph with +/- edges.
2. Pose MAP graph-signal restoration problem.
3. Perturb graph Laplacian to ensure PSD.
4. Solve num. stable MAP as sparse lin. system.
[1] Yu Mao, Gene Cheung, Chia-Wen Lin, Yusheng Ji, “Image Classifier Learning from Noisy Labels via Generalized Graph
Smoothness Priors,” IEEE IVMSP Workshop, Bordeaux, France, July 2016. (Best student paper award)[2] G. Cheung, W.-T. Su, Y. Mao, C.-W. Lin, "Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights," submitted
to IEEE Transactions on Signal and Information Processing over Networks, November 2016. (arXiv)61

Other GSP Works• Coding of spectral image [1], 3D point cloud w/ GFT.
• Coding of graph data w/ graph wavelets.
• Political leaning estimation [2].
• Wireless signal / power estimation [3].
[1] J. Zeng, G. Cheung, Y.-H. Chao, I. Blanes, J. Serra-Sagrista, A. Ortega, "Hyperspectral
Image Coding using Graph Wavelets," IEEE International Conference on Image
Processing, Beijing, China, September, 2017.

[2] B. Renoust et al., "Estimation of Political Leanings via Graph-Signal Restoration,"
IEEE International Conference on Multimedia and Expo, Hong Kong, China, July, 2017[3] M. Kaneko, G. Cheung, W.-t. Su, C.-W. Lin, "Graph-based Joint Signal / Power
Restoration for Energy Harvesting Wireless Sensor Networks," IEEE Globecom,
Singapore, December, 2017.

62

Q&A

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

BJTU 11/25/2017

63