逆向工程中的點(diǎn)云采樣算法研究

林秀芳

（福建農(nóng)林大學(xué) 金山學(xué)院，福建 福州 350002）

作為產(chǎn)品設(shè)計(jì)制造的一種手段，在20世紀(jì)90年代初，逆向工程技術(shù)開始引起了各國工業(yè)界的高度重視。逆向工程，又稱反求工程（Reverse Engineering），是將已有產(chǎn)品模型或?qū)嵨锬Ｐ娃D(zhuǎn)化為工程設(shè)計(jì)模型和概念模型，再在此基礎(chǔ)上對(duì)已有產(chǎn)品進(jìn)行再設(shè)計(jì)和制造。逆向工程的體系結(jié)構(gòu)由數(shù)據(jù)獲取、數(shù)據(jù)處理、曲面建模以及基于CAD模型的再設(shè)計(jì)和產(chǎn)品制造組成[1]。

測(cè)量數(shù)據(jù)點(diǎn)云一般密度很大，所構(gòu)造的三角面片模型容量過于巨大，因此存儲(chǔ)、處理或顯示都將消耗大量的時(shí)間和計(jì)算機(jī)資源。另外，用于誤差評(píng)價(jià)時(shí)，點(diǎn)云也不能過密，否則計(jì)算量會(huì)更大，將消耗大量的時(shí)間。因此，在逆向工程中測(cè)量數(shù)據(jù)的精簡(jiǎn)是數(shù)據(jù)處理的重要工作之一，而點(diǎn)云采樣是數(shù)據(jù)精簡(jiǎn)的一個(gè)重要方法。

激光掃描儀獲取的掃描線數(shù)據(jù)排列密集，沒有明顯的拓?fù)潢P(guān)系，為了滿足CAD建模軟件的要求，應(yīng)生成矩形拓?fù)渚W(wǎng)格形式的數(shù)據(jù)。矩形拓?fù)渚W(wǎng)格點(diǎn)應(yīng)隨著曲面曲率變化而變化，曲率越大部分，采樣點(diǎn)應(yīng)當(dāng)越密集，曲率小的部分，采樣點(diǎn)應(yīng)當(dāng)稀疏。Pahk[2]初步探討了在模具型面上隨曲率變化的采樣的問題。Li[3]提出了依據(jù)曲率測(cè)度的采樣網(wǎng)格產(chǎn)生方法，該方法能自組織地形成拓?fù)渚W(wǎng)格，但沒有研究逆向工程中，在給定曲面建模逼近精度的條件下，如何選取采樣點(diǎn)的問題。文獻(xiàn)[4]中探討了隨曲率變化的采樣布點(diǎn)，但沒有涉及如何在給定采樣精度下選取最少的采樣點(diǎn)。文獻(xiàn)[5]中雖然給出了一種確定合理采樣點(diǎn)數(shù)的方法，但其就幾何意義并不明確。

1 點(diǎn)云采樣算法描述

本文先用準(zhǔn)均勻B樣條曲線對(duì)激光掃描線點(diǎn)云數(shù)據(jù)進(jìn)行逼近擬合，然后利用曲率獲得重采樣點(diǎn)，最后對(duì)兩兩相鄰的曲線進(jìn)行采樣點(diǎn)的匹配細(xì)分，生成網(wǎng)格狀數(shù)據(jù)點(diǎn)陣作為曲面建模的型值點(diǎn)，以滿足CAD軟件建模的要求。

1.1 截面曲線上密集測(cè)量數(shù)據(jù)點(diǎn)的B樣條曲線逼近

本文采用的準(zhǔn)均勻B樣條曲線類型可以使人們對(duì)曲線在端點(diǎn)的行為有更好的控制，從而提高了曲線的靈活度和逼近的精度。此外，在求解B樣條曲線的控制點(diǎn)時(shí)本文用最小二乘逼近法，在保證精確度的同時(shí)可以提高計(jì)算效率。

下面介紹如何采用準(zhǔn)均勻B逼近算法對(duì)截面曲線數(shù)據(jù)進(jìn)行擬合[6]。 設(shè)截面曲線數(shù)據(jù)點(diǎn)列為 Pi，i=0，1，…，m，擬合后的B樣條曲線為

