基于結(jié)構(gòu)元素分解的二值形態(tài)學(xué)并行快速算法

程　楷，程　勇

(1.上海交通大學(xué)　圖像通信與信息處理研究所，上?！?00240；2.南京工程學(xué)院　通信工程學(xué)院，江蘇　南京　211167)

基于結(jié)構(gòu)元素分解的二值形態(tài)學(xué)并行快速算法

程楷1，程勇2

(1.上海交通大學(xué)圖像通信與信息處理研究所，上海200240；2.南京工程學(xué)院通信工程學(xué)院，江蘇南京211167)

摘要:提出結(jié)構(gòu)元素為4連通或8連通區(qū)域時(shí)數(shù)學(xué)形態(tài)學(xué)膨脹腐蝕的快速算法。首先將二維結(jié)構(gòu)元素分解成不同方向的一維結(jié)構(gòu)元素；然后，通過分步移位位操作實(shí)現(xiàn)二維形態(tài)學(xué)膨脹、腐蝕算法；最后利用二值圖像的特點(diǎn)，將連續(xù)的若干個(gè)像素點(diǎn)視為一個(gè)整體并行操作，從而實(shí)現(xiàn)算法性能提升，相比于其他算法具有速度快、易操作等優(yōu)點(diǎn)。

關(guān)鍵詞:分解；并行；膨脹；腐蝕

1數(shù)學(xué)形態(tài)學(xué)處理

數(shù)學(xué)形態(tài)學(xué)用具有一定形態(tài)的結(jié)構(gòu)元素去量度和提取圖像中的對(duì)應(yīng)形狀，從而實(shí)現(xiàn)對(duì)圖像的分析和識(shí)別。數(shù)學(xué)形態(tài)學(xué)處理在邊緣檢測(cè)、特征提取、圖像分割、細(xì)節(jié)去除、孔洞填充等圖像處理以及計(jì)算機(jī)視覺領(lǐng)域有著非常廣泛的應(yīng)用[1]。

形態(tài)學(xué)處理一般算法是將一個(gè)結(jié)構(gòu)元素在二值圖像上逐點(diǎn)移動(dòng)，對(duì)每個(gè)像素點(diǎn)進(jìn)行若干次邏輯判斷從而得到處理結(jié)果。為提高形態(tài)學(xué)處理的運(yùn)算效率，楊琨等提出利用結(jié)構(gòu)元素在運(yùn)算過程中存在的大量的重復(fù)運(yùn)算區(qū)域，通過在后一次運(yùn)算中使用前一次運(yùn)算的結(jié)果來縮短運(yùn)算時(shí)間的算法[2]。該算法具有理論基礎(chǔ)簡(jiǎn)單，實(shí)現(xiàn)方便的特點(diǎn)，但是對(duì)于比較小的結(jié)構(gòu)元素，性能提高不明顯。陸宗琪等提出采用線段編碼的方式，將當(dāng)前線段與其相鄰的上下線段之間進(jìn)行邏輯運(yùn)算，從而實(shí)現(xiàn)膨脹腐蝕運(yùn)算[3]。該算法由于需要對(duì)二值圖像進(jìn)行額外的線段編碼工作，導(dǎo)致對(duì)單個(gè)膨脹腐蝕操作效果的改善大打折扣，沒有較為廣泛的適用性。Cheng等通過檢測(cè)二值圖像的邊緣，對(duì)邊緣像素點(diǎn)進(jìn)行操作來實(shí)現(xiàn)膨脹腐蝕的快速運(yùn)算[4]，對(duì)于邊界比較復(fù)雜的情況，該算法的優(yōu)化效果不好。MatthewJ.Thurley等利用圖形處理器(GPU)的并行計(jì)算優(yōu)勢(shì)，采用CUDA這一NVIDIA推出的并行計(jì)算架構(gòu)進(jìn)行性能優(yōu)化[5]。該算法對(duì)于分辨率較高的圖像會(huì)有較高的性能提升，但是對(duì)硬件的要求較高，適用性不強(qiáng)。

本文將4連通或8連通結(jié)構(gòu)元素分解為不同方向上的一維結(jié)構(gòu)元素，利用分步的移位操作實(shí)現(xiàn)形態(tài)學(xué)腐蝕膨脹。同時(shí)利用二值圖像的特點(diǎn)，即其像素值為0或者1，采用分段的方式，將相鄰的若干個(gè)像素看成一個(gè)整體，通過并行操作實(shí)現(xiàn)算法性能提升。算法的速度可以提高4～6倍，具有易操作適用性廣泛的特點(diǎn)。

