超越halcon速度的二值圖像的腐蝕和膨脹，實(shí)現(xiàn)目前最快的半徑相關(guān)類算法(附核心源碼)。

發(fā)布時(shí)間：2019-03-20 12:32,

瀏覽次數(shù)：1259

, 標(biāo)簽：

halcon

我在兩年前的博客里曾經(jīng)寫(xiě)過(guò)?SSE圖像算法優(yōu)化系列七：基于SSE實(shí)現(xiàn)的極速的矩形核腐蝕和膨脹(最大值和最小值)算法

一文，通過(guò)SSE的優(yōu)化把矩形核心的腐蝕和膨脹做到了不僅和半徑無(wú)關(guān)，而且速度也相當(dāng)?shù)目?#xff0c;當(dāng)時(shí)在被博文的評(píng)論里有博友提出了如下的問(wèn)題：

#1樓 2018-02-21 20:26 | 胡一譚

博主的思路很巧妙，只是這個(gè)算法本身還是不夠快，優(yōu)化效果與商業(yè)軟件還是有比較大差距，4096X8192大小的的灰度圖商業(yè)軟件(halcon)只需要33ms，

本文需要250ms，考慮到商業(yè)軟件采用多核優(yōu)化，我測(cè)試機(jī)器是4核，

通常優(yōu)化加速比在3倍左右，因此，本文并行化后的理論耗時(shí)為250/3=83

.33ms。但我采用OpenMP對(duì)本文算法進(jìn)行優(yōu)化后達(dá)不到3倍的加速比。還是需要尋找更好的思路。

當(dāng)時(shí)看到這個(gè)評(píng)論后，真的覺(jué)得這博友是不是搞錯(cuò)了，這么大的圖像，怎么可能只要33ms就處理完了呢，就是最簡(jiǎn)單的一個(gè)圖像處理算法，反色(Invert)經(jīng)過(guò)極度優(yōu)化后也需要大概7/8毫秒的，所以我當(dāng)時(shí)內(nèi)心是不認(rèn)可這個(gè)速度的。

后續(xù)我也在考慮二值圖像的這個(gè)特殊性，曾經(jīng)有考慮過(guò)比如膨脹時(shí)，遇到有個(gè)是白色的像素則停止循環(huán)，也考慮過(guò)使用直方圖的方式進(jìn)行優(yōu)化，畢竟直方圖也只有兩個(gè)像素了，但是也還是達(dá)不到上述速度，有些甚至還更慢。所以后續(xù)一直也沒(méi)有什么進(jìn)步。

前幾日，網(wǎng)友LQC-Jack突然又再次提到了這個(gè)問(wèn)題，他認(rèn)為針對(duì)這個(gè)問(wèn)題確實(shí)有更快的方法，畢竟二值得特殊性擺在那里：

其中的“你box濾波的，sum>0當(dāng)前點(diǎn)就是255”

這個(gè)是關(guān)鍵，是啊，針對(duì)二值圖求局部矩形內(nèi)的最大值，和求二值圖像的局部均值如果我們能夠建立起聯(lián)系，那么就可以借助于快速的局部均值算法間接的實(shí)現(xiàn)腐蝕或膨脹，我在博客里有多篇文章提到了局部均值的終極優(yōu)化，特別是

SSE圖像算法優(yōu)化系列十三：超高速BoxBlur算法的實(shí)現(xiàn)和優(yōu)化(Opencv的速度的五倍)

一文中提到的方式，效率及其高，針對(duì)4096X8192的二值圖也就是30ms左右能搞定。希望燃起。

那如何將兩者搭橋呢，仔細(xì)想想確實(shí)很簡(jiǎn)單，如果是求最大值(膨脹)，那么只要局部有一個(gè)像素為255，結(jié)果就為255，此時(shí)的局部均值必然大于0

(考慮實(shí)際因素，應(yīng)該是局部累加值，因?yàn)榭紤]最后的整除，不排除某個(gè)局部區(qū)域，只有一個(gè)白點(diǎn)，當(dāng)局部過(guò)大時(shí)，整除后的結(jié)果可能也為0)，而只有所有局部?jī)?nèi)的像素都為0是，最大值才為0，這個(gè)時(shí)候

