NL-Means（Non-Local Means，非局部均值）是图像去噪领域公认的经典算法，它利用图像自身的冗余性，通过寻找相似像素块并对它们加权平均来恢复干净图像。然而原始论文中的暴力实现复杂度极高，对一张512乘512的灰度图全图遍历，可能需要上亿次块距离计算，耗时以分钟计。本文从性能瓶颈出发，详细讲解如何利用积分图和一系列快速算法技巧，让NL-Means的计算速度提升一到两个数量级。
NL-Means为什么慢：计算瓶颈分析
NL-Means的核心思想是：对图像中每个像素，在其邻域内寻找所有结构相似的像素块，根据块之间的相似程度计算权重，再用这些权重对像素值做加权平均。设块大小为f乘f（例如7乘7），搜索窗口大小为S乘S（例如21乘21），那么对每个中心像素，需要与窗口内约441个候选块逐一计算距离，每次距离计算涉及49个像素的差值平方累加。
粗略估算一下计算量：对一个百万像素的图像，总的乘加次数约为 1000000 × 441 × 49 ≈ 2.2×10^10，也就是两百多亿次运算。即使使用C语言配合编译器优化，单线程也很难在一秒内完成。如果按照原始论文的全图搜索（搜索范围是整幅图像），计算量还要再放大几百倍，这就是NL-Means慢的根本原因。
更关键的是，块距离计算内部存在大量重复劳动。相邻两个候选块有f乘(f-1)个像素是重叠的，暴力实现每次都从头累加，完全忽略了这种重叠性。这就好比每次算前n项和都从第一项加起，却没有利用已经算好的部分和。识别出这个冗余，正是后续所有加速方案的突破口。
积分图加速：把双重循环变成常数操作
积分图（Integral Image）最初由Viola和Jones在人脸检测中提出，它能把任意矩形区域内的像素求和降到O(1)复杂度。定义积分图I(x,y)为原图从左上角到坐标(x,y)的矩形区域像素累加和，那么任意矩形区域R内的像素和，只需查四次积分图并做三次加减即可得到。
用于NL-Means时，技巧在于计算的不是像素和，而是两个块之间的差值平方和。注意到平方运算可以展开：
Σ (p(i) - q(i))^2 = Σ p(i)^2 + Σ q(i)^2 - 2 × Σ p(i) × q(i)
前两项是单幅图的平方图，可以直接构建平方积分图，查询任意块的像素平方和只需O(1)。真正麻烦的是中间的交叉项Σ p(i)×q(i)，它描述两幅（或同一幅图平移后）对应位置的乘积。Darbon等人在2008年提出的经典方案是：对每一个可能的偏移量d，构造一幅乘积图P(x,y) = f(x,y) × f(x+d)，对P再建积分图。这样对每个偏移，所有块距离都可以通过积分图查询加常数次运算得到。
这种方法的复杂度分析：设搜索窗口内有K个偏移量（例如21乘21窗口有441个），每个偏移需要建一幅O(N)的乘积积分图，之后每个像素的该偏移距离查询是O(1)。总复杂度从O(N × K × f^2)降为O(N × K)，块大小f^2这个因子被完全消掉了。当块从7乘7换成11乘11时，传统实现耗时增加约2.5倍，积分图方案几乎不变，块越大加速比越明显。同时权重累加也可以用同样的积分图机制并行完成，避免第二遍遍历。
下面给出基于OpenCV和Python的简化示例，演示利用平方积分图加速部分距离项的思路（完整实现还需处理交叉项）：
import cv2
import numpy as np
def integral_sq(img):
# 计算平方图并求积分图，float64避免溢出
sq = img.astype(np.float64) ** 2
return cv2.integral(sq)
def block_sq_sum(ii, x, y, f):
# 利用积分图O(1)查询以(x,y)为中心、边长f的块的平方和
half = f // 2
x1, y1 = max(x - half, 0), max(y - half, 0)
x2, y2 = min(x + half + 1, ii.shape[1] - 1), min(y + half + 1, ii.shape[0] - 1)
return (ii[y2, x2] - ii[y1, x2]
- ii[y2, x1] + ii[y1, x1])
# 实际的快速NL-Means还需对每个偏移d构建乘积积分图
# prod = img * shift(img, d)，再对prod求积分图，从而O(1)得到交叉项
# OpenCV的fastNlMeansDenoising内部即采用类似的积分图加速策略值得一提的是，OpenCV已经内置了积分图加速版本的实现，即fastNlMeansDenoisingColored系列函数，其内部正是采用上述快速算法，处理速度远快于自己写的暴力版本。如果不是出于学习或定制需求，优先调用现成的高效实现是最务实的选择。
工程层面的进一步提速：限制搜索与块降采样
除了算法层面的积分图加速，工程上还有多个可以叠加的优化手段。第一是限制搜索窗口。原始论文允许全图搜索，但实验表明自然图像的相似块绝大多数集中在中心像素周围21乘21甚至13乘13的区域内，把全图搜索改成固定窗口搜索，计算量直接下降数百倍，而去噪质量（PSNR）通常只下降0.1到0.3dB，性价比极高。
第二是块降采样策略。Buades等人后续提出的变体不再为每个块单独计算权重，而是让相邻块共享同一组偏移权重，权重计算次数从N次降到K次（K为偏移数量，通常几百），每个像素的最终值由覆盖它的所有块的估计结果聚合而来。这一改动把权重计算的开销摊薄了数十倍，且实验显示对去噪质量影响甚微。
第三是硬件与并行化。积分图方案中各个偏移量的积分图构建与查询彼此完全独立，天然适合并行。在CPU上可以用OpenMP按偏移量分线程；在GPU上，乘积积分图的构建可用scan算法高效实现，整个算法能压缩到几十毫秒级别，满足准实时处理需求。另外，对高分辨率图像，先下采样估计噪声参数和权重参数，再回原分辨率执行，也能显著减少计算。
最后需要注意参数与质量的平衡。积分图方法使用float累加大图像的平方和时可能出现精度问题，实践中应使用float64或分段累加；搜索窗口半径与去噪强度sigma需要匹配，盲目增大窗口只会增加耗时。综合积分图加速、窗口限制和并行化三招，NL-Means完全可以从分钟级压缩到亚秒级，让这个经典算法在实时性要求较高的场景中也能占有一席之地。