基于粒子群的彩色印刷品图像分层搜索定位算法

李 强,耿云逸,吴福培,2,李昇平,2,阳 春,陈 练

(1.汕头大学工学院机电系,广东 汕头 515063;2.汕头轻工装备研究院,广东 汕头 515063)

0 引言

随着机器视觉技术在印刷品检测中的推广应用,印刷的速度和要求越来越高,需要对常见的印刷品表面缺陷,如飞墨、划痕、刀丝、漏印等进行精确快速检测.检测过程包括图像获取、图像处理、目标定位、检测与识别,而作为中间环节的目标定位在很大程度上制约着缺陷检测的速度,定位质量的高低也直接影响后续误判的概率.另一方面,印刷图像向宽幅面、多色彩的方向发展,图像本身数据量的增加也对检测的速度提出了挑战.为了适应生产的需要,提高产品质量,目标定位作为检测的一个前提显得越来越重要.

受复杂生产环境、振动、噪声、张力变化、传输信号中断等因素的影响,给图像精确定位带来了难点,算法本身的不理想也增加了搜索的负担.为了提高定位的时间,实现模板的快速匹配,文献[5]对模板图像进行抽样提取匹配点,采用遗传算法的非遍历机制,迅速收敛到全局最优解,减少匹配过程的计算量.文献[7]借助模拟退火算法的思想,提出了一种尺度参数可变的散乱点匹配,通过曲线约束进行控制点筛选达到更广泛的收敛区间和更高的定位精度.这些方法在提高搜索效率上有一定积极作用,但是面对印刷品高速、高精检测的要求时,多数算法的速度会遇到瓶颈,匹配速度和精度不可均衡,很难满足生产的要求.针对这一问题,本文首先采用图像金字塔(图1),对图像进行分层预处理,从计算效率和存储来看,可以快速生成.其次,由于分层后可以确定每层图像的像素点的个数,因此建立了各层基于特征点的目标函数.最后采用粒子群搜索算法进行分层迭代搜寻,由粗到细求解各层最优匹配参数,相比直接对整幅图像进行搜索,该方法计算简单、收敛快,精度高.

图1 图像金字塔

1 图像分层预处理

1.1 图像分层预处理

图像金字塔化一般包括两个步骤:首先,对图像用低通滤波器进行平滑;其次,对平滑后的图像在横纵两个方向按固定比例(常为0.5)进行抽样.对任意一幅图像,通过一个kXk的卷积模板加权平均为新的像素构成的第二级图像,再在第二级图像的基础上构成第三级图像,持续下去构成一系列的序列.像素大小为mXn的参考模板序列和像素大小为MXN的待测图像序列分别表示为:

其中,w=1,2,…,p,p是图像金字塔的层数,具体的分层层数的选择,根据模板图像和待匹配的图像的大小以及k的大小而定.图2表示的是图像经过提取边缘轮后,由高斯低通滤波器进行平滑,生成四层金字塔:

图2"铁观音"分层

图2 所示为目标图像"铁观音"的边缘在不同层数下的边缘检测.由于金字塔的层数实际对应频率域的尺度选择,而多尺度表达随着尺度参数的增加冗余信息也变得更多.在第二层,边缘阴影比较清晰的突显出来;而第三层,由于经过两次平滑而导致边缘形状扭曲变形;而第四层是由第三层平滑得到,如果采用第四层图像对该图像结构进行定位和检测,将会导致更严重的偏差,由此可认为该层不适合定位和检测,是多余的信息.因此,选择合适的层数或尺度因子对目标图像的定位与检测至关重要.

1.2 搜索空间

图3中,T是参考模板,点个数为mXn,si,j是待测图像,大小为MXN;坐标(i,j)表示模板覆盖被搜索图的左上角坐标;p表示图像分层层数.则由分层预处理可知:第w层的搜索范围:

图3 分层图

2 印刷品图像的匹配模型

2.1 点匹配模型

目标定位过程中需要考虑的参数有:平移

参数,旋转参数,尺度因子等;用图像的仿射变换来解决图像间的几何位置差别.若原图像素中某一点坐标为(x1,y1),经过仿射变换后的坐标为(x2,y2),则:

可用向量和矩阵表示为P2=T+sRP1.上式中P2,P1为坐标,T是平移向量,tx、ty为欧式空间x方向平移分量、y方向平移分量,s是尺度或比例因子,θ是旋转因子,R为旋转矩阵.为了确定变化后的图像与标准图像间差异的最小位置,相似性度量采用距离函数的形式:

式中,f(x1,y1)是参考图像在(x1,y1)的像素点,f(x2,y2)是待匹配图像在(x2,y2)的像素点.本文将模板和待测图像进行分层后,可知在第w层上像素点个数分别为:.从而建立像素点的分层匹配模型为:

2.2 粒子群算法(PSO)

