Geometric hashing

From Wikipedia, the free encyclopedia

In computer science, geometric hashing is a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an affine transformation. (Extensions exist to some other object representations and transformations.) In an off-line step, the objects are encoded by treating each (non-collinear) triple of points as a geometric basis. The remaining points can be represented in an invariant fashion with respect to this basis using two parameters. All such quadruples of object points are stored in a two-dimensional table that represents a discretization of these parameters. In the on-line step, randomly selected triples of data points (for example, from an image) are considered as candidate bases. For each candidate basis, the remaining data points are encoded according the basis and possible correspondences from the object are found in the previously constructed table. The candidate basis is accepted if a sufficiently large number of the data points index a consistent object basis.

Geometric hashing is used in computer vision and structural alignment of proteins.