一種點(diǎn)云數(shù)據(jù)曲線光順處理算法*

王 可，唐忠輝，孫興偉

(沈陽(yáng)工業(yè)大學(xué) 機(jī)械工程學(xué)院，沈陽(yáng) 110870)

0 引言

隨著科學(xué)技術(shù)的進(jìn)步，尤其是計(jì)算機(jī)輔助工程在產(chǎn)品開(kāi)發(fā)中的廣泛運(yùn)用，人們對(duì)產(chǎn)品的性能與外觀要求日益提升，而產(chǎn)品的光順程度是其中的一個(gè)重要影響因素，因此，產(chǎn)品表面的光順性就顯得尤為重要。光順處理也一直是CAGD 中的一個(gè)研究熱點(diǎn)，它在汽車、船舶、航空、航天等眾多領(lǐng)域應(yīng)用越來(lái)越廣泛，對(duì)它的研究具有重要的理論及應(yīng)用價(jià)值［1］。從產(chǎn)品制造加工的角度來(lái)說(shuō)，設(shè)計(jì)產(chǎn)品的幾何光順性不好會(huì)導(dǎo)致加工困難，生產(chǎn)效率低下，從而使加工成本提高。除此之外，曲線曲面的光順性對(duì)產(chǎn)品的物理性能、產(chǎn)品的質(zhì)量和產(chǎn)品的外觀等都將產(chǎn)生重要的影響。所以，曲線曲面的光順處理一直受到了工業(yè)界、學(xué)術(shù)界的廣泛關(guān)注。

近年光順擬合的研究較多，關(guān)于曲線的光順處理方法，總體上可分為兩類:整體光順?lè)ê途植抗忭樂(lè)ǎ?］。曲線的整體光順?lè)椒ǔＳ玫挠心芰糠?、小波法和最小二乘法?］?；诠忭樤砜煞譃榛诠?jié)點(diǎn)刪除、插入的光順;其中，最早最有影響力的光順?lè)椒ㄊ?987 年Farin［4］等提出的一種通過(guò)“節(jié)點(diǎn)消去與插入”的B 樣條曲線光順?lè)椒?，該方法的本質(zhì)是利用曲線的曲率圖進(jìn)行人工交互修改，以使曲率變化比較均勻，最終達(dá)到曲線光順的要求。

在眾多數(shù)據(jù)處理方法中，最小二乘法是其中一種較常用的數(shù)據(jù)擬合方法。但當(dāng)處理點(diǎn)云數(shù)據(jù)時(shí)，如果只采用一條曲線函數(shù)擬合點(diǎn)云數(shù)據(jù)，當(dāng)多項(xiàng)式階數(shù)太低，擬合精度達(dá)不到預(yù)定效果。要提高擬合精度和效果就需要提高擬合曲線階數(shù)，但階數(shù)太高又帶來(lái)計(jì)算上的復(fù)雜性和難操作性，甚至出現(xiàn)龍格現(xiàn)象，很難取得較好的擬合效果和精度。如果采取分段擬合，擬合后的曲線在分段處可能不連續(xù)。為了有效地解決上述問(wèn)題，本文提出了基于拉格朗日乘數(shù)法點(diǎn)云數(shù)據(jù)光順處理的方案。

1 數(shù)學(xué)模型的建立

在現(xiàn)代工業(yè)革命的進(jìn)程中，為了利用先進(jìn)制造技術(shù)與方法，需要通過(guò)一定處理，然后將實(shí)物模型轉(zhuǎn)化為CAD 模型，最后反求出該產(chǎn)品的數(shù)學(xué)模型，從而將產(chǎn)品實(shí)物轉(zhuǎn)化為產(chǎn)品數(shù)學(xué)模型，進(jìn)一步研究出同類的先進(jìn)產(chǎn)品的科學(xué)技術(shù)稱為“逆向工程”，又稱“反向工程”或者“反求工程”［5］。在將實(shí)物模型轉(zhuǎn)化為CAD 模型的過(guò)程中，為了保證反求出的產(chǎn)品模型盡可能接近產(chǎn)品實(shí)物，需要得到產(chǎn)品實(shí)物表面上的大量的離散點(diǎn)，這些離散點(diǎn)一般稱為點(diǎn)云數(shù)據(jù)［6］。由于原始數(shù)據(jù)龐大，因此，對(duì)數(shù)據(jù)曲線擬合往往不可以在全域上進(jìn)行擬合，而是分段多次在不同數(shù)據(jù)點(diǎn)上進(jìn)行擬合［7］。

定義:在分段曲線擬合中，進(jìn)行一次曲線擬合所包括的點(diǎn)數(shù)區(qū)間稱為窗口。

