一種并行二值圖像連通域標記算法?

甘曉英 白 陽 何曉棟 劉 斌

（1.西安鐵路職業(yè)技術學院電子信息學院 西安 710014）（2.陜西科技大學電子信息與人工智能學院 西安 710021）

1 引言

連通區(qū)域一般是指圖像中具有相同像素值且相鄰的前景像素點組成的圖像區(qū)域。如果像素點A與B鄰接，則A與B連通。所以，如果A與B連通，B與C連通，則A與C連通。相互連通的像素形成了一個區(qū)域，而不連通的像素形成了不同的區(qū)域。一個所有的像素相互連通像素構成的集合，成為一個連通區(qū)域。CCL（Connect Component Label?ing）是連通域標記［1］領域的一個常見問題，連通區(qū)域分析是一種在圖像分析處理的眾多應用領域中較為常用和基本的方法。傳統(tǒng)的單線程算法主要通過對標記矩陣進行線性掃描，后進行等價類劃分，而后通過一定規(guī)則合并等價類，最終實現(xiàn)連通域標記的過程。但單線程算法的計算能力極其有限，在處理像素較多的二值圖像時，效率相對較低。如果采用單線程的方法處理數(shù)量較多的、像素較多的圖像時，是十分浪費時間和精力的。

GPU為圖像處理器，又稱顯示核心、視覺處理器、顯示芯片，主要被用于計算機中的輔助圖形處理，是一種專門在工站、游戲機和一些移動設備上圖像運算工作的微處理器，是特意為處理較為復雜的數(shù)學幾何運算。而GPU本身也是一種多核設備，將一般的數(shù)學問題模擬為圖像計算問題通過GPU加速處理從而實現(xiàn)CPU并行計算的效果，目前GPU并行計算廣泛應用在區(qū)塊鏈貨幣挖礦、氣象預測等領域有著廣泛的應用［2～3］。本文旨在通過對CCL問題的可并行化進行研究，提出適合于GPU并行處理的標記算法［4］，實現(xiàn)并分析算法效率。

2 連通域標記算法目前研究現(xiàn)狀

輪 廓 跟 蹤 連 通 域 標 記 算 法［5］（Fu Chang，Chun-Jen Chen等設計實現(xiàn)）是根據(jù)由一次光柵掃描的標記和再次對連通區(qū)域進行掃描判斷一個連通域，此算法在運用中有優(yōu)良的線性特性和魯棒性。混合對象標記算法［6］（J.Martin-Herrero設計實現(xiàn)）根據(jù)光柵掃描以及隊列的優(yōu)缺點，將二者聯(lián)合使用，實驗效果比較滿意。高速組件標記算法［7］（T.Goto，MYoshida等設計實現(xiàn)）使用遍歷鄰接矩陣標的算法記出等價像素。兩階段連接組件標記算法［8］（K.Wu，K.Suzuki設計實現(xiàn)）是判斷每個等價像素點是否等價并對應一個點，彼此銜接變?yōu)榄h(huán)。時至當前，使用CPU單線程方式處理連通域標記算法的效率已經(jīng)達到一個瓶頸，在目前的基礎上再有所提高已經(jīng)不太可能，或提升的空間十分有限。但基于GPU多線程并行處理的方式已經(jīng)成為大大提升算法效率的可能，例如重慶大學的覃方濤［9］等通過使用GPU來提升標記算法的效率，但存在一定的缺點，并不是一個十分完整的算法，不能再某些測試樣本中使用，而且該算法的實現(xiàn)效率較低。北京科技大學徐正光［10］實現(xiàn)了小于一千像素圖像的的連通域標記算法，但時下這樣的算法越來越不能滿足圖像處理需求，適應性較差。此外還有很多學者［11～13］設計的算法，歸根結底屬于等價標記算法，并無太多創(chuàng)新點，運算速度也沒有太大的提升。

3 連通域標記

在數(shù)字圖像中，圖像的最小單位為像素，每一個像素四周都有八個完全不一樣的像素，像素的鄰接關系為上下左右四個像素為四鄰接關系，若包括對角線位置的四個像素，就為八鄰接關系，如圖1所示。

如圖1所示，是二值圖像連通域標記中的八連通域結構，八連通域是兼顧當前像素的左上、上、右上、左、右、左下、下、右下等八個方向［14］的連接狀況。八連通域則定義為

圖1 八連通域

圖2 光柵掃描

