均值漂移算法对纬编提花针织物图像分割的探讨-发表版.doc

均值漂移算法对纬编提花针织物图像分割的探讨杨配裕，龙海如(东华大学 纺织学院，上海 201620)摘要 为了取代人工方法来分析纬编提花针织物的彩色花型和绘制意匠图，探讨了用几种不同分割算法对提花针织物图像进行色彩识别.首先对织物的实拍图进行必要的矫正，接着采用K-均值聚类算法、阈值分割算法、均值漂移算法以及编程工具，进行色彩的聚类和分割，实现了织物图像彩色花型的自动识别，最后在均值漂移算法的基础上，在取定的图像范围内自动生成了彩色意匠图.研究结果表明，与其他两种方法相比，均值漂移分割算法的彩色花型识别率较高，去除杂色效果较好，具有应用可行性.关键词：纬编提花针织物；均值漂移算法；图像分割；彩色意匠图中图分类号：TS 101.8 文献标志码：AInvestigation on image segmentation of weft jacquard knitted fabric bases on mean-shift algorithmYANG Pei-yu , LONG Hai-ru(College of Textiles, Donghua University, Shanghai 201620, China)Abstract: To replace manual method to analyze colored pattern and draw notation of weft jacquard knitted fabric, three different methods were applied to segment images of weft jacquard knitted fabric. Firstly pictures of the fabric were taken and the images were rectified, and then k-mean cluster algorithm, threshold algorithm and mean-shift algorithm were used to implement automatic color clustering and segmentation of the pattern images by programming of Visual C+. Finally, according to the mean-shift algorithm, a colored knitting notation was produced automatically in the given image area. By making a comparison among these three methods, the mean-shift algorithm was proved to have feasibility for its high recognition ability of pattern and good effect of noise filtering.Key words: weft jacquard knitted fabric; mean-shift algorithm; image segmentation; colored knitting notation 计算机技术和图像处理方法的不断发展，使各行各业许多繁琐的工作可以从简单的重复劳动中解放出来.针织企业在生产过程中，经常要对来样进行织物分析从而确定各种上机工艺参数，其中意匠图或者编织图的绘制是一个必不可少的过程.对于纬编提花针织物来说，目前采用的方法是借用照布镜等辅助工具，用人工肉眼的方式来分辨它的花型，比较费时费力.如果应用图像处理方法来自动分析和绘制纬编提花针织物花型意匠图，不仅能够加速从来样到意匠图的转化过程，而且还可以为后续的通过计算机来自动生成上机编织工艺创造条件.图像分割的目的是把一个含有多个特征的图像分割成若干互不重叠的区域，它通常是根据给定图像的颜色、灰度值或纹理等相似属性以及分割准则，将一幅图像划分成几个有相似属性的像素集合.图像分割的方法很多，在灰度图像的基础上主要运用的有直方图阈值法、特征空间聚类、区域增长、边缘检测、模糊方法、神经元网络等，各种方法都可以有条件地延伸到彩色图像的分割 1.图像2收稿日期：2006年10月24日作者简介：杨配裕（1981），男，浙江绍兴，硕士研究生，数字化纺织，Email：的分割结果因图像分割准则和分割目标的不同而不同，所以难以提出一个确切的标准来衡量分割效果的好坏.本文涉及的纬编提花针织物图像是一种比较复杂的实时图，线圈的歪斜，线圈孔隙中底色的影响，照片拍摄中噪点以及织物本身在光照下的反射等因素，都会给图像分割过程带来不小的影响，因此，如何选用最合适的方法来分析织物图片，进而识别和区分每一个线圈单元的颜色，是本文要解决的主要问题. 本文以较为常见的三色纬编提花针织物为对象，采用k-均值聚类算法、阈值分割算法和均值漂移算法进行彩色线圈花型的分割和识别，并且在综合比较的情况下，以均值漂移算法的理论和自动分割的效果为基础，进而绘制出相应的彩色花型意匠图.1 纬编提花针织物图像的获取和矫正该织物图像的获取可以借助平板扫描仪或者数码相机，只要保证织物纵行和横列间的垂直状态，而且取样范围大于一个完全组织即可.一般说来，通过相机或者扫描仪直接得到的图像线圈横列不可能完全平行于图片的上沿，同理，它的纵行也不可能完全垂直于图片上沿，这就要求在获取图像以后进行必要的处理，使之纵行横列之间相互垂直，并且横列与图片上沿严格平行. 由于不能彩色印刷，故本文将三色（白、深蓝、深红）纬编提花针织物的实拍彩色图像转化为灰度图，如图1所示，其中最浅色为白色，最深色为深蓝色，中间色为深红色，一个完全组织的花高为22横列，花宽为18纵行.各个线圈中心点基本上都有反面线圈底色的影响，而且线圈横列整体右斜，更包含了不完整线圈和杂色的影响.这需要在分割前将这些影响因素消除，同时可以将图片适当地截取使生成的意匠图更加精确.经过有关软件调整处理后的图像如图2所示. 图1 织物实拍图像图 图2 调整后的图像 Fig.1 Fabric image Fig.2 Rectified image2 几种分割算法的实现和比较2.1 K-均值聚类算法K-均值聚类算法通常也被称为C-均值聚类，在图像分割中是一种比较成熟的方法，已经被运用到非常广泛的领域.它的核心思想是把所有的n个向量xi（i=1，2，n）分为c个组Gj(j=1，2，c)，并求得每个组的聚类中心，使得目标函数，即表征每个类距离指标的值达到最小.如果把距离选择为欧几里德距离，第j个组中向量xk与相应聚类中心ci间的目标函数可定义为： (1) 如果引用一个cn的二维矩阵U来表示已经划分过的组，那么随着聚类中心的确定，可以导出下列式子： (2)必须指出的一点是，所有的元素只能够隶属于一个聚类中心的组，所以针对式(2)，可以得出以下必须满足的条件： (3) 于是可以得出K-均值聚类算法的一般步骤： (1) 人为地规定计算的聚类中心数量ci并且进行初始化； (2) 根据式(2)来确定每一个点确定的隶属矩阵；(3) 根据式(1)计算价值函数，如果目标函数J满足一定的阈值，则自动停止；(4) 根据条件式(3)修正聚类中心，返回第二步继续开始.由此可见，K-均值聚类算法是一个反复迭代收敛的过程，但是它最后并不一定收敛于最优值，所以聚类中心的取值要反复调整以使结果趋于最优.而且由于反复递归迭代，它的计算量非常大，所以一般只用于灰度级图像的聚类分割.因此，K-均值聚类算法的缺陷比较明显，须人为指定聚类数量，计算量大十分依赖初始的聚类中心，只能够收敛到局部的极值.根据上述原理，笔者在V中利用C+对K-均值聚类算法进行编程来实现对图像的分割.由于计算量的问题，只对织物经滤波和腐蚀处理的灰度图像，即图3进行了K-均值聚类分割运算，结果如图4和图5所示. 图3 256色处理图图 4 K=3分割图 图5 K=4分割图Fig.3 Processed image of 256 colors Fig.4 Segmented image of K=3 Fig.5 Segmented image of K=4从图4可以看出，在K=3时颜色较近的最深色（深蓝）和中间色（深红）基本上被归并为一种颜色，因而分割效果失真.从图5可以看出,K=4时候人为地增加了一种不必要的颜色，而且每个线圈中心的杂色影响更加明显，所以K-均值聚类算法对于纬编提花针织物的自动分割和识别是一种不理想的方法.2.2阈值分割算法阈值分割算法的历史很久，现已提出了大量的算法.简单说来，对灰度图像的取阈值分割就是先确定一个处于图像灰度取值范围之中的灰度阈值，然后将图像中各个像素的灰度值都与这个阈值相比较，并根据比较结果将对应的像素（分割）划为两类：像素的灰度值大于阈值的为一类，像素的灰度值小于阈值的为一类（灰度值等于阈值的像素可归入这两类之一）.这两类像素一般分属图像中的两类区域，所以对像素根据阈值分类达到了区域分割的目的. 由此可以得出阈值分割的一般步骤：(1) 确定阈值；(2) 将像素值和阈值比较；(3) 把像素归类. 与灰度图像不一致的是，如果采用彩色图像分割，建立一个直方图，那么它只能够表示一个三维的数组，要用这个数组来确定划分的阈值是比较困难的，Kurugollu提出了一种直方图多阈值的彩色图像分割方法3.该方法直接采用RGB色彩空间，对应地来建立三个空间向量IRG、IRB、IGB，针对这三个向量来建立直方图，进行平滑和抽取以后，通过顶点择取的方法来为每个直方图选取一个阈值，分别进行分割以后再进行融合，得到最终的分割结果. 笔者根据阈值分割的一般原理，针对灰度级别的纬编提花针织物图像，利用VC+6.0编程实现了3种方法的阈值分割效果，如图6、图7、图8所示. 图6 迭代阈值分割 图7阈值35峰谷阈值分割 Fig.6 Iterative threshold segmentation Fig.7 Peak-to-valley threshold segmentation of value=35在该织物的色彩分割中，由图6可见，采取迭代阈值分割，会将最深色（深蓝）和中间色（深红）强制转化为黑色，而使最浅色（白色）转成全白，效果十分不理想.由图7可见，取阈值为35的峰谷阈值分割，使分割结果严重失真.由图8可见，手动取阈值100的半阈值分割将灰度值小于100的背景归一化到全白，而保持最深色（深蓝）和中间色（深红）的颜色和纹理不变，这样能有效去除背景色上的杂色和噪点.但根据分割结果只能说半阈值分割是一种有效的前处理方法，而不是有效的颜色分割算法.阈值分割算法的局限性也比较明显，首先它单独基于颜色分割得到的区域是不完整的，而且运用于较复杂的织物图像，它的波峰和波谷不会很明显，因此很难人为取定.图8 阈值100半阈值分割Fig.8 Half threshold segmentation of value=1002.3均值漂移算法 在30年以前，均值漂移的方法就已经被引入到图像处理和模式识别上了，但是长期以来都没有被广泛地关注.一直到1995年，Chen Y才在他的一篇文章中讨论了均值漂移算法的优点，而且叙述了其在图像分割领域的可行性4. 均值漂移聚类算法是对特征空间的聚类，所以我们舍弃不适用的RGB色彩空间，采用L、U、V均匀彩色模型6.在此空间中，代表亮度，和代表色差，色彩之间的差异可以用欧几里德距离来表示：(4)的值越小，就说明两点之间的颜色差异越小.如果再结合特定点在图像中的平面位置（x，y），可以重建一个5维的函数（L，U，V，x，y）来表达每一个特定的点. 简单地说，均值漂移是一种基于核密度估计的算法，它和所有的聚类算法一样是要求对空间里面的所有点进行归类7.它总是沿着密度增大的方向进行漂移，它的核函数可以写成多种格式，采用一般的Epanechnikov格式如下： (5)它的漂移向量和核密度梯度之间有如下的关系5： (6)式中h是指定的带宽，c是定义的常数，在将算法实用化的时候都可以人为指定h和c的值，在本实验中它们分别代表空间和色彩的漂移量，而是核密度估计的梯度表达式： (7) 均值漂移算法设计在某个特定的超球体Sh(x)内进行搜索， Sh(x)表示d维特征空间半径为空间漂移量h，体积为hdcd的超球体，其中心在，包含nx个空间点，本实验中，因为已经确定了一个5维的函数（L，U，V，x，y）来表示每一个特定的点x，所以d为确定值5，再通过指定空间漂移量h和色彩漂移量c的值，就可以对每一个区域内的点x进行运算.从式(6)可以知道，漂移向量和核密度梯度的方向是一致的，所以搜索漂移轨迹的时候只要算出就可相应得到，下式(8)为确定的迭代表达式： (8) 综上所述，首先针对纬编提花针织物的彩色图像建立5维空间模型，5维空间中的每一个点都表征了它在图像中的所有属性：包括它的坐标和色彩.因此，只要将这个5维的空间进行漂移聚类，再将聚类的结果反映到图像上，就得到了最终的结果.鉴于上述两个理论，均值漂移算法对纬编提花针织物图像分割的一般步骤如下：(1) 从图像的第一个中心，开始遍历整个图像，以确定均值漂移过程中不断变化的超球体中心；(2) 确定的超球体中计算窗体中心的偏移向量，直到满足设定的收敛条件；(3) 将收敛的色彩赋值给当前空间点；(4) 利用漂移向量对核窗口进行下一步的漂移.基于均值漂移的一般原理，利用VC+6.0的编程，实现了对纬编提花针织物图像的分割运算.在计算过程中，可以为空间域和色彩域取不同的值，采取不同的空间域(h)值和色彩域(c)值，分割的效果也不尽相同.在分割过程中，先要选定一个空间域h来保证空间上的连续性，然后根据选定的空间域值h来对此区域中包含的像素点进行处理，确保其颜色信息的一致性.经过这些步骤以后，空间上相邻、色彩上相似的点就被归并到一类当中，从而完成了对纬编提花针织物图像的分割.选定同一空间域(h)为8，而色彩域(c)分别为8、16、24的条件下，进行纬编提花针织物图像的分割，其效果如图9所示. (a) h8c8 (b) h8c16 (c) h8c24图9 相同空间域不同色彩域均值漂移分割图Fig.9 Mean-shift image segmentation with same space ranges and different color ranges 均值漂移聚类算法在纬编提花针织物图像的像素空间搜索下一个漂移轨迹点时，需要同时设置停止搜索的条件，当漂移向量小于给定值时停止漂移.这使得针织物图像在高密度区域产生模糊效应而去除小色块的干扰，而在高密度区域一般都是该织物受噪点和不必要杂色干扰最多的区域，这对带有许多杂色干扰的针织物是十分有用的.从图9可知，随着色彩漂移量的不断增加，干扰因素也越来越模糊直至消失，但是色彩漂移超过一定量的时候，会使分割结果失真.图9(a)中色彩域取8，它的色彩漂移程度比较小，线圈中点的杂色仍然会有影响，效果不是太理想；图9(b)中色彩域取16，适度的色彩漂移使杂色影响基本上消失，而且保留了线圈的色彩和形状要素，分割效果十分显著；而图9(c)中色彩域取到24时分割图像已开始失真，左上角的白色单元开始消失，效果不理想.2.4结果比较 在实验过程中，对比这3种分割方式，可以得出它们的优劣点： (1) 对K-均值聚类分割而言，如果纬编提花针织物图像非常理想化，经过必要的去噪、去杂色以及色彩范围的缩减，再在实验过程中多次调整初次聚类的中心来进行分割，还是能够满足应用的需求，但这与计算机自动分割的差距较大. (2) 对阈值分割而言，人为地去选定一个阈值来进行半阈值分割，能够实现背景色的分离，却达不到色彩分割要求，而且在阈值控制不易以及色彩偏多的情况下不适合，最主要的是与纬编提花针织物色彩分割的要求相背离. (3) 相对来说，均值漂移分割对本文目标的实现是最适合的，它既能够满足在全彩色下分割的需求，计算量也得到了较好的控制.而且，漂移过程中去除织物上的杂色是它理想化的功能.当然，这种方法也有缺点，比如对不同线圈密度需要人为地来调整空间和色彩的区域范围值，但只要反复试验几次便可以趋近于最优值.除了本文之外，笔者还应用均值漂移分割方法对另外几种2至5色纬编提花针织物图像进行了试验，也取得了较高的彩色花型识别率. 尽管有利有弊，但是瑕不掩瑜，基于均值漂移的分割方法最终被确定为实现彩色纬编针织物图像自动分割的最佳方案.3 彩色意匠图的生成3.1织物纵密和横密的确定 利用二维傅里叶变换(FFT)或者小波变换的图像处理方法，对灰度级别单色针织物密度的自动测量已经有了较多的研究.但是对于颜色数目较多的纬编提花针织物，目前还没有通过图像处理自动测量其密度的成熟方法，所以笔者对均值漂移算法分割后的纬编提花针织物图像图9(b)，采取了人工方法来界定其密度，从而自动画出意匠图的方格线，结果如图10所示.3.2 彩色意匠图的生成 在意匠图的方格线确定后，绘制意匠图的最简单的方法，就是根据带方格的效果图10，取每一个方格中心点的色彩值来自动填充本方格的色彩8.图11是在Matlab 6.01编程环境下实现的织物意匠图的自动填充绘制.由于针织物本身的特殊性，难免会发生意匠图的错位和跳色，图11的跳色现象有了很好的控制.但是由于原始织物的线圈横列和纵行并非严格垂直，所以经过分割和绘制后，图11中右下方的花纹图案比左下方的花纹图案下移了一个横列位置. 图10 意匠图方格线划分 11 最终彩色意匠图Fig.10 Squared line division of notation Fig.11 Final colored notation4 结语 利用数码相机获取了三色纬编提花针织物的原始图像，在对图像进行必要的去噪处理后，用均值漂移算法来进行色彩的聚类和分割，既去除织物图片上的杂色，又保留了原来图像上的色彩信息.对截取的针织物图像进行分色处理后，取分色以后每个线圈中心点的颜色来填充该线圈，即得到与均值漂移分割的织物图像一致的彩色意匠图.要实现自动生成与原始纬编提花针织物完全一致的意匠图，还需要解决该织物密度的自动测量，以及线圈横列和纵行不垂直的矫正等问题.参考文献1 YANG C K, TSAI W H. Reduction of Color Space Dimensionality by M