基于预测的触摸接触跟踪

摘要

在基于预测的触摸接触跟踪的实施例中，将触摸输入传感器数据辨识为触摸屏显示器上接触的一系列分量。可以识别接触的第一分量，且可以确定第二分量与接触相关。可以随后使第一分量和第二分量相关联以表示接触的跟踪。接触的后续分量可以被确定和与接触的先前分量相关联以进一步表示接触的跟踪。

说明书

相关申请

本申请要求Zhao等人2011年2月12日提交的题为“Prediction-Based Touch Contact Tracking”的美国临时申请序列号61/442,222的优先权，其公开内容整体经引用并入本文。

背景技术

便携式运算设备（如，移动电话、便携式和平板计算机、娱乐设备、手持导航设备等）越来越多地提供可以使得用户难以导航和选择与用户想要在设备上发起的功能有关的命令的较多功能和特征。除了用来与运算设备交互的传统技术（如，鼠标、键盘、以及其它输入设备）之外，通常在移动电话和平板计算机中集成、以及对于显示和用户可选择触摸和姿态输入均运用触摸传感器和触摸屏显示器。对于具有触摸传感器和/或触摸屏显示器的这些类型便携式设备的连续设计挑战是用以跟踪根据传感器图像数据的持续帧识别的触摸和姿态输入的触摸信号处理。触摸屏显示器上的触摸接触表示姿态的运动轨迹，如，当用户使用他或她的手指触及触摸屏显示器时和维持与显示器接触时的姿态。不能正确跟踪和解释姿态输入的触摸接触运动轨迹会导致姿态辨识操作和姿态跟踪处理的故障。

对于作为相对较小或短姿态的姿态运动，传统跟踪处理会静态匹配来自持续帧的空间上共处的触摸接触。然而，此途径对于作为相对较大或长姿态的姿态运动并不有效，如，通常可以在涉及诸如闪烁或平移的快速姿态的平板计算机或其它类型板材形式因素上使用。跟踪处理可能对姿态的完整运动不是灵敏的，这会致使姿态“中断”，所述姿态的完整运动随后可能被辨识和处理为较之实际姿态运动而言更加短的运动范围。可替选地，如果跟踪处理对姿态运动过于灵敏，则这会导致误跟踪触摸接触，如，当用户通过触摸屏显示器上显示的软或虚拟键盘输入文本时。

发明内容

此发明内容介绍基于预测的触摸接触跟踪的简化概念，并且下面在具体实施方式中进一步描述和/或在图中示出概念。此发明内容不应当被视为描述要求保护主题的必要特征，也不用来确定或限制要求保护主题的范围。

描述基于预测的触摸接触跟踪。在实施例中，将触摸输入传感器数据辨识为触摸屏显示器上接触的一系列分量。可以识别接触的第一分量，并且可以确定第二分量以与接触相关。可以随后使第一分量和第二分量相关联以表示接触的跟踪。接触的后续分量可以被确定和与接触的先前分量相关联以进一步表示接触的跟踪。

在其它实施例中，向接触的第一分量和向第二分量、以及向表示接触跟踪的后续分量分配相同的标识符以使所有分量与接触相关联。可以基于评估从预测分量位置至接触的一个或更多个额外分量的距离的最近邻近者准则验证与接触的后续分量相关的预测分量位置。另外，可以基于接触的分量之间的最小最大距离确定将分量确定为接触的分量。

附图说明

参照附图描述基于预测的触摸接触跟踪的实施例。可以通篇使用相同的标记引用图中示出的相似特征和组件：

图1示出了其中可以实施基于预测的触摸接触跟踪实施例的示例系统。

图2示出了按照一个或更多个实施例的基于预测的触摸接触跟踪的示例方法。

图3示出了按照一个或更多个实施例的接触跟踪服务的示例架构。

图4示出了按照一个或更多个实施例的用于处理基于预测的触摸接触跟踪的示例架构。

图5示出了按照一个或更多个实施例的基于预测的触摸接触跟踪的高级流程图。

图6示出了按照一个或更多个实施例的到达合并的示例。

图7示出了按照一个或更多个实施例的判定区域的运动预测的示例。

图8示出了按照一个或更多个实施例的多级最大距离确定的最小最大距离确定的示例。

图9示出了按照一个或更多个实施例的可以表明不想要的分量关联的交叉轨道的示例。

图10示出了按照一个或更多个实施例的如何运算和考虑如图9中所示交叉轨道的示例。

图11示出了按照一个或更多个实施例的基于预测的触摸接触跟踪的示例方法。

图12示出了按照一个或更多个实施例的基于预测的触摸接触跟踪的示例方法。

图13示出了按照一个或更多个实施例的基于预测的触摸接触跟踪的示例方法。

图14示出了可以实施基于预测的触摸接触跟踪实施例的示例设备的各种组件。

具体实施方式

