基于改进滴水算法的芯片图像粘连字符分割

陈慧敏 张合生 朱晓锦

(上海大学机电工程与自动化学院 上海 200444)

0 引 言

芯片表面字符是辨别封装相同但是功能不同的芯片的唯一方式，所以在进行集成电路测试前，需要对IC芯片表面的制造商名称、产品编号、序列号等字符进行识别[1]。能否正确识别一个字符，字符分割起着重要的作用，因为在识别前需要将字符从文字图像中准确地分离出来[2]。但是由于工业环境复杂，所采集的图像普遍存在亮度对比度较低、字符断裂和噪声干扰等问题。在对芯片图像进行预处理时可能会造成芯片字符标识粘连。所以，在识别之前必须先对粘连字符进行分割。

针对粘连字符分割，许多学者进行研究并取得了有益的成果。Ma等[3]针对藏文历史文献图像中的粘连字符，使用改进的harris角点检测算法来提取粘连区域分割点，准确率达到95%，但并不适用于芯片图像。Farulla等[4]提出一种新的模糊策略并结合粘连字符的三个特点，在噪声情况下也能进行较好的分割，但在对于笔画重叠的字符可能无法实现准确分割。Zaw等[5]提出了一种基于区域定位的粘连字符分割技术，使用缅甸文字的孔洞数、上下分量和左右分量等特征进行分割。姜燕[6]引入种子点概念，并用下种子点产生引力，使得水滴在合力作用下运动，但是其只能分割固定个数的字符。李兴国等[7]将字符的宽度统计值和竖直投影直方图中的投影极小值点相结合找到分割点，对验证码粘连字符分割取得了较好的效果，对芯片图像中一些宽度差别较大的字符无法正确分割。Tang等[8]结合二叉树和字符宽度选取分割最优路径，有效降低了分割位置的不确定性，但容易受到伪谷底的影响。

本文使用一种基于改进滴水算法的方法，对芯片图像粘连字符进行分割。利用字符宽度、分割点方差和上下分割点对应关系来筛选垂直投影、上轮廓和下轮廓的局部极小值，以此提高滴水算法起始点的正确率；考虑水滴的不同位置受到种子点(即下分割点)的影响不同，因此定义不同的水滴滴落规则，得到更为精准的分割。实际测试表明，本文方法可有效解决芯片图像的字符粘连问题，并且在分割精准度上拥有良好的表现。

1 滴水算法

在常见的粘连字符分割方法中，滴水算法相对较为简单且有效，并且在分割粘连数字串上拥有较好的效果，其基本原理是模拟水滴在重力的作用下从高处向下滴落的过程来对粘连字符进行切分[9]。水滴从粘连字符串的顶端沿轮廓向下或水平滴落，当水滴落入字符轮廓的凹陷处时，水滴会融入字符笔画中，穿透笔画继续向下滑落。在此过程中，水滴经过的轨迹就构成了粘连字符分割的路径。

滴水算法主要受三个因素影响，分别是起始滴落点、水滴运动规则和运动方向。图1(a)中n0表示为水滴当前像素点位置，其下一步的水滴位置由其左右的两个像素点和下方的三个像素点共同决定。

图1 滴水算法原理图

一组滴水算法根据水滴下落方向的不同会有不同的分割路径[10]，以其中的Top-Left方法为例，水滴的运动规则如图1(b)所示，其中w表示白色像素，b表示黑色像素，*表示既可能是白色像素，也可能是黑色像素。以图1(b)中的(1)为例，当前水滴位置相邻像素都为白色时，水滴将会向下滴落。当水滴落入字符轮廓的凹陷处时，情况4和情况5循环交替出现，即水滴在水平左右来回移动。因此传统的滴水算法起始点选取困难并且容易造成断裂字符[11]。

