(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210306414.1 (22)申请日 2022.03.25 (71)申请人 中国科学院软件研究所 地址 100190 北京市海淀区中关村南四街 4 号 (72)发明人 田丰　张子悦　黄进　王宏安　 (74)专利代理 机构 北京君尚知识产权代理有限 公司 11200 专利代理师 李文涛 (51)Int.Cl. G06T 7/11(2017.01) G06F 17/18(2006.01) G06F 9/451(2018.01) (54)发明名称 任意形状目标点选落点区域可能性分布预 测方法及系统 (57)摘要 本发明提出一种任意形状目标点选落点区 域可能性分布预测方法及系统， 属于计算机图形 用户界面领域， 在显示的界面内容上选择一个具 有任意形状的目标， 获得该目标的质 心坐标； 利 用多边形最大内切圆算法在目标中寻找最大内 切圆， 再将该最大内切圆从原目标中切割出来， 迭代实现将目标划分成多个内切圆区域； 获取各 个内切圆区域的中心坐标以及半径， 计算出用户 点击目标时落入 各个内切圆区域的概率。 本发明 针对平面上的复杂多边形目标选择任务， 通过切 割最大内切圆来划分区域， 计算区域中心面积和 到目标质心的距离， 预测出落点落入任意区域的 可能性分布， 预测更加简单、 高效。 权利要求书1页 说明书6页 附图1页 CN 114842023 A 2022.08.02 CN 114842023 A 1.一种任意形状目标点选落 点区域可能性分布预测方法， 其特 征在于， 步骤 包括： 在显示的界面内容上选择一个具有任意形状的目标， 获得 该目标的质心坐标； 利用多边形最大内切圆算法在目标中寻找最大内切圆， 再将该最大内切圆从原目标中 切割出来， 之后在剩余的图形中寻找 最大内切圆并从图形中切割出来， 按此迭代进 行， 实现 将目标划分成多个内切圆 区域； 获取各个 内切圆区域的中心坐标以及 半径， 根据 该中心坐标和所述质心坐标计算各个 内切圆区域的中心到质心的距离， 根据内切圆区域的半径和中心到质心的距离计算出用户 点击目标时落入各个内切圆 区域的概 率。 2.如权利要求1所述的方法， 其特 征在于， 目标的质心坐标为世界坐标系下的坐标。 3.如权利 要求1所述的方法， 其特征在于， 多边形最大内切圆算法为ImageJ中所采用的 Max Inscribed Circles算法。 4.如权利要求1所述的方法， 其特征在于， 在剩余的图形中寻找最大内切圆并从图形中 切割出来， 按此迭代进行， 直到所剩图形的面积不足原目标图像面积的20％。 5.如权利要求1所述的方法， 其特征在于， 内切圆区域的中心到质心的距离包括内切圆 区域的中心到质心之间在切线和法线方向上的距离 。 6.如权利要求5所述的方法， 其特征在于， 计算用户点击目标时落入各个 内切圆区域的 概率pi的公式为： 式中， ri表示内切圆区域的半径， dt,i和dn,i分别表示内切圆区域的中心 到质心之间在切 线和法线方向上的距离； C是归一化常数， 其中K表示内 切圆区域的数量， c1,c2,c3是常参数； 7.如权利要求6所述的方法， 其特 征在于， 系数a,b根据经验数据拟合得到， 步骤 包括： 指定目标 大小和形状作为实验条件； 将初始显示界面呈现给用户， 记录用户多次选择落点位置数据， 作为该实验条件下的 经验数据， 重复获取多个实验条件下的经验数据； 记录目标的各个内切圆区域上真实的用户落点数量所占用户点击该目标的总落点数 量的比值； 将各个内切圆区域上真实的用户落点数量比值与公式计算得到的预测概率构造最小 均方误差， 再利用梯度下降算法对数据进行优化拟合， 得到系数a,b的值。 8.一种任意形状目标点选落点区域可能性分布预测系统， 其特征在于， 包括存储器和 处理器， 在该存储器上存储有计算机程序， 该 处理器执行该程序时实现权利要求 1‑7任一项 所述方法的步骤。权　利　要　求　书 1/1 页 2 CN 114842023 A 2任意形状目标点选落点区域可能性分布预测方 法及系统 技术领域 [0001]本发明属于计算机图形用户界面领域， 具体涉及图形用户界面中针对任意形状目 标点选落 点区域可能性分布预测方法及系统。 背景技术 [0002]随着大型网络游戏、 增强和虚拟现实系统等应用的普及， 需要用户进行点选目标 的场景变得越来越多， 例如第一人称视角的射击类游戏、 元宇宙中的交互等等。 同时 随着计 算机图形学、 动画设计等领域的发展进步， 用户的画 面已经不再是简单的矩形、 圆形等基本 图形的罗列， 而是由各种各样不规则的复杂形状所组成。 例如在射击类游戏中， 不同的用户 角色往往对应着不同的不规则的外部轮廓。 在上述这些场景中， 目标 的尺寸以及形状因素 都会对用户进 行目标选择任务时的落点分布有着很大的影响。 因此为了辅助界面设计人员 的工作， 需要一种简洁明了的任意形状目标的用户点选落 点分布预测方法。 [0003]在真实的交互场景中， 被选择的目标往往在两个维度上都存在有界尺寸。 因此， 很 多研究探讨了二维目标形状对用户点选目标时的表现的影响。 MacKenzie和Buxton两人考 虑到用户点击目标时靠近目标的角度的不同对目标的宽度提出了五种表示方法， 从而将本 来只适合于一维的目标选取任务的菲兹定律拓展到了二维空间中(参考文献： MacKenzie, S.and Buxton,W.(1992).Extending  Fitts'law  to two‑dimensional  tasks.ACM  CHI  Conference  on Human Factors in Computing  Systems.p.219 ‑226.)。 更进一步地， A ccot 等人发现对于一个固定大小的二维目标来说， 目标对用户在进行选择操作时的幅度约束W 和方向约束H有着不一样的影响效果， 而且 幅度约束W相较于方向约束H要更加占据主导地 位。 因此他们提出了一个带有自由权重系数 η 的欧几里得模型来平衡这两种不同的影响(参 考文献： Johnny  Accot and Shumin Zhai.2003.Refining  Fitts'law  models for  bivariate  pointing.In  Proceedings  of the SIGCHI Conference  on Human Factors  in Computing Systems(CHI'03).193‑200.)。 [0004]需要特别强调的一点是上面提到的这些工作的研究重点基本上都集中在点击矩 形目标的任务上。 然而随着近些年计算机图形界面的发展， 在当前 的用户界面中点击具有 任意不规则形状的目标已经变得非常常见。 S heikh等人在关于菲兹定律的研究中发现目标 的形状对于用户选择目标的移动时间有着显著的影响。 他们通过利用二 维正态分布和一个 “cookie‑cutter”方法来估计目标的形状并且显著提高了菲兹定律对于不同形状的目标的 用户点选时间预测的准确度(参考文献： Sheikh,I.H.,&Hoffmann,E.R.(1994).Effect  of  target shape on movement  time in a Fitts task.Ergonomics,37(9),1533 ‑1547)。 在 另外一个值得注 意的研究中， Tovi  Grossman等人提出了一个基于概率的菲兹定律模 型， 在 静态的目标选择任务中这个模型可以比较准确的预测出用户点击大量非矩形的目标时的 所需要的移动时间。 该基于概率的菲兹定律模型的核心思想是将开环运动中击中目标的概 率映射到原始菲兹定律的难度值指标(参考文献： Tovi  Grossman,Nicholas  Kong,and   Ravin Balakrishnan.2007.Modeling  pointing  at targets of arbitrary  shapes.In  说　明　书 1/6 页 3 CN 114842023 A 3