描述基于预测的触摸接触跟踪的实施例。如以上所注意到的，可能不能准确跟踪和/或处理运算设备（如，移动电话或便携式计算机）的触摸屏显示器上的触摸和姿态输入。基于预测的触摸接触跟踪使用来自先前帧的触摸位置处分量的预测，并且可以在高运动的情形中可靠实现跟踪而同时，可以避免软键盘的情形中的误跟踪。触摸接触跟踪可以基于接触的先前识别分量的预测位置，其中一套规则定义通过预测获得的跟踪的有效性的范围。如果不存在预测，则经由最小最大距离确定（例如，算法或流程）、以及可选地通过跟踪交叉的惩罚项实施解决方案以发起预测。

基于预测的触摸接触跟踪的实施例可以包括分量识别和接触跟踪的基于预测的两级流程。使用第一级的流程基于预测对于姿态输入跟踪建立接触分量的初始关联，使用第二级的流程基于最近邻近者接触映射准则进行验证以生成接触分量的最终关联。另外有关的是定义多手指触摸和姿态辨识操作的一套规则。这可以被实施用于具有触摸屏显示器的任何基于板材的设备、平板设备、移动电话或计算机，以及对于诸如表面、间接触摸等的其它类似技术。

实施例还包括接触映射上的最小最大距离确定以生成预测余量的触摸接触的分量关联、以及在预测不可用时产生分量位置的初始预测。流程还考虑惩罚穿过或通过初始姿态输入跟踪选择的姿态运动跟踪。实施例还包括用以处理和分辨（resolve）混淆为单个分量的多个触摸位置的情形的途径、以及用以处理和分辨两个或更多个触摸位置混淆为单个、较大分量时的到达合并的途径。还可以实施本文中描述的技术的应用以通过执行展望预测减少触摸延迟。

虽然可以在任何数量的不同设备、系统、环境、网络、和/或配置中实施基于预测的触摸接触跟踪的特征和概念，但在以下示例设备、系统、以及方法的上下文中描述基于预测的触摸接触跟踪的实施例。

图1示出了其中可以实施基于预测的触摸接触跟踪的各种实施例的示例系统100。示例系统包括可以是移动电话104、娱乐设备、导航设备、用户设备、无线设备、便携式设备、平板计算机106、双屏折叠设备108等中任何一个或组合的运算设备102。运算设备包括实施以感测姿态输入112（如，触摸屏显示器上显示的用户界面中的用户发起姿态）的集成触摸屏显示器110。在此示例中，姿态输入是在箭头表明的大致方向上触摸屏显示器上的两手指姿态，但是可以是单手指姿态输入、或者多手指姿态输入（例如，三或更多手指姿态输入）。可以通过各种组件（如，一个或更多个处理器和存储器设备）、以及如参照图14中示出的示例设备进一步描述的任何数量和组合的不同组件实施任何运算设备以实施基于预测的触摸接触跟踪的实施例。

在示例系统100中，运算设备102包括实施以将触摸输入传感器数据116辨识为触摸屏显示器110上的姿态输入112的触摸输入模块114（例如，较低层组件）。运算设备还包括作为HID报告120（即，人类接口设备包括）接收来自触摸输入模块的触摸输入传感器数据的姿态辨识应用118（例如，较高层组件）。HID报告包括与运算设备的触摸屏显示器上的姿态输入相关的时间和位置数据、以及确定的触摸接触跟踪。实施姿态辨识应用118以辨识和生成如根据与输入或输入的组合（如，姿态输入112）相关联的触摸输入数据（例如，HID报告120）所确定的各种姿态。姿态辨识应用可以根据各种用户可选择输入生成各种姿态，如，选择姿态、握持姿态、运动姿态、敲击姿态、以及其它类型的姿态。

运算设备102的输入辨识系统可以包括用以区分各种类型输入的任何类型输入检测特征和/或设备，如，传感器（电容式或电阻式）、光感测像素、触摸传感器、摄像器、和/或解释用户交互、姿态、输入、以及运动的自然用户接口。在实施方式中，输入辨识系统可以根据可辨别变量（如，根据方向变量、根据开始区域位置变量和结束区域位置变量、和/或根据运动速率变量（例如，每秒特定数量的像素））检测运动输入。

如本文中所述，可以作为设备的触摸屏显示器上通过一个或更多个手指的用户输入辨识姿态输入，并且姿态输入包括各自与触摸屏显示器上手指的输入相关的一个或更多个接触。在图1示例中，两手指姿态输入112包括识别为与姿态输入的第一手指相关的第一接触122、以及与姿态输入的第二手指相关的第二接触124的两个接触。

作为一系列帧接收姿态输入数据，并且帧包括表示接触的一个触摸位置（例如，沿着作为一个手指的姿态输入）的分量。对于两手指姿态输入，帧可以包括与第一手指的输入相关的第一接触的分量，以及包括与第二手指的输入相关的第二接触的分量（对于多于两手指姿态输入诸如此类）。

