Web环境下手绘草图数据实时精简方法

舒 瑶，盛步云，萧 筝，赵飞宇，张成雷

(武汉理工大学 机电工程学院, 湖北 武汉 430070)

近年来，随着大众创新创意设计能力和意识的提高，越来越多的普通消费者希望亲自参与甚至是独立完成产品的设计和制造，体验产品的三维建模和加工制造过程。同时，伴随着互联网技术与先进制造技术的快速发展与融合，一种满足用户“个性化设计和制造”需求的服务平台——3D打印云平台正逐步进入普通大众的视野。3D打印云平台的出现使得普通大众有机会利用昂贵的3D打印设备和软件独立进行产品创新设计与制造。而3D打印的前提是3D建模，目前大部分3D打印云平台的建模方式大多采用传统的WIMP(window, icon, menu, pointer)输入方式。这种3D建模方式需要频繁地切换选择各种菜单和按钮，对用户的专业要求较高，制约了普通用户创新力的发挥。而手绘草图三维建模技术操作简单、交互性强、符合传统纸笔交互习惯，可以解决上述问题。但与此同时，由于在3D打印云平台上进行三维建模的过程是处于Web环境下的，因此，其对手绘草图数据的在线传输与处理提出了更高的实时性和高效性要求。

手绘草图三维建模通过采集用户手绘的轨迹数据来绘制草图，再通过拉伸、旋转、放样、扫描或膨胀等操作生成三维网格，从而实现三维模型的建立。由于采集到的顶点数量繁多且存在抖动和外界干扰，导致原始数据中含有较多的噪声和冗余点，严重影响Web环境下数据的传输与处理，降低了三维模型在线生成的速度和质量。

近年来，关于手绘草图的研究主要集中在草图的分割与识别[1-2]，而对手绘草图数据的压缩精简研究较少，特别是对Web环境下手绘草图数据的实时精简研究更少。目前，最简单的手绘草图数据精简方法是均匀采样法[3]，其运算效率较高，但是无法保证精简结果的稳定性。而最常用的是经典的道格拉斯普克算法[4]，该算法具有平移、旋转、逆向不变性和压缩误差小等优点，但其时间复杂度较高，属于批量处理算法。除此之外，还有分裂-合并法[5]、角点检测法[6]以及动态规划法[7]等。但是，这些算法均为离线批量处理算法，其耗时较长，难以满足Web环境下手绘草图数据传输和处理的实时性和交互性要求。针对这一问题，同时考虑到用户手绘习惯的不确定性和随意性，提出一种适用于不同手绘速度的数据实时精简方法，以满足Web环境下手绘草图三维建模对数据传输、处理的实时性和对模型的轻量化方面的要求。

1 Web环境下手绘草图三维建模流程

如图1所示，Web环境下手绘草图三维建模的流程可分为3大步骤：客户机本地数据采集与重采样、Web服务器端数据实时精简以及客户机浏览器端三维模型生成与修改。

(1)手绘草图数据通过连接在客户机本地的手绘板进行采集，同时，为减轻网络数据传输压力，去除原始数据中的噪声点，保证在不同手绘速度下得到的点列密度大致相同，笔者通过设定相邻两轨迹点间的最小距离，在数据采集过程中对原始数据进行实时重采样，即弦长限值法。通过该方法初步去除手绘草图较密区域的部分冗余点。

图1 Web环境下手绘草图三维建模流程

(2)为了尽量提高手绘草图数据的处理效率，重采样得到的手绘轨迹点将被实时上传到Web服务器上，以对其进行实时精简处理。精简方法选用的是基于滑动窗口控制的长度误差法。使用长度作为衡量误差的标准比使用垂直欧式距离作为衡量误差的标准更准确，且可以重复利用上一步重采样过程中计算得到弦长值，因此可以进一步提高计算效率。

(3)Web服务器将精简后的数据发送到客户端浏览器，并按顺序连接精简后的手绘草图，得到一个首尾封闭的二维多边形。再对其进行拉伸和网格化处理后，生成最终的轻量化模型。

2 手绘草图数据实时精简

2.1 数据采集与预处理

手绘草图数据的采集量受采样设备、用户习惯和外界干扰的影响，其具有数据量大、数据疏密程度不一致、顶点分布不均匀、数据质量差等特点。因此，在手绘草图数据传输到Web服务器之前需要进行预处理，以提高后续数据的网络传输和处理效率。针对手绘草图数据的特点及存在的问题，笔者提出弦长限值法在数据采集的过程中对其进行实时重采样，以稀释原始数据的密集段并消除噪声点。

通过手绘板采集到的草图数据是一系列矢量轨迹顶点[8]。弦长限值法的基本思想就是在原始数据采集的过程中实时地计算相邻顶点之间的弦长，并删除弦长小于阈值的顶点，得到顶点疏密一致、且原始信息保存较为完整的重采样轨迹。设原始手绘草图数据为：Sn={Pi:(xi,yi),i=1,2,…,n}，则弦长限值法实时重采样的步骤如下：

(1)用户下笔绘制草图，采集得到轨迹起始点P1；

(4)用户提笔，绘画完毕，同时原始数据全部采集并重采样完成。

