盧俊 盧俊 張保明 郭海濤 陳小衛(wèi)

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

關(guān)鍵詞：并查集；影像關(guān)系圖；多視匹配點(diǎn)；尋址；加權(quán)編碼；樹狀圖

中圖分類號(hào)： P237；TP751 文獻(xiàn)標(biāo)志碼：A英文標(biāo)題