Skip to content

[GSOC] Speeding-up AKAZE, part #3#9249

Merged
alalek merged 4 commits intoopencv:masterfrom
hrnr:akaze_part3
Aug 3, 2017
Merged

[GSOC] Speeding-up AKAZE, part #3#9249
alalek merged 4 commits intoopencv:masterfrom
hrnr:akaze_part3

Conversation

@hrnr
Copy link
Copy Markdown
Contributor

@hrnr hrnr commented Jul 27, 2017

cc: @bmagyar

This is currently based on #8951. I will rebase on master, once it gets in.

Currently this contains reworked version of finding scale space extremas. Speed up for images with lots of keypoints is ~3.6x.


Geometric mean

                                                   Name of Test                                                        perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf      perf      perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf   
                                                                                                                    8200996b1  b12facf48  aa5a72b46  8cc0b286c  1d3f7fe9e  c13351891  76151e566  ea089a8ab  f9c2951fa  ba071d1ad  09c7288de  d71718dea  61a35d7a6  1d42c1fa8  70b66d1b6 1a4c8989d b12facf48  aa5a72b46  8cc0b286c  1d3f7fe9e  c13351891  76151e566  ea089a8ab  f9c2951fa  ba071d1ad  09c7288de  d71718dea  61a35d7a6  1d42c1fa8  70b66d1b6  1a4c8989d 
                                                                                                                                                                                                                                                                                                      vs         vs         vs         vs         vs         vs         vs         vs         vs         vs         vs         vs         vs         vs         vs    
                                                                                                                                                                                                                                                                                                     perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf       perf   
                                                                                                                                                                                                                                                                                                  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1  8200996b1 
                                                                                                                                                                                                                                                                                                  (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor) (x-factor)
detectAndExtract::feature2d::(AKAZE_DEFAULT, "cv/detectors_descriptors_evaluation/images_datasets/leuven/img1.png") 73.555 ms  65.326 ms  45.166 ms  45.018 ms  42.333 ms  39.708 ms  39.556 ms  38.896 ms  43.073 ms  39.038 ms  37.845 ms  37.977 ms  38.303 ms  31.364 ms  33.183 ms 33.253 ms    1.13       1.63       1.63       1.74       1.85       1.86       1.89       1.71       1.88       1.94       1.94       1.92       2.35       2.22       2.21   
detectAndExtract::feature2d::(AKAZE_DEFAULT, "stitching/a3.png")                                                    58.468 ms  52.088 ms  35.045 ms  34.284 ms  32.775 ms  30.440 ms  29.703 ms  30.023 ms  31.295 ms  30.154 ms  28.886 ms  29.472 ms  28.711 ms  23.899 ms  26.021 ms 26.826 ms    1.12       1.67       1.71       1.78       1.92       1.97       1.95       1.87       1.94       2.02       1.98       2.04       2.45       2.25       2.18   
detectAndExtract::feature2d::(AKAZE_DEFAULT, "stitching/s2.jpg")                                                    276.495 ms 250.674 ms 173.192 ms 165.687 ms 162.380 ms 148.727 ms 151.201 ms 156.154 ms 169.405 ms 159.459 ms 149.227 ms 157.420 ms 151.767 ms 119.365 ms 76.862 ms 77.646 ms    1.10       1.60       1.67       1.70       1.86       1.83       1.77       1.63       1.73       1.85       1.76       1.82       2.32       3.60       3.56

@hrnr
Copy link
Copy Markdown
Contributor Author

hrnr commented Jul 27, 2017 •
edited
Loading

Notice that 1a4c898 actually slows things down. I can't really explain that.

edit: Of cause that I have removed that hack, it is better to use L2, which is used in the original algorithm. But I'm just curious, why it runs slightly slower. maybe it has got just negligible impact + measuments fluctuations?

@sovrasov sovrasov added the GSoC label Jul 31, 2017
@vpisarev
Copy link
Copy Markdown
Contributor

vpisarev commented Jul 31, 2017

@hrnr, thank you, cool results! Are you going to do any more commits or it can be reviewed and integrated?

@vpisarev vpisarev self-assigned this Jul 31, 2017
@hrnr
Copy link
Copy Markdown
Contributor Author

hrnr commented Jul 31, 2017

