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

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