基于贝赛尔曲线位图矢量化方法的研究*

胡学峰，朱家明**，刘雅倩，朱 勇

（1.安徽财经大学统计与应用数学学院，安徽蚌埠233030；2.安徽财经大学金融学院，安徽蚌埠233030）

基于贝赛尔曲线位图矢量化方法的研究*

胡学峰1，朱家明1**，刘雅倩2，朱 勇1

（1.安徽财经大学统计与应用数学学院，安徽蚌埠233030；2.安徽财经大学金融学院，安徽蚌埠233030）

针对简单图案的边界线条提取，以所给图中的黑白图案为切入点，综合分析了图案轮廓特征点的坐标值数据，根据贝塞尔曲线的建立原理，笔者尝试构建了基于贝塞尔曲线的图形边界线条提取、图形边界线条提取修正和简单彩色图形边界线条提取等模型，运用Excel进行相应数据处理，并使用Photoshop、Matlab等软件提取出图形的边界线条，Opencv软件对拟合的线条进行了检验。最后，将所求结果和实际相比较，发现得到的矢量边缘线图案很大程度上接近于现实图案。

位图；贝赛尔曲线；双线性差值；误差分析；极限替代法；Matlab7

矢量图从本质上只是使用曲线方程对图形进行的精确描述，在以像素为基本显示单元的显示器或打印机上是无法直接表现的。将矢量图转换成以像素点阵来表示的信息，再加以显示或打印，这个过程称之为栅格化。栅格化的逆过程相对比较困难。本文运用matlab图像技术提取出图1中图像轮廓点，并依照贝赛尔曲线对其进行分类成n段间断曲线进行复原，再将这n段进行拼接形成模拟出来的原图形。最后将这种方法推广，得到一种基于贝赛尔曲线的位图反栅格化模型。

1 栅格化的位图图案的边缘线的提取

1.1 研究思路

将问题拆解成两部分：第一，图形边缘线的提取；第二，对提取的边缘线矢量化。首先，通过matlab对题中已给定的图形（见图1）进行轮廓特征点提取，得到轮廓特征点的坐标位置之后，对这些特征点的位置进行插值并拟合，其次，考虑到插值之后的图像不够圆滑，为了减小误差，将图像等分切割为四部分，然后利用贝塞尔曲线的思想，对已插值后的轮廓特征点分别进行贝塞尔曲线的曲线矢量化，从而得到四个部分矢量化轮廓曲线图，最后将四部分的曲线图结合起来形成一个整体轮廓图。

图1 栅格化图

1.2 数据处理

（1）去除噪点干扰

由于对于扫描后的图像,其经过栅格化之后图片上存在许多噪点,在矢量化的预处理阶段,必须先将其剔除,以消除对矢量化的干扰。这里笔者利用photoshop对图片进行噪点剔除[2]。

（2）轮廓特征点坐标值提取

用matlab程序分别提取出四组图形(1)、(2)、(3)、(4)的轮廓特征点。

（3）图像分割

将曲线分割成四个部分理论依据：第一，对整个图形的轮廓特征点进行拟合的话，数据过少，误差太大，笔者采取将轮廓特征点连成的图像分割成四个部分的办法（见图1）；第二，一条曲线可在任意点切割成两条或任意多条子曲线，每一条子曲线仍是贝塞尔曲线；第三，一些看似简单的曲线（如圆）无法以贝塞尔曲线精确的描述，可以将其分成四个部分，当每个内部控制点对单位圆上的外部控制点水平或垂直的的距离为时，分成四段的贝塞尔曲线，可以小于千分之一的最大半径误差近似于圆，同理类推到一些不规则的封闭曲线当中，将其切分为四个部分（如图2）。

图2 图形轮廓特征点的散点图

（4）轮廓特征点坐标插值处理

由于提取的轮廓特征点可能过于稀少，导致重构的轮廓失真，这里采取插值的办法。处理轮廓特征点的流图：

图3 轮廓特征点插值处理流程图

第一，光滑区域一维插值处理：对于很光滑区域，即没有尖点的情况下采取一维插值法。这里笔者对切割的四块图片中的第（1）、（2）、（4）块图（见图2）都使用了一维插值法。

第二，非光滑区域双线性插值处理：双线性插值可以有效地消除锯齿现象,插值质量高。这里笔者应用双线性插值的思想对图像（3）（图2）进行类双线性插值处理。见图4。

图4 图像(3)边缘非光滑区域双线性处理流程图

图5 边缘特征点补充图

接下来进行第一步：X方向的线性插值:

第二步：做Y方向的点P1和P2插值,由R1与R2计算P点:

这样对每两个点都做如上处理，用matlab编程辅助，可以对边缘的非光滑区域做出很好的插值。

1.3 理论方法——基于贝塞尔曲线的图形边界线条提取理论

线性贝塞尔曲线给定点P0，P1，B(t)代表经过t时间的坐标轴位置，线性贝塞尔曲线只是一条两点之间的直线。这条线由下式给出：

二次方贝塞尔曲线的路径由给定点P0，P1，P2的函数B(t)追踪：

则n阶贝塞尔曲线可如下推断。给定点P0，P1…Pn，其贝塞尔曲线即曲线的参数形为：

