基于游程的連通區(qū)域標(biāo)記兩次掃描快速算法*

呂常魁 徐巖 羅冰心

(南京航空航天大學(xué) 機(jī)電學(xué)院， 江蘇 南京 210016)

基于游程的連通區(qū)域標(biāo)記兩次掃描快速算法*

呂?？?徐巖 羅冰心

(南京航空航天大學(xué) 機(jī)電學(xué)院， 江蘇 南京 210016)

為提高二值圖像連通區(qū)域標(biāo)記(CCL)的計(jì)算效率，提出快速游程標(biāo)記(FRL)算法，對(duì)基于游程的兩次掃描算法中的傳統(tǒng)游程連通檢測(cè)算法進(jìn)行了優(yōu)化；然后介紹了基于FRL與并查集的整體算法；最后對(duì)FRL的計(jì)算效率進(jìn)行了實(shí)驗(yàn)驗(yàn)證，并將整體算法與RTS 與SAUF 兩種典型的兩次掃描CCL算法進(jìn)行了比對(duì)分析.結(jié)果表明：FRL算法省去了行間游程不必要的后續(xù)比對(duì)，使得比對(duì)形式接近于鏈?zhǔn)?，大幅度提高了游程?biāo)記的計(jì)算效率，時(shí)間復(fù)雜度由傳統(tǒng)RL算法的O(mn)降為O(m+n-1)，執(zhí)行時(shí)間降為與并查集運(yùn)算環(huán)節(jié)同一量級(jí)；整體算法的性能明顯優(yōu)于RTS算法，總體上略優(yōu)于SAUF算法.

連通區(qū)域標(biāo)記；兩次掃描算法；連通檢測(cè)算法；游程標(biāo)記；并查集

連通區(qū)域標(biāo)記(CCL)是機(jī)器視覺、模式識(shí)別等領(lǐng)域的重要底層基礎(chǔ)算法之一.CCL以像素或游程為基本處理單元，檢測(cè)二值圖像中屬于同一連通區(qū)域的所有單元并進(jìn)行區(qū)域標(biāo)記.CCL按掃描模式主要可分為多次掃描算法[1- 2]、兩次掃描算法[3- 12]和一次掃描算法[13- 14].常用的CCL算法以兩次掃描算法為主.兩次掃描算法一般分為3個(gè)階段：① 掃描圖像，檢測(cè)單元間連通性，賦予各單元臨時(shí)標(biāo)記并記錄單元間等價(jià)標(biāo)記信息；② 處理等價(jià)對(duì)表，獲得各臨時(shí)標(biāo)記的最終標(biāo)記；③二次掃描各單元，賦予各單元最終標(biāo)記.現(xiàn)代兩次掃描算法多基于傳統(tǒng)算法，在加快等價(jià)對(duì)處理速度[4- 5,10,12- 13]、減少近鄰搜索次數(shù)[7,11]、并行計(jì)算[8- 9]等方面對(duì)算法進(jìn)行優(yōu)化.

基于游程的兩次掃描算法是現(xiàn)代主流算法之一.游程指二值圖像行序列中由連續(xù)的、具有相同灰度級(jí)的像素(一般指前景像素)構(gòu)成的線片段.以游程作為基本處理單元，消除了像素級(jí)處理中行間像素的階梯形鄰接產(chǎn)生等價(jià)對(duì)的現(xiàn)象，有效減少了等價(jià)對(duì)數(shù)量[15].現(xiàn)代算法多在提升等價(jià)標(biāo)記處理效率方面開展研究[4- 5,10,12]，而在第一環(huán)節(jié)的行間游程連通性檢測(cè)中，多采用雙層循環(huán)遍歷比對(duì)的傳統(tǒng)模式.研究發(fā)現(xiàn)，基于游程的CCL算法較為耗時(shí)的往往是第一個(gè)環(huán)節(jié).本研究首先提出快速游程標(biāo)記(FRL)算法，該算法對(duì)傳統(tǒng)游程連通性檢測(cè)算法進(jìn)行了優(yōu)化；然后介紹了基于FRL與并查集的整體算法，整體算法應(yīng)用高效的并查集算法RemSP[16]進(jìn)行等價(jià)標(biāo)記處理；最后，對(duì)FRL的計(jì)算效率進(jìn)行了實(shí)驗(yàn)驗(yàn)證，并將整體算法與RTS[5]、SAUF[7]這兩種典型的兩次掃描CCL算法進(jìn)行了實(shí)驗(yàn)比對(duì)分析.

