多點觸摸屏分類算法

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。這爲您預期手指接下來的位置提供了期望值。現在您可以將指定手指的成本定義爲實際註冊位置與預期位置之間距離的一些函數。

總結每個指尖分配的成本並找到成本最低的配置。

現在，如果你想要更復雜，你所要做的就是使用更復雜的模型。也許你不想假設手指獨立移動。您可能希望期望手指移動之間存在某種相關性。在這種情況下，可以改進模型，計算新的點預期並像以前一樣計算分配的成本。