k-d tree算法的研究

作者:51CTO博主 RaySaint

先前一篇文章《SIFT算法研究》讲了讲SIFT特征具体是如何检测和描述的,其中也提到了SIFT常见的一个用途就是物体识别,物体识别的过程如下图所示:

如上图(a),我们先对待识别的物体的图像进行SIFT特征点的检测和特征点的描述,然后得到了SIFT特征点集合。接下来生成物体目标描述要做的就是对特征点集合进行数据组织,形成一种特殊的表示,其作用是为了加速特征点匹配的过程。所谓的特征点匹配本质上是一个通过距离函数(例如欧式距离)在高维矢量之间进行相似性检索的问题,简单来讲就是范围查询或者K近邻查询的问题。

范围查询就是给定查询点和查询距离阈值,从数据集中找出所有与查询点距离小于查询距离阈值的数据;K近邻查询就是给定查询点和正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,它就是最近邻查询。

如上图(b)我们从输入图像中进行SIFT特征点的检测和特征点的描述后,得到了一个待查询点的集合,接下来就是要找出集合中的每一个待查询点在(a)过程得到的目标物体的特征点集合中进行2近邻查询(即得到最近邻和次近邻),得到一组特征点的匹配对<待查询点,待查询点的最近邻>;得到所有匹配对后,然后通过阈值法(与最近邻的距离要小于一个常数)和比值法(与最近邻的距离比次近邻的距离要小于一个常数)进行提纯,滤去较差的匹配对。得到最终的匹配对集合。最后在计算单应性矩阵时,使用RANSAC算法再进行一次提纯,剔除错误的匹配对。关于RANSAC算法,我还会再写一篇文章讲一讲。David G.Lowe的论文说3个或以上的特征点匹配对可以确认一个正确的识别。(因为单应性矩阵的计算最少得使用4个点,并且可能会有错误匹配的情况存在,所以最好需要多一点的特征点匹配对)

本文的主要目的是讲一下如何创建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实际上是一种二叉树。每个结点的内容如下:

域名

类型

描述

dom_elt

kd维的向量

kd维空间中的一个样本点

split

整数

分裂维的序号,也是垂直于分割超面的方向轴序号

left

kd-tree

由位于该结点分割超面左子空间内所有数据点构成的kd-tree

right

kd-tree

由位于该结点分割超面右子空间内所有数据点构成的kd-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 tree的构建是一个逐级展开的递归过程。

其算法的伪代码如下:

算法:createKDTree 构建一棵k-d tree  输入:exm_set 样本集  输出 : Kd, 类型为kd-tree  1. 如果exm_set是空的,则返回空的kd-tree  2.调用分裂结点选择程序(输入是exm_set),返回两个值         dom_elt:= exm_set中的一个样本点         split := 分裂维的序号  3.exm_set_left = {exm∈exm_set – dom_elt && exm[split] <= dom_elt[split]}     exm_set_right = {exm∈exm_set – dom_elt && exm[split] > dom_elt[split]}  4.left = createKDTree(exm_set_left)  right = createKDTree(exm_set_right) 

现在来解释一下分裂结点选择程序。分裂结点的选择通常有多种方法,最常用的是一种方法是:对于所有的样本点,统计它们在每个维上的方差,挑选出方差中的最大值,对应的维就是split域的值。数据方差最大表明沿该维度数据点分散得比较开,这个方向上进行数据分割可以获得最好的分辨率;然后再将所有样本点按其第split维的值进行排序,位于正中间的那个数据点选为分裂结点的dom_elt域。

下面以一个简单的例子来解释上述k-d tree的构建过程。假设样本集为:{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}。构建过程如下:

(1)确定split域,6个数据点在x,y维度上的数据方差分别为39, 28.63。在x轴上方差最大,所以split域值为0(x维的序号为0)

(2)确定分裂节点,根据x维上的值将数据排序,则6个数据点再排序后位于中间的那个数据点为(7,2),该结点就是分割超平面就是通过(7,2)并垂直于split=0(x)轴的直线x=7

