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

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

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

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

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

图选项

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

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

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

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

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

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

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

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

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

Step2 计算采样点平均速度，用将采样点分为低速点(v_i≤和高速点(v_i；分别对2类点计算其相对于的上偏差v_h和下偏差v_l，如图 2所示，其中横坐标为采样点序号，纵坐标为采样点的速度值；

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

图选项

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

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

b) 若高速曲线段与等值线相交且交点个数大于给定值(本文取3)，转步骤c)；否则判定该高速曲线段受到噪声或绘图速度影响，需将其与前后相邻的低速曲线段合并，构成新的低速曲线段；

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

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

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

点击浏览公式

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

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

点击浏览公式

点击浏览公式

Step2 将$\left\{ {{{v'}_i};i = 0,1,2, \cdots ,\left\lfloor {\left( {n - 1} \right)/{T_d}} \right\rfloor + 2} \right\}$作为某一笔画采样点的速度值序列，易证，该笔画为常速笔画，对其进行特征点提取，得到转化后的速度分割点序列；

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

点击浏览公式

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

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

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

点击浏览公式

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

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

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

图选项

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

图选项

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

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

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

图选项

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

图选项

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

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

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