基于幾何配準的三維模型幾何比對方法研究

周 培， 劉 銘， 王 騰， 楊 欣， 聶蓉梅

(1. 北京宇航系統(tǒng)工程研究所，北京 100076；2. 山東山大華天軟件有限公司，山東 濟南 250000)

基于幾何配準的三維模型幾何比對方法研究

周 培1， 劉 銘2， 王 騰1， 楊 欣2， 聶蓉梅1

(1. 北京宇航系統(tǒng)工程研究所，北京 100076；2. 山東山大華天軟件有限公司，山東 濟南 250000)

針對設(shè)計師在進行協(xié)同建模時無法快速查看模型變更信息的問題，提出了快速比對兩個模型幾何差異的方法。首先，通過等步長采點獲取兩個模型的點云數(shù)據(jù)；然后，利用主元分析法計算兩個點云的特征向量從而獲取點云的參考坐標系，推導(dǎo)兩個點云參考坐標系的坐標變換，將兩個點云調(diào)整到一致，即可實現(xiàn)點云的初始配準；最后，利用最近點迭代法對兩個點云進行精確配準，記錄配準后兩個點云中的非重疊區(qū)域，可獲取兩個點云的幾何差異區(qū)域。測試結(jié)果表明該方法可以有效識別兩個模型的幾何差異。

點云；幾何配準；幾何比較；協(xié)同建模

隨著三維CAD技術(shù)的迅速發(fā)展，三維CAD軟件已經(jīng)在制造業(yè)、工程設(shè)計等領(lǐng)域廣泛應(yīng)用。相對二維工程圖設(shè)計，設(shè)計者們在利用CAD軟件設(shè)計產(chǎn)品時也經(jīng)常面臨新的問題。由于產(chǎn)品方案隨時可能發(fā)生變更，設(shè)計師經(jīng)常會根據(jù)上級發(fā)出的變更通知對已有的模型進行更改，并手工記錄更改點。然而在模型較復(fù)雜、變更細節(jié)較多時，如果仍然采用手工記錄的方式，一方面難以避免漏記、錯記，另一方面極不易察覺關(guān)聯(lián)尺寸等非直接變更導(dǎo)致的更改。由此產(chǎn)生的變更信息用于

指導(dǎo)后續(xù)的生產(chǎn)制造，勢必會影響產(chǎn)品質(zhì)量。因此設(shè)計師在設(shè)計產(chǎn)品時，尤其是多位設(shè)計者進行協(xié)同建模時，非常需要有工具可以提供三維模型的幾何比較，讓每位設(shè)計者可以在本地不同版本的模型中快速定位更改點。

目前國內(nèi)還沒有一款專門提供模型幾何比較功能的工具，但有關(guān)模型比較的研究有很多，多數(shù)基于配準算法的模型相似性研究，主要應(yīng)用于質(zhì)量檢測、模型檢索、人臉識別等技術(shù)領(lǐng)域[1-5]。如張志波等[1]提出改進的工業(yè)CT圖像與CAD模型的比對檢測方法，主要研究了CT圖像與CAD模型的幾何誤差，及數(shù)字化測量設(shè)備對產(chǎn)品質(zhì)量的檢測。美國PTC公司研發(fā)的三維CAD軟件Creo Parametric已經(jīng)在國內(nèi)航天、工程機械領(lǐng)域廣泛使用，其提供了零件級模型的幾何比較功能，但此功能需進行原點配準，不適于兩個模型沒有配準對齊的場景。模型的配準對齊是進行模型比對的關(guān)鍵，目前常用的配準算法如Besl和M cKay[6]提出的基于優(yōu)化理論的最近點迭代法(iterative closest point, ICP)，以及近期的基于曲率或基于幾何特征的點云比對算法[7-8]，還未被應(yīng)用于三維模型幾何比對領(lǐng)域。

針對上述現(xiàn)狀，本文提出了一種基于幾何配準的幾何比較方法。測試結(jié)果表明，該方法可以較好地對齊兩個三維CAD模型，有效找出兩個模型的幾何差異，并具有較好的魯棒性，成功集成應(yīng)用于Creo Parametric三維設(shè)計平臺，改進現(xiàn)有幾何比較方法。

1 Creo Parametric的幾何比較方法及不足

1.1 Creo Parametric的幾何比較方法

作為第一款運用“參數(shù)化設(shè)計”思想的三維CAD軟件，Creo Parametric自身提供了零件級的幾何比較。可以在“零件”模式下，比較兩個零件或一個零件的兩個不同版本，獲得兩個零件或不同版本間存在幾何差異的圖形報告。

