超越OpenCV速度的MorphologyEx函式實作（特別是對于二值圖，速度是CV的4倍左右）。-有解無憂

最近研究了一下opencv的 MorphologyEx這個函式的替代功能，他主要的特點是支持任意形狀的腐蝕膨脹，對于灰度圖，速度基本和CV的一致，但是 CV沒有針對二值圖做特殊處理，因此，這個函式對二值圖的速度和灰度是一樣的，但是這個函式，如果使用的話，估計大部分還是針對二值影像，因此，我對二值圖做了特別優化，速度可以做到是CV這個函式的4倍左右，

MorphologyEx的主要功能是對灰度圖進行相關形態學的處理，比如腐蝕、膨脹、開閉等計算，其代碼可以在github上找到：https://github.com/opencv/opencv/blob/master/modules/imgproc/src/morph.dispatch.cpp#L1160

　　opencv的這個代碼，1000多行，從頭看到尾，就沒有看到幾句和演算法本身有關的內容，仔細看下里面有下面的代碼：

他不是呼叫Opencl就是使用IPP庫，還是自己去想演算法的優化吧，

其實這個演算法的優化我在很多年前就一直在考慮，只是一直么有動手，主要是無思路，最近在研究模板匹配的時候，因為有需求，做了下帶蒙版功能的NCC匹配，對于這個類似的演算法也就有了想法，

在正常情況下，我們的核是矩形的或者是圓形的，對于矩形核，在SSE影像演算法優化系列七：基于SSE實作的極速的矩形核腐蝕和膨脹（最大值和最小值）演算法一文中已經提出了優化演算法，對于圓形半徑，在【短道速滑八】圓形半徑的影像最大值和最小值演算法的實作及其實時優化（非二值圖）一文也提出了解決方案，兩種方案都非常的高效和快速，

如果是任意形狀的核，考慮到其無固定的規律，上述常規的優化手段都無法完成，如何弄呢，

我對這個演算法想過很久，那么最近我得到的結論是肯定不能整體做優化，我想到的就是把蒙版區域按水平方向或者垂直方向分割成一條一潭訓者一列一列的小塊，每個小塊單獨執行類似的演算法，那么比如一個9*9的蒙版，如果其中的連續的小塊有20個，那最多也就是標準矩形演算法的20倍耗時（實際是不需要的，以為有很多公共計算），而矩形演算法的速度是非常非常高效的，

實踐了下，這個做法是有效的，而且也是相對來說高效的，但是后面想了下，為什么要分割成一條一條的呢，畢竟有很多條條的寬度或者高度是一樣的，可以把他們作為一個整體合并成一個Rectangle，對一個Rectanle進行處理，和標準的矩形核的演算法也不是一樣的嗎，

　　如下所示，如果按照列方向一次一個列，則有31個列，但是如果是將相同高的列合并，則只有19個，數量減少了近一半，

　　　　　　　　　　原圖　　　　　　　　　　　　　　　　　　　　列方向的分塊矩形　　　　　　　　　　　　　　　　行方向的分塊矩形

　　實踐表明，這種處理后，整體能有效的提高計算速度，

至于是選擇列方向的分塊矩形還是行方向的，則和演算法本身的優化有一定的關系，比如在本例中，由于SIMD的特性，我們在計算腐蝕或者膨脹的時候，利用的有關的G值和H值在垂直方向計算時可方便的使用SIMD指令進行比較，因此，選擇列方向的分塊則更為有利，

　　那么對于二值影像的腐蝕和膨脹，我們在超越halcon速度的二值影像的腐蝕和膨脹，實作目前最快的半徑相關類演算法（附核心原始碼）一文中有提高一種更為特別的優化手段，那么這個手段但讓也可以用到本例中來，而在Opencv中，MorphologyEx函式是沒有對這個做特殊處理的，

　　我們做下簡單的速度比較：

　　對一副 500萬像素的圖進行 31*31的橢圓蒙版進行處理，本例耗時約為95ms， CV耗時約為 250ms，

但是奇怪的是，如果在CV中把蒙版的尺寸設定為偶數，比如30*30，其執行速度會快很多，比如同樣上述圖，CV的耗時只有78毫秒了，和我這里速度差不多，目前還不知道這個問題是怎么引起的，