1 FRL算法描述

采用結(jié)構(gòu)R(Row，StartCol，EndCol，Label) 表示游程，4個(gè)參數(shù)依次為游程的行號(hào)、起始列標(biāo)、終止列標(biāo)與臨時(shí)標(biāo)記號(hào).設(shè)當(dāng)前行Xi+1游程為Ri+1，上一行Xi游程為Ri，按8連通判斷規(guī)則，則Ri+1與Ri連通的充要條件為：Ri+1·StartCol ≤Ri·EndCol+1且Ri+1·EndCol ≥Ri·StartCol-1.假設(shè)Ri已被標(biāo)記，則Xi+1游程標(biāo)記和等價(jià)對(duì)生成的一般規(guī)則如下：

① 如果Ri+1與Ri連通且Ri+1未標(biāo)記，則Ri+1·Label←Ri·Label；② 如果Ri+1與Ri連通，而Ri+1已標(biāo)記，且Ri+1與Ri標(biāo)記號(hào)不相同，則生成等價(jià)對(duì)Ri+1·Label,Ri·Label；③ 如果Ri+1與上一行所有游標(biāo)均不連通，則賦予Ri+1新標(biāo)記.

傳統(tǒng)游程標(biāo)記算法按從左到右順序，將Xi+1每一游程與Xi所有游程兩兩比對(duì)，進(jìn)行連通狀態(tài)檢測(cè)與游程標(biāo)記.設(shè)Xi與Xi+1游程個(gè)數(shù)分別為m和n，則Xi+1所有游程標(biāo)記算法時(shí)間復(fù)雜度為O(mn).為便于說明，稱該算法為RL.研究發(fā)現(xiàn)，利用游程間的位置關(guān)系，可以省去不必要的后續(xù)比對(duì)，將算法時(shí)間復(fù)雜度降為O(m+n-1).將上下行游程間位置關(guān)系定義為圖1所示的4種基本類型.

圖1 游程間4種基本位置關(guān)系

以圖2為例，按8連通判斷規(guī)則，說明這4種基本類型的處理規(guī)則：① 按從左到右順序，首先將Xi第一個(gè)游程Ri(1)與Xi+1第一個(gè)游程Ri+1(1)進(jìn)行比對(duì).Ri(1)與Ri+1(1)不連通，且Ri(1)·EndColRi+1(1)·EndCol +1，屬圖1(b)中類型，該情況下，Ri(2)后續(xù)游程均不可能與Ri+1(1)連通，故Ri+1(1)退出比對(duì)序列，取Ri+1(1)下一游程Ri+1(2)，與Ri(2)繼續(xù)比對(duì)；③Ri(2)與Ri+1(2)連通，且Ri(2)·EndCol≤Ri+1(2)·EndCol，屬圖1(c)中類型，該情況下，Ri+1(2)后續(xù)游程均不可能與Ri(2)連通，則Ri(2) 不再參與比對(duì)，對(duì)Ri+1(2)進(jìn)行標(biāo)記或生成等價(jià)對(duì)后，取Ri(2)下一游程Ri(3)，與Ri+1(2)繼續(xù)比對(duì)；④Ri(3)與Ri+1(2)連通，且Ri(3)·EndCol>Ri+1(2)·EndCol，屬圖1(d)中類型，該情況下，Ri(3)后續(xù)游程均不可能與Ri+1(2)連通，故Ri+1(2)不再參與比對(duì)，對(duì)Ri+1(2)進(jìn)行標(biāo)記或生成等價(jià)對(duì)后，取Ri+1(2)下一游程Ri+1(3)，與Ri(3)繼續(xù)比對(duì).

