放置在电容式触摸屏上时区分并跟踪多个对象

摘要

一种用于区分和跟踪放置在触摸屏上的多个对象的算法有五个步骤。步骤S1是从触摸屏上检测到的触摸点的位置中找出候选图案，其中触摸点是在某一时间瞬间检测到的。步骤S2是从步骤S1获得的候选图案中舍弃无效的(即重叠的)候选图案。步骤S3是验证和更新每个识别的图案的几何形状。步骤S4是更新在步骤S3中幸存的识别图案的属性。步骤S5是推测图案的几何形状，并显示对象。在下一个时间瞬间重复步骤S1至S5。在下一个时间瞬间执行步骤S1时，从任何已识别的图案排除候选图案，以减少执行步骤S1所需的计算和存储。

权利要求

1.一种用于区分和跟踪放置在触摸屏上的多个对象的方法，单个对象配置成在所述触摸屏上产生模仿的触摸，该方法包括以下步骤：(a)识别并定位所述对象在时间瞬间在所述触摸屏上的触摸点；

(b)根据所述触摸点的位置找出候选图案，其中，单个候选图案包括三个触摸点，所述三个触摸点形成与一组预定义对象中的已知预定义对象相关的指纹三角形相一致的三角形，所述三个触摸点被视为所述单个候选图案的三个锚点；

(c)根据所述候选图案和所述步骤(a)中识别的所述触摸点的所述位置通过更新过程更新识别图案集，其中，单个识别图案用于指示所述触摸屏上的检测到的对象，并被分配有由所述检测到的对象产生的多个触摸点，分配给所述单个识别图案的所述触摸点包括用于识别所述检测到的对象的三个锚点；以及所述更新过程包括将所述候选图案的子集并入所述识别图案集中，其中，选择所述子集使得在所述子集中，每个锚点均属于一个且仅属于一个候选图案，以避免单个锚点被多个候选图案共享，由此避免由两个或多个物理对象创建单个锚点的无效情况；以及(d)下一个时间瞬间重复处理步骤，其中，所述处理步骤包括所述步骤(a)至所述步骤(c)。

2.根据权利要求1所述的方法，其中，执行所述步骤(d)使得在所述下一个时间瞬间执行所述步骤(b)时，在所述步骤(a)中识别的并与为所述时间瞬间确定的所述识别图案集中的任何分配的触摸点相吻合的任何触摸点被排除在找出所述候选图案的考虑之外，以便在与不了解所述识别图案集的情况下执行相比较时减少所需计算和存储。

3.根据权利要求1所述的方法，其中，所述更新过程还包括：

清除任何无效的识别图案的所述识别图案集，其中，无效的识别图案被定义为没有一个以上的锚点与所述步骤(a)中识别的任何所述触摸点相吻合。

4.根据权利要求3所述的方法，其中，所述更新过程进一步包括：

基于所述单个候选图案的所述三个锚点的位置创建所述单个候选图案的点集，其中，所述点集是代表已知预定义对象的大小和取向的有界区域。

5.根据权利要求4所述的方法，其中，所述有界区域是圆。

6.根据权利要求4所述的方法，其中，所述有界区域是三角形、四边形或多边形。

7.根据权利要求4所述的方法，其中，通过选择过程选定所述子集，该选择过程包括：将所述子集初始化为空集；

依次逐一检验所述候选图案，以确定被检验的候选图案是否无效，其中，无效的候选图案定义为使所述无效的候选图案的任何锚点被所述识别图案集中的任何识别图案或已经包括在所述子集中的任何候选图案共享；以及响应于发现所述被检验的候选图案不是无效的，将所述被检验的候选图案包括到所述子集中。

8.根据权利要求7所述的方法，其中

在依次检验所述候选图案时，所述候选图案按图案重叠程度的升序布置，其中，所述单个候选图案的各自图案重叠程度是通过对三个数字的求和来计算的，每个所述数字是包围所述单个候选图案的单个锚点的各点集的总数。

9.根据权利要求4所述的方法，其中，清除所述识别图案集包括：

通过核查分配给所述单个识别图案的各个触摸点是否是所述步骤(a)中识别的所述触摸点之一并被所述单个识别图案的所述点集所包围，来验证所述各个触摸点；以及响应于发现所述各个触摸点是无效的，将所述各个触摸点从所识别图案中去除。

10.根据权利要求3所述的方法，其中，所述更新过程进一步包括：

确定所述单个识别图案是否不完整，其中，不完整的识别图案被定义为只有两个锚点与所述步骤(a)中识别的所述触摸点吻合，从而所述不完整的识别图案具有缺失的锚点；以及响应于发现所述单个识别图案是不完整的，从其两个吻合的锚点估计所述单个识别图案的所述缺失的锚点的位置，从而使所述单个识别图案被重新分配三个锚点。

11.根据权利要求4所述的方法，其中，所述更新过程进一步包括：

在所述子集并入到所述识别图案集之后以及在清除所述识别图案集之后，根据不同识别图案的各个点集和在所述步骤(a)中识别的、在所述识别图案集中未指定为锚点的剩余触摸点的位置，将所述剩余触摸点分配给所述不同识别图案作为信息点。

12.根据权利要求11所述的方法，其中，所述更新过程进一步包括：在所述剩余的触摸点被分配后，根据通过分配给所述单个识别图案的任何信息点收到的数据，更新所述单个识别图案的属性。

