Continuous Domain Analysis of Graph
Laplacian Regularization for Image Denoisng

Presenter: Gene Cheung
National Institute of Informatics[1] Jiahao Pang, Gene Cheung, Wei Hu, Oscar C. Au, "Redefining Self-Similarity in Natural Images for
Denoising Using Graph Signal Gradient," in APSIPA ASC, Siem Reap, Cambodia, December, 2014.

GSP Workshop, 31 Oct 2014

Outline• Introduction• Convergence of theGraph Laplacian Regularizer• Justification of theGraph Laplacian Regularizer• Formulation and Algorithm• Experimental Results• Towards the Optimal
Graph Laplacian Regularizer• ConclusionBefore

AfterLena,   30
2

Outline• Introduction• Convergence of theGraph Laplacian Regularizer• Justification of theGraph Laplacian Regularizer• Formulation and Algorithm• Experimental Results• Towards the Optimal
Graph Laplacian Regularizer• Conclusion

BeforeAfterLena,   30
3

Motivation (I)• Image denoising—a basic restoration problem:
observationnoisey  xedesired signal• It is under-determined, needs image priors for regularization
fidelity term

min y  x 2   prior(x)2prior termx• Graph Laplacian regularizer: should be small for target patch xSG (x)  xT Lx

L  DAgraph Laplacian matrix• Many works use Gaussian kernel to compute graph weights [2]: dist i, j 2 
wij  exp2 dist(i, j ) is some distance metric between pixels i and j[2] D. Shuman, S. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: extending highdimensional data analysis to networks and other irregular domains,” IEEE Signal Processing Magazine, vol. 30, no. 3, pp. 83–98, 2013.

4

Motivation (II)• However…

a. Why is SG (x)  x T Lx a good prior?
b. Why using Gaussian kernel for edge weights?
c. How to design a discriminant x T Lx for restoration?
• We answer these by viewing• discrete graph as samples of high-dimensional manifold.

approximate

discrete graphcontinuous manifold

5Our Contributions
1. Using Gaussian kernel to compute graph weights, SG (x)  x T Lx
converges to a continuous functional S , which can beinterpreted as regularizer in continuous domain.
Graph Laplacianregularizer SG

converge

A continuous functionalS for regularization

2. Analysis of functional S provides understanding of what signals
are being discriminated and to what extent, on a point-by-point
basis in the continuous domain.
3. We design a discriminant S for regularization in continuous
domain, then obtain the graph Laplacian regularizer SG
Design discriminant S

obtainThe corresponding SG6

Outline• Introduction• Convergence of theGraph Laplacian Regularizer• Justification of theGraph Laplacian Regularizer• Formulation and Algorithm• Experimental Results• Towards the Optimal
Graph Laplacian Regularizer• Conclusion

BeforeAfterLena,   30
7

Road MapContinuous Domain

Discrete Domain

Choose the continuousNfeature functions{ f n }n 1Sample { f n }nN1 to obtain
Nthe discrete {f nD }n
1SAMPLEGet metric space G  R 22
on point-by-point basis

Obtain continuousfunctional S (h)Compute the weights
and Laplacian L  R M M

CONVERGE

Graph LaplacianRegularizer SG (h D )• Different { f n }nN1 leads to different regularization behavior!
8Graph Construction (I)RoadmapFeaturesSamples• First, define:• 2D domain   R— the shape of an image2•   si  [ xi yi ] | si  ,1  i  M T— a set of M random samples
uniformly distributed on  ,construed as pixel locations{ f n }nN1

N{f nD }n1Matrix
G  R 22Graph weights,and L  R M Mconverge

FunctionalRegularizerS  ( h)SG (h D )• (Freely) choose N continuous functions
f n ( x, y ) :   R , 1  n  N𝑦𝑓𝑛 (𝑥, 𝑦)called feature functions, can be• intensity for gray-scale image ( N  1)
• R, G, B channels for color image ( N  3 )Ω𝑂𝑥9