在图1示例中，姿态输入112的第一接触122包括持续分量，如，沿着第一接触在不同触摸位置处的分量126、分量128、以及分量130。类似地，姿态输入112的第二接触124包括持续分量，如，沿着第二接触在不同触摸位置处的分量132、分量134、以及分量136。相应地，两手指姿态输入的第一帧包括分量系列中N－2处的相应第一和第二接触的分量126和分量132。类似地，N－1处的姿态输入接下来的帧包括相应第一和第二接触的分量128和分量134，N处的姿态输入的当前帧包括相应第一和第二接触的分量130和分量136。

因此，姿态输入的接触跨越多个帧和包括来自每个持续帧的识别成与接触、或者与接触的部分相关的分量。分量表示帧中接触的触摸位置（例如，在把分量识别成了与接触相关之后）。如实施例中所述，可以基于评估分量位置之间距离的最近邻近者接触映射准则把分量识别成与特定接触相关。然而，如果最近邻近者接触映射未识别对已有接触之一的分量，则可以生成姿态输入的新接触以表示用来在触摸屏显示器上做姿态的额外手指的跟踪。

触摸输入模块114将触摸输入传感器数据116辨识为运算设备102的触摸屏显示器110上姿态输入112的两个接触122、124的分量系列。在实施例中，实施触摸输入模块114以对于每个接触的每个分量根据触摸输入传感器数据116生成传感器映射图138。传感器映射图表示接触的各个分量，如，当用户发起触摸屏显示器110上的姿态输入112时。在此示例中，传感器映射图包括作为表示传感器映射图中元素位置处信号强度的8位十六进制值示出的元素140。触摸输入传感器数据的较强传感器信号表明与传感器映射图中元素的较多触摸接触。可以作为二维阵列生成传感器映射图，二维网格中元素的阵列索引与从触摸屏显示器上的姿态输入感测的触摸接触相关。可以减去静止基线电平以使得把未检测为触摸接触的一部分的传感器映射图周围区域中的元素归一化为零电平。

运算设备102还包括实施以确定与触摸屏显示器110上姿态输入（如，姿态输入112）的一个或更多个接触对应的预测触摸接触跟踪144的接触跟踪服务142。可以作为计算机可执行指令（如，软件应用）实施、以及通过一个或更多个处理器执行接触跟踪服务以实施本文中描述的各种实施例。还可以作为运算设备中专用传感器设备硬件上的固件实施接触跟踪服务。在此示例中，把接触跟踪服务示出成实施为触摸输入模块114的组件。可替选地，可以作为独立软件应用或服务实施接触跟踪服务以预测触摸接触跟踪。

在实施例中，实施接触跟踪服务142以执行基于预测的触摸接触跟踪的各种流程和/或算法。接触跟踪服务可以识别和预测映射为两个接触（例如，相关、相关联）的姿态输入的分量。分量126－130表示第一接触122的跟踪，以及分量132－136表示第二接触124的跟踪。为识别成与特定接触相关的分量均分配相同的标识符。例如，为第一接触122的分量126－130均分配相同的第一标识符，为第二接触124的分量132－136均分配相同的第二标识符，其中，第一和第二标识符不同以区分单独接触。如下面进一步描述的，接触跟踪服务可以基于评估从预测分量位置至接触的额外分量的距离的最近邻近者准则验证预测分量位置与接触的后续分量相关。附加地，接触跟踪服务可以基于接触的分量之间的最小最大距离确定来确定分量与特定接触相关。

按照基于预测的触摸接触跟踪的一个或更多个实施例参照各图2、11、12、以及13描述示例方法200、1100、1200、以及1300。通常，可以使用软件、固件、硬件（例如，固定逻辑电路）、人工处理、或者其任何组合实施本文中描述的服务、功能、方法、流程、组件、以及模块中的任一个。软件实施表示在通过计算机处理器执行时执行指定任务的程序代码。可以在可以包括软件、应用、例程、程序、对象、组件、数据结构、流程、模块、功能等的计算机可执行指令的总体上下文中描述示例方法。可以把程序代码存储在计算机处理器本地和/或远程的一个或更多个计算机可读存储介质设备中。也可以通过多个计算机设备在分布式运算环境中实践方法。进一步地，本文中描述的特征是平台独立的和可以在具有各种处理器的各种运算平台上实施。

图2示出了基于预测的触摸接触跟踪的示例方法200。描述方法块的次序并非意在解释成限制，并且可以按任何次序组合任何数量的描述的方法块以实施方法、或者替代方法。

在块202，在触摸屏显示器上辨识姿态输入。例如，运算设备102处的触摸输入模块114（图1）辨识各种输入或输入的组合，如，示例设备104的触摸屏显示器110上的姿态输入112。在此示例中，姿态输入112是包括识别成与姿态输入的第一手指相关的第一接触122、以及与姿态输入的第二手指相关的第二接触124的两个接触的两手指姿态输入。

在块204，确定与姿态输入对应的基于预测的触摸接触跟踪。在块206，基于接触的一个或更多个先前分量预测接触接下来的分量位置。在块208，基于接触的分量之间的最小最大距离确定预测接触接下来的分量。在块210，映射姿态输入的接触的分量以表示接触的跟踪。在块212，预测分量的初始关联以建立接触的跟踪。在块214，基于最近邻近者准则验证接触的分量的最终关联。在块216，分辨混淆为接触的单个分量的多个触摸位置。在块218，对于与接触的分量合并的额外触摸位置分辨接触合并（merge-on-contact）。

