曹建立，陳志奎，王宇新，郭 禾

（1.大連理工大學(xué) 軟件學(xué)院，遼寧 大連 116620；2.大連理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024）

0 概述

區(qū)域填充是指對圖像中一塊被封閉輪廓包圍的區(qū)域重新著色。圖像中區(qū)域的表達(dá)方式主要有：對于規(guī)則或近似為多邊形的區(qū)域，使用頂點/邊的形式來表達(dá)；對于較復(fù)雜的形狀，用光柵圖像來表達(dá)；為進(jìn)一步壓縮存儲空間，用鏈碼的形式來表達(dá)。

以頂點/邊的形式表示多邊形，采用射線法、弧長法進(jìn)行逐點填充，或使用有序邊表、活動邊表、奇偶掃描轉(zhuǎn)換算法進(jìn)行逐行填充［1-2］。這些算法主要計算出射線、掃描線與多邊形邊的交點，利用奇偶規(guī)則來判斷某個像素是否位于多邊形內(nèi)部，進(jìn)而進(jìn)行填充。

對于光柵格式的圖像，區(qū)域填充問題可以用種子填充法來解決。光柵圖像中的區(qū)域可以用兩種方式定義：內(nèi)部定義是區(qū)域內(nèi)部像素具有一種特定顏色，而區(qū)域外部像素具有其他顏色；邊界定義是區(qū)域輪廓上的像素具有不同于背景色的特定顏色。在內(nèi)部定義區(qū)域上運行的種子填充算法稱洪泛法［3］；在邊界定義區(qū)域上運行的種子填充算法稱邊界填充算法［2，4］。洪泛法和邊界填充算法流程相似，僅在判斷區(qū)域邊界時存在細(xì)微差別。種子填充算法需要一個輪廓內(nèi)部的像素作為種子點，算法從種子點開始，通過4 連通或8 連通規(guī)則向鄰居像素進(jìn)行填充。

FREEMAN［5］通過區(qū)域輪廓的起點和像素間的相對位置來記錄區(qū)域輪廓線信息，該編碼方式稱為鏈碼，具有節(jié)省空間、易于提取幾何特征的優(yōu)點。CAI［6］等研究基于鏈碼的圖像恢復(fù)方式，利用相鄰像素間的相對位置對像素進(jìn)行分類，從而決定哪些像素間的線段需要被填充。LIU 等［7］提出一種基于鏈碼并融合了邊界點奇偶性檢查和區(qū)域生長法優(yōu)點的填充算法。研究者對基于鏈碼的填充算法做了進(jìn)一步優(yōu)化［8-10］。

體圖形學(xué)［11］廣泛應(yīng)用在建模、工業(yè)設(shè)計、醫(yī)學(xué)影像中。將種子填充算法移植到三維空間以解決封閉空間的填充問題。針對該問題，F(xiàn)ENG 等［12］提出一種高效的三維種子填充算法。薛斌黨［13］通過改進(jìn)棧結(jié)構(gòu)和入棧種子方法去除多余出入棧和回溯操作，提高算法效率。YU［14］等提出基于掃描切片的三維種子填充算法。

填充算法在地理信息系統(tǒng)、遙感數(shù)據(jù)分析［15］、計算機(jī)動畫制作、目標(biāo)識別［16-17］、圖像重建［10］、區(qū)域覆蓋［18］、工業(yè)設(shè)計［19-20］、醫(yī)學(xué)影像［21］等方面有重要的應(yīng)用。本文在異構(gòu)平臺上設(shè)計并實現(xiàn)并行反向填充算法，利用不同并行方案在CPU 和GPU 處理器上獲取最佳參數(shù)。通過構(gòu)建異構(gòu)流水線處理模型批量處理圖像，有效提高處理器的利用率和輪廓填充速度。

1 種子填充與反向填充算法

在多數(shù)情況下，光柵格式圖像可以直接獲得，如衛(wèi)星遙感、地質(zhì)勘探、工業(yè)監(jiān)控等場景，而頂點和鏈碼表示的圖像需做進(jìn)一步提取處理。傳統(tǒng)種子填充算法如圖1 所示。

圖1 傳統(tǒng)種子填充算法示意圖Fig.1 Schematic diagram of traditional seed filling algorithm

種子填充算法的缺點主要有：1）使用深度優(yōu)先堆棧來保存種子數(shù)據(jù)，每個像素點需進(jìn)棧出棧一次才能完成填充，因此算法效率低；2）需人工交互，在每個封閉輪廓內(nèi)指定一個像素作為種子，該缺點對于批量處理圖像十分不利。

針對第1 個缺點，PAVLIDIS 等［1］提出掃描線種子填充算法，該算法只保存一條連續(xù)待填充線段最右側(cè)的像素作為種子，堆棧的訪問次數(shù)，提高填充效率。研究者從種子存儲結(jié)構(gòu)、像素訪問順序等方面對該算法進(jìn)行優(yōu)化［22-24］，進(jìn)一步提高算法效率。陳卓等［20］在獲取新種子點入棧階段采用多線程并行方案，在一定程度上提升了算法的并行度。VUCKOVIC等［25］通過使用針對內(nèi)存訪問高度優(yōu)化的線性圖像數(shù)據(jù)結(jié)構(gòu)［26］和DMA 技術(shù)，從實現(xiàn)角度優(yōu)化掃描線種子填充算法的效率。

