一種八鄰域圖像邊界追蹤改進(jìn)算法

胡晉山，康建榮，張 琪，劉鵬程，朱銘達(dá)

(1.江蘇師范大學(xué)地理測繪與城鄉(xiāng)規(guī)劃學(xué)院，江蘇 徐州 221116；2.華中師范大學(xué)城市與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079；3.江蘇師范大學(xué)科文學(xué)院，江蘇 徐州 221116)

利用形態(tài)學(xué)方法對圖像進(jìn)行邊界檢測，只是在圖像中定位標(biāo)記出邊界點(diǎn)，為了自動提取各邊界線的坐標(biāo)序列，還需要對檢測后的邊界點(diǎn)進(jìn)行邊界追蹤[1]。傳統(tǒng)的邊界追蹤算法主要有Square跟蹤算法[2]、摩爾鄰域跟蹤算法[3]、徑向掃描算法[4]等，這些算法主要用于提取環(huán)形封閉邊界。其中Square跟蹤算法適用范圍較窄，無法跟蹤八鄰域圖形邊界；摩爾鄰域邊界追蹤算法考慮了圖形邊界的八鄰域關(guān)系，但由于其停止準(zhǔn)則的局限性，無法跟蹤大量的圖形輪廓；徑向掃描算法實(shí)質(zhì)上是一種新的在給定像素點(diǎn)的摩爾鄰域內(nèi)搜索邊界點(diǎn)的方法,其邊界追蹤停止準(zhǔn)則與摩爾鄰域邊界追蹤算法相同。邊界追蹤算法的難點(diǎn)在于如何確定跟蹤方向，較為經(jīng)典的算法有爬蟲法、光柵掃描法[1]、八鄰域追蹤算法[5]。其中爬蟲法和光柵掃描法都需要反復(fù)追蹤圖像局部區(qū)域，由于無法準(zhǔn)確計算重復(fù)跟蹤圖像次數(shù)，往往會使程序陷入死循環(huán)；八鄰域邊緣追蹤算法雖然能夠單次掃描圖像獲得目標(biāo)的輪廓，但無法識別較為狹窄的邊界重疊狀況，容易將多條重疊的邊緣線追蹤為單條邊緣線，或在重疊交叉處將單條邊緣線追蹤為多條邊緣線。當(dāng)前國內(nèi)外專家學(xué)者們也在不斷研究圖像邊緣線提取方法，石爽等[6]提出了雙層邊界區(qū)域生長的追蹤算法，實(shí)現(xiàn)對“厚”邊界及斷點(diǎn)處的邊界跟蹤，但是該算法時間復(fù)雜度較高；戴激光等[7]提出了一種鏈碼跟蹤與相位驗(yàn)證相結(jié)合的直線提取方法，該方法僅能在噪聲較小的光學(xué)圖像中實(shí)現(xiàn)直線的檢測；譚凱等[8]用雙閾值判別方法來提取地面激光點(diǎn)云圖像的非邊緣點(diǎn)、邊緣點(diǎn)與噪聲點(diǎn)；趙麗科[9]等提出基于鏈碼優(yōu)先級的直線提取算法，實(shí)現(xiàn)了圖像中物體邊界的直線快速提取。上述這些方法多是專門針對某些應(yīng)用領(lǐng)域而設(shè)計的算法，因此有一定的局限性。本文在分析經(jīng)典的邊界追蹤算法原理的基礎(chǔ)上，改進(jìn)基于八鄰域邊界追蹤算法，以解決邊界追蹤過程中邊界間斷、重疊、相鄰等特殊狀況，實(shí)現(xiàn)圖像邊界的自動提取。

1 八鄰域邊界追蹤改進(jìn)算法

1.1 八鄰域

當(dāng)進(jìn)行邊界追蹤搜索時，與當(dāng)前點(diǎn)所有方向相鄰接的像素點(diǎn)稱為該像素點(diǎn)的8個鄰接像素[10]，如圖1所示，設(shè)定目標(biāo)C右側(cè)平行點(diǎn)為0鄰域點(diǎn)，按逆時針方向?qū)肃徲螯c(diǎn)分別標(biāo)號為0、1、2、…、7。

圖1 八鄰域

