CODEWITHSUNDEEP
opencvorb
Colin747
Colin747

Reputation: 5023

ORB/BFMatcher - why norm_hamming distance?

I'm using the OpenCV implementation of ORB along with the BFMatcher. The OpenCV states that NORM_HAMMING should be used with ORB.

Why is this? What advantages does norm_hamming offer over other methods such as euclidean distance, norm_l1, etc.

Upvotes: 3

Views: 4204

Answers (3)

GuillaumeL
GuillaumeL

Reputation: 1025

When comparing descriptors in computer vision, the Euclidian distance is usually understood as the square root of the sum of the squared differences between the two vectors' elements.

The ORB descriptors are vectors of binary values. If applying Euclidian distance to binary vectors, the squared result of a single comparison would always be 1 or 0, which is not informative when it comes to estimating the difference between the elements. The overall Euclidian distance would be the square root of the sum of those ones and zeroes, again not a good estimator of the difference between the vectors.

That's why the Hamming distance is used. Here the distance is the number of elements that are not the same. As noted by Catree, you can calculate it by a simple boolean operation on the vectors, as shown in the figure below. Here D1 is a single 4-bit descriptor that we are comparing with 4 descriptors shown in D2. Matrix H is the hamming distances for each row.

A quick illustration of Hamming distance calculation in CV.

Upvotes: 5

Salim Azak
Salim Azak

Reputation: 89

L1/L2 distance is used for string based descriptors and Hamming distance is used for binary descriptors (AKAZE, ORB, BRIEF etc.).

Upvotes: 0

Catree
Catree

Reputation: 2517

ORB (ORB: an efficient alternative to SIFT or SURF) is a binary descriptor.

It should be more efficient (in term of computation) to use the HAMMING distance rather than the L1/L2 distance as the HAMMING distance can be implemented using a XOR followed by a bit count (see BRIEF: Binary Robust Independent Elementary Features):

Furthermore, comparing strings can be done by computing the Hamming distance, which can be done extremely fast on modern CPUs that often provide a specific instruction to perform a XOR or bit count operation, as is the case in the latest SSE [10] instruction set.

Of course, with a classical descriptor like SIFT, you cannot use the HAMMING distance.

You can test yourself:

  • D1=01010110
  • D2=10011010
  • L2_dist(D1,D2)=sqrt(4)=2
  • XOR(D1,D2)=11001100 ; bit_count(11001100)=4

Upvotes: 3

Related Questions