三維塊匹配算法

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

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

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

此時的三維矩陣已經進行很好的處理。對三維矩陣進行硬閾值處理，將比較小的係數置0，然後通過在第三維的一維反變換和二維反變換得到處理後的圖像塊。每個二維塊均是對去噪圖像的估計，分別將這些塊融合到原來的位置，每個像素的強度通過每個對應位置的塊的值加權平均，權重取決於置0的個數和噪聲強度（標準差sigma的值）。

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

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

兩個三維數組均進行二維、一維變換。通常最終估計的二維變換採用DCT變換以得到更好的效果。用維納濾波將噪聲圖形成的三維矩陣進行係數放縮，該係數通過基礎估計的三維矩陣的值以及噪聲強度得出。濾波後再通過反變換將噪聲圖的三維矩陣變換回圖像估計。最終通過與第一步類似的加權求和方式將三維矩陣的各個塊復原成二維圖像形成最終估計，加權的權重取決於維納濾波的係數和sigma的值。

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

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