MSER快速自然场景倾斜文本定位算法

张开玉 邵康一 卢迪

摘 要：针对在自然场景中文本定位需要大量样本训练导致算法运行速度较慢且倾斜文本难以定位的问题，提出了一种基于最大稳定极值区域（maximally stable extremal regions，MSER）结合层次聚类的快速自然场景倾斜文本定位算法。利用MSER椭圆拟合的方法对图片进行最大极值稳定区域的选取，并根据拟合椭圆的自身特征和在图像上的位置特征，过滤掉大部分的非文本区域，筛选出文本候选区域。运用层次聚类的思想，快速对文本区域逐层聚类融合，最终将单个的文本区域合并成单词区域，实现高效的倾斜场景文本定位。实验结果表明，与传统的定位算法相比，该算法在没有损失定位精度的情况下运算速度有明显的提升。

关键词：场景文本;最大稳定极值区域;层次聚类;椭圆拟合

DOI：10.15938/j.jhust.2019.02.012

中图分类号： TP391.41

文献标志码： A

文章编号： 1007-2683（2019）02-0081-08

Abstract：Aiming at the problem that text localization requires a large number of training samples in natural scenes， which leads to low speed of algorithm running and it is difficult to locate skewed text， a fast natural scene skewed text localization algorithm based on maximally stable extremal regions（MSER） with hierarchical clustering is proposed . The method of MSER ellipse fitting is used to select the maximally stable extremal regions of the images， and according to the characteristics of the fitting ellipse and its position on the images， the majority of nontext regions are filtered out and the text candidate regions are selected. By using the idea of hierarchical clustering， the text regions can be clustered gradually and merged into text regions rapidly. Finally the individual text regions are merged into word regions， which can achieve efficient localization of skewed scenes. Experimental results show that the speed of this algorithm has improved significantly without loss of locating accuracy compared with traditional positioning algorithms.

Keywords：scene text; maximally stable extremal regions; hierarchical clustering; ellipse fitting

收稿日期： 2017-04-20

基金项目： 黑龙江省自然科学基金（面上项目）（F2016022）.

作者简介：

邵康一（1992—），男，硕士研究生;

卢 迪（1971—），女，博士后，教授.

通信作者：

张开玉（1978—），男，博士研究生，副教授，Email：gotoayun@126.com.

0 引 言

自然场景文本定位是一种利用计算机将自然场景图像中的文本定位出来的方法，这种方法不仅要求定位的精度，还要求定位的速度。Ye等[1]将自然场景文本检测的方法分为了两大类：滑动窗口法和基于连通的方法。在滑动窗口法中Chen等[2]根据综合平均密度特征、密度方差以及直方圖特征，通过Adaboost分类器定位。伊芳等[3]首先提取视频图像中的连通区域并分析视频文本的5类特征，最后通过Adaboost强分类器取得正确的文本区域。但是此类方法比较复杂，需要对特征样本进行训练，花费时间也比较长。近年来，基于连通的方法逐渐体现出它的优势，其中MSER算法较为突出。Koo[4]等使用结合MSER区域检测子的文本定位方法，获得了2011年ICDAR大赛的冠军。Yin[5]等使用结合枝剪的MSER区域检测子的文本定位方法，获得了2013年ICDAR大赛的冠军，这体现了MSER在当前文本定位中的强大实力。而后的2015年的ICDAR文本定位大赛变得更加具有挑战性，相较于水平排列文本类型较多的ICDAR2011[6]和ICDAR2013[7] 文字/字符图像数据库，ICDAR2015[8]数据库更多包含的是大场景中多方向的倾斜文本信息。近几年对于倾斜文本定位的研究也有一定的发展， Zhu[9]使用从像素级，文本级，文本行级三个层面来设计的基于卷积神经网络和支持向量机（SVM）的三层结构场景文本定位算法对倾斜文本进行定位，虽然效果优秀，但是在算法中需要在文本级中利用卷积神经网络对纹理特征进行提取与分类以及在文本行级利用SVM对HOG特征进行分类，算法复杂程度较高且需要进行样本训练。受RANSAC（Random Sample Consensus）算法[10]启发，一种基于相似连通分量与直线拟合的文本区域提取算法被用于倾斜文本的定位，此算法根据相似样本的聚类和直线拟合模型的检验完成对倾斜文本的定位。虽然这种方法不需要进行样本训练，但是此方法会因为文本附近细微的干扰影响整个文本区域的定位。

