一種權值約束的精確配準算法

蔣睿嵩， 魏發遠， 馮大勇， 閆茂振

（中國工程物理研究院總體工程研究所，四川 綿陽 621900）

一種權值約束的精確配準算法

蔣睿嵩， 魏發遠， 馮大勇， 閆茂振

（中國工程物理研究院總體工程研究所，四川 綿陽 621900）

針對數據與模型的精確配準問題，提出一種權值約束的配準算法，通過對配準點施加不同的權值，利用權值約束保證模型重要區域的配準精度。首先，論文基于經典配準模型，引入權重因子，建立了改進的權值約束的配準模型。針對配準模型的求解問題，通過對現有SVD-ICP算法進行適應性改進，提出并研究了帶權SVD-ICP(wSVD-ICP)算法，重點推導了基于wSVD算法求解旋轉矩陣R和平移矩陣T的過程。最后，論文利用仿真數據和實測數據對配準模型進行了驗證；計算結果表明，論文所提算法通過對精度要求較高區域分配高權值進行約束，可有效提升該局部區域的配準精度；同時，可在一定程度上改進整體配準精度和效率。

配準；權值；約束；wSVD-ICP

模型配準作為計算機圖形圖像領域的基本技術之一，目前已廣泛地應用于三維重構、機器人視覺、模式識別、幾何處理以及CAD/CAM等領域[1-2]。模型配準實際上就是求解待配準模型與理論模型之間的最優空間變換，使待配準模型通過這個最優空間變換得到新的數據模型與理論模型滿足相似度測量要求。模型之間的變換可分為剛性變換和非剛性變換兩類[3]；對于工業領域的產品形狀檢測而言，需將產品視為剛體，因此，論文重點研究剛體的精確配準問題。

迭代最近點(Iterative Closest Point, ICP)算法[1,4]是剛體配準中最為典型的算法之一。ICP算法通過求取最小平方來減小每一次迭代過程中對應點集的平均誤差，以及通過查找最近鄰點來減小對應點對之間的距離。ICP算法雖然存在局部收斂的問題，但是由于其概念清晰、收斂性較好等優點，得到了廣泛的關注。許多學者從點對選取、點對匹配和最小化策略等方面，對ICP算法進行了改進[5]；如Fitzgibbon[6]提出了LM算法對ICP算法進行加速，Jost和Hugli[7]提出了一種多分辨率的 ICP算法以提高算法的速度和魯棒性，Phillips等[8]提出一種分段ICP算法以檢測并刪除參與配準的異常點。此外，也有研究人員對ICP算法進行改進，并將其應用于非剛體配準[9-10]。

在實際工程應用中，配準模型的不同區域往往具有不同的重要度。例如，在產品檢測中，不同區域有不同的設計公差，理想的配準函數應該保證公差要求較高區域的配準精度，而適當放寬公差帶較寬區域的配準精度。

為此，通過引入權值約束的概念，通過對配準模型中較為重要的區域賦予較高的權重，從而實現模型的高精度配準。在已有的研究中，權值的設置主要是為區分點集是否參與配準[6]，權值也僅有0和1。針對該問題，論文首先基于經典的配準目標函數，研究了改進的帶權配準目標函數；在此基礎上，針對目標函數的優化求解，提出了一種改進的 SVD-ICP算法求取模型配準參數；最后，通過兩個配準算例，對算法進行驗證分析。

1 權值約束的配準模型

對于待配準模型和理論模型的空間配準問題，就是要找到合適的空間變換參數，使得目標函數最小。基于基本的配準目標函數F1，建立權值約束的配準目標函數F2，如式(2)所示：其中，式(2)中引進了約束權因子，被定義為參與配準的點集的重要程度；公式中N為參與配準的點數；Pi(i=1,2,…,N)為待配準模型上的點；Qi為Pi在CAD模型曲面上的投影點；wi是約束權因子；R為旋轉矩陣；T為平移矩陣。

對配準模型的優化，其實質即為通過令目標函數最小，得到 6 個最優配準參數(α,β,γ,Tx,Ty,Tz)，其中前3個變量為繞X、Y、Z軸的角度參數，也就是所謂的Euler角。后3個變量為沿X、Y、Z軸的平移參數。通常，旋轉矩陣和平移矩陣分別表達為式(3)、式(4)：

2 模型求解算法

針對帶權值約束的配準目標函數的求解問題，提出并研究一種權值約束的 SVD-ICP算法(wSVD-ICP)，該方法具有迭代收斂速度快、配準精度高等優點。論文首先研究wSVD-ICP算法的基本步驟，在此基礎上，重點研究基于wSVD算法的空間變換參數計算方法。

2.1 wSVD-ICP算法步驟

對于預先得到的待配準模型和已知的理論模型，要得到待配準模型相對理論模型的變換矩陣，基于wSVD-ICP求解算法的迭代步驟一般如下：

步驟1初始化變換矩陣R0、T0。

步驟，2k 為 求迭取代變次換數后：的待配準模型(i=1, 2, … ,N)

