一種基于“弦”的邊界跟蹤算法

劉兆財(cái),王東興,田洪志,林建鋼

(煙臺(tái)大學(xué)機(jī)電汽車(chē)工程學(xué)院,山東 煙臺(tái) 264005)

在一個(gè)基于輪廓特征的模式識(shí)別[1]系統(tǒng)中,需要邊界像素點(diǎn)的有序排列,才能從中提取目標(biāo)通用形狀特征。邊界跟蹤[2-4]就是來(lái)完成這項(xiàng)工作的,是數(shù)字圖像處理技術(shù)中用來(lái)提取形狀信息的一種重要方法,是基于輪廓形狀匹配的一個(gè)重要步驟。

一般在獲取圖像中目標(biāo)輪廓、質(zhì)心、不變矩等操作前都會(huì)對(duì)二值圖像進(jìn)行連通域劃分,即對(duì)二值圖像進(jìn)行連通域標(biāo)記[5-6],而在連通域標(biāo)記算法中,目前應(yīng)用較廣、速度極快的是基于游程編碼的連通域標(biāo)號(hào)算法[7-9],本文在詳細(xì)分析了此種標(biāo)號(hào)算法基礎(chǔ)上,提出了一種基于“弦”的邊界跟蹤算法。

傳統(tǒng)的邊界跟蹤算法有蟲(chóng)隨法[10]、光柵掃描法[11]和八鄰域邊界跟蹤法[12]等。蟲(chóng)隨法和光柵掃描法都要多次重復(fù)才能得到結(jié)果,由于重復(fù)次數(shù)需要人為確定,因此跟蹤結(jié)果未必準(zhǔn)確。八鄰域跟蹤算法性能相對(duì)較好,因此提取給定圖像邊界時(shí)用到的頻率較高,然而八鄰域跟蹤算法需要掃描當(dāng)前邊界點(diǎn)的八鄰域來(lái)判斷下一邊界點(diǎn),并且邊界上的每個(gè)點(diǎn)都要進(jìn)行八鄰域判斷,判斷總次數(shù)多,搜索冗余也較多。當(dāng)然,一些學(xué)者也提出了一些改進(jìn)算法,如崔鳳魁等[13]提出目標(biāo)鄰域點(diǎn)的邊界點(diǎn)搜索方法, 該算法從上一邊界點(diǎn)的下一鄰域點(diǎn)開(kāi)始搜索, 將搜索方向減至7個(gè),但仍有大量搜索冗余未被去除。王福生等[14]將搜索方向減至最多5次,比崔鳳魁等[13]提出的目標(biāo)鄰域點(diǎn)邊界點(diǎn)搜索算法的搜索冗余少。但這些改進(jìn)的算法只是在八鄰域的基礎(chǔ)上進(jìn)行的算法優(yōu)化,依然需要對(duì)每個(gè)邊界點(diǎn)進(jìn)行八鄰域的判斷,所需判斷邊界點(diǎn)總次數(shù)仍然較多,并且邊界上的每個(gè)點(diǎn)都要進(jìn)行掃描。

當(dāng)連通域采用游程編碼[15]表示時(shí),若要采用上述傳統(tǒng)算法進(jìn)行邊界跟蹤,則還需要將用游程編碼表示的連通域轉(zhuǎn)換為用光柵圖像表示的連通域,進(jìn)一步增加了從連通域獲取其邊界輪廓的處理時(shí)間。而本文算法則是直接根據(jù)游程編碼方法的特性進(jìn)行下一邊界點(diǎn)的判斷,所以對(duì)目標(biāo)輪廓進(jìn)行邊界跟蹤時(shí),所需進(jìn)行邊界點(diǎn)判斷的總次數(shù)相較于傳統(tǒng)的邊界跟蹤算法就有了很大的降低,而且無(wú)需逐像素掃描每一個(gè)邊界點(diǎn),此時(shí)邊界跟蹤效率也得到了明顯的提高。本文算法可以在快速標(biāo)記連通域后再進(jìn)行快速的目標(biāo)輪廓提取,而無(wú)需在連通域標(biāo)記后先將連通域轉(zhuǎn)換為光柵圖像形式,再使用其他的傳統(tǒng)邊界跟蹤算法來(lái)提取目標(biāo)物體的輪廓,此時(shí)目標(biāo)物體的輪廓提取效率有了極大的提升。

1 RLRegion連通域

