陳芷+吳捷+馬小虎

摘 要： 點云數(shù)據(jù)與CAD模型的坐標(biāo)匹配和對應(yīng)關(guān)系的建立是數(shù)字化比對檢測系統(tǒng)的關(guān)鍵技術(shù)。利用k?D樹空間快速搜索策略改進(jìn)傳統(tǒng)ICP算法實現(xiàn)點云數(shù)據(jù)與CAD模型坐標(biāo)精確匹配，采用半邊數(shù)據(jù)結(jié)構(gòu)建立點云數(shù)據(jù)與CAD模型對應(yīng)關(guān)系，利用點到邊和點到點的對應(yīng)關(guān)系解決待測工件的邊緣和棱線以及特征明顯變化區(qū)域的偏差檢測問題。在此基礎(chǔ)上研制了數(shù)字化比對檢測系統(tǒng)。試驗結(jié)果表明該系統(tǒng)運算速度快、精度高，具有很好的應(yīng)用效果。

關(guān)鍵詞： 坐標(biāo)匹配； 點云數(shù)據(jù)； 對應(yīng)關(guān)系建立； 對比檢測

中圖分類號： TN911.23?34； TP391.7 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2017）12?0162?03

Abstract： The coordinate matching between point cloud data and CAD model and establishment of their corresponding relation are the key technologies of digital contrast detection system. The k?D tree space fast search strategy is used to improve the traditional ICP algorithm to achieve the coordinate accurate match between point cloud data and CAD model. The half edge data structure is adopted to build the corresponding relation between point cloud data and CAD model. The corresponding relation of point?to?edge and point?to?point is employed to solve the deviation detection problem of edge and ridge of UUT， and the region with obvious feature variation. On the above basis， a digital contrast detection system was developed. The test results indicate that the system has fast calculating speed and high precision and good application effect.

Keywords： coordinate matching； point cloud data； corresponding relation establishment； contrast detection

隨著制造業(yè)的發(fā)展，自由曲面等復(fù)雜型面已廣泛地應(yīng)用于產(chǎn)品的設(shè)計和制造過程中。為了保證具有復(fù)雜型面工件的加工質(zhì)量以及生產(chǎn)效率，需要對其進(jìn)行快速精確的誤差檢測。而傳統(tǒng)模板檢測方法由于自身諸多不足已不能滿足實際生產(chǎn)要求[1]。數(shù)字化比對檢測技術(shù)的出現(xiàn)為解決這一難題提供了新的途徑[2]。目前在國外，許多著名的汽車制造廠商比如豐田、大眾、通用等均已將數(shù)字化比對檢測技術(shù)逐漸應(yīng)用于實際生產(chǎn)過程中，大大降低了產(chǎn)品開發(fā)制造成本，縮短了產(chǎn)品開發(fā)制造周期[3]。而在國內(nèi)，數(shù)字化比對檢測技術(shù)的應(yīng)用幾乎還是空白，數(shù)字化比對檢測技術(shù)尚未成熟，其中主要的關(guān)鍵技術(shù)有待進(jìn)一步的研究。因此，必須要對這些關(guān)鍵技術(shù)進(jìn)行深入研究，讓數(shù)字化比對技術(shù)能夠真正地應(yīng)用于實際，滿足生產(chǎn)要求。

1 坐標(biāo)匹配

坐標(biāo)匹配就是要計算得到點云數(shù)據(jù)與CAD模型之間的坐標(biāo)變換矩陣，通過矩陣運算，使得點云數(shù)據(jù)與CAD模型處于同一個坐標(biāo)空間下[4]。

1.1 ICP算法

ICP（Iterative Closest Points）算法通過搜索點云數(shù)據(jù)與CAD模型中的最近點點對，并利用這些最近點對間的距離構(gòu)造目標(biāo)函數(shù)，進(jìn)行迭代運算最終求出坐標(biāo)旋轉(zhuǎn)、平移矩陣，使得目標(biāo)函數(shù)值最小[5]。通常原始ICP算法空間搜索的時間復(fù)雜度是，其中和表示點云數(shù)據(jù)和CAD模型頂點集中點的數(shù)目。如果點的數(shù)量很大，這個過程將非常耗時，因此最近點點對的搜索是ICP算法的瓶頸。本文利用k?D樹來進(jìn)行最近點對的搜索，大大提高了搜索效率。

1.2 k?D樹空間搜索策略

