Geometric hashing

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.

Geometric Hashing in Computer Vision

Geometric Hashing is one of method used for object recognition.

Use Geometric Hashing for Object Recognition

Let’s say that we want to check if [http://club.cyworld.com/club/board/image/imgbrd_viewurl.asp?image_url=/230024/2008/6/9/99/model_0.jpgModel Image] can be seen in [http://club.cyworld.com/club/board/image/imgbrd_viewurl.asp?image_url=/230012/2008/6/9/1/input_0.jpgInput Image] or not. This can be accomplished with Geometric Hashing.

Approach

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

Preprocessing 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. For example, see [http://club.cyworld.com/club/board/image/imgbrd_viewurl.asp?image_url=/230044/2008/6/9/89/model.gifModel Image with Input Point Features] .

2. Introduce a basis to describe the locations of the feature points. For example, see [http://club.cyworld.com/club/board/image/imgbrd_viewurl.asp?image_url=/230042/2008/6/9/22/model2.gifModel Image with Basis Image] .

3. Describe feature locations with respect to that basis: [http://club.cyworld.com/club/board/image/imgbrd_viewurl.asp?image_url=/230018/2008/6/9/67/model3.gifTransformed Point Features] ( each unit = .25).

4. Store the basis in a Hash Table. Also, store the point locations and features in the Hash Table.

Hash Table:

Recognition Phase

1. Find interesting feature points in the input image. [http://club.cyworld.com/club/board/image/imgbrd_viewurl.asp?image_url=/230019/2008/6/9/86/Input.gifInput Image with Interesting Point Features]

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. [http://club.cyworld.com/club/board/image/imgbrd_viewurl.asp?image_url=/230017/2008/6/9/13/input3.gifInput Image with Arbitrary Basis]

3. Perform scaling, rotation, and translation with the interest point features based on the arbitrary basis. [http://club.cyworld.com/club/board/image/imgbrd_viewurl.asp?image_url=/230039/2008/6/9/94/input4.gifTransformed Point Features] (Each Unit = .5)

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.

Input Table:

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.

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.

Mirror Image

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.

References

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