一种基于带权A~*搜索算法的正射影像镶嵌线网络优化方法
|
摘要
提出了一种基于带权A~*搜索算法的镶嵌线网络优化方法。首先,利用标准Voronoi图生成初始镶嵌线网络;然后,利用测区的数字表面模型(digital surface model, DSM)数据生成对应的高程梯度图(也称为边缘图);再对初始镶嵌线网络的节点进行自动调整,将位于建筑物上的节点移动至附近的地面;最后,利用一种带权A~*搜索算法,结合高程梯度图,对初始镶嵌线网络中的每一条镶嵌线进行智能优化,避开建筑物或者高差变化大的区域,获得最优的镶嵌线网络。利用3组真实的无人机数据对该方法进行实验,初步结果表明,该方法适用于排列不规则的测区,可有效优化镶嵌线网络,镶嵌线可自动避开大部分城区建筑物以及山区的山脊等,对城区以及山区影像都可得到高质量的正射影像。实验结果表明,对于第1组数据,此方法得到的结果在镶嵌线的选取上要优于商业软件OrthoVista。
An automatic optimization method based on weighted A~* search algorithm is proposed. The main process can be divided into four steps: the first step is to generate the initial seam-line network using standard Voronoi map; and then use the digital surface model(DSM) data to generate the corresponding elevation gradient map(also known as edge map); then the initial nodes of the seam-line network are automatically adjusted, the nodes located on the building are moved to the near ground; finally a weighted A~* algorithm combined with the elevation gradient map are used to pilot all the seam-lines to avoid high buildings,and obtain the optimal seam-line network. This method is tested with three real UAV dataset. Preliminary result has shown that our method is suitable for unmanned aerial vehicle imagery,and acceptable mosaic image is produced. The result is proved to be better than the result of OrthoVista for dataset 1.
An automatic optimization method based on weighted A~* search algorithm is proposed. The main process can be divided into four steps: the first step is to generate the initial seam-line network using standard Voronoi map; and then use the digital surface model(DSM) data to generate the corresponding elevation gradient map(also known as edge map); then the initial nodes of the seam-line network are automatically adjusted, the nodes located on the building are moved to the near ground; finally a weighted A~* algorithm combined with the elevation gradient map are used to pilot all the seam-lines to avoid high buildings,and obtain the optimal seam-line network. This method is tested with three real UAV dataset. Preliminary result has shown that our method is suitable for unmanned aerial vehicle imagery,and acceptable mosaic image is produced. The result is proved to be better than the result of OrthoVista for dataset 1.
引文
[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
[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
[4] Fernández E,MartíR. GRASP for Seam Drawing in Mosaicking of Aerial Photographic Maps[J]. Journal of Heuristics,1999(5):181–197
[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
[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
[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
[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
[9] Soille P. Morphological Image Compositing[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28:673–683
[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
[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
[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
[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
[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
[15] 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(左志权，张祖勋，张剑清，等. DSM辅助下城区大比例尺正射影像镶嵌线智能检测[J].测绘学报，2011,40(1):84-89)
[16] 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(陈继溢，许彪，张力，等.采用最优生成树的正射影像镶嵌线快速智能检测[J].测绘学报，2015,44(10):1 125-1 131)
[17] 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(袁修孝，钟灿.一种改进的正射影像镶嵌线最小化最大搜索算法[J].测绘学报，2012,41(2):199-204)
[18] 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(岳贵杰，杜黎明，刘凤德，等. A*搜索算法的正射影像镶嵌线自动提取[J].测绘科学，2015,40(4):151-154)
[19] 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(丁锴为，邹峥嵘，张云生，等.基于图割算法的正射影像镶嵌线自动选择[J].测绘与空间地理信息，2016(9):54-56)
[20] Dijkstra E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik,1959,1:269-271
[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
[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] Sun Jie,Ma Hongchao,Tang Xuan,et al. Optimization of LiDAR System Ortho-image Mosaic Seamline[J]. Geomatics and Information Science of Wuhan University,2011,36(3):325-328(孙杰，马洪超，汤璇，等.机载LiDAR正射影像镶嵌线智能优化研究[J].武汉大学学报·信息科学版，2011,36(3):325-328)
[24] 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(张剑清，孙明玮，张祖勋，等.基于蚁群算法的正射影像镶嵌线自动选择[J].武汉大学学报·信息科学版，2009,34(6):675-678)
[25] 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(焦晨静，陈时雨，赵鹏祥，等.顾及结构信息的DOM镶嵌线搜索算法[J].测绘科学，2016,41(1):190-193)
[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
[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
[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
[29] 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(汪韬阳，张过，李德仁，等.卫星遥感影像的区域正射纠正[J].武汉大学学报·信息科学版，2014,39(7):838-842)
[30] 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(袁修孝，段梦梦，曹金山，等.正射影像镶嵌线自动搜索的视差图算法[J].测绘学报，2015,44(8):877-883)
[31] Milgram D L. Computer Methods for Creating Photomosaics[J]. IEEE Transactions on Computers,1975,24:1 113–1 119
[32] 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(潘俊，王密，李德仁，等.基于顾及重叠的面Voronoi图的接缝线网络生成方法[J].武汉大学学报·信息科学版，2009,34(5):518-522)
[33] 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(潘俊，王密，李德仁，等.接缝线网络的自动生成及优化方法[J].测绘学报，2010,39(3):289-294)
[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
[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
[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
[4] Fernández E,MartíR. GRASP for Seam Drawing in Mosaicking of Aerial Photographic Maps[J]. Journal of Heuristics,1999(5):181–197
[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
[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
[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
[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
[9] Soille P. Morphological Image Compositing[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28:673–683
[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
[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
[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
[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
[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
[15] 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(左志权，张祖勋，张剑清，等. DSM辅助下城区大比例尺正射影像镶嵌线智能检测[J].测绘学报，2011,40(1):84-89)
[16] 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(陈继溢，许彪，张力，等.采用最优生成树的正射影像镶嵌线快速智能检测[J].测绘学报，2015,44(10):1 125-1 131)
[17] 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(袁修孝，钟灿.一种改进的正射影像镶嵌线最小化最大搜索算法[J].测绘学报，2012,41(2):199-204)
[18] 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(岳贵杰，杜黎明，刘凤德，等. A*搜索算法的正射影像镶嵌线自动提取[J].测绘科学，2015,40(4):151-154)
[19] 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(丁锴为，邹峥嵘，张云生，等.基于图割算法的正射影像镶嵌线自动选择[J].测绘与空间地理信息，2016(9):54-56)
[20] Dijkstra E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik,1959,1:269-271
[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
[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] Sun Jie,Ma Hongchao,Tang Xuan,et al. Optimization of LiDAR System Ortho-image Mosaic Seamline[J]. Geomatics and Information Science of Wuhan University,2011,36(3):325-328(孙杰，马洪超，汤璇，等.机载LiDAR正射影像镶嵌线智能优化研究[J].武汉大学学报·信息科学版，2011,36(3):325-328)
[24] 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(张剑清，孙明玮，张祖勋，等.基于蚁群算法的正射影像镶嵌线自动选择[J].武汉大学学报·信息科学版，2009,34(6):675-678)
[25] 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(焦晨静，陈时雨，赵鹏祥，等.顾及结构信息的DOM镶嵌线搜索算法[J].测绘科学，2016,41(1):190-193)
[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
[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
[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
[29] 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(汪韬阳，张过，李德仁，等.卫星遥感影像的区域正射纠正[J].武汉大学学报·信息科学版，2014,39(7):838-842)
[30] 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(袁修孝，段梦梦，曹金山，等.正射影像镶嵌线自动搜索的视差图算法[J].测绘学报，2015,44(8):877-883)
[31] Milgram D L. Computer Methods for Creating Photomosaics[J]. IEEE Transactions on Computers,1975,24:1 113–1 119
[32] 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(潘俊，王密，李德仁，等.基于顾及重叠的面Voronoi图的接缝线网络生成方法[J].武汉大学学报·信息科学版，2009,34(5):518-522)
[33] 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(潘俊，王密，李德仁，等.接缝线网络的自动生成及优化方法[J].测绘学报，2010,39(3):289-294)
[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