Geometric hashing

<h2 id="geometric-hashing-in-computer-vision">Geometric hashing in computer vision</h2>
<p>Geometric hashing is a 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 index of object model in the base.
</p>
<h3>Example</h3>
<p>For simplicity, this example will not use too many <a href="/facts/Feature_detection_(computer_vision)/GdfWRp5U">point features</a> and assume that their descriptors are given by their coordinates only (in practice <a href="/facts/Visual_descriptors/rQ6qc984">local descriptors</a> such as <a href="/facts/Scale-invariant_feature_transform/oX14fcpr">SIFT</a> could be used for indexing).
</p>
<h4>Training Phase</h4>

<ol><li>Find the model's feature points. Assume that 5 feature points are found in the model image with the coordinates 
  
    
      
        (
        12
        ,
        17
        )
        ;
      
    
    {\displaystyle (12,17);}

(
        45
        ,
        13
        )
        ;
      
    
    {\displaystyle (45,13);}

(
        40
        ,
        46
        )
        ;
      
    
    {\displaystyle (40,46);}

(
        20
        ,
        35
        )
        ;
      
    
    {\displaystyle (20,35);}

(
        35
        ,
        25
        )
      
    
    {\displaystyle (35,25)}
  
, see the picture.</li>
<li>Introduce a basis to describe the locations of the feature points. For 2D space and <a href="/facts/Affine_transformation/BD7yDr10">similarity transformation</a> 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 
  
    
      
        
          x
          ′
        
      
    
    {\displaystyle x'}
  
 axis is directed towards one of them, the 
  
    
      
        
          y
          ′
        
      
    
    {\displaystyle y'}
  
 is orthogonal and goes through the origin. The scale is selected such that absolute value of 
  
    
      
        
          x
          ′
        
      
    
    {\displaystyle x'}
  
 for both basis points is 1.</li>
<li>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 <a href="/facts/Robust_decision/Y3nm5Do6">robust</a> to noise, we take the bin size 0.25. We thus get the coordinates 
  
    
      
        (
        −
        0.75
        ,
        −
        1.25
        )
        ;
      
    
    {\displaystyle (-0.75,-1.25);}

(
        1.00
        ,
        0.00
        )
        ;
      
    
    {\displaystyle (1.00,0.00);}

(
        −
        0.50
        ,
        1.25
        )
        ;
      
    
    {\displaystyle (-0.50,1.25);}

(
        −
        1.00
        ,
        0.00
        )
        ;
      
    
    {\displaystyle (-1.00,0.00);}

(
        0.00
        ,
        0.25
        )
      
    
    {\displaystyle (0.00,0.25)}
  
</li>
<li>Store the basis in a <a href="/facts/Hash_table/Ht4ptDPF">hash table</a> 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.</li>
<li>Repeat the process for a different basis pair (Step 2). It is needed to handle <a href="/facts/Occlusion_culling/hk9dqmDE">occlusions</a>. Ideally, all the non-<a href="/facts/Collinearity/SxbVBJYR">colinear</a> pairs should be enumerated. We provide the hash table after two iterations, the pair (P1, P3) is selected for the second one.</li></ol>
<p>Hash Table:
</p>
<table><tbody><tr><th>Vector (                              x          ′                      {\displaystyle x'}  ,                               y          ′                      {\displaystyle y'}  )</th><th>basis</th></tr><tr><td>                    (        −        0.75        ,        −        1.25        )        ;              {\displaystyle (-0.75,-1.25);}  </td><td>(P2,P4)</td></tr><tr><td>                    (        1.00        ,        0.00        )        ;              {\displaystyle (1.00,0.00);}  </td><td>(P2,P4)</td></tr><tr><td>                    (        −        0.50        ,        1.25        )        ;              {\displaystyle (-0.50,1.25);}  </td><td>(P2,P4)</td></tr><tr><td>                    (        −        1.00        ,        0.00        )        ;              {\displaystyle (-1.00,0.00);}  </td><td>(P2,P4)</td></tr><tr><td>                    (        0.00        ,        0.25        )              {\displaystyle (0.00,0.25)}  </td><td>(P2,P4)</td></tr><tr><td>                    (        1.00        ,        0.00        )        ;              {\displaystyle (1.00,0.00);}  </td><td>(P1,P3)</td></tr><tr><td>                    (        0.00        ,        1.25        )        ;              {\displaystyle (0.00,1.25);}  </td><td>(P1,P3)</td></tr><tr><td>                    (        −        1.00        ,        0.00        )        ;              {\displaystyle (-1.00,0.00);}  </td><td>(P1,P3)</td></tr><tr><td>                    (        0.00        ,        −        0.25        )        ;              {\displaystyle (0.00,-0.25);}  </td><td>(P1,P3)</td></tr><tr><td>                    (        0.00        ,        0.50        )              {\displaystyle (0.00,0.50)}  </td><td>(P1,P3)</td></tr></tbody></table>
<p>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.
</p>
<h4>Recognition Phase</h4>
<ol><li>Find interesting feature points in the input image.</li>
<li>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.</li>
<li>Describe coordinates of the feature points in the new basis. Quantize obtained coordinates as it was done before.</li>
<li>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).</li>
<li>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.</li></ol>
<h3>Finding mirrored pattern</h3>
<p>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.  There are two ways to detect mirrored objects.
</p>
<ol><li>For the vector graph, make the left side positive, and the right side negative. Multiplying the x position by -1 will give the same result.</li>
<li>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.</li></ol>
<h3>Geometric hashing in higher-dimensions</h3>
<p>Similar to the example above, hashing applies to higher-dimensional data. For three-dimensional data points, three points are also needed for the basis. The first two points define the x-axis, and the third point defines the y-axis (with the first point). The z-axis is perpendicular to the created axis using the right-hand rule. Notice that the order of the points affects the resulting basis
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Perceptual_hashing/0Rrjl0YD">Perceptual hashing</a></li></ul>

<ul><li>Wolfson, H.J. & Rigoutsos, I (1997). <a href="http://graphics.stanford.edu/courses/cs468-01-winter/papers/wr-ghao-97.pdf">Geometric Hashing: An Overview.</a> IEEE Computational Science and Engineering, 4(4), 10-21.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>A.S. Mian, M. Bennamoun, and R. Owens, Three-dimensional model-based object recognition and segmentation in cluttered scenes., IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, Oct. 2006, pp. 1584-601. <a href="https://www.ncbi.nlm.nih.gov/pubmed/16986541" target="_blank">https://www.ncbi.nlm.nih.gov/pubmed/16986541</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Moll, Mark; Bryant, Drew H.; Kavraki, Lydia E. (2010-11-11). "The LabelHash algorithm for substructure matching". BMC Bioinformatics. 11: 555. doi:10.1186/1471-2105-11-555. ISSN 1471-2105. PMC 2996407. PMID 21070651. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2996407" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2996407</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Nussinov, R.; Wolfson, H. J. (1991-12-01). "Efficient detection of three-dimensional structural motifs in biological macromolecules by computer vision techniques". Proceedings of the National Academy of Sciences of the United States of America. 88 (23): 10495–10499. Bibcode:1991PNAS...8810495N. doi:10.1073/pnas.88.23.10495. ISSN 0027-8424. PMC 52955. PMID 1961713. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC52955" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC52955</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Geometric hashing open-in-new

Geometric hashing