13.根据权利要求3所述的方法，其中，所述更新过程进一步包括：

在所述子集并入到所述识别图案集之后以及在清除所述识别图案集之后，根据所述单个识别图案的所述三个锚点的位置计算或更新所述单个识别图案的几何形状，其中，所述单个识别图案的所述几何形状包括所述触摸屏上所述单个识别图案的参考点和所述单个识别图案相对于所述触摸屏的取向。

14.根据权利要求13所述的方法，还包括以下步骤：

(e)推测所述单个识别图案的轨迹，使追踪所述对象的屏幕图标的各个轨迹能够提前在所述触摸屏上显示，以补偿所述触摸屏的延迟，其中，在所述步骤(d)中，所述处理步骤进一步包括所述步骤(e)。

15.根据权利要求14所述的方法，其中，通过推测过程来推测所述单个识别图案的所述轨迹，该推测过程包括：获得所述单个识别图案在多个不同时间瞬间的各个几何形状的时间序列，其中，所述多个不同时间瞬间包括所述时间瞬间；和使用线性回归技术，基于所述单个识别图案的各个几何形状的所述时间序列估计所述单个识别图案的未来几何形状，从而推测所述单个识别图案的所述轨迹。

16.根据权利要求15所述的方法，其中，所述线性回归技术是基于多项式的线性回归技术。

17.一种设备，包括触摸屏和一个或多个处理器，所述触摸屏能够由所述一个或多个处理器控制，以感测在所述触摸屏上进行的触摸，所述一个或多个处理器配置成根据权利要求1所述的方法执行区分和跟踪放在所述触摸屏上的多个对象的过程，单个对象配置成在所述触摸屏上产生模仿的触摸。

18.一种存储程序的非暂时性计算机可读介质，其中，该程序当在一个或多个处理器上执行时，使所述一个或多个处理器根据权利要求1所述的方法执行用于区分和跟踪放置在触摸屏上的多个对象的过程，单个对象配置成在所述触摸屏上产生模仿的触摸。

说明书

放置在电容式触摸屏上时区分并跟踪多个对象

[0001] 与相关申请的交叉引用

[0002] 本申请要求2019年3月26日提交的美国临时申请第62/823,735号的优先权，该申请的全部公开内容通过引用并入本文中。

技术领域

[0003] 本发明涉及一种区分和跟踪放置在电容式触摸屏上的多个对象的技术，其中每个对象在可由触摸屏检测的选定触摸点处产生多个触摸。

背景技术

[0004] 本公开内容涉及建立在US9,589,161、US9,715,687和US2018/0211071中公开的著作上的新颖的发展。US9,589,161、US9,715,687和US2018/0211071的公开内容通过引用并入本文中。

[0005] 本公开考虑了多个卡/对象放置在电容式触摸屏上的场景。为了图示，图1描述了这种场景的一个实施例。每个对象均都有自己的锚点和信息点的集合。关于锚点和信息点的细节，见US2018/0211071。一般来说，三个锚点集形成三角形或三角形图案。三角形图案可由触摸屏处理器唯一识别，使得处理器可以将识别的图案与已知图案的数据库进行比较，以检测哪个对象与识别的图案相对应。然后，该对象可以被识别。信息点与对象相关联。信息点的出现和消失可以随着时间的推移进行切换，信息点被对象用来将数据信息从对象传送到触摸屏处理器。期望的是基于在触摸屏上激活的触摸点(即由触摸屏检测到的触摸点)的集合，同时识别放置在触摸屏上的所有的卡/对象以及它们的位置和取向。

[0006] 检测和区分触摸屏上的多个卡/对象在游戏和教育玩具方面有巨大的应用，其中此类应用需要或能够将多个对象放在触摸屏上，以增强用户互动体验和新功能。这样的用户体验只有在属于以下类别之一的专门的触摸桌或触摸板上才能实现。

[0007] 1.有摄像头监视桌子的表面区域，以从空中的角度识别对象。

[0008] 2.在屏幕下方嵌入有近场通信(NFC)收发器的网格，游戏物品被贴上NFC标签，以便进行连续的位置检测。

[0009] 3.表面下方有摄像头，仰视并辨识放置在表面上的对象的光学图案。

[0010] 4.在屏幕的边缘上添加红外线传感器网格，从对象的阴影中确定触摸位置。

[0011] 然而，由于在电容式触摸屏之外还需要额外的硬件组件，上述解决方案都不具有成本效益。本领域需要有一种技术，用于检测和区分触摸屏上的多个对象，而不需要在触摸屏之外需要额外的硬件组件。

发明内容

[0012] 本公开提供了一种用于区分和跟踪放置在触摸屏上的多个对象的方法。单个对象配置成在所述触摸屏上产生模仿的触摸。

[0013] 该方法包括步骤(a)至(d)。

[0014] 在步骤(a)中，识别并定位所述对象在时间瞬间在所述触摸屏上的触摸点。

[0015] 在步骤(b)中，根据所述触摸点的位置找出候选图案。单个候选图案包括三个触摸点，这三个触摸点形成与一组预定义对象中的已知预定义对象相关的指纹三角形相一致的三角形。所述三个触摸点被视为所述单个候选图案的三个锚点。

