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

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

(機械系統(tǒng)與振動國家重點實驗室(上海交通大學)， 上海 200240)

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

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

(機械系統(tǒng)與振動國家重點實驗室(上海交通大學)， 上海 200240)

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

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

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

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

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

1復雜形面的邊界特征

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

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

圖1　典型匹配斷面圖

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

圖2　車身封閉件匹配評價指標

圖3　邊界任意一點處的匹配特征

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

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

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

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

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

(1)

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

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

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

(2)

2.2匹配邊界特征提取

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

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

(3)

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

(4)

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

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

圖5　k鄰近點、最小二乘平面和法向量示意

(a) 非邊界點

(b) 邊界點

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

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

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

3案例分析

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

圖8　匹配特征試驗對象及其隨機點云數(shù)據(jù)

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

圖9　稀釋前點云及其邊界特征點

圖10　稀釋點云及其邊界特征點

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

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

掃描點云

稀釋點云及提取邊界

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

4結(jié)論

1)本文針對車身裝配中復雜形面的匹配問題，確定了匹配邊界的提取目標，并提出了一種適用于復雜形面的邊界特征提取方法.

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

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

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

參考文獻

[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]. 上海交通大學學報, 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ù) [J]. 機械工程學報, 2004, 4(9): 116-120.

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

[8] 陳義仁, 王一賓, 彭張節(jié), 等. 一種改進的散亂點云邊界特征點提取算法 [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]張旭, 王青, 柯映林. 基于模板的點云邊特征提取技術(shù) [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]周培德. 計算幾何: 算法分析與設(shè)計 [M]. 北京: 清華大學出版社, 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

基金項目:國家自然科學基金(50905117)

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

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

中圖分類號:TP391.7

文獻標志碼:A

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

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