6082 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 29, 2020
Abstract—Recently, many fast implementations of the bilateral
and the nonlocal filters were proposed based on lattice and vector
quantization, e.g. clustering, in higher dimensions. However, these
approaches can still be inefficient owing to the complexities in the
resampling process or in filtering the high-dimensional resampled
signal. In contrast, simply scalar resampling the high-dimensional
signal after decorrelation presents the opportunity to filter signals
using multi-rate signal processing techniques. Cis work proposes
the Gaussian lifting framework for efficient and accurate bilateral
and nonlocal means filtering, appealing to the similarities between
separable wavelet transforms and Gaussian pyramids. Accurately
implementing the filter is important not only for image processing
applications, but also for a number of recently proposed bilateral-
regularized inverse problems, where the accuracy of the solutions
depends ultimately on an accurate filter implementation. We show
that our Gaussian lifting approach filters images more accurately
and efficiently across many filter scales. Adaptive lifting schemes
for bilateral and nonlocal means filtering are also explored.
Index Terms—Nonlinear filtering, inverse problems, Gaussian
pyramids, wavelet transforms
!" !!"#$%&'"($!#
$%#&'()*+,)(#-(*+,#'.#)#/0/1('/+),#-(*+,#*2)*#3)/#.400*2#0,#
5+/0'.+# '4)6+.# 72'(+# 8,+.+,9'/6#+56+."# :',.*# '/*,05;3+5#
&<#=;,'32#)/5#>+;(+#?@A#).#*2+#/0/('/+),#B);..')/#-(*+,C#'*#7).#
()*+,#,+15'.309+,+5#&<#D4'*2#)/5#E,)5<#?FA#;/5+,#*2+',#DGD=H#
I,)4+70,J"#K+#8,+.+/*#/)4+#L&'()*+,)(#-(*+,M#'.#5;+#*0#N04).'#
)/5#O)/5;32'#?PA"#=.#)((;5+5#*0#&<#*2+#0,'6'/)(#/)4+C#&'()*+,)(#
-(*+,'/6#+..+/*')((<#)5)8*.#'*.#B);..')/#-(*+,#J+,/+(#*0#*2+#'/8;*#
'4)6+C#,+5;3'/6#*2+#-(*+,#.*,+/6*2#)3,0..#*2+#'4)6+#+56+."#Q;+#
*0#*2+#+56+18,+.+,9'/6#8,08+,*<C#&'()*+,)(#-(*+,'/6#'.#30440/(<#
;.+5#'/#'4)6+#8,03+..'/6#*).J.#?RAS?TA#)/5#)#/;4&+,#0I#9'.'0/1
,+()*+5#)88('3)*'0/.#?UAS?@VA"#N70# 7+((1J/07/#6+/+,)('W)*'0/.#
0I#*2+#&'()*+,)(#-(*+,#),+X#*2+#Y0'/*#&'()*+,)(#-(*+,#?RAC#?TAC#72'32#
5+,'9+.#*2+#+56+#'/I0,4)*'0/#I,04#)/0*2+,#'4)6+C#)/5#*2+#/0/1#
(03)(#4+)/.#5+/0'.'/6#-(*+,.#?@@AC#?@FAC#8,080.+5#0,'6'/)((<#&<#
E;)5+.#et al"#?@PA#)/5#=7)*+#)/5#>2'*)J+,#?@RA"#K+#/0/1(03)(#
4+)/.#-(*+,C#'/#8),*'3;(),C#4)<#&+#.++/#).#)#2'62+,15'4+/.'0/)(#
6+/+,)('W)*'0/#0I#*2+#&'()*+,)(#-(*+,C#720.+#80'/*17'.+#&'()*+,)(#
.'4'(),'*<#4+).;,+#'.#,+8()3+5#;.'/6#)#8)*3217'.+#0/+"#>+#,+I+,#
*2+#,+)5+,#*0#*2+#*;*0,')(.#&<#Z),'.#et al.#?@[A#)/5#O'()/I),#?@\A#
I0,#)/#+]*+/.'9+#,+9'+7#0I#&'()*+,)(C#/0/1(03)(#4+)/.#5+/0'.'/6#
)/5#0*2+,#,+()*+5#-(*+,.C#).#7+((#).#*2+',#)88('3)*'0/."#
# G/I0,*;/)*+(<C#&'()*+,)(#-(*+,'/6#'.#3048;*)*'0/)((<#'/*+/.'9+#
'I#'*.#;/5+,(<'/6#B);..')/#J+,/+(#2).#)#(),6+#.;880,*"#>2+/#*2+#
-(*+,#'.#'48(+4+/*+5#5',+3*(<C#*2+#3048;*)*'0/)(#3048(+]'*<#0I#
*2+#&'()*+,)(#-(*+,#6,07.#^;)5,)*'3)((<#7'*2#*2+#J+,/+(#.'W+C#)/5#
*2'.#8,+3(;5+.#*2+#;.+#0I#*2+#-(*+,#72+/#*2+#,+^;',+5#J+,/+(#2).#
)#.;880,*#).#(),6+#).#*2+#'4)6+#'*.+(I#I0,#+])48(+"#=#/;4&+,#0I#
+_3'+/*#&'()*+,)(#-(*+,'/6#'48(+4+/*)*'0/.#2)9+#*2+,+I0,+#&++/#
8,080.+5#?@TAS?FRAC#)((#0I#72'32#+]8(0'*#*2+#I)3*#*2)*#-(*+,'/6#)#
2'6215'4+/.'0/)(#.'6/)(#;.'/6#)#(),6+#B);..')/#J+,/+(#3)/#)(.0#
&+#)32'+9+5#&<#`'a#507/1.)48('/6#*2+#'/8;*#.'6/)(C#`''a#-(*+,'/6#
*2+#507/1.)48(+5#.'6/)(#7'*2#)#B);..')/#&(;,#J+,/+(C#)/5#*2+/#
`'''a#;81.)48('/6#*2+#-(*+,+5#.'6/)("#D;32#)#.+,'+.#0I#08+,)*'0/.#
'.#0I*+/#,+I+,,+5#*0#).#*2+#.8()*1&(;,1.('3+#8'8+('/+"#K'.#8'8+('/+##
3)/#)(.0#&+#;.+5#*0#)33+(+,)*+#0*2+,#2'6215'4+/.'0/)(#B);..')/#
-(*+,.#.;32#).#/0/(03)(#4+)/.#?@PAC#*<8'3)((<#'48(+4+/*+5#).#)#
.']1#*0#+'62*15'4+/.'0/)(#B);..')/#-(*+,#?F[A"#=#/;4&+,#0I#I).*#
4+*205.#?F\AS?PVA#),+#.8+3'-3#*0#-(*+,'/6#6,)<.3)(+#'4)6+."#
# :).*#&'()*+,)(#-(*+,'/6#4+*205.#?@TAS?FRA#&).+5#0/#*2+#.8()*1
&(;,1.('3+#8'8+('/+#*2;.#5'b+,#40.*(<#'/#*2+',#'48(+4+/*)*'0/#0I#
&(;,,'/6#)/5#,+.)48('/6"#c+.)48('/6#'.#*<8'3)((<#'48(+4+/*+5#
;.'/6#.3)(),#,+.)48('/6#?@TAC#?@dAC#()**'3+#,+.)48('/6#?F@AC#)/5#
40,+#6+/+,)(#9+3*0,#,+.)48('/6#?FPAC#?FRA#72+,+).#*2+#&(;,,'/6#
08+,)*0,.#),+#0I*+/#'48(+4+/*+5#).#)#.+,'+.#0I#0/+15'4+/.'0/)(#
30/90(;*'0/.#?@dAC#?F@AC#0,#9')#O0/*+#e),(0#.)48('/6#?FVA"#K+#
.8()*1&(;,1.('3+#.*,)*+6<#;.+5#5+*+,4'/+.C#'/#*;,/C#*2+#08*'4;4#
5)*)#.*,;3*;,+#I0,#,+8,+.+/*'/6#*2+#,+.)48(+5#.'6/)("#$).24)8.#
)/5#*,++.#),+#*70#30440/#320'3+.#0I#/0/('/+),#5)*)#.*,;3*;,+."#
# $07+9+,C#'*#'.#7+((1J/07/#I,04#)#.0;,3+#305'/6#8+,.8+3*'9+#
) *+,-./0123)04/41546)7-8-.3)9:;)9<=>?)0451.46)@4A0-+0B)9C;)9<9<?)+//42346)
*+0/D)9C;)9<9<E)%+34)FG)2-AH1/+31F,)7201H)=C;)9<9<?) 6+34)FG) /-004,3)540.1F,)
*+B)=;)9<9<E)I4)+..F/1+34)4613F0)/FF061,+31,8)3D4)04514J)FG)3D1.)K+,-./0123)
+,6) +220F51,8) 13) GF0) 2-AH1/+31F,) J+.L) %0E) 'D+,60+) M4ND+0) M44H+K+,3-H+E)
(Corresponding author: Sean I. Young.)
) M4+,) (E) OF -,8 ) +,6) P40,6) Q10F6) +04) J13D) 3D4) (,GF0K+31F,) MB.34K.) R+AFS
0+3F0B;) %42+03K4,3) FG) TH4/301/+H) T,81,4401,8;) M3+,GF06) &,1540.13B;) M3+,GF06;))
'7)>UC<V)&M7)W4SK+1HL).4+,<X.3+,GF06E46-;)A810F6X.3+,GF06E46-YE)
) %+516)"+-AK+,) 1.) J13D) 3D4) M/DFFH) FG) TH4/301/+H) T,81,4401,8)+,6)"4H4/FKS
K-,1/+31F,.;) &,1540.13B) FG) !4J) MF-3D)Z+H4.;)MB6,4B;) !MZ) 9<V9)7-.30+H1+)
W4SK+1HL)6E3+-AK+,X-,.JE46-E+-YE)
) %1813+H)$A[4/3)(64,31\40)=<E==<>]"(^E9<9<E9>:UCV_)
Gaussian Lifting for Fast Bilateral
and Nonlocal Means Filtering
Sean I. Young , Member, IEEE, Bernd Girod , Fellow, IEEE, and David Taubman , Fellow, IEEE
T
@18E)=E)$-0)A1H+340+H)\H3401,8)2124H1,4E)Z4)04.+K2H4)3D4).18,+H)F,3F)3D4)54031/4.)
FG)+)`R"S0F3+346)H+331/4)WH4G3Y;)+,6)AH-0)3D4)04.+K2H46).18,+H).42+0+34HB)1,)3D4)
.2+31+H)𝑥
)+,6)0+,84)
𝑧
1
′
, 𝑧
2
′
)61K4,.1F,.)1,)+)K-H31S./+H4)G+.D1F,)W018D3YE#
Level 1
Level 0
Rotated resampling Multi-scale blurring
𝑥, 𝑧
1
′
, 𝑧
2
′
𝑧
1
′
=<V_S_=U>) a) 9<9<) (TTTE) ^40.F,+H)-.4) 1.) 240K13346;) A-3) 042-AH1/+31F,]0461.301A-31F,) 04b-104.) (TTT) 240K1..1F,E)
M44) D332.L]]JJJE1444EF08]2-AH1/+31F,.]018D3.]1,64cED3KH) GF0) KF04) 1,GF0K+31F,E
)
YOUNG et al.: GAUSSIAN LIFTING FOR FAST BILATERAL AND NONLOCAL MEANS FILTERING 6083
#
*2)*#.3)(),#,+.)48('/6#)I*+,#5+30,,+()*'0/#3)/#8+,I0,4#.'4'(),(<#
*0#9+3*0,#,+.)48('/6#`'/#*+,4.#0I#,)*+#)/5#5'.*0,*'0/a#?P@A"#K'.#
.;66+.*.#*2)*#&'()*+,)(#-(*+,'/6#4+*205.#&).+5#0/#5+30,,+()*'0/#
)/5#.'48(+#.3)(),#,+.)48('/6#.20;(5#8+,I0,4#.'4'(),(<#*0#40,+#
,+3+/*#0/+.#&).+5#0/#3(;.*+,'/6"#D'48(+#.3)(),#,+.)48('/6#)(.0#
8,09'5+.#'/*+,+.*'/6#0880,*;/'*'+.#I0,#&(;,,'/6f.'/3+#(0718)..##
-(*+,'/6#,+5;3+.#*2+#&)/57'5*2#0I#*2+#.'6/)(C#7+#3)/#&(;,#40,+#
+_3'+/*(<#&<#8,06,+..'9+(<#5+3,+).'/6#*2+#.)48('/6#,)*+#0I#*2+#
'/*+,4+5')*+#&(;,,+5#0;*8;*."#!*#'.#*2+.+#8,'/3'8(+.#I,04#.0;,3+#
305'/6#*2)*#6;'5+#0;,#I).*#'48(+4+/*)*'0/#0I#*2+#&'()*+,)(#-(*+,"#
# !/#*2'.#70,JC#7+#8,+.+/*#0;,#I,)4+70,J#I0,#I).*#)/5#)33;,)*+#
&'()*+,)(#)/5#2'6215'4+/.'0/)(#B);..')/#-(*+,'/6#9')#('I*'/6"#!/#
4;(*',)*+#.'6/)(#8,03+..'/6C#)#('I*'/6#.32+4+#'.#)#I).*#)(60,'*24#
*0#3048;*+#*2+#7)9+(+*#*,)/.I0,4#0I#)#.'6/)(C#;.+5#'/#*2+#gZ%B#
FVVV#'4)6+#3048,+..'0/#.*)/5),5#?PFA#I0,#+])48(+"#>+#)88+)(#
*0#*2+#.'4'(),'*'+.#&+*7++/#)#B);..')/#8<,)4'5#)/5#*2+#7)9+(+*#
*,)/.I0,4#*0#30/.*,;3*#)/#+_3'+/*#4;(*'15'4+/.'0/)(#4;(*'1,)*+#
'48(+4+/*)*'0/.#0I#*2+#&'()*+,)(#)/5#/0/(03)(#4+)/.#-(*+,."#>+#
.;44),'W+#)/5#'((;.*,)*+#0;,#09+,)((#-(*+,#8'8+('/+#'/#:'6"#@"#
!!" cTR7"T%)>$#`#
# K+#+),('+.*#)88,0)32+.#*0#)33+(+,)*'/6#&'()*+,)(#-(*+,'/6#),+#
I0,#6,)<.3)(+#'4)6+.C#)/5#'/90(9+#)88,0]'4)*'0/.#0I#*2+#,)/6+#
J+,/+(.#9')#&).'.#+]8)/.'0/."#Z0,'J('#?F\A#;.+5#80(</04')(.#I0,#
*2+#&).'.#+]8)/.'0/C#)/5#e2);52;,<#et al.#?FTAC#)#*,'60/04+*,'3#
&).'."#D;&.+^;+/*(<C#Z)8),'#et al"#?PVA#8,080.+5#)#/0/1.2'I*)&(+#
&).'.#08*'4'W+5#I0,#6'9+/#'4)6+#.*)*'.*'3.C#)/5#e2);52;,<#)/5#
Q)&2)5+#?PPA#)#B);..')/#&).'.C#72'32#7).#+]*+/5+5#'/#*;,/#&<#
H)',#)/5#e2);52;,<#?FRA#;.'/6#4;(*'19),')*+#B);..')/.#I0,#*2+#
&'()*+,)(#-(*+,'/6#0I#30(0,#)/5#2<8+,1.8+3*,)(#'4)6+."#D;6'40*0#
)/5#h)4)*)#?FdA#8,080.+5#)#I;,*2+,#:0;,'+,#)88,0]'4)*'0/#I0,#
*2+#B);..')/#&).'.C#72'(+#B)9).J),#)/5#e2);52;,<#?PRA#;.+5#)#
80(</04')(#&).'.#+]8)/.'0/#I0,#I).*#)5)8*'9+#&'()*+,)(#-(*+,'/6"#
# e0/3;,,+/*(<#7'*2#*2+#&).'.#+]8)/.'0/#4+*205.C#)#/;4&+,#0I#
I).*#&'()*+,)(#-(*+,.#7+,+#8,080.+5#&).+5#0/#*2+#.8()*1&(;,1.('3+#
-(*+,#8'8+('/+#0I#Q;,)/5#)/5#Q0,.+<#?@TA"#K'.#8'8+('/+#-(*+,.#)#
(+9+(#.+*#0I#'4)6+#'/*+/.'*'+.C#*2+/#'/*+,80()*+.#*2+#-(*+,+5#(+9+(#
.+*.#*0#6+/+,)*+#*2+#-/)(C#&'()*+,)(1-(*+,+5#'4)6+"#K'.#(+9+(1.+*#
)88,0)32#'.#+]*+/5+5#*0#*2+#&'()*+,)(#-(*+,'/6#0I#30(0,#'4)6+.#'/#
?@dA#7'*2#)#[15'4+/.'0/)(#507/1.)48('/6#()**'3+"#N0#09+,304+#
*2+#3048;*)*'0/)(#)/5#4+40,<#'/+_3'+/3<#0I#-(*+,'/6#0/#.;32#
)#2'6215'4+/.'0/)(#()**'3+C#=5)4.#et al"#?F@A#8,080.+5#*0#-(*+,#
0/#)#.8),.+#*,')/6;(),#()**'3+#'/.*+)5"#$07+9+,C#507/1.)48('/6#
`0,#^;)/*'W)*'0/a#0/#)#()**'3+#'.#0/(<#0/+#.8+3'-3#'/.*)/3+#0I#*2+#
40,+#6+/+,)(#30/3+8*C#9+3*0,#^;)/*'W)*'0/"#K+#4)/'I0(51&).+5#
4+*205#0I#B).*)(#)/5#i('9+',)#?FFA#,+.)48(+.#.+8),)&(<#0/*0#)#
4)/'I0(5C#72'(+#*2+#B);..')/#Q1*,++#?FVA#0/*0#*2+#(+)I#/05+.#
0I#)#Q1*,++"#O0W+,09#)/5#9)/#5+#>+'Y+,#?FPA#0&.+,9+5#*2)*#)#
/)*;,)(#'4)6+#*<8'3)((<#30/*)'/.#)#('4'*+5#/;4&+,#0I#30(0,.C#.0#
*2)*#'4)6+#8']+(.#4)<#&+#3(;.*+,+5#`0,#9+3*0,1^;)/*'W+5a#'/#*2+#
30(0,#.8)3+"#H)',#)/5#e2);52;,<#?FRA#304&'/+#*2+#30(0,1.8)3+#
3(;.*+,'/6#4+*205#7'*2#J+,/+(#)88,0]'4)*'0/"#>+#+/.30/3+#)((#
.;32#,+.)48('/6#)/5#3(;.*+,'/6#)88,0)32+.#'/#)#6+/+,)(#9+3*0,1#
,+.)48('/6#.8()*1&(;,1.('3+#I,)4+70,J"#=((#4+*205.#4+/*'0/+5#
)&09+C#).#7+((#).#0;,.C#2)9+#3048;*)*'0/)(#3048(+]'*'+.#72'32#
),+#('/+),#'/#'4)6+#.'W+C#)/5#30/.*)/*#'/#*2+#-(*+,#.3)(+"#
# >2'(+#.04+#)88,0)32+.#?FRAC#?P[A#304&'/+#&).'.#+]8)/.'0/.#
)/5#.8()*1&(;,1.('3+#4+*205.#*0#)33+(+,)*+#&'()*+,)(#-(*+,'/6C#7+#
+]*+/5#*2+#()**+,#('/+#0I#*+32/'^;+.#'/#0;,#8,+.+/*#70,J"#=#&,'+I#
,+9'+7#'.#/07#6'9+/#I0,#*2+#&'()*+,)(#-(*+,#)/5#.8()*1&(;,1.('3+"#
A. (e Bilateral Filter
# D;880.+#7+#2)9+#)#.)48(+5#6,)<.3)(+#'4)6+#∈
𝑁
#720.+#
8']+(#(03)*'0/.#30,,+.80/5#*0#*2+#.)48('/6#0I#.04+#,+3*)/6;(),#
.;880,*#0/#*2+#-#8()/+"#G.'/6##).#)/#'/8;*C#*2+#0;*8;*#
out
#0I#
*2+#&'()*+,)(#-(*+,#3)/#&+#+]8,+..+5#).X#
#
𝑛
out
=
1
𝑛
e
−|𝐮
𝑛
−𝐮
𝑚
|
2
/2
𝑛
𝑚
,#
`@a#
#
𝑛
= e
−|𝐮
𝑛
−𝐮
𝑚
|
2
/2
𝑚
,#
I0,#1 ≤≤C#72+,+#7+#5+/0*+#&<#
𝑛
#*2+#80.'*'0/#0I#*2+#*2##
8']+(#'/#*2+#11#.8)3+"#K)*#'.C#
#
𝑛
=
𝑛
𝑋
𝑛
𝑌
𝑛
𝑍
,
#
`Fa#
'/#72'32#
𝑋
C#
𝑌
#)/5#
𝑍
#),+#*2+#-(*+,#.3)(+.#'/#*2+',#,+.8+3*'9+#
5'4+/.'0/."#K+,+I0,+C#&'()*+,)(#-(*+,'/6#3)/#&+#,+6),5+5#40,+#
6+/+,)((<#).#*2,++15'4+/.'0/)(#B);..')/#-(*+,'/6#7'*2#*2+#-(*+,#
504)'/#,+.*,'3*+5#*0#80'/*.#
𝑛
#I0,#1 ≤≤"#
# :'(*+,'/6#`@a#3)/#&+#7,'**+/#3048)3*(<#'/#4)*,']#/0*)*'0/#).#
#
out
=
†
, = (),#
`Pa#
'/#72'32#*2+#+(+4+/*.#
𝑚𝑛
= e
−|𝐮
𝑛
−𝐮
𝑚
|
2
/2
#0I##,+8,+.+/*#*2+#
(a) Scalar resampling [17], [19] (b) Lattice resampling [21] (c) Vector resampling [20], [23] (d) KLT + Scalar resampling
@18E)9E)#4.+K2H1,8)FG)3D4).18,+H)WAH+/N)6F3.Y)F,3F)+,6)G0FK)3D4)54031/4.)FG)+)/F+0.4)80+2D)W80+B)6F3.YE)%-01,8).2H+331,8;)4+/D).18,+H)4H4K4,3)1.)b-+,31d46)F,3F)3D4)
/4,30F16.)FG)3D4)/F,3+1,1,8)eF0F,F1)/4HH.)+,6)+//-K-H+346E)%-01,8).H1/1,8;)3D4).18,+H)4H4K4,3)1.)+540+846)G0FK)3D4)5+H-4.).3F046)+3)3D4)/4HH)/4,30F16.E)*-H31H1,4+0)
F0)A+0B/4,301/)04.+K2H1,8)/+,)+H.F)A4)-.46)1,)2H+/4)FG)b-+,31d+31F,)W,4+04.3S,418DAF0)04.+K2H1,8Y)6421/346)D404E
#
6084 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 29, 2020
#
)_/'*<#&+*7++/#*2+#.'6/)(#+(+4+/*.#
𝑚
#)/5#
𝑛
"#:,04#)#6,)821
*2+0,+*'3#8+,.8+3*'9+C#7+#3)/#,+6),5##).#*2+#)5Y)3+/3<#4)*,']#
0I#)#7+'62*+5#6,)82#7'*2#9+,*'3+.# = {
𝑛
}C#)/5#.'4'(),(<C##
).#*2+#6,)82#5+6,++#4)*,']"#K+/C#*2+#4)*,']#
†
#30,,+.80/5.#
*0#,)/50417)(J1/0,4)('W)*'0/#0I#*2+#)5Y)3+/3<#4)*,']#"#K'.#
8+,.8+3*'9+#3).*.#*2+#'4)6+#∈
𝑁
#40,+#'/*;'*'9+(<#).#)#6,)82#
.'6/)(#∈
𝑈
C#;.'/6#*2+#'.040,82'.4#&+*7++/#
𝑁
#)/5#
𝑈
"#
# %9)(;)*'/6#`Pa#4)<#)88+),#'/*,)3*)&(+#I0,#(),6+#9)(;+.#0I#*2+#
.3)(+#8),)4+*+,.#
𝑋
#)/5#
𝑌
#.'/3+#*2+#5+/.+#4)*,']##)*#2)/5#
2).#/0#0&9'0;.#.*,;3*;,+#*2)*#3)/#&+#+]8(0'*+5"#$07+9+,C#'I#*2+#
().*#300,5'/)*+#
𝑛
#'.#)&.+/*#I,04#
𝑛
C#*2+#9+,*+]#.+*##5+-/+.#)#
*7015'4+/.'0/)(#e),*+.')/#6,'5C#)/5#*2+#+9)(;)*'0/#0I##
.'48('-+.#*0#30/90(9'/6##7'*2#)/<#30(;4/#0I#"#>2+/#*2+#
𝑛
#
300,5'/)*+#'.#'/3(;5+5C##/0#(0/6+,#('9+.#0/#)#*7015'4+/.'0/)(#
8()/+C#&;*#)#*7015'4+/.'0/)(#4)/'I0(5#'/#)#*2,++15'4+/.'0/)(#
.8)3+"#!*#'.#*2'.#8,+.+/3+#0I#
𝑛
#'/#
𝑛
#72'32#2'/5+,.#)/#+_3'+/*#
+9)(;)*'0/#0I#`Pa"#e0/90(;*'0/#0I#*2+#+/*',+C#*2,++15'4+/.'0/)(#
.8)3+#&<#)#B);..')/#J+,/+(#'.#3048;*)*'0/)((<#'/+_3'+/*#.'/3+#
*2+#,+.;(*#0I#30/90(;*'0/#'.#/++5+5#0/(<#0/#"#K+#'/+_3'+/3<#
0I#/)j9+#30/90(;*'0/#'.#40,+#8,0/0;/3+5#I0,#&'()*+,)(#-(*+,'/6#
0I#30(0,#'4)6+.C#72+,+#*2+#*7015'4+/.'0/)(#4)/'I0(5#'.#'/.'5+#
)#-9+15'4+/.'0/)(#----#.8)3+#'/.*+)5"#
# D'/3+#*2+#*2,++15'4+/.'0/)(#-(*+,#6,'5#'.#808;()*+5#.8),.+(<#
&<#'4)6+#.)48(+.#0/(<#)*#*2+#(03)*'0/.#C#0/+#/++5#/0*#-(*+,#'/#
*2+#+/*',+#2'6215'4+/.'0/)(#.8)3+C#&;*#0/#*2+#*7015'4+/.'0/)(#
4)/'I0(5#+4&+55+5#7'*2'/#*2+#.8)3+"#K'.#4+)/.#*2)*#4+40,<#
/++5#/0*#&+#)((03)*+5#I0,#*2+#+/*',+#*2,++15'4+/.'0/)(#()**'3+"#=##
/0/1('/+),#5)*)#.*,;3*;,+#.;32#).#)#5'3*'0/),<#0,#)#*,++#4)<#)(.0#
&+#;.+5#*0#.*0,+#*2+#.'6/)(#+(+4+/*.#0/(<#0/#*2+#4)/'I0(5."#K+#
(00J;8.#0/#5'3*'0/),'+.#)/5#*,++.#),+#+_3'+/*C#'/3;,,'/6#)#(1)#
*0#(log )#30.*#I0,#)/#)9+,)6+#(00J;8"#!/#)((#3).+.C#*2+#)3*;)(#
-(*+,'/6#0/#*2+#4)/'I0(5.#3)/#&+#)33+(+,)*+5#;.'/6#*2+#8'8+('/+#
J/07/#).#.8()*1&(;,1.('3+"#
B. Fast Bilateral Filtering
# N70#8,08+,*'+.#0I#B);..')/#-(*+,#J+,/+(.#(+)5#;.#/)*;,)((<#*0#
)33+(+,)*+5#-(*+,'/6"#:',.*C#*2+#J+,/+(.#),+#3',3;(),(<#.<44+*,'3#
)/5#.+8),)&(+C#,+/5+,'/6#B);..')/#-(*+,'/6#)#.+8),)&(+#-(*+,'/6#
08+,)*'0/"#D+30/5C#B);..')/#-(*+,#J+,/+(.#),+#3(0.+5#;/5+,#*2+#
30/90(;*'0/#08+,)*'0/C#.0#7+#3)/#I)3*0,#)#(),6+#B);..')/#-(*+,#
;.'/6#)#3).3)5+#0I#.4)((+,#B);..')/."#K'.#3)/#&+#&+/+-3')(#'I#
'*#'.#40,+#+_3'+/*#*0#'*+,)*+#B);..')/#-(*+,.#0I#.4)((+,#.;880,*#
,)*2+,#*2)/#;.'/6#)#.'/6(+#B);..')/#J+,/+(#0I#(),6+#.;880,*"#K+#
&'()*+,)(#-(*+,'/6#0I#)/#'4)6+#∈
𝑈
#2)9'/6#(),6+#.8)*')(#-(*+,#
.3)(+.#3)/#*2;.#&+#)33+(+,)*+5#&<#`'a#507/1.)48('/6#∈
𝑈
#*0#
∈
𝑉
#0/#*2+#9+,*'3+.##0I#)#30),.+,#*2,++15'4+/.'0/)(#11#
6,)82C#`''a#&(;,,'/6##;.'/6#)#.4)((#B);..')/#J+,/+(#*0#8,05;3+#
′C#-/)((<#`'''a#;81.)48('/6#′ *0#8,05;3+#
out
∈
𝑈
"#N0#,+5;3+#
3048(+]'*<C#7+#0I#30;,.+#,+^;',+#*2)*#
|
|
|
|
"#
# k+*#;.#)..;4+#7'*20;*#(0..#0I#6+/+,)('*<#*2)*#-(*+,# `Pa#2).#
.3)(+.#=
𝑋
=
𝑌
=
𝑍
"#i/+#3)/#I)3*0,#*2+#-(*+,#)330,5'/6#
*0#*2+#.8()*1&(;,1.('3+#8'8+('/+#`'aS`'''a#).##
#
= 
∗
,#
`Ra#
'/#72'32#
∗
∈
𝑉 ×𝑈
#'.#)#507/1.)48(+,#720.+#507/.)48('/6#
I)3*0,.#),+##)(0/6#+)32#)]'.C#)/5#∈
𝑉 ×𝑉
#'.#)#&(;,#08+,)*0,#
2)9'/6#.3)(+#"#>2+/#.8()**'/6#)/5#.('3'/6#),+#8+,I0,4+5#;.'/6#
^;)/*'W)*'0/C#*2+#-(*+,#.3)(+.#)/5#*2+#.;&1.)48('/6#I)3*0,#4;.*#
.)*'.I<#
2
=
2
2
+ (1 6
⁄
)
2
C#72+,+#(1 6
⁄
)
2
#'.#*2+#.;4#0I#*2+#
,+.)48('/6#9),')/3+.#0I#
∗
)/5#"#c+.)48('/6#4+*205.#&).+5#
0/#&),<3+/*,'3#)/5#4;(*'1('/+),#,+.)48('/6#3)/#&+#;.+5#'/.*+)5#
0I#^;)/*'W)*'0/#`0,#/+),+.*1/+'62&0,#,+,+.)48('/6a#).#7+(("#
# D8()**'/6#)/5#.('3'/6#3)/#&+#&).+5#0/#.3)(),C#()**'3+#0,#9+3*0,#
,+.)48('/6C#).#7+#'((;.*,)*+#'/#:'6"#F"#K+#320'3+#0I#,+.)48('/6#
.32+4+C#'/#*;,/C#5+*+,4'/+.#*2+#'48(+4+/*)*'0/#0I#*2+#&(;,,'/6#
08+,)*'0/"#:0,#+])48(+C#.3)(),#,+.)48('/6#).#;.+5#'/#?@TAC#?@dA#
+/)&(+.#&(;,,'/6#*0#&+#'48(+4+/*+5#).#)#.+8),)&(+#30/90(;*'0/#
'/#+)32#5'4+/.'0/"#D)5(<C#.3)(),#,+.)48('/6#'.#(+..#*2)/#'5+)(#'I#
*2+#.;880,*#0I#*2+#.'6/)(#'.#/0*#)('6/+5#*0#*2+#)]+.#0I#*2+#.^;),+#
.)48('/6#()**'3+f*2+#&(;,#I,04#0/+#()**'3+#80'/*#*0#)/0*2+,#3)/#
0/(<#&+#8,08)6)*+5#&<#)55'/6#'/*+,4+5')*+#()**'3+#80'/*.#)(0/6#
*2+#)]+.C#72'32#'/3;,.#3048;*)*'0/#)/5#.*0,)6+#30.*.#*2)*#6,07#
+]80/+/*')((<#7'*2#*2+#/;4&+,#0I#5'4+/.'0/.#0I#*2+#.'6/)("#K+#
8+,4;*02+5,)(#()**'3+#^;)/*'W+,#0I#?F@A#'48,09+.#*2+#+_3'+/3<#
0I#.+8),)&(+#30/90(;*'0/#&+3);.+#*2+#()**'3+#)]+.#2)9+#)#2'62+,#
5+6,++#0I#,0*)*'0/)(#.<44+*,<"#l+3*0,#^;)/*'W)*'0/#`3(;.*+,'/6a#
I)3'('*)*+.#&(;,,'/6#9')#O0/*+#e),(0#4+*205.#'I#*2+#504)'/#)/5#
,)/6+#5'4+/.'0/.#),+#3(;.*+,+5#Y0'/*(<#?FVAC#0,#9')#30/90(;*'0/#
'I#0/(<#*2+#,)/6+#5'4+/.'0/.#),+#3(;.*+,+5#?FPAC#?FRA"##
# :,04#*2+#8,+.+/*#5'.3;..'0/C#'*#4)<#.++4#*2)*#*2+#9+3*0,#)/5#
()**'3+#,+.)48('/6#)88,0)32+.#),+#&+**+,1.;'*+5#*0#.8()**'/6#)/5#
.('3'/6#*2)/#.3)(),#,+.)48('/6"#$07+9+,C#*2+.+#*70#,+.)48('/6#
.*,)*+6'+.#2)9+#)#/;4&+,#0I#5,)7&)3J.#'/#)#2'62+,15'4+/.'0/)(#
.8)3+"#l+3*0,#^;)/*'W)*'0/#9')#k(0<5m.#)(60,'*24#3)/#30/9+,6+#
@18E)UE)P+0B/4,301/)04.+K2H1,8)F,)+).b-+04)H+331/4E)@10.3;)J4)\,6)3D4)54031/4.)FG))
3D4)`-D,).1K2H4c)3D+3)/F,3+1,.)3D4).F-0/4)54034cE)I4,;)J4)-.4)3D4)A+0B/4,301/)
/FF061,+34.)FG)3D4).F-0/4)54034c)+.)3D4)04.+K2H1,8)J418D3.)GF0)3D4)54031/4.)FG)
3D4)/F,3+1,1,8).1K2H4c)W1HH-.30+346)H4G3YE)I4).D+646)0481F,.)+04)3D4)/+,F,1/+H)
.1K2H1/4.) Δ = {𝐯 ∶ 0 ≤ 𝑣
1
≤ ⋅ ⋅ ⋅ ≤ 𝑣
𝐾+1
≤ 1}
)GF0)
𝐾 = 2
)WH4G3Y;
3 )W018D3YE)
^40K-31,8)+,6).D1G31,8)3D4)1,4b-+H1314.)FG)Δ)20F6-/4.)3D4)04K+1,1,8).1K2H1/4.E)
#
#
#
∆#
.#
∆#
#
#
0.2#
0.4
0.4#
1#
@18E)CE)Q+-..1+,) \H3401,8)FG)+)F,4S61K4,.1F,+H).18,+H)F,)+)2B0+K16)FG)D418D3)
𝐿 = 2E)I4)-2J+06)\H340)2+..)WH4G3Y)/F,5FH54.).18,+H.)J13D)+)Q+-..1+,)N40,4H)
+,6)6B+61/+HHB).-AS.+K2H4.)3D4KE)I4)6FJ,J+06)\H340)2+..)W018D3Y)\0.3)1,.403.)
d40F.)1,3F)3D4).18,+H.)+,6)/F,5FH54.)3D4K)J13D)+)Q+-..1+,)N40,4HE)I4)4f4/3154)
./+H4)FG)3D4)AH-0)1.)3D4)+88048+31F,)FG)3D4)AH-0)./+H4.)+/0F..)+HH)H454H.E
#
downward pass
upward pass
Level 1
Level 0
#
#
YOUNG et al.: GAUSSIAN LIFTING FOR FAST BILATERAL AND NONLOCAL MEANS FILTERING 6085
#
.(07(<#'/#2'62#5'4+/.'0/.#7'*2#)#.;8+,180(</04')(#70,.*13).+#
3048(+]'*<"#%9+/#*2+#+]*,)#5+6,++#0I#,0*)*'0/)(#.<44+*,<#I,04#
*2+#`8+,4;*02+5,)(a#()**'3+#,+.)48('/6#5+3,+).+.#).#*2+#/;4&+,#
0I#5'4+/.'0/.C#)/5#)88,0)32+.#*2)*#0I#*2+#,+3*)/6;(),#()**'3+#'/#
*2+#('4'*#?F@A"#:;,*2+,C#7+#7'.2#*0#.;&1.)48(+#*2+#'/*+,4+5')*+#
,+.;(*.#'/#*2+#.+^;+/3+#0I#.+8),)*+#30/90(;*'0/.#*0#'48,09+#*2+#
&(;,,'/6#+_3'+/3<C#&;*#('/+),#5+8+/5+/3+#0I#*2+#8+,4;*02+5,)(#
()**'3+#I,)4+#8,+9+/*.#*2'."#
!!!" i&#)Z#$^$MT%)OT"g$%#
# !/#0;,#8,080.+5#4+*205C#7+#.8()*#)/5#.('3+#&<#5+30,,+()*'/6#
*2+#.'6/)(#;.'/6#*2+#'4)6+1.8+3'-3#hkNC#)/5#.3)(),1,+.)48('/6#
*2+#5+30,,+()*+5#.'6/)(#).#5+8'3*+5#'/#:'6"#F#`5a"#>+#&(;,#;.'/6#
)#8<,)4'51('J+#.32+4+#'/#*2+#hkN#504)'/#`:'6"#Pa"#i;,#;.+#0I#
*2+#hkN#'.#*0#,0*)*+#*2+#.'6/)(#.8)3+#I0,#+_3'+/*#&(;,,'/6"#K'.#
5'b+,.#I,04#*2+#;.+#0I#8)*32#Ze=#'/#/0/(03)(#4+)/.#5+/0'.'/6#
?F[AC#*2+#60)(#0I#72'32#'.#5'4+/.'0/)('*<#,+5;3*'0/"#
A. Splatting and Slicing
# k+*#;.#5+/0*+#&<#C#*2+#4)*,']#720.+#*2#30(;4/#'.#5+-/+5#
).#`Fa"#K+/C#*2+#5+30,,+()*'/6#*,)/.I0,4##0I##'.#*2+#4)*,']#
0I#+'6+/9+3*0,.#0I#
∗
"#>+#.8()*#;.'/6#.3)(),#^;)/*'W)*'0/#0I#
*2+#.'6/)(#)(0/6#*2+#,0*)*+5#)]+.#5+-/+5#&<#*2+#30(;4/.#0I#*2+#
0,*2060/)(#4)*,']#"#K'.#'.#+^;'9)(+/*#*0#,+.)48('/6#0/*0#*2+#
.3)(+5#'/*+6+,#()**'3+# =
{
∶
∗
∈(1
⁄
)
𝐾
}
"#c)*2+,#*2)/#
;.'/6#/+),+.*1/+'62&0,#,+.)48('/6C#72'32#3)/#'/*,05;3+#&(03J1
),*'I)3*.#'/#*2+#-(*+,+5#'4)6+C#7+#;.+#&),<3+/*,'3#,+.)48('/6#*0#
*2+#9+,*'3+.#0I#h;2/#.'48('3+.#`:'6"#Ra"#=88+/5']#=#5+*)'(.#*2+#
8,03+5;,+#I0,#&),<3+/*,'3#,+.)48('/6"#H0*+#*2)*#507/.)48('/6#
)/5#;8.)48('/6#08+,)*'0/.#),+#)5Y0'/*#*0#+)32#0*2+,C#.0#7+#3)/#
.*0,+#*2+#.8()**'/6#7+'62*.#)/5#,+;.+#*2+4#I0,#.('3'/6"#
# N0#-(*+,#)#.'6/)(#'/#'*.#*2#5'4+/.'0/#7'*2#.3)(+#
𝑘
C#7+#4;.*#
-/5#)#507/1.)48('/6#I)3*0,#
𝑘
≥1#I0,#)#6'9+/#9),')/3+#
2
#0I#
*2+#&(;,C#.;32#*2)*#-(*+,#9),')/3+.#5;+#*0#.8()**'/6C#&(;,,'/6#)/5#
.('3'/6#.;4#*0#
𝑘
2
"##D'/3+#*2+#9),')/3+#0I#&),<3+/*,'3#,+.)48('/6#
5;,'/6#.8()**'/6#'.#(1 3
⁄
)
𝑘
2
C#7+#,+^;',+##
#
𝑘
2
= 3
𝑘
2
(
3
2
+ 1
)
⁄
,
#
`[a#
/0*'/6#*2)*#
𝑘
2
#4;.*#&+#.4)((#I0,#)/#09+,)((#B);..')/#,+.80/.+"#
B. Blurring via Lifting
# E(;,,'/6#'.#'48(+4+/*+5#).#)#.+,'+.#0I##30/90(;*'0/.#)(0/6#
*2+#,0*)*+5#5',+3*'0/.C#09+,304'/6#*2+#+]80/+/*')(#.*0,)6+#)/5#
3048;*)*'0/)(#3048(+]'*<#)..03')*+5#7'*2#)55'/6#'/*+,4+5')*+#
()**'3+#80'/*.#)(0/6#*2+#0,'6'/)(#)]+."#D'/3+#*2+#,0*)*+5#()**'3+#'.#
0,*2060/)(C#)/5#(0718)..#-(*+,'/6#,+5;3+.#*2+#&)/57'5*2#0I#*2+#
.'6/)(C#7+#3)/#'/*+,(+)9+#*2+##30/90(;*'0/.#7'*2#.;&.)48('/6#
*0#&(;,#40,+#+_3'+/*(<"#K'.#,+.+4&(+.#-(*+,'/6#0/#)#B);..')/#
8<,)4'5#`.++#:'6"#Pa#'/#)#2'62+,15'4+/.'0/)(#.8)3+"#
# Q;,'/6#.8()**'/6C#*2+#.'6/)(#7).#,+.)48(+5#'/#+)32#0I#*2+##
5'4+/.'0/.#;.'/6#*2+#,+.)48('/6#I)3*0,.#`[a"#K+,+I0,+C#7+#3)/#
&(;,#'.0*,08'3)((<#7'*2#9),')/3+#
2
#'/#)((#5'4+/.'0/.#*0#)32'+9+##
*2+#*),6+*#-(*+,#.3)(+#
𝑘
#'/#+)32#5'4+/.'0/#"#>+#;.+#B);..')/#
('I*'/6#*0#&(;,#+_3'+/*(<#'/#)#4;(*'1,)*+#4)//+,"#
!l" B7&MM(7!)k(@"(!Q#
# :0,#&(;,,'/6C#(+*#;.#)..;4+#*2+#-(*+,'/6#)/5#*2+#.;&.)48('/6#
.*+8.#),+#,+8+)*+5##*'4+."#K'.#3)/#&+#+]8,+..+5#&<#+]8)/5'/6#
*2+#&(;,#08+,)*0,#'/#`Ra#).#
#
= 
2
∗

2
∗
𝐿 times
downward pass
2

2
𝐿 times
upward pass
,
`\a#
'/#72'32#
2
#'.#)#.;&1.)48(+,#7'*2#*2+#.;&1.)48('/6#I)3*0,#2#'/#
*2+#1C#1#)/5#15'4+/.'0/.C#)/5##'.#)#B);..')/#-(*+,#7'*2#*2+#
-(*+,#.3)(+.#=
𝑋
=
𝑌
=
𝑍
"#
# D;&1.)48('/6#I)3*0,#0I#2#'.#;.+5#'/#`Ta#.'/3+#('I*'/6#.32+4+.#
),+#6+/+,)((<#5<)5'3C#,+^;','/6#*2)*#*2+#.'6/)(#&+#.8('*#'/#+9+/1#
)/5#0551'/5+]+5#+(+4+/*."#>+#,+I+,#*0#*2+#3).3)5+5#-(*+,'/6#'/#
`\a#).#;87),5#)/5#507/7),5#-(*+,#8)..+.#0/#)#5<)5'3#B);..')/#
8<,)4'5#0I#2+'62*#"#=.#7+#'((;.*,)*+#'/#:'6"#PC#*2+#;87),5#8)..#
.;33+..'9+(<#-(*+,.#*2+#.'6/)(#)/5#*2+/#.;&1.)48(+.#'*#72'(+#*2+#
507/7),5#8)..#'/.+,*.#W+,0.#'/#*2+#.'6/)(#)/5#*2+/#-(*+,.#'*"#=*#
+)32#8<,)4'5#(+9+(C#*2+#B);..')/#-(*+,##8,+.+,9+.#.3)(+##0I#
&(;,#7'*2#,+.8+3*#*0#*2+#.;&1.)48(+5#6,'5C#72'32#'.#)..;4+5#*0#
2)9+#;/'*#6,'5#.8)3'/6"#B'9+/##)/5#C#*2+#.3)(+##0I#&(;,##'.##
6'9+/#&<#
#
2
= 2
2
2ℓ
𝐿−1
ℓ=0
2
=
(
2 3
⁄
)(
2
2𝐿
−1
)
2
.
#
`Ta#
# !/#7)9+(+*1&).+5#'4)6+#8,03+..'/6C#('I*'/6#.32+4+.#,+I+,#*0#
I).*#'48(+4+/*)*'0/.#0I#*2+#3()..'3#5'.3,+*+#7)9+(+*#*,)/.I0,4.#
?P\A"#H0#)55'*'0/)(#70,J'/6#.*0,)6+#'.#/++5+5#.'/3+#+9+,<#.*+8#
0I#*2+#('I*'/6#)(60,'*24#4)<#09+,7,'*+#*2+#'/8;*#.'6/)(#7'*20;*#
,+/5+,'/6#*2+#*,)/.I0,4#',,+9+,.'&(+"#=/0*2+,#)59)/*)6+#0I#*2+#
@18E) hE) "JFS61K4,.1F,+H) Q+-..1+,) H1G31,8) F,) F,4) H454H) FG) 3D4) 2B0+K16E)I4)
.18,+H) 1.) 30+,.GF0K46) .42+0+AHB) 51+) H1G31,8) GF0) 4+/D)𝑘 = 1, . . . , 𝐾
)FG) 3D4)
𝐾)
61K4,.1F,.)W.DFJ,)D404)GF0)𝐾 = 2YE)!4J)54031/4.)+04)+6646)6-01,8)3D4)H1G31,8)
20F/4..)1G)3D4B)6F),F3)+H04+6B)4c1.3)W6+.D46)+00FJ.YE)
#
#
#
𝑥-lifting 𝑦-lifting
Input 𝑥
ℓ
Dual step
Primal step
1
#
Output 𝑥
ℓ+1
1
#
2
#
2
#
@18E)VE)Q+-..1+,)H1G31,8)+22H146)F,)+).2+0.4)F,4S61K4,.1F,+H).18,+HE)T54,S)+,6)
F66S1,64c46)54031/4.)+04)04204.4,346)AB)AH+/N)+,6)80+B)6F3.)04.24/3154HBE)T54,)
W04.2E)F66Y)4H4K4,3.)+f4/3)F,HB)F66)W04.2E)454,Y)4H4K4,3.E)!4J)54031/4.)+04)
/04+346)1G)3D4B)6F),F3)+H04+6B)4c1.3E)
6086 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 29, 2020
#
('I*'/6#.32+4+#'.#*2)*#'*#3)/#+).'(<#&+#)88('+5#*0#5)*)#5+-/+5#0/##
6,'5.#7'*2#',,+6;(),#&0;/5),'+.#0,#.)48(+#.8)3'/6#?PTAC#?PUA"#=#
-(*+,&)/J#'48(+4+/*)*'0/#,+^;',+.#.+8),)*+#&0;/5),<#-(*+,.#0,#
+]*+/5'/6#*2+#.'6/)(#)*#*2+#&0;/5),'+."#H+'*2+,#0I#*2+.+#70;(5#
&+#.'48(+#I0,#.8),.+#2'6215'4+/.'0/)(#.'6/)(."#
# K+#)&09+#I+)*;,+.#0I#*2+#('I*'/6#.32+4+#3)/#&+#+]8(0'*+5#I0,##
&'()*+,)(#-(*+,'/6#).#7+(("#:0,#+])48(+C#*2+#&'()*+,)(#-(*+,#&).+5#
0/#30/90(;*'0/#70;(5#,+^;',+#)((03)*'/6#&0*2#'/8;*#)/5#0;*8;*#
&;b+,.#*0#8+,I0,4#*2+#-(*+,'/6#72+,+).#)#('I*'/61&).+5#0/+#3)/#
08+,)*+#'/18()3+#*0#,+5;3+#4+40,<#;.+"#O0.*#'480,*)/*(<C#+)32#
('I*'/6#.*+8#,+^;',+.#J/07(+56+#0/(<#0I#'44+5')*+#/+'62&0,.#0I##
+)32#9+,*+]#,+6),5(+..#0I#*2+#-(*+,#J+,/+(#.;880,*"#>+#3)/#)(.0##
8,08)6)*+#*2+#/+'62&0,2005#'/I0,4)*'0/#I,04#32'(5#9+,*'3+.#*0#
8),+/*#0/+.#).#*2+#('I*'/6#8,06,+..+.C#,+5;3'/6#*2+#*0*)(#/;4&+,##
0I#(00J;8#08+,)*'0/.#/++5+5#I0,#/+'62&0,'/6#9+,*'3+."##
# e0/.'5+,#B);..')/#-(*+,'/6#0I#)#&'1'/-/'*+C#0/+15'4+/.'0/)(#
.'6/)(##&<#('I*'/6"#!/'*')('W'/6#
ℓ=0
= C#*2+#;87),5#-(*+,#8)..##
'/90(9+.#.;33+..'9+#B);..')/#507/1.)48('/6#0I#
ℓ
#*0#8,05;3+#
ℓ+1
#)3,0..#)((#8<,)4'5#(+9+(.#= 0, 1, . . . , −1"#>+#+]8,+..##
*2'.#507/1.)48('/6#).#
ℓ+1
=↓
2
(∗
ℓ
)C#72+,+##,+8,+.+/*.#
)#-(*+,#J+,/+("#=.#)/#+])48(+C#'I#7+#30/.'5+,#)#.<44+*,'3#-(*+,#
J+,/+(##7'*2#*2+#Z1*,)/.I0,4#
#
() =
0
+
1
(
1
+
−1
) +
2
(
2
+
−2
),#
`Ua#
*2+/#
ℓ+1
3)/#&+#3048;*+5#;.'/6#*2+#('I*'/6#.*+8.#
#
𝑣+1
ℓ
←
𝑣+1
ℓ
+
0

𝑣+0
ℓ
+
𝑣+2
ℓ
#
`d5a#
#
𝑣+0
ℓ
←
𝑣+0
ℓ
+
1

𝑣+1
ℓ
+
𝑣−1
ℓ
#
`d8a#
#
𝑣+0
ℓ
←
2
𝑣+0
ℓ
#
`d/a#
)/5#(+**'/6#
𝑣/2
ℓ+1
=
𝑣
ℓ
#I0,#)((#∈2"#
# K+#('I*'/6#30+_3'+/*.#'/#`da#3)/#&+#5+,'9+5#).#
#
0
=
2
1
,
1
=
1
0
−2
2
,
2
=
0
−2
2
#
`@Va#
`.++#=88+/5']#=a"#E0,,07'/6#*+,4'/0(06<#I,04#('I*'/6#7)9+(+*#
*,)/.I0,4.C#7+#,+I+,#*0#*2+#;85)*+#0I#0551'/5+]+5#.)48(+.#`d5a#
).#)#5;)(1('I*'/6#.*+8C#*2+#;85)*+#0I#+9+/1'/5+]+5#0/+.#`d8a#).#)#
8,'4)(1('I*'/6#.*+8C#)/5#`d/a#).#)#/0,4)('W)*'0/#.*+8"#>+#5+8'3*#
*2+#('I*'/6#.*+8.#I0,#)#0/+15'4+/.'0/)(#.'6/)(#'/#:'6"#["#
# K+#507/7),5#-(*+,#8)..#'/'*')('W+.#
𝐿
=
𝐿
C )/5#8,05;3+.#
ℓ
#&<#;81.)48('/6#
ℓ+1
#I0,#= −1, . . . , 0"#>+# +]8,+..# *2'.#
;81.)48('/6#).#
ℓ
= ∗(↑
2
ℓ+1
)C#72+,+##'.#6'9+/#&<#`Ua#).#
&+I0,+"#N0#3048;*+#
ℓ
C#7+#-,.*#(+*#
𝑣
ℓ
=
𝑣/2
ℓ+1
#)/5#
𝑣+1
ℓ
= 0#I0,##
)((#∈2C#)/5#;.+#*2+#('I*'/6#.*+8.#
#
𝑣+0
ℓ
←
2
𝑣+0
ℓ
#
`@@/a#
#
𝑣+0
ℓ
←
𝑣+0
ℓ
+
1
(
𝑣+1
ℓ
+
𝑣−1
ℓ
)
#
`@@8a#
#
𝑣+1
ℓ
←
𝑣+1
ℓ
+
0
(
𝑣+0
ℓ
+
𝑣+2
ℓ
)#
`@@5a#
I0,#)((#∈2.#K+#('I*'/6#.*+8.#`@@a#),+#*2+,+I0,+#0&*)'/+5#&<#
,+9+,.'/6#*2+#0,5+,#0I#('I*'/6#.*+8.#`da"#>+#/0*+#*2+#('I*'/6#.*+8.##
`@@a#),+#/0*#*2+#'/9+,.+C#&;*#*2+#)5Y0'/*C#0I#`daf*2'.#'.#40,+#0,#
(+..#+9'5+/*#I,04#*2+#*,)/.80.+#,+()*'0/#)40/6#*2+#;87),5#)/5#
*2+#507/7),5#-(*+,#8)..+.#'/#`\a"#H0*+#*2+#/0,4)('W)*'0/#.*+8.#
`d/a#)/5#`@@/a#/++5#/0*#&+#8+,I0,4+5#'/#8,)3*'3+"#
# :0,#B);..')/#('I*'/6#'/##5'4+/.'0/.C#7+#)88(<#('I*'/6#.*+8.#
.+8),)*+(<#'/#+)32#0I#*2+##5'4+/.'0/."#!/#*2+#;87),5#-(*+,'/6#
8)..C#*2+#('I*'/6#.*+8.#I0,#*2+#*2#5'4+/.'0/#),+#+]8,+..+5#).#
#
𝐯+1𝐤
ℓ
←
𝐯+1𝐤
ℓ
+
0
(
𝐯+0𝐤
ℓ
+
𝐯+2𝐤
ℓ
)#
`@F5a#
#
𝐯+0𝐤
ℓ
←
𝐯+0𝐤
ℓ
+
1
(
𝐯−1𝐤
ℓ
+
𝐯+1𝐤
ℓ
)#
`@F8a#
#
𝐯+0𝐤
ℓ
←
2
𝐯+0𝐤
ℓ
#
`@F/a#
I0,#)((#= (
1
,
2
, . . . ,
𝐾
) ∈2
𝑘
⊕
𝐾−𝑘
C#72+,+#∈
𝐾
#'.#
*2+#*2#30(;4/#0I#*2+#'5+/*'*<#4)*,']"#K+#('I*'/6#08+,)*'0/.#'/#
*2+#*7015'4+/.'0/)(#3).+#` = 2a#),+#'((;.*,)*+5#'/#:'6"#\"#K+#
507/7),5#('I*'/6#.*+8.#),+#8,+.3,'&+5#&<#,+9+,.'/6#*2+#0,5+,#0I#
*2+#('I*'/6#.*+8.#`@Fa"#>+# ,+I+,# *0#*2+#9+,*'3+.#− )/5#+
'/#`@Fa#).#*2+#8,+5+3+..0,#)/5#*2+#.;33+..0,C#,+.8+3*'9+(<C#0I#
0/#(+9+(##)/5#'/#5'4+/.'0/#"#
# !/#6+/+,)(C#7+#,+^;',+#)#('I*'/6#.32+5;(+#*0#8,03+..#*2+#.'6/)(#
'/#)((##5'4+/.'0/."#>+#30;(5#.32+5;(+#*2+#('I*'/6#.*)6+.#(+9+(#
&<#(+9+(C#8+,I0,4'/6#I0,#+)32#(+9+(#C#*2+#('I*'/6#.*+8.#)3,0..#)((#
#5'4+/.'0/."#=.#)/#)(*+,/)*'9+C#0/+#30;(5#.32+5;(+#*2+#('I*'/6#
.*)6+.#5'4+/.'0/#&<#5'4+/.'0/C#8+,I0,4'/6#'/#+)32#5'4+/.'0/#
C#*2+#('I*'/6#.*+8.#)3,0..#*2+##(+9+(."#>2'(+#*2+#*70#.32+5;(+.#
8,05;3+#'5+/*'3)(#-(*+,+5#0;*8;*C#*2+#()**+,#0/+#'.#40,+#+_3'+/*#
.'/3+#'*#3)/#4)]'4)((<#507/1.)48(+#*2+#.'6/)(#'/#*2+##)/5#*2+#
#5'4+/.'0/.#&+I0,+#('I*'/6#'/#*2+##0,#,0*)*+5#11#5'4+/.'0/.##
`I0,#30(0,#'4)6+.aC#72+,+#4)/<#/+7#9+,*'3+.#),+#3,+)*+5"#
l" k(@"(!Q)!*^RT*T!"7"($!#
# K+#.8()*#.'6/)(#∈
𝑉
#'.#.;880,*+5#0/(<#0/#*2+#.;&.+*##0I#
*2+#*2,++15'4+/.'0/)(#11#()**'3+#`I0,#*2+#&'()*+,)(#-(*+,'/6#0I#
6,)<.3)(+#'4)6+.a#0,#)#15'4+/.'0/)(#0/+#'/#6+/+,)(C#.0#7+#50#
/0*#/++5#*0#)((03)*+#4+40,<#I0,#*2+#720(+#()**'3+"#D'/3+#('I*'/6#
08+,)*'0/.#,+^;',+#J/07(+56+#0/(<#0I#*2+#3;,,+/*#9+,*+]#)/5#'*.#
*70#'44+5')*+#/+'62&0,.#'/#*2+#3;,,+/*#5'4+/.'0/#`@FaC#7+#;.+#
)#50;&(<1('/J+5#('.*#*0#,+8,+.+/*#*2+#9+,*'3+.#0I#)#.'6/)(C#.*0,'/6#
.'6/)(#9)(;+.#'/#*2+#9+,*+]#0&Y+3*.C#*06+*2+,#7'*2#80'/*+,.#*0#*2+#
8,+3+5'/6#)/5#.;33++5'/6#9+,*'3+."#
# G.'/6#*2+#enn#.</*)]C#0;,#9+,*+]#0&Y+3*.#3)/#&+#,+8,+.+/*+5#
).#'/.*)/*')*'0/.#0I#
#
class Vertex (
short pos[K]
float val[D]
Vertex* pred
Vertex* succ
)
`@Pa#
'/#72'32#pos[K]#.*0,+.#*2+#300,5'/)*+#9+3*0,#0I#*2+#9+,*+]#0/##
*2+#15'4+/.'0/)(#()**'3+C#)/5#val[D]C#*2+##'4)6+#.)48(+.#
)*#*2'.#80.'*'0/C#72+,+#= 1#I0,#6,)<.3)(+#'4)6+.C#)/5#= 3#
I0,#30(0,#'4)6+."##
𝑀 )
𝑛)
𝑐
𝑛
)
ℎ
𝑛
, ℎ
−𝑛
)
𝑔
𝑛+1
, 𝑔
1−𝑛
1
0
1
0.5000000
0.5000000
0.500000000
0.250000000
1.00000000
2
0
1
2
1.0000000
0.2500000
0.2500000
0.375000000
0.250000000
0.062500000
0.66666667
0.16666667
3
0
1
2
3
2.2500000
0.8888889
0.2500000
0.0555555
0.277777778
0.222222222
0.111111111
0.027777778
0.47500000
0.22500000
0.03750000
#
"7PRT)()
RIFTING AND @ILTER 'OEFFICIENTS FOR %ISCRETE )
PSMPLINE `ER NELS OF $RDER 𝑀 )
YOUNG et al.: GAUSSIAN LIFTING FOR FAST BILATERAL AND NONLOCAL MEANS FILTERING 6087
#
# K+#('I*'/6#'.#8+,I0,4+5#5'4+/.'0/#&<#5'4+/.'0/#,)*2+,#*2)/#
(+9+(#&<#(+9+("#K)*#'.C#7+#(008#09+,#*2+#5'4+/.'0/.#'/#*2+#0;*+,###
(008C#)/5#09+,#*2+#(+9+(.#'/#*2+#'//+,#(008X#
#
procedure lifting_blur
#
#
#
for#= 1,2, . . . ,
`@Ra#
#
#
for#= 1,2, . . . ,
#
#
upward_pass(, )#
#moralize(, )
#
#
end
#
#
end
#
#
for#= , . . . ,2,1
#
#
for#= , . . . ,2,1
#
#
demoralize(, )
#downward_pass(, )
#
#
end
#
#
end
#
end
#
'/#72'32#moralize(, )#)/5#demoralize(, )#,+()<#.;33+..0,.#
)/5#8,+5+3+..0,.#&+*7++/#(+9+(.##)/5#+ 1C#*0#I;,*2+,#,+5;3+#
*2+#/;4&+,#0I#9+,*+]#(00J;8.#/++5+5"#E<#30/*,).*C#('I*'/6#(+9+(#
&<#(+9+(#70;(5#,+^;',+#)((03)*'/6#4+40,<#I0,##.;33+..0,#)/5#
8,+5+3+..0,#80'/*+,.#I0,#moralize#)/5#demoralizeC#72'32#)55.#
*0#4+40,<#;.+"#
# N0#*,)9+,.+#*2+#+9+/1#)/5#*2+#0551'/5+]+5#9+,*'3+.#+_3'+/*(<#
5;,'/6#('I*'/6C#7+#,+*)'/#*2+#.+*.#
even
𝑘,ℓ
#)/5#
odd
𝑘,ℓ
#0I#+)32#(+9+(##
)/5#5'4+/.'0/##)/5#808;()*+#*2+4#72+/+9+,#/+7#9+,*'3+.#),+#
3,+)*+5#5;,'/6#.8()**'/6#)/5#('I*'/6"#H0*+#*2)*#)#9+,*+]#'.#)55+5#
*0#0/(<#0/+#.+*#'/#8,)3*'3+X#+'*2+,#
even
𝐾−1,𝐿−1
#0,#*2+#.+*#
odd
𝑘,ℓ
#I0,#
.04+#0 ≤< , 0 ≤< "#=((#,+4)'/'/6#+9+/1'/5+]+5#.+*.#
3)/#&+#30/.*,;3*+5C#0/#*2+#o<C#;.'/6#*2+#,+()*'0/.2'8#
#
even
𝑘
𝑖
,ℓ
𝑖
=
even
𝑘
𝑖+1
,ℓ
𝑖+1
∪
odd
𝑘
𝑖+1
,ℓ
𝑖+1
,
#
`@[a#
'/#72'32#
𝑖
C#)/5#
𝑖
C#= 1,2, . . . #),+#,+.8+3*'9+(<#*2+#5'4+/.'0/#
)/5#*2+#(+9+(#8,03+..+5#5;,'/6#*2+#*2#('I*'/6#.*)6+"##
# #K+#('I*'/6#.*+8.#'/#`@Ra#3)/#&+#'48(+4+/*+5#).##
#
procedure upward_pass
(
,
)
#
#
#
for#
∈
even
𝑘,ℓ
`@\
a
#
#
#
. pred.val +=
0
.val
. succ.val +=
0
.val
#
#
end
#
#
for#
∈
odd
𝑘,ℓ
#
#
. pred.val +=
1
.val
. succ.val +=
1
.val
#
#
end
#
end
#
procedure downward_pass
(
,
)
#
for#
∈
odd
𝑘,ℓ
#
.val +=
1
. pred.val
.val +=
1
. succ.val
#
end
#
for#
∈
even
𝑘,ℓ
#
.val +=
0
. pred.val
.val +=
0
. succ.val
#
end
#
end
#
/0*'/6#*2)*#7+#'*+,)*+#09+,#*2+#'/8;*#9+,*'3+.#5;,'/6#*2+#;87),5##
8)..C#&;*#09+,#*2+#0;*8;*#9+,*'3+.#5;,'/6#*2+#507/7),5#8)..f
*2+#507/7),5#8)..#'.#*2+#)5Y0'/*#0I#*2+#;87),5#0/+C#.0#7+#3)/#
8+,I0,4#*2+#507/7),5#-(*+,#8)..#&<#,+8()<'/6#*2+#;87),5#8)..##
08+,)*'0/.#'/#*2+#,+9+,.+#0,5+,"#
# !/#8,)3*'3+C#7+#4;.*#-,.*#32+3J#*2)*#*2+#*70#80'/*+,.#. pred#
)/5#. succ#2)9+#&++/#'/'*')('W+5"#!I#/0*C#7+#)..'6/#*0#*2+4#*2+#
30,,+.80/5'/6#9+,*'3+.#I,04#"#>+#'48(+4+/*##).#)#2).2#.+*#
*0#I)3'('*)*+#+_3'+/*#(00J;8#;.'/6#9+,*+]#300,5'/)*+."#k00J;8.#
*2+,+I0,+#'/3;,#(1)#30.*#0/#)9+,)6+#,+6),5(+..#0I#*2+#/;4&+,#
0I#9+,*'3+.#'/#"#D'/3+##'.#.8),.+#'/#
𝐾
C#3+,*)'/#9+,*'3+.#4)<#
&+#4'..'/6#)#8,+5+3+..0,#0,#)#.;33+..0,"#Q;,'/6#*2+#('I*'/6C#*2+#
4'..'/6#9+,*'3+.#),+#)55+5#*0##*0#8,08)6)*+#*2+#B);..')/#&(;,#
I,04#0/+#5'4+/.'0/#*0#)/0*2+,p#.++#:'6"#\"#=55'*'0/#0I#9+,*'3+.#
*0##3)/#&+#.++/#).#*2+#5'()*'0/#0I#*2+#.'6/)(#.;880,*#5;,'/6#*2+#
30/90(;*'0/#0I#*2+#.'6/)(#&<#)#-(*+,#J+,/+("#
# >+#I;,*2+,#,+5;3+#*2+#/;4&+,#0I#(00J;8#08+,)*'0/.#,+^;',+5#
&<#8,08)6)*'/6#/+'62&0,2005#)/5#()**'3+#&0;/5),'+.#I,04#(+9+(#
#*0#(+9+(#+ 1#).#('I*'/6#8,06,+..+."#=*#(+9+(#C#*2+#32'(5#9+,*+]#
)*#)/#055#(03)*'0/#2
ℓ
(2+ 1)#'.#)5Y)3+/*#*0#*70#8),+/*#9+,*'3+.#
)*#(03)*'0/.#2
ℓ
2= 2
ℓ+1
#)/5#2
ℓ
(2+ 2) = 2
ℓ+1
(+ 1)"#K+#
8),+/*#9+,*'3+.#),+#)5Y)3+/*#)*#(+9+(#+ 1C#.0#7+#40,)('W+X#
#
procedure
moralize
(
,
)
#
#
for#
∈
odd
𝑘,ℓ
`@Ta#
#
. pred.succ= .succ
. succ.pred = .pred
#
end
#
end
#
)/5#5+(+*+#*2+#0551'/5+]+5#9+,*+]# )*#*2+#.)4+#*'4+#.'/3+#'*#'.#
/0#(0/6+,#,+^;',+5"#!I#4+40,<#'.#/0*#)/#'..;+C#7+#3)/#8,+.+,9+#
*2+#0551'/5+]+5#9+,*'3+.#I0,#5+40,)('W)*'0/#()*+,C#0&9')*'/6#*2+#
/++5#*0#(00J#;8#32'(5#9+,*'3+.#5;,'/6#*2+#507/7),5#8).."#!/#)/#
)/)(060;.#4)//+,C#7+#5+40,)('W+#8),+/*#9+,*'3+.#;.'/6##
#
procedure#demoralize(, )
#
#
for#∈
odd
𝑘,ℓ
`@Ua#
#
#
. pred.succ=
. succ.pred =
#
end
#
end
#
*0#,+.*0,+#8),+/*#9+,*'3+.#*0#*2+',#.*)*+.#8,'0,#*0#40,)('W)*'0/"#
l!" #eg$('T)$@):(R"T#)hT#!TRM#
# k),6+,#-(*+,.#3)/#2+(8#,+5;3+#.8+3*,)(#)(').'/6#'/*,05;3+5#&<#
@18E)_E)%1./0434)PS.2H1,4.)FG)F0640.)𝑀 = 1, 4)W.DFJ,)+.)54031/+H)H1,4.Y)+,6)3D4)
Q+-..1+,)G-,/31F,.)+3)3D4)/F004.2F,61,8)./+H4)𝜎)W.DFJ,)+.).D+646)+04+.YE)I4)
PS.2H1,4)GF0)𝑀 = 4
)/HF.4HB)+220Fc1K+34.)3D4).+K2H4.)FG)3D4)Q+-..1+,)/-054E
#
Linear B-spline (𝑀 = 1) Septic B-spline (𝑀 = 4)
𝐻
=
1/2#
𝐻
=
√
2
6088 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 29, 2020
#
.;&1.)48('/6#)*#+)32#8<,)4'5#(+9+("#!/#0/+#5'4+/.'0/C#-(*+,'/6#
)#.'6/)(#;.'/6#)#(),6+#.<44+*,'3#J+,/+(#3)/#&+#'48(+4+/*+5#&<#
)(*+,/)*'/6##('I*'/6#.*+8.#(dual, primal, . . . )#'I#*2+#J+,/+(#2).#
(+/6*2#2 + 1 = 5, 9, 13, . ..#)/5##.*+8.#(primal, dual, . . . )#
'I#*2+#-(*+,#(+/6*2#'.#2 + 1 = 3, 7, 11, . ..#K+#0,5+,'/6#0I#*2+#
('I*'/6#.*+8.#'.#5'b+,+/*#I0,#*2+#*70#3).+.#*0#+/.;,+#*2)*#*2+#().*#
.*+8#'.#)(7)<.#8,'4)(#`.'/3+#7+#8,+.+,9+#0/(<#*2+#+9+/1'/5+]+5#
+(+4+/*.C#-/'.2'/6#*2+#('I*'/6#7'*2#)#5;)(#.*+8#70;(5#7).*+#*2+#
().*#('I*'/6#.*+8a"#=88+/5']#=#8,09'5+.#)#6+/+,)(#+]8,+..'0/#I0,#
*2+#('I*'/6#30+_3'+/*.#0I#E1.8('/+#J+,/+(."#
# N0#6;'5+#*2+#320'3+#0I#-(*+,C#7+#/0*+#-,.*#*2)*#-(*+,#J+,/+(##
'.#,+^;',+5#*0#&+#0551(+/6*2#)/5#.<44+*,'3"#i&.+,9'/6#*2)*#*2+#
507/7),5#-(*+,#8)..#
ℓ
= ∗(↑
2
ℓ+1
)#3)/#&+#7,'**+/#).#
#
𝑣+0
ℓ
= 2
2𝑚+0
𝑣+𝑚
ℓ+1
𝑚∈ℤ
#
`@d
a
#
#
𝑣+1
ℓ
= 2
2𝑚+1
𝑣+𝑚
ℓ+1
𝑚∈ℤ
,
#
*2+#.+30/5#,+^;',+4+/*#&+304+.#
#
2
2𝑚+0
𝑚∈ℤ
= 2
2𝑚+1
𝑚∈ℤ
= 1,#
`FVa#
.0#*2)*#*2+#*70#82).+.#2)9+#'5+/*'3)(#)9+,)6+#&,'62*/+..+."#
# e0/.*,;3*'/6#B);..')/#J+,/+(.#&<#.)48('/6#*2;.#,+^;',+.#;.#
*0#3200.+#)#.;'*)&(+#-(*+,#.3)(+#)/5#(+/6*2C#)/5#,+/0,4)('W+#*2+#
+9+/1#)/5#0551'/5+]+5#.)48(+#+(+4+/*.#*0#.)*'.I<#`FVa"#>+#3)/##
30/.'5+,#'/.*+)5#J+,/+(.##720.+#Z1*,)/.I0,4#2).#*2+#I0,4##
#
() = 2
−2𝑀
(+ 2 +
−1
)
𝑀
,#
`F@a#
*2)*#'.C#)#5'.3,+*+#E1.8('/+#?PdAC#?RVA#0I#0,5+,#2#7'*2#*2+#-(*+,#
.3)(+#
/2"#=((#0;,#8,+9'0;.(<#'480.+5#,+^;',+4+/*.#0I#055#
-(*+,#(+/6*2C#.<44+*,<#)/5#W+,0#H<^;'.*#6)'/#),+#);*04)*'3)((<#
.)*'.-+5"#:0,#)#.;_3'+/*(<#(),6+#C#*2+#-(*+,#30+_3'+/*.##),+#
)#3(0.+#)88,0]'4)*'0/#0I#*2+#.)48(+5#B);..')/#I;/3*'0/X#
#
𝑛
≈
1
√

e
−
𝑛
2
𝑀
`FFa#
`.++#:'6"#Ta"#K'.#I0((07.#5',+3*(<#I,04#*2+#Q+#O0'9,+1k)8()3+#
*2+0,+4#?R@AC#)/5#8),)((+(.#*2+#30/9+,6+/3+#0I#E1.8('/+.#*0#*2+#
B);..')/#'/#*2+#30/*'/;0;.#504)'/"#N<8'3)((<C#;.'/6#)#E1.8('/+#
J+,/+(#8,09'5+.#-(*+,'/6#'48,09+4+/*.#0I#1SF#5E#3048),+5#*0#
;.'/6#)#.)48(+5#B);..')/#J+,/+(#7'*2#*2+#.)4+#-(*+,#.3)(+"#>+#
('.*#*2+#('I*'/6#30+_3'+/*.#
𝑛
#I0,#E1.8('/+#J+,/+(.#'/#N)&(+#!"#
## G.'/6#*2+#5'.3,+*+#('/+),#E1.8('/+#-(*+,#` = 1a#I0,#&(;,,'/6#
.*'((#8,09'5+.#)#.('62*#'48,09+4+/*#'/#)33;,)3<C#3048),+5#7'*2#
;.'/6#&),<3+/*,'3#,+.)48('/6#I0,#.8()**'/6#)/5#.('3'/6"#>+#-/5#
*2)*#*2+#3;&'3#E1.8('/+#-(*+,# = 2#8,09'5+.#)#6005#)33;,)3<1
+_3'+/3<#*,)5+10b"#=(*20;62#E1.8('/+.#3)/#0/(<#)32'+9+#-(*+,#
.3)(+.#
√
0.5,
√
1.0,
√
1.5, . . . C#0/+#3)/#.*'((#)32'+9+#)/<#5+.',+5#
09+,)((#-(*+,#.3)(+#&<#.+**'/6#*2+#.8()*#.3)(+#`[a#)88,08,')*+(<"##
l!!" =%7^"(eT)k(@"(!Q)7!%)e$*^RTi("O#
# K+#,;//'/6#*'4+#0I#B);..')/#('I*'/6#'.#('/+),#'/#*2+#/;4&+,#
0I#9+,*'3+.#'/#C#.0#7+#4)<#30/.'5+,#)#.('62*(<#405'-+5#('I*'/6#
.32+4+#72'32#3,+)*+.#I+7+,#'/*+,4+5')*+#9+,*'3+.#).#*2+#('I*'/6#
8,06,+..+."#>+#-,.*#0&.+,9+#*2)*C#)*#+)32#(+9+(C#*2+#.0(+#8;,80.+#
0I#/+7#9+,*'3+.#3,+)*+5#)*#055#(03)*'0/.#'.#*0#8,08)6)*+#*2+#&(;,#
&+*7++/#*70#9+,*'3+.#)*#+9+/#(03)*'0/."#K+#('I*'/6#.*+8.#0I#*2+#
.;&.+^;+/*#(+9+(.#)/5#5'4+/.'0/.#50#/0*#'/5+]#*2+#055#9+,*'3+.#
0I#*2+#3;,,+/*#(+9+(C#.0#7+#4)<#.J'8#3,+)*'/6#9+,*'3+.#)*#*2+#055#
(03)*'0/."#>+#,+I+,#*0# *2'.#.32+4+#).#0;,#5;)(1)5)8*'9+#.32+4+#
.'/3+#5;)(#('I*'/6#.*+8.#),+#)5)8*+5#/0*#*0#3,+)*+#9+,*'3+."#!/#0;,#
+]8+,'4+/*.C#7+#0&.+,9+#*2)*#5;)(1)5)8*+5#('I*'/6#3)/#5+3,+).+#
*2+#/;4&+,#0I#9+,*'3+.#8,03+..+5#*0#)&0;*#PVq#72'(+#'/3;,,'/6#
)#-(*+,'/6#'/)33;,)3<#0I#1S2#dB#,+()*'9+#*0#0;,#2'62(<#)33;,)*+#
/0/1)5)8*+5#('I*'/6#.32+4+"#:'(*+,'/6#+]8+,'4+/*.#0I#D+3*'0/#r#
),+#&).+5#0/#0;,#5;)(1)5)8*'9+#('I*'/6#.32+4+"#>+#'((;.*,)*+#*2+#
5;)(1)5)8*'9+#('I*'/6#.32+4+#'/#:'6"#U"#
# Z,'4)(#('I*'/6#.*+8.#),+#/0*#)5)8*+5#'/#*2+#.)4+#7)<#&+3);.+#
)5)8*'/6#*2+4#'/*,05;3+.#)#(),6+#-(*+,'/6#'/)33;,)3<#`[ST#dB#
,+()*'9+#*0#*2+#;/)5)8*+5#('I*'/6#.32+4+a"#i*2+,#)5)8*'9+#('I*'/6#
*+32/'^;+.C#*,)5'*'0/)((<#;.+5#*0#5+.'6/#)5)8*'9+#)/5#/0/1('/+),#
*,)/.I0,4.#?RFC#e2"#PAC#3)/#)(.0#&+#)88('+5#*0#0;,#I,)4+70,J#*0#
30/.*,;3*#-(*+,.#7'*2#5'b+,+/*#+56+18,+.+,9'/6#8,08+,*'+."#
# O0,+#I;/5)4+/*)((<C#7+#3)/#/07#+]8,+..#*2+#3048;*)*'0/)(#
3048(+]'*<#0I#('I*'/6#).#(
𝐾
)C#72+,+##5+/0*+.#*2+#-(*+,m.#
5'4+/.'0/)('*<C##'.#*2+#/;4&+,#0I#'4)6+#.)48(+.C#)/5#C#*2+#
6,07*2#I)3*0,#5+*+,4'/+5#&<#*2+#/;4&+,##0I#('I*'/6#.*+8.#)/5#
*2+#)5)8*'9'*<#0I#*2+#5;)(#('I*'/6#.*+8."#i;,#('I*'/6#.32+4+.#*2;.#
.3)(+#+]80/+/*')((<#7'*2#"#$07+9+,C##'.#,+()*'9+(<#.4)((C#.0##
*2+#,;//'/6#*'4+#0I#0;,#-(*+,#'.#3048),)&(+#*0#40.*#0*2+,#2'621
5'4+/.'0/)(#B);..')/#-(*+,.C#).#.++/#'/#D+3*'0/#r"#%]80/+/*')(##
.3)()&'('*<#0I#.+8),)&(+#-(*+,'/6#'/#2'62#5'4+/.'0/.#)(.0#80'/*.#
*0#*2+#/++5#I0,#.;&1.)48('/6#&+*7++/#(+9+(.#)/5#5'4+/.'0/.#'/#
*2+#-,.*#8()3+"#!I#/0#.;&1.)48('/6#'.#'/90(9+5C##&+304+.#9+,<#
(),6+C#72'32#(+)5.#*0#)#,)8'5#+]80/+/*')(#6,07*2#'/#*2+#/;4&+,#
0I#9+,*'3+.#*0#,+/5+,#.+8),)&(+#-(*+,'/6#'/*,)3*)&(+"#>+#-/5#*2)*#
= 1.14, 1.37, 1.37, 1.58#`/0#hkNaC#)/5#1.11, 1.31, 1.31, 1.47#
`7'*2#hkNa#+48','3)((<C#I0,# = 2
∗
, 2, 3
∗
, 3#,+.8+3*'9+(<"#$+,+#
*2+#∗#5+/0*+.#*2+#30,,+.80/5'/6#)5)8*'9+#('I*'/6#.32+4+."#
l!!!" cTR7"($!)"$)>7e T R T " M #
# !/#4;(*'1.3)(+#'4)6+#8,03+..'/6C#7)9+(+*#('I*'/6#.32+4+.#),+#
;.+5#*0#)/)(<W+#)/5#.</*2+.'W+#'4)6+.#7'*2#7)9+(+*#&).+."#i;,#
('I*'/6#.32+4+.#3)/#&+#'/*+,8,+*+5#).#)#7)9+(+*#*,)/.I0,4#.'/3+#
0;,#;87),5#)/5#507/7),5#-(*+,#8)..+.#30,,+.80/5#*0#)/)(<.'.#
)/5#.</*2+.'.C#,+.8+3*'9+(<C#0I#*2+#'4)6+#'/#*2+#-(*+,#&).'."#K'.##
30//+3*'0/#&+*7++/#7)9+(+*#*,)/.I0,4.#)/5#0;,#('I*'/6#.32+4+#
3)/#&+#;.+5#*0#)/)(<W+#*2+#09+,)((#-(*+,#,+.80/.+#0I#0;,#.32+4+##
&).+5#0/#*2+#5'.3,+*+#E1.8('/+#-(*+,#J+,/+(."#>+#)(.0#.207# *2)*#
Input 𝑥
ℓ
Adapted step
Primal step
1
#
Output 𝑥
ℓ+1
1
#
2
#
2
#
@18E):E)%-+HS+6+2346)H1G31,8)+22H146)F,)+).2+0.4)F,4S61K4,.1F,+H).18,+HE)T54,S)
+,6)F66S1,64c46)54031/4.)+04).DFJ,)+.)AH+/N)+,6)80+B)6F3.)04.24/3154HBE)%-+H)
H1G31,8)D+.)A44,)+6+2346),F3)3F)/04+34),4J)54031/4.;)JD1/D)20F6-/4.)+).2+0.40)
F-32-3).18,+HE)'GE)@18E)VE)
YOUNG et al.: GAUSSIAN LIFTING FOR FAST BILATERAL AND NONLOCAL MEANS FILTERING 6089
#
0;,#('I*'/6#I,)4+70,J#'.#/0*#)#*,;+#7)9+(+*#*,)/.I0,4"#
# =#7)9+(+*# *,)/.I0,4#&).+5#0/#)#-(*+,1&)/J#4+*205#,+^;',+.#
5+.'6/'/6#)/)(<.'.#(071#)/5#2'6218)..#-(*+,.##)/5#C#,+*)'/'/6#
*2+#.'6/)(.#
#
ℓ+1
=↓
2
(
∗
ℓ
)
,
ℓ+1
=↓
2
(
∗
ℓ
)#
`FPa#
I0,#= 0, . . . , −1"#K+#-,.*#+]8,+..'0/#0I#`FPa#'.#*2+#;87),5#
-(*+,#8)..#.++/#+),('+,C#&;*#6'9+/#
ℓ+1
#)/5#
ℓ+1
C#7+#/07#2)9+#
*2+#)&'('*<#*0#,+309+,#
ℓ
"#K+#,+309+,<#3)/#&+#7,'**+/#).#
#
ℓ
=
∗(↑
2
ℓ+1
) + ∗(↑
2
ℓ+1
)#
`FRa#
I0,#= −1, . . . , 0C#72+,+#
#)/5##),+#*2+#(071#)/5#*2+#2'621
8)..#.</*2+.'.#-(*+,.#5+,'9+5#I,04##)/5#"#
# G.'/6#*2+#('I*'/6#.32+4+C#7+#3)/#0&*)'/#*2+#.'6/)(#
ℓ+1
#`FPa#
&<#(+**'/6#
𝑛
ℓ+1
=
2𝑛+1
ℓ
#I0,#∈#)I*+,#*2+#'/8;*#.'6/)(#
ℓ
#2).##
&++/#*,)/.I0,4+5#9')#;85)*+.#`da"#!I#*2+#('I*'/6#.32+4+#'.#&).+5#
0/#*70#('I*'/6#.*+8.#` = 2aC#*2+#J+,/+(.#C#C#
#)/5##'48('+5#
&<#*2+#('I*'/6#.*+8.#),+#
#
() #
= (+1
2
+ 4
1
+ 6
0
+ 4
−1
+ 1
−2
)/16#
`F[a#
#
()
= (+1
1
+ 4
0
+ 1
−1
)
−1
/6
#
() #
= (−1
1
+ 4
0
−1
−1
)/6#
#
() #
= (+1
2
−4
1
+ 6
0
−4
−1
+ 1
−2
)
−1
/16#
`.++#=88+/5']#Ea"#H0*+#*2)*#&0*2##)/5# ),+#(0718)..#J+,/+(.#
'/#*2'.#3).+C#2'/*'/6#*2)*#0;,#('I*'/6#.32+4+#50+.#/0*#'48(+4+/*#
)#7)9+(+*#*,)/.I0,4"##
# K+#,+()*'0/.2'8#&+*7++/#`FRa#)/5#*2+#507/7),5#-(*+,#8)..#
&+304+.#3(+),+,#'I#7+#7,'*+#*2+#507/7),5#-(*+,#8)..#).#
#
ℓ
= ∗
(
↑
2
ℓ+1
)
+ ∗
(
↑
2
ℓ+1
)#
`F\a#
I0,#= −1, . . . , 0C#'/#72'32#7+#'/'*')('W+#
𝐿−1
=
𝐿−1
#)/5#
= "#K+/C#*2+#507/7),5#-(*+,#8)..#30,,+.80/5.#*0#.</*2+.'.#
;.'/6#8,'4)(#-(*+,.#(, )C#)/5#,+30/.*,;3*'0/#`FRa#'.#.</*2+.'.#
;.'/6#5;)(#0/+.#(
, )"#i;,#B);..')/#('I*'/6#I,)4+70,J#'.#*2;.#
,+()*+5#*0C#&;*#/0*#'5+/*'3)(#*0C#7)9+(+*#('I*'/6"#:'6"#d#'((;.*,)*+.#
*2+#5'b+,+/3+#&+*7++/#B);..')/#('I*'/6#)/5#7)9+(+*#('I*'/6"#
# O0,+09+,C#72'(+#*2+#,+()*'0/.2'8#&+*7++/#`FPa#)/5#`FRa#4)<#
20(5#I0,#4)/<#-(*+,#8)',.#(, )#)/5#(
, )C#/0*#)((#0I#*2+4#),+#
*,;+#7)9+(+*#*,)/.I0,4."#K+#*,)/.I0,4#4)*,']#5+-/+5#&<#.*+8.#
`FPa#2).#)#30/5'*'0/#/;4&+,#0I#∞#'/#*2+#('4'*#).#→∞"#K'.#
'.#+]8+3*+5#.'/3+#0;,#J+,/+(.##)/5##),+#&0*2#(0718)..C#.0#*2+#
&).'.#I;/3*'0/.#*2+<#<'+(5#),+#)(40.*#30(('/+),#)*#2'62#(+9+(.#0I#
*2+#8<,)4'5"#%9+/#72+/##'.#-/'*+C#*2+#(),6+#30/5'*'0/#/;4&+,#
0I#*2+#*,)/.I0,4#2'/5+,.#*2+#;.+#0I#*2+#'/9+,.+#*,)/.I0,4C#.'/3+#
'*#)48('-+.#.4)((#,0;/5'/6#+,,0,.#'/#('I*'/6#30+_3'+/*.#*0#(),6+#
+,,0,."#K+#30/.*,;3*'0/#0I#)#.*)&(+#E1.8('/+#7)9+(+*#*,)/.I0,4#
'.#5'.3;..+5#'/#?RPAC#?RRA"#=#&'()*+,)(#-(*+,#)88,0)32#*0#7)9+(+*#
5+/0'.'/6#'.#5'.3;..+5#'/#?R[A"#
!r" %i^T#(*T!"7R)cTM&R"M#
# >+#)/)(<W+#*2+#)33;,)3<#)/5#,;//'/61*'4+#32),)3*+,'.*'3.#0I#
0;,#-(*+,#'48(+4+/*)*'0/#I0,#9),'0;.#-(*+,#30/-6;,)*'0/.#;.'/6#
*2+#h05)J#N,;+#e0(0,#'4)6+#5)*).+*C#72'32#30/*)'/.#FR#'4)6+.#
0I# = 512 ×768#8']+(.#+)32"#=((#-(*+,#'48(+4+/*)*'0/.#;.+5#
'/#*2+#+]8+,'4+/*.#),+#8,09'5+5#&<#*2+#,+.8+3*'9+#);*20,.
1
"#K+#
6,0;/51*,;*2#-(*+,#'4)6+#'.#6+/+,)*+5#&<#+9)(;)*'/6#`@a#;.'/6#)#
('4'*+5#.8)*')(#.;880,*#0I#
−3
𝑋,𝑌
, +3
𝑋,𝑌
2
"#=((#*'4'/6.#),+#
0&*)'/+5#0/#)#.'/6(+#30,+#0I#)#F"T#B$W#!/*+(#e0,+#'[#eZG"#
A. Grayscale Bilateral Filtering
# >+# -(*+,# *2+# 6,)<.3)(+130/9+,*+5#30;/*+,8),*.#0I#*2+#h05)J#
'4)6+#5)*).+*#)*#5'b+,+/*#-(*+,#.3)(+.C#)/5#3048),+#0;,#0;*8;*.#
)6)'/.*#*2+#6,0;/5#*,;*2#0;*8;*#0&*)'/+5#&<#5',+3*(<#3048;*'/6#
`Pa"#>+#;.+#ZDHc#)/5#DD!O#&+*7++/#*2+#*70#0;*8;*.#*0#6);6+#
*2+#0&Y+3*'9+#^;)('*<#0I#-(*+,#'48(+4+/*)*'0/"#N)&(+#!!#8,09'5+.#
)#.;44),<#0I#*2+#ZDHcC#DD!OC#)/5#,;//'/6#*'4+.#0I#0;,#-(*+,#
30/-6;,)*'0/."#:0,#3048),'.0/.C#*2+#,+.;(*.#0I#6,)<.3)(+#-(*+,.#
?FRAC#?FUAC#?FdA#2)9+#)(.0#&++/#'/3(;5+5"#i&.+,9+#*2+#B);..')/#
('I*'/6#-(*+,#8,09'5+.#40,+#I)90,)&(+#)33;,)3<1.8++5#*,)5+10b.#
3048),+5#*0#0*2+,#-(*+,#'48(+4+/*)*'0/."#=#9'.;)(#3048),'.0/#
0I#*2+#5'b+,+/*#-(*+,.#'.#6'9+/#'/#:'6"#@V"#!/#:'6"#@@C#7+#8(0*#*2+#
ZDHc#)/5#,;//'/6#*'4+.#0I#0;,#&'()*+,)(#-(*+,#)3,0..#9)(;+.#0I#
*2+#,)/6+#-(*+,#.3)(+#
𝑍
C#.207'/6#0;,#-(*+,#'.#&0*2#)33;,)*+#)/5#
+_3'+/*#09+,#)#7'5+#,)/6+#0I#*2+#-(*+,#.3)(+."#
B. Color Bilateral Filtering
# N0# +]8,+..#30(0,# &'()*+,)(#-(*+,'/6C#7+#.;&.*'*;*+#∈
𝑁
#`Pa#
I0,#∈
𝑁×3
"#K+#9+,*'3+.#'/#*2+#-(*+,#4)*,']##&+304+#
#
𝑛
=
𝑛
𝑋
𝑛
𝑌
𝑛1
𝑍
𝑛2
𝑍
𝑛3
𝑍
#
`FTa#
I0,#1 ≤≤"##
# N)&(+#!!!#)/5#:'6"#@P#.207#*2+#)33;,)3<1+_3'+/3<#*,)5+10b.#
0I#0;,#-(*+,#)*#.+(+3*#80'/*.##)/5#= 
𝑋,𝑌
,
𝑍
C#&0*2#7'*2#
)/5#7'*20;*#*2+#hkN#&+I0,+#*2+#.8()**'/6"#>+#)9+,)6+#*2+#-(*+,#
ZDHc#)/5#,;//'/6#*'4+#)3,0..#.3)(+.#
𝑋,𝑌
= 8, 12, 16, 24, 32#
)/5#
𝑍
= 16, 24, 32, 48, 64#`)#*0*)(#0I#F[#304&'/)*'0/.a#)3,0..#
FR#'4)6+."#:0,#,+I+,+/3+C#*2+#,+.;(*.#0I#?FVAS?FRA#),+#'/3(;5+5"#
# :0,#0;,#-(*+,C#7+#.++#*2)*#;.'/6#*2+#hkN#'48,09+.#*2+#ZDHc#
0I#*2+#-(*+,+5#'4)6+#&<#;8#*0#R#dBC#)/5#,+5;3+.#,;//'/6#*'4+.#
&<#;8#*0#0.2."#`>+#-/5#.'4'(),#'48,09+4+/*.#0/#@VVV#,)/504#
'4)6+.#I,04#!4)6+H+*#?R\AC#7'*2#P"@V#5E#)/5#P"dR#5E#ZDHc#
6)'/.#I0,#-(*+,#30/-6;,)*'0/.#U#)/5#@VC#,+.8+3*'9+(<"a#K+#hkN#
.*+8#*)J+.#0.03.#0/#)9+,)6+#I0,#)#512 ×768#'4)6+"#>+#.++#*2+#
('I*'/6#.32+4+# = 2
∗
C#= (1,1)#6'9+.#;.#)#*,)5+0b#&+*7++/#
@18E)>E)'FK2+01.F,)A43J44,)F-0)3JFSH454H)Q+-..1+,)H1G31,8)./D4K4)W3F2Y)+,6)+)
3JFS/D+,,4H)240G4/3)04/F,.30-/31F,)\H340)A+,N)WAF33FKY)GF0)+)F,4S61K4,.1F,+H)
.18,+HE)Q+-..1+,)H1G31,8)4..4,31+HHB)-.4.)F,4)2+10)FG)\H340.)GF0)AF3D)+,+HB.1.)+,6)
.B,3D4.1.)JD404+.)240G4/3)04/F,.30-/31F,)84,40+HHB)04b-104.)3JFE
#
Gaussian lifting scheme
Perfect reconstruction filterbanks
↓2
↓2
↓2
↓2
0#
out
↑2
↑2
↑2
↑2
↓2
↓2
↓2
↓2
↑2
↑2
↑2
↑2
)
1
7)'jj)1K2H4K4,3+31F,)FG)F-0)Q+-..1+,)H1G31,8)\H340)/+,)A4)6FJ,HF+6)G0
FK)
D332L]]JJJE813D-AE/FK].4+,,d]8+-..1+,
)
6090 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 29, 2020
#
-(*+,#)33;,)3<#)/5#+_3'+/3<#3(0.+#*0#*2+#8+,4;*02+5,)(#()**'3+#
-(*+,#?F@A"#!/#I)3*C#0;,#70,J#7).#'/'*')((<#40*'9)*+5C#'/#8),*C#&<#
*2+#'/)&'('*<#0I#?F@A#*0#8,09'5+#)/#2'62+,#-(*+,'/6#)33;,)3<"#K+#
08+,)*'/6#80'/*.#0I#)((#0*2+,#-(*+,.#('+#.*,'3*(<#'/.'5+#*2+#30/9+]#
2;((#0I#0;,#07/#30/-6;,)*'0/.#)/5#*2+#8+,4;*02+5,)(#-(*+,#0/+#
?F@A"#:'6"# @F# 8,09'5+.# )# 9'.;)(#3048),'.0/# 0I# '4)6+.#-(*+,+5#
;.'/6#5'b+,+/*#30/-6;,)*'0/."
C. Nonlocal Means Filter Experiments
# N0#+])4'/+#*2+#8+,I0,4)/3+#)/5#+_3'+/3<#32),)3*+,'.*'3.#0I#
0;,#-(*+,#I0,#'4)6+#5+/0'.'/6C#7+#)(.0#8+,I0,4#/0/(03)(#4+)/.#
0/#*2+#h05)J#'4)6+#5)*).+*"#:0,#*2'.#+]8+,'4+/*C#7+#)508*#*2+#
8)*32#Ze=#.*,)*+6<#0I#N).5'W+/#?F[A"#k+*#;.#5+/0*+#&<#
𝑛𝑝
C#*2+#
*2#Ze=#30+_3'+/*#0I#*2+#30(0,#×#8)*32C#3+/*+,+5#),0;/5#
*2#.)48(+C#72+,+#1 ≤ ≤#I0,#)#6'9+/#"#H0/1(03)(#4+)/.#
5+/0'.'/6#0I#30(0,#'4)6+.#'.#+]8,+..+5#;.'/6#`PaC#7'*2#9+,*'3+.#
/07#5+-/+5#).#
#
𝑛
=
𝑛
𝑋
𝑛
𝑌
𝑛1
𝑍
𝑛2
𝑍
. . .
𝑛𝑃
𝑍
#
`FUa#
I0,#1 ≤≤"#>+#3200.+# = 6C#= 7#).#,+3044+/5+5#&<##
?F[AC#.;32#*2)*#*2+#,+.;(*'/6#/0/(03)(#4+)/.#-(*+,#'.#)#B);..')/#
-(*+,#'/# = 8#5'4+/.'0/."#
# N)&(+#!l#)/5#:'6"#@[#8,09'5+#*2+#5+/0'.+5#'4)6+#ZDHc#)/5#
DD!O#09+,#*2+#.*)/5),5#5+9')*'0/.# = 8, 12, 24, 32, 48C#0I#*2+#
/0'.+"#>+# 8,09'5+#0/(<#*2+#-(*+,#30/-6;,)*'0/.#720.+#*'4'/6.#
),+#< 5."##:0,#,+I+,+/3+C#7+#'/3(;5+#*2+#5+/0'.+5#'4)6+#ZDHc#
,+.;(*.#I,04#*2+#0*2+,#2'62#5'4+/.'0/)(#-(*+,#'48(+4+/*)*'0/.#
).#7+((#).#EOPQ#?RTAC#72'32#'.#)(.0#&).+5#0/#/0/1(03)(#4+)/.#
8,'/3'8(+."#:0,#2'6215'4+/.'0/)(#-(*+,.C#7+#.+*#*2+#8),)4+*+,.#
*0#
𝑋,𝑌
= 6#)/5#
𝑍
= #).#,+3044+/5+5#&<#?F[AC#72+,+#7+#
;.+# = 2.33#I0;/5#9')#6,'5#.+),32#0/#*2+#h05)J#5)*).+*"#
# >+#/0*'3+#*2)*#I0,#'4)6+#5+/0'.'/6C#-(*+,'/6#40,+#)33;,)*+(<#
50+.#/0*#/+3+..),'(<#30,,+.80/5#*0#&+**+,#5+/0'.'/6#,+.;(*.C#)/5#
)((#-(*+,#30/-6;,)*'0/.#2)9+#.'4'(),#ZDHc"#:'(*+,'/6#7'*2#W+,0#
('I*'/6#.*+8.#` = 0a#6'9+.#;.#-(*+,'/6#,+.;(*.#*0#7'*2'/#V"[#5E#
0I#*2+#40,+#)33;,)*+#`.*),,+5a#30/-6;,)*'0/C#&;*#*)J+.#0/(<#0/+#
*+/*2#0I#*2+#*'4+"#G.'/6#*2+#hkN#8,'0,#*0#.8()**'/6#.'6/'-3)/*(<#
,+5;3+.#*2+#,;//'/6#*'4+#)/5#'48,09+.#*2+#ZDHc#.('62*(<"#K+#
8+,4;*02+5,)(#()**'3+#-(*+,#5+/0'.+.#'4)6+.#.('62*(<#&+**+,#*2)/#
#
#
#
#
#
#
#
#
(a) Input / true output
(b) Compressive BF [29]
(c) Shiftable 𝑂(1) [28]
(d) 𝑀 = 3
∗
, 𝐿 = (1,1)
@18E)=<E)e1.-+H)/FK2+01.F,)FG)80+B./+H4)A1H+340+H)\H3401,8)04.-H3.)GF0)3D4)@4B,K+,)1K+84)W640 × 360)21c4H.YE)(,)W+Y;)J4).DFJ)3D4)1,2-3)1K+84)+,6)3D4)80F-,6)30-3D)
F-32-3)GF0)𝜎
𝑋,𝑌
= 8)+,6)𝜎
𝑍
= 32E)(,)WAYkW6Y;)J4).DFJ)3D4)F-32-3)FG)61f404,3)\H340.)+,6)3D410)61f404,/4.)G0FK)3D4)30-4)F-32-3)1,)W+YE)I4)61f404,/4.)D+54)A44,)
+K2H1\46)16×)3F)+16)51.-+H1d+31F,E)I4)^M!#)FG)3D4)1K+84.)+04)WAY)U>EV_)6P)W/Y)56.26)6P)+,6)W6Y)VCE=h)6PE)
"7PRT)(()
7VERAGE PSNR ] SSIM AND TIMINGS OF FILTERS ACROSS)
𝜎
𝑋,𝑌
= 8,12,16,24,32 AND 𝜎
𝑍
= 16,24,32,48,64 ON THE)
9U KODAK IMAGES WCONVERTED TO GRAYSCALEYE)
)
) *43DF6)
*+3H+A)
])'jj)
^M!#)W6PY))
])MM(*
)
758E)0-,,1,8))
31K4)W.4/Y)
$3D40)
K43DF6.)
^40K-3FD460+H)R+331/4)l9=m)
'FK204..154)P@)l9>m)
MD1G3+AH4)𝑂(1))l9:m)
!+10)+,6)'D+-6D-0B
2
)l9Um)
!+10)+,6)'D+-6D-0B
3
)l9Um)
')
*)
')
*)
*)
U:E:9)])<E>>:C)
)
UhEU=)])<E>>:h)
VUE_9)])<E>>>>)
VCE=V)])<E>>_>)
VhE>_)])
1.0000)
<E<>U)
<EC9:)
=EV<>)
<EVU=)
=E=_<
$-0)\H340)
/F,\8-0+31F,.
)
𝑀 = 2;)) 𝐿 = (1,1))
𝑀 = 3
∗
;)𝐿 = (1,1)
†
)
𝑀 = 3;)) 𝐿 = (1,1))
𝑀 = 3;)) 𝐿 = (2,1))
𝑀 = 3;)) 𝐿 = (2,2)
*
)
𝑀 = 4;)) 𝐿 = (2,2))
')
')
')
')
')
')
V<E=h)])<E>>::)
VCE:<)])<E>>>h)
VUEC<)])<E>>>_)
VhE<=)])<E>>>:)
VhE>< ])<E>>>>)
57.12
])
1.0000)
0.069
<E<_>)
<E<:U)
<E=_=)
<E9_=)
<ECh<)
#
)
2
&.1,8):)/H-.340.)J13D)𝑂(1))Q+-..1+,)/F,5FH-31F,E)
)
3
&.1,8)=V)/H-.340.)J13D)𝑂(1))Q+-..1+,)/F,5FH-31F,E)
@18E)==E)7//-0+/B)+,6)4n/14,/B)FG)F-0)\H340)1K2H4K4,3+31F,)+/0F..)0+,84)\H340)
./+H4.E)^4+N)M!#)+,6)0-,,1,8)31K4.)D+54)A44,)+540+846)+/0F..)./+H4.)𝜎
𝑋,𝑌
=
8,12, 16, 24, 32
)F,)9U)1K+84.)FG)
512 × 768
)21c4H.)'GE)"+AH4)((E#
[24]
2
Permutohedral [21]
Ours
†
Nair and Chaudhury [24]
3
Ours
*
Permutohedral [21]
Ours
†
Ours
*
[24]
2
Nair and Chaudhury [24]
3
YOUNG et al.: GAUSSIAN LIFTING FOR FAST BILATERAL AND NONLOCAL MEANS FILTERING 6091
#
0;,#-(*+,#30/-6;,)*'0/#`V"F#5Ea#7'*2#.'4'(),#,;//'/6#*'4+."#>+#
)(.0#0&.+,9+#EOPQ#?RTA#8+,I0,4.#&+**+,#*2)/#/0/1(03)(#4+)/.#
4+*205."#:'6"#@R#8,09'5+.#)#9'.;)(#3048),'.0/#0I#*2+#5+/0'.+5#
'4)6+.#;.'/6#5'b+,+/*#/0/1(03)(#4+)/.#-(*+,#'48(+4+/*)*'0/."#
r" Q(M'&MM($!#
# !/#*2'.#70,JC#7+#8,080.+#*2+#B);..')/#('I*'/6#I,)4+70,J#I0,#
I).*#&'()*+,)(#)/5#/0/(03)(#4+)/.#-(*+,'/6"#i;,#4)'/#/09+(*<#'.#
*2+#)33+(+,)*'0/#I,04#4;(*',)*+#-(*+,'/6#7'*2#*2+#('I*'/6#.32+4+#
;.+5#'/#7)9+(+*1&).+5#'4)6+#3048,+..'0/"#N0#)((07#.+8),)&(+#
('I*'/6C#7+#,+.)48(+#*2+#'/8;*#'4)6+#'/#'*.#hkN#.8)3+#;.'/6#*2+#
;.;)(#3;&'3#()**'3+"#K'.#30/*,).*.#7'*2#8,+9'0;.#4+*205.#&).+5#
0/#*2+#.8()*1&(;,1.('3+#8'8+('/+#72+,+#.3)(),C#()**'3+C#)/5#9+3*0,#
,+.)48('/6#.*,)*+6'+.#),+#;.+5"#k),6+#)33+(+,)*'0/#'.#)**,'&;*+5#
*0#*2+#,+.)48('/6#'/#*2+#hkN#504)'/#).#0880.+5#*0#*2+#/)*;,)(#
0/+C#,+5;3'/6#*2+#/;4&+,#0I#'/*+,4+5')*+#9+,*'3+.#3,+)*+5"#
# i;,#('I*'/6#)88,0)32#I)3'('*)*+.#*2+#;.+#0I#(),6+,#&(;,#J+,/+(.#
&<#.;33+..'9+(<#507/1.)48('/6#)/5#;81.)48('/6#*2+#'4)6+C#'/#
)#I).2'0/#.'4'(),#*0#*2+#30/.*,;3*'0/#0I#B);..')/#8<,)4'5."#K+#
&(;,,'/6#)*#+)32#.3)(+#'.#8+,I0,4+5#;.'/6#('I*'/6C#72'32#,+5;3+.#
*2+#/;4&+,#0I#(00J;8.#/++5+5#I0,#/+'62&0,'/6#9+,*'3+."#i7'/6#
*0#*2+#2'6210,5+,#E1.8('/+#&(;,#J+,/+(.#;.+5C#0;,#-(*+,+5#0;*8;*#
)32'+9+.#9+,<#2'62#-(*+,#)33;,)3<#)3,0..#4)/<#-(*+,#.3)(+.#)/5#
30/-6;,)*'0/.C#+.8+3')((<#I0,#6,)<.3)(+#)/5#30(0,#-(*+,#3).+."#
#
#
#
#
#
(a) Input / true output
(b) 𝑀 = 2
∗
w/o KLT
(c) 𝑀 = 2
∗
with KLT
(d) 𝑀 = 1 with KLT
(e) 𝑀 = 2 with KLT
@18E)=9E)e1.-+H)/FK2+01.F,)FG)F-0)A1H+340+HS\H34046)04.-H3.)GF0)3D4)*+/+J)1K+84)W512 × 768)21c4H.Y)+3)\H340)/F,\8-0+31F,)𝐿 = (1,1)
E)(,)W+Y;)J4).DFJ)3D4)1,2-3)
1K+84)+,6)3D4)80F-,6)30-3D)F-32-3)GF0)
𝜎
𝑋,𝑌
= 16
)+,6)
𝜎
𝑍
= 32
E)(,)WAYk
W4Y;)J4).DFJ)3D4)F-32-3)FG)F-0)\H340)+,6)13.)61f404,/4)G0FK)3D4)30-4)F-32-3)1,)W+YE)I4)
61f404,/4.)D+54)A44,)+K2H1\46)
8×
)3F)+16)51.-+H1d+31F,E)I4)24+N)M!#)FG)3D4)F-32-3)1K+84.)+04)WAY)U:Eh9)6P;)W/Y)V<E<U)6P;)W6Y)U=E9C)6P;)+,6)W4Y)52.45)6PE)
@18E)=CE)I4)4n/14,/BS+//-0+/B)/D+0+/3401.31/.)FG)F-0)\H340)1K2H4K4,3+31F,)GF0)
61f404,3) \H340) /F,\8-0+31F,.) WJ13D) 3D4) `R"YE) ^M!#) +,6) 0-,,1,8) 31K4.) +04)
+540+846)+/0F..)𝜎
𝑋,𝑌
= 8, 12, 16, 24, 32))W3F2)2HF3.Y)+,6)+66131F,+HHB)+/0F..)
𝜎
𝑍
= 16, 24, 32, 48, 64
)WAF33FKY)F,))9U)1K+84.)FG)
512 × 768
)21c4H.)4+/DE
#
[21]
[24]
3,5
6
7
8
10
[22]
[23]
9
[24]
2,5
11
"7PRT)((()
7VERAGE PSNR AND TIMINGS OF FILTERS ACROSS)
𝜎
𝑋,𝑌
= 8,12,16,24,32 AND 𝜎
𝑍
= 16,24,32,48,64 ON THE)
9U `ODAK IMAGESE ^ARETOSOPTIMAL CONFIGURATIONS IN BOLDE)
)
) *43DF6)
*+3H+A)
])'jj
)
^4+N)M!#)
W6PY
)
758E)0-,,1,8))
31K4)W.4/Y
)
$3D40
)
K43DF6.
)
76+23154)*+,1GFH6.)l99m)
Q+-..1+,)𝐾%S3044)l9<m)
QHFA+H)'FHF0)M2+0.13B
4
)l9Cm
^40K-3FD460+H)R+331/4)l9=m)
!+10)+,6)'D+-6D-0B
2,5
)l9Um)
!+10)+,6)'D+-6D-0B
3,5
)l9Um)
*)
')
')
')
*)
*)
C>E99)
ChE__)
UhE=U)
48.39
ChE:V)
U9E9<)
<ECUU)
=EU<U)
<E9VC)
0.191
<EU9<)
=E<_<
)
$-0.)J13D
)
WJ]FY)`R"
)
𝑀 = 1;)) 𝐿 = (0,1))
6
𝑀 = 1;)) 𝐿 = (1,1))
𝑀 = 2
∗
;)𝐿 = (0,1))
7
)
𝑀 = 2
∗
;)𝐿 = (1,1))
8
)
𝑀 = 2;)) 𝐿 = (0,1))
𝑀 = 2;)) 𝐿 = (1,1))
9
)
𝑀 = 3
∗
;)𝐿 = (1,1))
10
)
𝑀 = 3;)) 𝐿 = (0,1))
𝑀 = 3;)) 𝐿 = (1,1))
11
)
')
')
')
')
')
')
')
')
')
39.56)WChE=>Y)
U=E_U)WC_Eh<Y)
42.89)WU=EC9Y)
50.18)WU_ECUY)
UCEUU)WU=E_>Y)
52.28)WU>E=<Y)
54.24)WV<ECCY)
UCEU:)WU9E9_Y)
55.63)WV=E_CY)
0.132)W<E=9:Y)
) <E=:V)W<E=hUY)
0.153)W<E=_CY)
0.259)W<E9_hY)
) <E=_V)W<E=VCY)
) 0.431)W<EUU_Y)
0.585)W<EhCVY)
) <E=>>)W<E9<CY)
1.030
)W=E9C=Y
)
#
)
4
'H-.340)64/FK2F.131F,)J13D)R&%)WG+.3;)=h)/H-.340.;)64H3+)FG)=h]UYE)
)
5
&.1,8)𝑂(1))Q+-..1+,)/F,5FH-31F,)J13D)3D4)G+.3op+8)F231F,E#
Ours
8
Nair and Chaudhury [24]
3,5
[23]
4
Permutohedral [21]
Ours
7
Nair and Chaudhury [24]
3,5
[23]
4
[21]
Ours
8
Ours
7
6092 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 29, 2020
#
Improving other filters:#i/+#4)<#).J#'I#*2+#)33;,)3'+.#0I#0*2+,#
&'()*+,)(#-(*+,.#3)/#)(.0#&+#'48,09+5#&<#;.'/6#)#2'62+,10,5+,#E1
.8('/+#J+,/+(."#$07+9+,C#&(;,,'/6#;.'/6#)#2'62+,10,5+,#E1.8('/+#
J+,/+(#'/#*2+#)&.+/3+#0I#4;(*'1,+.0(;*'0/#3)/#&+#'/+_3'+/*"#:0,#
+])48(+C#*2+#8+,4;*02+5,)(#()**'3+#-(*+,#3)/#&+#405'-+5#*0#;.+#
)#2'6210,5+,#E1.8('/+#J+,/+(C#&;*#*2'.#(+)5.#*0#)#,)8'5#6,07*2#'/#
*2+#/;4&+,#0I#9+,*'3+.#*0#8,03+..#'I#7+#50#/0*#'/*+,(+)9+#507/1
.)48('/6#7'*2#&(;,,'/6"#i/+#3)/#9'+7#0;,#('I*'/6#I,)4+70,J#).#
I)3'('*)*'/6#4;(*'1,+.0(;*'0/#-(*+,'/6#0I#.8),.+#.'6/)(.#'/#)#2'62#
5'4+/.'0/C#).#/++5+5#I0,#I).*#)/5#)33;,)*+#&'()*+,)(#-(*+,'/6"#
# i/+#4)<#7)/*#*0#'/30,80,)*+#*2+#hkN#).#8),*#0I#,+.)48('/6#
'/#0*2+,#-(*+,.#).#7+(("#$07+9+,C#;.'/6#*2+#hkN#'.#3048('3)*+5#
I0,#*2+#8+,4;*02+5,)(#()**'3+#-(*+,#.'/3+#*2+#&).'.#0I#*2'.#()**'3+#
50+.#/0*#)('6/#7'*2#)#.^;),+#()**'3+#0/+"#i/#*2+#0*2+,#2)/5C#*2+#
B);..')/#Q1*,++#-(*+,#3)/#&+/+-*#&<#;.'/6#*2+#hkN#8,'0,#*0#
.8('**'/6#/05+.#)3,0..#*2+',#(0/6+.*#5'4+/.'0/."#
Further acceleration: :0,#I;,*2+,#)33+(+,)*'0/#+.8+3')((<#'/#*2+#
2'62+,#5'4+/.'0/.C#0/+#4)<#30/.'5+,#/0/.+8),)&(+#('I*'/6#?RUA#
,)*2+,#*2)/#0;,#8,080.+5#.+8),)&(+#('I*'/6#I,)4+70,J#*0#I;,*2+,#
+5;3+#*2+#/;4&+,#0I#*+480,),<#9+,*'3+.#.8)7/+5"#N0# '48,09+#
*2+#,;//'/6#*'4+#I;,*2+,C#7+#3)/#,+)5'(<#8),)((+('W+#*2+#-(*+,#)*#
)/#0;*+,#(+9+(#&<#5'9'5'/6#)/#'4)6+#'/*0#*'(+.#)/5#-(*+,'/6#*2+4#
;.'/6#*2+#09+,()81.)9+#4+*205"#=(.0C#('J+#*2+#BZG#9+,.'0/.#0I#
0*2+,#I).*#&'()*+,)(#-(*+,.#?FVAS?FFA#&).+5#0/#*2+#.8()*1&(;,1.('3+#
I,)4+70,JC#7+#+]8+3*#*2+#BZG#'48(+4+/*)*'0/#0I#0;,#-(*+,#*0#
,+^;',+#4'(('.+30/5.#0I#8,03+..'/6#*'4+#)*#,+()*'9+(<#(07#.8)*')(#
,+.0(;*'0/.#+"6"#s10
6
#8']+(."#!/#*2'.#70,JC#7+#30/.'5+,+5#0/(<#
/0/1'*+,)*'9+#&'()*+,)(#-(*+,'/6C#&;*#+]8+3*#0;,#-(*+,#*0#&+#;.+I;(#
I0,#.8++5'/6#;8#*2+#'/5'9'5;)(#'*+,)*'0/.#0I#)5)8*'9+#/0/1(03)(#
4+)/.#-(*+,'/6#?@FAC#?@RA#).#7+((#*0#&+**+,#8,+.+,9+#*+]*;,+#)/5#
+56+.#72'(+#5+/0'.'/6"#
=^^T!%(i)=#
E7#O'T!"#(')cTM7*^R(!Q#
# N0# ,+.)48(+# &),<3+/*,'3)((<#0/#3;&'3#()**'3+#
𝐾
C#7+#/++5#*0#
-,.*#30/.*,;3*#)#*,')/6;()*'0/#I0,#*2+#3+((#
[
0, 1
]
𝐾
"#=#8),*'3;(),(<#
;.+I;(#*,')/6;()*'0/#5;+#*0#h;2/#?RdA#8),*'*'0/.#
[
0,1
]
𝐾
#'/*0#*2+#
.+*#
{
∆
𝝅
}
#0I#!#.'48('3+.#72+,+#
#
∆
𝝅
=
{
∶0 ≤
𝜋
1
≤
𝜋
2
≤≤
𝜋
𝐾
≤1
}
,#
`Fda#
)/5##'.#0/+#0I#*2+#!#8+,4;*)*'0/.#0I#(1, . . . , )"#!I#7+#2)9+#
= 2C#.'48('3+.#
{
∆
𝝅
}
#),+#*2+#*70#*,')/6(+.#'/#*2+#&0**041(+I*#
.^;),+#0I#:'6"#R#`(+I*a"#=#80'/*##'/#
[
0,1
]
𝐾
#&+(0/6.#*0#Y;.*#0/+#
∆
𝝅
#'I#'*.#300,5'/)*+.#.)*'.I<#*2+#'/+^;)('*'+.#`Fda#.*,'3*(<"#>2+/#
&+(0/6.#*0#4;(*'8(+#∆
𝝅
C#7+#)..'6/#'*#*0#)/<#30/*)'/'/6#∆
𝝅
"#
# $+,+C#7+#5+*)'(#.8()**'/6#80'/*.#∈
[
0, 1
]
𝐾
#0/*0#
{
0, 1
}
𝐾
"#!/#
*2+#6+/+,)(#3).+C#0/+#3)/#.8()*#I,04#)/<#80'/*#∈
𝐾
C#&<#-,.*#
.8()**'/6#I,04#*2+#I,)3*'0/)(#8),*#0I##0/*0#
{
0, 1
}
𝐾
C#*,)/.()*'/6#
*2+#0;*304+#0I#*2'.#.8()**'/6#&)3J#*0#*2+#30,,+3*#9+,*'3+.#&<#*2+#
#
#
#
#
#
(a) Noisy / clean images
(b) Gaussian 𝐾D-tree
(c) Nair and Chaudhury
(d) Permutohedral lattice
(e) 𝑀 = 1, 𝐿 = (0,1)
∗
@18E)=UE)e1.-+H)/FK2+01.F,)FG)F-0),F,HF/+H)K4+,.)04.-H3.)GF0)3D4)@+/4)1K+84)W427 × 640)21c4H.Y)+3).4H4/3)\H340)/F,\8-0+31F,.E)(,)W+Y;)J4).DFJ)3D4)/H4+,)1K+84)+,6)
3D4)1K+84)/F00-2346)AB)+6613154)Q+-..1+,),F1.4)FG)𝜎 = 24E)(,)WAYkW4Y;)J4).DFJ)3D4)61f404,/4)A43J44,)3D4)F-32-3)20F6-/46)AB)5+01F-.)\H340)/F,\8-0+31F,.)+,6)3D4)
/H4+,)1K+84)1,)W+YE)I4)^M!#)FG)3D4)1K+84.)+04)W+Y)9<EVC)6P;)WAY)9>E>9)6P;)W/Y)C9E=_)6P;)W6Y)32.53)6P)+,6)W4Y)C9EC9)6PE)
"7PRT)(e)
7
VERAGE PSNR AND TIMINGS OF OUR FILTER CONFIGURATIONS WITH
THE KLT ACROSS MULTIPLE FILTER SCALESE EVALUATED ON THE
`ODAK DATASET W9U IMAGESYE CFE @IG =VE)
)
) *43DF6)
*+3H+A)
])'jj)
^M!#)W6PY)
])MM(*)
758E)0-,,1,8)
31K4)W.4/Y
)
)
(,2-3)j)Q+-..1+,),F1.4)
k)
9CE:U)])<EhVC:)
k
)
$3D40)\H340
)
K43DF6.
)
76+23154)*+,1GFH6.)l99m)
Q+-..1+,)𝐾%S3044)l9<m)
^40K-3FD460+H)R+331/4)l9=m)
!+10)+,6)'D+-6D-0B
3
)l9Um)
P*C%)lUhm)
*)
')
')
*)
')
C<E=:)])<E::_=)
C=E=C)])<E:>VV)
C=E:>)])<E>9>C)
9_E>=)])<E:>VC)
33.99 / 0.9551
hE<CC)
hEC99)
CE:<9)
9EUC<)
9>E<_h
)
$-0.)J13D
)
3D4)`R"
)
𝑀 = 0;)) 𝐿 = (0,0))
𝑀 = 1;)) 𝐿 = (0,1)
∗
𝑀 = 1;)) 𝐿 = (1,0))
𝑀 = 2
∗
;)𝐿 = (1,0)))
𝑀 = 2;)) 𝐿 = (1,0)))
')
')
')
')
')
C=E==)])<E>==>)
C=EhC)])<E>99=)
C=E99)])<E>=9:)
C=E9<)])<E>=C=)
C=EC<)])<E>=U=)
0.380)
CE_CC)
=E=9C)
=E:99)
9E_<U
)
#
Ours*
Gaussian
K
D
-
tree [20]
Manifolds [22]
Permutohedral [21]
BM3D [46]
@18E)=VE)%4,F1.1,8)240GF0K+,/4)FG)D18DS61K4,.1F,+H)\H340)1K2H4K4,3+31F,.)FG)
"+AH4) ((() +/0F.. ) ,F1.4) .3+,6+06) 6451+31F,.E) ^M!#) 5+H-4.) +04) +540+846) +/0F..))
3D4)`F6+N)6+3+.43)W9U)1K+84.YE)q$-0.r)1.)3D4).3+0046)5+01+,3)1,)"+AH4)((()WJ13D)
3D4)`R"YE)I4)/H4+,)1K+84.)D+54)+)24+N)+K2H13-64)FG)9VVE)'GE)"+AH4)(eE
#
YOUNG et al.: GAUSSIAN LIFTING FOR FAST BILATERAL AND NONLOCAL MEANS FILTERING 6093
#
'/*+6+,#8),*#0I#"#k+*#;.#5+/0*+#&<#∆∈
[
0, 1
]
𝐾
#*2+#L3)/0/'3)(M##
.'48(+]#72'32#2).#+ 1#9+,*'3+.#
0
, . . . ,
𝐾
#6'9+/#&<#
#
𝑘
= (0, . . . ,0
𝐾−𝑘
, 1, . . . ,1
𝑘 times
)
∗
#
`PVa#
`.++#:'6"#R#I0,#'((;.*,)*'0/#0I#∆#72+/# = 2, 3a"#K+,+I0,+C#*2+#
*2#9+,*+]#
𝑘
#0I#∆#'.#0/+#720.+#300,5'/)*+.#.;4#*0#"#E+3);.+#
8+,4;*'/6#*2+#300,5'/)*+.#0I#
𝑘
#8,+.+,9+.#*2+',#.;4C#'*#I0((07.#
*2)*#*2+#*2#9+,*+]#0I#+9+,<#∆
𝝅
#2).#*2+#300,5'/)*+#.;4#0I#"#
# K+#&),<3+/*,'3#,+.)48('/6#7+'62*.#0I##),+#6'9+/#8,+3'.+(<#
&<#'*.#&),<3+/*,'3#300,5'/)*+.#= (
0
, . . . ,
𝐾
)#7'*2#,+.8+3*#
*0#9+,*'3+.#
0
, . . . ,
𝐾
"#i/+#3)/#-/5##&<#.0(9'/6#*2+#.<.*+4#
0I#('/+),#+^;)*'0/.#(
0
, . . . ,
𝐾
)= #.;&Y+3*#*0#
∗
= 1X#
#
0 0 1
0 1 1
1 1 1
0
1
𝐾
=
1
𝐾
1
,#
`P@a#
*2+#.0(;*'0/#0I#72'32#'.#6'9+/#&<#
#
𝑘
=
1 −
𝐾
if = 0
𝐾−𝑘+1
−
𝐾−𝑘
if 0 < <
1
if = .
#
`PFa#
# !/#*2+#6+/+,)(#3).+C#7+#-,.*#-/5#*2+#.'48(+]#∆
𝝅
#30/*)'/'/6#
*2+#80'/*#∈
[
0, 1
]
𝐾
#&<#(00J'/6#)*#*2+#8+,4;*)*'0/##*2)*#.0,*.#
*2+#300,5'/)*+.#0I##/0/5+3,+).'/6(<"#K+#*2#9+,*+]#
𝝅
𝑘
#0I#*2+#
.'48(+]#∆
𝝅
#'.#6'9+/#&<#8+,4;*'/6#*2+#300,5'/)*+.#0I#
𝑘
&<#*2+#
8+,4;*)*'0/#
−1
#*2)*#,+9+,.+.#*2+#.0,*'/6"#K+#7+'62*.##;.+5#
*0#.8()*#*0#
𝝅
0
, . . . ,
𝝅
𝐾
#),+#I0;/5#&<#.0(9'/6#`P@aC#&;*#/07#7'*2##
*2+#.0,*+5#300,5'/)*+.#0I##0/#*2+#,'62*12)/5#.'5+"#E),<3+/*,'3#
,+.)48('/6#7+'62*.#5;,'/6#.('3'/6#),+#3048;*+5#.'4'(),(<"#
=^^T!%(i)E#
QT#(e(!Q)"gT)k(@"(!Q)e$T@@('(T!"M#
# i/+#7)<#*0#5+,'9+#*2+#('I*'/6#30+_3'+/*.#30,,+.80/5'/6#*0#)#
8,+1+]'.*'/6#7)9+(+*#*,)/.I0,4#'.#*0#I)3*0,#'*.#80(<82).+#4)*,']#
).#)#.+,'+.#0I#;88+,1#)/5#(07+,1*,')/6;(),#4)*,'3+.#?[VA"#>+#3)/#
3048;*+#*2+#('I*'/6#30+_3'+/*.#I0,#0;,#.32+4+#40,+#.'48(<#&<#
/0*'/6#*2)*#0;,#('I*'/6#.*+8.#)88('+5#*0#*2+#Q',)3#5+(*)#.+^;+/3+#
8,05;3+.#*2+#5+.',+5#J+,/+("#e0/.'5+,#*2+#3).+# = 2"#k+**'/6#
ℓ
[
]
=
2
[]#)/5#-(*+,'/6#507/7),5.#`@@aC#7+#0&*)'/#
#
ℓ+1
() =
2
(
0
1
(
2
+
−2
) +
0
(
1
+
−1
)
+(1 + 2
0
1
))
=
2
(
2
+
−2
) +
1
(
1
+
−1
) +
0
#
`PPa#
I0,#0;,#('I*'/6#.32+4+#*0#30,,+.80/5#*0#B);..')/#-(*+,'/6"#K'.#
6'9+.#;.#)#.<.*+4#0I#+^;)*'0/.#'/#*2,++#9),')&(+.C#
0
C#
1
#)/5#
2
X#
#
0
1
2
=
2
,
0
2
=
1
,
2
(1 + 2
0
1
) =
0
,#
`PRa#
)/5#.0(9'/6#*2+#/0/('/+),#.<.*+4#`PRa#8,05;3+.#`@Va"##
# >+#3)/#;.+#*2+#.)4+#I)3*0,'/6#'/#*2+#6+/+,)(#3).+#72+,+#*2+#
/;4&+,#0I# ('I*'/6# .*+8.# ≠2"#>+# 8,09'5+#+]8('3'*# I0,4;()+#
2+,+#I0,#*2+#('I*'/6#30+_3'+/*.#
0
,
2
, . . . ,
𝑀
#30,,+.80/5'/6#*0#
*2+#.<44+*,'3#&(;,#J+,/+(.# 0I#(+/6*2.#2+ 1 = 3, 7, 9"#!/#
*2+#.'48(+.*#.32+4+#72+,+# = 1C#7+#0&*)'/X#
#
0
=
1
0
,
1
=
0
.#
`P[a#
# H07C#I0,#T1*)8#-(*+,#J+,/+(.#` = 3aC#7+#2)9+#
#
0
=
3
2
+
3
0
−
2
1
2
(
2
2
−
0
)
#
`P\a#
#
1
=
2
2
2
1
−
3
2
−
3
0
#
#
2
=
3
2
,
3
=
0
− 2
2
.#
cT@T#T!'TM#
) l=m) eE ) 7 - 0 1 / D ) + , 6 ) s E ) Z4 - H 4 ; ) q ! F , SR1,4+0)Q+-..1+,)@1H340.)^40GF0K1,8)T684)
^04.4051,8)%1f-.1F,;r)1,)DAGM-Symposium;)=>>V;)22E)VC:kVUVE)
) l9m) ME) *E) MK13D)+,6)sE)*E) P0+6B;)qM&M7!t+) ,4J) +220F+/D)3F) HFJ)H454H)
1K+84)20F/4..1,8;r)Int. J. Comput. Vis.;)5FHE) 9C;),FE)=;)22E)UVk_:;) *+B)
=>>_E)
) lCm) 'E) "FK+.1) +,6) #E) *+,6-/D1;) qP1H+340+H) \H3401,8) GF0) 80+B) +,6) /FHF0))
1K+84.;r)1,)ICCV;)=>>:;)22E):C>k:UhE)
) lUm) TE) T1.4K+,,) +,6) @E) %-0+,6;) q@H+.D) ^DF3F80+2DB) T,D+,/4K4,3) 51+)
(,301,.1/)#4H18D31,8;r)1,)SIGGRAPH;)9<<U;)22E)h_Ckh_:E)
) lVm) RE)Z+,8;)RESOE ) Z4 1 ; ) ` E ) u D F - ; ) P E ) Q - F ; ) + , 6 ) g E SOE ) M D - K ; ) q g 1 8 D ) 6 B , + K 1 / )
0+,84) 1K+84) D+HH-/1,+31F,;r) 1,) Proceedings of the 18th Eurographics
Conference on Rendering Techniques;) 7104SH+Se1HH4;) MJ13d40H+,6;)
MJ13d40H+,6;)9<<_;)22E)C9=kC9hE)
) lhm) 7E) O+K+.+N1;) gE) "+N+-[1;) ME) `+,4NF;) "E) `+,+64;) +,6) gE) $DN1;))
q%4,18D31,8L) T,D+,/4K4,3) FG) ,18D331K4) 1K+84.) GF0) +) .-0541HH+,/4))
/+K40+;r)1,)CVPR;)9<<:;)22E)=<V=kUhV=E)
) l_m) QE)^43./D,188;)#E) Md4H1.N1;)*E)780+J+H+;)*E) 'FD4,;)gE)gF224;) +,6)`E)
"FB+K+;)q%1813+H) ^DF3F80+2DB) J13D) @H+.D) +,6) !FSp+.D)(K+84)^+10.;r)1,)
SIGGRAPH;)!4J)OF0N;)!O;)&M7;)9<<U;)22E)hhUkh_9E)
) l:m) ^E )M +, 6)+,6) ME )"4HH4 0;)q ^+ 03 1/ H4)5 16 4F L)H F, 8S0+,84)KF31F,)4.31K+31F,)-.1,8)
2F1,3)30+[4/3F014.;r)Int. J. Comput. Vis.;)5FHE):<;)22E)_9SS>=;)$/3E)9<<:E)
) l>m) 7E)PH41J41..)+,6)*E)Z40K+,;)q@-.1,8)31K4SFGSp18D3)6423D)+,6)/FHF0)GF0)
04+HS31K4).48K4,3+31F,)+,6)30+/N1,8;r)1,)Dynamic 3D Imaging;)M201,840;)
P40H1,;)g4164HA408;)9<<>;)22E)V:kh>E)
)l=<m) #E) @+33+H;) *E)780+J+H+;) +,6) ME) #-.1,N14J1/d;) q*-H31./+H4) MD+24) +,6)
%43+1H)T,D+,/4K4,3)G0FK)*-H31SH18D3)(K+84)'FHH4/31F,.;r)1,)SIGGRAPH;)
!4J)OF0N;)!O;)&M7;)9<<_;)22E)V=L=kSV=L>E)
)l==m) 'E) `4050+,,) +,6) sE) PF-H+,840;) q$231K+H) M2+31+H)76+23+31F,)GF0) ^+3/DS
P+.46)(K+84)%4,F1.1,8;r)IEEE Trans. Image Process.;)5FHE)=V;),FE)=<;)22E)
9:hhk9:_:;)$/3E)9<<hE)
)l=9m) ME) ^E)7J+34) +,6) #E) "E) ZD13+N40;) q&,.-24051.46;) 1,GF0K+31F,S3D4F0431/;)
+6+23154)1K+84)\H3401,8)GF0)1K+84)04.3F0+31F,;r)IEEE Trans. Pattern Anal.
Mach. Intell.;)5FHE)9:;),FE)C;)22E)ChUkC_h;)*+0E)9<<hE)
)l=Cm) 7E)P-+64.;)PE)'FHH;)+,6)sES*E)*F04H;)q7),F,SHF/+H)+H8F013DK)GF0)1K+84)
64,F1.1,8;r)1,)CVPR;)9<<V;)22E)h<khVE)
)l=Um) ME) ^E) 7J+34) +,6) #E) "E) ZD13+N40;) qg18D40SF0640) 1K+84) .3+31.31/.) GF0)
-,.-24051.46;)1,GF0K+31F,S3D4F0431/;)+6+23154;)1K+84)\H3401,8;r)1,)CVPR;)
9<<V;)22E)UUkV=E)
)l=Vm) ME) ^+01.;) ^E) `F0,20FA.3;)sE)"-KAH1,;) +,6) @E)%-0+,6;) qP1H+340+H) \H3401,8L)
I4F0B)+,6)+22H1/+31F,.;r)Found. Trends® Comput. Graph. Vis.;)5FHE)U;)
,FE)=;)22E)=k_C;)9<<>E)
)l=hm) ^E ) * 1H +, G+0; ) q 7) "F-0) F G) * F 64 0, ) ( K+ 84 ) @ 1H 34 01 ,8L ) ! 4J ) ( ,. 18 D3. ) + ,6 )
*43DF6.;)PF3D)^0+/31/+H)+,6)I4F0431/+H;r)IEEE Signal Process. Mag.;)5FHE)
C<;),FE)=;)22E)=<hk=9:;)s+,E)9<=CE)
)l=_m) @E) %-0+,6) +,6) sE) %F0.4B;) q@+.3) A1H+340+H) \H3401,8) GF0) 3D4) 61.2H+B) FG) D18DS
6B,+K1/S0+,84)1K+84.;r)1,)SIGGRAPH;)!4J)OF0N;)!O;)&M7;)9<<9;)22E)
9V_k9hhE)
)l=:m) sE)'D4,;)ME)^+01.;)+,6)@E)%-0+,6;)q#4+HS31K4)4684S+J+04)1K+84)20F/4..1,8)
J13D)3D4)A1H+340+H)8016;r)1,)SIGGRAPH;)!4J)OF0N;)!O;)&M7;)9<<_;)22E)
=<CL=SS=<CL>E)
)l=>m) ME)^+01.)+,6)@E)%-0+,6;)q7)G+.3)+220Fc1K+31F,)FG)3D4)A1H+340+H)\H340)-.1,8)
+).18,+H)20F/4..1,8)+220F+/D;r)Int. J. Comput. Vis.;)5FHE):=;),FE)=;)22E)9Uk
V9;)s+,E)9<<>E)
)l9<m) 7E)76+K.;)!E)Q4HG+,6;)sE)%FH.F,;)+,6)*E)R45FB;)qQ+-..1+,)`%S3044.)GF0)
G+.3) D18DS61K4,.1F,+H) \H3401,8;r) 1,) SIGGRAPH;) !4J)OF0N;) !O;) &M7;)
9<<>;)22E)9=L=k9=L=9E)
)l9=m) 7E)76+K.;) sE) P+4N;) +,6) *E)7E) %+51.;) q@+.3) D18DS61K4,.1F,+H) \H3401,8)
-.1,8)3D4)240K-3FD460+H)H+331/4;r)Comput. Graph. Forum;)5FHE)9>;),FE)9;)
6094 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 29, 2020
#
22E)_VCk_h9;)*+B)9<=<E)
)l99m) TE) ME) RE) Q+.3+H) +,6) *E) *E) $H15410+;)q76+23154)K+,1GFH6.) GF0) 04+HS31K4)
D18DS61K4,.1F,+H)\H3401,8;r)ACM Trans Graph;)5FHE)C=;),FE)U;)22E)CCL=k
CCL=C;)s-HE)9<=9E)
)l9Cm) *E) QE) *Fd40F5) +,6) sE)5+,)64)Z41[40;) qQHFA+H)'FHF0) M2+0.4,4..) +,6) +)
RF/+H) M3+31.31/.) ^01F0) GF0) @+.3) P1H+340+H) @1H3401,8;r) IEEE Trans. Image
Process.;)5FHE)9U;),FE)=9;)22E)V:U9kV:VC;)%4/E)9<=VE)
)l9Um) ^E ) ! +1 0) + ,6 ) ` E) ! E) ' D+-6 D-0B;) q @+ .3 ) g 18 DS%1K4,.1F,+H) P1H+340+H) +,6)
!F,HF/+H)*4+,.)@1H3401,8;r)IEEE Trans. Image Process.;)5FHE)9:;),FE)C;)
22E)=U_<k=U:=;)*+0E)9<=>E)
)l9Vm)"E)"+.61d4,;)q^01,/12+H)/FK2F,4,3.)GF0),F,SHF/+H)K4+,.)1K+84)64,F1.1,8;r)
1,)ICIP;)9<<:;)22E)=_9:k=_C=E)
)l9hm) @E) ^F01NH1;) q'F,.3+,3) 31K4) $W=Y) A1H+340+H) \H3401,8;r) 1,) CVPR;) 9<<:;) 22E)
=<hCSSh>=>E)
)l9_m) `E)!E)'D+-6D-0B;)%E)M+84;)+,6)*E)&,.40;)q@+.3)$W=Y)P1H+340+H)@1H3401,8)
&.1,8)"018F,FK4301/)#+,84)`40,4H.;r)IEEE Trans. Image Process.;)5FHE)
9<;),FE)=9;)22E)CC_hkCC:9;)%4/E)9<==E)
)l9:m) `E) !E) 'D+-6D-0B;) q7//4H40+31F,) FG) 3D4) MD1G3+AH4) $W=Y) 7H8F013DK) GF0)
P1H+340+H)@1H3401,8)+,6)!F,HF/+H)*4+,.;r)IEEE Trans. Image Process.;)5FHE)
99;),FE)U;)22E)=9>=k=C<<;)720E)9<=CE)
)l9>m) `E) M-81KF3F) +,6) ME) `+K+3+;) q'FK204..154) P1H+340+H) @1H3401,8;r) IEEE
Trans. Image Process.;)5FHE)9U;),FE)==;)22E)CCV_kCCh>;)!F5E)9<=VE)
)lC<m) QE)^+2+01;)!E)(6FJ-;)+,6)"E)e+0.HF3;)q@+.3)P1H+340+H)@1H3401,8)GF0)%4,F1.1,8)
R+084)C%)(K+84.;r)IEEE Trans. Image Process.;)5FHE)9h;),FE)=;)22E)9V=k
9h=;)s+,E)9<=_E)
)lC=m) eE ) ` E ) Q F B + H ; ) q I 4 F 0 4 3 1 / + H ) G F - , 6 + 3 1 F , . )FG)30+,.GF0K)/F61,8;r)IEEE Signal
Process. Mag.;)5FHE)=:;),FE)V;)22E)>k9=;)M42E)9<<=E)
)lC9m) %E) "+-AK+,) +,6) *E) *+0/4HH1,;) JPEG2000: Image Compression
Fundamentals, Standards and PracticeE) !F0J4HH;) *7;) &M7L) `H-J40;)
9<<=E)
)lCCm) `E) !E) 'D+-6D-0B) +,6) ME) %E) %+AD+64;) q@+.3) +,6) ^0F5+AHB) 7//-0+34)
P1H+340+H)@1H3401,8;r)IEEE Trans. Image Process.;)5FHE)9V;),FE)h;)22E)9V=>k
9V9:;)s-,E)9<=hE)
)lCUm) #E)QE)Q+5+.N+0)+,6)`E)!E)'D+-6D-0B;)q@+.3)76+23154)P1H+340+H)@1H3401,8;r)
IEEE Trans. Image Process.;)5FHE)9:;),FE)9;)22E)__>k_><;)@4AE)9<=>E)
)lCVm) RE)%+1;)*E)O-+,;)+,6)iE)uD+,8;)qM24461,8)&2)3D4)P1H+340+H)@1H340L)7)sF1,3)
7//4H40+31F,)Z+B;r)IEEE Trans. Image Process.;)5FHE)9V;),FE)h;)22E)9hV_k
9h_9;)s-,E)9<=hE)
)lChm) QE)M30+,8)+,6)"E)!8-B4,;)Wavel ets and Filter BanksE)M(7*;)=>>hE)
)lC_m) ZE ) MJ4H64,.;) qI4) H1G31,8) . /D4K4L) +) /F ,.30- /31F, ) FG) .4/F,6 ) 84,4 0+31F ,)
J+54H43.;r)SIAM J. Math. Anal.;)5FHE)9>;),FE)9;)22E)V==kVUh;)*+0E)=>>:E)
)lC:m) ZE )MJ4H6 4,.) +,6) ^E)M/D0v640;) qP-1H61,8)BF- 0) FJ ,) J+54 H43.) +3) DFK4;r) 1,)
Wavelets in the Ge oscienc es;)P40H1,;) Q40K+,BL) M201,840;)9<<<;)22E)_9k
=<_E)
)lC>m) RE) M/D-K+N40;) Spline Functions: Basic UeoryE) '+KA01684;) &`L)
'+KA01684)&,1540.13B)^04..;)9<<_E)
)lU<m) *E) e43340H1;) sE) `F5+w451x;) +,6) eE) `E) QFB+H;) Foundations of Signal
ProcessingE)'+KA01684)&,1540.13B)^04..;)9<=UE)
)lU=m) 7E) ^+2F-H1.) +,6) ME) &E) ^1HH+1;) Probability, Random Variables and
Stochastic Processes;)U3D)46131F,E)PF.3F,;)*7;)&M7L)*/Q0+JSg1HH;)9<<9E)
)lU9m) *E) gE) s+,.4,) +,6) ^E) sE) $F,1,/c;) Second Generation Wavelets and
ApplicationsE)RF,6F,;)&`L)M201,840;)9<<VE)
)lUCm) 'E)`E)'D-1)+,6)sE)Z+,8;)q$,)/FK2+/3HB).-22F0346).2H1,4)J+54H43.)+,6)+)
6-+H13B)201,/12H4;r)Trans. Am. Math. Soc.;)5FHE)CC<;),FE)9;)22E)><Ck>=V;)
=>>9E)
)lUUm) *E) &,.40;)7E)7H60F-A1;) +,6) *E) T64,;) q7) G+K1HB) FG) 2FHB,FK1+H) .2H1,4)
J+54H43)30+,.GF0K.;r) Signal Process.;) 5FHE) C<;) ,FE) 9;) 22E) =U=k=h9;) s+,E)
=>>CE)
)lUVm) *E) uD+,8) +,6) PE) `E) Q-,3-0N;) q*-H3104.FH-31F,) P1H+340+H) @1H3401,8) GF0)
(K+84)%4,F1.1,8;r)IEEE Trans. Image Process.;)5FHE)=_;),FE)=9;)22E)9C9Uk
9CCC;)%4/E)9<<:E)
)lUhm) $E) #-..+NF5.NB) et al.;) q(K+84!43) H+084) ./+H4) 51.-+H) 04/F8,131F,)
/D+HH4,84;r)Int. J. Comput. Vis.;)5FHE)==V;),FE)C;)22E)9==k9V9;)%4/E)9<=VE)
)lU_m) `E)%+AF5;)7E)@F1;)eE)`+3NF5,1N;)+,6)`E)T81+d+01+,;)q(K+84)%4,F1.1,8)AB)
M2+0.4) CS%) "0+,.GF0KS%FK+1,) 'FHH+AF0+3154) @1H3401,8;r) IEEE Trans.
Image Process.;)5FHE)=h;),FE):;)22E)9<:<k9<>V;)7-8E)9<<_E)
)lU:m) sE)`F5+w451x)+,6)ZE)MJ4H64,.;)qZ+54H43)G+K1H14.)FG)1,/04+.1,8)F0640)1,)
+0A130+0B)61K4,.1F,.;r)IEEE Trans. Image Process.;)5FHE)>;),FE)C;)22E)U:<k
U>h;)*+0E)9<<<E)
)lU>m) gE)ZE)`-D,;)qMFK4)'FKA1,+3F01+H)R4KK+.)1,)"F2FHF8B;r) IBM J. Res.
Dev.;)5FHE)U;),FE)V;)22E)V=:kV9U;)!F5E)=>h<E)
)lV<m) (E)%+-A4/D14.)+,6)ZE)MJ4H64,.;)q@+/3F01,8)J+54H43)30+,.GF0K.)1,3F)H1G31,8)
.342.;r)J. Fourier Anal. Appl.;)5FHE)U;),FE)C;)22E)9U_k9h>;)*+B)=>>:E)
Sean I. Young) 04/41546) PE'FK) +,6) PETE) 648044.) 1,) .FG3J+04) 4,81,4401,8))
G0FK) 3D4) &,1540.13B) FG) 7-/NH+,6) 1,) 9<<:;) +,6) 3D4) *ET,8M/) +,6) ^DE%E))
648044.)G0FK)3D4)&,1540.13B)FG)!4J)MF-3D)Z+H4.;)MB6,4B;)1,)9<==)+,6)9<=:;)
04.24/3154HBE) g4) 1.) /-004,3HB) +) ^F.36F/3F0+H) #4.4+0/D40) J13D) 3D4) %42+03K4,3))
FG)TH4/301/+H)T,81,4401,8;)M3+,GF06)&,1540.13B;)M3+,GF06;)'7E)(,)9<=h;)D4)J+.)
+) 51.131,8) 04.4+0/D40) +3) (,340%1813+H) 'FKK-,1/+31F,.;) M+,) %148F;) '7E) g1.)
04.4+0/D)1,3404.3.)+04)H+084S./+H4)F231K1d+31F,)+,6)1,540.4)20FAH4K.)1,)1K+84)
20F/4..1,8E) g4) 04/41546) 3D4)7^#M](7^#) A4.3) 2+240) +J+06) +3) %('"7) 9<=:;)
3F843D40)J13D)%+516)"+-AK+,E)
Bernd Girod 04/41546)3D4)T,81,4401,8)%F/3F0+34)648044)G0FK)&,1540.13B)FG)
g+,,F540;)Q40K+,B;)+,6)3D4)*EME)648044)G0FK)Q4F081+)(,.313-34)FG)"4/D,FHF8BE)
&,31H)=>>>;)D4)J+.)+) ^0FG4..F0)J13D)3D4)TH4/301/+H) T,81,4401,8)%42+03K4,3;)
&,1540.13B)FG)T0H+,84,k!-04KA408E)g4)1.)/-004,3HB)3D4)#FA403)RE)+,6)7-604B)
ME)g+,/F/N)^0FG4..F0)FG)TH4/301/+H)T,81,4401,8;)M3+,GF06)&,1540.13B;)'7;)&M7E)
g4)D+.)+-3DF046)F540) h<<) /F,G404,/4) +,6) [F-0,+H) 2+240.)+,6).1c)AFFN.E)g1.)
04.4+0/D)1,3404.3.)+04)1,)3D4)+04+)FG)1K+84;)5164F;)+,6)K-H31K461+).B.34K.E)7.)
+,)4,304204,4-0;)D4)J+.) 1,5FH546)1,),-K40F-.).3+03-2)54,3-04.;)+KF,8)3D4K)
^FHB/FK;)e15F)MFG3J+04;):×:;)+,6)#4+H!43JF0N.E)g4)1.)+)T&#7M(^)@4HHFJ;)+)
K4KA40)FG)3D4)!+31F,+H)7/+64KB)FG)T,81,4401,8;)+,6)+)K4KA40)FG)3D4)Q40K+,)
!+31F,+H)7/+64KB)FG)M/14,/4.)WR4F2FH61,+YE)g4)04/41546)3D4)T&#7M(^)M18,+H)
^0F/4..1,8)P4.3)^+240)7J+06)1,)9<<9;)3D4)(TTT)*-H31K461+)'FKK-,1/+31F,)
P4.3)^+240)7J+ 06 ) 1,) 9<<_;) 3D4) T&#7M(^) (K +84) 'FKSK-,1/+31F,)P4.3)^+240)
7J+06) 1,) 9 <<:;) 3D 4) T &# 7M (^) M 18 ,+H) ^0F/4. .1 ,8) *F.3) ' 1346) ^+24 0) 7J+06) 1,)
9<<:;)3D4)T&#7M(^)"4/D,1/+H)7/D1454K4,3)7J+06)1,)9<<U;)+,6)3D4)"4/D,1/+H)
7/D1454K4,3)7J+06)FG)3D4)(TTT)M18,+H)^0F/4..1,8)MF/143B)1,)9<==E
David Taubman)04/41546)PEME)+,6)PETE)648044.)1,)4H4/301/+H)4,81,4401,8)G0FK)
3D4)&,1540.13B)FG)MB6,4B;)1,)=>:h)+,6)=>::;)04.24/3154HB;)+,6)3D4)*EME)+,6)^DE%E)
648044.) G0FK) 3D4) &,1540.13B) FG) '+H1GF0,1+) +3) P40N4H4B;) 1,) =>>9) +,6) =>>U;)
04.24/3154HBE) @0FK) =>>U) 3F) =>>:;) D4) J+.) J13D) g4JH433S^+/N+06y.) #4.4+0/D)
R+AF0+3F014.;)^+HF)7H3F;)'7E)g4)[F1,46)&!MZ)1,)=>>:;)JD404)D4)1.)/-004,3HB)+)
^0FG4..F0)J13D)3D4)M/DFFH)FG)TH4/301/+H)T,81,4401,8)+,6)"4H4/FKK-,1/+31F,.E)
g4) D+.) +-3DF046) 3D4) AFFN) s^TQ9<<<L) (K+84) 'FK204..1F,) @-,6+K4,3+H.;)
M3+,6+06.)+,6)^0+/31/4;)J13D)*E)*+0/4HH1,E)g1.)04.4+0/D)1,3404.3.)1,/H-64)D18DHB)
./+H+AH4) 1K+84) +,6) 5164F) /FK204..1F,;) KF31F,) 4.31K+31F,) +,6) KF64H1,8;)
1,540.4)20FAH4K.)1,)1K+81,8;)240/423-+H)KF64H1,8;)+,6)K-H31K461+)61.301A-31F,)
.B.34K.E)g4)04/41546)3D4)&,1540.13B)*46+H)G0FK)3D4)&,1540.13B)FG)MB6,4BE)g4)
D+.)04/41546)3JF)A4.3)2+240)+J+06.)G0FK)3D4)(TTT)'10/-13.)+,6)MB.34K.)MF/143B)
GF0) 3D4) =>>h) 2+240) 4,313H46)7) 'FKKF,) @0+K4JF0N) GF0) #+34) +,6) %1.3F031F,S
P+.46)M/+H1,8)FG)g18DHB)M/+H+AH4)'FK204..46)e164F;)+,6)G0FK)3D4)(TTT)M18,+H)
^0F/4..1,8) MF/143B) GF0) 3D4) 9<<<) 2+240) 4,313H46) g18D) ^40GF0K+,/4) M/+H+AH4)
(K+84)'FK204..1F,)J13D)TP'$"E
)