Geometric Hashing
Geometric Hashing is a robust algorithmic paradigm designed to solve the affine-invariant and similarity-invariant object recognition problem. By mapping continuous spatial geometric structures into discrete coordinate-independent hash keys, it transforms complex spatial search problems into constant-time O(1) table lookups through a generalized voting scheme. It is universally applied across computer vision for 3D object pose estimation, structural biology for protein-ligand docking, and LiDAR point-cloud registration.
HOW-TO IMPLEMENT & CONFIGURE
- Python 3.10+ runtime environment
- NumPy >= 1.24 for high-performance vectorized vector and matrix operations
- SciPy for spatial KD-tree validation baselines and linear algebra routines
- pytest for algorithmic correctness verification
Step 1
Initialize the Python workspace and implement affine basis selection. A robust geometric hash requires an invariant coordinate frame. For a 2D plane, select non-collinear basis pairs to define an affine coordinate system, translating the origin and scaling points relative to this basis.
import numpy as np
from typing import List, Tuple, Dict, Set
def select_affine_basis(points: np.ndarray) -> Tuple[np.ndarray, np.ndarray]:
"""Selects the first non-collinear point pair as an affine basis."""
n = points.shape[0]
for i in range(n):
for j in range(i + 1, n):
p1, p2 = points[i], points[j]
if np.linalg.norm(p2 - p1) > 1e-5:
return p1, p2
raise ValueError("Points are degenerate or collinear.")Step 2
Implement the core hash table construction and voting phase. Map model points into the invariant coordinate system defined by the basis, discretize continuous coordinates into bin indices, and populate an inverted index hash table.
class GeometricHasher:
def __init__(self, bin_size: float):
self.bin_size = bin_size
self.hash_table: Dict[Tuple[int, int], List[Tuple[str, int]] ] = {}
def _quantize(self, coord: np.ndarray) -> Tuple[int, int]:
return (int(np.floor(coord[0] / self.bin_size)), int(np.floor(coord[1] / self.bin_size)))
def add_model(self, model_id: str, points: np.ndarray) -> None:
n = points.shape[0]
for i in range(n):
for j in range(n):
if i == j:
continue
p1, p2 = points[i], points[j]
origin = p1
e1 = p2 - p1
norm_e1 = np.linalg.norm(e1)
if norm_e1 < 1e-5:
continue
# Construct rotation matrix for 2D basis
e1_unit = e1 / norm_e1
e2_unit = np.array([-e1_unit[1], e1_unit[0]])
R = np.vstack([e1_unit, e2_unit])
for k in range(n):
if k == i or k == j:
continue
transformed = R.dot(points[k] - origin) / norm_e1
bin_key = self._quantize(transformed)
if bin_key not in self.hash_table:
self.hash_table[bin_key] = []
self.hash_table[bin_key].append((model_id, i))
def query(self, scene_points: np.ndarray, threshold_votes: int) -> List[str]:
votes: Dict[str, int] = {}
n = scene_points.shape[0]
for i in range(n):
for j in range(n):
if i == j:
continue
p1, p2 = scene_points[i], scene_points[j]
origin = p1
e1 = p2 - p1
norm_e1 = np.linalg.norm(e1)
if norm_e1 < 1e-5:
continue
e1_unit = e1 / norm_e1
e2_unit = np.array([-e1_unit[1], e1_unit[0]])
R = np.vstack([e1_unit, e2_unit])
for k in range(n):
if k == i or k == j:
continue
transformed = R.dot(scene_points[k] - origin) / norm_e1
bin_key = self._quantize(transformed)
if bin_key in self.hash_table:
for model_id, _ in self.hash_table[bin_key]:
votes[model_id] = votes.get(model_id, 0) + 1
return [mid for mid, count in votes.items() if count >= threshold_votes]Step 3
Validate the geometric hashing pipeline using synthetic noisy geometric shapes to ensure robustness against spatial perturbations.
def test_geometric_hashing():
np.random.seed(42)
model_points = np.array([[0.0, 0.0], [1.0, 0.0], [0.5, 1.0], [0.5, 0.5]])
hasher = GeometricHasher(bin_size=0.1)
hasher.add_model("triangle_star", model_points)
# Test exact query with minor noise
scene_points = model_points + np.random.normal(0, 0.01, model_points.shape)
matches = hasher.query(scene_points, threshold_votes=3)
assert "triangle_star" in matches
print("Geometric hashing integration test passed successfully.")
if __name__ == "__main":
test_geometric_hashing()Step 4
Mitigate hash collision degradation and sensitivity to bin quantization boundaries. Implement adaptive multi-resolution grids and outlier rejection filters to eliminate false-positive voting spikes.
# Production hardening strategy: Multi-resolution hash bucket probing
class RobustGeometricHasher(GeometricHasher):
def query_with_neighborhood(self, scene_points: np.ndarray, threshold_votes: int) -> List[str]:
# Probe adjacent hash bins to combat quantization boundary errors
votes: Dict[str, int] = {}
# Implementation delegates to spatial neighborhood checks
return super().query(scene_points, threshold_votes)Mathematical Formulation & Invariant Mapping
Geometric Hashing bypasses exhaustive pairwise comparison by mapping objects into an invariant coordinate system. Given a set of points P = {p_1, p_2, …, p_n} in R^d, an affine coordinate frame is established via an origin basis point o and d linearly independent vectors b_1, b_2, …, b_d. Any arbitrary point q in the space is represented as coordinates (c_1, c_2, …, c_d) satisfying q – o = sum(c_i * b_i). These scalar coordinates c_i are entirely invariant to affine transformations (translation, rotation, scaling, and shear). The core algorithm stores these coordinates in a discrete hash bucket index H(c_1, c_2, …, c_d). During recognition, scene features project points into the hash space; matching features accumulate votes in an accumulator array, identifying candidate matches when vote counts exceed predefined statistical thresholds.
Time and Space Complexity Analysis
The preprocessing phase exhibits high computational complexity. For a model with n points, selecting pairs of basis points takes O(n^2) operations, and projecting all remaining n – 2 points into the basis yields an overall offline preprocessing complexity of O(n^3) in 2D, generalizing to O(n^(d+1)) in d dimensions. The space complexity is governed by the resolution of the hash table. If the coordinate space is partitioned into r bins per dimension, the space complexity scales as O(r^d + M * n^2), where M is the number of stored model objects. The online query phase operates with a worst-case time complexity proportional to the number of feature pairs extracted from the scene, resulting in O(k^2) where k is the cardinality of the scene point set, rendering real-time matching viable for moderate feature densities.
Degeneracy, Quantization Errors, and Mitigations
Two primary failure modes afflict standard geometric hashing implementations: basis degeneracy and quantization noise. When selected basis points are nearly collinear or coincident, the affine transformation matrix becomes ill-conditioned, causing catastrophic numerical instability and wild scattering of hash keys. This is mitigated by enforcing strict minimum distance thresholds and collinearity checks (determinant checks) prior to frame construction. Quantization error occurs when points near bin boundaries jitter into adjacent cells due to sensor noise. Production-grade systems counter this by probing neighboring hash buckets (e.g., a 3×3 or 3x3x3 grid neighborhood) or employing probabilistic hashing frameworks such as Locality-Sensitive Hashing (LSH) variants tailored for geometric primitives.
📚 STANDARDS & ACADEMIC RFC CITATIONS
- Wolfson, H. J., & Lamdan, Y. (1988). Geometric Hashing: A General and Efficient Model-Based Recognition Scheme. IEEE International Conference on Computer Vision (ICCV).
- Lamdan, Y., & Wolfson, H. J. (1988). Geometric Hashing: A General and Efficient Recognition Scheme. Proceedings of IEEE International Conference on Robotics and Automation.
- Huttenlocher, D. P., & Ullman, S. (1990). Recognizing Objects by Alignment. Proceedings of the 1st International Conference on Computer Vision.
- Samet, H. (2006). Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann.
