留言板

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

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

一种基于带权A*搜索算法的正射影像镶嵌线网络优化方法

郑茂腾 熊小东 朱俊锋 鲁一慧 刘薇 邱焕斌

郑茂腾, 熊小东, 朱俊锋, 鲁一慧, 刘薇, 邱焕斌. 一种基于带权A*搜索算法的正射影像镶嵌线网络优化方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(11): 1650-1658. doi: 10.13203/j.whugis20180080
引用本文: 郑茂腾, 熊小东, 朱俊锋, 鲁一慧, 刘薇, 邱焕斌. 一种基于带权A*搜索算法的正射影像镶嵌线网络优化方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(11): 1650-1658. doi: 10.13203/j.whugis20180080
ZHENG Maoteng, XIONG Xiaodong, ZHU Junfeng, LU Yihui, LIU Wei, QIU Huanbin. A Novel Seam-Line Network Optimization Method Using the Weighted A* Algorithm for UAV Imagery[J]. Geomatics and Information Science of Wuhan University, 2019, 44(11): 1650-1658. doi: 10.13203/j.whugis20180080
Citation: ZHENG Maoteng, XIONG Xiaodong, ZHU Junfeng, LU Yihui, LIU Wei, QIU Huanbin. A Novel Seam-Line Network Optimization Method Using the Weighted A* Algorithm for UAV Imagery[J]. Geomatics and Information Science of Wuhan University, 2019, 44(11): 1650-1658. doi: 10.13203/j.whugis20180080

一种基于带权A*搜索算法的正射影像镶嵌线网络优化方法

doi: 10.13203/j.whugis20180080
基金项目: 

国家自然科学基金 41601502

国家重点研发计划 2017YFB0503800

中央高校基本科研业务费专项资金(中国地质大学(武汉)) CUG170664

详细信息
    作者简介:

    郑茂腾, 博士, 副研究员, 主要从事航空航天摄影测量的理论与方法研究。tengve@163.com

  • 中图分类号: P237

A Novel Seam-Line Network Optimization Method Using the Weighted A* Algorithm for UAV Imagery

Funds: 

The National Natural Science Foundation of China 41601502

the National Key Research and Development Program of China 2017YFB0503800

the Fundamental Research Funds for the Central Universities, China University of Geosciences(Wuhan) CUG170664

