军标图符按标示功能和几何特点不同,可分为规则军标和非规则军标2类.前者指不依比例尺标绘的点状军标,其外观形状、线画构成和各比例关系保持不变;后者包括半依比例尺的线状军标和依比例尺的面状军标,用于标示行军路线、障碍分布、覆盖范围等信息,图形线条的走向根据具体地形和作战意图等因素确定,线条长度、方向等几何特征的变化性大,没有规则、固定的形状.
此外,点状军标和非规则军标的识别目标不同.在态势标绘系统的实现过程中,点状军标能预先制成标准化模板文件,如二维矢量模型或图像;而非规则军标需要根据若干控制点,常通过曲线拟合的方式动态生成.因此,手绘点状军标的识别目标仅仅是模式分类,而对非规则军标不仅要获得形状类别,还需获得形状参数,如各线条图元的类别和控制点.
由于形状特点的差异和识别目标的不同,手绘点状和非规则军标难以采用统一的识别方法.当前对手绘军标识别的研究都只针对单一类型的军标图符,没有考虑两类图符的类型区分和混合识别问题.在之前的工作中,曾提出一种基于图元匹配的手绘非规则军标识别方法[4]和一种基于方向特征的手绘点状图符识别方法[8](文献[8]是点状图符的通用识别方法,不只针对军标).然而在实际应用中,点状和非规则军标通常是混合输入,对一个类型未知的手绘军标进行识别是一个必须解决的问题.否则,基于草图的态势标绘系统将难以投入实际应用.
由于军标图符是一个相对小众的研究对象,对混合点状和非规则军标的手绘识别问题的研究还不多.与此类似的研究包括手绘图文笔画分类[9]、印刷体和手写体分类[10]、混合多语种字符识别[11, 12]等.针对混合输入点状和非规则军标时的手绘图符识别问题,本文提出一种基于最小生成树(MST)覆盖模型和置信度转化的识别方法.
1 混合识别方案设计1.1 算法概述首先形式化定义以下术语:类型(type),指军标图符是点状军标或非规则军标;类别(class),指具体类属性,如指挥所、进攻箭头等.获取图符类别是军标识别的最终任务.手绘军标图符混合识别的难点在于非规则军标的线条可变性大,难以提取稳定的几何、图像特征,同点状军标的几何性质差异较大.图 1(a)所示的进攻箭头和双箭头图符都属于非规则军标,箭头可随着进攻方向移动,箭身部分将被自动拉伸或弯曲,而图 1(b)所示的点状军标的各图元关系(如长度比值)固定不变.
 |
| 图 1 2种不同类型的军标图符 Fig. 1 Two different types of military symbols |
| 图选项 |
本文算法的框架如图 2所示.对类型未知的待识别军标图符,整合几何、结构和识别信息,对图符类型进行判定,然后对不同类型的图符输入各自识别模块,最后得到识别结果.本文将文献[8]和文献[4]的方法分别作为点状和非规则军标识别模块.军标类型的粗判定利用几何和结构信息实现,它适用于特征明显的非规则军标图符的快速类型确认.点状军标覆盖模型和非规则军标覆盖模型分别从全体点状军标和全体非规则军标的角度评估待识别模式的类型,二者都属于识别信息.通过置信度估计的方法融合这两类识别信息,精确判别待识别图符类型.需要说明的是,文献[4]在识别非规则军标时作出假设:每条笔画仅属于一个图元,它可能是图元的一部分,也可能是一个完整图元,即不能用一个笔画绘制多个图元.本文仍沿用该假设,用户绘制非规则军标时每条笔画仅属于一个图元,但对点状军标的绘制方式没有限制.
 |