传统的文本定位算法存在两个方面的问题，一是对于倾斜文本的定位效果不佳，例如文[11]中采用的双向投影算法，在只有水平方向文本的情况下定位效果不错，但是对于倾斜文本定位效果就不是很理想。二是运行花费时间长，基于分类器的文本定位算法[2，3，9]，需要花费大量时间在样本的处理与训练上，虽然定位精度高，但是耗时较长。

基于上述两个方面的问题，本文提出了一种基于MSER结合层次聚类的快速自然场景倾斜文本定位算法，运用MSER快速地对图像文本区域进行定位，避免了样本处理与训练耗时长的问题，再利用层次聚类的思想，对倾斜方向的文本有效地进行融合，以解决倾斜文本定位效果不佳的问题。

1 算法结构

本研究设计的算法流程如图1所示。

1）把需要处理的彩色图像进行灰度化处理，利用MSER椭圆拟合算法对灰度图像上的MSER区域进行快速提取。

2）通过粗过滤和细过滤对提取的MSER区域进行过滤筛选，删除非文本区域。

3）运用层次聚类的思想进行文本融合。通过字符间距粗分类、字符链条件过滤、相似度字符链合并和RGB均值单字符与字符链筛选4个步骤将分散的文本区域合并成单词区域，最终达到所需要的效果。

2 MSER拟合椭圆场景文本定位算法

2.1 MSER拟合椭圆算法

最大极值稳定区域（MSER）[12]因为其具有仿射不变性以及对文本区域较为敏感的特点[13-15]，因此被广泛应用于自然场景图像的文本定位。但MSER所提取的区域一般是不规则的，这样的区域不利于进行特征描述[4]，因此本文所用的MSER椭圆拟合算法，利用结构仿射不变的特性将不规则的MSER区域拟合成规则的椭圆度量区域，在MSER椭圆拟合算法中，每一个代替不规则 MSER区域的拟合椭圆都会有各自的编号记录在matlab工作区（workspace）的MSERRegions中，MSERRegions{region1，region2，region3，…}，在每一个region中记录着对应MSER区域拟合椭圆的丰富信息，其中包括了拟合椭圆长轴与短轴的长度（Axes）、中心点坐标（Location）、拟合椭圆的方向，即长轴的方向（Orientation）以及被拟合椭圆包围的MSER区域中所有像素点的坐标信息（PixelList）。非文本区域过滤的大致思路就是利用包含在拟合椭圆中的信息，设置多层条件过滤，将不符合条件的拟合椭圆从MSERRegions中删除，而符合条件的保留其中，最终达到快速有效地删除非文本区域的效果。

2.2 基于拟合椭圆特征的非文本区域过滤

对图像进行MSER区域提取之后，图像上呈现着大量用拟合椭圆圈出的疑似文本区域，如图4所示，其中包括文本区域与非文本区域，因此需要根据文本区域与非文本区域拟合椭圆之间的特征差异对非文本区域进行删除。

将非文本区域的过滤过程分为粗过滤过程与细过滤过程，粗过滤的作用为大范围地过滤图像中的非文本区域，为后续的细过滤减少不必要的运算工作量。细过滤是在粗过滤的基础上，对与文本区域特征较为相近的非文本区域进行过滤，为后续的文本融合做好铺垫。

2.2.1 非文本区域粗过滤

