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

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

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

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

中图分类号： P237；TP751 文献标志码：A英文标题