從圖像左上角的第一個像素開始向后掃一條水平線，然后快速地回到左邊偏下一點像素的位置，再掃描第二天水平線，照此固定的順序掃描下去，直到最后一條水平線，即完成整個圖像的掃描。

圖3 一次掃描的結果

如圖3所示，是經(jīng)過光柵掃描一次后的標記結果，可以發(fā)現(xiàn)因為光柵掃描的局限性（只能順序掃描）會導致在八連接體規(guī)則下原本相連的像素之間會有不同的標記，因此一次光柵掃描后還必須進行實際連接標記之間的合并，才能保證連接標記的正確性。

4 連通域標記的并行化

4.1 實際標記合并問題

二值圖像連通域快速標記算法是一種效率較高的單線程標記算法，在第二步的等價標記合并時采用集合合并方式有效提升了算法整體處理效率。

圖4 快速標記算法第一次標記結果

連通域快速標記算法標記結果如上圖4所示，從圖中可知標記像素“5”和“1”，“1”和“6”，“6”和“2”，“7”和“3”以及“8”和“4”等價，算法需要一個快速而有效方式處理等價合并。經(jīng)對比分析在基于CPU的二值圖像連通域標記算法中上述算法效率最高也是最具魯棒性的，對于各種類型的圖像進行的標記實驗中都表現(xiàn)為最優(yōu)。

4.2 基于CPU的算法的效率瓶頸

20世紀末期，GPU剛剛使用時，其浮點運算的能力和當時的CPU并沒有太大的差別，但以后的大約10年的時間里，CPU處理器的發(fā)展遇到了瓶頸，電路密度由于制造工藝而無法大幅優(yōu)化，時鐘頻率由于高功耗也無法進一步提升，多核由于其他方面的小號并未使運算效率線性提升。摩爾定律開始發(fā)揮不出應有的功效。由上述可知基于CPU的二值圖像連通域標記算法都是單線程運行，而且都需要進行兩次光柵掃描。基于CPU的單線程算法由于計算資源限制的原因效率提升空間有限。因此，提出了改變單線程順序處理的方式，采用硬件支持的多線程并行處理的方式來提升算法的效率［15］。

4.3 可并行化分析

4.3.1 標記溯源

針對某一個二值圖像，對所有像素按照像素的位置賦予一個初始標記值，而后對圖像中所有的像素點自左向右逐行掃描的順序進行掃描，并對每個像素根據(jù)八連接體規(guī)則進行反向推理，即每個像素將獲得一個該像素八連接體規(guī)則遞歸鄰域內(nèi)的一個最小標記，即可以被認為是該像素的實際標記，這個最小標記值即這個連通域內(nèi)部的標記值，即該區(qū)域的標記值，而這個值也是一個“頂點”，是遞歸區(qū)域內(nèi)的“頂點”。下面將著重說明連通域存在“頂點”以及如何有效的尋找一個“頂點”。

如圖5所示，在如圖所示的連通域中以及八連接體規(guī)則下，“31”像素按照溯源規(guī)則得到最小標記“22”，“22”像素得到源標記值“13”，最終“13像素”的最小標記為“2”。同理，“3”像素，“11”像素，“12”像素，“20”像素，“21”像素按照光柵掃描的反向順序最后的最小標記為“2”。

圖5 標記溯源

4.3.2 偽溯源

在實際的大多數(shù)二值圖像中，按照溯源規(guī)則尋找其連通域的最小標記，將會得到并不是正確的源標記值。如圖6所示，通過尋找頂點的遞歸方法，找到屬于每個像素的實際標記值，然而由于反向推理的標記方式也存在著不足，會存在偽遞歸的現(xiàn)象，稱為“偽溯源”，即“頂點”并非最終標記值，因此還要必須通過一定的方式解決這個問題。偽溯源的本質(zhì)是溯源的缺陷造成的，為解決這種缺陷就必須在溯源后再進行必要的處理解決這種偽溯源問題。

圖6 偽溯源

4.3.3 標記合并處理

如圖7所示，相鄰四個位置上的目標“NW”、“NE”、“SW”、“SE”，這四個位置上的元素總是具有相同的標記，這個原則在八連接體規(guī)則下二值圖像連通域標記問題中任何情況下都是成立的。

圖7 四像素標記一致