2膨脹與腐蝕

定義1，作為Z2中的集合A和B，B對(duì)A的膨脹定義為

A⊕B={Z|(B^Z∩A≠Φ)}

(1)

該公式可以等價(jià)表示為

A⊕B={Z|(B^Z∩A?A)}

(2)

式中：z表示結(jié)構(gòu)元素的位移；B^表示集合B的反射集合。由定義得出的膨脹算法為將給定的結(jié)構(gòu)元素在二值圖像上依次平移，若該結(jié)構(gòu)元素覆蓋的原二值圖像上有一個(gè)或多個(gè)點(diǎn)像素值為1，則將結(jié)構(gòu)元素中心點(diǎn)所在的二值圖像像素值賦為1，否則將該點(diǎn)像素值賦為0，當(dāng)結(jié)構(gòu)元素走完整幅圖像時(shí)，便可以得到膨脹結(jié)果。

定義2，作為Z2中的集合A和B， B對(duì)A的腐蝕定義為

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

(3)

該公式可以等價(jià)表示為

A?B={Z|(B)Z∩Ac=Φ}

(4)

式中：Ac是A的補(bǔ)集；Ф是空集。

同理，由定義得出的腐蝕算法為當(dāng)結(jié)構(gòu)元素覆蓋的二值圖像像素值全部為1時(shí)，將結(jié)構(gòu)元素中心點(diǎn)所在的二值圖像像素值賦為1，否則賦為0。由定義得出的形態(tài)學(xué)處理算法效率較為低下，原因在于需要遍歷整個(gè)圖像的每個(gè)像素值，對(duì)于每個(gè)像素值，仍需要進(jìn)行一系列的邏輯判斷才能得到運(yùn)算結(jié)果。當(dāng)結(jié)構(gòu)元素較為龐大或者二值圖像分辨率較高時(shí)，處理速度會(huì)變得尤其慢。此外，由于結(jié)構(gòu)元素在二值圖像上依次滑動(dòng)處理每個(gè)像素，因而會(huì)有大量重復(fù)的邏輯判斷，當(dāng)圖像前景區(qū)域比較大時(shí)，這些重復(fù)判斷會(huì)造成更加多的資源浪費(fèi)。

結(jié)論1，由定義可知膨脹和腐蝕關(guān)于集合求補(bǔ)運(yùn)算和反射運(yùn)算是對(duì)偶的，即

(A?B)c=Ac⊕B^

(5)

(A⊕B)c=Ac?B^

(6)

因此，可以利用相同的結(jié)構(gòu)元素，使用B膨脹圖像的背景(即膨脹Ac)，并將結(jié)果求補(bǔ)即可得到B對(duì)該圖像的腐蝕結(jié)果。

3基于分解的膨脹腐蝕快速算法

3.1基于分解的膨脹快速算法

3.1.1算法原理

對(duì)于一幅需要進(jìn)行形態(tài)學(xué)操作的二值圖像，不需要對(duì)每個(gè)像素進(jìn)行單獨(dú)處理，而是可以利用一個(gè)無符號(hào)整數(shù)(unsignedint)來表示連續(xù)的若干個(gè)像素值，這個(gè)無符號(hào)整數(shù)的每一位均代表原圖中的一個(gè)像素點(diǎn)的像素值。因此，一幅M×N的二值圖像可以按行表示為M個(gè)整數(shù)，其中每個(gè)整數(shù)都是一個(gè)N位的無符號(hào)整數(shù)。同理，也可以按列表示為N個(gè)整數(shù)，其中每個(gè)整數(shù)都是一個(gè)M位無符號(hào)整數(shù)。

本文將討論4連通和8連通的結(jié)構(gòu)元素，如圖1所示。

圖1結(jié)構(gòu)元素

對(duì)于4連通的結(jié)構(gòu)元素，可以將其分解為(1 1 1)和(1 1 1)’兩個(gè)方向上的一維結(jié)構(gòu)元素，其中(1 1 1)’表示矩陣(1 1 1)的轉(zhuǎn)置。(1 1 1)對(duì)原始圖像的膨脹結(jié)果可以表示為將圖像中每個(gè)像素值為1的點(diǎn)的左、右像素點(diǎn)均賦值為1，這一步也可以通過將按行構(gòu)造出的若干個(gè)整數(shù)向左按位平移一位，向右按位平移一位，將這3個(gè)整數(shù)按位取或得到。(1 1 1)’對(duì)原始圖像的膨脹結(jié)果可以表示為將圖像中每個(gè)像素值為1的點(diǎn)的下、上像素點(diǎn)均賦值為1，這一步也可以通過將按列構(gòu)造出的若干個(gè)整數(shù)向左按位平移一位，向右按位平移一位，將這3個(gè)整數(shù)按位取或得到。最后，將上述兩個(gè)步驟得到的兩個(gè)整數(shù)按位取或即可得到最終膨脹結(jié)果。4連通膨脹算法流程見圖2所示。

