最近邻 resize 的实现和优化

目录
  • 1. 目的
  • 1. 影响性能的因素
  • 2. 对照: cv::resize 耗时(4ms)
  • 3. 实现和优化
    • naive 实现. 19ms
    • 第1次优化：提前算索引. 提速 2ms
    • 第2次优化：展开最里层循环中的Mat.ptr到外层. 提速9ms
    • 第3次优化: 展开次里层循环中 Mat.ptr 为外一层指针. 提速2ms
    • 第4次优化: 表格存 src_j * channels 而不是 src_j. 提速 1.4 ms
    • 第5次优化: 提前知晓通道数量为3. 提速 2ms
    • 第6次优化: 提前知晓原图和目标图的尺寸. 提速 0.5 ms
  • 4. 总结

1. 目的

记录最近邻插值（resize）在如下限定条件下的优化：

  • Android ARMv8 平台, 小米11 (QCOM 888)
  • 单线程
  • 绑小核
  • 原图: w=1920, h=1080, c=3
  • 目标: w=768, h=448, c=3
  • 和 OpenCV 4.5.5 Android 比对结果和速度

优化结果： 从 19 ms 优化到 2.5 ms. 作为对比：

  • cv::resize( INTER_NEAREST ) 耗时 4 ms
  • 没写 SIMD，通用优化（第4次优化）基本和 OpenCV 性能持平
  • 特定优化（提前知道通道数、图像尺寸）进一步提升了性能

1. 影响性能的因素

按优先级排序：

  1. 算法 / 策略. （本文不考虑）
  2. 大小核心. 小核心耗时可能是大核心的10倍
  3. 访问像素时的索引计算.
    • 常规的像素坐标访问
    • 插值算法中的 src/dst 坐标映射
  4. 提前知晓参数, 编译器自动优化
    • channels, height, width，缩放比例参数

这里贴出完整的耗时结果供参考， 后续则对每种优化贴出具体代码:

小核心：

method cost
cv::resize 4.116511 ms
plain::resize_nn 19.32479 ms
better::resize_nn_v1 16.67385 ms
better::resize_nn_v2 8.003958 ms
better::resize_nn_v3 5.574219 ms
better::resize_nn_v4 4.313802 ms
better::resize_nn_v5 3.067396 ms
better::resize_nn_v6 2.856667 ms

大核心：

method cost
cv::resize 0.975156 ms
plain::resize_nn 2.391042 ms
better::resize_nn_v1 2.247709 ms
better::resize_nn_v2 1.565156 ms
better::resize_nn_v3 1.208750 ms
better::resize_nn_v4 1.189636 ms
better::resize_nn_v5 0.862031 ms
better::resize_nn_v6 0.761927 ms

2. 对照: cv::resize 耗时(4ms)

std::string filename = load_prefix + "/1920x1080.jpg";

cv::Mat src = cv::imread(filename);

cv::Size dsz;
dsz.height = 448;
dsz.width = 768;

cv::Mat result_cv;
{
    AutoTimer timer("cv::resize");
    cv::resize(src, result_cv, dsz, 0, 0, cv::INTER_NEAREST);
}

耗时：
cv::resize: took 4.116511 ms
plain::resize_nn: took 19.324792 ms
better::resize_nn_v1: took 16.673854 ms
better::resize_nn_v2: took 8.003958 ms
better::resize_nn_v3: took 5.574219 ms
better::resize_nn_v4: took 4.313802 ms
better::resize_nn_v5: took 3.067396 ms
better::resize_nn_v6: took 2.856667 ms

3. 实现和优化

naive 实现. 19ms

template
static
T clip(T val, T minval, T maxval)
{
    if (minval > maxval) {
        std::swap(minval, maxval);
    }

    T result = val;
    if (val < minval) {
        result = minval;
    }
    if (val > maxval) {
        result = maxval;
    }
    return result;
}

