基于點(diǎn)云數(shù)據(jù)的數(shù)字化比對(duì)檢測(cè)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

陳芷+吳捷+馬小虎

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

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

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

1 坐標(biāo)匹配

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

1.1 ICP算法

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

1.2 k?D樹空間搜索策略

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

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

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

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

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

2.2 點(diǎn)對(duì)面的關(guān)系

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

2.3 點(diǎn)對(duì)邊的關(guān)系

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

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

2.4 點(diǎn)對(duì)點(diǎn)的關(guān)系

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

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

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

4 試驗(yàn)分析

4.1 處理效率

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

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

4.2 偏差精度

本系統(tǒng)采用與德國(guó)GOM公司開發(fā)的TRITOP系統(tǒng)中的點(diǎn)云數(shù)據(jù)檢測(cè)模塊進(jìn)行偏差計(jì)算結(jié)果比較分析來(lái)側(cè)面地反映系統(tǒng)的精度。兩個(gè)點(diǎn)云檢測(cè)模塊對(duì)葉片的檢測(cè)結(jié)果如圖5所示?？梢钥吹絻烧叩奶幚斫Y(jié)果在大體上是一致的。

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

5 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

[3] 陳勝利.快速成形技術(shù)及其發(fā)展趨勢(shì)[J].制造業(yè)自動(dòng)化，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樹的空間點(diǎn)數(shù)據(jù)分組算法[J].地球信息科學(xué)學(xué)報(bào)，2015（1）：1?7.

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

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