图像局部不变性特征与描述笔记

数字图像处理

---

图像的特征点匹配概述

特征点匹配原理

如果提取的两个特征点描述矢量间距离很小，这两个特征点在对应场景的同一位置，特征点匹配技术就是利用这个原理，从两组特征点集合中找到两辆距离最近的特征点匹配对，这个匹配对对应的是场景同一个位置。
特征点匹配问题可以归结为一个通过距离函数在高维矢量之间进行相似性检索的问题。针对度量空间设计的索引结构算法在进行相似度查询时只利用了距离函数的三角不等式性质，所以使用更加普遍。

特征匹配算子

1. 穷举法: 将数据集中的点与查询点逐一进行距离比较。所以优点是不需要进行任何的数据预处理，操作也很简单。但是它没有利用数据集本身蕴含的任何结构信息，搜索效率相对较低。
2. 建立数据索引:先进行预处理即建立数据索引，然后在进行快速匹配。因为实际数据一般都会呈现出簇状的聚类形态，他通过设计有效的索引结构可以大大加快检索的速度。

索引结构的算法举例

1. 索引树结构：对搜索空间进行层次划分，如果划分出的空间没有重叠叫Clipping法，比如K-d树，如果有重叠叫Overlapping法，比如R-树
2. Hash法
3. 空间填充曲线法

相似性查询的方式

索引结构中相似性查询有两种基本方式：

1. 范围查询：从数据集中找出所有与查询点距离小于给定距离阈值的数据。
2. k-近邻查询：从数据集中找到距离查询点最近的k个数据，当k=1时，它就是最近邻查询。

---

kd-树算法

kd-树是对数据点在k维空间中划分的一种数据结构。是一个二叉树，每个节点表示的是一个空间范围。

优点

比较容易刻画数据的聚簇性质，适应数据集的统计分布特性。

构建二叉树

kd-树种每个结点的数据类型，kd-树是一种二叉排序树

节点数据结构

字段	数据类型	描述
Node-data	数据矢量	数据集中某个数据点,是n维矢量
Range	空间矢量	该节点所代表的空间范围
split	整数	确定分割左右子节点的那个维度
left	左子树	这棵树上的data都小于Node-data
right	右子树	这棵树上的data都大于Node-data

构建kd树的流程图

二分法

举个例子

数据集{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1. 确定split域，也就是第一维，因为数据集里有两维，第一维的方差是39，第二维的方差是28.63。在第一维上的方差最大。
2. 确定选定维度的中值；这里第一维的序列是2,4,5,7,8,9 ，这里选的是7也就是我们选到的根节点的数据室（7,2）
3. 比较剩下的数据，在指定维度上的分量如果大于根节点的值那就在右子树，如果小于或等于根节点的值那就在左子树上。
4. 递归分下去。

匹配对提纯