非文本区域的粗过滤过程是一个过滤自然场景图像中较为明显的非文本区域的过程。这些非文本区域可以通过拟合椭圆自身的特征和空间位置快速地大范围地过滤，为非文本区域的细过滤过程做好铺垫。通过对大量文本区域与非文本区域拟合椭圆的特征进行观察和比较，可以发现文本区域拟合椭圆的长轴与短轴的比值通常在一定的范围之内且通常位于图像的内部，很少位于图像的边缘，通过这2个特征就可以大致确定文本区域的位置。将拟合椭圆的长轴与短轴的比值记为α，经过反复试验当α的阈值设为7时过滤效果比较理想。当疑似文本区域的α值小于7时，这个区域就被视为非文本区域，从MSERRegions中删除。接着通过拟合椭圆内所包含的MSER像素信息就能快速地过滤位于图像边缘的非文本区域。当拟合椭圆所对应的MSER区域含有图像边界像素点时，就可以判断这个区域为非文本区域，可以从MSERRegions中删除。就此完成了非文本区域的粗过滤，粗过滤效果如图5所示。为了更加直观，剔除的部分与背景进行了黑色填充处理。

2.2.2 非文本区域细过滤

经过了非文本区域的粗过滤之后，图像中非文本区域的数量大大降低，但还是存在着许多与文本区域拟合椭圆特征相似、重合嵌套的非文本区域，若不过滤这些区域不仅会使之后文本融合的運算量大大增加，还会让最后的定位结果大打折扣。MSER椭圆拟合算法是将不规则的MSER提取区域拟合成规则的椭圆形，拟合出的椭圆面积与实际的MSER面积存在一定的差异，而大多数的文本区域都是属于比较松散的分布，因此文本区域的拟合椭圆面积与MSER像素面积的比值会比非文本区域更高，利用这个特征可以删除一部分非文本区域。将拟合椭圆面积与MSER实际面积的比值记为 ，经过反复实验测试，将β的阈值设置为2.5比较理想，当疑似文本区域的β小于2.5时，认为此区域为非文本区域。但是也存在一些特殊的情况，例如1、f、l，这些细长的字符的β值通常小于2.5，非常容易造成误删除，因此需要在β的阈值判断后增加一个补偿判断，若被删除的区域中α值大于4且小于7，则不会被删除，继续保留在MSERRrgions中。在图像中还存着许多重合嵌套的拟合椭圆，它们严格来说都是属于文本区域，但是重合嵌套的拟合椭圆会影响后续程序的运算速度和定位效果，因此最理想的效果就是每一个文本区域只对应一个拟合椭圆。通过对重复嵌套椭圆的分析，发现嵌套类型大致可以分为两种，第一种是同一个字符的拟合椭圆重复嵌套，拟合椭圆大部分重合或是近似完全重合;第二种情况是两个字母或是连续的几个字符被选定了MSER拟合椭圆区域，但在这个区域内又选定了其中单个或多个字符的MSER拟合椭圆区域，这种情况中小的椭圆包含于大的椭圆或者是近似于包含于大的椭圆内。对于上述2种情况，过滤的准则为尽量选取较大的拟合椭圆，这样不仅能使字符区域选取得更加完整，还能减少拟合椭圆的数量，加快运算速度。在此设置一个重叠误差，将重叠误差记为OE（Overlaperror），其表达式为

3 基于层次聚类的文本区域合并

