一種一階連續(xù)分段曲線擬合方法*

段振云，王　寧，趙文輝，李　寧

(1.沈陽(yáng)工業(yè)大學(xué) 機(jī)械工程學(xué)院，沈陽(yáng)　110870；2.北方重工集團(tuán)有限公司 輸送設(shè)備分公司，沈陽(yáng)　110141)

?

一種一階連續(xù)分段曲線擬合方法*

段振云1，王寧1，趙文輝1，李寧2

(1.沈陽(yáng)工業(yè)大學(xué) 機(jī)械工程學(xué)院，沈陽(yáng)110870；2.北方重工集團(tuán)有限公司 輸送設(shè)備分公司，沈陽(yáng)110141)

摘要：分段曲線擬合是一種常用的數(shù)據(jù)處理方法，但在分段點(diǎn)處擬合曲線往往不能滿足連續(xù)性要求。提出一種一階連續(xù)分段曲線擬合方法，即在確定每個(gè)擬合區(qū)間的原始數(shù)據(jù)個(gè)數(shù)之后，采用最小二乘法進(jìn)行擬合，并在分段點(diǎn)處重復(fù)使用前一段末端數(shù)據(jù)，且對(duì)每段數(shù)據(jù)的起始點(diǎn)進(jìn)行加權(quán)，使分段擬合曲線在分段點(diǎn)處更加逼近，減小擬合誤差，根據(jù)擬合曲線重合部分的端點(diǎn)信息，采用三次Hermite插值的方法構(gòu)造一條連接分段擬合曲線的插值曲線，使分段點(diǎn)處滿足一階連續(xù)，逐段處理，得到一條全局光滑連續(xù)的擬合曲線。將一階連續(xù)分段曲線擬合方法應(yīng)用于處理齒輪視覺(jué)檢測(cè)中提取的齒廓邊緣數(shù)據(jù)，證明擬合曲線在分段點(diǎn)處一階連續(xù)，且擬合誤差減小，易于編程實(shí)現(xiàn)。

關(guān)鍵詞：分段擬合；分段點(diǎn)；加權(quán)；Hermite插值；一階連續(xù)

0引言

在工程實(shí)踐和科學(xué)實(shí)驗(yàn)中，常常需要對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行曲線擬合。例如應(yīng)用機(jī)器視覺(jué)技術(shù)對(duì)齒輪進(jìn)行測(cè)量時(shí)，根據(jù)邊緣檢測(cè)算法提取的齒輪邊緣信息是一系列離散的數(shù)據(jù)點(diǎn)。為了提高邊緣的測(cè)量精度，進(jìn)一步降低隨機(jī)噪聲對(duì)邊緣定位精度的影響，需要對(duì)提取的邊緣點(diǎn)數(shù)據(jù)進(jìn)行曲線擬合。最小二乘法是解決曲線擬合問(wèn)題最常用的方法，根據(jù)最小均方差原則，可以有效得出最佳擬合函數(shù)[1]。

對(duì)于具有多個(gè)顯著局部特征的數(shù)據(jù)，使用一個(gè)擬合函數(shù)來(lái)描述難以取得較好的擬合精度和效果，一般采用分段擬合的方法，在每段區(qū)間上進(jìn)行局部最小二乘法擬合。然而，擬合函數(shù)在區(qū)間分段點(diǎn)上不一定連續(xù)，在相鄰區(qū)間邊界附近的擬合效果不理想[2-3]。