如圖8所示，以4像素為一整體，將圖像像素分為8個區(qū)域，分別標記為“1”、“2”、“3”、“4”、“5”、“6”、“7”、“8”，進行溯源標記，結果與單個像素溯源標記的結果一致。如圖所示，進行標記合并后本需要開啟32個并發(fā)線程的溯源過程，只需要開啟1/4數(shù)量的線程即可得出結果，減少并發(fā)量，提高溯源效率。

圖8 像素一致標記

5 并行算法設計與實現(xiàn)

為了減少并發(fā)線程數(shù)目，提出了標記合并處理，所以處理的圖像必須是4的整數(shù)倍像素，因此必須對圖像進行必要預處理，以背景像素（0）補充目標的行和列，確保圖像像素符合要求。

初始標記。如矩陣A表示，分割后的圖9，所有標記值用矩陣元素的形式表示，以4像素為整體，對每個分塊依次給予初始標記1，2，…25。

溯源標記。如矩陣B所示，經(jīng)過溯源標記后得出的結果為矩陣C，其中存在偽溯源的標記情況，因此還需對此結果進行處理，確保標記正確。

圖9 圖像預處理

如圖10所示，對于偽溯源的情況，在經(jīng)過一次反向推理的“頂點”標記后，進行循環(huán)掃描，即相鄰鄰域內(nèi)的標記值是否相等一致，如若不相等一致用較小值覆蓋較大值，以此類推直到標記值完全正確。經(jīng)過實驗分析，這種比對至少需要10次，最大需要64次，可能的次數(shù)為像素寬*高/16并向上取整的次數(shù)。經(jīng)過實驗表明分析，和多次測試結果說明，通過循環(huán)查找后最終得到了正確的圖像標記值。

圖10 整體處理過程

6 結論

二值圖像連通域標記實質(zhì)上是對圖像的像素矩陣進行處理的，得到的標記像素矩陣，且任何算法對二值圖像的標記都是一樣的。按照軟件測試中邊界覆蓋的要求，本文通過對“螺旋型”，“分叉型”等極端圖像以及正常類型的二值圖像矩陣進行連通域標記，并將標記結果與Lifeng He等發(fā)表的在Pattern Recognition雜志上Fast connected-com?ponent labeling文章中所使用的程序的標記結果進行對比，經(jīng)過對比發(fā)現(xiàn)結果完全一致，并通過多種類型的疊加測試，結果均與該算法的標記結果一致，確保了本文所設計的算法的有效性。如下圖所示，是具體標記結果的情況。

圖11 原始二值圖像矩陣

圖12 標記結果矩陣

如圖11和12所示，圖11是標記前的二值圖像矩陣，圖12是標記后的標記值矩陣，根據(jù)二值圖像連通域八連接體標記規(guī)則，標記結果有效。

為了比較算法采用并行處理和CPU單線程處理的效率，分別將算法在GTM520M_E和K20_E以及CPU進行了實現(xiàn)。GTM520M_E是入門級顯卡，也就是低端顯卡，性能很一般。K20_E屬于高性能計算產(chǎn)品，基于Kepler架構。最終結果如圖13所示。

圖13 算法效率測試

如圖13所示，在像素較少的初始區(qū)間，算法在K20_E的計算效率要高于入門級GPU，以及明顯優(yōu)于CPU。在圖像像素不斷增多后CPU算法效率不斷下降，尤其當像素達到一定值時，算法效率幾乎呈垂直下降。而并行處理算法效率雖然也會有所下降，但相較于CPU來說，算法在并行處理時，能夠處理像素較多的圖像，并且效率并不會有非常明顯的下降。由于基于單線程CPU算法設計處理極限為1024*1024大小的圖像，根據(jù)線性回歸分析，在圖像像素越多，包含的連接體數(shù)目越大時并行算法具有明顯的優(yōu)勢，甚至入門級的GPU設備效率也會高于單線程CPU算法。另外對并行算法的穩(wěn)定性也進行了測試，在同一大小圖像包含不同數(shù)目的連接體時標記的速率差的絕對值在10ms內(nèi)，所以并行處理算法具有較高的穩(wěn)定性。

7 結語

通過對現(xiàn)有二值圖像標記算法的研究探討，針對標記算法的缺陷，對連通域標記問題進行了GPU可并行化研究，并根據(jù)研究結果設計和實現(xiàn)了算法。最終實驗結果表明并行標記算法效率整體高于單線程CPU標記算法，尤其是圖像像素不斷增多后，效率增加更為明顯。但目前算法對略小的圖像的應用性不是太好，處理效果不明顯，這是今后的改進之處。