How does vl_ubcmatch work technically?

Question

I am reading through vl_ubcmatch's function source code, provided here, and I am trying to understand, how does it compute the score, and how does it work technically internally.

However, this C code has these macros, weird ## variables like, and what not, that I don't have experience with. So the main problem here is rather my incompetency in C. If possible, could somebody tell me, how does vl_ubcmatch work exactly? How does it compare two descriptors?

Answer 1

This is explained in Sections 7.1 and 7.2 of Distinctive Image Features from Scale-Invariant Keypoints.

Documentation for the function is here: http://www.vlfeat.org/mdoc/VL_UBCMATCH.html

A match from feature d1 in image 1 to feature d2 in image 2 is used only if the distance between d1 and d2 is significantly smaller than the distance to d1 and any other feature in image 2. The match needs to be significantly better than any other potential match. "Significant" is defined by the threshold that you pass to the VL_UBCMATCH function.

Section 7.2 refers to an approximate nearest neighbor search structure, but VL_UBCMATCH doesn't use this:

for(k1 = 0 ; k1 < K1 ; ++k1, L1_pt += ND ) {                        \
                                                                    \
  PROMOTE_##MXC best = maxval ;                                     \
  PROMOTE_##MXC second_best = maxval ;                              \
  int bestk = -1 ;                                                  \
                                                                    \
  /* For each point P2[k2] in the second image... */                \
  for(k2 =  0 ; k2 < K2 ; ++k2, L2_pt += ND) {                      \
                                                                    \
    int bin ;                                                       \
    PROMOTE_##MXC acc = 0 ;                                         \
    for(bin = 0 ; bin < ND ; ++bin) {                               \
      PROMOTE_##MXC delta =                                         \
        ((PROMOTE_##MXC) L1_pt[bin]) -                              \
        ((PROMOTE_##MXC) L2_pt[bin]) ;                              \
      acc += delta*delta ;                                          \
    }                                                               \
                                                                    \
    /* Filter the best and second best matching point. */           \
    if(acc < best) {                                                \
      second_best = best ;                                          \
      best = acc ;                                                  \
      bestk = k2 ;                                                  \
    } else if(acc < second_best) {                                  \
      second_best = acc ;                                           \
    }                                                               \
  }                                                                 \
                                                                    \
  L2_pt -= ND*K2 ;                                                  \
                                                                    \
  /* Lowe's method: accept the match only if unique. */             \
  if(thresh * (float) best < (float) second_best &&                 \
     bestk != -1) {                                                 \
    pairs_iterator->k1 = k1 ;                                       \
    pairs_iterator->k2 = bestk ;                                    \
    pairs_iterator->score = best ;                                  \
    pairs_iterator++ ;                                              \
  }                                                                 \
}

Here's the pseudocode:

matches = []
For each descriptor k1 in image 1:
    closest_match_distance = Infinity
    second_closest_match_distance = Infinity
    best_match = None
    For each descriptor k2 in image 2:
        distance_squared = d(k1, k2)
        if (distance_squared < closest_match_distance):
            second_closest_match_distance = closest_match_distance
            closest_match_distance = distance_squared
            best_match = k2
    If (threshold * closest_match_distance <
      second_closest_match_distance AND best_match != None):
        matches.Insert((k1, best_match, closest_match_distance))
return matches