基于輪廓重心參數(shù)調(diào)整的Bezier曲線擬合方法

酈悅?cè)A，吳繼偉

基于輪廓重心參數(shù)調(diào)整的Bezier曲線擬合方法

酈悅?cè)A，吳繼偉

傳統(tǒng)的3次Bezier曲線擬合方法在擬合漢字輪廓曲線時(shí)，迭代次數(shù)多，效率較低。針對(duì)擬合的效率，設(shè)計(jì)了一種基于3次Bezier曲線的漢字曲線輪廓擬合新方法。該方法的核心是簡(jiǎn)單高效的參數(shù)迭代算法。在3次Bezier曲線控制點(diǎn)的求取方法上，采用最小二乘法擬合；在參數(shù)的優(yōu)化問(wèn)題上，用過(guò)型值點(diǎn)重心的直線與擬合曲線間的交點(diǎn)求解參數(shù)，迭代優(yōu)化參數(shù)取值。該迭代算法占用資源少，運(yùn)算量小，計(jì)算簡(jiǎn)便。實(shí)驗(yàn)結(jié)果表明，針對(duì)一般型值點(diǎn)和漢字輪廓特征點(diǎn)的曲線擬合，在相同精度要求下，該算法迭代次數(shù)少，收斂速度快，能達(dá)到更好的擬合效果。

Bezier曲線擬合；最小二乘法；型值點(diǎn)重心迭代；漢字曲線輪廓描述

0 引言

在圖形工程實(shí)踐中，經(jīng)常需要將由型值點(diǎn)用參數(shù)多項(xiàng)式曲線來(lái)逼近，從而達(dá)到容易造型和修改的目的。目前，型值點(diǎn)擬合的基本方法是采用3次Bezier曲線擬合。Bezier曲線以其優(yōu)良的性質(zhì)，在諸多形式的參數(shù)多項(xiàng)式曲線中獨(dú)樹(shù)一幟，一經(jīng)問(wèn)世，就受到工業(yè)界的重視和廣泛應(yīng)用。用Bezier曲線擬合型值點(diǎn)的算法，能使擬合后的曲線光順。文獻(xiàn)[1-3]提供了大量的實(shí)踐證明，這種方法是完全可行的。

目前，漢字曲線輪廓字形廣泛使用3次Bezier曲線描述。原因有二：一是Bezier曲線具有良好的直觀性和局部修改性，方便交互式地修改曲線的形狀；二是Bezier曲線與其它曲線一樣也具有仿射變換不變性，這使得對(duì)字形作任意放大和縮小變換時(shí)，曲線均能精確地描述字形輪廓。漢字曲線輪廓字庫(kù)連續(xù)性好，字形美觀而且變化豐富，縮放后可保證文字質(zhì)量，漢字曲線輪廓字庫(kù)需要較少的存儲(chǔ)空間，在工業(yè)界廣泛應(yīng)用[4-6]。

用Bezier曲線擬合型值點(diǎn)的傳統(tǒng)方法是參數(shù)型最小二乘法，這是當(dāng)前主要的擬合技術(shù)[7-12]。3次Bezier曲線C(t)的參數(shù)方程是公式（1）：

參數(shù)型最小二乘法擬合首先要得到參數(shù)t的取值。在首次擬合時(shí)，參數(shù)t的取值用累加弦長(zhǎng)法求解出。由于僅靠一次擬合的精度不能滿足要求，需要在前一次擬合的基礎(chǔ)上優(yōu)化參數(shù)t，以達(dá)到預(yù)期的精度要求。而參數(shù)的優(yōu)化方式影響到迭代次數(shù)和迭代精度。傳統(tǒng)的做法是找到擬合曲線上對(duì)應(yīng)于型值點(diǎn)距離最近的一點(diǎn)，以這一點(diǎn)的t值作為下一次迭代的參數(shù)，持續(xù)迭代過(guò)程，直至誤差精度滿足要求后迭代結(jié)束，這種方法為最短距離迭代算法。

最短距離迭代算法進(jìn)行曲線擬合時(shí)存在以下兩個(gè)問(wèn)題：

（1）參數(shù)的求解公式復(fù)雜，需要求解的參數(shù)多，占用資源，不夠快速，給算法的設(shè)計(jì)帶來(lái)難度，并且計(jì)算量大。

（2）用累加弦長(zhǎng)法首次求解參數(shù)t，欲達(dá)到目標(biāo)精度，收斂較慢，迭代次數(shù)較多。

針對(duì)以上各種算法的不足，本文提出了一種更為簡(jiǎn)單的迭代方法，使用三次Bezier曲線擬合型值點(diǎn)，基于型值點(diǎn)輪廓重心的參數(shù)進(jìn)行迭代，達(dá)到更好的擬合效果。通過(guò)實(shí)驗(yàn)試算，本文提出的方法應(yīng)用于漢字輪廓特征點(diǎn)的擬合問(wèn)題上，取得了理想的效果。

