基于貝賽爾曲線位圖矢量化方法的研究*

胡學(xué)峰，朱家明**，劉雅倩，朱 勇

（1.安徽財(cái)經(jīng)大學(xué)統(tǒng)計(jì)與應(yīng)用數(shù)學(xué)學(xué)院，安徽蚌埠233030；2.安徽財(cái)經(jīng)大學(xué)金融學(xué)院，安徽蚌埠233030）

基于貝賽爾曲線位圖矢量化方法的研究*

胡學(xué)峰1，朱家明1**，劉雅倩2，朱 勇1

（1.安徽財(cái)經(jīng)大學(xué)統(tǒng)計(jì)與應(yīng)用數(shù)學(xué)學(xué)院，安徽蚌埠233030；2.安徽財(cái)經(jīng)大學(xué)金融學(xué)院，安徽蚌埠233030）

針對(duì)簡(jiǎn)單圖案的邊界線條提取，以所給圖中的黑白圖案為切入點(diǎn)，綜合分析了圖案輪廓特征點(diǎn)的坐標(biāo)值數(shù)據(jù)，根據(jù)貝塞爾曲線的建立原理，筆者嘗試構(gòu)建了基于貝塞爾曲線的圖形邊界線條提取、圖形邊界線條提取修正和簡(jiǎn)單彩色圖形邊界線條提取等模型，運(yùn)用Excel進(jìn)行相應(yīng)數(shù)據(jù)處理，并使用Photoshop、Matlab等軟件提取出圖形的邊界線條，Opencv軟件對(duì)擬合的線條進(jìn)行了檢驗(yàn)。最后，將所求結(jié)果和實(shí)際相比較，發(fā)現(xiàn)得到的矢量邊緣線圖案很大程度上接近于現(xiàn)實(shí)圖案。

位圖；貝賽爾曲線；雙線性差值；誤差分析；極限替代法；Matlab7

矢量圖從本質(zhì)上只是使用曲線方程對(duì)圖形進(jìn)行的精確描述，在以像素為基本顯示單元的顯示器或打印機(jī)上是無(wú)法直接表現(xiàn)的。將矢量圖轉(zhuǎn)換成以像素點(diǎn)陣來(lái)表示的信息，再加以顯示或打印，這個(gè)過(guò)程稱之為柵格化。柵格化的逆過(guò)程相對(duì)比較困難。本文運(yùn)用matlab圖像技術(shù)提取出圖1中圖像輪廓點(diǎn)，并依照貝賽爾曲線對(duì)其進(jìn)行分類成n段間斷曲線進(jìn)行復(fù)原，再將這n段進(jìn)行拼接形成模擬出來(lái)的原圖形。最后將這種方法推廣，得到一種基于貝賽爾曲線的位圖反柵格化模型。

1 柵格化的位圖圖案的邊緣線的提取

1.1 研究思路

將問(wèn)題拆解成兩部分：第一，圖形邊緣線的提?。坏诙?，對(duì)提取的邊緣線矢量化。首先，通過(guò)matlab對(duì)題中已給定的圖形（見圖1）進(jìn)行輪廓特征點(diǎn)提取，得到輪廓特征點(diǎn)的坐標(biāo)位置之后，對(duì)這些特征點(diǎn)的位置進(jìn)行插值并擬合，其次，考慮到插值之后的圖像不夠圓滑，為了減小誤差，將圖像等分切割為四部分，然后利用貝塞爾曲線的思想，對(duì)已插值后的輪廓特征點(diǎn)分別進(jìn)行貝塞爾曲線的曲線矢量化，從而得到四個(gè)部分矢量化輪廓曲線圖，最后將四部分的曲線圖結(jié)合起來(lái)形成一個(gè)整體輪廓圖。

圖1 柵格化圖

1.2 數(shù)據(jù)處理

（1）去除噪點(diǎn)干擾

由于對(duì)于掃描后的圖像,其經(jīng)過(guò)柵格化之后圖片上存在許多噪點(diǎn),在矢量化的預(yù)處理階段,必須先將其剔除,以消除對(duì)矢量化的干擾。這里筆者利用photoshop對(duì)圖片進(jìn)行噪點(diǎn)剔除[2]。

（2）輪廓特征點(diǎn)坐標(biāo)值提取

