图像的特征点匹配概述
特征点匹配原理
如果提取的两个特征点描述矢量间距离很小，这两个特征点在对应场景的同一位置，特征点匹配技术就是利用这个原理，从两组特征点集合中找到两辆距离最近的特征点匹配对，这个匹配对对应的是场景同一个位置。
特征点匹配问题可以归结为一个通过<font color=blue>距离函数</font>在高维矢量之间进行相似性检索的问题。针对度量空间设计的索引结构算法在进行相似度查询时只利用了距离函数的三角不等式性质，所以使用更加普遍。
特征匹配算子
- 穷举法: 将数据集中的点与查询点逐一进行距离比较。所以优点是不需要进行任何的数据预处理，操作也很简单。但是它没有利用数据集本身蕴含的任何结构信息，搜索效率相对较低。
- <font color=blue>建立数据索引</font>:先进行预处理即建立数据索引，然后在进行快速匹配。因为实际数据一般都会呈现出簇状的聚类形态，他通过设计有效的索引结构可以大大加快检索的速度。
索引结构的算法举例
- 索引树结构：对搜索空间进行层次划分，如果划分出的空间没有重叠叫Clipping法，比如<font color=blue>K-d树</font>，如果有重叠叫Overlapping法，比如R-树
- Hash法
- 空间填充曲线法
相似性查询的方式
索引结构中相似性查询有两种基本方式：
- 范围查询：从数据集中找出所有与查询点距离小于给定距离阈值的数据。
- <font color=blue>k-近邻查询</font>：从数据集中找到距离查询点最近的k个数据，当k=1时，它就是最近邻查询。
kd-树算法
kd-树是对数据点在k维空间中划分的一种数据结构。是一个二叉树，每个节点表示的是一个空间范围。
构建二叉树
kd-树种每个结点的数据类型，kd-树是一种二叉排序树
节点数据结构
| 字段 | 数据类型 | 描述 |
|---|---|---|
| Node-data | 数据矢量 | 数据集中某个数据点,是n维矢量 |
| Range | 空间矢量 | 该节点所代表的空间范围 |
| split | 整数 | 确定分割左右子节点的那个维度 |
| left | 左子树 | 这棵树上的data都小于Node-data |
| right | 右子树 | 这棵树上的data都大于Node-data |
构建kd树的流程图
start=>start: 特征点数据集
op1=>subroutine: 展开kd-树
start->op1
op2=>operation: 选择最大方差的维数赋给split
op1->op2
op3=>operation: 选取split维的中值作为阈值根节点
op2->op3
con=>condition: 数据小于中值
op3->con
op4=>operation: 左子树特征数据
op5=>operation: 右子树特征数据
sub1=>subroutine: 展开左子树
sub2=>subroutine: 展开右子树
con(yes)->op4->sub1
con(no)->op5->sub2
