戴激光，張 力，李晉威，方鑫鑫

1. 遼寧工程技術大學測繪與地理科學學院, 遼寧 阜新 123000; 2. 中國測繪科學研究院, 北京 100039

一種鏈碼跟蹤與相位驗證相結合的直線提取方法

戴激光1,2，張 力2，李晉威1，方鑫鑫1

1. 遼寧工程技術大學測繪與地理科學學院, 遼寧 阜新 123000; 2. 中國測繪科學研究院, 北京 100039

提出了一種鏈碼跟蹤與相位驗證相結合的直線提取方法。該方法首先針對Canny邊緣圖提出一種完全細化方法；其次提出一種改進的鏈碼跟蹤方法，其步驟包括檢測鏈碼端點，建立動態(tài)鏈碼主方向確定鏈碼跟蹤方向，優(yōu)先跟蹤八鄰域內邊緣點，八鄰域內無邊緣點再進行八鄰域外邊緣點，并采用直線化分析對鏈碼進行動態(tài)約束；最后對鏈碼進行直線擬合及相位驗證，滿足條件輸出直線，不滿足要求的鏈碼則重新設定端點進行跟蹤直線提取。通過多種不同光學圖像數(shù)據(jù)的試驗結果分析表明，本文所提出的方法不僅能夠精確實現(xiàn)邊緣直線信息的擬合，并且能夠解決由于白噪聲及相位編組所引起的直線斷裂問題。

直線提取；細化方法；鏈碼跟蹤；相位驗證

直線提取是計算機視覺及航空遙感圖像處理領域中一個關鍵的問題[1-2]。作為圖像中一種規(guī)則離散點集，線特征相比于點特征能夠提供更加明確、豐富的結構信息，其方向、長度、端點及直線間的拓撲關系等信息在圖像壓縮、目標識別、圖像匹配等領域具有重要的應用價值[3-6]。但如何構建一種直線提取模型，從不規(guī)則離散邊緣點集中獲取有意義的直線信息，具有相當大的難度[7]。

自頂而下方法是直線提取的一個有效策略，該類方法是將圖像中具有一定空間關系的邊緣點進行聚類，尋找解析形式獲取直線參數(shù)信息。其中以Hough變換方法最為典型，該方法具有抗噪性好的優(yōu)點，并且對共線短直線連接具有較好的穩(wěn)健性。缺點是復雜度高、參數(shù)難以選擇、缺乏局部特性、直線端點定位難度大，易產生虛假直線及漏檢問題[8-11]。

直線提取的另外一種策略是自下而上方法，該類方法采用一定的約束準則跟蹤邊緣點，并對跟蹤編組后的邊緣點集進行直線擬合。其中以邊緣鏈碼與相位編組方法為典型代表，前者通過直線幾何約束準則進行邊緣鏈碼編組，利用合并或分裂方法完成對直線的提取[12]。該類方法原理比較簡單，計算量小同時適合實時處理，但也存在直線易斷裂、無意義直線較多等缺點[13-15]。究其原因在于以下4點：①鏈碼跟蹤受限于起始點的位置；②幾何約束準則是以45°為基準方向碼，這并不能滿足實際直線角度要求；③多邊緣交叉點處易引發(fā)其他方向邊緣的斷裂，這主要是由于邊緣圖細化程度不夠，交叉點無法準確定義，難以建立有效邊緣補償機制；④對形成直線的邊緣點缺乏相位約束機制，難以避免由不同相位邊緣點構成無效直線問題的發(fā)生。與鏈碼編組方法不同的是，邊緣點相位是相位編組方法進行鏈碼跟蹤的主要約束準則，因而這類方法檢測的有效直線產出率高[16]，但也是受到邊緣點相位的約束，局部白噪聲、起始點相位、相位分組閾值等因素均會引發(fā)相位交錯分組的問題，使得直線提取效果的完整性較差[17-19]。

針對自下而上直線提取方法中存在的問題，論文提出一種鏈碼跟蹤與相位驗證相結合的直線提取方法。該方法首先建立細化規(guī)則對邊緣圖進行完全細化；其次通過檢測端點進行鏈碼跟蹤直線擬合，同時在跟蹤過程中建立的動態(tài)鏈碼主方向，以精確鏈碼直線幾何約束準則；最后利用邊緣點相位進行直線有效性約束，以此解決在相位編組方法中出現(xiàn)的斷裂問題以及鏈碼跟蹤方法中的直線有效性驗證問題，獲取更好的直線擬合效果，實現(xiàn)利用直線分析影像結構信息的目的。

1 方 法

如圖1所示為本文方法的流程圖。該方法充分結合了鏈碼跟蹤與相位編組的優(yōu)點：首先，利用鏈碼跟蹤幾何約束準則，避免局部白噪聲所引起的直線斷裂問題；其次，對鏈碼跟蹤的直線進行相位驗證，防止無效直線的產生。

圖1 方法流程Fig.1 Flowchart of the proposed method

具體步驟如下:

(1)利用Canny方法提取邊緣圖及其相位圖。

