改進的變長夾角鏈碼算法及在碼頭識別中的應用

張永梅， 楊飛， 許靜

(1.北方工業大學計算機學院，北京 100144； 2.北方工業大學電子信息工程學院，北京 100144；3.廣東省普及型高性能計算機重點實驗室，深圳市服務計算與應用重點實驗室，深圳 518060)

?

改進的變長夾角鏈碼算法及在碼頭識別中的應用

張永梅1，3， 楊飛2， 許靜1

(1.北方工業大學計算機學院，北京 100144； 2.北方工業大學電子信息工程學院，北京 100144；3.廣東省普及型高性能計算機重點實驗室，深圳市服務計算與應用重點實驗室，深圳 518060)

針對變長夾角鏈碼對曲線近似時的角度信息損失問題，提出了一種變長夾角鏈碼的改進方法，并將該方法應用于碼頭目標的特征提取。該方法改變了變長夾角鏈碼算法在折線終點選取時的規則，在繼承變長夾角鏈碼優點的基礎上，保留了曲線曲率較大的拐角，略去了曲線的較小波動，使有較小波動的曲線近似為直線。改進后的方法使折線能更好地逼近曲線，應用折線逼近并表示曲線，有利于提取曲線的角度特征和線特征。應用該方法提取圖像特征，用于碼頭目標的檢測，針對水陸分割后的海岸線使用改進的夾角鏈碼提取海岸線的幾何特征。實驗表明，該方法能夠有效地提取碼頭的直角、平行線特征，再依據碼頭先驗知識，標記出碼頭區域。

夾角鏈碼； 變長夾角鏈碼； 曲線描述； 特征提??； 港口檢測； 圖像處理

0 引言

在圖像識別研究中，碼頭目標的識別因其在軍用與民用領域都有特殊的研究意義，受到了廣泛關注?，F有的碼頭目標識別方法主要依據碼頭所在位置、碼頭的帶狀特征、碼頭周邊特征[1-2](比如靠岸艦船、碼頭上下文)等，很少有依據碼頭本身所具有的幾何特征來檢測其所在位置的。

圖像的特征提取是數字圖像處理的重要內容，是圖像識別的前提。曲線作為描述圖像的邊緣、輪廓等特征主要對象，已成為研究的關注點。如何描述、提取這些邊緣曲線、輪廓曲線所包含的特征，是圖像特征提取研究的重要內容。對于曲線的描述，有依據邊界連續兩點間的相對位置，對邊界點編碼的Freeman鏈碼[3]表示法； 有根據邊界連續三點的關系，對中間點進行編碼的頂點鏈碼[4]表示法； 還有借助曲線的某些具有特殊特征的點的關鍵點描述法等。趙宇等[5]提出了一種夾角鏈碼方法，該方法使用定長線段近似曲線，減小了曲線存儲所占空間； 劉淑娟等[6]對夾角鏈碼進行了改進，提出了變長夾角鏈碼。該方法克服了夾角鏈碼對線段長度的限制，在存儲空間相當的情況下，對曲線的描述更為精確。這種方法還具有平移、拉升、旋轉不變性，在圖像的存儲、重建、匹配、目標檢測等方面具有重要作用[7-10]。但是，該方法在描述曲線中的較長直線時，容易丟失直線末端的角度信息，使得曲線的角度變得圓滑，從而影響整個曲線特征提取的精度。此外，以上曲線的描述方法多用于曲線的描述、存儲、匹配，很難用于提取曲線的特征。

本文提出了一種變長夾角鏈碼的改進方法。實驗表明，該方法與改進前的方法相比，能更好地逼近曲線。將改進后的方法應用于提取海岸線特征的結果顯示，該方法較好地保留了原曲線的直線特征以及角度特征，利用這些特征結合先驗知識成功地標記出了碼頭區域。

1 理論與方法

1.1 夾角鏈碼與變長夾角鏈碼的描述

