基于微软Kinect体感游戏控制器的人体姿态识别方法研究(7)
时间:2017-03-02 22:40 来源:毕业论文 作者:毕业论文 点击:次
注：在数学中，超平面是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轴方向； (责任编辑：qin) |