定位单个文本区域对文本识别是没有意义的，因此需要将单个的文本区域合并成完整的单词区域。不同于ICDAR2011与ICDAR2013数据库，ICDAR2015数据库越来越来趋向于大场景以及多角度的倾斜文本的定位，而略微倾斜的文本对于水平聚合效果的影响不是很大，但是对于倾斜角度较大的文本效果就非常的差了。为了解决上述问题，本文提出了一种运用层次聚类的思想，先将文本区域中的字符通过距离阈值分类并连接成字符链，再通过计算字符链之间的相似度，将相似程度较高的字符链进行合并，对于未被分类的单个字符或是未被合并的单个字符链，通过与已被合并的字符区域的RGB均值进行比较，保留符合条件的单个字符和字符链，避免了单个字符和字符链的误删除，进一步保证了文本的完整性，因此基于层次聚类的文本区域合并不仅仅是一个文本区域合并的过程，也是一个进一步对非文本区域过滤的过程。这种自底向上的方法使文本合并更为准确，保证了合并时单词的完整性。

3.1 字符链

字符链不仅仅是简单的字符分类，而是一种高级的字符聚合。字符链将分类好的杂乱的单个字符按照图像中字符相邻的顺序连接成一个有顺序的字符整体，从字符链中不但可以了解到最基本的字符个数，而且因为字符链是一个整体，可以从中观察到单个字符中观察不到的特征，利用这些特征能更加利于字符的融合。

3.2 字符链相似度因素的选择

在基于层次聚类的文本区域合并中，最为重要的步骤就是通过计算字符链之间的相似度来合并字符链，因此字符链相似度因素的选择就显得十分重要。多数情况下，在同一个倾斜的文本中即使文本被分成了多个分散的字符链，字符链之间也有着相似的倾斜程度，并且这些字符链都有着相近的字符个数，通过以上两点特征就可以对字符链进行合并。

3.3 具体步骤

基于层次聚类的文本合并具体可以分为4个步骤：第一步为字符间距粗分类，第二步为字符链条件过滤，第三步为根据字符链的相似度进行字符链的合并，第四步为根据RGB均值对单独的字符和字符链进行筛选。

1）计算每个文本区域之间的欧式距离，即每个拟合椭圆中心点之间的欧式距离，再通过一个字符间距的阈值来进行初步的分类。

经过非文本区域的过滤，MSERRegions中还剩余i个MSER区域（region），将字符间距的阈值记为avgdis，通过式（2）计算出阈值avgdis，其中dis表示每个文本到其他文本的欧式距离中最小的2个值的平均值。通过这个阈值就初步得到在距离方面互相有关联的字符组，在同一个字符组中相邻的字符相连就能形成字符链。为了更加直观地看出字符链，图像中用细线连接字符来表示字符链，用灰色和白色的线来区分不同的字符链，效果如图7所示。

2）判断并筛选符合要求的字符链。计算字符个数大于3的字符组中第一个字符与其他字符连线的角度

3）对初步分类的字符链进行进一步的聚合。如果2条字符链至少共享一个相同字符的话，通过计算这2条字符链之间的相似程度来判断这2条字符链是否需要合并。

4）在文本区域合并的第一步中通过字符间距阈值分类后除了字符组之外还存在着未被分组的单个文本区域和在第三步中未被合并的单个字符链，单个的文本区域可能包含着1个字母或是数字，而单个的字符链可能是与整体文本距离较远的文本区域，因此不能直接删除。在一张圖片中，文本区域的字符颜色通常都较为相近，因此这些文本区域的RGB均值也较为相近。通过计算比较这些区域的RGB均值来判断这些区域是否需要删除。RGB均值的定义为

在每个MSER区域所对应的彩色图像中包含着n个像素点，而每个像素点都有其各自的R、G、B值，avgRGB即为每个像素点R、G、B三个数值的平均值，RGB均值即为这个区域中所有像素点avgRGB的平均值。计算每个未被分组的单个文本区域与未被合并的单个字符链区域的avgcolori（i表示未被分组的单个文本区域与未被合并的单个字符链区域的总个数）与所有已被确定为文本的字符链区域的avgcolorall进行比较

根据式（9）就能将不符合条件的区域删除。处理效果如图10所示。

最后计算并画出每个字符链区域的最大外接矩形，就能完成对文本区域的选取。就此完成了非文本区域的过滤与文本区域的合并，最终得到需要的单词区域，最终效果如图11所示。

