Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Find_Scale_Space_Extrema questions #30

Open
caseymcc opened this issue Feb 20, 2017 · 8 comments
Open

Find_Scale_Space_Extrema questions #30

caseymcc opened this issue Feb 20, 2017 · 8 comments

Comments

@caseymcc
Copy link

I am writing an OpenCL version of the code and I have most things working in a basic manner (optimization is still needed). But when locating the extrema my implementation is locating about a 3rd less feature points and closer examination of Find_Scale_Space_Extrema in the original code I am slowing finding the subtle differences. But it has left me with some lingering questions.

First it seems that higher octave pixels position are not properly centered in regards to the original resolution. The algorithm seems to center the pixel over the top left pixel that the higher octave represents, meaning that all distance calculations seem to have a shift.

image

I would have expect more like this

image

Shouldn't there be a half pixel shift added to all the calculations for pixel position during the extrema search?

Second why does the repeat filtering only look down/up 1 level of evolution? If multiple feature points consistently show up centered in close proximity in multiple evolution (no matter how far away they are in evolution) why are they not considered the same point? It might make sense to filter any feature point clusters after sub-pixel positions are calculated.
@caseymcc
Copy link
Author

and to add on a question,

image

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?

@caseymcc
Copy link
Author

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.

@pmoulon
Copy link
Collaborator

pmoulon commented Feb 21, 2017

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

@pablofdezalc
Copy link
Owner

pablofdezalc commented Feb 24, 2017 via email

@caseymcc
Copy link
Author

caseymcc commented Feb 24, 2017 •
edited
Loading

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.

@pablofdezalc
Copy link
Owner

pablofdezalc commented Feb 27, 2017 via email

@caseymcc
Copy link
Author

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.

@pablofdezalc
Copy link
Owner

pablofdezalc commented Feb 27, 2017 via email

@hrnr hrnr mentioned this issue Aug 16, 2018
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@pablofdezalc @caseymcc @pmoulon