面向復(fù)雜形面匹配的邊界特征提取方法

高　翔， 王　華， 陳關(guān)龍

(機(jī)械系統(tǒng)與振動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室(上海交通大學(xué))， 上海 200240)

面向復(fù)雜形面匹配的邊界特征提取方法

高翔， 王華， 陳關(guān)龍

(機(jī)械系統(tǒng)與振動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室(上海交通大學(xué))， 上海 200240)

摘要:針對(duì)車身封閉件裝配過(guò)程中的匹配優(yōu)化問(wèn)題，提出一種面向復(fù)雜形面匹配的邊界特征提取方法. 對(duì)匹配邊界特點(diǎn)進(jìn)行分析，確定邊界點(diǎn)的提取信息、采樣間距大小及其搜索鄰域. 對(duì)采樣后的點(diǎn)云數(shù)據(jù)，建立k-d樹(shù)進(jìn)行索引. 對(duì)采樣點(diǎn)在搜索鄰域內(nèi)的鄰近點(diǎn)建立最小二乘微切平面，利用投影到微切平面局部坐標(biāo)系內(nèi)的鄰近點(diǎn)分布特性，判斷邊界特征點(diǎn)及其匹配特征. 案例分析驗(yàn)證了該方法在處理復(fù)雜形面匹配邊界特征點(diǎn)提取時(shí)的有效性，在不影響匹配效果的前提下，本文方法可顯著提高復(fù)雜形面邊界特征的提取效率.

關(guān)鍵詞:車身裝配; 復(fù)雜形面匹配; 點(diǎn)云數(shù)據(jù); 邊界特征提取

車身封閉件(包括車燈、引擎蓋、行李箱蓋、車門(mén)等)的外形設(shè)計(jì)隨著消費(fèi)者審美需求的提高，逐漸從傳統(tǒng)的規(guī)則形狀發(fā)展為三維復(fù)雜外形面[1]. 這種復(fù)雜形面在匹配過(guò)程中，由車身封閉件的形面邊界和白車身本體的形面邊界構(gòu)成的縫隙和面差往往很難通過(guò)人工測(cè)量進(jìn)行準(zhǔn)確評(píng)估. 另外，傳統(tǒng)匹配方法[2-5]的匹配數(shù)據(jù)主要來(lái)源于三坐標(biāo)測(cè)量機(jī)，只能在一定的時(shí)間內(nèi)測(cè)量有限個(gè)測(cè)點(diǎn)，同時(shí)由于受到了測(cè)量物體本身的定位偏差、制造偏差以及裝配偏差等影響，這些測(cè)點(diǎn)只能部分表達(dá)被測(cè)物體匹配邊界的狀態(tài)；相比之下，通過(guò)點(diǎn)云掃描設(shè)備獲得的點(diǎn)云數(shù)據(jù)就可以更好地反映出匹配邊界的特性，通過(guò)對(duì)復(fù)雜形面邊界特征提取，可以進(jìn)一步優(yōu)化復(fù)雜形面之間的姿態(tài)匹配.