例如，运算设备102处的接触跟踪服务142（图1）确定与示例设备104的触摸屏显示器110上的姿态输入112对应的基于预测的触摸接触跟踪。接触跟踪服务还基于姿态输入的接触的一个或更多个先前分量预测姿态输入的接触接下来的分量位置；基于接触的分量之间的最小最大距离确定预测姿态输入的接触接下来的分量；映射（例如，相关、关联）姿态输入的接触的分量以表示接触的跟踪；预测分量的初始关联以建立接触的跟踪；基于最近邻近者准则验证接触的分量的最终关联；分辨混淆为接触单个分量的多个触摸位置；和/或分辨与接触的分量合并的额外触摸位置的接触合并。

图3示出了实施以便进行触摸信号处理的参照图1描述的接触跟踪服务142的示例实施方式和各种组件。图4示出了用于处理基于预测的触摸接触跟踪的示例架构400并参照图1中示出的触摸输入模块114、以及参照图1和3中示出的接触跟踪服务142描述。图5示出了作为图3中接触跟踪服务142的组件示出的触摸接触跟踪器模块300（也称作“接触跟踪器”）实施的基于预测的触摸接触跟踪的高级流程图500。

在402（图4）输入（例如，在触摸输入模块114处接收）触摸输入传感器数据116，并且触摸输入模块的传感器单元根据姿态输入的接触的每个分量的触摸输入传感器数据生成传感器映射图302（图3）。可以在404处对于归一化为零电平的传感器映射图周围的元素减去、或者以其他方式去除基线电平。例如，可以将传感器映射图138生成为二维网格，其中间距为5mm并且元素深度为八至十六位。在406实施连通分量分析器304以便进行连通分量分析。连通分量分析器接收归一化传感器映射图420作为输入和生成表示姿态输入的分量代替的触摸接触的连通接触分量的阵列306。在408实施触摸接触跟踪器模块300以便进行分量识别和接触跟踪以关联（例如，相关或映射）来自先前帧的分量和表示连续姿态运动的轨迹（例如，跟踪）（如，第一接触122的跟踪和第二接触124的跟踪）的当前帧中触摸位置处的分量。

在图5中，在块502在作为输入接收到每个新帧时对于可预测性检查来自先前帧的一套触摸接触。在块504把仍在初始跟踪阶段（即，来自块502的“是”）中、以及在建立了触摸接触关联的足够历史之前的触摸接触输入到触摸接触映射模块308（也称作“接触映射器”）以便进行最小最大接触映射。最小最大接触映射生成映射接触分量310的初始关联，其随后被输出和缓存为用于未来帧的具有关联历史的确定分量312。

在块506把并非初始触摸接触（即，来自块502的“否”）的触摸接触（例如，当接收了至少两个先前帧时）输入到运动预测模块314以便进行运动预测以生成触摸接触预测位置316。基于最近邻近者距离匹配算法在块510把这些触摸接触预测位置连同当前帧的连通分量508一起输入到触摸接触映射模块308以便进行最近邻近者接触映射。在512针对准则检查最近邻近者距离匹配的结果以确定是否把当前帧的分量成功映射到了接触的先前分量。

如果分量的映射成功（即，来自块512的“是”），则在块514把映射关联输入到触摸接触合并器模块318。如果分量的映射未成功（即，来自块512的“否”），则在块516把分量输入到触摸接触映射模块308以便进行最小最大接触映射并调用两级组合映射。利用来自运动预测模块314的输入（即，作为在块506的输出）和连通分量508，最小最大接触映射试图，基于最小最大距离确定以及涉及手部和/或手指运动动力学的一套规则建立这两套分量位置之间的第一级关联。随后在块518处理第一级映射关联以便对最终确定接触关联进行最近邻近者距离验证。

对于在第一级未建立映射（例如，在块518）的那些接触，在块520将它们路由到所有分量上以便进行接触混淆检查以确定可以是如触摸接触合并器模块318在块514所确定的合并接触的可能混淆。单个分量可以关联到多个触摸接触位置，这会在姿态输入运动的多个手指较贴近地移动以基于触摸输入传感器数据作为单个分量显现时出现。为了检测触摸接触合并器，对于第一级接触关联之后的任何未映射分量，可以对于所有分量发起最近邻近者检验以便进行接触关联，并且任何匹配表明单个分量与多个触摸位置之间的混淆关联。

触摸接触合并器模块318处理和分辨合并分量，如，以独立检查两个触摸位置的[x,y]网格点坐标是否一样。接触合并器可以包括混淆为一个分量的多个触摸位置、以及当第一手指在触摸屏显示器上触摸时已经感测或检测第一触摸位置且用户紧贴第一手指放置第二手指时到达合并的场景。可以随后把两个触摸位置检测成在一个较大分量中合并在一起。