[0016] 在步骤(c)中，根据所述候选图案和所述步骤(a)中识别的所述触摸点的所述位置更新识别图案集。单个识别图案用于指示所述触摸屏上的检测对象，并被分配有由所述检测对象产生的多个触摸点。分配给所述单个识别图案的所述触摸点包括用于识别所述检测对象的三个锚点。特别地，通过更新过程更新所述识别图案集。所述更新过程包括：将候选图案的子集并入所述识别图案集中。选择所述子集使得在所述子集中，每个锚点均属于一个且仅属于一个候选图案，以避免单个锚点被多个候选图案共享。该更新过程还包括清除所述识别的图案集中任何无效的识别图案。无效的识别图案被定义为没有一个以上的锚点与所述步骤(a)中识别的任何所述触摸点相吻合。

[0017] 在步骤(d)中，下一个时间瞬间重复处理步骤。所述处理步骤包括所述步骤(a)至所述步骤(c)。在所述下一个时间瞬间执行所述步骤(b)时，优选且有利地，在所述步骤(a)中识别的并与为所述时间瞬间确定的所述识别图案集中的任何分配的触摸点相吻合的任何触摸点被排除在找出所述候选图案的考虑之外。有利的是，在与不了解所述识别图案集的情况下执行相比较时，减少所需计算和存储。

[0018] 优选地，所述更新过程进一步包括：基于所述单个候选图案的所述三个锚点的位置创建所述单个候选图案的点集。所述点集是代表所述已知预定义对象的大小和取向的有界区域。所述有界区域可以是圆或任何其他形状。所述有界区域也可以是三角形、四边形或多边形。

[0019] 在更新过程中，通过选择过程选定所述候选图案的所述子集。优选地，该选择过程包括：将所述子集初始化为空集；依次逐一检验所述候选图案，以确定被检验的候选图案是否无效；以及响应于发现所述被检验的候选图案不是无效的，将所述被检验的候选图案包括到所述子集中。无效的候选图案定义为使所述无效的候选图案的任何锚点被所述识别图案集中的任何识别图案或已经包括在所述子集中的任何候选图案共享或已经使用。

[0020] 在依次检验所述候选图案时，优选地，所述候选图案按图案重叠程度的升序布置。所述单个候选图案的各自图案重叠程度是通过对三个数字的求和来计算的，每个所述数字是包围所述单个候选图案的单个锚点的各点集的总数。

[0021] 优选地，所述清除所述识别图案集包括：通过核查分配给所述单个识别图案的各个触摸点是否是所述步骤(a)中识别的所述触摸点之一并被所述单个识别图案的所述点集所包围，来验证所述各触摸点；以及响应于发现所述各触摸点是无效的，将所述各触摸点从所述识别的图案中去除。

[0022] 在更新过程中，优选的是确定确定所述单个识别图案是否不完整。不完整的识别图案被定义为只有两个锚点与所述步骤(a)中识别的所述触摸点吻合，从而所述不完整的识别图案具有缺失的锚点。还优选的是，响应于发现所述单个识别图案是不完整的，从其所述两个吻合的锚点估计所述单个识别图案的所述缺失锚点的位置，从而使所述单个识别图案被重新分配三个锚点。

[0023] 在进行所述子集到所述识别图案集的所述并入以及对所述识别图案集的所述清除之后，优选的是，根据所述不同识别图案的各个点集和所述剩余触摸点的位置，更新过程将在所述步骤(a)中识别的、在所述识别图案集中未指定为锚点的剩余触摸点分配给不同的识别图案作为信息点。

[0024] 在所述剩余的触摸点被分配后，优选的是，根据通过分配给所述单个识别图案的任何信息点收到的数据，更新过程更新所述单个识别图案的属性。

[0025] 在进行所述子集到所述识别图案集的所述并入以及对所述识别图案集的所述清除之后，优选的是，更新过程进行根据所述单个识别图案的所述三个锚点的位置计算或更新所述单个识别图案的几何形状。所述单个识别图案的所述几何形状包括所述触摸屏上所述单个识别图案的参考点和所述单个识别图案相对于所述触摸屏的取向。

[0026] 可选地，所述的方法还包括步骤(e)。在步骤(e)中，推测所述单个识别图案的轨迹，使追踪所述对象的屏幕图标的各个轨迹可提前在所述触摸屏上显示，以补偿所述触摸屏的延迟。在所述步骤(d)中，所述处理步骤进一步包括所述步骤(e)。

[0027] 通过推测过程可以推测所述单个识别图案的所述轨迹。在该推测过程中，获得所述单个识别图案在多个不同时间瞬间的各几何形状的时间序列。所述多个不同时间瞬间包括所述时间瞬间。然后，使用线性回归技术，基于所述单个识别图案的各几何形状的所述时间序列估计所述单个识别图案的未来几何形状，从而推测所述单个识别图案的所述轨迹。所述线性回归技术可以是基于多项式的线性回归技术。

[0028] 本公开还提供一种设备，包括触摸屏和一个或多个处理器。所述触摸屏可由所述一个或多个处理器控制，以感测在所述触摸屏上进行的触摸。所述一个或多个处理器配置成根据所述方法的任一实施方式执行区分和跟踪放在所述触摸屏上的多个对象的过程，其中单个对象配置成在所述触摸屏上产生模仿的触摸。