其中 Nj，k（u）為 k 次 B 樣條基函數(shù)（k=3），而 dj是待求的B樣條控制點(diǎn)。

1.2 基于曲率特征的采樣規(guī)劃算法

基于曲率特征的采樣是指在曲線曲率大的部分采樣點(diǎn)分布應(yīng)當(dāng)密集，在曲率小的地方分布應(yīng)當(dāng)稀疏。本文采用了根據(jù)質(zhì)點(diǎn)系平衡原理的局部插值方法來計(jì)算采樣點(diǎn)的分布[7]。如圖1所示質(zhì)點(diǎn)系，若質(zhì)點(diǎn)m1和m2分別位于u軸上的u1和u2處，且m1>m2，則質(zhì)點(diǎn)系的質(zhì)心u在軸上的位置uc為:

圖1 質(zhì)點(diǎn)系Fig.1 System of particles

上式可進(jìn)一步寫成一般的力矩平衡方程形式：

其中uc是平衡質(zhì)點(diǎn)系的質(zhì)心位置，uj是平衡質(zhì)點(diǎn)系中各指點(diǎn)的空間位置，其質(zhì)量為 mj，j=1，2，L。 顯然如果 mj越大，質(zhì)心位置uc就越接近質(zhì)點(diǎn)位置uj。相似地，可以將這個(gè)原理用于截面曲線采樣點(diǎn)的自適應(yīng)生成。也即若將各點(diǎn)的曲率函數(shù)k（u）視為各質(zhì)點(diǎn)的質(zhì)量，則質(zhì)心的位置將趨于曲率大的部分。

1.3 矩形拓?fù)渚W(wǎng)格數(shù)據(jù)點(diǎn)陣的生成

完成所有曲線依照曲率變化規(guī)劃采樣點(diǎn)分布后，采用曲線間采樣點(diǎn)匹配細(xì)分方法。曲線間采樣點(diǎn)匹配是指在相鄰的兩條截面曲線ci和ci+1之間，取采樣點(diǎn)數(shù)少的曲線ci上的一個(gè)點(diǎn)，然后在另一曲線ci+1的采樣點(diǎn)中尋找其對(duì)應(yīng)點(diǎn)，對(duì)應(yīng)點(diǎn)定義為ci+1在上所有采樣點(diǎn)與其距離最近的點(diǎn)。

當(dāng)ci上所有點(diǎn)找到對(duì)應(yīng)點(diǎn)之后，對(duì)曲線ci進(jìn)行細(xì)分。

1） 令 si，y和 si+1，y分別表示相鄰曲線 ci和 ci+1上相互匹配的采樣點(diǎn)，其中y=1，2，…m，m是ci的采樣點(diǎn)數(shù)。首先規(guī)定這兩條截面曲線ci和ci+1的首末采樣點(diǎn)一一對(duì)應(yīng)，即si，1對(duì)應(yīng)于si+1，1，si，m對(duì)應(yīng)于 si+1，m。

2） 假設(shè)曲線 ci+1上 si+1，y和 si+1，y+1間有未被匹配的點(diǎn) pi+1，y，x，其中 x=1，2， …n，n 是 si+1，y 和 si+1，y+1間的未被匹配的點(diǎn)的數(shù)目。 應(yīng)該按照 pi+1，y，1、pi+1，y，2…pi+1，y，n的順序依次往下確定各個(gè)點(diǎn)對(duì)應(yīng)于ci上的細(xì)分點(diǎn)，具體步驟是：為了確保在ci找到的細(xì)分點(diǎn)與 pi+1，y，x相對(duì)應(yīng)， 就要計(jì)算出 pi+1，y，x將 si+1，y 和 si+1，y+1間的曲線分成兩段曲線和弧長的 比 例 ，然 后按同樣的比例在曲線ci的 si，y和si，y+1間的曲線上增加一個(gè)采樣點(diǎn)，以此作為 pi+1，y，x的對(duì)應(yīng)點(diǎn)。