Graph Construction (II)• Sampling f n at positions in  gives N
discretized feature functions
f nD  [ f n ( x1 , y1 ) f n ( x2 , y2 )  f n ( xM , yM )]T
𝑓𝑛 (𝑥, 𝑦)𝑦𝑓𝑛 (𝑥𝑖 , 𝑦𝑖 )Roadmap
Features
Samples{ f n }nN1

N{f nD }n1Matrix
G  R 22Graph weights,and L  R M Mconverge𝒔𝑖𝑂Ω

FunctionalRegularizerS  ( h)SG (h D )𝑥

• For each pixel location si  , define a length N  2 vectorv i  [ xi yi  f1D (i )  f 2D (i )   f ND (i )]T is a tunable constant• Build a graph G with M vertices, each pixel location si have a vertex Vi10

Graph Construction (III)Roadmap
FeaturesSamples• Weight between vertices Vi and V j{ f n }nN1

N{f nD }n1Matrix
G  R 22Graph weights,and L  R M Mdegree before normalization

i   j 1 (dij )mwij  ( i  j )   (dij )converge

normalization factor FunctionalRegularizerS  ( h)SG (h D )clipped Gaussian kernel d2 exp   2 
 (d )   2・ 0

2d  r,distance dij2  v i  v j 2otherwise

 si  s j

where r   Cr and Cr is a constant22  2  n 1 (f nD (i )  f nD ( j )) 2N• G is an r-neighborhood graph, i.e., no edge connecting twovertices with distance greater than r
11Graph Construction (IV)RoadmapFeatures
Samples• Our graph G is very general• e.g., choose a small  with proper r ,obtain the 2D grid graph{ f n }nN1

N{f nD }n
1MatrixG  R 22Graph weights,and L  R M Mconverge• A — its (i, j ) entry is wijm(i,j)—
its
entryisD j 1 wij

FunctionalRegularizerS  ( h)SG (h D )unnormalized Graph
Laplacian L  D  A• h( x, y ) :   R is a continuous candidate functionh D  [h( x1 , y1 ) h( x2 , y2 )  h( xM , yM )]T — samples of h( x, y )• SG (h )  (h ) Lh — graph Laplacian regularizer, a functional on R M
DD TD

12

Convergence of the Graph Laplacian Regularizer (I)Roadmap
Features
Samples• The continuous counterpart of SG is afunctional S on domain S (h)   (h) G (h)T1 det G  dxdy

{ f n }nN1

N{f nD }n1Matrix
G  R 22Graph weights,and L  R M M2 1h  [ x h  y h]T is the gradient of hconverge• G is a 2-by-2 matrix:  N   x f n 2n 1G  I2  N  n 1  x f n · y f nFunctionalRegularizerS  ( h)SG (h D )

  f · f 
 I    f · f   f  Nn 1x ny2Nn 12x2 identitymatrixnyn

N2n 1nTn

Structure tensor [3] of thegradients {f n ( x, y )}nN1• G is computed from {f n }n 1 on a point-by-point basis
N[3] H. Knutsson, C.-F. Westin, and M. Andersson, “Representing local structure using tensors ii,”
in Image Analysis. Springer, 2011, vol. 6688, pp. 545–556.

13

Convergence of the Graph Laplacian Regularizer (II)• Theorem : convergence of SG to S

M 2 1
lim 4 1 SG h D  ~ S h M  M  1 0RoadmapFeatures
Samples{ f n }nN1

N{f nD }n1Matrix
G  R 22Graph weights,and L  R M M

number of samples M increases

neighborhood r   Cr shrinks“~” means there exist a constantsuch that equality holds.

converge

FunctionalRegularizerS  ( h)SG (h D )• With results of [4], we proved it by viewing a graph as proxy of anN  2 -dimensional Riemannian manifold
Vertex

