【13.6】几何哈希（Geometric Hashing）

几何散列(几何哈希,Geometric Hashing)是一种最初在计算机视觉中开发的，用于将几何特征与这些特征的数据库相匹配的技术，可用于许多其他领域。 即使可识别的数据库对象经历了变换或仅存在部分信息，也可以进行匹配。 该技术高效且多项式复杂度低。

物体识别(object recognition)是大多数计算机视觉研究的终极目标。 理想的物体识别系统应该能够识别图像中被部分遮挡或经历了几何变换的物体。 大多数系统将使用大型模型数据库并应用基于模型的识别。

假设您想让机器人能够识别工厂车间的所有物体和工具。 如果只有几百个对象，您可以设计这些对象的数据库并将其存储在机器人的内存中。 当机器人从摄像机或距离传感器接收其环境的感官图像时，它应该能够从存储器中快速检索出现在图像中的对象。 虽然在人类视觉中很自然，但机器人中的这项任务需要解决几个复杂的问题：

1. 获取场景中的对象相对于其初始数据库位置显示为旋转和平移，并且整个场景经历依赖于传感器的变换，例如摄像机的投影变换。( 说白了，看到的角度和方向要跟数据库保存的状态一直哦 )
2. 场景中的对象可能部分地相互遮挡，并且场景可能包括未包括在数据库中的其他对象。
3. 从数据库中检索每个单独的对象并将其与搜索匹配的观察场景进行比较在计算上是低效的。 例如，如果场景仅包含圆形对象，则检索与其匹配的矩形对象没有意义。

我们需要一种允许直接访问相关信息的方法 - 例如基于索引的方法。 例如，如果要查找长文本字符串中的单词，则可以使用由作为单个单词的函数的索引访问的表。 该表包含单词出现的字符串以及单词在字符串中的位置。 通过从表中检索所有出现情况来定位单词很容易。

这种方法最初被提出用于几何对象识别，利用基于局部几何特征的指数，这些指数对于对象变换保持不变。 这些特征是处理部分遮挡的局部特征，并且它们的索引函数对于相关变换是不变的，因为与文本中的单词不同，几何特征具有位置和方向。 十多年来，基于索引的方法已成为构建可与大型模型数据库一起运行的工作识别系统的首选方法。

在其现代化的形式中，几何散列是一种基于索引方法的方法，起源于Schwartz和Sharir的工作。这些第一步努力集中在使用边界曲线匹配技术从轮廓中识别旋转，平移和部分遮挡的二维物体。与简化的文本类比相反，实现技术更复杂，需要形状信息而不仅仅是局部特征的位置。 两种形状可以具有相同的局部特征，但在外观上完全不同。 如果形状的刚性是保守的，那么不仅局部特征而且它们的相对空间配置也很重要。

为了利用几何一致性并在二维和三维环境中处理基于模型的物体识别，Schwartz，Wolfson和Lamdan开发了一种新的几何散列技术，适用于任意点集或constellations，在各种几何变换下。 他们开发了有效的算法，用于识别由点集或由透视变换的仿射近似下的曲线表示的平面刚体，并且它们扩展了在任意变换下识别点集的技术，并将刚性3D对象与单个2D图像区分开来

One of the advantages is that geometric hashing is inherently parallel.

一、举例说明

为简单起见，此示例不会使用太多的点要素，并假设它们的描述符仅由其坐标给出。

1.1 训练阶段 Preprocessing phase

1.找到模型的特征点。 假设在具有坐标的模型图像中找到5个特征点(12,17); (45,13); (40,46); (20,35); (35,25)

图像坐标系中对象的点，以及基础坐标系的轴（P2，P4）

2.引入描述特征点位置的基础。 对于2D空间和相似性变换，基础由一对点定义。 原点（ point of origin）位于连接两个点（在我们的例子中为P2，P4）的段的中间，x’轴指向其中一个，y’是正交的并且穿过原点（ point of origin）。 选择标度使得两个基点的x’的绝对值为1。

3.描述相对于该基础的特征位置，即计算这些点到新坐标轴的投影。 坐标应该是离散的，以使更好识别噪声，我们将箱尺寸设为0.25。 因此我们得到坐标（-0.75，-1.25）;（1.00,0.00）;（ - 0.50,1.25）;（-1.00,0.00）;（0.00,0.25）

4.将基础存储在由要素索引的哈希表中（在这种情况下仅转换坐标）。 如果有更多对象要匹配，我们还应该将对象编号与基础对一起存储。

5.对不同的基础对重复该过程（步骤2）。 需要处理遮挡。 理想情况下，应列举所有非共线对。 我们在两次迭代后提供哈希表，为第二次迭代选择对（P1，P3）。

哈希表:

大多数哈希表不能将相同的键映射到不同的值。 因此在现实生活中，不会在哈希表中对基本键（1.0,0.0）和（-1.0,0.0）进行编码。

1.2 识别阶段 Recognition Phase

1.在输入图像中查找有趣的特征点。

2.选择任意的基础。 如果没有合适的任意基础，则输入图像可能不包含目标对象。

3.描述新基础中特征点的坐标。 量化获得的坐标，如前所述。

4.将输入图像中的所有变换点要素与哈希表进行比较。 如果点要素相同或相似，则增加相应基础的计数（以及对象的类型，如果有的话）。

5.对于每个基数使得计数超过某个阈值，验证其对应于在步骤2中选择的图像基础的假设。将图像坐标系转移到模型1（对于假定的对象）并尝试匹配它们。 如果成功，则找到该对象。 否则，请返回步骤2。

参考资料

• 《Geometric Hashing: An Overview》： https://web.stanford.edu/class/cs273/refs/geohash.pdf
• https://en.wikipedia.org/wiki/Geometric_hashing