Creo Parametric自身幾何比較的原理：生成第一個零件的點云數(shù)據(jù)，然后將其疊加到第二個零件上。之后，Creo Parametric生成兩個零件間偏差的著色顯示，并在圖形窗口中顯示出來。

執(zhí)行Creo Parametric幾何比較功能時，需要設(shè)置“測量間距”和“公差”，其中“測量間距”用于控制點云密度，“公差”用于控制顯示。

使用該工具的前提是兩個零件已配準對齊，如果兩個零件的幾何拓撲信息一樣，但位置不同，那么Creo Parametric自身的幾何比較將會認為兩個零件存在幾何差異。

1.2 Creo Parametric幾何比較方法的不足

下面演示Creo Parametric的幾何比較效果：首先利用 Creo Parametric創(chuàng)建一個簡單100×100×100的正方體，作為原始模型，如圖1(a)所示。然后，將原始模型沿x軸正方向移動30 mm，沿y軸正方向移動10 mm，得到新的模型，作為更改后的模型，如圖1(b)所示。

圖1 兩個正方體模型：幾何相同，位置不同

執(zhí)行Creo Parametric的幾何比較功能，比較圖 1中的兩個正方體模型的幾何差異，比較效果如圖2所示。

Creo Parametric在比較兩個幾何完全相同但位置不同的三維CAD模型時，會判定兩個模型存在幾何差異。因此，現(xiàn)有Creo Parametric的幾何比較方法并不適用于比較兩個姿態(tài)未對齊的三維模型，存在較大局限性。

圖2 Creo Parametric幾何比較效果：藍色區(qū)域即幾何差異區(qū)域

2 基于幾何配準的幾何比較方法

針對Creo Parametric幾何比較方法的不足，本文提出了一種基于幾何配準的幾何比較方法。該方法的基本原理是通過幾何配準來匹配兩個模型點云的重疊部分，記錄不重疊區(qū)域中的點作為差異點，將差異點所在幾何面作為差異顯示。算法流程如圖3所示。

圖3 基于幾何配準的幾何比較方法的算法流程圖

2.1 讀取兩個模型的幾何信息

通過兩種方法可獲取兩個三維模型的幾何拓撲信息：①直接通過模型所屬CAD軟件的二次開發(fā)接口獲取；②在模型所屬CAD軟件未提供二次開發(fā)接口的情況下，將模型文件轉(zhuǎn)換成step格式，再按step標準讀取模型step文件中的幾何信息。

2.2 獲取模型的點云

等步長對模型所有面進行采點，獲取的點集作為模型點云數(shù)據(jù)。所述“步長”就是采點間距。

2.3 進行初始配準

獲取到點云數(shù)據(jù)后，構(gòu)造協(xié)方差矩陣來計算兩個點云的局部坐標系，并通過其對兩個模型點云進行初始配準。利用點云數(shù)據(jù)構(gòu)造協(xié)方差矩陣的方法，在統(tǒng)計學(xué)中被稱為主元分析法（principal Component analysis, PCA）。PCA的目的是“降噪”、“去冗余”，構(gòu)造對角化協(xié)方差矩陣。

上述構(gòu)造協(xié)方差矩陣的方法如下：

設(shè)有集合 S= {X1,X2,···,Xm}，S中的每個元素都是一個樣本集，那么由這些樣本集構(gòu)成協(xié)方差矩陣

舉一個三維的例子：假設(shè)數(shù)據(jù)集有 3個維度{X,Y,Z}，每個維度樣本集含有n個元素，則協(xié)方差矩陣為

綜上所述，協(xié)方差矩陣的意義是為了描述維度之間的線性相關(guān)關(guān)系。獲取到點云數(shù)據(jù)后，通過點云中的樣本點坐標，構(gòu)造{X,Y,Z} 3個維度的

協(xié)方差矩陣。然后，通過對角化協(xié)方差矩陣使得維度間的相關(guān)性盡可能小，并使得保留下來的維度的方差盡可能大。對角化后的矩陣，其對角線上是協(xié)方差矩陣的特征值，取最大的 3個特征值對應(yīng)的特征向量即可作為點云的3個主軸方向。

下面簡述兩個模型點云初始配準[9]的實現(xiàn)流程：

步驟1. 利用點云數(shù)據(jù)構(gòu)造協(xié)方差矩陣。