針對第2 個缺點，柳稼航［27］提出一種反向填充算法，先求出輪廓的外接矩形，進(jìn)而在外接矩形上任選一點作為種子，確定該種子點一定位于輪廓的外部。反向填充算法如圖2 所示。以此種子為出發(fā)點完成對輪廓外部的填充。將上一步的結(jié)果進(jìn)行一次求反，即獲得封閉輪廓內(nèi)的填充結(jié)果。由于避免了人工指定種子，該算法適合工業(yè)上處理批量圖像。例如，在流水線工件檢測場景中，工業(yè)相機(jī)對流水線上工件進(jìn)行拍照和處理，每秒可能產(chǎn)生數(shù)十幀圖像。使用傳統(tǒng)種子填充算法對圖像中不規(guī)則封閉輪廓內(nèi)部進(jìn)行填充，需要人工在每張圖片的輪廓內(nèi)部指定一個像素作為種子，無法保證處理的可靠性和效率，反向填充算法則克服了這些缺點。

圖2 反向填充算法Fig.2 Conversely filling algorithm

隨著半導(dǎo)體和光學(xué)技術(shù)的不斷進(jìn)步，視頻和圖像設(shè)備的分辨率越來越高，數(shù)據(jù)量越來越大。在民用方面，如蘋果手機(jī)iphone11 拍照最大分辨率達(dá)到了3 840 像素×2 160 像素（4K 高清），視頻錄制分辨率也到了1 920像素×1 080像素（1 080P）；華為Mate30 手機(jī)拍照最高支持7 296像素×5 472像素（40MP 選項）；高清電視信號也采用4K 高清標(biāo)準(zhǔn)。在工業(yè)方面，遙感技術(shù)、地質(zhì)勘探、地圖測繪、土地資源可視化等領(lǐng)域也產(chǎn)生海量的高分辨圖像。目前，無論是掃描線種子填充算法還是反向填充算法都基于堆棧/隊列的串行算法，無法充分利用多核、多線程、異構(gòu)處理器的優(yōu)勢。例如，即使采用高性能的C++圖形庫OpenCV，對8 KB 分辨圖像進(jìn)行一次填充需要約120 ms，每秒鐘只能處理8.3 幀。因此，處理高分辨、大批量的圖像，設(shè)計高效率的種子填充算法非常有必要。

基于以上需求，本文提出了并行反向填充算法，在保留反向填充算法無需人工交互優(yōu)點的同時，利用多核、異構(gòu)處理器提高算法性能。

2 基于圖連通的并行填充算法

2.1 相關(guān)概念

為更方便和準(zhǔn)確地描述算法流程，定義如下概念：

圖像邊界：矩形圖形的四條邊（border），即圖像中坐標(biāo)x=0、x=w?1、y=0、y=h?1 的像素；

圖像輪廓：待填充區(qū)域的輪廓線（contour/boundary）；

背景色：原始圖像中背景顏色，本文采用灰度值0；

輪廓線色：原始圖像中輪廓線的顏色是待填充區(qū)域和背景區(qū)域的分隔線，輪廓線內(nèi)部為待填充區(qū)域，外部為背景區(qū)域，本文采用灰度值255；

結(jié)果外部色：填充結(jié)果中要求對輪廓外部填充的顏色，本文采用灰度值0；

結(jié)果內(nèi)部色：填充結(jié)果中要求對輪廓內(nèi)部填充的顏色；

外部邊界種子：位于圖像邊界上的種子；

內(nèi)部隨機(jī)種子：均勻分布函數(shù)產(chǎn)生的非邊界種子，可能位于背景區(qū)域、帶填充區(qū)域、輪廓線上；

外部邊界種子線程：以外部邊界種子為初始填充點的線程；

內(nèi)部隨機(jī)種子線程：以內(nèi)部隨機(jī)種子為初始填充點的線程；

線程填充任務(wù)量：每個線程所填充的像素個數(shù)，衡量線程之間的負(fù)載均衡程度。

2.2 算法設(shè)計

基于圖連通的并行填充算法中，在圖像的邊界上放置若干外部邊界種子，圖像的內(nèi)部放置若干內(nèi)部隨機(jī)種子。使多個線程同時從圖像的內(nèi)部和外部一起填充，從而提升算法并行度和填充效率。但也帶來新的問題，即算法開始時，無法判定這些內(nèi)部隨機(jī)種子位于輪廓內(nèi)部還是外部，其填充過的區(qū)域是否合理。為了解決該問題，為每個線程增加一個鄰居堆棧來記錄該線程在填充過程中與其他線程的相鄰關(guān)系。在完成填充后，使用并查集算法來完成相鄰區(qū)域的合并。

2.2.1 種子生成

種子生成主要是生成M個外部邊界種子和N個內(nèi)部隨機(jī)種子。

1）生成M個外部邊界種子，在圖像邊界上選擇M個點作為外部邊界種子，為了簡化算法，直接在圖像的4 條邊界上選擇若干像素作為種子，不求輪廓的外接矩形。

