基于速度特征的在线手绘笔画快速分割方法

王淑侠，张茜，王守霞，王关峰，高满屯

(西北工业大学，陕西西安 710072)

基于速度特征的在线手绘笔画快速分割方法

王淑侠，张茜，王守霞，王关峰，高满屯

(西北工业大学，陕西西安 710072)

针对现有基于速度特征的笔画分割方法对匀速绘制笔画过度分割的问题，提出一种创新性的基于速度特征的笔画分割方法。首先对笔画进行折线化预处理，从而将笔画的采样点进行数据压缩得到能反映笔画的折点序列；为了提高用户的绘制自由度，按照输入笔速的不同将笔画分为常速笔画和准匀速笔画，并按其特征的不同，给出相应的速度特征提取算法。对于前者给出了基于三线阈值的速度特征提取算法，后者则先采用基于“滤波-锐化处理”的方法将准匀速笔画转化为常速笔画，再通过常速笔画的速度特征提取算法得到其速度特征点，并针对笔画特征的模糊性提出以点段形式表示准匀速笔画的速度特征。最后通过自主开发的FSR＿SS系统对上述算法加以验证，并给出其他算法与本文算法结果的比较分析。实验结果表明，基于速度特征的笔画分割方法能实时进行在线手绘笔画分割，为后期手绘图的识别研究奠定了基础。

概念设计；在线草图；过分割；速度特征；草图识别；笔画分割

手绘草图是人类一种自然而直接的思维交流方式。草图识别工具提供给设计师一个展现设计思维，开展创造性设计工作的平台。草图识别过程一般包括：笔画处理、符号识别、笔画规整、形状推理、高层次识别［1］。笔画分割是草图识别的重要的第一步，该步骤将笔画分割为一组连续的几何线元。其中，几何线元是草图识别的最基本构件，就像是钢梁如何形成一个复杂结构建筑，这些几何线元又可以被重新组成更复杂的形状［2］。最常见的几何线元有直线段、圆弧和曲线，还有较复杂的形状如椭圆弧、螺旋线、涡状线等。然而，影响笔画分割的因素，除了绘制速度、曲率和曲线转角等几何方面外，还涉及到用户所使用的设备环境、用户绘制习惯等诸多方面［3］。如何对笔画进行分割，且同时满足精度、效率和适应性标准，是草图识别的关键技术问题之一，而至今没有方法可以达到这些标准［4］。

现有的大多数笔画分割方法采用速度、曲率等信息确定笔画分割点。Yu等人［5］提出首先对输入笔画进行几何线元的近似拟合，如果拟合失败，则依据最大曲率点分割笔画，并对得到的子段重复上述过程，最后在后处理阶段中将分段结果合并。Shortstraw［6］的笔画分割方法首先对笔画进行重采样，然后依次计算相邻2个重采样点之间的距离，即“稻草值”，该“稻草值”可以表示该点的局部曲率。所有重采样点中，“稻草值”低于固定阈值的被认定为候选分割点，这些候选分割点将笔画分割成若干子段；然后检测每个子段的线性拟合结果，如果拟合失败，则在该子段中继续增加分割点以完成笔划分割。在各组中以速度值最小点作为速度特征点。Sezgin等提出基于速度和曲率混合的分割方法［7］，该方法以速度平均值的90%作为阈值，该速度特征提取方法对笔划绘制的要求较为严格。Wolin的分类-合并-重复技术(SMR)［8］以速度最小值点和曲率最大值点为候选分割点，然后基于拟合误差对各子段进行合并。Istraw等［9］在Shortstraw基础上，增加了局部速度最小值点作为候选分割点，该系统可以将笔画表示为直线与圆弧的组合。由于分割算法繁多，而且与应用紧密相关，因此，对于不同的应用，其对分割方法提出的要求可能完全不同，所以对算法的性能进行比较也是十分困难的。

本文首先给出一些相关的基本概念，然后给出了基于速度特征的笔画分割方法。并在作者自主开发的原型系统上对已有的基于速度特征的笔画分割方法进行分析比较。文中的单笔画识别方法采用了基于分类识别方法［10］，现可识别的最基本的几何线元包括直线段、折线段椭圆、圆、椭圆弧、圆弧、双曲线和抛物线。

1　概 述

基于速度特征的笔画分割包括笔画预处理、速度特征提取、笔画分割三部分内容。笔划分割算法的具体流程如图1所示。

图1　基于速度特征的笔画分割流程图

1.1预处理