图6示出了在与来自先前帧的分量606相关联的第一接触跟踪604中与来自当前帧的分量602到达合并的示例600。示例还示出了检测成与其它分量602已经合并在一起以形成一个较大分量610的混淆触摸位置608。可以通过评估到达合并的条件和特性检测到达合并。例如，接触到分量映射是1对1（即，不存在接触混淆）；投影触摸位置在分量的区域内；分量的尺寸远远大于接触的尺寸；并且预测位置从分量团的中心离开，但是仍在分量区域内。

可替选地，当接触的速度高时，分量的平移在把这二者投影到与速度垂直的方向时远远大于接触的平移；并且当接触的速度高时，预测位置从分量团的中心离开——均在投影到与速度垂直的方向之后。当这些条件均符合时，可以在它的中心处于与分量团的中心上的原始接触成对角的情况下生成另一接触且此新接触是对分量的混淆。

为了分辨到达合并，接触跟踪服务142可以试图分辨一个分量610中的两个触摸位置和在合并状态中跟踪它们，如下面在概率途径中所述的。可替选地，接触跟踪服务可以基于合并分量的初始触摸输入传感器数据确定分量602的第一触摸位置和把第二触摸位置608分辨成是合并分量的任何新触摸输入传感器数据。

图7示出了表示给定接触的跟踪的情况下接触（如，示例设备104（图1）的触摸屏显示器110上姿态输入112的接触）的预测分量位置704的判定区域702的运动预测的示例700。在实施例中，在姿态输入在触摸屏显示器上在位置N－2处开始和继续跟踪接触至位置N－1和随后至位置N时实施接触跟踪服务142的运动预测模块314（图3）以便进行运动预测。基于对预测分量位置704的接近作为与N－2和N－1处的分量相关联的分量确定位置N处的分量。当存在识别为先前N个帧中的i的分量的关联时，则可以如以下公式中那样，通过接触的先前分量位置的线性组合预测X_i的当前帧中分量的位置

。

如果例如N＝3，则一个解是经由简单恒定加速度条件确定的常数a1＝2.5、a2＝－2、以及a3＝0.5。如果例如N＝2，则解是a1＝2和a2＝－1。通常，这些系数可以是时间相关变量，可以运用较先进的技术（如，卡尔曼滤波器）通过迭代流程确定参数。

对于以上预测阶段中生成的第i触摸位置的每个分量，最近邻近者接触映射试图关联当前帧的分量X(t)。可以如本文中所述和/或通过其它技术和算法解决最近邻近者接触映射。可以在考量当前帧的所有分量以确定X(t)在围绕预测位置为中心的二维判定区域702内的分量时建立映射关联。可以首先利用与帧t－1处的第i接触的实际触摸形状匹配的区域对应的半径r的圆形形状构建判定区域。随后沿着速度的方向通过速度有关扩展、以及通过与速度的范数成比例的扩展因子λ修改圆形形状区域。此扩展考虑速度预测的不准确性引入的误差。通常，λ可以具有上限λmax以避免沿着速度的方向贴近在一起的姿态输入运动的手指之间的错误关联。在一个实施方式中，λ＝（1+λmax|v|）/（1+|v|），然而λ的其它选择也可能。

在实践中，可以在相反流程中执行证实最近邻近者接触映射准则的流程。首先运算：差异向量，随后通过沿着速度向量v＝X(t－1)－X(t－2)方向的因子1/λ执行d上的相反缩放。随后针对判定区域的半径r检查所得向量的范数，并且小于r的值表明确定了关联。最近邻近者接触映射的另一扩展是实施概率途径，其中，定义向量d的概率分布函数，并且不是传递分量X(t)属于哪个触摸的硬性判定，在所有分量之中传递概率分布。可以通过HID报告传递此信息以使得姿态辨识应用118（图1）（例如，较高层）可以运用该信息。

在实施例中，可以建立最近邻近者接触映射成功的准则，例如以在块512（图5）确定成功映射。通常，最近邻近者接触映射生成可靠触摸分量关联。然而，在触摸接触速度的一些分布中，可以确定不可靠关联，例如当涉及的触摸位置的速度快和在某些方向上有显著的加速度时。所得预测分量地点变得较贴近邻近分量而非应当与预测分量相关联的跟踪接触分量的地点。

用以检测不可靠关联的此状况的简单条件是确定最近邻近者映射之后不相关联分量的总数量大于分量的数量与触摸的数量之间的差异。注意，这是充分条件，因为理论上会存在分类成差映射的良好映射。由于帧的绝大多数具有可靠的关联预测，所以不可靠关联的状况（例如，故障情形）很可能将会具有很小的百分比（例如，小于5%）（带有可忽略的运算成本）。如果检测到故障情形，则可以如接触跟踪服务的触摸接触映射模块308所实施的，调用组合接触映射的算法或流程以确定正确关联。