1.2 基于八鄰域的邊界追蹤步驟

邊界追蹤算法包含以下3個基本步驟：①確定追蹤邊界的起始點(diǎn)[11]；②選取合適的鄰接點(diǎn)搜索機(jī)理，進(jìn)行邊界線像素點(diǎn)的追蹤及提取；③確定邊界線追蹤終止準(zhǔn)則。

1.2.1 確定邊界線起點(diǎn)

本文算法對二值圖像從頂端開始從左向右、從上至下逐行掃描，檢測到的第一個邊界點(diǎn)標(biāo)定為目標(biāo)邊界線的起點(diǎn)，并停止對圖像邊界線起始點(diǎn)的掃描。

1.2.2 搜索機(jī)理

如圖2所示，標(biāo)定當(dāng)前像素點(diǎn)為C，該像素點(diǎn)的前一邊界點(diǎn)為P，連接PC，并作PC的垂線將八鄰域分割為兩部分，這樣將邊界點(diǎn)的檢索范圍縮小了50%?；疑袼攸c(diǎn)為待檢測的八鄰域點(diǎn)，依據(jù)圖2中PC不同的方向，按順時針方向依次判斷其鄰域5個像素點(diǎn)是否為目標(biāo)邊界點(diǎn)，若搜索到某一像素點(diǎn)為目標(biāo)邊界點(diǎn)，則記錄該點(diǎn)為當(dāng)前邊界線的邊界點(diǎn)，并依據(jù)當(dāng)前像素點(diǎn)與前一個邊界點(diǎn)的位置關(guān)系繼續(xù)追蹤下一個邊界點(diǎn)。

1.2.3 終止準(zhǔn)則

(1) 環(huán)形邊界線追蹤終止判斷依據(jù)。如圖3所示，從像素值為1的邊界起點(diǎn)開始邊界線追蹤，順時針沿黑色虛線箭頭的灰色像素點(diǎn)的有序集合即為所要提取目標(biāo)邊界線，當(dāng)追蹤到像素值為2點(diǎn)，正確路徑應(yīng)該為①號實(shí)線箭頭指向，但是，若按②號實(shí)線箭頭指向追蹤，會追蹤到另一組邊界，因此，本方法約定，當(dāng)邊緣點(diǎn)追蹤至目標(biāo)邊界線起點(diǎn)的八鄰域范圍內(nèi)或正好回到起始點(diǎn)，且進(jìn)入方向與邊界線追蹤走勢相同時，停止目標(biāo)邊界線追蹤，環(huán)形邊界追蹤完成。

圖2 搜索機(jī)理

圖3 終止準(zhǔn)則(1)

(2) 非閉合邊界線終止準(zhǔn)則。如圖4所示，1點(diǎn)為目標(biāo)邊界線起始點(diǎn)，順時針追蹤至2點(diǎn)時，終止當(dāng)前邊界線追蹤，并重新返回起始點(diǎn)1，其順時針方向邊界線的第2個邊界點(diǎn)設(shè)為當(dāng)前邊界起始點(diǎn)的前一邊界點(diǎn)，按逆時針方向追蹤直至3點(diǎn)時，停止邊界線追蹤，并設(shè)置3點(diǎn)為此邊界線新的起點(diǎn)，結(jié)束非閉合邊界線的追蹤。

圖4 終止準(zhǔn)則(2)

1.3 整幅圖像邊界拓?fù)潢P(guān)系處理

當(dāng)追蹤一幅圖像中所有邊界線時還需要解決3個問題：首先是不同邊界線起始點(diǎn)的定位及標(biāo)記；然后正確追蹤邊界線，并獲得目標(biāo)邊界線的坐標(biāo)序列及邊界線類型；最后還需處理好邊界線的拓?fù)潢P(guān)系，確保不存在邊界線漏跟蹤和重復(fù)跟蹤的現(xiàn)象。由于像素是有寬度的，基于像素追蹤邊界時，需要考慮由像素組成的邊界之間的復(fù)雜關(guān)系，如孤島[12]、內(nèi)外邊界[13]等情況。

1.3.1 內(nèi)外邊界標(biāo)定

