基于矢量化方法的套色图光滑变换算法

1、基于矢量化方法的套色图光滑变换算法*汤锋1 王章野1 刘钢1 许端清2 彭群生11浙江大学CAD&CG国家重点实验室 浙江杭州 3100272浙江大学计算机学院 浙江杭州 310027 摘要：图像的光滑变换一直是图象处理领域中的一个难点，目前已有的算法中没有一种能很好适用于所有纺织行业中的套色图象。本文中提出了一种新的算法，该算法首先进行图象的矢量化，用多边形逼近轮廓，然后再用基于拐点和弯曲角的方法对边界点集合进行精简，最后进行变换和重构。这样在保持原来形状的基础上减少了变换过程中产生的毛刺。实验表明本算法能鲁棒地处理各种套色图象。关键词：轮廓跟踪 毛刺剔除 边界简化 图象重构。中图法

2、分类号:TP 391 文献标识码:A 文章编号:1006-8961(2003)spec-Vector Method Based Few-color Image Smooth TransformationFeng Tang1, Zhangye Wang1, Gang Liu1, Duanqing Xu2 and Qunsheng Peng11State Key Lab. CAD&CG, Zhejiang University, Hangzhou 3100272College of Computer Science, Zhejiang University, Hangzhou 310027

3、Abstract Image transformation is a frequently used operation in CAD systems, but how to keep the image smooth in the transformation is a difficult problem, current methods cannot process very well for few color images in textile industry. In this paper we propose a new algorithm for this, first the

4、image is vectorized, using a polygon to approximate the contours of different colors, then we use a dominate point based approach to reduce the number of contour points, then the transformation is applied on the reduced contour points, finally we fill the transformed polygon to reconstruct the final

5、 image. Experiments show that this approach can deal with most few color images.Keywords contour tracing, blur elimination, contour simplification, image reconstruction1.引言数字图象可被分为灰度图象，彩色图象，套色图象和二值图象1。其中套色图像是指由某几种颜色的均匀色块构成的图象，不同色块间具有明显的分界线，已被广泛的应用于纺织、印染等工业中。以简单的图象旋转为例，经过旋转变换，象素点的坐标总要乘以一个旋转矩阵，这样产生的浮点

6、数在重采样的时候要取整，产生了许多偏离正常位置的点，当这种偏离大于一定的值时，我们称这种点为毛刺点，即使图像看上去不光滑的点。提到光滑，我们很容易想到B样条的光滑的特性，所以就有了基于B样条曲线拟和法2的光滑变换处理。其思想是：从原图象中抽取能够代表图象轮廓的控制点，将图象变换作用于这些控制点，然后用B样条进行拟和，得到新图象的轮廓。最后，用某种填充算法对新图象的轮廓进行填充，从而得到变换后的新图象。 这种算法虽然可以在某种程度上保持图象的光滑性，但却不能很好的保持图形的原状，在图2中的1，2处的色块变细了，3处的色块改变了形状。这个缺点产生的原因是高阶B样条的形状难于控制，以致不能很好的保持

7、图像原来的形状。 图1 原图 图 2 原图旋转30度（基于B样条算法）2.基于线性变换的图象光滑变换处理针对高阶的B样条拟和法的缺陷，我们这里采用了线性的直线拟和的方法，用多边形去拟和边界，然后对多边形的顶点（即轮廓的控制点）进行变换，之后再通过处理过的轮廓的控制点重构出完整的图像。大多数工业中使用的图像有很强的规律性：第一、这些图像大多由一些简单的色块组成，颜色数不会太多（一般在256色以下）；第二、这些图像的边界一般都是由某几种曲线组合而成（这是由软件工具所决定的），除去少量的拐点，图像的边界是光滑的。从实现上说, 整个方法的可分为如下几步：1)图象的矢量化;2)基于矢量的图象变换;3)图

