基于OpenCL的腐蝕膨脹算法的并行優(yōu)化

王文善, 張維忠, 李 強

(青島大學計算機科學技術(shù)學院, 山東 青島 266071)

傳統(tǒng)的腐蝕膨脹算法一般是在CPU運行的串行算法,算法中存在大量的相似運算和冗余運算,算法效率低,隨著圖像處理技術(shù)的不斷發(fā)展,圖像和結(jié)構(gòu)元素不斷增大,漸漸無法滿足形態(tài)學實時圖像處理的要求。當前研究的熱點是提高圖像處理算法的效率、準確性和通用性,許多學者對腐蝕膨脹算法進行了改進研究。基于SE去組合的快速無失速低復雜度體系結(jié)構(gòu)方法[1]對于結(jié)構(gòu)元素進行了優(yōu)化,降低了算法的計算復雜性,但其通用性較低。通過積累結(jié)構(gòu)元件內(nèi)每個像素的PPI指數(shù)來找到最純凈的像素[2],提高了算法的自動化程度和效果,然而算法的處理速度并沒有提高。二維結(jié)構(gòu)元素的1-D分解和點對分解[3]可提高計算速度,但僅針對凸集等緊1-D分解元效果較好,因此通用性不強。1-D 分解元的結(jié)構(gòu)元素構(gòu)造的點對分解算法[4-6],計算速度快但不適合于灰度圖;對于區(qū)域采用線段表示法的方法[7]算法的準確性有所提高,但這種算法適宜于連續(xù)施行腐蝕膨脹操作的情況;減少相鄰像素重復區(qū)域的計算量的方法[8],本質(zhì)上還是串行算法,速度提高有限;在 CUDA 平臺上進行改進和并行化實現(xiàn)是一種有效的并行算法[9-10],只針對單一平臺,通用性有限。本研究通過并行化和優(yōu)化算法,提高了腐蝕膨脹算法的計算效率,并具備較好的通用性。本文提出了基于OpenCL的腐蝕膨脹快速并行算法,通過利用像素無關(guān)性和圖形處理器的分層存儲機制[11],優(yōu)化存儲結(jié)構(gòu)和訪存方式,以及合理劃分工作組和工作項,提高算法的實現(xiàn)速度。同時,還提出了基于OpenCL改進的膨脹與腐蝕快速并行算法,通過存儲結(jié)果在共享內(nèi)存中,減少計算冗余,提高效率,顯著提高了腐蝕膨脹算法的效率。

1 圖像的腐蝕膨脹算法

1.1 腐蝕原理

腐蝕是求局部最小值,即計算結(jié)構(gòu)元素在圖像中所覆蓋區(qū)域的像素點最小值,并把最小值賦給當前結(jié)構(gòu)元素中心指定的像素[12]。設(shè)A是輸入圖像,B是結(jié)構(gòu)元素,則結(jié)構(gòu)元B平移z后的集合表示為

(B)z={c|c=b+z,b∈B}

用B對A進行灰度腐蝕表示為

A?B={z|(B)z?A}

即結(jié)構(gòu)元B平移z后依然包含在集合A中所有的z的集合,又表示為

A?B={z|(B)z∩Ac=?}

其中,Ac是集合A的補集,也就是不在集合A中的其他元素。

1.2 膨脹原理

則B對A膨脹表示為

2 腐蝕膨脹并行算法

2.1 腐蝕膨脹并行算法

由腐蝕膨脹算法原理可知,傳統(tǒng)串行算法通過雙重循環(huán)遍歷圖像中每個像素點,雙重循環(huán)遍歷結(jié)構(gòu)元素的每個子元素,使結(jié)構(gòu)元素中心與當前像素點重合,通過乘法計算出結(jié)構(gòu)元素覆蓋的所有像素點的值,從中取得最小值和最大值,即腐蝕的最終結(jié)果和膨脹的最終結(jié)果,遍歷整個圖像,把最終結(jié)果賦值給對應(yīng)像素點。串行腐蝕膨脹示意圖如圖1所示,若結(jié)構(gòu)元素為3×3矩陣,當前元素為30,將結(jié)構(gòu)元素的中心與當前元素重合,計算結(jié)構(gòu)元素覆蓋范圍的像素點與結(jié)構(gòu)元素的乘積,取最小值作為腐蝕值,最大值為膨脹值,繼續(xù)循環(huán)至下一個元素21,重復當前操作,直至遍歷完圖像中所有像素點。

