如何快速计算每个像素半径R圆形邻域内的最高频颜色

是否存在O(n)复杂度的算法？ #

存在，核心前提是你已经提前做了颜色聚类将总颜色数K限制为常数（不随图像尺寸、半径R变化），核心技术是固定形状邻域的滑动直方图增量更新，运行原理如下：

• 第一步先将聚类后的所有颜色映射为0~K-1的整数索引，整个过程只需要遍历一次图像，时间复杂度O(n)。
• 预先生成半径R的圆形邻域的坐标偏移表，记录所有属于圆内的相对坐标点。
• 计算左上角第一个有效中心（R, R）对应的圆形邻域的颜色直方图，统计每个颜色的出现次数，这个步骤时间复杂度O(R²)，和整体n相比可以忽略。
• 之后所有中心的直方图都通过增量更新得到：
  1. 横向移动中心时，仅需要减去当前窗口左侧移出圆范围的所有像素的计数，加上右侧新移入圆范围的所有像素的计数，每次更新操作的次数和R成正比，但是因为K是常数，判断众数的操作可以通过维护当前最大计数值和对应颜色做到O(1)。
  2. 换行移动中心时，同理仅需要减去顶部移出圆范围的所有行的像素计数，加上底部新移入圆范围的所有行的像素计数。
• 因为每个像素只会被加入直方图一次、移出直方图一次，整体时间复杂度为O(n + K)，当K为常数时就是O(n)。

如果没有提前做颜色聚类，全彩场景下K=2^24，那么没有实用的O(n)算法，因为每次更新后查找众数的复杂度会变成O(K)，整体复杂度会上升到O(n*K)，实际运行速度还不如基础版本。

现有算法的优化方案（不考虑并行） #

可以从以下几个维度优化，实测通常能带来10~100倍的速度提升：

• 替换Python原生循环为Numpy向量化操作：纯Python的多层循环是性能瓶颈，用Numpy的切片、掩码、广播操作实现统计逻辑，能利用底层C实现的运算能力大幅提速。
• 预生成圆形邻域掩码：提前计算好半径R对应的2R+1尺寸的二值掩码，圆内位置标1、外部标0，后续统计时直接用掩码过滤邻域像素，不需要每次判断坐标是否在圆内。
• 增量更新直方图而非重复统计：不要每个中心都重新遍历整个圆形邻域，按照上面提到的滑动窗口逻辑，仅更新移出/移入的像素计数，同时维护当前窗口的最大计数值和对应颜色，不需要每次遍历所有颜色找众数。
• 利用业务规则剪枝：你已经给中心像素设置了更高权重，统计前可以先判断中心颜色的计数是否已经大于等于其他颜色的最大可能计数，如果满足可以直接返回中心颜色，跳过剩余统计逻辑。
• 优化存储类型：颜色索引用uint8存储，直方图计数用uint16存储（半径R≤255时，圆形邻域总像素数不超过20万，完全满足存储需求），减少内存读写开销。

内容的提问来源于stack exchange，提问作者Doreapp