2）生成N個內(nèi)部隨機(jī)種子，利用隨機(jī)函數(shù)在圖像內(nèi)部隨機(jī)選擇若干像素點作為內(nèi)部隨機(jī)種子。假設(shè)輪廓外像素點個數(shù)為X，輪廓內(nèi)部像素點個數(shù)為Y，輪廓線上像素點個數(shù)為Z。隨機(jī)種子的位置可能出現(xiàn)3 種情況：（1）位于待填充區(qū)域外部，概率為X/（X+Y+Z）；（2）位于待 填充區(qū) 域內(nèi)部，概率為Z/（X+Y+Z）；（3）位于待填充區(qū)域邊界上，概率為Y/（X+Y+Z）。通常情況下Z遠(yuǎn)小于X和Y，故第3 種情況出現(xiàn)的概率很小。

由于種子掃描線算法首先進(jìn)行行填充，如果兩個種子位于同一行，則這兩個種子的填充區(qū)域會很快相遇，降低算法效率。為避免這種情況發(fā)生，在初始化時將種子盡量放置在不同的行上。具體做法是在圖像內(nèi)部以均勻間隔確定N條橫線，然后在每條橫線上用隨機(jī)函數(shù)產(chǎn)生一個點作為隨機(jī)種子點。

種子分布情況如圖3 所示。圖3 演示種子數(shù)量為16 的分布情況（4 個外部種子編號1～4，12 個內(nèi)部種子編號5～16）。

圖3 種子分布情況Fig.3 Seeds distribution

2.2.2 多個線程填充

串行反向填充算法只啟動1 個線程，使用1 個不同于原圖中背景色和輪廓色的標(biāo)簽。對并行反向填充算法而言，以邊界種子為起始點的線程填充區(qū)域位于輪廓外部；以內(nèi)部隨機(jī)種子為起始點的線程在填充時無法判定所填充的區(qū)域位于輪廓外部還是內(nèi)部，填充結(jié)果是否合理。因此需要為每個內(nèi)部隨機(jī)種子線程指派1 個唯一的填充標(biāo)記，并在填充完成后對每個線程所填充的區(qū)域進(jìn)行分析，剔除無效區(qū)域。如果使用256 級灰度圖像，每個像素用1 Byte 表示，背景色為0 黑色，輪廓線為255 白色，則使用的標(biāo)記為1～254。將標(biāo)簽1 分配給外部邊界種子共同使用，則最多可以使用253 個內(nèi)部隨機(jī)種子線程來并行填充。對于需要同時運行更多線程才能發(fā)揮優(yōu)勢的GPU 而言，1 Byte 提供的標(biāo)記范圍不足以發(fā)揮硬件的全部潛力，所以在GPU 版本中，使用雙字節(jié)的unsigned short 類型代替unsigned char 類型來保存每個像素。

1）標(biāo)記設(shè)定規(guī)則

外部邊界種子線程可以確定其定位于待填充輪廓的外部，其填充區(qū)域也一定位于輪廓外部，所以外部邊界種子線程全部使用同一個填充標(biāo)記1。

在填充前無法判定內(nèi)部隨機(jī)種子線程的種子位于輪廓內(nèi)部還是外部，其填充區(qū)域是否有效也待檢測，所以每個線程使用唯一的填充標(biāo)記。為簡便起見，使用線程號作為填充標(biāo)記。

2）填充規(guī)則

在多線程環(huán)境下，需要對種子掃描線算法的填充規(guī)則進(jìn)行擴(kuò)充。

對于內(nèi)部隨機(jī)種子的情況3，即種子落在輪廓線上（如圖3、圖4 中的種子10）不做任何操作，直接結(jié)束線程。該情況在串行算法中不會發(fā)生，在并行算法中發(fā)生的概率也很小。

對于外部種子線程以及內(nèi)部隨機(jī)種子的情況1（種子位于輪廓外部）和情況2（種子位于輪廓內(nèi)部），按照以下規(guī)則進(jìn)行填充：（1）當(dāng)遇到一個未填充像素時（值為背景色0），填充為該線程自己的填充標(biāo)記；（2）當(dāng)遇到輪廓線（值為255）或圖像邊界（坐標(biāo)超出圖像范圍）時，結(jié)束當(dāng)前行填充，從堆棧中出棧新種子，開始上下相鄰行填充；（3）當(dāng)遇到其他線程填充過的像素時（值不為0，也不為255），不僅要按照標(biāo)準(zhǔn)的種子掃描線算法結(jié)束當(dāng)前行的填充，還要將該像素的值（即其他線程的填充標(biāo)記）記錄到本線程私有的鄰居堆棧中。為減少冗余數(shù)據(jù)，規(guī)定外部邊界種子線程（填充標(biāo)記為1）不用記錄鄰居關(guān)系。由于鄰居關(guān)系具有對偶性，這個規(guī)定不影響結(jié)果的正確性。

多線程填充后的結(jié)果如圖4 所示，此時圖像中任意像素屬于以下3 種情況之一：1）位于被填充過的區(qū)域中，此時像素值為填充該像素的線程填充標(biāo)記（1～254），如字母E 內(nèi)部被標(biāo)簽6、15 填充，H 的內(nèi)部被標(biāo)簽8 填充，輪廓外的部分被其他線程的標(biāo)簽所填充；2）位于未被填充過的封閉輪廓內(nèi)部，某些封閉區(qū)域的內(nèi)部可能沒有落入種子，所以輪廓內(nèi)部未被填充過，保持原來的值（背景色0），如字母G 的內(nèi)部；3）位于輪廓線上，輪廓線上的像素不會被任何線程填充，保持原來的值（輪廓色255）。

