algorithm - 基于离散点的手势检测算法

Question

我正在尝试解决将人类生成的手势与已知手势匹配的问题。人工生成的手势将由一系列点表示，这些点需要插入到路径中并与现有路径进行比较。下图显示了我要比较的内容

您能否提供一些我可以读懂的资源或概念来帮助我指出正确的方向，以建立可匹配这两条路径的算法？我之前没有这样做的经验，因此任何见解将不胜感激。

Answer 1

接收输入
每隔一段时间测量一次输入。每隔xx毫秒，请测量用户的手/手指/手写笔的坐标。

存储模式和输入
模式（预期输入）
修改图案。目前，它是一个连续的“功能”，但是很难测量输入。间隔使用离散点。此间隔可能非常短，具体取决于您要求手势的准确性。实际上，它应该很短；要比较的点越多越好（我将在下一部分中对此进行更好的解释）。
输入（从用户那里接收）
在测量输入时，输入测量间隔必须足够短，以使每个接收到的连续输入点对都足够接近以与预期点进行比较。
想象一下，用户非常快速地执行某些手势（并在您的输入阅读器仅读取三个帧的时间内完成了手势）。模式和输入无法可靠地比较：

为避免这种情况，输入阅读器的间隔必须相对较短。但是，这可能不是一个大问题，因为大多数硬件甚至可以读取最快的人类手势。
回到模式：它们应该总是足够详细，以包括比任何可能的输入更多的点。预期点越多，精度越高。如果用户缓慢移动，则输入将有更多点；如果它们快速移动，则输入将更少。
考虑一下：完成一个手势将为您提供图案所包含的输入帧的一半。用户以“正常”速度移动，因此，为简化算法，您可以将模式“变钝” 2倍，然后直接将输入坐标与模式坐标进行比较。
这种方法比想到的替代方法容易（请参阅下一节）。

模式“密度”（坐标频率）
如果期望点数量较少，则必须进行近似以匹配输入。
这是一个“极端”示例，但它证明了这一概念。给定此模式和输入：

无法将点3r与点2或点3进行可靠比较，因此必须使用点2、3和3r的某些功能来确定3r是否在正确的路径上。现在考虑相同的输入，但是图案的密度较高：

现在，您不必妥协，因为3r本质上肯定在手势的模式上。模式密度的略微降低会使其很好地匹配输入。

定位
相对定位
您可能不希望比较手势的绝对位置（例如在触摸屏上），而希望在某个空间平面内的任何位置允许该手势。为此，必须将输入的起点与某个坐标系相关联。

正常化
为了便于用户使用，允许在“大小”范围内完成手势。您不希望比较原始数据，因为输入平面的大小可能与模式平面的大小不匹配。
在x和y方向上对输入进行归一化以匹配图案的大小。不要保持宽高比。

根据先前的项目符号，将输入与坐标系相关
查找任意两个输入点之间的最大水平和垂直距离（分别称为RecMaxH和RecMaxV）
找到任意两个图案点之间的最大水平和垂直距离（分别称为ExpMaxH和ExpMaxV）
将所有输入点的x坐标乘以ExpMaxH/RecMaxH
所有输入点的y坐标乘以ExpMaxV/RecMaxV


现在，您可以比较两组更相似的点。规范化可以比这更详细。例如，您可以一次标准化3个点的集合以获得难以置信的相似图像（但是您可能必须对每个图案进行此操作，然后比较所有差异的总和以找到最可能匹配的图案）。
我建议将所有手势的模式存储为相同大小的图形。在测量输入与可能的模式匹配的接近度时减少了计算量。

何时测量输入
用户驱动
想象一下一个按钮，单击/激活该按钮后，它将使您的程序开始测量输入。这与Google的语音搜索类似，后者不会持续记录和搜索。而是说“ Ok Jarvis”或单击方便的麦克风图标，然后开始说出您的查询。
好处：

简化算法
防止用户无意中触发事件。想象一下，您所说的每个单词是否都经过分析并作为搜索查询的一部分发送给Google。有时，您只是无意做任何事情。

缺点：

不太人性化。用户必须竭尽全力来触发手势录制。

例如，如果您要编写手势搜索（荒谬的示例），则这可能是更好的实现方法。没有人希望他们做出的任何举动都被解释为您的应用程序中的一个动作。但是，如果您正在编写Kinect风格或基于手势的游戏，则可能需要不断记录并寻找手势。
不变
您的程序以指定的间隔恒定地记录手势坐标（可以简化为“记录是否有运动，否则不存储坐标”）。您必须做出一个决定：在确定当前存储的动作不是可识别的手势之前，您将记录多少个“帧”？
将坐标存储在缓冲区中：排队的时间是您愿意记录的最大帧数的1.5倍或2倍（请谨慎）。

一旦确定此缓冲区中存在与模式匹配的帧序列，就执行该手势的结果并清除队列。

如果下一个手势可能是最近手势的“选项”，则将应用程序状态记录为“当前正在等待____手势的选项”，然后等待该选项出现。

如果确定缓冲区中的前x帧可能不匹配某个模式（由于其顺序或位置），则将其从队列中删除。


好处：

允许更动态地处理手势
用户输入自动识别

缺点：

更复杂的算法
更重的计算

如果您要编写基于实时输入运行的游戏，那么这可能是正确的选择。

算法
如果您使用的是用户驱动的识别：

在允许的时间范围内（或直到用户表明已完成）记录所有输入
要评估输入，请降低图案的密度以匹配输入的密度
将输入与坐标系相关
标准化输入
使用函数比较的方法（此计算的松散度取决于您：标准偏差，方差，值的总差异等），然后选择最小差异可能性。
如果没有任何可能的相似度足以满足您要求的阈值（您必须决定），请不要接受输入。

如果您使用恒定测量：
在缓冲区中，将max_sequence_size（由您决定）的序列视为在frame_multiples（由您决定）的每一个倍数处开始的可能手势。例如，如果我所有可能的手势最长不超过20帧，并且我相信每5帧就会开始一个新手势（并且我不会在这5帧中丢失任何关键数据），所以我将比较每个部分缓冲区到所有可能的手势（0-19、5-24、10-29等的部分）。当frame_multiples减少时，这会增加计算量。对于完美的测量，frame_multiples为1（但这可能不合理）。

希望您喜欢阅读这个答案，就像享受编写它一样。我以前从未做过此事，但您以一种不常发生的方式激起了我的兴趣。请编辑并完善我的答案！如果有一部分看起来不完整，请添加它。我对（尤其是经验更丰富的）回应和批评感到非常好奇。