Ask Your Question
6

The difference between BruteForce-Hamming and BruteForce-HammingLUT

asked 2013-05-31 10:09:26 -0600

MysticBE gravatar image

I read the document about the matching, and googled the internet for the difference between BruteForce-Hamming and BruteForce-HammingLUT, but could not find a good answer anywhere.

The only thing I could get back from my own data is that the BruteForce-Hamming is about 1 ms faster then the other. But the matching results are virtually the same.

edit retag flag offensive close merge delete

Comments

1

LUT typically stands for "look-up table" which may explain the speed gain. Don't know if there's a difference...

Guanta gravatar imageGuanta ( 2013-06-01 15:53:07 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
6

answered 2013-06-03 09:36:40 -0600

czerhtan gravatar image

I cannot find the exact source where the two variations are implemented, but usually, the Hamming distance algorithm relies on two steps: an XOR operation between two bit vectors, and a population count on the resulting bit vector.

The XOR is pretty straight-forward on any type of architecture, but the popcount algorithm can sometimes be speeded up by using processor-specific instruction sets (such as SSE2/SSSE3/...). When these instruction sets are not available/supported, it is also possible to use a look-up table in an attempt to speed up the 'naive' algorithm.

If, in your case, the regular Hamming variation is faster, I would assume your OpenCV bins were built with SSE2/SSSE2/... support enabled, and the algorithm defaults to the accelerated version. On low-end processors, the LUT version is usually faster (although it always depends on the LUT size and the bit vector length).

Info on Hamming dist: http://en.wikipedia.org/wiki/Hamming_distance

Info on 'popcount' algorithms and accelerated implementations: http://wm.ite.pl/articles/sse-popcount.html

edit flag offensive delete link more

Comments

+1. Nice explanation.

SR gravatar imageSR ( 2013-06-05 03:17:33 -0600 )edit

Question Tools

Stats

Asked: 2013-05-31 10:09:26 -0600

Seen: 6,703 times

Last updated: Jun 03 '13