　　相關測驗代碼如下：

    IplConvKernel *kernel0 = cvCreateStructuringElementEx(31, 31, 15, 15, CV_SHAPE_ELLIPSE);

    for (int i = 0; i < 100; i++)
        cvMorphologyEx(Src, Dest, NULL, kernel0, CV_MOP_DILATE, 1);

    cvReleaseStructuringElement(&kernel0);

    QueryPerformanceCounter(&t2);
    printf("Use Time:%f\n", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart * 1000);

    IplConvKernel *kernel1 = cvCreateStructuringElementEx(30, 30, 15, 15, CV_SHAPE_ELLIPSE);
    QueryPerformanceCounter(&t1);

    for (int i = 0; i < 100; i++)
        cvMorphologyEx(Src, Dest, NULL, kernel1, CV_MOP_DILATE, 1);

    cvReleaseStructuringElement(&kernel1);
    QueryPerformanceCounter(&t2);
    printf("Use Time:%f\n", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart * 1000);

    IplConvKernel *kernel2 = cvCreateStructuringElementEx(15, 15, 7, 7, CV_SHAPE_ELLIPSE);
    QueryPerformanceCounter(&t1);

    for (int i = 0; i < 100; i++)
        cvMorphologyEx(Src, Dest, NULL, kernel2, CV_MOP_DILATE, 1);

    cvReleaseStructuringElement(&kernel2);
    QueryPerformanceCounter(&t2);
    printf("Use Time:%f\n", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart * 1000);

    IplConvKernel *kernel3 = cvCreateStructuringElementEx(14, 14, 7, 7, CV_SHAPE_ELLIPSE);
    QueryPerformanceCounter(&t1);

    for (int i = 0; i < 100; i++)
        cvMorphologyEx(Src, Dest, NULL, kernel3, CV_MOP_DILATE, 1);
    cvReleaseStructuringElement(&kernel3);

    QueryPerformanceCounter(&t2);
    printf("Use Time:%f\n", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart * 1000);

CV的耗時統計如下（100次回圈計算的耗時），

如果是同樣一份大小的二值影像，在本例只需22ms，CV的耗時則還是和上面的一樣，

這里也不得不說一句，Intel的IPP的優化功能真的也還是不錯，

使用halcon的也做了類似的測驗，halcon里對于規則的影像有一些特別的函式，比如 gray_dilation_rect， gray_dilation_shape，他的這些算子和我的標準優化的版本速度差不多，而對于其他的自定義形狀，則要使用read_gray_se讀取一個固定格式的檔案，當然對于我們上面使用的橢圓， halcon已經有個一個定義好的函式gen_disc_se，

對于橢圓，在Halcon中我用下述代碼測驗：

read_image (Image, 'd:/1.bmp')
gen_disc_se (SE, 'byte', 31, 31, 0)
for J := 0 to 100 - 1 by 1
    gray_dilation(Image, SE,  ImageDilation)
endfor

得到的速度結果非常嚇人，回圈100次也只要1600ms，那意味著每次只要16ms，比我這里要快5倍多，真是牛逼，然后看了下gray_dilation的說明檔案，在Parallelization一項里有這個說明：Automatically parallelized on internal data level.即在在內部資料級別自動并行，同時觀察上述代碼運行時的CPU運行情況，CPU的使用率高達80%左右，我個人分析他內部是做了多核并行的，這樣的話我還可以接受的，我的機器是4核單位，如果我的速度除以4，嗨嗨，

說到這，我正好也抽空研究了下read_gray_se這個函式，如果我要在Halcon里實作其他非規則形狀的腐蝕，只能通過這個函式，這個函式的需要從檔案里讀取一些列資料，而這個檔案我在百度搜索，基本沒看到有詳細的說明，Halcon幫助檔案里到時有說明，不過有點晦澀，我這里正好解釋下，也當做給自己做個筆記，不然時間長了，我自己也不記得了，

他對檔案(文本檔案）的要求如下：

　　第一行指明型別，可以是一下三個字符中的一種： 'byte', 'uint2' or 'real' 注意不要帶引號，對于影像資料，一般用byte

　　第二行，是指 structuring element 的尺寸，寬度 + 空格 +　高度

　　第三行，這個比較重要，他的意思我們可以這樣理解，就是按照單行方向考慮，你需要計算腐蝕和膨脹的連續區域的總數量，

接下來的每一行資料，都必然是3個數字，每個數字之間用空格隔開，第一個資料是指這個行所在的行號（以0為下標起點），第二個資料只區域的起點，第三個資料只區域的終點，

這些行的行數必須和第三行的數字對應，而且不能超過高度和寬度的范圍，

　　接下來的資料就是Halcon獨有的了，我的和CV的都不具有這個功能，他還能指定structuring element 每個位置對應的偏移量值，就在對應位置的元素值加上這個偏移量值作為計算腐蝕和膨脹的依據，可正可負，這個確實比較強大，但是測驗表明，如果有這些值，函式的計算速度可能會急劇下降，比如前面的測驗代碼中gen_disc_se (SE, 'byte', 31, 31, 0)，如果更改為gen_disc_se (SE, 'byte', 31, 31, 1),100次的速度會立即增加到8秒多，

比如前面對應的31*31的橢圓區域的SE就可以用下述字符描述：

不過，由這個結構，也可以窺探到，Halcon內部的Region結構可能用的是這種單行的RLE編碼，而不是基于Rectangle的，

上面的例子可能不是很好，因為他正好是一行只有一個結構，其實一行是可以是有多個，比如下面的資料:

本例相關測驗結果可參考： https://files.cnblogs.com/files/Imageshop/MaskFilter.rar?t=1652089081

如果想時刻關注本人的最新文章，也可關注公眾號：

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/472278.html

標籤：其他

上一篇：YAPI斷言功能無法使用，報錯assert.equal is not a function（已解決）

下一篇：技術分享 | web 控制元件的互動進階