步驟2. 利用Jacobi方法計算協(xié)方差矩陣的特征值和特征向量，取最大的 3個特征值對應(yīng)的特征向量作為點云局部坐標系的3個主軸方向。

步驟 3. 計算點云重心，作為點云局部坐標系原點。

步驟 4. 將兩個點云的參考坐標系調(diào)整到一致，即可達到兩個點云的初始配準，最終使得兩個模型的姿態(tài)自動對齊。

2.4 進行精確配準

完成初始配準后，兩個模型點云大致重合，為了盡可能縮小點云之間的旋轉(zhuǎn)和平移錯位，還需要利用ICP算法[9]對兩個模型點云進行精確配準。

ICP算法是應(yīng)用最為廣泛的幾何配準算法，其是基于最小二乘法的最優(yōu)匹配算法，目的在于尋找最小二乘逼近的坐標變換矩陣。ICP算法中最經(jīng)典的方法是“Point To Point”就近點搜索算法，這個方法主要運用kd-tree的方法實現(xiàn)就近點搜索。其中，kd-tree是一個二叉樹的數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點表示一個空間范圍，主要用于快速檢索在 kd-tree中與查詢點距離最近的數(shù)據(jù)點。下面簡述兩個模型點云精確配準的實現(xiàn)步驟。

設(shè)

其中，P、Q表示兩個模型的點云數(shù)據(jù)，pi表示為點云P中第i個數(shù)據(jù)點，qj表示為點云Q中第j個數(shù)據(jù)點，M為點云P的數(shù)據(jù)點個數(shù)，N為點云Q的數(shù)據(jù)點個數(shù)，R3表示為實數(shù)點集。

運用點到點的 ICP進行精確配準[6,9-10]的主要步驟：

步驟 1. 利用 kd-tree的數(shù)據(jù)結(jié)構(gòu)存儲點集 Q的所有數(shù)據(jù)點。

步驟2. 遍歷點集P中的所有點pi，在點集Q檢索最近點 qt。令 xi=qt，生成新的點集 X, X = { x| x ∈ R3, i = 1,2,···,M}。由于每個點p∈P都

i ii能在點集Q中找到一個對應(yīng)的最近點，所以點集P與點集 X的數(shù)據(jù)點個數(shù)相同，且對應(yīng)的點具有相同的下標，即pi的最近點為xi。

步驟3. 計算點集P的重心坐標，記為μp；計算點集X的重心坐標，記為μx。

步驟4. 利用單位四元數(shù)法計算點集P到點集X的最佳旋轉(zhuǎn)變換 R，單位四元數(shù)法的算法流程如下：

不妨先設(shè)旋轉(zhuǎn)向量為單位四元數(shù)q=［q , q, q, q］T， 其 中 q≥0， 且

R0 1 2 30。

首先，構(gòu)造點集P、X的協(xié)方差矩陣

然后，根據(jù)矩陣C構(gòu)造4乘4正定矩陣

其中，tr(C)表示矩陣C的對角線元素之和，I3表示3階單位矩陣，。

最后，計算矩陣N的特征值和特征向量，其最大特征值對應(yīng)的特征向量即最佳旋轉(zhuǎn)向量 qR，從而，得最佳旋轉(zhuǎn)矩陣R，即

步驟5. 計算最佳平移向量 T =μx- Rμp。

步驟6. 利用得到的旋轉(zhuǎn)變換R和平移變換T對點集 P進行變換，得到經(jīng)過坐標轉(zhuǎn)換后的點集Trans(P)。

步驟7. 計算點集Trans(P)到點集Q的距離平方和dk，其中，dk表示第k次迭代計算的距離平方和。若大于或等于預(yù)先給定的閾值τ(τ＞0)，則返回步驟2；直到或迭代次數(shù)達到預(yù)設(shè)的最大值時，迭代終止。

2.5 記錄幾何差異

精確配準后的兩模型點云會重疊在一起，記錄不重疊的點作為差異點。應(yīng)用 OpenGL的顯示庫，先將兩個原始模型顯示出來，然后涂色顯示差異點所在的幾何面。顯示效果以幾何面為單位。

3 Creo Parametric幾何比較方法的改進

雖然第 2節(jié)給出的算法可以解決兩個模型姿態(tài)未對齊的應(yīng)用場景，但也存在一個問題：由于最終獲取的差異點云中可能是受設(shè)計師直接更改影響的點云，所以可能無法真正反映模型的實際變更。