void resize_nn_v0(const cv::Mat& src, cv::Mat& dst, cv::Size dsize)
{
    int depth = CV_MAT_DEPTH(src.type());
    if (depth != CV_8U) {
        CV_Error(cv::Error::StsBadArg, "只支持 uchar 类型");
    }

    cv::Size ssize = src.size();
    int channels = src.channels();

    dst.create(dsize, src.type());

    const int src_height = ssize.height;
    const int src_width = ssize.width;
    const int dst_height = dsize.height;
    const int dst_width = dsize.width;

    const float scale_w = src_width * 1.0 / dst_width;
    const float scale_h = src_height * 1.0 / dst_height;

    for (int i = 0; i < dst_height; i++)
    {
        int src_i = static_cast(i * scale_h);
        src_i = clip(src_i, 0, src_height-1);

        for (int j = 0; j < dst_width; j++)
        {
            int src_j = static_cast(j * scale_w); 
            src_j = clip(src_j, 0, src_width-1);

            for (int k = 0; k < channels; k++)
            {
                // .ptr(int, int) returns uchar* type
                dst.ptr(i, j)[k] = src.ptr(src_i, src_j)[k];
            }
        }
    }
}

即使是朴素实现， 仍然避开了一些坑：

  • 使用了 cv::Mat， 避免了手动定义数据结构 （naive 实现时没必要自己搞一套，应当通用）
  • 三重循环的遍历， 是遍历 dst 图而非 src 图， 使得映射索引的计算是用乘法获得，而不是除法（除法指令周期比乘法多）
  • 提前算出缩放因子 scale_w, scale_h， 而非在 for 循环中重复计算
  • 为保持和 OpenCV 结果一致， 对算出的索引施加截断（clip）
  • src_i 这一映射索引的计算， 放在了外层循环而非内层循环，避免了一些重复计算

耗时：
cv::resize: took 4.116511 ms
plain::resize_nn: took 19.324792 ms
better::resize_nn_v1: took 16.673854 ms
better::resize_nn_v2: took 8.003958 ms
better::resize_nn_v3: took 5.574219 ms
better::resize_nn_v4: took 4.313802 ms
better::resize_nn_v5: took 3.067396 ms
better::resize_nn_v6: took 2.856667 ms

第1次优化：提前算索引. 提速 2ms

原本要做 O(dh * dw) 次的索引计算和使用， 现改为 O(dw + dh) 次计算和 O(dw * dh) 次使用： 消除了不必要的乘法加法运算。

// 提前算索引. decrease 2ms
void resize_nn_v1(const cv::Mat& src, cv::Mat& dst, cv::Size dsize)
{
    int depth = CV_MAT_DEPTH(src.type());
    if (depth != CV_8U) {
        CV_Error(cv::Error::StsBadArg, "只支持 uchar 类型");
    }

    cv::Size ssize = src.size();
    int channels = src.channels();

    dst.create(dsize, src.type());

    const int src_height = ssize.height;
    const int src_width = ssize.width;
    const int dst_height = dsize.height;
    const int dst_width = dsize.width;

    const float scale_w = src_width * 1.0 / dst_width;
    const float scale_h = src_height * 1.0 / dst_height;

    std::vector src_h_table(dst_height);
    std::vector src_w_table(dst_width);

    for (int i = 0; i < dst_height; i++)
    {
        src_h_table[i] = static_cast(i * scale_h);
        src_h_table[i] = clip(src_h_table[i], 0, src_height - 1);
    }
    for (int j = 0; j < dst_width; j++)
    {
        src_w_table[j] = static_cast(j * scale_w);
        src_w_table[j] = clip(src_w_table[j], 0, src_width - 1);
    }

    for (int i = 0; i < dst_height; i++)
    {
        //int src_i = static_cast(i * scale_h);
        //src_i = clip(src_i, 0, src_height - 1);
        int src_i = src_h_table[i];

        for (int j = 0; j < dst_width; j++)
        {
            //int src_j = static_cast(j * scale_w);
            //src_j = clip(src_j, 0, src_width - 1);
            int src_j = src_w_table[j];

            for (int k = 0; k < channels; k++)
            {
                // .ptr(int, int) returns uchar* type
                dst.ptr(i, j)[k] = src.ptr(src_i, src_j)[k];
            }
        }
    }
}

耗时：
cv::resize: took 4.116511 ms
plain::resize_nn: took 19.324792 ms
better::resize_nn_v1: took 16.673854 ms
better::resize_nn_v2: took 8.003958 ms
better::resize_nn_v3: took 5.574219 ms
better::resize_nn_v4: took 4.313802 ms
better::resize_nn_v5: took 3.067396 ms
better::resize_nn_v6: took 2.856667 ms

