LineVirtualIterator #13869

chacha21 · 2019-02-19T20:26:28Z

Proposal of LineVirtualIterator, an alternative to "LineIterator not attached to any mat".
This is basically the same implementation, replacing the address difference by a single "offset" variable. elemsize becomes irrelevant and considered to be 1. "step" is thus equal to size.width since no stride is expected.

related to #13843

Proposal of LineVirtualIterator, an alternative to "LineIterator not attached to any mat". This is basically the same implementation, replacing the address difference by a single "offset" variable. elemsize becomes irrelevant and considered to be 1. "step" is thus equal to size.width since no stride is expected.

fixed warning

alalek

Please add some accuracy tests.

modules/imgproc/src/drawing.cpp

modules/imgproc/include/opencv2/imgproc.hpp

modules/imgproc/src/drawing.cpp

alalek · 2019-02-22T10:16:44Z

modules/imgproc/src/drawing.cpp

+
+    s = dy < 0 ? -1 : 0;
+    dy = (dy ^ s) - s;
+    istep = (istep ^ s) - s;


"undefined behavior"

Lets try to avoid that.
Compilers are smart enough (or at least this is not required in non "heavy" constructor calls).

Not sure to understand this one. This is the LineIterator implementation; is there a problem here ?

instead of being too conservative, the new implementation gets rid of "offset/step" and only keeps a "Point currentPos" up to date. left_to_right is renamed to forceLeftToRight as suggested (even for the old LineIterator) assert() replaced by CV_Assert() (even for the old LineIterator)

chacha21 · 2019-02-23T19:51:33Z

some suggested improvements have been made in the new commit.
However, adding "accuracy tests" is a new step for me in my learning curve of OpenCV contributing, I still have to learn it.

[edit]
current commit is broken, I had implemented a broken test that mislead me

[edit2]
fixed

+fixed last commit so that LineVirtualIterator gives at least the same results as LineIterator +added a new constructor that does not require any Size, so that no clipping is done and iteration occurs from pt1 to pt2. This is done by adding a spatial offset to pt1 and pt2 so that the same implementation is used, the size being in that case the spatial size between pt1 and pt2

fixed warnings

fixed whitespace

trailing whitespace

+added a new constructor that takes a Rect rather than a Size. It computes the line pt1->pt2 that clips that rect. Yet again, this is still based on the same implementation, thanks to the Size and the currentPosOffset that can artifically consider the origin of the rect at (0,0)

chacha21 · 2019-02-24T21:46:09Z

I still did not update the doc in the source code, I am first waiting to know whether the pull request is accepted or not

revert changes on original LineIterator implementation, that will be superseded by the new LineVirtualIterator anyway

asmorkalov · 2019-11-11T05:27:59Z

@chacha21 Do you have a chance to work on some tests for the new feature?

VadimLevin

Thanks for your work!

There is a couple of improvements those can be done.

Also consider to use const where it is possible and add spaces between math operators e.g. pos.x+offset.x%2 is quite unreadable.

VadimLevin · 2020-01-14T06:47:28Z

modules/imgproc/include/opencv2/imgproc.hpp

@@ -4717,7 +4717,7 @@ class CV_EXPORTS LineIterator
    not to depend on the ordering of pt1 and pt2 parameters
    */
    LineIterator( const Mat& img, Point pt1, Point pt2,
-                  int connectivity = 8, bool leftToRight = false );
+                  int connectivity = 8, bool forceLeftToRight = false );


Documentary string should be updated too (forceLeftToRight).

modules/imgproc/include/opencv2/imgproc.hpp

modules/imgproc/src/drawing.cpp

modules/imgproc/test/test_drawing.cpp

Use C++11 chained constructors Improved code style

Added offset as random test data.

VadimLevin · 2020-01-16T07:58:01Z

Thank you for your work!
Please, fix documentary string for LineIterator because you've changed the parameter name and add documentary strings for implemented functionality. But I suppose, last item should be done after @alalek approve code changes.

vpisarev · 2020-02-03T11:30:21Z

@chacha21, thank you for the contribution! I think, in this class it makes sense to modify implementation of Bresenham algorithm to operate directly on the pixel coordinates. With current implementation it's so slow that we can basically use the original class, just add an extra constructor to it.