經(jīng)過(guò)游程編碼標(biāo)記后的連通域,在這里將其稱(chēng)為RLRegion連通域,而此RLRegion連通域中的基本描述單元?jiǎng)t用弦(Chord)來(lái)描述(圖1),很顯然,每個(gè)弦的2個(gè)端點(diǎn)一定在域的邊界上,但中間點(diǎn)也可能在域的邊界上,圖1中部與其上多個(gè)弦或其下多個(gè)弦相鄰接的弦,一行中可能有一個(gè)弦,也有可能有多個(gè)弦。

圖1 由弦所描述的RLRegion連通域Fig.1 A RLRegion connected region described by chords

當(dāng)連通域改為用弦描述時(shí),根據(jù)弦上的像素列坐標(biāo)的連續(xù)性,很多情況下就不需要逐像素搜索邊界上的像素。

2 算法描述

2.1 獲得RLRegion連通域

對(duì)二值圖像進(jìn)行基于游程編碼的連通域標(biāo)號(hào)處理時(shí),取一目標(biāo)連通域,在逐行掃描圖像的過(guò)程中,將每一行中連續(xù)的白色像素組成的序列作為一個(gè)弦(Chord),并記下它的起始列坐標(biāo)、終止列坐標(biāo)以及它所在行坐標(biāo)。其中弦的數(shù)據(jù)結(jié)構(gòu)定義為

struct WDChord {

Inty; //行坐標(biāo)

Intxb; //起始列坐標(biāo)

Intxe; //終止列坐標(biāo)

};

假設(shè)RLRegion連通域由N個(gè)弦組成。

R={Ci=(xbi,xei,yi)|i∈[0,N-1]}。

(1)

每個(gè)弦都有其對(duì)應(yīng)的序號(hào),弦序號(hào)范圍由0到(N-1)。在RLRegion連通域中,弦序號(hào)從左到右,從上到下依次排列,一行中可能有一個(gè)弦序號(hào),也可能有多個(gè)弦序號(hào),每行中的第一個(gè)弦的序號(hào)在這里稱(chēng)其為首弦序號(hào)。

2.2 獲取RLRegion連通域的行信息

連通域行信息的數(shù)據(jù)結(jié)構(gòu)定義如下:

struct ConnRegInfo {

int nYFirstRow;

int nYLastRow;

int* pRowSCN;

uchar* pChordF;

};

其中:nYFirstRow為連通域第一行y坐標(biāo),nYLastRow為連通域最后一行y坐標(biāo),pRowSCN用來(lái)存儲(chǔ)每一行上首弦的序號(hào),pChordF則用來(lái)存儲(chǔ)每一弦的首端標(biāo)記。

2.3 初始化首端標(biāo)記

申請(qǐng)存儲(chǔ)空間存儲(chǔ)連通域中每一個(gè)弦的首端標(biāo)記,并將其全部初始化為0。每一個(gè)弦的首端即首像素在被搜索記錄后,就將其首端標(biāo)記賦值為1。當(dāng)搜索完外層輪廓后,若存在內(nèi)層輪廓,內(nèi)層輪廓中肯定有弦的首端未進(jìn)行標(biāo)記的,此時(shí)通過(guò)首端標(biāo)記便可進(jìn)行內(nèi)層輪廓的搜索。

2.4 搜索RLRegion連通域外邊界及內(nèi)邊界

搜索外邊界時(shí)取序號(hào)為0的弦為首弦,記為弦C0(xb0,xe0,y0)，xb0為A的首像素的列坐標(biāo)，xe0為其尾像素的列坐標(biāo)，y0為其行坐標(biāo)。

為了按逆時(shí)針?lè)较蝽樞蚺帕型獠窟吔缇€上的像素,或沿順時(shí)針?lè)较蚺帕袃?nèi)部邊界線上的像素,弦的搜索方向分為2個(gè),D1:沿著每條弦的首端向下(行地址變大),D2:沿著每條弦的尾端向上(行地址變小),為簡(jiǎn)單起見(jiàn),規(guī)定搜索任何一條邊界線時(shí)起始搜索方向均為D1。

為了應(yīng)用下述方法,記C0(xb0,xe0,y0)=A(xbA,xeA,yA)。

2.4.1 按D1法搜索 首先判斷當(dāng)前弦下一行的y坐標(biāo)是否超出連通域最大的y坐標(biāo),若是,判斷下一行上無(wú)鄰接弦,否則,需要從左側(cè)遍歷下一行上是否有當(dāng)前弦的鄰接弦。

圖2為相鄰2行上2弦鄰接的極限情況,記弦B為(xbB,xeB,yB),則相鄰2行上弦A與B不鄰接的條件為(xeBxeA+1)。