| 图 2 提出算法的流程图 Fig. 2 Flowchart of proposed algorithm |
| 图选项 |
1.2 军标类型粗区分同一幅态势图中,点状军标的几何大小具有相近性,而非规则军标由于用来表示地域或部队行为,几何大小不固定,有的显著大于点状军标,有的和点状军标大小相近.且非规则军标的图元组成不同于点状军标,是有用的结构信息.因此,本文通过几何和结构信息分析,快速判断明显是非规则军标的图符.
1) 几何信息分析.
图符几何特征可用多种形式表示,如包围盒面积、包围盒对角线、笔画总长度、凸壳面积等.由于在手写汉字的分割和识别[13]以及草图识别研究中,包围盒几何特征简单有效[14],本文以此作为图符几何特征.若满足
则待识别模式为非规则军标.式中：D和R分别为待识别图符有向包围盒对角线长度和有向包围盒长宽比；max(DP)为点状军标训练样本的有向包围盒对角线长度的最大值；max(RP)为点状军标训练样本的有向包围盒长宽比的最大值；λ1和λ2为较宽松的阈值,取λ1=2.0,λ2=3.0.
2) 结构信息分析.
非规则军标具有较稳定的结构信息,可用于区别点状军标,如非规则军标的图元包括实心小圆或小齿、长螺旋线、长折线、闭合猪腰形等,而点状军标没有这类图元.它们作为非规则军标的专有图元,具有很强的指示性.如果检测到待识别图符具有上述图元,则也可直接判定为非规则军标.识别这类图元可以用启发式规则[15, 16],笔画特征包括长度、折线拟合误差、累计转向角度、笔迹密度、反向计数(相邻3个采样点夹角为锐角的个数,能检测填充区域)、闭合度、外接矩形长宽比等.需要说明的,本节的图元识别只用来实现图符类型粗区分,并不用来识别非规则军标的类别,和文献[4]的图元定义不同.
综上所述,若待识别图符满足式(1)或检测出非规则军标专有图元,则直接判定为非规则军标,输入非规则军标识别模块,得到最终识别结果.
2 点状军标覆盖模型及置信度估计点状军标覆盖模型及置信度估计的目的是将所有类别的点状军标看作一个整体,从全局的角度,度量待识别军标属于点状军标类型的可能性.
本文采用可拒绝分类问题的思想.它是模式识别中的一类特殊问题,主要研究训练同类样本在高维空间中分布形成的复杂几何形体并对其构建合理的覆盖描述模型.其理论基础是同类样本的流形分布具有连续性:同类样本分布在同一个光滑流形上,不存在孤立的样本点[17].胡正平和冯凯[17]提出一种基于最小生成树(MST)的可拒绝分类算法,本文以此为借鉴并作改进,建立点状军标覆盖模型.不同于文献[17]的0-1判定,本节通过点状军标覆盖模型提取待识别模式相对于全体点状军标的特征,并训练一个分类器,最后将分类器输出转换为后验概率.考虑到支持向量机(SVM)在解决小样本、非线性以及高维模式识别中具有许多特有的优势[18],本文采用SVM分类器.本节主要有3个步骤:①点状军标图符特征提取;②建立MST覆盖模型;③待识别图符类型置信度估计.
2.1 点状军标图符特征提取手绘点状军标和手写汉字有类似之处,可以借鉴汉字识别的相关成果,方向特征对汉字识别非常有效,因此点状军标图符的特征提取方法步骤如下：
首先,将图符线性缩放到100×100范围内并重采样(保持宽高比),提取采样点局部方向特征:对每一个笔画,任取一采样点Pi,除笔画的最后一点外,都有一个后继点Pi+1,将局部向量(Pi,Pi+1)按平行四边形法则分解到0°,45°,90°,135°共4个方向轴,如图 3(a)所示,得到4个响应强度值,作为点Pi的4方向特征.
 |
| 图 3 点状军标图符特征提取示意图 Fig. 3 Feature extraction schematic of point military symbols |
| 图选项 |
然后,对图符区域进行8×8网格划分:先计算所有采样点几何重心,经过重心点画出一对水平和竖直网格线,它们将采样点分成4个子区域,然后在每一个子区域内采用同样的方法迭代计算2次,即得到8×8网格,如图 3(b)所示,网格可吸收草图的局部形变.
最后,对每个网格单元,累加其内部所有采样点的4方向特征,共得到8×8×4=256维的特征矢量,作为点状图符的特征描述.
2.2 建立MST覆盖模型提取点状军标训练样本的特征矢量后,借鉴文献[17]的方法建立点状军标的自适应覆盖模型,简述如下:
首先,对由点状军标训练样本组成的高维特征空间的点集,计算一个MST.然后,根据同类样本的连续性规律,采用MST刻画高维空间样本点的分布:将MST的边(不含端点)作为新增虚拟样本,该MST作为覆盖模型的骨架,并对每个样本点(包括真实训练样本和虚拟样本)计算一个局部覆盖半径,从而“认识”该类别.图 4为一组二维空间样本点组成的MST覆盖模型示意图,图 4(a)为MST组成的覆盖模型骨架,其中直线端点表示真实样本,图 4(b)为计算覆盖半径后的覆盖模型.设点状军标样本的类别一共有C类,对每一类别建立一个MST覆盖模型,它们的并集作为点状军标的覆盖模型.
 |
