改进的变长夹角链码算法及在码头识别中的应用

张永梅， 杨飞， 许静

(1.北方工业大学计算机学院，北京 100144； 2.北方工业大学电子信息工程学院，北京 100144；3.广东省普及型高性能计算机重点实验室，深圳市服务计算与应用重点实验室，深圳 518060)



改进的变长夹角链码算法及在码头识别中的应用

张永梅1，3， 杨飞2， 许静1

(1.北方工业大学计算机学院，北京 100144； 2.北方工业大学电子信息工程学院，北京 100144；3.广东省普及型高性能计算机重点实验室，深圳市服务计算与应用重点实验室，深圳 518060)

针对变长夹角链码对曲线近似时的角度信息损失问题，提出了一种变长夹角链码的改进方法，并将该方法应用于码头目标的特征提取。该方法改变了变长夹角链码算法在折线终点选取时的规则，在继承变长夹角链码优点的基础上，保留了曲线曲率较大的拐角，略去了曲线的较小波动，使有较小波动的曲线近似为直线。改进后的方法使折线能更好地逼近曲线，应用折线逼近并表示曲线，有利于提取曲线的角度特征和线特征。应用该方法提取图像特征，用于码头目标的检测，针对水陆分割后的海岸线使用改进的夹角链码提取海岸线的几何特征。实验表明，该方法能够有效地提取码头的直角、平行线特征，再依据码头先验知识，标记出码头区域。

夹角链码； 变长夹角链码； 曲线描述； 特征提取； 港口检测； 图像处理

0 引言

在图像识别研究中，码头目标的识别因其在军用与民用领域都有特殊的研究意义，受到了广泛关注。现有的码头目标识别方法主要依据码头所在位置、码头的带状特征、码头周边特征[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。