Find_Scale_Space_Extrema questions about akaze HOT 8 OPEN

and to add on a question,

In the above picture assume both the orange and blue extremas (small circle pixel, larger circle extrema search radius) are in the same evolution and the red is in the next evolution. For simplicity lets assume orange's response is 1, red's is 2 and blue's is 3. On orange and blue's find iteration both are selected as feature points as the are the maximum for the search radius and don't overlap with each other. When red's iteration occurs red is selected as a feature (assuming orange is first in the feature list) via this code

// Compare response with the same and lower scale
      for (size_t ik = 0; ik < kpts_aux.size(); ik++) {

        if ((point.class_id - 1) == kpts_aux[ik].class_id ||
            point.class_id == kpts_aux[ik].class_id) {
          dist = sqrt(pow(point.pt.x() * ratio - kpts_aux[ik].pt.x(), 2) +
                      pow(point.pt.y() * ratio - kpts_aux[ik].pt.y(), 2));
          if (dist <= point.size) {
            if (point.response > kpts_aux[ik].response) {
              id_repeated = ik;
              is_repeated = true;
            } else {
              is_extremum = false;
            }
            break;
          }
        }
      } 

Since red's response is higher than orange's, red is listed as a repeat of orange and will later replace orange. However since there is a "break" upon finding any feature point within distance the blue point is never checked against the red. Later when this code executes

for (size_t i = 0; i < kpts_aux.size(); i++) {

is_repeated = false;
const Keypoint& point = kpts_aux[i];
for (size_t j = i + 1; j < kpts_aux.size(); j++) {

  // Compare response with the upper scale
  if ((point.class_id + 1) == kpts_aux[j].class_id) {
    dist = (point.pt - kpts_aux[j].pt).squaredNorm();

    if (dist <= point.size * point.size) {
      if (point.response < kpts_aux[j].response) {
        is_repeated = true;
        break;
      }
    }
  }
}

if (is_repeated == false) {
  kpts.push_back(point);
}

}

Blue never gets compared to red either as red is outside the distance searched by blue. Even if it had been since red is a lower value it would not have considered it a repeat. In the end we end up with 2 feature points, blue which clearly should be and red which has an extrema within its range that is higher, is this the intent?

from akaze.

Even worse I think is if red's response is 3, orange's is 2 and blue's is 1. First iteration orange and blue are selected. Next iteration red replace orange and we end up with 2 feature points red which is clear but also blue which is smallest of the 3.

from akaze.

Regarding your last message, in the OpenMVG AKAZE implementation we (@rperrot, @pmoulon) choose to do a full search in order to avoid the selection problem of the original method https://github.com/openMVG/openMVG/blob/master/src/openMVG/features/akaze/AKAZE.cpp#L243

from akaze.

from akaze.

I see where the center offset ".5*(ratio-1.0)" is used in the calculation of the final pixel location in both Find_Scale_Space_Extrema and Do_Subpixel_Refinement. However I was more questioning why is it not used in the distance calculation between pixels that are being compared.

~line 290

ratio = pow(2.0f, point.octave);
...
point.pt.x = jx;
point.pt.y = ix;
...
dist = (point.pt.x*ratio-kpts_aux[ik].pt.x)*(point.pt.x*ratio-kpts_aux[ik].pt.x) +
                 (point.pt.y*ratio-kpts_aux[ik].pt.y)*(point.pt.y*ratio-kpts_aux[ik].pt.y);

If the current pixel is in a higher octave, the pixel is calculating its distance from the top left corner of the top left pixel of the base resolution that the octave pixel represents. At octave 3 I believe that is a 4 pixel shift from center. And the keypoint is calculating from a center shifted position.

Seems the points should be immediately center shifted before the distance calculation like:

point.pt.x = jx+0.5f;
point.pt.y = ix+0.5f;

and later when the ratio is used it will be in the center of the 4 pixels it represents in the lower octave.

from akaze.

from akaze.

Thanks for the reply.

I was just checking to make sure there wasn't some mathematical/reliability/quality of result reason for the choices that were made. Performance will be a little arbitrary between the original and the GPU version and some algorithmic choices will have positive/negative results depending on the platform, so knowing that these choice have more to do with performance rather than the quality of the results gives more leeway in how I set it up for the GPU. I haven't got around to performance testing just yet as I still have some lingering result differences that I am trying to tract down. What led me down this path was that I was getting far fewer results than what the original was getting (after verifying that derivatives and evolutions were approximately the same if not exact). So I am back tracking to see where the differences are, one of the main ones was that I was comparing all levels of evolution when removing repeats rather than just 1 up/down.

I have since altered it to work only 1 up/down and I believe that results in a better quality result. I can see now that it is more than just getting more points when doing that. The end result is that comparing a high octave to a low octave based on the proximity of point size invalidates some extremas that are truly unique. In the end I think I would like to filter based on some other metric than just the point size and after sub pixel is calculated (although this obvious adds more to the processing it is orders of magnitude lower than it is on the CPU).

Ill post benchmarks once I can find the last linger issues and get a run or two at performance (some of the code I have written is grossly inadequate for the GPU).

Thanks again.

from akaze.

from akaze.