圖2 相鄰2行上2弦鄰接的極限情況Fig.2 The limiting case of the adjacency of two chords on two adjacent rows

如圖3,若當(dāng)前弦A的下一行上沒(méi)有與其鄰接的弦,說(shuō)明弦A上的像素均為邊界像素,記錄A的首像素的坐標(biāo)(xbA,yA),要標(biāo)記弦A的首端已搜索即對(duì)弦A進(jìn)行首端標(biāo)記,避免搜索內(nèi)部邊界時(shí)該弦的首像素被作為起始像素,其尾端會(huì)在下次搜索時(shí)處理,當(dāng)前弦序號(hào)不變,搜索方向變?yōu)镈2,按照D2法繼續(xù)搜索。

圖3 A的下一行上沒(méi)有與其鄰接的弦Fig.3 There is no adjacent chord on the next line of A

當(dāng)前弦A的下一行有與A鄰接的弦B,可分為以下幾種情況:

(a) 弦B的首像素的列坐標(biāo)大于A的首像素的列坐標(biāo)加1,即xbB>xbA+1時(shí)。

如圖4,這種情況下,從A的首像素開(kāi)始至少有2個(gè)邊界像素(如下方黑色像素塊),按順序記錄黑色像素塊的2個(gè)端像素的坐標(biāo):(xbA,yA)和(xbB-1,yA),當(dāng)前弦改為弦B,搜索方向不變。

圖4 xbB>xbA+1Fig.4 xbB>xbA+1

(b) 當(dāng)xbB=xbA或xbB=xbA+1時(shí),如圖5,這種情況下,A的首像素為邊界像素,記錄其坐標(biāo)(xbA,yA),當(dāng)前弦改為弦B,搜索方向不變。

圖5 xbB=xbA或xbB=xbA+1Fig.5 xbB=xbA or xbB=xbA+1

(c) 當(dāng)xbB=xbA-1時(shí),并且在A的同一行上A的左側(cè)沒(méi)有弦與B鄰接,如圖6,A的首像素為邊界像素,記錄其坐標(biāo)(xbA,yA),當(dāng)前弦改為弦B,搜索方向不變。

圖6 xbB=xbA-1，并且A的左側(cè)沒(méi)有弦與B鄰接Fig.6 xbB=xbA-1, and the left side of A has no chord adjacent to B

(d) 當(dāng)xbB

圖7 xbB

(e) 在A的同一行上A的左側(cè)有弦C(xbC,xeC,yC)與B鄰接，并且xeC=xbA-2，如圖8,A的首像素為邊界像素,記錄其坐標(biāo)(xbA,yA),弦B上列坐標(biāo)為xbA-1的像素也是邊界像素,記錄其坐標(biāo)(xbA-1,yB),當(dāng)前弦改為弦C,搜索方向改為D2。

圖8 A的左側(cè)有弦C與B鄰接并且xeC=xbA-2Fig.8 The left side of A has chord C adjacent to B, and xeC=xbA-2

(f)在A的同一行上A的左側(cè)有弦C(xbC,xeC,yC)與B鄰接，并且xeC

圖9 A的左側(cè)有弦C與B鄰接并且xeC

(a)—(f)情況下均要標(biāo)記弦A的首端已搜索即對(duì)弦A進(jìn)行首端標(biāo)記,避免搜索內(nèi)部邊界時(shí)這些弦的首像素被作為起始像素。

2.4.2 按D2法搜索 首先判斷當(dāng)前弦上一行的y坐標(biāo)是否小于連通域最小的y坐標(biāo),若是,判斷上一行上無(wú)鄰接弦,否則,需要從右側(cè)遍歷上一行上是否有鄰接弦。

如圖10,若當(dāng)前弦A的上一行上沒(méi)有與A鄰接的弦,說(shuō)明弦A上的像素均為邊界像素,記錄A的尾像素的坐標(biāo)(xeA,yA),要標(biāo)記弦A的尾端已搜索,避免搜索內(nèi)部邊界時(shí)該弦的尾像素被作為起始像素,其首端會(huì)在下次搜索時(shí)處理,當(dāng)前弦不變,搜索方向變?yōu)镈1,按照D1法繼續(xù)搜索。

圖10 A的上一行上沒(méi)有與其鄰接的弦Fig.10 There is no adjacent chord on top of A

當(dāng)前弦A的上一行有與A鄰接的弦,可分為以下幾種情況:

(a) 弦B的尾像素的列坐標(biāo)小于A的尾像素的列坐標(biāo)減1,即xeB

