目標

本教程的目的是向您展示如何使用OpenCV parallel_for_框架輕松并行化代碼。為了說明這個概念，我們將編寫一個程序來繪制一個利用幾乎所有可用CPU負載的Mandelbrot集合。完整的教程代碼在這里。如果您想要有關(guān)多線程的更多信息，則必須參考參考書或課程，因為本教程的目的是保持簡單。

前提

第一個先決條件是使用OpenCV構(gòu)建并行框架。在OpenCV 3.2中，以下并行框架按照以下順序提供：

1. 英特爾線程構(gòu)建塊（第三方庫，應(yīng)顯式啟用）
2. C =并行C / C ++編程語言擴展（第三方庫，應(yīng)明確啟用）
3. OpenMP（集成到編譯器，應(yīng)該被顯式啟用）
4. APPLE GCD（系統(tǒng)范圍廣，自動使用（僅限APPLE））
5. Windows RT并發(fā)（系統(tǒng)范圍，自動使用（僅Windows RT））
6. Windows并發(fā)（運行時的一部分，自動使用（僅限Windows） - MSVC ++> = 10））
7. Pthreads（如果有的話）

您可以看到，OpenCV庫中可以使用多個并行框架。一些并行庫是第三方庫，必須在CMake（例如TBB，C =）中進行顯式構(gòu)建和啟用，其他可以自動與平臺（例如APPLE GCD）一起使用，但是您應(yīng)該可以使用這些庫來訪問并行框架直接或通過啟用CMake中的選項并重建庫。

第二個（弱）前提條件與要實現(xiàn)的任務(wù)更相關(guān)，因為并不是所有的計算都是合適的/可以被平行地運行。為了保持簡單，可以分解成多個基本操作而沒有內(nèi)存依賴性（無可能的競爭條件）的任務(wù)很容易并行化。計算機視覺處理通常易于并行化，因為大多數(shù)時間一個像素的處理不依賴于其他像素的狀態(tài)。

簡單的例子：繪制一個Mandelbrot集

我們將使用繪制Mandelbrot集的示例來顯示如何從常規(guī)的順序代碼中輕松調(diào)整代碼來平滑計算。

理論

Mandelbrot定義被數(shù)學(xué)家Adrien Douady命名為數(shù)學(xué)家Benoit Mandelbrot。它在數(shù)學(xué)領(lǐng)域以外是著名的，因為圖像表示是一類分形的一個例子，一個表現(xiàn)出每個尺度顯示的重復(fù)圖案的數(shù)學(xué)集（甚至更多的是，Mandelbrot集是整體形狀可以是自相似的反復(fù)看不同規(guī)模）。對于更深入的介紹，您可以查看相應(yīng)的維基百科文章。在這里，我們將介紹公式來繪制Mandelbrot集（從維基百科的文章）。

Mandelbrot集是在二次映射迭代中的0的軌道的復(fù)平面中的的值的集合c

依然有限。也就是說，復(fù)數(shù)是Mandelbrot集的一部分，如果以z_0 = 0開始并重復(fù)應(yīng)用迭代，則z_n的絕對值保持有界，然而大n得到。這也可以表示為

Pseudocode

用于生成Mandelbrot集合的表示的簡單算法稱為“逃逸時間算法”。對于渲染圖像中的每個像素，如果復(fù)數(shù)在最大迭代次數(shù)下是有界的，則使用遞歸關(guān)系進行測試。不屬于Mandelbrot集的像素將迅速逃脫，而我們假設(shè)像素在固定的最大迭代次數(shù)后位于集合中。迭代次數(shù)很高會產(chǎn)生更為詳細的圖像，但計算時間會相應(yīng)增加。我們使用“轉(zhuǎn)義”所需的迭代次數(shù)來描繪圖像中的像素值。

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)
}

關(guān)于偽代碼和理論之間的關(guān)系，我們有：

在這個數(shù)字上，我們記得一個復(fù)數(shù)的實部是在x軸和y軸上的虛部。如果我們放大特定位置，您可以看到整個形狀可以反復(fù)顯示。

履行

逃脫時間算法實現(xiàn)

int mandelbrot(const complex<float> &z0, const int max)
{
    complex<float> z = z0;
    for (int t = 0; t < max; t++)
    {
        if (z.real()*z.real() + z.imag()*z.imag() > 4.0f) return t;
        z = z*z + z0;
    }
    return max;
}

在這里，我們使用std::complex模板類來表示一個復(fù)數(shù)。此函數(shù)執(zhí)行測試以檢查像素是否處于置位，并返回“轉(zhuǎn)義”迭代。

順序Mandelbrot實現(xiàn)

void sequentialMandelbrot(Mat &img, const float x1, const float y1, const float scaleX, const float scaleY)
{
    for (int i = 0; i < img.rows; i++)
    {
        for (int j = 0; j < img.cols; j++)
        {
            float x0 = j / scaleX + x1;
            float y0 = i / scaleY + y1;
            complex<float> z0(x0, y0);
            uchar value = (uchar) mandelbrotFormula(z0);
            img.ptr<uchar>(i)[j] = value;
        }
    }
}

在這個實現(xiàn)中，我們依次迭代渲染圖像中的像素，以執(zhí)行測試以檢查像素是否可能屬于Mandelbrot集。

