基于特征點的三維模型配準算法

◆徐磊

（遼寧大學 遼寧 110036）

1 引言

在計算機視覺研究領域中，三維物體配準技術是一項非常重要的基礎研究。

三維模型配準可以分為兩類：粗配準、精配準。粗配準可以在兩個模型姿態未知的情況下，提供快速、高效的方式，完成兩個模型之間的配準工作。同時粗配準還可以為精配準提供一個良好的初始位置條件，減少精配準迭代所需的時間消耗。精配準可以完成模型之間精細的配準，使模型之間的誤差更小。

基于RANSAC的粗配準方法[1]利用“點云”數據間的重疊區域確定對應點，根據對應點求解待匹配點云間的剛體變換關系；一種是ICP算法（迭代最近點算法）[2]，一種是利用ICP的改進算法[3]。

2 基于特征點的三維模型配準算法

2.1 特征點提取

研究人員將網格頂點v的法向張量投票定義為與1環面相鄰的加權協方差矩陣的和：

因為一個法向投票張量是一個對稱的“正半定”二階張量，它可以被分解為如下形式：

我們可以根據張量T的特征值，將三角網格上的一個頂點分類為角點，邊上點和面上點，依據Shimizu等[4]的定義，如果頂點位于“拐角”或“銳邊”上，邊緣強度大約是1，如果它位于一個面上，則幾乎為0。分類條件為：

2.2 模型粗配準（改進的4pcs算法）

算法概括：給定兩個“點”集P，Q，不確定度δ，以及“點集”P與“點集”Q重疊度的預估f，結合本文章節2頂點特征提取，獲得相應的特征“點集”S1，S2。我們的目標是找到一個剛性變換使得“點集”S1中的點盡可能多的與“點集”S2中的某些點的距離小于δ。

（1）在“點集”P的特征“點集”S1中選擇一些共面4點對。

（2）對于給定的基礎對X，我們可以定義放射不變比集合。從“點集”Q的特征“點集”S2中提取出所有滿足e1=e2且在一定范圍δ內的條件即與X相符合的4點集合。

（3）為了確認唯一的Ti，我們計算Ti（v），并且統計有多少點與“點集”S2之間的距離小于δ，最后得到最佳剛性變換矩陣T。

2.3 模型細配準（改進的ICP算法）

ICP算法核心是最小化一個目標函數：

可歸納為以下步驟：

給定兩個“點集”P1，P2，每一次迭代，匹配程度都在提高。

步驟1.篩選：由P1中的點，在P2中搜索出其最近的點，組成一個點對；找出兩個點集中所有的點對組成兩個新點集。（隨機篩選法與最近鄰點法）

步驟2.計算重心：根據“點集”對，計算兩個新點集的重心（均勻分配權重）。

步驟3.R、T優化：由新點集，計算出下一步計算的旋轉矩陣R，和平移矩陣T。

步驟4.收斂：得到旋轉矩陣和平移矩陣R、T，就可以計算“點集”P2進行剛體變換之后的新點集P21，由計算P2到P21的距離平方和，以連續兩次距離平方和之差絕對值，作為是否收斂的依據。若小于閾值，就收斂，停止迭代（固定比例法）。

步驟5.重復：重復1-5，直到收斂或達到既定的迭代次數。

3 結果分析

從圖1的配準結果來看快速4PCS粗配準算法能夠將三維模型初步對齊，為細配準階段提供良好的初始位置，而改進的ICP算法能夠實現模型的進一步精確配準，從而實現模型的完全匹配。

圖1 Dragon模型“先粗后細”配準結果，Armadillo模型“先粗后細”配準結果

4 總結

針對帶有噪聲的三維網格模型，本文提出了一種“先粗配再細配”的模型配準方法。該算法首先基于張量投票提取出模型的特征頂點，之后采用一種快速4PCS配準算法實現模型的粗配準，不僅可以避免算法陷入局部極值，而且大大提高了配準的精度；細配準算法則是通過改進ICP算法實現兩個曲面的最終精確配準。在今后的研究中，要進一步優化算法的時間性能和配準精度。