几何哈希是一种用于计算机视觉和模式识别的方法，通过将场景中的几何特征与预计算的数据库进行匹配来识别物体。它由Yehezkel Lamdan和Haim J. Wolfson在1980年代末开发，并在基于模型的目标识别领域产生了重要影响。该技术以其处理部分遮挡的能力以及对常见几何变换的不变性而著称，使其成为早期模板匹配方法的稳健替代方案。
几何哈希的核心思想是将每个物体模型表示为一组特征点（如角点、边缘或兴趣点），并将其空间关系编码到哈希表中。在识别过程中，通过提取查询场景自身的特征点来处理场景，并利用哈希表对候选模型进行投票。这一投票过程使系统能够快速推测可能存在的模型，即使只有物体特征的一个子集可见。
历史发展
几何哈希源于1980年代计算几何和计算机视觉的研究。Lamdan和Wolfson在1988年发表于IEEE国际计算机视觉会议的论文《几何哈希：一种通用且高效的基于模型的识别方案》中引入了这一概念。该方法建立在早期哈希和几何匹配工作的基础上，但引入了一种新颖的模型特征索引方式，使识别既快速又对噪声具有容忍性。
该技术在1990年代获得了广泛关注，特别是在工业零件检测、机器人和医学成像等应用中。它还被改编用于分子生物学中的蛋白质结构比较，其中原子或残基的几何排列可以在不同分子之间进行匹配。截至2020年代初，几何哈希仍是计算机视觉中的基础概念，尽管在许多实际应用中已被基于深度学习的方法所取代。
算法概述
几何哈希算法分为两个阶段：预处理和识别。在预处理阶段，对于数据库中的每个模型，提取一组特征点。对于每对有序点（或一个基，通常为定义坐标框架的两个点），算法计算所有其他点相对于该基的坐标。这些相对坐标随后存储在哈希表中，并以基和模型标识符作为关联值。
在识别过程中，提取场景的特征点，算法选择一对随机点作为候选基。它使用该基计算剩余场景点的相对坐标，并在哈希表中查找它们。每次匹配都会为相应的模型和基增加一票。在处理所有可能的基（或采样子集）后，投票数最高的模型被选为最佳匹配。算法随后通过将模型对齐到场景并检查一致性来验证匹配。
这种方法对平移、旋转和均匀缩放具有不变性，因为相对坐标是在归一化框架中计算的。它还能处理部分遮挡，因为只需模型特征的一个子集存在于场景中，即可累积足够的票数。
在计算机视觉中的应用
几何哈希已应用于多个需要稳健目标识别的领域。在工业自动化中，它用于定位传送带上的零件，这些零件可能相对于参考物旋转或缩放。在机器人领域，它帮助机器人识别和抓取杂乱环境中的物体。该方法对遮挡的容忍性使其适用于识别堆叠中部分隐藏物体的任务。
在医学成像中，几何哈希用于对齐X射线或MRI图像中的解剖结构，辅助图像配准和手术规划等任务。在分子生物学中，它促进了蛋白质三维结构的比较，目标是在氨基酸序列变化的情况下找到相似的折叠模式。这些应用利用了该技术在不要求单个点之间显式对应的情况下匹配几何配置的能力。
与现代方法的比较
随着2010年代Machine learning和Deep learning的兴起，几何哈希在主流计算机视觉中的重要性有所下降。基于Neural network架构的方法，特别是Convolutional neural network和Transformer (architecture)模型，在大规模识别任务中取得了更高的准确性。这些现代方法直接从数据中学习特征表示，而几何哈希依赖于手工设计的几何特征和显式空间索引。
然而，几何哈希在某些场景中仍具有优势。它不需要大量训练数据，使其在只有少量物体示例时非常有用。它还提供可解释的匹配结果，因为投票过程揭示了哪些特征对识别有贡献。相比之下，深度学习模型通常表现为黑盒。截至2020年代中期，将几何哈希与Machine learning结合用于特征提取的混合方法已被探索，但仍处于小众地位。
局限性与扩展
几何哈希的一个局限性是它对特征点提取质量的敏感性。如果特征检测器产生噪声或不一致的点，哈希表查找将变得不可靠。该算法在模型数量增加时扩展性较差，因为哈希表可能变得庞大且占用大量内存。为解决这一问题，已提出扩展方案，例如使用随机基或分层哈希来减少搜索空间。
另一种扩展涉及使用仿射或投影变换，而不仅仅是相似变换，这拓宽了适用场景的范围。一些变体结合颜色或纹理信息与几何特征以提高区分度。尽管有这些增强，速度和稳健性之间的基本权衡仍然是一个挑战，该技术通常与其他方法结合使用，例如现代系统中的基于Data Augmentation的训练。
遗产与影响
几何哈希影响了计算机视觉的后续发展，包括大规模图像检索中的哈希使用以及SIFT（尺度不变特征变换）等局部特征描述符的设计。将几何不变量索引到哈希表中的思想在许多后续算法中可见。它还通过展示几何推理如何在计算系统中高效实现，为更广泛的Artificial intelligence领域做出了贡献。
如今，几何哈希在计算机视觉课程中被作为基于模型识别的经典示例进行教学。其原理在专业应用中仍然相关，例如点云中的三维物体识别和计算机辅助设计中的形状匹配。尽管它不再主导该领域，但其概念性贡献仍然是Artificial intelligence和模式识别历史的重要组成部分。