EDCircles Request for Ideas

This time I've given the following image to EDColor:

It generates nice edges and segments:

But, EDCircle misses one of my markers (the top blue one).

I've tried adjusting gradThresh and sigma (the blur size). It's possible to tweak them so that all six markers are found in this test image, but then I get a similar problem, with missing markers, in other test images, so I want to keep gradThresh and sigma fixed.

That marker looks close to circular in the segments image:

... which gives me hope that EDCircles could be tweaked to detect it.

I want to dive into EDCircles.cpp to see if there's anything I can do. Do you have any immediate ideas about where I could start?
Is there something in the segment structure around the circle that makes it an edge case, or particularly hard to detect?

Best regards,

Hi @tobbelobb,

There is a huge grey area when it comes to what is a circle or not in real images, (and it is even worse for ellipses!)
So, because of the pixelization of curves, the less resolution you have, the more trouble it gets.
EDCircles first checks closed segments for circles and ellipses and extract them pretty fast and accurate.
Then it extracts arcs by analyzing consecutive (short) line segments and then attempts to join the extracted arcs that look like belonging to the same prospective circle with respect to several heuristics.

I suggest you:

The algorithm invalidates the detected circles in the last step and it sometimes invalidates true circles. So you can check if your circles are actually detected but then invalidated due to the poor gradient distribution. (not very probable though)
Try to modify your marker design so that it produces closed edge segments for your markers. You can simply put a background (pick a contrastive color ) underneath your spherical markers. If you do this, the algorithm would not have to deal with arcs obtained from distinct edge segments.
If it does not help, you can start with checking the extracted arcs and see if the algorithm can catch reasonable arcs from your markers.

Good luck!

Absolutely. If there's something ED_Lib has told me, it is that partial ellipses and circles are everywhere. It's fun to get surprised by some of the ellipses that ED_Lib finds in my office.

Interesting suggestions! I will try the first one today. Maybe I can draw invalidated circles in a separate color. It should be quick.

I'm optimistic that adding a background (even just a partial one) will work. Still, I'm interested to see if I can find a way to visualize the extracted arcs anyways. It will teach me something about the algorithm.

Will definitely put a background behind my markers once I get tired of arc heuristics and need to move on ;)

Thanks!

So here are the arcs (edarc1) of my effector:

The marker in question is enclosed by these arcs:

I think these images, and particularly the last one, are what I need to try to improve to get where I want.

So, if we skip the sign equality requirement between firstLine and lastLine here:

ED_Lib/EDCircles.cpp

Line 796 in f187542

if (info[lastLine].sign != info[firstLine].sign) break;

By removing that line, we can make the arc stretch further around the marker:

This hack also finds one more billiard ball in the billiard.jpg training image that ships with ED_Lib. However, it also finds a few more "weird" or "unexpected" ellipses in that image, so it's just pushing the trade-off in one direction, it's not improving precision of accuracy in a fundamental way.

Also, it's still not enough to detect the marker that I wanted to detect. But maybe it's a valuable hint about what I should try tomorrow.

So, I've tried many things and failed.
I did find one tiny thing that fixed the example above, but broke another brittle test case.

I noticed that the JoinAnchorPointsUsingSortedAnchors() function was biased towards drawing straight lines instead of curved ones, because of the order of if-else clauses here:

ED_Lib/ED.cpp

Line 501 in f187542

if (edgeImg[r*width + c - 1] >= ANCHOR_PIXEL) { c--; }

... and in three analogous places further down.

Changing this if-else order to ACB, instead of the current BAC in all four places makes the EDCircles(EDColor) test in test.cpp find one more billiard ball. And finally in a way that I kind of understand.

(Some other clauses were also biased, see

ED_Lib/ED.cpp

Line 510 in f187542

if (A > B) {

, but I did not observe any instance of the bias every playing a role. I guess the gradient values are very rarely equal)

I will put backgrounds behind my markers now, and go on with my life.

Best regards

Well, sometimes a small update on the physical environment is worth hundred lines of code :)
It is really difficult to solve this problem as your spheres are really small and the resolution is limited.
Although I do not really remember all of them but we had perform so many experiments and trials with ED, and found out that there is no magical heuristic that solves all problems. After some trial & error and some progress, you come to a position that it stops optimising for majority of the issues. I mean, after a point it gets better for some problematic cases but gets worse for others. Bottom line, it looks like you are now in a such position now and better to help the algorithm by providing easier markers to catch :)

ED_Lib really is a lot more tested, optimized, and polished on the performance side than what the repo stats (eg number of commits, tests, contributors, build files, CI pipeline etc) could have one thinking. I guess it's because an older, C version existed and was in practical use for some time before this repo, and because academical papers (not commits) has been the main medium for publishing ED_Lib progress.

So I think a lot of knowledge has been baked into the code with great effort. I'd love to see a push for setting up formal tests and getting ED_Lib into OpenCV so that effort and knowledge doesn't get lost. I will keep my eyes out for potential ways to fund such an effort.

Hello @tobbelobb, indeed ED_Lib has an older C version. Under Prof. Topal, I tried to refactor legacy C code into object oriented C++ code. At the time I was senior student at my university and wasn't really proficient at Git/GitHub usage, hence the all code pushed at once.

I also think in order to reach more people, repo should contain tests, CI pipeline etc.. as you mention. That being said, after my graduation I've leaned into full-stack development instead of image processing so I couldn't maintain the repo much. I would love to help you to improve the repo, also the code. Unfortunately, in my daily job I am not using C++ and I have forgot lots of stuff so my help here might be questionable here 😅. It would be awesome if we get ED_Lib into OpenCV, that was our initial goal as well. I believe many people can benefit from it.

Anyways, thank you for your interest and comments.

i have a PR to merge some ED_Lib functionality into OpenCV

any help ( testing, giving ideas etc.) about the PR will be appreciated.

That's awesome!
I have made quite a lot of changes in my fork trying to make it more robust, without changing the behavior (or, at least only when change was intentional).

Maybe the biggest changes I've made are in EDColor. I've moved many global variables that were hidden inside the class definition, and made them into explicit arguments to the functions instead. Cleaning up EDColor.h was my main focus, so look into that one first.

If you have the time to dig through the relevant commits, you'll find other improvements as well, like getting parallel pixel processing with OpenCV's for_each function. That measurably sped up EDColor, but not by a lot.

There's also a lot of clang-tidy fixes, a lot of fixing warnings, a lot of const correctness, swapping out C-style arrays with C++ std::arrays, using the correct one among delete/delete[]. Previous authors had used delete in a few places where they should have used delete[]. Fixing a potential index out of bounds bug. But above all, I've tried to weed out manual memory management and just use std::vector or std::stack instead.

I guess a large change is also to make test.cpp into an executable with boost-ut. Just be aware that I've changed some of the #defined limits at the top of EDCircles.h, so my tests expect slightly different behaviour compared to upstream EDLib.

https://gitlab.com/tobben/hpm/-/tree/master/hpm/ed

@tobbelobb thanks for your feedback. ED_Lib is merged in OpenCV partly and i will continue to work on unmerged parts and improvements.
i will take a look on your fork.