基于曲线逼近的简图参数化外文翻译资料

英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

基于曲线逼近的简图参数化

摘 要

本文提出了一种基于分段三次Bezier曲线逼近的在线徒手画对象参数化方法。目标是在一定的容错范围内以紧凑的格式表示简图，以较低的计算量来实际适应在线图形输入。首先根据笔速和局部曲率，在数字墨水中生成一组用户预期的断点。然后通过优化分段Bezier曲线逼近来参数化一个简单图案的每个笔划，以最小化笔划路径与曲线之间的拟合误差。实验结果表明，这两种方法对于绘制各种图形对象都是有效的。

关键词：Bezier曲线，参数化，曲线拟合

一 介绍

随着计算机融入日常生活，基于笔的用户界面被视为主要的输入方法。 此外，使用无法通过语音或文本有效表示的图形对象快速可视化和传达人类想法的功能在图形计算中非常受欢迎[1]。 图形数据的快速增长持续需要更有效的方法来表示和压缩粗略图形数据。 代表写意的数据不仅需要压缩以减少内部处理大小和低带宽传输，而且还需要保留用户的初衷和信息的方便访问和进一步处理，例如形状识别、协同设计、创意排列等。

对于现有技术，笔的移动通常由数字化板捕获，并作为路径的采样笔点存储，称为数字墨水，同时捕获接收器的图像。这种技术的缺点是，在图像中传输的简图通常需要相当大的存储容量，并且不能被接收器修改。尽管已有大量的简图识别实验，如基于特征的[2][3]、基于图形的[4][5]、机器学习[6][7][8]和参数化方法，如多边形[9]、B样条[10]和贝塞尔曲线[11]，但大多数实验都是猜测并将图形简图转换为规则形状。然而，它们被指控背离用户的意图，并且是计算的负担，特别是对于移动设备。在形状表示和分类中考虑了参数化方法和拟合技术。这些方法的一个好处是，它们可以在用户绘图过程中使用几个参数来近似笔移动的路径，并且计算效率高。只有少数研究致力于这个问题[11][12]。

在本文中，介绍了一种简图近似方法，该方法使用分段递归三次贝塞尔曲线近似对在数字墨水中捕获的在线手绘对象执行有效的参数化。 目标是以紧凑的格式表示手绘简图，在一定的容错范围内实现高压缩率，并以较低的计算量成为实际应用中实际适用的解决方案。

本文的其余部分组织如下：我们提出的策略的主要思想在第 2 节中概述。在第 3 节中，给出了用于生成用户预期断点的笔画分段方法。 在第 4 节中，我们将详细讨论递归贝塞尔曲线近似的简图参数化。 第 5 节将展示我们的实验。 最后一节给出了结论。

二 简图参数化的建议策略

贝塞尔曲线表示法由于其系数易于获得且其形状易于操纵而被广泛使用。一条贝塞尔曲线使用两个锚点、曲线上控制点和至少一个形状点、曲线外控制点来定义。曲线上控制点是实际位于曲线路径上的曲线的两个端点，而其他曲线外控制点定义了从两个端点开始的梯度，通常不位于曲线路径上。曲线外点控制曲线的形状。曲线实际上是曲线外控制点的混合。贝塞尔曲线的曲线外控制点越多，可以表示的形状就越复杂，但是会使数学曲线方程的阶数变得更高。使用高阶贝塞尔曲线近似手绘笔画减少了曲线上的点数并产生更紧凑的数据表示。然而，高阶曲线方程的逼近通常需要大量的计算。

为了轻松操作简图，Raymaekers 等人 [11] 提出了一种方法，将简图的各个像素分组为由三次贝塞尔曲线表示的段。每当曲线拟合的最小二乘误差超过预设阈值时，就会创建一个新的线段，并可以通过最小二乘法最小化构建该线段的两个偏离曲线点。为了简图的计算效率和数据压缩，Park 和 Kwon [12] 最近提出了一种简图近似方法，通过使用最小二乘误差近似对一系列二次贝塞尔曲线进行分段拟合。上述两种方法的共同点是曲线控制点的产生仅依赖于局部几何曲率，使得曲线与相应数据点之间的差异尽可能小。然而，单独由曲率信息确定曲线控制点并不是传递用户意图的可靠方式。并且使用最小二乘误差近似拟合未确定的分割点也很耗时。

我们提出了一种使用三次Bezier曲线参数化简图的方法，其中复杂形状的笔划由分段近似的三次Bezier曲线表示，因为Bezier曲线只能表示简单的弧形曲线。图1显示了我们提出的近似方法的处理图。该过程有两个独立的子处理模块，笔划分段和曲线近似循环。笔划分段仅在每个给定笔划输入集执行一次，以在每个笔划处生成一系列用户预期的断点，其中笔划移动速度达到最小值，曲率急剧变化。选择这些候选断点作为曲线近似循环中的初始曲线控制点。曲线逼近例程，包括曲线控制点（包括曲线上和曲线外控制点）选择、Bezier曲线逼近和拟合误差评估，递归运行，直到分段拟合误差达到满意程度。递归曲线近似循环有两个嵌套的子进程。内部是非曲线控制点的优化，它优化分段曲线逼近以最小化拟合误差。外部是对曲线上控制点的调整，通过对每条当前曲线进行二等分来生成一些新的曲线上控制点，以增加分段数并减少拟合误差。由一组笔划绘制的输入图形对象最终可以表示为某些三次贝塞尔曲线的一组参数。通过优化曲线外控制点，可以在一定程度上避免由于使用一系列三次贝塞尔曲线（与高阶贝塞尔曲线近似值相比）而在笔划上产生过多断点（曲线点上）的风险。

图1 使用递归曲线逼近的简图参数化示意图

三 用户指定的断点生成