| 图 4 MST覆盖模型图[17] Fig. 4 Minimum spanning tree (MST) coverage model diagram[17] |
| 图选项 |
MST覆盖模型的关键是计算样本点(记为xP)的覆盖半径,它与以下2个因素有关:xP周围的真实样本点分布密度,密度越大,则xP的覆盖半径越大;xP所在边的长度越长,则xP覆盖半径越小.计算细节请参考文献[17].
2.3 基于点状军标MST覆盖模型的置信度估计置信度是衡量模式分类结果可靠性的指标,常用于多方案融合[19],广泛应用于手写文本的分割和识别[13].本节的目的是根据点状军标的MST覆盖模型,估计待识别图符的类型置信度.
文献[17]建立的基于MST的可拒绝分类算法没有考虑拒识决策的置信度,即测试样本拒识与否是一个0-1判断,具体表现是:建立C个类别MST覆盖模型后,计算测试样本到每一类MST的距离,如果没有MST覆盖区域包含该测试样本,则说明其不属于C类中任何一类,拒识;否则,样本属于C类中的某一类,再进一步对测试样本进行分类.由于草图信息的模糊性,这种二值描述难以达到鲁棒性和精确性的统一.本文结合点状军标和非规则军标的混合识别问题,将军标图符类型判别问题以置信度的形式输出,以便融合多种信息.为此,提出的改进方法如下：
将点状军标训练样本分为2部分,记为集合A1、A2,记非规则军标训练样本集合为B.用A1建立点状军标的MST覆盖模型,记为集合{MST1,MST2,…,MSTC}(MSTi为第i类点状军标的MST覆盖模型).
对A2∪B中的每个样本x,记
式中：Pij为第i类MST上的第j个样本点(包括真实样本和虚拟样本)；d(·，·)表示两点间的距离；Rad()表示局部覆盖半径.
记(i*,j*)=argmini,j(Fi),取
作为x的特征描述,这是一个二维矢量,然后建立二分类问题:
据此,文献[17]的决策方法实际是
本文不采用该决策方法,所提出的方法是:用A2∪B训练一个SVM分类器,其中样本特征描述如式(3)所示,训练样本的标记为
标准SVM分类器的决策函数f(x)为样本到决策边界的距离,可利用Logistic回归模型进一步将f(x)转换为后验概率：
式中：a,b∈R为模型参数,可用极大似然估计方法计算,记
则似然函数为
式中：N为集合A2∪B中样本的总数.对数似然函数为
采用梯度下降法对ln L求极大值,即可估计出参数a,b.
3 非规则军标覆盖模型及置信度估计同第2节类似,非规则军标覆盖模型的目的是将所有类别的非规则军标看作一个整体,从全局的角度,度量待识别图符属于非规则军标的可能性.
要建立非规则军标的MST覆盖模型,首先要度量任意2个非规则军标的距离,采用基于图元匹配的度量方法[4],简述如下:
记U和T为2个手绘图符,图符表示为
式中：u和t分别为U和T的图元；u为U中图元个数；t为T中图元个数.建立U和T的图元匹配代价矩阵为
式中：c(ui,tj)表示图元(ui,tj)的匹配距离或代价.图元匹配的任务可以转化为一个指派问题:对U的每一个图元,在T中指派一个图元与之一一对应,使总匹配代价最小,可用匈牙利算法(Hungary algorithm)求解,最坏情况下复杂度是O(N3),U和T的距离即为图元匹配的总代价.c(ui,tj)与图元类型、图元间空间拓扑关系和图元长度有关,细节请参考文献[4].
非规则军标的MST覆盖模型及其置信度的计算方法与2.2节和2.3节类似,不同之处仅仅是2个图符距离度量方法,不再赘述.
4 军标类型区分文献[20]指出,将多个分类器的输出转换为置信度后,融合多个分类器,能取得比单个分类器更好的效果.融合规则有固定规则(fixed rules)和训练规则(trained rules)2类.固定规则简单易用,训练规则较为复杂,常用的固定规则就能取得较好效果,如Max-rule,Median-rule,Sum-rule等,因为Max-rule的效果几乎是固定规则中最好的,因此,本文采用Max-rule.Max-rule可具体表述为:对M类的分类问题,使用K个分类器,分类器输出为dkj(xk),其含义是采用第k个分类器时,待识别模式x到第j类的距离.转换后相应的置信度记为zkj,k=1,2，…,K;j=1,2，…,M.融合后的置信度为
设由点状军标覆盖模型计算出的待识别图符x的类型置信度为
由非规则军标覆盖模型计算出的类型置信度为
其中:y的含义同式(4);MSTP和MSTI分别表示点状和非规则军标的MST覆盖模型.按Max-rule的思想,融合方法为
经置信度融合后,将待识别模式判别到置信度大的类型中去,然后再输入相应的识别模块进行分类,得到最终识别结果.
5 实验与分析实验用的点状图形样本来自文献[21],该数据集包含了113类美军军标图符,由8个志愿者绘制而成,每人绘制5组,共有113×5×8=4 520个样本.由于当前学术界对手绘非规则军标的研究很少,没有可供使用的公开数据,本文采集了以下数据集:共包含36种非规则军标,其中线状23种,面状13种,采集设备为Wacom绘图板CTL-660,基本性能参数为采样分辨率100线/mm,精确度0.25 mm,笔读取速度133点/s,由5个志愿者绘制,每人绘制5组,共得36×5×5=900个样本.各志愿者均具有军事学背景,能熟练使用计算机,年龄为20~35周岁.每个志愿者按照个人习惯绘制图符,每个样本绘制工整,不能过于随意.部分样本如图 5所示.
 |
