Random Walk Graph Laplacian based Smoothness
Prior for Soft Decoding of JPEG Images
Xianming Liu

http://homepage.hit.edu.cn/pages/xmliu
http://arxiv.org/abs/1607.01895
ICME2016 TutorialOverview Background Popular Priors

 Laplacian Prior Sparsity Prior Graph-signal Smoothness Prior Random Walk Graph Laplacian Regularizer
 Soft Decoding based on Priors Mixture Experimental Results
 Conclusion

ICME2016 Tutorial

Background Compressed image restoration: important and practicalproblem: Compression is the most common cause of image degradation.
 Compression is indispensable in almost all visual communication
systems.

 Compressed image restoration is a non-trivial problem: Compression noises are signal-dependent.
 Far from being white and independent.
 Composite noises: blocking and ringing effects.

ICME2016 Tutorial

JPEG Image Restoration
 Problem Formulation
Encoder:DCT

qi  round (Yi / Qi ), Y =Tyquantization parameter

DCT Coefficients

8x8 pixel block

Decoder: the quantization bin (q-bin) constraint

qi Qi  Yi  (qi  1) Qi , i  1, 2, , 64.

ICME2016 Tutorial

Hard Decoding vs. Soft Decoding Hard Decoding Reconstruct DCT coefficients using thecenters of assigned quantization bins.

 Soft Decoding Find the most probable signal WITHIN
the set of quantization bin constraints.
 Signal priors is used for aid-Laplacian [Lam and Goodman, TIP’00]
Local/non-local similarity [Zakhor, TCSVT’92]

JPEG

Soft decoding

JPEG
55Soft decoding[Zhai et al., TCSVT’08, TMM’08] [ Zhang et al., TIP’14]

Total Variation [Bredies, SIAM J. Img. Sci’12]
Sparsity [Jung et al., SPIC’12] [Liu et al., CVPR’15, TIP’16 ]Sparsity + TV [Chang et al. TSP’15]
Low-rank Prior [Zhao et al., TCSVT’16][Zhang et al,TIP’16]

ICME2016 Tutorial

Related Work of Graph-based Image
Restoration and Enhancement
 Denoising [Hu et al., MMSP’14, ICIP’14], [Pang et al. APSIPA’14,
ICASSP’15]

 Super-resolution [Mao et al., GlobalSIP’13, 3DTV’14]
 Dequantization [Liu et al, ICIP’15][Hu et al.,SPL’16]
 Deblurring [Kheradmand and Milanfar, TIP’14]
 Bit-depth Enhancement [Wan et al., TIP’16]
 Joint Denoising and Contrast Enhancement [Liu et al.,ICASSP’15]

ICME2016 Tutorial

MAP Formulation
Maximum a posterior (MAP):

The likelihood is defined as: patch surrounds block x is the basic processing unit

MAP formulation becomes

ICME2016 TutorialLaplacian Prior Q-bins: constrain the search space of individual DCT coefficients Laplacian Prior: states the probability density function of individual
DCT coefficients
 MMSE Formulation[Lam and Goodman, TIP’00]

 Closed-form Solution

For higher frequencies, the Laplacian parameter is larger;
i.e., the distribution is sharper and more skewed to 0.
ICME2016 TutorialLaplacian Prior Advantageclosed-form MMSE solution
smaller expected squared error than a MAP solution

 Limitation

can only be used to recover code blocks separately
cannot handle block artifacts that occur across adjacent blocks

 Solution

 We turn to employ the sparsity prior at a larger patch level x.

ICME2016 TutorialSparsity Prior Sparse Signal Modelover-complete dictionary

sparse code

 Sparse Coding orthogonal matching pursuit (OMP) [Cai and Wang, TIT’11]
 computational complexity is linear with the size of dictionary

 Sparsity Prior

ICME2016 TutorialSparsity-based Soft Decoding

 Step 1–Initial Estimation: The Laplacian prior is used to get an initialestimation of x.
 Step 2–Sparse Decomposition:
 Step 3–Quantization Constraint:

Lemma 1: The sparsity-based soft decoding
algorithm converges to a local minimum.
ICME2016 Tutorial

Limitation of Small KSVD Dictionary
 Complexity linearly increases with the size of dictionary.
 In practice, a just reasonable over-complete dictionary is used.
 KSVD Dictionary Training

Training pixel patchDCT patch

Parsavel’s theorem
pre-set sparsity limit

We analyze the behavior of dictionary
learning in frequency domain
ICME2016 Tutorial

Limitation of Small KSVD Dictionary
When K = 1, dictionary learning becomes
vector quantization (VQ) design problem

 Selecting M atoms is analogous to designing M partitions

ICME2016 Tutorial

Limitation of Small KSVD Dictionary
When K = 1, dictionary learning becomes
vector quantization (VQ) design problem

 Selecting M atoms is analogous to designing M partitions
 When N tends to infinite:
Expected square error

a product of Laplacian distributions for individual DCT frequencies• low frequencies: decay slowly• high frequencies: more skewed and concentrated around zero
ICME2016 Tutorial

Limitation of Small KSVD Dictionary When the number of atoms is small
 quantization is coarser for large
magnitude in AC than DC

When the dictionary Φ is small, thesparsity prior is difficult to recoverlarge magnitude of high DCT
frequencies.

 When the dictionary is large enough
Illustration of product VQ for DC and AC frequencies

 quantization for large magnitude inhigh frequency is sufficiently fine.

When the dictionary Φ is large
enough, the sparsity prior canrecover large magnitude of high DCTfrequencies well.

ICME2016 TutorialEmpirical Observation
 Mean Frequency

DCT frequency

DCT coefficientof atom

1000

ICME2016 Tutorial

7000

Empirical Observation
 Mean Frequency

DCT frequency

DCT coefficientof atom

When dictionary is small, the mean frequency ofatoms is low, the sparsity prior cannot recover high
DCT frequencies well.1000

ICME2016 Tutorial

7000

Three Priors Complement Each OtherICME2016 TutorialGraph-signal Smoothness Prior Graph Laplacian Regularizer Different graph Laplacian matrixesCombinatorial graph Laplacian:Symmetrically normalized graph Laplacian:Random walk graph Laplacian:Doubly stochastic graph Laplacian:Graph Laplacian

Symmetric

Symmetrically Normalized

Yes

No

Doubly StochasticYes

Yes

Combinatorial

Random WalkYes
No

ICME2016 Tutorial

DC eigenvector

Yes
Yes

[Kheradmand and Milanfar, TIP’14]

Graph-signal Smoothness Prior Graph Frequency Interpretation
 Eigen decomposition:•eigenvalues carry the notion of frequency

 Graph Fourier transform: We get Minimizing
will suppress high graph frequencies andpreserve low graph frequencies.

 x is smoothened with respect to the graph PWS signals can be well approximated by low graph frequencies
for appropriately constructed graphs. [Hu et al., MMSP’14, ICIP’14]
 Discontinuities inside PWS signals translate to high DCTfrequencies.
ICME2016 TutorialWhy Graph Prior Works Wellfor PWS Signals?
 Spectral clustering: given a similarity graph, separate its vertices intotwo subsets of roughly the same size via spectral graph analysis.
 Normalized cut (Ncut) [Shi and Malik, TPAMI’00]
Relaxed solution of Ncut!

NP-hard!

wherePWC!

ICME2016 Tutorial

Interpretation from the Perspective ofSpectral Clustering
Rayleigh quotientwith respect to v1 minimizes the objective, since

v1 is the first eigenvector of

 v is orthogonal to v1 , according to Rayleigh quotient, the solution
is the second eigenvector of
The second eigenvector v2 of Ln is a relaxedsolution to the Ncut problem, which is PWS;
if the solution becomes exact, then v2 is PWC.

 Low graph frequencies ofrepresent PWS signals.

