Editing Geometric hashing (section)

=== Example ===
For simplicity, this example will not use too many [[Feature detection (computer vision)#Corners / interest points|point features]] and assume that their descriptors are given by their coordinates only (in practice [[Visual descriptors|local descriptors]] such as [[Scale-invariant feature transform|SIFT]] could be used for indexing).

==== Training Phase ====
[[Image:GeometricHasingExample.png|thumb|right|393px|Points of the object in the image coordinate system, and axes for the coordinate system for the basis (P2,P4)]]
# Find the model's feature points. Assume that 5 feature points are found in the model image with the coordinates <math>    (12,17);</math><math>(45,    13); </math><math>   (40,    46);</math><math>     (20,    35); </math><math>    (35,    25)</math>, see the picture.
# Introduce a basis to describe the locations of the feature points. For 2D space and [[Affine transformation|similarity transformation]] the basis is defined by a pair of points. The point of origin is placed in the middle of the segment connecting the two points (P2, P4 in our example), the <math>x'</math> axis is directed towards one of them, the <math>y'</math> is orthogonal and goes through the origin. The scale is selected such that absolute value of <math>x'</math> for both basis points is 1.
# Describe feature locations with respect to that basis, i.e. compute the projections to the new coordinate axes. The coordinates should be discretised to make recognition [[Robust decision|robust]] to noise, we take the bin size 0.25. We thus get the coordinates <math>(   -0.75,   -1.25);</math><math>    (1.00,         0.00);</math><math>   (-0.50,    1.25);</math><math>   (-1.00,         0.00); </math><math>        (0.00,    0.25)</math>
# Store the basis in a [[hash table]] indexed by the features (only transformed coordinates in this case). If there were more objects to match with, we should also store the object number along with the basis pair.
# Repeat the process for a different basis pair (Step 2). It is needed to handle [[Occlusion culling|occlusions]]. Ideally, all the non-[[collinearity|colinear]] pairs should be enumerated. We provide the hash table after two iterations, the pair (P1, P3) is selected for the second one.

'''Hash Table:'''

{| class="wikitable"
|-
! Vector (<math>x'</math>, <math>y'</math>)
! basis
|-
| <math>(   -0.75,   -1.25);</math>
| (P2,P4)
|-
| <math>    (1.00,         0.00);</math>
| (P2,P4)
|-
| <math>   (-0.50,    1.25);</math>
| (P2,P4)
|-
| <math>   (-1.00,         0.00); </math>
| (P2,P4)
|-
| <math>        (0.00,    0.25)</math>
| (P2,P4)
|-
| <math>(   1.00,   0.00);</math>
| (P1,P3)
|-
| <math>    (0.00,         1.25);</math>
| (P1,P3)
|-
| <math>   (-1.00,    0.00);</math>
| (P1,P3)
|-
| <math>   (0.00,         -0.25); </math>
| (P1,P3)
|-
| <math>        (0.00,    0.50)</math>
| (P1,P3)
|}

Most hash tables cannot have identical keys mapped to different values. So in real life one won’t encode basis keys (1.0, 0.0) and (-1.0, 0.0) in a hash table.

==== Recognition Phase ====
# Find interesting feature points in the input image.
# Choose an arbitrary basis. If there isn't a suitable arbitrary basis, then it is likely that the input image does not contain the target object.
# Describe coordinates of the feature points in the new basis. Quantize obtained coordinates as it was done before.
# Compare all the transformed point features in the input image with the hash table. If the point features are identical or similar, then increase the count for the corresponding basis (and the type of object, if any).
# For each basis such that the count exceeds a certain threshold, verify the hypothesis that it corresponds to an image basis chosen in Step 2. Transfer the image coordinate system to the model one (for the supposed object) and try to match them. If successful, the object is found. Otherwise, go back to Step 2.