The best circle fitting algorithm

Question

I need a very precise algorithm for fitting a circle to the set of data points (actually I need to determine the center). The data comes after the binarization and segmentation of the image. I tried simple center of mass and weighted center of mass algorithms and also pre-made OpenCv::fitEllipse function. I have obtained the best results from OpenCV function, but still, the accuracy is not sufficient. The results are impaired significantly, when the center is anchored in subpixel regions. The accuracy I obtained is not sufficient even when dealing with the modeled data, which is bad, as eventually, the procedure will have to deal with the data captured by comeras. Have you got any suggestions what kind of algorithm should I look for or have you got any ready solution? I would rather refrain from linking any external libs. Thanks for your help. edited: Calibration target can be localizaed in any region of the field of view. Hereunder the best results I acieved with OpenCV procedure: ``…

Accepted Answer

An Algorithm using Image Transformations and Clustering

I made up a small Algorithm using Image Transformations and some Statistic to detect your circles. Let's see if it is up to your error expectation. Any good image and statistics library will do, I implemented it using Mathematica.

Run as follows:

1. Import your image and run a Bottom Hat Transform

We start trying to isolate the circles. The Bottom Hat Transform with a Box Matrix kernel helps. Almost any image library comes with the algorithm already implemented.

```
a = Import@"https://i.stack.imgur.com/hiSjj.png";   
b = BottomHatTransform[Binarize@a, BoxMatrix[30]]  
```

The result is

2. Run a Hit Miss Transform to isolate the circles

The Hit Miss Transform excels in finding well defined geometrical objects. It is also easy to program and is almost always present in image libraries.

```
c = Binarize@HitMissTransform[b, DiskMatrix[20]]
```

The result is:

And our circles are already isolated and reduced to their central core.

3. Get just the white pixels from image

This is an implementation-dependent step, so I'll not comment on this one.

```
ttflat = Flatten[Table[{i, j, ImageData[c][[i, j]]}, {i, 1232}, {j, 1624}], 1];  
ttfilter = Select[ttflat, #[[3]] == 1 &];  
```

Let's see how many pixels are left

```
Dimensions@ttfilter  
{3684, 3}   
```

So 3684 pixels left, almost 82 per circle. Enough to do some statistics.

3. Use Cluster Analysis to pick each circle

Cluster Analysis may be an overkill here, but as I have it already implemented, is easier to use it than program something new :). You may do your own or use a stats library.

```
ttc = FindClusters[ttfilter, 45, Method -> {"Agglomerate", "Linkage" -> "Complete"}];
```

With our clusters already found, let's find the mean for x and y in each cluster. Those are the centers of the circles:

```
means = N[Mean /@ ttc, 5]  
```

The result is a list of 45 coordinates like:

```
{{161.67, 1180.1}, {162.75, 1108.9}, 
 {164.11, 1037.6}, {165.47, 966.19} .....  
```

We are almost done.

Let's check our result. We superimposed both images, drawing crosses and circles around the detected centers.

Click to enlarge, so you may get an idea of the errors involved.

HTH!

Edit

I compared the results from your table with my results.

Assumming the circles are in straight lines, I used Least Squares Fit to trace a line and calculated the residuals.

Form the graph below, you may see that "M"y line fit better than "Y"ours. But that is assuming the circles aligned ...

Edit 2

These are the calculated coordinates for the first 45 circles in your second image. I have a systematic offset of 1 pixel. Probably due to some image manipulation I did, but is easy to correct :) ... just subtracted one pixel on X and Y ...

```
{{51.135, 79.692}, {51.135, 179.69}, {51.135, 279.69},{51.135, 379.69}, {51.135, 479.69},
 {51.135, 579.69}, {51.135, 679.69}, {51.135, 779.69},{51.135, 879.69}, {51.135, 979.69}, 
 {51.135, 1079.7}, {51.135, 1179.7}, {51.135, 1279.7},{51.135, 1379.7}, {51.135, 1479.7}, 
 {151.13, 79.692}, {151.13, 179.69}, {151.13, 279.69},{151.13, 379.69}, {151.13, 479.69},
 {151.13, 579.69}, {151.13, 679.69}, {151.13, 779.69},{151.13, 879.69}, {151.13, 979.69}, 
 {151.13, 1079.7}, {151.13, 1179.7}, {151.13, 1279.7},{151.13, 1379.7}, {151.13, 1479.7}, 
 {251.13, 79.692}, {251.13, 179.69}, {251.13, 279.69},{251.13, 379.69}, {251.13, 479.69}, 
 {251.13, 579.69}, {251.13, 679.69}, {251.13, 779.69},{251.13, 879.69}, {251.13, 979.69}, 
 {251.13, 1079.7}, {251.13, 1179.7}, {251.13, 1279.7},{251.13, 1379.7}, {251.13, 1479.7}}
```

And this is the image:

The best circle fitting algorithm

Solution

Problem