【文献翻译】Detecting Text in Natural Scenes with Stroke Width Transform
原文 Detecting Text in Natural Scenes with Stroke Width Transform
1. Introduction
相对于扫描印刷页、传真和商业卡片，检测自然场景中的文字对于许多计算机视觉应用都是非常重要的一步。例如视障人士提供计算辅助、商业中的地理位置自动编码和在城市环境中的机器导航。在室内或室外的环境中检索文字可以为各种各样的视觉任务提供上下文线索。另外可以看出，图像检索算法的表现十分依赖于文字定位模块。例如，对于两本有着相同封面设计，但是不同文字的书，可以证明的是，如果不利用文字定位和 OCR 那么几乎不可能将它们区分开来。在最近的研究中有很多都是关于文本定位的问题[1,2,3,4,5,6,7]。有两个竞赛（Text Location Competition at ICDAR 2003 [8] 和 ICDAR 2005 [9]) 被举行以用来评估相关技术的水平。竞赛的结果表明这里依旧有很大的改进和提升空间 (ICDAR 2005 的冠军为 67% 的召回率和 62% 的准确率)。本文的定义了一个合适的图像算法，可以快速可靠的检测文本。这与之前的工作有所不同。本文所述算法称为 Stroke Width Transform （SWT) ，因为其将图像数据从包含每个颜色值的像素转换为最有可能的笔画宽度。最终的系统能都检测文本，并且不受拉伸缩放，方向，字体和语言的影响。
当我们直接使用自然场景图像时，OCR 的准确度缺急剧下降。如 Figure 11 所示。这里有许多原因导致这样的结果。首先，最主要的原因是 OCR 引擎是被设计用来识别扫描文字，并且依赖于将文字与背景像素的分割。这对于扫描文字通常来讲是十分容易的，但是对于自然场景图像来说则是十分困难的。其次，自然场景图像有着十分广泛的成像条件，因此会有噪声，模糊，遮蔽等。最后，对于传统 OCR 来说，文档的布局通常是简单和有结构的，但是对于自然场景图像来说就复杂的多，因为其中文本会少的多，并且在几何和外观上都几乎不存在高可变性的整体结构。
从其它元素中分离文字的一个特征是文字几乎有着不变的笔画宽度。这则可以用来取得可能包含文本的区域。在本文中就利用的这个特征，可以表明的是一个本地的图像操作加上几何推理就可以用来可靠的获取文本。本文工作主要展现的就是如何计算每个像素的笔画宽度。 Figure 1c 显示了该操作的输出，可以用来将文本从高频背景中分隔。使用逻辑和灵活的几何推理将相似宽度的笔画组合在一起形成更大的区域，而这些区域则很可能包含文字。这种推理还可以区分文字和任意的绘画，如 Figure 2。注意，本文不要求笔画的宽度是恒定的，允许其缓慢的变化。
本文所述的方法与之前的方法有所不同，本文并不从每一个像素寻找一个分割特征，如梯度、颜色。本文则是收集足够的信息用来智能的将像素分组。在本文的方法中，一个像素的梯度只有在它有对应的反向梯度时才有意义。几何验证大大减少了检测像素的数量，因为一个笔画将会导致许多的匹配对在一个小范围内大量出现。另一个值得注意的是本文的方法没有使用在其他方法中用到的多尺度金字塔 [e.g. 3, 4, 25]，而是使用了自底向上的信息集成，合并拥有像素笔画宽度的像素构成组件。这使得能够在同一幅图像上在大范围尺度中检测文字。并且由于没有使用几个离散方向的上的滤波组件，因此可以检测任意方向上的笔画。
此外，由于本文没有使用任何的特定语言过滤的机制，如 OCR filtering stage [3] 或在一个与文字有关的候选窗口中统计梯度。这使得本文所述方法称为一个真正的多语言文本定位算法。
并不是所有应用都要求字符识别过程。但如果需要后续的文字识别，那么一个成功的字符定位步骤将极大的影响字符识别的表现。先前的一些算法由于需要对图像区域进行分类，所有无法给出 OCR 所需要的分割掩码。而本文的方法有着足够的信息来精确的进行文字分割。
2. Previous work
之前已经有了大量的工作关于直接从自然场景图像和视频帧中提取文本。最近的工作则是从其他的领域对提取线性特征进行了研究。
关于全面的文本检测方法调研可以看[1, 2]。 通常来讲文本检测的方法可以分为两类：基于纹理的方法和基于区域的方法。基于纹理的方法[e.g 3, 4, 18, 19, 22] 使用多个尺度对图像进行扫描，根据文本的多个属性对像素的邻域进行分类，如边的高密度、文本行上方或下方的低梯度、较高的方差、小波或 DCT 系数。这类方法的不足之处包括由于需要在多个尺度上扫描图像带来的复杂计算、不同尺度上的信息整合问题以及由于实际上只有很小的（或足够缩小的）文本显示了算法所需要的属性因此缺乏精确性。
另一种文本检测则是基于区域的[e.g 5, 6, 23]。在这些方法中，展现了特定属性的像素，诸如近似恒等的颜色、将被分在一起。得到的连通分量将通过几何或者纹理特征过滤掉确定不属于文本的连通分量。这种方法最吸引人的地方是它可以同时的检测在任何尺度下的文本信息，并且不限与水平文本。本文的方法就属于这种类型，但是这里使用的主要特征并不同于一般使用颜色、边缘或强度相似。本文通过测量每个像素的笔画宽度并且合并拥有相似宽度的邻近像素到连通分量，这些连通分量则是可能包含文本的区域。
本文所述方法在在检测笔画宽度方面与文献[7] 中有一些相似。 而然本文所述方法与其又有很大的不同。在文献[7] 中提及的方法水平的扫描图像，寻找一对突然改变的强度（如暗文本在亮背景上）。然后在两个突然变化点之间的区域将被检测颜色稳定和笔画宽度（笔画宽度的范围假定是已知的）。筛选出的区域将被组合成一个大小为 W 的垂直窗口。如果足够的区域被找到，就声明一个笔画存在。这种方法的缺陷就是需要包含一组与待寻找文本相关的参数（如垂直窗口大小 W ）、无法检测垂直笔画并且并检测到的笔画并没有组成字符，单词或是句子。最终其只能检测到近乎水平的文字。其最终所用的测试数据也并不是来自于 ICDAR。本文实现了来自于文献[7] 的度量方法并显示出本文所述方法优于其他方法－见第 4 小节。
其他的方法同样也用到了笔画宽度的思想[21]，但是其仅仅只是寻找到字符的水平笔画，因此它通过遍历所有水平笔画来检测垂直笔画，并通过形态学膨胀将候选区像素连接成一个区域。由于该文章所述方法不能处理任意方向的笔画，因此也没有提供其在 ICDAR 上的表现数据。
最后，文献[25] 使用笔画宽度思想来检测视频中的叠加文本。该方法的局限性包括需要对滤波器的尺度和方向进行积分，并且其同样只关注水平方向上的文本。
本文所定义的笔画与线性特征相关，通常与遥感（提取道路网络）医学影像（血管分割）。由在空中或是卫星拍摄的照片中，道路的宽度和其范围通常是已知的，但是在自然场景图像中的文字笔画宽度则会发生巨大的变换。另外，公路通常是细长的线，弯曲也很少，但是这并不适合去文字。大多数道路检测方法都依赖于上述特征，因此其并不能直接应用与文字检测。通过调查相关技术可以发现[10]， 最好的方法是文献[11]，它利用道路的便是是反平行的这一特征来检测道路中间的点，然后并将这些候选点组合到一起。并没有使用恒定的道路宽度来进行组合。本文的方法对每一个像素的笔画宽度进行密集的投票，从而形成一种更加稳定的笔画识别方法。而不是建一个脆弱并且困难的中心候选分组的过程。另一种方法[12] 使用低分辨率图像寻找线特征，再从高分辨率图像中寻找边缘特征。将其应用于本文检测的情况下，则需要一个完整的多尺度金字塔。另外，小的或是细的文字依旧可能会无法检测出。
通过在血管分段方法的调研[13]。在该领域中通常使用模型拟合，脊线查找(脊线算子、二值化后细化、小波)等方法。在文献[14, 15] 中血管宽度作为一个额外的用户指定的血管跟踪特征。目前并没有通过血管宽度，自底向上的来直接进行血管探测，但这种方法将会在本文中所描述。
3. The text detection algorithm
在本章节中将描述本文所述文字检测算法。首先将定义笔画的概念，然后再解释笔画宽度变化－Stroke Width Transform (3.1) 以及如何将像素组合成字符候选区(3.2)。最后，将叙述将字符这成更大的单词或是文本行结构，以便以更进一步的过滤。算法流程图如 Fig.5 所示。
3.1 The Stroke Width Transform
Stroke Width Transform (SWT) 是一个本地的图像操作，它通过计算每一个像素的最可能的包含这个像素的笔画宽度。它将输出一个与输入图像大小相等的图像，但其中的每一个元素都包含了与像素关联的笔画宽度。本文定义笔画宽度是一个图像中的一个连续部分，并且形成了一个宽度几乎一致的条带，如图 Figure 3(a) 所示。本文假设我们并不知道其笔画的宽度，仅仅是找到它。
最初每一个元素的的 SWT 将被设置成 $\infty$ 。为了发现笔画，本文首先利用 Canny edge detector [16] 计算图像的边缘信息。然后考虑每一个边缘像素 $p$ 的梯度方法 $d_p$ ，如图 Fig. 3b 所示。如果 $p$ 在一个笔画边界上，那么 $d_p$ 一定大致的垂直于笔画的方法。接下来做一条射线 $r = p + n \cdot d_p，n > 0$ 直到边缘像素 $q$ 。令像素 $q$ 梯度方向为 $d_q$ 。如果 $d_q$ 的方大致上与 $d_p$ 的方向相反 ($d_q = -d_p \pm \pi /6$) 。那么每一个 SWT 输出图像中的与 [$p, q$] 相关的元素元素 s 都指定其笔画宽度 $| \overrightarrow{p - q} |$ ，除非已经存在了一个更小的值，如图 Fig. 4a 所示。另一方面，如果 $q$ 没有被找到，或者 $d_q$ 的方向并不是 $d_p$ 的反方向，那么这条射线则是无效的。 Figure 3 显示了 SWT 的计算过程。
如图 Fig. 4b 所示，SWT 值可能会处于更加复杂的情况中，如拐点。如果用上述方法计算其所得到的笔画宽度并不是其真实的笔画宽度。因此本文将该笔画遍历所有保留的射线，计算其所有像素的 SWT 中值 m。并且将所有高于 m 的笔画宽度值重新设置为 m。
这里描述的 SWT 算法对于边缘像素的数量是呈线性的，在训练阶段确定笔画宽度也是呈线性的。
3.2 Finding letter candidates
SWT 的输出图像中每一个像素均包含了其最可能属于的笔画的宽度。算法的下一步就是将这些像素组合成字母。在本节中，本文将描述一组为此目的使用的相当普遍的规则。
两个相邻的拥有相同笔画宽度的像素将会被聚合在一起。为此，本文修改了经典的 Connected Component 算法[17]，将关联规则从二进制掩码更改为比较像素的SWT值的判断。一个传统的比较就可以满足，如果两个相邻像素的 SWT 比值不超过 3.0 那么其分为一组。这些本地的规则将会保证光滑变化的笔画宽度也同样将会被组合在一起，因此也允许更精细的字体和透视变形，如图 Fig. 8 所示。为了适应亮字暗底，或其相反，本文将运行两次该算法，一次沿着 $d_p$ 方向，另一次沿着 $-d_p$ 方向。
接下来需要识别出可能包含字符的部分。为此文本使用了一组相当灵活的规则。规则的参数将通过训练集获得[8]。 首先进行的是计算每一个连通组件的中笔画宽度的方差，并剔除掉方差过大的连通组件，例如植物，它们在大多数自然场景中包括城市和乡村都很可能出现，并且很难将其与文字区分。如图 Figure 1(c) 所示，这个测试足以区分文本区域，其比植物更加一致。其学习阈值是特定连接组件的平均笔画宽度的一半。
许多对自然图像的处理会可能会生成细长的连通域，这些连通域肯定是不会包含字符的。使用一些额外的规则可以剔除掉这些连通域。例如限制其纵横比在 0.1 到 10 之间。同样的，本文也限制其纵横比在连通分量的直径和其不超过的 10 的笔画宽度中值之间。
另一个常见的问题是连通分量可能会围绕着文本，例如符号。本文通过限制其一个组件的边框不会超过其他两个组件来消除这类影响。
最后，组件的尺寸过大，或者过小都可能被忽略。在本文的训练集中，限制了字体的高度为 10 到 300 像素。使用高度测量可以使得能探测到粘连的草书，如手写，Arabic 字体以及小字符由于边缘检测阶段的不完美以及噪声产生的粘连。
剩余的连通分量则被认为是包含字符的候选区域，并且在下个章节将描述如何将这些区域组合成词或句。所有在几何上的测量的阈值都是通过对训练集的优化得出的。具体来说，在训练集上，我们使用 OTSU 算法进行自适应二值化，计算出每个边界框中表示字母的连通分量，接下来再提取连通分量。 再不断的对每个过滤参数进行修改，最终使得 99% 的连通分量都能被检测到。
3.3 Grouping letters into text lines
为了更进一步的提高算法的可靠性，本文进一步的研究了将字符进行分组。寻找这样的组是一个重要的过滤机制，因为单个字母通常不会出现在图像中，这种推理允许我们去除随机分散的噪声。
文本的另一个重要的暗示是其通常呈现一个线性的结构。同一行的文字应该具有相似性，包括相似的笔画宽度、字符宽度、高度以及字符间距。这些推理被证明是直接的，有价值的。例如，一个灯柱挨着一个车轮不会被错误的认为是字符 “O” 和 “I” 的联合，因为其的灯柱的高度要比车轮高很多。如果两个候选字符有着相似的笔画宽度（笔画宽度中值的比值小于 2.0），高度比不超过 2.0 （由于字符存在大小写），字符间距不超过较宽字符的 3 倍，那么本文将考虑其是否可能属于同一为本行。除此之外，候选字符的颜色均值同样也会被比较，在同一个词的字符通常来讲有着相似的颜色。这些所有的参数都是通过队训练集优化的得出的，如在 3.2 节所述一样。
该算法的下一步是将上述测量过的候选字符聚合成链。首先，每个链由一对字符组成。如果两个链公用一端，并且有相似的方向，那么这两个链可以合并在一起。这个过程直到没有可以合并的链为止。每一个产生的足够长度（至少有 3 个字符）的链则被认为是一个文本行。
最后，文本行将被分割成单独的单词，通过使用一种启发式算法，计算连续字母之间的水平距离直方图，并估计分隔单词内字母距离和单词间字母距离的距离阈值。但是通产来讲并不需要这一步，本文进行这一步是为了与其它[8] 方法在 ICDAR 2003 数据库上进行比较。在为本文的数据结果展示中并没有使用这个步骤，因为已经标记了整个文本行。
4. Experiments
为了提供一个基本的比较，本文在一个公开的数据集[24] 上运行本文所述算法，在最近的两次文本检测比赛中都使用了它：ICDAR 2003 [8] 和 ICDAR 2005 [9]。尽管一些字符检测工作已近在竞赛后公布，但是并没有人声称取得了较好的结果。此外， ICDAR 依旧是使用最为广泛的用来测试自然场景字符检测的数据集。
许多其它的检测方法由于其使用了自定义的数据集，所有无法与其比较。ICDAR 数据集包含了 258 张训练图像和 251 张测试图像。这些图像时全彩色的并且图像尺寸为 307x93 到 1280x960 像素。算法将通过 $f-measure$ 进行比较，其包含了两个度量：准确率和召回率。本文遵循文献[8]，为了完整起见在此描述。
每一个算法的输出都是一组矩形标明检测到的文字（如 Fig. 6)，这里称为评估。一组真正的包含文本的矩形，这里称为目标由数据集提供。匹配 $m_p$ 被定义为两个矩形的交集面积除以包含这两个矩形的最小矩形面积。这个数值为 1 则表明这两个矩形是相同的，为 0 则表示这两个矩形没有交集。对于每个估计矩形，在目标集中找到最接近的匹配，反之亦然。然后，最佳比配 $m(r, R)$ 一个矩形 $r$ 在一组矩形 $R$ 中定义为：
然后，准确率和召回率的定义如下：
其中 $T$ 和 $E$ 分别代表目标矩形集和评估矩形集。
标准的 $f-measure$ 结合使用准确率和召回率来给出一个单一的评价。其相关权重通过一个 $\alpha$ 参数来进行控制。当 $\alpha = 0.5$ 时，召回率和准确率的权重是相当的。
不同的算法在准确率、召回率和 $f-measure$ 上的比较如 Table 1 所示。
为了说明笔画宽度信息和几何过滤的重要性。本文额外的在测试数据集上运行了两次本算法。第一次将所有的笔画宽度值小于 $\infty$ 都设为 5 （变为常数，并不会明显的影响结果）。第二次，关闭几何过滤。在两次运行中准确率和召回率都有所下降（第一次 $p=0.66,r=0.55$ ， 第二次 $p=0.65,r=0.5$）。这足以表明笔画宽度信息的重要性。
在 Figure7 中，展示了文本没有被检测到的典型情况。这是由于文字高亮、透明、过大或者过分的模糊，以及弯曲的基线造成的。
为了能和文献[7] 中的结果比较，本文已经实现了文种提及的比较方法。本文所述算法的表现如下： 字符召回率为 79。04%，笔画准确率为 79.59%（本文定义的笔画与其文中有所不同，本文统计了目标矩形内和外的连通分量）。另外，本文还统计的像素准确率，目标矩形内的像素数量除以探测到的像素数量。这个比率为 90.39%。这个结构要优于文献[7] 中的结果。
此外还提供了在 ICDAR 数据库的结果，我们还提供了一个新的基准数据库用来进行测试，它可以免费的从网上下载，包含 307 张彩色图像，分辨率从 1024x1360 到 1024x768。这个数据库要比 ICDAR 难，由于其包含植物、重复的图案，如窗户，如果不利用 OCR 几乎无法区分出其中的文字等。本文所述算法在这个数据库上的表现如下：$precision: 0.54, recall: 0.42 f-measure: 0.47$ 。测量方式如文献[8] 所述。
本文所述方法的副产品之一则是字符掩码，这个掩码可以用作文本分割掩码。为了评估算法产生的字符掩码的可用性，本文提供了一个现成的OCR包，其中包含几个包含文本的自然的图像，此外，还有表示文本背景分割的二值化图像。OCR 在两种情况下识别的结果如 Figure 11 所示。
5. Conclusion
本文中叙述了如何利用笔画宽度的方法来进行文本检测，并且定义了笔画还由此得出的一个有效的计算算法用于计算这个新特征。提取该特征，则可以提供一个可靠且灵活的方式进行字符检测。不同于之前的文本检测使用的特征，本文提出的 SWT 能够在非局部范围（笔画宽度有时取决于相距很远的像素所包含的信息。）进行密集评估（计算每一个像素）。与最近可用的测试相比，本文所述的算法达到了第一名，比报告中的速度快了大约15倍。该特征具有足够的优势，可以单独使用，不需要像以前的一些方法[3]中使用的实际字符识别步骤。这允许我们将该方法应用于许多语言和字体。
这里依旧有一个能够改进的地方，聚合字符可以通过考虑笔画的方法来改进聚合的结果。这将能够检测出文本行是弯曲的情况。我们将在将来进行这方面的探索。