文献[12]中，对水滴算法进行了数学描述。设当前水滴坐标为(xi,yi)，水滴路径为T，则T(xi+1,yi+1)=f(xi,yi,Wi),其中i=0,1,2,…N,(xi+1,yi+1)表示为下个水滴坐标位置，Wi是水滴在当前位置上的重力势能的衡量。Wi的值由式(1)所决定。

(1)

式中：zj表示nj点的像素值，白色像素为1,黑色像素为0。Wj表示nj点为下一个滴落点权重大小，Wj=6-j。

2 改进的滴水算法

传统的滴水算法的起点选择是通过对字符图像从上到下从左到右扫描每一行像素，第一个满足(…1*0…01…)分布的白色像素点为水滴算法的起点[13]。其中，1表示白色像素点，0表示黑色像素点，*表示既可以是白色相似点也可以是黑色像素点。上述方式选择的初始滴落点可能处于字符的凹陷处或者是字符内部，这将会造成错误分割。因此本文利用垂直投影和上下轮廓选出候选滴落点，再基于字符宽度、双向路径方差和上下点一一对应关系筛选得到初始滴落点。

对芯片粘连字符的分割，首先检测轮廓连通域，并对其进行分析，提取得到粘连字符。然后对粘连区域进行垂直投影，得到垂直投影直方图和上下轮廓图，三者相互印证得到分割候选点。利用预处理时得到的字符的最小宽度Dmin和最大宽度Dmax，对候选点进行第一次筛选；对第一次筛选后的分割点进行双向路径求方差，并进行第二次筛选；最后根据上下分割点对应关系，补齐或筛选得到有效分割点。以有效上分割点为改进的滴水算法的初始滴落点，以有效下分割点为算法终止点。然后根据水滴位置与种子点(即下分割点)之间的距离选择不同的滴落规则进行分割。对分割结果进行判断，若不满足单字符条件，则继续进行粘连分割。算法流程如图2所示。

图2 粘连字符分割流程

2.1 芯片图像预处理

分割可为两步：图像的预处理和字符的分割[8]，所以先对芯片图像进行预处理。工厂采集环境复杂，多数的芯片图像亮度和对比例都较低，因此先对图像进行对比度和亮度处理，然后将图片二值化；为了能够准确地得到字符宽度，将图片进行缩放处理；此时得到的图片可能存在许多噪声，噪声往往不利于字符分割，所以对图片进行中值滤波处理。最后，为了防止断裂字符影响字符宽度的统计对图片进行膨胀处理。芯片图像经过预处理后如图3所示。

图3 芯片图像预处理图

2.2 粘连区域提取

2.2.1 标准字符

本文需要利用字符宽度等先验信息对粘连字符进行分割，所以需要先统计标准字符的大小。随机选取部分芯片图像进行手工分割，排除过窄与过宽的字符后，统计分离出的字符宽高比，从而得到字符宽高比最小值Pmin和最大值Pmax。

对预处理后图像中的白色像素内容进行轮廓连通域检测，根据连通域作最小外接矩形框。对图像中的矩形框进行筛选，来定位目标图像中的字符部分。在所得矩形框中选择宽高比在[Pmin,Pmax]之间的矩形框视为标准字符，并对这些矩形框的宽高比、宽度和高度分别求均值。将这些作为该芯片图像的标准字符，参考值为：宽度Waver和高度Haver，最小字符宽度Dmin和最大字符宽度Dmax。

2.2.2 粘连区域提取

针对芯片中存在横竖混排字符的情况，采用对膨胀后的芯片图像进行轮廓连通域检测并根据连通域最小外接矩形框的面积、宽度和高度等先验条件进行行列矩形框判断，将相邻的行(或列)矩形框合并，最后得到行列字符。行列判断过程如图4(a)所示。对行字符(列字符旋转90度)进行水平投影分割后，使用最小外接矩形框方法将图片分割成若干区域。检测各个矩形框宽高比和宽度等信息与标准字符的参考值进行比较，可以很容易地合并断裂字符，并且提取出粘连字符区域。如图4(b)所示，经以上分析方法提取的芯片字符区域中包含部分粘连字符区域。