4 实验结果

本文的算法程序在CPU为i5、主频为3.30GHZ、内存为8G的64位win10计算机上的MATLAB2013进行运行，本文算法使用的图像库为2015年ICDAR大赛场景图像文本定位比赛所使用的图像数据集，该数据集中包含了1000幅图像的训练用数据集以及包含了500幅图像的测试用数据集，因为本文所用的算法不需要事先进行样本训练，所以在整个数据集中只使用测试用数据集。测试用数据集中的图片是通过头戴式相机拍摄得到的，其中文本内容多为英文和阿拉伯数字，文本场景多为店铺的广告牌，商场指示牌，街道路牌以及街边广告，共500幅，图像的分辨率均为1280×720。

ICDAR2015所用的自然场景文本图像相较于前几届ICDAR难度有较大的提升，主要体现在图像中的文本背景更加复杂多变以及图像中多方向的文本信息。ICDAR大赛自ICDAR2003制定了新的评价机制[16]，具体为用3个参数来衡量算法的定位结果，分别是召回率（recall），准确率（Precision）和f值。召回率的定义为正确检测到的文本数与真实文本总数的比值，准确率的定义为正确检测到的文本数与所有检测到的文本数的比值，f值的定义为

本文算法通过ICDAR2015中的500幅测试图像与ICDAR2015的多个优秀算法以及文[11]的算法进行比较，比较的内容包括2个方面，一是用f值的大小来衡量算法的定位精度，二是用算法处理测试图像的平均时间来衡量算法的运算速度以及运行时间的方差来衡量运行速度的稳定性。比较结果见表1和表2。

从表1中可以看出，本文算法因为使用对文本区域较为敏感的MSER算法，召回率可以达到50.21%，但是相较与使用样本特征训练的算法，例如BaiduIDL和SRCBTextProcessinglab，在准确率方面有所欠缺，但还是在最终取得了45.59%的f值。从表2中可以看出本文算法以13.53s的平均运行时间取得第一，并且运行速度更加稳定。综合定位效果和运算时间，本文算法在降低了运行时间的同时也没有损失定位精度。

再对比文[11]中的定位算法，如图13与图14所示，在左侧幅图像的对比中，由于本文算法在文本融合最后对单独的文本区域和单独的字符链区域做了RGB均值筛选，因此对于文[11]算法没有删除的非文本区域有着更好的过滤效果。如图13左侧图像所示，经过文[11]算法处理后遗留着一块非文本区域，而本文算法在文本融合时通过比较两块区域的RGB均值（文本区域字体为蓝色灯光，非文本区域为红色与白色的灯光），两者的RGB均值相差大于25%，因此能够删除非文本区域。在右侧第二幅图像的对比中，由于文[11]中的双向投影算法使用到了水平穿越线，而水平穿越线的插入位置为此文本区域横向投影向量最大值的中点处。倾斜的文本区域与水平穿越线产生了一定的夹角，使得水平穿越线未能穿过文本区域中k字母的中心点，导致k字母无法被定位到。而本文算法使用的是从部分到整体的文本融合方法，相较与整体融合方法，效果有明显的提升。

5 结 论

针对现有算法定位速度较慢且难以定位倾斜文本的问题，提出了一种基于MSER结合层次聚类的快速自然场景倾斜文本定位算法，并从理论上以及MATLAB实验中证明了本文算法的可行性和合理性。使用MSER椭圆拟合的方法快速有效地删除自然场景图像中的非文本区域，降低了文本定位所需的时间。运用层次聚类的思想，在有效定位倾斜文本的同时还能对残留的非文本区域进行进一步的滤除。实验表明本文算法在有效降低运行时间的同时没有损失对倾斜文本的定位精度。

参 考 文 献：