组合接触映射可以建立先前帧中建立的接触的给定集合与当前帧中分量的给定集合之间的可靠映射。当确定预测和最近邻近者接触映射故障时，可以使用组合接触映射通过匹配预测位置与分量的位置之间的预测余量建立两个集合（例如，触摸位置与分量）之间的第一级关联。当未在接触存在时间的初始阶段确定预测时，还可以使用组合接触映射建立初始关联。如果如会在新接触的前两个帧中可能发生的一样，不存在接触的初始关联，则触摸接触映射模块308可以随后把原始位置设置成预测位置，并且不存在预测余量。触摸接触映射模块可以包括组合接触映射算法、距离映射的最小最大距离确定算法、以及用于惩罚彼此交叉的姿态输入运动的轨道的交叉轨道抑制器。可以经由最小最大算法和/或通过其它技术和算法（如，匈牙利算法）如本文中所述实施组合接触映射算法。

在实施例中，可以实施接触的最近邻近者检验和分量关联。可以通过与最近邻近者接触映射类似的第二级检验过程评估通过最小最大距离确定建立（如下面进一步描述的）的第一级关联。具体地，确认在最小最大映射阶段对到的初始关联的建立之后当前帧的分量X(t)在X(t)落到围绕第i接触的预测位置为中心的二维预测区域中的情况下属于第i接触。通常，与最近邻近者接触映射的差异是并非评估给定的所有可能分量，对于检验过程选择具有第一级关联的分量。

图8示出了多级最大距离确定的最小最大距离确定的示例800。在实施例中，实施接触跟踪服务142的触摸接触映射模块308（图3）以确定用以把先前帧的分量关联（例如，确定、相关）到当前帧的分量以使得使映射内所有映射对之间的最大距离最小化的理想映射。根据如何应用最小最大距离确定，从其进行映射的先前帧的分量位置可以是后续帧中分量的预测位置。

最小最大距离确定寻求确定先前帧的分量与当前帧的分量之间的最大距离最小的映射。在此示例中，已经识别了从分量804至后续分量的触摸位置806的最大距离802。随后确定从当前帧中的分量808至先前帧中的分量810的映射。例如，第一接触的确定是在812是选择虚线还是实线表示的分量关联，并且第二接触的确定是在814是选择虚线还是实线表示的分量关联。

在公式中，P(i)定义从N向M的映射，其中，N表示来自先前帧的接触上数字标记的集合，M表示当前帧中分量的标记。更具体地，P(i)是取M中的值（范围0…M－1）的i ∈ N（范围0…N-1）的函数，以使得对于i≠j，P(i) ≠P(j)。此外，P表示所有可能P(i)的整个集合，确定P内的最佳P(i)以使得映射定义当前分量与最合理的先前触摸位置的关联。

对于P中的任何P(i)，阵列D(i,P)：i∈ N表示映射中每对i的距离。更具体地，对于映射中的每对i，把距离D(i,P)定义成当前帧的分量的位置与存在预测的情况下先前帧的分量的预测位置、或者先前帧的分量的位置之间的L²距离。随后发起D(i,P)的阵列的降序排序，并且把结果表示成排序D(k,P)，其中0 ≤ k < N，和：

可以在解以下最小化问题时获得最佳P：；其中：

。

值ED是来自最大距离匹配的贡献，并且值MAXD是显示屏幕上的最大距离（通常是对角距离）。此示例中的分层最大距离匹配一旦匹配了距离较大的分量就考虑配置的退化。

图9示出了可以表明当前帧中的分量902与来自先前帧的分量904之间不想要的关联的交叉轨道的示例900。最小最大距离确定可以不正确地关联当前分量与先前分量。把值EC(P)定义成与映射P中所有对标记的轨道中交叉的数量成比例，并且在大约100Hz的采样率下，可以把交叉视为伪映射。在此示例中，分量A到分量C、以及分量B到分量D的映射比分量A到D和B到C的交叉轨道优选。然而，在没有EC(P)的情况下，纯ED(P)将很可能不正确地关联分量A至D和B至C的交叉轨道，这明显是不期望的。

图10示出了如何运算和考虑交叉轨道（如，图9中示出的）的示例1000。EC的运算认为对于轨道和的对，它们彼此交叉的条件是在以下不等式同时成立时：

；其中

a = (a₀, a₁) =  x₁ – x₀

b = (b₀, b₁)  = x₂ – x₃

c = (c₀, c₁) =  x₂ – x₀。

图11示出了基于预测的触摸接触跟踪的示例方法1100。描述方法块的次序并非意在解释成限制，并且可以按任何次序组合任何数量的描述的方法块以实施方法、或者替代方法。

可以运用概率分布来划分一个较大分量610来分辨触摸合并器的示例600（图6）中示出的两个接触的混淆触摸位置以使得每个接触（例如，接触602和接触608）可以关联到分量的单独部分。在实施例中，接触跟踪服务142可以把第一分量分辨为帧（N）的第一接触（即，形心），以及把与第一分量不同的第二分量分辨为帧（N）的第二接触。当第一和第二接触合并到后续帧（N+1）中的较大分量中时，把较大合并分量分辨为第一接触和第二接触。可以分辨任何数量的合并接触。