步驟3計算與待配準模型(i=1,2, …,N)對應的理論模型上的最近點(i=1,2,…,N)。

步驟4基于wSVD分解算法，由和對變換矩陣 Rk-1、 Tk-1進行更新得到 Rk、Tk。

步驟5計算待配準模型與理論模型間的偏差 εk：

步驟 6如果 εk＜δ（δ為預先指定的迭代閾值）或者達到最大迭代次數，退出；否則令k=k+1，轉步驟2。

2.2 wSVD算法

針對權值約束的配準目標函數求解問題，對現有 SVD算法進行改進，通過加入權值約束，實現模型的精確配準。該算法在給定配準控制點集{Pi}、{Qi}(i=1,2,…,N)的前提下，可計算兩個待配準模型之間的旋轉變換R與平移變換T。

針對式(2)所示的配準目標函數，按式(7)計算待配準模型 Pi( i= 1,2,…,N)及其在理論模型上的對應點集 Qi(i= 1,2,…,N)的帶權質心：

其中， wi為配準點 Pi所對應的權值。

利用式(8)，計算這兩個數據集合中每一個數據點相對于質心的位移。

將式(8)代入式(2)，可得：

將上式的右邊展開，得到：

通過簡單數學推理可知，F2最小等價于F最大：

式中：

根據Lemma定理，對任何正定矩陣 AAT和正交矩陣B，有如下結論（證明過程參見文獻[11]）：

令H的奇異值分解為：

這里U和V是3×3正交矩陣，Λ是3×3具有非負元素的對角矩陣，令：

于是有：

它是對稱和正定的。因此根據Lemma定理，對任何3×3正交矩陣B：

這樣，在所有3×3正交矩陣中，X使F最大，也就是使 F2最小。

根據上述討論，權值約束的 SVD算法步驟為：

步驟1根據配準控制點集按照式(7)計算兩個待配準模型的質心 P'、 Q′。

步驟2利用式(8)計算這兩個配準控制點集合中每一個數據點相對于質心的位移。

步驟3根據式(12) 計算3×3矩陣H，并對矩陣H進行奇異值分解得到式(14)。

步驟4計算旋轉矩陣R：

步驟5計算平移矩陣T：

3 算例驗證與比較分析

本節設計兩個具體算例對論文所提的配準算法進行有效性驗證。兩個算例都以渦輪葉片截面點作為實驗對象。其中，算例一為仿真數據，直接從理論模型上截取后進行空間變換得到，其幾何形態與理論模型完全一致，如圖1所示。算例二為實際葉片的三坐標測量數據，其幾何形態與理論模型存在一定的差異，從而可更好地驗證權值約束的配準模型對待配準數據重要部位的配準精度提升能力。根據工程設計知識，葉片越厚的部位（葉盆和葉背部位）公差越大，對配準的精度要求相對較低；葉片越薄的部位（前緣和后緣）公差越小，對配準的精度要求相對較高，如圖2所示。因此，配準點的權值以最小壁厚處為1，其余各點權值為此處壁厚除最小壁厚所得值，配準點權值分布，如圖3所示。

3.1 基于仿真數據的算例驗證

圖1 仿真數據

圖2 實測數據

圖3 葉片截面配準點權值分布圖

本算例以仿真數據為實驗對象，考察權值約束的配準模型對截面線的配準效果。仿真數據構造方法為：從截面線提取200個配準控制點并進行空間坐標變換。不失一般性，同時考慮到ICP算法容易陷入局部最優的問題（論文主要解決權值配準問題，因此對局部最優問題不作討論），設定較小的變換參數如表1所示。通過變換得到仿真數據，該仿真數據與理論模型只存在空間變換關系，其幾何形態完全一致。配準結果及相關數據列出如表 2所示，程序執行環境為：Intel Core2 2.33GHz，2GB RAM，NVIDIA GeForce 8600GT。

表1 仿真數據變換參數

表2 仿真數據變換參數對比

從表2中的數據可以看出，由于配準模型與理論模型幾何形態完全一致，權值約束對配準精度的影響表現得并不明顯。但是，在有權值約束的情況下，模型配準結果的最大誤差、平均誤差以及迭代次數都略小于無約束情況，從而說明有約束與無約束情況相比，不僅配準后模型更逼近理論模型，也提高了收斂速度，改善了配準效率。

3.2 基于實測數據的算例驗證

通過實測渦輪葉片截面線形成配準模型。在此基礎上考察配準模型同理論模型的配準結果，從而驗證權值約束的配準算法對變形數據的配準效果。采用 wSVD-ICP算法進行配準模型求解，得到的配準變換參數如表3，迭代收斂過程如圖4所示。

表3 加權配準與非加權配準的變換參數

圖4 權值約束與經典配準算法對比