Coordinate on Ω

Coordinate on (N+2)-D manifold

Visi   xi , yi v i  [ xi yi  f1D (i )  f 2D (i )   f ND (i )]T[4] M. Hein, “Uniform convergence of adaptive graph-based regularization,” in Learning Theory. Springer, 2006, pp. 50–64.

14Outline• Introduction• Convergence of theGraph Laplacian Regularizer• Justification of theGraph Laplacian Regularizer• Formulation and Algorithm• Experimental Results• Towards the Optimal
Graph Laplacian Regularizer• Conclusion

BeforeAfterLena,   30
15

Justification of Graph Laplacian Regularizer (I)S (h)   (h) G (h)T1 det G G  I   2  n 1 f n · f n N2 1dxdy

RoadmapFeatures
Samples{ f n }nN1

N{f nD }n1Matrix
G  R 22Graph weights,and L  R M M

TSG (h D )  (h D )T Lh Dconverge• SG converges to S ,With S , any new insights wecan gain on SG ??

FunctionalRegularizerS  ( h)SG (h D )• The eigen-space of G reflects statistics of {f n }nN1•(h)T G 1 (h) measures length of h in a metric spaceestablished by G !

•S integrates the gradient norm
16

Justification of Graph Laplacian Regularizer (II)• Metric space defiendby G

𝜕𝑦Ellipses are norm-balls, reflects
Nhow concentration of {f n }n 1Green dots are {f n ( x, y )}nN1𝑙

𝜕𝑥𝑂l: Eigenvector corresponds tothe largest eigenvalue of G,
goes through the cluster of {f n }nN.1S (h)   (h) G (h)T1 det G G  I   2  n 1 f n · f n N2 1

dxdy

T

17

Justification of Graph Laplacian Regularizer (III)• The 2D metric space provides a clear picture of what signals arebeing discriminated and to what extent, on a point-by-point basis
in the continuous domain!
𝜕𝑦𝜕𝑦𝜕𝑥𝑙𝑂𝜕𝑥𝑂𝑙(a)(b)• (a) is more skewed, or discriminant, than (b)• In (a), a small distance away from the direction
orthogonal to l brings large metric distance18

Justification of Graph Laplacian Regularizer (IV)• Lesson: Select feature functions properly!
• Suppose A is the truth gradient, choose { f n }n 1 such thatN• (i) l goes through A;
𝜕𝑦(ii) Ellipses stretched flat along l.
𝐴

𝜕𝑦𝐴𝑙

𝜕𝑥

𝜕𝑥𝑙

𝑂

𝑂(a) A good scheme, {f n }n1 aresimilar to the ground-truth AN(b) A bad scheme…

• For the case of discrete images, one can seek forsimilar patches in terms of gradient!
19Outline• Introduction• Convergence of theGraph Laplacian Regularizer• Justification of theGraph Laplacian Regularizer• Formulation and Algorithm• Experimental Results• Towards the Optimal
Graph Laplacian Regularizer• Conclusion

BeforeAfterLena,   30
20

Problem Formulation and Algorithm Development• Adopt a patch-based recovery framework to denoise the image• For a noisy patch p 0 on the image
1.

Assume a “self-similar-in-gradient” image model, search for K  1
patches similar to p 0 in terms of gradient in pre-filtered image.

2.

Compute graph Laplacian from the similar patches.

3.

Solve the unconstrained quadratic optimization iteratively:q ・  arg min p 0  q 2  q T Lq
2q

to obtain the denoised patch q・• Aggregate denoised patches to form an updated image.
• Denoise the given image iteratively to gradually enhance its quality.
• Our denoising method is named
Graph-based Denoising using Gradient-based Self-similarity (GDGS)
21Outline• Introduction• Convergence of theGraph Laplacian Regularizer• Justification of theGraph Laplacian Regularizer• Formulation and Algorithm• Experimental Results• Towards the Optimal
Graph Laplacian Regularizer• Conclusion