笔画碎片是一个非常基本的问题，使其广泛适用于智能墨水操作以及其他更高级别的数字墨水分析。笔画碎片化的目标是将各种各样的简图符号碎片化为更简单的结构，以便它们能够以不太复杂的形式忠实地表示原始形式。笔画碎片的主要挑战是找出哪些颠簸和弯曲（断点）是有意的，哪些是意外。大多数现有方法仅基于曲率进行笔划分段。通常，单独的曲率信息不足以确定这些点。相反，基于速度的方法已被证明是一种更可靠的措施，用于确定预期的断点，以便观察到笔尖的速度在预期的角点 [5] [13] 处显着降低。对于简图参数化，笔划分段的目的是通过笔速和曲率信息快速提取每个笔划处的急转笔移动点和弯曲点，这些点作为贝塞尔曲线的初始曲线控制点。

（一） 基于笔速的候选断点选择

已经发现，在形状 [5][13] 中制造多种有意的不连续性（例如由两条线形成的角）时，很自然会减慢笔的速度。 类似地，当使用单个笔划绘制矩形时，用户可能会在角落处放慢速度，这些角落应该是线段点。 图 2 显示了我们实验中典型正方形的速度曲线。 可以通过低笔速轻松识别角落。

图2 1正方形速度剖面图

给定一个数字笔画 S，其中包含 N 个按时间顺序排列的点 {P1, P2,..., PN}。 还有一个对应的速度序列：{SP1,SP2,hellip;,SPN}，其中SPi代表点Pi处的笔速。 当满足以下条件时，点 Pi 将被选为候选断点：

其中，是整个笔画的平均笔速，a和b是两个阈值，它们会根据笔画的长度影响候选断点的间距，必须通过一些统计实验来设置。

（二） 基于曲率的候选断点生成

在某些情况下，某些用户的预期断点无法通过笔速定位，因为用户可能会在没有笔速变化的情况下流畅地绘制它，所以必须使用曲率信息来捕捉这些点。 我们开发了一种近似方法来测量段或笔画的曲率变化，并使用基于滑动窗口算法 (SWA) 的贪婪方法来选取候选断点。 给定一个固定大小的窗口，该窗口包含一个笔画的许多连续墨点，从每个样本点到窗口中连接第一点和最后一点的线的距离 dink 可以根据它们的相对位置进行计算和签名 绘制方向，即左侧的距离为正，右侧的距离为负，如图3（a）所示。 这两个点之间所有墨点的距离之和可以看作是一个线段受两个端点影响的曲率的度量。

相应地，从笔画的第一个样本点开始，我们首先设置一个单位宽度的滑动窗口，该窗口包含至少两个连续的笔画墨点，计算窗口中线段曲率的测量值，如图所示图3（b）。窗口的宽度随着笔画的绘制方向逐步加宽，窗口中线段曲率的测量值是递增计算的，直到测量值超过实验阈值或测试笔画的所有墨点。每当测量值超过实验阈值时，该窗口中的最后一个点将被选为候选断点并作为下一次重复的新起点。然后，原始大小的窗口移动到该点的位置，重复上述相同的过程，直到检查窗口中的所有连续点，如图3（b）所示。它可以最大限度地减少由笔移动抖动引起的过度分裂的机会。窗口大小取决于笔画的墨点密度，并且可以作为每个笔画的周长和边界框的函数给出。窗口扩大的步骤和曲率测量的阈值必须通过在精度和效率之间进行权衡来实验定义。在我们的实验中，两个参数分别设置为 15（像素）和 150（像素）。

图3. 使用曲率生成候选断点

经过上述处理后，除了笔划的两个端点之外，还可以得到两部分候选断点，它们是笔速达到局部最小值的墨点，或者曲率测量值局部最大值的墨点。 但是，其中一些是冗余的，需要进行候选合并以去除多余的或相邻的点。 最终，任何两个相邻的断点将它们之间的线段作为子笔划分开，并将用作三次贝塞尔曲线的初始曲线控制点。

四 使用分段三次贝塞尔曲线的简图参数化

（一） 三次贝塞尔曲线逼近简图原理

对于具有一些断点（可以只有两个端点）的碎片化笔画（或笔画的一部分）有资格进行进一步处理，应用三次贝塞尔曲线逼近方法来找出曲线控制点。 估计具有两个曲线上控制点和两个曲线外控制点的三次贝塞尔曲线满足以下条件，如图 4 所示。

图 4. 三次贝塞尔曲线近似的简图

(1). 估计曲线的两个on-curve控制点应该是笔画的断点（包括首尾墨点）； 例如，P0和P3、P3和P6，如图4所示。

(2). 估计曲线的两个偏离曲线控制点应分别位于该段两端（入曲线控制）点的相应切线上； 例如，P1.位于P0处的切线T1上，P2.位于P3处的切线T2上，依此类推，如图4所示。

(3). 对于共享一个公共断点的任意两个相邻线段，例如图 4 中的 P3，它们在该点的切线应共线，以使曲线平滑连接，即图4中的T2和T3是共线向量。换句话说，连续段的第一个偏离曲线的控制点应该与前一段的最后两个曲线控制点共线； 例如，P2、P3和P4应共线。

(4). 通过优化偏离曲线控制点，使实际行程与近似曲线的拟合误差在可接受范围内。 如果拟合误差超过某个阈值，则应调整曲线上的控制点。 对每个新生成的段重复递归曲线拟合操作，直到误差落入容差范围内。

对于具有两个端点P0和P3的给定线段（或整个笔划），其具有两个曲线上控制点P0和P3以及两个曲线外控制点<stron

剩余内容已隐藏，支付完成后下载完整资料</stron

资料编号：[595903]，资料为PDF文档或Word文档，PDF文档可免费转换为Word