目前用于解決分段擬合曲線連續(xù)性問(wèn)題的方法均存在局限性，有的是在選擇分段點(diǎn)時(shí)，以每段擬合數(shù)據(jù)的最后一個(gè)點(diǎn)作為下一段擬合數(shù)據(jù)的起始點(diǎn)，這樣并不能保證擬合曲線的連續(xù)性[4]；有的只限于兩個(gè)分段區(qū)間，對(duì)于具有多個(gè)分段區(qū)間的情況則不能處理[5]；有的則是把全局連續(xù)性約束的分段擬合問(wèn)題轉(zhuǎn)化為帶等式約束的誤差最小化模型，通過(guò)拉格朗日乘數(shù)法推導(dǎo)出模型的最小二乘回歸系數(shù)，這種方法的缺陷是不具有局部性，當(dāng)分段數(shù)據(jù)中含有1個(gè)或多個(gè)誤差數(shù)據(jù)時(shí)，會(huì)對(duì)最終擬合函數(shù)產(chǎn)生一定的影響[6]。

為了解決上述問(wèn)題，提出一種一階連續(xù)分段曲線擬合方法，以數(shù)據(jù)加權(quán)和三次Hermite插值為基礎(chǔ)，對(duì)分段數(shù)據(jù)逐段進(jìn)行擬合，實(shí)現(xiàn)擬合曲線的一階連續(xù)性，減小擬合誤差。

1分段擬合曲線連續(xù)性條件

由于使用最小二乘法對(duì)數(shù)據(jù)進(jìn)行分段擬合可以更加準(zhǔn)確地反映出數(shù)據(jù)點(diǎn)的整體分布狀況，對(duì)于分段點(diǎn)處的數(shù)據(jù)進(jìn)行加權(quán)，可以使分段擬合曲線在區(qū)間分段點(diǎn)處增進(jìn)對(duì)數(shù)據(jù)點(diǎn)的逼近程度，減小分段點(diǎn)附近的擬合誤差，使用Hermite插值的端點(diǎn)條件可以使分段擬合曲線在區(qū)間分段點(diǎn)處具有一階連續(xù)性[7-9]，因此提出一種一階連續(xù)分段曲線擬合方法。

可用Beta約束定義分段擬合曲線的連續(xù)性，具體分析為：當(dāng)存在實(shí)數(shù)βi(i=1,2,···,n)，其中β1>0,使分段擬合曲線在分段點(diǎn)P的兩側(cè)導(dǎo)矢滿足由方程(1)給出的一組Beta約束時(shí)，則稱(chēng)分段擬合曲線在分段點(diǎn)處具有Gn連續(xù)性。

(1)

由以上定義可知，若方程(1)中第一個(gè)方程成立，則P點(diǎn)為相鄰分段擬合曲線的公共連接點(diǎn)，即有G0連續(xù)性。 若第二個(gè)方程也成立，即在分段點(diǎn)P處的一側(cè)切矢是另一側(cè)切矢的正數(shù)倍，表明相鄰分段擬合曲線在該點(diǎn)具有G1連續(xù)性[10]。一階連續(xù)分段曲線擬合算法用到的就是上述曲線的G0和G1連續(xù)性條件。

對(duì)于一組數(shù)據(jù)，首先對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分段，確定每次擬合所使用的原始數(shù)據(jù)點(diǎn)個(gè)數(shù)，并且前一段的最后一個(gè)數(shù)據(jù)點(diǎn)作為下一段的第一個(gè)數(shù)據(jù)點(diǎn)。分段完成之后，對(duì)第一段數(shù)據(jù)點(diǎn)進(jìn)行最小二乘法擬合，擬合之后按一定的弧長(zhǎng)將擬合曲線進(jìn)行離散，得到一系列的離散點(diǎn)。對(duì)于第二段數(shù)據(jù)，取第一段擬合曲線的末端幾個(gè)離散點(diǎn)和第二段原始數(shù)據(jù)共同構(gòu)成，為了使分段擬合曲線在分段點(diǎn)處更加逼近，將第二段數(shù)據(jù)的起始點(diǎn)進(jìn)行加權(quán)處理，即重復(fù)使用起始點(diǎn)多次，然后再進(jìn)行最小二乘法曲線擬合，但這樣處理之后仍然存在分段點(diǎn)處不連續(xù)的問(wèn)題，因此將第二段擬合曲線也進(jìn)行離散，使用兩分段擬合曲線重合部分的端點(diǎn)信息，利用G0和G1連續(xù)性條件，進(jìn)行三次Hermite插值，減小擬合曲線在分段點(diǎn)附近的偏離量，實(shí)現(xiàn)分段擬合曲線在分段點(diǎn)處的一階連續(xù)，以此類(lèi)推，逐段進(jìn)行分段擬合和離散，并對(duì)數(shù)據(jù)進(jìn)行加權(quán)處理，以插值曲線代替相鄰擬合曲線的重合部分，使分段擬合曲線之間光滑連接，得到一條全局光滑連續(xù)的分段最小二乘法擬合曲線。

