基于Hausdorff距离的海底地形匹配算法仿真研究

第３３卷　

１．３３　第９期　

Ｎｏ．９　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２００７年５月　

Ｍａｙ　２００７　

・博士论文・　文章编号：ｌ０ｏｏ－＿３４２８（２【Ｉｌｌ７）０９．－一ｌ００７—－０３　文献标识码：Ａ　中图分类号：ＴＰ３９１・４　

基于Ｈａｕｓｄｏｒｆｆ距离的海底地形匹配算法仿真研究　

徐遵义１，２　９晏磊　，宁书年　，刘光军　

（１．中国矿业大学（北京）机电与信息工程学院，北京１０００８３；２．北京大学遥感与ＧＩＳ研究所，　空间信息集成与３Ｓ工程应用北京市重点实验室，北京１００８７１；３．海军装备研究院，北京１０００７３）　

摘要：地形匹配算法是海底地形辅助导航系统的关键技术之一。根据海底地形的特殊特性，传统地形匹配算法直接应用于ＳＴＡＮ时，易　

出现定位精度大幅降低和算法不稳定性问题。该文提出一种基于地形轮廓匹配原理的新算法，该算法利用改进的Ｈａｕｓｄｏｒｆｆ距离作为水深　实时测量曲线与海底地形图水深曲线之间的度量函数。改进的Ｈａｕｓｄｏｒｆｆ距离对匹配对象存在的小误差不敏感，在一定程度上还可反映空　

间两条曲线的方位关系，该算法定位精度高、稳定性好。利用某海域地形图进行的仿真实验表明：该算法是可行的，定位精度比现有算法　

提高一倍左右。　关健词：地形匹配；海底地形辅助导航；Ｈａｕｓｄｏｒｆｆ距离　

Ｒｅｓｅａｒｃｈ　０ｎ　Ｓｅａｂｅｄ　Ｔｅｒｒａｉｎ　Ｍａｔｃｈ　Ａｌｇｏｒｉｔｈｍ　Ｓｉｍｕｌａｔｉｏｎ　

Ｂａｓｅｄ　ｏｎ　Ｈａｕｓｄｏｒｆｆ　Ｄｉｓｔａｎｃｅ　

ＸＵ　Ｚｕｎｙｉ　，ＹＡＮ　Ｌｅｉ　，ＮＩＮＧ　Ｓｈｕｎｉａｎ　，ＬＩＵ　Ｇｕａｎ￣ｕｎ　

（１．Ｃｏｌｌｅｇｅ　ｏｆ　Ｅｌｅｃｔｒｉｃａｌ　ａｎｄ　Ｍｅｃｈａｎｉｃａｌ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｈｉｎａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｍｉｎｉｎｇ＆Ｔｅｃｈｎｏｌｏｇｙ（Ｂｅ　ｉ“ｇ），Ｂｅｉｊｉｎｇ　１　０００８３；　

２．Ｂｅｉｊｉｎｇ　Ｋｅｙ　Ｌａｂ　ｏｆ　Ｓｐａｔｉａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｉｎｔｅｇｒａｔｉｏｎ　ａｎｄ　３Ｓ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ａｐｐｌｉｃａｔｉｏｎｓ，Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｒｅｍｏｔｅ　Ｓｅｎｓｉｎｇ　ａｎｄ　ＧＩＳ，Ｐｅｋｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，　

Ｂｅｉｊｉｎｇ　１　００８７　１；３．Ｎａｖｙ　Ｅｑｕｉｐｍｅｎｔ　Ｉｎｓｔｉｔｕｔｅ，Ｂｅｉｊｉｎｇ　１　０００７３）　

［Ａｂｓｔｒａｃｔ］Ｔｅｒｒａｉｎ　ｍａｔｃｈ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｋｅｙ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｉｎ　ｓｅａｂｅｄ　ｔｅｒｒａｉｎ　ａｉｄｅｄ　ｎａｖｉｇａｔｉｏｎ　ｓｙｓｔｅｍ（ＳＴＡＮ）．Ｍｏｓｔ　ｏｆ　ｔｅｒｒａｉｎ　ｍａｔｃｈ　

ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｄｅｒｉｖｅｄ　ｆｒｏｍ　ａｉｄｅｄ　ｎａｖｉｇａｔｉｏｎ　ｓｙｓｔｅｍ　ｉｎ　ｔｈｅ　ａｉｒｐｌａｎｅ　ｏｒ　ｔｈｅ　ｍｉｓｓｉｌｅ．Ｗｈｅｎ　ｔｈｅｙ　ａｒｅ　ｄｉｒｅｃｔｌｙ　ａｐｐｌｉｅｄ　ｔＯ　ＳＴＡＮ，ｔｈｅ　ｐｏｓｉｔｉｏｎｉｎｇ　ｐｒｅｃｉｓｉｏｎ　

ｈａｖｅ　ｆａｌｌｅｎ　ｏｆｆ　ｓｈａｒｐｌｙ　ａｎｄ　ｂｅｃｏｍｅ　ｕｎｓｔａｂｌｅ　ｂｅｃａｕｓｅ　ｏｆ　ｔｈｅ　ｓｅａｂｅｄ　ｔｅｒｒａｉｎ　ｐａｒｔｉｃｕｌａｒｉｔｙ．Ｈｅｒｅ，ａ　ｎｅｗ　ａｐｐｒｏａｃｈ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｐｒｉｎｃｉｐｌｅｓ　ｏｆ　ｔｅｒｒａｉｎ　ｃｏｎｔｏｕｒ　ｍａｔｃｈ（ＴＥＲＣＯＭ）ｉｓ　ｐｒｅｓｅｎｔｅｄ．Ｉｔ　ｕｓｅｓ　ｔｈｅ　ｍｏｄｉｆｉｅｄ　Ｈａｕｓｄｏｒｆｆ　ｄｉｓｔａｎｃｅ　ａｓ　ａ　ｃｏｓｔ　ｆｕｎｃｔｉｏｎ　ｆｏｒ　ｔｈｅ　ｔｗｏ　ｓｔｒｉｐｓ　ｏｆ　ｓｐａｔｉａｌ　ｗａｔｅｒ　ｄｅｐｔｈ　ｃｕｒｖｅ　ｉｎ　

ｔｈｅ　ｓｕｒｖｅｙ　ａｎｄ　ｔｈｅ　ｍａｐ．Ａｓ　ｔｈｅ　ｍｏｄｉｆｉｅｄ　Ｈａｕｓｄｏｒｆ　ｄｉｓｔａｎｃｅ　ｉｓ　ｑｕｉｔｅ　ｔｏｌｅｒａｎｔ　ｏｆ　ｔｈｅ　ｓｍａｌｌ　ｐｅｒｔｕｒｂａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ｃｕｒｖｅｓ　ａｎｄ　ｉｎｃｌｕｓｉｖｅ　ｏｆ　ｔｈｅｉｒ　ｄｉｒｅｃｔｉｏｎ　

ｐａｒｔｌｙ，ｔｈｅ　ｎｅｗ　ａｐｐｒｏａｃｈ　ｈａｓ　ｈｉｇｈ　ｐｏｓｉｔｉｏｎｉｎｇ　ｐｒｅｃｉｓｉｏｎ　ａｎｄ　ｒｏｂｕｓｔｎｅｓｓ．Ｍｏｒｅｏｖｅｒ，ｅｘｐｅｒｉｍｅｎｔｓ　ｗｉｔｈ　ｐｅｄｅｓｔｒｉａｎ　ｓｉｍｕｌａｔｉｏｎ　ｃｏｎｆｉｒｍ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　

ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｐｐｒｏａｃｈ．Ｔｈｅ　ｓｙｓｔｅｍ　ａｃｈｉｅｖｅｓ　ｈｉｇｈｅｒ　ｐｏｓｉｔｉｏｎｉｎｇ　ｐｒｅｃｉｓｉｏｎ　ｔｈａｎ　ｔｈａｔ　ｏｆ　ｔｈｅ　ｃｏｎｖｅｎｔｉｏｎａｌ　ＴＥＲＣＯＭ　ａｌｇｏｒｉｔｈｍ．　

［Ｋｅｙ　ｗｏｒｄｓｌ　Ｔｅｒｒａｉｎ　ｍａｔｃｈ；Ｓｅａｂｅｄ　ｔｅｒｒａｉｎ　ａｉｄｅｄ　ｎａｖｉｇａｔｉｏｎ（ＳＴＡＮ）：Ｈａｕｓｄｏｒｆｆｄｉｓｔａｎｃｅ　

ｌ概述　

地形辅助导航系统的研究始于２０世纪６０年代，２０世纪　９０年代后期获得广泛应用，其目的在于提高巡航导弹和战术　

飞机的导航定位精度　１。近年来，随着海洋测量技术的进步，　

将海底地形用于水下运载体（Ｕｎｄｅｒｗａｔｅｒ　Ｖｅｈｉｃｌｅ，ｕｖ）辅助导　航逐渐成为研究的前沿问题。ＳＴＡＮ虽可参考、借鉴导弹、　

飞机上成熟的地形辅助导航理论和算法，但有其自身特殊性：　

海底地形图和水深测量误差大、随机性强；单位时间内可用　

于匹配解算的信息量较少；匹配解算期间惯性导航系统　

（Ｉｎｅｒｔｉａｌ　Ｎａｖｉｇａｔｉｏｎ　Ｓｙｓｔｅｍ，ＩＮＳ）误差积累大；匹配算法实时　

性要求低。　地形匹配算法是地形辅助导航的关键技术之一，主要有　传统的地形轮廓匹配（Ｔｅｒｒａｉｎ　Ｃｏｎｔｏｕｒ　Ｍａｔｃｈ，ＴＥＲＣＯＭ）算法、　

惯性地形辅助导航（Ｓａｎｄｉａ　Ｉｎｅｒｔｉａｌ　Ｔｅｒｒａｉｎ　Ａｉｄｅｄ　Ｎａｖｉｇａｔｉｏｎ，　

ＳＩＴＡＮ）算法以及迭代最近等值线点（１ｔｅｒａｔｉｖｅ　Ｃｌｏｓｅｓｔ　Ｃｏｎｔｏｕｒ　Ｐｏｉｎｔ、ＩＣＣＰ）算法等　｝。将上述匹配算法直接应用于ＳＴＡＮ　

时，通过仿真试验发现：匹配精度普遍较低，最好的仍属传　

统ＴＥＲＣＯＭ算法，定位精度也下降了一个数量级；某些算　

法还出现不稳定性问题。Ｈａｕｓｄｏｒｆ距离是一种极大、极小距　

离，主要用于测量两个点集问的匹配程度，已在二值图像相　似性度量中得到广泛应用｛４－７１￣由于改进的Ｈａｕｓｄｏｒｆ距离对　

匹配对象存在的小误差不敏感，因此在一定程度上还可反映　空间两条曲线的方位关系，本文将其引入ＳＴＡＮ，提出基于　

Ｈａｕｓｄｏｒｆ距离的海底地形匹配算法，以提高ＳＴＡＮ系统的定　

位精度。　

２Ｈａｕｓｄｏｒｆｆ距离　

给定２个有限点集，即　Ａ＝　）　

Ｂ＝｛ｂｌ，ｂ２…，ｂｑ｝　

则点集Ａ、Ｂ之间的Ｈａｕｓｄｏｒｆｆ距离定义为　０　Ｈ（Ａ，Ｂ）＝ｍａｘ（ｈ（Ａ，Ｂ）、ｈ（Ｂ、Ａ））　（１）　ｈ（Ａ，Ｂ）＝　ｈｌｌ，＾（Ｂ，Ａ）＝　ｌｉｂ一“！【　（　）　

式中，ｌ１．１ｌ为定义在点集Ａ和Ｂ上的某种距离范数，本文采　

用Ｌ２范数（欧氏距离）。函数ｈ（Ａ，Ｂ）称为从点集Ａ到点集Ｂ　

的有向Ｈａｕｓｄｏｒｆ距离。Ｈ（Ａ，Ｂ）反映了点集Ａ和点集Ｂ的　

基金项目：国家安全基础研究基金资助重大项目（５　１　３０６０３０　１）　作者简介：徐遵义（１９６９－－），男，博士生，主研方向：地球探测与信　

息技术；晏磊、宁书年，教授、博导；刘光军，高工　

收稿日期：２００６—０６—２７　Ｅ－ｍａｉｌ：ｚｕｎｙｉｘｕ＠ｓｏｈｕ．

ｃｏｍ　维普资讯 http://www.cqvip.com 不匹配程度，Ｈａｕｓｄｏｒｆ距离越大，则两个集合相差越远。　式（１）所定义的Ｈａｕｓｄｏｒｆｆ距离依赖于一个点集和另一个　

点集中最不匹配点的距离，这使得它对任何远离中心的噪声　点非常敏感，为此人们对其进行了改进。Ｄｕｂｕｉｓｓｏｎ和Ｊａｉｎ　

在研究了各种改进形式后，指出平均Ｈａｕｓｄｏｒｆ距离（Ｍｅａｎ　

Ｈａｕｓｄｏｒｆｆ　Ｄｉｓｔａｎｃｅ，ＭＨＤ）具有最好的性能　Ｊ。有向ＭＨＤ定　

