Use std::priority_queue in inpaint function for performance improvement by unnonouno · Pull Request #25122 · opencv/opencv

unnonouno · 2024-02-29T02:32:50Z

In cv::inpaint implementation, it uses a priority queue with O(n) time linear search. For large images it is very slow.
I replaced it with C++'s standard library std::priority_queue, that uses O(log(n)) algorithm.
In my use case, it is x10 faster than the original.

Pull Request Readiness Checklist

See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request

I agree to contribute to the project under Apache 2 License.
To the best of my knowledge, the proposed patch is not based on a code under GPL or another license that is incompatible with OpenCV
The PR is proposed to the proper branch
There is a reference to the original bug report and related work
There is accuracy test, performance test and test data in opencv_extra repository, if applicable
Patch to opencv_extra has the same branch name.
The feature is well documented and sample code can be built with the project CMake

asmorkalov · 2024-02-29T06:13:05Z

Perf results (11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz):

Geometric mean (ms)

                        Name of Test                           4.x-3  patched-3 patched-3 
                                                                                    vs    
                                                                                  4.x-3   
                                                                                (x-factor)
Debevec::HDR                                                  97.038   94.884      1.02   
DenoisingColored::OCL_Photo                                   166.807  163.219     1.02   
DenoisingGrayscale::OCL_Photo                                 85.176   82.939      1.03   
Mertens::HDR                                                  165.032  162.349     1.02   
Robertson::HDR                                                86.545   83.813      1.03   
inpaint::InpaintArea_InpaintingMethod::(24x24, INPAINT_NS)     7.700    7.276      1.06   
inpaint::InpaintArea_InpaintingMethod::(24x24, INPAINT_TELEA)  7.684    7.184      1.07   
inpaint::InpaintArea_InpaintingMethod::(32x32, INPAINT_NS)    11.586   11.204      1.03   
inpaint::InpaintArea_InpaintingMethod::(32x32, INPAINT_TELEA) 10.596   10.177      1.04   
inpaint::InpaintArea_InpaintingMethod::(64x64, INPAINT_NS)    37.057   36.585      1.01   
inpaint::InpaintArea_InpaintingMethod::(64x64, INPAINT_TELEA) 29.687   29.543      1.00

asmorkalov · 2024-02-29T06:15:39Z

@unnonouno Thanks a lot for the patch. Could you provide performance test case, where the improvement is visible. For now I see ~5% speedup.

asmorkalov · 2024-02-29T06:22:10Z

modules/photo/src/inpaint.cpp

    CvPriorityQueueFloat& operator=(const CvPriorityQueueFloat &); // assign disabled

 protected:
-    CvHeapElem *mem,*empty,*head,*tail;


I propose to remove CvPriorityQueueFloat as it is not public API and replace its usage with std object calls. cv::Ptr is not needed any more and you can use std::priority_queue& as parameter.

I see. That is a good idea. I'll fix it.

Actually I need to add next_order variable in the priority queue class to keep insertion order for complete compatibility. It is because std::priority_queue cannot keep insertion order when two elements have the same score.
So I think it is simpler to keep this class. If it is OK to break compatibility, i can remove this variable. Even in that case, the result is almost same. How do you think?

unnonouno · 2024-02-29T06:43:42Z

Thanks a lot. It depends on the size of the image. I'll make another performance test with a large image.

asmorkalov · 2024-02-29T07:07:38Z

Please use existing test images from opencv_extra + resize, if it's required. I do not think, that we need extra files for it.

unnonouno · 2024-03-01T23:46:19Z

I made a dot pattern mask, and the PR is significantly faster.

4.x branch:

[----------] 2 tests from Perf_InpaintingMethod_inpaintDots
[ RUN      ] Perf_InpaintingMethod_inpaintDots.inpaintDots/0, where GetParam() = INPAINT_NS
[ PERFSTAT ]    (samples=10   mean=14.11   median=14.01   min=13.95   stddev=0.25 (1.8%))
[       OK ] Perf_InpaintingMethod_inpaintDots.inpaintDots/0 (151 ms)
[ RUN      ] Perf_InpaintingMethod_inpaintDots.inpaintDots/1, where GetParam() = INPAINT_TELEA
.
.
[ PERFSTAT ]    (samples=10   mean=2716.57   median=2715.88   min=2712.82   stddev=3.40 (0.1%))
[       OK ] Perf_InpaintingMethod_inpaintDots.inpaintDots/1 (27175 ms)
[----------] 2 tests from Perf_InpaintingMethod_inpaintDots (27326 ms total)

This PR:

[----------] 2 tests from Perf_InpaintingMethod_inpaintDots
[ RUN      ] Perf_InpaintingMethod_inpaintDots.inpaintDots/0, where GetParam() = INPAINT_NS
[ PERFSTAT ]    (samples=10   mean=14.58   median=14.50   min=14.43   stddev=0.22 (1.5%))
[       OK ] Perf_InpaintingMethod_inpaintDots.inpaintDots/0 (155 ms)
[ RUN      ] Perf_InpaintingMethod_inpaintDots.inpaintDots/1, where GetParam() = INPAINT_TELEA
[ PERFSTAT ]    (samples=10   mean=63.58   median=63.48   min=63.03   stddev=0.45 (0.7%))
[       OK ] Perf_InpaintingMethod_inpaintDots.inpaintDots/1 (646 ms)
[----------] 2 tests from Perf_InpaintingMethod_inpaintDots (801 ms total)