(2) 采用論文所提出的細化規(guī)則對邊緣圖進行完全細化處理，以避免多邊緣交叉點處引發(fā)的直線斷裂問題。

(3) 遍歷搜索邊緣端點，以此作為鏈碼起始點進行跟蹤。

(4) 以端點為起始點，利用論文所提的鏈碼跟蹤方法進行邊緣點編組，在編組結束后對邊緣點進行直線擬合。

(5) 對擬合后的直線進行有效性判斷，不滿足要求則表明當前起始端點出現(xiàn)錯誤，進入步驟(6)；滿足要求則輸出直線，同時判斷當前鏈碼是否可以繼續(xù)跟蹤，滿足要求則進入步驟(7)；不滿足要求則進入步驟(3)。

(6) 以當前提取的邊緣鏈碼為基礎，按照跟蹤順序確定第3個邊緣點作為端點進入步驟(4)，前面2個邊緣點刪除。

(7) 以當前鏈碼終點為端點，進入步驟(4)。

1.1 邊緣提取

Canny方法是效果較優(yōu)的一種邊緣檢測算子，該方法通過建立梯度圖，利用高低兩個閾值來提取圖像中的邊緣信息。由于充分考慮了圖像中的梯度幅值與局部結構信息，因此具有較強的實用性[20]。在這里僅對傳統(tǒng)Canny方法部分步驟進行修改，包括以下內容：

(1) 在進行影像濾波處理時，選擇16×1的高斯濾波器。

(2) 梯度檢測以x向梯度圖為例，先對原圖像y向濾波，然后進行x向梯度檢測；對y向梯度圖檢測，則先對原圖像x向濾波，然后進行y向梯度檢測。

(3) 邊緣點相位計算。這里借鑒文獻[17]中對邊緣點的相位計算方法，其公式如下

ang(i,j)=arctan[gx(i,j)/-gy(i,j)]

(1)

式中，i為圖像y向坐標；j為圖像x向坐標；ang(i,j)是坐標為(i,j)的邊緣點相位；gx(i,j)為x向梯度檢測值；gy(i,j)為y向梯度檢測值。

Canny方法在邊緣提取過程中采取了非極大值抑制處理，但由于抑制方向為目標點的梯度方向，通常該方向對比梯度幅值來源于相鄰兩像素梯度插值，故難以避免多像素寬度邊緣、毛刺等現(xiàn)象的發(fā)生，而這可能導致以下3個問題的出現(xiàn)：

(1) 鏈碼跟蹤起始端點很難清晰定義。

(2) 鏈碼可能會向非邊緣方向跟蹤，造成鏈碼的斷裂，降低了直線提取的完整性。

(3) 邊緣交叉點判斷條件很難設計，進而導致在邊緣交叉處直線發(fā)生斷裂。

因而，對Canny邊緣圖必須進行細化處理。

1.2 邊緣細化

細化作為二值圖像處理中的一種基本方法，目的是減少圖像成分，保留區(qū)域的最基本信息，便于圖像進行識別和分析。經典細化方法有ZS方法[21-22]、HSCP方法[23-24]、OPTA方法[25]等，這些方法通過大量試驗驗證均存在細化程度不足、細化過度、毛刺點大量存在等問題，無法滿足鏈碼跟蹤要求。因此本文依據(jù)Canny提取的邊緣圖，基于最大限度保留直線信息的原則，提出一種新的細化規(guī)則。如圖2所示為邊緣鄰域方向模板。

×為當前待處理目標點;P0-P23表示相對于×點的不同方向鄰點;P0-P7為點×的八鄰域點;P8-P23為八鄰域外點。

依據(jù)Canny方法處理后的邊緣圖像，分別對不同情形下目標點進行細化處理：

(1) 八鄰域內無邊緣點，直接對目標點進行消除處理。

(2) 當八鄰域內僅有1個邊緣點時，這表明目標點可能為毛刺點也可能為端點。

(a) 假定八鄰域內邊緣點為四角點。例如P1為邊緣點，對P1八鄰域進行判斷，由于P0、P2為非邊緣點，×無需判斷，即只需對P8、P9、P10、P11、P125點進行判斷。

若上述5點中3點以上為邊緣點，則×點必然為毛刺點，進行消除處理。

若2點為邊緣點，則根據(jù)×點與P0點方向形成主方向進行判斷，若1點與主方向相同，另外1點與主方向相鄰，即2點為P9和P10或P10和P11，則目標點保留；其他情況下目標點進行消除處理。

僅有1個邊緣點，則保留當前目標點。

(b) 假定邊緣點為四鄰點。假定P0為邊緣點，判斷其八鄰域，由于P1、P2、P6、P7為非邊緣點，即需對P8、P9、P233點進行分析：

若3點為邊緣點，則×點為毛刺點，進行消除處理。

若2點為邊緣點，則根據(jù)×點與P0點方向形成主方向進行判斷，若2點為P8、P23時目標點保留；其余情況目標點進行消除處理。