粒子群算法是介于遗传算法和进化规划之间的一种群体智能算法,由于其随机搜索的本质,不容易陷入局部最优解,基于适合度概念的进化特征又保证了算法的快速性.在粒子群算法中,每个个体称为一个"粒子",每个粒子都具有位置矢量和速度矢量,而位置矢量代表问题的一个可能的解.PSO中涉及的主要概念如下.

zi=(zi1,zi2,…,ziD),即群体由m个粒子构成,zi为第i个粒子(i=1,2,…,m)的D维位置矢量,根据事先设定的适应值函数计算zi当前的适应值.vi=(vi1,vi2,…,viD)为粒子的飞行速度,即粒子移动的距离.pi=(pi1,pi2,…,pid,…,piD)为单个粒子搜索到的最优位置.pg=(pg1,pg2,…,pgd,…,pgD)为整个粒子群迄今为止搜索到的最优位置.如图4为粒子调整位置的示意图.

图4中随机分配3个粒子,求解三个匹配参数,粒子维数为3.以粒子1为例,首先随机分配起始搜寻位置和粒子速度v1,计算适应值:z11.粒子2、粒子3进行相同的操作,将三个个体极值中的适应度最优个体的位置和适应值记录到全局极值中.然后,更新速度和位置,v2是按公式(6)更新后的速度,是按公式(7)调整后的下一个搜索点.其中,vpi记录搜索到最佳位置处单个粒子的速度,vpg记录搜索到最佳位置处整个粒子的速度.在迭代过程中,粒子反复跟踪个体和群体的最佳适应值不断调整自己的位置,从而得到最优解.粒子根据以下式子更新速度和位置:

图4 粒子群迭代过

其中,i=1,2,…,m;d=1,2,…,D;k是迭代次数,γ是惯性权重因子;r1,r2是[0,1]

之间的随机数,用来保持群体的多样性;c1,c2是学习因子.

2.3 基于粒子群的分层搜索

在高速印刷中,在印刷张力的作用下纸张保持相对稳定连续的运动,此时尺度或比例的变化极小,可假设为常量,因此s取1.公式(5)简化为:该问题可以描述为:以适应度评价函数D=D(T,R,w)为判决基准下,在搜索空间为公式(2)各层上(第w层)找到最佳匹配点的位置时求解匹配参数的值.因此,算法描述如下:

其中,w=1,2,…,p表示金字塔的第w层,ε为设置的门限值.当第w层搜索结束,以取得全局最优解的粒子位置作为下一层的初始搜索位置,缩小了随机分配搜寻的范围.其次,由于每个粒子具有向全局最优解接近的趋向,可以很好的避免搜索中的局部最优解,尤其是受到噪声、振动干扰的突变像素所在位置粒子.

图5 算法流程图

3 实验结果及分析

实验平台为Pentium(R)D CPU 2.20GH和2GB内存,在机器视觉处理软件Halcon下完成.课题在卷筒纸印刷中要求表面缺陷的最小检测精度为0.2 mm,检测速度不低于200 m/min,印刷纸的最大幅宽为1020 mm,相当于每秒检测5张1020X720 mm的单张纸.首先,确定初始化粒子个数m=30,随机分布到待测图像上,图像长宽为361X 160 mm,像素个数为1024X454,匹配模板像素大小为74X84,采用3X3卷积模板对图像分层.其次,结合最小精度和像素分辨率选定恰当的阈值作为算法迭代的终止条件.最后,由定位参数对待测图像进行仿射变换实现位置校正.实验流程如图6所示.

为了获取标准图像,程序连续采集25张印刷品样品图像,通过在线学习训练得到如图7(a)所示的效果图.如图7(b)所示待测图像总共有300张,分别被处理成不同的旋转角度:1°,2°,4°,6°.

图6 实验流程图

图7 实验图像

在图7(b)中,待测图像存在旋转偏移,偏移角度为2°,并且有飞墨.在选择ROI区域后,首先提取区域边缘特征建立形状模板,然后模板进行分层,本实验层数为3层,见图7(c).采用图6中的粒子初始参数,对待测图像分层搜索,如图7(d)右侧与下侧边缘,实验结果显示图像像素的位置整体被校正.

3.1 校正偏差和分层后时间的对比

实验统计了如表1所示的不同偏移角度下的平均时间和角度对比.同时,测试了如表2所示的不同分层层数下的时间.

表1 不同角度下的偏差和平均时间

表1表示分层数为3层时的角度偏差对比,角度偏移相当于同时存在水平偏移和垂直偏移.算法搜索的角度与实际值存在一定误差,主要原因有二:一是由于粒子群算法本身在迭代过程的计算误差不断累积产生的;其次是对模板进行边缘匹配时,边界点或噪声点对待测图像的干扰产生的伪边缘造成边缘检测误差.试验中对连续图像进行了多次测试,统计结果显示平均校正偏差不超过0.1°,即水平误差达到0.999个像素,垂直误差达到0.017个像素,校正精度很高.

表2 不同分层下的平均时间

