Skip to content

DNN: supports Scatter and ScatterND from ONNX#22529

Merged
asmorkalov merged 1 commit intoopencv:4.xfrom
fengyuentau:scatter_scatternd
Oct 17, 2022
Merged

DNN: supports Scatter and ScatterND from ONNX#22529
asmorkalov merged 1 commit intoopencv:4.xfrom
fengyuentau:scatter_scatternd

Conversation

@fengyuentau
Copy link
Copy Markdown
Member

@fengyuentau fengyuentau commented Sep 18, 2022 •
edited
Loading

Fixes #22528

Merge with: opencv/opencv_extra#1009

Checklist:

  • Scatter impl
  • Scatter impl for negative indices
  • Test data for Scatter
  • ScatterND impl
  • ScatterND impl for negative indices
  • Test data for ScatterND
  • Disable the perf test to save CI server resources before merge

ONNX operator doc: https://github.com/onnx/onnx/blob/main/docs/Operators.md#Scatter

Benchmark

Benchmark was done on M1 Macbook Air (16G mem). Time is in milliseconds.

*: Shapes of input, indices, updates are all [8, 256, 128, 100].

Version Operation mean median min
intial Scatter 223.53 223.44 220.77
initial Scatter-add 241.19 241.86 238.11
+ passing_mat Scatter 228.51 228.36 226.45
+ passing_mat Scatter-add 249.08 249.20 247.54
current impl: + optm + pm Scatter 154.62 153.80 153.38
current impl: + optm + pm Scatter-add 169.39 169.63 168.20

*: Shapes of input, indices, updates are [8, 256, 128, 100], [8, 256, 128, 100, 4], [8, 256, 128, 100] respectively.

Version Operation mean median min
intial ScatterND 465.92 465.25 464.78
initial ScatterND-add 475.01 473.86 473.13
+ passing_mat ScatterND 464.59 464.40 464.13
+ passing_mat ScatterND-add 473.80 470.24 465.80
+ pm + ng index ScatterND 511.17 508.44 507.73
+ pm + ng index ScatterND-add 518.91 518.56 510.94
+ optm1 + pm + ng index ScatterND 227.04 226.29 225.21
+ optm1 + pm + ng index ScatterND-add 218.58 218.37 217.26
current impl: + optm2 + optm1 + pm + ng index ScatterND 132.87 132.94 132.09
current impl: + optm2 + optm1 + pm + ng index ScatterND-add 135.17 135.05 133.93

Potential issue

ScatterND should support duplicate indices if reduction is not none. Also ScatterND permits negative indices. See here for more details.

Notice: Current impl does not check for duplicate indices if reduction is none.

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

@fengyuentau fengyuentau mentioned this pull request Sep 20, 2022
Closed
4 tasks
@fengyuentau fengyuentau mentioned this pull request Sep 25, 2022
Merged
@fengyuentau fengyuentau marked this pull request as ready for review September 27, 2022 12:07
@fengyuentau fengyuentau requested a review from rogday September 27, 2022 12:07
asmorkalov
asmorkalov reviewed Oct 3, 2022
View reviewed changes
rogday
rogday suggested changes Oct 3, 2022
View reviewed changes
Copy link
Copy Markdown
Member

@rogday rogday left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you for contribution!
Comments about the algorithm are valid only for the case of continuous matrices, but you assume it in a few places, so we could benefit from optimization.

@fengyuentau
Copy link
Copy Markdown
Member Author

fengyuentau commented Oct 16, 2022

Commits are squashed.

rogday
rogday reviewed Oct 16, 2022
View reviewed changes
Copy link
Copy Markdown
Member

@rogday rogday left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I had a few ideas for speeding this up further, if you don't mind. The code should behave exactly the same. I ran tests, but might've missed something. Please take a look.

rogday
rogday approved these changes Oct 17, 2022
View reviewed changes
Copy link
Copy Markdown
Member

@rogday rogday left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM! 👍

@asmorkalov asmorkalov merged commit ec7fc5a into opencv:4.x Oct 17, 2022
@alalek alalek mentioned this pull request Jan 8, 2023
Merged
@asmorkalov asmorkalov added this to the 4.7.0 milestone Jan 23, 2023
@fengyuentau fengyuentau deleted the scatter_scatternd branch March 14, 2023 07:42
@fengyuentau fengyuentau mentioned this pull request Feb 21, 2024
Open
48 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@asmorkalov asmorkalov asmorkalov approved these changes

+1 more reviewer

@rogday rogday rogday approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

category: dnn feature

Projects

None yet

Milestone

4.7.0

Development

Successfully merging this pull request may close these issues.

(-2:Unspecified error) Can't create layer "onnx_node!ScatterND_274" of type "ScatterND" in function 'getLayerInstance'

3 participants

@fengyuentau @asmorkalov @rogday