2一階連續(xù)分段曲線擬合方法

已知數(shù)據(jù)可以表示為(xi,yi)，i=1,2,3…n，采用一階連續(xù)分段曲線擬合方法對(duì)數(shù)據(jù)進(jìn)行處理。首先根據(jù)數(shù)據(jù)的分布特點(diǎn)，確定每段擬合曲線所用的原始數(shù)據(jù)個(gè)數(shù)為q1。按以下步驟對(duì)數(shù)據(jù)進(jìn)行分段擬合。

(1)擬合函數(shù)一般為多項(xiàng)式函數(shù)，在一定范圍內(nèi)，連續(xù)函數(shù)可用多項(xiàng)式任意逼近，因此取第一段擬合數(shù)據(jù)為(xi,yi)，i=1,2,3…q1確定擬合曲線的表達(dá)式f1(x)的形式為：

(2)

(2)將擬合后的曲線進(jìn)行離散，若曲線的表達(dá)式為f1(x)，設(shè)定離散弧長(zhǎng)為s，則對(duì)于擬合曲線f1(x)，以(x1,f1(x1))為起始點(diǎn)進(jìn)行離散，得到離散點(diǎn)(xl1,yl1)，l1=1,2,3…n1。

(4)同理，對(duì)于擬合曲線f2(x)，以(xn1-4,f2(xn1-4))為起始點(diǎn)進(jìn)行離散，得到離散點(diǎn)(xl2,yl2)，l2=1,2,3…n2。

(5)對(duì)于得到的離散點(diǎn)數(shù)據(jù)(xl1,yl1)，l1=1,2,3…n1和(xl2,yl2)，l2=1,2,3…n2，其中(xl1,yl1)，l1=n1-4,n1-3…n1和(xl2,yl2)，l2=1,2,3…5是兩段擬合曲線的重合部分，因此將這段數(shù)據(jù)用插值曲線表示，實(shí)現(xiàn)兩分段擬合曲線的一階連續(xù)。以(xn1-3,yn1-3)和(x4,y4)為插值曲線的兩個(gè)端點(diǎn)，確定兩分段擬合曲線連接部分插值曲線的形式為Q=α1x3+α2x2+α3x+α4，則其應(yīng)當(dāng)滿足端點(diǎn)條件(即端點(diǎn)位置、端點(diǎn)的單位切向量)，記

H(xj)=yj,H′(xj)=mj(j=0,1)

(3)

可以證明，滿足插值條件(3)的三次Hermite插值函數(shù)是存在且唯一的[11]。

具體約束條件為：

(4)

通過(guò)約束條件(4)，求出插值曲線的系數(shù)α1、α2、α3、α4，由于插值曲線在端點(diǎn)處一階連續(xù)，因此可以實(shí)現(xiàn)兩分段擬合曲線的光滑連接。

按照上述步驟，逐段進(jìn)行處理，可以得到一條整體較為光滑且與所給數(shù)據(jù)點(diǎn)整體走勢(shì)較為相符的連續(xù)曲線。

3實(shí)驗(yàn)分析

圖1　數(shù)據(jù)樣本點(diǎn)

