几何散列

在计算机科学中，几何散列是一种有效寻找由经历过仿生变换的离散点代表的二维对象的方法，尽管存在对其他对象代表和变换的扩展。

在一个离线步骤中，通过将每一对点作为一个几何基础来对物体进行编码。

其余的点可以用两个参数以不变的方式表示这个基础。对于每一个点，它的量化转换坐标作为一个键存储在哈希表中，而基点的索引作为一个值。然后选择一对新的基点，并重复这一过程。

在在线（识别）步骤中，随机选择的数据点对被认为是候选基点。对于每个候选基点，剩余的数据点根据该基点进行编码，并在先前构建的表格中找到与对象的可能对应关系。

如果有足够多的数据点索引到一个一致的对象基础，那么候选基础就被接受。几何散列最初是在计算机视觉中提出的，用于二维和三维的物体识别，但后来被应用于不同的问题，如蛋白质的结构排列。

几何散列是一种用于对象识别的方法。比方说，我们想检查一个模型图像是否可以在输入图像中看到。这可以通过几何散列来完成。

该方法可用于识别一个基地中的多个物体之一，在这种情况下，散列表不仅要存储姿势信息，还要存储基地中物体模型的索引。

为了简单起见，本例将不使用过多的点特征，并假设它们的描述符只由它们的坐标给出。

找到模型的特征点。假设在模型图像中找到5个坐标为(12,17)的特征点。引入一个基础来描述特征点的位置。对于二维空间和相似性转换来说，基点是由一对点定义的。

原点放在连接两点（在我们的例子中是P2，P4）的线段的中间，x′是正交的，并通过原点。比例尺的选择是这样的，即xxx值为{displaystylex’}的xxx值为1。两个基点的xxx值为1。

描述相对于该基础的特征位置，即计算对新坐标轴的投影。坐标应该被离散化，以使识别对噪声具有鲁棒性，我们采用0.25的bin大小。

因此，我们得到的坐标是(-0.75,-1.25)。将基础存储在一个以特征为索引的哈希表中（本例中只有变换后的坐标）。

如果有更多的对象需要匹配，我们也应该将对象的编号与基础对一起存储。对不同的基础对重复这一过程（步骤2）。这是处理闭塞的需要。理想情况下，所有的非线性对都应该被列举出来。

我们在两次迭代后提供哈希表，对(P1,P3)的选择是第二次。哈希表。大多数哈希表不能有相同的键映射到不同的值。所以在现实生活中，人们不会在哈希表中编码基础键（1.0,0.0）和（-1.0,0.0）。

在输入图像中寻找有趣的特征点。选择一个任意的基础。如果没有合适的任意基，那么输入图像很可能不包含目标对象。在新的基上描述特征点的坐标。

按照之前的方法对获得的坐标进行量化。将输入图像中所有转换后的点特征与哈希表进行比较。如果点特征相同或相似，则增加相应基础的计数（以及对象的类型，如果有的话）。

对于计数超过一定阈值的每个基础，验证其是否与步骤2中选择的图像基础相对应的假设。将图像坐标系转移到模型坐标系（对于假定的物体），并尝试将它们匹配起来。

如果成功，就找到了该物体。否则，回到第2步。寻找镜像图案这个方法似乎只能处理缩放、平移和旋转。然而，输入的图像可能包含镜像变换的对象。