[0029] 此外，本公开提供一种存储程序的非暂时性计算机可读介质。该程序当在一个或多个处理器上执行时，使所述一个或多个处理器根据所述方法的任一实施方式执行用于区分和跟踪放置在触摸屏上的多个对象的过程，其中单个对象配置成在所述触摸屏上产生模仿的触摸。

[0030] 本公开内容的其他方面被公开，如以下实施方式所说明的。

附图说明

[0031] 图1是放置在计算装置的触摸屏上的多个对象的照片，示出用户可以通过将对象放置在触摸屏上特别选定的位置来与计算装置互动。

[0032] 图2描绘了一个流程图，示出了用于示例性地说明用于区分和跟踪放置在触摸屏上的多个对象的公开方法的算法的流程。

[0033] 图3描绘了通过进行算法的步骤S1从多个触摸点创建多个候选图案的实例。

[0034] 图4描绘了在进行步骤S2.1之后创建的点集(示出为圆)，示出了圆的重叠存在，其中重叠的圆被认为是无效的圆并应被舍弃。

[0035] 图5描绘了在算法的整个步骤S2完成后的多个识别的图案，示出任何重叠的圆被去除。

[0036] 图6描绘了通过进行算法的步骤S5来图解地示出预测触摸屏上的识别图案的移动的实例。

[0037] 图7描绘了在所公开的方法中使用的示例性处理步骤的流程。

[0038] 图8描绘了一个流程图，示出根据所公开的方法的某些实施方式的用于更新识别图案集的更新过程的示例性步骤。

[0039] 图9描绘了根据所公开的方法的某些实施方式的用于选择要并入识别图案集的候选图案的选择过程的示例性步骤。

[0040] 图10描绘了根据所公开的方法的某些实施方式的用于推测每个识别的图案的轨迹的示例性步骤。

[0041] 图11描绘了用于实施所公开的方法的设备，其中该设备包括触摸屏以及一个或多个处理器。

具体实施方式

[0042] 本文提供一种用于区分放置在电容式触摸屏上的多个对象并跟踪触摸屏上的对象的方法。该方法首先描述一种计算机实施的算法，用于区分和跟踪放置在触摸屏上的对象。该算法是所公开方法的一个示例性实施方式的实际实现。该方法的细节通过对所公开的算法的概括而进一步详尽阐述。

[0043] 本文使用的系统模型和变量描述如下。设M是在任何时间瞬间在屏幕上激活的触摸点的数量。也就是说，在上述的时间瞬间，屏幕上检测到M个触摸点。期望确定放置在屏幕上的对象的数量，并根据触摸屏处理器检测到的激活的触摸点来区分这些对象。设N为放置在屏幕上的对象的实际数量。由于一个对象包含三个锚点，并可能包括一个或多个信息点，因此，N的上限为M/3。即，N≤M/3。将P表示为对象图案(或简称为图案)，它是代表对象O的点的集合。设{a1,a2,a3}为P的锚点。设{A1,A2,A3}为P的锚点三角形，其中锚点三角形是唯一的预定义形状，使得P中除了{a1,a2,a3}之外没有其他3个点能够形成与{A1,A2,A3}所形成的三角形一致的三角形。即，

[0044] 以及r＝a3

[0045] 其中，△pqr代表由触摸屏上的三点p、q和r组成的三角形；并且 意味着"一致"。P的锚点三角形也被命名为指纹三角形，因为指纹三角形与所代表的对象O有关，因此对对象识别有用。设{x,y,θ}为P的几何形状，其中(x,y)是P在屏幕上的某个预定参考点的位置，而θ是P相对于屏幕的取向。方便的是，预先确定的参考点可以是P的某个锚点。取向θ可以定义为绕参考点(x,y)从屏幕的水平轴线到连接参考点的△a1a2a3最长边的旋转角度。在一个实际的选择中，a1、a2和a3可能以逆时针的方式布置，边a1a2是△a1a2a3的最长边。参考点(x,y)可以选择为a1，这样就可以根据边a1a2和屏幕的水平轴线来确定取向θ。△a1a2a3的锚点位置可用于计算{x,y,θ}，这就是所代表的对象O的几何形状。注意，为了独特、明确地确定几何形状，要求指纹三角形的三个边相互不同。因此，对象O的指纹三角形不得是等腰三角形或等边三角形。

[0046] 借助图2来说明所公开的算法，图2描绘了该算法的流程。如图2所示，该算法作为一个循环被执行，其中该循环包括操作步骤的序列。该操作步骤序列是针对屏幕在一个时间瞬间检测到的M个触摸点的集合执行的。通过以循环方式执行该算法，操作步骤的序列被重复用于在连续的时间瞬间获得的触摸点的集合。由于新的对象可能被放在屏幕上或从屏幕上移走，所以在不同的时间瞬间获得的触摸点数量很可能是不同的。此外，偶尔也会发生触摸屏电子/处理器对实际上不存在的触摸点的错误检测(即假阳性)。在执行处理步骤的序列结束时，会得到识别的图案集。每个被识别的图案均包括与图案有关的数据，如图案的几何形状。通过每次用新的检测到的触摸点集递归地重复操作步骤序列，来更新识别的图案集。该算法包括步骤S1至S5。

[0047] 在步骤S1中，要从M个检测到的触摸点中找出候选图案。示例性地，步骤S1由以下伪码说明。

