Fast and Intelligent Seamline Detection for Orthoimage Mosaicking Based on Minimum Spanning Tree

doi:10.11947/j.AGCS.2015.20140467

Abstract

Abstract: A method of fast and intelligent seamline detection is presented that based on minimum spanning tree for high resolution orthoimage mosaicking. The image gradient and difference of homonymy pixels in the overlap area are calculated to build the differential image, which is deemed as a weighted undirected graph. According to the Bottleneck model, the optimal seamline is detected on the differential image by finding the minimum spanning tree of the weighted undirected graph. This method discards the conventional iterative process, thus achieves high speed. Experiment results illustrate the value of the proposed method which achieves great efficiency and guarantees the quality of the seamlines at the same time.

Key words: minimum spanning tree(MST), Bottleneck model, orthoimage mosaicking, intelligent seamline detection

CLC Number:

P237

CHEN Jiyi, XU Biao, ZHANG Li, AI Haibin, DU Quanye. Fast and Intelligent Seamline Detection for Orthoimage Mosaicking Based on Minimum Spanning Tree[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10): 1125-1131.

References

[1] ZHANG Zuxun, ZHANG Jianqing. Digital Photogrammetry[M]. Wuhan: Wuhan University Press, 1997. (张祖勋, 张剑清. 数字摄影测量学[M]. 武汉: 武汉大学出版社, 1997.)
[2] DAVIS J. Mosaics of Scenes with Moving Objects[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Santa Barbara: IEEE Computer Society, 1998: 354-360.
[3] CHON J, KIM H. Determination of the Optimal Seam-lines in Image Mosaicking with the Dynamic Programming (DP) on the Converted Cost Space[M]//RUTKOWSKI L, TADEUSIEWICZ R, ZADEH L A, et al. Artificial Intelligence and Soft Computing: Lecture Notes in Computer Science. Berlin: Springer, 2006, 4029: 750-757.
[4] 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(1): 86-92.
[5] YUAN Xiuxiao, ZHONG Can. An Improvement of Minimizing 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.)
[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] KERSCHNER M. Seamline Detection in Colour Orthoimage Mosaicking by Use of Twin Snakes[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2001, 56(1): 53-64.
[8] WANG Lin, AI Haibin, ZHANG Li. Automated Seamline Detection in Orthophoto Mosaicking Using Improved Snakes[C]//Proceedings of the 2nd International Conference on Information Engineering and Computer Science. Wuhan: IEEE, 2010: 1-4.
[9] AI Haibin, ZHANG Li, WANG Lin. Automatic Mosaicking Method for Large Block of Orthophotos[C]//Proceedings of SPIE 8005, MIPPR 2011: Parallel Processing of Images and Optimization and Medical Imaging Processing.Guilin: SPIE, 2011.
[10] ZHANG Jianqing, SUN Mingwei, ZHANG Zuxun. 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.)
[11] SUN Mingwei. Research on Key Technology of Automatical and Fast DOM Generation[D]. Wuhan: Wuhan University, 2009. (孙明伟. 正射影像全自动快速制作关键技术研究[D]. 武汉: 武汉大学, 2009.)
[12] ZUO Zhiquan, ZHANG Zuxun, ZHANG Jianqing, et al. Seamlines 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.)
[13] SUN Jie, MA Hongchao, TANG Xuan. Optimization of LiDAR System Ortho-image Mosaic Seam-line[J]. Geomatics and Information Science of Wuhan University, 2011, 36(3): 325-328. (孙杰, 马洪超, 汤璇. 机载LiDAR正射影像镶嵌线智能优化研究[J]. 武汉大学学报: 信息科学版, 2011, 36(3): 325-328.)
[14] WAN Youchuan, WANG Dongliang, XIAO Jianhua, 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.
[15] GONZALEZ R C, WOODS R E. Digital Image Processing[M]. RUAN Qiuqi, RUAN Yuzhi, Trans. Beijing: Publishing House of Electronics Industry, 2009. (冈萨雷斯, 伍兹. 数字图像处理[M]. 阮秋琦, 阮宇智, 译. 北京: 电子工业出版社, 2009.)
[16] PAN Jun, WANG Mi. A Seam-line Optimized Method Based on Difference Image and Gradient Image[C]// Proceedings of the 19th International Conference on Geoinformatics. Shanghai: IEEE, 2011: 1-6.
[17] YANG Yi, GAO Yuan, LI Haitao, et al. An Algorithm for Remote Sensing Image Mosaic Based on Valid Area[C]//2011 International Symposium on Image and Data Fusion. Tengchong: IEEE, 2011: 1-4.
[18] PAN Jun, WANG Mi, LI Deren, et al. Automatic Generation of Seamline Network Using Area Voronoi Diagrams with Overlap[J]. IEEE Transactions on Geoscience and Remote Sensing, 2009, 47(6): 1737-1744.
[19] PAN Jun. Research on Automatic Color Consistency Processing and Generation of Seamline Network for Aerial Images[D]. Wuhan: Wuhan University, 2008. (潘俊. 自动化的航空影像色彩一致性处理及接缝线网络生成方法研究[D]. 武汉: 武汉大学, 2008.)
[20] FERNANDEZ E, GARFINKEL R, ARBIOL R. Mosaicking of Aerial Photographic Maps via Seams Defined by Bottleneck Shortest Paths[J]. Operations Research, 1998, 46(3): 293-304.
[21] CORMEN T H, LEISERSON C, IVEST R, et al. Introduction to Algorithms[M]. PAN Jingui, GU Tiecheng, LI Chengfa, et al. Trans. Beijing: China Machine Press, 2010. (科曼, 莱瑟森, 李维斯特, 等. 算法导论[M]. 潘金贵, 顾铁成, 李成法, 等译. 北京: 机械工业出版社, 2010.)
[22] DOUGLAS D H, PEUCKER T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J]. The Canadian Cartographer, 1973, 10(2): 112-122.