# Detecting Ellipses in Images

Brett's Pick this week is `Ellipse Detection Using 1D Hough Transform`, by Martin Simonovsky.

### Contents

#### Introduction

I've written several times in the past about detecting circles in images (here, here, and here). I've written, too, on drawing ellipses. Today, I want to write about *detecting 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's `ellipseDetection()` 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*, in your search image. You'll almost certainly want to operate on an "edge image" rather than a simple binary mask of your regions of interest, and to play with the function's nine input parameters to limit the search. Among these parameters, you can specify the range of major axes lengths to consider, and the minimum aspect ratio. You may also specify some parameters for limiting the angles of the ellipses you seek; this could be very useful if you know the ellipse orientations *a priori*. Even after such limits are used, an exhaustive search examines *N* x *N* candidates 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 from *N* x *N* to *N* x randomize. If randomize is 0, then the search is exhaustive--increased accuracy at a computational cost.)

#### A Test Drive

So let's try it out on a sample image of our creation. We can start with an image containing circles, and warp it to generate ellipses:

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

I *segmented* the image by:

- Using the colorThresholder to create a mask of the background
- Splitting the color image into R, G, and B components (
`imsplit`) - Masking the R, G, and B planes individually (
`R(backgroundMask) = 0`, ...) - Re-compositing the masked planes into an RGB image (
`cat`) - Converting the masked RGB image to grayscale (
`im2gray`) - Calculating (with carefully selected input parameters) the edges of the grayscale image (
`edge`) - Filtering the results to select the desired Major Axes Lengths and Areas (
`imageRegionAnalyzer`,`bwpropfilt`)

In just a few minutes, I had an edge image in which 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, calling `ellipseDetection()` on the binary mask of the warped chips *without* first 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 used `imdistline` to measure the major and minor axes lengths:

Then I used `protractor` to 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 search params.numBest = 30; %(Number of chips = 26)

bestFits = ellipseDetection(edgeMask, params);

#### Paring Results

Wait...what? `bestFits` contains 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 dramatically *overspecify* the 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 wrote `pareResults` to 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 wrote `visualizeEllipses` to call `drawellipse` directly on the output of `ellipseDetection`.

#### 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 7 -10 7 7 -4 -47 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 via `fspecial`. That syntax is no longer recommended; the newer `imgaussfilt` is more efficient. Also, the call to `fspecial` requires an *integer* argument for the second (`'hsize'`) parameter. (I added a call to `round()` in my version.) Finally, since getting good results requires tuning a number of parameters, this function is just *begging* for 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 your thoughts and comments.

**범주:**- Picks

## 댓글

댓글을 남기려면 링크 를 클릭하여 MathWorks 계정에 로그인하거나 계정을 새로 만드십시오.