k?D樹是一個針對K維度空間所設(shè)計的二元搜索樹，其本質(zhì)是一個二叉樹[6]，其典型應(yīng)用是求點的k個最近點。k?D樹的生成過程就是平面被軸和軸連續(xù)遞歸劃分的過程，直到最后分割的區(qū)域內(nèi)只有一個點。這樣的分割過程就對應(yīng)了一個完全二叉樹，二叉樹的分支節(jié)點對應(yīng)一條分割線，而每個葉子節(jié)點就對應(yīng)一個數(shù)據(jù)點。利用k?D樹進(jìn)行最近點對搜索的時間復(fù)雜度為，遠(yuǎn)小于傳統(tǒng)的遍歷算法。因此，運用k?D樹空間搜索策略可以在很大程度上提高ICP算法的計算效率。

2 對應(yīng)關(guān)系

通常對于點云數(shù)據(jù)與CAD模型對應(yīng)關(guān)系的建立主要是尋找各點所對應(yīng)的CAD模型上的面片，利用點云各點與CAD模型面片之間的距離表示偏差[7]，然而這些方法不能保證在所有區(qū)域都能得到正確的計算結(jié)果。通過建立半邊數(shù)據(jù)結(jié)構(gòu)表達(dá)CAD模型表面三角形面、邊、頂點的拓?fù)潢P(guān)系，增加點到邊的對應(yīng)關(guān)系和點到點的對應(yīng)關(guān)系，可以彌補傳統(tǒng)方法的不足。

2.1 半邊數(shù)據(jù)結(jié)構(gòu)

半邊數(shù)據(jù)結(jié)構(gòu)是一種以界限為基礎(chǔ)的拓?fù)浣Y(jié)構(gòu)。其基本原理是把三角網(wǎng)格的每條連線分為兩個相等且方向相反的半邊（邊界除外）[8]，如圖1所示。圖1中有四條邊以點為起點，分別為：，，和。索引信息分別儲存在點的結(jié)構(gòu)里，通過找到點，就可以遍歷其所連接邊的鄰邊、孿邊快速得到鄰近三角形的所有信息。

2.2 點對面的關(guān)系

建立點對面的對應(yīng)關(guān)系是點云數(shù)據(jù)比對檢測的基礎(chǔ)。首先對于CAD模型中所有頂點的坐標(biāo)信息建立k?D樹數(shù)據(jù)結(jié)構(gòu)，快速搜索點云中各點所對應(yīng)的CAD模型上的最近頂點。然后通過半邊結(jié)構(gòu)從該對應(yīng)點開始遍歷與該點相連的所有三角面片，根據(jù)判斷準(zhǔn)則找出符合要求的三角面片。

2.3 點對邊的關(guān)系

由于在待測工件的邊緣和棱線以及特征明顯變化的區(qū)域附近，點云數(shù)據(jù)中的點很難在CAD模型上找到滿足要求的對應(yīng)三角面片。如果在這些地方依然采用點對面的對應(yīng)關(guān)系來進(jìn)行處理顯然是行不通的，必須尋找出滿足條件的對應(yīng)邊來建立對應(yīng)關(guān)系。其對應(yīng)邊判斷準(zhǔn)則如圖2所示。

首先，計算出點數(shù)據(jù)中點對于CAD模型中邊的投影點坐標(biāo)；其次，通過計算投影點到邊的兩個端點的距離之和是否大于該邊的長度判斷投影點是否在邊上，若大于則說明投影點不在邊上。根據(jù)這個判斷條件，圖2（a）滿足條件，則可以確定該邊是點的對應(yīng)邊，而圖2（b）則不滿足該判斷條件，則認(rèn)為點與該邊沒有對應(yīng)關(guān)系。

2.4 點對點的關(guān)系

如果經(jīng)過上述兩個步驟，點云上的點依然沒能夠建立點對面或者點對邊的對應(yīng)關(guān)系的話，那么將此點與其在CAD模型中的最近點組成點對點的對應(yīng)關(guān)系，以這兩個點的距離來表示偏差。這種情況一般會出現(xiàn)在待測工件中的棱角和具有尖銳特征的地方。

3 系統(tǒng)實現(xiàn)

檢測系統(tǒng)主要功能包括：點云數(shù)據(jù)與CAD模型初步坐標(biāo)匹配、坐標(biāo)精匹配、點云數(shù)據(jù)各點偏差計算以及色斑圖顯示偏差結(jié)果等功能模塊。圖3表明了本文所開發(fā)的整個數(shù)字化比對檢測系統(tǒng)各個功能模塊的關(guān)系。

4 試驗分析

4.1 處理效率