第2次优化：展开最里层循环中的Mat.ptr到外层. 提速9ms

void resize_nn_v2(const cv::Mat& src, cv::Mat& dst, cv::Size dsize)
{
    int depth = CV_MAT_DEPTH(src.type());
    if (depth != CV_8U) {
        CV_Error(cv::Error::StsBadArg, "只支持 uchar 类型");
    }

    cv::Size ssize = src.size();
    int channels = src.channels();

    dst.create(dsize, src.type());

    const int src_height = ssize.height;
    const int src_width = ssize.width;
    const int dst_height = dsize.height;
    const int dst_width = dsize.width;

    const float scale_w = src_width * 1.0 / dst_width;
    const float scale_h = src_height * 1.0 / dst_height;

    std::vector src_h_table(dst_height);
    std::vector src_w_table(dst_width);

    for (int i = 0; i < dst_height; i++)
    {
        src_h_table[i] = static_cast(i * scale_h);
        src_h_table[i] = clip(src_h_table[i], 0, src_height - 1);
    }
    for (int j = 0; j < dst_width; j++)
    {
        src_w_table[j] = static_cast(j * scale_w);
        src_w_table[j] = clip(src_w_table[j], 0, src_width - 1);
    }

    for (int i = 0; i < dst_height; i++)
    {
        int src_i = src_h_table[i];

        for (int j = 0; j < dst_width; j++)
        {
            int src_j = src_w_table[j];

            uchar* dst_pixel = dst.ptr(i, j);
            const uchar* src_pixel = src.ptr(src_i, src_j);
            for (int k = 0; k < channels; k++)
            {
                // .ptr(int, int) returns uchar* type
                //dst.ptr(i, j)[k] = src.ptr(src_i, src_j)[k];
                dst_pixel[k] = src_pixel[k];
            }
        }
    }
}

耗时：
cv::resize: took 4.116511 ms
plain::resize_nn: took 19.324792 ms
better::resize_nn_v1: took 16.673854 ms
better::resize_nn_v2: took 8.003958 ms
better::resize_nn_v3: took 5.574219 ms
better::resize_nn_v4: took 4.313802 ms
better::resize_nn_v5: took 3.067396 ms
better::resize_nn_v6: took 2.856667 ms

第3次优化: 展开次里层循环中 Mat.ptr 为外一层指针. 提速2ms

void resize_nn_v3(const cv::Mat& src, cv::Mat& dst, cv::Size dsize)
{
    int depth = CV_MAT_DEPTH(src.type());
    if (depth != CV_8U) {
        CV_Error(cv::Error::StsBadArg, "只支持 uchar 类型");
    }

    cv::Size ssize = src.size();
    int channels = src.channels();

    dst.create(dsize, src.type());

    const int src_height = ssize.height;
    const int src_width = ssize.width;
    const int dst_height = dsize.height;
    const int dst_width = dsize.width;

    const float scale_w = src_width * 1.0 / dst_width;
    const float scale_h = src_height * 1.0 / dst_height;

    std::vector src_h_table(dst_height);
    std::vector src_w_table(dst_width);

    for (int i = 0; i < dst_height; i++)
    {
        src_h_table[i] = static_cast(i * scale_h);
        src_h_table[i] = clip(src_h_table[i], 0, src_height - 1);
    }
    for (int j = 0; j < dst_width; j++)
    {
        src_w_table[j] = static_cast(j * scale_w);
        src_w_table[j] = clip(src_w_table[j], 0, src_width - 1);
    }

    for (int i = 0; i < dst_height; i++)
    {
        int src_i = src_h_table[i];
        uchar* dst_line = dst.ptr(i);
        const uchar* src_line = src.ptr(src_i);
        for (int j = 0; j < dst_width; j++)
        {
            int src_j = src_w_table[j];

            //uchar* dst_pixel = dst.ptr(i, j);
            uchar* dst_pixel = dst_line + j * channels;
            //const uchar* src_pixel = src.ptr(src_i, src_j);
            const uchar* src_pixel = src_line + src_j * channels;
            for (int k = 0; k < channels; k++)
            {
                dst_pixel[k] = src_pixel[k];
            }
        }
    }
}

