Geometric Hashing Technique

Geometric Hashing : It is a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an affine transformation. The models are assumed to be known in advance, and thus allow pre-processing, as follows:

- Pick a reference frame.
- Compute the 3D orthonormal basis associated with this reference frame and its shape signature (e.g. triangle sides length).
- Compute the coordinates of all the other points (in a pre-specified neighborhood) in this reference frame.
- Use each coordinate as an address to the hash (look-up) table. Store the entry [protein id, ref. frame, shape sign., point] at the hash table address.
- Repeat above steps for each model reference frame (non-collinear triplet of model points).

Recognition stage of the algorithm uses the hash table, prepared in the pre-processing step. The matching of a target object is accomplished as follows:

- For each reference frame of the target:
- Compute the 3D orthonormal basis and the shape signature associated with it.
- Compute the coordinates of all other points in the current reference frame.
- Use each coordinate to access the hash-table and retrieve all the records [protein id, ref. frame, shape sign.,point].
- For records with matching shape signature "vote" for the pair [protein, ref. frame].
- Compute the transformations of the ``high scoring'' hypotheses. For each hypothesis one can also register the pairs of matching points. This match list along with the transformation comprise a seed match.