夾角鏈碼使用固定長度的折線來近似曲線，并用折線之間的夾角來表示曲線，如圖1(a)所示。曲線SE起點為S，以定長直線SL1，L1L2，L2L3…逼近曲線。具體方法描述參見文獻[5]。該方法具有平移、拉伸、旋轉的不變性，但是，該方法使用固定的折線表示曲線，當曲線的某段近似為直線時，此方法仍然使用多段折線表示。變長夾角鏈碼在此基礎上依據實際情況改變折線長度，如圖1(b)所示。曲線SE，從起點S開始，依次向后延伸，直到長度為最小定長lmin，記為SA1，從A1開始往后，記做L1，直到SL1與SA1的夾角大于某一閾值ε，將L1向前回退一點，以SL1近似描述曲線SA1L1； 繼續以L1為起點重復上述操作，直到終點E。具體描述方法見參考文獻[6]。

(a) 夾角鏈碼 (b) 變長夾角鏈碼

圖1 夾角鏈碼與變長夾角鏈碼

Fig.1 Angle chain code and Length variable angle chain code

可變夾角鏈碼繼承了夾角鏈碼的優點，同時克服了在曲率較小區域出現多折線的缺點。處理后的結果可用于曲線的存儲，形狀的匹配等。但是，以上2種方法都容易造成角度信息的丟失。例如圖1的(b)圖中，L1點若取在A1所在位置，則能更好地體現曲線SA1L1的特性。

1.2 改進的變長夾角鏈碼

以上2種方法在用于描述目標曲線輪廓時，曲線拐角出現了被平滑的現象，這對于曲線的幾何特征的提取，例如直角、平行線的提取造成了嚴重的影響。為了克服變長夾角鏈碼角度信息損失的情況，根據其特點，修改了逼近線段終點選取的位置。如圖2所示，圖中分別給出了對同一曲線按照變長夾角鏈碼逼近曲線和改變終點位置所得到的不同折線的示意圖。

(a) 原圖 (b) 變長夾角鏈碼逼近示意圖 (c) 改變折線終點逼近效果示意圖

圖2 改進前后示意圖

Fig.2 Schematic diagram

圖2(a)為需要做近似的曲線原圖，圖2(b)為按照變長夾角鏈碼算法的逼近效果圖，其中折線SL1L2E為最終結果，由圖2(b)可以看出，逼近結果中的拐角所在點丟失。圖2(c)為在圖2(b)的基礎上，改變折線終點的效果圖，例如： 當SA1與SL1的夾角剛好滿足閾值ε時，(b)圖選擇L1作為折線終點，(c)圖選擇曲線SA1L1中距離直線SL1最遠的點B1作為折線終點，(c)圖中的SB1B2E為最終的逼近結果。比較圖2(b)(c)可見，改變折線終點所取位置，可以提高對曲線的逼近效果，可以更好地保留曲線的角度特征。

本節給出了改進后的算法描述以及與原方法的比較，從占據存儲空間大小和特征保留兩方面給出了改進前后方法的區別。

1.2.1 算法描述

在文獻[5]中，關于變長夾角鏈碼設計，已詳細論證了初始夾角閾值ε和最小定長lmin的設定方法，這里沿用該文獻方法。計算時輸入角度閾值ε、最小定長lmin和曲線SE。算法中涉及的字母參見圖3。

圖3 改進的變長夾角鏈碼生成圖

具體算法過程如下：

1)從起點S開始，依次遍歷從起點S到終點E的各點，直到SA1等于lmin，記錄點A1。

2)從A1點起，遍歷A1到E的點，直到點L1使得SA1與SL1的夾角首次大于ε，記錄點A2。

3)選取曲線段SA1L1中距離直線SL1最遠的點，記做B1。

4)以B1作為曲線的新起點，B1E作為新的輸入曲線，重復1)—3)，并依次記錄下B1，B2，B3，…,Bn，直到到達終點E。

5)經過前4步后，出現了線段SB1，B1B2，…，BnE，依次遍歷線段中相鄰線段，若相鄰線段的夾角小于ε，則舍去2條線段的連接點，將二者合并為一條線段。例如： 當圖2中的線段SB1和B1B2夾角小于ε時，舍去B1。

6)重復5)，直到所有的相鄰線段夾角都滿足條件，得到的折線即為曲線SE使用該方法的逼近結果。

1.2.2 與變長夾角鏈碼的比較

實驗表明，改進的變長夾角鏈碼在第5)6)步消除了前4步所產生的多余線段點。以北京市輪廓圖為例進行實驗并對比，北京市輪廓圖邊緣比較復雜，處理時需要更多的點，提取結果見圖4。

(a) 原圖(北京市地圖)(b) 輪廓圖(c) 變長夾角鏈碼結果(d) 改進后的結果

