如何通过减少迭代优化ImageBlur代码以提升运行速度？

当然可以通过减少迭代次数让这段代码运行更快，原代码的核心问题是每个像素都重复遍历邻域内的所有像素，时间复杂度为O(W×H×(2dx+1)×(2dy+1))，当dx、dy较大时，迭代次数会呈指数级增长。最有效的优化方式是用**积分图像（前缀和）**将邻域求和的复杂度降到O(1)，整体迭代次数直接压缩到O(W×H)。

原代码的隐藏问题 #

先提个关键bug：原代码在计算过程中直接修改了原图像的像素值，后续像素的计算会使用已经被模糊后的像素，导致最终的模糊结果不符合预期。优化时必须先保留原始图像的完整数据。

优化方案：积分图像法 #

积分图像的核心是预先计算每个位置的前缀和，后续任意矩形区域的像素和都可以通过4个点的差值快速得到，完全不需要遍历邻域：

步骤1：构建积分图像 #

遍历一次原始图像，生成一个积分图像数组，其中integral[y][x]表示原图像左上角(0,0)到(x,y)的所有像素之和。

步骤2：快速计算邻域和 #

对于每个目标像素(x,y)，其邻域范围是[x-dx, x+dx] × [y-dy, y+dy]，利用积分图像可以直接算出这个区域的像素和，再除以有效像素数得到均值。

优化后的代码 #

#include <stdint.h>
#include <stdlib.h>

typedef struct {
    uint8_t* pixel;
    int width;
    int height;
} Image;

void ImageBlur(Image img, int dx, int dy) {
    if (dx <= 0 && dy <= 0) return;

    size_t imgWidth = (size_t)img.width;
    size_t imgHeight = (size_t)img.height;
    int64_t* integral = malloc(sizeof(int64_t) * imgWidth * imgHeight);
    if (!integral) return;

    // 步骤1：构建积分图像
    for (size_t y = 0; y < imgHeight; ++y) {
        int64_t rowSum = 0;
        for (size_t x = 0; x < imgWidth; ++x) {
            size_t idx = y * imgWidth + x;
            rowSum += img.pixel[idx];
            if (y == 0) {
                integral[idx] = rowSum;
            } else {
                integral[idx] = integral[(y-1)*imgWidth + x] + rowSum;
            }
        }
    }

    // 步骤2：利用积分图像计算每个像素的模糊值
    // 先创建临时数组保存结果，避免修改原图像影响计算
    uint8_t* result = malloc(sizeof(uint8_t) * imgWidth * imgHeight);
    if (!result) {
        free(integral);
        return;
    }

    for (size_t y = 0; y < imgHeight; ++y) {
        for (size_t x = 0; x < imgWidth; ++x) {
            // 计算邻域的边界（确保不越界）
            int x1 = (int)x - dx;
            int x2 = (int)x + dx;
            int y1 = (int)y - dy;
            int y2 = (int)y + dy;
            x1 = x1 < 0 ? 0 : x1;
            x2 = x2 >= (int)imgWidth ? (int)imgWidth - 1 : x2;
            y1 = y1 < 0 ? 0 : y1;
            y2 = y2 >= (int)imgHeight ? (int)imgHeight - 1 : y2;

            // 用积分图像计算区域和
            int64_t sum = integral[y2 * imgWidth + x2];
            if (x1 > 0) sum -= integral[y2 * imgWidth + (x1 - 1)];
            if (y1 > 0) sum -= integral[(y1 - 1) * imgWidth + x2];
            if (x1 > 0 && y1 > 0) sum += integral[(y1 - 1) * imgWidth + (x1 - 1)];

            // 计算有效像素数
            int count = (x2 - x1 + 1) * (y2 - y1 + 1);
            result[y * imgWidth + x] = (uint8_t)(sum / count);
        }
    }

    // 将结果复制回原图像
    for (size_t i = 0; i < imgWidth * imgHeight; ++i) {
        img.pixel[i] = result[i];
    }

    // 释放内存
    free(integral);
    free(result);
}

优化效果说明 #

• 迭代次数：原代码需要W×H×(2dx+1)×(2dy+1)次迭代，优化后只需要2×W×H次（一次构建积分图，一次计算结果），迭代次数减少了几个数量级，dx、dy越大，提速效果越明显。
• 修复了原代码的bug：通过临时数组保存结果，避免了计算过程中修改原图像导致的错误。
• 运算效率：用整数运算替代了多次内存访问和累加，进一步提升速度。

额外优化建议 #

• 如果图像尺寸固定，可预先分配积分图像和结果数组的内存，避免每次调用时的malloc开销。
• 对于彩色图像，可以对每个通道单独应用该优化逻辑。
• 如果平台支持SIMD指令，可以进一步加速积分图像的构建过程。

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