耗时：
cv::resize: took 4.116511 ms
plain::resize_nn: took 19.324792 ms
better::resize_nn_v1: took 16.673854 ms
better::resize_nn_v2: took 8.003958 ms
better::resize_nn_v3: took 5.574219 ms
better::resize_nn_v4: took 4.313802 ms
better::resize_nn_v5: took 3.067396 ms
better::resize_nn_v6: took 2.856667 ms

第4次优化: 表格存 src_j * channels 而不是 src_j. 提速 1.4 ms

void resize_nn_v4(const cv::Mat& src, cv::Mat& dst, cv::Size dsize)
{
    int depth = CV_MAT_DEPTH(src.type());
    if (depth != CV_8U) {
        CV_Error(cv::Error::StsBadArg, "只支持 uchar 类型");
    }

    cv::Size ssize = src.size();
    int channels = src.channels();

    dst.create(dsize, src.type());

    const int src_height = ssize.height;
    const int src_width = ssize.width;
    const int dst_height = dsize.height;
    const int dst_width = dsize.width;

    const float scale_w = src_width * 1.0 / dst_width;
    const float scale_h = src_height * 1.0 / dst_height;

    std::vector src_h_table(dst_height);
    std::vector src_w_table(dst_width);

    for (int i = 0; i < dst_height; i++)
    {
        src_h_table[i] = static_cast(i * scale_h);
        src_h_table[i] = clip(src_h_table[i], 0, src_height - 1);
    }
    for (int j = 0; j < dst_width; j++)
    {
        src_w_table[j] = static_cast(j * scale_w);
        src_w_table[j] = clip(src_w_table[j], 0, src_width - 1) * channels;
    }

    for (int i = 0; i < dst_height; i++)
    {
        int src_i = src_h_table[i];
        uchar* dst_line = dst.ptr(i);
        const uchar* src_line = src.ptr(src_i);
        for (int j = 0; j < dst_width; j++)
        {
            //uchar* dst_pixel = dst.ptr(i, j);
            uchar* dst_pixel = dst_line + j * channels;
            //const uchar* src_pixel = src.ptr(src_i, src_j);
            const uchar* src_pixel = src_line + src_w_table[j];
            for (int k = 0; k < channels; k++)
            {
                dst_pixel[k] = src_pixel[k];
            }
        }
    }
}

耗时：
cv::resize: took 4.116511 ms
plain::resize_nn: took 19.324792 ms
better::resize_nn_v1: took 16.673854 ms
better::resize_nn_v2: took 8.003958 ms
better::resize_nn_v3: took 5.574219 ms
better::resize_nn_v4: took 4.313802 ms
better::resize_nn_v5: took 3.067396 ms
better::resize_nn_v6: took 2.856667 ms

第5次优化: 提前知晓通道数量为3. 提速 2ms

void resize_nn_v5(const cv::Mat& src, cv::Mat& dst, cv::Size dsize)
{
    int depth = CV_MAT_DEPTH(src.type());
    if (depth != CV_8U) {
        CV_Error(cv::Error::StsBadArg, "只支持 uchar 类型");
    }

    cv::Size ssize = src.size();
    //int channels = src.channels();
    const int channels = 3; //!!

    dst.create(dsize, src.type());

    const int src_height = ssize.height;
    const int src_width = ssize.width;
    const int dst_height = dsize.height;
    const int dst_width = dsize.width;

    const float scale_w = src_width * 1.0 / dst_width;
    const float scale_h = src_height * 1.0 / dst_height;

    std::vector src_h_table(dst_height);
    std::vector src_w_table(dst_width);

    for (int i = 0; i < dst_height; i++)
    {
        src_h_table[i] = static_cast(i * scale_h);
        src_h_table[i] = clip(src_h_table[i], 0, src_height - 1);
    }
    for (int j = 0; j < dst_width; j++)
    {
        src_w_table[j] = static_cast(j * scale_w);
        src_w_table[j] = clip(src_w_table[j], 0, src_width - 1) * channels;
    }

    for (int i = 0; i < dst_height; i++)
    {
        int src_i = src_h_table[i];
        uchar* dst_line = dst.ptr(i);
        const uchar* src_line = src.ptr(src_i);
        for (int j = 0; j < dst_width; j++)
        {
            //uchar* dst_pixel = dst.ptr(i, j);
            uchar* dst_pixel = dst_line + j * channels;
            //const uchar* src_pixel = src.ptr(src_i, src_j);
            const uchar* src_pixel = src_line + src_w_table[j];
            for (int k = 0; k < channels; k++)
            {
                dst_pixel[k] = src_pixel[k];
            }
        }
    }
}