圖24連通膨脹算法流程

對(duì)于8連通的結(jié)構(gòu)元素，同樣可以將其分解為(1 1 1)和(1 1 1)’兩個(gè)方向上的一維結(jié)構(gòu)元素。(1 1 1)對(duì)原始圖像的膨脹結(jié)構(gòu)可以表示為將圖像中每個(gè)像素值為1的點(diǎn)的左、右像素點(diǎn)均賦值為1，這一步也可以通過將按行構(gòu)造出的若干個(gè)整數(shù)向左按位平移一位，向右按位平移一位，將這3個(gè)整數(shù)按位取或得到。(1 1 1)’對(duì)原始圖像的膨脹結(jié)構(gòu)可以表示為將圖像中每個(gè)像素值為1的點(diǎn)的下、上像素點(diǎn)均賦值為1，與4連通結(jié)構(gòu)元素不同的是，這一步需要將(1 1 1)對(duì)原始圖像膨脹的結(jié)果按列構(gòu)造出的若干個(gè)整數(shù)向左按位平移一位，向右按位平移一位，將這3個(gè)整數(shù)按位取或得到。8連通膨脹算法流程見圖3所示。

圖38連通膨脹算法流程

3.1.2算法流程

根據(jù)上述原理，可以通過對(duì)按行或者按列構(gòu)造的若干個(gè)整數(shù)進(jìn)行位操作來得到最終膨脹結(jié)果。將若干個(gè)相鄰像素點(diǎn)視為一個(gè)整體使用并行的操作方式可以提升算法的效率。

在本文中，對(duì)于一幅大小為M×N的二值圖像，將每一行連續(xù)的32個(gè)像素值作為一個(gè)整數(shù)，當(dāng)N/32不等于0時(shí)，即每行像素值個(gè)數(shù)不是32的整數(shù)倍時(shí)，在每行末尾補(bǔ)充32-N%32個(gè)值為0的像素，這樣便可以將原始的M×N的二值圖像分段成一幅M×?N%32」的新圖，該圖中每個(gè)“像素值”均為一個(gè)32位的無符號(hào)整數(shù)。構(gòu)造過程如圖4所示，圖5顯示了構(gòu)造之前的圖像和對(duì)應(yīng)分段圖。

圖4　分段圖構(gòu)造過程

同理，若將原始圖像矩陣轉(zhuǎn)置后進(jìn)行如上操作，可以得到圖像按列構(gòu)造出的分段圖。 構(gòu)造完二值圖像對(duì)應(yīng)的分段圖之后，形態(tài)學(xué)膨脹腐蝕便可以在分段圖上進(jìn)行操作。4連通和8連通的膨脹快速算法見圖6和圖7。在進(jìn)行移位操作時(shí)，需要考慮相鄰兩個(gè)整數(shù)的邊界位，即當(dāng)x的最后一位為1，而x右邊的整數(shù)y第一位為0時(shí)，若需要進(jìn)行右移移位，則需要將y的第一位置為1；同理，當(dāng)x的第一位為1，而x左邊的整數(shù)z最后一位為0時(shí)，若需要進(jìn)行左移移位，則需要將z的最后一位置為1。

圖6　4連通膨脹快速算法

3.2基于分解的腐蝕快速算法

根據(jù)結(jié)論1，可以知道形態(tài)學(xué)腐蝕和膨脹具有對(duì)偶性的特點(diǎn)，因此為得到4連通或者8連通結(jié)構(gòu)元素對(duì)一幅二值圖像的腐蝕結(jié)果，將二值圖像取反，然后進(jìn)行上述膨脹操作，最后將得到的結(jié)果再次取反即可。由于二值圖像取反操作也可以在分段圖上進(jìn)行，因此腐蝕快速算法的流程仍是建立在分段圖之上的。

圖7　8連通膨脹快速算法

3.3性能比較

