# 如何找到2D空间中的object

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 specific 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 specfied.
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-树是一种平衡二叉树。

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

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

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

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

k-d树算法就是要根据数据点确定分割线（面），然后再在kd树上进行最邻近查找（匹配）。

当两幅图像的Sift特征向量生成以后，下一步就可以采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。

ratio取值在0. 4~0. 6之间最佳(如果这个地方你要改进，最好给出一个匹配率和ration之间的关系图，这样才有说服力)，
• 小于0. 4的很少有匹配点;
• ratio=0.4 对于准确度要求高的匹配；
• ratio=0. 5　一般情况下。
• ratio=0. 6 对于匹配点数目要求比较多的匹配;
• 大于0. 6的则存在大量错误匹配点;

# k-d tree算法

Liang, Q., Borthwick, A.G.L. and Stelling, G. (2004)  Simulation of Dam and Dyke-break Hydrodynamics on Dynamically Adaptive Quadtree Grids.  International Journal for Numerical Methods in Fluids, 46: 127-162.

Posted in computer vision

Tags:

### TomTom

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