另一個要做的就是將像素坐標轉(zhuǎn)換為Mandelbrot集空間：

    Mat mandelbrotImg(4800, 5400, CV_8U);
    float x1 = -2.1f, x2 = 0.6f;
    float y1 = -1.2f, y2 = 1.2f;
    float scaleX = mandelbrotImg.cols / (x2 - x1);
    float scaleY = mandelbrotImg.rows / (y2 - y1);

最后，要將灰度值分配給像素，我們使用以下規(guī)則：

• 如果達到最大迭代次數(shù)（像素假定為Mandelbrot集合），則像素為黑色，
• 否則我們根據(jù)轉(zhuǎn)義的迭代分配灰度值，并按比例縮放以適應(yīng)灰度范圍。

int mandelbrotFormula(const complex<float> &z0, const int maxIter=500) {
    int value = mandelbrot(z0, maxIter);
    if(maxIter - value == 0)
    {
        return 0;
    }
    return cvRound(sqrt(value / (float) maxIter) * 255);
}

使用線性尺度變換不足以感知灰度變化。為了克服這個問題，我們將通過使用平方根尺度轉(zhuǎn)換（從他的博客文章中借鑒于Jeremy D. Frens ）來提高感知：

綠色曲線對應(yīng)于簡單的線性尺度變換，藍色一到平方根尺度變換，您可以觀察到在這些位置觀察斜率時最低值將如何提升。

并行Mandelbrot實現(xiàn)

當看到順序?qū)崿F(xiàn)時，我們可以注意到每個像素是獨立計算的。為了優(yōu)化計算，我們可以通過利用現(xiàn)代處理器的多核架構(gòu)并行執(zhí)行多個像素計算。為了輕松實現(xiàn)，我們將使用OpenCV cv :: parallel_for_框架。

class ParallelMandelbrot : public ParallelLoopBody
{
public:
    ParallelMandelbrot (Mat &img, const float x1, const float y1, const float scaleX, const float scaleY)
        : m_img(img), m_x1(x1), m_y1(y1), m_scaleX(scaleX), m_scaleY(scaleY)
    {
    }
    virtual void operator ()(const Range& range) const
    {
        for (int r = range.start; r < range.end; r++)
        {
            int i = r / m_img.cols;
            int j = r % m_img.cols;
            float x0 = j / m_scaleX + m_x1;
            float y0 = i / m_scaleY + m_y1;
            complex<float> z0(x0, y0);
            uchar value = (uchar) mandelbrotFormula(z0);
            m_img.ptr<uchar>(i)[j] = value;
        }
    }
    ParallelMandelbrot& operator=(const ParallelMandelbrot &) {
        return *this;
    };
private:
    Mat &m_img;
    float m_x1;
    float m_y1;
    float m_scaleX;
    float m_scaleY;
};

首先是聲明一個繼承自cv :: ParallelLoopBody并覆蓋的自定義類virtual void operator ()(const cv::Range& range) const。

該范圍operator ()表示將由單獨線程處理的像素子集。這種分割是自動完成的，以平均分配計算負荷。我們必須將像素索引坐標轉(zhuǎn)換為2D [row, col]坐標。另請注意，我們必須保留對mat圖像的參考，以便能夠原地修改圖像。

并行執(zhí)行調(diào)用：

    ParallelMandelbrot parallelMandelbrot（mandelbrotImg，x1，y1，scaleX，scaleY）;
    parallel_for_（Range（0，mandelbrotImg.rows * mandelbrotImg.cols），parallelMandelbrot）;

這里，范圍表示要執(zhí)行的操作的總數(shù)，因此圖像中的像素總數(shù)。要設(shè)置線程數(shù)，可以使用：cv :: setNumThreads。您還可以使用cv :: parallel_for_中的nstripes參數(shù)指定拆分次數(shù)。例如，如果您的處理器有4個線程，則設(shè)置cv::setNumThreads(2)或設(shè)置nstripes=2應(yīng)與默認值相同，它將使用所有可用的處理器線程，但將僅在兩個線程上分割工作負載。

注意

C ++ 11標準允許通過擺脫ParallelMandelbrot類并用lambda表達式來替換它來簡化并行實現(xiàn)：

    parallel_for_(Range(0, mandelbrotImg.rows*mandelbrotImg.cols), [&](const Range& range){
        for (int r = range.start; r < range.end; r++)
        {
            int i = r / mandelbrotImg.cols;
            int j = r % mandelbrotImg.cols;
            float x0 = j / scaleX + x1;
            float y0 = i / scaleY + y1;
            complex<float> z0(x0, y0);
            uchar value = (uchar) mandelbrotFormula(z0);
            mandelbrotImg.ptr<uchar>(i)[j] = value;
        }
    });

結(jié)果

您可以在這里找到完整的教程代碼。并行實現(xiàn)的性能取決于您擁有的CPU類型。例如，在4個內(nèi)核/ 8個線程CPU上，您可以預(yù)期加速大約為6.9X。有很多因素可以解釋為什么我們不能達到將近8倍的加速。主要原因主要是由于：

• 創(chuàng)建和管理線程的開銷，
• 后臺進程并行運行，
• 4個硬核之間的差異，每個核心有2個邏輯線程，8個硬件核心。

由教程代碼生成的圖像（您可以修改代碼以使用更多迭代，并根據(jù)轉(zhuǎn)義的迭代分配像素顏色，并使用調(diào)色板獲得更多美學(xué)圖像）：

Mandelbrot設(shè)置為xMin = -2.1，xMax = 0.6，yMin = -1.2，yMax = 1.2，maxIterations = 500