在IntelCorei5-3470CPU@ 3.2GHz，4GbyteRAM，Windows8 32位操作系統(tǒng)的硬件環(huán)境下進(jìn)行實(shí)驗(yàn)。對(duì)不同分辨率以及不同紋理復(fù)雜度的二值圖像進(jìn)行了實(shí)驗(yàn)，采用的結(jié)構(gòu)元素為8連通結(jié)構(gòu)元素，進(jìn)行膨脹實(shí)驗(yàn)的原始圖像以及最后結(jié)果見圖8，性能比較見表1。由于運(yùn)行時(shí)間與計(jì)算機(jī)速度、負(fù)載有關(guān)，因此本文中的數(shù)據(jù)取的是平均值。由于本文的快速算法只是對(duì)32bit整數(shù)操作，并不關(guān)心整數(shù)的具體內(nèi)容，因此二值圖像的紋理復(fù)雜程度并不會(huì)對(duì)本算法的性能有較大影響。

表1　性能比較

4結(jié)論

本文提出了一種基于結(jié)構(gòu)元素分解的二值形態(tài)學(xué)并行快速算法。將結(jié)構(gòu)元素分解為不同方向的一維結(jié)構(gòu)元素，通過分步的移位操作實(shí)現(xiàn)形態(tài)學(xué)腐蝕膨脹。最后利用二值圖像的特性，構(gòu)造出32bit整數(shù)形成的分段圖，在該分段圖上進(jìn)行并行的位操作來實(shí)現(xiàn)算法的性能提升。該算法相比于傳統(tǒng)的形態(tài)學(xué)處理操作，在性能上有了大幅提升。二值圖像分辨率越大，本算法的性能提升越明顯。同時(shí)，由于本算法只是對(duì)整數(shù)操作，并不關(guān)心整數(shù)的具體內(nèi)容，因此，二值圖像本身的紋理復(fù)雜程度并不會(huì)影響本算法的性能，這也是對(duì)一些需要首先進(jìn)行邊界檢測(cè)的形態(tài)學(xué)處理方法的提升。

參考文獻(xiàn)：

[1]RAFAELC. 數(shù)字圖像處理[M].3版.北京：電子工業(yè)出版社，2013.

[2]楊琨，曾立波，王殿成.數(shù)學(xué)形態(tài)學(xué)腐蝕膨脹運(yùn)算的快速算法[J].計(jì)算機(jī)工程與應(yīng)用，2005(34)：54-56.

[3]陸宗琪，朱煜.數(shù)學(xué)形態(tài)學(xué)腐蝕膨脹運(yùn)算的快速算法[C]//第十三屆全國(guó)圖象圖形學(xué)學(xué)術(shù)會(huì)議. 北京：清華大學(xué)出版社，2006：15-20.

[4]CHENGXinyu.Fastbinarydilation/erosionalgorithmusingreferencepoints[C]//Proc.InternationalConferenceonNetworkingandDigitalSociety. [S.l.]：IEEEPress，2009：87-90.

[5]MATTHEWJ.Fastmorphologicalimageprocessingopen-sourceextensionsforGPUprocessingwithCUDA[J].IEEEjournalofselectedtopicsinsignalprocessing，2012(6)：849-855.

Fastparallelalgorithmofmorphologyoperationbasedonelementsubsection

CHENGKai1，CHENGYong2

(1. Institute of Image Communication & Network Engineering， Shanghai Jiaotong University， Shanghai 200240， China2.Institute of Communication Engineering， Nanjing Institute of Technology，Nanjing 211167， China)

Abstract:In this paper， a fast algorithm of mathematical morphology dilation and erosion operation with the structuring element of 4-connectivity and 8-connectivity is presented. Decomposing the structure element into two directions， dilation and erosion are obtained through bit manipulation. Besides， utilizing the characteristic of binary image， an integer is obtained connecting several image pixels， which helps improve the performance. The new algorithm is simpler to optimizing design， convenient to realize and has higher performance.

Key words:subsection； parallel； dilation； erosion

中圖分類號(hào):TN911.73

文獻(xiàn)標(biāo)志碼:A

DOI：10.16280/j.videoe.2016.03.006

基金項(xiàng)目：江蘇省自然科學(xué)基金項(xiàng)目(BK20131342)

作者簡(jiǎn)介：

程楷(1991— )，碩士生，主要研究數(shù)字圖像處理、計(jì)算機(jī)視覺。

責(zé)任編輯：時(shí)雯

收稿日期：2015-11-13

文獻(xiàn)引用格式：程楷，程勇.基于結(jié)構(gòu)元素分解的二值形態(tài)學(xué)并行快速算法[J].電視技術(shù),2016，40(3)：26-29.

CHENGK，CHENGY.Fastparallelalgorithmofmorphologyoperationbasedonelementsubsection[J].Videoengineering,2016,40(3)：26-29.