论文阅读--基于贪吃蛇算法和部首识别的手写文本切分

Article

Data

目的

解决对手写中文文本中：

结论

以陕西省某高中试卷中1542行手写文本作为实验数据进行了算法验证，结果表明，该算法切分正确率可达到82.15％

背景

方法

本算法通过模拟贪吃蛇在文本图像中爬行得到非线性切分路径.

爬行规则

爬行规则：

• 待切分文本图像中的字符作为障碍物
• 给定起点
• 爬行趋势为竖直方向
• 遇到障碍物沿障碍物边缘向下
• 进入字符凹陷区域，回溯
• 到达终点得到的有效路径形成原始切分路径

综上可知蛇的爬行不会穿过字符笔划，减少了字符损伤

爬行顺序：

• 表示当前位置

$b$表示black字符像素点

$w$表示white背景像素点

★表示任意，即不影响决策

=>表示像素转换，爬行策略优先级依次为$p_a - p_g$

本算法对手写文本进行两次切分：

1. 粗切分：分割非粘连字符和交错字符
2. 二次切分：将1的结果结合宽高比阈值判断粘连字符，并以候选粘连点作为蛇爬行的起点，切分粘连字符

候选路径优化

基于多重约束规则的候选路径优化

爬行后的路径存在冗余，本文通过结合：

• 字符平均宽度
• 水平重叠率
• 分段投影特征

建立路径优化规则，从而得到文本候选切分路径。

水平重叠率?

左右两字符快在垂直方向上的重叠长度与两字符块宽度比值的最大值

$$
L_x = max(\frac {|X_L - X_R|}{W_L}, \frac{|X_L - X_R|}{W_R})
$$

• $W_L$左侧字符宽度

• $W_R$右侧字符宽度

• $X_L$左侧字符横坐标最大值

• $X_R$右侧字符横坐标最小值

• $X_L \geq X_R$

分段投影特征

以像素点$(y,x)$为界，将$(x,y)$所在列像素点分为上下两个部分，分别统计字符像素个数，$G_1(y,x)$ 和 $G_x(y,x)$分别表示点$(y,x)$上方和下方的字符像素个数。

约束规则

定义

对于字符图像$I$，设宽高分别为$W,H$，对该图像进行二值化操作后，令：

• $I(h,w)=1$表示字符像素
• $I(h,w) = 0$表示背景像素
• $h = 1, 2, 3, …, H$
• $w = 1, 2, 3, …, W$
• 路径列表$P=[P_1, P_2, P_3,…,P_i,…,P_n]$
• 路径$P_i = {(y_1,x_1),(y_2,x_2),…,(y_m,x_m)}(i=1,2,..,n)$

约束

1. 若$P_i$到$P_{i+k}(0 < k \leq n-i)$之间无字符像素且重点相同，则从该重点向起点回溯，得到一条长度较短的路径。回溯时使用爬行规则，但趋势向上左右相反
2. 若$P_i$左右两侧字符快的$L_x(重叠率) \geq T_x(重叠率阈值)$，则删除$P_i$。（本文取$T_x= 50%$）
3. 若$P_i$为非线性路径，存在$(y,x) \in P_i$,
   1. $G_1(y,x) = 0$则从该点向上形成垂直路径
   2. $G_2(y,x) = 0$则从该点向下形成垂直路径
   3. 删除$P_i$
4. 若$P_i$到$P_{i + c} (0 < c \leq n-i)$之间无字符像素，只保留$P_{i+c/2}$

候选粘连点提取

基于轮廓曲线极值和骨架特征的候选粘连点提取

本文将粘连分为两类：

1. 简单粘连：只有一笔粘连，一般出现在字间笔划薄弱位置
2. 复杂粘连：多笔粘连的同时还存在笔划重叠，粘连点处的结构与汉字内部结构相似，多为笔划交叉点

如下图所示的AD区域的粘连点为简单粘连点，BC中的为复杂粘连点

本文使用基于轮廓曲线局部极值提取简单粘连点。

