imgproc: optimise local cost computation in IntelligentScissorsMB::buildMap by cpoerschke · Pull Request #21959 · opencv/opencv

cpoerschke · 2022-05-08T21:07:01Z

When reading the code I noticed a TODO(opt) comment, this pull request is for that.

https://github.com/opencv/opencv/blob/4.5.5/modules/imgproc/src/intelligent_scissors.cpp#L628

float cost = cost_q + local_cost(q, r);  // TODO(opt): compute partially until cost < cost_r

Notes

imgproc: fix two typos (imput, magnutude) #21941 and this pull request change the same non-test files. However, the changes themselves don't overlap i.e. there should be no merge conflicts.
Based on https://github.com/opencv/opencv/wiki/Branches#which-branch-should-i-target-my-pr this pull request here could be for 3.4 instead of 4.x branch. However, it is for 4.x since 3.4 doesn't have the intelligent scissors code.

Test run snippet

$ export OPENCV_TEST_DATA_PATH=../opencv_extra/testdata

$./bin/opencv_perf_imgproc --gtest_filter="TestIntelligentScissorsMB*" 
...
[ RUN      ] TestIntelligentScissorsMB_buildMap_setComputeFullLocalCost.buildMap_setComputeFullLocalCost/0, where GetParam() = false
...
[ PERFSTAT ]    (samples=10   mean=5459.27   median=5452.70   min=5410.39   stddev=34.39 (0.6%))
[       OK ] TestIntelligentScissorsMB_buildMap_setComputeFullLocalCost.buildMap_setComputeFullLocalCost/0 (54604 ms)
[ RUN      ] TestIntelligentScissorsMB_buildMap_setComputeFullLocalCost.buildMap_setComputeFullLocalCost/1, where GetParam() = true
...
[ PERFSTAT ]    (samples=10   mean=5635.78   median=5634.03   min=5621.81   stddev=9.53 (0.2%))
[       OK ] TestIntelligentScissorsMB_buildMap_setComputeFullLocalCost.buildMap_setComputeFullLocalCost/1 (56360 ms)
...

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

cpoerschke · 2022-05-21T21:13:30Z

Here are some more notes on the optimisation.

The local_cost(p, q) is computed as the sum of three terms

weight_non_edge_compute * non_edge_feature.at<uchar>(q) +
weight_gradient_direction * fD +
weight_gradient_magnitude * fG

and the optimisation uses the non-negativity of the terms and the fact that we don't need the exact cost if the cost exceeds the threshold. E.g. if term1 increases the cost above the threshold then also adding the non-negative terms term2 and term3 cannot decrease the cost to below the threshold and so we can omit computing and adding term2 and term3.

Supporting links w.r.t. non-negativity of the terms:

weight_non_edge_compute * non_edge_feature.at<uchar>(q)
- https://github.com/opencv/opencv/blob/4.5.5/modules/imgproc/src/intelligent_scissors.cpp#L180
- https://github.com/opencv/opencv/blob/4.5.5/modules/imgproc/src/intelligent_scissors.cpp#L344
- non_edge_feature via uchar type
weight_gradient_direction * fD
- https://github.com/opencv/opencv/blob/4.5.5/modules/imgproc/src/intelligent_scissors.cpp#L181
- https://github.com/opencv/opencv/blob/4.5.5/modules/imgproc/src/intelligent_scissors.cpp#L536
weight_gradient_magnitude * fG

cpoerschke · 2022-06-07T21:05:36Z

Thanks for approving the CI run for this pull request!

Reviewing the "PR:4.x W10 / BuildAndTest (pull_request) Cancelled after 360m — BuildAndTest" outcome, this was

Run RET=$(git ls-remote --heads "https://github.com/cpoerschke/opencv_extra" "4.x-intelligent-scissors-optimisation") || true
Error: The operation was canceled.

and apparently because (at the time) there was no https://github.com/cpoerschke/opencv_extra fork in existence. Basic git documentation searching found no git ls-remote options or other git commands that would obviously handle this scenario and so I've just gone ahead and created a fork of the repo. Hope that helps? Thank you.

alalek · 2022-10-08T23:38:18Z