义为　

＾　）＝古∑　（３）　

式中，Ｐ为模型集Ａ中元素的个数。　

３基于Ｈａｕｓｄｏｒｆｆ距离的海底地形匹配算法　

３．１搜索区域的确定　在进行地图匹配时，首先是根据ＩＮＳ解算的位置确定搜　

索区域。如果搜索区域太小，则无法包含舰船的实际位置，　导致匹配失败；如果搜索区域太大，不仅增加匹配计算时间，　

而且还可能导致误匹配。通常的方法是根据概率准则获得一　

个误差椭圆，即该误差椭圆必须以一定的概率包含舰船的实　

际位置。根据统计理论，假设ＩＮＳ定位系统的方差、协方差　

矩阵模型为　

Ｐ＝ｌ　一　ｎ　ｌ（４）　ｌ　Ｊ　

式中，Ｏ＂ｘ、　、是定位系统的东向和北向标准差；　：、　是　

方差，　、　是协方差，则误差椭圆　为　

＝　、　＋　－－－　）　】　’　

６＝　、　２＋　２　Ｊ（　１　）　＋４　］　）　

：　一　ａｒｃｔａｎＩ　１　（７）　２　２　ｌ　Ｏ＇ｙ　Ｊ　式中，ａ为椭圆的长半轴，ｂ为椭圆的短半轴，巾是椭圆长　

半轴与正北方向的夹角，　是单位权值的后验方差，又称扩　

展因子，椭圆中心是当前ＩＮＳ给出的位置。由于误差椭圆计　算量大和使用不方便等特点，因此在实际应用时通常将搜索　

区域定义为矩形区域，该矩形区域为椭圆区域的最小包围矩　

形，如图ｌ所示，计算公式为　ｆ　＝２　（８）　

Ｉ　：２ｘ／—ａ２　ｃｏｓ＂￣＋—ｂ２　ｓｉｎ２　

图１矩形搜索区　

通过改变扩展因子　的值来调整椭圆的大小以获得不　

同的置信度，如定位误差的分布是标准正态分布，取　＝３．Ｏ３，　

则可获得９５％的置信度，由于数字地形图误差、计算误差和　

累积误差等都具有不确定性，因此实际计算时扩展因子还要　

增大。　

３．２匹配序列的确定　设水深测量序列为　

Ｌ＝｛（ｓｘ】，ｓｙ】，ＳＺ】），（ｓｘ２，ｓｙ２，ＳＺ２），，，．，（ｓｘＬ，ｓｙＬ，　））　

Ｒ一　（１）Ｌ为水深测量序列的长度；　

（２）（　，ｓｙ　，ＳＺ　），（ｉ＝１，２，…，Ｌ）为测量点的经度、纬度和　

水深值；　（３）ＳＬ在电子海图上相应位置坐标为　

ＭＬ＝｛（ｍｘ】，ｍｙ】），（ｍｘ２，ｍｙ！），…，（ｍｘＬ，ｍｙＬ）｝　

（４）（ｍｘ．，ｍＹｉ）为（　，ｓＹｉ，ＳＺ　）在电子海图上对应的点；　

（５）（　，　）与（ｎ，ｌｘｉ，ｍｙ　）的偏离值（经纬度值）为　

ＤＬ＝｛（　】，ｄｙ】），（ｄｒ！，ｄｙ２）．．．．，（　Ｌ，ｄｙ　）｝　

（６）搜索序列为　

ＭＳＬｊ＝ｌ＜ｍｓ￣Ｊ，ｍｓｙ　ｍｓｚ】　（ｍＳＸ２，，删　ｍｓｚ２　…，（ｍｓｘ￣，，　，ｍｓｚ　）ｊ　（　＝ｌ，２…．，　ｘｙ　）　

如图２所示，以点（ｒｅｘ１，　）为中心，以式（８）计算的　

，Ｙ　为边长创建搜索窗ＩＺｌ，对于搜索窗ＩＺｌ内每一个节点　

以ｓＬ为模板形成搜索序列ＭＳＬｊ，根据式（２）、式（１）计算　Ｈ（ＳＬ，ＭＳＬｉ），根据ｍｉｎ｛Ｈ（ＳＬ，ＭＳＬ２ｊ求出匹配序列。　

水深测量序列（ｓｘｊ．ｓｙｊ．ｓｚｊ）　水深测量序列对应海图水深序列（ｍｘｊ，ｍｙｊ）　搜索序列（ｍｓｘｉｊ．ｍｓｙｉｊ）