| 利用并查集的多视匹配点提取算法 |
| |
| 引用本文： | 卢俊,张保明,郭海涛,陈小卫. 利用并查集的多视匹配点提取算法[J]. 计算机应用, 2016, 36(6): 1659-1663. DOI: 10.11772/j.issn.1001-9081.2016.06.1659 |
| |
| 作者姓名： | 卢俊 张保明 郭海涛 陈小卫 |
| |
| 作者单位： | 信息工程大学 地理空间信息学院, 郑州 450052 |
| |
| 基金项目： | 国家973计划项目(2012CB720000)。 |
| |
| 摘 要： | 多视匹配点的提取是多视影像场景三维重建的核心问题之一,提取结果将直接影响三维重建的精度。将多视匹配点的提取问题转化为动态连通性问题,设计了基于并查集算法的解决方案。采用高效的树结构来组织并查集中的节点,在树中采用parent-link连接方式,使得每次增加匹配点对的过程中只需修改单个节点的寻址参数,避免了遍历数组来比较寻址参数的计算过程,提高了查找和修改的效率。同时通过加权策略对算法进行优化,利用加权编码方式替代常用的硬编码,可以平衡树状图的结构,降低树中节点的平均深度。多组影像集的实验结果表明,基于并查集的算法可以提取更多的多视匹配点,并且计算效率要优于传统的广度优先搜索算法。
|
| 关 键 词： | 并查集 影像关系图 多视匹配点 寻址 加权编码 树状图 |
| 收稿时间： | 2015-11-09 |
| 修稿时间： | 2016-01-20 |
Extraction algorithm of multi-view matching points using union find |
| |
| 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. DOI: 10.11772/j.issn.1001-9081.2016.06.1659 |
| |
| Authors: | LU Jun ZHANG Baoming GUO Haitao CHEN Xiaowei |
| |
| Affiliation: | Institute of Geospatial Information, Information Engineering University, Zhengzhou Henan 450052, China |
| |
| 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. |
| |
| Keywords: | Union Find (UF) image relation graph multi-view matching point addressing weighted encoding dendrogram |
|
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
