查看“︁總變差去噪”︁的源代码

[[Category:信號處理]]
__FORCETOC__
'''總變差去噪'''（[[英語]]：Total Variation Denoising）是訊號處理中一種常見的降噪方法，於1992年由L. I. Rudin、{{le|斯坦利·奧舍|Stanley Osher|S. Osher}}和E. Fatemi提出，因此亦稱為ROF模型<ref name="rof92">{{cite journal|last1=Rudin|first1=L. I.|last2=Osher|first2=S.|last3=Fatemi|first3=E.|year=1992|title=Nonlinear total variation based noise removal algorithms|journal=Physica D|volume=60|issue=1–4|pages=259–268|doi=10.1016/0167-2789(92)90242-f|bibcode=1992PhyD...60..259R|citeseerx=10.1.1.117.1675|id=}}</ref>。一個含有雜訊的訊號相較於其未受[[雜訊]]影響的訊號，會有較大的[[總變差]]值，即其梯度絕對值的總和較大。因此若能找到一個與原始訊號相似且總變差較小的訊號，即可作為原始訊號的降噪結果。此算法可以在去除雜訊的同時保留邊緣，即使在低[[訊號雜訊比]]的情況下，依然能有效的去噪和保留邊緣。

==總變差==
{{see also|總變差}}
總變差為一[[函數]]其數值變化的總和。可表示為其[[微分]]後取絕對值再[[積分]]的結果。
===一維連續函數===
若一函數<math>y=f(x)</math>為一維[[連續]][[可微]]函數，其在[[區間]]<math>[a,b]\subset\mathbb{R}</math>之總變差定義為
: <math>TV_a^b(y) = \int_{a}^{b}|f'(x)|dx</math>,
其中<math>f'(x)</math>為<math>f(x)</math>的一次微分。

當<math>f(x)</math>不可微分時，其總變差由一般性的定義給出:
: <math>TV_a^b(y) = \sup_{\mathcal{P}} \sum_{i=0}^{n_P-1} | f(x_{i+1})-f(x_i) |</math>,
其中<math>\mathcal{P}</math>為區間<math>[a,b]</math>中所有可能的[[分割]]，即<math>\scriptstyle \mathcal{P} =\left\{P=\{ x_0, \dots , x_{n_P}\}|P\text{ is a partition of } [a,b] \right\}</math>。

===一維離散函數===
若一函數<math>y=f(x)</math>為一維[[離散]]函數，則其總變差定義為
: <math>TV(y)=\sum_{n}|f(x_{n+1})-f(x_n)|</math>.
即[[差分]]後取絕對值再加總的結果。

==一維訊號去噪==
設輸入的觀察訊號為<math>x</math>，對<math>x</math>去噪得到的訊號為<math>y</math>。我們可以透過解[[最佳化]]問題來從<math>x</math>得到<math>y</math>。當以總變差去噪法對訊號進行去噪時，最佳化問題應滿足以下兩個條件:
*<math>x</math>與<math>y</math>相似，以保留訊號整體的結構性
*<math>y</math>的總變差不大，以降低雜訊
在數學上，兩個訊號的相似度可以以兩者差的<math>L_2</math>-[[範數]]表示，即
: <math>E(x,y)=\frac{1}{2}\left \| x-y \right \|_2^2 = \frac{1}{2}\sum_{n}(x_n-y_n)^2</math>,
其中<math>\left \| \cdot \right \|_2</math>即為<math>L_2</math>-範數，而<math>x_n, y_n</math>為訊號的[[取樣]]點。

藉由上述數學表達式，總變差去噪法的最佳化問題可以寫成
: <math>\min_{y}E(x,y)+\lambda TV(y)</math>.
即利用[[最小平方法]]，並以總方差作為[[正規化]]的正規項，以求得去噪結果。其中<math>\lambda</math>為正規化參數，用於調整正規項的重要程度。