點(diǎn)云邊界特征的提取在逆向工程領(lǐng)域應(yīng)用較多，直接從點(diǎn)云提取邊界特征的方法主要有兩類. 一類是基于切邊特征的提取方法，柯映林等[6]對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行了柵格化劃分，識(shí)別出種子邊界柵格，根據(jù)空間拓?fù)錁?gòu)型連接邊界柵格，由于采用了拓?fù)溥壿嬇袛嗨惴?，提高了邊界提取效率和穩(wěn)定性，但是柵格劃分的大小會(huì)對(duì)邊界特征的精度產(chǎn)生一定影響；孫殿柱等[7]提出了散亂數(shù)據(jù)點(diǎn)云邊界特征自動(dòng)提取算法，對(duì)散亂點(diǎn)云數(shù)據(jù)采用R-tree結(jié)構(gòu)進(jìn)行空間索引，進(jìn)而提取參考點(diǎn)附近的k個(gè)最近點(diǎn)，建立參考點(diǎn)的微切平面，針對(duì)微切平面上的參考點(diǎn)及其最近點(diǎn)的投影連線，用判斷最大鄰近向量夾角的方法識(shí)別出散亂點(diǎn)云的邊界. 陳義仁等[8]用三維排序的方法建立索引，用場(chǎng)力大小來(lái)判斷投影點(diǎn)集是否位于曲面邊界，提高了算法運(yùn)算速度. 另一類是基于交線特征的提取方法[9-13]. Pauly等[9]針對(duì)局部鄰域進(jìn)行協(xié)變量分析潛在的特征點(diǎn)，通過(guò)改變鄰域半徑大小，可以實(shí)現(xiàn)不同精度的數(shù)據(jù)處理結(jié)果. 張旭等[10]提出的基于模板的點(diǎn)云特征提取技術(shù)，由理論模型在計(jì)算機(jī)輔助設(shè)計(jì)下生成理論交線上的離散點(diǎn)和切矢量，進(jìn)而在模板上切片獲得截面用于二維數(shù)據(jù)分析，并以理論離散點(diǎn)為分界依據(jù)，將截面數(shù)據(jù)分成兩段后擬合獲得兩段曲線交點(diǎn)，即邊界交線特征上的點(diǎn). Gumhold等[11]在鄰域中建立了黎曼圖，同樣采用了協(xié)方差分析的方式標(biāo)記潛在交線特征. 兩種方法都使用最小生成樹(shù)連接特征點(diǎn)，并用曲線擬合的方式最終獲得近似的邊界特征. Demarsin等[12]使用主成分分析法計(jì)算點(diǎn)的法向量，并通過(guò)鄰域的法向偏差對(duì)點(diǎn)云進(jìn)行分割，同時(shí)也采用了最小生成樹(shù)法連接邊界點(diǎn). Daniels等[13]采用移動(dòng)最小二乘法對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行光滑特征的提取，從特征點(diǎn)中構(gòu)建邊界交線，最后連接相鄰的邊界交線，形成封閉光滑的特征線. 在這兩類方法中，前者針對(duì)有界點(diǎn)云數(shù)據(jù)的邊界進(jìn)行提取，后者則對(duì)點(diǎn)云數(shù)據(jù)中造型面之間的交線進(jìn)行提取，兩類特征的提取方法有很大的差異. 此外這些研究主要用于提取掃描對(duì)象的邊界點(diǎn)集，從而得到簡(jiǎn)化模型，實(shí)現(xiàn)對(duì)掃描對(duì)象的曲面重構(gòu)及逆向造型.

本文針對(duì)具有復(fù)雜外形面的車身封閉件匹配這一問(wèn)題，提出了通過(guò)提取復(fù)雜形面輪廓邊界的空間坐標(biāo)及其表面信息的方法，為復(fù)雜形面邊界進(jìn)一步匹配優(yōu)化提供依據(jù).

1復(fù)雜形面的邊界特征

按照邊界形成的成因來(lái)分類，復(fù)雜形面的邊界曲線可以分為兩類，一類是由單個(gè)曲面的邊界自然形成的，如鈑金件切邊、車燈的邊界等；另一類是兩個(gè)曲面相交時(shí)產(chǎn)生的交線，如車身上的對(duì)應(yīng)匹配區(qū)域由于沖壓、鑄造、翻邊或者折邊等工藝形成的交線.

如圖1所示，典型的匹配斷面既包含切邊形成的匹配邊界，也包含交線形成的匹配邊界. 對(duì)于交線特征，從掃描設(shè)備的視角來(lái)看，當(dāng)掃描范圍只覆蓋匹配側(cè)外表面時(shí)，其匹配邊界即為切線特征. 因此，對(duì)于交線特征的表面，可以通過(guò)規(guī)范掃描設(shè)備的掃描路徑將其轉(zhuǎn)化為切邊邊界特征，從而形成統(tǒng)一的邊界形式進(jìn)行邊界特征提取.

