几周前，我随手翻了翻有什么能优化的代码，纯粹为了好玩。Rust的image crate进入了视线：以前用过，下载量排名靠前，而且图像处理本身就是计算密集型任务。很快，我盯上了一个叫fast_blur的方法。名字都这么叫了，不优化一下说不过去。
最终结果：对u8像素图像，最高快了5.9倍。
在讲优化之前，先搞清楚模糊算法是怎么回事。不同算法在质量和速度之间怎么取舍，fast_blur又站在哪个位置。
高斯模糊可能是最常见的，大家说的"模糊"一般就指这个。每个像素被替换成邻居的加权平均，σ控制影响范围。实际实现里，像素是离散的，所以变成卷积核，核大小k和σ直接挂钩。
朴素二维高斯模糊是O(k²)每像素。但可以拆成两个一维pass，复杂度降到O(k)。image-rs的blur就是这么实现的。不过如果愿意牺牲质量，还能更快。
盒式模糊简单得多：每个像素替换成固定窗口内邻居的平均值，相当于用均匀权重做卷积。确实能模糊，但核没有平滑过渡，结果比高斯更生硬、更不自然。
盒式模糊也能拆成两个一维pass。而且所有权重都是1/k，可以把除法提出来：先累加所有值，最后统一除一次。更进一步，每个pass用滑动窗口，不用每次都重新算平均。最终每像素大约2次加法（垂直+水平）加1次除法，复杂度变成O(1)，和核大小无关。
从O(k²)到O(1)，快了很多。代价是结果更块状、更不自然。
Fast Almost-Gaussian Filtering，也就是fast_blur，试图两全其美——只要精确度不是硬性要求。核心思路是：连续做3次盒式模糊，精心选择核大小，结果能很好地逼近真正的高斯模糊。
每多一次盒式模糊，核就变得更平滑、更接近高斯。好消息是，这样能得到看起来不错的模糊效果，但用的全是盒式模糊。
既然只用盒式模糊，我们就有了看起来还行的模糊，但复杂度是O(1)每像素，和σ无关。这正是image-rs里fast_blur的实现。
现在算法背景清楚了，复杂度和质量也明白了，可以开始看代码、想办法让它更快了。
热门跟贴