Geometric Hashing

May 27, 2002

Annie Christian

ÝÝÝÝÝÝÝÝÝÝÝ Geometric hashing allows a computer to more easily recognize 2 and 3D objects by comparing these objects to a previously defined database of known objects.Ý A simple example of geometric hashing would be a square.Ý Previously, very simplistic algorithms would calculate the pixels on a known square and then traverse a screen pixel by pixel comparing the known points to the screen until another square was found.Ý In geometric hashing, two points on the square are chosen, and a graph is drawn from those two points.Ý The graph is then scaled so that the distance between the two points is equal to 1.Ý An x-axis is used to connect the two points and a y-axis is drawn at the midpoint between the two points.Ý At this time, a third point can be found in the square and plotted under the parameters of the newly formed graph.Ý The points are then stored in a hash table with three parameters, the model number, and the x and y coordinates of the third point.Ý The same computation is done for all of the pictureís pairs of points.Ý All of this can be done separately, and should not affect the running time of the algorithm.

ÝÝÝÝÝÝÝÝÝÝÝ Once the database has been formed, a computer can begin to recognize objects.Ý By plotting points on an object just as it would have when making the database, the computer can come up with the information it would need for a hash table entry.Ý The computer then compares this information to its database.Ý Each figure that matches receives a point.Ý The computer repeats these steps for every pair of points in the objects it is attempting to recognize.Ý Afterwards, the number of points each known shape received can be tallied.Ý This algorithm does not necessarily pinpoint exactly which shape it has recognized, but it does return a list of shapes that are similar.Ý

Week1