图4 粘连字符区域提取过程

2.3 字符分割点

2.3.1 分割候选点

文献[14]通过对粘连字符做垂直投影，统计投影值的局部极小值点以此得到初始滴落点。但是对于原本就存在凹陷的英文字符，此方法难以得到较为准确的初始滴落点。本文对垂直投影图和上下轮廓图分别求取局部极值，并相互印证，得到字符分割候选点。

先对二值图像进行反色处理后得到白底黑字的图像，再进行垂直投影得到图5(a)的垂直投影图。

图5 粘连字符区域垂直投影图和轮廓图

由字符每列的最高点组成的轮廓称之为上轮廓[15]，其定义如式(2)所示。

PT(i)=ET(i)i=1,2,…,M

(2)

式中：M表示图像总列数，PT(i)表示像素点坐标，ET(i)表示第i列从上到下遇到的第一个白色像素点的纵坐标值。若此列无白色像素点，则ET(i)=0。

同理，由字符每列的最低点组成的轮廓称之为下轮廓。其定义如式(3)所示。

PB(i)=EB(i)i=1,2,…，M

(3)

式中：PB(i)表示像素点坐标；EB(i)表示第i列从下到上遇到的第一个白色像素点的纵坐标值。若此列无白色像素点，则EB(i)=0。由此得到的上下轮廓图如图5中(b)和(c)所示。

对垂直投影图和上轮廓图求局部极大值，对下轮廓图求局部极小值。如果存在一个ε>0,使得对于任意满足|x-x*|<ε的x都有f(x)≤f(x*)(或f(x)≥f(x*))，则称f(x*)为局部极值。由此得到图6中的局部极值点。

图6 局部极值点

一般上下分割点与垂直投影极值点是对应关系，所以为了去除上下轮廓的伪投影极值点，可以通过三组局部极值点互相筛选得到上下分割候选点，即满足式(4)。最后得到的每对上下候选点之间不超过a个像素点，且最后得到的垂直投影极值点不超过a个像素点。本文实验中选择a=5作为分割点之间的距离，是由于上下分割点之间距离较近，能够排除大部分上下轮廓的伪投影极值点。

(4)

式中：m[i]表示上轮廓分割候选点的横坐标值，n[i]表示下轮廓分割候选点的横坐标值,v[i]表示垂直投影分割候选点的横坐标值。

2.3.2 有效分割点

经过2.3.1节的筛选后，依旧存在部分伪分割点，所以需对分割候选点进一步筛选。本文利用字符宽度、双向路径方差和上下分割点对应关系提取有效分割点。

为了得到更准确的粘连字个数k，对小数点后两位进行四舍五入操作。k的求取公式如下：

(5)

式中：round(·)为四舍五入操作，w和h分别代表粘连区域的宽度和高度，Waver和Haver分别代表标准字符的宽度和高度。

分别从左右两端开始向另一端根据字符宽度确定有效分割点，并对最后得到的这两组分割点进行方差计算[16]，选取方差较小的一组作为有效分割点。设分割候选点共有N个，具体步骤如下：

Step1如式(6)所示，在[xp+Dmin，xp+Dmax]内寻找上轮廓有效分割点。其中：d表示可容许范围误差；p=0时，xp表示粘连字符区域的左端点，p>0时，xp表示找到的前一个有效分割点。

(6)

Step2同理，从右端开始向左确定一组上轮廓有效分割点，即在[xp-Dmax，xp-Dmin]内寻找上轮廓有效分割点。此时p=0，xp表示粘连字符区域的右端点。

(7)

Step3设此时得到的有效分割点个数为S，有效分割点数组为sp。分别对上述两组有效分割点求取方差，选取方差较小的一组为上轮廓有效分割点mp。方差公式如下：

(8)

Step4同理，对下轮廓局部极值求取有效分割点np。

