蔣睿嵩， 魏發(fā)遠(yuǎn)， 馮大勇， 閆茂振

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

一種權(quán)值約束的精確配準(zhǔn)算法

蔣睿嵩， 魏發(fā)遠(yuǎn)， 馮大勇， 閆茂振

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

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

配準(zhǔn)；權(quán)值；約束；wSVD-ICP

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

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

在實際工程應(yīng)用中，配準(zhǔn)模型的不同區(qū)域往往具有不同的重要度。例如，在產(chǎn)品檢測中，不同區(qū)域有不同的設(shè)計公差，理想的配準(zhǔn)函數(shù)應(yīng)該保證公差要求較高區(qū)域的配準(zhǔn)精度，而適當(dāng)放寬公差帶較寬區(qū)域的配準(zhǔn)精度。

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

1 權(quán)值約束的配準(zhǔn)模型

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

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

2 模型求解算法

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

2.1 wSVD-ICP算法步驟

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

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

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

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

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

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

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

2.2 wSVD算法

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

針對式(2)所示的配準(zhǔn)目標(biāo)函數(shù)，按式(7)計算待配準(zhǔn)模型 Pi( i= 1,2,…,N)及其在理論模型上的對應(yīng)點集 Qi(i= 1,2,…,N)的帶權(quán)質(zhì)心：

其中， wi為配準(zhǔn)點 Pi所對應(yīng)的權(quán)值。

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

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

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

通過簡單數(shù)學(xué)推理可知，F(xiàn)2最小等價于F最大：

式中：

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

令H的奇異值分解為：

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

于是有：

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

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

根據(jù)上述討論，權(quán)值約束的 SVD算法步驟為：

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

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

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

步驟4計算旋轉(zhuǎn)矩陣R：

步驟5計算平移矩陣T：

3 算例驗證與比較分析

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

3.1 基于仿真數(shù)據(jù)的算例驗證

圖1 仿真數(shù)據(jù)

圖2 實測數(shù)據(jù)

圖3 葉片截面配準(zhǔn)點權(quán)值分布圖

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

表1 仿真數(shù)據(jù)變換參數(shù)

表2 仿真數(shù)據(jù)變換參數(shù)對比

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

3.2 基于實測數(shù)據(jù)的算例驗證

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

表3 加權(quán)配準(zhǔn)與非加權(quán)配準(zhǔn)的變換參數(shù)

圖4 權(quán)值約束與經(jīng)典配準(zhǔn)算法對比

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

圖5 配準(zhǔn)誤差分布圖

4 結(jié) 論

針對產(chǎn)品測量數(shù)據(jù)的配準(zhǔn)問題，在分析現(xiàn)有配準(zhǔn)算法的基礎(chǔ)上，提出了一種權(quán)值約束的模型精確配準(zhǔn)算法。通過在配準(zhǔn)目標(biāo)函數(shù)中引入權(quán)值約束，利用權(quán)值控制優(yōu)化算法的搜索方向，從而可有效保證精度要求較高區(qū)域的配準(zhǔn)精度。針對配準(zhǔn)目標(biāo)函數(shù)的優(yōu)化求解，論文在經(jīng)典SVD-ICP算法的基礎(chǔ)上，研究了wSVD-ICP算法。最后，論文利用仿真數(shù)據(jù)和實測數(shù)據(jù)設(shè)計了兩個算例對權(quán)值約束的配準(zhǔn)模型進行了驗證，實驗結(jié)果表明：

（1）針對待配準(zhǔn)模型同理論模型一致的情況，權(quán)值約束的配準(zhǔn)算法在配準(zhǔn)的精度和效率上略優(yōu)于傳統(tǒng)配準(zhǔn)算法。

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

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

[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] 劉 晶. 葉片數(shù)字化檢測中的模型配準(zhǔn)技術(shù)及應(yīng)用研究[D]. 西安: 西北工業(yè)大學(xué), 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-），男，四川安岳人，博士。主要研究方向為計算機輔助設(shè)計、復(fù)雜產(chǎn)品結(jié)構(gòu)優(yōu)化設(shè)計技術(shù)。E-mail：ruisong.jiang@gmail.com

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