[0048] S1.1.对于屏幕上的三个触摸点{p1,p2,p3}的每一组，如果这三个触摸点还没有被分配到任何图案，则：

[0049] S1.1.1.如果 那么：

[0050] S1.1.1.1.创建候选图案P′i；

[0051] S1.1.1.2.设定P′i，p2＝a2i和p3＝a3i。

[0052] 实际上，屏幕在分辨不同的触摸点方面具有有限的分辨率。因此，触摸点的位置是估计的位置，并且可能与实际位置有一点偏差。在实施步骤S1.1.1中，在评估△p1p2p3是否与△A1A2A3一致时，期望能考虑到屏幕的有限分辨率。例如，如果边pmpn和边AmAn之间的长度百分比误差小于(m,n)＝(1,2)，(1,3)和(2,3)的可容忍误差，则△p1p2p3可以被确定为与△A1A2A3一致。该可容忍误差可以是例如10％。

[0053] 注意，为了确定△p1 p2 p3是否与△A1 A2 A3一致，需要有屏幕分辨率的知识。在不知道屏幕分辨率或屏幕尺寸的情况下，识别与△A1A2A3相似的、缩放系数在预定的小范围内的三角形△p1p2p3。然后假定△p1p2p3与△A1A2A3一致，从而创建候选图案。△p1p2p3是否真的与△A1A2A3一致，将在稍后阶段用诸如分配给候选图案的信息点的位置等辅助信息进行验证。

[0054] 作为执行步骤S1的结果，形成N'个候选图案，其中N'≥N。这N'个候选图案将在后续步骤中被单独评估，以找出N'个候选图案中的哪N个属于屏幕上的实际对象。

[0055] 图3描绘了通过进行步骤S1从多个触摸点创建多个候选图案的实例。请注意，一个触摸点可能被不同的图案共享，导致重叠的图案。重叠的图案显然是无效的；否则，屏幕上的一个触摸点会被至少两个物理对象所创建。需要在后续步骤中去除重叠的图案。

[0056] 在步骤S2中，要从N'个候选图案中舍弃无效的(即，重叠的)候选图案。示例性地，，借助图4和图5，步骤S2由以下伪代码说明。

[0057] S2.1.对于每个候选图案P′i，进行：

[0058] S2.1.1.创建点集Ci，代表图案P′i的圆；

[0059] S2.2.对于每个候选图案P′i，进行：

[0060] S2 .2.1 .设Si是由以下包围P ′i的锚点的圆的数量总和，即其中|.|代表"数量"；

[0061] S2.3.将候选图案按Si的升序排序；

[0062] S2.4.对于按照Si的升序布置的每一个候选图案P′i，进行：

[0063] S2.4.1.如果{a1,a2,a3}i中的所有点都没有被分配到任何已识别的图案，那么：

[0064] S2.4.1.1.创建识别图案Pi；

[0065] S2.4.1.2.将{a1,a2,a3}i分配给Pi；

[0066] S2.4.2.否则：

[0067] S2.4.2.1.舍弃Pi。

[0068] 在步骤S2.1.1中，Ci被创建为相对于P′i的锚点具有预定大小和位置的圆。由于图案在实践中与物理对象相关联，并且由于对象的边界和尺寸是已知的，因此可以确定圆Ci的大小。例如，可以将Ci设定为直径为5厘米的圆，圆心选为P′i的第一和第二锚点之间的中点。圆只是有界区域的一个实施方案，它代表了已知的预定义对象的大小和取向。除了圆之外，用于Ci的有界区域的其他实现方式包括矩形、三角形、四边形、多边形等等。

[0069] 在步骤S2.3中，首先将所有N'个候选图案按Si的升序布置。然后通过步骤S2.4.1(包括S2.4.1.1和S2.4.1.2)和S2.4.2(包括S2.4.2.1)对布置好的N'个候选图案的序列进行逐一处理。

[0070] 上述列出的程序的优点在于，确保了要识别的非重叠图案的最大数量。图4描绘了在进行步骤S2.1(包括步骤S2.1.1)之后创建的点集(示为圆)。请注意，圆的重叠是存在的。图5描绘了在步骤S2完成后的多个识别图案，该图示出任何重叠的圆被去除。

[0071] 在步骤S3中，是验证和更新每个识别的图案的几何形状。示例性地，该步骤S3由以下伪代码说明。

[0072] S3.1.对于每个已识别的图案Pi，进行：

[0073] S3.1.1.对于每个被分配给Pi的触摸点，进行：

[0074] S3.1.1.1.如果所考虑的触摸点不存在或不被Ci所包围，那么：

[0075] S3.1.1.1.1.从Pi中去除所考虑的触摸点；

[0076] S3.2.对于每一个已识别的图案Pi，进行：

[0077] S3.2.1.如果不存在{a1,a2,a3}i的触摸点或只存在{a1,a2,a3}i中的一个触摸点，那么：

[0078] S3.2.1.1.舍弃Pi；

[0079] S3.2.2.否则

[0080] S3.2.2.1.如果只有{a1,a2,a3}i中的2个存在，那么：

[0081] S3.2.2.1.1.用现有的2个锚点预测错过的锚点的位置；

[0082] S3.2.2.2.如果 那么：

[0083] S3.2.2.2.1.舍弃Pi；

[0084] S3.2.2.3.否则