使用基于骨架特征提取复杂粘连点。

最后结合笔划估计宽度、两点距离、四方向笔段长度、邻域像素个数建立粘连点筛选机制，确定候选粘连点。

定义

轮廓曲线

由每列字符像素边界点坐标组成：

上轮廓曲线
$$
S_{up}(x) = min { y |I(y,x), x=1,2,…,W }
$$
下轮廓曲线
$$
S_{down}(x) = max{y|I(y,x),x=1,2,…,W}
$$

笔划估计宽度

水平、竖直扫描二值图像，统计连续字符像素个数$m_i(1 < m_i < W/3)$，及评论$n(m_i)$，按$n(m_i)$降序排列，取前3个$m_i$计算均值得到笔划估计宽度$U_m$，即
$$
U_m = [\frac {\sum _{i = 1} ^ 3 m_i n(m_i)}{\sum _ {i=1} ^ 3 n(m_i)}]
$$

四方向笔段长度

某一特征点分别在0°、45°、90°、135°的四个方向上连续字符的个数

获取轮廓曲线

然后采用 差分遍历向量法 反别计算上轮廓曲线的波峰和(% emp 下轮廓曲线的波谷 %}，得到局部极值点，将其加入粘连点集合。

以图像左下角作为原点绘制轮廓曲线得到如下图：

计算骨架点

利用[细化算法](https://kns.cnki.net/kcms/detail/detail.aspx?dbcode=CJFD&dbname=CJFDLAST2020&filename=JYRJ202007018&uniplatform=NZKPT&v=EO30oldB0qFHz6WIVpa_Hy8kR-Yt5zXwCPy4vH16IO2ZxIeHIJtdaj-eeumC_7vz)提取字符骨架，扫描字符像素点，若其八邻域内有3个及以上字符像素，则认为该点为骨架点。

但由于骨架提取过程中存在一定程度的毛刺和畸形，导致提取到冗余骨架点，需进行过滤

提取得到的骨架点如下图所示：

冗余骨架点过滤

• 骨架点所在四方向笔段长度均小于$U_m$，认为该点为孤立噪点，删除该点
• 若两个骨架点距离较远，满足$D_s < U_m$，则保留所属笔段方向更多、笔段长度更大的一点。其中$D_s$为两点间距离

筛选后得到的骨架点：

候选粘连点

• 粘连点很少弧线在字符粘连区域边界，因此保留$[\frac{1}{3}W_{avg},W_{cur}-\frac{1}{3}W_{avg}]$内的粘连点，$W_{cur}$为当前字符宽度，$W_{avg}$为平均字符宽度
• 保留距离轮廓粘连点$2U_m$范围内的骨架点
• 保留相邻$U_m$范围内领域像素个数最小的粘连点

基于贪吃蛇的文本切分算法

粗切分

根据手写字体字间笔划稀疏，的特点，粗切分起点由垂直投影值和笔划宽度自适应得到

对于垂直投影$V = [V_1, V_2,V_3, V_W]$，粗切分起点$(y,x)$，应符合：
$$
\begin{cases}
V_x \leq \xi U_m \\
I(y,x)=0
\end{cases}
, 1 \leq x \leq W, y = 1
$$
$\xi$为调节参数吗，越大蛇的初始爬行路径越多，本文取3，得到起点集合$A(x) = {(y,x) | y = 1, x \in [1,W]}$

粗切分算法（SnakeSegmentB）实现过程如下：

1. 输入二值化的文本图像$I$
2. 初始化切分路径列表$P$，一次爬行轨迹集合$P_i$
3. 计算垂直投影列表$V$和笔划宽度$U_m$
4. 计算贪吃蛇爬行起点集合$A(x)$
5. 遍历$A(x)$，根据(% emp 爬行规则 %}向下爬行，将有效轨迹坐标加入$P_i$；若$P_i$终点坐标在图像最后一行，则将$P_i$加入$P$；否则，$P_i$置空；直到遍历结束
6. 对$P$，应用规则1-4
7. 输出手写文本切分路径列表$P$