原始数据重采样的效果如图2所示，用户手绘的原始点列Sn在起点A和终点E处存在明显的抖动和停留，且在拐点B、C、D处，由于手绘速度减慢导致原始数据较为密集。重采样后，A、B、C、D、E处附近的顶点明显被稀释且消除了噪声干扰。同时，草图轨迹的平滑性、连续性等特性得以保留。记重采样后的手绘草图数据为：Sm={Pi:(xi,yi),i=1,2,…,m,m4.5 px时，重采样后虽然可以全部去除原始数据中的噪声且不会出现局部点列过密的情况，但是会导致原始数据在拐角处和尖角处丢失一部分特征信息；因此本文选择lε=4.0 px作为重采样的阈值。

图2 原始点列弦长限值法重采样效果

2.2 手绘草图数据实时精简方法

不同手绘情况下采集到的数据经过重采样后得到的是一系列疏密程度大致相等且保留了原始数据几乎所有特征信息的点列。此时的点列虽然分布较为稀疏，但仍存在大量可以精简掉的非关键顶点。通过实验发现：曲率越小的地方，可删除的非关键顶点越多；而曲率越大的地方，需要保留的关键顶点越多。针对这种情况，再考虑到重采样之后点列Sm中相邻两点间弦长已知，提出了在重采样过程中利用滑动窗口控制的长度误差限值法快速删除Sm中曲率极小处的非关键点，保留曲率极大处的关键点。同时，为了减少计算量，利用滑动窗口内的长度误差代替离散点局部曲率。

滑动窗口算法非常简单直观、快速高效，适用于在线实时处理具有无限、高速等特性的数据流[9]。手绘草图数据流的在线实时处理与离线处理相比，其计算对象往往不是整个笔画的所有点列信息，而是把计算对象限定在某个可操作的范围内，如一个滑动窗口范围内的点列信息。长度误差的计算公式为：

El=(Lsum-L)/Lsum×100%

(1)

式中：Lsum为滑动窗口范围内相邻两点间连接线段长度的总和，其结果可以直接从重采样过程中获得；L为滑动窗口范围内连接首尾两端点的线段长度。

基于滑动窗口的长度误差限值法主要思想是：给定手绘草图数据精简的长度误差阈值ε，再判断精简掉窗口内所有中间点后长度误差El的范围；如果El<ε，则扩大滑动窗口范围直到El≥ε，再将上一个窗口内的所有中间顶点删除；如果在初始滑动窗口中El>ε，则直接保留窗口内所有的顶点。其具体的流程如图3所示。

图3 基于滑动窗口的长度误差限值法流程图

图4 基于滑动窗口的长度误差限值算法示意图

另外，采用MDL-2算法[10]对数字曲线逼近效果准确率为94.5%，并将其作为本文草图数据精简的理想值，同时结合实验测试结果，最终确定长度误差El的阈值ε取值为5.0%。

3 实例应用与结果分析

为了验证提出的手绘草图数据实时精简方法的有效性，将其应用到一款基于Web的三维轻量化建模系统中，并通过设计多组实验对该方法的实际精简效果进行对比分析。实验采用的手绘板型号为Wacom Bamboo CTL-671/ K0-F，其采样频率为133点/s，分辨率为0.01 mm/点。在一台Intel(R) 至强Xeon-E5-2620V4 2.1 GHz CPU，32 GB RAM，600 GB 15 000 r/min硬盘的服务器上部署该系统。利用局域网和Chrome浏览器在一台Intel(R) i5-6500 CPU 3.2 GHz，8 GB运行内存，500 GB 5 400 r/min硬盘，核心显卡的客户机上访问该系统。然后在手绘板上以5种速度绘制4种不同的图形，对数据精简前后生成三维建模的过程与结果进行对比测试。

测试用的手绘草图数据为一组常被用于多边形逼近算法和特征点提取算法性能检测的经典benchmark轮廓曲线[11-12]。通过以300 px/s的速度绘制该组曲线，再用本文的方法对其进行重采样和精简处理，结果如图5所示。

表1为4种图形以5种不同的速度绘制时，数据精简前后多个参考指标的比对。表中N为原始数据顶点个数，M为重采样后顶点个数，K为精简后顶点个数，CR=N/K为顶点总压缩比，El为精简后总长度误差，T1为精简前模型生成时间，T2为精简后模型生成时间，ηt=(T1-T2)/T1

图5 4种经典图形的草图轨迹处理效果

为模型生成速率的提高量，S1为精简前生成三维模型的大小，S2为精简后生成三维模型的大小，ηs=(S1-S2)/S1表示数据精简前后三维模型的轻量化程度。

表1 4种不同图形以5种不同速度绘制时的精简结果

通过分析表1可知：用不同的速度绘制同一个图形时，手绘速度越慢，采集到的原始数据就越多，数据的精简效果也越好；但是在不同的手绘速度下，重采样后的数据量以及精简后的数据量、数据误差大小、模型生成时间以及生成的三维模型文件大小几乎不变；而用相同的速度绘制不同的图形时，数据的压缩率一致。这表明：本文算法的数据精简效率与图形种类无关而与用户的手绘速度有关。如图6(a)所示，对所有不同图形而言，手绘速度越慢，数据精简后模型生成速率提高越多。同样地，通过分析图6(b)可知：手绘速度越慢，数据精简后三维模型轻量化程度越高。

图6 不同手绘速度下的数据精简效果

4 结论

笔者提出的Web环境下草图数据实时精简方法综合考虑了不同手绘条件，如设备采样频率、用户手绘速度、手绘草图形状、笔尖抖动和停顿等因素对草图数据采集和精简效果的影响，设计了弦长限值法对原始数据进行实时重采样。重采样处理不仅大大减少了原始手绘草图数据量，还可以消除因抖动和停顿产生的噪声点和冗余点。同时，基于滑动窗口控制的长度误差法有效地利用了重采样过程中的弦长数据，提高了Web环境下草图数据的处理效率。最终，通过将该方法应用到一款基于Web的三维轻量化建模软件中，验证了笔者提出的方法可以在保证生成的三维模型不失真的情况下，大大精简了Web环境下需要传输和处理的草图数据量，并使三维模型的生成速率提高了60%～90%，使三维模型的轻量化程度提高了7%～30%，基本满足Web环境下手绘草图三维建模的要求。