中文核心期刊

中国科学引文数据库(CSCD)来源期刊

中国高校优秀科技期刊

中国宇航学会深空探测技术专业委员会会刊

高级检索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

小天体表面纹理曲线精准匹配算法

王光泽 邵巍 郗洪良 姚文龙 黄翔宇

王光泽, 邵巍, 郗洪良, 姚文龙, 黄翔宇. 小天体表面纹理曲线精准匹配算法[J]. 深空探测学报(中英文), 2021, 8(3): 306-314. doi: 10.15982/j.issn.2096-9287.2021.20200096
引用本文: 王光泽, 邵巍, 郗洪良, 姚文龙, 黄翔宇. 小天体表面纹理曲线精准匹配算法[J]. 深空探测学报(中英文), 2021, 8(3): 306-314. doi: 10.15982/j.issn.2096-9287.2021.20200096
WANG Guangze, SHAO Wei, CHI Hongliang, YAO Wenlong, HUANG Xiangyu. Accurate Matching Algorithm of Small Celestial Body Surface Texture Curve[J]. Journal of Deep Space Exploration, 2021, 8(3): 306-314. doi: 10.15982/j.issn.2096-9287.2021.20200096
Citation: WANG Guangze, SHAO Wei, CHI Hongliang, YAO Wenlong, HUANG Xiangyu. Accurate Matching Algorithm of Small Celestial Body Surface Texture Curve[J]. Journal of Deep Space Exploration, 2021, 8(3): 306-314. doi: 10.15982/j.issn.2096-9287.2021.20200096

小天体表面纹理曲线精准匹配算法

doi: 10.15982/j.issn.2096-9287.2021.20200096
基金项目: 国家重点研发计划资助项目(2019YFA0706500);国家自然科学基金资助项目(61773227,61673057,61803028)
详细信息
    作者简介:

    王光泽(1996– ),男,硕士研究生,主要研究方向:计算机视觉、深度学习。通讯地址:青岛科技大学自动化与电子工程学院(266100)E-mail:gzwang96@126.com

    邵巍(1980– ),男,教授,主要研究方向:深空探测器自主导航、机器视觉、图像处理与智能感知。本文通讯作者。通讯地址:青岛科技大学自动化与电子工程学院(266100)E-mail:greatshao@126.com

  • ● The curve descriptors and curvatures are combined for accurate curve matching. ● Constructing scale and rotation invariant curvature based on curvature integral. ● The algorithm in this paper achieves an accurate matching rate of more than 84% under illumination,scale and rotation transformation.
  • 中图分类号: V448.2

