SWT论文笔记

传统图像处理算法SWT论文阅读笔记

引言

该算法由Boris Epshtein等人于2010年提出并于2010年的CVPR上发表论文《Detecting Text in Natural Scenes with Stroke Width Transform》。本文提出了一项新的用于图像目标检测的特征：Stroke Width，并提出了对其进行量化的方法，通过实验证明了使用该特征进行文字检测能够得到不错的效果。该算法IDCAR2003竞赛中使用的数据集上取得了73%的查准率与60%的召回率，并且仅花费0.94秒，是以往算法的1/15。

论文中描述的算法包括三个主要步骤：

利用canny算子检测图片边界
计算笔画宽度变化Stroke Width Transform，得到SWT图像
通过SWT图像得到多个连通域
通过定义规则过滤一些连通域，得到候选连通域
将连通域合并为文本行

计算笔画宽度

本文定义了Stroke Width特征，该特征描述了某一笔的宽度。SWT算法进行文字检测时就是利用同一笔画的宽度相近进行的。那么，对于图中任一一个像素点，该如何寻找其笔画宽度呢？

本文中提出的方法是利用梯度。

对于如下图a所示的笔画：

对于处于笔画边缘的像素点P，按p的梯度方向进行搜索，找到同一笔画下对应像素p。

图C中射线经过的像素使用当前最小值和笔画宽度进行匹配。

将笔画宽度初始值均设置为无穷大，首先使用Canny算子检测图片边缘信息，计算每个像素点p对应的梯度方向 $d_p$ ，如果p位边界笔画，则沿着射线 $r = p + n*d_p, n>0$ 寻找另一个边界像素点q，如果q的梯度方向 $d_q$ 与 $d_p$ 几乎相反，则就可以使用这两个点来计算该段笔记的长度。

判断两个梯度方向相反时使用如下方式：

$(d_q = -d_p \pm \pi/6)$

若点p的梯度与点q的梯度的反方向夹角在 $\pm \pi/6$ 之间，那么这两点间的距离为一个笔画宽度。

对于找到了q的p点，输出segment值，segment[p,q]段内像素取通过该像素点的宽度的最小值，笔画宽度为：

$segment[p,q] = ||\vec{p - q}||$

对于没找到对应像素点q，或者 $d_p$ 与 $d_q$ 不符合反向条件的点p，则丢弃这条射线。

而对于如下情况：

一个笔画中的像素，可能得到两个笔画宽度。对于图a的情况，将红点p处的笔画宽度设置为最小的那个值。对于图b的情况，两条射线均无法表示笔画的宽度，这是笔画宽度取里面所有像素计算得到的笔画宽度的中值作为红点处笔画的宽度。

考虑到背景和文字的亮度关系存在两种情况：

文字比背景亮
背景比文字亮

因此这一步骤往往需要执行两次，最终得到一张SWT图像。

计算连通域

通过上述步骤得到SWT图像后，该图像中每个像素点的值为对应像素所在笔画的宽度，即SWT值。

这一步作者通过修改经典的Connected Component algorithm算法[1]，将连接规则从binary mask改为比较相邻像素SWT值实现。

基于同一笔画中笔画宽度相近这一理论，我们可以认为相邻像素的SWT值如果近似，那么将这两个像素划分为一个连通域。

现将相邻像素SWT值比不超过3.0的归为一个连通域。这样就能得到多个连通域。

过滤连通域

对于得到的多个连通域，可能存在噪声影响，例如下图所示的黑色区域均为连通域：

下面我们希望通过过滤这一操作，仅保留最有可能是文字的连通域，得到效果如下：

作者使用了ICDAR2003数据集进行了一系列相对宽松的规则学习。最终过滤规则如下：

如果某连通域的内方差过大（内方差过大指连通域的内方差大于平均笔画宽度的一半），则认为该连通域不是有效的。该规则主要针对自然场景中树叶等干扰物的影响
如果某连通域过大（宽度大于300）或过小（宽度小于10），则认为该连通域不是有效的。
如果连通域的直径与连通域SWT的中位数的比值超过10，则认为该连通域是不是有效的。该规则主要针对自然环境中长而窄的分量
考虑到类似广告牌的情况，连通域将会包裹在文字四周，作者通过限制连通域的外接矩形不能包括超过两个其他的连通域，来区别出这类文字。

连通域合并

文中认为，在自然场景中，一般不会只有单个字母出现，所有将连通域合并为文本有利于进一步将噪声排除。

当两个连通域满足下面条件时，认为这两个连通域是一对：

两个连通域中值的比小于2.0（连通域中值，指的是连通域中所有像素值的中值）
两个连通域高的比小于2.0（连通域的高，指其外界矩形的高）
两个连通域之间的距离小于较宽的连通域宽度的3倍（连通域之间的距离为连通域外接矩形中心点之间的距离）
两个连通域的颜色相似（代码可用两个连通域对应于原图区域的像素均值代表该连通域的颜色）

得到两两连通域组成的多对连通域后，如果有两对连通域有共享的连通域，共享的连通域都在连通域对的一端（即连通域的首端或者尾端），且方向相同（方向用一个连通域中心到另一个连通域中心的方向），就将这两对连通域合并为一个新的连通域组，依次进行，知道没有连通域对需要合并则合并结束。

最后将合并完的结果中滤除小于3的连通域的连通域组得到的最终结果，认为是一行文字。

Reference

[1] B. K. P. Horn, “Robot Vision”, McGraw-Hill Book Company, New York, 1986.