1 方法和技術(shù)

首先，假設(shè)型值點(diǎn)均位于起始點(diǎn)和終止點(diǎn)連線的同一側(cè)，在實(shí)際情況中，位置處于同一側(cè)的型值點(diǎn)總是可以通過(guò)分割型值點(diǎn)集得到。

先做如下的定義：

定義1相鄰的型值點(diǎn)兩兩間用線段連接，形成的多邊形叫型值點(diǎn)多邊形。

定義2型值點(diǎn)多邊形的重心坐標(biāo)叫型值點(diǎn)輪廓重心。

定義3相鄰的兩個(gè)型值點(diǎn)與型值點(diǎn)重心構(gòu)成的三角形的面積為型值點(diǎn)權(quán)值如公式（2）：

1.1 型值點(diǎn)輪廓重心的計(jì)算

（1）將型值點(diǎn)多邊形分割成三角形

連接起始點(diǎn)Q0和終止點(diǎn)Qn，得到一條線段。過(guò)型值點(diǎn)做線段的垂線，垂足分別為，并求解垂足的坐標(biāo)。連接相應(yīng)的線段，這樣就把具有n個(gè)頂點(diǎn)的多邊形分割為個(gè)個(gè)三角形。

（2）對(duì)分割后的每個(gè)三角形，計(jì)算它們相應(yīng)的的重心坐標(biāo)和面積。

三角形的面積可由公式（4）求得公式（4）：

圖1 型值點(diǎn)多邊形重心

如圖1所示，在得到每一塊三角形的重心和面積后，計(jì)算多邊形的重心。由公式（5）得到多邊形的重心坐標(biāo)如公式（5）：

1.2 基于最小二乘法的三次Bezier 曲線擬合

三次Bezier曲線由4個(gè)點(diǎn)控制點(diǎn)來(lái)描述，0P是起點(diǎn)，1P是第一控制點(diǎn)，2P是第二控制點(diǎn)，3P是終點(diǎn)。其中起點(diǎn)坐標(biāo)，終點(diǎn)的坐標(biāo)是待定點(diǎn)的坐標(biāo)是。

（1）記Ci是擬合曲線上對(duì)應(yīng)于參數(shù)ti的點(diǎn)如公式（6）：

（2）用最小二乘法擬合，要求擬合曲線上的點(diǎn)Ci與型值點(diǎn)之間的距離的平方差之和達(dá)到極小。即公式（7）：

1.3 參數(shù)ti的優(yōu)化問(wèn)題

進(jìn)行最小二乘法擬合時(shí)，必須先確定參數(shù)ti的值。首次擬合時(shí)，傳統(tǒng)方法采用累加弦長(zhǎng)法，將型值點(diǎn)間的弦長(zhǎng)累加作為參數(shù)ti。本文用型值點(diǎn)權(quán)值wi來(lái)確定參數(shù)ti的值。相比于累加弦長(zhǎng)法，雖然按權(quán)值確定參數(shù)ti的初始誤差較大，但迭代收斂速度快，誤差能很快收斂，最終效果優(yōu)于累加弦長(zhǎng)法。

得到參數(shù)ti的值后，用最小二乘法進(jìn)行第一次擬合。之所以要先估計(jì)參數(shù)ti，是因?yàn)樵谑状螖M合給定的輪廓段的型值點(diǎn)時(shí)，沒(méi)有得到型值點(diǎn)的擬合曲線，無(wú)法求出曲線弧長(zhǎng)。因此第一次擬合時(shí)，按型值點(diǎn)權(quán)值求出參數(shù)ti的值，再用參數(shù)型最小二乘法去擬合給定型值點(diǎn)，這種方法是合理的，但由于是估計(jì)值，顯然不夠精確，因此最短距離法和文章方法在首次擬合時(shí)都不能得到較好的擬合效果。僅僅一次擬合效果不理想，所以有必要優(yōu)化參數(shù)ti的取值。在參數(shù)ti的取值的優(yōu)化技術(shù)上，傳統(tǒng)的做法是求解出型值點(diǎn)與擬合曲線距離最近的點(diǎn)的ti值，作為下一次迭代的參數(shù)。本文提出了一種基于型值點(diǎn)重心的參數(shù)ti優(yōu)化方法。此方法的優(yōu)點(diǎn)是計(jì)算量小，擬合速度快，擬合誤差小。

已知求得的Bezier曲線C(t)，(0≤t≤1)，離散型值點(diǎn)列如公式（9）：

3 總結(jié)

本文提出了基于型值點(diǎn)重心的三次Bezier曲線擬合算法。算法基于型值點(diǎn)重心計(jì)算參數(shù)，迭代更新控制點(diǎn)的位置。算法相當(dāng)簡(jiǎn)單并且十分有效。本文介紹的擬合算法，經(jīng)過(guò)試算驗(yàn)證和軟件模擬，這些方法在理論上是可行的。