(3)左子空间和右子空间,分割超面x=7将整个空间氛围两部分,x<=7的部分为左子空间,包含3个数据点{(2,3), (5,4), (4,7)};另一部分为右子空间,包含2个数据点{(9,6), (8,1)}。如下图所示

(4)分别对左子空间中的数据点和右子空间中的数据点重复上面的步骤构建左子树和右子树直到经过划分的子样本集为空。下面的图从左至右从上至下显示了构建这棵二叉树的所有步骤:

k-d tree的最近邻搜索算法

如前所述,在k-d tree树中进行数据的k近邻搜索是特征匹配的重要环节,其目的是检索在k-d tree中与待查询点距离最近的k个数据点。

最近邻搜索是k近邻的特例,也就是1近邻。将1近邻改扩展到k近邻非常容易。下面介绍最简单的k-d tree最近邻搜索算法。

基本的思路很简单:首先通过二叉树搜索(比较待查询节点和分裂节点的分裂维的值,小于等于就进入左子树分支,等于就进入右子树分支直到叶子结点),顺着“搜索路径”很快能找到最近邻的近似点,也就是与待查询点处于同一个子空间的叶子结点;然后再回溯搜索路径,并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点,如果有可能,则需要跳到其他子结点空间中去搜索(将其他子结点加入到搜索路径)。重复这个过程直到搜索路径为空。下面给出k-d tree最近邻搜索的伪代码:

算法:kdtreeFindNearest /* k-d tree的最近邻搜索 */  输入:Kd /* k-d tree类型*/  target /* 待查询数据点 */  输出 : nearest /* 最近邻数据结点 */  dist /* 最近邻和查询点的距离 */  1. 如果Kd是空的,则设dist为无穷大返回  2. 向下搜索直到叶子结点  pSearch = &Kd  while(pSearch != NULL)  {  pSearch加入到search_path中;  if(target[pSearch->split] <= pSearch->dom_elt[pSearch->split]) /* 如果小于就进入左子树 */  {  pSearch = pSearch->left;  }  else  {  pSearch = pSearch->right;  }  }  取出search_path最后一个赋给nearest  dist = Distance(nearest, target);  3. 回溯搜索路径  while(search_path不为空)  {  取出search_path最后一个结点赋给pBack  if(pBack->left为空 && pBack->right为空) /* 如果pBack为叶子结点 */  {  if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )  {  nearest = pBack->dom_elt;  dist = Distance(pBack->dom_elt, target);  }  }  else  {  s = pBack->split;  if( abs(pBack->dom_elt[s] - target[s]) < dist) /* 如果以target为中心的圆(球或超球),半径为dist的圆与分割超平面相交, 那么就要跳到另一边的子空间去搜索 */  {  if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )  {  nearest = pBack->dom_elt;  dist = Distance(pBack->dom_elt, target);  }  if(target[s] <= pBack->dom_elt[s]) /* 如果target位于pBack的左子空间,那么就要跳到右子空间去搜索 */  pSearch = pBack->right;  else  pSearch = pBack->left; /* 如果target位于pBack的右子空间,那么就要跳到左子空间去搜索 */  if(pSearch != NULL)  pSearch加入到search_path中  }  }  } 

OK,现在举一些例子来说明上面的最近邻搜索算法会比较直观。

假设我们的k-d tree就是上面通过样本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}创建的。将上面的图转化为树形图的样子如下:

我们来查找点(2.1,3.1),在(7,2)点测试到达(5,4),在(5,4)点测试到达(2,3),然后search_path中的结点为<(7,2), (5,4), (2,3)>,从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141;

然后回溯至(5,4),以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆,并不和超平面y=4相交,如下图,所以不必跳到结点(5,4)的右子空间去搜索,因为右子空间中不可能有更近样本点了。

于是在回溯至(7,2),同理,以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆并不和超平面x=7相交,所以也不用跳到结点(7,2)的右子空间去搜索

至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2.1,3.1)的最近邻点,最近距离为0.141。

再举一个稍微复杂的例子,我们来查找点(2,4.5),在(7,2)处测试到达(5,4),在(5,4)处测试到达(4,7),然后search_path中的结点为<(7,2), (5,4), (4,7)>,从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202;