将鼠标按键-移动-松键的过程中由采样点序列形成的一条轨迹称为笔画。笔画的预处理过程为：首先将笔画的第一个和最后一个采样点连成的直线作为笔画的初始拟合，然后在采样点中计算最大规范误差ε，若该误差值高于某一阈值，则在离上述直线段最远的采样点上设置一个折点。在每一个子笔画中，重复上述分段算法，直到将笔画在最大规范误差范围内完全分裂并将其用折线段进行代替。该算法的实现取决于其阈值函数［11］的确定。

1.2速度特征提取的新方法现状以及改善方法

现有速度特征提取一般采用基于平均值的方法［7］。Sezgin采用速度阈值对笔画进行分组，在各组中以速度值最小点作为速度特征点。该方法虽然解决了速度特征的提取问题，但是由于局部噪音的存在可能导致分组错误，而且绘图速度较均匀时特征提取也会失效。

本文针对以上算法存在的问题，进行了深入研究，并提出以下解决办法：

1)首先对速度曲线进行平滑处理，有效避免局部噪声影响；然后通过速度平均值及其上下偏差3个阈值与笔画的瞬时速度进行比较从而确定分割点，有效避免算法对笔画噪声敏感的问题。

2)提出了常速笔画和准匀速笔画的概念，当采样点个数与笔画累积长度的比值不大于一个给定值ξmax(文中取0.15)且笔画平均速度大于一个给定值vmax(文中取400 pixel/s)时，该笔画被定义为常速笔画，否则为准匀速笔画。

3)针对常速笔画，给出基于“三线阈值”的分割方法。对于准匀速笔画，则通过“滤波-锐化处理”将其转化为常速笔画进行处理。该方法可以有效减少采样点个数并增强速度曲线峰值特征。

2　基于速度特征的笔画分割

根据用户在绘制图形的过程中输入笔速的不同将速度特征的提取分为常速笔画和准匀速笔画的速度特征提取。

2.1常速笔画的速度特征提取

设｛pi；i＝0，1，2，…，n｝、｛vi；i＝0，1，2，…，n｝分别为笔画采样点序列及其对应的速度，其中速度单位为pixel/s，n为采样点个数，首尾点的速度取零。常速笔画的分割算法如下：

Step1 对笔画采样点的速度曲线进行相邻两点间平滑处理；

图2　采样点的速度曲线及相应的高低速曲线段

Step3 等值线vl与速度曲线相交将速度曲线分割为多个曲线段，定义交点在横坐标上的投影为Li(0＜i＜n)，设L0和Ln为速度曲线的首尾两点在横坐标上的投影。将处于等值线vl下方的曲线段称为低速曲线段，否则称其为高速曲线段。其特征分别为：首尾两曲线段均为低速段曲线；低速段曲线与高速段曲线交叉出现；每个曲线段中至少包含一个采样点的速度值，如图2所示。研究者通常认为每个低速曲线段中应有一个速度特征点。但实验中发现，当用户绘制自由度增大时，低速曲线段中可能不存在速度特征点。为此，本文以vh和为基准对低速段曲线进行如下修正，设j＝1。

a)若第j个高速曲线段与等值线vh相交，进入步骤c)；

c)对下一段高速曲线段(j＝j＋1)进行以上操作；

Step4 在修正后的低速曲线段中，分别选取最小速度点作为速度特征点，即速度分割点；将上述算法称为“三线阈值分割法”，采用该方法可以很好的解决常速笔画的速度特征提取问题。

2.2准匀速笔画的速度特征提取

若可将准匀速笔画转化为常速笔画，便可按常速笔画的进行分割处理。加权平均的平滑滤波处理可使单位长度内的采样点个数减少，从而增大其与笔画累积长度的比值，但通过该处理会使平均速度变小，为避免该影响可采用线性锐化处理方法增强速度曲线峰值特征。因此，文中采用滤波－锐化处理方法减少采样点个数并增强速度曲线峰值特征，从而将准匀速笔画转化为常速笔画。对转化后的笔画进行笔画分割，并根据映射关系反求准匀速笔画的速度分割点段。采用速度分割点段进行分割更符合准匀速笔画自身具有的模糊特性要求。对笔画进行平滑滤波处理，其加权平均的采样点个数，记为Td。按式(1)计算，其中ns为控制系数(本文取0.04)。

准匀速笔画的分割算法如下：

Step1 对笔画速度曲线进行坐标变换，得到以速度平均值为横轴的速度曲线；除首尾采样点外，依次将连续的Td个采样点进行平滑滤波处理，直到剩余的采样点的个数小于Td为止；再进行锐化处理， (2)式为滤波－锐化处理公式：

式中，Tv为线性锐化系数，按照以下经验公式确定

