Brett's Pick this week isEllipse Detection Using 1D Hough Transform, byMartin Simonovsky。

Contents

Introduction

I've written several times in the past about detecting circles in images (这里,这里, and这里). I've written, too, ondrawing ellipses。Today, I want to write aboutdetecting ellipses。

Since ellipses are described by more parameters than are lines or circles, detecting ellipses is more challenging than is detecting lines or circles. And while we have nice functionality for detecting the simpler shapes (houghlines,imfindcircles), we do not (currently) have a function to detect ellipses. Enter Martin's ellipse-detection function.

The Source

Fortunately, and appropriately, Martin cited the source for his algorithm; he used a paper (Y. Xie, Q. Ji. "A New Efficient Ellipse Detection Method." 1051-4651/02 IEEE, 2002) that I have had on my desk for quite some time, thinking that I would one day sit down to implement it in MATLAB code. I love that Martin did that work for me--it makes me appreciate the File Exchange all the more.

The Implementation

After playing around with Martin'sellipseDetection()for most of an afternoon, I have some thoughts to share. First, recognize that ellipse detection is an expensive memory hog; the computation scales with the square of the number of nonzero pixels,N，在您的搜索图像中。几乎可以肯定，您想在“边缘图像”上操作，而不是您感兴趣的区域的简单二进制掩码，并使用函数的九个输入参数来限制搜索。在这些参数中，您可以指定要考虑的主要轴长度和最小纵横比的范围。您还可以指定一些参数以限制所寻求的椭圆的角度；如果您知道椭圆方向，这可能非常有用a priori。即使使用了此类限制，详尽的搜索检查NxNcandidates for major axes. Martin's function provides a parameter that allows you to trade off between speed and accuracy. (The "randomize" parameter is not a Boolean variable, as the name suggests; rather it reduces the search space fromNxNtoNx randomize. If randomize is 0, then the search is exhaustive--increased accuracy at a computational cost.)

A Test Drive

因此，让我们在我们创建的示例图像上尝试一下。我们可以从包含圆圈的图像开始，然后翘曲以生成椭圆：

inputImage = imread('coloredChips.png'); tform = affine2d([1 0 0; 0.75 1 0; 0 0 1]); inputImage = imwarp(inputImage, tform); imshow(inputImage) title("Test Image")

Segmentation

Isegmentedthe image by:

在短短几分钟,我有一个边缘图像摘要h to detect those ellipses:

Detecting the Ellipses

With this binary edge mask in hand, I was ready to search for ellipses--first, naively:

bestFits = ellipseDetection(edgeMask);

The operation completed in (just) less than a second, but the results were underwhelming:

(By the way, callingellipseDetection()on the binary mask of the warped chipswithoutfirst calculating the edges took upwards of 20 minutes, and the results were even worse!)

Improving the Results

To improve the performance, I judiciously selected input parameters to reduce the computational cost. First, I usedimdistlineto measure the major and minor axes lengths:

Then I usedprotractorto get a sense of the orientations of the ellipses:

After a few minutes, I found my way to:

params.minMajorAxis = 55; params.maxMajorAxis = 75; params.minAspectRatio = 0.4;%1 = circle; 0 = line;params.rotation = 35; params.rotationSpan = 10; params.randomize = 0;%Exhaustive searchparams.numBest = 30;%(Number of chips = 26)

bestFits = ellipseDetection(edgeMask, params);

Paring Results

Wait...what?bestFitscontains paramaters for 30 detections (a manual count informs me that there are 26 ellipses wholly contained in the image), but when visualizing the results, it appears that there are far fewer. What's going on?

It turns out that the algorithm is susceptible to reporting the same ellipse multiple times. (If I drag those cyan ellipses, there are other coincident ellipses underneath!)

Experimenting, I found it quite useful to dramaticallyoverspecifythe number of ellipses I wanted to detect, then to pare the results in post-processing. Consider:

params.smoothStddev = 0.5; params.numBest = 1000;%(Number of chips = 26)bestFits = ellipseDetection(edgeMask, params); minCenterDistance = 10; minScore = 30; maxAspectRatio = 0.6; bestFits = pareEllipseFits(bestFits,。。。minCenterDistance, minScore, maxAspectRatio);

I wrotepareResultsto allow filtering by minimum center distance (to disallow overlapping detections), minimum score, and maximum aspect ratio. Using that paring approach, I can request far more detections (params.numBest = 1000) than I really want, then discard "bad" results. I'm pretty pleased with the way it's working!

A Note on Visualizing the Results

Finally, I also wrotevisualizeEllipsesto calldrawellipsedirectly on the output ofellipseDetection。

Notes

In the interest of making this post a bit shorter (I know...too late!), I didn't post all of the code. If anyone would like to see it, I'm happy to share. Just drop me an email at:

char (cumsum ([98 17 -11 -47 -10 7 7 4 45 12 19 -12 15 -8 3 -7 8 -69 53 12 -2]))

Also, there are a few other files on the Exchange that purport to facilitate ellipse detection. Please leave me a comment if you'd like to see those considered those in a subsequent post!

A Couple of Suggestions

Martin's implementation uses Gaussian filtering viafspecial。That syntax is no longer recommended; the newerimgaussfiltis more efficient. Also, the call tofspecialrequires anintegerargument for the second ('hsize') parameter. (I added a call toround()in my version.) Finally, since getting good results requires tuning a number of parameters, this function is justbeggingfor a code-generating app to front it; that's perhaps a project for another day!

Thank you, Martin...finding this function, and figuring out how to use it, gives me a valuable tool in my image processing arsenal.

As always, I welcome yourthoughts and comments。

Get the MATLAB code

Published with MATLAB® R2022a