利用并查集的多視匹配點提取算法

盧俊 盧俊 張保明 郭海濤 陳小衛

摘 要：多視匹配點的提取是多視影像場景三維重建的核心問題之一，提取結果將直接影響三維重建的精度。將多視匹配點的提取問題轉化為動態連通性問題，設計了基于并查集算法的解決方案。采用高效的樹結構來組織并查集中的節點，在樹中采用parentlink連接方式，使得每次增加匹配點對的過程中只需修改單個節點的尋址參數，避免了遍歷數組來比較尋址參數的計算過程，提高了查找和修改的效率。同時通過加權策略對算法進行優化，利用加權編碼方式替代常用的硬編碼，可以平衡樹狀圖的結構，降低樹中節點的平均深度。多組影像集的實驗結果表明，基于并查集的算法可以提取更多的多視匹配點，并且計算效率要優于傳統的廣度優先搜索算法。

關鍵詞：并查集；影像關系圖；多視匹配點；尋址；加權編碼；樹狀圖

中圖分類號： P237；TP751 文獻標志碼：A英文標題