的局部累加值也必然為0。如果是求最,小值(腐蝕)，只要局部有一個(gè)像素為0值，結(jié)果就為0，只有局部所有像素都為255，結(jié)果才為255，那么這里的信息反饋到局部均值就等同于說(shuō)平均值為255，則結(jié)果為255，否則結(jié)果就為0(同樣的道理，這里實(shí)際編程時(shí)要用局部累加值，而不是平均值)。

如此一來(lái)，我們會(huì)發(fā)現(xiàn)，這種實(shí)現(xiàn)過(guò)程相比標(biāo)準(zhǔn)的方框模糊來(lái)說(shuō)還少了一些步驟，我們先貼下我SSE優(yōu)化方框模糊的核心部分：

1 int BlockSize = 4, Block = (Width - 1) / BlockSize; 2 __m128i OldSum =

_mm_set1_epi32(LastSum); 3 __m128 Inv128 = _mm_set1_ps(Inv); 4 for (int X = 1;

X < Block * BlockSize +1; X += BlockSize) 5 { 6 __m128i ColValueOut =

_mm_loadu_si128((__m128i *)(ColValue + X -1)); 7 __m128i ColValueIn =

_mm_loadu_si128((__m128i *)(ColValue + X + Radius + Radius)); 8 __m128i

ColValueDiff = _mm_sub_epi32(ColValueIn, ColValueOut);// P3 P2 P1 P0 9 __m128i

Value_Temp = _mm_add_epi32(ColValueDiff, _mm_slli_si128(ColValueDiff,4)); //

P3+P2 P2+P1 P1+P0 P0 10 __m128i Value = _mm_add_epi32(Value_Temp,

_mm_slli_si128(Value_Temp,8)); // P3+P2+P1+P0 P2+P1+P0 P1+P0 P0 11 __m128i

NewSum = _mm_add_epi32(OldSum, Value); 12 OldSum = _mm_shuffle_epi32(NewSum,

_MM_SHUFFLE(3, 3, 3, 3)); // 重新賦值為最新值 13 __m128 Mean =

_mm_mul_ps(_mm_cvtepi32_ps(NewSum), Inv128);14

_mm_storesi128_4char(_mm_cvtps_epi32(Mean), LinePD + X); 15 }

注意第14及第15行為求均值并最終保存數(shù)據(jù)到內(nèi)存中的過(guò)程，其中的NewSum中保存即為累加的值，注意這里因?yàn)橛谐?#xff0c;所以借用了浮點(diǎn)版本的相關(guān)指令，同時(shí)增加了相關(guān)的類型轉(zhuǎn)換過(guò)程。

這里，為了適應(yīng)我們的腐蝕和膨脹的需求，這兩句是不需要的，按照上述分析，比如膨脹效果，只需作如下改動(dòng)：

LinePD[X + 0] = NewSum.m128i_i32[0] > 0 ? 255 : 0; LinePD[X + 1] =

NewSum.m128i_i32[1] > 0 ? 255 : 0; LinePD[X + 2] = NewSum.m128i_i32[2] > 0 ? 255

:0; LinePD[X + 3] = NewSum.m128i_i32[3] > 0 ? 255 : 0;

以上代碼只是示意，如果真的這樣寫(xiě)，會(huì)破壞SSE算法的整體的和諧性，而且這種SSE中穿插普通C代碼會(huì)帶來(lái)性能上的極大損失，一種處理方法如下所示：

__m128i Flag = _mm_cmpgt_epi32(NewSum, _mm_setzero_si128()); Flag =

_mm_packs_epi32(Flag, Flag);*((int *)(LinePD + X)) =

_mm_cvtsi128_si32(_mm_packs_epi16(Flag, Flag));

我們利用SSE中比較運(yùn)算符的特殊性，產(chǎn)生諸如0XFFFFFFFF這樣的結(jié)果，然后在通過(guò)有關(guān)飽和運(yùn)算將他們減低到8位，注意上面使用的都是有符號(hào)的飽和計(jì)算。

對(duì)于腐蝕的過(guò)程，你知道怎么寫(xiě)嗎？

我們經(jīng)過(guò)簡(jiǎn)單測(cè)試，處理一副4096X8192大小的二值圖，任意的半徑大小，耗時(shí)基本穩(wěn)定在24ms左右，比boxblur也快了很多。

我也構(gòu)思過(guò)不實(shí)用累加和的方式判斷，比如使用或運(yùn)算或者與運(yùn)算，但是都是解決不了進(jìn)出像素的處理問(wèn)題，因此，整體看來(lái)是還是用累加最為科學(xué)。