圖1　典型匹配斷面圖

傳統(tǒng)車身封閉件與車身裝配后通過(guò)裝配體之間縫隙的大小和外表面之間面差的大小來(lái)評(píng)價(jià)兩者之間的匹配質(zhì)量(如圖2所示). 簡(jiǎn)單形面可以使用塞尺和面差計(jì)人工測(cè)量,進(jìn)行評(píng)價(jià)，但是對(duì)于三維復(fù)雜形面之間的匹配，肉眼難以定量地確定形面之間的匹配關(guān)系. 邊界點(diǎn)本身的空間坐標(biāo)位置只能表達(dá)兩個(gè)邊界點(diǎn)之間相對(duì)的位置關(guān)系，匹配得好壞還需要通過(guò)縫隙和面差的大小來(lái)進(jìn)行評(píng)價(jià).

圖2　車身封閉件匹配評(píng)價(jià)指標(biāo)

圖3　邊界任意一點(diǎn)處的匹配特征

2匹配邊界特征的提取方法

匹配特征提取方法基本流程包括以下步驟：使用k-d樹(shù)(多維二叉樹(shù))建立二叉數(shù)據(jù)分類和索引結(jié)構(gòu)，將每個(gè)數(shù)據(jù)存儲(chǔ)在每個(gè)節(jié)點(diǎn)中，可以實(shí)現(xiàn)鄰近點(diǎn)的搜索[14]；通過(guò)對(duì)復(fù)雜形面的分析,確定采樣間距和特征搜索鄰域；通過(guò)鄰域內(nèi)鄰近點(diǎn)的位置關(guān)系，確定匹配邊界特征，并提取相應(yīng)的空間坐標(biāo)和形面的向量特征.

2.1采樣間距和特征搜索鄰域的確定

對(duì)于復(fù)雜形面，通過(guò)掃描得到的點(diǎn)云數(shù)據(jù)往往是由幾次掃描數(shù)據(jù)拼合而成的. 具有完整表面信息的點(diǎn)云數(shù)據(jù)通常是散亂點(diǎn)云，因此需要對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行稀釋和均一化處理.

對(duì)于匹配邊界特征的鄰域，首先要考慮的是采樣原則. 一方面通過(guò)均勻采樣可以保證散亂點(diǎn)云數(shù)據(jù)的有序規(guī)范；另一方面采樣間距的大小決定了最終的匹配效果，采樣間距越小，綜合匹配效果越好，但是也會(huì)造成計(jì)算量的增加，從而影響匹配效率.

(1)

式(1)代表每條圓弧近似直線段的單位向量，而其法向方向，則可以表示為

圖4　線段擬合匹配邊界示意

進(jìn)一步對(duì)內(nèi)外圈圓弧近似直線段的縫隙間距d進(jìn)行計(jì)算：

(2)

2.2匹配邊界特征提取

掃描點(diǎn)云中包含著大量的坐標(biāo)數(shù)據(jù)信息，按照匹配需求可劃分為兩類：一類是具有匹配功能的邊界點(diǎn)；另一類是對(duì)匹配貢獻(xiàn)度較小的面點(diǎn)，這一類點(diǎn)云數(shù)據(jù)在數(shù)據(jù)處理中屬于冗余信息，需要進(jìn)行剔除，留下邊界點(diǎn)云用于下一步的處理.

根據(jù)前文討論結(jié)果，以πr/18為鄰域搜索半徑，應(yīng)用k-d樹(shù)建立的索引對(duì)點(diǎn)云每一點(diǎn)的鄰域點(diǎn)進(jìn)行搜索，以該鄰域內(nèi)的點(diǎn)作為該點(diǎn)的局部參考面的點(diǎn)集，采用最小二乘法對(duì)該點(diǎn)集進(jìn)行擬合.

