改进的Potrace提花织物图像矢量化算法*

姚鹏鹏， 樊 臻， 张森林

(浙江大学 电气工程学院，浙江 杭州 310007)

改进的Potrace提花织物图像矢量化算法*

姚鹏鹏， 樊 臻， 张森林

(浙江大学 电气工程学院，浙江 杭州 310007)

为了对提花织物图像进行矢量化，针对其颜色少、色块大的特点，提出了改进的Potrace图像矢量化算法。原始的Potrace算法只能实现对二值图像的矢量化，改进后的算法将位图中的色块逐个分解生成一个个的闭合路径，之后将这些闭合路径按照其各自分布拼接成树状结构并矢量化，最终生成一个完整的矢量图形。该算法在实际的应用中取得较好效果。

提花织物； Potrace 算法； 图像矢量化； 路径分解

0 引 言

图像的矢量化尤其是彩色图像的矢量化一直是图像处理的难点。而国内外现有的有名的矢量化软件的普遍缺点是抗噪声性差矢量化的精度和速度都不高，而且这些软件的应用偏向于工程图纸领域地理信息系统和计算机辅助制造等[1]。

提花织物图像不同于普通的彩色图像，它是由一个个的色块组成[2]，理论上更容易进行矢量化。将图像矢量化后，有利于图像的再利用和再创造。图像矢量化对于提花织物图案的处理还有其他重要的意义，例如:可用于提花织物的图像识别和图片压缩[3,4]。本文提出了改进的Potrace矢量化算法，在处理提花织物图像时，取得了很好的效果。

1 总体方案

本文主要是对Potrace矢量化算法的改进。Potrace位图矢量化算法只可以处理二值图像(即黑白图像)，改进后的Potrace算法能够支持K种颜色的位图图像。首先将K种颜色的位图分解为K张二值图片，分别对这些图片进行路径搜索，之后根据这些路径的位置关系，拼接成一颗路径树，最后调用Potrace的路径矢量化算法，生成矢量图像。提花织物图像一般不超过16种颜色，非常适合使用此方法。

2 Potrace位图矢量化算法

Potrace矢量算法是加拿大教授Selinger Peter提出并实现的二值位图(即黑白图片)矢量化算法。该算法可以将一个位图转化为一个光滑的，放缩无锯齿化的矢量图。Potrace算法主要分为5步：1)位图被分解成划分黑白区域之间边界的一系列路径；2)每一个路径被一个最优的多边形拟合；3)每一个多边形被转化为一条光滑的轮廓线；4)此步为可选的，如果可能的话，合成的曲线通过加入连续的贝塞尔曲线段进行最优化处理；5)输出被调整成需要的格式。

Potrace矢量化算法计算速度快，效果好，支持的输出格式丰富，但是存在一个严重的缺点，它只可以对二值图像进行矢量化。为了使Potrace更具使用价值，需要对其进行改进，以使它能够对索引色图像进行矢量化[5,6]。

3 Potrace算法的改进

对Potrace算法的改进主要集中在对路径分解的改进上。对于一张二值图片，想象将该图片放置于一个坐标系里面，每个像素角落的坐标值为整数值。假设该图片的背景色是白色，前景色是黑色并假设超过图片边界的颜色都是白色。如果点p拥有一个整数值坐标，这个点必然是4个像素的交接点。如果这4个像素的颜色不完全相同，就称这个点为顶点(vertex)。如果2个顶点v和w的欧几里得距离是1，称从v到w有一个边缘(edge)。如果从v到w的边缘将黑白像素分开，并且黑像素在边缘的左边，白像素在边缘的右边，称边缘的方向为从v到w。路径(path)是由一个序列的顶点{v0,…,vn}组成,如果v0=vn，则称这条路径是闭合路径。路径分解的目的就是将一幅图片G分解成许多的闭合路径。

二值图像路径分解流程如图1所示。首先寻找1对颜色不一样的邻接像素，比如可以寻找最左出现的黑色像素的那一列。这2个像素将会形成一个边缘，将黑色像素在左边白色像素在右边的方向定义为正方向。这是一个长度为一的路径。沿着这条路径方向接着向下寻找，保证黑色的像素在左边白色的像素在右边。一直寻找，直到来到起点，就可以定义一个闭合的路径了。每当搜索完成一条路径的时候，将这条路径移走，并且将其内部的像素置反。这样就定义了一个新的图，然后再一次使用这个方法，直到所有的像素都是白色为止。之后的工作就是对每个路径进行独立的操作。

图1 二值图像分解流程图Fig 1 Flow chart of binary image decomposition

在Potrace算法中，矢量图在内存中用树的结构表示。如图2(a)所示的二值图像，将会生成图2(b)所示的A，B，C，D，E，F，H，I8条路径。其中,A路径包含B路径，那么，B就是A的孩子；而A路径跟F路径没有包含与被包含的关系，那么，路径A跟F就是兄弟关系。图2(a)将最终生成如图2(c)的树的结构。

