基于微软Kinect体感游戏控制器的人体姿态识别方法研究(9)
k-d树的最近邻搜索步骤如下：
1.从根节点开始，算法递归地向下移动，搜索点插入的话，也是用同样的方式 (例如，往左还是往右取决于当前文下，该节点是比当前节点大还是小)
2.一旦到达叶子节点，就把该节点保存为当前最佳点。
3.算法展开递归，在每个节点上进行如下步骤：
4.如果当前节点比当前最佳点更近，那么它就成为当前最佳点。
5.检查在当前分割平面的另一半是否存在比当前最佳点更接近搜索点的点。这个由分割超平面和环绕搜索点(半径等于当前最短距离)的超球面交叉完成。由于超平面的所有坐标轴都是对齐的，因此，只需做一个简单的比较，看看搜索点的分割坐标和当前节点的差异是否小于搜索点到当前最佳点的距离（所有坐标）。
6.如果超球面穿过平面，说明平面的另一半存在更近点，因此必须从当前节点开始，往树的另一分支向下移动，递归地寻找更近点。如果超球面和分割平面不交叉，那么可以继续往下走，该节点下的另一分支可以整个消除。
7.对于根节点，上述步骤完成后，搜索就完成。
3.3 姿态数据库的创建
3.3.1 关节点位置的度量
Kinect的骨骼追踪框架可追踪人体20个关节点。这20个关节点的位置可以用一个枚举类型来表示。每个关节点的位置可以通过x, y, z三个值来描述。其中x, y分别是水平和竖直方向的位置，z为深度值，用于描述该关节点相对于Kinect深度摄像头的距离（并非直接描述距离，因为需要进行一系列的转换）。
3.3.2 姿态数据采集
我们运行骨骼追踪框架，对参与者进行动作捕捉（需要多名参与者，保证姿态种类），参与者作出一系列典型动作，包括手势，足部动作，等等。获得的姿态χi根据根关节位置和观察方向进行归一化，保证全局转换下的一致性。为了使数据库中的姿态种类最大化，数目最小化，我们用贪心采样算法[2]选择了记录姿态的一个子集。
图8 Kinect骨骼追踪框架所定位的20个关节点
至此,两个姿态χ1和χ2之间的距离便通过参照关节位置dP(χ1, χ2) ≔ 1/J • ||Pχ1 − Pχ2 ||2的平均Euclidean距离测算出来。与[2]对比，一旦所有选择的姿态对之间的距离达到了一个确定的阈值，我们就立刻截断采样。通过截断采样，我们获得了一系列姿态，而且任何两个姿态之间的距离dP都大于1.8cm。
针对每个选定的姿态，我们考虑左右手，左右脚，以及头部的末端执行器位置，拟合为 。以下三个原因促进了这些特性的使用。第一，即使单靠ToF数据[4]，末端执行器的位置也能通过不同姿态的大型集合高效地估算出来，第二，对于许多姿态而言，这些位置是特有的，从而为削减搜索空间产生了一个合适的表征。第三，它们使低文特征向量促进了高效索引方法的使用。总之，末端执行器为全身姿态构成了一种合理的中间层表示，一方面，抽象出噪音输入数据的大部分细节，同时，另一方面也保留了姿态估算所需的辨识能力。我们在15文叠加矢量 上使用上文介绍的kd-树[1]来进行索引。由于骨骼大小(例如身高或臂展)因人而异，姿态数据库必须适应参与者。因为这在展示的系统中并没有实现，所以此任务可以用重定位框架解决。即使没有重定位，通过处理MI，如果身体比例和数据库骨骼相差不大，我们也能跟踪人物动作。
3.4 数据库查询
在这一部分，我们展示如何使用一种高效的查询算法，无需提取测量极值的先验语义标签。目的是为了在姿态数据库中，通过用恢复测量极值 作为查询输入来搜索数据库kd树，依次确定一个合适的全身姿态 ，然而，末端执行器位置的语义在数据库动作中是可知的，于此不同，查询端极值的语义标签是未知的。为了部分解决丢失的语义，[10]中的方法用一个分类器在手，头，脚等部分运用距离图像补丁。然而，这个过程对于一个实时景象来说代价相对太大(根据[3]，每帧60ms)。在我们的方案中，我们通过在搜索数据库时对 做一系列排列，规避了分类难题。确切地说，让S5成为所有五个排列中的对称组，让S⊆S5成为包含排列σ的子集，这样 中的位置更加接近前一帧 的末端执行器。即