(3)

此時(shí)，求方程(3)最小二乘解，將點(diǎn)集的坐標(biāo)陣擴(kuò)展成滿秩矩陣，對(duì)其進(jìn)行奇異值分解得到最小特征值的特征向量υmin，即平面方程參數(shù)的最小二乘解aLS.

(4)

式(4)中U和V為正交矩陣，特征向量用υi(i=1,2,3,4)表示. 求解方程式的最小特征值，即可確定方程

F(x,y,z)=a1x+a2y+a3z+a4=0

圖5　k鄰近點(diǎn)、最小二乘平面和法向量示意

(a) 非邊界點(diǎn)

(b) 邊界點(diǎn)

通過(guò)局部坐標(biāo)系，計(jì)算每一個(gè)向量的與x軸的夾角αi(i=1,2,…,k)，并按照大小對(duì)其進(jìn)行排序，相鄰向量間的夾角可表示為

如圖7所示，對(duì)圖中所示的圓形物體進(jìn)行均勻采樣后，位于邊界處的采樣點(diǎn)的最大夾角和位于內(nèi)部的采樣點(diǎn)的最大夾角有顯著不同. 根據(jù)前文確定的鄰域大小，計(jì)算單個(gè)采樣點(diǎn)與k鄰近點(diǎn)組成的向量夾角. 對(duì)非邊界點(diǎn)，最大夾角為45°，對(duì)邊界點(diǎn)，最大夾角在90°～225°變化，因此邊界點(diǎn)的采樣閾值可確定為90°，采樣點(diǎn)的最大夾角大于此閾值的即為邊界特征點(diǎn). 由此，具有不同形態(tài)特征和采樣條件的物體均可以根據(jù)以上原則進(jìn)行數(shù)據(jù)分析，計(jì)算得出合理的夾角閾值，同時(shí)通過(guò)設(shè)定閾值，篩選出最大夾角大于閾值的采樣點(diǎn)，從而獲得邊界點(diǎn)點(diǎn)集.

圖7　采樣點(diǎn)在鄰域內(nèi)的最大相鄰向量夾角

3案例分析

如圖8所示，以兩個(gè)半圓柱匹配對(duì)象為例，對(duì)本文方法進(jìn)行試驗(yàn)驗(yàn)證. 半圓柱弧面各自以隨機(jī)生成的散亂點(diǎn)云數(shù)據(jù)來(lái)表征，長(zhǎng)圓柱弧面由20 000個(gè)隨機(jī)點(diǎn)構(gòu)成，而短圓柱弧面則有10 000個(gè)隨機(jī)點(diǎn)構(gòu)成，匹配邊界處圓弧的半徑為1.

圖8　匹配特征試驗(yàn)對(duì)象及其隨機(jī)點(diǎn)云數(shù)據(jù)

根據(jù)前文定義,采樣間距應(yīng)小于πr/36，搜索鄰域應(yīng)小于πr/18，這里選定采樣間距為0.08，搜索鄰域?yàn)?.16，相鄰向量夾角閾值為155°. 稀釋前的點(diǎn)云搜索鄰域設(shè)為0.08，如圖9所示，從長(zhǎng)圓柱弧面和短圓柱弧面提取出的邊界點(diǎn)數(shù)分別為344個(gè)和288個(gè)，分別耗時(shí)287.89 s和127.24 s；邊界點(diǎn)稀釋后的點(diǎn)云數(shù)據(jù)如圖10所示，在保留原有特征的同時(shí)，長(zhǎng)圓柱弧面的點(diǎn)云數(shù)量從20 000個(gè)減少到了847個(gè)；而短圓柱弧面的點(diǎn)云數(shù)量則從10 000個(gè)減少到了435個(gè). 從稀釋后的點(diǎn)云中提取出邊界點(diǎn)，數(shù)量分別為84和74個(gè)，分別耗時(shí)3.36 s和1.50 s.