考慮一般情況，行間每?jī)蓚€(gè)游程按上述規(guī)則比對(duì)結(jié)束后，其間必有一個(gè)游程因不可能與比對(duì)行后續(xù)游程連通而退出比對(duì)，則其所屬行下一游程繼續(xù)加入比對(duì).這種比對(duì)過程接近于鏈?zhǔn)?，設(shè)上下行游程個(gè)數(shù)分別為m和n，則比對(duì)過程時(shí)間復(fù)雜度為O(m+n-1).算法實(shí)現(xiàn)要點(diǎn)如下：① 以Xi游程作為比對(duì)參考游程，仍按雙重循環(huán)形式與Xi+1游程比對(duì)(Xi游程為外循環(huán)，Xi+1游程為內(nèi)循環(huán))，進(jìn)入內(nèi)循環(huán)前，如果Xi當(dāng)前游程尚未標(biāo)記，則進(jìn)行標(biāo)記；② 基于上文規(guī)則，按從左到右順序比對(duì)Xi與Xi+1間游程，設(shè)當(dāng)前比對(duì)游程為Ri(a)與Ri+1(b)，則：若Ri+1(b)退出比對(duì)，則繼續(xù)內(nèi)循環(huán)，取Xi+1下一游程Ri+1(b+1)與Ri(a)繼續(xù)比對(duì)；若Ri(a)退出比對(duì)，則跳出內(nèi)循環(huán)，繼續(xù)外循環(huán)，取Xi下一游程Ri(a+1)與Ri+1(b)及其后續(xù)游程繼續(xù)比對(duì)；③ 對(duì)于當(dāng)前行Xi+1游程 ，只對(duì)與Xi游程有連通關(guān)系的進(jìn)行標(biāo)記.

設(shè)Xi+1為當(dāng)前行，搜索Xi+1獲得游程集合{Ri+1(b)}，b{0,1,…,n-1}，游程Label參數(shù)值均

圖2 行間游程位置關(guān)系及比對(duì)形式示例

置為-1，表示未標(biāo)記；設(shè)上一行Xi游程集合為{Ri(a)}，a←{0,1,…,m-1}，當(dāng)前最大臨時(shí)標(biāo)記表示為MaxLabel.將該算法命名為FRL，偽碼如下：

算法1 Procedure FRL (Ri,Ri+1)

輸入:Xi游程集合{Ri(a)}；Xi+1游程集合{Ri+1(b)}；當(dāng)前最大臨時(shí)標(biāo)記MaxLabel.

結(jié)果: 標(biāo)記Xi+1中與Xi有連通關(guān)系的游程，標(biāo)記Xi中未標(biāo)記的游程；生成等價(jià)對(duì).

1k←0;

2fora←0 tom-1do

3begin

4ifRi(a). Label=-1then∥標(biāo)記Xi中未標(biāo)記的游程

5begin

6 MaxLabel←MaxLabel+1;

7Ri(a)·Label←MaxLabel;

8end;

9forb←kton-1do

10begin

11k←b;

12ifRi(a)·EndCol

thenbreak; ∥類型a

13ifRi(a)·StartCol >Ri+1(b)·EndCol +1

thencontinue; ∥類型b

14ifRi+1(b)·Label=-1thenRi+1(b)·Label←Ri(a)·Label

15elseifRi(a)·Label≠Ri+1(b)·Labelthen處理等價(jià)對(duì)Ri(a)·Label,Ri+1(b)·Label;

16 ifRi(a)·EndCol≤Ri+1(b)·EndColthenbreak;∥類型c；類型d則繼續(xù)內(nèi)循環(huán)

17end;

18end;

2 基于FRL與并查集的整體算法描述

整體算法分為游程搜索與存儲(chǔ)、游程標(biāo)記與等價(jià)對(duì)生成、等價(jià)對(duì)合并、游程最終標(biāo)記4個(gè)基本環(huán)節(jié).設(shè)二值圖像大小為w×h(寬度×高度)，則其最大可能游程個(gè)數(shù)為w×h/2，最大可能連通區(qū)域個(gè)數(shù)為w×h/4.建立尺寸為w×h/2的一維數(shù)組A，用以存儲(chǔ)臨時(shí)標(biāo)記號(hào)的最終標(biāo)記.鑒于本研究應(yīng)用并查集算法進(jìn)行等價(jià)對(duì)合并操作，根據(jù)并查集算法思想，首先按各臨時(shí)標(biāo)記均為孤立節(jié)點(diǎn)狀態(tài)對(duì)A進(jìn)行初始化：A[m]←m，m←{0,1,…，wh/2-1}.

第1環(huán)節(jié)負(fù)責(zé)搜索圖像各行游程，生成并存儲(chǔ)游程數(shù)據(jù)結(jié)構(gòu).為便于下文說明，命名該計(jì)算環(huán)節(jié)為RS.將圖像左右邊緣置為背景點(diǎn)，設(shè)二值圖像背景、前景灰度值分別為vb和vo，令v←voxorvb，則當(dāng)前行Xi中滿足Xi[i]xorXi[i+1]=v的像素即為各游程的起始像素或中止像素.對(duì)圖像進(jìn)行光柵掃描，獲取各行游程，將所有游程數(shù)據(jù)結(jié)構(gòu)存于一維動(dòng)態(tài)數(shù)組容器RVector中，以便于后續(xù)的連通區(qū)域特征計(jì)算.游程數(shù)據(jù)結(jié)構(gòu)Label參數(shù)值均置為-1，表示未標(biāo)記.