本文分段曲線擬合是在每一個(gè)窗口中進(jìn)行擬合，得到一條多項(xiàng)式擬合方程，輸出前兩個(gè)數(shù)據(jù)之間的擬合曲線，然后窗口向后移動(dòng)一個(gè)數(shù)據(jù)點(diǎn)，組成下一個(gè)擬合窗口再進(jìn)行下一次的擬合，一直擬合完最后一個(gè)窗口。如下圖1 是用M 個(gè)點(diǎn)為一個(gè)窗口去擬合N 對(duì)數(shù)據(jù)點(diǎn)，共有N－M +1 個(gè)窗口。

圖1 分段曲線擬合示意圖

設(shè)點(diǎn)云數(shù)據(jù)區(qū)間為［x1，xN］，設(shè)N 對(duì)型值點(diǎn)為(xj，yj)(j = 1，2，…，(N－1)，N)，每個(gè)窗口逼近多項(xiàng)式g(x):

其中:在窗口1 中是采取傳統(tǒng)意義上的最小二乘法擬合，即可求的擬合多項(xiàng)式g1(x)。

設(shè)在第k 個(gè)(k = 2，3，4，…，(N－M +1))窗口的多項(xiàng)式為:

式中:ak0，ak1，ak2，…，ak(n－1)，akn為待定系數(shù)。

為保證曲線在xk處，gk－1(x)過(guò)渡到gk(x)時(shí)曲線連續(xù)，要求前后兩段曲線在xk處的函數(shù)值相等，即要加入端點(diǎn)約束條件:

同時(shí)，為保證曲線在xk處，gi－1(x)過(guò)渡到gi(x)時(shí)曲線光順，要求前后兩段曲線在xk處的一階導(dǎo)數(shù)值也相等，即加入端點(diǎn)約束條件:

2 數(shù)學(xué)模型的求解

該數(shù)學(xué)模型是一個(gè)帶極值的約束問(wèn)題，本文采用拉格朗日乘數(shù)法［8］，將條件極值問(wèn)題轉(zhuǎn)化為無(wú)條件極值問(wèn)題來(lái)求解.以第k(k = 2，3，4，…，(N－M +1))個(gè)窗口為例，具體方法如下:

引入拉格朗日乘子λl(l = 1，2)，并設(shè)Hk=gk(xk)－ gk－1(xk)，Kk= g'k(xk)－ g'k－1(xk)，所以，模型的邊界約束條件為:

Hk= 0， Kk= 0

則拉格朗日函數(shù)為:

其中:xk＜xj＜xk+M－1。

為了使擬合后的曲線盡可能的逼近測(cè)量值，就必須拉格朗日函數(shù)值Q 最小，可以改變系數(shù)aki值的大小，為此令Q 對(duì)每一個(gè)系數(shù)求偏導(dǎo)數(shù)，并令其偏導(dǎo)數(shù)為零，即:

其中:Φf(x)= xf，f = (0，1，2，3，…，n)

寫(xiě)成矩陣的形式有:

其中:

其中

由以上矩陣方程即可求出拉格朗日函數(shù)中系數(shù)aki(i = 1，2，3…n)以及λl(l = 1，2)，從而可以得到數(shù)據(jù)點(diǎn)［k，k +1］之間擬合曲線，根據(jù)該方法依次求解，即可得到全域上的擬合曲線。

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

下面給出該算法在螺旋曲面測(cè)量光順問(wèn)題中的一個(gè)應(yīng)用實(shí)例。工程中在加工測(cè)量螺旋曲面截面廓形的時(shí)候，一般是用千分尺測(cè)量截面的大小徑，然后通過(guò)測(cè)量數(shù)據(jù)來(lái)設(shè)定數(shù)控機(jī)床的下一步刀補(bǔ)，該測(cè)量方法工作效率低且測(cè)出的數(shù)據(jù)精度不是很理想。本文采用激光測(cè)量連續(xù)測(cè)量螺旋曲面截面廓形上的點(diǎn)，由測(cè)量值組成整個(gè)截面廓形，如圖2。

圖2 測(cè)量值組成的截面廓形

將圖2 中左上方的小方框位置進(jìn)行局部放大后如圖3 所示，可以看到因測(cè)量?jī)x器的誤差、加工時(shí)工件的振動(dòng)以及工件表面刀花等因素的影響，測(cè)得的點(diǎn)云數(shù)據(jù)是一條不光順的封閉曲線，因此，需要對(duì)測(cè)量點(diǎn)進(jìn)行光順處理。由于測(cè)量得到的數(shù)據(jù)是一組密集的點(diǎn)云數(shù)據(jù)(大徑10cm 左右的螺桿外輪廓測(cè)量2000 個(gè)數(shù)據(jù)點(diǎn))。用現(xiàn)有的方法無(wú)法有效地對(duì)其進(jìn)行光順。