在块1102，运用跟踪方法把第一触摸位置分辨为帧（N）的第一形心（N）。在块1104，把与第一触摸位置不同的第二触摸位置分辨为帧（N）的第二形心（N）。跟踪在第一触摸位置和第二触摸位置仍然不同的情况下继续到后续帧（N+1）。然而，如果如在块1106所确定的，第一触摸位置和第二触摸位置合并到后续帧（N+1）中的较大分量中，则在块1108把合并触摸位置分辨为第一形心（N+1）和第二形心（N+1）。

在块1108，可以发起方法以识别组合统计量大致等于来自帧（N）的第一接触的单独统计量和第二接触的单独统计量的总和的帧（N+1）中的连续分量。这种统计量的非限制示例是整体分量的面积。例如，如果帧（N+1）中合并分量的面积大致等于帧（N）中单独接触的组合面积，则合并分量可以被检验。可替选地或另外，可以在合并分量的协方差基本上等于先前帧中各个接触的组合协方差的情况下检验连续接触。也可以在两个接触混淆为单个、较大分量时对于到达合并发起方法1100，并且块1104在未把第二接触识别成单独接触而是混淆在去往第一接触的较大分量中时被跳过。

图12示出了如对于姿态输入的单个接触的基于预测的触摸接触跟踪的示例方法1200。描述方法块的次序并非意在解释成限制，可以按任何次序组合任何数量的描述的方法块以实施方法、或者替代方法。

在块1202，将触摸输入传感器数据辨识为触摸屏显示器上接触的一系列分量。例如，运算设备102处的触摸输入模块114（图1）将触摸输入传感器数据116辨识为（如，示例设备104上的）触摸屏显示器110上的姿态输入112的接触（例如，两个接触122、124中的任一个）的分量系列。

在块1204，识别接触的第一分量。在块1206，确定与接触相关的第二分量。在块1208，使第一分量和至少第二分量相关联以表示接触的跟踪。例如，运算设备102处的接触跟踪服务142（图1）根据第一帧识别接触122的第一分量126，预测发起第二帧的接触的后续分量的位置和根据第二帧确定与接触相关的第二分量128，以及在通过最近邻近者准则的情况下关联第一分量和至少第二分量以表示接触的跟踪。如果未通过最近邻近者准则，则作为新接触的触摸位置发起来自第二帧的后续分量，并且终止先前接触。在实施例中，接触跟踪服务142基于接触的第一与第二分量之间的最小最大距离确定来确定第二分量与接触相关。

在块1210，根据接触的跟踪预测接触的分量位置。例如，接触跟踪服务142根据接触的跟踪预测接触的分量位置（例如，基于表示接触跟踪的接触的先前分量）。在块1212，预测分量位置与接触的后续分量相关。在块1214，基于最近邻近者准则把预测分量位置验证成与接触的后续分量相关。例如，接触跟踪服务142基于评估从预测分量位置至接触的一个或更多个额外分量的距离的最近邻近者接触映射把预测分量位置验证成与接触的后续分量相关。在块1216，随后向与接触相关联的所有分量分配相同的标识符。例如，接触跟踪服务142还把相同的标识符分配给表示接触跟踪的后续分量。

图13示出了如对于姿态输入的多个接触的基于预测的触摸接触跟踪的示例方法1300，。描述方法块的次序并非意在解释成限制，可以按任何次序组合任何数量的描述的方法块以实施方法、或者替代方法。

在块1302，将触摸输入传感器数据辨识为包括触摸屏显示器上至少两个接触的姿态输入的一系列分量。例如，运算设备102处的触摸输入模块114（图1）将触摸输入传感器数据116辨识为包括（如，示例设备104上的）触摸屏显示器110上的两个接触122、124的姿态输入112的一系列分量。在此示例中，用户发起包括第一接触122和包括第二接触124的两手指姿态输入。

在块1304，把第一分量确定成与姿态输入的第一接触的第二分量相关。在块1306，把第一分量映射到第二分量以表示第一接触跟踪。在块1308，向第一接触的第一和第二分量中的这二者分配第一标识符。例如，运算设备102处的接触跟踪服务142（图1）确定第一分量126与姿态输入112的第一接触122的第二分量128相关，把第一分量映射到第二分量以表示第一接触的跟踪，以及向第一接触的第一和第二分量中的这二者分配标识符。

在块1310，把第三分量确定成与姿态输入的第二接触的第四分量相关。在块1312，把第三分量映射到第四分量以表示第二接触跟踪。在块1314，向第二接触的第三和第四分量中的这二者分配第二标识符。例如，运算设备102处的接触跟踪服务142（图1）预测分量132与姿态输入112的第二接触124的分量134相关，映射分量以表示第二接触的跟踪，以及向第二接触的分量中的这二者分配第二、不同标识符。

在块1316，基于评估从每个分量至接触的一个或更多个额外分量的距离的最近邻近者准则把接触的分量验证成正确相关。例如，接触跟踪服务142基于评估每个分量至接触的一个或更多个额外分量的距离的最近邻近者接触映射验证接触的分量正确相关。

