一種一階連續分段曲線擬合方法*

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

(1.沈陽工業大學 機械工程學院，沈陽　110870；2.北方重工集團有限公司 輸送設備分公司，沈陽　110141)

?

一種一階連續分段曲線擬合方法*

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

(1.沈陽工業大學 機械工程學院，沈陽110870；2.北方重工集團有限公司 輸送設備分公司，沈陽110141)

摘要：分段曲線擬合是一種常用的數據處理方法，但在分段點處擬合曲線往往不能滿足連續性要求。提出一種一階連續分段曲線擬合方法，即在確定每個擬合區間的原始數據個數之后，采用最小二乘法進行擬合，并在分段點處重復使用前一段末端數據，且對每段數據的起始點進行加權，使分段擬合曲線在分段點處更加逼近，減小擬合誤差，根據擬合曲線重合部分的端點信息，采用三次Hermite插值的方法構造一條連接分段擬合曲線的插值曲線，使分段點處滿足一階連續，逐段處理，得到一條全局光滑連續的擬合曲線。將一階連續分段曲線擬合方法應用于處理齒輪視覺檢測中提取的齒廓邊緣數據，證明擬合曲線在分段點處一階連續，且擬合誤差減小，易于編程實現。

關鍵詞：分段擬合；分段點；加權；Hermite插值；一階連續

0引言

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

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

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

為了解決上述問題，提出一種一階連續分段曲線擬合方法，以數據加權和三次Hermite插值為基礎，對分段數據逐段進行擬合，實現擬合曲線的一階連續性，減小擬合誤差。

1分段擬合曲線連續性條件

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

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

(1)

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

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

2一階連續分段曲線擬合方法

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

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

(2)

(2)將擬合后的曲線進行離散，若曲線的表達式為f1(x)，設定離散弧長為s，則對于擬合曲線f1(x)，以(x1,f1(x1))為起始點進行離散，得到離散點(xl1,yl1)，l1=1,2,3…n1。

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

(5)對于得到的離散點數據(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是兩段擬合曲線的重合部分，因此將這段數據用插值曲線表示，實現兩分段擬合曲線的一階連續。以(xn1-3,yn1-3)和(x4,y4)為插值曲線的兩個端點，確定兩分段擬合曲線連接部分插值曲線的形式為Q=α1x3+α2x2+α3x+α4，則其應當滿足端點條件(即端點位置、端點的單位切向量)，記

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

(3)

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

具體約束條件為：

(4)

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

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

3實驗分析

圖1　數據樣本點

圖2　獨立曲線擬合

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

在應用機器視覺技術測量齒輪時，通過邊緣檢測算法提取齒廓邊緣坐標點信息，其分布情況如圖4a所示，為了更好地說明一階連續分段曲線擬合方法的實用性，取局部邊緣坐標點，如圖4b所示，分別進行分段獨立曲線擬合和一階連續分段曲線擬合方法擬合。數據點為45個，將該邊緣分為3段，每段使用原始數據15個，由于齒輪理論齒廓為漸開線，因此每個區間均采用三次函數進行擬合。圖5為采用獨立分段曲線擬合方法擬合，擬合曲線在分段點處的跳躍量為0.23像素，曲線不連續，這樣會對齒輪測量造成一定的誤差；圖6為采用一階連續分段曲線擬合方法擬合，擬合曲線在分段點處具有連續性，可以提高齒輪測量的精度。

圖3　一階連續分段曲線擬合方法

圖4　齒輪邊緣坐標點

圖5　獨立曲線擬合

圖6　一階連續分段曲線擬合方法

4結論

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

[參考文獻]

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

[2] 王可, 唐忠輝, 孫興偉. 一種點云數據曲線光順處理算法[J].組合機床與自動化加工技術, 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]. 科學技術與工程,2007,7(3):352-355.

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

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

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

[8] 張龍飛, 檀結慶. 局部插值的H-Bezier曲線分段光順擬合[J]. 合肥工業大學學報(自然科學版),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連續的封閉非均勻B樣條曲線迭代算法[J]. 機械設計與制造, 2014(2):225-228.

[11] 彭愛清. 基于幾何Hermite插值的曲線光順研究[D]. 合肥:合肥工業大學,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

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

DOI:10.13462/j.cnki.mmtamt.2016.05.008

收稿日期：2015-06-28

*基金項目：十二五國家科技支撐計劃(2014BAF08B01)

作者簡介：段振云(1971—)，男，河南新鄉人，沈陽工業大學教授，博士生導師，博士，研究方向為復雜曲面加工技術、視覺檢測，(E-mail)13604045543@139.com；通訊作者：王寧(1991—)，女，遼寧大連人，沈陽工業大學博士研究生，研究方向為齒輪視覺檢測，(E-mail)wangningcom@126.com。

中圖分類號：TH161;TG506

文獻標識碼：A