法律状态公告日
法律状态信息
法律状态
2018-05-18
授权
授权
2015-12-09
实质审查的生效 IPC(主分类):G06K9/68 申请日:20150629
实质审查的生效
2015-11-11
公开
公开
技术领域
本发明涉及一种在线多笔画重复绘制草图的聚类与拟合方法,用于将在线多笔画重复绘制草图转换为二维线图,用于手写板、智能手机等智能手绘输入设备。
背景技术
手绘草图是人类的一种常用的思想交流的方式,它自然、简便,而且能表达模糊的概念,便于用户进行创造性活动。草图识别工具提供给设计师一个展现设计思维,开展创造性设计工作的平台,但由于用户手绘习惯和方式的不同对有效识别草图和推测用户意图带来很大困难。草图识别的目的,是在用户绘制约束最小的情况下,达到最佳的识别效率和效果。多笔画重复绘制是手绘草图中常见的现象:设计师通常先以单笔画绘制一张粗略的草图形成大致轮廓,然后在已有轮廓的基础上加深或修正笔画以强调设计意图或使草图更加清晰。如何对多笔画绘制的草图进行正确的聚类及拟合以表示预期的几何图形是在线草图识别的一个重要内容,笔画聚类的效果直接影响到后续的识别结果。
目前在线手绘图解释系统大部分不支持或有条件的支持笔画的重复绘制,发明人发现现有技术至少存在以下技术问题:对用户绘制习惯进行约束,如要求用户在特定时间内输入笔画或绘制完成一个图形后点击按钮确定;不能将所有输入笔画全部解释成草图的一部分;基于对笔画的分类进行多笔画聚类,聚类过程只能在同类型笔画之间进行。
发明内容
要解决的技术问题
本发明用于将在线多笔画重复绘制草图转换为二维线图,解决已有的在线手绘图解释系统对用户绘制习惯进行约束,不能将所有输入笔画全部解释成草图的一部分或只对同类型笔画聚类的技术问题。
技术方案
一种在线多笔画重复绘制草图的聚类与拟合方法,其特征在于步骤如下:
步骤1:对每个输入笔画的计算机数据提取包括笔画起点和笔画终点的N个采样点,得到采样点序列{pi;0≤i≤n},对采样点序列进行折线化逼近处理,得到折点序列{zi;0≤i≤M};采用经典Graham扫描算法对输入笔画进行扫描得到笔画的凸包,然后采用极值法得到笔画的最小包络矩形;
步骤2:遍历笔画的折点序列{zi;0≤i≤M},依次在相邻两折点间构造一个长为该两折点间的欧式距离,宽为w的矩形,得到关于笔画折点的构造矩形序列{Pi;0≤i<M};遍历笔画的折点序列{zi;0≤i≤M},依次构造以折点为圆心、直径为w的圆,得到关于笔画折点的构造圆形序列{Ci;0≤i≤M};所述的矩形序列{Pi;0≤i<M}与圆形序列{Ci;0≤i≤M}的并集构成了笔画容差带;所述的w定义为笔画包络最小矩形的周长c及笔画宽度b的函数:
步骤3:依次比较两条输入笔画之间的最小包络矩形的周长大小,计算周长较小的笔画的采样点落入周长较大的笔画的笔画容差带的数量占周长较小的笔画的总采样点数的比例,若该比例大于一个给定的阈值p,则将该两条笔画添加到一个笔画集合中,每一个笔画集合为一个子草图gj,得到子草图序列G={gj;0≤j<m};
步骤4:遍历子草图序列G={gj;0≤j<m},采用单笔画识别方法判断子草图gj(0≤j<m)是否为直线段,如果是,则对该子草图进行直线段拟合,得到一条拟合直线段;否则,采用单笔画识别方法对子草图中的笔画依次进行单笔画识别,步骤如下:
1)若gj中只包含折线段笔画或同时包含折线段笔画和直线段笔画,则对其进行折线段拟合,得到一系列直线段的组合;
2)若gj只包含二次曲线,则对所有待拟合笔画的逼近折线段的折点进行最小二乘拟合;
3)若gj包含有折线段曲线和二次曲线的笔画,计算gj中各条笔画的最小包络矩形周长ci,并求出最大值cmax,依次将ci与cmax进行比较,若所有的ci都满足cmax-ci>cmax/3,则采用最小二乘拟合将子草图gj整体拟合为一条二次曲线;否则弹出人机交互对话框以供用户确定采用折线段拟合或最小二乘拟合;
所述的直线段拟合:随机选择待拟合的所有笔画的折点集合中的最远点对的某一个点作为该拟合直线段的起点,另一个点作为终点,连接起点和终点产生一条直线段;
所述的折线段拟合:将待拟合的所有的折线段笔画依据其笔画逼近折线段的折点分割为若干子笔画,然后如步骤3所述对所有子笔画进行笔画聚类,得到关于子笔画的子草图序列,最后依次对这些子草图序列进行直线段拟合,得到关于该折线段子草图的拟合直线段组合。
所述的N大于等于5。
所述的p为0.4。
所述的二次曲线类型包括椭圆、圆、双曲线和抛物线。
有益效果
本发明首先通过笔画逼近折线段的折点序列,构造包围笔画的容差带;然后通过依赖于多笔画重复绘制判定算法的聚类算法将原始草图分成若干个子草图;最后将这些子草图拟合为直线段、折线段、二次曲线等标准图元。本发明方法可以对在线多笔画重复绘制草图中的笔画进行聚类,有效解决不同类型重复绘制笔画的聚类问题,并且将聚类结果准确拟合为直线段、折线段、二次曲线等标准图元,从而将多笔画重复绘制草图高效转换为二维线图。
附图说明
图1:在线多笔画重复绘制草图的聚类与拟合方法的流程图;
图2:输入笔画的采样点、折点及最小包络矩形示意图;
图3:笔画容差带构造示意图;(a)构造矩形序列;(b)构造圆序列;(c)最终笔画容差带;
图4:多笔画重复绘制判定方法示意图;
图5:手绘三维模型投影图聚类与拟合实例;
具体实施方式
现结合实施例、附图对本发明作进一步描述:
本实施例中采用的多笔画重复绘制草图的聚类与拟合方法,采用以下步骤:
如图1所示,一种将在线多笔画重复绘制的草图转换为二维线图的聚类与拟合方法,包括以下步骤:
步骤1:首先,对接收到的输入笔画提取N个采样点,N不小于5,采样点包含笔画起点和笔画终点,相邻采样点的间隔时间不小于S,S取0.015s,得到笔画的采样点序列{pi;0≤i≤n},这里的输入笔画指按键——移动——松键的过程中形成的一条轨迹;然后,对有效输入笔画进行折线化逼近,得到折点序列{zi;0≤i≤M};最后,首先采用经典Graham扫描算法得到笔画的凸包,然后采用极值法得到笔画的最小包络矩形。如图2所示,笔画的采样点、折点和最小包络矩形分别用小黑点、蓝色圆圈和红色矩形框表示。
所述折线化逼近过程采用文献“WangS,GaoM,QiL.Freehandsketchinginterfaces:earlyprocessingforsketchrecognition[C]//Proceedingsofthe12thinternationalconferenceonHuman-computerinteraction.NewYork:SpringerVerlag,2007,4551:161-170”中公开的方法,其中折线化逼近程度系数C取0.2。
步骤2:通过笔画的折点序列构造笔画容差带;
通过笔画逼近折线段的折点构造一系列矩形和圆形创建一个带圆弧过渡的等距边线围成的封闭多边形区域作为该笔画的容差带,这个容差带是所有矩形与圆形的并集。具体算法如下:
首先,遍历笔画的折点序列{zi;0≤i≤M},依次在相邻两折点间构造一个长为该两折点间的欧式距离,宽为w的矩形,得到关于笔画折点的构造矩形序列{Pi;0≤i<M},如图3(a)所示;
然后,遍历笔画的折点序列{zi;0≤i≤M},依次构造以折点为圆心、直径为w的圆,获取关于笔画折点的构造圆形序列{Ci;0≤i≤M},如图3(b)所示;
最后,笔画容差带表现为上述矩形序列{Pi;0≤i<M}与圆形序列{Ci;0≤i≤M}的并集,如图3(c)所示。
本发明将笔画容差带的宽度w定义为笔画最小包络矩形周长c及笔画宽度b的函数,构造函数如下:
步骤3:若草图绘制未绘制完成,则转步骤1继续输入笔画;否则,得到输入笔画序列D={si;0≤i<u}(u为笔画数);
步骤4:对接收到的所有输入笔画序列D={si;0≤i<u}(u为笔画数)进行笔画聚类,从而将草图中所有输入笔画分成若干笔画集合(称为子草图),得到子草图序列G={gj;0≤j<m},其中,m为子草图数,gj={sk;0≤k<tj}(tj≤u)表示子草图,tj为子草图gj的笔画数。
具体步骤如下:
步骤4.1:新建一个空的子草图链表G,j=0,m=0,。
步骤4.2:新建子草图gj,tj=0,x=1,y=1。
步骤4.3:将D中的第一条笔画s0移除并添加到gj,tj=tj+1,u=u-1;若u=0,转步骤4.6。
步骤4.4:令x=y,y=tj,采用多笔画重复绘制判定算法依次判定D中剩余的笔画si(0≤i<u)与上一步添加到gj中的笔画sk(x-1≤k<y)是否构成多笔画重复绘制,若是,则将sk从D中移除并添加到gj,tj=tj+1,u=u-1。
判定两条笔画是否构成多笔画重复绘制的多笔画重复绘制判定算法具体如下,设nenter的初始值为0:
步骤4.4.1:比较两条笔画之间的最小包络矩形的周长,较小的笔画记为smin,另一条笔画记为smax;
步骤4.4.2:遍历笔画smin的采样点序列{pi;0≤i≤nmin},判断采样点是否落入笔画smax容差带的矩形集合{Pj;0≤j<M}中某一矩形内(或边界上),如果是,则nenter=nenter+1;
步骤4.4.3:遍历笔画smin的采样点序列,判断采样点是否落入笔画smax容差带的圆形集合{Cj;0≤j≤M}中某一圆内(或边界上),如果是,则nenter=nenter+1;
步骤4.4.4:计算nenter与Smin采样点个数nmin的比值,若nenter/nmin大于一个给定的阈值δ(本文取0.4),则认为该两条笔画构成多笔画重复绘制;其中δ的大小影响多笔画判定的严格程度,δ值越大则需要多笔画重复绘制时笔画绘制的越紧凑。
多笔画重复绘制判定示意图如图4所示。
步骤4.5:若y>tj或u>0,转步骤4.4;
步骤4.6:将gj添加到G,m=m+1;若u>0,则j=j+1,转步骤4.2;
步骤4.7:结束。
步骤5:遍历步骤4中得到的子草图序列G={gj;0≤j<m}(可能含有一条或多条笔画),依次将子草图gj拟合为标准图元,包括直线段、折线段和二次曲线,其中gj={si;0≤i<tj}(tj为其笔画数)。拟合子草图gj的具体步骤如下:
步骤5.1:判断子草图gj(0≤j<m)是否为直线段;如果是,则对该子草图进行直线段拟合,得到一条拟合直线段;否则,对子草图中的笔画依次进行单笔画识别。
这里的判断子草图是否为直线段和单笔画识别方法采用文献“王淑侠,高满屯,齐乐华.基于模糊理论的在线手绘图识别[J].模式识别与人工智能,2008,21(3):317-325”中公开的方法,可识别的曲线类型为单笔画或多笔画绘制直线段,单笔画绘制折线段和单笔画绘制二次曲线(包括椭圆、椭圆弧、圆、圆弧、双曲线和抛物线)。
根据笔画的单笔画识别结果,将笔画称为折线段笔画、直线段笔画或二次曲线笔画,其中折线段笔画和直线段笔画统称为折线段曲线。
直线段拟合的具体方法是:首先求待拟合所有笔画的折点集合中的最远点对,然后用随机选择该点对中的某一个点作为该拟合直线段的起点,另一个点作为终点,最后连接该起点和终点产生一条直线段;
步骤5.2:若gj中只包含折线段笔画或同时包含折线段笔画和直线段笔画,则对其进行折线段拟合,得到一系列直线段的组合。
折线段拟合的具体方法是:首先将待拟合的所有的折线段笔画依据其笔画逼近折线段的折点分割为若干条子段(称为子笔画),然后通过上述笔画聚类算法对所有子笔画进行笔画聚类,得到关于子笔画的子草图序列,最后依次对这些子草图序列进行直线段拟合,得到关于该折线段子草图的拟合直线段组合;
步骤5.3:若gj只包含二次曲线,则运用最小二乘拟合方法将其拟合为一条二次曲线,二次曲线类型包括椭圆(椭圆弧)、圆(圆弧)、双曲线和抛物线。
二次曲线拟合的具体方法是:以待拟合笔画的逼近折线段的折点集合为拟合数据,进行最小二乘拟合将其拟合为标准二次曲线,如式(1)所示,然后对标准二次曲线进行具体类型判定和封闭性检测与端点确定。
ax2+bxy+cy2+dx+ey+f=0(1)
二次曲线具体类型的判定采用文献“王淑侠,高满屯,齐乐华.基于二次曲线的在线手绘图识别[J].西北工业大学学报,2007,25(1):37-41”中公开的方法。
封闭性检测与端点确定采用文献“王淑侠,王关峰,高满屯,等.基于时空关系的在线多笔画手绘二次曲线识别[J].模式识别与人工智能,2011,24(1):82-89”中公开的方法。
步骤5.4:若gj包含有不同类型(折线段曲线和二次曲线)的笔画,则通过子草图中最小包络矩形的周长较大的笔画的类型或借助人机交互方式确定拟合结果:设gj中单笔画识别结果为折线段曲线的笔画集合为Pj={si;0≤i<fj},单笔画识别结果为二次曲线的笔画集合为Cj={si;0≤i<cj},fj+cj=tj。
具体步骤如下,设p=0,c=0。
步骤5.4.1:依次计算gj中各条笔画的最小包络矩形周长ci,并求出最大值,记为cmax;
步骤5.4.2:依次将ci与cmax进行比较,若cmax-ci<cmax/3且si为折线段曲线,则p=p+1;否则c=c+1;
步骤5.4.3:若c>0,p=0,则判定该混合类型子草图为二次曲线,采用所述二次曲线拟合方法将子草图gj整体拟合为一条二次曲线;
步骤5.4.4:若p>0,则弹出人机交互对话框以供用户确定曲线拟合结果,三种曲线拟合结果可供选择:1)“二次曲线”,采用所述二次曲线拟合方法将gj整体拟合为一条二次曲线;2)“折线段曲线”,采用所述折线段拟合方法将Pj拟合为一系列直线段的组合;3)“共现”,分别对两类笔画(Pj和Cj)进行折线段和二次曲线拟合,得到一条折线段曲线和一条二次曲线。
表1为采用本发明方法将在线多笔画重复绘制的三维模型投影图拟合为二维线图的实例。其中第一列为原始输入草图;第二列为草图中笔画的单笔画识别结果;第三列为笔画聚类结果,其中不同子草图以不同颜色表示;第四列将各个子草图拟合为标准图元的结果。
由图5可见,本发明方法可以有效解决多笔画重复绘制草图的聚类与拟合问题,将多笔画重复绘制草图高效转换为二维线图。图5第1行表明本发明方法可以很好地处理由折线段或直线段构成的多笔画重复绘制草图。图5第2~3行表明本发明方法可以将不同类型的笔画聚为一类,通过引入人机交互模式,可使系统准确地表达用户的设计意图;对笔画的折点序列进行最小二乘拟合可以较好的完成二次曲线拟合任务。
机译: 一种可见的植物草图绘制方法以及植物的zuchtgefaess
机译: 一种基于笔画识别的在线手写韩文识别方法
机译: 一种转换绣花框以便沿hz重复绘制的方法