8、象的重构.图象的矢量化是将各种颜色的色块的边界轮廓找出来，在它们中寻找控制点。基于矢量的图象变换就是对控制点进行相应的旋转、放大等变换图象的重构是根据基于矢量的图象变换的基础上得到的点来对新得到的边界进行填充，得到目标图象。3 图象的矢量化图象的矢量化34是用轮廓跟踪的方法将各种颜色的色块的边界轮廓找出来，在它们中寻找控制点，从而用很少的信息表达光栅图。31 轮廓跟踪 ：得到图象中所有色块的轮廓，轮廓跟踪算法比较成熟，具体算法参见132基于候选点夹角的拐点寻找算法：定义1： 拐点-图象轮廓上的转折点，在拐点两侧，轮廓的走向有明显的不同。在本文中，拐点被认为是特征夹角(见定义5)小于某一阈值的候

9、选点(定义4)。拐点是描述图象轮廓的重要信息。也就是在变换的过程中需要保持的信息。定义2: 尖点如果在轮廓上存在某一象素点A，满足：A的0-近邻和2-近邻(或者2-近邻和4-近邻或者4-近邻和6-近邻或者0-近邻和6-近邻)是轮廓点，而其它近邻不是轮廓点；我们称A为尖点。定义3：轮廓段在两个候选点之间的轮廓线。在一个轮廓段，最多只能够存在两种不同的链码值。定义4：候选点设lc1和lc2是当前轮廓段的两种链码值，P点是当前点，Q点是P点的后继点。lc3是Q点的链码值。如果：1)是尖点，那么，P是候选点；2)如果lc1!=lc2时,lc3!=lc1并且lc3!=lc2，那么，P是候选点。3) 如果

10、lc1=lc2时,如果|lc3-lc2|>1，P是候选点。定义5：特征夹角设A，B，C是三个候选点，夹角是B点的特征夹角。算法描述：符号 : listcode是链码的集合，lc1和lc2是当前轮廓段的两种链码值，B点是当前候选点，A点和C点分别是B的前一个和后继候选点，lc3是B点的链码值。INF-ANGLE是特征夹角的阈值。i表示当前轮廓点,num表示轮廓点的数量，bp表示轮廓点的集合。Dis表示前一个候选点和当前点的序列距离,dif函数计算两个链码值之差的绝对值。算法分为9个步骤：Lc1=listcode1,lc2=listcode2;把起始象素点添加到候选点列表中，dis=0;Fo

11、r(i=2;i<num;i+)If bpi是尖点 把bpi添加到候选点列表中,lc1=listcodei+1,dis=0,continue;Else if (lc2=lc1 | dis=0) Lc2=listcodei;lc3=listcodei+1;If(lc3=lc1 | lc3=lc2) /当前点bpi不是候选点Dis+;Continue;else if(lc1!=lc2 | dif(lc3,lc2)>1 ) / bpi是候选点把bpi添加到候选点列表中,lc1=listcodei+1,dis=0; 遍历候选点集合。对于候选点B，如果B是尖点，那么，将B添加到拐点列表中;否则

12、，计算夹角ABC，如果夹角ABC小于某一给定值INF-ANGLE，那么，将B添加到拐点列表中，同时记录下夹角ABC;33 基于控制点弯曲角的特殊的控制点寻找法控制点是指描述轮廓内容的一般的轮廓点，也就是逼近原轮廓的多边形的顶点。主要包括多边形拟和得到的点，上面的拐点，和下面要特殊处理的特殊的控制点。本文采用了基于聚合的最小均误差线段逼近法得到逼近多边形。具体算法参照25用上面的方法对很多的图象处理的结果都很好，但是对于实际应用中的套色图象，经常会有很细的线条（一般是3个象素宽）如图3这样的图像用上面的方法会出现什么问题呢？通过上面的方法得到的控制点如图5。 图 3 图4 图5可以看到，对于伸出

