一種八鄰域圖像邊界追蹤改進算法

胡晉山，康建榮，張 琪，劉鵬程，朱銘達

(1.江蘇師范大學地理測繪與城鄉規劃學院，江蘇 徐州 221116；2.華中師范大學城市與環境科學學院，湖北 武漢 430079；3.江蘇師范大學科文學院，江蘇 徐州 221116)

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

1 八鄰域邊界追蹤改進算法

1.1 八鄰域

當進行邊界追蹤搜索時，與當前點所有方向相鄰接的像素點稱為該像素點的8個鄰接像素[10]，如圖1所示，設定目標C右側平行點為0鄰域點，按逆時針方向將八鄰域點分別標號為0、1、2、…、7。

圖1 八鄰域

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

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

1.2.1 確定邊界線起點

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

1.2.2 搜索機理

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

1.2.3 終止準則

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

圖2 搜索機理

圖3 終止準則(1)

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

圖4 終止準則(2)

1.3 整幅圖像邊界拓撲關系處理

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

1.3.1 內外邊界標定

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

圖5 內外邊界標定

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

1.3.2 孤 島

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

圖7 “孤島”

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

2 試驗驗證

2.1 算法精度驗證

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

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

表1 兩種算法結果比較

2.2 大范圍圖像邊界提取

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

圖9 北地群島區域海岸線提取

2.2.1 北地群島區域海岸線提取

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

2.2.2 北地群島區域海冰邊界線提取

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

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

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

3 結 語

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