Accurate Matching Algorithm of Small Celestial Body Surface Texture Curve

  • 摘要: 探测器着陆过程中可将不规则曲线作为视觉导航陆标,曲线精准匹配是进行视觉导航的重要前提。针对曲线描述符算法难以精准匹配、曲率匹配算法仅能处理两条曲线的问题,提出一种曲线描述符与曲率相结合的曲线精准匹配算法。通过Edge Drawing算法完成曲线提取后,对曲线及支撑区域构建描述符,根据最近邻距离比率原则完成粗匹配;之后计算曲线无符号曲率积分,以等积分间隔对曲率采样,并基于归一化互相关算法完成曲线精准匹配。实验结果表明,该算法在尺度、旋转与光照变换下可以达到84%以上精准匹配率。
    Highlights
    ● The curve descriptors and curvatures are combined for accurate curve matching. ● Constructing scale and rotation invariant curvature based on curvature integral. ● The algorithm in this paper achieves an accurate matching rate of more than 84% under illumination,scale and rotation transformation.
  • 图  1  曲线提取结果

    Fig.  1  Curve extraction result

    图  2  曲线描述符结构

    Fig.  2  Curve descriptor structure

    图  3  曲线粗匹配

    Fig.  3  Curves rough matching

    图  4  曲线拟合结果

    Fig.  4  Curve fitting results

    图  5  连续曲线曲率

    Fig.  5  Curvature of continuous curve

    图  6  曲率积分尺度不变性

    Fig.  6  Scale invariance of curvature integral

    图  7  原曲率与采样后曲率

    Fig.  7  Original curvature and sampled curvature.

    图  8  曲线段匹配度

    Fig.  8  Curve segment matching score

    图  9  暴力匹配结果

    Fig.  9  Brute force match results

    图  10  采取策略后匹配结果

    Fig.  10  The matching result after adopting strategies.

    图  11  弗雷歇距离计算

    Fig.  11  Fréchet distance calculation.

    图  12  不同变换下描述符匹配算法实验结果

    Fig.  12  The experimental results of descriptor matching algorithm under different transformations

    图  13  尺度变换下实验结果

    Fig.  13  The experiment results with scale variation

    图  14  旋转变换下实验结果

    Fig.  14  Matching score with illumination variation

    图  15  光照亮度变换下实验结果

    Fig.  15  The experiment results with illumination variation

    表  1  不同变换下描述符匹配算法精准匹配率

    Table  1  The accurate matching rate of descriptor matching algorithm under different transformations

    匹配方法尺度旋转光照
    描述符/%52.5454.2580.39
    下载: 导出CSV

    表  2  不同变换下精准匹配率

    Table  2  The accurate matching rate under different transformations

    匹配方法尺度旋转光照
    曲线精准匹配/%86.4984.4489.36
    下载: 导出CSV
  • [1] 崔平远,贾贺,朱圣英. 小天体不规则度与光学导航质心提取及应用[J]. 宇航学报,2021,42(1):83-91.

    CUI P Y,JIA H,ZHU S Y. Asteroid irregularity degree and application in centroid extraction of optical navigation[J]. Journal of Astronautics,2021,42(1):83-91.
    [2] TSUDA Y,YOSHIKAWA M,SAIKI T,et al. Hayabusa2–sample return and kinetic impact mission to near-earth asteroid Ryugu[J]. Acta Astronautica,2019,156:387-393. doi:  10.1016/j.actaastro.2018.01.030
    [3] 张哲,孙瑾,杨刘涛. 融合相关滤波与关键点匹配的跟踪算法[J]. 光学学报,2019,39(2):259-267.

    ZHANG Z,YANG J,YANG L T. Tracking algorithm based on correlation filter fusing with keypoint matching[J]. Acta Optica Sinica,2019,39(2):259-267.
    [4] 修春波,马云菲,潘肖楠. 基于距离融合的图像特征点匹配方法[J]. 计算机应用,2019,39(11):3158-3162.

    XIU C B,MA Y F,PAN X N. Image feature point matching method based on distance fusion[J]. Journal of Computer Applications,2019,39(11):3158-3162.
    [5] 李鹤宇,王青. 一种具有实时性的SIFT特征提取算法[J]. 宇航学报,2017,38(8):865-871.

    LI H Y,WANG Q. A Real-time SIFT feature extraction algorithm[J]. Journal of Astronautics,2017,38(8):865-871.
    [6] BAKAMBU J N,LANGLEY C,PUSHPANATHAN G,et al. Field trial results of planetary rover visual motion estimation in Mars analogue terrain[J]. Journal of Field Robotics,2012,29(3):413-425. doi:  10.1002/rob.21409
    [7] 胡涛,贺亮,曹涛,等. 行星陨石坑检测算法研究综述[J]. 载人航天,2020,26(5):656-663. doi:  10.3969/j.issn.1674-5825.2020.05.018

    HU T,HE L,CAO T,et al. Review of planetary crater detection algorithms[J]. Manned Spaceflight,2020,26(5):656-663. doi:  10.3969/j.issn.1674-5825.2020.05.018
    [8] 田阳,李国庆,宋新. 一种三维地形特征提取和匹配方法[J]. 宇航学报,2018,39(6):690-696.

    TIAN Y,LI GUO Q,SONG X. A novel 3D terrain feature detecting and matching method[J]. Journal of Astronautics,2018,39(6):690-696.
    [9] 郑磊,胡维多,刘畅. 基于深度学习的大型陨石坑识别方法研究[J]. 北京航空航天大学学报,2020,46(5):994-1004.

    ZHENG L,HU W D,LIU C. Large crater identification method based on deep learning[J]. Journal of Beijing University of Aeronautics and Astronautics,2020,46(5):994-1004.
    [10] 邵巍,陈海燕,孟琳,等. 基于鲁棒曲线匹配的星表特征跟踪方法[J]. 深空探测学报(中英文),2014,1(1):75-80.

    SHAO W,CHEN H Y,MENG L,et al. Planetary terrain features tracking method based on robust curve matching[J]. Journal of Deep Space Exploration,2014,1(1):75-80.
    [11] CUI P Y,GAO X Z,ZHU S Y,et al. Visual navigation based on curve matching for planetary landing in unknown environments[J]. Acta Astronautica,2020,170:261-274. doi:  10.1016/j.actaastro.2020.01.023
    [12] LIU H,ZHI S,WANG Z. IOCD:Intensity order curve descriptor[J]. International Journal of Pattern Recognition & Artificial Intelligence,2013,27(7):980-985.
    [13] 王志衡,智珊珊,刘红敏. 基于亮度序的均值标准差描述子[J]. 模式识别与人工智能,2013,26(4):409-416. doi:  10.3969/j.issn.1003-6059.2013.04.012

    WANG Z H,ZHI S S,LIU H M. Intensity order based mean-standard deviation descriptor[J]. Pattern Recognition and Artificial Intelligence,2013,26(4):409-416. doi:  10.3969/j.issn.1003-6059.2013.04.012
    [14] LIU H,CHEN L,WANG Z,et al. GOCD:Gradient order curve descriptor[J]. IEICE TRANSACTIONS on Information and Systems,2017,100(12):2973-2983.
    [15] COHEN F S,HUANG Z,YANG Z. Invariant matching and identification of curves using B-splines curve representation[J]. IEEE Transactions on Image Processing,1995,4(1):1-10. doi:  10.1109/83.350818
    [16] TANIAI T,MATSUSHITA Y,SATO Y,et al. Continuous 3D label stereo matching using local expansion moves[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence,2016,40(11):2725.
    [17] 刘双印. 三维自由曲线的立体匹配及重构方法[D]. 成都: 电子科技大学, 2018.

    LIU S Y. Stereo matching and reconstruction of three dimensional free curve[D]. Chengdu: University of Electronic Science and Technology of China, 2018.
    [18] CUI M,FEMIANI J,HU J,et al. Curve matching for open 2D curves[J]. Pattern Recognition Letters,2009,30(1):1-10. doi:  10.1016/j.patrec.2008.08.013
    [19] TOPAL C,AKINLAR C. Edge drawing:a combined real-time edge and segment detector[J]. Journal of Visual Communication and Image Representation,2012,23(6):862-872. doi:  10.1016/j.jvcir.2012.05.004
    [20] ZHANG L,KOCH R. An efficient and robust line segment matching approach based on LBD descriptor and pairwise geometric consistency[J]. Journal of Visual Communication and Image Representation,2013,24(7):794-805. doi:  10.1016/j.jvcir.2013.05.006
    [21] 李莎莎,徐惠霞,邓重阳. 数据点加权最小二乘渐进迭代逼近及其B样条曲线拟合[J]. 计算机辅助设计与图形学学报,2019,31(9):1574-1580.

    LI S S,XU H X,DENG C Y. Data-weighted least square progressive and iterative approximation and related B-spline curve fitting[J]. Journal of Computer-Aided Design & Computer Graphics,2019,31(9):1574-1580.
    [22] 黄世泽,陈威,张帆,等. 基于弗雷歇距离的道岔故障诊断方法[J]. 同济大学学报(自然科学版),2018,46(12):1690-1695.

    HUANG S Z,CHEN W,ZHANG F,et al. Method of turnout fault diagnosis based on Fréchet distance[J]. Journal of Tongji University(Natural Science),2018,46(12):1690-1695.
  • [1] 周涛, 徐洋, 胡海峰, 章思严, 张焕鑫.  “长征八号”运载火箭电气系统一体化设计技术 . 深空探测学报(中英文), 2021, 8(1): 17-26. doi: 10.15982/j.issn.2096-9287.2021.20200014
    [2] 谢浩然, 詹亚锋, 王晓伟, 陈曦.  卫星通导一体化技术及其在探月中的应用 . 深空探测学报(中英文), 2021, 8(2): 154-162. doi: 10.15982/j.issn.2096-9287.2021.20200087
    [3] 武迪, 程林, 王伟, 李俊峰.  基于切换系统的小推力轨迹优化协态初始化方法 . 深空探测学报(中英文), 2021, 8(4): 1-6. doi: 10.15982/j.issn.2096-9287.2021.20200090
    [4] 徐浩, 裴福俊, 蒋宁.  一种基于李群描述的深空探测器姿态估计方法 . 深空探测学报(中英文), 2020, 7(1): 102-108. doi: 10.15982/j.issn.2095-7777.2020.20171117002
    [5] 朱立颖, 叶志玲, 李玉庆, 付中梁, 徐勇.  小天体探测自主绕飞智能规划建模 . 深空探测学报(中英文), 2019, 6(5): 463-469. doi: 10.15982/j.issn.2095-7777.2019.05.007
    [6] 王鹏, 武小宇, 张立华.  低成本多小天体并行交会技术 . 深空探测学报(中英文), 2019, 6(1): 73-81. doi: 10.15982/j.issn.2095-7777.2019.01.011
    [7] 甄贺伟, 徐晓玲, 李果, 周祚万.  应用于空间微生物防护的多尺度杂化抗菌剂研究 . 深空探测学报(中英文), 2019, 6(1): 37-45. doi: 10.15982/j.issn.2095-7777.2019.01.006
    [8] 路伟涛, 任天鹏, 陈略, 韩松涛, 王美.  一种基于小波相关滤波的无线电干涉测量处理方法 . 深空探测学报(中英文), 2019, 6(1): 82-87. doi: 10.15982/j.issn.2095-7777.2019.01.012
    [9] 刘向南, 李英飞, 向程勇, 谌明, 李晓亮.  激光测距通信一体化技术研究及深空应用探索 . 深空探测学报(中英文), 2018, 5(2): 147-153,167. doi: 10.15982/j.issn.2095-7777.2018.02.006
    [10] 刘德赟, 赖小明, 王露斯, 刘晓庆, 赵曾, 张加波, 全齐全.  小天体表面采样技术综述 . 深空探测学报(中英文), 2018, 5(3): 246-261. doi: 10.15982/j.issn.2095-7777.2018.3.007
    [11] 王馨悦, 孙越强, 李永平, 唐萍.  质谱计在行星系统与小天体探测中的应用 . 深空探测学报(中英文), 2017, 4(6): 522-528. doi: 10.15982/j.issn.2095-7777.2017.06.004
    [12] 安然, 王敏, 梁新刚.  基于不变流形的地-月L2点转移轨道优化设计 . 深空探测学报(中英文), 2017, 4(3): 252-257. doi: 10.15982/j.issn.2095-7777.2017.03.008
    [13] 王春锋.  卫星编队自主相对导航与通信一体化系统探讨 . 深空探测学报(中英文), 2017, 4(1): 38-42. doi: 10.15982/j.issn.2095-7777.2017.01.006
    [14] 于正湜, 朱圣英, 崔平远, 刘延杰.  小天体表面移动技术研究进展 . 深空探测学报(中英文), 2017, 4(4): 301-309. doi: 10.15982/j.issn.2095-7777.2017.04.001
    [15] 刘延杰, 朱圣英, 崔平远.  小天体安全着陆与表面探测控制方法研究 . 深空探测学报(中英文), 2016, 3(4): 370-376. doi: 10.15982/j.issn.2095-7777.2016.04.009
    [16] 曾祥远, 李俊峰, 刘向东.  不规则小天体引力场内的广义甩摆轨道 . 深空探测学报(中英文), 2016, 3(1): 29-33. doi: 10.15982/j.issn.2095-7777.2016.01.004
    [17] 席莎, 邵巍.  一种基于多尺度边缘提取的陨石坑检测算法 . 深空探测学报(中英文), 2016, 3(4): 384-388. doi: 10.15982/j.issn.2095-7777.2016.04.011
    [18] 张羽飞, 刘景昊, 黄勇, 谢懿.  利用"火星快车"三程多普勒跟踪数据限定局部洛伦兹不变性 . 深空探测学报(中英文), 2015, 2(2): 144-148. doi: 10.15982/j.issn.2095-7777.2015.02.007
    [19] 江秀强, 陶婷, 杨威, 李爽.  附着小天体的最优制导控制方法 . 深空探测学报(中英文), 2015, 2(1): 53-60. doi: 10.15982/j.issn.2095-7777.2015.01.008
    [20] 于洋, 宝音贺西.  小天体附近的轨道动力学研究综述 . 深空探测学报(中英文), 2014, 1(2): 93-104.
  • 加载中
图(15) / 表 (2)
计量
  • 文章访问数:  164
  • HTML全文浏览量:  51
  • PDF下载量:  31
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-12-25
  • 修回日期:  2021-05-09
  • 网络出版日期:  2021-07-15
  • 刊出日期:  2021-06-30

小天体表面纹理曲线精准匹配算法

doi: 10.15982/j.issn.2096-9287.2021.20200096
    基金项目:  国家重点研发计划资助项目(2019YFA0706500);国家自然科学基金资助项目(61773227,61673057,61803028)
    作者简介:

    王光泽(1996– ),男,硕士研究生,主要研究方向:计算机视觉、深度学习。通讯地址:青岛科技大学自动化与电子工程学院(266100)E-mail:gzwang96@126.com

    邵巍(1980– ),男,教授,主要研究方向:深空探测器自主导航、机器视觉、图像处理与智能感知。本文通讯作者。通讯地址:青岛科技大学自动化与电子工程学院(266100)E-mail:greatshao@126.com

  • ● The curve descriptors and curvatures are combined for accurate curve matching. ● Constructing scale and rotation invariant curvature based on curvature integral. ● The algorithm in this paper achieves an accurate matching rate of more than 84% under illumination,scale and rotation transformation.
  • 中图分类号: V448.2

摘要: 探测器着陆过程中可将不规则曲线作为视觉导航陆标,曲线精准匹配是进行视觉导航的重要前提。针对曲线描述符算法难以精准匹配、曲率匹配算法仅能处理两条曲线的问题,提出一种曲线描述符与曲率相结合的曲线精准匹配算法。通过Edge Drawing算法完成曲线提取后,对曲线及支撑区域构建描述符,根据最近邻距离比率原则完成粗匹配;之后计算曲线无符号曲率积分,以等积分间隔对曲率采样,并基于归一化互相关算法完成曲线精准匹配。实验结果表明,该算法在尺度、旋转与光照变换下可以达到84%以上精准匹配率。

注释:
1)  ● The curve descriptors and curvatures are combined for accurate curve matching. ● Constructing scale and rotation invariant curvature based on curvature integral. ● The algorithm in this paper achieves an accurate matching rate of more than 84% under illumination,scale and rotation transformation.