用matlab程序分別提取出四組圖形(1)、(2)、(3)、(4)的輪廓特征點(diǎn)。

（3）圖像分割

將曲線分割成四個(gè)部分理論依據(jù)：第一，對(duì)整個(gè)圖形的輪廓特征點(diǎn)進(jìn)行擬合的話，數(shù)據(jù)過(guò)少，誤差太大，筆者采取將輪廓特征點(diǎn)連成的圖像分割成四個(gè)部分的辦法（見圖1）；第二，一條曲線可在任意點(diǎn)切割成兩條或任意多條子曲線，每一條子曲線仍是貝塞爾曲線；第三，一些看似簡(jiǎn)單的曲線（如圓）無(wú)法以貝塞爾曲線精確的描述，可以將其分成四個(gè)部分，當(dāng)每個(gè)內(nèi)部控制點(diǎn)對(duì)單位圓上的外部控制點(diǎn)水平或垂直的的距離為時(shí)，分成四段的貝塞爾曲線，可以小于千分之一的最大半徑誤差近似于圓，同理類推到一些不規(guī)則的封閉曲線當(dāng)中，將其切分為四個(gè)部分（如圖2）。

圖2 圖形輪廓特征點(diǎn)的散點(diǎn)圖

（4）輪廓特征點(diǎn)坐標(biāo)插值處理

由于提取的輪廓特征點(diǎn)可能過(guò)于稀少，導(dǎo)致重構(gòu)的輪廓失真，這里采取插值的辦法。處理輪廓特征點(diǎn)的流圖：

圖3 輪廓特征點(diǎn)插值處理流程圖

第一，光滑區(qū)域一維插值處理：對(duì)于很光滑區(qū)域，即沒有尖點(diǎn)的情況下采取一維插值法。這里筆者對(duì)切割的四塊圖片中的第（1）、（2）、（4）塊圖（見圖2）都使用了一維插值法。

第二，非光滑區(qū)域雙線性插值處理：雙線性插值可以有效地消除鋸齒現(xiàn)象,插值質(zhì)量高。這里筆者應(yīng)用雙線性插值的思想對(duì)圖像（3）（圖2）進(jìn)行類雙線性插值處理。見圖4。

圖4 圖像(3)邊緣非光滑區(qū)域雙線性處理流程圖

圖5 邊緣特征點(diǎn)補(bǔ)充圖

接下來(lái)進(jìn)行第一步：X方向的線性插值:

第二步：做Y方向的點(diǎn)P1和P2插值,由R1與R2計(jì)算P點(diǎn):

這樣對(duì)每?jī)蓚€(gè)點(diǎn)都做如上處理，用matlab編程輔助，可以對(duì)邊緣的非光滑區(qū)域做出很好的插值。

1.3 理論方法——基于貝塞爾曲線的圖形邊界線條提取理論

線性貝塞爾曲線給定點(diǎn)P0，P1，B(t)代表經(jīng)過(guò)t時(shí)間的坐標(biāo)軸位置，線性貝塞爾曲線只是一條兩點(diǎn)之間的直線。這條線由下式給出：

二次方貝塞爾曲線的路徑由給定點(diǎn)P0，P1，P2的函數(shù)B(t)追蹤：

則n階貝塞爾曲線可如下推斷。給定點(diǎn)P0，P1…Pn，其貝塞爾曲線即曲線的參數(shù)形為：

將這個(gè)n階的貝塞爾曲線作為筆者的理論模型。

1.4 結(jié)果的分析

利用上面求出的模型通過(guò)matlab軟件編程求出四塊圖形的分別擬合情況，如圖6。

將圖像雖然切割成四部分，但是四部分的像素點(diǎn)的坐標(biāo)還是不變的，所以根據(jù)坐標(biāo)再將這四塊擬合曲線組合在一起，形成如下的圖像邊緣線提取圖（圖7）。

圖6 圖形輪廓特征點(diǎn)擬合圖

圖7 圖案的邊界線條圖

2 位圖邊緣線的提取優(yōu)化和推廣

2.1 預(yù)處理與分析