图14示出了可以实施为参照先前图1－13描述的任何设备、或者设备实施的服务的示例设备1400的各种组件。在实施例中，设备可以实施为以任何形式的消费者、计算机、便携式、用户、通信、电话、导航、电视、家电、游戏、媒体回放、和/或电子设备的固定或移动设备中的任何一个或组合。设备还可以与操作设备的用户（即，人）和/或实体相关联以使得设备描述包括用户、软件、固件、硬件、和/或设备组合的逻辑设备。

设备1400包括实现设备数据1404（如，接收的数据、正接收的数据、对于广播调度的数据、数据的数据分组等）的有线和/或无线通信的通信设备1402。设备数据或其它设备内容可以包括设备的配置设置、设备上存储的媒体内容、和/或与设备的用户相关联的信息。设备上存储的媒体内容可以包括任何类型的音频、视频、和/或图像数据。设备包括经由其可以接收任何类型数据、媒体内容、和/或输入（如用户可选择的输入和从任何内容和/或数据源接收的任何其它类型音频、视频、和/或图像数据）的一个或更多个数据输入1406。

设备1400还包括通信接口1408，如，串行、并行、网络、或者无线接口中的任何一个或更多个。通信接口提供设备与其它电子、运算、以及通信设备通过其与设备传送数据的通信网络之间的连接和/或通信链路。

设备1400包括处理各种计算机可执行指令以控制设备操作的一个或更多个处理器1410（例如，微处理器、控制器等中的任何一个）。可替选地或另外，可以通过结合大体以1412识别的处理和控制电路实施的软件、硬件、固件、或者固定逻辑电路中的任何一个或组合实施设备。在实施例中，设备1400还可以包括实施以辨识触摸输入传感器数据的触摸输入模块1414。虽然未示出，设备可以包括耦合设备内各种组件的系统总线或数据传送系统。系统总线可以包括不同总线结构（如，存储器总线或存储器控制器、外围总线、通用串行总线、和/或运用各种总线架构中的任何总线架构的处理器或本地总线）中的任何一个或组合。

设备1400还包括实现数据存储的一个或更多个存储器设备1416（例如，计算机可读存储介质），如，随机存取存储器（RAM）、非易失性存储器（例如，只读存储器（ROM）、闪存等）、以及盘存储设备。可以作为任何类型的磁或光学存储设备（如，硬盘驱动器、可记录和/或可重写盘等）实施盘存储设备。设备还可以包括海量存储介质设备。

计算机可读介质可以是运算设备访问的任何可用介质。以示例而非限制的方式，计算机可读介质可以包括存储介质和通信介质。存储介质包括以信息存储的任何方法或技术（如，计算机可读指令、数据结构、程序模块、或者其它数据）实施的易失性和非易失性、可移除和不可移除介质。存储介质包括但不限于RAM、ROM、EEPROM、闪存或其它存储器技术、CD-ROM、数字多功能盘（DVD）或其它光学存储部件、磁盒、磁带、磁盘存储或其它磁存储设备、或者可以用来存储信息和可以通过计算机访问的任何其它介质。

通信介质通常在调制数据信号（如，载波或其它传输机制）中实施计算机可读指令、数据结构、程序模块、或者其它数据。通信介质还包括任何信息输送介质。调制数据信号以在信号中编码信息的方式设置或改变它的特性中的一个或更多个特性。以示例而非限制的方式，通信介质包括诸如有线网络或直接连线连接的有线介质，以及诸如声学、RF、红外、以及其它无线介质的无线介质。

存储器设备1416提供用以存储设备数据404、其它类型的信息和/或数据、各种设备应用1418的数据存储机制。例如，可以将操作系统1420维持为存储器设备内的和在处理器上执行的软件应用。设备应用还可以包括设备管理器，如，任何形式的控制应用、软件应用、信号处理和控制模块、对特定设备原生的代码、特定设备的硬件抽象层等。在此示例中，设备应用1418包括实施如本文中所述的角度接触几何形状的实施例的姿态辨识应用1422和触摸跟踪服务1424。

设备1400还包括生成用于音频系统1428的音频数据和/或生成用于显示系统1430的显示数据的音频和/或视频处理系统1426。音频系统和/或显示系统可以包括处理、显示、和/或以其他方式重现音频、视频、显示、和/或图像数据的任何设备。可以经由RF（射频）链路、S视频链路、合成视频链路、分量视频链路、DVI（数字视频接口）、模拟音频连接、或者其它类似通信链路向音频设备和/或向显示设备传送显示数据和音频信号。在实施方式中，音频系统和/或显示系统是设备的外界组件。可替选地，音频系统和/或显示系统是示例设备的集成组件，如，集成触摸屏显示器。

虽然以特定于特征和/或方法的语言描述了基于预测的触摸接触跟踪的实施例，但所附权利要求的主题并不一定限于描述的具体特征或方法。相反，作为基于预测的触摸接触跟踪的示例实施方式公开了具体特征和方法。