基于几何特征的在线手绘草图分割

摘要

This paper describes a new method for segmenting non-single stroke to 2D geometric primitives based on geometrical features, which are further interpreted as 2D line drawings. This method can support rapid seg-menting and fitting of non-single stroke based on the polygonal vertices each stroke during its preprocessing stage. A processing stroke method based on polygonal approximation is used for online stroke compression. According to the convexity-concavity of a polyline which can represent the stroke, the stroke is classified convex stroke and concave stroke. For the former, an extraction principle of geometric feature is presented that stroke should be di-vided into sections as little as possible. Meanwhile, a corresponding algorithm is proposed based on this principle. For the latter, stroke need to be split into several convex strokes, then their geometric features are extracted. A new segmenting principle that the polygonal vertices should be most in per unit length of the stroke for that the concave stroke is split several convex strokes. Finally, a combination method of primitives is also introduced to eliminate over-segmentation. The proposed method has been tested with our stroke segmentation sub-system of online freehand sketch recognition system (FSR_JS), which is robust and easier to use by removing some limita-tions embedded with most existing sketching systems which only accept single stroke drawing. The test results showed that the proposed method can support freehand sketching based conceptual design with no limitations on drawing sequence and directions while achieving a satisfactory segmentation rate.%针对现有基于几何特征的笔画分割方法的不足, 提出一种将笔画分为可识别基本几何线元的组合的笔画分割方法. 首先将笔画的采样点进行基于折线化逼近的数据压缩, 得到反映笔画特征的折点序列. 其次依据折点的方向将笔画分为凸笔画和凹笔画, 对于凸笔画给出了其分割点提取原则——将笔画分割成跨度最大的几条子笔画的组合, 并给出了相应的提取算法; 而凹笔画的几何特征提取方法是先将其进行凸化处理, 将凹笔画分割成几个凸笔画的组合, 然后通过凸笔画的分割点提取算法得到凹笔画的分割点; 在进行凹笔画的凸化处理时提出了单位长度内所跨折点数最大的分割原则及算法. 最后采用单一线元合并方法对误分割点进行修正处理. 通过自主开发的FSR_JS原型系统对上述算法进行验证, 并给出了笔画分割点修正前, 后的比较分析, 结果表明, 本文方法能有效地解决在线手绘笔画的分割问题, 通过分割点的修正可有效地提高分割正确率, 为后期手绘图的识别研究及三维重构奠定了基础.