因?yàn)樯衔闹羞M(jìn)行四部分切割之后發(fā)現(xiàn)原圖與擬合后的矢量曲線不能很好地進(jìn)行重合，考慮到在取點(diǎn)時(shí)由于對(duì)某些不是圓滑的點(diǎn)直接就進(jìn)行模擬，而貝塞爾曲線本身模擬出來(lái)的是一條曲線，這導(dǎo)致原圖出現(xiàn)棱角的地方會(huì)由于曲線擬合而出現(xiàn)棱角磨平，不符合原圖。

為此筆者用以下切割點(diǎn)的規(guī)則，即轉(zhuǎn)折點(diǎn)切割原則：

第一，根據(jù)已知的位圖文件判斷有哪些轉(zhuǎn)折點(diǎn)，并進(jìn)行標(biāo)記。

第二，對(duì)已讀出的輪廓點(diǎn)我們根據(jù)位圖文件以特殊的轉(zhuǎn)折點(diǎn)作為切割點(diǎn)，對(duì)由于噪點(diǎn)而產(chǎn)生的轉(zhuǎn)折點(diǎn)丟失給予補(bǔ)點(diǎn)，并以此為端點(diǎn)。

使用轉(zhuǎn)折點(diǎn)切割原則進(jìn)行輪廓點(diǎn)切割后，應(yīng)出現(xiàn)n組輪廓點(diǎn)，每組輪廓點(diǎn)的粗略連線應(yīng)該是一條光滑的圓弧，再利用貝塞爾曲線進(jìn)行擬合。

2.2 柵格化位圖圖案邊界線的提取方法修正

（1）數(shù)據(jù)預(yù)處理

①直線區(qū)域與曲線區(qū)域的檢測(cè):當(dāng)相鄰3點(diǎn)的斜率相等(直線,斜線)。其余情況用圓弧曲線區(qū)域。

②對(duì)于直線區(qū)域處理方法：由于直線區(qū)域的存在會(huì)使得提取的圖形邊界線線條過(guò)于粗糙生硬，并且會(huì)對(duì)下一步的曲線擬合造成麻煩，也會(huì)使得圖片失真，所以對(duì)于直線區(qū)域，要采取必要的處理。

當(dāng)相鄰3點(diǎn)的斜率相等(即為直線,斜線)時(shí)候，取以下兩種方法：

長(zhǎng)度約束的分段方法：即為在此直線區(qū)域上每隔一定距離取得一點(diǎn)作為分段點(diǎn),按序插入到直線區(qū)域兩端點(diǎn)之間即可。

坐標(biāo)微調(diào)法：于一個(gè)坐標(biāo)可能出現(xiàn)多個(gè)坐標(biāo)(如圖中的點(diǎn)有多個(gè))的情況，便需要對(duì)插值點(diǎn)的選取做一定微調(diào)，采取對(duì)于做修改后帶入，再進(jìn)行spline插值擬合。

③對(duì)于圓弧曲線區(qū)域處理辦法：處理方法采取前文中一樣的插值辦法。

(2)理論準(zhǔn)備

首先用matlab提取出該圖像的輪廓特征點(diǎn)位置，再對(duì)圖像輪廓線的依照轉(zhuǎn)折點(diǎn)重新切割成線段AB,BC,AC三種情況，見圖8。

圖8 圖像輪廓切割圖

仍然按照貝塞爾曲線擬合的辦法，得出曲線的方程擬合模型：

(3)位圖圖案邊界線的提取修正：

對(duì)于AC曲線進(jìn)行擬合的結(jié)果精確卻太復(fù)雜，所以繼續(xù)對(duì)AC段曲線進(jìn)行切割，切割成AB,BC,CD,DE,EF,AF六段，切割情況如下：

圖9 圖像輪廓再切割圖

圖10 圖像輪廓擬合曲線

對(duì)這五段曲線的輪廓特征點(diǎn)在進(jìn)行貝塞爾曲線擬合的基礎(chǔ)下，可分別用matlab進(jìn)行擬合并求解出AE、EF、DF、CD、BC、AB段相應(yīng)貝塞爾參數(shù)方程結(jié)果，并作出擬合圖（如圖10）。

由于采取的是貝塞爾函數(shù)擬合，而貝塞爾函數(shù)特征即為很多高次項(xiàng)之和，故結(jié)果雖然復(fù)雜，但是能夠精確擬合出曲線輪廓。

