KDtree文档Word文档下载推荐.docx
《KDtree文档Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《KDtree文档Word文档下载推荐.docx（7页珍藏版）》请在冰点文库上搜索。
首先考虑最简单的划分法，即选择第一个数作为比较对象，S中剩余的其他所有K维数据都跟该数在维度i上的值（分割值）进行比较，如果小于分割值则划A集合，大于则划入B集合。
把A集合和B集合分别看做是左子树和右子树，那么我们在构造一个二叉树的时候，当然是希望它是一棵尽量平衡的树，即左右子树中的结点个数相差不大。
而A集合和B集合中数据的个数显然跟分割值有关，因为它们是跟分割值比较后才被划分到相应的集合中去的。
好了，现在的问题就是确定分割值了。
给定一个数组，怎样才能得到两个子数组，这两个数组包含的元素个数差不多且其中一个子数组中的元素值都小于另一个子数组呢？
方法很简单，找到数组中的中值（即中位数），然后将数组中所有元素与中值进行比较，就可以得到上述两个子数组。
同样，在维度i上进行划分时，分割值就选择该维度i上所有数据的中值，这样得到的两个子集合数据个数就基本相同了。
构建好一棵Kd-Tree后，之后就要进行查找了，Kd-Tree主要有两种查找方法，一种是设不定回溯次数得查找，这种查找方式保证能找到最优值，但是因为回溯的存在，当维数很高时效率下降的很快，另一种是设定回溯次数的查找方法，在回溯中有些树分支存在最近邻的可能性比其他树分支要高，因为树分支离查找点之间的距离或相交程度是不一样的，离查找点更近的树分支存在查找点的最近邻的可能性更高。
因此，我们需要区别对待每个待回溯的树分支，即采用某种优先级顺序来访问这些待回溯树分支，使得在有限的回溯次数中找到目标点的可能性很高。
2自己实现kd-tree
最开始想去看看opencv中有没有实现好的Kd-Tree，但是网上查找后，基本上给出的例子都最多到3维数据的查找，于是决定自己实现一个Kd-Tree，经过一周多的努力，总算实现了从建立树到查找数据的全过程，但是通过实验发现实际查找效率上只能达到暴力搜索的三分之一，性能不是很理想，不能达到实验室需求。
于是决定分析opencv关于Kd-Tree查找的算法。
3opencv实现的kd-tree的算法
网上给出的例子都是通过cv:
:
Index这个类来调用Kd-Tree算法，经过分析发现，这个类最后调用的是cvflann:
KDTreeIndex来实现具体算法。
下面来具体介绍opencv的做法。
cvflann:
KDTreeIndex类的构造函数如下：
首先就是Matrix<
ElementType>
类型的inputData，顾名思义，这个类型代表构建Kd-Tree的输入数据，这个类内数据很简单，主要就是保存了输入数据的首地址，数据的个数和每个数据的维数，以及一个operator[]函数（下标运算符的重载函数）。
这个函数的作用就是输入一个索引值，然后返回该索引值数据的首地址。
函数内就一句话returndata+index*stride，因此根据这个重载函数可以得知Matrix<
类内保存的数据必须是连续存放的。
因为网上的例子都通过cv:
Index这个类来调用Kd-Tree算法，其中关于数据连续的检测都在这个类中完成，但是现在我们要直接调用底层的实现类，所以要自己确保数据的连续性。
构造函数的第二个参数是IndexParams类型的params，可以看到它有默认值，这个params表示建立索引的方式，opencv实现的Kd-Tree为了实现限制回溯的查找方式，采用了把数据打乱后同时建立多棵树，这样每颗数的分割维度和分割值都不相同，查找数据时，同时对多棵树进行查找，之后回溯时根据优先队列，在多棵树上回溯查找。
这种设计主要是为了提高查找精度。
其实看源码可以发现IndexParams就是std:
map<
cv:
String,any>
的别名，而cvflann:
KDTreeIndex主要用到”trees”这个参数，这就是前面说的建立Kd-Tree的个数，如果要采用限制回溯查找次数的方法的话，这个”trees”要大于等于一，要是采用不限制回溯查找次数的方法的话，这个”trees”必须为一。
构造函数的第三个参数是Distance类型的d，参数也带有默认值，Distance表示是opencv中用来计算距离的类，这里我们传的是计算L2距离的类。
在实际使用中，一般都是用L2距离，所以一般传前两个参数的值就行了。
这个构造函数主要做的工作就是把inputData保存到自己的类中，获取数据的维数和个数获取需要建立数的个数，分配数的根节点并保存，以及建立索引数组。
初始化之后就要建立Kd-Tree了，建立主要通过buildIndex（）函数，函数如下
可以看到根据需要建立Kd-Tree的个数，循环去建立，因为采用了std:
random_shuffle（vind_.begin（）,vind_.end（））;
，因此每次建立的数都不一样，这个函数实际调用了工具函数divideTree
这个函数完成了具体的建立树的过程，可以看到其中还调用了其他的函数来完成工作，具体建立数的原理也和我前面说的过程差不多，比如确立分割维度和分割值，这里我只说下opencv采取的提高速度的只要方法，meanSplit（ind,count,idx,cutfeat,cutval）;
完成具体的确立分割维度和分割值的工作，剩下的就是递归建树，首先是计算均值，这里opencv并没有计算有数据在维度上的均值，它最多取随机的100个数据进行计算，这也是前面建立多颗Kd-Tree而都不相同的原因，当然再提高了计算速度的同时，也容易造成误差，我想这也是它采取建立多颗Kd-Tree的原因，来避免这种误差。
之后对取出的最多100个数据计算方法，opencv只计算了平方和，并没有开根号，这也提高了速度，最后根据均值和方差，对索引数组进行重新排列，这是通planeSplit这个函数完成的，它把比搜索值小的放在索引前面，大的放在索引后面，然后获得索引点，之后递归的进行建立树。
如果是叶子节点的话，节点中的divefeat保存的就是索引值，通过索引，就能获得原始的数据了。
下面是数据的查找，cvflann:
KDTreeIndex类用findNeighbors这个接口函数完成数据的查找：
第一个参数是ResultSet<
DistanceType>
&
result，这是个基类，在Kd-Tree查找数据时，传递的是它的派生类KNNUniqueResultSet，这个类主要可以设定查询的个数，进行查询结果使得保存，以及对距离近行排序，因为最终的结果可能返回多个，因此这个类可以实现返回距离最近的前几个的索引cvflann:
KNNUniqueResultSet<
float>
resultSet
（1）;
可以按照这种方法使用。
传递的1表示最终返回结果的个数。
第二个参数是constElementType*的数组，这就是查询的数据，传递的是指针。
第三个参数是一个查询参数，这个和前面的建树参数类似，实际上也是个map，这个查询参数主要用来设定查询是回溯的次数，可以通过设定"
checks"
的值，如果"
设定为
-1，那么代表不限定回溯次数的意思，当设定"
为-1时，前面的建立数的参数”trees”必须为1。
在函数中可以看到如果不现在回溯次数调用getExactNeighbors，如果限制则调用getNeighbors在限制次数的搜索函数中，利用优先队列来实现对分支距离的排序，对距离最近的分支优先搜索。
具体过程就不讨论了。
4opencv实现的kd-tree的问题
但是opencv实现的kd-tree不能满足实验室的需求，因为opencv需要建立数的数据必须连续存放，而且必须按照它给出的形式存，因此需要改造Matrix<
类，改变其中的operator[]函数（下标运算符的重载函数）读取数据的方法，最开始我计划采用派生类的方法，但是发现Matrix<
类里的operator[]函数不是虚函数，于是最后采用的方法是模仿opencv的实现，自己写一个kd-tree的类，并且自己重新写一个Matrix<
类。
这样可以随意改变数据的存放方式，使用上更加灵活，并且方便扩展。
4自己的kd-tree的使用方法
我主要重写了两个opencv自带的类，分别是cvflann:
KDTreeIndex和Matrix<
类，我起名为My_KD_Tree和My_Matrix，这两个类的实现和opencv自带的差不多，我主要讲讲不同点，和使用。
首先是My_Matrix类，下面是我重写的operator[]函数。
为了实验自己的想法是否可行，我这里完全改写的operator[]函数完全从硬盘中去获取数据，即My_Matrix里只保存数据的个数和维数，这个函数每给一个索引，才去硬盘中读取一条数据，保存到内存。
这样不用再内存中保存大量的数据，也可以把索引建立起来，当然这只是实验证明可行。
以后这个函数还可以改。
以后修改函数时，只要保证My_Matrix里保存数据的个数和维数，给予一个索引operator[]函数能取得数据的首地址即可。
My_Matrix的空间很大。
还有就是My_KD_Tree中的改动，主要就是把其中原来保存数据的constMatrix<
dataset_;
变为My_Matrix<
dataset_，这里去掉了const属性主要为了方便以后的扩展，具体如下图所示
另外原始的cvflann:
KDTreeIndex接口很不友好，要设置很多参数，比如建树时的参数和搜索时的参数，save树和load树也不好用，如果没有看过源码很难知道怎么去使用，因此我在My_KD_Tree中采用了更简便的设计，让接口使用更加方便。
下面介绍My_KD_Tree的使用方法
首先是构造函数。
我保留了和cvflann:
KDTreeIndex同样的构造方法，同时新加了一个构造函数如下：
这个函数参数把Matrix变为My_Matrix，第二个参数我直接采用数字设置，代表需要建立几颗树，如果要不限制回溯次数的查找，params必须设为1。
My_KD_Tree的接口函数有四个分别是voidbuild（）;
//建立一棵树，voidsave（constcv:
String&
filename）//保存索引，voidload（constcv:
filename）//读取索引，voidfind（constElementType*vec,int&
ans,ElementType&
dis）//是查询目标。
前面三个接口很容易使用，第四个是查询，其中vec是查找数据的首地址，第二个ans是找到最近的数据在My_Matrix中的索引，可以用operator[]找到实际的值，第三个是找到的数据和实际查找数据的距离，这个值没有开过根号。
另外My_KD_Tree中不需要设置查找参数，这里我都根据前面的建树值自动设置，方便使用。
其中第一次建立数时必须用build（），也可以用save来保存建立好的树，这样，下次就可以不用建树，直接用load去读取数即可，这可以节省建立数的时间。
最后My_KD_Tree和My_Matrix都是在命名空间cvflann:
中，使用的时候要注意。
下面给出使用实例
5总结
这也算我一次看opencv的源码，上面说的只是冰山一角，真的看了很多opencv和kd—tree有关的源代码，感觉opencv的很多设计值以及算法得我去学习，比如它建树时对分割维度和分割值得计算，对距离排序的方法，对boost中DynamicBitset的重新实现和使用，内存池的实现和使用等。
另外，看源码，让我对c++中面向对象的编程，封装，数据抽象，继承，模板有了更深刻的理解，看到了很多只在书本中讲解，未曾实际使用过的东西，感觉c++真的博大精深，想用好c++很不容易，还需要多学习才行。
也希望吴老师以后能多让我们看点比较好的开源库中的源代码。
升级会员 