Geometric Hashing

In computer science, geometric hashing is a method for efficiently searching for two-dimensional objects represented by discrete points that have undergone an affine transformation, although extensions exist for other object representations and transformations. In the offline stage, objects are encoded by treating every pair of points as a geometric basis. The remaining points can be represented invariantly with respect to this basis using two parameters. For each point, its quantized transformed coordinates are stored in a hash table as a key, with the indices of the basis points stored as the value. A new pair of basis points is then chosen, and the process is repeated. In the online (recognition) stage, randomly chosen pairs of data points are treated as candidate bases. For each candidate basis, the remaining data points are encoded according to that basis, and possible correspondences to the object are looked up in the previously built table. A candidate basis is accepted if a sufficiently large number of data points index a consistent basis of the object.

Geometric hashing was originally proposed in computer vision for recognizing objects in 2D and 3D, but was later applied to a variety of problems, such as protein structural alignment.

Geometric hashing in computer vision

Geometric hashing is a technique used for object recognition. Suppose we want to check whether a model image is visible in an input image. This can be achieved using geometric hashing. The method can also be used to recognize one of several objects in a database, in which case the hash table must store not only pose information but also the index of the object model in the database.

Example

For simplicity, this example will not use too many point objects, and it is assumed that their descriptors are given only by their coordinates (in practice, local descriptors such as SIFT can be used for indexing).

Learning phase

Object points in the image coordinate system and the axes of the basis coordinate system (P2, P4)

1. Find the feature points of the model. Suppose that 5 feature points are detected in the model image, with coordinates (12,17); (45,13); (40,46); (20,35); (35,25) , see the picture.
2. Introduce a basis to describe the arrangement of the feature points. For two-dimensional space and a similarity transformation, the basis is defined by a pair of points. The origin is placed at the midpoint of the segment connecting the two points (P2, P4 in our example). the axis is directed toward one of them, is orthogonal to it and passes through the origin. The scale is chosen so that the absolute value of for both basis points equals 1.
3. Describe the arrangement of the objects relative to this basis, i.e. compute the projections onto the new coordinate axes. The coordinates must be quantized so that recognition is robust to noise; we take a bin size of 0.25. Thus we obtain the coordinates (−0.75,−1.25); (1.00,0.00); (−0.50,1.25); (−1.00,0.00); (0.00,0.25)
4. Store the basis in a hash table indexed by objects (in this case, only by the transformed coordinates). If there were more objects to match, we would also need to store the object number together with the basis pair.
5. Repeat the process for another basis pair (step 2). This is necessary to handle occlusions. Ideally, all non-collinear pairs should be enumerated. Below is the hash table after two iterations; for the second one, the pair (P1, P3) is chosen.

Hash table:

Most hash tables cannot have identical keys mapped to different values. Thus, in real life, the basis keys (1.0, 0.0) and (-1.0, 0.0) are not encoded in the hash table.

Recognition phase​​

1. Find interesting features in the input image.
2. Choose an arbitrary basis. If no suitable arbitrary basis exists, it is quite likely that the input image does not contain the target object.
3. Describe the coordinates of the feature points in the new basis. Quantize the resulting coordinates as before.
4. Compare all transformed point objects in the input image with the hash table. If the point objects are identical or similar, increment the counter for the corresponding basis (and object type, if any).
5. For each basis whose value exceeds a certain threshold, test the hypothesis that it corresponds to the image basis chosen in step 2. Transform the image coordinate system into the model coordinate system (for the assumed object) and try to match them. If successful, the object has been found. Otherwise, return to step 2.

Finding a mirrored pattern

It might seem that this method can only handle scaling, translation and rotation. However, the input image may contain the object under a mirror transformation. Therefore, geometric hashing must also be able to find the object in this case. There are two ways to detect mirrored objects.

1. For vector graphics, make the left side positive and the right side negative. Multiplying the x-position by -1 will give the same result.
2. Take 3 points as the basis. This makes it possible to detect mirror images (or objects). In fact, using three points as the basis is another approach to geometric hashing.

Geometric hashing in higher dimensions

As in the example above, hashing can be applied to higher-dimensional data. For three-dimensional data points, three points are likewise needed as a basis. The first two points define the X axis, and the third point defines the Y axis (together with the first point). The Z axis is perpendicular to the resulting axes, following the right-hand rule. Note that the order of the points affects the resulting basis.

See also

• Perceptual hashing