在一些优化模型中含有 偏导项与数据项,对其求最小化。一种方法是利用 Eular Lagrange 变换,求解出关于未知变量的解。 还有一种方法是利用 快速Fourier 变换来求解。 如L0 滤波中,对子问题 S S 的解,公式 (7)
最小化目标函数: ∑p{(Sp−Ip)2 β((∂xSp−hp)2 (∂ySp−vp)2)}∑p{(Sp−Ip)2 β((∂xSp−hp)2 (∂ySp−vp)2)} (1)
上式的解用FFT 表示为: S=F−1{F(I)+β(F(∂x)∗F(h)+F(∂x)∗F(v)))F(1)+β(F(∂x)∗F(∂x))+F(∂y)∗F(∂y)} S = F − 1 { F ( I ) + β ( F ( ∂ x ) ∗ F ( h ) + F ( ∂ x ) ∗ F ( v ) ) ) F ( 1 ) + β ( F ( ∂ x ) ∗ F ( ∂ x ) ) + F ( ∂ y ) ∗ F ( ∂ y ) }
这个Fourier 等式是如何推导出来的 ?
推导过程中主要涉及两个主要内容 (1) Eular lagrange 变换。 (2)Laplacian 算子的 FFT 表达。
首先以 1 维函数为例推导 Laplacian 算子的 FFT 表达: 记函数 f(x) f ( x ) 的 FFT 为 F(u) F ( u ) , 有
f(x)⇔F(u) f ( x ) ⇔ F ( u ) ,
平移函数的FFT,
f(x−n0)⇔exp(−j2πun0)F(u) f ( x − n 0 ) ⇔ e x p ( − j 2 π u n 0 ) F ( u )
则前向差分算子 ∇xf=f(x+1)−f(x) ∇ x f = f ( x + 1 ) − f ( x ) 的FFT为:
f(x+1)−f(x)⇔(exp(j2πu)−1)F(u) f ( x + 1 ) − f ( x ) ⇔ ( e x p ( j 2 π u ) − 1 ) F ( u )
后向差分算子的FFT为
f(x)−f(x−1)⇔(1−exp(−j2πu))F(u) f ( x ) − f ( x − 1 ) ⇔ ( 1 − e x p ( − j 2 π u ) ) F ( u )
则 Laplacian 算子 △2f(x)=f(x+1)−2f(x)+f(x−1) △ 2 f ( x ) = f ( x + 1 ) − 2 f ( x ) + f ( x − 1 ) 的FFT 变换为
△2f(x)⇔(exp(j2πu)−2+exp(−j2πu))F(u) △ 2 f ( x ) ⇔ ( e x p ( j 2 π u ) − 2 + e x p ( − j 2 π u ) ) F ( u ) =−((exp(j2πu)−1)(˙exp(−j2πu)−1)F(u) = − ( ( e x p ( j 2 π u ) − 1 ) ( ˙ e x p ( − j 2 π u ) − 1 ) F ( u ) =−((exp(j2πu)−1)(˙exp(j2πu)−1)∗F(u) = − ( ( e x p ( j 2 π u ) − 1 ) ( ˙ e x p ( j 2 π u ) − 1 ) ∗ F ( u )
这时得到了Laplacian 算子与梯度算子的 FFT 关系 F(△2f(x))⇔−F(∇xf)∗F(∇xf)∗F(u) F ( △ 2 f ( x ) ) ⇔ − F ( ∇ x f ) ∗ F ( ∇ x f ) ∗ F ( u ) 其中 ∗ ∗ 表示复共轭。
下面看Eular_Lagrange 等式 (1)的Eular _Lagrange 等式表达为
2(Sp−Ip)−2β((∂x(∂xSp−hp)+∂y(∂ySp−vp))=0 2 ( S p − I p ) − 2 β ( ( ∂ x ( ∂ x S p − h p ) + ∂ y ( ∂ y S p − v p ) ) = 0
即: S−β(∂xxS+∂yyS)=I−β(∂xh+∂yv) S − β ( ∂ x x S + ∂ y y S ) = I − β ( ∂ x h + ∂ y v )
对等上式两边进行FFT有
F(S)+β(F(∂x)F(∂x)∗+F(∂y)F(∂y)∗)F(S)=F(I)−β(F(∂x)F(h)+F(∂y)F(v)) F ( S ) + β ( F ( ∂ x ) F ( ∂ x ) ∗ + F ( ∂ y ) F ( ∂ y ) ∗ ) F ( S ) = F ( I ) − β ( F ( ∂ x ) F ( h ) + F ( ∂ y ) F ( v ) )
整理得 F(S)=F(I)−β(F(∂x)F(h)+F(∂x)F(v))1+β(F(∂x)F(∂x)∗+F(∂y)F(∂y)∗) F ( S ) = F ( I ) − β ( F ( ∂ x ) F ( h ) + F ( ∂ x ) F ( v ) ) 1 + β ( F ( ∂ x ) F ( ∂ x ) ∗ + F ( ∂ y ) F ( ∂ y ) ∗ )