多点触摸屏分类算法

Question

什么是算法可以用来解决以下分类问题？ 我们有多点触摸屏，用户可以用两个或三个手指同时触摸它。

1. 用户触摸屏幕后，我们记得他的手指的初始位置。每个手指从设备获取一组坐标。
2. 当用户移动手指时，我们应该跟踪他的手指的移动。

问题是，当手指彼此接近时。如何确定哪个手指属于哪个点？

我知道这是一种分类问题。什么是算法可以用来解决这个问题？

Answer 1

一个问题是从时间t的N个位置的报告开始，并且在时间t + 1报告N个位置，并计算出在时间t的位置1与在时间t + 1的位置3相同的手指。军方经常以数据融合的名义来看待这类事情。一种方法是记下时间t与时间t处的位置i与时间t + 1处的位置j相关联的成本，然后以最小总成本找到排列 - 这是http://en.wikipedia.org/wiki/Assignment_problem的实例。

如果设备实际上报告两个手指非常靠近在一起，您会遇到一个更复杂的问题 - 但您当然不需要考虑许多不同的位置，因此您应该能够尝试各种方式将一份头寸报告视为两份不同的报告，然后选择最高的得分可能性。

Answer 2

考虑到您正在尝试将三个点分配给三个手指，解决分配问题对此是过度的。即使您试图将五个点指定给五个手指，您最好使用蛮力方法来确定手指点的最佳配置。请注意，对于三个手指和三个点，手指只有六个可能的唯一分配点。因此，最好只计算每个分配配置的成本，并选择成本最低的那个。

但是，我认为这是缺少你的问题的重点。棘手的部分不是分配过程本身，而是为每个可能的分配选择体面的“成本”功能。如果成本函数没有考虑先前的指定点分配，那么将任何手指分配给任何点都有相同的成本，因此您将手指分配到同一个移动点时缺乏任何“连续性”。

所以你的目标是确保你的任务模型的真实生活。我建议的方法是这样的：

定义手指运动的物理模型。一个非常简单的模型将是一个动量模型，其中每个手指彼此独立并被假定为具有某种惯性。如果一个手指在一帧中移动dx，dy，则会期望它在第二帧中移动dx，dy。这为您预期手指接下来的位置提供了期望值。现在您可以将指定手指的成本定义为实际注册位置与预期位置之间距离的一些函数。

总结每个指尖分配的成本并找到成本最低的配置。

现在，如果你想要更复杂，你所要做的就是使用更复杂的模型。也许你不想假设手指独立移动。您可能希望期望手指移动之间存在某种相关性。在这种情况下，可以改进模型，计算新的点预期并像以前一样计算分配的成本。