Editing Geometric hashing (section)

{{Distinguish |Geohashing}}

In [[computer science]], '''geometric hashing''' is a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an [[affine transformation]], though extensions exist to other object representations and transformations. In an off-line step, the objects are encoded by treating each pair of points as a geometric [[Basis (linear algebra)|basis]]. The remaining points can be represented in an [[Invariant (mathematics)|invariant]] fashion with respect to this basis using two parameters. For each point, its [[Quantization (signal processing)|quantized]] transformed coordinates are stored in the [[hash table]] as a key, and indices of the basis points as a value. Then a new pair of basis points is selected, and the process is repeated. In the on-line (recognition) step, randomly selected pairs of data points are considered as candidate bases. For each candidate basis, the remaining data points are encoded according to 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 was originally suggested in [[computer vision]] for [[object recognition]] in 2D and 3D,<ref name=Mian2006>A.S. Mian, M. Bennamoun, and R. Owens, [https://www.ncbi.nlm.nih.gov/pubmed/16986541 Three-dimensional model-based object recognition and segmentation in cluttered scenes]., IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, Oct. 2006, pp. 1584-601.</ref> but later was applied to different problems such as [[structural alignment]] of [[protein]]s.<ref>{{Cite journal|last1=Moll|first1=Mark|last2=Bryant|first2=Drew H.|last3=Kavraki|first3=Lydia E.|date=2010-11-11|title=The LabelHash algorithm for substructure matching|journal=BMC Bioinformatics|volume=11|pages=555|doi=10.1186/1471-2105-11-555|pmid=21070651|pmc=2996407|issn=1471-2105 |doi-access=free }}</ref><ref>{{Cite journal|last1=Nussinov|first1=R.|last2=Wolfson|first2=H. J.|date=1991-12-01|title=Efficient detection of three-dimensional structural motifs in biological macromolecules by computer vision techniques|journal=Proceedings of the National Academy of Sciences of the United States of America|volume=88|issue=23|pages=10495–10499|issn=0027-8424|pmid=1961713|doi=10.1073/pnas.88.23.10495|pmc=52955|doi-access=free|bibcode=1991PNAS...8810495N }}</ref>