以圖4的兩個零件為例，圖4(a)是原始模型，圖4(b)是更改后的模型，圖中紅色線框部分即設(shè)計師的實際變更。

圖4 兩個存在幾何差異的模型：線框區(qū)域是實際幾何變更

利用第2節(jié)的算法進行比較，會判定圖5中紅色線框區(qū)域為兩個模型的差異，達不到“顯示設(shè)計師實際變更”的比對效果。

圖5 基于幾何配準的幾何比較方法的比對效果

為了解決上述問題，本文提出了一種改進的Creo Parametric幾何比較方法，該方法基于 Creo Parametric的建模機制：在建模時，生成的每個幾何面都會有唯一對應(yīng)的 ID，且若該幾何面發(fā)生改變時，面ID不變。

根據(jù)上述機制，通過獲取模型所有幾何面進行面ID匹配，比較匹配上的幾何面。算法步驟如圖6所示。

圖6 改進的Creo Parametric幾何比較方法的算法流程圖

步驟 1. 利用二次開發(fā)接口獲取模型所有面ID，匹配兩個模型中面ID相同的幾何面。

步驟2. 獲取匹配成功的兩個幾何面的幾何信息。并通過等步長的面上采點法獲取幾何面的點云數(shù)據(jù)。

步驟3. 對兩個面的點云數(shù)據(jù)進行配準，判斷是否存在點間距在閾值之外的差異點。若兩個面存在差異點，則記錄兩個面作為幾何差異。

由于第2節(jié)已經(jīng)介紹了點云配準的算法步驟，所以上述算法的第 3步中不再贅述。與上節(jié)不同之處在于，本節(jié)點云配準的采點對象是模型中通過面ID匹配的幾何面，而上節(jié)則是直接對整個模型所有面進行采點。

改進的Creo Parametric幾何比較方法利用面ID找出兩個模型所有幾何面的匹配關(guān)系，所以可真實反映設(shè)計師的實際變更。然而在應(yīng)用上需滿足一個前提條件：設(shè)計者在變更模型時，是在原有模型基礎(chǔ)上進行幾何修改，沒有再重新創(chuàng)建原模型。如果設(shè)計師進行模型變更時，重新創(chuàng)建原有模型，那么所有幾何面將生成新的面 ID，會導(dǎo)致更改前后的兩個模型中不再存在面 ID對應(yīng)關(guān)系，因此無法利用改進的Creo Parametric幾何比較方法進行幾何面匹配。

4 實例驗證

本實驗利用Creo Parametric設(shè)計了兩組模型，如圖 7所示。這兩組模型都存在幾何差異，且姿態(tài)未對齊。圖 7中紅色線框區(qū)域即兩個模型的幾何變更。

圖7 兩組原始模型

分別使用基于幾何配準的幾何比較方法、改進的Creo Parametric幾何比對方法對兩組模型進行幾何比較測試。

4.1 基于幾何配準的幾何比較方法的測試結(jié)果

先獲取兩組模型的點云數(shù)據(jù)，點云數(shù)據(jù)如圖8所示。

對兩組模型點云進行初始配準，初始配準效果如圖9所示。

對兩組模型點云進行精確配準，精確配準效果如圖10所示。

顯示存在差異的點云區(qū)域，顯示效果如圖 11所示。

圖8 兩組模型的整體點云圖

圖9 兩組模型點云的初始配準效果圖

圖10 兩組模型點云的精確配準效果圖

圖11 基于幾何配準的幾何比對方法的比較效果圖

從圖11的比較結(jié)果來看，基于幾何配準的幾何比較方法可找出兩個模型中所有存在差異的點云，且可較好地應(yīng)用于模型姿態(tài)未對齊的場景。同時，由于該方法僅需要兩個模型的點云數(shù)據(jù)，所以可適用于目前如 Pro/E、UG、CATIA、Solidworks等主流CAD軟件。

4.2 改進的Creo Parametric幾何比較方法的測試結(jié)果

改進的Creo Parametric幾何比較方法，首先利用二次開發(fā)接口獲取模型的幾何面信息和對應(yīng)的面ID，根據(jù)面ID匹配更改前后的兩個模型的幾何面。對匹配成功的幾何面進行面上采點，獲取面的點云數(shù)據(jù)，再利用“基于幾何配準的幾何比較方法”對兩個面的點云數(shù)據(jù)進行對比。若兩個面的點云存在閾值外的差異點，則為差異點云。兩組模型的差異點云如圖 12所示(差異點云以面為單位顯示)。最后以幾何面為單位顯示模型差異，如圖13所示。