表2表示单层数搜索与多层搜索的时间对比,对单层图像采用粒子群平均时间超过1s,在相同的参数下对分层后的图像采用粒子群搜索时间大幅降低.当分层层数为3层,最大角度偏移为6°时,印刷品的校正时间仅仅占检测时间的27.66%.这是因为,分层前单层图像和模板匹配时的计算量为(1024-74)X(454-83)=352450,图像分3层后,最大分辨率图层下的搜索量降为352450÷9=39161,全部图层的数据量与分层前数据量相比降低了3倍.对于高精度凹印机,印刷品在印刷位置上是相对平稳的,在印刷张力的作用下图像偏移的角度要低于2°,实际中匹配的时间要低于测试的时间.

3.2 与其他算法时间对比

按本文算法在搜索时间上,对文献所提出的几种算法进行了对比,在相同的硬件条件下,采用相同尺寸的图片和模板,分层层数为3层,对300张待测印刷品的平均匹配时间进行了统计,如表3:

表3 几种算法的性能比较

从表3可知,在搜索时间上,文献[13]和文献[14]分别采用禁忌搜索和粒子群算法,相对来说提高了速度,文献[5]对单层模板进行抽样,采用遗传算法进行非遍历机制,相比来说收敛时间更快.本文算法平均时间最低,达到11.7 ms,可知对图像和模板进行多层抽样,结合粒子群搜索的特性更能提高算法的实时性.

在粒子群搜索中,粒子在图像中搜索最佳位置的过程是跟随当前单个粒子找到的最好位置和群体中的最好位置,是一种单项的信息共享机制.相比遗传算法的种群向比较均匀的最优区域移动,粒子群的所有粒子加速向自身最好位置靠近的特性使得收敛速度较快;由于金字塔多分辨率表达的每一层分辨率都要减少固定比率,低分辨率下维数小、数据量小.所以在最高层搜索目标时,可快速定位目标图像的位置,下一层图像以上一层图像的最佳点开始搜索定位目标图像,可避免对整层进行匹配计算量大的问题.因此,该方法可以明显的降低匹配时间,应用于印刷品全画面在线检测系统,实时性和精度都较高.

4 结论

本文建立了印刷品图像的分层匹配模型,描述了基于粒子群的搜索策略.在此基础上,提出了一种基于粒子群算法的分层搜索定位方法,解决了工程实践中因图像宽幅面、数据量大而带来的定位时间消耗过大的问题.实验结果表明,该方法可以很好的对印刷品进行位置校正,校正偏差平均不超过0.1°,对最大偏移角度为6°的图像搜索时间高达12.6 ms,仅占检测时间的27.66%,可以实现对印刷品的准确、快速定位.

[1]Glukman J.Scale Variant Image Pyramids[J]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2006,1(10):1069-1075.

[2]Klein S,Staring M,Pluim J P W.Evaluation of optimization methods for nonrigid medical image registration using mutual information and B-splines[J]. IEEE Transactions on Image Processing,2007,16(12):2879-2890.

[3]Wei X L,Zhang H,Ma Y J,et al.An optimization algorithm of image mosaic based on maximum mutual information[J].Journal of Optoelectronics Laser,2009,20(10):1399-1402.

[4]刘建伟,梁晋,梁新合,等.大尺寸工业视觉测量系统[J].光学精密工程,2010,18(1):127-133.

[5]姜凯,陈海霞,刘立峰,等.基于模板抽样的快速图像匹配算法[J].光学精密工程,2004,12(3):312-315.

[6]梁鹏,何俊诗,黎绍发.基于多尺度LBP金字塔特征的分类算法[J].计算机工程,2011,37(8):167-168.

[7]魏阳杰,吴成东,董再励.基于亚像素图像块匹配方法的压电陶瓷驱动特性测量[J].机械工程学报,2010,46(17):152-158.

[8]林洪彬,刘彬,张玉存.逆向工程中点散乱云变尺度配准算法研究[J].机械工程学报,2011,47(14):2-6.

[9]葛宝臻,马云峰,魏耀林.求解粒子群粒度分布的改进Projection算法[J].光学精密工程,2012,20(1):198-203.

[10]吴福培,张宪民.印刷电路板无铅焊点假焊的检测[J].光学精密工程,2011,19(3):698-702.

[11]李博,杨丹,邓林.移动机器人闭环检测的视觉字典树金字塔TF-IDF得分匹配方法[J].自动化学报,2011,37(6):666-673.

[12]王君本,卢选民,贺兆.一种基于鲁棒特征的匹配算法[J].计算机工程与科学,2011,33(2):112-117.

[13]程红,陈文剑.禁忌搜索算法在图像匹配中的应用研究[J].地理与地理信息科学,2011,27(6):33~35.

[14]王维真,熊义军,魏开平,等.基于粒子群算法的灰度相关图像匹配技术[J].计算机工程与应用,2010,46(12):169-171.