滴水算法

Writen By Lindsay On Jun 10, 2019

1. 前言

   对于连接字符的分割,在实际应用中具有很大的用处,如手写字符的识别,验证码的自动识别等,都有可能用到字符分割。有很多常用的分割方法,包括对连接字符的图像直接对半分割,适用于各个字符的宽度大致相等的情况。也可以将整个图像的所有行相加,使用傅里叶变换到频率域后进行分割,在两个字符的分割处,往往频率较高,之后可以选取频谱的峰值进行分割。但是对于连接程度过大的字符往往难以分割。
   由于前两种算法都具有一定的局限性,这时通常考虑使用滴水分割算法以及惯性滴水分割算法,大惯性滴水分割算法。

2. 分割步骤

   1. 首先通过一般性的单字符识别算法对字符串进行识别,对于识别出,且具有较高置信度的字符,判断其不需要进行分割,立即返回识别的字符。对于无法正确识别的字符,判断其连通域的宽度,如果字符宽度较窄,甚至比单个字符窄,判断其为不可识别的字符进行返回。如果字符较宽,尝试使用分割算法对字符进行分割判断。
   2. 滴水分割算法通过模仿水滴滴落来对字符进行分割。因此,在分割之前,需要对水滴低落的位置进行选择。首先可以通过遍历的方法进行选择,对于第一行的每一个像素,选择其作为分割的起始点,选择所有起始点中分割后置信度最高的方法。这种选取方法往往能得到滴水分割的最优解,但是其时间复杂度往往很高。如果采用简单的起始点选择策略,可以大大的优化算法的时间复杂度。对图像从上至下逐行进行扫描,当一行存在两个或两个以上的非0像素(0代表白色像素,1代表黑色像素)时,选取最左和最右非0像素之间的一个位置作为分割起始点,通常选取第一个非零像素右边的相邻像素作为分割起始点。
   3. 使用滴水分割算法对字符进行分割,具体的分割方法见本文第3、4部分。
   4. 对分割后的字符进行识别,如果置信度达到要求,则接收分割后的两个字符。如果置信度较低,则将起始点向右循环移动一个像素,重新分割,重复步骤3。如果所有的起始点都进行尝试后,仍然没有可信的分割方式,判断该图像为不可识别的字符。

3. 传统滴水算法

   因为传统滴水算法从上往下滴落,只需要考虑左右相邻像素,以及下方以及斜下方的三个像素,如下图,通过比对这五个像素的值,调整水滴的滴落方向。
mat
   水滴下落方向的选择如下图( w 代表白色像素, b 代表黑色像素, * 表示不关心其颜色)
Next pixel
   当遇到情况5和情况6时,需要附加额外的条件。这两种情况下,像素都尽可能的向一个方向移动,直至遇到黑色的像素点或者5、6以外的情况才会停止。而且当遇到 5...56...65 或者 6...65...56 这样的情况时,无视其周围的像素值,直接向下移动一个像素,防止像素点在图像的一行中不断震荡。

4. 惯性滴水算法

   传统滴水算法存在缺陷,滴水算法倾向与寻找距离顶端最远的分割点,但这个分割点不一定是正确的分割点(如下图)。同时,传统滴水算法在手写数字中,很容易遇到毛刺或其他局部极小点,陷入到其中是往往导致不理想的分割。
split
   惯性滴水算法通过对传统滴水算法的改进,来避免传统滴水算法中的缺陷。
   惯性滴水算法通过给“水滴”赋予一个“惯性”的属性,通过惯性,以及周围像素的情况,来共同决定水滴滴落的方向。
   惯性滴水算法值需要在遇到情况1和情况3时才考虑惯性的影响,其余情况仍然按照传统滴水算法的下落位置分割。在情况2和情况6的操作中,会赋予像素向左的一个惯性值。在情况4和情况5的操作中,会赋予像素向右的惯性值。在遇到情况1和情况3时,需要同时考虑惯性以及“重力”的影响。在情况1中,“重力”与分别与向左或向右的惯性结合,像素不会垂直下落,而会移动到左下角或者右下角。在情况3中,只需要考虑右的惯性,向左的惯性对下落不产生影响。
   惯性滴水算法能解决一部分分割点错误的情况,但仍然不能避免惯性滴水算法陷入到毛刺中。为此,可以通过调整水滴的宽度为 2B+1 来避免这种情况,该算法称为大滴水算法。通常 B 选择 0,1,2 选择为0时,退化成普通的惯性滴水算法。
   使用传统滴水算法,惯性滴水算法,大滴水算法进行图像分割的对比如下图,从左至右依次为传统滴水算法,惯性滴水算法,B为1的大惯性滴水算法,B为2的大惯性滴水算法。
sample

参考文献:

  1. Inertial and Big Drop Fall Algorithm By Xiujuan Wang, Kangfeng Zheng, and Jun Guo, 2006
  2. Segmentation of Numeric Strings By G. Congedo, G. Dimauro, S. Impedovo, G. Pirlo , 1995