王文善, 張維忠, 李 強(qiáng)

(青島大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 山東 青島 266071)

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

1 圖像的腐蝕膨脹算法

1.1 腐蝕原理

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

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

用B對(duì)A進(jìn)行灰度腐蝕表示為

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

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

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

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

1.2 膨脹原理

則B對(duì)A膨脹表示為

2 腐蝕膨脹并行算法

2.1 腐蝕膨脹并行算法

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

圖1 串行腐蝕膨脹示意圖

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

圖2 像素?zé)o關(guān)并行算法示意圖

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

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

圖3 改進(jìn)的腐蝕膨脹并行算法

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)平臺(tái)是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é)果與分析

為了驗(yàn)證各算法的速度,比較相同結(jié)構(gòu)元素、不同圖像大小的各算法的加速比。固定結(jié)構(gòu)元素為3×3,對(duì)比腐蝕膨脹并行算法、改進(jìn)腐蝕膨脹并行算法、內(nèi)存優(yōu)化后腐蝕膨脹并行算法、內(nèi)存優(yōu)化后改進(jìn)腐蝕膨脹并行算法在圖像大小分別為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ìn)的腐蝕膨脹并行算法加速比略高于一般的腐蝕膨脹并行算法,且與未經(jīng)優(yōu)化的并行算法相比,經(jīng)過內(nèi)存優(yōu)化后的并行算法加速比有較大的提高。

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

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

4 結(jié)束語

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