圖9　稀釋前點(diǎn)云及其邊界特征點(diǎn)

圖10　稀釋點(diǎn)云及其邊界特征點(diǎn)

通過(guò)圓柱體案例分析，驗(yàn)證了本方法的可行性和提取效率. 為了進(jìn)一步驗(yàn)證本方法在工程應(yīng)用中的有效性，本文對(duì)具有復(fù)雜形面特點(diǎn)的某車型尾燈的邊界進(jìn)行了研究.

如圖11所示，通過(guò)掃描設(shè)備對(duì)該尾燈的數(shù)據(jù)進(jìn)行掃描后得到原始點(diǎn)云數(shù)據(jù)，初始點(diǎn)云數(shù)量為73 050個(gè). 通過(guò)對(duì)邊界點(diǎn)的分析，其主要匹配區(qū)域(圖中尾燈的左下和右上的邊界區(qū)域)的邊界近似圓弧半徑不小于60，因此采樣間距設(shè)為5，得到稀釋后的點(diǎn)云數(shù)據(jù)，為3 356個(gè). 采用本文方法提取邊界特征，搜索鄰域距離設(shè)為10，相鄰向量夾角閾值設(shè)為155°，得到邊界特征208個(gè)，耗時(shí)15.82 s；采用文獻(xiàn)[7]的方法，搜索最近鄰近點(diǎn)設(shè)為10個(gè)，相鄰向量夾角閾值設(shè)為155°，得到邊界特征210個(gè)，耗時(shí)615.27 s；顯然在初始條件和結(jié)果基本一致的情況下，本文方法得到的是動(dòng)態(tài)的鄰近點(diǎn)，對(duì)于邊界點(diǎn)，其鄰近點(diǎn)必然少于非邊界點(diǎn)的鄰近點(diǎn)，因此本文的提取效率比原有方法得到了顯著提高.

掃描點(diǎn)云

稀釋點(diǎn)云及提取邊界

從簡(jiǎn)單圓柱和實(shí)際尾燈的案例分析中可以發(fā)現(xiàn)，對(duì)于散亂點(diǎn)云數(shù)據(jù)，根據(jù)其匹配特征定義合理的采樣間距對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行稀釋，從而獲得均勻分布的點(diǎn)云. 在滿足匹配要求的前提下，可以提高邊界特征點(diǎn)的提取效率.

4結(jié)論

1)本文針對(duì)車身裝配中復(fù)雜形面的匹配問(wèn)題，確定了匹配邊界的提取目標(biāo)，并提出了一種適用于復(fù)雜形面的邊界特征提取方法.

2)以k-d樹(shù)數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)，根據(jù)復(fù)雜形面的匹配特點(diǎn)，確定了采樣間距和搜索域的大小，精簡(jiǎn)了目標(biāo)點(diǎn)云數(shù)據(jù).

3)通過(guò)對(duì)采樣點(diǎn)在搜索鄰域內(nèi)的鄰近點(diǎn)建立最小二乘微切平面，分析鄰近點(diǎn)投影到微切平面局部坐標(biāo)系后的分布特性，從而確定邊界特征點(diǎn)并提取匹配所需信息，包括邊界點(diǎn)坐標(biāo)及其匹配局部坐標(biāo)系向量.

4)通過(guò)案例分析，對(duì)本方法進(jìn)行了驗(yàn)證. 在不影響匹配效果的前提下，其匹配邊界的提取效率得到顯著提高，為復(fù)雜形面匹配過(guò)程中分析、評(píng)估、優(yōu)化提供了數(shù)據(jù)基礎(chǔ).

參考文獻(xiàn)

[1] GAO X, WANG H, CHEN G. Fitting optimization based on weighted Gaussian imaging method for auto body taillight assembly [J]. Assembly Autom, 2014, 34(3): 255-263.

[2] WU S K, HU S J, WU S M. Optimal door fitting with systematic fixture adjustment [J]. International Journal of Flexible Manufacturing Systems, 1994, 6(2): 99-121.