thus are suitable to compactly

ICME2016 Tutorial

Random Walk Graph Laplacian The first eigenvector of ,, is not a constantvector does not have DC component  notsuitable for filtering natural images.
 Matrix similarity transformation1
has the left eigenvectors

Random walk graphLaplacian!

 GFT using the left eigenvectors
1https://en.wikipedia.org/wiki/Matrix_similarity

ICME2016 Tutorial

Random Walk Graph Laplacian However,is asymmetric, there is no clear interpretation ingraph frequency domain of.

 We use

instead, and can derive:

ICME2016 Tutorial

Random Walk Graph Laplacian We have a graph frequency interpretation of our Left Eigenvector
Random-walk Graph Laplacian (LERaG):
high frequencies of random walk graph Laplacianare suppressed to restore smooth signal x
 The proposed regularizer can be efficiently computed as:

Only adjacency matrix is involved, noneed to compute other matrix
ICME2016 Tutorial

Advantages of the Proposed
Graph Laplacian Compared with combinatorial graph Laplacian

Our Laplacian is based on random walk graph Laplacian (normalized),therefore, it is insensitive to the degrees of graph vertices.

 Compared with normalized graph Laplacian

Our Laplacian can efficiently filter constant signals, thus is suitable forimage filtering.

 Compared with doubly stochastic graph Laplacian
Our Laplacian can be computed simply.
ICME2016 Tutorial

Analysis of Ideal Piecewise
Constant Signals
 1D Piecewise constant (PWC) signal
 A full-connected graph is built

 The first eigenvector
 The second eigenvector

PWC

 We can see thatICME2016 Tutorial

Analysis of Ideal Piecewise
Constant Signals
Given an ideal two-piece PWC signal x, D1/2x
can be represented exactly using the first twoeigenvectors of Ln corresponding to eigenvalue0, hence LERaG evaluates to 0.


is a ideal low-pass given eigenvectors of There is no penalty for LERaG.

ICME2016 Tutorial

Analysis of Piecewise
Smooth Signals
 1D piecewise smooth (PWS) signal:
 A full-connected graph is built
 The normalized graph Laplacian The second eigenvector

is still block-diagonal
Roughly PWS

is also roughly PWS:
 There is a small penalty of LERaG.
ICME2016 Tutorial

Analysis of Ideal Piecewise
Smooth Signals

ICME2016 Tutorial

Soft Decoding via Priors Mixture The objective function

 λ1 is fixed We adaptively increase λ2 if q-bin indices q indicate thepresence of high DCT frequencies in target x.

 Optimization

 Laplacian prior provides an initial estimation;
 Fix x and estimate α; Fix α and estimate x.

ICME2016 Tutorial

Experimental Results

 Compared methods

 BM3D: well-known denoising algorithm
 KSVD: with a large enough over-complete dictionary (100x4000);
our method 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]
ICME2016 TutorialPSNR and SSIM Evaluation

ICME2016 TutorialQF-PSNR Evaluation

ICME2016 TutorialSubjective Quality Evaluation

ICME2016 TutorialSubjective Quality Evaluation

ICME2016 Tutorial

Other Comparison
 Computation complexity comparisonTIME

Average

BM3D

373.35KSVD

209.71

ANCE

307.43

DicTV

39.53

 Comparison with other graph regularizers

ICME2016 Tutorial

SSRQC
70.32

Proposed

143.73

Conclusion
 We propose a new graph-signal smoothness prior basedon left eigenvectors of the random walk graph Laplacian.

 with desirable image filtering properties can recover high DCT frequencies of piecewise smooth signals
well can be used in other image restoration or general GSP tasks

 We combine the Laplacian prior, sparsity prior and our newgraph-signal smoothness prior into an efficient JPEG
images soft decoding algorithm.

ICME2016 Tutorial

Thanks! Any Question?
xmliu.hit@gmail.com

ICME2016 Tutorial