Search code examples
pythonopencvdistancehamming-distance

Why cv2.NORM_HAMMING gives different value than actual hamming distance?


I am using the Hamming Distance to compute the difference among two keypoints descriptors obtained by the BRISK descriptor from opencv. I follow the suggestion of opencv documentation and use cv2.NORM_HAMMING while computing the distance as follows:

dist_opencv = cv2.norm(des_1,des_2,cv2.NORM_HAMMING)

It provides a value 87.0 among two descriptors. However, according to Hamming Distance description this is incorrect. I followed two alternative approaches (implement in python) to verify this:

dist_alt_app_1 = len(np.where(np.abs(des_1 - des_2)>0)[0])
dist_alt_app_2 = sum(el1 != el2 for el1, el2 in zip(des_1, des_2))

Both of dist_alt_app_1 and dist_alt_app_2 provides a value 43 which is not similar to 87.0 obtained from opencv. Did some search to know the reason for this difference. But did not find an explanation and clarification.

Can anyone please provide an explanation for this difference? Thanks in advance.

============= Adding an example here (to make the question more generalized):

des_1 = [180  25 195  96  96  88   0   0]
des_2 = [244  27 195  96  96 192   0   0]

for the above two descriptors, dist_opencv = 5.0 and the others (dist_alt_app_1 and dist_alt_app_2) gives 3. While 3 is the correct Hamming distance why opencv provides 5.0?


Solution

  • Your values:

    180  25 195  96  96  88   0   0 
    244  27 195  96  96 192   0   0
    

    In binary

    10110100 ‭00011001‬ ‭11000011‬ ‭01100000‬ ‭01100000‬ ‭01011000‬ 00000000 00000000
    ‭11110100‬ ‭00011011‬ ‭11000011‬ ‭01100000‬ ‭01100000‬ ‭‭11000000‬ 00000000 00000000
     ^             ^                             ^  ^^
    

    I count 5 differences => Hamming distance is 5 => OpenCV is correct


    Tip:

    You can compute the Hamming distance between two values by counting the number of "1" after XOR-ing the two values. Pseudocode:

    HammingDistance = count_1(xor(val1, val2))
    
    01011000
    ‭‭11000000‬ 
    -------- xor
    10011000 => it has 3 "1"