由于此时得到的上轮廓和下轮廓有效分割点个数可能不相同，为后续能将下分割点设为种子点对水滴位置进行引导，所以根据上下分割点一一对应关系，进行最后一步筛选。筛选情况分为以下四种：

(1) 当mp和np中有一组个数与k-1相同，且另一组个数不为0时，则利用个数是k-1这组，以式(9)为标准筛选另外一组。例如，假设mp个数与k-1相同，np个数为n，从np中选取与每个上分割点不相差a个像素点的下分割点作为有效点。

(9)

(2) 当mp和np的个数都不与k-1相同，且两者个数都既不为0也互不相同时，则选择个数小的数组筛选个数大的数组，筛选标准为式(9)。

(3) 当mp和np的个数都不与k-1相同时，且两者个数中有一组为0，若np个数为0则以mp中的数据为初始滴落点，并让(mp[i],h)为下分割点，其中：mp[i]表示上分割点的横坐标值，h表示粘连字符区域的高度；若mp个数为0则以(np[i],0)为初始滴落点，np中的数据为下分割点。

(4) 当mp和np的个数相同且都不为k-1时，则进行互相筛选，即满足式(9)。

根据上述情况，对分割候选点mp和np进行筛选.若筛选后两组个数不同，对个数小的以(mp[i],h)或(np[i],0)进行填充，最后得到上下有效分割点，如图7所示。可见，分割点的选取避免了字符凹陷的部分。选取上分割点作为初始滴落点，下分割点作为种子点，使得水滴在合力作用下运动。

图7 上下有效分割点

2.4 滴落规则

文献[6]中，通过引入种子点概念，使得水滴在合力作用下运动，本文在此基础上进行改进。通过缩小引力范围来提高分割的精准度，对在重力作用下的水滴规则进行了修改，主要以向下为首个选择方向，种子点的位置仅作为引导方向，避免水滴为了向种子点位置靠近而产生斜切路径。在水滴未进入种子点(即下分割点)引力影响范围内时，水滴主要受重力作用，种子点主要起着方向引导的作用；当水滴进入种子点影响范围内时，水滴受引力和重力共同作用。设(x0,y0)为当前水滴位置，下分割点即引导点为位置为(x1,y1)。算法分为以下两种情况：

(1) 0≤y0≤0.5y1时，水滴主要受重力作用。

当x0>x1时，以左下为引导方向，水滴的运动规则如图8(a)所示。如果(x0,y0+1)为白色像素，水滴则直接向下滴落；如果(x0,y0+1)为黑色像素，则会依次按照左下、右下、左边和右边作为下一个水滴位置。

(a) 0≤y0<0.5×y1&& x0>x1

(b) 0≤y0<0.5×y1&& x0>x1

(c) 0≤y0<0.5×y1&& x0>x1图8 受重力作用下的水滴运动图

当x0=x1，只受重力作用。因为此时引导点和水滴点处于同一列，不受任何方向引导，水滴的运动规则如图8(b)所示。

当x0

其中，当水滴落入字符凹陷处即局部极值时，对应的处理如下：(a)、(b)和(c)三种情况中，若情况(4)和情况(5)不断交替出现时，应从a(4)转入b(6)、b(4)转入b(6)以及c(4)转入b(6)。

(2) 0.5y1≤y0≤y1时，水滴受合力作用。

当x0>x1时，水滴的运动规则如图9(a)所示，合力方向为左下；如果(x0+1,y0+1)为白色像素，水滴则直接向左下方向滴落；如果(x0+1,y0+1)为黑色像素，则会依次按照下、右下、左边和右边作为下一个水滴位置。

(a) 0.5×y1≤y0x1

(b) 0.5×y1≤y0x1

(c) 0.5×y1≤y0x1图9 受合力作用下的水滴运动图

当x0=x1时，水滴的运动规则如图9(b)所示，合力方向向下，与只受到重力作用时保持一样的运动规则。

当x0