圖12 兩組模型點云的差異面點云圖

圖13 改進的Creo Parametric幾何比較方法的比較效果圖

從圖 13的比較結(jié)果來看，改進的 Creo Parametric幾何比較方法明顯具有更好的比較效果，可真實顯示設(shè)計師的實際更改。但由于該方法需要兩個模型存在面ID對應(yīng)關(guān)系，所以應(yīng)用范圍較窄。

5 結(jié) 束 語

三維模型幾何比對對實際的協(xié)同建模具有重要意義，本文給出的基于幾何配準的幾何比較方法，主要是將幾何配準算法應(yīng)用于模型姿態(tài)對齊，使得該方法可以處理更多的應(yīng)用場景。但該方法并不存在對配準算法的修改和優(yōu)化。針對“如何真實反映設(shè)計師的實際變更”的問題，本文也描述了一種改進的Creo Parametric幾何比較方法。由實例驗證可以看出，本文提出的思路是可行有效的，在計算機輔助設(shè)計中將具有良好的應(yīng)用前景。

[1] 張志波, 曾 理, 何洪舉. 改進的工業(yè) CT圖像與CAD 模型的比對檢測[J]. 計算機應(yīng)用研究, 2012, 29(6): 2242-2245.

[2] 史寶全, 梁 晉, 劉 青, 等. 基于約束搜索球的點云數(shù)據(jù)與 CAD模型精確比對檢測[J]. 計算機集成制造系統(tǒng), 2010, 16(5): 929-934.

[3] 王 勇, 唐 靖, 饒勤菲, 等. 一種新的散亂點云快速去噪算法[J]. 計算機應(yīng)用與軟件, 2015, 32(7): 74-78.

[4] 陶海躋, 達飛鵬. 一種基于法向量的點云自動配準方法[J]. 中國激光, 2013, 40(8): 179-184.

[5] 潘仁林, 達飛鵬, 鄒紅艷, 等. 基于面部曲線彈性匹配的三維人臉識別方法[J]. 圖學(xué)學(xué)報, 2014, 35(3): 358-367.

[6] Besl P J, M cKay N D. A method for registration of 3D shapes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[7] 馬忠玲, 周明全, 耿國華, 等. 一種基于曲率的點云自動配準算法[J]. 計算機應(yīng)用研究, 2015, 32(6): 1878-1880.

[8] 張 步, 姚頑強, 陳 鵬. 基于幾何特征的建筑物點云配準方法[J]. 大地測量與地球動力學(xué), 2015, 35(3): 416-419.

[9] 戴靜蘭, 陳志楊, 葉修梓. ICP算法在點云配準中的應(yīng)用[J]. 中國圖象圖形學(xué)報, 2007, 12(3): 517-521.

[10] 朱延娟, 周來水, 張麗艷. 散亂點云數(shù)據(jù)配準算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2006, 18(4): 475-481.

Research on Geometric Com parison of 3D M odels Based on Geometric Registration

Zhou Pei1, Liu M ing2, Wang Teng1, Yang Xin2, Nie Rongmei1

(1. Beijing Institute of Astronautical Systems Engineering, Beijing 100076, China; 2. Shandong Hoteamsoft Software Co., Ltd, Jinan Shandong 250000, China)

In order to help designers to check model changes quickly in a collaborative design, this paper focuses on how to rapidly compare geometric differences between two 3D models. First, the equidistant point clouds of two models are computed, and then a reference coordinate system of each point cloud is obtained by using the principal component analysis method. A transformation is then found to match the two point clouds to achieve an initial registration. Finally, the ICP (iterative closest point) method is used to realize accurate registration for the two point clouds. By computing the non-overlapping domain after the exact registration, we obtain the geometric differences between the two point clouds. The numerical example shows that the proposed method can effectively recognize the geometric differences of two 3D models.

point cloud; geometric registration; geometric comparison; collaborative modeling

TP 391

10.11996/JG.j.2095-302X.2016040483

A

2095-302X(2016)04-0483-08

2015-11-17；定稿日期：2016-01-17

國防基礎(chǔ)科研計劃重大項目(A0320131002)

周 培(1984–)，男，安徽全椒人，高級工程師，博士。主要研究方向為計算機輔助幾何設(shè)計、數(shù)字化設(shè)計與仿真技術(shù)。

E-mail：zhoup2@126.com