将这个n阶的贝塞尔曲线作为笔者的理论模型。

1.4 结果的分析

利用上面求出的模型通过matlab软件编程求出四块图形的分别拟合情况，如图6。

将图像虽然切割成四部分，但是四部分的像素点的坐标还是不变的，所以根据坐标再将这四块拟合曲线组合在一起，形成如下的图像边缘线提取图（图7）。

图6 图形轮廓特征点拟合图

图7 图案的边界线条图

2 位图边缘线的提取优化和推广

2.1 预处理与分析

因为上文中进行四部分切割之后发现原图与拟合后的矢量曲线不能很好地进行重合，考虑到在取点时由于对某些不是圆滑的点直接就进行模拟，而贝塞尔曲线本身模拟出来的是一条曲线，这导致原图出现棱角的地方会由于曲线拟合而出现棱角磨平，不符合原图。

为此笔者用以下切割点的规则，即转折点切割原则：

第一，根据已知的位图文件判断有哪些转折点，并进行标记。

第二，对已读出的轮廓点我们根据位图文件以特殊的转折点作为切割点，对由于噪点而产生的转折点丢失给予补点，并以此为端点。

使用转折点切割原则进行轮廓点切割后，应出现n组轮廓点，每组轮廓点的粗略连线应该是一条光滑的圆弧，再利用贝塞尔曲线进行拟合。

2.2 栅格化位图图案边界线的提取方法修正

（1）数据预处理

①直线区域与曲线区域的检测:当相邻3点的斜率相等(直线,斜线)。其余情况用圆弧曲线区域。

②对于直线区域处理方法：由于直线区域的存在会使得提取的图形边界线线条过于粗糙生硬，并且会对下一步的曲线拟合造成麻烦，也会使得图片失真，所以对于直线区域，要采取必要的处理。

当相邻3点的斜率相等(即为直线,斜线)时候，取以下两种方法：

长度约束的分段方法：即为在此直线区域上每隔一定距离取得一点作为分段点,按序插入到直线区域两端点之间即可。

坐标微调法：于一个坐标可能出现多个坐标(如图中的点有多个)的情况，便需要对插值点的选取做一定微调，采取对于做修改后带入，再进行spline插值拟合。

③对于圆弧曲线区域处理办法：处理方法采取前文中一样的插值办法。

(2)理论准备

首先用matlab提取出该图像的轮廓特征点位置，再对图像轮廓线的依照转折点重新切割成线段AB,BC,AC三种情况，见图8。

图8 图像轮廓切割图

仍然按照贝塞尔曲线拟合的办法，得出曲线的方程拟合模型：

(3)位图图案边界线的提取修正：

对于AC曲线进行拟合的结果精确却太复杂，所以继续对AC段曲线进行切割，切割成AB,BC,CD,DE,EF,AF六段，切割情况如下：

图9 图像轮廓再切割图

图10 图像轮廓拟合曲线

对这五段曲线的轮廓特征点在进行贝塞尔曲线拟合的基础下，可分别用matlab进行拟合并求解出AE、EF、DF、CD、BC、AB段相应贝塞尔参数方程结果，并作出拟合图（如图10）。

由于采取的是贝塞尔函数拟合，而贝塞尔函数特征即为很多高次项之和，故结果虽然复杂，但是能够精确拟合出曲线轮廓。

（4）位图图案边界线的提取的检验

①检验思想

根据贝塞尔曲线的推理过程，其本身无法用一般方程进行表示，则用参数方程：表示贝塞尔曲线。但参数方程本身无法利用公式

进行方程拟合优度的检验，为此笔者提出极限替代法思想。

极限替代法：

图11 值的模糊取值示意图

②检验结果

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

综上所有的曲线区域都通过了拟合优度的检验。这一点从图9和图10对比也可以看出。

3 结论

对于一般平面图形，采用一般的线性拟合或者十次以内的函数拟合能大概求出元图形轮廓，但本文的贝茨拟合方法能够较为准确地运用编程方法求出不具备简单变化规律的轮廓线，且拟合函数唯一，都是n次以内的贝茨函数，可以在一定误差范围内较为精确模拟出原曲线。

注释及参考文献：

[1]2014年第七届“认证杯”数学中国数学建模网络挑战赛B题[EB/OL].http://www.tzmcm.cn/.

[2]用ps技术处理图片噪点：[EB/OL]http://jingyan.baidu.com/article/b907e627f170fb46e6891c5c.html.

[3]严兰兰,宋来忠,李军成.有理Bezier曲线的拼接[J].三峡大学报（自然科学版）,2005,27(5):469-471.

[4]姜启源等.数学模型[M].北京:高等教育出版社,2003：440.

[5]杨桂元,黄己立．数学建模[M].合肥：中国科技大学出版社，2008:220.

[6]吴礼斌.经济数学实验与建模[M].南开：天津大学出版社,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

国家自然科学基金（项目编号：11301001）；安徽财经大学教研项目（项目编号：acjyzd201429）。

胡学峰（1994-），男，安徽滁州人，本科在读，研究方向：信息与计算科学。**为通信作者朱家明。