從表3可以看出，使用權值約束的配準模型，配準后的最大誤差及平均誤差均小于標準配準模型。此外，從圖4可以看出，兩種配準模型的收斂速度相當。但是，使用加權配準模型，其主要目的是為保證截面線前、后緣處的配準精度，因此，需要進一步考察論文算法對公差精度要求較高區域的變形抑制效果。兩種模型的配準控制點相對于理論模型的誤差，如圖5所示，從圖中可以看出，權值約束的配準模型通過將型線前、后緣處的誤差轉移到葉盆、葉背區域，有效的保證了截面線前、后緣的配準精度。

圖5 配準誤差分布圖

4 結 論

針對產品測量數據的配準問題，在分析現有配準算法的基礎上，提出了一種權值約束的模型精確配準算法。通過在配準目標函數中引入權值約束，利用權值控制優化算法的搜索方向，從而可有效保證精度要求較高區域的配準精度。針對配準目標函數的優化求解，論文在經典SVD-ICP算法的基礎上，研究了wSVD-ICP算法。最后，論文利用仿真數據和實測數據設計了兩個算例對權值約束的配準模型進行了驗證，實驗結果表明：

（1）針對待配準模型同理論模型一致的情況，權值約束的配準算法在配準的精度和效率上略優于傳統配準算法。

（2）針對待配準模型同理論模型不一致的情況，通過權值約束的配準算法，可將配準精度向公差要求較高區域轉移，從而提升公差要求較高區域的配準精度。

此外，由于ICP算法的固有特性，本文算法可能陷入局部最優。為避免此問題，可將配準分為粗配準和精配準兩步，初配準采用GA等全局優化算法，在精配準階段采用本文算法。同時，本文的研究主要針對剛體配準展開，對非剛體配準，論文算法并不適用，需要在此基礎上進行改進，這也是進一步的研究工作之一。

[1] Besl P J, McKay N D. A method of registration of 3D shapes [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-255.

[2] Li Hongdong, Hartley R. The 3D-3D registration problem revisited [C]//IEEE 11th International Conference on Computer Vision. Rio de Janeiro, 2007: 1-8.

[3] Myronenko A, Song X. Point set registration: coherent point drift [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(12): 2262-2275.

[4] Zhang Z. Iterative point matching for registration of free-form curves and surfaces [J]. International Journal of Computer Vision, 1994, 13(2): 119-152.

[5] Rusinkiewicz S, Levoy M. Efficient variants of the ICP algorithm [C]//IEEE Third International Conference on 3-D Digital Imaging and Modeling. Quebec City, 2001: 145-152.

[6] Fitzgibbon A W. Robust registration of 2D and 3D point sets [J]. Image and Vision Computing, 2003, 21(13): 1145-1153.

[7] Jost T, Hugli H. A multi-resolution ICP with heuristic closest point search for fast and robust 3D registration of range images [C]//IEEE Fourth International Conference on 3-D Digital Imaging and Modeling. Alberta, 2003: 427-433.

[8] Phillips J M, Liu R, Tomasi C. Outlier robust ICP for minimizing fractional RMSD [C]//IEEE Sixth International Conference on 3-D Digital Imaging and Modeling. 2007: 427-434.

[9] Du Shaoyi, Zheng Nanning, Ying Shihui, You Qubo, Wu Yang. An extension of the ICP algorithm considering scale factor [C]//IEEE International Conference on Image Processing, 2007: 193-196.

[10] Du Shaoyi, Zheng Nanning, Ying Shihui, Liu Jianyi. Affine iterative closest point algorithm for point set registration [J]. Pattern Recognition Letters, 2010, 31(9): 791-799.

[11] 劉 晶. 葉片數字化檢測中的模型配準技術及應用研究[D]. 西安: 西北工業大學, 2006.

A New Weight Constraint Precision Registration Algorithm

Jiang Ruisong, Wei Fayuan, Feng Dayong, Yan Maozhen
(Institute of Structural Dynamic, China Academy of Engineering Physics, Mianyang Sichuan 621900, China)

Aiming at the precision registration, a registration algorithm with weight constraint is studied in this paper. This algorithm can ensure the registration accuracy by imposing different weights to different registration points. First, the registration model with weight constraint is established by introducing weight factor into traditional registration model. Second, in order to solve the registration model, a weight constraint SVD-ICP algorithm (wSVD-ICP) is studied based on the classical SVD-ICP algorithm. Especially, the detailed solving process of rotation matrix R and transform matrix T based on wSVD algorithm is shown. At last, two applications are presented for demonstration by using simulation data and measuring data respectively. The results indicate that the algorithm employed in this paper can improve the local registration accuracy significantly by assigning high weight to the high precision demand registration points. Moreover, the algorithm can improve the global registration accuracy and efficiency.

registration; weight; constraint; wSVD-ICP

TP 391

A

2095-302X (2014)02-0167-06

2013-06-12；定稿日期：2013-09-06

蔣睿嵩（1984-），男，四川安岳人，博士。主要研究方向為計算機輔助設計、復雜產品結構優化設計技術。E-mail：ruisong.jiang@gmail.com

馮大勇（1970-），男，四川閬中人，高級工程師，碩士。主要研究方向為計算機輔助設計、設計制造一體化技術。E-mail：fdyuse@163.com