如圖5所示，圖5(a)為原始圖像，目視該區(qū)域有兩條邊界，一條為外邊界，一條為內(nèi)邊界。圖5(b)是在不標(biāo)定內(nèi)外邊界情況下，基于上文追蹤機(jī)理獲取的邊界，其中P1為外邊界追蹤起點(diǎn)，標(biāo)定為A的邊界線為外邊界；因此，當(dāng)從像素點(diǎn)P2點(diǎn)開始追蹤內(nèi)邊界時，只能檢測出孤點(diǎn)P2。為此本文借鑒了文獻(xiàn)[14]中依據(jù)3×3模板劃分邊界點(diǎn)類型，如圖6所示，像素值0、1與X分別表示非目標(biāo)區(qū)域點(diǎn)、目標(biāo)區(qū)域點(diǎn)及未知區(qū)域點(diǎn)，邊界點(diǎn)C分為三類，分別為：左端點(diǎn)(圖6(a))，右端點(diǎn)(圖6(b))，尖點(diǎn)(圖6(c)行尖點(diǎn)、圖6(d)列尖點(diǎn))。右端點(diǎn)和尖點(diǎn)均有可能成為內(nèi)邊界起始點(diǎn)，因此需要判定邊界點(diǎn)被檢索的次數(shù)。

圖5 內(nèi)外邊界標(biāo)定

本算法約定：①所有邊界起始點(diǎn)均標(biāo)識為未檢索點(diǎn)，此種情況只能檢索出一條外邊界線，如圖5(b)所示，忽略外邊界線內(nèi)的孤立點(diǎn)；②所有未被檢索過的右端點(diǎn)均可被默認(rèn)為內(nèi)邊界的起始點(diǎn)；③為避免尖點(diǎn)區(qū)域可能出現(xiàn)邊界重疊現(xiàn)象，標(biāo)志可檢索2次；④給予每條邊界不同的檢索標(biāo)志，若出現(xiàn)重復(fù)檢索且在不同邊界上，判定重疊，同一點(diǎn)檢索不能超出兩次，以此減少漏追蹤、重復(fù)追蹤現(xiàn)象。

1.3.2 孤 島

如圖7所示，圖7(a)為原始圖像；圖7(c)為正確的邊界追蹤方式，其中P1為邊界A的起始點(diǎn)，P2為邊界B的起始點(diǎn)；圖7(b)是基于上文邊界搜索機(jī)理追蹤的邊界線，在追蹤至灰色像素點(diǎn)A時，邊界追蹤走勢出現(xiàn)錯誤，將兩條邊界檢索為一條邊界，這種由于細(xì)小像素點(diǎn)連接的區(qū)域重疊稱為“孤島效應(yīng)”。

圖7 “孤島”

為解決孤島效應(yīng)，本算法基于Freeman鏈碼進(jìn)行判別[15]。為每條邊界設(shè)置特定的邊界標(biāo)志，當(dāng)一個像素點(diǎn)在同一條邊界追蹤過程中被追蹤2次，首先判定此點(diǎn)是否為起始點(diǎn)，若非起始點(diǎn)，則需判定點(diǎn)類型，若為尖點(diǎn)則可能出現(xiàn)為孤島現(xiàn)象；然后，依據(jù)尖點(diǎn)類型確定處理方式，若為行尖點(diǎn)，則回歸該像素點(diǎn)在該邊界出現(xiàn)的首次位置，并記錄其與前一邊界點(diǎn)的走向，若由左向右，則掩去該點(diǎn)的1、2、3鄰域點(diǎn)，從右向左則剔除該點(diǎn)的5、6、7鄰域的邊界點(diǎn)(如圖1所示)，繼續(xù)檢索；若為列尖點(diǎn)，同樣回歸該像素點(diǎn)首次出現(xiàn)的位置，記錄其與前一像素點(diǎn)的位置關(guān)系，并依據(jù)位置關(guān)系剔除相應(yīng)鄰域點(diǎn)，從該像素點(diǎn)開始重新檢索。該方法從重疊點(diǎn)處斷開被檢索邊界線，依據(jù)邊界線走向掩膜去掉部分干擾像素，進(jìn)而達(dá)到分離兩個邊界的目的。

2 試驗(yàn)驗(yàn)證

2.1 算法精度驗(yàn)證