其中，当水滴落入字符凹陷处即局部极值时，对应的处理如下：当水滴出现a(4)→b(5)→a(4)不断交替时，应从a(4)转入(a)6；当水滴出现a(4)→a(5)→a(6)或a(5)→a(4)→a(5) 不断交替时，应从a(4)转入(a)6；当水滴出现b(4)→a(5)→b(4)或b(5)→c(5)→b(5)不断交替时，应从b(4)或b(5)转入b(6)；当水滴出现c(4)→b(5)→c(4)不断交替时，应从c(4)转入c(6)；当水滴出现c(4)→c(5)→c(4)或c(5)→c(4)→c(5)不断交替时，应从c(4) 转入c(6)。

(3)y0=y1时，水滴平移至(x1,y1)。

在分割好的字符图像中可能依然存在粘连，为了防止发生欠分割，对每个分割出的子图都进行粘连区域判断。当切分后的图像宽高之比满足式(10)时，认为子图中字符依然存在粘连，则继续根据上述方法进行粘连字符切分；若不满足式(10)，则认为此时得到的为单幅字符图像。

(10)

选取1.5倍的标准字符宽高比作为判断条件是考虑到粘连区域中存在“1”或“i”等宽度过小的字符这类情况。

3 实验结果与分析

为了验证所提出算法的有效性，选取了在上海某芯片封装制造企业所采集芯片的表面字符图像进行实验并分析结果。由于复杂的生产环境，所采集的图像普遍存在亮度对比度低、字符断裂和噪声干扰等问题，因此在对芯片图像进行预处理时会造成芯片字符粘连。随机选取200幅芯片图像，粘连区域共436个，其中包括双字粘连、多字粘连和字符倾斜。

本文实验中，误差d=8，像素误差a=5，对印刷字符较粗的芯片选取正常字符宽高之比为[0.4, 0.95]之间，字符较细的芯片为[0.1, 0.4]之间。首先经过本文的预处理来提取粘连字符区域，然后分别采用竖直投影分割算法、文献[7]算法和本文算法进行字符分割。以文献[17]中的字符分割准则为标准来统计正确率，即满足式(11)则认为得到正确分割，其中A表示算法分割出的字符图像，B表示正确字符分割图像。

(11)

从实验结果中可以看出，针对芯片图像中粘连字符分割，本文的算法相比竖直投影法和传统滴水算法取得更好的效果。部分芯片粘连字符分割结果如图10和表1所示，可看出较目前已有文献所采用的算法，本文算法准确率高，能够对断裂字符进行准确分割且运行时间较短。对粘连严重的芯片字符图像能够进行准确分割，起始滴落点位置的确定有所提高并且可以得到较为完整的轮廓分割路径。对分割失败的字符图像进行分析，主要原因有以下两部分：部分芯片字符大小差距过大，导致起始滴落点的位置选择错误，从而导致字符过分割；在粘连情况十分严重的情况下，由于种子点的影响，导致切分路径产生误差，导致某些字符轮廓不够完整。

图10 本文方法与竖直分割、文献[7]算法对比

表1 部分芯片粘连字符分割结果

4 结 语

本文提出一种改进的滴水算法对芯片图像粘连字符进行分割。在传统的滴水算法上，对起始滴落点的选取进行优化，并改进滴落规则。通过字符宽度、方差和分割点对应关系提取有效分割点，提高了起始滴落点的准确度；根据当前水滴位置与种子点之间的距离来选择水滴滴落方式，从而得到拥有较为完整的字符图像。实验结果证明了该方法的有效性和高精准度。实验过程中也发现，此方法依然还存在着一些不足之处。例如，字符大小差距过大时，字符粘连位置难以确定；对于一些笔画重叠、粘连严重的字符无法进行正确分割；当字符严重扭曲时，水滴的运动规则无法分割出完整的字符轮廓。因此，如何提高在这些情况下粘连字符的分割准确率，则是下一步要继续深入研究的方向。