第2環(huán)節(jié)應(yīng)用FRL算法對(duì)RVector中行間游程進(jìn)行比對(duì)，判斷其連通性，按上文所述規(guī)則，賦予RVector中未標(biāo)記游程臨時(shí)標(biāo)記號(hào)(Label參數(shù))，并生成等價(jià)對(duì)表.這里可以應(yīng)用游程數(shù)據(jù)結(jié)構(gòu)的Row參數(shù)來判斷游程所屬行，從而獲取相鄰兩行的游程.此外，F(xiàn)RL計(jì)算結(jié)束后，需繼續(xù)掃描圖像最后一行的游程，將其中Label參數(shù)為-1的游程按上文規(guī)則賦予臨時(shí)標(biāo)記號(hào).

第3環(huán)節(jié)應(yīng)用并查集算法對(duì)等價(jià)對(duì)表中的所有等價(jià)對(duì)進(jìn)行合并，目的是根據(jù)等價(jià)對(duì)所反映的臨時(shí)標(biāo)記間的動(dòng)態(tài)連通關(guān)系構(gòu)建并查集樹.在游程標(biāo)記過程中，每生成一個(gè)等價(jià)對(duì)，即基于數(shù)組A所反映的臨時(shí)標(biāo)記間動(dòng)態(tài)父子關(guān)系，對(duì)等價(jià)對(duì)兩個(gè)臨時(shí)標(biāo)記分別進(jìn)行根節(jié)點(diǎn)搜索操作，合并兩個(gè)臨時(shí)標(biāo)記所屬支路，將較大根節(jié)點(diǎn)的父節(jié)點(diǎn)指向較小根節(jié)點(diǎn)，這里將A數(shù)組中以較大根節(jié)點(diǎn)序號(hào)為下標(biāo)的元素值置為較小根節(jié)點(diǎn)序號(hào).為提高后續(xù)根節(jié)點(diǎn)搜索效率，通常需要對(duì)支路進(jìn)行路徑壓縮.圖像游程等價(jià)對(duì)形成的支路一般高度較低，如果路徑壓縮過程中存在過多中間數(shù)組操作，反而會(huì)降低計(jì)算效率.根據(jù)Patwary研究成果[16]，采用較為高效的RemSP算法.RemSP算法不刻意進(jìn)行根節(jié)點(diǎn)搜索，以快速進(jìn)行支路合并為目的，巧妙運(yùn)用插接(SPlicing，SP)方法，便搜索邊合并，直至到達(dá)某一支路的根節(jié)點(diǎn).

第4環(huán)節(jié)的目的是確定并更新所有臨時(shí)標(biāo)記的最終標(biāo)記.全部等價(jià)對(duì)合并操作結(jié)束后，形成并查集森林.對(duì)并查集森林進(jìn)行基于PH算法[16]的Find運(yùn)算，按由大到小順序進(jìn)行臨時(shí)標(biāo)記的根節(jié)點(diǎn)搜索，并進(jìn)行最終路徑壓縮操作，將每一臨時(shí)標(biāo)記的父節(jié)點(diǎn)標(biāo)記號(hào)置為其所屬并查集樹根節(jié)點(diǎn)標(biāo)記號(hào).二次掃描RVector，賦予各游程最終標(biāo)記號(hào).對(duì)于游程R，其最終標(biāo)記為：R·Label←A[R·Label].

3 實(shí)驗(yàn)結(jié)果分析

測(cè)試所用PC機(jī)配置如下：CPU為Intel Core(TM)2 Quad，主頻2.66 GHz，內(nèi)存3.0 GB，操作系統(tǒng)為 Windows XP.算法均用Pascal語言實(shí)現(xiàn).實(shí)驗(yàn)圖像含隨機(jī)圖像與真實(shí)圖像兩類.隨機(jī)圖像尺寸為1 024×1 024，按從1×1到10×10的10種粒度，分別隨機(jī)生成前景像素比例范圍為1%～99%的二值圖像序列(見圖3).真實(shí)圖像源自南加州大學(xué)信號(hào)圖像處理研究所的SIPI圖庫[17]，在SIPI兩個(gè)子庫Textures與Aerials中，各選取了25幅尺寸均為1 024×1 024的圖像.應(yīng)用Otsu算法對(duì)圖像進(jìn)行二值化，采用取多次重復(fù)運(yùn)算均值的方式獲取相應(yīng)運(yùn)算環(huán)節(jié)的執(zhí)行時(shí)間.