13、来的枝状的线条得到的控制点是线条的顶点，这样，其前后的两个控制点都连到该点，这样，伸出来的线条经过处理放大2倍就会产生如图5所示的结果，使线条很尖，不能保持原来的形状。针对这种情况，我们采用了基于控制点弯曲角6的特殊的控制点寻找法来将相邻的前后两点也选为控制点。这样就能避免这种常见现象的出现。从轮廓中提取曲率较大的点（控制点），并将它们用直线连接起来就可以很好的勾画出原图的边界。根据曲率大的点具有更有价值的信息，我们对得到的控制点进行遍历，如果发现某个控制点相对于其相邻点有较大的曲率我们就在这个点周围选择一些点作为完善的控制点加入控制点列表。首先，我们要给出离散型曲线的曲率的精确的定义。而对数

14、字图象中的曲线，由于切线斜率变化不是任意小，不能用=d/dl描述。在Freeman链码中，相邻的斜率变化只能是45°的整数倍。我们可以用(Yi+k Yi)/(Xi+k-Xi)来表示在Pi点的斜率（其中k>1）。对于任意一个轮廓上的点pi，与它相关的上下文可定义为一个对称的点的集合S(Pi) = Pi-k,Pi-1,Pi,Pi+1,Pi+k，我们可用它来度量轮廓上点的曲率。k是半径（以Pi为中心的前后对称点对的数目）。定义6：k-弯曲角(k-angular bending)：定义Pa，Pb 分别为给定点Pi前后的两个点，它们的坐标为Pi前后k个点的坐标的平均值6。Pa的坐标: X

15、a = , Ya = Pb的坐标为：Xb = Yb = 根据这些值，k-矢量可定义为：ki = (Xa Xi, Ya Yi). ki = (Xi Xb,Yi Yb),在Pi点的k-弯曲角定义为两个矢量的夹角k(Pi) = 图6 定义：1-弯曲角1的直观描述图 7这些定义中，符号的正负代表了曲线在点Pi的凹(>0)凹(<0)。在实际应用中，我们用的是1-弯曲角的定义。我们对控制点集合中的所有点进行遍历，当发现当前点的1-弯曲角大于某个值时，就将该点的前后两点也选为控制点。经过测试，将阈值设为120度效果较好。上图是图7通过上面的方法的到的放大2倍的结果，可见该方法对于消除尖点是很有效

16、的。4.基于矢量的图象变换和图象重构通过上面的矢量化，图象可以有很少的边界的控制点来表示了，基于矢量的图象变换就是将变换矩阵（旋转、缩放）作用到控制点上。将相同色块的轮廓的控制点连起来就生成了变换后的目标图象的轮廓，对得到的轮廓进行多边形填充就可以得到目标图象。5.实验结果及结论图8是原始图，图9是原图旋转30度得到的结果，图10是原图放大1.2倍得到的结果，可以看出，得到的结果和B样条算法相比能在保持光滑性的同时保持了图象的原来的特征形状。图象的光滑处理是一个一直没能得到彻底解决的问题，特别是套色图象的光滑变换中一直没有一个令人满意的解决方法。如何能在图象变换过程中既能保持原有的形状又能保证

17、边界的光滑是一个非常困难的问题。本文提出的基于矢量化的方法通过减少变换矩阵作用的象素数和在变换中保持图象原有的特征的方法，快速而简单的解决了该问题。实验表明本算法能鲁棒地处理各种套色图象。图 8 原始图象图10 放大1.2倍的结果图 9 旋转30度的结果 参 考 文献1Pavlids, T., Algorithms for Graphics and Image Processing M, Computer Science Press, 1982.2吴良武,保持轮廓清晰光滑的灰度图象放大算法, 计算机辅助设计与图形学学报J,2002, 14(4):306-3093沈立,张晨曦，黑白图像得矢量化J

18、，计算机辅助设计与图形学学报.2000, 12(3):170-1734董海卫，江早，王永军，基于矢量化二值工程图得符号提取算法J，计算机辅助设计与图形学学报.2000, 12(4):294-2985Shu Chien Huang ,Yung Nien Sun Polygonal approximation using genetic algorithmsC Proceedings of CAIP'99, Ljubljana, Slovenia, 1-3 September, 1999, pp. 175-1826Vincent Beau,Mark Singer, Reduced resolution and scale space for dominant feature de