逆向工程中的點云采樣算法研究

林秀芳

（福建農林大學 金山學院，福建 福州 350002）

作為產品設計制造的一種手段，在20世紀90年代初，逆向工程技術開始引起了各國工業界的高度重視。逆向工程，又稱反求工程（Reverse Engineering），是將已有產品模型或實物模型轉化為工程設計模型和概念模型，再在此基礎上對已有產品進行再設計和制造。逆向工程的體系結構由數據獲取、數據處理、曲面建模以及基于CAD模型的再設計和產品制造組成[1]。

測量數據點云一般密度很大，所構造的三角面片模型容量過于巨大，因此存儲、處理或顯示都將消耗大量的時間和計算機資源。另外，用于誤差評價時，點云也不能過密，否則計算量會更大，將消耗大量的時間。因此，在逆向工程中測量數據的精簡是數據處理的重要工作之一，而點云采樣是數據精簡的一個重要方法。

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

1 點云采樣算法描述

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

1.1 截面曲線上密集測量數據點的B樣條曲線逼近

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

下面介紹如何采用準均勻B逼近算法對截面曲線數據進行擬合[6]。 設截面曲線數據點列為 Pi，i=0，1，…，m，擬合后的B樣條曲線為

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

1.2 基于曲率特征的采樣規劃算法

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

圖1 質點系Fig.1 System of particles

上式可進一步寫成一般的力矩平衡方程形式：

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

1.3 矩形拓撲網格數據點陣的生成

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

當ci上所有點找到對應點之后，對曲線ci進行細分。

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

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

即使相鄰曲線的曲率變化差異很大，也可以實現采樣點的細分，如圖2所示。按上述方法處理所有曲線，可獲得矩形網格數據點陣。

2 應用實例

為了驗證改進算法的可靠性，即使兩兩掃描曲線間曲率變化差異很大，也可以實現曲線間采樣點的細分，本章把自適應重采樣算法應用于小熊蝴蝶結測量數據的建模。小熊蝴蝶結測量數據如圖3所示。

首先用B樣條曲線逼近每條截面曲線上的測量數據，以其中一條截面曲線為例，該截面線的測量點如圖4所示，其相對應的逼近曲線和截面線上的采樣點如圖5所示。

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

圖3 蝴蝶結模型測量數據Fig.3 Measurement data of bowknot modle

圖4 截面線測點Fig.4 Measurement point of section line

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

經曲線間節點匹配、細分生成矩形拓撲網格數據如圖6所示。

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

3 結束語

圖6 匹配細分后的矩形拓撲網格數據Fig.6 Rectangular topology grid data after matching and segmentation

圖7 網格化模型Fig.7 Griddized model

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

[1]金濤，童水光.逆向工程技術[M].北京：機械工業出版社，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的散亂數據點自由曲面重構[J].計算機輔助設計與圖形學學報，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]來新民，黃田，林忠欽.數學模型已知的自由曲面數字化自適應采樣[J].計算機輔助設計與圖形學學報，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]施法中.計算機輔助幾何設計與非均勻有理B樣條[M].北京：北京航天航空大學出版社，1994.

[7]劉志剛.逆向工程中線結構光視覺傳感器與CMM集成測量技術研究[D].西安:西安交通大學，2000.