如何使用 OpenCV parallel_for_ 函数并行化你的代码（Mandelbrot 集示例）

注：关于将 parallel_for_ 应用于图像卷积的用法，请参见本教程。

目标

本教程的目标是向你展示如何使用 OpenCV 的 parallel_for_ 框架来轻松地并行化你的代码。为了说明这个概念，我们将编写一个程序来绘制 Mandelbrot 集（曼德博集），充分利用几乎所有可用的 CPU 负载。完整的教程代码在此处。如果你想了解更多关于多线程的信息，你需要参考相关参考书或课程，因为本教程旨在保持简单。

前置条件

第一个前置条件是 OpenCV 在构建时启用了某个并行框架。在 OpenCV 4 中，以下并行框架按此顺序可用：

Intel Threading Building Blocks（第三方库，需要显式启用）
OpenMP（集成到编译器中，需要显式启用）
APPLE GCD（系统级，自动使用（仅限 APPLE））
Windows RT concurrency（系统级，自动使用（仅限 Windows RT））
Windows concurrency（运行时的一部分，自动使用（仅限 Windows - MSVC++ >= 10））
Pthreads（如果可用）

如你所见，OpenCV 库中可以使用多种并行框架。一些并行库是第三方库，必须在 CMake 中显式构建并启用（例如 TBB），另一些则随平台自动可用（例如 APPLE GCD），但你应该能够直接或通过在 CMake 中启用选项并重新构建库来访问某个并行框架。

第二个（弱）前置条件更多地与你想要完成的任务相关，因为并非所有计算都适合/可以被改造成以并行方式运行。为简单起见，可以被拆分为多个无内存依赖（无可能的竞态条件）的基本运算的任务很容易并行化。计算机视觉处理通常很容易并行化，因为在大多数情况下一个像素的处理不依赖于其他像素的状态。

简单示例：绘制 Mandelbrot 集

我们将以绘制 Mandelbrot 集为例，展示如何从常规的顺序代码轻松地改造代码以并行化计算。

理论

Mandelbrot 集的定义以数学家 Benoit Mandelbrot 的名字命名，由数学家 Adrien Douady 提出。它在数学领域之外也很出名，因为其图像表示是分形（fractal）的一个例子——分形是一种在每种尺度上都展现出重复模式的数学集合（更进一步，Mandelbrot 集是自相似的，因为整个形状可以在不同尺度上反复看到）。如需更深入的介绍，你可以查看相应的维基百科条目。这里，我们只介绍绘制 Mandelbrot 集的公式（来自上述维基百科条目）。

Mandelbrot 集是复平面中那些 $c$ 值的集合，对于这些值，0 在二次映射的迭代下 $\begin{cases} z_0 = 0 \\ z_{n+1} = z_n^2 + c \end{cases}$ 的轨道保持有界。也就是说，一个复数 $c$ 属于 Mandelbrot 集，如果从 $z_0 = 0$ 开始并反复应用该迭代，无论 $n$ 变得多大， $z_n$ 的绝对值都保持有界。这也可以表示为 $\limsup_{n\to\infty}|z_{n+1}|\leqslant2$

伪代码

一种生成 Mandelbrot 集表示的简单算法被称为”逃逸时间算法”（escape time algorithm）。对于渲染图像中的每个像素，我们使用递推关系测试在最大迭代次数下该复数是否有界。不属于 Mandelbrot 集的像素会很快逃逸，而我们假设在固定的最大迭代次数之后该像素属于该集合。较高的迭代次数会产生更详细的图像，但计算时间也会相应增加。我们用”逃逸”所需的迭代次数来描绘图像中的像素值。

For each pixel (Px, Py) on the screen, do:
{
  x0 = scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2, 1))
  y0 = scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-1, 1))
  x = 0.0
  y = 0.0
  iteration = 0
  max_iteration = 1000
  while (x*x + y*y < 2*2  AND  iteration < max_iteration) {
    xtemp = x*x - y*y + x0
    y = 2*x*y + y0
    x = xtemp
    iteration = iteration + 1
  }
  color = palette[iteration]
  plot(Px, Py, color)
}

