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

程　楷，程　勇

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

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

程楷1，程勇2

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

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

關鍵詞:分解；并行；膨脹；腐蝕

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

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

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

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

2膨脹與腐蝕

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

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

(1)

該公式可以等價表示為

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

(2)

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

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

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

(3)

該公式可以等價表示為

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

(4)

式中：Ac是A的補集；Ф是空集。

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

結(jié)論1，由定義可知膨脹和腐蝕關于集合求補運算和反射運算是對偶的，即

(A?B)c=Ac⊕B^

(5)

(A⊕B)c=Ac?B^

(6)

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

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

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

3.1.1算法原理

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

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

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

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

圖24連通膨脹算法流程

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

圖38連通膨脹算法流程

3.1.2算法流程

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

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

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

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

圖6　4連通膨脹快速算法

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

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

圖7　8連通膨脹快速算法

3.3性能比較

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

表1　性能比較

4結(jié)論

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

參考文獻：

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

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

[3]陸宗琪，朱煜.數(shù)學形態(tài)學腐蝕膨脹運算的快速算法[C]//第十三屆全國圖象圖形學學術會議. 北京：清華大學出版社，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

中圖分類號:TN911.73

文獻標志碼:A

DOI：10.16280/j.videoe.2016.03.006

基金項目：江蘇省自然科學基金項目(BK20131342)

作者簡介：

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

責任編輯：時雯

收稿日期：2015-11-13

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

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