Geometric hashing

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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Hash function — A hash function is any well defined procedure or mathematical function for turning some kind of data into a relatively small integer, that may serve as an index into an array. The values returned by a hash function are called hash values, hash… …   Wikipedia

  • Хеширование — Хеш функция, отображающая множество имён в множество натуральныых чисел Хеширование (иногда «хэширование», англ. hashing)  преобразование по детерменированному алгоритму входного массива данных прои …   Википедия

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Object recognition (computer vision) — Feature detection Output of a typical corner detection algorithm …   Wikipedia

  • Hash — may refer to:* Hash symbol, #, called number sign or pound sign in the USA and Canada * Hashish, a psychoactive drug derived from the Cannabis plant * Hash (food), a coarse chunky mixture of beef and other things, e.g. corned beef hash ; cf. Hash …   Wikipedia

  • List of computer vision topics — This is a list of computer vision and image processing topics Contents 1 Image enhancement 2 Transformations 3 Filtering, Fourier and wavelet transforms and image compression …   Wikipedia

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”