Geometric hashing

In computer science, geometric hashing is originally a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an affine transformation, though extensions exist to some other object representations and transformations. In an off-line step, the objects are encoded by treating each (non-collinear) pairs of points as a geometric basis. The remaining points can be represented in an invariant fashion with respect to this basis using two parameters. For each point, its discretized 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 (for example, from an image) 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 for object recognition in computer vision, but later was applied to different problems such as structural alignment of proteins.

Geometric Hashing in Computer Vision

Geometric Hashing is one of method used for object recognition. Let’s say that we want to check if a model image can be seen in an input image. This can be accomplished with geometric hashing. The method could be used to recognize one of the multiple objects in a base, in this case the hash table should store not only the pose information but also the number of object model in the base.

Approach

For simplicity, this example will not use too many point features.

Training Phase

1. Find the model's feature points. Assume that 5 feature points are found in the model image and that these points (and their features) are unique.
2. Introduce a basis to describe the locations of the feature points.
3. Describe feature locations with respect to that basis.
4. Store the basis in a hash table. Also, store the point locations and features in the hash table.

Hash Table:

point	Vector ($x'$, $y'$)	RGB
P1	(-1, 0)	(42, 43, 42)
P2	(-1.75, -0.75)	(64, 86, 110)
P3	(-1.25, -0.5)	(51, 52, 47)
P4	(.5, .5)	(72, 84, 69)
P5	(1, 0)	(34, 41, 34)

Recognition Phase

1. Find interesting feature points in the input image.
2. 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.
3. Perform scaling, rotation, and translation with the interest point features based on the arbitrary basis.
4. 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.
5. If the count exceeds a certain threshold, then it is likely that the target object is to be seen in the input image. Otherwise, go back to Step 2.

Input Table:

point	Vector (x, y)	RGB
P1	(-1, 0)	(60, 81, 105)
P2	(1, 0)	(23, 35, 15)
P3	(2, 0.5)	(113, 123, 83)
P4	(2, -.05)	(40, 31, 39)
P5	(3.5, -1)	(56, 68, 39)
P6	(4.5, -1.5)	(68, 80, 64)
P7	(-2, -1)	(93, 105, 69)
P8	(-0.5, -1)	(49, 50, 45)
P9	(1, -1.5)	(56, 68, 39)
P10	(2, -2)	(70, 70, 37)
P11	(3, -2.5)	(71, 82, 42)
P12	(4, -3)	(30, 39, 31)

In this example, hash table’s P1 and input table’s P1 correspond, but hash table’s P2 and input table’s P2 do not correspond.

Finding mirrored pattern

It seems that this method is only capable of handling scaling, translation, and rotation. However, the input Image may contain the object in mirror transform. Therefore, geometric hashing should be able to find the object, too. In fact, there are two ways to detect mirrored objects.

1. For the vector graph, make the left side as positive, and the right side as negative. Or multiplying the x position by -1 will give the same result.
2. Use 3 points for the basis. This allows detecting mirror images (or objects). Actually, using 3 points for the basis is another approach for geometric hashing.

See also

• Geohashing, the game suggested by Randal Munroe, have nothing to do with geometric hashing.

References

• Wolfson, H.J. & Rigoutsos, I (1997). Geometric Hashing: An Overview. IEEE Computational Science and Engineering, 4(4), 10-21.