一种基于TDH的手绘图形方向识别方法＊

张友根，吴玲达 ，2.，宋汉辰

（1.国防科学技术大学信息系统工程重点实验室，湖南 长沙 410073；2.装备学院重点实验室，北京 101416）

1 引言

近年来，随着平板电脑、触摸屏、数位板等设备的快速发展和普及，面向各种领域的基于手绘图形识别的草图交互界面受到了学术界、产业界的高度重视和广泛研究[1]。许多领域中的图形常可以有多个（甚至任意多个）朝向，使得手绘图形识别的复杂度增大：一方面，识别方法要克服图形旋转的影响，实现旋转自由的匹配，这限制了许多不具有旋转不变性的特征和识别方法的应用，增加了匹配识别的计算复杂度；另一方面，在一些应用中还需要在识别的输出结果中包含输入图形的方向，例如根据识别的方向将库中定义的规整图形旋转至相应的角度，以替换用户输入的图形。

目前对于手绘图形的旋转自由匹配识别方法主要包括三类：

（1）对图形提取旋转不变的特征，如Zernike矩模[2]、像素级约束直方图[3]等，这些特征具有良好的旋转不变性，但当图形集较大时（尤其是存在相似图形时）常难以进行细化特征提取和区分。

（2）通过逐角度搜索的方式旋转待识别图形与模板图形进行匹配[4]，或存储模板图形在多个角度下的版本分别用于匹配[5，6]。这类方法可以赋予原本对方向敏感的特征表示和匹配方法一定的旋转自由识别能力，但也使得识别计算开销急剧增大，通常只适用于较小规模的图形集。

（3）在预处理阶段首先识别图形的方向，然后根据识别结果对图形进行方向校正。这类方法的一个主要优点是可以对校正后的图形应用许多有效的、但对方向敏感的特征或识别方法，如相似关键区域分析[7]等。

显然，方向识别是这类方法的关键，本文即以手绘图形的方向识别问题作为研究对象。

在手绘图形（包括手写文字）识别领域，已有学者对图形方向识别问题开展了一些研究，Huang等[8]提出了一种针对倾斜手写汉字的识别方法，该方法基于“手写汉字的书写起始点位置（相对规则方向而言）稳定”的假设，对旋转的汉字进行方向校正和重调整处理。Reaver等[9]也采用了笔画起始点位置对单笔画图形进行方向调整。He等[10]利用汉字笔画书写方向的规律对倾斜角度在±π／3内的手写汉字进行方向识别和校正。总体而言，目前大部分的手写文字方向识别与校正方法都利用了文字结构或用户输入模式的固有规律，而对许多手绘图形（尤其是多笔画图形）而言，图形结构没有固定规律，用户也很难形成稳定一致的绘制习惯。此外，在形状图像识别领域，也有一些针对形状方向识别问题的研究[11，12]。

本文提出一种面向手绘图形的方向识别方法，利用统计切向直方图TDH（Tangent Direction Histogram）特征描述手绘图形笔画的方向信息，通过TDH 旋转匹配确定待识别图形与模板图形之间的相对方向夹角。这种方向描述和匹配识别方法原理简单，计算高效，且不依赖于特定的图形结构和用户输入模式，对笔画构成较规则的手绘图形具有较好的方向识别效果。

2 基于切向直方图的方向识别

手绘图形由笔画组成，通过笔画采样点数据很容易计算出局部方向信息，而且当图形方向变化时，组成图形的各条笔画也相应地旋转相同的角度。因此，本文通过统计笔画采样点集的局部切线方向作为手绘图形的方向描述特征，进而匹配识别出图形之间最可能的方向夹角。

2.1 切向直方图定义

首先对输入的原始图形笔画数据进行预处理，将按时间采样的原始笔画轨迹以空间等间距方式进行重采样，从而消除原始数据中因笔速变化带来的影响。重采样间距设置为L／NR，其中L 为图形笔画总长度，NR用于控制重采样后的点数，可权衡精度和效率的要求进行设置。采用这种与笔画总长度成比例的间距进行重采样后，可以消除图形尺度对后续方向特征提取和识别带来的影响。