English Abstract

王光泽, 邵巍, 郗洪良, 姚文龙, 黄翔宇. 小天体表面纹理曲线精准匹配算法[J]. 深空探测学报(中英文), 2021, 8(3): 306-314. doi: 10.15982/j.issn.2096-9287.2021.20200096
引用本文: 王光泽, 邵巍, 郗洪良, 姚文龙, 黄翔宇. 小天体表面纹理曲线精准匹配算法[J]. 深空探测学报(中英文), 2021, 8(3): 306-314. doi: 10.15982/j.issn.2096-9287.2021.20200096
WANG Guangze, SHAO Wei, CHI Hongliang, YAO Wenlong, HUANG Xiangyu. Accurate Matching Algorithm of Small Celestial Body Surface Texture Curve[J]. Journal of Deep Space Exploration, 2021, 8(3): 306-314. doi: 10.15982/j.issn.2096-9287.2021.20200096
Citation: WANG Guangze, SHAO Wei, CHI Hongliang, YAO Wenlong, HUANG Xiangyu. Accurate Matching Algorithm of Small Celestial Body Surface Texture Curve[J]. Journal of Deep Space Exploration, 2021, 8(3): 306-314. doi: 10.15982/j.issn.2096-9287.2021.20200096
    • 近年来,各国纷纷开展了小天体着陆与采样返回任务[1-2],为获得有价值的科学素材,需要探测器着陆到具有较高的科学价值的特定区域,这就需要探测器具备精确导航的能力。视觉导航是目前发展较为成熟的自主导航方法,并在各种深空探测任务中得到不同程度的发展与应用,其利用光学敏感器件获取天体及其表面图像,通过图像中提取的特征来确定探测器空间位置等信息。

      当前用于视觉导航的地标主要分为两类。一类是使用图像中的特征点信息进行导航,例如使用角点检测算法来估计检测器的速度[3-5],Bakambu等[6]提出这类算法通常不如使用图像区域匹配稳定。特征点反映的信息量远低于边缘特征曲线,尤其对于多尺度特征点,存在无法与图像中物理纹理相对应的情况,其应用场景受限。

      另一类是将天体表面的岩石和火山口等自然特征用作导航陆标。同时,这些特征还能在着陆阶段用于障碍物躲避。许多学者对陨石坑的探测和匹配方法做了很多研究[7-9]。这些算法中大多数都使用陨石坑形状、阴影等信息进行匹配,在处理沟壑、重叠的坑或不规则的岩石时容易发生误匹配[10]

      不规则曲线特征在天体表面普遍存在,可作为导航陆标进行导航。对曲线精准匹配是进行视觉导航的重要前提[11]。国内外众多学者针对曲线匹配方法展开研究。

      基于描述符的方法是曲线匹配重要分支。Liu 等[12]通过按亮度划分曲线支撑区域构建了描述符IOCD(Intensity Order Curve Descriptor)。王志衡等[13]为解决描述符主方向难以确定的问题,提出了描述符IOMSD(Intensity Order based Mean Standard Deviation Descriptor),在图像受到模糊、噪声干扰时,可以保持不变性。Chen 等[14]提出梯度阶曲线描述符,对光照变化与噪声干扰有较好的鲁棒性。基于曲线描述符曲线匹配方法根据曲线支撑区域相似度来进行匹配,当局部判断为匹配时,则认为整条曲线匹配,因此基于曲线描述符曲线匹配计算量较小,但难以实现曲线精准匹配。

      基于曲率的方法也是曲线匹配重要方向。Cohen 等[15]提出使用B样条来近似拟合曲线,通过曲率等曲线特征的计算进一步完成曲线匹配工作。Taniai[16] 等提出基于图像分割的空间曲线局部匹配算法,该算法可以得到空间曲线分段描述,并保证了曲线的光滑性[17]。Cui 等[18]通过计算等积分间隔下曲率实现曲线精准匹配,该算法具有尺度与旋转不变性。基于曲率的曲线匹配,适于处理图像中两条曲线匹配问题,当对多条曲线匹配时计算量过于庞大。

      为实现曲线精准匹配,提出一种曲线描述符与曲率相结合的曲线精准匹配算法,通过描述符完成曲线粗匹配,再根据曲率完成精准匹配。本文具体结构安排如下:第一部分介绍了多尺度纹理曲线提取算法与曲线描述符构建方法;第二部分在曲线描述符粗匹配基础上,介绍尺度不变曲率计算与匹配;第三部分在光照、尺度及旋转变换下分析实验结果;第四部分对文章进行总结。

    • 曲线特征提取是匹配的基础,为综合多尺度纹理特征,对原始图像降采样处理,获得一系列不同分辨率图像,建立高斯金字塔模型。

      基于Topal等[19]提出的Edge Drawing算法对每层图像分别进行曲线提取。根据边缘像素特点,使用Sobel算子计算梯度图,为加快计算速度,设置阈值筛选像素梯度,剔除小梯度像素。

      为获得连续边缘曲线,放弃逐像素点边缘判断的思路,而采用基于节点的方法。首先根据梯度图,选择局部梯度极大值对应像素点作为节点。之后由节点开始进行像素连接,当满足以下条件之一停止。

      1)当不处于边缘区域时,即当前像素点经梯度阈值筛选后,属于被剔除部分;

      2)当检测边缘重复时,即对所在曲线进行像素连接过程中,当前像素点已被检测过一次。

      对各尺度提取所得曲线,需变换回原尺度空间。在基于采样系数k构建的高斯金字塔中,对于第j层中检测曲线上一点$({\bar x_i},{\bar y_i})$,变换到原尺度空间后坐标为

      $$ \left\{ {\begin{array}{*{20}{c}} {{x_i} = {{\bar x}_i} \cdot {k^j}} \\ {{y_i} = {{\bar y}_i} \cdot {k^j}} \end{array}} \right. $$ (1)

      将曲线上所有点变换到原尺度后,对离散点进行线性插值。在原尺度空间,对曲线上相邻两点坐标(x1y1)与(x2y2),在区间[x1x2]上某一位置x处纵坐标取值为+

      $$ y = {y_1} + (x - {x_1})\frac{{{y_2} - {y_1}}}{{{x_2} - {x_1}}} $$ (2)

      经过坐标变换与插值,高斯金字塔各层曲线提取结果被变换原尺度空间。多尺度曲线提取结果如图1(b)所示,相比单尺度提取结果如图1(a),所得曲线更加全面。同时基于Edge Drawing算法提取的边缘曲线更加连续,并保证单像素宽度,另外曲线基于节点生成,边缘图像噪声较少。

      图  1  曲线提取结果

      Figure 1.  Curve extraction result

    • 对曲线进行描述时,采用分段描述的方法,将每段曲线近似作为直线进行描述符构建[10,20],该描述符包含曲线自身特征同时加入其周围纹理信息,具备良好的辨识性。

      描述时,将近似直线两侧区域划分为m条矩形带如图2所示将近似直线两侧区域划分为m条矩形带,记作{B1B2B3,··· ,Bm},每条矩形带宽度为w,每个矩形带都是曲线支撑区域的子区域。为保证描述符的旋转不变性,将像素梯度向近似直线方向与正交方向投影。假设子区域中某像素梯度值为g,拟合直线方向为dL,与直线正交方向为d,则局部梯度可表示为

      图  2  曲线描述符结构

      Figure 2.  Curve descriptor structure

      $$ g' = {(g \cdot {d_{\rm L}},g \cdot {d_ \bot })^{\rm T}} $$ (3)

      对于第i段曲线支撑区域的Bj矩形带,通过对第k行不同方向梯度值求和可得

      $$ \left\{ {\begin{array}{*{20}{c}} {p1_k^{ij} = \displaystyle\sum\limits_{g' \cdot {d_ \bot } > 0} {\left| {g' \cdot {d_ \bot }} \right|} } \\ {p2_k^{ij} = \displaystyle\sum\limits_{g' \cdot {d_ \bot } < 0} {\left| {g' \cdot {d_ \bot }} \right|} } \\ {p3_k^{ij} = \displaystyle\sum\limits_{g' \cdot {d_L} > 0} {\left| {g' \cdot {d_L}} \right|} } \\ {p4_k^{ij} = \displaystyle\sum\limits_{g' \cdot {d_L} < 0} {\left| {g' \cdot {d_L}} \right|} } \end{array}} \right. $$ (4)

      对所有曲线段梯度值求和,可得整条曲线Bj矩形带的第k行梯度信息

      $$ \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} p1_k^j = \displaystyle\sum {p{\rm{1}}_k^{ij}} \\ p{\rm{2}}_k^j = \displaystyle\sum {p{\rm{2}}_k^{ij}} \\ p{\rm{3}}_k^j = \displaystyle\sum {p{\rm{3}}_k^{ij}} \\ \end{array} \\ {p{\rm{4}}_k^j = \displaystyle\sum {p{\rm{4}}_k^{ij}} } \end{array}} \right. ,\; j \in 1,2,\cdots,l $$ (5)

      将每行不同方向梯度之和堆叠,可得曲线Bj矩形带梯度矩阵

      $$ {{ H}_j} = \left( {\begin{array}{*{20}{c}} {p1_1^j}&{p1_2^j}&{\cdots}&{p1_n^j} \\ {p2_1^j}&{p2_2^j}&{\cdots}&{p2_n^j} \\ {p3_1^j}&{p3_2^j}&{\cdots}&{p3_n^j} \\ {p4_1^j}&{p4_2^j}&{\cdots}&{p4_n^j} \end{array}} \right) \in {R^{4 \times n}} $$ (6)

      其中:n为计算第j条矩形带所需行数

      $$ n = \left\{ {\begin{array}{*{20}{l}} {2w,j = 1||m} \\ {3w,{\rm{else}}} \end{array}} \right. $$ (7)

      Hj每行进行均值向量Uj与标准差向量Sj的求解计算,同时为满足光照不变性进行归一化处理,两者共同构成曲线矩形带Bj的描述符BDj可表示为

      $$ { B}{{ D}_j} = {(\frac{{{ U}_j^{\rm T}}}{{\left| {\left| {{ U}_j^{\rm T}} \right|} \right|}},\frac{{{ S}_j^{\rm T}}}{{\left| {\left| {{ S}_j^{\rm T}} \right|} \right|}})^{\rm T}} \in {R^8} $$ (8)

      通过对所有矩形带描述符进行求解,获得曲线描述符CBD

      $$ { CBD} = {({ BD}_1^{\rm T},{ BD}_2^{\rm T},\cdots,{ BD}_m^{\rm T})^{\rm T}} \in {R^{8 \times m}} $$ (9)

      根据最近邻距离比例原则,采用BF匹配算法匹配曲线描述符,曲线粗匹配结果如图3所示。

      图  3  曲线粗匹配

      Figure 3.  Curves rough matching

    • 基于曲线描述符的曲线匹配算法仅能对曲线粗略匹配,难以实现最相似部分匹配,影响后续导航精度。本文在此基础上加入基于曲率的曲线匹配算法,以实现对曲线的精准匹配。原始曲线为离散数据形式,为尽可能准确计算曲线曲率,需对曲线数据进行平滑拟合,同时削弱噪声的影响。

      传统的贝塞尔曲线拟合方法仅需少量控制点即可生成复杂平滑曲线,控制简便且具有较强控制能力,但灵活性较差,难以修改局部特征,某一控制点发生改变对拟合曲线整体都有影响。针对贝塞尔算法的缺点,B样条拟合算法被提出,该算法逼近多边形特征精度更高,且具备局部修改性[21],B样条算法曲线拟合表达式为

      $$ P(t) = \sum\limits_{i = 0}^n {{P_i}{F_{i,k}}(t){\rm{ }}(0 \leqslant t \leqslant 1)} $$ (10)

      其中:n表示用来拟合曲线的点个数;Pi表示拟合曲线的离散点;Fikt)表示的K阶基函数定义为

      $$ {F_{i,k}}(t) = \frac{1}{{k!}}\sum\limits_{m = 0}^{k - i} {( - } {C_{k + 1}}{)^m}{(t + k - m - j)^k}{\rm{ }}(0 \leqslant t \leqslant 1) $$ (11)

      三次B样条曲线相比二次B样条曲线更加光滑,同时计算量在可接受范围。通过4个相邻离散点计算可得三次B样条曲线,对式(11)进行求解可得

      $$ \left\{ \begin{array}{l} {F_{0,3}}(t) = \dfrac{1}{6}{(1 - t)^3} \\ {F_{1,3}}(t) = \dfrac{1}{6}(3{t^3} - 6{t^2} + 4) \\ {F_{2,3}}(t) = \dfrac{1}{6}( - 3{t^3} + 3{t^2} - 3t + 1) \\ {F_{3,3}}(t) = \dfrac{1}{6}{t^3} \end{array} \right. $$ (12)

      将式(12)代入式(10),得到三次B样条曲线表达式为

      $$ P(t) = {P_0}{F_{0,3}}(t) + {P_1}{F_{1,3}}(t) + {P_2}{F_{2,3}}(t) + {P_3}{F_{3,3}}(t) $$ (13)

      分别用2种算法拟合曲线,结果如图4所示。与3次B样条曲线拟合图4(b)相比,贝塞尔曲线拟合结果图4(a)整体趋势平滑,但对曲线细节表现力较差。基于曲率的曲线匹配算法是根据曲线弯曲程度进行匹配,对曲线细节拟合要求高,贝塞尔拟合曲线易造成误匹配,故B样条曲线拟合算法更适合。

      图  4  曲线拟合结果

      Figure 4.  Curve fitting results

    • 对于图5中连续曲线,曲率表示为曲线弧切线转角与弧长之比

      $$ k = \frac{{\Delta \alpha }}{{\Delta s}} $$ (14)

      其中:$\vartriangle \alpha $为弧切线转角,$\vartriangle s$为对应弧长。

      图  5  连续曲线曲率

      Figure 5.  Curvature of continuous curve

      在曲线曲率基础上进行曲率积分计算,由于曲线中存在拐点,且有符号曲率积分非单调变化,导致同一积分数值可能对应多个曲率值,因此本文选择使用无符号曲率积分。给定弧长为l的曲线,曲线曲率绝对值积分为

      $$ K(0:l) = \int_0^l {|k(s)|{\rm{d}}s} $$ (15)

      其中,K(0∶l)为曲率绝对值之和。将该曲线缩放a倍得到新曲线,其曲率绝对值之和为

      $$ \bar K(0:al) = \int_0^{al} {|\bar k(\bar s)|{\rm{d}}\bar s} $$ (16)

      其中:$\bar K(0:al)$为缩放后曲线曲率绝对值之和;$\bar k(\bar s)$为缩放后曲线曲率,由于曲率与曲线长度成反比,因此

      $$ |\bar k(\bar s)| = \frac{1}{a}|k(s)| $$ (17)
      $$ {\rm{d}}\bar s = a{\rm{d}}s $$ (18)

      将式(17)与式(18)代入式(16)可得

      $$ \begin{aligned}[b] \bar K(0:al) & = \int_0^{al} {\frac{1}{a}|k(s)|{\rm{d}}\bar s} \\ & = \int_0^l {\frac{1}{a}|k(s)|a{\rm{d}}s} \\ & = \int_0^l {|k(s)|{\rm{d}}s} \\ \end{aligned} $$ (19)

      由式(19)可得曲率积分的尺度不变性,即如果两输入曲线具有相同的部分,则对曲线进行尺度变换,且两者尺度因子为m,则它们在弧长轴上(坐标轴横轴)的跨度之比也为m,且曲率积分(坐标轴纵轴)跨度相等[19],如图6所示。

      图  6  曲率积分尺度不变性

      Figure 6.  Scale invariance of curvature integral

      利用曲率绝对值积分尺度不变性,以等曲率积分间隔对曲率进行采样,使采样后曲率具有尺度不变特性。对于尺度不同但存在相似部分的两条曲线,其曲率在经过采样处理后,其相同部分在横轴上跨越相同长度,两条曲线精准匹配问题转换为采样后两曲率曲线的精准匹配问题,简化匹配难度。

      等积分间隔采样后,原曲率曲线变化剧烈处被拉长,而变化较平缓处被压缩。在设置采样间隔时,曲率积分间隔越小,曲线细节信息越准确,但同时会保留更多噪声,且计算量大;而间隔增大时会丢失部分数据信息,但可以削弱噪声影响并且减小计算量,如图7所示。经实验,积分间隔设置为5时,能保证数据精度同时加快运行速度。

      图  7  原曲率与采样后曲率

      Figure 7.  Original curvature and sampled curvature.

    • 对于两条曲线采样后曲率匹配,采用归一化互相关算法进行相似度计算,计算公式为

      $$ v(u) = \frac{{\sum\nolimits_{i \in \Omega } {[f(i) - \overline f ][t(i - u) - \overline t ]} }}{{\sqrt {\sum\nolimits_{i \in \Omega } {{{[f(i) - \overline f ]}^2}} \sum\nolimits_{i \in \Omega } {{{[t(i - u) - \overline t ]}^2}} } }} $$ (20)

      其中:f为较短曲线中的一部分,作为模板窗口沿着较长曲线滑动;u为两条曲线的偏移量;$\bar t$为模板内曲率均值;$\bar f$为滑动窗口在第二条曲线上曲率均值;v取值范围为[–1,1],数值越大相似度越高。

      为确定两曲线最相似部分,从较短曲线a中截取所有可能曲线段与另一曲线b进行曲率匹配。对于截取的第i条曲线段ci在曲线b上滑动匹配时,将互相关系数最大处(图8 P点)作为曲线段ci与曲线b的匹配度。曲线a上所有可能曲线段完成计算后,将匹配度最高曲线段作为两曲线最相似部分。

      图  8  曲线段匹配度

      Figure 8.  Curve segment matching score

      对于所有可能曲线段进行匹配时,曲线段越短通常相关系数越大,直接利用归一化互相关系数暴力匹配,计算量大且得到的大多是长度短、难以利用的曲线如图9所示。

      图  9  暴力匹配结果

      Figure 9.  Brute force match results

      为提高匹配效果并减小计算量采取以下策略。

      1)设置曲线段长度与步长

      精准匹配时对曲线a中所有曲线段进行互相关计算效率较低。经多次试验,设置步长与截取曲线长度为

      $$ \left\{ \begin{array}{l} step = \max (0.02 \cdot {n_s},1) \\ {n_j} \in A \\ A = \left\{ {0.4{n_s},0.5{n_s},0.6{n_s},0.7{n_s},0.8{n_s},0.9{n_s},{n_s}} \right\} \end{array} \right. $$ (21)

      其中:step为步长;nj为截取曲线长度;A为截取曲线长度集合;ns为曲线a长度。

      2)修改曲线段匹配度计算方式

      考虑到曲线长度较长时,计算所得相关系数一般较低,为获得较长曲线匹配结果,计算匹配得分时加入曲线长度作为权重系数

      $$ S{\rm{ }} = {\rm{ }}v{\rm{ }}×{\rm{ }}L $$ (22)

      其中:S为匹配结果最终得分;L为曲线段c的长度。

      设曲线a长度为nsb长度为nl,暴力匹配方法截取曲线长度${n_j} \in [1,{n_s}]$,此时匹配计算复杂度

      $$ \begin{aligned}[b] T({n_s},{n_l}) & = \sum\limits_{{n_j} = 1}^{{n_s}} {{n_l} - {n_j} + 1} \\ & = - 0.5n_s^2 + 0.5{n_s} + {n_s}{n_l} \\ &= O({n^2}) \end{aligned} $$ (23)

      采取两策略后,匹配时间复杂度为

      $$ \begin{aligned}[b] T({n_s},{n_l}) & = \sum\limits_{{n_j} \in A} {\frac{1}{{0.02}}} \\ & = 350 \\ & = O(1) \end{aligned} $$ (24)

      比较式(23)与式(24)可知,匹配时间复杂度最高次项由2次降为0次,计算量大幅减少,同时匹配效果得到提升如图10所示。

      图  10  采取策略后匹配结果

      Figure 10.  The matching result after adopting strategies.

    • 对于本文提出的曲线精准匹配算法,从时间复杂度与精准匹配率两方面进行分析。

      曲线匹配时间与硬件环境密切相关,因此使用算法执行所需要的计算工作量即时间复杂度来进行比较。基于描述符进行曲线匹配时,采用最近邻比率原则,需要找到最近邻和次近邻匹配项,设两匹配图像提取到的曲线数分别为n1n2,则描述符匹配时间复杂度为

      $$ {T_d} = {n_2} \cdot {n_1} = O({n^2}) $$ (25)

      如2.3节中所述,在曲率匹配中一对曲线计算时间复杂度为O(1),则曲率匹配总体时间复杂度为

      $$ {T_c} = ({n_d}) \cdot O(1) = O(n) $$ (26)

      其中nd为基于描述符匹配得到的匹配曲线对数。

      将描述符与曲率结合后算法时间复杂度为

      $$ T = {T_d} + {T_c} = O({n^2}) + O(n) = O({n^2}) $$ (27)

      比较式(25)、式(26)、式(27)可得,在基于描述符匹配基础上,加入曲率匹配后时间复杂度仍然为On2)。本文提出曲线精准匹配算法与基于描述符的匹配算法相比,算法时间复杂度保持不变。

      在精准匹配率方面,由于探测器下降阶段,图像纹理特征会发生缩放、旋转及光照变换,故分别在3种情况下进行实验。为评价不同变换下曲线精准匹配效果,对匹配曲线进行离散弗雷歇距离计算[22]。对于2条匹配曲线,根据两者长度之比设置采样间隔,得到长度相等的两曲线AB。之后通过旋转、平移将两曲线端点重合如图11所示。

      图  11  弗雷歇距离计算

      Figure 11.  Fréchet distance calculation.

      计算两曲线弗雷歇距离时,对于曲线B上一点m,计算该点到曲线A上各点欧氏距离,将所有欧氏距离中最小值作为候选弗雷歇距离。对曲线B中各点完成计算后,将候选弗雷歇距离最大值作为曲线A与曲线B的弗雷歇距离。经实验,在评估时将弗雷歇距离小于5的结果作为精准匹配。

      实验所用为从NASA官网得到的真实小天体图像。图12为尺度、旋转与光照变换下描述符匹配算法实验结果,表1为3种变换下相应精准匹配率。结合图12表1可知,基于描述符匹配算法在尺度与旋转变换下精准匹配效果较差。

      图  12  不同变换下描述符匹配算法实验结果

      Figure 12.  The experimental results of descriptor matching algorithm under different transformations

      表 1  不同变换下描述符匹配算法精准匹配率

      Table 1.  The accurate matching rate of descriptor matching algorithm under different transformations

      匹配方法尺度旋转光照
      描述符/%52.5454.2580.39

      图13~15展示了尺度、旋转与光照变换下本文所述曲线精准匹配算法实验结果,表2为3种变换下相应精准匹配率。结合图13~15表2可以看出,在尺度、旋转与光照变换下,本文描述的描述符与曲率相结合的曲线精准匹配算法可以达到84%以上精准匹配率。

      图  13  尺度变换下实验结果

      Figure 13.  The experiment results with scale variation

      图  14  旋转变换下实验结果

      Figure 14.  Matching score with illumination variation

      图  15  光照亮度变换下实验结果

      Figure 15.  The experiment results with illumination variation

      表 2  不同变换下精准匹配率

      Table 2.  The accurate matching rate under different transformations

      匹配方法尺度旋转光照
      曲线精准匹配/%86.4984.4489.36
    • 针对曲线描述符难以精准匹配、曲率匹配仅能处理两条曲线的问题,本文提出一种将两者相结合的曲线精准匹配算法,主要包括曲线提取、描述符匹配与曲率匹配3部分。曲线提取部分根据Edge Drawing算法进行边缘曲线检测;描述符匹配部分对曲线及周围支撑区域信息进行描述,根据最近邻距离比率原则完成粗匹配;曲率匹配部分根据无符号曲率积分对曲率曲线重采样,并根据归一化互相关算法完成曲线精准匹配。实验结果表明,本文提出的算法可以达到84%以上的精准匹配率。

参考文献 (22)

目录

    /

    返回文章
    返回