More Information
    Author Bio:

    ZHENG Maoteng, PhD, associate researcher, specializes in photogrammetry and remote sensing. E-mail:tengve@163.com

  • 摘要: 提出了一种基于带权A*搜索算法的镶嵌线网络优化方法。首先,利用标准Voronoi图生成初始镶嵌线网络;然后,利用测区的数字表面模型(digital surface model,DSM)数据生成对应的高程梯度图(也称为边缘图);再对初始镶嵌线网络的节点进行自动调整,将位于建筑物上的节点移动至附近的地面;最后,利用一种带权A*搜索算法,结合高程梯度图,对初始镶嵌线网络中的每一条镶嵌线进行智能优化,避开建筑物或者高差变化大的区域,获得最优的镶嵌线网络。利用3组真实的无人机数据对该方法进行实验,初步结果表明,该方法适用于排列不规则的测区,可有效优化镶嵌线网络,镶嵌线可自动避开大部分城区建筑物以及山区的山脊等,对城区以及山区影像都可得到高质量的正射影像。实验结果表明,对于第1组数据,此方法得到的结果在镶嵌线的选取上要优于商业软件OrthoVista。
  • 图  1  Voronoi图的结构示意图

    Figure  1.  Voronoi Diagram of a Constrained Area

    图  2  DSM和DEM的断面对比图

    Figure  2.  DSM and DEM of the Same Area

    图  3  像素的8个邻域

    Figure  3.  8 Directions in the Neighborhood of a Pixel

    图  4  高程梯度图与影像叠加对比

    Figure  4.  Comparison of Edge Diagram and the Corresponding Image

    图  5  镶嵌线网络节点活动范围示意图

    Figure  5.  Combined Constrained Area (Filled Area)

    图  6  镶嵌线节点优化对比

    Figure  6.  Comparison of Refined Vertex Location and the Initial Vertex Location

    图  7  A*搜索算法前两步各点的权值示意图

    Figure  7.  Weight of the First Two Steps of the A* Searching Algorithm

    图  8  3组实验数据的地面覆盖范围

    Figure  8.  Ground Coverage of Three Datasets

    图  9  第1组数据的初始镶嵌线网络以及优化后的镶嵌线网络对比

    Figure  9.  Comparison of Initial and Refined Seam-Line Networks with Dataset 1

    图  10  第1组数据的初始镶嵌线以及用本文方法优化后的镶嵌线的部分细节对比图

    Figure  10.  Comparison of Initial Seam-Lines and the Optimized Seam-Lines with Dataset 1 in Details

    图  11  第2组数据的初始镶嵌线网络和本文方法优化后的镶嵌线对比图

    Figure  11.  Comparison of Initial and Refined Seam-Lines with Dataset 2

    图  12  第2组数据的初始镶嵌线以及用本文方法优化后的镶嵌线的部分细节对比图

    Figure  12.  Comparison of the Initial Seam-Lines and the Optimized Seam-Lines with Test Dataset 2 in Details

    图  13  第3组数据的初始镶嵌线网络和本文方法优化后的镶嵌线对比图

    Figure  13.  Comparison of Initial and Refined Seam-Lines with Respective to Dataset 3

    图  14  第3组数据的初始镶嵌线以及用本文方法优化后的镶嵌线的部分细节对比图

    Figure  14.  Comparison of the Initial Seam-Lines and the Optimized Seam-Lines with Test Dataset 3 in Details

    图  15  本文方法与OrthoVista处理得到的镶嵌线网络在两个不同区域的细节对比图

    Figure  15.  Comparison of the Seam-Lines Refined by OrthoVista and the Proposed Method in Details

    表  1  实验数据信息

    Table  1.   Experimental Data Infomration

    数据 地形 正射影像数 采样间隔/m 单幅覆盖范围/m2
    1 城区 75 0.24 320×430
    2 山区 120 0.35 1 189×1 035
    3 郊区 52 0.05 270×201
    下载: 导出CSV

    表  2  本文方法和OrthoVista的运行时间对比

    Table  2.   Comparison of Processing Time with OrthoVista and the Proposed Method

    方法 处理时间/s 被镶嵌线穿过的建筑物数目/个
    初始镶嵌线 221
    OrthoVista 272 130
    本文方法 118 51
    下载: 导出CSV
  • [1] Botterill T, Mills S, Green R. Real-Time Aerial Image Mosaicking[C]. The IEEE International Conference of Image and Vision Computing, Queenstown, New Zealand, 2010
    [2] Chon J, Kim H, Lin C. Seam-line Determination for Image Mosaicking: A Technique Minimizing the Maximum Local Mismatch and the Global Cost[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2010, 65: 86–92 doi:  10.1016/j.isprsjprs.2009.09.001
    [3] Fernández E, Garfinkel R, Arbiol R. Mosaicking of Aerial Photographic Maps via Seams Defined by Bottleneck Shortest Paths[J].Operations Research, 1998, 46: 293–304 doi:  10.1287/opre.46.3.293
    [4] Fernández E, Martí R. GRASP for Seam Drawing in Mosaicking of Aerial Photographic Maps[J]. Journal of Heuristics, 1999(5):181–197 doi:  10.1023-A-1009633811636/
    [5] Kerschner M. Seamline Detection in Colour OrthoImage Mosaicking by Use of Twin Snakes[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2001, 56: 53–64 doi:  10.1016/S0924-2716(01)00033-8
    [6] Mills S, McLeod P. Global Seamline Networks for Orthomosaic Generation via Local Search[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013, 75: 101–111 doi:  10.1016/j.isprsjprs.2012.11.003
    [7] Pan J, Wang M, Li D, et al. Automatic Generation of Seamline Network Using Area Voronoi Diagrams with Overlap[J]. IEEE Transactions on Geosciences and Remote Sensing, 2009, 47: 1 737–1 744 doi:  10.1109/TGRS.2008.2009880
    [8] Pan J, Zhou Q, Wang M. Seamline Determination Based on Segmentation for Urban Image Mosaicking [J]. IEEE Geoscience and Remote Sensing Letters, 2014, 11: 1 335–1 339 doi:  10.1109/LGRS.2013.2293197
    [9] Soille P. Morphological Image Compositing[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28: 673–683 doi:  10.1109/TPAMI.2006.99
    [10] Wan Y, Wang D, Xiao J, et al. Tracking of Vector Roads for the Determination of Seams in Aerial Image Mosaics[J]. IEEE Geoscience and Remote Sensing Letters, 2012, 9: 328-332 doi:  10.1109/LGRS.2011.2167712
    [11] Wan Y, Wang D, Xiao J, et al. Automatic Determination of Seamlines for Aerial Image Mosaicking Based on Vector Roads Alone[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013, 76: 1-10 doi:  10.1016/j.isprsjprs.2012.11.002
    [12] Yu L, Holden E J, Dentith M C, et al. Towards the Automatic Selection of Optimal Seam Line Locations When Merging Optical Remote Sensing Images[J]. International Journal of Remote Sensing, 2012, 33: 1 000-1 014 doi:  10.1080/01431161.2010.545083
    [13] Zagrouba E, Barhoumi W, Amri S. An Efficient Image-Mosaicing Method Based on Multifeature Matching[J]. Machine Vision and Applications, 2009, 20: 139-162 doi:  10.1007/s00138-007-0114-y
    [14] Zhao Y, Han T, Feng S, et al. Remote Sensing Image Mosaic by Incorporating Segmentation and the Shortest Path[J]. Communications in Computer and Information Science, 2013, 398: 684-691 http://cn.bing.com/academic/profile?id=943d067158ddcf3e1acd1661a52ded62&encoded=0&v=paper_preview&mkt=zh-cn
    [15] 左志权, 张祖勋, 张剑清, 等. DSM辅助下城区大比例尺正射影像镶嵌线智能检测[J].测绘学报, 2011, 40(1):84-89 http://d.old.wanfangdata.com.cn/Periodical/chxb201101016

    Zuo Zhiquan, Zhang Zuxun, Zhang Jianqing, et al. Seamline Intelligent Detection in Large-scale Urban Orthoimage Mosaicking[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(1):84-89 http://d.old.wanfangdata.com.cn/Periodical/chxb201101016
    [16] 陈继溢, 许彪, 张力, 等.采用最优生成树的正射影像镶嵌线快速智能检测[J].测绘学报, 2015, 44(10):1 125-1 131 doi:  10.11947/j.AGCS.2015.20140467

    Chen Jiyi, Xu Biao, Zhang Li, et al. Fast and Intelligent Seamline Detection for Orthoimage Mosaicking Based on Minimum Spanning Tree[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10): 1 125-1 131 doi:  10.11947/j.AGCS.2015.20140467
    [17] 袁修孝, 钟灿.一种改进的正射影像镶嵌线最小化最大搜索算法[J].测绘学报, 2012, 41(2):199-204 http://www.cqvip.com/QK/90069X/201202/41590545.html

    Yuan Xiuxiao, Zhong Can. An Improvement of Minimize Local Maximum Algorithm on Searching Seam Line for Orthoimage Mosaicking[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2):199-204 http://www.cqvip.com/QK/90069X/201202/41590545.html
    [18] 岳贵杰, 杜黎明, 刘凤德, 等. A*搜索算法的正射影像镶嵌线自动提取[J].测绘科学, 2015, 40(4): 151-154 http://d.old.wanfangdata.com.cn/Periodical/chkx201504033

    Yue Guijie, Du Liming, Liu Fengde, et al. Automatic Seamline Detection for Orthophoto Mosaicking Based on A* Searching Algorithm[J], Science of Surveying and Mapping, 2015, 40(4): 151-154 http://d.old.wanfangdata.com.cn/Periodical/chkx201504033
    [19] 丁锴为, 邹峥嵘, 张云生, 等.基于图割算法的正射影像镶嵌线自动选择[J].测绘与空间地理信息, 2016(9): 54-56 doi:  10.3969/j.issn.1672-5867.2016.09.016

    Ding Kaiwei, Zou Zhengrong, Zhang Yunsheng, et al. Automatically Seam-line Selection for Mosaicking Ortho-Photo via Graph Cut Algorithm[J]. Geomatics and Spatial Information Technology, 2016(9): 54-56 doi:  10.3969/j.issn.1672-5867.2016.09.016
    [20] Dijkstra E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik, 1959, 1: 269-271 doi:  10.1007/BF01386390
    [21] Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1972, 37(4): 28-29 doi:  10.1109-TSSC.1968.300136/
    [22] Niu L, Zhuo G. An Improved Real 3D A* Algorithm for Difficult Path Finding Situation[J]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2008, 37(B4): 927-930
    [23] 孙杰, 马洪超, 汤璇, 等.机载LiDAR正射影像镶嵌线智能优化研究[J].武汉大学学报∙信息科学版, 2011, 36(3):325-328 http://ch.whu.edu.cn/CN/abstract/abstract495.shtml

    Sun Jie, Ma Hongchao, Tang Xuan, et al. Optimization of LiDAR System Ortho-image Mosaic Seam-line[J]. Geomatics and Information Science of Wuhan University, 2011, 36(3): 325-328 http://ch.whu.edu.cn/CN/abstract/abstract495.shtml
    [24] 张剑清, 孙明玮, 张祖勋, 等.基于蚁群算法的正射影像镶嵌线自动选择[J].武汉大学学报∙信息科学版, 2009, 34(6): 675-678 http://ch.whu.edu.cn/CN/abstract/abstract1342.shtml

    Zhang Jianqing, Sun Mingwei, Zhang Zuxun, et al. Automated Seamline Detection for Orthophoto Mosaicking Based on Ant Colony Algorithm[J]. Geomatics and Information Science of Wuhan University, 2009, 34(6): 675-678 http://ch.whu.edu.cn/CN/abstract/abstract1342.shtml
    [25] 焦晨静, 陈时雨, 赵鹏祥, 等.顾及结构信息的DOM镶嵌线搜索算法[J].测绘科学, 2016, 41(1): 190-193 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chkx201601037

    Jiao Chenjing, Chen Shiyu, Zhao Pengxiang, et al. An Improved DOM Seam Line Searching Algorithm Based on Structural Information[J]. Science of Surveying and Mapping, 2016, 41(1): 190-193 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chkx201601037
    [26] Chen Q, Sun M, Hu X, et al.Automatic Seamline Network Generation for Urban Orthophoto Mosaick with the Use of a Digital Surface Model[J]. Remote Sensing, 2014(6):12 334–12 359 http://cn.bing.com/academic/profile?id=c5a0270ccb5594118376b0ba3adeeec2&encoded=0&v=paper_preview&mkt=zh-cn
    [27] Ma Hongchao, Sun Jie. Intelligent Optimization of Seam-Line Finding for Orthophoto Mosaicking with LiDAR Point Clouds[J]. Journal of Zhejiang University: Science C, 2011, 12: 417–429 doi:  10.1631/jzus.C1000235
    [28] Pang S, Sun M, Hu X, et al. SGM-based Seamline Determination for Urban Orthophoto Mosaicking[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2016, 112: 1-12 doi:  10.1016/j.isprsjprs.2015.11.007
    [29] 汪韬阳, 张过, 李德仁, 等.卫星遥感影像的区域正射纠正[J].武汉大学学报∙信息科学版, 2014, 39(7):838-842 http://ch.whu.edu.cn/CN/abstract/abstract3030.shtml

    Wang Taoyang, Zhang Guo, Li Deren, et al. Block Ortho-rectification for Satellite Images[J]. Geomatics and Information Science of Wuhan University, 2014, 39(7): 838-842 http://ch.whu.edu.cn/CN/abstract/abstract3030.shtml
    [30] 袁修孝, 段梦梦, 曹金山, 等.正射影像镶嵌线自动搜索的视差图算法[J].测绘学报, 2015, 44(8):877-883 http://d.old.wanfangdata.com.cn/Periodical/chxb201508009

    Yuan Xiuxiao, Duan Mengmeng, Cao Jinshan, et al. A Seam Line Detection Algorithm for Orthophoto Mosaicking Based on Disparity Image[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(8):877-883 http://d.old.wanfangdata.com.cn/Periodical/chxb201508009
    [31] Milgram D L. Computer Methods for Creating Photomosaics[J]. IEEE Transactions on Computers, 1975, 24: 1 113–1 119 doi:  10.1109-T-C.1975.224142/
    [32] 潘俊, 王密, 李德仁, 等.基于顾及重叠的面Voronoi图的接缝线网络生成方法[J].武汉大学学报∙信息科学版, 2009, 34(5): 518-522 http://ch.whu.edu.cn/CN/abstract/abstract1256.shtml

    Pan Jun, Wang Mi, Li Deren, et al. Generation of Seamling Network Using Area Voronoi Diagram with Overlap[J]. Geomatics and Information Science of Wuhan University, 2009, 34(5): 518-522 http://ch.whu.edu.cn/CN/abstract/abstract1256.shtml
    [33] 潘俊, 王密, 李德仁, 等.接缝线网络的自动生成及优化方法[J].测绘学报, 2010, 39(3): 289-294 http://d.old.wanfangdata.com.cn/Periodical/chxb201003012

    Pan Jun, Wang Mi, Li Deren, et al. Approach for Automatic Generation and Optimization of Seamline Network[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(3): 289-294 http://d.old.wanfangdata.com.cn/Periodical/chxb201003012
    [34] Kim K H, Sin S, Lee W. Exploring 3D Shortest Distance Using A* Algotihm in Unity3D[J]. Journal of Arts and Imaging Science, 2015, 2(3): 1-5
  • [1] 吴建华, 戴鹏, 胡烈云.  一种面向多尺度面状居民地匹配的Voronoi图自适应构建算法 . 武汉大学学报 ● 信息科学版, 2022, 47(2): 304-312. doi: 10.13203/j.whugis20200324
    [2] 岳庆兴, 高小明, 唐新明.  基于半全局优化的资源三号卫星影像DSM提取方法 . 武汉大学学报 ● 信息科学版, 2016, 41(10): 1279-1285. doi: 10.13203/j.whugis20140730
    [3] 王邦松, 张继贤, 卢丽君, 黄国满, 赵争.  利用Voronoi图辅助星载干涉雷达配准 . 武汉大学学报 ● 信息科学版, 2016, 41(10): 1339-1343. doi: 10.13203/j.whugis20140549
    [4] 李佳田, 罗富丽, 余莉, 张蓝, 康顺, 林艳.  梯度Voronoi图及其构建算法 . 武汉大学学报 ● 信息科学版, 2016, 41(2): 163-170. doi: 10.13203/j.whugis20140025
    [5] 胡玮, 陶伟东, 苑振宇, 王结臣.  一种Voronoi图的扫描地图矢量化方法 . 武汉大学学报 ● 信息科学版, 2013, 38(4): 470-474.
    [6] 沈晶, 刘纪平, 林祥国, 赵荣.  集成距离变换和区域邻接图生成Delaunay三角网的方法研究 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 1000-1003.
    [7] 付仲良, 刘思远.  MR-tree空间索引的Voronoi图改进及其并行空间查询方法 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1490-1494.
    [8] 王海军, 邓羽, 张文婷, 贺三维.  利用元胞自动机和遗传算法的Voronoi图生成 . 武汉大学学报 ● 信息科学版, 2010, 35(7): 778-781.
    [9] 穆超, 余洁, 许磊, 郭培煌.  基于高分辨率遥感影像的DSM建筑物点的提取研究 . 武汉大学学报 ● 信息科学版, 2009, 34(4): 414-417.
    [10] 潘俊, 王密, 李德仁.  基于顾及重叠的面Voronoi图的接缝线网络生成方法 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 518-521.
    [11] 闫超德, 白建军, 赵仁亮.  基于Voronoi图的点状目标邻近空间分布测度方法 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 48-51.
    [12] 李光强, 邓敏, 朱建军.  基于Voronoi图的空间关联规则挖掘方法研究 . 武汉大学学报 ● 信息科学版, 2008, 33(12): 1242-1245.
    [13] 闫超德, 赵仁亮, 陈军, 赵学胜.  Voronoi图的首最邻近递归收敛特性及其应用 . 武汉大学学报 ● 信息科学版, 2008, 33(11): 1194-1197.
    [14] 童晓冲, 贲进, 张永生.  基于二十面体剖分格网的球面实体表达与Voronoi图生成 . 武汉大学学报 ● 信息科学版, 2006, 31(11): 966-970.
    [15] 唐亮, 黄培之, 谢维信.  顾及数据空间分布特性的模糊C-均值聚类算法研究 . 武汉大学学报 ● 信息科学版, 2003, 28(4): 476-479.
    [16] 陈军, 赵仁亮, 乔朝飞.  基于Voronoi图的GIS空间分析研究 . 武汉大学学报 ● 信息科学版, 2003, 28(S1): 32-37.
    [17] 闫浩文, 郭仁忠.  基于Voronoi图的空间方向关系形式化描述模型 . 武汉大学学报 ● 信息科学版, 2003, 28(4): 468-471,479.
    [18] 闫浩文, 郭仁忠.  用Voronoi图描述空间方向关系的理论依据 . 武汉大学学报 ● 信息科学版, 2002, 27(3): 306-310.
    [19] 李成名, 陈军, 朱英浩.  基于Voronoi图的空间邻近定义与查询 . 武汉大学学报 ● 信息科学版, 1998, 23(2): 128-131.
    [20] 李成名, 陈军.  Voronoi图生成的栅格算法 . 武汉大学学报 ● 信息科学版, 1998, 23(3): 208-210.
  • 加载中
图(15) / 表(2)
计量
  • 文章访问数:  2549
  • HTML全文浏览量:  103
  • PDF下载量:  110
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-06-13
  • 刊出日期:  2019-11-05

一种基于带权A*搜索算法的正射影像镶嵌线网络优化方法

doi: 10.13203/j.whugis20180080
    基金项目:

    国家自然科学基金 41601502

    国家重点研发计划 2017YFB0503800

    中央高校基本科研业务费专项资金(中国地质大学(武汉)) CUG170664

    作者简介:

    郑茂腾, 博士, 副研究员, 主要从事航空航天摄影测量的理论与方法研究。tengve@163.com

  • 中图分类号: P237

摘要: 提出了一种基于带权A*搜索算法的镶嵌线网络优化方法。首先,利用标准Voronoi图生成初始镶嵌线网络;然后,利用测区的数字表面模型(digital surface model,DSM)数据生成对应的高程梯度图(也称为边缘图);再对初始镶嵌线网络的节点进行自动调整,将位于建筑物上的节点移动至附近的地面;最后,利用一种带权A*搜索算法,结合高程梯度图,对初始镶嵌线网络中的每一条镶嵌线进行智能优化,避开建筑物或者高差变化大的区域,获得最优的镶嵌线网络。利用3组真实的无人机数据对该方法进行实验,初步结果表明,该方法适用于排列不规则的测区,可有效优化镶嵌线网络,镶嵌线可自动避开大部分城区建筑物以及山区的山脊等,对城区以及山区影像都可得到高质量的正射影像。实验结果表明,对于第1组数据,此方法得到的结果在镶嵌线的选取上要优于商业软件OrthoVista。

English Abstract

郑茂腾, 熊小东, 朱俊锋, 鲁一慧, 刘薇, 邱焕斌. 一种基于带权A*搜索算法的正射影像镶嵌线网络优化方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(11): 1650-1658. doi: 10.13203/j.whugis20180080
引用本文: 郑茂腾, 熊小东, 朱俊锋, 鲁一慧, 刘薇, 邱焕斌. 一种基于带权A*搜索算法的正射影像镶嵌线网络优化方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(11): 1650-1658. doi: 10.13203/j.whugis20180080
ZHENG Maoteng, XIONG Xiaodong, ZHU Junfeng, LU Yihui, LIU Wei, QIU Huanbin. A Novel Seam-Line Network Optimization Method Using the Weighted A* Algorithm for UAV Imagery[J]. Geomatics and Information Science of Wuhan University, 2019, 44(11): 1650-1658. doi: 10.13203/j.whugis20180080
Citation: ZHENG Maoteng, XIONG Xiaodong, ZHU Junfeng, LU Yihui, LIU Wei, QIU Huanbin. A Novel Seam-Line Network Optimization Method Using the Weighted A* Algorithm for UAV Imagery[J]. Geomatics and Information Science of Wuhan University, 2019, 44(11): 1650-1658. doi: 10.13203/j.whugis20180080
  • 正射影像镶嵌时,由于相邻影像的拍摄角度、时间不一,在地面高程起伏大的区域容易造成几何差异,因此在选择镶嵌线时,应当尽量选择高程变化较小的区域,以最大程度上减少镶嵌线上的几何差异。针对这一问题,学者们提出了很多不同的解决方法,这些方法主要可以分为基于像方以及基于物方的镶嵌线选取方法两大类。基于像方的方法主要是利用影像的颜色或者灰度信息来选取镶嵌线,使得镶嵌后的影像在镶嵌线上的视觉差异达到最小。基于物方的方法则是利用物方的高度信息,使镶嵌线避开建筑物或者高程变化大的区域,从而得到几何差异最小的镶嵌线。常用的地面高程信息包括数字高程模型(digital elevation model, DEM)、数字表面模型(digital surface model, DSM),以及激光探测与测距点云(light detecting and ranging, LiDAR)等。

    基于像方的镶嵌线选取方法不需要任何其他辅助信息,仅使用影像的颜色或者灰度信息[1-19]。输入数据就是单纯的正射影像,因此该方法对数据的要求不高。通常情况下,这些方法都定义了一个能量函数,该能量函数能够反映镶嵌线上的灰度或者灰度变化信息,灰度变化越大,能量函数值越大,反之亦然。因此选取最优的镶嵌线可以转化为求某个能量函数的最小值问题。这些方法包括双胞胎蛇算法(twin snake algorithm)[5]、最小路径搜索算法(Dijkstra’s algorithm)[2, 10-11, 20]、最小最大搜索算法[2, 17]、A*搜索算法[18, 21-23]、形态学算法[9]、蚁群算法[24]、最优生成树[16]、动态规划[25]、图割算法[19]等。

    基于物方的镶嵌线选取方法则是利用地面辅助信息(如DEM、DSM、LiDAR点云等)来确定最优镶嵌线。在这些地面辅助信息的帮助下,可以使镶嵌线避开建筑物或者高程变化大的区域[15, 23, 26-30]。当镶嵌线经过的区域均为平地时,镶嵌线上面的几何差异可忽略不计,此时镶嵌线即为最优的镶嵌线。但是文献[26]中同时使用了DEM、DSM两种辅助数据,并生成了影像高程同步模型(orthoimage elevation synchronous model, OESM)数据。DEM数据是DSM数据的滤波结果,滤波算法的选取直接关系到DEM的质量,也关系到镶嵌线选取的质量。同理,文献[23, 27]中使用的是LiDAR点云的滤波结果。点云的滤波质量也会直接影响镶嵌线的选取。文献[28, 30]都采用了一种不需要地面辅助数据的方法,仅仅是利用外方位元素生成视差图,但这两个文献中使用的外方位元素数据也相当于是物方辅助数据。上述方法均不能适用于山区或无人机影像。另外,这些方法均没有提到如何对镶嵌线网络的节点进行优化,如果镶嵌线网络的节点正好位于建筑物上,则经过该节点的镶嵌线无论经过怎样的优化都必然会穿过这一建筑物。

    无论是基于像方的方法还是基于物方的方法,它们都存在一定的局限性,特别是对于山区影像以及高分辨率且排列不规则的无人机影像的镶嵌,目前仍然没有一个很好的解决方案。本文提出一种基于A*搜索算法的正射影像镶嵌方法,仅使用DSM数据作为辅助信息,可以有效解决无人机影像以及山区影像的正射镶嵌问题。文献[18, 23, 27]也采用了A*搜索算法,但是均没有将高程信息引入到A*搜索算法的能量函数中,而仅仅是利用高程信息生成障碍物区域图,以便A*搜索算法避开这些障碍物。本文利用DSM数据生成了高程梯度图,然后将高程梯度数据引入到A*搜索算法的能量函数中,使得算法搜索时考虑到高程梯度的影响,从而自动避开高程梯度大的区域,也即避开城区建筑物、山区山脊线等容易产生几何差异的区域,最终生成最优的镶嵌线。

    • 初始镶嵌线网络一般是采用Voronoi图来生成。以每一张正射影像的中心点为种子点,生成一系列相互连接且没有重叠度的多边形网络,构成Voronoi图。每个种子点都被一个唯一的多边形包围,其结构如图 1所示。更多关于Voronoi图的特点以及生成方法可以参考文献[31-33]。

      图  1  Voronoi图的结构示意图

      Figure 1.  Voronoi Diagram of a Constrained Area

    • 采用Voronoi图生成的初始镶嵌线网络还存在一系列问题,如节点位置可能位于建筑物上,镶嵌线也可能穿越建筑物或者高度变化大的区域。因此,这些节点以及镶嵌线还需要进一步优化。为了使镶嵌线网络中的节点和镶嵌线均能避开建筑物或者高度变化大的区域,本文首先利用DSM数据来生成高程梯度图,然后根据高程梯度图来重新调整节点位置,并对每一条镶嵌线进行重新选取和优化,最终得到一个最佳的镶嵌线网络。

    • DSM数据并不能直接反映地物高度情况,如果同时还有DEM数据,可以将DSM数据与DEM数据作差,即可得到地物的高度(见图 2)。

      图  2  DSM和DEM的断面对比图

      Figure 2.  DSM and DEM of the Same Area

      图 2中可以看出,如果只有DSM,则无法得到地物的高度信息。因此文献[26]同时使用了DSM和DEM数据,文献[27]使用了过滤后的LiDAR点云。如果是山区,DSM与DEM几乎是相同的,此时文献[26-27]的方法无法获得最优的镶嵌线。

      本文仅使用DSM数据,虽然不能直接得到地物的高度信息,但是可以得到地面的高程梯度信息。如果是平地,则高程梯度接近0,此时镶嵌线可以通过该区域;如果是建筑物,则其边缘地区的高程梯度较大,此时镶嵌线不能通过该区域。换言之,可以通过高程梯度图作为辅助来选取最优的镶嵌线,只要使镶嵌线优先通过高程梯度较小的区域,则可以确保镶嵌线避开高程起伏大的区域,同时也可以避开建筑物以及植被等。

      首先计算DSM中每个像素的高程梯度,然后将高程梯度值作为灰度值重新写入一个新的Geotiff文件,该文件的大小与DSM大小一致,只是灰度值记录的不是该像素的高度信息,而是该像素的高程梯度信息,这个新的Geotiff文件就是高程梯度图。每个像素的高程梯度计算方法如图 3所示,其计算公式为:

      图  3  像素的8个邻域

      Figure 3.  8 Directions in the Neighborhood of a Pixel

      $$R\left( i,j \right)=\text{max }\!\!~\!\!\text{ }\left( {{g}_{1}},{{g}_{2}}\ldots {{g}_{8}} \right)$$ (1)

      式中,gk(k=1, 2…8)分别表示8个方向的梯度值。

      $$I\left( i,j \right)=\left\{ \begin{array}{*{35}{l}} 0,\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }R\left( i,j \right)\le T \\ k\times R\left( i,j \right),\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }R\left( i,j \right)>T\text{ }\!\!~\!\!\text{ } \\ \end{array} \right.$$ (2)

      式中,R(ij)表示像素(ij)的高程梯度;k是将高程梯度转化为图像灰度的系数;I (ij)为高程梯度图的灰度;T是阈值,当高程梯度大于该阈值时,将其乘以系数k转化成高程梯度图的灰度值,当高程梯度小于该阈值时,则认为该像素位于平地区域,将其灰度值设为0。本文中阈值T被设置为0.5 m。

      经过上述处理后,可以得到高程梯度图,如图 4所示。

      图  4  高程梯度图与影像叠加对比

      Figure 4.  Comparison of Edge Diagram and the Corresponding Image

      图 4中可以看出,高程梯度图基本上都是由边缘组成,因此也可以称之为边缘图。利用这个边缘图,可以引导镶嵌线避开建筑物或者其他高程变化大的区域(如山脊等)。

    • 初始镶嵌线网络的节点位置具有随机性,它有可能落在建筑物或者高程变化较大的区域,此时必须将这些节点进行重新调整,否则经过该节点的镶嵌线必然会穿过建筑物或者高程变化较大的区域。本文的节点即传统办法中所谓的镶嵌线的开始点和结束点。文献[6]中提出了一种优化节点的方法,该方法以节点为中心,划定了一个圆形区域,允许节点在该圆形区域内自由移动,以选取最佳的节点位置。但是该方法划定的区域太小,若建筑物在影像上所占的面积较大,超过了节点活动范围,此时无论节点在活动范围内如何移动,该节点总是位于建筑物上。对于无人机影像,其分辨率较高,建筑物在影像上的面积一般较大,因此文献[6]的方法还存在一定的局限性。

      本文在初始镶嵌线网络的基础上,对每个节点划定了一个较大的活动范围,然后在该范围内搜索最优的节点位置。在利用Voronoi图生成的初始镶嵌线网络中,如图 1所示,除了边界上的点,其余每个节点都与3个节点相邻。可以将某个节点的3个邻接节点连接起来,构成一个三角形区域,如图 5中的红色虚线三角形所示,这个区域即是该节点的活动范围。在该范围内移动节点,不会改变与该点相邻的3个多边形的凸属性,即保持了所有多边形均是凸多边形的良好特性。同时,为了避免出现漏洞,节点还必须位于节点周围影像的重叠度范围内,如图 5中的绿色虚线区域(此处为三度重叠区域)。因此将节点的活动范围进一步限制在红色虚线三角形与绿色虚线多边形的交会区域,也即图 5中的填充区域。

      图  5  镶嵌线网络节点活动范围示意图

      Figure 5.  Combined Constrained Area (Filled Area)

      划定节点活动范围以后,根据节点的高度以及梯度信息,在该范围内搜索最优的节点位置,当节点位于建筑物顶部时,其高度值比其相邻的地面要高,此时通过搜索活动范围内的高度最小的点,可以将建筑物顶部的点移动至地面,同时为了确保节点远离建筑物边缘,还要搜索高度梯度最小的点,也即搜索高度加上梯度绝对值最小的位置。重新定位节点后的镶嵌线网络如图 6所示。

      图  6  镶嵌线节点优化对比

      Figure 6.  Comparison of Refined Vertex Location and the Initial Vertex Location

      图 6中可以看出,经过节点优化处理后,镶嵌线网络中的位于建筑物上的节点均已被移动至附近的地面,且保持了镶嵌线网络中凸多边形的属性。

    • 经过对镶嵌线网络的所有节点位置进行优化之后,最后的步骤就是对每一条镶嵌线进行优化,也即重新选取镶嵌线,使镶嵌线避开建筑物或者高程变化较大的区域。本文利用边缘图的辅助,结合一种带权A*搜索算法,在搜索最短路径的时候,考虑路径上高程梯度值的影响,使得搜索到的路径在避开高程梯度较大区域的同时,路径长度最短。

      A*搜索算法是在文献[21]中被首次提出,该算法是一种图形搜索算法[34],主要应用于游戏等最短路径搜索。其数学原理可以在原始文献[21]中找到。它采用的能量函数为:

      $$F=G+H$$ (3)

      式中,F表示从起始点经过当前搜索点到结束点的总能量;G表示从起始点到当前搜索点的距离值;H表示从当前搜索点到结束点的估计距离值。

      通过上述能量函数,A*算法可以最终搜索到一条最短路径,其具体的搜索步骤如图 7所示。图 7中,每个方块代表 1个像素,灰色方块A表示搜索起点,灰色方块B表示结束点,黑色方块表示需要越过的障碍区。

      图  7  A*搜索算法前两步各点的权值示意图

      Figure 7.  Weight of the First Two Steps of the A* Searching Algorithm

      图 7(a)可以看出,在起点A的周围,右下角的F值最小(F = 54),所以A*算法将选择该像素点作为下一步的起点,如图 7(b)所示,然后重新计算该点周围8领域内每个像素点的F值。如果8领域内有像素点的F值已经计算过了,则重新计算该点的F值,并比较原F值与新F值的大小。如果新F值小于原F值,则保留新F值,否则继续使用原F值。以此类推,逐像素进行搜索,即可最终找到一条从AB的最短路径。更加具体的搜索步骤可以参考文献[34]。

      在正射影像镶嵌中,理想的镶嵌线不仅需要路径最短,同时还需要该路径上的高程梯度值最小,也即该路径上的几何差异最小(辐射差异在本文中暂不考虑)。换言之,一条最优的镶嵌线必须满足在高程梯度值最小的基础上,同时路径长度也最小。根据上述思想,本文提出了一种新的能量函数:

      $${{F}_{w}}=\alpha \left( G+H \right)+\beta I$$ (4)

      式中,Fw是新的能量值;I是当前点的高程梯度值;α ∈ (0,1]、β ∈ [ 0,1 ]分别表示原始能量(G + H)和高程梯度I在新的能量函数中的权重。

      D = G + H,将式(4)简化得到:

      $${{F}_{w}}=\alpha D+\beta I$$ (5)

      式中,D表示能量函数中的距离项;I表示能量函数中的高程梯度项。

      如果α = 1且β = 0,则式(5)就是一个标准的A*搜索算法,此时搜索到的路径就是一条从起始点到结束点的直线。系数α的值必须大于零,因为距离项D可以确保搜索算法总是指向结束点;若α = 0,距离项对能量函数的影响为零,则不能保证搜索算法正常收敛。当α > 0且β > 0时,距离项D和高程梯度项I将会同时影响搜索算法,影响的大小取决于系数αβ的大小。此时搜索算法将会引导镶嵌线避开那些高程梯度值较大的区域,同时能够确保最终收敛至结束点。系数αβ可以被认为是新的能量函数中距离项和高程梯度项的权值,因此该算法被称为带权A*搜索算法。

      新的能量函数中,距离项和高程梯度项对搜索结果的影响可以通过系数αβ来进行调节,如果α>β,则搜索到的路径将更加趋近于一条直线,但可能会穿过很多建筑物或者高程梯度大的区域;如果α < β,则搜索到的路径可以避免更多的建筑物或者高程梯度大的区域,但此时的路径也将更加弯曲,长度更长。因而系数αβ需要根据数据的不同特性来进行调整。如果测区属于城区,则建筑物较多,此时应该适当增加高程梯度项的权值β,也即让搜索算法具有更大的避开建筑物的能力,同时牺牲了路径的长度;而如果是郊区或者山区,建筑物较少,则适当减小高程梯度项的权值β。针对本文中的无人机城区数据,选取α = 0.3,β = 0.6;而对于山区数据,则选择α = 0.3,β = 0.4。

    • 采用3组真实的无人机数据测试本文提出的算法,原始数据由北京中测智绘科技有限公司提供,每组数据的DSM采用该公司的MiRauge3D摄影测量软件处理得到,具体的数据信息如表 1所示。3组数据的地面覆盖范围如图 8所示,从图 8中可以看出,3组数据的地面排列较为不规则,特别是第3组数据。

      表 1  实验数据信息

      Table 1.  Experimental Data Infomration

      数据 地形 正射影像数 采样间隔/m 单幅覆盖范围/m2
      1 城区 75 0.24 320×430
      2 山区 120 0.35 1 189×1 035
      3 郊区 52 0.05 270×201

      图  8  3组实验数据的地面覆盖范围

      Figure 8.  Ground Coverage of Three Datasets

      根据本文的算法思想,笔者开发了一套正射影像纠正与智能镶嵌系统,同时还选取了知名正射影像制作软件OrthoVista(版本4.5)作为对照,该软件是从官方网站www.OrthoVista.com下载的试用版。所有的实验均是在一台普通计算机上完成,配置为Inter (R) Core(TM) i5-33320M 2.60 GHz CPU, 8.00 GB RAM, 64 bit Windows 7操作系统。

    • 分别对3组数据生成初始镶嵌线网络和优化后的镶嵌线网络,并将其叠加至拼接后的大正射影像上,如图 9所示。

      图  9  第1组数据的初始镶嵌线网络以及优化后的镶嵌线网络对比

      Figure 9.  Comparison of Initial and Refined Seam-Line Networks with Dataset 1

      图 9图 10中可以看出,第1组数据是城区影像,初始的镶嵌线网络中,很多节点位于建筑物上,且镶嵌线也大部分穿越了建筑物,而经过本文方法优化后的镶嵌线网络,大部分建筑物上的节点被调整到了附近的地面,且镶嵌线也避开了大部分建筑物。

      图  10  第1组数据的初始镶嵌线以及用本文方法优化后的镶嵌线的部分细节对比图

      Figure 10.  Comparison of Initial Seam-Lines and the Optimized Seam-Lines with Dataset 1 in Details

      图 11图 12中可以看出,第2组数据是山区影像,人工建筑物较少,但是山区有很多高程变化较大的区域,如山脊等,如果镶嵌线经过这些区域,仍可能会在拼接后的正射影像上产生几何差异。初始镶嵌线大部分穿过了山脊线,而经过本文方法优化后的镶嵌线则沿着高程变化最小的方向延伸,避开了这些山脊线,从而避免了可能出现在拼接后正射影像上的几何差异。从图 11的中间可以看出,对于山区的少量建筑物,本文方法生成的镶嵌线也能够正常避开。

      图  11  第2组数据的初始镶嵌线网络和本文方法优化后的镶嵌线对比图

      Figure 11.  Comparison of Initial and Refined Seam-Lines with Dataset 2

      图  12  第2组数据的初始镶嵌线以及用本文方法优化后的镶嵌线的部分细节对比图

      Figure 12.  Comparison of the Initial Seam-Lines and the Optimized Seam-Lines with Test Dataset 2 in Details

      第3组数据排列十分不规则,如图 8(c)所示。但本文方法仍然可以很好地处理这类数据,如图 1314所示,经过本文方法的处理,得到了一张完整的正射影像图,仅仅是边缘部位由于DSM数据的缺失而产生了边缘不规则现象,而且镶嵌线避开了大部分明显建筑物。但是由于该数据大部分区域为植被,因此镶嵌线优化效果未能完全体现。

      图  13  第3组数据的初始镶嵌线网络和本文方法优化后的镶嵌线对比图

      Figure 13.  Comparison of Initial and Refined Seam-Lines with Respective to Dataset 3

      图  14  第3组数据的初始镶嵌线以及用本文方法优化后的镶嵌线的部分细节对比图

      Figure 14.  Comparison of the Initial Seam-Lines and the Optimized Seam-Lines with Test Dataset 3 in Details

    • 为了比较本文算法与其他算法的区别,利用OrthoVista软件处理本文数据中的第1组数据,整体结果如图 9(b)所示,具体的细节对比见图 15

      图  15  本文方法与OrthoVista处理得到的镶嵌线网络在两个不同区域的细节对比图

      Figure 15.  Comparison of the Seam-Lines Refined by OrthoVista and the Proposed Method in Details

      图 15中可以看出,OrthoVista生成的镶嵌线并不能很好地避开建筑物,而且部分区域的镶嵌线还发生了相互缠绕;本文方法生成的镶嵌线避开了大部分建筑物,且镶嵌线之间没有相交,镶嵌线具有唯一性。从表 2中镶嵌线穿过建筑物的数目也印证了上述说法。另外,从表 2中还可以看出,本文方法的运行时间更少,即效率更高。

      表 2  本文方法和OrthoVista的运行时间对比

      Table 2.  Comparison of Processing Time with OrthoVista and the Proposed Method

      方法 处理时间/s 被镶嵌线穿过的建筑物数目/个
      初始镶嵌线 221
      OrthoVista 272 130
      本文方法 118 51
    • 本文提出了一种基于带权A*搜索算法的正射影像镶嵌线自动选取方法,使用3组真实数据对其进行测试,并对比常用的正射影像制作软件OrthoVista,可以得出以下结论:(1)本文方法可以有效处理无人机影像(包括影像排列极其不规则的测区)以及山区影像,生成的镶嵌线网络能够较好地避开建筑物以及高程变化较大的区域,拼接后的正射影像几何差异较小。(2)针对第一组测试数据,本文方法的处理结果在时间和质量上均优于商业软件OrthoVista。

      本文的带权A*搜索算法不仅可以搜索最优的镶嵌线,同时还可以通过引入其他不同的能量项来搜索其他最优路径。本文使用的Voronoi图分割算法仅适用于影像重叠度较大(一般要求相邻影像重叠度大于60%)的测区,当影像重叠度较小时,利用Voronoi图计算得到的初始镶嵌线网络容易出现漏洞。另外,本文的方法使用了DSM数据,因此其结果与DSM数据的质量有直接关系,如果DSM能够正确地反映地面情况,则处理结果是正确的,如果DSM数据质量较差,以至于不能反映地面的实际情况,则处理的结果也会随之产生偏差。

参考文献 (34)

目录

    /

    返回文章
    返回