modules/imgproc/test/test_intelligent_scissors.cpp

+};

+INSTANTIATE_TEST_CASE_P(/**/, Imgproc_IntelligentScissorsMB, testing::Combine(testing::Values( true, false ),
+                                                                              testing::Values( 1, 100 )));


What is the purpose of adding 100 iterations for the accuracy test?

It was a naive way of getting performance test numbers ... I have now in cd6ef45 added a separate performance test instead.

modules/imgproc/src/intelligent_scissors.cpp

asmorkalov · 2023-05-23T12:43:59Z

@cpoerschke Thanks a lot for the patch! Couple of questions for the solution:

If I understand correctly, the optimized branch produces the same result. In case if we rich threshold with some part of cost sum, then we've got what we want. cost_map contains only values bellow threshold and half-baked cost values that are above threshold are not added there. Why do you need special flag to switch behaviour?
Could you modify some (not all) tests to check contour values, but not only contour size? It allows to check item 1.

cpoerschke · 2023-05-23T20:37:51Z

Hi @asmorkalov - thanks for the review!

If I understand correctly, ... Why do you need special flag to switch behaviour?

Your understanding is correct. The special flag (during development) helps compare performance and accuracy via the parameterised tests but yes beyond that there is technically no need for the flag to remain. Sometimes flags can help preserve existing behaviour for APIs for backwards compatibility between versions or so but that is not the case here I think.

Could you modify some (not all) tests to check contour values, but not only contour size? It allows to check item 1.

Have just added a commit that modifies (so far only) one test to check ca. 5+5% of the contour values, at the beginning and the end of the contour.

asmorkalov · 2023-05-24T06:12:17Z

I propose 2 things:

Dump full contour to file with FileStorage (yaml or yaml.gz) and check full contour in several tests or all tests. You need to create PR to opencv_extra repo with the same branch name. If the branches match they are testsed together by CI.
Remove flag and stay with optimized branch. I do not see reason to presume original behavior, if they are equivalent. Test with full contour check ensures it.

cpoerschke · 2023-05-25T21:57:16Z

I propose 2 things:

Dump full contour to file with FileStorage (yaml or yaml.gz) and check full contour in several tests or all tests. You need to create PR to opencv_extra repo with the same branch name. If the branches match they are testsed together by CI.
...

#23688 opened for the first thing - .xml files seemed more common than .yaml files and so I went with that for now. opencv/opencv_extra#1065 is the matching PR for the opencv_extra repo.

cpoerschke · 2023-05-26T19:24:59Z

I propose 2 things:

...

Remove flag and stay with optimized branch. I do not see reason to presume original behavior, if they are equivalent. Test with full contour check ensures it.

a01344e commit added for the second thing.

asmorkalov · 2023-05-27T07:06:47Z

I propose to restore perf test. We can use summary.py and other scripts to compare performance numbers for different versions, e.g. gefore and after patch.

@asmorkalov

imgproc: add basic IntelligentScissorsMB performance test #23698 Adding basic performance test that can be used before and after the #21959 changes etc. as per @asmorkalov's #21959 (comment) comment. ### 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

@asmorkalov

imgproc: add contour values check to IntelligentScissorsMB tests Preparation for the #21959 changes as per @asmorkalov's #21959 (comment) suggestion. ### 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

asmorkalov · 2023-06-07T08:37:01Z

@cpoerschke Thanks a lot for the contribution! I merged accuracy and performance tests. Could you rebase the PR with optimization on top of current 4.x and squash commits?

…ildMap

cpoerschke · 2023-06-07T22:01:02Z

@cpoerschke Thanks a lot for the contribution! I merged accuracy and performance tests. Could you rebase the PR with optimization on top of current 4.x and squash commits?

Thanks @asmorkalov for the review inputs! I've rebased and squashed the commits.

Also ran the performance test on the commit before and the commit itself - unless I'm misreading the numbers the optimisation actually makes things slower now. Would like to look into that more thoroughly, perhaps I missed something when removing the switch flag? The accuracy tests pass.

asmorkalov · 2023-06-08T08:54:55Z

I see optimization effect, but the mentioned function is not bootle neck:

python3 ../opencv-master/modules/ts/misc/summary.py ./IntelligentScissorsMB-4.x.xml ./IntelligentScissorsMB-opt.xml 

Geometric mean (ms)

             Name of Test              IntelligentScissorsMB-4.x IntelligentScissorsMB-opt IntelligentScissorsMB-opt
                                                                                                      vs            
                                                                                           IntelligentScissorsMB-4.x
                                                                                                  (x-factor)        
buildMap::TestIntelligentScissorsMB::0         7995.334                  7819.149                    1.02           
buildMap::TestIntelligentScissorsMB::1         7988.302                  7816.922                    1.02

asmorkalov

👍

@asmorkalov

imgproc: add contour values check to IntelligentScissorsMB tests Preparation for the opencv#21959 changes as per @asmorkalov's opencv#21959 (comment) suggestion. ### 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

@asmorkalov

imgproc: add basic IntelligentScissorsMB performance test opencv#23698 Adding basic performance test that can be used before and after the opencv#21959 changes etc. as per @asmorkalov's opencv#21959 (comment) comment. ### 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

@asmorkalov

imgproc: add contour values check to IntelligentScissorsMB tests Preparation for the opencv#21959 changes as per @asmorkalov's opencv#21959 (comment) suggestion. ### 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

@asmorkalov

imgproc: add basic IntelligentScissorsMB performance test opencv#23698 Adding basic performance test that can be used before and after the opencv#21959 changes etc. as per @asmorkalov's opencv#21959 (comment) comment. ### 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

@asmorkalov

imgproc: add contour values check to IntelligentScissorsMB tests Preparation for the opencv#21959 changes as per @asmorkalov's opencv#21959 (comment) suggestion. ### 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

fengyuentau added the category: imgproc label May 9, 2022

alalek reviewed Oct 8, 2022

View reviewed changes

modules/imgproc/src/intelligent_scissors.cpp Show resolved Hide resolved

asmorkalov modified the milestones: 4.7.0, 4.8.0 Dec 12, 2022

asmorkalov requested review from asmorkalov and removed request for alalek May 23, 2023 06:43

asmorkalov self-assigned this May 23, 2023

cpoerschke mentioned this pull request May 25, 2023

imgproc: add contour values check to IntelligentScissorsMB tests #23688

Merged

6 tasks

cpoerschke mentioned this pull request May 27, 2023

imgproc: add basic IntelligentScissorsMB performance test #23698

Merged

6 tasks

imgproc: optimise local cost computation in IntelligentScissorsMB::bu…

f597838

…ildMap

cpoerschke force-pushed the 4.x-intelligent-scissors-optimisation branch from a01344e to f597838 Compare June 7, 2023 21:50

cpoerschke marked this pull request as draft June 7, 2023 22:01

asmorkalov approved these changes Jun 8, 2023

View reviewed changes

asmorkalov marked this pull request as ready for review June 8, 2023 13:44

asmorkalov merged commit 5d913f4 into opencv:4.x Jun 8, 2023

asmorkalov mentioned this pull request Jul 12, 2023

(5.x) Merge 4.x #23979

Merged

Uh oh!

Conversation

cpoerschke commented May 8, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Notes

Test run snippet

Pull Request Readiness Checklist

Uh oh!

cpoerschke commented May 21, 2022

Uh oh!

cpoerschke commented Jun 7, 2022

Uh oh!

alalek Oct 8, 2022

Choose a reason for hiding this comment

Uh oh!

cpoerschke Oct 9, 2022

Choose a reason for hiding this comment

Uh oh!

Uh oh!

asmorkalov commented May 23, 2023

Uh oh!

cpoerschke commented May 23, 2023

Uh oh!

asmorkalov commented May 24, 2023

Uh oh!

cpoerschke commented May 25, 2023

Uh oh!

cpoerschke commented May 26, 2023

Uh oh!

asmorkalov commented May 27, 2023

Uh oh!

asmorkalov commented Jun 7, 2023

Uh oh!

cpoerschke commented Jun 7, 2023

Uh oh!

asmorkalov commented Jun 8, 2023

Uh oh!

asmorkalov left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

cpoerschke commented May 8, 2022 •

edited

Loading