然后回溯至(5,4),以(2,4.5)为圆心,以dist=3.202为半径画一个圆与超平面y=4相交,如下图,所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中,现在search_path中的结点为<(7,2), (2, 3)>;另外,(5,4)与(2,4.5)的距离为3.04 < dist = 3.202,所以将(5,4)赋给nearest,并且dist=3.04。

回溯至(2,3),(2,3)是叶子节点,直接平判断(2,3)是否离(2,4.5)更近,计算得到距离为1.5,所以nearest更新为(2,3),dist更新为(1.5)

回溯至(7,2),同理,以(2,4.5)为圆心,以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索

至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2,4.5)的最近邻点,最近距离为1.5。

两次搜索的返回的最近邻点虽然是一样的,但是搜索(2, 4.5)的过程要复杂一些,因为(2, 4.5)更接近超平面。研究表明,当查询点的邻域与分割超平面两侧的空间都产生交集时,回溯的次数大大增加。最坏的情况下搜索N个结点的k维kd-tree所花费的时间为:

后记

到此为止,k-d tree相关的基本知识就说完了。关于k-d tree还有很多扩展。由于大量回溯会导致kd-tree最近邻搜索的性能大大下降,因此研究人员也提出了改进的k-d tree近邻搜索,其中一个比较著名的就是 Best-Bin-First,它通过设置优先级队列和运行超时限定来获取近似的最近邻,有效地减少回溯的次数。

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-10-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏派森公园

最简单的NP-Hard问题

1468
来自专栏编程

新知识 用Python从零开始构造决策树

起步 本章介绍如何不利用第三方库,仅用python自带的标准库来构造一个决策树。 熵的计算公式: ? 对应的python代码: ? 条件熵的计算 根据计算方法:...

3298
来自专栏ATYUN订阅号

Seq2seq模型的一个变种网络:Pointer Network的简单介绍

Pointer Network(为方便起见以下称为指针网络)是seq2seq模型的一个变种。他们不是把一个序列转换成另一个序列, 而是产生一系列指向输入序列元素...

4795
来自专栏利炳根的专栏

学习笔记CB014:TensorFlow seq2seq模型步步进阶

神经网络。《Make Your Own Neural Network》,用非常通俗易懂描述讲解人工神经网络原理用代码实现,试验效果非常好。

4973
来自专栏人工智能LeadAI

TensorFlow Tutorial-1

1、Why TensorFlow? 网上有关介绍太多了,我就不多说了,这里主要注重使用。 ? Intro.PNG ? github.PNG 2、Programi...

36711
来自专栏量化投资与机器学习

MATLAB简易验证码识别程序介绍

本推文主要识别的验证码是这种: ? ? ? 第一步: 二值化 所谓二值化就是把不需要的信息通通去除,比如背景,干扰线,干扰像素等等,只剩下需要识别的文字,让图片...

2379
来自专栏懒人开发

(4.7)James Stewart Calculus 5th Edition:Optimization Problems

根据下图,可以得到大体表达式: 已知 2x + y = 2400 求 A = xy = ? 的最大值

663
来自专栏李智的专栏

Deep learning基于theano的keras学习笔记(1)-Sequential模型

《统计学习方法》中指出,机器学习的三个要素是模型,策略和优算法,这当然也适用于深度学习,而我个人觉得keras训练也是基于这三个要素的,先建立深度模型,然后选用...

821
来自专栏量子位

如何优雅地用TensorFlow预测时间序列:TFTS库详细教程

作者:何之源 转载自知乎专栏:AI Insight 量子位 已获授权编辑发布 这篇文章中,作者详细介绍了TensorFlow Time Series(TFTS)...

5226
来自专栏数据科学与人工智能

【Python环境】使用 scikit-learn 进行机器学习的简介

概要: 该章节,我们将介绍贯穿scikit-learn使用中的“机器学习(Machine Learning)”这个词汇,并给出一些简单的学习示例。 一、机器学习...

25510

扫码关注云+社区