以下文章来源于深圳大学可视计算研究中心 ，作者曹仲豪
导读
本文是VCC曹仲豪同学对论文 Detecting Viewer-Perceived Intended Vector Sketch Connectivity 的解读，该工作来自不列颠哥伦比亚大学和英伟达公司并已被发表在计算机图形学顶级会议SIGGRAPH 2022上。
项目主页：
https://www.cs.ubc.ca/labs/imager/tr/2022/SketchConnectivity/
手绘的草图通常并不精确，在笔画之间通常会留有空隙，而人类观察者能很好地判断出空隙是否应该闭合。该工作基于人类的感知线索，训练了一组分类器，从草图当中提取出笔画之间的连接关系。
注：本文
均来自原论文与其项目主页。
I
引言
自由形式的草图在我们日常生活中随处可见，既作为一种艺术形式，也可以作为计算机应用程序的输入信息。由于触控设备的普及，这些草图中大多以矢量格式记录和存储，以方便后续的处理。草图处理程序通常需要输入的草图当中的笔画之间精确地相交在一起，然而艺术家绘制的自由形式草图通常是不精确且随意的:本来应该相连的笔画之间常常会留有开口。虽然人类观察者很容易感知到艺术家的笔画之间的连接意图，并且可以手动或者半自动地纠正这些错误，但是这一过程十分消耗时间，并且枯燥乏味。
一个可以想到的方法是使用经过人类注释的数据进行训练，该方法意味着需要一个庞大的经过完整注释的草图数据库。然而，一张草图包含着许多笔画，手动完成一张草图的注释通常需要20分钟以上的时间，所以该方法并不可行。本次导读论文介绍了一种新颖的算法，该方法结合了数据驱动和感知驱动。该方法基于人类观察者对于笔画之间连接性的局部和全局感知线索，可以从不精确的自由绘制矢量草图当中检测笔画的连接。该算法训练了两个分类器，这两个分类器通过局部线索，可以分别评估笔画之间形成端到端连接或者T字形连接的可能性。通过这两个分类器筛选之后，再利用全局上下文，识别出有可能形成回路的笔画。该方法使用95个输入草图来验证其有效性。该方法的有效性为92%，而人工标注有效性为94%。
II
技术贡献
本工作主要贡献如下：
首次提出一种大幅领先当前工作的草图笔画闭合算法；
成功提取人类观察者感知笔画连接性的全局和局部线索。
如下图所示，参与者被询问该方法与其他方法的上色图像哪一种结果更好。结果表明，大部参与者都认为该方法生成的结果相较于其他方法而言更加优秀。
图1 在所有竞争方案当中，参与者以9比1或更多的比例选择该方法
III
方法介绍
本方法首先研究了人类观察者的感知线索，然后将该线索应用到分类器训练中，最后通过分类器来评估笔画之间形成连接的可能性。
符合预期的草图连通性感知研究
该算法的目标是识别人类观察者所能感知到的连接和间隙。在对相关文献的回顾当中，部分文献指出了观察者在识别连接时可能使用的一些线索。Company等人[1]指出，笔画断点之间的距离在对于是否连接的感知当中起着很大的作用，如图2中 和 所示，一般会认为a中的笔画是相连的，而b中的笔画应该断开。值得注意的是，该距离是相对的，而不是绝对的，在同一距离下，更宽的笔画会认为更加靠近；同样的，更长的笔画相比短的笔画更容易被认为是相连的。笔画之间的角度也是一大考量因素，如图2中 和 所示。可以注意到，其他笔画的存在与否也会影响到连通性的判断，如图2中 和 所示。最后，闭合原则[2]在分析草图连通性时是一个关键原则。该原则指出，如果闭合笔画间的空隙会形成封闭环路的话，观察者很可能在心理上倾向于自动闭合笔画之间的空隙。在形成一个环路时，我们可以考虑在环路内内切的最大圆的直径D与序列中连续笔画之间最大的间隙L的长度之间的比值 ， 值越大，观察者越倾向于认为应该形成环路。通过分析， 的最小值为1，即若低于数值，则观察者就倾向于不形成环路，该数值被称为最小环路比。
图2 人类观察者使用局部和全局线索来确定悬空端点(红色)是有意的，还是连接的一部分
分类器训练
该方法训练了两个分类器。第一个分类器负责判断笔画端到端之间是否形成回路。给定笔画 和 上的两个端点 和 ，该分类器使用了四组特征。首先是距离特征，如下公式所示，该距离使用了笔画之间的包络距离，其中 和 为曲线的最大宽度：
接下来是两端笔画的方向，如下图所示，该方法引入了笔画的切线和端点之间的夹角 , ,同时测量了 , 分别后退 后到对方笔画的距离。
图3 笔画特征
然后是笔画的相对位置,使用 在 上的投影点 ， 沿着笔画 到其最近的端点的距离即为该特征值。最后是局部上下文特征。该特征为端点 到除了笔画 和 之外最近的笔画的距离。
第二个分类器判断笔画之间是否形成T字形闭合。该分类器的距离、方向和上下文特征与第一个分类器相似，区别是方向特征只计算单边。同时，该分类器引入了一个新的特征，端点的密度值,即为该端点到区域中所有端点的距离函数。其中, 为该端点所属的笔画的平均宽度。
算法流程
主要流程如下图所示，首先通过两个分类器生成主要的连接（笔画之间端到端的连接和T字形的连接），然后在主要连接的基础上继续生成次要连接（例如多个笔画的相连），最后应用闭合原则闭合回路，生成最终的结果。
图4 算法流程
主要连接分类
主要连接步骤首先确定有可能形成预期连接的端点对或端点和笔画，然后使用两个分类器计算形成每一个连接的相应概率。当将要闭合的笔画符合闭合原则的情况下，若一个端点有两个或者以上可能形成的连接时，选择概率最大化的连接笔画形成连接。
图5 主要连接的连接流程
次要连接分类
次要连接主要关注的是多个笔画之间的连接。它分析了剩余的悬垂端点和在上一步确定主要连接的节点，并评估是否应该将悬垂笔画与这些节点相连接。该步骤可以使用T字形连接分类器来进行该判断，即将已经相连的两条笔画当成是一条笔画，再与剩余的笔画进行比较。
全局闭合分类
最后一个步骤是判断潜在的闭合环路。首先，在所有相邻的笔画上找到最近的点对;对于每一对点对，计算由连接该点对对与所形成的回路的最小环路比 ，若 ，我们则认为该点对之间应该形成连接。
IV
部分结果展示
下图展示了该算法的生成结果和与不同方法之间的比较，草图当中不连通的区域被赋予了不同的颜色。可以看出，该工作相比于其他工作，在应该闭合的相应区域能较好地完成任务。
图6 该研究方法和其他方法的比较
V
总结与展望
该工作提出了一个全新的方法，用于闭合自由绘制草图里的应该闭合的区域。该方法通过局部和全局的人类感知线索训练了二元分类器，可靠地预测了端点之间形成合理连接地可能性。该研究在不同精确度的草图上都成功验证了结果的可靠性。尽然如此，仍然有少部分图像生成的结果令用户不满意（如图1所示，部分参与研究的用户选择了neither），表明该工作仍有后续提升的空间。
VI
思考与讨论
Q: 除了本文方法，还有其他消除间隙的方法吗？效果如何？
A: 该方法是第一个以全自动的形式消除间隙的方法。其余的间隙消除方法主要设计成半自动的形式，可以大致分为两类:一种是先收集用户输入，然后将此输入应用于核心算法的方法;另外一种是首先自动执行笔画连接的步骤，然后让用户以交互的方式改进初始结果的方法。这两种方法都不能达到减轻参与人员工作量的目的。
Q: 能否依照笔画输入顺序来决定是否连接相应笔画？
A: 如下图所示，当呈现一个不完整的草图时，该方法和人类观察者都认为两条蓝色笔画应该相连，但实际情况相反，因而在绘制过程中自动关闭这些间隙所达到的结果并不理想。处理完整的草图为该方法提供了更完整的决策背景，使得输出更好地反映艺术家的意图。
图7 一张草图在不同的绘制阶段
以下是开放性问题，欢迎读者朋友留言讨论：
Q: 在本研究中，输入的草图笔画都是需要整合和美化，以避免过度绘制的情况出现。然而实际情况中，一般的草图都是随手绘制，过度绘制的笔画（overdrawing）难以避免，能否在后续工作中将笔画的简化与笔画的连接两个步骤相结合？
转自：“arXiv每日学术速递”微信公众号
如有侵权，请联系本站删除！