Yes, I'm planning to optimize further at least non-linear diffusion and Scharr kernels with nonstandard sigmas.

#8951 is ready for merge, it improves CPU perf by ~2.0x and implements basic OCL support.

@vpisarev
Copy link
Copy Markdown
Contributor

vpisarev commented Jul 31, 2017

ok, thanks! as we are preparing 3.3 now, perhaps, it makes sense to merge something now

@vpisarev
Copy link
Copy Markdown
Contributor

vpisarev commented Jul 31, 2017

👍

@vpisarev vpisarev added this to the 3.3 milestone Jul 31, 2017
@hrnr
Copy link
Copy Markdown
Contributor Author

hrnr commented Jul 31, 2017

Ok, this can go in too, but it should be rebased on #8951. When #8951 gets in I will rebase it, and it is good to go.

@alalek
Copy link
Copy Markdown
Member

alalek commented Aug 1, 2017

@hrnr #8951 is merged. Please rebase this patch.

hrnr added 3 commits August 1, 2017 16:00
@hrnr
use finding of scale extremas from fast_akaze
1479fae 
* incorporade finding of extremas and subpixel refinement from Hideaki Suzuki's fast_akaze (https://github.com/h2suzuki/fast_akaze)
* use opencv parallel framework
* do not search for keypoints near the border, where we can't compute sensible descriptors (bugs fixed in ffd9ad9, 2c53895), but the descriptors were not 100% correct. this is a better solution

this version produces less keypoints with the same treshold. It is more effective in pruning similar keypoints (which do not bring any new information), so we have less keypoints, but with high quality. Accuracy is about the same.
@hrnr
incorporate bugfix from upstream
4fb7e57 
* fix bug in subpixel refinement
* see commit db3dc22981e856ca8111f2f7fe57d9c2e0286efc in Pablo's repo
@hrnr
rework finding of scale space extremas
642fff7 
* store just keypoints positions
* store positions in uchar mask for effective spatial search for neighbours
* construct keypoints structs at the very end
@hrnr
Copy link
Copy Markdown
Contributor Author

hrnr commented Aug 1, 2017

rebased and remowed the fixup commit.

@hrnr
lower inlier threshold in test
59c6438 
* win32 has lower accuracy
@hrnr
Copy link
Copy Markdown
Contributor Author

hrnr commented Aug 2, 2017

build failed on win32, which seems to have a slightly lower accuracy. I have lowered the treshold a bit.

BTW Do you have idea why buildbot scheduled a win32 build? These builders has not been scheduled ever before for this PR.

@alalek
Copy link
Copy Markdown
Member

alalek commented Aug 2, 2017

Some builders are optional on precommit checks.

We observed that:

  • there is no testdata for kaze/akaze tests, so these tests don't check results, just write them.
  • valgrind builder detects unitialized values in akaze algorithm results

@hrnr
Copy link
Copy Markdown
Contributor Author

hrnr commented Aug 2, 2017

Testdata are an omission, but now I'm not sure if it is wise to have tests like these at all. For descriptors test the exact number of keypoints must be the same, which might be problematic as everything in AKAZE is done in floats. Detector test seems to be quite fine though.

What is the approach to these magic values controlling tests? Shouldn't we drop them (at least for AKAZE) and rely only on invarience tests, which don't control any magic values?

I'll check the problem with valgrind.

@alalek
Copy link
Copy Markdown
Member

alalek commented Aug 2, 2017

Agree, current tests look strange and currently they are broken. I will take a look on them.

@alalek
Copy link
Copy Markdown
Member

alalek commented Aug 2, 2017

@hrnr Valgrind issue: there are untouched last two bits of descriptor: 61 bytes is 488 bits, but MLDB [changes] 486 bits only.

@alalek
Copy link
Copy Markdown
Member

alalek commented Aug 3, 2017

Lets put it in and fix remaining issues.
👍

@alalek alalek merged commit 3166d0c into opencv:master Aug 3, 2017
@hrnr hrnr mentioned this pull request Aug 24, 2017
Merged
@shimat shimat mentioned this pull request Aug 15, 2018
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

@vpisarev vpisarev

Labels

GSoC

Projects

None yet

Milestone

3.3

Development

Successfully merging this pull request may close these issues.

4 participants

@hrnr @vpisarev @alalek @sovrasov