僅有1個邊緣點，當前目標點保留。

(3) 當八鄰域內存在2個邊緣點時，如2點不存在連通性，例如2點為P0和P23，當前目標點予以保留。而當2點存在連通性時：

(a) 當2點為P0和P2類似對角關系時，若P0和P2在其八鄰域內除×點外均存在邊緣點，則目標點消除；

(b) 當兩點為P0和P1類似四連通關系時，若P0和P1在其八鄰域內均有邊緣點，除僅有P8、P9、P8和P9為邊緣點3種情況外，可消除當前目標點，其余情況下目標點均予以保留。

(4) 當目標點八鄰域內存在3個邊緣點時，如3點之間存在八連通關系，則當前目標點消除。

(5) 八鄰域內存在4個邊緣點時，如4點均存在四連通關系，消除當前目標點。

(6) 八鄰域內存在5個邊緣點時，如5點間存在連通關系，消除當前目標點。

在論文中，通常圖像細化需要進行2～3次處理，以達到邊緣圖完全細化的目的。

1.3 邊緣鏈碼直線提取

采用論文細化方法可將邊緣線條寬度降為單像素，便于邊緣鏈碼跟蹤。論文首先確定鏈碼起始端點，其次設計動態(tài)跟蹤約束主方向，依據(jù)主方向采取先八鄰域點后八鄰域外點方式進行鏈碼跟蹤，并對鏈碼跟蹤結果進行動態(tài)直線化分析，最終利用相位驗證的方式輸出有效直線。在鏈碼方向碼的設計中，與傳統(tǒng)方向碼不同，論文引入非整數(shù)的方向碼，以精細確定鏈碼跟蹤的方向。如圖3所示，中心點為當前鏈碼跟蹤點，八鄰域為0—7方向碼，0—7外延對應的是鏈碼八鄰域外方向碼，其中八鄰域外方向碼為相對于中心點的非整數(shù)方向碼。

圖3 鏈碼方向碼示意圖Fig.3 Sketch map of chain code direction

具體關鍵步驟及相關說明如下：

(1) 鏈碼起始端點檢測。起始端點檢測是鏈碼跟蹤的基礎，偽端點必然引發(fā)鏈碼斷裂、方向發(fā)生偏轉等問題。如圖4所示為自然圖像邊緣局部放大圖，如果僅采用由左至右、由上至下遍歷方式定義端點，那么灰色虛框邊緣點必然首先被遍歷為鏈碼起始端點，以此為基礎鏈碼向右側跟蹤，導致完整鏈碼斷裂，而左側分裂后的鏈碼也可能因長度過低而被過濾掉。因此在論文中，起始端點是指單端點(八鄰域內存在1個邊緣點)與環(huán)狀端點(八鄰域內存在2個邊緣點)。環(huán)狀端點主要存在于房屋、田塊等閉合地物場景中，其檢測方式可以依據(jù)其八鄰域內兩邊緣點間存在對角關系進行判斷。為防止環(huán)狀端點檢測對鏈碼跟蹤構成干擾，本文采取先單端點后環(huán)狀端點的順序進行鏈碼跟蹤，進入步驟(2)。

圖4 邊緣局部放大圖Fig.4 Partial enlarged detail of edge

(2) 動態(tài)鏈碼主方向(Main_Orient)確定。傳統(tǒng)鏈碼跟蹤過程中，直線鏈碼約束準則通常由鏈碼起始跟蹤方向或鏈碼組最后跟蹤點方向確定，這將引發(fā)兩方面的問題：一方面以45°為基準的方向碼很難清晰表達鏈碼的直線特性；另一方面過少點確定的鏈碼方向極易受到異常點的干擾，促使鏈碼發(fā)生斷裂。因此，本文在設計直線鏈碼約束時，建立的動態(tài)鏈碼主方向是隨鏈碼變化而不斷發(fā)生變化的，這符合鏈碼的整體直線特性，排除了鏈碼跟蹤受到起始端點和局部異常點干擾的可能性，并且主方向不再受限于8個方向，更加符合實際直線角度。本文首先將起始端點作為鏈碼起點，搜索與起始端點連通的下一邊緣點，將鏈碼初始方向記錄為Orient，然后進入步驟(3)。具體計算公式如下

Dif_Orient(i)=Index(i)-Orient

(2)

(3)

M_Dif_Orient(i)=Index(i)-Main_Orient

(4)式中，Index(i)為第(i+2)個邊緣點相對于第(i+1)個邊緣點方向碼；Dif_Orient(i)為Index(i)與起始方向鏈碼的差值，取值范圍為[-4,4]；M_Dif_Orient(i)為Index(i)與鏈碼主方向差值，取值范圍為[-4,4]；n為當前鏈碼組除前兩個點外其他邊緣點數(shù)量。

(3) 鏈碼跟蹤方式。首先判斷當前點八鄰域是否存在邊緣點，如果存在，采用八鄰域內跟蹤，轉到步驟(4)，否則采用八鄰域外跟蹤，轉到步驟(5)。