[0085] S3.2.2.3.1.更新{x,y,θ}i和Ci。

[0086] 在步骤S3.1.1.1中，“所考虑的触摸点不存在”意味着从当前考虑的M个检测的触摸点(由屏幕检测)中找不到分配给Pi的该触摸点。

[0087] 在步骤S3.2.2.2中， 表示"不一致"。

[0088] 上述列出的程序的结果是消除任何没有足够的锚点来确定其代表对象的几何形状的识别图案，或者发现是在步骤S2中创建的假阳性结果。

[0089] 在步骤S4中，更新在步骤S3中幸存的识别图案的属性。示例性地，该步骤S4由以下伪代码说明。

[0090] S4.1.对于未被分配到任何图案的每个检测到的触摸点Pk，进行：

[0091] S4.1.1.如果Pk被任何Ci所包围，那么：

[0092] S4.1.1.1.将Pk分配给Pi；

[0093] S4.1.2.如果Pi缺少1个锚点，并且 那么：

[0094] S4.1.2.1.设定Pk为遗漏的锚点；

[0095] S4.1.3.否则

[0096] S4.1.3.1.设定Pk为Pi的信息点。

[0097] S4.2.对于每一个已识别的图案Pi，进行：

[0098] S4.2.1.根据其信息点更新其属性(例如，ID)。

[0099] 图案的属性可用于识别哪个物理对象被放置在屏幕上，并且可提供不同的用户界面(UI)响应。

[0100] 在步骤S4.1完成时，已识别的图案集已经被更新。

[0101] 在步骤S5中，推测图案的几何形状，并显示对象。为方便起见，在不丧失一般性的情况下，考虑当前的时间瞬间为零。让以前的时间瞬间为ΔT‑1、ΔT‑2等。示例性地，步骤S5由以下伪代码说明。

[0102] S5.1.对于每一个识别的图案Pi，进行：

[0103] S5.1.1.找到Pi的时间序列，以及相应的几何图形 其中T＝{ΔT‑t+1,ΔT‑t+2,…,ΔT‑1,0}，并且t为时间序列的最大样本量。

[0104] S5.1.2.以T为预测因子，以 为响应因子，进行基于多项式的线性回归分析，即

[0105] S5.1.3.估计 其中ΔTj是未来的时间瞬间；

[0106] S5.1.4.在触摸屏上显示对象Oi的视觉通知，几何形状为

[0107] 在步骤S5.1.2中，能够使用其他线性回归技术。

[0108] 以预测的未来几何形状显示对象能够补偿触摸屏的延迟，从而创建更多的响应性输出。图6提供了用于图解上述程序的实例。

[0109] 本公开的一个方面是提供一种用于区分和跟踪放置在电容式触摸屏上的多个对象的方法。该方法是上述算法的一般化。单独的对象配置成在触摸屏上产生模仿的触摸，并且触摸屏配置成感应模仿的触摸。确定触摸屏上的对象的各个位置和取向。此外，这些对象被跟踪，从而预测单个对象的未来位置和取向。预测的位置和取向对于实际应用是有用的，在该应用中，例如，打算通过一些视觉动画提前显示跟随单个对象的屏幕图标。

[0110] 示例性地，借助于图7来说明该方法。图7描绘了在所公开的方法中使用的示例性处理步骤的流程。

[0111] 在步骤710中，识别并定位对象在触摸屏上的时间瞬间所做的触摸点。为方便起见，在不丧失一般性的情况下，该时间瞬间被称为当前时间瞬间。

[0112] 然后在步骤720中确定候选图案。特别是，候选图案是根据在步骤710中确定的触摸点的位置创建和确定的。单独的候选图案包括形成与一组预定义对象中的已知预定义对象相关的指纹三角形一致的三角形的触摸点中的三个。上述触摸点中的三个被认为是单个候选图案的三个锚点。该步骤720可由算法的步骤S1实现。

[0113] 在确定了候选图案之后，在步骤730中根据候选图案和在步骤710中识别的触摸点的位置更新识别图案集。单独的识别图案用于指示触摸屏上的检测到的对象，并被分配由检测到的对象产生的多个触摸点。分配给单个识别图案的触摸点包括用于识别检测对象的三个锚点。

[0114] 特别地，通过更新过程更新识别图案集。该更新过程至少布置成将候选图案的子集并入识别图案集(步骤731)，并且清除无效的任何识别图案的识别图案集(步骤732)。进行候选图案子集的选择，使得在该子集中，每个锚点均属于一个且仅属于一个候选图案，以避免单个锚点被多个候选图案共享或使用。一无效的识别图案被定义为具有不超过一个锚点与步骤710中识别的任何触摸点吻合。该步骤730可借助算法的步骤S2和S3实现，并可选地借助其步骤S4实现。

[0115] 通过上述标准定义无效的识别图案的合理性如下。如果分配给单个识别图案的锚点没有与在步骤710中识别的任何检测到的触摸点吻合，则几乎可以肯定与单个识别图案相关的对象已经从其先前检测到的位置移开。如果只有一个这样的锚点，那么也很有可能该对象已经从先前检测到的位置上移开了。然而，如果有两个分配的锚点与步骤710中识别的一些检测到的触摸点吻合，那么很可能剩下的分配的锚点没有被成功检测到，所以对象实际上没有被移走。如果对象已经从其先前记录的位置移开，则与该对象相关的单个识别图案已经过时，应从识别图案集中去除。反之，如果对象在先前记录的位置上仍然完好无损，则该单个识别图案仍然是有信息的，可以保留在识别图案集中。