試驗(yàn)選取MPEG7-CE(moving picture experts group)圖形庫中的4幅圖像(如圖8所示)進(jìn)行邊界提取測試，將本文算法與摩爾鄰域邊界追蹤算法所得結(jié)果進(jìn)行比較，并將兩種結(jié)果分別視為2個隨機(jī)矩陣，求解這2個矩陣的相關(guān)系數(shù)，結(jié)果見表1。從表1可以看出，相關(guān)系數(shù)接近于1，說明本文提出的算法是正確的。另外由于試驗(yàn)所選4個測試圖像相對簡單，本文算法計算效率稍高于摩爾鄰域邊界追蹤算法，時間效率差別為毫秒級。

圖8 MPEG7-CE圖形庫模板中的4幅圖像

表1 兩種算法結(jié)果比較

2.2 大范圍圖像邊界提取

本文選取美國國家冰雪數(shù)據(jù)中心免費(fèi)提供的北半球2014年9月14日的雪冰產(chǎn)品，空間分辨率為4 km的ASCII數(shù)據(jù)，時間分辨率為1 d，投影方式為極地方位投影，北極點(diǎn)為投影中心點(diǎn)。鑒于北地群島區(qū)域島嶼較多，冰塊與海岸、冰塊與冰塊之間的距離較短，邊緣線的拓?fù)潢P(guān)系較為復(fù)雜，因此本次試驗(yàn)以北地群島作為目視判別區(qū)域，裁剪得到圖像網(wǎng)格數(shù)量為181×181像素，如圖9(a)所示。

圖9 北地群島區(qū)域海岸線提取

2.2.1 北地群島區(qū)域海岸線提取

利用形態(tài)學(xué)邊緣檢測模型生成以陸地及陸地上積雪為前景色的水陸二值圖像(如圖9(b)所示)，然后運(yùn)用本文基于八鄰域邊界追蹤改進(jìn)算法提取了海岸線(如圖9(c)所示)，將圖9(c)與圖9(a)疊加，從目視解譯及邊界融合狀況發(fā)現(xiàn)與實(shí)際圖像一致，說明改進(jìn)后的八鄰域邊緣追蹤方法適用于大范圍具有復(fù)雜拓?fù)潢P(guān)系的圖像邊界提取。

2.2.2 北地群島區(qū)域海冰邊界線提取

將圖9(a)中北地群島區(qū)域圖像的冰作為前景色，得到該區(qū)域的海冰二值圖像，然后運(yùn)用本文算法追蹤海冰邊界線。本次試驗(yàn)共提取出13條海冰邊界線，如圖10(a)所示，13條邊界線中有3條孤立的邊界線，其余邊界線之間拓?fù)潢P(guān)聯(lián)。分別將圖10(a)中具有代表性的兩個邊界區(qū)域局部放大。其中箭頭①指向位置為海冰邊界線重疊部位有一個公共點(diǎn)，即為本文所述的“孤島”現(xiàn)象；箭頭②指向位置為海冰邊界重疊處的內(nèi)、外邊界標(biāo)定提取結(jié)果。

利用海冰二值圖像提取出的邊界線只是海冰的包絡(luò)線，而對于北極通航，往往需要獲取北極海冰區(qū)域與開闊水域之間的邊界，因此還需去除海岸線的影響，將圖10(a)海冰邊界線與圖9(c)海岸線相重疊的部分去除，即忽略為數(shù)不多的細(xì)碎海冰，最終得到北地群島海冰邊緣線，如圖10(b)所示。

圖10 北地群島海水邊緣線提取

3 結(jié) 語

本文在分析現(xiàn)有邊界追蹤算法的基礎(chǔ)上，提出了基于八鄰域邊界追蹤改進(jìn)算法，采用Visual C++語言進(jìn)行編程實(shí)現(xiàn)，可以一次性追蹤出二值圖像目標(biāo)的準(zhǔn)確輪廓線，且能夠很好地解決孤島、邊界重疊及內(nèi)外邊界的提取等問題，最后應(yīng)用試驗(yàn)驗(yàn)證了該算法的正確性，并用實(shí)例進(jìn)行了大范圍圖像邊界線提取的有效性驗(yàn)證。