(4) 八鄰域跟蹤。判斷當前點八鄰域內邊緣點數(shù)量：

八鄰域內僅有1個邊緣點時，依據(jù)式(3)分析當前跟蹤方向與鏈碼主方向差異M_Dif_Orient(i)，若差值為-4或4，這表明鏈碼方向發(fā)生劇烈變形，則鏈碼斷裂進入步驟(7)；其他情況下，進入步驟(6)。

若邊緣點不唯一時，當前目標點通常為邊緣交叉點，根據(jù)式(4)計算不同邊緣點方向碼與主方向碼差值，選擇最小絕對差值方向碼作為當前鏈碼跟蹤方向，進入步驟(6)；同時在當前鏈碼跟蹤結束后對邊緣交叉點進行邊緣補償，即將邊緣交叉點單獨設為邊緣點。以防止鏈碼形成直線后，原有鏈碼內全部邊緣點非邊緣化，進而導致下一邊緣直線的斷裂。

(5) 八鄰域外跟蹤。判斷鏈碼是否存在過度離散化問題，即鏈碼中八鄰域外連接點數(shù)量(計入即將跟蹤點)與當前鏈碼邊緣點數(shù)量之間的比值是否低于閾值δ，若是則直接進入步驟(7)；如高于閾值δ，則判斷八鄰域外最接近Main_Orient、Main_Orient-0.5和Main_Orient+0.5方向上是否存在邊緣點，如果是轉到步驟(6)；如果不存在，轉到步驟(7)。

(6) 鏈碼直線化分析。為確保獲取最佳鏈碼終點，分別對步驟(4)和步驟(5)加入的邊緣點進行以下判斷：

(a) 鏈碼方向檢測。每次加入的新點i均進行檢測，即當M_Dif_Orient(i)、M_Dif_Orient(i-1)、M_Dif_Orient(i-2)均為同一符號，并且累計絕對值大于3.0以上時，這表明當前鏈碼發(fā)生明顯偏轉，必將改變擬合直線方向，因此鏈碼立即斷裂，進入步驟(7)。

(b) 鏈碼點與擬合直線距離檢測。當加入邊緣點數(shù)量n為3的倍數(shù)時，進行直線最小二乘擬合，對鏈碼中的點進行抽樣計算與直線垂直距離，若距離超過垂直距離閾值ε時，鏈碼斷裂進入步驟(7)。

通過上述兩種檢測后，利用式(2)和式(3)更新Main_Orient，進入步驟(3)。

(7) 對獲取的邊緣鏈碼進行相位編組驗證，通過最小二乘方法求取直線方向，接著對邊緣點進行相位驗證。該方法首先統(tǒng)計鏈碼中邊緣點相位符合直線方向的數(shù)量(相位與直線方向之間差異不超過π/4弧度)，其次將該數(shù)量與鏈碼組邊緣點總數(shù)量進行對比，判斷比值是否低于閾值θ：

(a) 若低于閾值θ，判斷直線長度是否達到閾值τ,滿足要求則直接輸出直線，接著以當前鏈碼終點為端點進入步驟(3)；不滿足要求則按照鏈碼跟蹤順序，將第3點邊緣點視為端點，進入步驟(3)。

(b) 若當前鏈碼高于閾值θ并且鏈碼中存在交叉點，則按照鏈碼跟蹤順序，將前兩個邊緣點刪除，鏈碼中其余點恢復為邊緣點后進入步驟(1)，防止影響交叉點處其他直線的提取。

(c) 若當前鏈碼高于閾值θ且不存交叉點，同時這種情況是由步驟(4)和步驟(6)鏈碼產生斷裂所產生，則按照鏈碼跟蹤順序，將前兩個邊緣點刪除，其余點按照原來鏈碼順序由前兩點建立Orient，后續(xù)點依次更新Main_Orient，進入步驟(3)；如當前鏈碼由步驟(5)進入，則轉入步驟(1)。

2 試驗結果及分析

為了深入驗證論文方法關鍵步驟的試驗效果，論文分別對邊緣細化結果與直線提取效果進行討論。

2.1 圖像細化結果試驗分析

為驗證論文提出細化方法的實際效果，以VS2010作為處理平臺，分別對論文細化方法、HSCP方法和ZS方法進行編程實現(xiàn)，并通過大量圖像對3種方法的處理性能進行比較。

為清晰展示邊緣細化結果，圖5給出了3種方法邊緣圖局部細化對比結果。首先由圖5(b)局部圖像中可以看出Canny邊緣圖中存在像素冗余、毛刺等多種問題，細化處理十分必要。如圖5(d)所示HSCP方法處理結果明顯有信息丟失的現(xiàn)象發(fā)生，并且數(shù)據(jù)的冗余問題依然沒有得到較好的解決，同時毛刺問題仍然存在；而ZS方法相對于HSCP方法局部信息丟失較少，但毛刺現(xiàn)象依然沒有根除。如圖5(c)所示，論文方法細化結果比較光滑，不存在毛刺現(xiàn)象，同時基本完整保存原有邊緣連通信息。利用人工對論文方法細化后的Lena邊緣圖進行全面細致觀察，邊緣毛刺、冗余現(xiàn)象已完全消除，得到了保持8連接、完全細化的邊緣圖。而在運行效率方面，3種方法的耗時基本都在0.1 s左右，相差不大。

