1. Introduction
傳統的 denoise 著重在 local means 的方法，基本上不外乎是在 target pixel 的附近判斷是否要保留或是抹除 target pixel。缺點是抹除的同時卻也模糊了細節，然後方向就跑去 anisotropic diffusion，neighbor 的判斷越來越多考量和限制， edge 強弱和方向啥的。
這邊要提的 non-local means 的方式主要基於 patch search 的方式來尋找相似的區塊作平均。
2. 3D denoising (3D NR)
源自於 random noise 的假設，已知靜態的原始訊號 \(S\) ，與一個隨時間 \(t\) 改變的 random noise \(N(t)\)，其在時間 \(t\) 的訊號 \(F(t)\) 關係如下
\[F(t)=S+N(t)\]
如果這個 random noise 分布是一個 mean 為 0 的常態分佈，有正有負的抵銷 \(N(t)\) 項，加總越多 \(F(t)\) 的平均值將會使 noise 項趨近於 0 。
\[\frac{1}{n}\sum_{t=0}^{n}{F(t)}\cong{S}\]
所以某些相機在高 iso 時候會連拍複數張影像對每個 pixel 取均值來做 denoise。而在錄影時就是與前一個 base frame 做平均，但遇到動態場景時則可能因為平均到前一個物體的 pixel 值，而出現不自然的殘影，這也是 3D NR 的困難點：判斷移動場景。
3. Non-Local Means
如同 3DNR 點對點的在時間軸上平均化 noise ， non-local means 則是相信畫面中有許多重複的 patch ，對這些相似的patch應用平均化來達到 denoise 的效果，其概念像是 3D NR 的 2D patch search 版。
如 figure 1 ，要做 patch \(p\) 時，假設搜尋到 3 個 candidate 分別為\(q_1,q_2,q_3\)，denoise 的 patch 為 \(p^{‘}\) ，關係如下
\[p^{‘}=w_{0}p+w_{1}q_1+w_{2}q_2+w_{3}q_3, \sum_{i=0}^{3}{w_i}=1\]
其中 \(q_1,q_2\) 都與 \(p\) 很像，可以猜想 \(w1, w2\) 會比 \(w3\) 大得多了。而 \(w_{i}\) 定義為 patch SSD 有關的常態分佈。
3.1 Patch difference
其中最難定義的便是兩個 patch 到底像不像，在 noise 的環境中，光靠 pixel-difference 肯定效果有限的。常見的方法是定義一些 structured basis 來進行投影，如 Haar-like features；也有些人利用 SVD 取出 significant basis。
3.2 Search strategy
最簡單的 search strategy 就是 global search ，當然也有越來越加速的方法來實現，如 quad-tree based，multi-scale 方法等。而在影片處理上更可以考慮前幾個 frame 搜尋到的位置。