查看“︁三维块匹配算法”︁的源代码

'''三维块匹配算法'''（{{lang-en|'''Block Matching 3D'''}}，[[縮寫]]：'''BM3D'''）是一个效果比较好的[[图像去噪]]算法。通过与相邻图像块进行匹配，将若干相似的块整合为一个三维矩阵，在三维空间进行滤波处理，再将结果反变换融合到二维，形成去噪后的图像。该算法去噪效果显著，可以得到目前为止最高的[[峰值信噪比]]<ref>http://bolyai.cs.elte.hu/~izsakf/amata/cikkek08/buades10.pdf，Image{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }} Denoising Methods.A New Nonlocal Principle</ref>，但时间复杂度比较高。

==算法步骤==
BM3D算法分两个步骤，两个步骤算法类似，第一步通过原图匹配进行简单去噪形成基础估计，第二步通过原图和基础估计进行更细致的去噪，将[[PSNR]]进一步提高。

===第一步（基础估计）===
首先，在噪声图中以一个步长（通常为3个像素<ref name="Implementation"/>）设定若干个参照块（reference block），每个参照块在周围适当区域内进行搜索，寻找若干个差异最小的块（两个块的差异通常用<math>L_2</math>-[[范数]]来量化），将这些块以任意顺序整合成一个三维矩阵。通常会设定一个阈值，只将距离小于这个阈值的块整合到矩阵中，同时也会设置相似块的最大数量。参照块自己也是自己的相似块且差异度为0。

一个块<math>Z_{X}</math>与参考块<math>Z_{X_R}</math>的差异定义如下
: <math>d(Z_{X_R},Z_{X}) = \frac{\left\|Z_{X_R}-Z_{X}\right\|_2^2}{N_1}</math>,
其中<math>\left\|\cdot\right\|_2</math>为<math>L_2</math>-范数，<math>N_1</math>为块的大小。

将距离小于一个阈值的块整合成一个三维矩阵<math>S_{X_R}</math>
:<math>S_{X_R}={x\in X:d(Z_{X_R},Z_{X})<\tau_{match}}</math>

形成若干个三维的矩阵之后，首先将每个三维矩阵中的二维的块（即噪声图中的某个块）进行二维[[变换编码]]，可采用[[小波变换]]或[[DCT变换]]等（通常[[BIOR1.5]]小波变换更为常用，效果也更好）。如果使用的是小波变换，为了更好的分离出低频信息，需要变换多次——即在每次变换的左上角1/4低频区继续进行二维变换，直到完成2×2的变换为止。二维变换结束后，在矩阵的第三个维度进行一维变换（通常为[[阿达马变换|hadamard变换]]）。

此时的三维矩阵已经进行很好的处理。对三维矩阵进行硬阈值处理，将比较小的系数置0，然后通过在第三维的一维反变换和二维反变换得到处理后的图像块
: <math>\hat{Y}_{S_{X_R}} = \mathcal{T}_{3D}^{-1}(\Gamma(\mathcal{T}_{3D}(S_{X_R})))</math>，
其中<math>\mathcal{T}_{3D}</math>为三维变换，<math>\Gamma(\cdot)</math>为硬阈值函数。

此时三维矩阵中的每个二维块均是对去噪图像的估计，分别将这些块融合到原来的位置，每个像素的强度通过每个对应位置的块的值加权平均，权重取决于置0的个数和噪声强度（[[标准差]]sigma的值）。

通过如上步骤，便得到了基础估计，实践表明该结果已经是一个很好的去噪结果，通过第二步可以进一步提高去噪图的PSNR。

===第二步（最终估计）===
第二步与第一步类似。但在块匹配时是用第一步的结果图即基础估计进行匹配，块匹配的差异上限通常比第一步小一些。通过块匹配的结果，每个参考块形成两个三维矩阵：一个是通过基础估计形成的三维矩阵，另一个是通过这次匹配的坐标在噪声图上整合出的三维矩阵。

两个三维数组均进行二维、一维变换。通常最终估计的二维变换采用DCT变换以得到更好的效果。用[[维纳滤波]]将噪声图形成的三维矩阵进行系数放缩，该系数通过基础估计的三维矩阵的值以及噪声强度得出:
: <math>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}</math>。
滤波后再通过反变换将噪声图的三维矩阵变换回图像估计
: <math>\hat{Y}_{S_{X_R}} = \mathcal{T}_{3D}^{-1}(W_{S_{X_R}}\mathcal{T}_{3D}(S_{X_R}))</math>
最终通过与第一步类似的加权求和方式将三维矩阵的各个块复原成二维图像形成最终估计，加权的权重取决于维纳滤波的系数和<math>\sigma</math>的值。

经过最终估计之后，BM3D算法已经将原图的噪声显著地去除。

==参数选取==
不同的参数会导致不同的性能和运算复杂度<ref name="Implementation">{{Cite web |url=http://www.ipol.im/pub/art/2012/l-bm3d/article_lr.pdf |title=存档副本 |accessdate=2013-02-01 |archive-date=2016-03-05 |archive-url=https://web.archive.org/web/20160305064635/http://www.ipol.im/pub/art/2012/l-bm3d/article_lr.pdf |dead-url=no }}</ref>，且不同参数的表现也与噪声的强度有关。根据测试，通常情况下块的大小为8×8，第一步在33×33像素的范围内选取16个最接近参照块的块，第二步在同样的范围内选取32个。第一步的硬阈值设为2.7。

==彩色图像==
BM3D算法仅适用于单通道的灰阶图像。对于多通道的彩色图像，由于自然图像中[[RGB]]三个通道有高度相关性，通常会将图像转换为以[[明度]]-[[色度 (物理學)|色度]]表示的[[色彩空间]]如[[YUV]]、[[YCbCr]]、等。对于此类色彩空间有以下几点观察:
*相较于色度通道(U,V)，明度通道(Y)有较高的[[SNR]]。
*明度通道(Y)包含较多有意义的图像成份(边缘、阴影、材质等)。
*色度通道(U,V)大多为低频信息。
*色度通道(U,V)中的等明度区域大致相同。
因此，彩色图像的BM3D算法可藉由计算明度通道中的相似块，并选取色度通道中与明度通道相似块相同座标的块组成该通道的三维矩阵。其后的三维变换、滤波、加权平均及融合等步骤则由各通道分别各自完成。

==参考文献==
{{Reflist}}
*[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4271520 该算法的设计者发表的论文]

[[Category:图像处理]]