圖1 串行腐蝕膨脹示意圖

將以上過程看作像素獨立,每個像素點只與當前結(jié)構(gòu)元素覆蓋范圍內(nèi)的像素點有關(guān),可同時對圖像中所有像素點進行計算,像素無關(guān)并行算法示意圖如圖2所示。第一階段為每個像素點劃分工作項,將結(jié)構(gòu)元素中心對應(yīng)各工作項代表的像素點,同時對每個工作項進行卷積計算;第二階段對每個工作項中計算出的所有像素點進行排序,每個工作項中最小值為當前工作項所對應(yīng)像素點腐蝕值,每個工作項中的最大值為當前工作項所對應(yīng)像素點膨脹的值,將計算結(jié)果保存至本地內(nèi)存。

圖2 像素無關(guān)并行算法示意圖

2.2 基于特定結(jié)構(gòu)元素的膨脹腐蝕并行算法

由圖1可以看出,當結(jié)構(gòu)元素中所包含的子元素相同時,相鄰2個像素點與結(jié)構(gòu)元素進行卷積計算時,存在計算冗余。例如,將3×3的全1結(jié)構(gòu)元素分別覆蓋30和21像素點,其元素[40,30,26,33,21,50]分別計算2次,若再覆蓋24像素點,則列[33,21,50]進行3次相同的計算,存在大量的計算冗余,即使采用像素無關(guān)并行算法,依然存在大量的冗余計算。因此,基于OpenCL進行改進,改進的腐蝕膨脹并行算法如圖3所示,具體改進如下:

圖3 改進的腐蝕膨脹并行算法

1) 假定結(jié)構(gòu)元素為3×3的全1矩陣,取結(jié)構(gòu)元素的某一列作為新的結(jié)構(gòu)元素,則新結(jié)構(gòu)元素為3×1矩陣,為每個像素點劃分工作項,將新的結(jié)構(gòu)元素中心與每個像素點重合。

2) 在每個工作項中同時對新的結(jié)構(gòu)元素進行卷積計算,不同的是每個像素點只是對舊結(jié)構(gòu)元素的一列進行卷積計算,將計算出來的每一列的最大值(膨脹)或最小值(腐蝕)保存在共享存儲器中。

3) 在共享內(nèi)存中,每一個工作項讀取一個結(jié)構(gòu)元素所覆蓋的所有列的最大值或最小值,對于3×3的結(jié)構(gòu)元素,工作項會讀取當前像素與前后像素的共享內(nèi)存的值,并計算出這些值的最大值(膨脹)或最小值(腐蝕),最終結(jié)果即為膨脹或腐蝕的結(jié)果。

該方法能夠確保結(jié)構(gòu)元素覆蓋的每一列只計算一次,與傳統(tǒng)的串行計算方法相比,理論上計算量減少了3倍,效率大大提高。雖然大幅度減少了計算冗余,但對結(jié)構(gòu)元素有限制,因此該方法更適用于在特定結(jié)構(gòu)元素中。

2.3 腐蝕膨脹并行優(yōu)化

基于OpenCL的腐蝕膨脹并行算法和改進的并行算法中,以一個線程計算源圖像中的一個像素點,在OpenCL中一個工作項即代表一個線程[13]。由于實驗使用平臺為嵌入式平臺的MaLi-T860 GPU,受最大工作項大小所限,分配每個工作組中的工作項大小為16×16,若源圖像分辨率為m×n,則分配工作組數(shù)目為(m/16)×(n/16)。

