基于OpenCL的腐蝕膨脹算法的并行優化

王文善, 張維忠, 李 強

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

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

1 圖像的腐蝕膨脹算法

1.1 腐蝕原理

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

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

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

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

即結構元B平移z后依然包含在集合A中所有的z的集合,又表示為

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

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

1.2 膨脹原理

則B對A膨脹表示為

2 腐蝕膨脹并行算法

2.1 腐蝕膨脹并行算法

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

圖1 串行腐蝕膨脹示意圖

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

圖2 像素無關并行算法示意圖

2.2 基于特定結構元素的膨脹腐蝕并行算法

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

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

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

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

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

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

2.3 腐蝕膨脹并行優化

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

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

圖4 OpenCL內存模型

3 實驗結果與分析

3.1 實驗環境

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

3.2 結果與分析

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

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

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

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

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

4 結束語

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