Geometric Hashing

Reading time: 25 minutes

Table of Contents:

1. Introduction
2. How it works
3. Pseudocode
4. Complexity
5. Applications

Introduction

Geometric hashing is a computer vision technique used to detect geometric features in images and matching them to a database with such features. What makes geometric hashing stand out is that it can detect overlapping objects, objects that have gone transformation, or when only partial information is present.

How it works

Geometric hashing works by getting discrete points on 2D or 3D objects and use those points to match models stored in a hash table.

In an image where there are partially blocked objects, its interest points are extracted and based on those points we overlap two structures to find its coincidence points.

There are two stages (1) preprocessing and (2) recognition. We can see the general scheme of the algorithm below

In the pre-processing stage, target points or its geometric features will be extracted in each structure and will be stored in a hash table. the process goes as follows:

1. Extract point features of the model. each dot represents a feature’s location or a list of one or more attributes.
2. Determine the minimal number of features as its basis or find an ordered pair of points as reference .
   This allows expression of the other features and reference that remains unchanged when the model undergoes rotation, translation, or scaling.
3. There will be a tuple of the different basis points of the model. This is because it is not guaranteed that our basis points will still be present if there’s partial occlusion. Thus we make different entries per model in the hash table.
4. Use the reference points/basis as an address to the hash table and store the object info in that space.

Then for the Recognition stage, the features of the input is to be detected, extracted, and mapped to different entries in the hash table until it finds a match. the process goes as follows:

1. points of interest in the input image is extracted.
2. a pair or basis of interest points will be determined
3. Using the interest points or basis points. use this to check appropriate entrance in the hash table and vote for the pairs (the model, and your basis/interest points) appearing.
4. when a certain pair scored high then it can be the match between the object in the input image and the model from the hash table.

Pseudocode

Preprocessing Stage:

For each point in an object in a scene:
    1. define reference points or basis; 
    2. compute the coordinates of all the other points in this reference frame; 
    3. Use the reference points/basis as an address to the hash table and store the object info 
        in that space;
End

Recognition Stage:

For each point in an object from input image:
    1. define reference points or basis; 
    2. compute the coordinates of all the other points in this reference frame; 
    3. Use the reference points/basis to look up the hash table ;
    4. For each model from the table that matches the input vote for its reference frame;
    5. for the reference frames with the highest votes then save the associated transformation;
End

Complexity

Let :
M - number of known models in database
S - Number of features of each scene during recognition
C - number fo features needed to form a basis
H - complexity of accessing hash table bin, this depends on the hash table size and bin distribution.

Worst case time complexity:
Preprocessing:Θ(Mnc+1)
Recognition:Θ(HSc+1)

Applications

Geomteric hashing is introduced as an efficient method for computer vision, it has been applied to different fields like, medical imaging, molecular biology,computer-aided design, and much more. Let's discuss some of them:

Medical Imaging
Geomteric hashing is used for medical imaging. There is a problem of getting information of a specific organ from different imaging techniques like CT Scan and MRIs, this means that there are different orientations of an organ and will be an issue when matching it to a specific model .Geometric hashing is a good solution for this problem because it can match a specific image/object to a model despite undergoing occlusion or transformation.

Here are is one study that implemented geomteric hashing in medical imaging: Medical Image Registration Using Geometric Hashing by A. Guéziec, X. Pennec and N. Ayache. It compares different medical images of the same thing that is taken from differnt views and use geomteric hashing to compute 3D transformations that automatically register medical images.

Molecular Biology
Geomteric is used to solve surface and volume matching problems in molecular biology. Geomteric hashing can be used for molecular docking, a method used in structural molecular biology and computer assisted design. The goal is to to predict preferred orientation of different molecules, or to predict their predominant binding mode.

Here's a study that implemented geomteric hashing for a geometric based process for molecular docking: A geometry-based suite of moleculardocking processes by Fischer, D., Lin, S. L., Wolfson, H. L., & Nussinov, R..

Sources

Wolfson, H.J. and Rigoutsos, I. Geometric hashing: an overview. IEEE Computational Science and Engineering, Volume: 4 , Issue: 4 , Oct.-Dec. 1997 Pages:10 - 21

Barequet, G. (2002). Geometric Hashing and Its Applications. In Database and Data Communication Network Systems (pp. 277–287). Elsevier. https://doi.org/10.1016/b978-012443895-8/50010-6