圖5 不同方法的細化效果比較Fig.5 Thinning results of different algorithms

2.2 直線擬合結果與分析

在對直線試驗效果進行評價時，論文基于以下原則對直線提取效果進行評價：①提取直線的有效性，即直線是否位于真實地物邊緣上；②直線的擬合長度，對同一邊緣應盡量采用少量的較長直線進行擬合，以降低機器對圖像信息的理解難度；③直線提取方法的運行時間。一個良好的直線提取方法應定義為，在保證直線提取正確率情況下，最大化擬合直線的同時提高方法運行速度。

2.2.1 參數(shù)分析

由于本文方法涉及一些閾值參數(shù)，因此需要對這些參數(shù)進行討論分析：

(1) 八鄰域外連接點數(shù)量與鏈碼組邊緣點數(shù)量比例閾值δ，該閾值是為防止鏈碼由多個八鄰域外點組成，進而導致虛假直線現(xiàn)象的發(fā)生，另外也是為了避免由異常點所引發(fā)的鏈碼斷裂問題。因此論文從以上兩方面考慮，將δ設定為0.2。

(2) 邊緣點與擬合直線垂直距離閾值ε。通過該閾值可對鏈碼進行直線幾何約束，防止鏈碼出現(xiàn)曲線化的傾向，因此該閾值設定不宜過大。但由于在跟蹤過程中鏈碼不斷更新主方向，并且鏈碼方向檢測已起到了部分直線幾何約束的作用，同時直線長度較大時閾值ε過小將導致直線斷裂。故論文綜合考慮將ε閾值設為3像素。

(3) 相位驗證閾值θ。該參數(shù)一方面是為了降低白噪聲對鏈碼跟蹤的影響，另一方面也是避免無效直線的產生，因此該閾值不宜過小，故將其設為0.9。

(4) 直線長度閾值τ。在圖像處理中，通常認為直線長度越大其信息量越大，而過短的直線不僅意義不大，同時也會影響機器對圖像的認知，因此論文設定τ為8像素。

以上參數(shù)是通過對多幅光學圖像的測試所確定，如果圖像中存在強烈干擾性噪聲或者SAR圖像，則上述參數(shù)需重新設定。

2.2.2 直線提取結果對比分析

為了充分驗證論文方法的有效性，分別利用文獻[10]方法、文獻[15]方法、LSD(line segment detector)方法[17]及EDlines(edge drawing lines)方法[18]等具有典型性的直線提取方法進行對比，其中文獻[10]方法、文獻[15]方法、LSD方法分別對應于Hough變換、鏈碼跟蹤及相位編組方法。在試驗中，文獻[10]方法和文獻[15]方法采用Canny邊緣圖，并利用ZS方法對邊緣圖進行細化處理。而LSD方法及EDlines方法則直接下載相應論文網站提供的開源代碼，將其放入VS2010平臺進行處理。

如圖6(a)所示，首先論文選取一幅近景圖像(638×638像素)，其中包含數(shù)量較少的清晰線性信息，便于對不同方法試驗效果進行人工檢查，其精度評定的依據(jù)是直線評價效果原則①。從圖6試驗結果可以看出，5種方法均可清晰檢測出圖像大致線性輪廓信息。但對圖6(c)和圖6(d)直線檢測的結果進行詳細觀察可以發(fā)現(xiàn)，文獻[10]和文獻[15]方法由于沒有進行完全細化及端點檢測，因此提取的直線長度過短并且數(shù)量過多，在連續(xù)邊緣線(例如窗口邊緣及墻角處)附近存在大量的斷裂直線，這不符合直線評價原則②的要求。而相對于另外兩種方法，圖6(b)論文方法試驗結果具有線狀特征更加簡潔的優(yōu)點，這在窗戶外沿與左側墻體的連接處有清晰呈現(xiàn)結果。如表1所示，對多種方法直線檢測的精度結果分析表明，論文方法、文獻[10]和文獻[15]方法不存在錯誤直線，而LSD和EDlines方法所檢測的錯誤直線主要出現(xiàn)在圖像的四周，圖像邊緣效應可能是出現(xiàn)這一問題的主要原因。對比直線提取的擬合長度可以看到，論文方法直線數(shù)量最小，但擬合長度卻最大，這說明論文方法所采用的細化方法和跟蹤方法是有效的，直線的完整性提取效果優(yōu)勢非常明顯。

圖6 近景圖像不同直線提取效果Fig.6 Line extraction results with different algorithms for close range image

表1 不同方法近景圖像直線提取結果

Tab.1 Line extraction results by different algorithms for close image