如圖11,這種情況下,從A的尾像素開(kāi)始至少有2個(gè)邊界像素,按順序記錄其2個(gè)端像素的坐標(biāo)(xeA,yA)和(xeB+1,yA),當(dāng)前弦改為弦B,搜索方向不變。

圖11 xeB

(b) 當(dāng)xeB=xeA或xeB=xeA-1時(shí)，如圖12，A的尾像素為邊界像素，記錄其坐標(biāo)(xeA,yA)，當(dāng)前弦改為弦B，搜索方向不變。

圖12 xeB=xeA或xeB=xeA-1Fig.12 xeB=xeA or xeB=xeA-1

(c) 當(dāng)xeB=xeA+1時(shí)，并且在A的同一行上A的右側(cè)沒(méi)有弦與B鄰接，如圖13，A的尾像素為邊界像素，記錄其坐標(biāo)(xeA,yA)，當(dāng)前弦改為弦B，搜索方向不變。

圖13 xeB=xeA+1并且A的右側(cè)沒(méi)有弦與B鄰接Fig.13 xeB=xeA+1, and the right side of A has no chord adjacent to B

(d)xeB>xeA+1，并且在A的同一行上A的右側(cè)沒(méi)有弦與B鄰接，如圖14，A的尾像素為邊界像素，記錄其坐標(biāo)(xeA,yA)，B上至少有2個(gè)邊界像素，按順序記錄其2個(gè)端像素的坐標(biāo)：(xeA+1,yB)和(xeB,yB)。當(dāng)前弦改為弦B，搜索方向不變。注意：鄰接弦的尾像素下次搜索時(shí)會(huì)被重復(fù)記錄。

圖14 xeB>xeA+1并且A的右側(cè)沒(méi)有弦與B鄰接Fig.14 xeB>xeA+1, and the right side of A has no chord adjacent to B

(e) 在A的同一行上A的右側(cè)有弦C(xbC,xeC,yC)與B鄰接，并且xbC=xeA+2，如圖15，A的尾像素為邊界像素，記錄其坐標(biāo)(xeA,yA)，弦B上列坐標(biāo)為xeA+1的像素也是邊界像素，記錄其坐標(biāo)(xeA+1,yB)，當(dāng)前弦改為弦C，搜索方向改為D1。

圖15 A的右側(cè)有弦C與B鄰接并且xbC=xeA+2Fig.15 The right side of A has chord C adjacent to B, and xbC=xeA+2

(f) 在A的同一行上A的右側(cè)有弦C(xbC,xeC,yC)與B鄰接，并且xbC>xeA+2，如圖16，A的尾像素為邊界像素，記錄其坐標(biāo)(xeA,yA)，弦B上列坐標(biāo)在xeA+1與xbC-1之間的像素也是邊界像素，按順序記錄2個(gè)端像素的坐標(biāo)：(xeA+1,yB)和(xbC-1,yB)，當(dāng)前弦改為弦C，搜索方向變?yōu)镈1。

圖16 A的右側(cè)有弦C與B鄰接并且xbC>xeA+2Fig.16 The right side of A has chord C adjacent to B, and xbC>xeA+2

2.4.3 搜索外邊界線 根據(jù)當(dāng)前搜索方向按照D1法或D2法搜索邊界上的每一個(gè)弦，直到當(dāng)前弦再次變回初始弦C0為止，若當(dāng)前搜索方向不是D1，則還需要記錄下弦C0的尾像素的坐標(biāo)。

2.4.4 搜索一條內(nèi)部邊界線 當(dāng)此連通域外邊界線找到后，接著遍歷各弦的首端標(biāo)記，找到第一個(gè)首端未標(biāo)記的弦作為首弦，初始搜索方向?yàn)镈1，此時(shí)，按照搜索外邊界線的方法搜索邊界上的每一個(gè)弦，找到一條內(nèi)部邊界線。

2.4.5 搜索所有內(nèi)部邊界線 最后按照上述找到一條內(nèi)部邊界線的方法找到所有內(nèi)部邊界線，此時(shí)所有弦的首端均完成標(biāo)記，即此連通域的所有內(nèi)外邊界線均已搜索完成。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)說(shuō)明

硬件條件為Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz；軟件環(huán)境為Visual Studio 2013×32 Debug模式和OpenCV3.0。

