基于K－均值聚类和分水岭算法的PCB彩色图像分割

惠鹏飞，苗凤娟，陶佰睿，王成琳

（齐齐哈尔大学通信与电子工程学院，黑龙江齐齐哈尔 161006）

基于K－均值聚类和分水岭算法的PCB彩色图像分割

惠鹏飞，苗凤娟，陶佰睿，王成琳

（齐齐哈尔大学通信与电子工程学院，黑龙江齐齐哈尔 161006）

针对光学检测印刷电路板（PCB）时需要进行图像分割的问题，提出一种结合K－均值聚类算法的分水岭算法，用于PCB彩色图像分割，即首先将PCB彩色图像聚类，分成不同的颜色区域，按照不同区域进行分水岭分割，最后，将分割线透明的加在原始图像上，完成分割。实验表明，本文提出的算法可以分割PCB彩色图像，并且分割效果好。

PCB;分水岭算法;彩色图像分割;聚类

印刷电路板（Printed Circuit Board，PCB）是电子零件彼此连接沟通的支撑物，它质量的好坏直接影响电子产品的正常工作，所以对PCB的检测是必要的。近年来，利用光学手段获取PCB表面图像，并通过图像处理的方法进行检验、分析和判断的光学检测PCB技术已成为研究的热点［1－4］。图像分割则是进行光学检测的首要步骤，其成功与否直接影响到后续的检测识别工作。现有的PCB图像分割算法有:文献［5］提出一种将PCB图像分割转化为阈值最优问题，进而利用改进遗传算法求解图像最优问题的算法;文献［6］提出了基于改进分水岭的PCB图像分割算法;文献［7］对PCB图像利用模糊集和Otsu理论进行分割。上述算法虽能成功地对PCB图像进行分割，但都只针对灰度图像，丢失了原始图像的色彩信息，PCB彩色图像的分割算法却未见提及。于是本文提出一种结合K－均值聚类算法的分水岭算法，用于PCB彩色图像分割。

1 K－均值聚类算法

聚类是对数据空间中数据对象进行分类，位于同一类中的数据对象之间的相似度较大，而位于不同类之间的数据对象差异度较大。聚类是一种无监督学习，能自动对数据集进行划分。常见的聚类算法有:K－means，DBSCAN，CURE等算法。K－means即K－均值聚类，该算法确定的K个划分到达平方误差最小，当聚类是密集的，且类与类之间区别明显时，效果较好。并且对于处理大数据集，该算法是相对可伸缩和高效的，计算的复杂度为O（NKt），其中N是数据对象的数目，t是迭代的次数，具体步骤如下:

第一步，选K个初始聚类中心，z1（1），z2（1），…，zK（1），其中括号内的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。

第二步，逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj（1）。假设i=j时，则zi（k）=zj（k），其中k为迭代运算的次序号，第一次迭代k=1，Sj表示第j个聚类，其聚类中心为zj。

第三步，计算各个聚类中心的新的向量值zj（k+1），j=1，2，…，K，求各聚类域中所包含样本的均值向量:其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小:在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K－均值算法。

第四步，若zi（k+1）≠zj（k），j=1，2，…，K，则返回第二步，将模式样本逐个重新分类，重复迭代运算;若zi（k+1）=zj（k），j=1，2，…，K，则算法收敛，计算结束。

2 本文算法

本文提出的结合K－均值聚类的分水岭算法，目的是对已经聚类的颜色目标进行分割，从而完成PCB彩色图像的分割。

2.1 分水岭算法

分水岭分割方法，是一种基于拓扑理论的数学形态学的分割方法，其基本思想是把图像看作是测地学上的拓扑地貌，图像中每一点像素的灰度值表示该点的海拔高度，每一个局部极小值及其影响区域称为集水盆，而集水盆的边界则形成分水岭。分水岭的概念和形成可以通过模拟浸入过程来说明。在每一个局部极小值表面，刺穿一个小孔，然后把整个模型慢慢浸入水中，随着浸入的加深，每一个局部极小值的影响域慢慢向外扩展，在两个集水盆汇合处构筑大坝，即形成分水岭。对于分水岭变换（Watershed by Immersion），令f:D是一幅灰度图像，它的最大和最小灰度值为h_max和h_min。定义一个从h_min到h_max的水位h不断递增的递归过程。在这个过程中每个与不同的局部最小相关的汇水盆地都不断扩展，定义X（h）记作在水位h时候汇水盆地的集合的并。在h+1层，一个连通分量T（h+1）或者是一个新的局部最小，或者是一个已经存在的X（h）中的一个盆地的扩展。对于后者，按邻接关系计算高度为h+1的每一个点与各汇水盆地的距离。如果1个点与2个以上的盆地等距离，则它不属于任何盆地，否则它属于与它距离最近的盆地。这样从而产生新的X（h+1）。把在高度h出现的局部最小记作MIN（h）。把Y（h+1，X（h））记作高度为h+1同时属于X（h）的点的集合。

分水岭变换Watershed（f）就是X（h_max）的补集。

2.2 结合K－均值聚类的分水岭算法