asmorkalov · 2024-03-02T09:59:21Z

Geometric mean (ms)

                        Name of Test                           4.x-1   patch-1  patch-1  
                                                                                   vs    
                                                                                 4.x-1   
                                                                               (x-factor)
Debevec::HDR                                                   98.356  95.311     1.03   
DenoisingColored::OCL_Photo                                   164.261  164.247    1.00   
DenoisingGrayscale::OCL_Photo                                  85.242  85.831     0.99   
Mertens::HDR                                                  164.607  164.901    1.00   
Robertson::HDR                                                 88.857  88.337     1.01   
inpaint::InpaintArea_InpaintingMethod::(24x24, INPAINT_NS)     7.660    7.304     1.05   
inpaint::InpaintArea_InpaintingMethod::(24x24, INPAINT_TELEA)  7.647    7.178     1.07   
inpaint::InpaintArea_InpaintingMethod::(32x32, INPAINT_NS)     11.609  11.180     1.04   
inpaint::InpaintArea_InpaintingMethod::(32x32, INPAINT_TELEA)  10.573  10.165     1.04   
inpaint::InpaintArea_InpaintingMethod::(64x64, INPAINT_NS)     37.113  36.428     1.02   
inpaint::InpaintArea_InpaintingMethod::(64x64, INPAINT_TELEA)  29.731  29.485     1.01   
inpaintDots::Perf_InpaintingMethod::INPAINT_NS                 26.154  26.213     1.00   
inpaintDots::Perf_InpaintingMethod::INPAINT_TELEA             3841.238 88.963    43.18

asmorkalov

👍

unnonouno · 2024-03-04T00:10:13Z

Thank you for quick review!

Use std::priority_queue in inpaint function for performance improvement opencv#25122 In `cv::inpaint` implementation, it uses a priority queue with O(n) time linear search. For large images it is very slow. I replaced it with C++'s standard library `std::priority_queue`, that uses O(log(n)) algorithm. In my use case, it is x10 faster than the original. ### Pull Request Readiness Checklist See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request - [x] I agree to contribute to the project under Apache 2 License. - [x] To the best of my knowledge, the proposed patch is not based on a code under GPL or another license that is incompatible with OpenCV - [x] The PR is proposed to the proper branch - [ ] There is a reference to the original bug report and related work - [x] There is accuracy test, performance test and test data in opencv_extra repository, if applicable Patch to opencv_extra has the same branch name. - [ ] The feature is well documented and sample code can be built with the project CMake

unnonouno added 3 commits February 27, 2024 13:39

Use std priority queue

7467d78

Fix style

985ab8c

Set order to keep insertion order

9875544

asmorkalov changed the base branch from master to 4.x February 29, 2024 05:44

asmorkalov added optimization category: photo labels Feb 29, 2024

asmorkalov requested changes Feb 29, 2024

View reviewed changes

Make a new test

8ccadbc

asmorkalov approved these changes Mar 2, 2024

View reviewed changes

asmorkalov merged commit 500c55a into opencv:4.x Mar 2, 2024

unnonouno deleted the pqueue branch March 4, 2024 00:09

unnonouno restored the pqueue branch March 5, 2024 06:30

asmorkalov mentioned this pull request Mar 6, 2024

(5.x) Merge 4.x #25168

Closed

asmorkalov mentioned this pull request Apr 1, 2024

5.x merge 4.x #25305

Merged

dkurt added this to the 4.10.0 milestone Apr 8, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Use std::priority_queue in inpaint function for performance improvement#25122

Use std::priority_queue in inpaint function for performance improvement#25122
asmorkalov merged 4 commits intoopencv:4.xfrom
unnonouno:pqueue

unnonouno commented Feb 29, 2024

Uh oh!

asmorkalov commented Feb 29, 2024 •

edited

Loading

Uh oh!

asmorkalov commented Feb 29, 2024

Uh oh!

asmorkalov Feb 29, 2024

Uh oh!

unnonouno Feb 29, 2024

Uh oh!

unnonouno Mar 2, 2024

Uh oh!

unnonouno commented Feb 29, 2024

Uh oh!

asmorkalov commented Feb 29, 2024

Uh oh!

unnonouno commented Mar 1, 2024

Uh oh!

asmorkalov commented Mar 2, 2024

Uh oh!

asmorkalov left a comment

Uh oh!

unnonouno commented Mar 4, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Uh oh!

Conversation

unnonouno commented Feb 29, 2024

Pull Request Readiness Checklist

Uh oh!

asmorkalov commented Feb 29, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

asmorkalov commented Feb 29, 2024

Uh oh!

asmorkalov Feb 29, 2024

Choose a reason for hiding this comment

Uh oh!

unnonouno Feb 29, 2024

Choose a reason for hiding this comment

Uh oh!

unnonouno Mar 2, 2024

Choose a reason for hiding this comment

Uh oh!

unnonouno commented Feb 29, 2024

Uh oh!

asmorkalov commented Feb 29, 2024

Uh oh!

unnonouno commented Mar 1, 2024

Uh oh!

asmorkalov commented Mar 2, 2024

Uh oh!

asmorkalov left a comment

Choose a reason for hiding this comment

Uh oh!

unnonouno commented Mar 4, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

asmorkalov commented Feb 29, 2024 •

edited

Loading