BeforeAfterLena,   3022

Experimental Results (I)• Test images: Lena, Barbara, Boats and Peppers• i.i.d. Additive White Gaussian Noise (AWGN)• Non-Local GBT (NLGBT) – an existing graph-based denoising method [5]• Compared to BF, NLM and NLGBT

1.4 dB better
than NLM!

Performance comparisons in PSNR (dB)
ImageStandard DeviationMethod15LenaBarbara

Boats

Peppers

2030

GDGS

NLM

33.47

32.03

32.35

31.51

30.61

29.45

BF

NLGBT

27.00

33.22

24.80

31.90

21.52

30.19

GDGS

NLM

31.71

30.76

30.33

30.15

28.33

27.91

BF

NLGBT

25.78

31.22

23.86

29.62

21.03

27.67

GDGS

NLM

31.59

30.69

30.30

29.74

28.55

27.68

BF

NLGBT

26.42

31.05

24.89

29.56

22.19

27.77

GDGS

NLM

33.30

31.96

32.38

31.48

30.83

29.50

BF

NLGBT

28.96

33.18

24.67

32.09

21.49

30.49

[5] W. Hu, X. Li, G. Cheung, and O. Au, “Depth map denoising using graph-based transform and group sparsity,”in IEEE Int’l Workshop on Multimedia Signal Processing, 2013.

23

Experimental Results (II)• GDGS vs NLM• GDGS vs NLGBT

GDGS

NLGBT

GDGS (31.39 dB)

NLM (30.38 dB)

GDGS

NLGBT

GDGS (29.34 dB)

NLM (28.62 dB)

Noise standard deviation   2524

Outline• Introduction• Convergence of theGraph Laplacian Regularizer• Justification of theGraph Laplacian Regularizer• Formulation and Algorithm• Experimental Results• Towards the Optimal
Graph Laplacian Regularizer• Conclusion

BeforeAfterLena,   3025

Towards Optimal Graph Laplacian Regularization• Our latest work [6] derives the optimal metric space G ・, leading
to optimal graph Laplacian regularization for denoising.
𝜕𝑦𝜕𝑦

𝜕𝑦

𝜕𝑥

𝑂

𝜕𝑥𝑙𝑙

𝜕𝑥

𝑂𝑂𝑙

• Metric space should be discriminant to the extent that
estimates of ground-truth gradient are reliable.
posterior prob. of ground truthG ・  arg min  G  G 0 (g ) F Pr g | g k k 0 dg
2G∆—whole gradient domainK 1ideal metric space given ground truth g[6] Jiahao Pang, Gene Cheung, Antonio Ortega, Oscar C. Au, "Optimal Graph Laplacian Regularization
for Natural Image Denoising," submitted to IEEE ICASSP, Brisbane, Australia, April, 2015.

26

Outline• Introduction• Convergence of theGraph Laplacian Regularizer• Justification of theGraph Laplacian Regularizer• Formulation and Algorithm• Experimental Results• Towards the Optimal
Graph Laplacian Regularizer• Conclusion

BeforeAfterLena,   3027

Conclusion• Image denoising is an ill-posed problem and requires good priors
for regularization.
• graph Laplacian regularizer with Gaussian kernel weights
converges to a continuous functional.
• Analysis of the continuous functional provides theoreticaljustification of why and under what conditions the graph Laplacian
regularizer can be discriminant.
• Our denoising algorithm with graph Laplacian regularizer andgradient-based similarity out-performs NLM by up to 1.4 dB.
• Our latest work obtains the optimal graph Laplacian, which isdiscriminant when the estimates are accurate, and robust whenthe estimates are not.
BeforeAfter28

Thank You!
Contact: Gene Cheung (cheung@nii.ac.jp)
Jiahao Pang (jpang@ust.hk)

GSP Workshop, 31 Oct 2014