[1] YE Q，DOERMANN D. Text Detection and Recognition in Imagery： A Survey[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2014， 37（7）： 1480.

[2] CHEN XR， YUILLE A. Detering and Reading Text in Natural Scenes[C]// IEEE Computer Vision and Pattern Recognition，Washington，D.C.，USA，2004：366.

[3] 尹芳，郑亮，陈田田.基于Adaboost的视频文本定位[J]. 哈尔滨理工大学学报， 2017， 22（1）：103.

[4] KOO H， KIM D.Scene Text Detection Via Connected Component Clustering and Nontext Filtering[J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society， 2013，22（6）： 2296.

[5] YIN X C，YIN X W，HUANGK Z，et al.Robust Text Detection in Natural Scene Images[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2014， 36（5）： 970.

[6] SHAHAB A， SHAFAIT F， DENGEL A.ICDAR 2011 Robust Reading Competition Challenge 2：reading Text in Scene Image[C]// Proceeding of International Conference on Document Analysis and Recognition， IEEE， Beijing， China， 2011（1）：1491.

[7] KARATZAS D， SHAFAIT F， UCHIDA S， et al.ICDAR 2013 Robust Reading Competiton[C]// Proceeding of International Conference on Document Analysis and Recognition， IEEE ，Washington， USA， 2013（1）：1484.

[8] KARATZAS D， LU S， SHAFAIT F， et al. ICDAR 2015 Competition on Robust Reading[C]// International Conference on Document Analysis and Recognition， IEEE Computer Society， Tunis， Tunisia， 2015（1）：1156.

[9] 朱安娜.基于卷積神经网络的场景文本定位及多方向字符识别研究[D].武汉：华中科技大学，2016：26.

[10]FISCHLER M A， BOLLES R C. Random Sample Consensus：A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Communications of the acm， 1981， 24（6）： 381.

[11]高士林，吉力新，李绍梅，等.基于MSER拟合椭圆的快速场景文本定位算法[J].计算机工程与设计，2015（3）：693.

[12]MATAS J， CHUM O， URBAN M， et al. Robust Widebaseline Stereo from Maximally Stable Extremal Regions[J]. Image & Vision Computing， 2004， 22（10）： 761.

[13]NEUMANN L， MATAS J. Realtime Scene Text Localization and Recognition[C]// IEEE Conference on Computer Vision and Pattern Recognition， IEEE Computer Society， Providence， RI， USA， 2012（1）：3538.

[14]姚聪. 自然图像中文字检测与识别研究[D]. 武汉：华中科技大学， 2014： 24.

[15]ASIBA T， SHWETA A D. Text Detection Using MSER and Stroke Width Transform[C]// Communication Systems and Network Technologies， 2015 Fifth International Conference on， Gwalior， India， 2015（1）： 568.

[16]LUCAS S M， PANARETOS A， SOSA L， et al. ICDAR 2003 Robust Reading Competitions[C]// International Conference on Document Analysis and Recognition， IEEE， Edinburgh， UK， 2003（1）：682.

[17]HU H， ZHANG C， LUO Y，et al. WordSup： Exploiting Word Annotations for Character Based Text Detection[C]// International Conference on Computer Vision， IEEE， Venice， Italy， 2017（1）： 4950.

[18]TIAN Z， HUANG W， HE T， et al. Detecting Text in Natural Image with Connectionist Text Proposal Network[C]// European Conference on Computer Vision. Springer， Cham， 2016（1）： 56.

[19]ZHONG Z， JIN L， ZHANG S， et al. DeepText： A Unified Framework for Text Proposal Generation and Text Detection in Natural Images[J]. Architecture Science， 2016（12）： 1.

[20]ZHANG C， YAO C， SHI B， et al. Automatic Discrimination Oftext and Nontext Natural Images[C]// International Conference on Document Analysis and Recognition， IEEE， Tunis， Tunisia， 2015（1）： 886.

（編辑：王 萍）