定位细化算法（精选七篇）
定位细化算法 篇1
关键词：RFID,室内定位,区域细化
0 引 言
现有的无线定位技术根据定位机制的不同,可以分为基于测距的方法和不基于测距的方法两类[1]。基于测距的定位机制利用到达时间延迟TOA(time of arrival)、信号到达时间差TDOA(time difference of arrival)、信号到达方向DOA(directional of arrival)和接收信号强度[2] RSS(receivesignal strength)来估计距离或来波方向,然后使用三边测量法、三角测量法或最大似然估计法等计算未知节点位置,如 SDP算法、MDS MAP算法和 ILS算法等。而不基于测距的定位机制[3]无需距离或角度信息,或无需直接测量这些信息,仅根据网络的连通性等信息实现节点的定位,如质心法、DV Hop法、无定形算法、APIT算 法[4]。
常用的室内定位技术有红外线定位、超声波定位、基于IEEE802.11无线定位和射频识别RFID定位技术等[5]。RFID技术由于其非基础和非视距等优点成为优选的定位技术。目前比较成熟的RFID室内定位方案有SpotON、3D-iD pinpoint和LANDMARC。以上这三种RFID室内定位方案都是采用射频信号强度(RSSI)数据作为定位依据。基于RSSI测距是一种廉价的测距技术。RSSI测量在硬件上是相当便宜和简单的,且原则上只要芯片之间能够通信,就能够估测出二者之间的距离,因此其应用范围十分广泛。其中LANDMARC系统引入参考标签来辅助定位,稳定、受环境变化的影响较小、成本较低、定位精度较高。由于考虑了全局的参考标签,采用LANDMARC算法的RFID定位技术实时性较低,通常情况下是采取每30s实现一次追踪定位的策略,然而在追求更高定位性能的应用中,LANDMARC算法还不能满足实际需求。
本文致力于减少LANDMARC算法无关的计算量的同时保持甚至提高定位精度,提出一种利用对射频信号强度调制进行定位区域的细化的策略来消除距离待定位标签较远的读卡器和参考标签对定位计算的影响。虽然本算法对于应用环境和标签有一定的要求,但是对于应用在更注重相对稳定的室内环境中获得更佳的定位性能RFID定位系统,本算法具有一定的优势。
1 LANDMARC算法基本思想和存在问题
1.1 LANDMARC算法[6]
为了提高定位精度,同时又不增加过多的读卡器,LANDMRAC系统引入了参考标签来进行辅助定位,在系统中用作定位时的参考点。参考标签的引入有如下三个主要的好处:首先,标签的价格远远低于读卡器,这样就避免了为提高定位精度而需要布置大量的读卡器,从而降低了系统成本。其次,周围环境的动态变化可以被容易地调节和掌控,因为环境变化的影响对参考标签和待定位标签是一样的,所以可以根据参考标签来实时更新探测区域内的环境信息。第三,定位信息更加精确和可靠。显然,读卡器和参考标签的放置方式将对整个系统的定位精确度有着至关重要的影响。
假设有n个读卡器,m个参考标签和u个待定位标签,读卡器工作在连续模式下,检测范围为1-8级。定义待定位标签的信号强度矢量为undefined,其中Sip表示读卡器i上接收到的待定位标签p的信号强度,i∈(1,n),p∈(1,u)。对于参考标签,定义相应的信号强度矢量undefined,其中θij表示读卡器i上参考标签j的信号强度, j∈(1,m)。对于待定位标签p,定义:
undefined
表示参考标签j和待定位标签p之间信号强度的差异关系,Ejp越小表示待定位标签p和参考标签j相隔越近。对于每个待定位标签,定义相应矢量undefined,找出最小的前k个Ejp,k∈(1,m),对应的k个参考标签称之为待定标签的最近邻居,然后对k个最近邻居的坐标按照不同的加权求和,最终得到待定位标签的坐标。
未知的待定位标签坐标(x, y)由如下方程获得:
undefined
式中,wl是第l个最近邻居的权重因子,l∈(1,k),(xl,yl)为预先测得参考标签坐标,对各坐标加权求和便可获得待定位标签和坐标。经验上,wl由下式给出:
undefined
1.2 LANDMARC算法存在问题
LANDMARC算法假设所有的参考标签都能够成为邻居标签的候选标签,这将带来很多不必要的计算[7]。为了选择邻居标签,LANDMARC将计算待定位标签和每个参考标签之间的所有欧几里德距离并比较不同的E值。假设每个读卡器所能检测到的最大范围如图1所示,只有读卡器2至读卡器4能够检测到目标标签,所以远离读卡器2至读卡器4检测范围的参考标签接近目标标签的几率很低。但是如果我们直接应用上述方程,只在读卡器1检测范围内的参考标签将加入到计算中来,因此将导致一些不必要的计算并增加服务器工作量,因为有时合理地选择参考标签相比合理分配权重更为重要,这将将影响系统时延,甚至可能影响到定位精度,不能满足要求更高定位性能的场合。
2 区域细化室内定位算法
和LANDMARC算法一样,本算法使用的室内定位感应系统依然有n个读卡器,m个参考标签和u个待定位标签,读卡器工作在连续模式下,检测范围为1-8级[8]。
本算法引入一种标签信号强度可调机制,假设待定位标签具备发射信号强度可调的功能,可调范围至少为三级,分别为大中小三级,大级信号强度为标签正常信号强度。信号在传播过程中经过一定的衰减后,其强度在读卡器检测范围之内。由于读卡器检测到的信号强度并不就是标签发送信号的强度,因此可在发送的射频信号中包含两位的信号强度编码,大中小三级分别对应11、10、01。读卡器根据信号强度编码确定标签发送的射频信号强度。可以根据标签的信号强度,在需定位的区域中对每个读卡器的各级信号检测范围进行预先测量,细化为区域Amax、Amid、Amid。在每次定位中,待定位标签首先以大级信号强度发送射频信号,根据读卡器所能检测到信号强度情况,确定参加该次定位的读卡器,同时根据读卡器各个Amax交集区域确定可能的定位区域。紧接着待定位标签发送中级信号强度射频信号,然后发送小级的信号强度的射频信号。
在发送完该轮的射频信号后,根据各个参加定位的读卡器接收信号强度的编码情况,确定待定位标签在每个读卡器的环形区域,并取各个区域交集便得到待定位标签所处的最小区域。
假设同时检测到某待定位标签信号读卡器有N个,N∈(1,n)理论上可选取该N个读卡器环形检测区域交集区域内的参考标签坐标作为最近邻居的候选标签。然而这个做法实际上可能导致丢失某些距离待定位标签较近的参考标签。因此,可选取在N个读卡器中选取N-1个读卡器环形检测区域交集区域,选取的原则是在读卡器组合Cundefined中,其交集区域最大,设其为Φmax,则:
Φmax = Aundefined∩Aundefined…Aundefined (4)
如图2所示,有2个读卡器检测到待定位标签Tag的大级射频信号,初步可确定待定位标签区域ATag = Aundefined∩Aundefined。然后读卡器1只检测到中级信号,读卡器2没有检测到中小级信号。可得,待定位标签处于读卡器1环形检测区域Aundefined= Aundefined-Aundefined,处于读卡器2环形检测区域Aundefined= Aundefined-Aundefined,最终的可得待定位标签所处的最小区域为:
ATag = Aundefined∩Aundefined= (Aundefined-Aundefined)∩(Aundefined-Aundefined)
即图中阴影部分交叉区域。
而在区域Φmax中存在有M个参考标签,M∈(1,m)。为书写方便,把选中读卡器数N-1记为N,别改写各信号强度向量,信号强度欧几里德距离,得到待定位标签p的信号强度矢量为undefined选中参考标签信号强度矢量undefined。
对于待定位标签p,p∈(1,u),定义信号强度欧几里德距离:
undefined
权重因子和相应权重系数式(2)和式(3)无需改写,然而k是预先确定的参数,当区域Φmax内的参考标签数M
在确定Φmax内参考标签后,标记邻居标签序列1,…,k,利用式(5)得出E1p,…,Ekp,由式(3)得权重因子w1,…,wk,从预先测得的参考标签坐标中获得坐标(x1,y1),…,(xk,yk),最终我们可由式(2)计算得出待定位标签坐标(x,y)。
需要说明的是,本算法所指等级信号强度范围都是在相对稳定的室内环境中预先测得的。若室内环境发生重大改变,则应重新测量各个读读卡器的各个等级的信号强度范围。另外由于算法要求标签具备发送不同等级强度的射频信号,这会增加一定的标签成本。但从下面的仿真结果可以看出,区域细化的定位算法相比LANDMARC算法具有较高的定位精度,同时其定位误差方差相对较小,性能更佳。可见本算法要求一定应用条件,更适合于注重在相对稳定的环境中获得更好的定位性能的RFID定位系统中。
3 算法仿真
仿真一个10m×10m的室内环境,如图3所示,布置9个读卡器,参考标签个数视参考标签之间距离而定,对待定位标签进行多个位置的定位,并比较本文算法和LANDMARC算法的定位精度性能。
定位精度性能指标为定位估计误差e,e为待定位标签实际坐标(x,y)和计算坐标(x0,y0)之间的线性距离:
undefined
对每个位置仿真T次,求定位估计误差的平均估计误差:
undefined
参考标签间隔1m,对同一个位置进行定位100次,分别比较取不同的k值时两个算法的平均定位误差,如图4所示。可知,两个算法最佳k值都较为接近,但为了减少计算量,提高系统速率时,可选择较小k值。而此时RDL依然保持了较好的性能,这是因为区域的细化使得候选的邻近标签相比LANDMARC更为接近待定位标签,即使较少的最近邻居也能获得较高的定位精度。当k变大时两个算法都因为把过多较远的参考标签纳入计算范围而影响了定位的精度。
分别对k=8时的LANDMARC算法和k=6时的RDL算法的定位误差进行概率分布统计,如图5所示。可知RDL算法相比LANDMARC算法定位误差在1m以内的概率更高,误差基本都在2m以内,而LANDMARC算法的定位误差则可能达到3m。原因是区域细化可使得区域内最接近待定位标签的参考标签比例更高。
分析读卡器和参考标签的布局对算法的影响。分为四种情况:将图1所示的9个读卡器,四个边上中间四个读卡器去掉,即剩下对角和中心5个读卡器,参考标签间隔用d表示,分别为0.8m和1.2m。仿真结果如图6所示。可见本算法有与LANDMARC算法相似的性质,即更密集的读卡器和参考标签可获得更高的定位精度。只要合理布局读卡器和选择合适的k值,合适的参考标签布局密度同样可获得较高的定位精度。但由于读卡器成本远高于标签成本,减少读卡器数目同时适当增加参考标签布局密度更有利于降低系统成本。
4 结 论
本文分析了LANDMARC算法并提出了一个更有效更精确的机制。在相对稳定的室内环境中,适当增加标签成本并进行预先的测量,本算法通过标签射频信号强度的调制进行检测区域的细分,减少邻居标签的候选数目降低计算量而且提高定位精度。仿真结果显示,相比LANDMARC算法,本算法定位性能更佳。
参考文献
[1]李方敏,龚思来,韩屏.一种结合功率控制的无线传感器网络区域定位算法[J].传感技术学报,2008,21(1):158 162.
[2]冯浩然,袁睿翕,慕春棣.无线网络中基于信号强度的定位及算法比较[J].计算机工程与应用,2006,42(32):1 3,11.
[3]杜新恒,程良伦.无线传感器网络中距离无关定位算法的研究[J].计算机工程与应用,2008,44(33):67 71.
[4]史龙,王福豹,段渭军,等.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(15):857 868.
[5]Sayed A H,Tarighat A.Network-based wireless location:challengesfaced in developing techniques for accurate wireless location informa-tion[J].IEEE Signal Processing Magazine:2005,22(4):24 40.
[6]Ni L M,Yunhao Liu,Yiu Cho Lau,et al.LANDMARC:indoor loca-tion sensing using active RFID[C]//Proceedings of the First IEEEInternational Conference on PerCom’03.2003:407 415.
[7]Taekyu Kim,Seungbeom Lee,Sin-Chong Park.Effect of collision onmovement tracking using active RFID power measurement[C]//Con-sumer Communications and Networking Conference,2009.6th IEEE10-13 Jan.2009:1 4.
二值图像的细化算法 篇2
关键词：二值图像,细化,连通性,边界点,连通点
0 引言
在计算机领域, 图像处理的问题越来越成为重要的一部分, 因为现在的数据交流, 已不再是简单的数值, 而是更多地转换到大量的图片和影音图像上来。所以一个个的图像处理的问题就摆在了我们的面前。但形形色色的图像处理的算法, 通过抽象处理, 都是可以归结为一些简单的处理。比如多颜色的处理, 可以先从两个颜色的情况开始, 再进行展开。二值图像的细化就是这些简单处理中的一个问题。二值图像就是只有黑白两种颜色构成的图像, 二值图像的细化就是将图像中的黑色部分沿着它的中心轴线将其细化为一个象素宽的线条的处理过程。二值图像的细化在计算机的图像处理领域有重要的意义, 它其实是显示了整个图像的一个拓扑结构, 它在一些模式识别, 点阵图形的矢量化等方面有很好的作用。
1 二值图像的细化的分析
首先, 对二值图像进行设定。这里假定二值图像以白色为底, 细化黑色部分, 且给出的黑色部分的图像为连通的。这样, 对任意的黑色图像, 必定存在一个合适的n为正整数, 使得它在以白色为底的2n×2n的正方形内。由于假定黑色图像的连通性, 则二值图像的细化处理后的图像必定是连通的。为了便于处理, 设计了一个256×256的正方形作为处理二值图像的区域, 且在初始的作图中保证黑色部分图像的连通性。
其次, 对边界点、连通点、连通单位等进行说明。边界点就是黑色图像区域内与白色图像区域接触的黑色像素, 这接触判断是考虑这点对应的上、下、左、右4个方向的4点是否存在白色像素。连通点就是若此点去掉的话, 黑色图像区域会失去连通性, 具体判断要考虑该点的8个方向的像素的颜色值。因为在后面的判断中有两个黑点去掉后, 黑色图像区域是否会失去连通性的, 我们在此定义使之失去连通性的两点为连通单位。
下面分析其中的一些原理。
对细化, 采用的是层层剥离的方法, 就是判断出它的边界点, 而它又不是连通点, 就可以去掉此点, 这是一个反复的扫描的过程。如果对一个矩形区域, 从左上角开始的的话, 逐行扫描, 反复进行, 直到留下的全为连通点或为一条线段的断点。根据实际的编程过程, 我最终确定了如下的扫描细化的过程:
在第一次扫描的时候, 将黑色像素点的信息压入一个链表, 包括坐标、颜色, 以下的扫描过程其实是对此链表的一次次的遍历, 也就是沿着链表反复的判断, 将一个个的点去掉, 而对边界点等等的判断, 则又么用到其接触的点, 这是不能从链表中得到的, 只能一次次的读取原始图像的信息, 同时也在改变原始图像信息 (这里是改变颜色) , 便于后续过程的判断。
以下是对链表的遍历 (其中的边界点、连通点的判断, 都留到下面的算法中具体的介绍) , 在一轮轮的遍历中, 逐步把边界点和连通点从链表中去掉, 直到链表为空。在此我设定了一些不同的颜色值, 以作不同情况的判断。而一轮需作两次的遍历。第一次遍历判断是否为边界点, 需考虑它的4个方向的像素颜色, 若确定为边界点, 才再继续判它是否为连通点, 接着, 考虑它的8个方向的像素颜色, 非连通的点, 改变链表内的数据, 将颜色值更改为红的, 而对应的原始的图像信息也更改颜色为红的, 若就是连通点, 在链表中设置此点数据的颜色值为篮色 (此值只在链表中出现, 以作最后判断是否是连通点) 。
这第一次的遍历, 只是将一些点判定为边界点或连通点, 且赋了个黑白外的其它颜色值 (红色) 来区分, 但现在的判定还不是最终的结果, 还需要对如下的一些特殊情况要详细考虑。
因为是一个有序的逐行扫描, 在判定一个点为边界点时, 前面已设定的红点仍相当于为黑的来考虑, 而在其后的连通点判断时, 将设定为红点的相当于是白来考虑;对设定的蓝点, 因为只改变链表中的数据, 其实在判定中直接读取原始的图像区域, 它仍为黑的, 所以没必要去更改原始的图像区域的点的颜色。我们注意图1下面的角, 当扫描的点1时, 点2还是黑的, 1只是个边界点且不为连通点, 取红的, 再判点2, 此时, 2明显是边界点, 而它的八个方向上, 只有点3, 4为黑的, 且不连接, 所以2点暂时可以定为连通点, 取成蓝的, 接着要判定点3了, 看到其它点, 它现在只有一个接触的黑点, 即点2, 所以取为红点, 这样, 我们看到, 点2其实可以取为黑的, 所以我们在第二次扫描遍历时, 对蓝点再判一次连通性, 若确实是连通点, 不改变原始图像区域的黑色像素的颜色, 而将该点从链表中去掉, 反之, 则直接将对应的像素的设为白的, 也就是在完成细化, 该点也同样要从链表中去掉。
依照第一次的遍历, 应得到如上的图形, 这样的情况在一定的角度上都是存在的, 很明显, 这样的细化是不对的, 所以在那里的红的部分, 有一部分是应该为黑色像素, 以正确显示图形细化后的拓扑结构。所以应该也要对红的点进行一个判断, 这就是第二步的遍历的要求了, 来消除这个情况的影响。
结合上面的分析, 我们看到:一轮的细化是要两次遍历, 第一次是挑出边界点 (设为红) 和连通点 (设为蓝) , 但链表元素的量不变, 第二次是对链表的再一次遍历, 将其中的红点的和蓝点的再各作一个不同的判断 (因为前面可能出现的两种情况) , 而最终, 这两类点在第二轮遍历中从链表中删除, 同时将点判定为用黑色值还是白色值。则经过一轮轮的细化过程, 最终链表为空, 也就是完成了细化的工作。
2 细化算法的处理过程
第一步, 先设计一个链表, 逐行扫描保存黑点图像的信息, 包括坐标, 颜色值。
第二步, 接着按分析, 进行一轮的遍历, 则有如下的算法:
对应链表中的每一个元素, 根据其坐标, 可以找出其旁边的8个点, 看 (图3) 。
第一次的遍历。找边界点:只要依顺序判断1、3、5、7 4个点的颜色是否都不是白的, 若未是则继续链表中下一个点的判断, 否就将链表中此点的颜色值改为红的, 对应图像中的象素颜色为红的;在此点为边界点的情况下, 找连通点, 最终若是连通点, 设链表中此点为蓝的, 但不更改图像中的颜色, 若不是连通点, 它就是已更改了的边界点。
第二次遍历。依照上面的分析, 要再次的遍历此链表, 这次要去掉链表中黑色、红色的颜色值的点, 但这两类点都分别有各自的判断算法, 以最终确定下来。看下面:
(1) 遇到红点, 判断对应的图像的像素颜色值是否为红的, 若不是红的, 即是黑的, 这点就是已经处理过, 保留图像中黑的情况, 链表中删除此点, 反之, 有下面的判断。
要判断它的周围的点是否有接触的黑点了, 这个判断应该简单了。正如图2中看到的, 有的红点旁边没有接触的黑点, 甚至为一串红的, 我们很清楚这里的红点应该有一些被判定为黑点的。若是有黑的点, 则先在图像中对应的点颜色改为白的了, 是在细化, 接着删除链表中的此点, 反之, 则还要判断下去。
这样, 这一点旁边的点只有红的和白的了, 我们先看看图4的两者情况, 要对应比较图4。
我们注意图4、图2, 箭头对应的红点, 它旁边没有黑点, 但有不同点, 与图2的点接触的红点中没有点与黑点相连, 而这图4的确是接触的红点中有点与黑点接触, 对图4的情况, 直接考虑将图像中的对应点设为白的, 链表中的此点去掉。对图2的情况, 就要在红区域中找出一条黑的单象素宽的线, 细化的一部分区域就显现了。
下面是对这情况的算法, 这里已经知道点的旁边都是为红的和黑的点了:
第一步, 作另一个链表A, 将此点作为它的第一个元素, 接着, 将它旁边的红点的象素一个个的添加到链尾, 同时在此统计一下红点的数量m, 接着, 走到链表的第二个元素, 以至链表的更后面的元素, 依顺序去判断它 (红点) 旁边的点是否有黑点, 若无, 则将它旁边的红点且又不在链表中 (这里也要有设计的步骤来处理) 的加入到链尾, 而有的话, 分两中情况:一, 如 (图8) 中出现的情况, 这类的确定就是现在在处理的元素在链表中的位置是小于等于m+1的, 正如上面介绍的, 此红的接触的红点中有点与黑点接触, 该考虑结束, 要判的点设为白点, 就如图8中箭头指向的点可以设为白的, 而在原链表中将此点去掉, 且将链表A释放掉, 此算法在此结束;二, 现在, 处理的元素在链表中的位置大于了m+1了, 就在图形中设它的颜色值为黑的, 且显示出来, 而释放链表A只留下第一个元素。
第二步, 重复第一步, 直到碰到在第一步中第一个情况, 结束算法。
这个算法中, 有将一些没有判断过的红点直接更改为确定的象素颜色值 (黑的) , 所以在原链表中判断到此点时, 就可以直接跳过, 这就是为什么要遇到红点, 先判断对应的图像的象素的颜色值是否为红的了。
(2) 遇到蓝色的, 对应着 (图6) 在按顺序判断一次, 它还是不是连通的点, 其中对红的点考虑成白的, 若有蓝的点考虑成黑的。若还是连通的, 则在图像上对应的点取为黑的, 链表中将此点去掉。
可以看到, 以上的步骤最终将红的和蓝的点都从链表中去掉了。
第三步, 在链表不为空的情况下, 重复第二步, 直到链表为空。
3 实例
以下两个是算法实现的例子 (图5、图6) , 原始的图像, 是在256×256的矩形内, 对应的右边的就是细化后的效果。
4 结束语
对于二值图像的细化, 我在每一轮处理中有两次的遍历, 以便将一些条件的判断限制在一小部分像素上, 而不需要对所有的像素都反复的判断。处理的结果还算比较理想, 能得到比较好的效果。
当然为了保持一定的效率, 在有些判断上还是比较简单。在算法思想一定的情况下, 图像处理的效果和速度总会存在一定的矛盾, 需要在算法上不断改进。
参考文献
[1]JAMES D.Foley, Andries van dam.计算机图形学原理及实践, C语言描述[M], 北京:机械工业出版社, 2004.
[2]GUNILLA BORGEFORS, GIULIANA RAMELLA, GABRIELLASANNITI DI BAJA, et al.On the Multiscale Representation of 2Dand 3DShapes[C].Received April 14;revised December 16, 1998;accepted January 20, 1999.
[3]G.borgefors and G.Sanniti di Baja, Shape Preserving Binary Pyra-mids[C].8th Portuguese Conference on Pattern Recognit.ion (Rec-Pad96) , Guimaraes, Portugal, 1996.
二值图像的快速细化算法 篇3
在图像处理领域, 处理大量的图像信息之前, 往往需要对图像进行预处理, 以便于后面的图像分析、图形理解和图形特征提取等。图像细化就是对于图像预处理方法的一种, 特别在文字识别、指纹识别与图像理解中, 对图像进行细化有效的提高了处理效率, 减少数据冗余。
1 像的细化分析
图像的细化主要是针对二值图而言, 对图像的细化过程实际上是求该图像骨架的过程。所谓的骨架, 可以理解为图像的中轴:长方形的骨架, 是长方向的中线;圆形的骨架, 是圆心这一点。
常用的细化算法有查表细化和逐层剥取细化。
查表细化是建立一个公认合理的索引表。规定黑色值1, 白色值0;从上到下, 从左到右依次逐个判断每一个点, 碰到当前7点为黑色, 然后通过公式 (图1) , 计算出当前点的i=0值, 所得的值对照索引表 (图2) 中值, 若deletemark=0, 该点删除, deletemark=1, 该点保留为黑色。反复扫描直到不再变化。
常用的逐层剥取细化算法有Hilditch, 该算法通过判断图像中属于边界点而不是连通点, 就可以去掉此点, 这是一种反复扫描的过程。如果对于一个矩形区域 (图3) , 从左上角开始到右下角, 每次扫描可以讲矩形最外面一层剔去, 层层剥离后, 最终剩下最中间的一条线 (图4) 。
综合以上分析, 上述算法处理图像时都需要反复对图像进行扫描, 删除可剔除点。若图像较粗, 扫描次数大量增加, 因此效率低下, 适合于小图或者少量图像处理。
2 细化算法
本算法基于逐层剥取理念, 快速细化算法改进了反复扫描的过程, 顺序、逆序搜索两次, 确定每个点的层数, 通过层数可判断该点属于边界点还是骨架, 因而优化算法的效率, 大量减少程序运算时间。
以下是对于算法的详细步骤 (规定黑色值1白色值0) :
第一步, 从上到下, 从左到右依次扫描每一个点, 若当前点 (x, y) 为黑点时, 需判断其右上、上、左上和左四点的情况 (图5) 。 (x-1, y+1) (x-1, y) (x-1, y-1) (x, y-1) 这四点可以理解为当前点是被该四点包围, 该点层数即四点层数最小值多一层;如果当前点 (x, y) 为白色, 层数值赋为0。
第二步, 自下而上, 自右而左, 与第一步相似的判断每个点的状态, 若当前点是黑点, 于是判断其左下、下、右下和右四点的情况 (图6) 。 (x+1, y-1) (x+1, y) (x+1, y+1) (x, y+1) 四点包围了当前点, 同样取这四点层数的最小值加1作为该点层数值;如果当前点 (x, y) 为白色, 层数值赋为0。
与此同时, 既然已经求得每一个点上包围层数值和下包围层数值, 每个点的实际层数其实就是两种层数值中最小值 (图7) 。
第三步, 从上到下, 从左到右依次扫描每一个点, 此时需要判断该点8方向 (图7) 范围内所有点层数的情况。如果当前点的层数值是周围相邻点中最大, 该点即保留;如果当前点的层数值并非最大, 该点即可删去。
综上步骤, 即完成了该图像细化的全部过程, 算法只需遍历3次, 就能将一幅图像进行快速细化。
3 结果分析
从图像上 (图8-0图9-0) 可以看出, 上述3种算法都能有效细化图像, 得到图像骨架;在索引表细化及Hilditch细化中保持了图像的连通性, 但出现大量毛刺;快速细化算法则出现部分断裂, 但较高描述图像形态。
从表1也可发现, 在线条较细的图像中 (图8-0) , 三种算法运行时间几乎相同;而在线条较粗的图像中 (图9-0) , 快速细化算法运算时间明显优于其余两种, 再将图像 (图9-0) 等比例放大一倍后, 快速细化算法运算时间约原图像的3倍, 而其余两种算法则需6-7倍, 从而看出快速细化算法的优势。
参考文献
[1]田刚, 马琨.数字图像处理在等差条纹骨架线提取中的应用[J].
[2]韩九强.机器视觉技术及应用[M].高等教育出版社, 2009.
[3]Rafael C.Gonzalez Richard E.Woods.冈萨雷斯数字图像处理[M].电子工业出版社, 2003.
[4]卞维新, 徐德琴, 王俊书.基于两极复合式指纹图像细化算法的研究[J].贵州工业大学学报:自然科学版, 2005, 34 (3) :80-84.
[5]王家隆, 郭成安.一种改进的图像模板细化算法[J].中国图象图形学报, 2004, 9 (3) :297-301.
[6]梅园, 孙怀江, 夏德深.一种基于改进后模板的图像快速细化算法[J].中国图象图形学报, 2006, 11 (9) :1306-1311.
手写体字符细化算法的研究 篇4
字符进行细化处理后能够消除字符图像中包含的冗余信息,避免不相关因素(如,手写字符的粗细)的干扰,减少计算机的运算量,进而使识别时间缩短。采用不同的字符细化算法提取到的字符骨架不同,会直接影响到在字符骨架的基础上提取的字符特征的好坏,最终对字符识别的正确率产生影响。因此,字符细化算法的研究显得尤为重要。
1 字符细化算法研究
1.1 FPA细化算法
针对经过二值化处理的手写字符图像中的任意一像素,选取周围3*3的窗口做判断处理,如图1所示。FPA方法[2]的原理,将笔划的外围黑像素进行逐层的剥除,最终保留属于字符骨架的像素点。为了确保骨架提取的连续性,将每次处理又分解成两次子处理。
第一次子处理:从所选窗口区域的东南边界和西北角对满足式a)、b)、c)、d)的黑像素点进行剥除处理;
第二次子处理:从所选窗口区域的西北边界和东南角对满足式a)、b)、c')、d')的黑像素点进行剥除处理;
反复执行以上两次子处理,直到得到字符骨架为止。
其中,A(P1)表示P2,P3,P4,P5,P6,P7,P8,P9,P2序列中出现01对的个数,B(P1)表示1在P1的周围八邻域窗口内出现的个数。公式a)用来限制字符骨架的端点不被剥离,公式b)保障字符骨架中间点的存留,如图2所示。公式c)、d)和公式c')、d')分别用来确保细化过程中只剥离东南边和西北角、西北边和东南角中不属于字符骨架的冗余点。
运用此算法对实验分割后的单个汉字进行细化,部分实验结果如下:图3为原图,图4为原图取反后的图,图5为实验得到的细化图。
1.2 SPTA细化算法
SPTA算法[3]同样选取的窗口进行冗余点剥离处理。与FPA算法的不同点是从图像的上、下、左、右四个方向出发对字符进行细化处理。以P点为中心的的周边区域,如图6(e)所示。P点的8—近邻用于决定点是否可剥离,表示为序列Q,其中Q={n0,n1,n2,n3,n4,n5,n6,n7}。
如果序列Q符合图6(a),6(b),6(c),6(d)所示情况的任何一种,则表示为字符的右边界点、上边界点、左边界点和下边界点。下面对字符的细化过程加以说明,并以右边界点为例。
安全点的评判以公式(1)—(4)的布尔函数为判断准则:
符合上图6中(a)模板的p点,即满足式的点,也就是字符的右边界点,如果布尔表达式(1)的返回值为假,则该点判定为安全点。
同理,字符的左、上、下边界点的判断分别依据表达式(2)、(3)、(4)的返回值。SPTA算法进行字符细化一般情形下需进行多轮检查,每轮检查又分成两次扫描,每次扫描检查字符图像的单个像素点。整个过程既可以逐行扫描亦可逐列扫描。首次扫描的目的是检查所有的左、右边缘点,将非安全点做以标记;第二次扫描对上、下边缘点进行同样的处理。当一轮扫描操作完成后,不再有被标记的点,则将所有被标记的点进行剥离处理,表示算法循环结束。否则,需进行新一轮扫描。
运用此算法对实验分割后的单个汉字进行细化,部分实验结果如下:图7为原图,图8为原图取反后的图,图9为细化后的结果。
1.3 改进的Hilditch细化算法
本文所采取的方法在经典Hilditch细化[4-5]算法(利用连接数Nc的基本串行算法)的基础上加以改进。依据图像腐蚀原理,考虑每个像素点的8—邻域以及8—邻域周围像素点的情况。分析像素点之间的关联情况,重新调整Hilditch算法所设定的限制条件。该方法在对字符细化的过程中,更加充分的考虑了各个像素,改进后的限制条件在不丢失关键点的同时能更加高效的剥离冗余像素点。
考虑一个像素点的8—邻域以及8—邻域周围像素点的情况示意图,如图10所示:
以上方法即为考虑周围25个点区域的方式。以P0点为例进行说明,在仅考虑8—邻域的情况下,当P0、P2、P3、P4为黑点,其余的点均为白点时,P0点并不可以直接剥离。因为仅考虑8—邻域时,P0点是横向拓扑点。新的判断方法时,若Pll、Pl2、Pl3、Pl4、Pl5、Pl6、Pl7点也是黑点,那么可以从纵向结构上判断P0点为冗余点,进行剥离处理。限制条件如下:
1)P0是黑点,即P0=1;
2)P0的8—邻域 ,白像素点 的个数在 [2,6] 之间 ,即8,其中;
3)从P1开始,对像素点进行逐对判断,若前一点和后一点的值分别为0和1,则将Ti的值置为1,否则置为0,i的范围为1,2,…,8。若,则表示满足该条件,记为Z0(P0)=1。
4)P1×P3×P7=0即点P1,P3,P7中任意一个或者多个点的值为0,或者Z0(P1)≠1即以P1为基准点的8—邻域点的Z0计算结果值不等于1。
5)P1×P3×P5=0即P1,P3,P5中任意一个或者多个点的值为0,或者Z0(P3)≠1即以P3为基准点的8—邻域点的Z0计算结果值不等于1。
当关注P1和P3的Z0运算时,P1和P3的8—邻域像素点情况示意图分别如图11和图12所示。
明显得知,计算Z0时,需要计算Ti在上述条件c)中,其i的取值范围为[1,8],但是,点P1、P3邻域点的下标与i的取值范围保持不同。
运用此算法对实验分割后的单个汉字进行细化,部分实验结果如下:图13为原图,图14为原图取反后的图,图15为细化后的结果。
2 算法结果分析
本文通过对60个样本的实验分析,从连续性、速度、骨架的保持、细化结果、像素特性、算法实现的难易度、以及细化效果方面对三个算法进行了比较分析,分析结果如表1所示。
3 结论
通过理论研究和实验分析,对三种算法提出了对比论证,FPA算法兼顾了连续性和四周噪声免疫,处理效果较好,容易实现。SPTA算法处理的结果是严格的单像素笔画,便于笔画跟踪提取,并且比较好地代表了笔画的中轴和保持了笔画的连续性,达到了细化的基本要求。对于Hilditch算法的改进,也是一种较好的模板法,细化后的图像没有改变原图像的主要特征,而且很好的排除了大量冗余信息的干扰。
虽然三个算法相对细化效果较好,但都存在一定问题,FPA算法难于排除撇、捺方向交叉笔画的畸变,且不是严格的单一像素。SPTA算法结果虽然是单一像素,但是速度比FPA稍慢,而且SPTA也难于克服45°交叉点畸变的问题。Hilditch算法虽然将转折位置的结构特征保留了下来,但个别多余信息冗余仍然存在,需对细节做进一步处理。
摘要：字符细化是手写体识别预处理中的关键技术,细化结果的好坏直接关系到识别率的高低。由于手写字符的多样性和随意性,目前没有统一的细化算法,因此细化算法的研究受到越来越多学者的关注。该文以非粘连字符作为研究对象,对基于模板的细化算法进行研究。采用FPA细化算法、SPTA细化算法、改进的Hilditch细化算法进行理论分析和编程实现,通过对比细化效果,分析了几种细化算法的优缺点。
关键词：手写体字符,细化,FPA算法,SPTA算法,Hilditch算法
参考文献
[1]魏炜,刘亚宁.改进的脱机手写汉字细化算法[J].计算机系统及应用,2011,20(6):184-187.
[2]张学东,张仁秋,关云虎,等.一种快速的手写体汉字细化算法[J].计算机应用与软件,2009,26(11):17-19.
[3]黄铁英,姜昱明.一种快速手写汉字细化算法[J].计算机工程,2004,30(19):121-128.
[4]白莹.手写汉字的细化算法研究[D].西安电子科技大学,2014.
一种改进的脱机手写文字细化算法 篇5
细化又称为骨架化,是在不影响原图像拓扑关系的条件下,快速而准确地将宽度大于一个像素的图形线条转变为一个像素宽线条的处理过程[1]。通常扫描进计算机的文字图像,笔划宽度大于1个像素,与单像素宽度的文字笔划相比,较宽的文字笔划在文字结构特征提取过程中,特征提取算法复杂,运算时间较长;由于输入所产生的噪声往往集中在字符笔划的边缘上,在原始文字笔划上直接提取结构特征易受到噪声影响,导致所提取特征不准确,因此,目前通用的方法是在进行文字结构特征提取之前,对文字图像进行细化处理。
一个好的细化算法应该达到如下要求:
(1)骨架图像必须保持原图像的连通性;
(2)骨架图像应尽可能是原图像的中心线;
(3)细化结果要尽可能细,争取得到一个像素宽的线条图像;
(4)应使用尽可能少的迭代次数;
(5)保留曲线的端点;
(6)保持原有字符的拓扑,几何特征,不应产生严重的畸变。
要达到上述目标,同时又使算法尽可能简单、快速,是一件非常困难的事情,因此细化算法的研究一直是一个非常活跃的领域。
2 已有细化方法
已有的细化算法按迭代方式不同分为串行算法和并行算法。在串行细化算法中,当前迭代的结果不仅取决于前一次的迭代图像,而且与当前处理情况有关;而在并行方式中,当前迭代仅仅由前一次的迭代情况决定。串行细化算法的处理结果依赖于对像素处理的先后顺序,因而像素点的消除或保留不可预测;而并行细化算法对图像进行细化时利用相同的条件同时检测所有像素点,其结果具有各向同性,因此从算法原理上并行方法优于串行方法[2]。
LeiHuang和GenxunWan在文献[3]中提出了一种有效的并行文字细化算法,该算法采用了7个保留模板和50个删除模板,分别如下:
图1中标志为1的点为白像素点,标志为0的点为黑像素点,标志为P的点为当前像素点,标志为X点表示不关心该点的像素灰度。
算法主要分成三个步骤:
(1)对文字图像进行扫描,若当前像素点灰度值为0(即当前像素为黑像素),与周围8邻域的像素关系满足删除模板且不满足保留模版,标记该像素点;
(2)整幅图像扫描完成后,将所有标记的像素点灰度值置为1(即将该像素点置成白色);
(3)重复进行步骤(1)、(2),直至没有像素点满足删除条件。
图3为一幅二值后的简牍文字图像,文字笔划宽度分布不均匀,图4为细化后的文字图像。
由文字细化后效果图可以看出,细化后的文字图像笔划宽度为1个像素,同时文字笔划基本没有出现分叉现象,但是文字笔划出现了明显的断笔,如第3列第5个字:
3 改进方案
图7为对文字进行一次细化迭代后所得图像。由该图像知,虽然文字还没有出现断笔现象,由于红色像素点满足删除模板12,浅蓝色像素点满足删除模板14,且这两个像素点都不满足保留模板,因此会被删除;当这两个像素点被删除后,两个黄色像素点会满足删除模板12、14,同样也会被删除掉……依此类推,文字的大部分竖笔划会被删除,图像出现了缺失笔划和断笔的情况。
针对该算法的缺点,本文提出了一种改进方法,其根本的实现思想在于当出现只有两个像素宽度的笔划时,保留该笔划的左边像素点,删除右侧像素。
具体步骤如下:
(1)当文字像素点满足删除模板10、12、32、39、40,查看当前像素点右侧第二个像素点的灰度值;若灰度为0(即为黑像素点),设置当前像素点的灰度为1,否则保留当前像素点灰度值;
(2)当文字像素点满足删除模板14或16时,将当前像素点位置的存入标志数组中;
(3)当文字像素点满足删除模板1或4时,将当前像素点的列坐标加1后与标志数组中的坐标进行比较:若与标志数组中的某个坐标相同,则保留当前像素点灰度值,否则将当前像素点的灰度置为1。
4 实验结果分析及结论
图8为用改进后的细化算法对文字图像进行细化处理所得结果,可以看出:
(1)文字笔划基本被细化成一个像素的宽度;
(2)文字笔划较少出现分叉现象;
(3)与原文字细化算法相比,文字笔划基本没有出现断笔;
(4)细化后的文字图像保持了原文字的拓扑特征。
改进后的文字细化算法,即满足了细化算法的6条要求,又不需要进行复杂的数学处理,处理速度较快,在批量手写文字识别处理领域具有广阔的应用前景。
摘要：在分析已有细化算法的基础上,针对两个像素宽的文字笔划,设计像素保留算法,有效解决了文字笔划断裂及丢失问题。实验证明,该改进算法能够准确提取文字骨架,在批量手写文字识别处理领域具有广阔的应用前景。
关键词：细化,模板,断裂,丢失
参考文献
[1]李文斌,徐卫林,崔卫纲.棉纤维长度测试系统的开发.纺织学报,2007;28(11):25—28
[2]王家隆.指纹图像的预处理及其改进算法.大连:大连理工大学硕士论文,2003
星载FPI干涉条纹细化和反演算法 篇6
在国家自然基金支持下, 中国科学院空间中心自行设计搭建了中高层大气风场FPI (Fabry-Perot Interference) 原理样机。采用日本滨松公司512×256的面阵CCD作为探测器, 单个像素大小为24μm, 积分时间设为800ms, 获取了干涉条纹图像[1]。经过研究, 实现解决了干涉条纹图像滤波和分割自动化处理[2], 获得的条纹图像见图1所示。
可见, 图1的干涉条纹粗、宽而且边缘弥散, 不细化成线状无法精确取数据进行反演计算。细化是必需的一个处理环节, 细化对反演计算中高层大气风场信息的精度至关重要。本文对细化概念进行深入阐释, 提供具体实用的细化算法, 给出运用VC++实现的效果并分析。
1细化
细化, 就是把一个具有一定面积的区域用一条 (或一组) 曲线 (或细线) 来代表, 提取一个图像的“骨架”, 即图像中央的骨骼部分。将研究的连接成分 (集合) 用符号“1”来表示, 背景用符号“0”来表示。细化操作就是用改变连接成分的形状使符号“l”中某些像素从“1”变成“0”, 迭代这一过程, 直到最后由一组单个像素组成的一组曲线 (或细线) 来代表整个区域, 这组曲线 (或细线) 应该保留着连接成分的连通性和轮廓的几何特征[3]。
目前还没有精确的细化过程数学定义, 细化算法是多样的。无论采用何种细化算法, 都应该满足两个条件:一是在细化过程中, 图像有规律地缩小;二是在逐步缩小过程中, 图像的连通性质保持不变。
以下从数学集合概念的角度探讨细化概念的含义。先规定S和Sc分别为矩形内的值为1和值为0的点的集合。
定义1:一点x的四个相邻点表示为x1, x3, x5, x7, 如图2所示, 称为x的4邻点;x的四个对角相邻的点表示为x2, x4, x6, x8, 这四个点与x的四个4—邻点一起称为x的8-邻接点。如图2所示。
图2 邻域图
定义2:具有相同的值 (0或1) 的两个点x、y称为是8-相连的, 如果x、y之间存在这样的一系列点a0 (=x ) , al, ... , an (=y) , 其中对于每个i (l≤i≤n) ai是ai-1的8-邻点, 并且每个ai的值与x、 y的值相等。相应的如果每个i (1≤i≤n) ai是ai-1的4-邻点, 则称x、y是4-相连的。
定义3:每一类8-相连点 (4-相连点) 的集合称作8-相连区 (4-相连区) 。Sc中有两类相连区, 一类在矩形的边缘, 称为背景, 另一类包含在S中间, 称为洞。
定义4:点x是在S中可删除的, 如果删掉x后不影响S的相连性。否则, 称点x是在S中不可删除的。
以上定义的意义在于讨论出细化的含义, 细化就是保持连接成分的连通性同时, 删去“可删除”的点, 最后剩余单像素“不可删”, 形成单像素曲线, 细化完成。定义的同时也给出了细化算法的一个发展方向, 以下形象地给出可删除的情况列举。
Yokoi证明过, 一点的可删除性可以通过计算8-相连性数得到。该8-相连性数定义如下:
其中U=取{1, 3, 5, 7}, xi表示像素的值, x
其中的x取值可以为0也可以为1。
2细化算法描述
第一步:扫描整幅图像, 用逻辑规则P1处理x点3×3邻域内的像素, 把要删除的元素做上标记, 先不删除。第二步:用逻辑规则P2处理x点3×3邻域内的像素, 把需要删除的元素打上标记。
扫描完整幅图像后, 删除做了标记的元素, 重复第一和二步的过程, 直到剩余单位宽度的线条为止。
令N (x) 为3×3窗口内目标像素的个数:
T (x) 表示序列x1 x2 x3 x4 x5 x6 x7 x8 x1中0→1变化的次数。两次迭代中用到的逻辑规则P1和P2形式为:
P1: (2≤N (x) ≤6) && (T (x) =1) ,
&& (x1·x3·x5=0) && (x3·x5·x7=0) ;
P2: (2≤N (x) ≤6) && (T (x) =1) ,
&& (x1·x3·x7=0) && (x1·x5·x7=0) 。
第一个条件 (2≤N (x) ≤6) 表示中心的邻域窗口内至少有2个到6个八连通相邻像素, 这样的中心可以删除。如果中心像素只有一个邻点, 说明是目标端点, 不能删除。如果有六个以上邻点, 说明它不是目标边界点, 删除它会引起边界腐蚀。
第二个条件T (x) =1检查像素x的周围是否只有一个连通成分, 只有一个连通成分, 则删除x不影响局部连通性, 可以将其删除。
第三和四个条件 (xl·x3·x5=0) 以 (x3·x5·x7) =0, 在x3=0, x5=0或同时为零得到满足, x3=0时, x属于东边界;x5=0时, x属于南边界;x1=0且x7=0时, x属于西北角。
第一步中, 细化算法删除了上述三种情况的像素。第二步中, 细化算法删除了北边界, 西边界, 和东南角的像素。
该算法处理的图像如图4所示。
还有一种迭代性更强的细化算法, 采用5×5模板, 满足下面4个条件则删除中心像素x:
(1) 2≤N (x) ≤6;
(2) T (x) =1;
(3) x1·x3·x7=0或者T (x1) ≠1;
(4) x1·x5·x7=0或者T (x7) ≠1。
其中T (x1) 指x1的3×3邻域中0→1变化的次数不是1, 即3×3邻域都是0或者不仅仅有1个连通成分;T (x7) 指x7的3×3邻域中0→1变化的次数不是1, 即3×3邻域中都是0或者不仅仅有1个连通成分。
该算法处理的图像如图5。
从细化效果看, 5×5模板算法细化的线条连通性好, 对噪声敏感一些;计算速度角度分析, 两者都可以很好地满足实时的星载有效载荷数据处理要求, 3×3模板算法速度更快一点。
图4和图5可知, 由于前续处理的影响, 存在噪声, 于是干涉条纹存在着分杈和桥连等缺陷, 需要做进一步的处理, 即条纹修整。
3条纹修整
条纹修整即去除分杈和桥连等缺陷, 本文采用数学形态学滤波的开运算消除线条分杈和桥连。因为条纹成垂直走向, 消除的则是水平方向的分杈和桥连。于是, 进行垂直方向的开运算。图4处理结果见图6, 图5处理结果见图7。
开运算滤波后的条纹图像局部还不光滑, 需要再做曲线光滑处理, 即采用多项式法进行曲线拟合, 该方法非常成熟, 此处从略。
4中高层大气风速的反演
考察扫描镜转向正北N时得到的干涉图像。对于条纹的干涉级m, 由多光速干涉条件得
其中, n为FP腔内介质反射率, d为FP腔间距;λ为产生干涉条纹气辉光辐射波长, rN为干涉圆环半径;f为聚焦透镜焦距[4]。
由于多普勒频移, 气辉光辐射波长变为
其中, c为光速, θ为天顶角, υN为水平风速经向分量 (南北向分量, 取南向北为正方向) 。由于rN/f<<1, 运用Taylor公式。则此时条纹的干涉级m满足
搭建Fabry-Perot测风干涉仪原理样机的标准具间距即腔间距d为22 mm、反射率n为0.85、波长λ0为630 nm、系统焦距f为595 mm , 中高层大气风速反演只需从图像中提取rN和相应m的值即可。
干涉圆环半径提取方法可采用迭代方法计算[5]得到, 该方法非常成熟, 此处从略。本文提及的反演算法理论基础翔实, 操作简便, 具备可行性, 具体反演计算的结果和分析下一步再探索研究。
5结论
应用VC++开发软件平台, 实现了细化的算法, 运用垂直方向开运算滤波消除了分杈和桥连的缺陷, 应用效果明显, 处理方法得到了验证。再曲线拟合以及提取条纹的干涉级m和相应rN值, 中高层大气风速信息便可以计算获得, 该算法理论基础翔实, 有很强可行性, 计算结果还有待下一步研究。
干涉条纹图像细化、条纹修整和特征数据提取、反演计算完全印证了FPI干涉原理, 进一步支撑了我国自主设计完成中高层大气风场FPI探测的工程可行性。
摘要：中国科学院空间中心自行设计搭建了带有大口径望远镜的星载FPI原理样机获取了干涉条纹图像。条纹图像滤波和分割自动化处理已经完成。条纹图像的细化对反演计算中高层大气风场信息的精度至关重要。深入探讨细化概念和细化算法, 进行细化条纹滤波修整。采用VC++进行实现, 应用效果明显, 得到验证。最后, 依据原理样机实际情况, 探讨中高层大气风速的反演算法, 说明其可行性。
关键词：干涉条纹图像,细化,条纹修整,反演
参考文献
[1]杜述松, 王咏梅, 王英鉴.中高层大气风场测量技术的研究.中国空间科学学会空间探测专业委员会第二十二次学术会议论文集, 2009:57—61
[2]韩威华, 王咏梅, 吕建工, 等.中高层大气风场星载FPI干涉条纹的处理.科学技术与工程, 2010; (4) :156—159
[3]傅宏石.ESPI条纹图像自动处理.长春:吉林大学:硕士毕业论文.2006
[4]赵正启, 周小珊, 艾勇.扫描式法布里-珀罗干涉仪测量高空大气风速.应用光学, 2006;27 (6) :558—562
一种快速的手写体汉字细化算法 篇7
手写体汉字细化的目的,是将汉字骨架提取出来的同时保持汉字细小部分的连通性,先对汉字图像进行细化有助于突出汉字形状特点和减少冗余信息。一个好的细化算法是以细化的质量和速度进行评价,细化主要应满足以下要求[1]:(1)细化图像的连通性必须与原图像保持一致;(2)细化图像中的线条宽度应尽量为单像素;(3)细化图像中的线条应尽可能是中心线;(4)细化图像应尽可能保持原图像的细节特征;(5)细化算法速度尽可能快。快速并行细化算法[2](简称FPA算法)满足以上五点要求,是一种经典的细化算法。FPA算法是同时从四个方向细化图像,对直线、拐角及T型交叉点能比较精确地保持与原图像的一致,但其存在缺陷:细化不全、可能产生信息丢失。后来的算法[3,4,5,6]针对FPA的这一缺点,提出了改进的并行细化算法。LW并行细化算法[3,4]改善了斜线信息丢失,但同时细化结果存在多余枝杈。基于模板保留的快速并行细化算法[5]利用模板保留了FPA丢失的信息。鲁棒的二值图像并行细化算法[6]先利用条件保留了FPA丢失的信息,再利用条件删除多余的像素。本文为了克服快速并行细化算法的缺点,提出了一种利用消除模板删除多余像素的同时并且保留了FPA丢失信息的细化算法,该算法具有不丢失信息、速度快、细化全、交叉点不变形等优点。
1 FPA算法
FPA算法是逐层剥去文字笔划外围黑像素而保留属于骨架的像素点。为了保证骨架的连续性,将每次迭代分为二次子过程。对一幅二值化后的汉字图像,设其前景点值为1,背景点值为0。对某一考察点P,对其八邻域做标记如图1所示。
第一次子过程中,循环考察汉字图像中的每一个前景点,如果同时满足下列条件(1)、(2)、(3)、(4)的像素点即标记为可删除点。当一次循环考察结束时,对作删除标记的点一起删除。第二次子过程中,循环考察汉字图像中的每一个前景点,如果同时满足下列条件(1)、(2)、(5)、(6)的像素点即标记为可删除点。当一次循环考察结束时,对作删除标记的点一起删除。反复执行这两次子过程,直至没有可删除的像素点为止。
(1) 2≤B(P)≤6;
(2) A(P)=1;
(3) P1×P3×P5=0;
(4) P3×P5×P7=0;
(5) P1×P3×P7=0;
(6) P1×P5×P7=0。
其中,A(P)表示P1、P2、…、P8,P1 序列中01对出现的个数,B(P)是P的八邻域窗口中1的个数。
条件(1)是为了保留孤立点(B(P)=0),端点(B(P)=1),近似内点(B(P)=7)和内点(B(P)=8)。条件(2)是为了保留骨架点。条件(3)和(4)是为了保证删除右边界、下边界、左上角,如图2 (a)-(c) 所示。条件(5)和(6)为了保证删除左边界、上边界、右下角,如图2 (d)-(f)所示。
FPA算法删除的边界点都满足A(P)=1,事实上A(P)=2 or A(P)=3时也可能是边界点,因此FPA算法细化不全。如图3(a)所示的阶梯图像, FPA算法会将其删除,导致信息丢失。
2 改进的细化算法
本文算法利用3×3消除模板来克服FPA算法存在的不足。本文共新增了八个消除模板,如图4所示。
如图4中(a)-(d)消除模板不仅可以删除图3(a)中斜线上的多余像素,同时克服了FPA丢失的信息。
前景点满足A(P)=3时,即分叉点,它也可能是边界点。如图5(a)所示分叉点处细化不彻底,消除模板图4(e)可以使分叉点彻底细化,细化结果如图5(b)所示。由于考虑到分叉点细化不彻底的情况还有模板旋转90°、180°、270°,所以增加了另外3个消除模板(f)-(h)。
本文算法利用8个消除模板,克服了FPA算法存在的不足,即细化不全,可能产生斜线信息丢失。本文算法描述为:
(1) 遍历整个汉字图像,找到前景点。
(2) 判断前景点是否使下式为真,如果为真,标记该点为可删除点。如果为假继续寻找下一前景点。
(2≤B(P)≤6 & A(P)=1 & P1×P3×P5=0 & P3×P5×P7=0) ‖ (A(P)=2 & P1×P7=1 & P3+P5+P8=0) ‖ (A(P)=2 & P1×P3= 1 & P2+P5+P7= 0) ‖ (P2+P4+P6+P8=0 & P1+P3+P5+P7=3)
(3) 遍历完整个汉字图像时,删除所有的被标记为删除点的前景点。
(4) 遍历整个汉字图像,找到前景点。
(5) 判断前景点是否使下式为真,如果为真,标记该点为可删除点。如果为假继续寻找下一前景点。
(2≤B(P)≤6 & A(P)=1 & P1×P3×P7=0 & P1×P5×P7=0) ‖ (A(P)=2 & P3×P5=1 & P1+P4+P7=0) ‖ (A(P)=2 & P5×P7=1 & P1+P3+P6=0) ‖ (P2+P4+P6+P8=0 & P1+P3+P5+P7=3)
(6) 遍历完整个汉字图像时,删除所有的被标记为删除点的前景点。
(7) 重复上述过程,直到没有像素被删除为止。
3 实验结果与分析
本实验选取多幅手写体汉字图像,经过本细化算法处理,能够很好地对二值化手写汉字图像进行彻底细化。为了说明本算法使汉字图像细化有所提高,本文利用快速并行细化算法、文献[5]和文献[6]的细化算法来比较细化结果。实验结果如图3和图6所示。四种细化算法的细化时间比较如表1所示。
注:时间单位为ms
从图3和图6中的细化结果可以看出,FPA算法会丢失信息。文献[5]的细化算法虽保留了FPA丢失的信息,但是细化不彻底。文献[6]的细化算法保留了丢失信息,骨架细化成单像素,但交叉变形大。本细化算法不仅保留了FPA丢失信息,并且细化全、交叉点不变形。从表1中的时间数据可以看出,本文细化所需时间明显比其它细化算法所需时间少。
4 结 论
本文细化算法的细化情况与原来的三种算法相比有明显提高。本文细化算法细化速度快,而且处理后的手写汉字图像保留了FPA丢失信息,具有细化全、交叉点不变形等特点。
参考文献
[1]冯星奎,李林艳,颜祖泉.一种新的指纹图像细化算法[J].中国图象图形学报,1999,4(10):835-838.
[2]Zhang TY,Suen C Y.Afast parallel algorithm for thinning digital pat-terns[J].Communications of ACM,1984,27(3):236-239.
[3]Lu HE,Wang P S P.An improved fast parallel algorithm for thinningdigital patterns[C]//Proc IEEE Confetence on Computer Vision andPattern Recognition,1985:364-367.
[4]Lu HE,Wang P S P.Acommention“a fast parallel thinning algorithmfor thinning digital patterns”[J].Communication of the ACM,1986,29(3):239-242.
[5]贺继刚,杨晓伟,吴广潮,等.基于模板保留的快速并行细化算法[J].计算机应用与软件,2007,24(12):26-28.
【定位细化算法】相关文章：
近场声源定位算法研究论文04-11
基于MALAB的车牌定位算法研究02-05
基于小波变换的汽车牌照定位算法10-09
基于眼睛特征定位的人脸模板匹配算法研究09-12
细化分工05-11
细化解读05-11
专业细化05-19
服务细化05-24
细化作业05-30
目标分解细化05-27