圖4 多線程填充后的結(jié)果Fig.4 Results after multithreading filling

當(dāng)所有線程完成填充后，每個內(nèi)部隨機(jī)種子線程的鄰居堆棧中會記錄與該線程填充區(qū)域相鄰的標(biāo)記。填充后的鄰居信息如表1 所示。

表1 填充后的鄰居信息Table 1 Neighbor information after filling

種子8 單獨落在一個輪廓的內(nèi)部，因此沒有鄰居；種子10 位于輪廓線上，提前結(jié)束，沒有進(jìn)行填充，故鄰居堆棧也為空。種子8 和12 位于同一輪廓內(nèi)部，所以相互記錄對方為鄰居。其他種子均在堆棧中記錄鄰居的標(biāo)簽。

針對當(dāng)前江蘇高校科技成果轉(zhuǎn)化效率較低的問題，完善高校、科研院所分類考核評價機(jī)制，把科技成果轉(zhuǎn)化、產(chǎn)學(xué)研協(xié)同創(chuàng)新作為重要考核指標(biāo)。借鑒上海市經(jīng)驗，引導(dǎo)高校院所建立技術(shù)轉(zhuǎn)移機(jī)構(gòu)，建立職務(wù)科技成果披露制度，完善技術(shù)轉(zhuǎn)移服務(wù)人員的職稱評定、收入分配等制度。借鑒浙江省的先進(jìn)做法，探索科技經(jīng)紀(jì)人試點工作，組織南京大學(xué)、東南大學(xué)、蘇州大學(xué)等研究型大學(xué)面向江蘇選派科技經(jīng)紀(jì)人，促進(jìn)高?？萍汲晒漠a(chǎn)業(yè)化［7］。

2.2.3 并查集算法合并連通區(qū)域

該步驟是并行反向填充算法的核心。有些隨機(jī)種子位于輪廓外部，有些位于輪廓內(nèi)部。位于輪廓外部的種子特征是其填充過的區(qū)域必定直接或間接同邊界種子的填充區(qū)域相鄰，需識別這些區(qū)域并將其反轉(zhuǎn)為結(jié)果背景色，剩余未被填充區(qū)域和被填充但與邊界種子填充區(qū)域不連通則設(shè)為結(jié)果前景色。

利用上一步得到的鄰居關(guān)系將相鄰區(qū)域進(jìn)行合并的本質(zhì)是動態(tài)連接（Dynamic connectivity）問題。鄰居關(guān)系具有自反性、對稱性和傳遞性，該問題可以利用不相交集合森林的并查集（Union_Find）算法［28］來解決。并查集算法通過Find 和Union 操作，利用給出元素之間鄰接聯(lián)系，將元素劃分成若干個集合，每個集合中的元素具有直接或間接聯(lián)系。該算法的時間復(fù)雜度為O（N×（1～lgM）），其中N是相鄰關(guān)系信息數(shù)量，M是合并后獨立集合的數(shù)量。

在填充問題中，N是全部線程鄰居關(guān)系的數(shù)量。在本例中，N=21，即算法記錄了21 條鄰居信息。除了邊界種子標(biāo)簽值1 之外，其他標(biāo)簽的鄰居關(guān)系存在部分冗余數(shù)據(jù)，例如線程5 記錄鄰居關(guān)系（5，7），而線程7 同樣記錄鄰居關(guān)系（7，5）。冗余鄰居關(guān)系記錄處理可以提前結(jié)束。M是合并后集合的個數(shù)。在填充問題中，每個獨立輪廓線會圍起一個獨立區(qū)域，全部輪廓外的部分則合并成另一個獨立區(qū)域，因此當(dāng)每個封閉輪廓內(nèi)部都有種子時，M為圖中輪廓數(shù)量+1。在本例中，字母G 中沒有包含種子，也沒有產(chǎn)生鄰居信息，所以沒有形成一個獨立區(qū)域，因此M=3+1?1=3。

并查集算法在運行初期，將每個填充標(biāo)記看作一顆只有一個節(jié)點的樹，全部標(biāo)記的集合構(gòu)成一個森林，用root 數(shù)組來表示樹中節(jié)點之間的父子關(guān)系。root 數(shù)組中下標(biāo)表示一個節(jié)點，而對應(yīng)數(shù)組元素值則表示該節(jié)點的父節(jié)點。算法開始運行時，外部邊界種子填充標(biāo)記對應(yīng)節(jié)點的數(shù)組元素值等于1，內(nèi)部隨機(jī)種子填充標(biāo)記對應(yīng)節(jié)點的數(shù)組元素值等于自己的下標(biāo)，表示自己是自己的父節(jié)點，即該樹目前只有自己一個節(jié)點。每個鄰居關(guān)系對的加入都可能導(dǎo)致兩顆樹合并成為一棵。具體操作是在root 數(shù)組中逐級向上查找鄰居關(guān)系對中兩個節(jié)點的根節(jié)點，如果兩者的根節(jié)點不同，則將一個節(jié)點的根節(jié)點設(shè)置為另一個節(jié)點的根節(jié)點的父節(jié)點，完成兩棵樹的合并；如果兩者根節(jié)點相同，說明屬于同一顆樹，這條鄰居信息是冗余數(shù)據(jù)，不需再做處理。為了簡便，規(guī)定合并時由值較小的節(jié)點充當(dāng)父節(jié)點。全部鄰居關(guān)系對處理后，得到若干棵合并后的樹。但此時的樹可能擁有較大的高度，不利于下一步查找工作。所以在完成合并后需對樹進(jìn)行路徑壓縮，將同一顆樹中所有節(jié)點的父節(jié)點都設(shè)為該樹的根節(jié)點。只需在root數(shù)組中進(jìn)行一次查找，便可確定一個節(jié)點是某個指定根節(jié)點的子節(jié)點。