耗时：
cv::resize: took 4.116511 ms
plain::resize_nn: took 19.324792 ms
better::resize_nn_v1: took 16.673854 ms
better::resize_nn_v2: took 8.003958 ms
better::resize_nn_v3: took 5.574219 ms
better::resize_nn_v4: took 4.313802 ms
better::resize_nn_v5: took 3.067396 ms
better::resize_nn_v6: took 2.856667 ms

第6次优化: 提前知晓原图和目标图的尺寸. 提速 0.5 ms

void resize_nn_v6(const cv::Mat& src, cv::Mat& dst, cv::Size dsize)
{
    int depth = CV_MAT_DEPTH(src.type());
    if (depth != CV_8U) {
        CV_Error(cv::Error::StsBadArg, "只支持 uchar 类型");
    }

    cv::Size ssize = src.size();
    //int channels = src.channels();
    const int channels = 3;

    dst.create(dsize, src.type());

    //const int src_height = ssize.height;
    //const int src_width = ssize.width;
    //const int dst_height = dsize.height;
    //const int dst_width = dsize.width;

    const int src_height = 1080;
    const int src_width = 1920;
    const int dst_height = 448;
    const int dst_width = 768;

    const float scale_w = src_width * 1.0 / dst_width;
    const float scale_h = src_height * 1.0 / dst_height;

    std::vector src_h_table(dst_height);
    std::vector src_w_table(dst_width);

    for (int i = 0; i < dst_height; i++)
    {
        src_h_table[i] = static_cast(i * scale_h);
        src_h_table[i] = clip(src_h_table[i], 0, src_height - 1);
    }
    for (int j = 0; j < dst_width; j++)
    {
        src_w_table[j] = static_cast(j * scale_w);
        src_w_table[j] = clip(src_w_table[j], 0, src_width - 1) * channels;
    }

    for (int i = 0; i < dst_height; i++)
    {
        int src_i = src_h_table[i];
        uchar* dst_line = dst.ptr(i);
        const uchar* src_line = src.ptr(src_i);
        for (int j = 0; j < dst_width; j++)
        {
            uchar* dst_pixel = dst_line + j * channels;
            const uchar* src_pixel = src_line + src_w_table[j];
            for (int k = 0; k < channels; k++)
            {
                dst_pixel[k] = src_pixel[k];
            }
        }
    }
}

耗时：
cv::resize: took 4.116511 ms
plain::resize_nn: took 19.324792 ms
better::resize_nn_v1: took 16.673854 ms
better::resize_nn_v2: took 8.003958 ms
better::resize_nn_v3: took 5.574219 ms
better::resize_nn_v4: took 4.313802 ms
better::resize_nn_v5: took 3.067396 ms
better::resize_nn_v6: took 2.856667 ms

4. 总结

1. 大小核心对性能的影响可能很大， 优化仍然有必要

最近邻 resize 这样一个简单的函数， 简单的测试可能得到很短的耗时，例如 2ms，进一步误以为没什么优化空间。而在复杂环境下可能会被分配到小核心上， 得到的耗时可能是原来的 10 倍。

2. Mat.ptr(i, j) 看着方便， 但在内存循环时大幅降低了性能

3. 提前计算出映射索引， 有一定性能提升， 不过没有 Mat.ptr(i, j) 那么大的影响

4. 编译阶段知晓更多的参数， 即使没写 SIMD， 也得到了比 OpenCV 更快的性能.

图像处理优化

相关

数字化制造的世界最高水平，灯塔工厂推动全价值链技术变革和优化

基于CDN边缘网络智能优化图片和视频

DP决策优化小结

UGUI优化

双一流博士整理的计算机视觉学习路线（深度学习+传统图像处理）

RabbitMQ的几种工作模式和优化建议

vue首屏优化

dp多维状态的优化

MySQL之针对应用层的优化

深度学习模型训练阶段的加速与优化

前端性能优化

单调队列优化DP历险记

标签