opencv 并行化代码

1. 目标

本文目标是演示如何使用 OpenCV parallel_for_ 框架轻松实现并行化。为了说明这个概念，将编写一个程序来对图像执行卷积操作。完整的代码在这里。

2. 前提

2.1 并行框架

第一个前提条件是使用并行框架构建 OpenCV。在 OpenCV 4.5 中，并行框架按以下顺序可用：

英特尔线程构建模块（第 3 方库，需要显式启用）

OpenMP（集成到编译器，需要显式启用）

APPLE GCD（系统范围，自动使用（仅限 APPLE））

Windows RT 并发（系统范围，自动使用（仅限 Windows RT））

Windows 并发（运行时的一部分，自动使用（仅限 Windows - MSVC++ >= 10））

如您所见，OpenCV 库中可以使用多个并行框架。一些并行库是第三方库，必须在构建之前在 CMake 中显式启用，而其他并行库是平台自动可用的（例如 APPLE GCD）。

2.2 竞争条件

当多个线程同时尝试写入或读取和写入特定内存位置时，就会出现竞争条件。基于此，可以将算法大致分为两类：-

只有单个线程将数据写入特定内存位置的算法。

例如，在卷积中，即使多个线程可以在特定时间从像素读取，也只有单个线程写入特定像素。

多个线程可以写入单个内存位置的算法。

寻找轮廓、特征等。此类算法可能需要每个线程同时将数据添加到全局变量。例如，在检测特征时，每个线程会将图像各自部分的特征添加到公共向量中，从而创建竞争条件。

将使用执行卷积的示例来演示 parallel_for_ 并行计算的使用。这是一个不会导致竞争条件的算法示例。

4. 理论

卷积是一种简单的数学运算，广泛用于图像处理。在图像上滑动一个称为卷积核的小矩阵，图像与卷积核相应值的乘积之和为输出图像提供特定像素的值（称为卷积核的锚点） . 根据卷积核中的值，会得到不同的结果。在下面的示例中，使用 3x3 卷积核（锚点在其中心）并在 5x5 矩阵上进行卷积以生成 3x3 矩阵。可以通过使用合适的值填充输入来更改输出的大小。

有关不同卷积核及其作用的更多信息，请查看此处

出于本文的目的，将实现函数的最简单形式，该函数采用灰度图像（1 通道）和奇数长度的方形卷积核并生成输出图像。该操作不会就地执行。

可以临时存储一些相关像素，以确保在卷积期间使用原始值，然后就地执行。但是，本教程的目的是介绍 parallel_for_ 函数，就地实现可能过于复杂。

5. 伪代码

InputImage src, OutputImage dst, kernel(size n)
makeborder(src, n/2)
for each pixel (i, j) strictly inside borders, do:
    value := 0
    for k := -n/2 to n/2, do:
        for l := -n/2 to n/2, do:
            value += kernel[n/2 + k][n/2 + l]*src[i + k][j + l]
    dst[i][j] := value
对于大小为n的卷积核，将添加大小为n/2的边框来处理边缘情况。然后运行两个循环以沿着内核移动并将乘积相加
6. 实现
6.1 顺序执行
void conv_seq(Mat src, Mat &dst, Mat kernel)
    int rows = src.rows, cols = src.cols;
    dst = Mat(rows, cols, src.type());
    // Taking care of edge values
    // Make border = kernel.rows / 2;
    int sz = kernel.rows / 2;
    copyMakeBorder(src, src, sz, sz, sz, sz, BORDER_REPLICATE);
    for (int i = 0; i < rows; i++)
        uchar *dptr = dst.ptr(i);
        for (int j = 0; j < cols; j++)
            double value = 0;
            for (int k = -sz; k <= sz; k++)
                // slightly faster results when we create a ptr due to more efficient memory access.
                uchar *sptr = src.ptr(i + sz + k);
                for (int l = -sz; l <= sz; l++)
                    value += kernel.ptr<double>(k + sz)[l + sz] * sptr[j + sz + l];
            dptr[j] = saturate_cast<uchar>(value);
首先创建一个与 src 大小相同的输出矩阵（dst），并为 src 图像添加边框（以处理边缘情况）。
  int rows = src.rows, cols = src.cols;
  dst = Mat(rows, cols, src.type());
  // Taking care of edge values
  // Make border = kernel.rows / 2;
  int sz = kernel.rows / 2;
  copyMakeBorder(src, src, sz, sz, sz, sz, BORDER_REPLICATE);
copyMakeBorder (src, src, sz, sz, sz, sz, BORDER_REPLICATE );
然后依次遍历 src 图像中的像素并计算内核和相邻像素值的值。然后将值填充到 dst 图像中的相应像素。
for (int i = 0; i < rows; i++)
        uchar *dptr = dst.ptr(i);
        for (int j = 0; j < cols; j++)
            double value = 0;
            for (int k = -sz; k <= sz; k++)
                // slightly faster results when we create a ptr due to more efficient memory access.
                uchar *sptr = src.ptr(i + sz + k);
                for (int l = -sz; l <= sz; l++)
                    value += kernel.ptr<double>(k + sz)[l + sz] * sptr[j + sz + l];
            dptr[j] = saturate_cast<uchar>(value);