經(jīng)過并查集算法處理后，可以得到若干棵樹。將這些樹分為以外部邊界種子填充標(biāo)記（值為1）為根的樹和不以1 為根的樹。在本例中，節(jié)點集合｛1，5，6，7，9，11，12，13，14，16｝都以1 為根，說明它們和邊界種子連通，同屬于輪廓的外部；而節(jié)點集合｛10｝和｛6，15｝分別以根6 和10 為根，同標(biāo)記1 不連通，可以確定其位于封閉輪廓的內(nèi)部。并查集算法結(jié)果如表2 所示。

2.2.4 反轉(zhuǎn)圖像

得到并查集結(jié)果后，掃描整個圖像，對每個像素進(jìn)行判定和處理，規(guī)則如下：

1）如果該像素未被填充（值為0），則必然位于輪廓內(nèi)部，需設(shè)為結(jié)果內(nèi)部色，例如字母G 的內(nèi)部；

2）如果該像素位于輪廓線上（值為255），則可以根據(jù)填充要求設(shè)為結(jié)果內(nèi)部色、外部色或者不變；

3）如果像素被某個標(biāo)記填充，且在root 數(shù)組中以該標(biāo)記為下標(biāo)的元素值為1，說明該像素和邊界種子連通，位于輪廓外部，將其設(shè)置為結(jié)果外部色；

4）如果像素被某個標(biāo)記填充，且在root 數(shù)組中以該標(biāo)記為下標(biāo)的元素值不為1，說明該像素位于輪廓內(nèi)部，將其設(shè)為結(jié)果內(nèi)部色，例如值為6、8、15 的像素。

至此，完成輪廓內(nèi)部的填充，合并后與反轉(zhuǎn)后的結(jié)果如圖5 所示。

圖5 并查集算法填充結(jié)果Fig.5 Filling results of Union_Find algorithm

2.3 線程同步問題分析

本文算法在填充階段啟動多個線程進(jìn)行填充，每個線程的任務(wù)量和填充范圍是不固定的，而是由種子附近的像素分布情況以及處理器的調(diào)度情況來決定，可能會出現(xiàn)多個線程同時訪問同一像素的情況。理論上，為了避免線程間的競爭，需要在讀寫像素時使用互斥量來保證結(jié)果的正確性，但互斥機(jī)制有比較高的代價，導(dǎo)致大量線程等待，從而降低算法效率。

對算法進(jìn)行分析和驗證，認(rèn)為有可能兩個甚至多個線程同時讀取同一個像素，判斷其為未填充像素后，同時將該像素放入自己的種子堆棧，并在填充完當(dāng)前行后將其出棧，并寫入本線程的標(biāo)簽。

在不使用互斥量的情況下，無法避免出現(xiàn)多個線程寫一個像素的現(xiàn)象，也無法確定多個線程的寫入順序，但可以保證最終必定有一個線程的標(biāo)記會被寫入，此像素不會被遺漏。由于這種情況一定發(fā)生在兩個或多個線程填充區(qū)域的邊界上，因此該像素最終被寫入哪個線程的標(biāo)記，都是合理的。發(fā)生競爭的線程會在各自的鄰居堆棧里記錄彼此相鄰關(guān)系，這些具有相鄰關(guān)系的區(qū)域在反轉(zhuǎn)階段都會被合并為一個區(qū)域。同樣適用一個線程的填充區(qū)域?qū)⒘硪粋€線程的填充區(qū)域分割開的情況。因此這個像素被填充為哪個線程的標(biāo)簽都不會影響最終結(jié)果的正確性。在本算法填充階段，無需使用代價高的原子操作、互斥量機(jī)制，放任線程間的自由競爭不存在死鎖、死循環(huán)或像素遺漏的問題。

在算法反轉(zhuǎn)階段，由于每個線程分配的待處理像素是固定的，因此不存在競爭、同步問題。

2.4 填充階段GPU 堆棧的構(gòu)造

種子掃描線算法在保存種子和鄰居信息時需要用堆棧數(shù)據(jù)結(jié)構(gòu)。在CPU 中實現(xiàn)該算法時，使用C++STL 提供可以根據(jù)存儲內(nèi)容動態(tài)調(diào)整容量的std：：stack 類。但CUDA 不支持C++STL，復(fù)雜數(shù)據(jù)結(jié)構(gòu)需要編程者自己實現(xiàn)，而在GPU 中使用動態(tài)分配內(nèi)存函數(shù)來實現(xiàn)具有動態(tài)調(diào)整容量功能的堆棧，其時間成本較高，因此使用定長數(shù)組和計數(shù)器變量來構(gòu)造GPU 堆棧。每個GPU 線程和CPU 線程執(zhí)行的算法完全相同，利用CPU 版本運行期間種子堆棧和鄰居堆棧的統(tǒng)計信息來設(shè)定GPU 堆棧的最大長度。CPU 版本在啟動不同數(shù)量的線程時，種子堆棧容量和鄰居堆棧的使用情況如圖6 所示（8 KB 分辨率圖像）。