vpisarev · 2020-02-03T11:31:19Z

modules/imgproc/include/opencv2/imgproc.hpp

+      const int offset = minusStep + (plusStep & mask);
+      const size_t flattenedCoord = (currentPos.y - currentPosOffset.y) * size.width + (currentPos.x - currentPosOffset.x) + offset;
+      currentPos.y = static_cast<int>((flattenedCoord / size.width) + currentPosOffset.y);
+      currentPos.x = static_cast<int>((flattenedCoord % size.width) + currentPosOffset.x);


basically, I mean that these 2 lines (currentPos.y=...; currentPos.x=...;) should be removed; instead, you should update currentPos directly using the Bresenham algorithm

The current implementation is rather far from standard Bresenham's algorithm descriptions, so it is not that straightfoward to rewrite differently all the cases in both 4 and 8 connectivity.

asmorkalov · 2020-03-06T08:08:44Z

@chacha21 @vpisarev do you have consensus on the solution?

vpisarev · 2020-03-26T23:16:25Z

@chacha21, @asmorkalov, I've updated the implementation, made it one class, not two. Hopefully, it's good enough to be merged

alalek

See comments in previous patch about that: #13843 (mentioned in PR description)

modules/imgproc/include/opencv2/imgproc.hpp

added one perfectly predictable check; in theory, since ptmode is set in the end of the constructor in the header file, the compiler can figure out that it's always true/false and eliminate the check from the inline `LineIterator::operator++()` completely

in the most common case (CV_8UC3) eliminated the check from the loop

vpisarev · 2020-04-08T12:52:58Z

@alalek, can we merge it?

* LineVirtualIterator Proposal of LineVirtualIterator, an alternative to "LineIterator not attached to any mat". This is basically the same implementation, replacing the address difference by a single "offset" variable. elemsize becomes irrelevant and considered to be 1. "step" is thus equal to size.width since no stride is expected. * Update drawing.cpp fixed warning * improvement of LineVirtualIterator instead of being too conservative, the new implementation gets rid of "offset/step" and only keeps a "Point currentPos" up to date. left_to_right is renamed to forceLeftToRight as suggested (even for the old LineIterator) assert() replaced by CV_Assert() (even for the old LineIterator) * fixed implementation +fixed last commit so that LineVirtualIterator gives at least the same results as LineIterator +added a new constructor that does not require any Size, so that no clipping is done and iteration occurs from pt1 to pt2. This is done by adding a spatial offset to pt1 and pt2 so that the same implementation is used, the size being in that case the spatial size between pt1 and pt2 * Update imgproc.hpp fixed warnings * Update drawing.cpp fixed whitespace * Update drawing.cpp trailing whitespace * Update imgproc.hpp +added a new constructor that takes a Rect rather than a Size. It computes the line pt1->pt2 that clips that rect. Yet again, this is still based on the same implementation, thanks to the Size and the currentPosOffset that can artifically consider the origin of the rect at (0,0) * revert changes revert changes on original LineIterator implementation, that will be superseded by the new LineVirtualIterator anyway * added test of LineVirtualIterator * More tests * refactoring Use C++11 chained constructors Improved code style * improve test Added offset as random test data. * fixed order of initialization * merged LineIterator and VirtualLineIterator * merged LineIterator & VirtualLineIterator * merged LineIterator & VirtualLineIterator * merged LineIterator & VirtualLineIterator * made LineIterator::operator ++() more efficient added one perfectly predictable check; in theory, since ptmode is set in the end of the constructor in the header file, the compiler can figure out that it's always true/false and eliminate the check from the inline `LineIterator::operator++()` completely * optimized Line() function in the most common case (CV_8UC3) eliminated the check from the loop Co-authored-by: Vadim Pisarevsky <vadim.pisarevsky@gmail.com>

chacha21 added 3 commits February 19, 2019 21:24

Update drawing.cpp

03b8d56

fixed warning

Merge remote-tracking branch 'upstream/master' into LineVirtualIterator

ba92da7

alalek reviewed Feb 22, 2019

View reviewed changes

chacha21 added 2 commits February 23, 2019 19:57

Merge remote-tracking branch 'upstream/master' into LineVirtualIterator

