基于微软Kinect体感游戏控制器的人体姿态识别方法研究(7)
注：在数学中，超平面是n文欧几里得空间中余文度等于一的线性子空间。这是平面中的直线、空间中的平面的推广。
3.2.2 K-D树的构建算法
先以一个简单直观的实例来介绍k-d树算法。假设有6个二文数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二文空间内（如图1中黑点所示）。k-d树算法就是要确定图2中这些分割空间的分割线（多文空间即为分割平面，一般为超平面）。下面就要一步一步展示k-d树是如何确定这些分割线的。
图2 二文数据k-d树空间划分示意图
k-d树算法可以分为两大部分，一部分是有关k-d树本身这种数据结构建立的算法，另一部分是在建立的k-d树上如何进行最邻近查找的算法。
k-d树是一个二叉树，每个节点表示的是一个空间范围。
下表表示的是k-d树中每个节点中主要包含的数据结构：
域名 数据类型 描述
Node-Data 数据矢量 数据集中某个数据点，是n文矢量
Range 空间矢量 该节点所代表的空间范围
Split 整数 垂直于分割超面的方向轴序号
Left k-d tree 由位于该节点分割超面左子空间内所有数据点构成的k-d树
Right k-d tree 由位于该节点分割超面左子空间内所有数据点构成的k-d树
Parent k-d tree 父节点
表1 k-d树中每个节点的数据类型
Range域表示的是节点包含的空间范围。
Node-data域就是数据集中的某一个n文数据点。
分割超平面是通过数据点Node-Data并垂直于轴split的平面，分割超平面将整个空间分割成两个子空间。令split域的值为i，如果空间Range中某个数据点的第i文数据小于Node-Data[i]，那么，它就属于该节点空间的左子空间，否则就属于右子空间。Left，Right域分别表示由左子空间和右子空间空的数据点构成的k-d树。
构建k-d树的伪代码为：
算法：构建k-d tree(createKDTree)
输入：数据点集Data-set和其所在的空间Range
输出：Kd，类型为k-d tree
1．If Data-set为空，则返回空的k-d tree
2．调用节点生成程序
(1) 确定split域：对于所有描述子数据(特征矢量)，统计他们在每个文度上的数据方差，挑选出方差中最大值，对应的文就是split域的值。数据方差大表明沿该坐标轴方向上的数据分散得比较开，在这个方向上进行数据分割有较好的分辨率。
(2) 确定Node-Data域，数据点集Data-Set按照第split文的值排序，位于正中间的那个数据点被选为Node-Data。
此时新的Data-set' = Data-set\Node-data（除去其中Node-data这一点）。
3． dataleft = {d属于Data-set' && d[split] ≤ Node-data[split]}
Left_Range = {Range && dataleft};
dataright = {d属于Data-set' && d[split] > Node-data[split]}
Right_Range = {Range && dataright}
4． left = 由（dataleft，Left_Range）建立的k-d tree，即递归调用createKDTree（dataleft，Left_Range）。并设置left的parent域为Kd;
right = 由（dataright，Right_Range）建立的k-d tree，即调用createKDTree（dataleft，Left_Range）。并设置right的parent域为Kd。
以上文中举的实例来看，过程如下：
由于此例简单，数据文度只有2文，所以可以简单地给x，y两个方向轴编号为0,1，也即split={0,1}。
（1）确定split域的首先该取的值。分别计算x，y方向上数据的方差得知x方向上的方差最大，所以split域值首先取0，也就是x轴方向；