[0116] 在步骤750中，对于下一个时间瞬间重复步骤710、720和730。在为下一时间瞬间进行步骤720时，更优选的是，在步骤710中识别的、与为当前时间瞬间确定的识别图案集中的任何分配触摸点吻合的任何触摸点在找出候选图案时不被考虑。有利的是，与在不知道识别图案集的情况下执行步骤720相比，使得所需计算和存储的减少。在算法的步骤S1.1中也实施排除已经分配给任何识别图案的触摸点。

[0117] 这种减少计算和存储的意义和优势进一步详尽阐述如下。首先注意到，放置在触摸屏上的每个对象均具有三个锚点，并且可能还有一个或多个信息点。此外，多个对象被放置在触摸屏上。在步骤710中可以检测到大量的触摸点。由于需要检查由三个检测到的触摸点形成的每个三角形，因此要测试的三角形数量是巨大的。为了说明问题，考虑这样一个实例的情况：每个对象产生4个触摸点。如果触摸屏上有两个对象，则需要测试的三角形数量为8！/(5！×3！)＝56。同样地，如果触摸屏上有三个和四个对象，要测试的三角形数量分别为12！/(9！×3！)＝220和16！/(13！×3！)＝560。随着放置在触摸屏上的对象数量的增加，需要测试的三角形数量急剧增加，而且几乎呈指数增长。这严重地加重了进行区分不同对象的计算的计算装置(例如平板电脑)的负担。另一方面，如果在找出候选图案时不考虑已经分配好的触摸点，那么计算量就会大大减少。考虑一个典型的实例，即在触摸感应的连续时间瞬间内，只移动放置在触摸屏上的一个对象。要测试的三角形数量只有4！/(1！×3！)＝4，而不考虑放在触摸屏上的对象数量。所需计算和存储的显著减少使得可以在典型的计算装置上实际实施区分和跟踪触摸屏上的多个对象。

[0118] 下面借助图8进一步说明步骤730中使用的更新过程。图8描绘了示出更新过程在更新识别的图案集时采取的示例性步骤的流程图。

[0119] 在步骤810中，基于单个候选图案的三个锚点的位置创建单个候选图案的点集。该点集是代表已知预定对象的大小和取向的有界区域。该步骤810可由算法的步骤S2.1实现。

[0120] 有界区域可以根据已知预定义对象的形状来塑造。例如，有界区域可以被塑造为圆形、矩形、三角形、四边形、多边形等。方便的是，有界区域优选设定为圆，因为只需要两个参数(即圆的中心和半径)就可以指定圆。由于三个锚点的位置和已知预设对象的边界是已知的，因此一般来说，圆的中心和半径很容易确定。本领域的技术人员也可以在对象的中心和三个锚点集合之间有约束的情况下，在预定义对象的集合中设计每个对象。约束的一个实例是，对象的中心与三个锚点形成的指纹三角形的中心点吻合。另一个实例是，对象的中心与指纹三角形最长边的中点吻合。

[0121] 在步骤820中，通过选择过程选定候选图案的子集。这些步骤可由算法的步骤S2.2‑S2.4实现。图9描绘了选择过程的示例性步骤。在选择过程中，通过逐一检验候选图案，子集逐渐被添加到可接受的候选图案中。最初，子集被初始化为空集，即空的集合(步骤910)。依次逐一检验候选图案，以确定被检验的候选图案是否无效，据此，如果发现被检验的候选图案不是无效的，则将其并入子集(步骤915)。定义无效的候选图案，使得无效的候选图案的任何锚点被识别图案集中的任何识别图案或被已经包括在子集中的任何候选图案所共享，或已经被识别图案集中的任何识别图案或被已经包括在子集中的任何候选图案使用。这种定义背后的合理性在于，有效的候选图案要被包括到已识别图案的集合中，并且不同的已识别图案是不重叠的。

[0122] 步骤915可以实施如下。首先将候选图案按照图案重叠程度的升序布置(步骤920)。通过将三个数字相加来计算单个候选图案的各自的图案重叠程度。这三个数字中的每一个均是由包围单个候选图案的单个锚点的各个点集的总数给出的。候选图案按照上述的升序逐一被检验。如果被检验的候选图案不是无效的(步骤930)，则被检验的候选图案被添加到子集中(步骤935)，这样子集被扩大。如果被检验的候选图案被发现是无效的(步骤
930)，则该候选图案被舍弃(步骤936)，不被添加到子集中。步骤930和条件步骤935、936重复进行，直到所有的候选图案都被检验(步骤940)。步骤920可由算法的步骤2.2和2.3实现。
步骤935和936可分别由算法的步骤2.4.1和2.4.2实现。如上所述，通过步骤920对候选图案进行排序，其优点是确保识别出最大数量的非重叠图案。

[0123] 在步骤820中获得候选图案的子集后，在步骤825中将候选图案的子集并入已识别的图案集中。