其實(shí)對(duì)于半徑比較小時(shí)，還是有更為快速的方法的，這里稍微簡(jiǎn)單描述下，但是可能很多人看不懂。

在我們上述的實(shí)現(xiàn)中，我們用的是int類型的數(shù)據(jù)來(lái)保存累加值，這是因?yàn)榘霃缴晕⒋笠稽c(diǎn)累加值就可能超過(guò)short類型所能表達(dá)的范圍，但是int類型SSE一次只能處理4個(gè)，而short類型數(shù)據(jù)SSE一次能處理8個(gè)，因此，如果做適當(dāng)?shù)淖儎?dòng)是否有可能使用short類型呢，是用可能的。

因?yàn)槭嵌祱D，所以就只有0和255兩個(gè)值，0值無(wú)所謂，那如果我們把255這個(gè)值修改成1，那么在半徑不大于某個(gè)數(shù)值(64還是其他數(shù)，可以自己畫(huà)一畫(huà))時(shí)，累加值將可控在short類型所能表達(dá)的范圍。

這是還有個(gè)問(wèn)題就是，255這個(gè)值如何變?yōu)?，如果使用_mm_blendv_epi8集合有關(guān)判斷語(yǔ)句是可以實(shí)現(xiàn)的，但是這個(gè)Blend是比較耗時(shí)的，反而得不償失。一個(gè)最好的辦法就是充分利用無(wú)符號(hào)和有符號(hào)數(shù)之間的特點(diǎn)，當(dāng)我們把一個(gè)等于255的unsigned

char數(shù)據(jù)類型強(qiáng)制轉(zhuǎn)換為signed char時(shí)，他的值就等于-1，和我們要的值1相反，

這個(gè)時(shí)候我們?cè)敬a里的_mm_add_epi8接可以使用_mm_sub_epi8代替，反之亦然。而在SSE里，這種類型轉(zhuǎn)換還不需要強(qiáng)制進(jìn)行，因?yàn)樗苯硬僮鲀?nèi)存。

我們貼下下面的代碼可能有人就能明白是什么意思了。

memset(ColValue + Radius, 0, Width * sizeof(unsigned char)); for (int Z =

-Radius; Z <= Radius; Z++) { unsigned char *LinePS = Src + ColOffset[Z +

Radius] * Stride; int BlockSize = 16, Block = Width / BlockSize; for (int X = 0

; X < Block * BlockSize; X += BlockSize) { unsigned char *DestP = ColValue + X +

Radius; __m128i Sample= _mm_loadu_si128((__m128i *)(LinePS + X)); // 255成為-1

_mm_storeu_si128((__m128i *)DestP, _mm_sub_epi8(_mm_loadu_si128((__m128i *

)DestP), Sample)); }for (int X = Block * BlockSize; X < Width; X++) { ColValue[X

+ Radius] += (LinePS[X] ==255 ? 1 : 0); // 更新列數(shù)據(jù) } }

普通的C代碼部分及時(shí)直接實(shí)現(xiàn)，而SSE部分，并沒(méi)有看到明顯的255到1之間的轉(zhuǎn)換，一起都在那幾句簡(jiǎn)簡(jiǎn)單單的代碼中。

通過(guò)這種相關(guān)的優(yōu)化，大概4096X8192的圖能做到12到13毫秒之間，已經(jīng)完全超過(guò)了Halcon的速度。

halcon中的腐蝕和膨脹也有圓形半徑的，同樣的半徑下圓形半徑在halcon中的耗時(shí)大概是矩形半徑的8倍左右，我相信halcon的圓形半徑的算法也是通過(guò)EDM算法來(lái)實(shí)現(xiàn)的，詳見(jiàn)

SSE圖像算法優(yōu)化系列二十五:二值圖像的Euclidean distance map(EDM)特征圖計(jì)算及其優(yōu)化

一文， 而我這里也差不都是這樣的時(shí)間比例。

源代碼下載：https://files.cnblogs.com/files/Imageshop/FastBlur.rar

極度優(yōu)化版本工程：https://files.cnblogs.com/files/Imageshop/SSE_Optimization_Demo.rar

，見(jiàn)Binary->Processing->Erode/Dilate菜單。

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的halcon区域腐蚀膨胀算子_超越halcon速度的二值图像的腐蚀和膨胀，实现目前最快的半径相关类算法（附核心源码）。...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。