设重采样后图形中某笔画包含的采样点序列为〈p0，p1，…，pN〉，计算各采样点pi（i＝1，…，N-1）处的局部切线方向：

需说明的是，虽然在联机手绘笔画轨迹中可以提取出笔画方向矢量角（取值范围为[0，2π）），但考虑到用户在手绘图形时对于图形中的同一段笔画既可能正向也可能反向输入（相对而言，手写文字的运笔方向通常较稳定），因此本文取采样点pi处切线的倾角（取值范围为[0，π））构造方向特征。

统计图形所含全部采样点的切方向角，构造一个切向直方图TDH，作为描述图形采样点集的局部方向统计特征。TDH 将角度范围[0，π）均分为M 块（bin），即TDH 的第j 块取值为方向角范围[（j-1）·π／M，j·π／M）内的采样点加权频数：

其中，wi为各采样点的统计权重。在手绘图形中，不同笔画部位的方向稳定性不尽相同，显然笔画平直部位的方向较弯曲部位更为稳定，对图形方向的指示能力也更强，因此，本文以各采样点处曲率的函数作为统计的权重。由于在预处理中已对笔画输入进行了空间等间距重采样，因此直接以切线倾角的变化值Δθi作为曲率度量，统计权重定义为：

手绘图形的笔画具有不精确性，例如原本平行的两条笔画在绘制时可能会出现细微夹角，因此，对TDH 进行加窗平滑处理：

其中，s控制窗口的宽度，W（·）表示平滑时窗口中各块的权重。最后，对TDH 进行归一化处理。图1是一个手绘图形朝向不同方向时的TDH 特征对比示例，横轴坐标为直方图bin的索引。从图1中可看出：图1a中的TDH 峰值bin为第47bin，图1b中的TDH 峰值bin为第16bin，二者对应的角度（141°和48°）分别指示了图形笔画的显著方向倾角。图1中手绘图形的方向夹角在TDH 中相应地表现为直方图bin的循环移位。

Figure 1 Example of sketched symbol TDH图1 手绘图形切向直方图示例

2.2 切向直方图匹配

手绘图形方向识别的目标是确定输入的待识别图形与库中的模板图形之间的方向夹角，从而将二者的方向调整对齐，便于进行进一步的细化特征提取和图形识别。由于图形方向旋转与TDH 特征中的循环移位相互对应，因此本文通过TDH 循环移位匹配，根据最佳匹配时的bin错位关系估算被匹配图形之间的方向夹角。为便于描述，以HU和HT分别表示待识别图形和模板图形的TDH 切向直方图，以ik和hk分别表示直方图binbk的索引和取值：ik＝Indexof （bk），hk＝H （ik）。

在模板库构建阶段，对每个模板图形HT，定位其取值最大的bin（记为bmax），将其对应的角度（以bin索引imax表示）作为图形主方向。

在识别阶段，对新输入的HU，首先按如下步骤提取其候选主方向：

Step 1 定位直方图中所有取值为局部极大值且大于3／M 的bin（记为 ｛bp｝），按hp降序排序后取前P（可能少于P）个，记为Bpeak＝｛b1，b2，…，bP｝。

Step 2 从b1开始，逐个检验bk∈Bpeak的取值是否满足hk＋1／hk＜0.5。若满足，则候选bin集合Bcandi＝Bpeak- ｛bk＋1，…，bP｝，转Step3。

Step 3 取各bk∈Bcandi所对应的角度（以bin索引ik表示），形成手绘图形的候选主方向集Icandi。

之所以选取满足条件的多个极大值bin方向作为候选主方向，是因为手绘图形受不均匀缩放等影响存在一定的变异性，多个显著方向之间可能出现混淆，提取多个候选方向相比于单一的主方向具有更好的鲁棒性。

给定HU的候选主方向ic和HT主方向imax，通过循环移位（imax-ic）个bin即可将HU与HT的主方向对齐，计算此时的直方图交作为二者的匹配相似程度度量：

当Simc较大时，表明手绘图形HU与HT的笔画方向构成相似程度较高，经循环移位（imax-ic）个bin 后使得二者对齐程度较好；否则，若Simc较小，则表明此时HU与HT之间笔画方向对齐程度较差。

计算所有候选主方向ic∈Icandi下的Simc，生成方向识别候选结果集 ｛（ic，Simc）｝。将各候选结果依Simc降序排列，取Top-n（n≥1）子集作为最终的方向识别结果。（ic，Simc）表示将HU旋转（imax-ic）·π／M 或π＋（imax-ic）·π／M 角度后可与HT对齐。

为避免在图形识别过程中多次对HU进行旋转变换来对齐不同的模板图形，减少在线识别处理的时间开销，可以令HU与HT的主方向都对齐到0角度方向：在离线模板库构建阶段，将各HT旋转-imax·π／M 角度存储，其TDH 特征也相应地循环移位imax个bin，使得图形主方向为0 角度方向（imax＝0）。在线识别时，只需以相同方式对HU根据其每个候选主方向执行一次图形旋转和TDH移位操作，即可使得HU与HT在0角度方向对齐。

3 实验结果与分析

3.1 实验配置

为验证基于TDH 的手绘图形方向识别方法的有效性，本文结合手绘军事标图应用，针对一组方向可变的手绘点状军标图形进行了实验，实验图形集包含7类共52种图形，图2列出了其中的部分图形。

Figure 2 Parts of sketched course-of-action symbols图2 部分实验用手绘点状军标图形

采用一台ThinkPad X200Tablet作为手绘图形输入设备。对每个图形给出一幅模板图形作为参考，请4位用户分别朝左上、左下、右上、右下4个方向绘制新的图形样本，然后标注各图形样本相对于指定方向的旋转角度，最终形成包含832个样本的测试图形集。

将本文方法（以下简记为TDH）与Revaud等[11]提出的基于Zernike矩的方法（以下简记为ZM）进行实验比较。ZM 方法属于基于图像的识别方法，在形状识别领域取得了较好的识别效果。

3.2 实验结果

表1为两种方法所识别结果的角度误差统计，将Δ 的取值范围划分为三个区间，角度误差小于5°表示能较精确地识别图形方向，而角度误差超过10°则可认为方向识别结果的可靠性较低。为降低手绘图形变异性导致的方向混淆误判，对存在多个显著方向的图形，TDH 方法可在识别结果中返回多个方向作为候选。表1中的TDH-1和TDH-2分别表示TDH 方法取前1和前2 个候选结果中最小角度误差时的统计结果。

Table 1 Over distribution of identify angle error表1 识别角度误差总体分布 %

表1中数据表明：TDH 方法对超过80%的图形所得的方向识别角度误差小于5°；对96.4%的图形第1候选识别结果的角度误差在10°以内；若考虑前两个候选结果，则角度误差在10°以内的图形占98.8%。ZM 方法则有15.75%的图形的方向识别角度误差超过了10°。

对各类军标图形的方向识别误差统计结果堆积图如图3 所示，每类中从上到下分别为采用TDH-1、TDH-2、ZM 的识别方法，识别角度误差落入各误差区间的测试样本比例。

Figure 3 Direction recognition results of different kinds of symbols图3 各类图形的方向识别结果

图3中结果表明：ZM 方法对C、E、F 等类别图形的方向识别效果较好，而对A、B、G 等类别图形的识别效果较差，其原因是这些图形的采样点集在空间分布上各向异性较差，加之手绘图形所具有的模糊性，使得其Zernike矩特征方向信息不够显著和稳定。相比而言，TDH 方法对不同类别的图形都具有更好的适应性，尤其对类A、C 等笔画构成简单、含单向长直笔画的图形识别效果较好。识别效果较差的图形主要是因笔画构成较杂乱，导致无法提取有效的显著方向，使得TDH 识别方法失效。

手绘交互对识别速度有很高的要求，本文对TDH 方法和ZM 方法的方向识别速度也进行了实验比较。方向识别处理的时间开销主要包括两部分：（1）表示阶段，即对未知图形进行预处理和TDH 特征提取以表示其方向信息，记为tr；（2）匹配阶段，即将未知图形与模板图形的方向特征进行匹配计算以估计二者的相对方向夹角，记一次匹配耗时为tm。对一个未知图形进行方向识别的在线处理时间可近似表示为tr＋模板数×tm。在本实验条件下（CPU：Intel Core Duo L9400 1.86GHz，RAM：2GB），TDH 方法和ZM 方法在表示阶段平均耗时tr分别为1.34ms和3.87ms，一次匹配平均耗时tm分别为0.016ms和0.035ms。实验结果表明这两种方法的时间开销都非常低，可满足交互实时性的要求，TDH 方法在两个阶段的时间开销均低于ZM 方法，但二者均处于相同数量级。

4 结束语

针对方向可变的手绘图形，本文提出了一种基于TDH 的方向识别方法，该方法简单高效，对笔画构成较规则的手绘图形具有较好的方向识别效果。利用识别的方向角可以旋转校正图形方向，进而使用原本对方向敏感的特征及方法进行细化识别。由于各领域的手绘图形多种多样，单一的方向识别方法很难适用于所有的图形。进一步的研究包括针对不同类型的手绘图形定义可定向性度量，以及多种方向识别方法的融合。

[1]Johnson G，Gross M D，Hong J，et al.Computational support for sketching in design：A review[J].Foundations and Trends in Human Computer Interaction，2009，2.1）：1-93.

[2]Hse H，Newton A R.Sketched symbol recognition using Ze-rnike moments[C]∥Proc of the 17th International Conference on Pattern Recognition，2004：367-370.

[3]Su Yang.Symbol recognition via statistical integration of pixel-level constraint histograms：A new descriptor[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，2.（2）：278-281.

[4]Kara L B，Stahovich T F.An image-based，trainable symbol recognizer for hand-drawn sketches[J].Computers ＆Graphics，2005，2.（4）：501-517.

[5]Fornés A，Lladós J，Sánchez G，et al.Rotation invariant handdrawn symbol recognition based on a dynamic time warping model[J].International Journal on Document Analysis and Recognition，2010，13（3）：229-241.

[6]Ouyang T Y，Davis R.A visual approach to sketched symbol recognition[C]∥Proc of the 21st International Joint Conference on Artifical Intelligence，2009：1463-1468.

[7]Leung K C，Leung C H.Recognition of handwritten Chinese characters by critical region analysis[J].Pattern Recognition，2010，43（3）：949-961.

[8]Huang Sheng-ming，Jin Lian-wen，Lv Jin.A novel approach for rotation free online handwritten Chinese character recognition[C]∥Proc of the 10th International Conference on Document Analysis and Recognition，2009：1136-1140.

[9]Reaver J，Stahovich T F，Herold J.How to make a quick＄：Using hierarchical clustering to improve the efficiency of the dollar recognizer[C]∥Proc of the 8th Eurographics Symposium on Sketch-Based Interfaces and Modeling，2011：103-108.

[10]He Ting-ting，Huo Qiang.A character-structure-guided approach to estimating possible orientations of a rotated isolated online handwritten Chinese character[C]∥Proc of the 10th International Conference on Document Analysis and Recognition，2009：536-540.

[11]Revaud J，LavouéG，Baskurt A.Improving Zernike moments comparison for optimal similarity and rotation angle retrieval[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（4）：627-636.

[12]Rosin P L，Zunic J.Orientation and anisotropy of multi-component shapes from boundary information[J].Pattern Recognition，2011，44（9）：2147-2160.