Gene Cheung
National Institute of Informatics
2nd September, 2016

Inverse Imaging Problems using
Graph-Signal Smoothness Priors.
PKU Visit 09/02/2016

1

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)• S. Yang, J. Liu, Z. Guo (Peking U. China)
PKU Visit 09/02/2016

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.
PKU Visit 09/02/2016

3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• Graph-Signal Smoothness Prior• Graph Laplacian regularizer• LERaG• Soft Decoding of JPEG Images• Mixture of Priors

PKU Visit 09/02/2016

5Outline• Graph Signal Processing• Graph spectrum• Graph-Signal Smoothness Prior• Graph Laplacian regularizer• LERaG• Soft Decoding of JPEG Images• Mixture of Priors

PKU Visit 09/02/2016

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.

PKU Visit 09/02/2016

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 12D 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.

PKU Visit 09/02/2016

8

Graph Signal Processing• Signals on structured 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?

nodeedge• Graph sampling theorems.

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

• Signal restoration: Given noisy and/orpartial 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.Program10

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.

112

34

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

w1, 20 0
1 0
0 1

1 0

 w1, 2
 0D
 0

 00 0
w1, 2  1 0 0
02 0

00 1

1Graph Laplacian:w1, 2

 w1, 2
 wL   1, 2
 0
 00100 w1, 20
w1, 2  1  1 0 
12  10
1 1 0L3,: x   x2  2 x3  x4f x  h   2 f x   f x  h f  x   limh 0h2PKU Visit 09/02/2016*https://en.wikipedia.org/wiki/Second_derivative11

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

L ui  i ui

1234…

8eigenvector
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.
PKU Visit 09/02/2016
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:Lrw  D 1L  I  D 1 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," IEEESignal Processing Letters, vol.22, no.11, pp. 1913-1917, November 2015.

13

Outline• Graph Signal Processing• Graph spectrum• Graph-Signal Smoothness Prior• Graph Laplacian regularizer• LERaG• Soft Decoding of JPEG Images• Mixture of Priors

PKU Visit 09/02/2016

14

Graph Laplacian Regularizer

1w1, 21
2

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

12x 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] Jiahao Pang, Gene Cheung, "Graph Laplacian Regularization for Inverse Imaging: Analysis in the Continuous Domain," submitted
to IEEE Transactions on Image Processing, April 2016.

15

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 ij 2 
 i j 2wi , j  expexp  2

 12
2




2. Solve obj. in closed form:

min y  x 2   x T L x2x• 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.

16

Spectral Clustering• Normalized Cut [1]:
min Ncut A, B : cut A, B A, B11  vol  A vol B  cut  A, B  Wi, jiA, jBvol  A   Di ,iiA• Problem is NP-hard, so:

min normalized cut

1. Rewrite as:

f T Lfmin Tff Df

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

2. Relax to:f T Lfmin T
ff 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 cut

17

Eigenvectors of Normalized graph Laplacian• Define:v : D f
1/ 2min y  x 2   x T L n x
2v1 : D 1
1/ 2• Problem rewritten as:Tv
Ln v*v  arg min Tvv v

xcandidate objective

Rayleigh quotient

s.t. v v1  0T~2 k kk• 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.
PKU Visit 09/02/201618

Eigenvectors of random walk graph Laplacian• Random walk graph Laplacian Lrw is similar:L rw  D 1 / 2 L n D1 / 2• Let: L n  VVTeigen-decomposition• Lrw has left eigenvectors VT D1 / 2 :diagonal matrix
w/ eigenvalues

VT D1 / 2 L rw  VT D1 / 2 D 1 / 2 VVT D1 / 2  VT D1 / 2• Advantage:T

1/ 2• Constant signal 1 maps to V D•  V DT

1/ 2

1

1/ 2→ DTmaps to V → v1is sparse.

[1] Xianming Liu, Gene Cheung, Xiaolin Wu, Debin Zhao, "Random Walk Graph Laplacian based Smoothness Prior for Soft Decodingof JPEG Images," submitted to IEEE Transactions on Image Processing, July 2016.

19

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," submitted to IEEE Transactions on Image Processing, July 2016.

20

Frequency Interpretation of LERaG• Promote low graph frequencies:

projection of signal x
to left e-vectors

coeff of Lrm’s left e-vectors

e-values of Ln, Lrm• Fast implementation of LERaG:

inverse diagonalmatrix

PKU Visit 09/02/2016

combinatorial
Laplacian21

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

SymmetricNormalized

DC e-vector

Combinatorial

Yes

NoYes

Symmetrically Normalized

Yes

Yes

NoRandom 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 onImage Processing, vol. 23, no. 12, pp. 5136–5151, Dec 2014.

22 x x 2
 l l 2 ij 2 
 i j 2wi , j  expexp  2

 12
2



LERaG for PWC Signal• Construct fully connected graph for PWC signal:• 1st eigenvector for e-value = 0:

PWC signal: 2 constantpieces w/ large gap Δ• 2nd eigenvector for e-value = 0:

• Can be shown that
• LERaG evaluates to 0!

1 Td min   ~k2  k2  0kPKU Visit 09/02/201623

Outline• Graph Signal Processing• Graph spectrum• Graph-Signal Smoothness Prior• Graph Laplacian regularizer• LERaG• Soft Decoding of JPEG Images• Mixture of Priors

PKU Visit 09/02/2016

24

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,PKU Visit 09/02/2016

, 64.
25

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 Td min   ~k2  k2  0k

2. Solve per-patch signal
restoration problem w/
2 priors:
1. Sparsity prior
2. Graph-signal
smoothness prior
PKU Visit 09/02/2016

26

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.

PKU Visit 09/02/201627

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]

PKU Visit 09/02/2016

28

PSNR / SSIM Comparison

PKU Visit 09/02/2016

29

Subjective Quality Evaluation

PKU Visit 09/02/2016

30

Subjective Quality Evaluation

PKU Visit 09/02/2016

31

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

PKU Visit 09/02/2016

32

Summary• Graph Signal Processing (GSP)• Tools to process signals that live on graphs.

• Graph-signal Smoothness for Inverse Problems• New regularizer: LERaG• Normalized• Handles constant / PWC signals• Computation-efficient• Soft Decoding of JPEG Images• Mixture of Laplacian, sparsity, graph-signal smoothnessprior
PKU Visit 09/02/2016

33

Q&A

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

PKU Visit 09/02/201634