不同方法直線總長度/像素直線數(shù)目/條錯誤直線數(shù)目/條耗時/s本文方法1678048602．21文獻[10]方法1607668303．01文獻[15]方法1329167001．28EDlines方法1624053290．046LSD方法16241493141．91

其次，如圖7(a)所示，為了驗證本文方法在航空圖像上的效果，對ISPRS官方網站提供的1800×1800像素航空數(shù)據(jù)進行分析。由于航片圖幅較大，直線信息過多，一方面人工檢查直線效果難度較大，沒有標準直線檢測對比圖；另一方面論文方法直線提取效果精度較高，這一點在圖6中有定量驗證，因此本文并未對后續(xù)圖像的5種方法試驗效果進行精度檢驗，僅對直線效果評價原則②和③進行探討。為了對試驗效果進行詳細觀察，如圖7(b)所示，本文對圖像黑色框內中建筑物直線信息進行局部放大分析，可以看到文獻[15]方法和本文方法所提取直線擬合效果較好，而文獻[10]、LSD、EDlines方法則存在直線斷裂的問題，其原因在于：文獻[10]方法采用聚類方法進行峰值檢測，連續(xù)性邊緣由于聚類不一致導致直線破裂；LSD和EDlines方法則與相位交錯編組及白噪聲有關。而相比于文獻[15]方法，本文方法提取直線更加清晰有效，并具有更好的連續(xù)性。由此可以表明，本文方法采用鏈碼形式進行跟蹤，利用先直線檢測后相位驗證的方式，可以有效解決白噪聲造成的直線破裂問題。本文方法也存在屋頂右下側直線信息漏檢的問題，這一問題取決于Canny邊緣圖效果，選取較低的高低閾值則右下側直線必然出現(xiàn)，但同時也會產生過多的無意義直線，例如圖像中樹木陰影所形成的直線信息，這將加大機器對圖像理解的難度，如何解決這一矛盾也是未來進一步需要探討的問題。

最后，本文嘗試對噪聲更多、模糊度更大的IKONOS光學衛(wèi)星全色圖像進行實驗，以進一步探討論文方法的抗噪性。如圖8(a)所示，圖像大小為1024×1024像素，覆蓋區(qū)域為城市近郊，區(qū)域內中包含房屋、梯田、道路等多種線性特征信息。通過5種方法局部直線提取效果對比分析表明：除了文獻[10]方法外，其余4種方法均能較好地提取建筑物輪廓線，但LSD方法存在一定的直線斷裂，本文方法、EDlines方法、文獻[15]方法則很少出現(xiàn)這一問題；而相對于EDlines方法和文獻[15]方法，本文方法連貫度更好，但也存在部分直線沒有檢測的問題。

圖7 航空圖像不同直線提取效果Fig.7 Line extraction results with different algorithms for aerial image

如表1和表2所示對比方法耗時，可以看到本文方法明顯優(yōu)于文獻[10]方法，但遠低于EDlines方法。由于EDlines方法網站不提供源代碼，只能采用其封裝動態(tài)鏈接庫，具體單進程運行效果無法有效預測，因此可比性不強。而本文方法耗時長于文獻[15]和LSD方法的原因在于，本文方法是鏈碼跟蹤與相位驗證的結合，需要進行迭代分析驗證。而文獻[15]和LSD方法分別是鏈碼跟蹤與相位編組的改進，不需進行迭代計算，因而計算速度較快。

表2 不同方法遙感圖像直線提取結果

3 結 語

本文提出一種鏈碼跟蹤與相位驗證相結合的直線擬合方法，相對于其他方法，具有以下幾個創(chuàng)新之處：

(1) 提出一種邊緣細化方法，實現(xiàn)了邊緣圖的完全細化。這使得鏈碼起始端點更加易于定義，多邊緣交叉處便于進行邊緣補償，有利于鏈碼的完整性提取。

(2) 改進了鏈碼跟蹤方法。對動態(tài)鏈碼主方向進行了定義，并給出了相應的計算公式，使得鏈碼跟蹤不再受到起始端點、局部異常點及45°基準方向碼的限制。

(3) 相位驗證與鏈碼跟蹤相結合。對鏈碼跟蹤獲取的直線進行相位驗證，解決了鏈碼直線提取方法中缺乏相位約束機制問題；同時先進行鏈碼跟蹤后進行相位驗證的方法，也解決了局部白噪聲、起始點相位、相位分組閾值等因素對相位編組直線提取方法的限制問題。

通過試驗的對比與分析，驗證了本文方法的優(yōu)越性。但其不足之處在于本文方法暫時僅能在噪聲相對較小的光學圖像中實現(xiàn)直線的檢測任務，還無法在強噪聲及SAR圖像中進行直線的提取，并且本文方法中的一些閾值參數(shù)尚需人工設定，這些問題都將是今后工作研究的重點。

[1] 董銀文, 苑秉成, 王航宇, 等. 一種有效的航拍圖像中直線提取算法[J]. 武漢大學學報(信息科學版), 2012, 37(2): 160-164. DONG Yinwen, YUAN Bingcheng, WANG Hangyu, et al. An Effective Algorithm for Line Extraction in Aerial Image[J]. Geomatics and Information Science of Wuhan University, 2012, 37(2): 160-164.