[3] FAINBERG Z, ZUSSMAN E. Even fitting closed curves: 2-D algorithm and assembly applications [J]. Journal of manufacturing science and engineering, 1999, 121(2): 265-272.

[4] 許技科, 王華, 鄭恒雍, 等. 基于分段 Hausdorff 距離的車身前臉匹配優(yōu)化 [J]. 上海交通大學(xué)學(xué)報(bào), 2010, 44(4): 0535-0539.

[5] GAO X, WANG H, CHEN G. Curve fitting optimization based on a mixed model for assembly applications[J]. Journal of Intelligent Manufacturing, 2015, 26(6): 1113-1120.

[6] 柯映林, 范樹(shù)遷. 基于點(diǎn)云的邊界特征直接提取技術(shù) [J]. 機(jī)械工程學(xué)報(bào), 2004, 4(9): 116-120.

[7] 孫殿柱, 范志先, 李延瑞. 散亂數(shù)據(jù)點(diǎn)云邊界特征自動(dòng)提取算法 [J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008, 36(8): 82-84.

[8] 陳義仁, 王一賓, 彭張節(jié), 等. 一種改進(jìn)的散亂點(diǎn)云邊界特征點(diǎn)提取算法 [J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(23): 177-180.

[9] PAULY M, KEISER R, GROSS M. Multi-scale feature extraction on point-sampled surfaces [J]. Computer Graphics Forum, 2003, 22(3): 281-289.

[10]張旭, 王青, 柯映林. 基于模板的點(diǎn)云邊特征提取技術(shù) [J]. 計(jì)算機(jī)集成制造系統(tǒng), 2008, 14(6): 1175-1181.

[11]GUMHOLD S, WANG X, MACLEOD R. Feature extraction from point clouds [C]//Proceedings of the 10th International Meshing Roundtable. Newport Beach: Sandia National Laboratories, 293-305.[12]DEMARSIN K, VANDERSTRAETEN D, VOLODINE T, et al. Detection of closed sharp edges in point clouds using normal estimation and graph theory [J]. Comput Aided Design, 2007, 39(4): 276-283.

[13]DANIELS J, HA L K, OCHOTTA T, et al. Robust smooth feature extraction from point clouds[C]//2007 SMI '07 IEEE International Conference on Shape Modeling and Applications. Lyon: IEEE, 2007: 123-136.

[14]周培德. 計(jì)算幾何: 算法分析與設(shè)計(jì) [M]. 北京: 清華大學(xué)出版社, 2000.

(編輯楊波)

A method on boundary feature extraction of complex surface fitting

GAO Xiang, WANG Hua, CHEN Guanlong

(State Key Laboratory of Mechanical System and Vibration(Shanghai Jiaotong University), Shanghai 200240, China)

Abstract:A method on boundary feature extraction of complex surface fitting was proposed due to the fitting optimization during the assembly of auto-body closure parts. The extraction objects, sampling size and searching neighbor were decided based on the fitting boundary features. Point cloud was sampled and constructed by k-d tree. The points within the searching neighbors were projected to their least square tangent plane and the boundary points with fitting features could be extracted by judging the distribution. A case study was conducted to prove the effectiveness and efficiency of this method.

Keywords:auto-body assembly; complex surface fitting; point cloud; boundary feature extraction

doi：10.11918/j.issn.0367-6234.2016.07.007

收稿日期:2015-08-03

基金項(xiàng)目:國(guó)家自然科學(xué)基金(50905117)

作者簡(jiǎn)介:高翔(1983—)，男，博士研究生； 陳關(guān)龍(1947—)，男，教授，博士生導(dǎo)師

通信作者:高翔， kami@sjtu.edu.cn

中圖分類號(hào):TP391.7

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):0367-6234(2016)07-0046-06

王華(1975—)，男，副教授，博士生導(dǎo)師；