Step2 将｛v′i；i＝0，1，2，…，⎿(n－1)/Td」＋2｝作为某一笔画采样点的速度值序列，易证，该笔画为常速笔画，对其进行特征点提取，得到转化后的速度分割点序列；

Step3 反求转化后的速度分割点对应的采样点段。易知，首尾点对应采样点的首尾点；除首尾点外，分割点序列中的第i点与采样点段序号的对应关系为

理论上对于平滑滤波处理时，若剩余点个数小于Td，则应将其平滑滤波跨度减小后求其速度均值。但由于连续的Td个点中速度分割点段至多只有一个，文中已将速度点序列的末尾点定义为速度分割点，故在剩余点个数小于Td时不会再出现其他速度分割点。

3　实验分析

根据上述算法，在Win 7环境下利用Visual C＋＋自主开发的基于速度特征的在线手绘图分割的原型系统(FSR－SS)。该系统可以进行笔画的输入，分割及识别。在Intel CPU 3GHz，4GB内存的环境下，对该系统进行了大量测试分析。

为了对基于速度特征的笔画分割算法的正确率进行分析，首先给出一些定义。设笔画的折点数为N，理想分割点数Nt是用户本身绘制意图想要的分割点数；Ns是仅利用笔画速度特征进行的笔画处理得到的分割点数；有效分割点数Nr是指出现在Ns中的理想分割点数。考虑算法得到的分割点数有时多于有时少于理想的分割点数Nt，本文给出笔画分割正确率δ的计算公式

3.1速度特征提取算法的比较分析

算例1 五角星的速度特征提取

图3～图4是对Sezgin算法和文中算法进行常速和准匀速手绘五角星图形的速度特征点提取的比较，小圆圈代表提取得到的速度特征点。

图3　常速五角星速度特征提取(采样点：61)

图4　准匀速五角星速度特征提取(采样点：342)

表1　2种算法提取的关键值比较

算例2 曲线图形的速度特征提取

图5、图6是对Sezgin算法和文中算法进行常速和准匀速手绘曲线图形的速度特征点提取的比较，小圆圈代表提取得到的速度特征点。

图5　常速曲线图形速度特征提取(采样点：69)

图6　准匀速曲线图形速度特征提取(采样点：451)

表2　2种算法提取的关键值比较

图3、图5是在常速绘制的情况下分别采用Sezgin算法和本文算法得到的速度特征提取情况，可观察到在常速绘制情况下本文算法的提取精度更高；图4、图6是在准匀速绘制的情况下采用Sezgin算法和本文算法提取得到的速度特征点情况，可观察到在准匀速绘制情况下，Sezgin算法完全失效，而本文算法的提取较准确。表1、2给出了常速和准匀速绘制五角星和曲线图形分别通过Sezgin算法和本文算法得到的关键数据比较。从表中可以看出， Sezgin算法没有对采样点进行处理，因此在处理前后的采样点个数并未发生变化，而本文算法对准匀速笔画的采样点进行滤波处理，因此处理后的点数明显减少；在常速绘制中，由于本文对笔画进行了平滑处理，因此2种算法得到的平均速度发生微小变化。在准匀速绘制中，本文采用了坐标变换，因此出现了速度平均值小于零的情况；本文以速度平均值和上下偏差作为三线阈值，而Sezgin算法采用单一阈值，最终得到的速度采样点个数明显不同。

从笔划分割方法的处理时间和正确率分析，在常速绘制下，由表1、2可以看出本文算法的笔画分割时间均略高于Sezgin算法，但其仍然满足用户的绘制要求，不会影响用户的绘图灵感，最为重要的是针对上述算例本文算法的分割正确率为100%，而Segin算法的分割正确率不高于66.7%。同时，在准匀速绘制情况下，Sezgin算法已失效，而本文相应的正确率在80%以上。总而言之，本文算法和Sezgin算法相比较，整体上也是得到了更为合理的提取结果，因此本文算法是可行的。

4　结 论

文中提出基于速度特征的笔画分割方法，首先对笔画进行预处理得到笔画的折点序列。然后，依据速度特征等信息系统自动对笔画进行常速笔画和准匀速笔画的分类，并给出了相应笔画的速度特征提取算法。前者采用“三线阈值”的速度特征提取算法；后者，则通过“滤波-锐化”处理将准匀速笔画转化为常速笔画，并针对笔画特征的模糊性提出以点段形式表示准匀速笔画的速度特征。最后通过算例对文中提出的基于速度特征的笔画分割算法加以验证，并和其它算法进行了比较，由实验结果可知，文中的算法可以快速地解决笔画的分割问题，为后期的笔画识别工作奠定了一定基础。同时发现，由于用户绘制的随意性会导致分割错误，若可以将基于速度特征提取的分割方法与其他分割方法相结合，在既保证分割速度的前提下，又能提高分割正确率，将是后期继续研究的方向。

［1］ Deufemia V，Risi M.A Dynamic Stroke Segmentation Technique for Sketched Symbol Recognition［J］.Pattern Recognition and Image Analysis，2005：335-357

［2］ Wolin A D.Segmenting Hand-Drawn Strokes［D］.Texas A＆M University，2010

［3］ 孙正兴，冯桂焕，周若鸿.基于草图的人机交互技术研究进展［J］.计算机辅助设计与图形学学报，2005，17(9)：1889-1899

Sun Zhengxing，Feng Guihuan，Zhou Ruohong.Techniques for Sketch-Based User Interface：Review and Research［J］.Journal of Computer Aided Design and Computer Graphics，2005，17(9)：1889-1899(in Chinese)

［4］ Tumen R S，Sezgin T M.DPFrag：Trainable Stroke Fragmentation Based on Dynamic Programming［J］.IEEE Trans on Computer Graphics and Applications，2013，33(5)：59-67

［5］ Yu B，Cai S.A Domain-Independent System for Sketch Recognition［C］//Proceedings of the 1st International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia，2003：141-146

［6］ Wolin A，Eoff B，Hammond T.Shortstraw：A Simple and Effective Corner Finder for Polylines［C］//Proceedings of the Fifth Eurographics Conference on Sketch-Based Interfaces and Modeling，2008：33-40

［7］ Sezgin T M，Stahovich T，Davis R.Sketch Based Interfaces：Early Processing for Sketch Understanding［C］//ACM Siggraph 2006 Courses，2006：22

［8］ Wolin A，Paulson B，Hammond T.Sort，Merge，Repeat：An Algorithm for Effectively Finding Corners in Hand-Sketched Strokes［C］//Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling，2009：93-99

［9］ Xiong Y，Laviola Jr J J.A ShortStraw-Based Algorithm for Corner Finding in Sketch-Based Interfaces［J］.Computers＆Graphics，2010，34(5)：513-527

［10］王淑侠，高满屯，齐乐华.基于模糊理论的在线手绘图识别［J］.模式识别与人工智能，2008，21(3)：317-325

Wang Shuxia，Gao Mantun，Qi Lehua.Online Freehand Sketching Recognition Using Fuzzy Theory［J］.Pattern Recognition and Artificial Intelligence，2008，21(3)：317-325(in Chinese)

［11］Wang S，Gao M，Qi L.Freehand Sketching Interfaces：Early Processing for Sketch Recognition［M］.Heidelberg：Springer， 2007：161-170

Segmentation of Online Sketching Using Velocity Features

Wang Shuxia，Zhang Qian，Wang Shouxia，Wang Guanfeng，Gao Mantun
(Northwestern Polytechnical University，Xi′an 710072，China)

We describe a new method for segmenting non-single stroke to 2D geometric primitives using velocity features；these primitives are further interpreted as 2D line drawings.This method can support rapid segmenting and fitting of non-single stroke using velocity features extracted during stroke-inputting stage.A stroke processing method using polygonal approximation is used for online stroke compression.In order to reduce the user＇s drawing limitation，we divide the stroke into common speed stroke and uncommon one according to such information as speed， sampling points and length of stroke.For common speed stroke，an extraction algorithm of velocity feature is presented using three threshold values：velocity and its upper deviation and lower one.For uncommon speed stroke，firstly it is transformed into the common one with the proposed filter-sharpness processing；then velocity features are extracted based on the feature extraction method of common stroke；finally，according to the fuzziness of velocity feature，dot segments represent the speed features of uncommon speed stroke.Finally，a combination method of primitives is introduced to eliminate over-segmentation.The proposed method has been tested with our FSR＿SS online freehand sketch recognition system；FSR＿SS is robust and easier to use by removing some limitations embedded with most existing sketching systems which only accept single stroke drawing.The test results show that the proposed method can support freehand sketching based conceptual design without limitations on drawing sequence and directions while still achieving a satisfactory segmentation rate.

conceptual design；freehand sketching，over-segmentation，pen speed，sketch recognition，stroke segmentation

TP391.41

A

1000-2758(2016)02-0235-06

2015-09-08基金项目：浙江大学CAD＆CG国家重点实验室开放课题(A1615)及国家自然科学基金(51105310)与西北工业大学研究生创意种子基金(22016082)资助

王淑侠(1978—)，女，西北工业大学副教授、博士，主要从事CAD＆CG、人机工程学研究。