對于改進(jìn)ICP法的計算效率主要取決于收斂速度，即進(jìn)行多少次的迭代運算。下面通過某水輪機葉片的點云數(shù)據(jù)與其CAD模型來對該系統(tǒng)的ICP坐標(biāo)匹配模塊進(jìn)行分析。利用改進(jìn)ICP法進(jìn)行坐標(biāo)精匹配時，選擇最近點對距離的平均值作為目標(biāo)函數(shù)，并設(shè)置ICP法的收斂條件為兩次迭代運算的目標(biāo)函數(shù)值相差的絕對值小于作為收斂判斷條件，經(jīng)過了9次迭代運算之后最終滿足收斂條件，完成匹配，效果如圖4所示。

根據(jù)測量，最終得到的改進(jìn)ICP法的計算效率如表1所示。從上述試驗檢測結(jié)果來看，改進(jìn)ICP算法實現(xiàn)點云數(shù)據(jù)與CAD模型坐標(biāo)精匹配計算效率較快，能夠滿足實際使用需求。

4.2 偏差精度

本系統(tǒng)采用與德國GOM公司開發(fā)的TRITOP系統(tǒng)中的點云數(shù)據(jù)檢測模塊進(jìn)行偏差計算結(jié)果比較分析來側(cè)面地反映系統(tǒng)的精度。兩個點云檢測模塊對葉片的檢測結(jié)果如圖5所示。可以看到兩者的處理結(jié)果在大體上是一致的。

然而由于TRITOP軟件的檢測原理是指用計算點云數(shù)據(jù)各點對CAD模型面片的最近距離來表示偏差，因此在邊緣棱角或者特征顯著變化的區(qū)域，其計算結(jié)果是不準(zhǔn)確的，如圖6（a）所示，當(dāng)偏差計算范圍是時發(fā)現(xiàn)TRITOP系統(tǒng)對于左側(cè)邊緣的部分點云數(shù)據(jù)由于與CAD模型上錯誤的面片建立了對應(yīng)關(guān)系，導(dǎo)致偏差計算的失效。而本系統(tǒng)由于在邊緣等特定區(qū)域采取了建立點對邊和點對點的對應(yīng)關(guān)系，很好地解決了這些特殊區(qū)域偏差的檢測問題，取得了很好的效果。如圖6（b）所示，在相同的偏差計算范圍下，可以看到在TRITOP系統(tǒng)中處理錯誤的點都得到了正確的偏差計算結(jié)果。

5 結(jié) 語

本文利用k?D樹空間快速搜索策略改進(jìn)ICP算法，采用半邊結(jié)構(gòu)來表達(dá)單元三角網(wǎng)格形式CAD模型的點、邊、面拓?fù)浣Y(jié)構(gòu)，以滿足在建立點云數(shù)據(jù)與CAD模型對應(yīng)關(guān)系時要快速遍歷CAD模型中所有幾何元素的要求，并在此基礎(chǔ)上研制了數(shù)字化比對檢測系統(tǒng)。通過對某水輪機葉片檢測，結(jié)果表明該系統(tǒng)運行效率快、精度高，具有很好的應(yīng)用效果。

參考文獻(xiàn)

[1] 高中亞，李振平，方海濱，等.二維復(fù)雜型面數(shù)字化比較技術(shù)的應(yīng)用[J].工具技術(shù)，2015，49（5）：60?62.

[2] 陸峰，李寧，趙德宏.復(fù)雜曲面三維輪廓精度數(shù)字化比對檢測與誤差分析[J].制造業(yè)自動化，2014（18）：46?50.

[3] 陳勝利.快速成形技術(shù)及其發(fā)展趨勢[J].制造業(yè)自動化，2009，31（10）：24?26.

[4] MA Hongchao， SUN Jie. Intelligent optimization of seam?line finding for orthophoto mosaicking with LiDAR point clouds [J]. Journal of Zhejiang University： Science C， 2011， 12（5）： 417?429.

[5] LI Jianchuan， YU Jianfeng. A new posture evaluation method of wing based on iterative closest point algorithm [J]. Advanced materials research， 2013， 718/720： 1279?1285.

[6] 魏海濤，杜云艷，任浩瑋，等.基于N?KD樹的空間點數(shù)據(jù)分組算法[J].地球信息科學(xué)學(xué)報，2015（1）：1?7.

[7] 徐偉恒，馮仲科，蘇志芳，等.一種基于三維激光點云數(shù)據(jù)的單木樹冠投影面積和樹冠體積自動提取算法[J].光譜學(xué)與光譜分析，2014（2）：465?471.

[8] 王繼東，陳桂林.基于半邊數(shù)據(jù)結(jié)構(gòu)的最短路徑算法及其實現(xiàn)[J].計算機工程與應(yīng)用，2009（8）：118?120.