高分辨圖像區域填充的并行計算方法

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

（1.大連理工大學 軟件學院，遼寧 大連 116620；2.大連理工大學 計算機科學與技術學院，遼寧 大連 116024）

0 概述

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

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

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

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

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

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

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

在多數情況下，光柵格式圖像可以直接獲得，如衛星遙感、地質勘探、工業監控等場景，而頂點和鏈碼表示的圖像需做進一步提取處理。傳統種子填充算法如圖1 所示。

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

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

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

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

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

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

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

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

2.1 相關概念

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

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

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

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

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

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

結果內部色：填充結果中要求對輪廓內部填充的顏色；

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

內部隨機種子：均勻分布函數產生的非邊界種子，可能位于背景區域、帶填充區域、輪廓線上；

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

內部隨機種子線程：以內部隨機種子為初始填充點的線程；

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

2.2 算法設計

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

2.2.1 種子生成

種子生成主要是生成M個外部邊界種子和N個內部隨機種子。

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

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

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

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

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

2.2.2 多個線程填充

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

1）標記設定規則

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

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

2）填充規則

在多線程環境下，需要對種子掃描線算法的填充規則進行擴充。

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

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

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

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

當所有線程完成填充后，每個內部隨機種子線程的鄰居堆棧中會記錄與該線程填充區域相鄰的標記。填充后的鄰居信息如表1 所示。

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

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

針對當前江蘇高校科技成果轉化效率較低的問題，完善高校、科研院所分類考核評價機制，把科技成果轉化、產學研協同創新作為重要考核指標。借鑒上海市經驗，引導高校院所建立技術轉移機構，建立職務科技成果披露制度，完善技術轉移服務人員的職稱評定、收入分配等制度。借鑒浙江省的先進做法，探索科技經紀人試點工作，組織南京大學、東南大學、蘇州大學等研究型大學面向江蘇選派科技經紀人，促進高校科技成果的產業化［7］。

2.2.3 并查集算法合并連通區域

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

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

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

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

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

2.2.4 反轉圖像

得到并查集結果后，掃描整個圖像，對每個像素進行判定和處理，規則如下：

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

2）如果該像素位于輪廓線上（值為255），則可以根據填充要求設為結果內部色、外部色或者不變；

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

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

至此，完成輪廓內部的填充，合并后與反轉后的結果如圖5 所示。

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

2.3 線程同步問題分析

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

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

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

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

2.4 填充階段GPU 堆棧的構造

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

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

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

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

3 實驗設計與分析

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

3.1 實驗設計

3.1.1 硬件配置

實驗平臺為HP580 Gen 9 服務器，XeonE7 10 核處理器，160 GB 內存。實驗平臺如表3 所示。

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

3.1.2 測試圖像數據

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

表4 實驗圖像數據Table 4 Experimental images data

3.1.3 評價手段

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

3.2 算法流程對比

相比傳統反向填充算法，本文算法省略了求外接矩形步驟，增加用并查集算法對多線程的填充標記進行分類。

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

3.3 算法最優參數獲取

3.3.1 填充階段

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

表5 填充階段最優參數Table 5 Optimal parameters in filling phase

采用最優參數配置時，雖然GPU 線程數量遠超CPU 方案，但GPU 填充實現的平均加速比（2.27）低于CPU（4.12）。主要原因是：

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

該算法具有三重循環和大量分支操作，易引起GPU 線程分支，導致線程之間串行執行，進而導致性能急劇下降。

2）大量不規則全局存儲器訪問

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

3）數據傳輸負擔大

相對于CPU 版本，GPU 版本還存在數據傳輸負擔，Kernel 運行前需要將圖像從CPU 傳輸到GPU，運行后需要將數據返回CPU，降低了GPU 的加速比。

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

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

3.3.2 反轉/合并階段

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

CPU 合并將圖像自上而下分割為若干塊，每個線程負責一塊圖像中像素的反轉。

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

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

表6 反轉階段最優參數Table 6 Optimal parameters in reverse phase

3.4 單張圖像性能對比

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

表7 不同技術的組合Table 7 Combination of different technologies

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

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

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

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

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

3.5 批量圖像流水線模型

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

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

串行模型和流水線模型如圖10 所示，當第i個圖像在CPU 上完成填充步驟后，將填充中間結果傳遞至GPU 進行合并/反轉，同時CPU 不需等待GPU工作完成，可以開始第i+1 個圖像的填充過程。此時異構平臺的CPU 和GPU 同時進行兩張圖片處理，實現任務間的并行。

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

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

構建一個長度為100 的圖像數組，模擬處理一批圖片的應用場景，計算整體處理時間后除以100，獲得單張圖片的處理時間。

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

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

4 結束語

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