how_to_use_OpenCV_parallel_for_640px-Mandelset_hires.png

为了将伪代码与理论联系起来，我们有：

$z = x + iy$
$z^2 = x^2 + i2xy - y^2$
$c = x_0 + iy_0$

在这张图中，我们回顾一下：复数的实部在 x 轴上，虚部在 y 轴上。你可以看到，如果我们在特定位置放大，整个形状可以反复可见。

实现

逃逸时间算法实现

（逃逸时间算法的代码实现见源代码。）

这里，我们使用 std::complex 模板类来表示复数。该函数执行测试以检查像素是否在集合中，并返回”逃逸”时的迭代次数。

顺序 Mandelbrot 实现

（顺序实现的代码实现见源代码。）

在此实现中，我们顺序地遍历渲染图像中的像素，执行测试以检查该像素是否可能属于 Mandelbrot 集。

另一件要做的事是将像素坐标转换为 Mandelbrot 集空间：

（坐标变换的代码实现见源代码。）

最后，为了给像素赋予灰度值，我们使用以下规则：

如果一个像素达到最大迭代次数（假定该像素属于 Mandelbrot 集），则该像素为黑色；
否则，我们根据逃逸迭代赋予一个灰度值，并缩放以适应灰度范围。

（灰度值赋值的代码实现见源代码。）

仅使用线性尺度变换不足以感知灰度变化。为了克服这一点，我们将通过使用平方根尺度变换来增强感知（借鉴自 Jeremy D. Frens 的博客文章）：

$f \left( x \right) = \sqrt{\frac{x}{\text{maxIter}}} \times 255$

绿色曲线对应简单的线性尺度变换，蓝色曲线对应平方根尺度变换，你可以观察到在观察这些位置的斜率时，最低值会如何被增强。

并行 Mandelbrot 实现

观察顺序实现时，我们可以注意到每个像素都是独立计算的。为了优化计算，我们可以利用现代处理器的多核架构并行执行多个像素计算。为了轻松实现这一点，我们将使用 OpenCV 的 cv::parallel_for_ 框架。

（并行实现的代码实现见源代码。）

第一件事是声明一个继承自 cv::ParallelLoopBody 的自定义类，并重写 virtual void operator ()(const cv::Range& range) const。

operator () 中的 range 表示将由单个线程处理的像素子集。这种拆分是自动完成的，以均匀分配计算负载。我们必须将像素索引坐标转换为二维的 [row, col] 坐标。还要注意，我们必须保持对 mat 图像的引用，以便能够就地修改图像。

并行执行通过以下方式调用：

（并行执行调用的代码实现见源代码。）

这里，range 表示要执行的操作总数，即图像中的像素总数。要设置线程数，你可以使用 cv::setNumThreads。你还可以使用 cv::parallel_for_ 中的 nstripes 参数来指定拆分数量。例如，如果你的处理器有 4 个线程，设置 cv::setNumThreads(2) 或设置 nstripes=2 应该是相同的，因为默认情况下它将使用所有可用的处理器线程，但只将工作负载拆分到两个线程上。

注： C++ 11 标准允许简化并行实现，方法是去掉 ParallelMandelbrot 类并用 lambda 表达式替换它：

（C++11 lambda 并行调用的代码实现见源代码。）

结果

你可以在此处找到完整的教程代码。并行实现的性能取决于你的 CPU 类型。例如，在 4 核 / 8 线程的 CPU 上，你可以预期约 6.9 倍的加速。有许多因素可以解释为什么我们没有实现接近 8 倍的加速。主要原因应该是：

创建和管理线程的开销；
并行运行的后台进程；
4 个物理核心每个核心 2 个逻辑线程与 8 个物理核心之间的差异。

教程代码生成的图像（你可以修改代码以使用更多迭代，并根据逃逸迭代赋予像素颜色，使用调色板以获得更具美感的图像）：