[2] BALTSAVIAS E P. Object Extraction and Revision by Image Analysis Using Existing Geodata and Knowledge: Current Status and Steps towards Operational Systems[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2004, 58(3-4): 129-151.

[3] ZHENG Yefeng, LI Huiping, DOERMANN D. A Parallel-line Detection Algorithm Based on HMM Decoding[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 27(5): 777-792.

[4] 周紹光, 陳超, 岳建平. 形狀先驗和圖割的高分辨率遙感影像道路段提取[J]. 測繪學報, 2014, 43(1): 60-65. DOI: 10.13485/j.cnki.11-2089.2014.0009. ZHOU Shaoguang, CHEN Chao, YUE Jianping. Extracting Roads from High-resolution RS Images Based on Shape Priors and Graph Cuts[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(1): 60-65. DOI: 10.13485/j.cnki.11-2089.2014.0009.

[5] 曹金山, 龔健雅, 袁修孝. 直線特征約束的高分辨率衛(wèi)星影像區(qū)域網平差方法[J]. 測繪學報, 2015, 44(10): 1100-1107, 1116. DOI: 10.11947/j.AGCS2.0152.0150023. CAO Jinshan, GONG Jianya, YUAN Xiuxiao. A Block Adjustment Method of High-resolution Satellite Imagery with Straight Line Constraints[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10): 1100-1107, 1116. DOI: 10.11947/j.AGCS2.0152.0150023.

[6] 王競雪, 宋偉東, 王偉璽. 同名點及高程平面約束的航空影像直線匹配算法[J]. 測繪學報, 2016, 45(1): 87-95. DOI: 10.11947/j.AGCS.2016.20140527. WANG Jingxue, SONG Weidong, WANG Weixi. Line Matching Algorithm for Aerial Image Based on Corresponding Points and Z-plane Constraints[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(1): 87-95. DOI: 10.11947/j.AGCS.2016.20140527.

[7] 徐勝華, 朱慶, 劉紀平, 等. 基于預存儲權值矩陣的多尺度Hough變換直線提取算法[J]. 測繪學報, 2008, 37(1): 83-88. XU Shenghua, ZHU Qing, LIU Jiping, et al. Straight Line Extraction via Multi-scale Hough Transform Based on Pre-storage Weight Matrix[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(1): 83-88.

[8] 文貢堅, 王潤生. 一種穩(wěn)健的直線提取算法[J]. 軟件學報, 2001, 12(11): 1660-1666. WEN Gongjian, WANG Runsheng. A Robust Approach to Extracting Straight Lines[J]. Journal of Software, 2001, 12(11): 1660-1666.

[9] CHUNG K L, CHEN T C, YAN Wenming. New Memory and Computation-efficient Hough Transform for Detecting Lines[J]. Pattern Recognition, 2004, 37(5): 953-963.

[10] 王競雪, 朱慶, 王偉璽, 等. 結合邊緣編組的Hough變換直線提取[J]. 遙感學報, 2014, 18(2): 378-389. WANG Jingxue, ZHU Qing, WANG Weixi, et al. Straight Line Extraction Algorithm by Hough Transform Combining Edge Grouping[J]. Journal of Remote Sensing, 2014, 18(2): 378-389.

[11] XU Zezhong, SHIN B S, KLETTE R. Accurate and Robust Line Segment Extraction Using Minimum Entropy with Hough Transform[J]. IEEE Transactions on Image Processing, 2015, 24(3): 813-822.

[12] FREEMAN H. Boundary Encoding and Processing[C]∥LIPKIN B S, ROSENFELD A. Proceedings of Picture Processing and Psychopictorics. New York: Academic Press, 1970: 241-266.

[13] 尚振宏, 劉明業(yè). 運用Freeman準則的直線檢測算法[J]. 計算機輔助設計與圖形學學報, 2005, 17(1): 49-53. SHANG Zhenhong, LIU Mingye. Line Detection Algorithm Using Freeman Criteria[J]. Journal of Computer-Aided Design & Computer Graphics, 2005, 17(1): 49-53.

[14] 趙麗科, 宋偉東, 王競雪. Freeman鏈碼優(yōu)先級直線提取算法研究[J]. 武漢大學學報(信息科學版), 2014, 39(1): 42-46, 122. ZHAO Like, SONG Weidong, WANG Jingxue. Straight Line Extraction Algorithm of Freeman Chain Code Priority[J]. Geomatics and Information Science of Wuhan University, 2014, 39(1): 42-46, 122.

[15] 王競雪, 宋偉東, 趙麗科, 等. 改進的Freeman鏈碼在邊緣跟蹤及直線提取中的應用研究[J]. 信號處理, 2014, 30(4): 422-430. WANG Jingxue, SONG Weidong, ZHAO Like, et al. Application of Improved Freeman Chain Code in Edge Tracking and Straight Line Extraction[J]. Journal of Signal Processing, 2014, 30(4): 422-430.

[16] BURNS J B, HANSON A R, RISEMAN E M. Extracting Straight Lines[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, 8(4): 425-455.

[17] VON GIOI R G, JAKUBOWICZ J, MOREL J M, et al. LSD: A Fast Line Segment Detector with a False Detection Control[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(4): 722-732.

[18] AKINLAR C, TOPAL C. EDLines: A Real-time Line Segment Detector with a False Detection Control[J]. Pattern Recognition Letters, 2011, 32(13): 1633-1642.

[19] 王競雪, 朱慶, 張云生, 等. 疊置分區(qū)輔助的相位編組直線提取算法[J]. 測繪學報, 2015, 44(7): 768-774, 790. DOI: 10.11947/j.AGCS.2015.20140234. WANG Jingxue, ZHU Qing, ZHANG Yunsheng, et al. Phase Grouping Line Extraction Algorithm Using Over-lapped Partition[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(7): 768-774, 790. DOI: 10.11947/j.AGCS.2015.20140234.

[20] CANNY J. A Computational Approach to Edge Detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, 8(6): 679-698.

[21] ZHANG T Y, SUEN C Y. A Fast Parallel Algorithm for Thinning Digital Patterns[J]. Communications of the ACM, 1984, 27(3): 236-239.

[22] 韓建峰, 宋麗麗. 改進的字符圖像細化算法[J]. 計算機輔助設計與圖形學學報, 2013, 25(1): 62-66. HAN Jianfeng, SONG Lili. An Improved Thinning Algorithm for Character Image[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(1): 62-66.

[23] HOLT C M, STEWART A, CLINT M, et al. An Improved Parallel Thinning Algorithm[J]. Communications of the ACM, 1987, 30(2): 156-160.

[24] 許宏科, 秦嚴嚴, 潘勇. 一種改進的邊緣細化方法[J]. 激光與紅外, 2014, 44(3): 319-324. XU Hongke, QIN Yanyan, PAN Yong. Improved Edge Thinning Method[J]. Laser & Infrared, 2014, 44(3): 319-324.

[25] CHIN R T, WAN H K, STOVER D L, et al. A One-pass Thinning Algorithm and Its Parallel Implementation[J]. Computer Vision, Graphics, and Image Processing, 1987, 40(1): 30-40.

(責任編輯:張艷玲)

A Line Extraction Method for Chain Code Tracking with Phase Verification

DAI Jiguang1,2,ZHANG Li2,LI Jinwei1,FANG Xinxin1

1. School of Geomatics,Liaoning Technical University，F(xiàn)uxin 123000，China; 2. Chinese Academy of Surveying and Mapping, Beijing 100039, China

A line extraction method for chain code tracking with phase verification was proposed in this study. Firstly, a complete refinement algorithm targeting the Canny edge map was presented. Secondly, an improved chain code tracking method was proposed, and the key algorithm steps were described as follows: detecting the start points of chain code; setting up dynamic main directions to determine the tracking directions of chain code; tracking edge points inside the eight neighborhoods was preferred, and then edge points outside the eight neighborhoods if no edge points existed inside the eight neighborhoods, meanwhile linear analysis was employed to perform dynamic constraints on the chain code. Finally, linear fitting and phase marshalling validation were processed upon the chain code tracking, where straight lines were output when condition were satisfied, otherwise the start points of chain code should be reset to extract straight lines. The experimental results from a variety of different optical image data showed that the proposed algorithm could not only achieve precise fit straight edge information, but also solve the linear fracture problems induced by white noise and phase grouping.

line extraction; thinning method; chain code tracking; phase verification

The National Natural Science Foundation of China (Nos. 41271374; 61540056; 41401535); Key Laboratory of Mapping from Space, National Administration of Surveying, Mapping and Geoinformation (No. K201402); State Key Laboratory of Resources and Environmental Information System

DAI Jiguang(1978—), male, PhD, associate professor, majors in feature extraction of high resolution image.

戴激光，張力，李晉威,等.一種鏈碼跟蹤與相位驗證相結合的直線提取方法[J].測繪學報，2017,46(2)：218-227.

10.11947/j.AGCS.2017.20160303. DAI Jiguang,ZHANG Li,LI Jinwei,et al.A Line Extraction Method for Chain Code Tracking with Phase Verification[J]. Acta Geodaetica et Cartographica Sinica,2017,46(2):218-227. DOI:10.11947/j.AGCS.2017.20160303.

P237

A

1001-1595(2017)02-0218-10

國家自然科學基金(41271374；61540056；41401535)；對地觀測技術國家測繪地理信息局重點實驗室開放基金項目(K201402)；資源與環(huán)境信息系統(tǒng)國家重點實驗室開放基金

2016-06-20

戴激光(1978—)，男，博士，副教授，從事高分辨率影像特征提取理論研究。

E-mail： daijg03@163.com

張力Corresponding author： ZHANG Li

E-mail： zhangl@casm.ac.cn

修回日期： 2016-12-02