圖6 堆棧使用情況（8 KB 分辨率圖像）Fig.6 Stack usage（8 KB resolution image）

從圖6 可以看到，在CPU 多線程環(huán)境下，種子堆棧的最大長度為14，平均長度約為5。將GPU 種子堆棧最大容量設(shè)置為16；鄰居堆棧最大長度為6，平均長度約為2，將GPU 鄰居堆棧最大容量設(shè)為8。實驗證明，此設(shè)置也可以處理8 KB 分辨率圖像時。像素坐標(biāo)使用無符號2 Byte 類型（最大65 535），每個像素的x、y坐標(biāo)共占8 Byte，每個線程的種子堆棧需要8×16=128 Byte。鄰居堆棧保存鄰居標(biāo)簽信息，標(biāo)簽也使用無符號2 Byte 類型，每個線程需要2×8=16 Byte。

待填充圖像被多個SM 共享，所以需放在全局內(nèi)存中；鄰居堆棧傳回Host 端，且訪問頻率低于種子堆棧，因此將其放在全局內(nèi)存中。而種子堆棧是每個線程私有的，無需與其他線程共享，具有較高的訪問頻率且無需回傳CPU，將其放在共享內(nèi)存中來加快訪問速度。Kepler 架構(gòu)［29］GPU 可以提供最大48 KB的共享內(nèi)存，每個SM 的共享內(nèi)存容量可以支持最多48 KB/128 Byte=384 個線程同時運行。

3 實驗設(shè)計與分析

本文算法將多個種子放置在圖像的邊界和內(nèi)部，多個線程同時從圖像的邊界和內(nèi)部開始填充，因此填充效率高于單種子填充算法。該算法增加了記錄區(qū)域鄰接關(guān)系和使用并查集判斷區(qū)域連通性步驟，則增加了算法的時間成本和空間代價。

3.1 實驗設(shè)計

3.1.1 硬件配置

實驗平臺為HP580 Gen 9 服務(wù)器，XeonE7 10 核處理器，160 GB 內(nèi)存。實驗平臺如表3 所示。

表3 實驗平臺信息Table 3 Experimental platform information

3.1.2 測試圖像數(shù)據(jù)

實驗中使用6 種常見分辨率的圖像作為測試數(shù)據(jù)，輪廓像素滿足4 連通規(guī)則。實驗圖像數(shù)據(jù)如表4所示。

表4 實驗圖像數(shù)據(jù)Table 4 Experimental images data

3.1.3 評價手段

采用C++11 提供的高精度chrono 庫，以μs 為單位，對算法和函數(shù)進(jìn)行測量。對GPU Kernel 進(jìn)行測量時，利用CUDA 同步函數(shù)進(jìn)行同步來確保準(zhǔn)確計時。在算法之間進(jìn)行橫向比較時，以串行算法作為基準(zhǔn)，采用相對于串行算法的加速比作為衡量手段。為保證客觀和可移植性，在編譯時使用默認(rèn)–O0 選項實現(xiàn)全部代碼。算法運行100 次并求平均值作為實驗結(jié)果。只統(tǒng)計算法在CPU、GPU 中處理的時間以及數(shù)據(jù)在CPU～GPU 傳輸?shù)臅r間。

3.2 算法流程對比

相比傳統(tǒng)反向填充算法，本文算法省略了求外接矩形步驟，增加用并查集算法對多線程的填充標(biāo)記進(jìn)行分類。

在初步實驗中，根據(jù)種子數(shù)量不同，種子生成耗時在3～760 μs；并查集算法耗時1～2 786 μs。相對于需要大量讀寫內(nèi)存，耗時達(dá)數(shù)十、數(shù)百毫秒的填充和反轉(zhuǎn)過程，這兩個步驟在算法總耗時中只占較小的比例。根據(jù)阿姆達(dá)爾定律，應(yīng)該對占算法中較大比例的部分進(jìn)行優(yōu)化，將并行化重點放在填充和反轉(zhuǎn)階段，采用C++多線程和CUDA 兩種技術(shù)對這兩個環(huán)節(jié)進(jìn)行并行化，通過實驗確定每個階段的最佳參數(shù)。

3.3 算法最優(yōu)參數(shù)獲取

3.3.1 填充階段

采用C++多線程技術(shù)和CUDA 技術(shù)來實現(xiàn)填充階段的并行化，每個線程負(fù)責(zé)一個種子的填充。C++多線程實現(xiàn)的關(guān)鍵參數(shù)是并發(fā)線程數(shù)量（種子數(shù)量），而CUDA 實現(xiàn)的性能不僅與線程數(shù)量（種子數(shù)量）有關(guān)，而且與Kernel 中Block 的配置有關(guān)，因此測試兩者的全部組合，并從中選擇6 種不同分辨率圖像上的加速比平均值作為衡量標(biāo)準(zhǔn)。填充階段最優(yōu)參數(shù)如表5 所示。