6.2 并行执行
在顺序执行时，可以注意到每个像素依赖于多个相邻像素，但一次只编辑一个像素。因此，为了优化计算，可以利用现代处理器的多核架构将图像分割成条带并在每个条带上并行执行卷积。OpenCV cv::parallel_for_框架自动决定如何有效地拆分计算并为我们完成大部分工作。
尽管特定条带中的像素值可能取决于条带外的像素值，但这些只是只读操作，因此不会导致未定义的行为。
首先声明一个继承自cv::ParallelLoopBody的自定义类并覆盖
virtual void operator ()(const cv::Range& range) const.
class parallelConvolution : public ParallelLoopBody
private:
    Mat m_src, &m_dst;
    Mat m_kernel;
    int sz;
public:
    parallelConvolution(Mat src, Mat &dst, Mat kernel)
        : m_src(src), m_dst(dst), m_kernel(kernel)
        sz = kernel.rows / 2;
    virtual void operator()(const Range &range) const CV_OVERRIDE
        for (int r = range.start; r < range.end; r++)
            int i = r / m_src.cols, j = r % m_src.cols;
            double value = 0;
            for (int k = -sz; k <= sz; k++)
                uchar *sptr = m_src.ptr(i + sz + k);
                for (int l = -sz; l <= sz; l++)
                    value += m_kernel.ptr<double>(k + sz)[l + sz] * sptr[j + sz + l];
            m_dst.ptr(i)[j] = saturate_cast<uchar>(value);
operator ()函数中参数Range 表示将由单个线程处理的值的子集。根据需求，可能有不同的分割范围的方法，这反过来会改变计算。
例如，我们可以
遍历整个图像并分割，通过如下方式获取[row, col]坐标（如上代码所示）：
virtual void operator()(const Range &range) const CV_OVERRIDE
    for (int r = range.start; r < range.end; r++)
        int i = r / m_src.cols, j = r % m_src.cols;
        double value = 0;
        for (int k = -sz; k <= sz; k++)
            uchar *sptr = m_src.ptr(i + sz + k);
            for (int l = -sz; l <= sz; l++)
                value += m_kernel.ptr<double>(k + sz)[l + sz] * sptr[j + sz + l];
        m_dst.ptr(i)[j] = saturate_cast<uchar>(value);
然后，我们将按以下方式调用 parallel_for_ 函数：
 parallelConvolution obj(src, dst, kernel);
 parallel_for_(Range(0, rows * cols), obj);
拆分行并计算每一行：
virtual void operator()(const Range &range) const CV_OVERRIDE
    for (int i = range.start; i < range.end; i++)
        uchar *dptr = dst.ptr(i);
        for (int j = 0; j < cols; j++)
            double value = 0;
            for (int k = -sz; k <= sz; k++)
                uchar *sptr = src.ptr(i + sz + k);
                for (int l = -sz; l <= sz; l++)
                    value += kernel.ptr<double>(k + sz)[l + sz] * sptr[j + sz + l];
            dptr[j] = saturate_cast<uchar>(value);
在这种情况下，我们调用具有不同范围的 parallel_for_ 函数：
parallelConvolutionRowSplit obj(src, dst, kernel);
parallel_for_(Range(0, rows), obj);
在上边的例子中，两种实现的性能差不多。某些情况可能允许更好的内存访问模式或其他性能优势。
要设置线程数，可以使用：cv::setNumThreads。还可以使用cv::parallel_for_中的 nstripes 参数指定拆分次数。例如，如果您的处理器有 4 个线程，则设置cv::setNumThreads(2)或设置nstripes=2应与默认情况下相同，它将使用所有可用的处理器线程，但只会将工作负载拆分到两个线程上。
C++ 11 标准允许通过去掉parallelConvolution类并用 lambda 表达式替换它来简化并行实现：
parallel_for_ (Range(0, rows * cols), [&]( const Range &range)
 parallel_for_(Range(0, rows * cols), [&](const Range &range)
                        for (int r = range.start; r < range.end; r++)
                            int i = r / cols, j = r % cols;
                            double value = 0;
                            for (int k = -sz; k <= sz; k++)
                                uchar *sptr = src.ptr(i + sz + k);
                                for (int l = -sz; l <= sz; l++)
                                    value += kernel.ptr<double>(k + sz)[l + sz] * sptr[j + sz + l];
                            dst.ptr(i)[j] = saturate_cast<uchar>(value);
7. 结果
执行这两种实现所花费的时间
512x512 输入，5x5 内核：
 This program shows how to use the OpenCV parallel_for_ function and
compares the performance of the sequential and parallel implementations for a
convolution operation
Usage:
./a.out [image_path -- default lena.jpg]
Sequential Implementation: 0.0953564s
Parallel Implementation: 0.0246762s
Parallel Implementation(Row Split): 0.0248722s
512x512 输入，3x3 内核
 This program shows how to use the OpenCV parallel_for_ function and
 compares the performance of the sequential and parallel implementations for a
 convolution operation
 Usage:
 ./a.out [image_path -- default lena.jpg]
 Sequential Implementation: 0.0301325s
 Parallel Implementation: 0.0117053s
 Parallel Implementation(Row Split): 0.0117894s
并行实现的性能取决于 CPU 类型。例如，在 4 核 - 8 线程 CPU 上，运行时间可能比顺序实现快 6 到 7 倍。有很多因素可以解释为什么没有实现 8 倍的加速：
创建和管理线程的开销，
并行运行的后台进程，
4 个硬件内核（每个内核有 2 个逻辑线程）和 8 个硬件内核之间的区别。
在本文中，使用了一个水平梯度卷积核（如上面的动画所示），它产生了一个突出垂直边缘的图像。
结果图像