由於<math>E(x,y)</math>和<math>TV(y)</math>皆為[[凸函數]]，因此一維總變差去噪的最佳化為一[[凸優化]]問題<ref name="little10">{{cite conference | first1 = M. A. | last1 = Little | first2 = Nick S. | last2 = Jones | year = 2010 | url = http://www.maxlittle.net/publications/little_icassp2010.pdf | title = Sparse Bayesian Step-Filtering for High-Throughput Analysis of Molecular Machine Dynamics | conference = 2010 IEEE International Conference on Acoustics, Speech and Signal Processing | booktitle = ICASSP 2010 Proceedings | access-date = 2020-06-13 | archive-date = 2018-07-28 | archive-url = https://web.archive.org/web/20180728163542/http://www.maxlittle.net/publications/little_icassp2010.pdf }}</ref>，有許多凸優化[[演算法]]可以求解，且其解必為全局最佳值。

==影像去噪==
影像為二維離散訊號，在ROF模型中定義的總變差為
: <math>TV(y)=\sum_{m,n}\left\|\nabla y_{m,n}\right\|_2 = \sum_{m,n}\sqrt{|y_{m+1,n}-y_{m,n}|^2+|y_{m,n+1}-y_{m,n}|^2}</math>,
其中<math>\nabla</math>為[[梯度]]運算子。

然而該定義不可微分，做為最佳化問題的正規項時不易求解。因此也有<math>L_1</math>-範數形式的二維總變差
: <math>TV(y)=\sum_{m,n}\left\|\nabla y_{m,n}\right\|_1 = \sum_{m,n}(|y_{m+1,n}-y_{m,n}|+|y_{m,n+1}-y_{m,n}|)</math>.
最佳化問題的形式與解一維訊號形式相同
: <math>\min_{y}E(x,y)+\lambda TV(y)</math>.
然而二維訊號的最佳化問題不一定為凸優化問題，因此無法以常見凸優化演算法求解。目前發展能求解的演算法有{{Link-en|原始-對偶演算法|Wikipedia:primal-dual method}}<ref name="chambolle04">{{cite journal | first = A. | last = Chambolle | year = 2004 | citeseerx = 10.1.1.160.5226 | title = An algorithm for total variation minimization and applications | journal = Journal of Mathematical Imaging and Vision | volume = 20 | pages = 89–97 | doi=10.1023/B:JMIV.0000011325.36760.1e}}</ref>、[[增广拉格朗日惩罚函数法#交替方向乘子法|交替方向乘子法]](ADMM)<ref>{{cite arXiv|author=Wahlberg, B. |author2=Boyd, S. |author3=Annergren, M. |author4=Wang, Y.|title=An ADMM algorithm for a class of total variation regularized estimation problems |eprint=1203.1828|date=2012|class=stat.ML }}</ref>、{{Link-en|布雷格曼方法|Wikipedia:Bregman method}}<ref>Bregman L. "A Relaxation Method of Finding a Common Point of Convex Sets and its Application to Problems of Optimization". Dokl. Akad. Nauk SSSR, v. 171, No. 5, 1966, p.p. 1019-1022. (English translation: Soviet Math. Dokl., v. 7, 1966, p.p. 1578-1581)</ref>等等。

==其他變形==
===高階微分===
總變差的概念為先微分取絕對值後再積分。因此在一些文獻中<ref name="Heide13">{{cite journal | first = F. | last = Heide | year = 2013 | title = High-quality computational imaging through simple lenses | journal = ACM Transactions on Graphics (TOG) | volume = 32 | pages = 1--14 | doi = 10.1145/2516971.2516974}}</ref>有使用到二階微分以上的例子。
當處理訊號為離散訊號時，二階差分的形式如下
: <math>f''(x_n)=f(x_{n-1})-2f(x_n)+f(x_{n+1})</math>
因此使用二階差分的總變差可定義為
: <math>TV^{(2)}(y) = \sum_{n}|f''(x_n)|</math>
而最佳化問題的形式為
: <math>\min_{y}E(x,y)+\lambda_1 TV(y)+\lambda_2 TV^{(2)}(y)</math>

===雙邊總變差去噪===
雙邊總變差(bilateral total variation)是2004年由S.Farisu和D.Robinson提出的最佳化正規項<ref name="Farisu04">{{cite journal | first = S. | last = Farisu | year = 2004 | title = Fast and robust multiframe super resolution | journal = IEEE transactions on image processing | volume = 13 | pages = 1327--1344 | doi = 10.1109/TIP.2004.834669}}</ref>。該正規項基於總變差，結合[[雙邊濾波器]]的概念而成。主要應用於[[影像復原]]。

雙邊總變差的形式如下
: <math>BTV(\mathbf{Y}) = \sum_{l=-P}^P\sum_{m=\max(0,-l)}^{P}\lambda^{|l|+|m|}\left\|\mathbf{Y}-\mathbf{S}_x^l\mathbf{S}_y^m\mathbf{Y}\right\|_1</math>,
其中<math>\mathbf{Y}</math>為處理圖片，<math>\mathbf{S}_x^l</math>與<math>\mathbf{S}_y^m</math>為兩個運算子，分別代表將圖片水平移動<math>l</math>個像素與垂直移動<math>k</math>個像素。<math>\lambda</math>為權重，隨著平移距離遞減。

當<math>l=1,m=0</math>和<math>l=0,m=1</math>時，圖片的每一個像素與相鄰之下一個像素相減，此時的雙邊總變差與總變差相同。當<math>l,m</math>為其它值時，可以當成是計算斜線方向以及將圖片[[降採樣]]後的總變差值。如此達到更好的正規化效果。

根據S.Farisu的實驗結果<ref name="Farisu04">{{cite journal | first = S. | last = Farisu | year = 2004 | title = Fast and robust multiframe super resolution | journal = IEEE transactions on image processing | volume = 13 | pages = 1327--1344 | doi = 10.1109/TIP.2004.834669}}</ref>，雙邊總變差相對於總變差，邊界模糊的情況較少，能夠更好的保留原圖片邊界。

==參見==
*[[數位訊號處理]]
*[[最佳化]]
*[[影像降噪]]
*[[高斯模糊]]
*[[中值濾波器]]
*[[雙邊濾波器]]
*[[非等向性擴散]]
*[[非局部平均]]
*[[三維塊匹配算法]]

==參考文獻==
{{refList}}