圖4 北京市輪廓圖及不同辦法提取結果

Fig.4 Beijing map and results of different extracting methods

對圖4中的后3幅圖存儲所需要的點數統計如表1所示。對北京市輪廓圖的處理，2種方法都采用角度閾值ε為5°，最小定長lmin為5個像素。

表1 輪廓圖點數統計

如圖4所示，變長夾角鏈碼和改進后的處理結果都很接近曲線。存儲效果上，與原圖相比，變長夾角鏈碼只需占用原存儲量的16.56%，改進后僅占用14.81%。修改后的方法在完成步驟4)時，逼近折線共包含87個點，經過步驟5)和6)后，減少19個點，符合算法設計時的預期結果。實驗表明，改進后的變長夾角鏈碼在一定程度上減少了曲線占用的存儲容量。

圖4與表1給出了改進后的方法在存儲方面的作用。采用帶有碼頭的海岸線作為處理對象，以說明改進后的方法在曲線逼近方面的優勢。原圖、水陸分割后提取的海岸線以及分別為使用改進前后方法的處理效果圖見圖5。

(a) 海岸圖像(b) 海岸線提取(c) 變長夾角鏈碼結果(d) 改進后的結果

圖5 海岸線圖像及各方法處理結果

Fig.5 The coast lineand results of different processingmethods

圖5中，(b)為曲線圖，含有很多毛刺，(c)(d) 圖用折線逼近后，毛刺減少。(c)圖與(b)圖相比，窄長的矩形碼頭一個被逼近為三角形，另一個碼頭的2條平行線明顯不再平行。這是由于變長夾角鏈碼在兩線段夾角超過閾值ε時，選擇超過閾值的前一點作為線段終點，當遇到碼頭這樣的具有較長線段時，達到閾值ε時所對應的弧長也相應增大，這時就難免損失碼頭的一個直角，使得碼頭矩形被逼近為三角形或梯形。(d) 圖為改進后方法的處理效果，由于在步驟3中采用距離曲線最遠點作為曲線終點，與(c)圖相比，在圖中圓形標記區域較好地保留了曲線的角度信息。根據文獻[5]中所述的面積法則，即近似折線與原曲線之間的陰影部分表示逼近誤差。圖6給出了圖5中的(c)(d)圖像相對于(b)圖的陰影圖。

(a) 改進前 (b) 改進后

圖6 陰影圖

Fig.6 Shadow map

如圖6所示，在427像元×400像元的圖像中，(a)圖中陰影部分像元數為3 556，而圖(b)中為2 570，減少了986個像元。改進前方法在直角區域處很容易出現大塊的陰影區域，而改進后方法所生成的圖像有了明顯改善。這表明改進后的方法在用折線逼近曲線時具有較好的效果。

2 碼頭識別的應用

2.1 幾何特征的提取

本文利用改進后的方法在曲線逼近方面具有的優勢，進行了提取海岸線或其他輪廓幾何特征的應用實驗。圖7為對圖5中的海岸線提取直角、平行線特征的結果。

(a) 直角提取 (b) 平行線提取

圖7 特征提取

Fig.7 Feature extraction

圖7(a)為海岸線提取直角的結果，與圖5(b)圖相對照，從上往下，第4個直角與原海岸線略有出入，其他圓形所標記出來的直角符合海岸線特征。這是由于在生成鏈碼的過程中，第4個直角所在位置的曲線被兩邊線段所代替。依據圖5(d)，生成的折線符合原曲線的走勢，所以依據折線提取直角是可行的。圖7(b)中為提取平行線的效果。由于本文所用方法是用折線表示曲線，因此對于直線的提取就變得容易了，直接設置直線長度閾值，即可準確提取所需要的直線。圖7(b)中加粗的4條線段接近兩兩平行，再次驗證了改進后方法對曲線的逼近效果。

2.2 碼頭識別實例

碼頭的識別一直是研究的熱點，在軍用方面具有特別重要的意義。目前采用的方法主要有基于碼頭上下文的識別方法、基于幾何特征的碼頭識別方法和基于SAR圖像的輻射特征的碼頭識別等。這幾種方法各有優缺點，也可混合使用。

