三維塊匹配算法

三維塊匹配算法（英語：Block Matching 3D，縮寫：BM3D）是一個效果比較好的圖像去噪算法。通過與相鄰圖像塊進行匹配，將若干相似的塊整合為一個三維矩陣，在三維空間進行濾波處理，再將結果反變換融合到二維，形成去噪後的圖像。該算法去噪效果顯著，可以得到目前為止最高的峰值信噪比，但時間複雜度比較高。

算法步驟

BM3D算法分兩個步驟，兩個步驟算法類似，第一步通過原圖匹配進行簡單去噪形成基礎估計，第二步通過原圖和基礎估計進行更細緻的去噪，將PSNR進一步提高。

第一步（基礎估計）

首先，在噪聲圖中以一個步長（通常為3個像素）設定若干個參照塊（reference block），每個參照塊在周圍適當區域內進行搜索，尋找若干個差異最小的塊（兩個塊的差異通常用$L_{2}$-範數來量化），將這些塊以任意順序整合成一個三維矩陣。通常會設定一個閾值，只將距離小於這個閾值的塊整合到矩陣中，同時也會設置相似塊的最大數量。參照塊自己也是自己的相似塊且差異度為0。

一個塊$Z_{X}$與參考塊$Z_{X_{R}}$的差異定義如下

$d(Z_{X_{R}},Z_{X})={\frac {\left\|Z_{X_{R}}-Z_{X}\right\|_{2}^{2}}{N_{1}}}$,

其中$\left\|\cdot \right\|_{2}$為$L_{2}$-範數，$N_{1}$為塊的大小。

將距離小於一個閾值的塊整合成一個三維矩陣$S_{X_{R}}$

$S_{X_{R}}={x\in X:d(Z_{X_{R}},Z_{X})<\tau _{match}}$

形成若干個三維的矩陣之後，首先將每個三維矩陣中的二維的塊（即噪聲圖中的某個塊）進行二維變換編碼，可採用小波變換或DCT變換等（通常BIOR1.5小波變換更為常用，效果也更好）。如果使用的是小波變換，為了更好的分離出低頻信息，需要變換多次——即在每次變換的左上角1/4低頻區繼續進行二維變換，直到完成2×2的變換為止。二維變換結束後，在矩陣的第三個維度進行一維變換（通常為hadamard變換）。

此時的三維矩陣已經進行很好的處理。對三維矩陣進行硬閾值處理，將比較小的係數置0，然後通過在第三維的一維反變換和二維反變換得到處理後的圖像塊

${\hat {Y}}_{S_{X_{R}}}={\mathcal {T}}_{3D}^{-1}(\Gamma ({\mathcal {T}}_{3D}(S_{X_{R}})))$，

其中${\mathcal {T}}_{3D}$為三維變換，$\Gamma (\cdot )$為硬閾值函數。

此時三維矩陣中的每個二維塊均是對去噪圖像的估計，分別將這些塊融合到原來的位置，每個像素的強度通過每個對應位置的塊的值加權平均，權重取決於置0的個數和噪聲強度（標準差sigma的值）。

通過如上步驟，便得到了基礎估計，實踐表明該結果已經是一個很好的去噪結果，通過第二步可以進一步提高去噪圖的PSNR。

第二步（最終估計）

第二步與第一步類似。但在塊匹配時是用第一步的結果圖即基礎估計進行匹配，塊匹配的差異上限通常比第一步小一些。通過塊匹配的結果，每個參考塊形成兩個三維矩陣：一個是通過基礎估計形成的三維矩陣，另一個是通過這次匹配的坐標在噪聲圖上整合出的三維矩陣。

兩個三維數組均進行二維、一維變換。通常最終估計的二維變換採用DCT變換以得到更好的效果。用維納濾波將噪聲圖形成的三維矩陣進行係數放縮，該係數通過基礎估計的三維矩陣的值以及噪聲強度得出:

$W_{S_{X_{R}}}={\frac {|{\mathcal {T}}_{3D}({\hat {Y}}_{S_{X_{R}}}^{basic})|^{2}}{|{\mathcal {T}}_{3D}({\hat {Y}}_{S_{X_{R}}}^{basic})|^{2}+\sigma ^{2}}}$。

濾波後再通過反變換將噪聲圖的三維矩陣變換回圖像估計

${\hat {Y}}_{S_{X_{R}}}={\mathcal {T}}_{3D}^{-1}(W_{S_{X_{R}}}{\mathcal {T}}_{3D}(S_{X_{R}}))$

最終通過與第一步類似的加權求和方式將三維矩陣的各個塊復原成二維圖像形成最終估計，加權的權重取決於維納濾波的係數和$\sigma$的值。

經過最終估計之後，BM3D算法已經將原圖的噪聲顯着地去除。

參數選取

不同的參數會導致不同的性能和運算複雜度，且不同參數的表現也與噪聲的強度有關。根據測試，通常情況下塊的大小為8×8，第一步在33×33像素的範圍內選取16個最接近參照塊的塊，第二步在同樣的範圍內選取32個。第一步的硬閾值設為2.7。

彩色圖像

BM3D算法僅適用於單通道的灰階圖像。對於多通道的彩色圖像，由於自然圖像中RGB三個通道有高度相關性，通常會將圖像轉換為以明度-色度表示的色彩空間如YUV、YCbCr、等。對於此類色彩空間有以下幾點觀察:

• 相較於色度通道(U,V)，明度通道(Y)有較高的SNR。
• 明度通道(Y)包含較多有意義的圖像成份(邊緣、陰影、材質等)。
• 色度通道(U,V)大多為低頻信息。
• 色度通道(U,V)中的等明度區域大致相同。

因此，彩色圖像的BM3D算法可藉由計算明度通道中的相似塊，並選取色度通道中與明度通道相似塊相同座標的塊組成該通道的三維矩陣。其後的三維變換、濾波、加權平均及融合等步驟則由各通道分別各自完成。

參考文獻

• 該算法的設計者發表的論文