任意形状目标点选落点区域可能性分布预测方法及系统

摘要

本发明提出一种任意形状目标点选落点区域可能性分布预测方法及系统，属于计算机图形用户界面领域，在显示的界面内容上选择一个具有任意形状的目标，获得该目标的质心坐标；利用多边形最大内切圆算法在目标中寻找最大内切圆，再将该最大内切圆从原目标中切割出来，迭代实现将目标划分成多个内切圆区域；获取各个内切圆区域的中心坐标以及半径，计算出用户点击目标时落入各个内切圆区域的概率。本发明针对平面上的复杂多边形目标选择任务，通过切割最大内切圆来划分区域，计算区域中心面积和到目标质心的距离，预测出落点落入任意区域的可能性分布，预测更加简单、高效。

说明书

技术领域

本发明属于计算机图形用户界面领域，具体涉及图形用户界面中针对任意形状目标点选落点区域可能性分布预测方法及系统。

背景技术

随着大型网络游戏、增强和虚拟现实系统等应用的普及，需要用户进行点选目标的场景变得越来越多，例如第一人称视角的射击类游戏、元宇宙中的交互等等。同时随着计算机图形学、动画设计等领域的发展进步，用户的画面已经不再是简单的矩形、圆形等基本图形的罗列，而是由各种各样不规则的复杂形状所组成。例如在射击类游戏中，不同的用户角色往往对应着不同的不规则的外部轮廓。在上述这些场景中，目标的尺寸以及形状因素都会对用户进行目标选择任务时的落点分布有着很大的影响。因此为了辅助界面设计人员的工作，需要一种简洁明了的任意形状目标的用户点选落点分布预测方法。