表5 填充階段最優(yōu)參數(shù)Table 5 Optimal parameters in filling phase

采用最優(yōu)參數(shù)配置時，雖然GPU 線程數(shù)量遠(yuǎn)超CPU 方案，但GPU 填充實現(xiàn)的平均加速比（2.27）低于CPU（4.12）。主要原因是：

1）種子掃描線算法不適合SIMT 執(zhí)行模型

該算法具有三重循環(huán)和大量分支操作，易引起GPU 線程分支，導(dǎo)致線程之間串行執(zhí)行，進(jìn)而導(dǎo)致性能急劇下降。

2）大量不規(guī)則全局存儲器訪問

GPU 版本中，圖像數(shù)據(jù)保存在全局內(nèi)存中，具有較長的訪問延遲。GPU 的編程手冊建議在顯存中合理安排數(shù)據(jù)，以便能進(jìn)行聯(lián)合訪問（coalesced access）。但每個線程的種子點和周圍輪廓都不相同，決定屬于同一warp 多個線程發(fā)出的內(nèi)存訪存請求是不連續(xù)和不規(guī)則的。種子堆棧使用共享內(nèi)存來實現(xiàn)，基于同樣的原因，同一warp 內(nèi)不同線程以不規(guī)則的方式訪問共享內(nèi)存，也會導(dǎo)致延遲。

3）數(shù)據(jù)傳輸負(fù)擔(dān)大

相對于CPU 版本，GPU 版本還存在數(shù)據(jù)傳輸負(fù)擔(dān)，Kernel 運行前需要將圖像從CPU 傳輸?shù)紾PU，運行后需要將數(shù)據(jù)返回CPU，降低了GPU 的加速比。

啟動較多線程才能發(fā)揮GPU 的優(yōu)勢，而每個線程需要唯一的填充標(biāo)記。為滿足這個要求，將圖像中每個像素用2 Byte 表示，這樣除了背景色和前景色外，還有65 534 個值可以作為線程填充標(biāo)記。但導(dǎo)致圖像數(shù)組的內(nèi)存占用量增加1 倍，數(shù)據(jù)在CPU和GPU 之間的傳輸耗費更長的時間。8 bit 和16 bit圖像的傳遞耗時對比如圖7 所示（8 KB 分辨率圖像），可以看出使用CUDAMemcpy2D（）函數(shù)在PCI?E 總線上傳輸數(shù)據(jù)時具有不對稱性，GPU 向CPU 回傳數(shù)據(jù)需要更長的時間，并且隨著傳輸量的增加，這種不對稱性越明顯。該問題不僅存在填充階段，在反轉(zhuǎn)階段也會影響算法效率。

圖7 8 位/16 位圖像傳輸耗時對比（8 KB 分辨率圖像）Fig.7 Comparison of transmission time with 8 bit/16 bit images（8 KB resolution image）

3.3.2 反轉(zhuǎn)/合并階段

合并階段是根據(jù)并查集算法結(jié)果，將第一階段中被不同標(biāo)記填充過圖像中的像素分為同圖像邊界連通、同圖像邊界不連通、圖像原來的輪廓，然后分別填充為結(jié)果背景色、結(jié)果前景色或保持不變。

CPU 合并將圖像自上而下分割為若干塊，每個線程負(fù)責(zé)一塊圖像中像素的反轉(zhuǎn)。

GPU 合并為每個像素啟動一個線程，線程數(shù)量由圖像分辨率決定。鑒于圖像的二維結(jié)構(gòu)，將Kernel 中的Block 也配置為二維結(jié)構(gòu)。為了獲得最優(yōu)性能，測試block.x、block.y兩個維度上全部可能的組合（每個維度的測試范圍從1～1 024，但一個Block中的線程數(shù)量上限為1 024，因此某些組合如256×8是非法組合）。GPU 中每個線程需要讀取一個像素，以像素值為下標(biāo)查找root 數(shù)組中對應(yīng)元素進(jìn)行標(biāo)記，根據(jù)該標(biāo)記向像素寫入不同的值，圖像數(shù)據(jù)和root 數(shù)組都位于全局內(nèi)存，因此算法性能對全局內(nèi)存的訪問效率比較敏感。

GPU 合并過程的輸入圖像數(shù)據(jù)有兩個來源：由CPU 填充的中間結(jié)果和由GPU 填充的中間結(jié)果。兩者最大的區(qū)別在于圖像像素位數(shù)不同。CPU 填充時最佳種子/線程數(shù)量是110，因此每個像素使用8 bit 的unsigned char 表 示。GPU 填充時 最佳種 子/線程數(shù)量是32 768，需要用位長為16 bit 的unsigned short 類型。兩者圖像容量相差一倍，root 數(shù)組長度（等于種子個數(shù)）相差32 768/110=297.89 倍。因此，在數(shù)據(jù)傳輸效率和GPU 全局內(nèi)存訪問性能上存在較大差異，導(dǎo)致同一算法表現(xiàn)出不同的平均加速比。反轉(zhuǎn)階段最優(yōu)參數(shù)如表6 所示。

表6 反轉(zhuǎn)階段最優(yōu)參數(shù)Table 6 Optimal parameters in reverse phase

