积分图如何实现均值滤波，为什么能把窗口求和从面积相关降到常数时间？｜小米 C/C++面经解析

60 秒回答模板

回答可以先说明均值滤波是在每个像素周围取一个矩形窗口，计算窗口内像素平均值；朴素实现对每个输出像素都重新遍历窗口，所以复杂度与窗口面积相关。积分图的定义是 S(x,y) 表示原图从左上角到当前位置之前的矩形累计和，构建时每个位置由左、上、左上和当前像素递推得到。求任意窗口 [x1,x2)×[y1,y2) 的和时，只需 S(x2,y2)-S(x1,y2)-S(x2,y1)+S(x1,y1)，四次访问就完成矩形求和。均值滤波只要把这个和除以实际窗口面积。最后要补充边界窗口、数据类型溢出、多通道分别处理、预处理成本和适用范围：积分图适合矩形均匀权重，不直接适合任意权重核。

考点 前缀预处理

难度 真实面经题

回答目标 让读者能用前缀和思想解释积分图均值滤波：明确构建、四角查询、面积归一化、复杂度下降原因，并能指出边界、溢出、多通道和适用范围限制。

深入解析

均值滤波的朴素成本

均值滤波也叫盒式滤波，输出像素等于周围矩形窗口内像素的平均值。若窗口大小为 K×K，朴素实现每个像素都要重新累加 K² 个值，总复杂度约为 O(HWK²)。当窗口变大时，重复求和非常多，因为相邻窗口共享了大量像素却没有复用。

积分图定义

积分图保存从图像左上角到某个位置的矩形前缀和。常用半开区间形式让 S(x,y) 表示原始图像中 x 之前、y 之前区域的累计和，并额外保留一行一列 0 作为边界。这样公式更统一，窗口碰到图像左边或上边时也不需要特殊分支。

构建递推关系

积分图可以一遍扫描构建：当前位置的前缀和等于左边前缀加上上边前缀，减去左上角被重复计算的区域，再加当前像素。每个位置只做常数次加减，因此构建成本是 O(HW)。这一步把大量后续窗口求和的重复工作提前压缩成前缀信息。

四角求矩形和

任意轴对齐矩形窗口的和都可以由右下、左下、右上、左上四个积分值组合得到：大前缀减去左侧区域和上侧区域，再加回被减了两次的左上区域。无论窗口面积是 3×3 还是 101×101，求和都只需要四个积分值和常数次加减。

均值输出和边界

得到窗口和后除以窗口面积就是均值。边界处可以选择裁剪窗口、复制边界、镜像边界或先 padding 再计算；若采用裁剪窗口，面积会随位置变化，除数必须使用实际有效像素数。边界策略不同会影响图像四周的亮度和平滑程度。

复杂度为何降为常数

积分图并不是让整个算法无成本，而是把每个窗口求和从 O(K²) 降为 O(1)，加上一次 O(HW) 预处理。因此对固定图像做大窗口或多窗口均值时收益很大。整体均值滤波复杂度从 O(HWK²) 变成 O(HW)，并且几乎不随窗口面积增长。

数据类型和多通道

积分图累计的是区域和，数值范围会远大于原像素。8 位图像在大分辨率或大窗口下使用 32 位整数可能仍有溢出风险，需要根据最大像素值和面积选择 32 位、64 位或浮点类型。彩色图像通常每个通道独立构建积分图，或使用向量化结构同时维护多个通道。

适用范围和限制

积分图最适合矩形窗口、均匀权重的求和或均值，也可扩展到局部方差等统计量。它不直接适合高斯卷积、Sobel 等非均匀权重核，除非用多个矩形近似。若窗口很小，积分图的额外内存和预处理未必比直接卷积更划算。

易错点

把积分图说成每次窗口仍要遍历，只是少算一点，没抓住四角 O(1) 查询的本质。
忘记左上区域会被减两次，需要加回，否则矩形和公式错误。
边界处仍除以固定窗口面积，导致图像边缘平均值偏暗或偏亮。
使用原像素类型保存积分图，忽略累计和可能远超 8 位或 16 位范围。
认为积分图可以直接加速所有卷积核，忽略它只适合矩形均匀权重求和。
没有说明预处理成本和额外内存，把单次小窗口滤波也绝对化为积分图更优。
多通道图像只建一个积分图，混淆颜色通道求和，导致输出颜色错误。

面试官追问

积分图为什么只要四个点就能求矩形和？

因为每个积分值都是从左上角开始的前缀矩形和，通过包含排除可以减掉窗口左侧和上侧区域，再加回重复减掉的左上区域。

积分图构建复杂度是多少？

每个像素只依赖左、上、左上和当前像素，常数次运算即可构建，所以预处理复杂度是 O(HW)。

边界处窗口面积怎么处理？

如果窗口被裁剪，就用有效区域面积作为除数；如果采用 padding，就按 padding 后窗口面积和像素定义计算，关键是训练或处理流程中保持策略一致。

积分图能不能做高斯滤波？

不能直接做精确高斯滤波，因为高斯核权重不是矩形内均匀权重；可以用多个盒滤波近似高斯，但那属于近似方案。

为什么要担心溢出？

积分图保存的是大区域累计和，最大值接近最大像素值乘以区域面积，大图或高位深图像很容易超过原像素类型范围。

窗口很小时还需要积分图吗？

不一定。小窗口直接卷积可能更简单且缓存友好，积分图更适合大窗口、多尺度窗口或大量重复矩形求和。