2.2.1 颜色空间选择

选择合适的颜色空间是成功进行彩色图像分割的首要环节，计算机处理分析系统接收到的PCB彩色图像是在RGB颜色空间中表示的。由于彩色显示器采用红、绿和蓝来生成目标颜色，所以RGB颜色空间是计算机图形学最通常的选择，这样可以简化系统的构架与设计。RGB颜色空间用三维的笛卡尔坐标系统来表示，如图1所示。

图1 RGB颜色空间图

其中，每个顶点的三色叠加值如表1所示。

表1 RGB颜色表

可见RGB颜色空间的色彩是比较丰富的，同时还是显示器硬件系统的默认颜色空间，做图像处理时的速度比其他颜色空间快，所以本文选择RGB颜色空间。

2.2.2 图像分割算法

将PCB彩色图像在RGB颜色空间中分别提取R、G、B三个灰度图像。将每幅灰度图像的像素值考虑成一组二维数学矩阵，在其中随机选取2个像素值x（i，j）和y（i，j）作为初始聚类中心，根据下列公式对剩余的像素值进行聚类

其中，当z（i，j）取到x（i，j）或y（i，j）时，上述公式中D为0，当z（i，j）为异于x（i，j）和y（i，j）的像素值时，设置D0为0.05，验证下列公式

设置阈值T，对T进行取值，满足上述公式则完成三幅灰度图像的聚类。对每幅聚类后的灰度图像进行分水岭分割，即对已经聚类好的灰度图像，利用公式（1）寻找相同高度的像素值，对分水岭变换后的三幅灰度图像进行单通道图像整合，合成RGB空间的彩色图像，即完成PCB彩色图像的分割。算法流程如图2所示。

3 实验与分析

利用本文提出的算法，在MATLAB 7.1环境下，对用CCD摄像机获取的PCB彩色图像进行仿真，如图3所示，可以看到，本文提出的算法可以很好地分割PCB彩色图像，分割清晰，PCB的结构保持完整，同时由于所采取的方法均为无监督算法，所以整体程序所消耗的时间较短，仅为7.254 s，说明了本文算法的高效性。

图2 算法流程图

4 结论

本文成功地分割了PCB彩色图像，提出了结合聚类算法的分水岭算法，通过实验仿真可以看到，所提出的算法可以清晰地分割PCB彩色图像，为之后的PCB检测工作奠定了基础。

图3 实验仿真图

:

［1］杜颜颜，杨帆，王晓颖.一种彩色PCB图像的边缘检测算法研究［J］.电视技术，2011，35（13）:112－115.

［2］李刚，韩建国.PCB图像检测中阈值化分割的研究［J］.北京化工大学学报，2002，29（4）:72－74.

［3］赵晓霞，王明泉，李高亮.一种基于偏微分方程的PCB图像增强方法［J］.电视技术，2011，36（3）:33－35.

［4］孙晓霞，熊红云.PCB检测系统中的图像预处理［J］.中国科技信息，2007，30（22）:116－117.

［5］曾成，赵锡钧，徐欣，等.PCB检测中图像分割技术研究［J］.传感器与微系统，2011，30（2）:26－28.

［6］曾歆懿，章云，季秀霞，等.基于分水岭变换的PCB图像分割［J］.质量工程卷，2007，20（1）:22－26.

［7］张鹏程，刘若钧，张记龙，等.基于模糊集和Otsu理论的PCB图像分割算法［J］.中北大学学报:自然科学版，2009，30（4）:386－389.

苗凤娟（1982— ），博士，主研传感器;

陶佰睿（1972— ），博士，主研传感器;

王成琳（1986— ），硕士生，主研图像处理。

PCB Color Image Segmentation Based on K－means Cluster and Watershed Algorithm

HUI Pengfei，MIAO Fengjuan，TAO Bairui，WANG Chenglin

（Communication and Electronic Engineering Institute，Qiqihar University，Heilongjiang Qiqihaer 161006，China）

According to the problem of optical detection printed circuit board（PCB）need image segmentation，a kind of combination clustering algorithm and watershed algorithm in PCB color image segmentation algorithm is put forward.Firstly，the PCB color image is clustered to divide into different color area，then the different area is segmented by watershed segmentation algorithm.At last，the cut－off rule transparent is added to the original image，the segmentation is completed.Experiments show that the proposed algorithm can split PCB color image，and segmentation effect is good.

PCB;watershed algorithm;color image segmentation;clustering

TN911.73;TP391.41

A

【本文献信息】惠鹏飞，苗凤娟，陶佰睿，等.基于K－均值聚类和分水岭算法的PCB彩色图像分割［J］.电视技术，2013，37（13）.

国家自然科学基金项目（61204127）;齐齐哈尔市科技局工业攻关项目（GYGG－201109）;齐齐哈尔大学青年教师科研启动支持计划项目（2010k－M03）;黑龙江省青年基金项目（QC2011C092）

惠鹏飞（1980— ），硕士，主研信息检测，电磁场与微波技术;

责任编辑:魏雨博

2012－10－31