Ellipse Detection

[bronxbomber92]

We've been experiencing pretty awful drops in performance (being able to procress approximately 4 images per second) in trying to the detect the target. I've narrowed down the performance bottleneck to the imaqDetectEllipses function (it accounts for approximately 80% of the performance hit). Has anyone else been having similar experiences? If so, what have you done/tried to allieviate the problem? I've looked at increasing the row and column step sizes of the CurveOptions object passed to imaqDetectEllipses, but I'm afraid that increasing this too much (ie, pass 20) will lead to a lot of missed ellipses at further distances (though I don't have any data to back this up due to an inadequate testing environment). I'm fearful I'm going to have to look into implementing our own ellipse detection code. On that note, have you guys looked at doing the same, and do you have any clue to how the imaqDetectEllipses function works under the hood (so, perhaps, I can avoid duplicating their implementation)?

I've been looking at using the hough transform to detect ellipses, but there isn't a whole lot of info out there on implementations details. I've been looking at OpenCV's HoughCircle function, and I can't imagine it being very fast either (though, I could be wrong..).

[Greg McKaskle]

There is a white paper on the ni site that covers vision and some of the things that affect performance the most.

The IMAQ library internally has two shape detection methods, Hough, and geometric matching. Both initially perform a horizontal and vertical rake to identify edge crossings and to greedily trace the edges within the rake width.

After the rake, the ellipse and other geometric shape detection filters the traces based on length, corners, straight edges, and the like. Then it fits an geometric ellipse to the trace, selecting the ones with the highest scores.

The Hough shape detection tends to be used for more complex shapes -- the ones where you train the library on your template shape. I really can't compare the OpenCV performance to the IMAQ performance, except to say that if the OpenCV is faster, the NI IMAQ guys should and probably have updated their algorithm and implementation to match or exceed. At least I hope that is what they do with their time.

If you can list the parameters you are using, I can tell you if anything stands out.

Greg McKaskle

[bronxbomber92]

Thanks for that overview of the workings of the internals of imaqDetectEllipses! We have a day off from robotics today, so when I get back tomorrow I will post the parameters I'm using.

What whitepaper are you referring to? I can't seem to find it.

Thanks!

[Greg McKaskle]

http://joule.ni.com/nidu/cds/view/p/id/1568/lang/en

As usual, I searched the sites and nothing. Then go to google and there it is.

Greg McKaskle

[bronxbomber92]

Ha, no wonder I couldn't find. Thanks.

Here are the parameters I'm using:

EllipseDescriptor
minMajorRadius - 3.0
maxMajorRadius - 160.0
minMinorRadius - 3.0
maxMajorRadius - 160.0

CurveOptions
extractionMode - IMAQ_NORMAL_IMAGE
threshold - 50
filterSize - IMAQ_NORMAL
minLength - 20
rowStepSize - 20
columnStepSize - 20
maxEndPointGap - 10
onlyClosed - false
subPixelAccuracy - false

ShapeDetectionOptions
mode - IMAQ_GEOMETRIC_MATCH_SHIFT_INVARIANT
anglesRanges - null
numAngleRanges - 0
scaleRange - 0
minMatchScore - 800

[Greg McKaskle]

I'm not certain what the defaults were for the other languages, but the first thing I'd change is set the threshold much higher, like 100 to 150. Lower thresholds cause many many more edges and will slow performance more than any of the other settings. The second thing would be to turn on the onlyClosed. Unless you start to care about occluded shapes, and perhaps even then, you don't need edges which only form fragments instead of closed shapes.

I'm not used to seeing the mode, so I'm assuming it is the default.

Greg McKaskle

[ideasrule]

The default ellipse detection method gets the luminance plane and passes that to imaqdetectEllipse. I found out last year that the conversion from RGB is HSL is very time-consuming. The math isn't hard, but every single pixel of every single frame has to be converted, which takes a significant amount of time. Passing one of the red/green/blue planes to imaqdetectEllipse should decrease processing time dramatically.

Also, you probably don't want to find ellipses only 3 pixels across. Try setting the minimum minor & major axes to 10. Otherwise, the code will pick up a lot of false positives.

Another thing: what do you want the code to do? If it's just picking up the vision target, the edge threshold can be set much higher. If you want to pick up soccer balls, your current edge threshold is fine.

[Greg McKaskle]

Extracting the luminance is far cheaper than fully converting to HSL. Go ahead and time it. It will be slightly more expensive than extracting one of the planes, and after all, which plane do you use to get black and white?

The 3 is indeed very small, but it is a radius of three, not the diameter and this is about the number needed for full field. If you are up closer, you can set the number higher to avoid small objects from being IDed as the target.

Greg McKaskle

[bronxbomber92]

Thanks for the input guys! I'm now in the middle of testing all other basic robot functionality, so any sort of vision stuff has been put on the back burner temporarily. Once I get back to it, I'll report back here with how things work out.

I've also developed my own ellipse detection that's specialized to only work with this year's target, so that's another thing I've got to try.

[adamdb]

Originally Posted by bronxbomber92

EllipseDescriptor
minMajorRadius - 3.0
maxMajorRadius - 160.0
minMinorRadius - 3.0
maxMajorRadius - 160.0

CurveOptions
extractionMode - IMAQ_NORMAL_IMAGE
threshold - 50
filterSize - IMAQ_NORMAL
minLength - 20
rowStepSize - 20
columnStepSize - 20
maxEndPointGap - 10
onlyClosed - false
subPixelAccuracy - false

ShapeDetectionOptions
mode - IMAQ_GEOMETRIC_MATCH_SHIFT_INVARIANT
anglesRanges - null
numAngleRanges - 0
scaleRange - 0
minMatchScore - 800

These parameters seem to be set by the following Java statements:

    static EllipseDescriptor ellipseDescriptor = new EllipseDescriptor(3, 200, 3, 100);
    static CurveOptions curveOptions = new CurveOptions(0, 40, 1, 25, 15, 15, 10, 1, 0);
    static ShapeDetectionOptions shapeOptions = new ShapeDetectionOptions(ShapeDetectionOptions.IMAQ_GEOMETRIC_MATCH_SHIFT_INVARIANT, 0, 0, 75, 125, 500);

But these classes aren't in the FRC javadocs, so I can see which value is which. Is there a javadoc or reference for these somewhere?

[bronxbomber92]

They are C structs, exposed to Java. They are documented by NI in NIVisionCVI located in C:\Program Files\National Instruments\Vision\Documentation

P.S. I'm working in C++, so I probably can't help you much beyond that w/ any Java specifics.

[ideasrule]

Originally Posted by Greg McKaskle

Extracting the luminance is far cheaper than fully converting to HSL. Go ahead and time it. It will be slightly more expensive than extracting one of the planes, and after all, which plane do you use to get black and white?

In that case, I stand corrected.

[theprgramerdude]

Say, if the ellipse found was the black circle on the vision target, would the pixels measured for the ellipse distance be the outer edge of the detected ellipse or the inner edge?

Also, the PointFloat objects holding the center of the ellipse that was found, how are these measured? Are they measuring from the origin in the bottom left of the screen (i.e. top right could be 640x,480y)?

[Greg McKaskle]

The default vision code will combine two concentric ellipses which are about the same size. It will keep the radius of the one with the larger score, could be changed to preserve based on size instead.

In LV, the normalize step uses 0,0 as the center of the camera with negative to left and up and positive to right and down. I can't be certain of the Y axis without testing, but I think that is what it returns. The underlying Imaq uses 0,0 of top-left, I think.

Greg McKaskle

[theprgramerdude]

Sorry that I didn't make this clear before, but I was referring to the C++ DetectEllipse() method.

Each returned EllipseMatch struct has a double major axis and minor axis, as well as a PointFloat, score and rotation.

I'm slightly lost as to what each value is measured in. So is the PointFloat measured in terms of distance from the center, with each 1.0, 2.0, 3.0 value being the amount of pixels from that, or would it be measured in terms of the total screen length, as in .5 would be half way from the origin? The documentation simply lists it as the value of the coordinate in the coordinate system, and the coordinate system isn't any more helpful.