利用并查集的多视匹配点提取算法

doi:10.11772/j.issn.1001-9081.2016.06.1659

计算机应用 ›› 2016, Vol. 36 ›› Issue (6): 1659-1663.DOI: 10.11772/j.issn.1001-9081.2016.06.1659

利用并查集的多视匹配点提取算法

卢俊, 张保明, 郭海涛, 陈小卫

信息工程大学地理空间信息学院, 郑州 450052

收稿日期:2015-11-09 修回日期:2016-01-20 出版日期:2016-06-10 发布日期:2016-06-08
通讯作者: 卢俊
作者简介:卢俊(1981-),男,湖北武汉人,讲师,博士,主要研究方向:计算机视觉、数字摄影测量;张保明(1961-),男,河北安国人,教授,硕士,主要研究方向:数字摄影测量、航天遥感工程;郭海涛(1976-),男,河南新安人,副教授,博士,主要研究方向:遥感图像处理、数字摄影测量;陈小卫(1989-),男,四川资阳人,博士研究生,主要研究方向:数字摄影测量。
基金资助:
国家973计划项目(2012CB720000)。

Extraction algorithm of multi-view matching points using union find

LU Jun, ZHANG Baoming, GUO Haitao, CHEN Xiaowei

Institute of Geospatial Information, Information Engineering University, Zhengzhou Henan 450052, China

Received:2015-11-09 Revised:2016-01-20 Online:2016-06-10 Published:2016-06-08
Supported by:
This work is partially supported by the National Basic Research Program (973 Program) of China (2012CB720000).

摘要/Abstract

摘要： 多视匹配点的提取是多视影像场景三维重建的核心问题之一,提取结果将直接影响三维重建的精度。将多视匹配点的提取问题转化为动态连通性问题,设计了基于并查集算法的解决方案。采用高效的树结构来组织并查集中的节点,在树中采用parent-link连接方式,使得每次增加匹配点对的过程中只需修改单个节点的寻址参数,避免了遍历数组来比较寻址参数的计算过程,提高了查找和修改的效率。同时通过加权策略对算法进行优化,利用加权编码方式替代常用的硬编码,可以平衡树状图的结构,降低树中节点的平均深度。多组影像集的实验结果表明,基于并查集的算法可以提取更多的多视匹配点,并且计算效率要优于传统的广度优先搜索算法。

关键词: 并查集, 影像关系图, 多视匹配点, 寻址, 加权编码, 树状图

Abstract: The extraction of multi-view matching points is one of the key problems in 3D reconstruction of multi-view image scenes, and the accuracy of the reconstruction will be affected directly by the extraction result. The extraction problem of multi-view matching points was converted into the dynamic connectivity problem and a Union-Find (UF) method was designed. The nodes of UF were organized using efficient tree structure in which parent-link connection was adopted. In the process of increasing the matching points, only the addressing parameters of a single node needed to be modified, which avoided comparing the calculation process of the addressing parameters through traversing the array, and the efficiencies of locating and modifying were improved. A weighting strategy was used to optimize the algorithm, and the weighted encoding method was used to replace the conventional hard encoding, which could balance the structure of the tree and reduce the average depth of the dendrogram. The experimental results of multiple image sets show that the proposed algorithm based on UF can extract more multi-view matching points, and is more efficient than the conventional Breadth-First-Search (BFS) algorithm.

Key words: Union Find (UF), image relation graph, multi-view matching point, addressing, weighted encoding, dendrogram

中图分类号:

P237
TP751

卢俊, 张保明, 郭海涛, 陈小卫. 利用并查集的多视匹配点提取算法[J]. 计算机应用, 2016, 36(6): 1659-1663.

LU Jun, ZHANG Baoming, GUO Haitao, CHEN Xiaowei. Extraction algorithm of multi-view matching points using union find[J]. Journal of Computer Applications, 2016, 36(6): 1659-1663.

参考文献

[1] SNAVELY N, SEITZ S M, SZELISKI R. Photo tourism: exploring photo collections in 3D[J]. ACM Transactions on Graphics, 2006, 25(3): 835-846.
[2] GHERARDI R, FARENZENA M, FUSIELLO A. Improving the efficiency of hierarchical structure-and-motion[C]//Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 1594-1600.
[3] 郭复胜.无人机图像的三维重建方法研究[D].北京:中国科学院大学,2013:21-52. (GUO F S. 3D Reconstruction from UAV images[D]. Beijing: University of Chinese Academy of Sciences, 2013: 21-52.)
[4] ZACH C, POLLEFEYS M. Practical methods for convex multi-view reconstruction[C]//Proceedings of the 11th European Conference on Computer Vision, LNCS 6314. Berlin: Springer, 2010: 354-367
[5] ZACH C, KLOPSCHITZ M, POLLEFEYS M. Disambiguating visual relations using loop constraints[C]//Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 1426-1433
[6] SNAVELY N, SIMON I, GOESELE M, et al. Scene reconstruction and visualization from community photo collections[J]. Proceedings of the IEEE, 2010, 98(8): 1370-1390.
[7] AGARWAL S, FURUKAWA Y, SNAVELY N, et al. Building Rome in a day[J]. Communications of the ACM, 2011, 54(10): 105-112.
[8] MOULON P, MONASSE P, MARLET R. Global fusion of relative motions for robust, accurate and scalable structure from motion[C]//Proceedings of the 2013 IEEE International Conference on Computer Vision. Piscataway, NJ: IEEE, 2013: 3248-3255.
[9] GALLER B A, FISCHER M J. An improved equivalence algorithm[J]. Communications of the ACM, 1964, 7(5): 301-303.
[10] STRECHA C, VON HANSEN W, VAN GOOL L, et al. On benchmarking camera calibration and multi-view stereo for high resolution imagery[C]//CVPR 2008: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2008: 1-8.
[11] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.
[12] HARTLEY R, ZISSERMAN A. Multiple view geometry in computer vision[M]. Cambridge: Cambridge University Press, 2004: 290-294.

利用并查集的多视匹配点提取算法

Extraction algorithm of multi-view matching points using union find

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

[1]	孙淑光, 周琪. 基于残差决策的自动飞行控制系统远程实时故障诊断[J]. 计算机应用, 2020, 40(5): 1522-1528.
[2]	贺庆建, 蔡涛, 王杰, 牛德姣. 面向NVM存储系统的快速文件访问系统[J]. 计算机应用, 2020, 40(2): 541-546.
[3]	马志强, 李海生. 基于KD-tree剖分的三维动态场景快速有效压缩[J]. 计算机应用, 2016, 36(9): 2590-2596.
[4]	查志远, 刘辉, 尚振宏, 李润鑫. 自适应加权编码L_1/2正则化的图像重建算法[J]. 计算机应用, 2015, 35(3): 835-839.
[5]	周相兵杨兴江马洪江. 基于划分算法的SaaS寻址中断软件生成策略[J]. 计算机应用, 2012, 32(02): 561-565.
[6]	万年红王雪蓉. 云信任驱动的物联网信息资源寻址模型[J]. 计算机应用, 2011, 31(05): 1184-1188.
[7]	刘蜀豫;李之棠;黎耀. 内容寻址网络CAN研究[J]. 计算机应用, 2005, 25(12): 2885-2887.