Akaze's implementation seems to have issues with rotational invariance

[stephanemagnenat]

I am trying to use Akaze for an application that searches correspondences between a template and an image seen by a camera.

As a start, I have written the common pipeline building on the excellent tutorial of Rust CV. I am using Akaze with threshold 0.001, looking for two nearest neighbors, and using a distance ratio criteria of 0.8 between the first best match and the second one (best_dist < 0.8 * next_best_dist), as suggested in the Akaze OpenCV tutorial. Besides that, I am using the functions matching and symmetric_matching from the tutorial as is.

For comparison, I created a similar pipeline in Python using OpenCV (4.7.0.72). When only scaling is involved, both Rust CV's Akaze and Open CV Akaze perform well:

Open CV, before matching: left: 2514 keypoints, right: 820 keypoints:

Rust CV, before matching: left: 5353 keypoints, right: 1480:

However, when I rotate the small image, Rust CV completely fails while Open CV works like a charm:

Open CV, before matching: left: 2514 keypoints, right: 1207 keypoints:

Rust CV, before matching: left 5353 keypoints, right: 2490

So, it looks to me that there is something very broken with the rotational invariance of RustCV's Akaze implementation.
Was this implementation ever validated against the OpenCV one?

I am also surprised by the different numbers of matches, as I would expect more similar ones between the two implementations.

[stephanemagnenat]

I believe I have found some fishy code: angs[idx] = res_y[idx].atan2(res_y[idx]). I believe it should something like res_y[idx].atan2(res_x[idx]) instead, especially when compared with the other versions. However, this correction is not enough to solve the problem.

[xd009642]

So the implementation was based off an existing Rust implementation and I think another independent implementation instead of OpenCV. I'm not sure if it was compared to OpenCVs implementation - but for more complicated algorithms I personally avoid that sometimes as OpenCV applies a lot of heuristics that may not be in the paper (from experience the OpenCV HOG adds in image pyramids and other things other implementations and the paper don't use).

The fishy line you spotted does seem to be a problem so a PR for that would be good. Does it improve the output at all?

I'm also not super familiar with this area - only mildly familiar as a casual user - so am likely not best to comment but I can try to help out. One question would be how does the matcher impact this?

I assume the visualisation is just showing the points that match between both and not the points where no match was found. Is there some worth in showing all the points identified in the rotated and non-rotated versions including unmatched ones to see if something's up. Although there are a lot of points so not sure if that's useful at all 🤔

[stephanemagnenat]

Yes showing all points is likely to be a lot. I think that showing only matching lines, as now, is enough so far. The matcher is the brute force one and the selection criteria is the same as in the OpenCV example code I'm using as a comparison.

I found other bugs in the translation from the original C++ implementation the previous Rust implementation is based on. You can follow my progress in this PR. I'm comparing the Rust code with that original implementation.

The one line correction above doesn't improve the performance so far. But correcting two more bugs (the missing reset of sum_x and sum_y to 0 and the too early increase of ang1) does improve a tiny bit the performance. We are still far from OpenCV though.

[stephanemagnenat]

Additional note, akaze_match from the original C++ implementation also works well with my test above, so it is likely the Rust translation that has mistakes.

[stephanemagnenat]

After comparing the evolutions of the same image, I can confirm that they are very different, so probably there is a bug already at that level in the Rust version.

Here are the levels 0 and 1, on the first image above:
evolutions_comparison.zip

[stephanemagnenat]

Already rust_evolution_0_Lt.exr looks suspicious. It seems that the Gaussian filter didn't work properly.

[stephanemagnenat]

I found that the gaussian_blur function gives incorrect results! Switching it for imageproc's gaussian_blur_f32 corrects the file rust_evolution_0_Lt.exr and make it look like the reference implementation.

[xd009642]

I guess it's an implementation detail of the gaussian blur regarding padding and the imageproc one applies some form of padding whereas cv doesn't

[stephanemagnenat]

No, it is worst than that, it happens in the center of the image, not in the borders. The Gaussian blur is seriously degraded. I have the impression that there is an incorrect optimization somewhere. But there are so many other bugs that at the moment I'll live with gaussian_blur_f32 that gives the same result as OpenCV now that I fixed it.

Fyi my approach to correct Rust CV's Akaze implementation is to dump the intermediate generated images (e.g. for the different maps of the evolutions) and compare with the ones from the original C++ implementation, that I have instrumented to generate the corresponding images at the same positions. That shows that, for example, the Scharr filters are also incorrect, leading to an error of a factor 40 in the estimation of the initial contrast for example.

[xd009642]

Okay, I know this is used as a key part of the VSLAM toolbox for reconstructing 3D point clouds from things like KITTI. Once the PR is ready it would be good to rerun that and make sure it still works as expected (oh god I might have to get vulkan working on my linux machine). I may also prod @vadixidav to take a look at it as he's more familiar with the code/domain than I am.

I'm aware that code like this can be tricky to test but it would be good to see some tests to catch certain issues discovered and try and prevent any regressions. I'll try and allocate some time later this week or next week to look into the gaussian blur some more

[stephanemagnenat]

Ok, good! I fully agree that it is worth checking that there is no regression.

Also, there is quite some re-implementation of features present in imageproc (e.g. Gaussian filter, Schaar filters, etc.). Personally I would prefer using the versions there, or contributing better implementations there if needed (but maybe the current implementations there might be faster now).

Also, in general, I would try to have similar functions performing similarly as their OpenCV counterparts. Of course, simplifications and differing details such as border management might be acceptable.

And I'm also all in for having tests ;-)

[xd009642]

When this crate was started imageproc/image didn't support having floats as a pixel type and iirc there had been an open issue for quite a while and it needed a big refactor to be possible. It may be that the reimplementations are no longer necessary

[stephanemagnenat]

The diffusion function nonlinear_diffusion::calculate_step is not consistent with the one of the C++ reference implementation: somehow it seems that it doesn't diffuse enough. The C++ code is very hard to read here, so relating the two is not trivial. It looks like the Rust code attempts to decompose the equation into two passes compared to the C++ code, which seems to make sense if the function is separable, but the result differ so something is lost.

Another possibility is that the Rust code was based on an earlier version of the reference implementation.

In any case, adding a missing 0.5 and changing a multiplication to an addition solves that problem! Now the non-linear space is created correctly compared to the reference implementation!

[stephanemagnenat]

@xd009642 one question: to debug I have instrumented the source codes of both the C++ and the Rust versions to dump quite some EXR images of the internal space on the way. Do we want to keep that in the future? It is quite intrusive, but if we want to ensure no regressions, we might want to keep that and compare with reference images. Is there an established best practice for such things in Rust CV?