本文所述的改進的變長夾角鏈碼算法可應用于基于幾何特征的碼頭識別的方法中。先對對象進行水陸分割，提取海岸線； 然后使用改進的變長夾角鏈碼算法處理所得到的海岸線，提取海岸線中的平行線對； 最后結合碼頭上下文特征(碼頭兩平行邊向外都是水域，且對角線分布在陸地區域)判斷兩平行線區域是否為碼頭區域。具體流程如圖8所示。

圖8 碼頭識別流程圖

對于圖5中的海岸線，在提取其平行線特征之后，根據經驗，平行線中間區域就是碼頭的潛在區域。但是由于多個碼頭相互平行時，可能出現不同碼頭邊界間相互平行的情況。針對這一問題，需要結合其他特征進一步篩選出碼頭區域。實驗結合提取海岸線過程中得到的水陸二值圖像，如圖9(a)所示，圖中白色區域表示陸地，黑色區域表示水域。若圖5(b)中兩平行線中間區域為陸地，即白色區域，認為該平行線為凸形碼頭的兩條邊。連接兩條平行線之間的線段即為碼頭區域。結果如圖9(b)中粗線所示。

(a) 水陸分割圖像 (b) 碼頭標記

圖9 碼頭識別實例1

Fig.9 Dock detection 1

圖10給出了利用本文方法對另一幅遙感圖像依次進行水陸分割、海岸線提取、碼頭區域標記的每一步的結果圖。

(a) 原圖 (b) 水陸分割 (c) 海岸線提取 (d) 碼頭標記

圖10 碼頭識別實例2

Fig.10 Dock detection 2

從圖10中可以看出，水陸分割圖像的精度以及海岸線提取的精度嚴重影響到后續的特征提取和碼頭區域的劃分。利用本文方法，很多碼頭標記不完整，這是由于本文只利用了變長夾角鏈碼提取幾何特征以及一些先驗知識，有些碼頭區域雙邊有停靠的船只或是其他障礙物，都會造成碼頭信息的丟失。如何使用本文方法提取幾何特征，再結合碼頭其他特征，可以作為研究碼頭識別的一種新思路。

3 結論

本文針對夾角鏈碼和變長夾角鏈碼的特點，改變了其在生成線段時端點的選擇，并在算法中添加消去多余線段的操作。實驗結果表明，在占用存儲量相當的情況下，修改后的方法更好地保留了角度信息，取得了更好的曲線逼近效果。使用生成的折線代替原來的曲線，有利于提取曲線的幾何特征。改進的變長夾角鏈碼能夠較好地近似圖像的輪廓曲線、邊界曲線等，可用于圖像輪廓和邊界幾何特征的提取，具有廣泛的應用前景。

將該方法應用于水陸分割后海岸線的描述，可以較好地保留碼頭目標的幾何特征。實驗中依據已有的碼頭先驗知識，結合本文方法所提供的碼頭幾何特征，成功標記出了碼頭區域。但是本文只用到了碼頭的最基本的先驗知識，如何根據碼頭的其他特征提高碼頭識別的速度以及識別精度，需要做進一步的研究。

[1] 陳琪,陸軍,趙凌君,等.基于特征的SAR遙感圖像港口檢測方法[J].電子與信息學報,2010,32(12):2873-2848. Chen Q,Lu J,Zhao L J,et al.Harbor detection method of SAR remote sensing images based on feature[J].Journal of Electronics & Information Technology,2010,32(12):2873-2848.

[2] 樊利恒,呂俊偉,于振濤.基于線不變矩和封閉性的遙感圖像港口識別[J].光電工程,2013,40(4):92-100. Fan L H,Lyu J W,Yu Z T.Port recognition in remote sensing images based on invariant linear-moment and closure[J].Opto-Electronic Engineering,2013,40(4):92-100.

[3] Freeman H.On the encoding of arbitrary geometric configurations[J].IRE Transactions on Electronic Computers,1961,EC-10(2):260-268.

[4] 魏巍,劉勇奎,段曉東,等.基于Huffman編碼的改進壓縮鏈碼[J].計算機應用,2014,34(12):3565-3569,3575. Wei W,Liu Y K,Duan X D,et al.Improved compression vertex chain code based on Huffman coding[J].Journal of Computer Applications,2014,34(12):3565-3569,3575.

[5] 趙宇,陳雁秋.曲線描述的一種方法:夾角鏈碼[J].軟件學報,2004,15(2):300-307. Zhao Y,Chen Y Q.Included angle chain:A method for curve representation[J].Journal of Software,2004,15(2):300-307.