即使相鄰曲線的曲率變化差異很大，也可以實(shí)現(xiàn)采樣點(diǎn)的細(xì)分，如圖2所示。按上述方法處理所有曲線，可獲得矩形網(wǎng)格數(shù)據(jù)點(diǎn)陣。

2 應(yīng)用實(shí)例

為了驗(yàn)證改進(jìn)算法的可靠性，即使兩兩掃描曲線間曲率變化差異很大，也可以實(shí)現(xiàn)曲線間采樣點(diǎn)的細(xì)分，本章把自適應(yīng)重采樣算法應(yīng)用于小熊蝴蝶結(jié)測(cè)量數(shù)據(jù)的建模。小熊蝴蝶結(jié)測(cè)量數(shù)據(jù)如圖3所示。

首先用B樣條曲線逼近每條截面曲線上的測(cè)量數(shù)據(jù)，以其中一條截面曲線為例，該截面線的測(cè)量點(diǎn)如圖4所示，其相對(duì)應(yīng)的逼近曲線和截面線上的采樣點(diǎn)如圖5所示。

圖2 細(xì)分方法的效果圖Fig.2 Effect drawing of subdivision method

圖3 蝴蝶結(jié)模型測(cè)量數(shù)據(jù)Fig.3 Measurement data of bowknot modle

圖4 截面線測(cè)點(diǎn)Fig.4 Measurement point of section line

圖5 截面線的B樣條擬合曲線和采樣Fig.5 B-Spline curve and sampling points of section line

經(jīng)曲線間節(jié)點(diǎn)匹配、細(xì)分生成矩形拓?fù)渚W(wǎng)格數(shù)據(jù)如圖6所示。

由采樣數(shù)據(jù)在I-DEAS建立的曲面模型如圖7所示。

3 結(jié)束語

圖6 匹配細(xì)分后的矩形拓?fù)渚W(wǎng)格數(shù)據(jù)Fig.6 Rectangular topology grid data after matching and segmentation

圖7 網(wǎng)格化模型Fig.7 Griddized model

本文采樣的對(duì)象是掃描線點(diǎn)云數(shù)據(jù)，掃描線是被測(cè)物體的截面曲線，彼此位于垂直于X或者Y軸的截面上，即平面曲線。在逼近擬合掃描線數(shù)據(jù)時(shí)用準(zhǔn)均勻B樣條曲線，提高了曲線的靈活度和逼近的精度。此外，此算法中采樣點(diǎn)細(xì)分方法適應(yīng)性強(qiáng)，不受兩兩曲線間曲率變化差異大小的影響。但由于文中所改進(jìn)的自適應(yīng)重采樣算法只是針對(duì)掃描線點(diǎn)云數(shù)據(jù)，所以如何把自適應(yīng)重采樣算法擴(kuò)展到處理散亂點(diǎn)云的鄰域也是一個(gè)值得研究的問題。

[1]金濤，童水光.逆向工程技術(shù)[M].北京：機(jī)械工業(yè)出版社，2003.

[2]Pahk H K.Development of computer-aided inspection system with CMM for integrated mold manufacturing[J].Annals of the CIRP，1993（42）：557-560.

[3]Li S Z.Adaptive sampling and mesh generation[J].Computer Aided Design，1995，27（3）：235-240.

[4]來新民，黃田，林忠欽.基于模型NURBS的散亂數(shù)據(jù)點(diǎn)自由曲面重構(gòu)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，1999，11（5）:433-436.LAI Xin-min，HUANG Tian，LIN Zhong-qin.NURBS based approach of surface reconstruction from scattered data[J].Journal of CAD and Graphics，1999，11（5）:433-436.

[5]來新民，黃田，林忠欽.數(shù)學(xué)模型已知的自由曲面數(shù)字化自適應(yīng)采樣[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，1999，11（4）：359-362.LAI Xin-min，HUANG Tian，LIN Zhong-qin. Known mathematical model[J].Journal of CAD and Graphics，1999，11（4）：359-362.

[6]施法中.計(jì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B樣條[M].北京：北京航天航空大學(xué)出版社，1994.

[7]劉志剛.逆向工程中線結(jié)構(gòu)光視覺傳感器與CMM集成測(cè)量技術(shù)研究[D].西安:西安交通大學(xué)，2000.