| 图 5 部分实验样本示例 Fig. 5 Subset of part symbols tested in experiments |
| 图选项 |
实验代码采用MATLAB编写,SVM分类器采用LibSVM工具包,核函数采用RBF函数,计算机配置:CPU:Interl Core i5-2400 3.10 GHz,RAM:4 GB.
5.1 单一类型的军标草图识别单一类型军标草图识别算法的有效性是混合识别的基础.首先验证单一类型的军标草图识别率.采用5重交叉法,针对点状军标样本,基于方向特征和SVM分类器[8]的识别率为98.3%;针对非规则军标,基于图元匹配的结构化识别方法[4]的识别率为96.2%.证明了两个单一类型的军标识别模块的有效性.
5.2 基于MST覆盖模型的军标类型区分为验证本文提出的基于MST覆盖模型的军标类型区分方法的效果,设计如下3组实验.
第1组:由于缺少对手绘军标混合识别问题的直接对比方法,本文用文献[17]的方法分别建立点状和非规则军标的覆盖模型,进行军标类型区分.
第2组:分别单独采用第2节和第3节的方法建立点状军标和非规则军标的覆盖模型后,使用SVM区分军标类型,它们属于在文献[17]的基础上改进了决策规则.
第3组：在第2组的基础上采用融合规则.
实验结果如表 1所示.
表 1 军标类型区分准确率 Table 1 Accuracy of symbol type identification
| 方法 | 准确率/% | |
| 点状军标覆盖模型 | 非规则军标覆盖模型 | |
| 文献[17] | 85.0 | 91.1 |
| 本文方法(不融合) | 87.3 | 93.2 |
| 本文方法(融合) | 94.7 | 94.7 |
表选项
表 1的结果表明:
1) 基于MST覆盖模型的军标类型区分方法有效,直接利用文献[17]的方法,就能取得较高的准确率,且非规则军标覆盖模型的效果较好.原因在于,非规则军标采用结构匹配方法计算2个图符间的距离,能较好地聚类同类样本,且样本绘制较为工整,不同类的样本混淆较少.
2) 当只使用一个覆盖模型时(不融合置信度),本文方法效果好于直接使用文献[17]中的方法.因为后者在军标类型区分时实际使用了线性判别函数,如式(5)所示,而本文通过SVM分类,效果较好,实验验证了这一点.
3) 融合置信度后的准确率有一定上升,验证了同时利用点状和非规则军标覆盖模型的效果比单一覆盖模型的效果好.
类型区分时易出错的图形如图 6所示,但错误图形较为集中,在后续工作中,可以有针对性地提取外围特征加以验证,降低错误率.
 |