基于傳統(tǒng)的最短距離的迭代方法計(jì)算量大、計(jì)算復(fù)雜。在新算法中， 各個(gè)型值點(diǎn)與重心之間的直線斜率都只進(jìn)行一次計(jì)算， 計(jì)算量小， 對(duì)于點(diǎn)數(shù)龐大的型值點(diǎn)集， 減少了計(jì)算的繁瑣， 避免了大量求解高次多項(xiàng)式根的問(wèn)題， 減少了空間數(shù)據(jù)的存儲(chǔ)量， 節(jié)省了計(jì)算時(shí)間， 具有一定的實(shí)用價(jià)值。

在漢字曲線輪廓特征點(diǎn)的擬合問(wèn)題上，本文方法得到了很好的效果。采用本方法擬合漢字曲線輪廓，可以達(dá)到均方誤差和迭代次數(shù)上的更優(yōu)選擇，是一種理想的解決辦法。展示的結(jié)果也表明算法能產(chǎn)生優(yōu)化的擬合曲線，算法在漢字曲線輪廓擬合上有著廣闊的應(yīng)用前景。但是在接近直線分布型值點(diǎn)上的擬合性能不好，本算法暫時(shí)還不能應(yīng)用于直線分布的型值點(diǎn)擬合。

[1] Deepak C. Srivastava, VipulRastogi, RajitGhosh. A rapid Bézier curve method for shape analysis and point representation of asymmetric folds[J]. Journal of Structural Geology, 2010 (32):685-692.

[2] M.Sarfraz , A.Masood. Capturing outlines of planar images using Bezier cubics[J] . Computers& Graphics, 2007 (31):719–729.

[3] AsifMasood, Muhammad Sarfraz. Capturing outlines of 2D objects with Bézier cubic approximation[J]. Image and Vision Computing, 2009 (27):704–712.

[4] 李培培. 曲線造型中關(guān)于擬合、參數(shù)化及形狀優(yōu)化問(wèn)題的研究[D].山東大學(xué),2012.

[5] 陳登梅. 曲線字庫(kù)自動(dòng)生成方法的研究[D].山東大學(xué),2007.

[6] 嚴(yán)紅娟. 女書(shū)曲線輪廓字形自動(dòng)生成方法研究與實(shí)現(xiàn)[D].中南民族大學(xué),2013.

[7] 張明星. 廣義Bézier曲線與B樣條曲線的研究[D].中南大學(xué),2013.

[8] 楊林英. Bézier曲線的拼接及擴(kuò)展[D].西北師范大學(xué),2013.

[9] 張嫻. 基于曲率分析的三次B-spline曲線保形采樣方法研究[D].西北農(nóng)林科技大學(xué),2012.

[10] 張超,王文靜. 一種改進(jìn)的折線轉(zhuǎn)分段Bezier曲線的擬合方法[J]. 測(cè)繪通報(bào),2011,12:72- 74.

[11] 王家潤(rùn),趙南松,華文元,等. 分段連續(xù)三次Bezier曲線控制點(diǎn)的構(gòu)造算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2010,22:190-193.

[12] 張嫻,張志毅,田素壘,等. 基于曲率分析的三次Bezier曲線采樣方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用,2013,05:160-162+253.

A Bezier Curve Fitting Method Based on Parameter Agustment of Contour Center

Li Yuehua, Wu Jiwei
(Department of control science and Engineering, Tongji University, Shanghai 201804,China)

When Fitting Chinese outline outline curves, the traditional cubic Bezier curve fit method is short fortoo many iterations and low efficiency. In response to the curve fit efficiency, the paper designs a new algorithmtofit Chinese outline fonts basedoncubic Bezier curve. The key of this method is a parameter iterative algorithm which is simple and efficient. Least-squares solution is applied to get the control points of cubic Bezier curves. In terms ofparameters optimization, intersections of lines that cross the contour center and fitting curve are used to calculate parameter through iterative optimization. Compared with traditional curve fitting method, this method has lowcost incalculation and is easy to compute. From the experiments with common data points and Chinese outline fonts, it is found that the results ofthe proposed method is better with less iterationsand faster in the speed of convergence rate under the same precision condition.

Bezier Curve; Least-Squares Solution; Contour Center Iteration; Chinese Outline Fonts

TP311.13

A

2014.11.12）

1007-757X(2015)01-0017-05

上海市科委科技攻關(guān)項(xiàng)目（11dz1505202）

酈悅?cè)A（1989-），男，同濟(jì)大學(xué)，控制科學(xué)與工程系，碩士研究生，研究方向：計(jì)算機(jī)軟件及圖像處理，上海，201801

吳繼偉（1974-），男，同濟(jì)大學(xué)，控制科學(xué)與工程系，講師，研究方向：圖像處理及模式識(shí)別，數(shù)據(jù)挖掘，上海，201801