圖17為原始的二值圖，該圖片大小為504 pixel×356 pixel。圖18為文獻(xiàn)[14]算法的邊界跟蹤結(jié)果。圖19為采用本文算法的邊界跟蹤結(jié)果。效率實(shí)驗(yàn)采用4組每組10張大小相同的二值圖像，1—4組分別對(duì)應(yīng)的圖片大小依次為504 pixel×356 pixel、500 pixel×500 pixel、30 pixel×19 pixel、11 pixel×11 pixel，運(yùn)用2種算法分別計(jì)算每張圖片的時(shí)間，取每組的平均時(shí)間，其中2種算法所執(zhí)行的對(duì)象都是經(jīng)過(guò)游程編碼標(biāo)記后的目標(biāo)連通域。

圖17 原二值圖Fig.17 Original binary image

圖18 文獻(xiàn)[14]算法的邊界跟蹤結(jié)果Fig.18 Boundary tracking result of Ref.[14]

3.2 結(jié)果與分析

3.2.1 輪廓跟蹤所存儲(chǔ)的點(diǎn)集 在上方的邊界跟蹤結(jié)果圖中，圖18繪制的是文獻(xiàn)[14]算法所得到的點(diǎn)集，圖19繪制的是本文算法跟蹤存儲(chǔ)的點(diǎn)集。若要得到點(diǎn)集對(duì)應(yīng)的完整輪廓，可以通過(guò)OpenCV中的drawContours()函數(shù)進(jìn)行繪制，該函數(shù)能將點(diǎn)與點(diǎn)之間的連線按照一定的拓?fù)潢P(guān)系來(lái)繪制，圖20為使用圖19中的點(diǎn)集繪制得到的輪廓圖。

圖19 本文算法邊界跟蹤結(jié)果Fig.19 Boundary tracking result of the proposed algorithm

圖20 drawContours()函數(shù)所繪制的輪廓Fig.20 The outline drawn by drawContours()

由邊界跟蹤結(jié)果圖可以看出,圖18的邊界跟蹤是將輪廓上的每個(gè)點(diǎn)都進(jìn)行了掃描存儲(chǔ),而圖19本文算法邊界跟蹤所掃描存儲(chǔ)的點(diǎn)為弦的端像素點(diǎn),且處于邊界上的弦的邊界點(diǎn)并未全部進(jìn)行掃描存儲(chǔ),從點(diǎn)集可以看出,本文算法要比八鄰域邊界跟蹤算法的搜索范圍小。

3.2.2 跟蹤效率 表1為2種不同算法運(yùn)行時(shí)間的比較。

表1 2種不同算法的運(yùn)行時(shí)間比較Tab.1 Execution time of two different algorithms s

由表1中的數(shù)據(jù)可以得到基于“弦”的邊界跟蹤算法比文獻(xiàn)[14]算法提高的效率,效率的公式為

η=(T2-T1)/T1。

(2)

由式(2)可以得到表2,從表2中可以得到本文算法的運(yùn)行時(shí)間效率要比文獻(xiàn)[14]算法的運(yùn)行時(shí)間效率平均提高了大約69.08%。

表2 效率提高Tab.2 Efficiency improvement table %

從已得的實(shí)驗(yàn)結(jié)果分析可知,組成RLRegion連通域中的“弦”越長(zhǎng),“長(zhǎng)弦”的占比越大,并且連通域邊界越規(guī)則,那么本文算法所提高的效率就越高。反之,連通域越小,“弦”越短,那么本文算法所提高的效率就不夠顯著。

4 結(jié)束語(yǔ)

本文在已有的基于游程編碼的連通域標(biāo)記基礎(chǔ)上,提出了一種基于“弦”的邊界跟蹤算法。該算法是專(zhuān)門(mén)針對(duì)由“弦”組成的RLRegion連通域進(jìn)行邊界跟蹤的特殊算法,在同等背景環(huán)境下,本文算法所耗時(shí)間要比八鄰域邊界跟蹤算法所耗時(shí)間少了很多,效率提高較為顯著。當(dāng)然本文算法也有不足之處,本文算法所使用的環(huán)境必須是在RLRegion連通域的基礎(chǔ)上才能使用,即在使用本文算法之前,要先對(duì)二值圖像進(jìn)行基于游程編碼的連通域標(biāo)記處理,使其變成由弦組成的連通域。盡管有這些不足,但連通域標(biāo)記又是幾乎所有二值圖像分析的基礎(chǔ),若要針對(duì)目標(biāo)連通域進(jìn)行輪廓提取等操作,需先對(duì)圖像進(jìn)行連通域標(biāo)記處理。而目前連通域標(biāo)記處理的算法中,基于游程編碼的連通域標(biāo)記算法是應(yīng)用較廣、效率最高的標(biāo)記算法,所以本文算法具有廣闊的應(yīng)用場(chǎng)景。