在真实的交互场景中，被选择的目标往往在两个维度上都存在有界尺寸。因此，很多研究探讨了二维目标形状对用户点选目标时的表现的影响。MacKenzie和Buxton两人考虑到用户点击目标时靠近目标的角度的不同对目标的宽度提出了五种表示方法，从而将本来只适合于一维的目标选取任务的菲兹定律拓展到了二维空间中(参考文献：MacKenzie,S.and Buxton,W.(1992).Extending Fitts'law to two-dimensional tasks.ACM CHIConference on Human Factors in Computing Systems.p.219-226.)。更进一步地，Accot等人发现对于一个固定大小的二维目标来说，目标对用户在进行选择操作时的幅度约束W和方向约束H有着不一样的影响效果，而且幅度约束W相较于方向约束H要更加占据主导地位。因此他们提出了一个带有自由权重系数η的欧几里得模型来平衡这两种不同的影响(参考文献：Johnny Accot and Shumin Zhai.2003.Refining Fitts'law models forbivariate pointing.In Proceedings of the SIGCHI Conference on Human Factorsin Computing Systems(CHI'03).193-200.)。

需要特别强调的一点是上面提到的这些工作的研究重点基本上都集中在点击矩形目标的任务上。然而随着近些年计算机图形界面的发展，在当前的用户界面中点击具有任意不规则形状的目标已经变得非常常见。Sheikh等人在关于菲兹定律的研究中发现目标的形状对于用户选择目标的移动时间有着显著的影响。他们通过利用二维正态分布和一个“cookie-cutter”方法来估计目标的形状并且显著提高了菲兹定律对于不同形状的目标的用户点选时间预测的准确度(参考文献：Sheikh,I.H.,&Hoffmann,E.R.(1994).Effect oftarget shape on movement time in a Fitts task.Ergonomics,37(9),1533-1547)。在另外一个值得注意的研究中，Tovi Grossman等人提出了一个基于概率的菲兹定律模型，在静态的目标选择任务中这个模型可以比较准确的预测出用户点击大量非矩形的目标时的所需要的移动时间。该基于概率的菲兹定律模型的核心思想是将开环运动中击中目标的概率映射到原始菲兹定律的难度值指标(参考文献：Tovi Grossman,Nicholas Kong,andRavin Balakrishnan.2007.Modeling pointing at targets of arbitrary shapes.InProceedings of the SIGCHI Conference on Human Factors in Computing Systems(CHI'07).463-472.)。

然而，上述这些有关目标选择任务的研究都无法直接应用到实际应用中。这主要是因为两个原因，首先，这些模型都过于复杂，例如Grossman的模型需要对任意形状的目标所围成的封闭区域进行积分，这是非常困难的操作。其次，尽管已经验证了在拥有常规图形的目标(例如圆形、矩形)上用户的点选落点分布正态分布符合，但是对于拥有不规则形状的目标用户的落点分布很有可能是多个分布的叠加，然而上述模型的大部分前提假设都是落点符合二维正态分布。因此，需要提出一种针对任意的一个目标形状可以直接给出划分的区域集合以及落点落入任意区域的可能性的模型，该模型对以选择复杂多边形目标为任务的应用软件的开发设计具有重要的指导作用和实践意义。

发明内容

本发明的目的是提出一种任意形状目标点选落点区域可能性分布预测方法及系统，针对平面上的复杂多边形目标选择任务，通过切割最大内切圆来划分区域，计算区域中心面积和到目标质心的距离，预测出落点落入任意区域的可能性分布。

为达到上述目的，本发明提供如下技术方案：

一种任意形状目标点选落点区域可能性分布预测方法，其步骤包括：

在显示的界面内容上选择一个具有任意形状的目标，获得该目标的质心坐标；

利用多边形最大内切圆算法在目标中寻找最大内切圆，再将该最大内切圆从原目标中切割出来，之后在剩余的图形中寻找最大内切圆并从图形中切割出来，按此迭代进行，实现将目标划分成多个内切圆区域；

获取各个内切圆区域的中心坐标以及半径，根据该中心坐标和所述质心坐标计算各个内切圆区域的中心到质心的距离，根据内切圆区域的半径和中心到质心的距离计算出用户点击目标时落入各个内切圆区域的概率。

进一步地，目标的质心坐标为世界坐标系下的坐标。

进一步地，多边形最大内切圆算法为ImageJ中用到的Max Inscribed Circles算法。

进一步地，在剩余的图形中寻找最大内切圆并从图形中切割出来，按此迭代进行，直到所剩图形的面积不足原目标图像面积的20％。

进一步地，内切圆区域的中心到质心的距离包括内切圆区域的中心到质心之间在切线和法线方向上的距离。

进一步地，计算用户点击目标时落入各个内切圆区域的概率p

式中，r

进一步地，系数a,b根据经验数据拟合得到，步骤包括：

指定目标大小和形状作为实验条件；

将初始显示界面呈现给用户，记录用户多次选择落点位置数据，作为该实验条件下的经验数据，重复获取多个实验条件下的经验数据；

记录目标的各个内切圆区域上真实的用户落点数量所占用户点击该目标的总落点数量的比值；

将各个内切圆区域上真实的用户落点数量比值与公式计算得到的预测概率构造最小均方误差，再利用梯度下降算法对数据进行优化拟合，得到系数a,b的值。

一种任意形状目标点选落点区域可能性分布预测系统，包括存储器和处理器，在该存储器上存储有计算机程序，该处理器执行该程序时实现上述方法的步骤。

本发明具有的积极效果在于：本发明方法只需知道该系统界面上目标的形状和尺寸，就可以预测该系统界面内用户点击目标时的落点落入目标任意区域的概率，而不需对原有界面的外观进行修改，也不需要用户进行额外的操作；本发明不仅适用于圆形、矩形等规则图形的目标，还适用于任意不规则图形。本发明依赖界面上执行任务时的设备、环境和场景，利用本发明方法粗粒度的预测任意形状目标的点选落点分布更加简单、高效，可以很好地辅助界面设计人员完成开发任务。本发明是对用户的落点区域进行预测，最终给出的反馈是用户点选目标时落入各个区域的概率，与现有技术在各个区域上利用三元高斯模型来得到概率分布以及使用高斯混合模型来将多个概率叠加的复杂计算相比，本发明可以简单地基于各部分的面积和距离关系通过一个公式来计算结果，计算过程简单，易于操作，可以直接应用在实际的场景中。

附图说明

图1为本发明的实施例中任意形状目标切割为多个区域的过程图；

图2为本发明的实施例中区域中心到质心的距离示意图。

具体实施方式

为使本发明的上述特征和优点能更明显易懂，下文将结合附图，对本发明的优选实施例进行详细说明。

本实施提供一种任意形状目标点选落点区域可能性分布预测方法，步骤如下：

1)显示界面内容，选定一个具有任意形状的目标(图形)，获得该目标的质心坐标；

2)通过迭代使用最大内切圆算法将复杂的目标分割为多个内切圆区域的集合；

3)得到目标各个内切圆区域的中心坐标以及半径，计算中心坐标到质心坐标的距离，将该距离和半径信息带入概率函数公式，得到落点落入各个区域的概率。

在步骤1)中，界面内容为一般交互系统显示的内容，本实施例不限定具体内容形式，其中，质心坐标为世界坐标系下的坐标C(c

在步骤2)中，为了实现将目标划分成多个区域的集合的目的，采用Max InscribedCircles算法来获得一个形状的最大内切圆。该算法是一种基于欧几里得距离映射的最大内切圆的算法实现。为了将目标分割成多个基础的图形，首先a)执行Max InscribedCircles算法来获得一个目标的最大内切圆并且将这个圆形作为目标的一个基础图形，b)之后将这个内切圆从目标中切割出来，之后将步骤a)中目标剩余的部分作为一个新的目标。重复上面的步骤直到新目标的面积低于原始目标的20％左右。这个分割目标的过程如图1所示，其中，每一个圆上的数字标号代表了在分割过程中的生成顺序。