02cea74

chacha21 added 5 commits February 24, 2019 15:01

Update imgproc.hpp

e851c15

fixed warnings

Update drawing.cpp

a6fe9d0

fixed whitespace

Update drawing.cpp

46c07e7

trailing whitespace

Merge remote-tracking branch 'upstream/master' into LineVirtualIterator

3e11ed4

alalek mentioned this pull request Mar 13, 2019

imgproc: revert #13843 #14043

Merged

chacha21 added 5 commits March 13, 2019 20:16

Merge remote-tracking branch 'upstream/master' into LineVirtualIterator

fbbcd4f

revert changes

7db9607

revert changes on original LineIterator implementation, that will be superseded by the new LineVirtualIterator anyway

Merge branch 'master' into LineVirtualIterator

6023f65

Merge remote-tracking branch 'upstream/master' into LineVirtualIterator

6a8fa75

Merge remote-tracking branch 'upstream/master' into LineVirtualIterator

3fe0799

chacha21 added 4 commits November 19, 2019 17:15

Merge branch 'master' into LineVirtualIterator

cbd2cb6

Merge remote-tracking branch 'upstream/master' into LineVirtualIterator

72f4646

added test of LineVirtualIterator

af3e253

More tests

acbfb16

asmorkalov requested a review from VadimLevin January 10, 2020 07:21

VadimLevin reviewed Jan 14, 2020

View reviewed changes

asmorkalov removed the pr: needs test New functionality requires minimal tests set label Jan 14, 2020

chacha21 added 2 commits January 14, 2020 11:05

Merge remote-tracking branch 'upstream/master' into LineVirtualIterator

861c127

refactoring

741dff5

Use C++11 chained constructors Improved code style

chacha21 added 2 commits January 14, 2020 12:47

improve test

4c421b8

Added offset as random test data.

fixed order of initialization

3510d0b

vpisarev reviewed Feb 3, 2020

View reviewed changes

asmorkalov added the pr: Discussion Required label Mar 13, 2020

vpisarev added 4 commits March 27, 2020 02:09

merged LineIterator and VirtualLineIterator

c37bfa0

merged LineIterator & VirtualLineIterator

c6e25a1

merged LineIterator & VirtualLineIterator

0576559

merged LineIterator & VirtualLineIterator

15bcfe1

alalek requested changes Mar 27, 2020

View reviewed changes

modules/imgproc/include/opencv2/imgproc.hpp Outdated Show resolved Hide resolved

vpisarev added 2 commits March 28, 2020 16:00

optimized Line() function

68f101d

in the most common case (CV_8UC3) eliminated the check from the loop

asmorkalov removed the pr: Discussion Required label Apr 9, 2020

alalek approved these changes Apr 13, 2020

View reviewed changes

alalek merged commit f351653 into opencv:master Apr 13, 2020

chacha21 deleted the LineVirtualIterator branch April 13, 2020 07:28

Uh oh!

LineVirtualIterator #13869

LineVirtualIterator #13869

Uh oh!

Conversation

chacha21 commented Feb 19, 2019

Uh oh!

alalek left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

alalek Feb 22, 2019

Choose a reason for hiding this comment

Uh oh!

chacha21 Feb 23, 2019

Choose a reason for hiding this comment

Uh oh!

chacha21 commented Feb 23, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

chacha21 commented Feb 24, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

asmorkalov commented Nov 11, 2019

Uh oh!

VadimLevin left a comment

Choose a reason for hiding this comment

Uh oh!

VadimLevin Jan 14, 2020

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

VadimLevin commented Jan 16, 2020

Uh oh!

vpisarev commented Feb 3, 2020

Uh oh!

vpisarev Feb 3, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

chacha21 Feb 18, 2020

Choose a reason for hiding this comment

Uh oh!

asmorkalov commented Mar 6, 2020

Uh oh!

vpisarev commented Mar 26, 2020

Uh oh!

alalek left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

vpisarev commented Apr 8, 2020

Uh oh!

Uh oh!

chacha21 commented Feb 23, 2019 •

edited

Loading

chacha21 commented Feb 24, 2019 •

edited

Loading

vpisarev Feb 3, 2020 •

edited

Loading