OpenCL內(nèi)存模型如圖4所示。OpenCL中將變量從主機端傳入設(shè)備端,把存放在CPU內(nèi)存中的變量傳遞到GPU的全局內(nèi)存[14],即GPU的顯存,把原始圖像數(shù)據(jù)保存在OpenCL的Image對象及相應(yīng)的采樣器Sampler,通過OpenCL提供的內(nèi)置函數(shù),更方便快速地處理圖像數(shù)據(jù)。算法是從全局內(nèi)存中讀取所需要的變量計算,將計算結(jié)果也保存其中。由于從顯存中直接讀寫數(shù)據(jù)速度較慢,因此對內(nèi)存分配進行優(yōu)化,將算法中常用的變量保存在本地內(nèi)存,常量保存在常量內(nèi)存,將算法計算結(jié)果保存在本地內(nèi)存,本地內(nèi)存是每個工作組獨有的內(nèi)存,可被當前工作組內(nèi)的所有工作項共享,起到共享內(nèi)存加速的作用。

圖4 OpenCL內(nèi)存模型

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

實驗平臺是AIO-3399C(AI)工業(yè)主板,軟件環(huán)境為Ubuntu18.04 LTS,硬件環(huán)境為雙Cortex-A72大核,四Cortex-A53小核處理器,ARM Mali-T860四核圖形處理器(GPU),內(nèi)存16G,開發(fā)環(huán)境為VSCode+OpenCL 1.2。

3.2 結(jié)果與分析

為了驗證各算法的速度,比較相同結(jié)構(gòu)元素、不同圖像大小的各算法的加速比。固定結(jié)構(gòu)元素為3×3,對比腐蝕膨脹并行算法、改進腐蝕膨脹并行算法、內(nèi)存優(yōu)化后腐蝕膨脹并行算法、內(nèi)存優(yōu)化后改進腐蝕膨脹并行算法在圖像大小分別為256×256、512×512、1 024×1 024、1 024×2 048、2 048×2 048、4 096×4 096的加速比。不同圖像大小的加速比如圖5所示。

圖5 不同圖像大小的加速比

由圖5中可以看出,在固定結(jié)構(gòu)元素大小的情況下,不同并行算法均比串行算法的速度快,隨著圖像變大,并行算法的加速比越高,其中在特定結(jié)構(gòu)元素下,改進的腐蝕膨脹并行算法加速比略高于一般的腐蝕膨脹并行算法,且與未經(jīng)優(yōu)化的并行算法相比,經(jīng)過內(nèi)存優(yōu)化后的并行算法加速比有較大的提高。

不同結(jié)構(gòu)元素大小的加速比如圖6所示。在固定圖像大小為1 024×1 024時,加速比隨著結(jié)構(gòu)元素大小的增大而增加,當結(jié)構(gòu)元素增加到13×13時,加速比最高可以達到94左右,即使一般情況,優(yōu)化過后加速比也能有88。

由圖5和圖6可以看出,并行算法的加速比與結(jié)構(gòu)元素大小和圖像大小有關(guān),且隨結(jié)構(gòu)元素大小的增大或圖像的增大而增大,所以對高分辨率的圖像和大結(jié)構(gòu)元素,腐蝕膨脹計算的加速更顯著。當矩陣大小較小時,系統(tǒng)啟動參與并行計算的工作項并不多,沒有充分利用GPU中的大量計算單元,且線程之間的切換較為頻繁,通信時間增加,因此加速效果并不顯著。當選取高分辨率圖像或大結(jié)構(gòu)元素時,由于每個線程計算量的增加,GPU中每個工作項都得到充分利用,線程之間的切換減少,而GPU最大的優(yōu)勢就是在于大批量的相同計算,因此加速比更大。

4 結(jié)束語

本文基于腐蝕膨脹算法的特性提出了一種基于OpenCL的并行算法,利用GPU的并行計算能力和內(nèi)存優(yōu)化,提高算法效率。通過合理劃分工作項和工作組,利用共享內(nèi)存存儲計算結(jié)果,并針對特定結(jié)構(gòu)元素的改進,提高算法的性能,在腐蝕膨脹算法中取得更高的效率和實時性,對于需要快速處理大量圖像數(shù)據(jù)的應(yīng)用場景具有實際價值。下一步主要在更深入的算法優(yōu)化和在其他硬件平臺上的應(yīng)用方面展開研究,提高算法性能,擴展其適用范圍。