在步骤3)中，每一个内切圆区域的半径用ri来表示，区域的中心坐标表示为A(a

d

d

在步骤3)中设计的概率函数与两个形状因子有关。一个与形状有关的元素是步骤2)种划分的区域的面积。通常来说，如果一个区域拥有更大的面积往往意味着有更大的可能性会有更多的落点落在这里，因此，它们的权重也理所当然的应该比其他区域的权重更大一些。另外一个与形状相关的因素是区域的中心到目标质心的距离。根据Grossman等人之前工作的发现，可以将一个形状的多边形质心看作是用户点选该目标时的瞄准中心。同时，之前的研究也发现与点击一个目标的边缘区域相比参加试验的被试者往往更倾向于点击目标的中心区域。基于这些工作，将任意区域的中心到目标质心的距离投影到坐标系X轴和Y轴(即切线和法线方向)上。

因此，提出了如下公式所示的概率函数。利用该公式，只需要带入目标各个区域的半径和到质心的距离就可以得到任意形状目标点选落点区域可能性分布。公式中的分子由三个部分组成：内切圆的面积以及区域的中心到目标的多边形质心之间在x轴和y轴方向上的距离。分母则是一个归一化的过程，这样做的目的是为了确保落点落入各个区域的概率之和为1。

式中，r

经验数据是指，对于任意一个具体的用户显示界面，在未使用本发明方法之前，用户在界面中重复对目标进行选择所得的选择落点数据。经验数据的获取通过一个用户实验完成，其遵循通用的人机交互用户实验步骤及准则，为了便于理解现将其简要描述如下：

i.将界面内容与目标定义和所处空间进行匹配。

ii.根据界面内容，指定一个目标的形状和尺寸作为实验条件。

iii.按照界面的原本形式向N个用户呈现，并要求他们利用原有的界面系统对该条件下的目标反复地选择M次。

iv.按照与该界面匹配的目标和空间的定义，记录所有M次选择落点位置，得到在实验条件下的经验数据。

v.重复上述第ii至iv步，得到其它实验条件下的经验数据。

实验的设计和实施过程需考虑次序效应、学习效应、疲劳程度、用户差异、样本数量等因素的影响，可遵循一般人机交互实验设计原则以消除这些因素的影响。

例如，可根据具体界面目标的大小和形状，选取10个目标半径和3个目标尺寸共10×3＝30个实验条件进行上述实验，用户个数N可为12个，同一条件下一个用户反复选择的次数M可为30次，由此，一个条件下可获得12×30＝360个选择落点，形成由30×360＝10800个选择落点组成的经验数据。

下面给出利用模型拟合上述经验数据从而对模型常数进行估计的步骤：

i.对于一个指定的实验条件(固定的目标尺寸和形状)，根据上述区域划分方法将其划分为多个区域的集合，之后计算落在每个区域的落点数量占用户点击该目标的总落点数的比重并计算每个区域的半径和到目标质心的距离。

ii.对于所有其它实验条件，重复上述步骤i，得到任意条件下在目标任意区域上用户落点的真实比重和概率模型预测的概率。

iii.将所有情况下的目标各个区域落点的真实占比与模型预测概率构造最小均方误差，之后利用梯度下降算法进行优化拟合，得到公式中系数a,b的值(估计值)。

利用这些系数的值代入计算各区域落点概率公式，就可以利用该公式求出任意一个形状的目标划分区域后用户点击目标时落在任意区域的概率。

通过以下实验验证本发明方法的有效性：

整个实验共有12名被试者参与，代码运行在Surface Pro 4上，并且外置一个23.8英寸的AOC的显示器，分辨率为1920×1080，实验所用的鼠标是Dell ms116t。为了测试复杂条件下本发明方法的鲁棒性，本实验包含三个目标尺寸(96、192、384像素)，三个目标速度(96、192、384像素/秒)，以及10个目标形状。每一位被试者为了完成此次实验，需要执行10个形状×3种尺寸×3种速度×10次重复＝900次点击任务。在每一次点击任务中，被试者需要点击界面正中心的开始按钮。之后，一个具有指定形状和尺寸的目标会出现在屏幕中并以指定的速度向一个随机的方向移动。在每一次点击任务中被试者只有一次机会去完成点击，无论其是否击中目标，点击的坐标都会被记录。在整个实验里，会产生12×900＝10800个落点。为了抵消目标速度的影响，当在计算每个区域的落点数量时，会先将所有落点沿着目标速度的方向移动一段距离(落点分布的中心到目标的质心之间的距离)。

相关性分析的结果表明各区域的面积以及该区域的中心与目标质心之间的距离分别在速度的切线和法线方向的距离与该区域上的落点数量具有显著相关性，本发明的概率函数计算出的落点落入每个的区域的概率与该区域上的落点数量也具有显著相关性。区域的面积与落点数量之间的Pearson相关性系数为0.675(p<0.001)，区域中心与目标质心在速度的切线方向的距离d

以上通过形式表达和实施例对本发明方法进行了详细的说明，但本发明的具体实现形式并不局限于此。本领域的一般技术人员，可以在不背离本发明所述方法的精神和原则的情况下对其进行各种显而易见的变化与修改。本发明的保护范围应以权利要求书所述为准。