圖3 前景像素比例為50%的不同粒度隨機(jī)圖像

Fig.3 Random images with a percentage of object pixels 50 %at different granularities

為檢驗(yàn)FRL算法性能，同時(shí)觀察各環(huán)節(jié)占整體執(zhí)行時(shí)間的比重，首先對(duì)整體算法各環(huán)節(jié)獨(dú)立進(jìn)行執(zhí)行時(shí)間測(cè)試實(shí)驗(yàn)，這需要在第2環(huán)節(jié)生成等價(jià)對(duì)表，在第3環(huán)節(jié)對(duì)等價(jià)表進(jìn)行批處理.根據(jù)測(cè)試結(jié)果，第4環(huán)節(jié)耗時(shí)量級(jí)一般遠(yuǎn)小于其他環(huán)節(jié)，故將第3、第4環(huán)節(jié)納為一個(gè)環(huán)節(jié)進(jìn)行測(cè)試.實(shí)驗(yàn)同時(shí)測(cè)試了RL算法，并與FRL進(jìn)行比對(duì).5×5粒度隨機(jī)圖像序列不同前景像素比例下的測(cè)試結(jié)果如圖4所示，真實(shí)圖像測(cè)試結(jié)果如表1所示.

表1 真實(shí)圖像測(cè)試中各環(huán)節(jié)執(zhí)行時(shí)間的最大值、均值與最小值

Table 1 Maximum，mean and minimum execution times of diffe-rent algorithm modules for real images

圖庫表征參數(shù)執(zhí)行時(shí)間/msRSRLFRLRemSP+FindTextures最大值12.251.14.01.6均值7.715.11.50.7最小值2.92.40.30.004Aerials最大值10.130.63.01.7均值8.317.82.01.1最小值7.411.51.60.005

由圖4及表1可以看出，傳統(tǒng)游程標(biāo)記算法模式下，RL環(huán)節(jié)較為耗時(shí)，運(yùn)行時(shí)間隨游程數(shù)量的增加呈指數(shù)級(jí)增長；RS環(huán)節(jié)次之，但其耗時(shí)與RL屬同一數(shù)量級(jí)；并查集運(yùn)算環(huán)節(jié)(RemSP+Find)耗時(shí)最少，一般情況下要比RL與RS至少低一個(gè)數(shù)量級(jí).應(yīng)用FRL算法替代RL算法，取得了非常理想的結(jié)果，近似鏈?zhǔn)降谋葘?duì)方式使得游程標(biāo)記環(huán)節(jié)計(jì)算耗時(shí)大幅度降低，降為與并查集運(yùn)算環(huán)節(jié)同一量級(jí).由圖4可以看出，隨著隨機(jī)圖像前景像素比的增加，雖然游程數(shù)量呈二次曲線形式變化，但FRL曲線仍保持了良好的線性.

圖4 隨機(jī)圖像序列前景像素比例變化時(shí)游程標(biāo)記信息與各環(huán)節(jié)執(zhí)行時(shí)間

Fig.4 Execution times of the every algorithm module and the run-length labeling information versus object pixels percentage of random image sequences

將整體算法(RS+FRL+ RemSP+Find)與RTS、SAUF算法進(jìn)行了計(jì)算耗時(shí)比對(duì).RTS與SAUF是CCL二次掃描算法中較為高效的代表性算法.RTS以游程為基本處理單元，以傳統(tǒng)RL方法進(jìn)行游程搜索，以數(shù)組式鏈表的方式進(jìn)行等價(jià)標(biāo)記合并，每次合并都對(duì)被合并鏈表中的標(biāo)記進(jìn)行一次最終標(biāo)記更新操作；SAUF算法則以像素為基本處理單元，應(yīng)用決策樹算法快速進(jìn)行像素的近鄰搜索、標(biāo)記與等價(jià)對(duì)生成操作，應(yīng)用優(yōu)化的并查集算法進(jìn)行等價(jià)標(biāo)記處理.隨機(jī)圖像與真實(shí)圖像的比對(duì)結(jié)果分別如圖5、表2所示.