[0124] 在步骤830中，通过验证所考虑的触摸点是否是在步骤710中识别的触摸点之一并且被单个识别的图案的点集所包围来验证分配给单个识别的图案的每个触摸点。如果考虑中的触摸点与步骤710中识别的一个触摸点相吻合并且也被点集合所包围，则该触摸点是有效的。如果所考虑的触摸点被发现是无效的，那么这个触摸点就会从单个识别的图案中去除。该步骤830可由算法的步骤S3.1实现。

[0125] 在步骤832中，找出识别图案集中的任何无效的识别图案。如上所述，无效的识别图案没有或只有一个分配的锚点与步骤710中识别的触摸点相吻合。根据步骤832的发现，在步骤835中去除识别图案集中的任何无效的识别图案，以便清除识别图案集。步骤832和835可由算法的步骤S3.2.1(包括S3.2.1.1)共同实现。

[0126] 将候选图案的子集并入识别图案集的步骤731包括步骤820和825。清除识别图案集中任何无效的识别图案的步骤732包括步骤830、832和835。尽管在图8中为说明目的示出步骤731在执行顺序上先于步骤732，但可以使用其他执行顺序，因为在执行步骤731时新引入识别图案集的识别图案已经是有效的，而步骤732旨在仅去除无效的识别图案。由此可见，步骤732可以在步骤731之前执行。

[0127] 优选地，更新过程进一步包括找出并修复识别图案集中任何不完整的识别候选的步骤850。不完整的识别图案被定义为只有两个锚点与步骤710中识别的触摸点吻合。注意，不完整的识别图案具有缺失的锚点。当发现单个识别图案不完整时，通过从两个吻合的锚点(即，与步骤710中识别的触摸点吻合的上述单个识别图案的两个锚点)估计缺失的锚点的位置，对其进行修复。修复后的单个识别图案被重新分配为三个锚点。该步骤850可由算法的步骤S3.2.2.1实现。

[0128] 优选的是，更新过程进一步包括计算或更新识别图案集中的单个识别图案的几何形状的步骤860。该步骤860在进行步骤731和732之后被执行。根据单个识别图案的三个锚点的位置来计算或更新几何形状。如上所述，单个识别图案的几何形状包括触摸屏上单个识别图案的参考点和单个识别图案相对于触摸屏的取向。该步骤860可由算法的步骤S3.2.2.3.1实现。

[0129] 在进行步骤731和732之后，优选的是根据不同识别的图案的各个点集和剩余触摸点的位置，将在步骤710中识别的并且在识别的图案集中未被指定为锚点的剩余触摸点分配给不同识别的图案作为信息点(步骤870)。该步骤870可由算法的步骤S4.1实现。

[0130] 在步骤870中分配了剩余的触摸点之后，优选根据通过分配给单个识别图案的任何信息点接收的数据更新单个识别图案的属性(步骤875)。单个属性可以是从一个或多个分配的信息点所传达的任何类型的信息。该步骤875可由算法的步骤S4.2实现。

[0131] 请参考图7。可选地，在步骤740中推测单个识别的图案的轨迹，从而跟踪对象的屏幕图标的各自轨迹可提前在触摸屏上显示，以补偿触摸屏的延迟。该步骤740可由该算法的步骤S5实现。在步骤750中，该步骤740也被重复用于下一个时间瞬间。

[0132] 图10描绘了实现步骤740的示例性步骤。在通过步骤740推测轨迹时，在多个不同的时间瞬时(步骤1010)获得单个识别图案的各自几何形状的时间序列。该多个不同的时间瞬间包括现在的时间瞬间。基于单个识别图案的各自几何形状的时间序列，使用线性回归技术来估计单个识别图案的未来几何形状(步骤1020)。通过估计未来的几何形状，推测单个识别图案的轨迹。该线性回归技术可以是基于多项式的线性回归技术。

[0133] 所公开的方法可在包括触摸屏的计算机系统上实施。在本公开的一些实施方式中，计算机系统被实现为单一的计算装置。在某些实际应用中，该计算装置被实施为移动计算装置，如平板电脑。图11描绘了用于实施所公开方法的设备1100。该设备1100包括触摸屏1110和一个或多个处理器1120。触摸屏1110可由一个或多个处理器1120控制。由此可见，一个或多个处理器1120可操作以配置触摸屏1110以感知对象的触摸，并在完成所公开的方法的步骤710中识别和定位对象。此外，一个或多个处理器1120配置为根据所公开的方法的任何实施方式执行用于区分和跟踪放置在触摸屏1110上的多个对象的过程。

[0134] 一个或多个处理器1120可以是或可以包括触摸屏处理器，其是集成到触摸屏1110的处理器。单个处理器可以由微控制器、通用处理器或特殊用途处理器(例如特定应用集成电路(ASIC)或数字信号处理器(DSP))实现，或者由可重新配置的逻辑器件(例如现场可编程门阵列(FPGA))实现。

[0135] 所公开的方法的每个实施方式均可以通过对一个或多个处理器1120进行编程而在设备1100中实施。产生的程序使一个或多个处理器1120执行上述用于区分和跟踪多个对象的过程。该程序可以存储在非临时性计算机可读介质中，例如光盘。

[0136] 本发明可以在不背离其精神或基本特征的情况下以其他具体形式体现。因此，本发明的实施方式在所有方面都应被视为说明性的，而不是限制性的。本发明的范围由所附的权利要求而不是由前述描述表示，因此在权利要求的含义和等效范围内的所有变化都理应被包含在本发明中。