[6] 劉淑娟,周恩輝,張有會,等.變長夾角鏈碼及其生成算法研究[J].河北師范大學學報:自然科學版,2010,34(6):652-655. Liu S J,Zhou E H,Zhang Y H,et al.Included angle chain of changeable length and its algorithm study[J].Journal of Hebei Normal University:Natural Science Edition,2010,34(6):652-655.[7] 張國英,程益鈺,李峰,等.資源三號衛星影像中線性目標的檢測技術[J].國土資源遙感,2014,26(2):33-37.doi:10.6046/gtzyyg.2014.02.06. Zhang G Y,Cheng Y Y,Li F,et al.Technology of linear target detection based on ZY-3 satellite images[J].Remote Sensing for Land and Resources,2014,26(2):33-37.doi:10.6046/gtzyyg.2014.02.06

[8] 曾接賢,李煒燁.曲率尺度空間與鏈碼方向統計的角點檢測[J].中國圖象圖形學報,2014,19(2):234-242. Zeng J X,Li W Y.Corner detection based on curvature scale space and chain code direction statistics[J].Journal of Image and Graphics,2014,19(2):234-242.

[9] 王要峰,崔艷.基于方向鏈碼去除骨架圖像毛刺算法[J].計算機應用,2013,33(S1):193-194,198. Wang Y F,Cui Y.Skeleton blur removing algorithm based on direction chain code[J].Journal of Computer Applications,2013,33(S1):193-194,198.

[10]王宴,孫怡.基于組合區域形狀特征的物體檢測算法[J].電子與信息學報,2011,33(12):2894-2901. Wang Y,Sun Y.Object detection based on shape feature of combined regions[J].Journal of Electronics & Information Technology,2011,33(12):2894-2901.

(責任編輯： 李瑜)

An improved length variable angle chain code algorithm and its application to dock identification

ZHANG Yongmei1,3， YANG Fei2， XU Jing1

(1.ComputerCollege,NorthChinaUniversityofTechnology,Beijing100144,China; 2.SchoolofElectronicInformationEngineering,NorthChinaUniversityofTechnology,Beijing100144,China; 3.GuangdongKeyLaboratoryofPopularHighPerformanceComputers,ShenzhenKeyLaboratoryofServiceComputingandApplications,Shenzhen518060,China)

This paper proposed an improved length variable angle chain code algorithm for the angle information loss of curve approximation and used this algorithm in dock detection. The new algorithm changes the rules in the selection of the end point and retains the advantages of length variable angle chain code; when occupying the same storage quantity, it can achieve better effect on retaining the corner of larger curvature. This method leaves out the small floatation of curve and it has a positive effect on angle feature and linear feature extraction. The authors used the method to extract the feature of image for dock detection, extracted the geometric feature based on the coastline, and marked out the dock areas combining the geometric feature with the existing knowledge. Experiments show this method can effectively extract right angle and parallel features.

angle chain code; length variable angle chain code; curve description; feature extraction; port detecting; image processing

10.6046/gtzyyg.2016.04.25

張永梅，楊飛，許靜.改進的變長夾角鏈碼算法及在碼頭識別中的應用[J].國土資源遙感,2016,28(4):164-169.(Zhang Y M，Yang F，Xu J.An improved length variable angle chain code algorithm and its application to dock identification[J].Remote Sensing for Land and Resources,2016,28(4):164-169.)

2015-06-09；

2015-08-10

國家自然科學基金項目“多源遙感圖像識別關鍵技術研究”(編號： 61371143)； 北京市自然科學基金項目“物聯網接入端信息采集與可靠高速傳輸關鍵技術研究”(編號： 4132026)； 廣東省普及型高性能計算機重點實驗/深圳市服務計算與應用重點實驗室開放課題“遙感圖像特征提取和挖掘方法研究”(編號： SZU-GDPHPCL2014)，北京市教委項目“面向虛實融合的多源圖像配準與識別科研平臺” (編號： PXM2015_014212_000024)及北京市教委“多源遙感圖像配準與識別科研平臺”項目(編號： XN081)共同資助。

TP 391.9

A

1001-070X(2016)04-0164-06

張永梅(1967-)，博士，教授，主要從事圖像處理、智能識別等方面的研究。Email: zhangym@ncut.edu.cn。