KD-tree

如何找到2D空间中的object

找到描述object的点即可!用Quadtree

Quadtree grids, which can be classified as a particular type of unstructured grid, consist of congruent but different size of square cells, which are constructed by recursive subdivision from an initial unit square according to prescribed yet flexible criteria. 

Quadtree grid for river bifurcation geometry.

uadtree grid generation is fast, automatic and robust. The procedure:

(1) Scale the physical ow domain so that it ts within a unit square.
(2) Divide the unit square into four equal quadrant cells.
(3) Check each cell in turn, and subdivide if necessary according to specific subdivision criteria.
(4) Carry out further cell subdivision to ensure that no cell has a side length more than twice the size of its neighbours.

Two sets of subdivision criteria are used.

  1. The first relates to the discretized boundary geometry of the shallow ow domain, which is represented by a set of seeding points. Here, a cell is divided when it contains two or more seeding points and its subdivision level is less than the maximum specfied.
  2. The second set of criteria relates to internal flow features, such as the root mean square values of the free surface gradients or the depth-averaged velocity component gradients. In dynamically adapting the grid, cells are added through further subdivision (enrichment) or removed (coarsened) by comparing the root mean square values to a look up table of prescribed maximum and minimum r.m.s. gradients

Quadtree grid example of a complicated geometric shape with boundary fitness.

KD Tree

Kd-树 其实是K-dimension tree的缩写,是对数据点在k维空间中划分的一种数据结构。其实,Kd-树是一种平衡二叉树。

举一示例:

假设有六个二维数据点 = {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点位于二维空间中。为了能有效的找到最近邻,Kd-树采用分而治之的思想,即将整个空间划分为几个小部分。六个二维数据点生成的Kd-树的图为:

2D 3D KD-tree

构建完一颗KD-TREE之后,如何使用它来做KNN检索呢?用下面的20s的GIF动画来表示:

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

特征点匹配实际上就是一个通过距离函数在高维矢量之间进行相似性检索的问题。针对如何快速而准确地找到查询点的近邻,现在提出了很多高维空间索引结构和近似查询的算法,k-d树就是其中一种。

SIFT算法中做特征点匹配的时候就会利用到k-d树。

索引结构中相似性查询有两种基本的方式:一种是范围查询(range searches),另一种是K近邻查询(K-neighbor searches)。

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

特征匹配算子大致可以分为两类:

  1. 一类是线性扫描法,即将数据集中的点与查询点逐一进行距离比较,也就是穷举,缺点很明显,就是没有利用数据集本身蕴含的任何结构信息,搜索效率较低
  2. 第二类是建立数据索引,然后再进行快速匹配。因为实际数据一般都会呈现出簇状的聚类形态,通过设计有效的索引结构可以大大加快检索的速度。

索引树属于第二类,其基本思想就是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠,其代表就是k-d树;后者划分空间相互有交叠,其代表为R树。

k-d树算法就是要根据数据点确定分割线(面),然后再在kd树上进行最邻近查找(匹配)。
当查询点的邻域与分割超平面两侧空间交割时,需要查找另一侧子空间,导致检索过程复杂,效率下降。研究表明N个节点的K维k-d树搜索过程时间复杂度为:tworst=O(kN1-1/k)。
实际应用中,如SIFT特征矢量128维SURF特征矢量64维,维度都比较大,直接利用k-d树快速检索(维数不超过20)的性能急剧下下降。假设数据集的维数为D,一般来说要求数据的规模N满足N»2D,才能达到高效的搜索。因此提出了改进的k-d tree近邻搜索,其中一个比较著名的就是 Best-Bin-First(在KD-tree上找KNN ),它通过设置优先级队列和运行超时限定来获取近似的最近邻,有效地减少回溯的次数。
欧式距离
 当两幅图像的Sift特征向量生成以后,下一步就可以采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。
图1的某个关键点,通过遍历找到图像2中距离最近的两个关键点。在这两个关键点中,如果最近距离除以次近距离小于某个阙值,则判定为一对匹配点。
降低这个比例阈值,SIFT匹配点数目会减少,但更加稳定。
为了排除因为图像遮挡背景混乱而产生的无匹配关系的关键点,Lowe提出了比较最近邻距离与次近邻距离的方法,距离比率ratio小于某个阈值(0.8)的认为是正确匹配。
ratio取值在0. 4~0. 6之间最佳(如果这个地方你要改进,最好给出一个匹配率和ration之间的关系图,这样才有说服力),
  • 小于0. 4的很少有匹配点;
  • ratio=0.4 对于准确度要求高的匹配;
  • ratio=0. 5 一般情况下。
  • ratio=0. 6 对于匹配点数目要求比较多的匹配;
  • 大于0. 6的则存在大量错误匹配点;
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

生活在西班牙

自己动手丰衣足食

BlueAsteroid

Just another WordPress.com site

Jing's Blog

Just another WordPress.com site

Start from here......

我的心情魔方

天才遠私廚

希望能做一個分享各種資訊的好地方

语义噪声

西瓜大丸子汤的博客

笑对人生,傲立寰宇

Just another WordPress.com site

Where On Earth Is Waldo?

A Project By Melanie Coles

the Serious Computer Vision Blog

A blog about computer vision and serious stuff

Cauthy's Blog

paper review...

Cornell Computer Vision Seminar Blog

Blog for CS 7670 - Special Topics in Computer Vision

datarazzi

Life through nerd-colored glasses

Luciana Haill

Brainwaves Augmenting Consciousness

槑烎

1,2,∞

Dr Paul Tennent

and the university of nottingham

turn off the lights, please

A bunch of random, thinned and stateless thoughts around the Web

%d bloggers like this: