k-d树算法 sift.doc

k-d 树算法 sift 本文的主要目的是讲一下如何创建 k-d tree 对目标物体的特征点集合进行数据组织和使用 k-d tree 最近邻搜索来加速特征点匹配。上面已经讲了特征点匹配的问题其实上是一个最近邻( K 近邻)搜索的问题。所以为了更好的引出 k-d tree ,先讲一讲最近邻搜索。最近邻搜索先给出一个最近邻的数学形式的定义。给定一个多维空间, 把中的一个向量成为一个样本点或数据点。中样本点的有限集合称为样本集。给定样本集 E ,和一个样本点 d,d 的最近邻就是任何样本点 d ’∈ E满足 None-nearer(E,d,d ’)。 None-nearer 如下定义: 上面的公式中距离度量是欧式距离, 当然也可以是任何其他 Lp-norm 。其中 di 是向量 d 的第 i 个分量。现在再来说最近邻搜索, 如何找到一个这样的 d’, 它离 d 的距离在 E 中是最近的。很容易想到的一个方法就是线性扫描, 也称为穷举搜索, 依次计算样本集 E 中每个样本点到 d 的距离, 然后取最小距离的那个点。这个方法又称为朴素最近邻搜索。当样本集 E 较大时( 在物体识别的问题中, 可能有数千个甚至数万个 SIFT 特征点) ,显然这种策略是非常耗时的。因为实际数据一般都会呈现簇状的聚类形态, 因此我们想到建立数据索引, 然后再进行快速匹配。索引树是一种树结构索引方法, 其基本思想是对搜索空间进行层次划分。 k-d tree 是索引树中的一种典型的方法。 k-d tree 的简介及表示 k-d tree 是英文 K-dimension tree 的缩写,是对数据点在 k 维空间中划分的一种数据结构。 k-d tree 实际上是一种二叉树。每个结点的内容如下: 样本集 E由 k-d tree 的结点的集合表示,每个结点表示一个样本点, dom_elt 就是表示该样本点的向量。该样本点根据结点的分割超平面将样本空间分为两个子空间。左子空间中的样本点集合由左子树 left 表示,右子空间中的样本点集合由右子树 right 表示。分割超平面是一个通过点 dom_elt 并且垂直于 split 所指示的方向轴的平面。举个简单的例子,在二维的情况下, 一个样本点可以由二维向量(x,y) 表示, 其中令 x 维的序号为 0, y 维的序号为 1 。假设一个结点的 dom_elt 为(7,2) , split 的取值为 0 ,那么分割超面就是 x=dom_elt(0)=7 , 它垂直与 x 轴且过点(7,2) , 如下图所示: (红线代表分割超平面) 于是其他数据点的 x 维(第 split=0 维)如果小于 7 ,则被分配到左子空间; 若大于 7, 则被分配到右子空间。例如,( 5,4 ) 被分配到左子空间, (9,6 )被分配到右子空间。如下图所示: 从上面的表也可以看出 k-d tree 本质上是一种二叉树,因此 k-d tre e 的构建是一个逐级展开的递归过程。其算法的伪代码如下: 1. 算法: createKDTree 构建一棵 k-d tree 2. 3. 输入: exm_set 样本集 4. 5. 输出: Kd, 类型为 kd-tree 6. 7. 1. 如果 exm_set 是空的,则返回空的 kd-tree 8. 9. 2. 调用分裂结点选择程序