圖2　獨(dú)立曲線擬合

顯然，與圖2a相比，采用一階連續(xù)分段曲線擬合方法所得的擬合曲線更加符合實(shí)際數(shù)據(jù)的連續(xù)性變化趨勢(shì)，且沒(méi)有帶入畸變，保證擬合曲線形狀的正確性。通過(guò)圖2b和圖3b的誤差曲線，可以看出采用一階連續(xù)分段曲線擬合方法比獨(dú)立分段曲線擬合方法擬合誤差小，在分段點(diǎn)處效果尤為突出，并且誤差波動(dòng)比獨(dú)立分段曲線擬合方法波動(dòng)小，擬合精度較高。

在應(yīng)用機(jī)器視覺(jué)技術(shù)測(cè)量齒輪時(shí)，通過(guò)邊緣檢測(cè)算法提取齒廓邊緣坐標(biāo)點(diǎn)信息，其分布情況如圖4a所示，為了更好地說(shuō)明一階連續(xù)分段曲線擬合方法的實(shí)用性，取局部邊緣坐標(biāo)點(diǎn)，如圖4b所示，分別進(jìn)行分段獨(dú)立曲線擬合和一階連續(xù)分段曲線擬合方法擬合。數(shù)據(jù)點(diǎn)為45個(gè)，將該邊緣分為3段，每段使用原始數(shù)據(jù)15個(gè)，由于齒輪理論齒廓為漸開(kāi)線，因此每個(gè)區(qū)間均采用三次函數(shù)進(jìn)行擬合。圖5為采用獨(dú)立分段曲線擬合方法擬合，擬合曲線在分段點(diǎn)處的跳躍量為0.23像素，曲線不連續(xù)，這樣會(huì)對(duì)齒輪測(cè)量造成一定的誤差；圖6為采用一階連續(xù)分段曲線擬合方法擬合，擬合曲線在分段點(diǎn)處具有連續(xù)性，可以提高齒輪測(cè)量的精度。

圖3　一階連續(xù)分段曲線擬合方法

圖4　齒輪邊緣坐標(biāo)點(diǎn)

圖5　獨(dú)立曲線擬合

圖6　一階連續(xù)分段曲線擬合方法

4結(jié)論

針對(duì)分段曲線擬合時(shí)，分段點(diǎn)處不能滿足連續(xù)性的問(wèn)題，提出一種一階連續(xù)分段曲線擬合方法，通過(guò)對(duì)起始點(diǎn)數(shù)據(jù)加權(quán)，并利用重合曲線的端點(diǎn)信息，構(gòu)造一條連接分段擬合曲線的插值曲線，保證擬合曲線在分段點(diǎn)處具有連續(xù)性。實(shí)驗(yàn)證明，使用一階連續(xù)分段曲線擬合方法進(jìn)行曲線擬合時(shí)，可以保證擬合曲線在分段點(diǎn)處一階連續(xù)，并且可以減小曲線擬合的誤差，其效果在分段點(diǎn)處尤為明顯，逐段對(duì)數(shù)據(jù)進(jìn)行處理，可以得到一條全局光滑連續(xù)的擬合曲線，避免擬合曲線在分段點(diǎn)處的二義性，另外，本文方法易于編程實(shí)現(xiàn)，可以用于處理實(shí)驗(yàn)數(shù)據(jù)。

[參考文獻(xiàn)]

[1] 李延芳. 基于協(xié)方差矩陣的輪廓曲線擬合算法研究[J]. 機(jī)械設(shè)計(jì)與制造, 2010(5):58-60.

[2] 王可, 唐忠輝, 孫興偉. 一種點(diǎn)云數(shù)據(jù)曲線光順處理算法[J].組合機(jī)床與自動(dòng)化加工技術(shù), 2013(2):64-69.

[3] Grama L, Rusu C. Phase approximation by divide-and-conquer piecewise linear fitting of gain[J]. International Symposium on Signals, Circuits and Systems, 2009: 1-4.