圖3 原螺旋曲面廓形局部放大分布圖

由于測(cè)量所得螺旋曲面廓形是由測(cè)量值組成的封閉曲線，不能使用本文的光順?lè)椒?，要先將其表示成極坐標(biāo)的形式，即r = r(θ)，θ ∈[ ]0 360 ，如圖4 所示。

圖4 極坐標(biāo)下截面廓形

應(yīng)用本文提出的基于拉格朗日乘數(shù)法對(duì)點(diǎn)云數(shù)據(jù)光順處理的算法進(jìn)行光順。在計(jì)算機(jī)上編寫(xiě)相應(yīng)的算法程序，經(jīng)過(guò)多次試驗(yàn)，當(dāng)選取選取五點(diǎn)為一個(gè)窗口，二次多項(xiàng)式為擬合函數(shù)時(shí)，處理后數(shù)據(jù)效果最佳。處理后得到的光順后曲線局部放大圖，如圖5所示。

通過(guò)光順后曲線與原測(cè)量值的比較可以看出，光順后曲線連續(xù)，并且在原型值點(diǎn)組成的曲線局部出現(xiàn)了細(xì)微的波動(dòng)被本文光順?biāo)惴ㄋ忭?，并且曲線的一階導(dǎo)數(shù)全域上連續(xù)，使之成為連續(xù)的光順曲線，并且光順后的曲線在原曲線的型值點(diǎn)列波動(dòng)的中心范圍內(nèi)穿過(guò)，因此擬合曲線較合理。

圖5 曲線的光順效果

選取局部放大圖的50%的測(cè)量點(diǎn)作為計(jì)算樣本進(jìn)行數(shù)據(jù)分析，如表1 所示。從表1 可知:原測(cè)量值與經(jīng)本文算法光順后曲線上對(duì)應(yīng)的點(diǎn)比較，最大偏離誤差值不超過(guò)0.1mm，偏移幅度小于0.5%，因此擬合精度高。

表1 光順前后數(shù)據(jù)

(續(xù)表)

4 結(jié)論

本文針對(duì)目前點(diǎn)云數(shù)據(jù)光順?biāo)惴ù嬖诘膯?wèn)題，提出了一種基于拉格朗日乘數(shù)法對(duì)點(diǎn)云數(shù)據(jù)光順處理的算法。顯示該算法能很好保持曲線原有性質(zhì)的基礎(chǔ)上使曲線連續(xù)及一階導(dǎo)數(shù)全局連續(xù)，證明了處理后的曲線光順效果較好，同時(shí)避免了使用高次曲線擬合帶來(lái)的種種弊端。達(dá)到了對(duì)點(diǎn)云數(shù)據(jù)預(yù)期的光順效果。為逆向工程中的點(diǎn)云數(shù)據(jù)中曲線光順處理提供一種有效的數(shù)學(xué)算法。

［1］李道軍，許春香. 擬合曲線光順?lè)椒ǖ难芯浚跩］. 信息技術(shù)，2011:277－278.

［2］章虎冬. 參數(shù)三次樣條曲線的局部?jī)?yōu)化光順?biāo)惴ǎ跩］.西安郵電學(xué)院學(xué)報(bào)，2011，16(2):68－70.

［3］趙罡，王愛(ài)增，穆國(guó)旺. 基于小波的非均勻B 樣條曲線自動(dòng)光順?biāo)惴ǎ跩］. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22(11):1925－1931.

［4］Farin G，Hoschek J，Kin M S. Handbook of Computer Aided Geometric Design［M］. Amsterdam:North Holland，2002:121－125.

［5］趙宇明，張國(guó)忠，于哲峰. CATIA 軟件在汽車逆向設(shè)計(jì)點(diǎn)云處理技術(shù)中的應(yīng)用研究［J］. 機(jī)械設(shè)計(jì)與制造，2005(6):80－82.

［6］劉丹. 基于點(diǎn)云數(shù)據(jù)的曲線擬合［D］. 遼寧:遼寧工程技術(shù)大學(xué)，2009.

［7］張旭臣，盧全海. 基于分段二次樣條函數(shù)的水位流量關(guān)系曲線擬合方法研究［J］. 水文，2010，30(4):59－62.

［8］同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系. 高等數(shù)學(xué)(下冊(cè))第五版［M］. 北京:高等教育出版社，2006.