（4）位圖圖案邊界線的提取的檢驗(yàn)

①檢驗(yàn)思想

根據(jù)貝塞爾曲線的推理過(guò)程，其本身無(wú)法用一般方程進(jìn)行表示，則用參數(shù)方程：表示貝塞爾曲線。但參數(shù)方程本身無(wú)法利用公式

進(jìn)行方程擬合優(yōu)度的檢驗(yàn)，為此筆者提出極限替代法思想。

極限替代法：

圖11 值的模糊取值示意圖

②檢驗(yàn)結(jié)果

AE段擬合曲線R2=0.9431,擬合效果很好；EF段擬合曲線R2=0.9946擬合效果非常好；DF段擬合曲線R2=0.9921，擬合效果非常好；CD段擬合曲線R2=0.9796，擬合效果非常好；BC段擬合曲線R2=0.7572擬合效果較好；AB段擬合曲線R2=0.9898，擬合效果非常好。

綜上所有的曲線區(qū)域都通過(guò)了擬合優(yōu)度的檢驗(yàn)。這一點(diǎn)從圖9和圖10對(duì)比也可以看出。

3 結(jié)論

對(duì)于一般平面圖形，采用一般的線性擬合或者十次以內(nèi)的函數(shù)擬合能大概求出元圖形輪廓，但本文的貝茨擬合方法能夠較為準(zhǔn)確地運(yùn)用編程方法求出不具備簡(jiǎn)單變化規(guī)律的輪廓線，且擬合函數(shù)唯一，都是n次以內(nèi)的貝茨函數(shù)，可以在一定誤差范圍內(nèi)較為精確模擬出原曲線。

注釋及參考文獻(xiàn)：

[1]2014年第七屆“認(rèn)證杯”數(shù)學(xué)中國(guó)數(shù)學(xué)建模網(wǎng)絡(luò)挑戰(zhàn)賽B題[EB/OL].http://www.tzmcm.cn/.

[2]用ps技術(shù)處理圖片噪點(diǎn)：[EB/OL]http://jingyan.baidu.com/article/b907e627f170fb46e6891c5c.html.

[3]嚴(yán)蘭蘭,宋來(lái)忠,李軍成.有理Bezier曲線的拼接[J].三峽大學(xué)報(bào)（自然科學(xué)版）,2005,27(5):469-471.

[4]姜啟源等.數(shù)學(xué)模型[M].北京:高等教育出版社,2003：440.

[5]楊桂元,黃己立．?dāng)?shù)學(xué)建模[M].合肥：中國(guó)科技大學(xué)出版社，2008:220.

[6]吳禮斌.經(jīng)濟(jì)數(shù)學(xué)實(shí)驗(yàn)與建模[M].南開：天津大學(xué)出版社,2009.

Bitmap Vector Method and Promotion Based on Bessel Curve

HU Xue-feng1,ZHU Jia-ming1，LIU Ya-qian2，ZHU Yong1
(1.School of Statistics and Applied Math，Anhui Finance and Econemics University，Bengbu,Anhui 233030；2.School of Finance，Anbui Finanle and Economics University，Bengbu，Anhui 233030)

This paper aims at extracting the boundary line of simple graphics.We select black and white pattern as the breakthrough point and analyze the data of coordinates point outline feature comprehensively.According to the principle of establishing the Bessel curve,based on the model,we build a graph boundary line of Bessel curve extraction,graphic boundary line extraction correction and simple color graphic boundary line extraction etc.Using Excel to process the data,using Photoshop,Matlab and other graphics software to extract the boundary lines,using Opencv to test the fitness of the lines.Finally,we compared the results to the actual and found that the vector edge line pattern close to the reality of pattern to a large extend.

bitmap;bessel curve;bilinear interpolation;error analysis;limit substitution method;Matlab7

TP391.72；TP391.41

A

1673-1891（2015）02-0072-04

2015-03-08

國(guó)家自然科學(xué)基金（項(xiàng)目編號(hào)：11301001）；安徽財(cái)經(jīng)大學(xué)教研項(xiàng)目（項(xiàng)目編號(hào)：acjyzd201429）。

胡學(xué)峰（1994-），男，安徽滁州人，本科在讀，研究方向：信息與計(jì)算科學(xué)。**為通信作者朱家明。