[4] 蔡山,張浩,陳洪輝,等. 基于最小二乘法的分段三次曲線擬合方法研究[J]. 科學(xué)技術(shù)與工程,2007,7(3):352-355.

[5] 劉曉莉,陳春梅.基于最小二乘原理的分段曲線擬合法[J].伊犁教育學(xué)院學(xué)報(bào), 2004,17(3): 132-134.

[6] 侯超鈞,曾艷姍,吳東慶,等.全局連續(xù)的分段最小二乘曲線擬合方法[J]. 重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2011, 28( 6): 44-48.

[7] 劉元朋,張定華,桂元坤,等. 用帶約束的最小二乘法擬合平面圓曲線[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2004,16(10):1382-1385.

[8] 張龍飛, 檀結(jié)慶. 局部插值的H-Bezier曲線分段光順擬合[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,34(10):1570-1575.

[9] Ren-Hong Wang, Jing-Xin Wang.The poisedness of interpolation problem for splines[J]. Applied Numerical Mathematics, 2005(54):95-103.

[10] 李思, 高健. G1連續(xù)的封閉非均勻B樣條曲線迭代算法[J]. 機(jī)械設(shè)計(jì)與制造, 2014(2):225-228.

[11] 彭愛(ài)清. 基于幾何Hermite插值的曲線光順研究[D]. 合肥:合肥工業(yè)大學(xué),2012.

(編輯趙蓉)

Method of First-order Continuous Piecewise Curve-fitting

DUAN Zhen-yun1，WANG Ning1，ZHAO Wen-hui1，LI Ning2

(1. School of Mechanical Engineering, Shenyang University of Technology, Shenyang 110870,China;2. Transportation Eequipment Branch, Northern Heavy Industries Group Co., Ltd, Shenyang 110141,China)

Abstract：Piecewise curve-fitting is a commonly used processing method of data, but at sub-point fitting curve often does not meet the requirement for continuity.This paper present a method of first-order continuous piecewise curve-fitting. Firstly, The method determining the number of original data in each fitting interval, using piecewise curve-fitting to process data, and reusing data at the end of the previous period in the subsection point, weighting the starting point of each piece of data, which can make a piecewise fitting curve in the subsection point more approaching, and reduce the fitting error, according to the fitting curve overlapping part of the endpoint information, utilizing cubic Hermite interpolation to structure a interpolation curve that links the two piecewise fitting curves, making sub-point satisfy the first-order continuous, piecewise processing, getting a global smooth continuous fitting curve. The method of first-order continuous piecewise curve fitting is applied to process extracted tooth profile edge data in gear vision inspection, which proved that the fitting curve in the subsection point is first-order continuous, and fitting error is reduced, also it is easy to program.

Key words：piecewise curve-fitting; sub-point; weighting; Hermite interpolation; first-order continuous

文章編號(hào)：1001-2265(2016)05-0029-03

DOI:10.13462/j.cnki.mmtamt.2016.05.008

收稿日期：2015-06-28

*基金項(xiàng)目：十二五國(guó)家科技支撐計(jì)劃(2014BAF08B01)

作者簡(jiǎn)介：段振云(1971—)，男，河南新鄉(xiāng)人，沈陽(yáng)工業(yè)大學(xué)教授，博士生導(dǎo)師，博士，研究方向?yàn)閺?fù)雜曲面加工技術(shù)、視覺(jué)檢測(cè)，(E-mail)13604045543@139.com；通訊作者：王寧(1991—)，女，遼寧大連人，沈陽(yáng)工業(yè)大學(xué)博士研究生，研究方向?yàn)辇X輪視覺(jué)檢測(cè)，(E-mail)wangningcom@126.com。

中圖分類(lèi)號(hào)：TH161;TG506

文獻(xiàn)標(biāo)識(shí)碼：A