3.4 單張圖像性能對比

在填充和合并步驟通過CPU 和GPU 技術(shù)組合形成一個完整的算法，完成圖像填充。不同技術(shù)的組合如表7 所示。

表7 不同技術(shù)的組合Table 7 Combination of different technologies

串行算法作為加速比計算標(biāo)準(zhǔn)使用單線程、單個堆棧來完成填充與反轉(zhuǎn)，作為有效性衡量標(biāo)準(zhǔn)的OpenCV 實現(xiàn)使用cv：：floodFill（）和cv：：threshold（）函數(shù)分別完成圖像的填充與反轉(zhuǎn)。在實驗平臺上測試各種方案的性能，并計算不同組合相對于串行實現(xiàn)的加速比，如圖8 所示。

圖8 相對串行不同組合的加速比Fig.8 Speedup of different combinations relative to serial

從圖8 可以看出，并行算法在高分辨圖像上的性能遠(yuǎn)高于低分辨圖像。因數(shù)據(jù)量較小時，多線程并行帶來的受益不足以彌補(bǔ)線程管理的開銷。GPU+GPU 組合略高于1 的加速比，這是因為填充過程復(fù)雜的邏輯結(jié)構(gòu)不適合GPU 的SIMT 執(zhí)行模型。組合CPU+CPU、CPU+GPU 則獲得了超過3 倍的加速比，高于OpenCV 實現(xiàn)的性能（彩色效果見《計算機(jī)工程》官網(wǎng)HTML 版）。不同組合各階段耗時情況如圖9 所示。

圖9 各階段不同組合耗時情況Fig.9 Time consumption of different combinations in each phase

從圖9 可以看出，不同組合中種子的初始化和并查集算法耗時只占非常小的比例，填充過程耗時占主導(dǎo)地位。在未使用GPU 的組合中，合并/反轉(zhuǎn)過程耗時占第2 位；在使用GPU 的組合中，數(shù)據(jù)傳輸占耗時的第2 位，合并/反轉(zhuǎn)過程占第3 位。

3.5 批量圖像流水線模型

實際應(yīng)用場景，如流水線工件檢測中，往往需要對批量圖像進(jìn)行處理。對于填充和合并在同一設(shè)備上運行的組合而言，批量圖像處理時間就是單個圖像處理時間的疊加；而CPU+GPU 的組合運行在異構(gòu)平臺上，對于批量任務(wù)，具有額外的優(yōu)勢，使得該組合具備進(jìn)一步優(yōu)化的可能：

1）CPU+GPU 組合的填充階段在CPU 上運行，而合并階段在GPU 上運行，對于批量填充任務(wù)，通過合理安排相鄰兩張圖像處理步驟之間的執(zhí)行順序，將異構(gòu)平臺構(gòu)建為流水線，進(jìn)一步提升處理效率。

串行模型和流水線模型如圖10 所示，當(dāng)?shù)趇個圖像在CPU 上完成填充步驟后，將填充中間結(jié)果傳遞至GPU 進(jìn)行合并/反轉(zhuǎn)，同時CPU 不需等待GPU工作完成，可以開始第i+1 個圖像的填充過程。此時異構(gòu)平臺的CPU 和GPU 同時進(jìn)行兩張圖片處理，實現(xiàn)任務(wù)間的并行。

圖10 串行模型和流水線模型Fig.10 Serial model and pipeline model

2）CPU+GPU 組合填充階段使用CPU，最佳種子/線程數(shù)量范圍是70～110，使用8 位的unsigned char 表示一個像素即可。相對于GPU 填充階段實現(xiàn)（最佳種子數(shù)量32 768，需要16 bit 像素），減少數(shù)據(jù)在CPU 和GPU 之間傳輸?shù)暮臅r。

構(gòu)建一個長度為100 的圖像數(shù)組，模擬處理一批圖片的應(yīng)用場景，計算整體處理時間后除以100，獲得單張圖片的處理時間。

異構(gòu)流水線模型處理批量任務(wù)的性能如圖11所示。從圖11 可以看出，相對于單張圖像填充、反轉(zhuǎn)兩階段串行的實現(xiàn)，在處理批量情況下，流水線模型平均性能提高了15.4%。

圖11 異構(gòu)流水線模型處理批量任務(wù)的加速比Fig.11 Speedup of heterogeneous pipeline model for batch tasks

4 結(jié)束語

本文在反向填充算法的基礎(chǔ)上設(shè)計了并行反向填充算法，并基于CPU 和GPU 平臺實現(xiàn)算法的填充、反轉(zhuǎn)/合并階段，獲得最優(yōu)參數(shù)。實驗結(jié)果表明，在6 種常見分辨率的圖像上，CPU+GPU 異構(gòu)方案和流水線模型分別獲得相對串行反向填充算法平均3.84 倍和4.43 倍的加速比，其 中，在4 KB 以上的高分辨圖像上獲得了平均5.68 倍和6.72 倍的加速比。改進(jìn)的算法具有無需人工設(shè)定種子的優(yōu)點，可以充分利用多核、異構(gòu)處理器的計算能力。下一步考慮將二維并行填充算法的優(yōu)勢延伸到三維填充算法中，優(yōu)化和隱藏數(shù)據(jù)傳輸以提高改進(jìn)算法的性能。