圖5 隨機(jī)圖像序列前景像素比例變化時(shí)各CCL算法執(zhí)行時(shí)間對(duì)比

Fig.5 Comparative execution times of different CCL algorithms versus object pixels percentage of random image sequences

表2 真實(shí)圖像測(cè)試中各CCL算法執(zhí)行時(shí)間的最大值、均值與最小值

Table 2 Maximum，mean and minimum execution times of different CCL algorithms for real images

圖庫表征參數(shù)執(zhí)行時(shí)間/msRTSSAUFRS+FRL+RemSP+FindTextures最大值70.617.617.3均值 21.612.39.1最小值3.52.92.5Aerials最大值48.916.516.4均值 29.014.211.7最小值9.912.05.9

由圖5可以看出，對(duì)于RTS算法，基于 RL的游程搜索耗時(shí)隨游程數(shù)量增長以二次曲線形式急劇增加；在等價(jià)標(biāo)記處理階段，數(shù)組式鏈表長度的不斷增長降低了后續(xù)等價(jià)對(duì)的處理效率.故隨著游程數(shù)量與等價(jià)對(duì)數(shù)量的增加，RTS算法執(zhí)行效率明顯下降.SAUF算法則相對(duì)比較穩(wěn)定，決策樹算法的應(yīng)用使得其在圖像連通情況較為復(fù)雜的情況下，搜索與標(biāo)記效率往往要高于基于游程的RS+RL算法.圖5同時(shí)表明，等價(jià)標(biāo)記處理階段中，在等價(jià)對(duì)數(shù)量較大情況下，經(jīng)路徑壓縮優(yōu)化的并查集算法比RTS數(shù)組式鏈表合并方法具有更好的魯棒性.

文中算法在游程標(biāo)記階段應(yīng)用FRL算法替代傳統(tǒng)RL算法，在等價(jià)標(biāo)記處理階段則采用了效率較高的RemSP并查集算法，這兩個(gè)環(huán)節(jié)均優(yōu)于RTS；與SAUF比較，雖然在等價(jià)標(biāo)記處理環(huán)節(jié)均采用了并查集優(yōu)化算法，但在單元搜索與標(biāo)記階段， FRL對(duì)該環(huán)節(jié)執(zhí)行效率的大幅度提升使得 RS+FRL方法總體上一般要優(yōu)于SAUF中的決策樹算法模式.由表2中的統(tǒng)計(jì)數(shù)據(jù)也可以看出，文中算法明顯優(yōu)于RTS算法，總體上略優(yōu)于SAUF算法.

4 結(jié)論

(1)FRL算法省去了行間游程不必要的后續(xù)比對(duì)，使得比對(duì)形式接近于鏈?zhǔn)?，時(shí)間復(fù)雜度由傳統(tǒng)RL算法的O(mn)降為O(m+n-1)，執(zhí)行時(shí)間降為與并查集運(yùn)算環(huán)節(jié)同一量級(jí).

(2)整體算法的性能明顯優(yōu)于RTS算法，總體上略優(yōu)于SAUF算法.

[1] HARALICK R M，SHAPIRO L G.Computer and robot vision(Volume 1) [M].Boston: Addison Wesley，1992.

[2] SUZUKI K，HORIBA I，SUGIE N.Linear-time connected-component labeling based on sequential local operations [J].Computer Vision & Image Understanding，2003，89(1): 1- 23.

[3] ROSENFELD A，PLATZ J.Sequential operator in digital pictures processing [J].Journal of ACM，1966,13(4):471- 494.

[4] LACASSAGNE L，ZAVIDOVIQUE B.Light speed labeling: efficient connected component labeling on RISC architectures [J].Journal of Real Time Image Processing,2011，6(2):117- 135.

[5] HE L，CHAO Y，SUZUKI K.A run-based two-scan labeling algorithm [J].IEEE Transactions on Image Processing，2008，17(5): 749- 756.

[6] FIORIO C，GUSTEDT J.Two linear time union-find stra-tegies for image processing [J].Theoretical Computer Science,1996,154(2):165- 181.

[7] WU K S，OTOO E，SUZUKI K.Optimizing two-pass connected component labeling algorithms [J].Pattern Analysis and Applications，2009，12(2): 117- 135.