| 图 6 类型区分错误的图形 Fig. 6 Symbols that failed to get right types |
| 图选项 |
5.3 混合点状和非规则军标的图符识别采用融合规则确定待识别图符的军标类型后,再用相应的识别算法确定具体类别,最终识别率为91.6%.由于单一类型的军标草图识别已经能达到较高的精度,识别错误的原因主要在于军标类型的区分错误.若类型错误,则类别无法识别正确.
识别速度方面,由于MST覆盖模型可在训练阶段预先生成,判别类型时只需计算待识别模式到MST的距离.识别一个图符的平均时间为167 ms.由于特征提取可在用户交互绘制过程中在后台并发处理,具有较大优化空间,能满足交互的实时性.
此外,融合2个覆盖模型(如5.2节的第3组实验)相比于使用单一覆盖模型(如5.2节的第2组实验),在军标类型区分阶段虽然时间消耗较多,但由于最终的图符识别仍能达到实时要求,且军标类型区分准确率有所提高,所以这种额外消耗是值得的.
6 结 论在基于草图的态势标绘系统中,对类型未知的手绘军标进行识别是一个必须解决的问题,但缺少文献对此进行研究.本文提出一种混合点状和非规则军标图符的手绘识别方法,分别建立点状和非规则军标的MST覆盖模型,并估计待识别模式的类型置信度,经置信度融合后确定军标类型,最后通过相应的军标识别模块进行识别.实验验证了本文方法的有效性.
本文的缺点是,军标类型区分和具体类别识别是2个独立过程,若类型区分错误,则该图符必然分类错误.下一步的工作主要是将以上2个过程统一在整体框架中,采用整体置信度的形式输出分类结果.
虽然本文的研究对象是军标图形,但标图作业在消防、电力、交通、公共安全、灾难救援等领域也有广泛的应用.不同领域具体的图形符号集不同,但在构成特点、标图方式上有很大相似之处,如广泛采用了点状、线状和面状图符.本文算法经适当修改,即可在其他领域中得到应用.
参考文献
| [1] | Sun Z B,Wang C H,Zhang L Q,et al.Query-adaptive shape topic mining for hand-drawn sketch recognition[C]∥Proceedings of 20th ACM International Conference on Multimedia.New York:ACM,2012:519-528. |
| Click to display the text | |
| [2] | 巩应奎,范玉青,吴志方.笔式草图的增量识别[J].北京航空航天大学学报,2006,32(5):621-624.Gong Y K,Fan Y Q,Wu Z F.Incremental recognition method for pen-based sketch[J].Journal of Beijing University of Aeronautics and Astronautics,2006,32(5):621-624(in Chinese). |
| Cited By in Cnki (1) | |
| [3] | 陈鸿,汤晓安,杨耀明,等.基于位移映射的非规则军队标号绘制算法[J].计算机辅助设计与图形学学报,2011,23(5):797-804.Chen H,Tang X A,Yang Y M,et al.Using displacement mapping for irregular military symbols rendering[J].Journal of Computer-Aided Design & Computer Graphics,2011,23(5):797-804(in Chinese). |
| Cited By in Cnki (6) | |
| [4] | 邓维,吴玲达,张友根,等.采用快速图元匹配的手绘非规则军标识别[J].计算机辅助设计与图形学学报,2014,26(10):1835-1843.Deng W,Wu L D,Zhang Y G,et al.Using fast primitive matching to recognize sketched irregular military marking symbols[J].Journal of Computer-Aided Design & Computer Graphics,2014,26(10):1835-1843(in Chinese). |
| Cited By in Cnki (0) | |
| [5] | 吴玲达,张友根,邓维,等.面向手绘军标图形的旋转自由识别方法[J].中国图象图形学报,2014,19(3):456-462.Wu L D,Zhang Y G,Deng W,et al.Rotation free recognition of hand-drawn military marking symbols[J].Journal of Image and Graphics,2014,19(3):456-462(in Chinese). |
| Cited By in Cnki (2) | |
| [6] | Hammond T,Logsdon D,Peschel J,et al.A sketch recognition interface that recognizes hundreds of shapes in course-of-action diagrams[C]∥Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI).New York:ACM,2010:4213-4218. |
| Click to display the text | |
| [7] | Cummings D,Fymat S,Hammond T.Sketch-based interface for interaction with unmanned air vehicles[C]∥Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems,2012. |
| Click to display the text | |
| [8] | Deng W,Wu L D,Yu R H,et al.On-line sketch recognition using direction feature[C]∥Proceedings of Human-Computer Interaction (INTERACT 2013).Heidelberg:Springer Verlag,2013:259-266. |
| Click to display the text | |
| [9] | Delaye A,Liu C L.Contextual text/non-text stroke classification in online handwritten notes with conditional random fields[J].Pattern Recognition,2014,47(3):959-968. |
| Click to display the text | |
| [10] | Malakar S,Das R K,Sarkar R,et al.Handwritten and printed word identification using gray-scale feature vector and decision tree classifier[J].Procedia Technology,2013,10:831-839. |
| Click to display the text | |
| [11] | Song Y H,Xiao G L,Zhang Y L,et al.A handwritten character extraction algorithm for multi-language document image[C]∥Proceedings of 11th International Conference on Document Analysis and Recognition (ICDAR).Piscataway,NJ:IEEE Press,2011:93-98. |
| Click to display the text | |
| [12] | Rani R,Dhir R,Lehal G S.Script identification of pre-segmented multi-font characters and digits[C]∥Proceedings of 12th International Conference on Document Analysis and Recognition (ICDAR).Piscataway,NJ:IEEE Press,2013:1150-1154. |
| Click to display the text | |
| [13] | 付强,丁晓青,蒋焰.基于多信息融合的中文手写地址字符串切分与识别[J].电子与信息学报,2008,30(12):2916-2920.Fu Q,Ding X Q,Jiang Y.Segmentation and recognition algorithm for Chinese handwritten address character string[J].Journal of Electronics & Information Technology,2008,30(12):2916-2920(in Chinese). |
| Cited By in Cnki (11) | |
| [14] | Blagojevic R,Chang S H H,Plimmer B.The power of automatic feature selection:Rubine on steroids[C]∥Proceedings of the Seventh Sketch-Based Interfaces and Modeling Symposium (SBIM).Goslar:Eurographics Association,2010:79-86. |
| Click to display the text | |
| [15] | Paulson B,Hammond T.PaleoSketch:Accurate primitive sketch recognition and beautification[C]∥Proceedings of 13th International Conference on Intelligent User Interfaces (IUI2008).New York:ACM,2008:1-10. |
| Click to display the text | |
| [16] | Paulson B.Rethinking pen input interaction:Enabling freehand sketching through improved primitive recognition[D].State of Texas:Texas A&M University,2010. |
| Click to display the text | |
| [17] | 胡正平,冯凯.高维空间多分辨率最小生成树模型的自适应一类分类算法[J].自动化学报,2012,38(5):769-775.Hu Z P,Feng K.An adaptive one-class classification algorithm based on multi-resolution minimum spanning tree model in high-dimensional space[J].Acta Automatic Sinica,2012,38(5):769-775(in Chinese). |
| Cited By in Cnki (2) | |
| [18] | 谢毓湘,栾悉道,陈丹雯,等.一种基于局部不变特征的图像特定场景检测方法[J].国防科技大学学报,2013,35(6):78-83.Xie Y X,Luan X D,Chen D W,et al.A method of specific image scene detection based on local invariant features[J].Journal of National University of Defense Technology,2013,35(3):78-83(in Chinese). |
| Cited By in Cnki (4) | |
| [19] | Liu C L,Hao H W,Sako H.Confidence transformation for combining classifiers[J].Pattern Analysis and Applications,2004,7(1):2-17. |
| Click to display the text | |
| [20] | Liu C L.Classifier combination based on confidence transformation[J].Pattern Recognition,2005,38(1):11-28. |
| Click to display the text | |
| [21] | Costagliola G,de Rosa M,Fuccella V.Recognition and autocompletion of partially drawn symbols by using polar histograms as spatial relation descriptors[J].Computers & Graphics,2014,39(2):101-116. |
| Click to display the text |