图2 二值图像矢量化Fig 2 Binary image vectorization

彩色图像的路径搜索流程如图3所示，依次取出每个颜色，生成一个新的空白二值图像。生成的二值图像与彩图长宽相等。遍历彩色图像，如果坐标原图中坐标(i，j)像素的颜色是当前取出的颜色，就将二值图中(i，j)所在的颜色置为黑色，其他的位置为白色。对于新生成的二值图像再进行路径搜索，每搜索完一条路径，就将其插入已有的路径中。插入的时候需要注意父节点一定要在其子孙节点之前。然后再调用Potrace的里面的链表转换为树的函数，将链表生成一颗树。

图3 彩色图像路径搜索流程图Fig 3 Flow chart of color image path searching

在路径搜索的时候会发现，大多数的路径会搜索2次。如图4(a)中的路径B，在对搜索的红色二值图片的时候，搜索了一次，在搜索蓝色二值图片的时候，又搜索了一次,显然重复了。解决的方法是在路径搜索的过程中为每个路径加上一个符号域，在图4(a)搜索红色二值图像的时候，会生成图4(b)所示的二值图像，搜索到路径A则将其符号设为‘+’，然后找到路径B，由于B包含在路径A里面将其符号设为‘-’，再然后找到路径C，将其路径设为‘+’，就这样不断重复，最后在插入链表的时候只将符号域为‘+’的路径插入，其他路径丢弃即可。这样如果没有剔除符号域为‘-’这一步，图4(b)会生成A→B→这样的链表，而在加入了剔除符号域为‘-’这一步之后，得到的链表将是A→C。

对图4(a)中的图像进行路径分解，红色的部分会首先生成一个A→C的链表。蓝色部分会生成一个B→D的链表。然后将蓝色部分的链表插入红色部分的链表，最终的链表是A→B→C→D.生成的树如图4(c)所示。

4 实验结果

图5是一组矢量化效果的展示，图5(b)对图5(a)进行了矢量化，图5(c)将其背景色去除。比较图5，可以看到，通过该方法能准确地检测出原图的轮廓，生成的矢量图光滑整齐，与原图差别小。

利用矢量化描述提花织物图像有如下优点：1)丝绸织物多为大色块，使用矢量方式存储可以有效地减小存储大小，节省存储空间；2)矢量化后的图稿易于修改，如图5(c)所示，只要一步简单的操作就能将其背景色去除或替换；3)以矢量形式描述的图稿易于提取花纹,有利于图像的再创作；4)矢量图像描述的是丝绸图像的图形信息，这些信息是CAD设计的主要信息，进行矢量描述后可以更方便地应用于图像的匹配与检索。

图5 矢量化效果图示Fig 5 Diagram of vecotorization effect

5 结 论

本文改进了Potrace算法的路径分解部分，使原来只能处理单色图片的Potrace算法支持了彩色图像的处理。尤其在对提花织物图像的处理中，该算法取得了很好的效果。但是，此算法依旧存在一些不足，比如：在处理颜色数量多的时候，该算法的处理速度很慢，因此，还需要继续地深入研究。

[1] 李文庆，郑秋华，张坤龙.基于用户交互的光栅图像局部矢量化方法[J].杭州电子科技大学学报,2011,31(6):91-94.

[2] 刘妹琴,程红梅.基于扩展“变球法”的颜色量化分析[J].工程设计学报,2006,13(3):175-178.

[3] 程红梅，颜钢锋.纹织图像的矢量化方法[J].纺织学报，2006,27(3)：33-35.

[4] 李文庆.针对维吾尔族图案重组设计的关键技术研究[D].杭州：杭州电子科技大学，2011.

[5] Selinger Peter.Potrace:A polygon-based tracing algorithm[2009—07—01].http:∥potrace.sourceforge.net/potrace.pdf.

[6] Selinger Peter.Potrace Library API[2009—07—01].http:∥potrace.sourceforge.net/potracelib.pdf.

Improved Potrace algorithm for vectorization of image of jacquard*

YAO Peng-peng, FAN Zhen, ZHANG Sen-lin

(College of Electrical Engineering,Zhejiang University,Hangzhou 310007,China)

In order to vectorize jacquard image,aiming at small amount of color and large color blocks,propose an improved Potrace algorithm for vectorization of image .The original Potrace algorithm can only realize vectorization of binary image and the improved algorithm decompose color blocks of bitmap one by one to closed paths which are combined to a tree structure later and merged to a vector graphic at last.This algorithm achieves good effect in practical use.

jacquard; Potrace algorithm; vectorization of image； path decomposition

2013—09—15

国家科技支撑计划资助项目(2013BAH58F02)

TP 391

A

1000—9787(2014)04—0125—03

姚鹏鹏(1989-)，男，江苏如皋人，硕士研究生，主要研究方向为数字图像处理，人工智能。