[8] SOH Y，ASHRAF H，HAE Y，et al.A hybrid approach to parallel connected component labeling using cuda [J].International Journal of Signal Processing Systems，2013,1(2):130- 135.

[9] GUPTA S，PALSETIA D，PATWARY MMA，et al.A new parallel algorithm for two-pass connected component labeling [J].Parallel & Distributed Processing Symposium Wokshops,2014,778(1):1355- 1362.

[10] GHARASUIE MM，GAFFARI A.An efficient run-based method for connected component labeling [C]∥9th Iranian Conference on Machine Vision and Image Processing(ICMVIP 2015).Tehran:Shahid Beheshti University，2015:100- 104.

[11] CHANG W Y，CHIU C C，Yang J H. Block-based connected-component labeling algorithm using binary decision trees [J].Sensors，2015，15(9):23763- 23787.

[12] 牛連強(qiáng)，彭敏，孫忠禮，等.利用游程集合的標(biāo)號(hào)傳播實(shí)現(xiàn)快速連通域標(biāo)記 [J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2015 (1) :128- 135.

NIU Lian-qiang，PENG Min，SUN Zhong-li,et al.Fast connected components labeling by propagating labels of run sets [J].Journal of Computer-Aided Design & Computer Graphic，2015 (1) :128- 135.

[13] CHANG F，CHEN C.A linear-time component-labeling algorithm using contour tracing technique [J].Computer Vision and Image Understanding，2004,93(2):206- 220.

[14] JEONG J W ，LEE G B ，LEE M J，et al.A single-pass connected component labeler without label merging period [J].Journal of Signal Processing Systems,2016,84(2):211- 223.

[15] 馮海文，牛連強(qiáng)，劉曉明.高效的一遍掃描式連通區(qū)域標(biāo)記算法 [J].計(jì)算機(jī)工程與應(yīng)用，2014，50(23)：31- 35.

FENG Hai-wen，NIU Lian-qiang，LIU Xiao-ming.Efficient one-scan algorithm for labeling connected component [J].Computer Engineering and Applications，2014，50(23)：31- 35.

[15] CABARET L，LACASSAGNE L.What Is the world’s fastest connected component labeling [C]∥IEEE Workshop on Signal Processing Systems(SiPS 2014).Belfast:IEEE，2014:1- 6.

[16] PATWARY M M A，BLAIR J，MANNE F.Experiments on union-find algorithms for the disjoint-set data structure [C]∥International Conference on Experimental Algorithms.Naples:Springer,2010:411- 423.

[17] Signal and Image Processing Institute，USC Viterbi.USI-SIPI image database [EB/OL].(2010- 12- 22)[2016- 06- 25].http:∥sipi.usc.edu/services/database/index.html.

AFastRun-BasedTwo-PassAlgorithmforConnectedComponentsLabeling

LYUChang-kuiXUYanLUOBing-xin

(College of Mechanical and Electrical Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, Jiangsu, China)

In order to improve the calculation efficiency of connected component labeling (CCL) algorithms of binary images, firstly, an algorithm named FRL, which optimizes the conventional overlapping runs detection algorithm for run-based two-pass labeling algorithms, is proposed. Secondly, a general algorithm on the basis of FRL and union find is introduced. Then, some experiments are carried out to verify the computational efficiency of FRL. Finally, a comparative analysis is made between the general algorithm and other two typical two-pass CCL algorithms (namely RTS and SAUF). The results demonstrate that, as FRL saves unnecessary subsequent connectivity checks on runs between adjacent rows, the connectivity detection process is optimized into a chain-like mode, the calculation efficiency of run length labeling process improves greatly, the time complexity reduces from conventionalO(mn) toO(m+n-1), and the execution time decreases to the same level as the union find algorithm module. Moreover, it is found that the proposed general algorithm greatly outperforms RTS but is slightly better than SAUF in general.

connected component labeling; two-pass algorithm; connectivity detection algorithm; run length labeling; union find

2016- 11- 10

國家自然科學(xué)基金資助項(xiàng)目(51375238)

*Foundationitem： Supported by the National Natural Science Foundation of China(51375238)

呂常魁(1971-)，男，博士，副教授，主要從事機(jī)器視覺及其工業(yè)檢測(cè)研究.E-mail:maillck@nuaa.edu.cn

1000- 565X(2017)07- 0084- 06

TP 391

10.3969/j.issn.1000-565X.2017.07.012