最佳圆拟合算法

本文介绍了最佳圆拟合算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 我需要一个非常精确的算法来将一个圆拟合到一组数据点（实际上我需要确定中心）。数据在图像的二值化和分割之后。 我尝试了简单的质心和质量加权中心算法，并且还预先做了OpenCv :: fitEllipse函数。我已经从OpenCV功能获得了最好的结果，但仍然，精度不够。当中心锚定在子像素区域中时，结果显着受损。 即使在处理建模数据时，我获得的精度也不够，这是不好的，因为最终，程序将必须处理由摄像机捕获的数据。 你有什么建议我应该寻找什么样的算法，或者你有任何现成的解决方案？我宁愿避免链接任何外部库。 感谢您的帮助。 编辑：校准目标可以定位在视场的任何区域。以下我用OpenCV过程获得的最佳结果： 169,367 748,345 167,557 820,788 165,690 893,158 164,047 965,197 162,715 1036,729 161,575 1108,089 160,477 1179,552 233,297 1015,313 232,076 1086,965 220,359 1229 ，578 268,494 1160,275 339,544 1162,980 362,017 1235,669 433,390 1238,491 482,754 1168,299 505,233 1241,039 554,85​​6 1170,664 577,302 1243,439 627,331 1172,795 649,507 1245,665 713,572 588,896 711,995 661,853 710,440 735,034 708,722 808,856 707,018 882,674 705,377 956,169 703,609 1029,211 701,716 1101,950 699,760 1174,689 721,895 1247,620 785,829 614,754 784,344 687,750 782,819 761,315 781,292 835,225 779,389 908,975 777,619 982,335 775,688 1055,275 773,672 1128 ，091 771,603 1200,724 编辑：数值生成模型和真实坐标中心： 51,1 79,8 51,1 179,8 51,1 279,8 51,1 379,8 51 ，1 479,8 51,1 579,8 51,1 679,8 51,1 779,8 51,1 879,8 51 ，1 979.8 51,1 1079,8 51,1 1179,8 51,1 1279,8 51,1 1379,8 51 ，1 1479.8 151,1 79,8 151,1 179,8 151,1 279,8 151,1 379,8 151 ，1 479,8 151,1 579,8 151,1 679,8 151,1 779,8 151,1 879,8 151 ，1 979.8 151,1 1079,8 151,1 1179,8 151,1 1279,8 151,1 1379,8 151 ，1 1479.8 251,1 79,8 251,1 179,8 251,1 279,8 251,1 379,8 251 ，1 479,8 251,1 579,8 251,1 679,8 251,1 779,8 251,1 879,8 251 ，1 979,8 251,1 1079,8 251,1 1179,8 251,1 1279,8 251,1 1379,8 251 ，1 1479.8 351,1 79,8 351,1 179,8 351,1 279,8 351,1 379,8 351 ，1 479,8 351,1 579,8 351,1 679,8 351,1 779,8 351,1 879,8 351 ，1 979,8 351,1 1079,8 351,1 1179,8 351,1 1279,8 351,1 1379,8 351 ，1 1479.8 451,1 79,8 451,1 179,8 451,1 279,8 451,1 379,8 451 ，1 479,8 451,1 579,8 451,1 679,8 451,1 779,8 451,1 879,8 451 ，1 979.8 451,1 1079,8 451,1 1179,8 451,1 1279,8 451,1 1379,8 451 ，1 1479.8 551,1 79,8 551,1 179,8 551,1 279,8 551,1 379,8 551 ，1 479,8 551,1 579,8 551,1 679,8 551,1 779,8 551,1 879,8 551 ，1 979,8 551,1 1079,8 551,1 1179,8 551,1 1279,8 551,1 1379,8 551 ，1 1479.8 651,1 79,8 651,1 179,8 651,1 279,8 651,1 379,8 651 ，1 479,8 651,1 579,8 651,1 679,8 651,1 779,8 651,1 879,8 651 ，1 979,8 651,1 1079,8 651,1 1179,8 651,1 1279,8 651,1 1379,8 651 ，1 1479.8 751,1 79,8 751,1 179.8 751,1 279,8 751,1 379,8 751 ，1 479,8 751,1 579,8 751,1 679,8 751,1 779,8 751,1 879,8 751 ，1 979.8 751,1 1079,8 751,1 1179,8 751,1 1279,8 751,1 1379,8 751 ，1 1479.8 851,1 79,8 851,1 179,8 851,1 279,8 851,1 379,8 851 ，1 479,8 851,1 579,8 851,1 679,8 851,1 779,8 851,1 879,8 851 ，1 979,8 851,1 1079,8 851,1 1179,8 851,1 1279,8 851,1 1379,8 851 ，1 1479.8 951,1 79,8 951,1 179,8 951,1 279,8 951,1 379,8 951 ，1 479,8 951,1 579,8 951,1 679,8 951,1 779,8 951,1 879,8 951 ，1 979,8 951,1 1079,8 951,1 1179,8 951,1 1279,8 951,1 1379,8 951 ，1 1479.8 1051,1 79,8 1051,1 179,8 1051,1 279,8 1051,1 379,8 1051 ，1 479,8 1051,1 579,8 1051,1 679,8 1051,1 779,8 1051,1 879,8 1051 ，1 979.8 1051,1 1079,8 1051,1 1179,8 1051,1 1279,8 1051,1 1379,8 1051 ，1 1479.8 1151,1 79,8 1151,1 179,8 1151,1 279,8 1151,1 379,8 1151 ，1 479,8 1151,1 579,8 1151,1 679,8 1151,1 779,8 1151,1 879,8 1151 ，1 979,8 1151,1 1079,8 1151,1 1179,8 1151,1 1279,8 1151,1 1379,8 1151 ，1 1479,8 解决方案 使用图像转换的算法群集 我使用图像转换和一些统计信息来构建一个小算法来检测您的圈子。让我们看看是否是由你的错误预期。 任何好的图像和统计库将做，我实现它使用Mathematica。 运行方法如下： 1.导入图像并运行Bottom Hat Transform 我们开始尝试隔离圈子。 优秀寻找定义明确的几何对象。它也很容易编程，并且几乎总是存在于图像库中。 c = Binarize @ HitMissTransform [b，DiskMatrix [20]] pre> 结果是： 我们的圈子已经被隔离并缩小到中心核心。 3.只从图像中获取白色像素 这是一个与实现相关的步骤，因此我不会评论这个。 ttflat = Flatten [Table [{i，j，ImageData [c] [[i，j] ]}，{i，1232}，{j，1624}]，1]; ttfilter =选择[ttflat，＃[[3]] == 1&]; 让我们看看剩下多少像素 Dimensions @ ttfilter {3684，3} 所以3684像素左，几乎82每个圆。足够做一些统计。 3.使用群集分析选择每个圈子 一个overkill在这里，但因为我已经实现了，是更容易使用它比程序的东西新:)。你可以做自己的或使用stats库。 ttc = FindClusters [ttfilter，45，Method - > {Agglomerate，Linkage - > 完成}]; 使用我们已经找到的集群，让我们找到每个集群中x和y的平均值。这些是圈子的中心： means = N [Mean / @ ttc，5] 结果是一个45坐标的列表，如： {{161.67，1180.1}，{162.75，1108.9}， {164.11，1037.6}，{165.47，966.19} ..... 我们差不多完成了。 让我们检查一下我们的结果。我们叠加了两个图像，在检测到的中心周围绘制十字和圆。 点击放大 ，以便您了解所涉及的错误。 HTH！ 编辑 我比较了你的表格的结果和我的结果。 假设圆圈是直线，我使用最小二乘法追踪线并计算残差。 形成下图，您可能会看到M线条比我们的Y线条更好。但这是假设圆圈对齐... 编辑2 45个圆圈在您的第二个图像。我有1个像素的系统偏移。可能是由于我做了一些图像处理，但很容易纠正:) ...只是减去一个像素在X和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.7}，{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}} 这是图片： 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: 169,367 748,345167,557 820,788165,690 893,158164,047 965,197162,715 1036,729161,575 1108,089160,477 1179,552233,297 1015,313232,076 1086,965220,359 1229,578268,494 1160,275339,544 1162,980362,017 1235,669433,390 1238,491482,754 1168,299505,233 1241,039554,856 1170,664577,302 1243,439627,331 1172,795649,507 1245,665713,572 588,896711,995 661,853710,440 735,034708,722 808,856707,018 882,674705,377 956,169703,609 1029,211701,716 1101,950699,760 1174,689721,895 1247,620785,829 614,754784,344 687,750782,819 761,315781,292 835,225779,389 908,975777,619 982,335775,688 1055,275773,672 1128,091771,603 1200,724Editted: The numerically generated model and the real coordinates of the centres:51,1 79,851,1 179,851,1 279,851,1 379,851,1 479,851,1 579,851,1 679,851,1 779,851,1 879,851,1 979,851,1 1079,851,1 1179,851,1 1279,851,1 1379,851,1 1479,8151,1 79,8151,1 179,8151,1 279,8151,1 379,8151,1 479,8151,1 579,8151,1 679,8151,1 779,8151,1 879,8151,1 979,8151,1 1079,8151,1 1179,8151,1 1279,8151,1 1379,8151,1 1479,8251,1 79,8251,1 179,8251,1 279,8251,1 379,8251,1 479,8251,1 579,8251,1 679,8251,1 779,8251,1 879,8251,1 979,8251,1 1079,8251,1 1179,8251,1 1279,8251,1 1379,8251,1 1479,8351,1 79,8351,1 179,8351,1 279,8351,1 379,8351,1 479,8351,1 579,8351,1 679,8351,1 779,8351,1 879,8351,1 979,8351,1 1079,8351,1 1179,8351,1 1279,8351,1 1379,8351,1 1479,8451,1 79,8451,1 179,8451,1 279,8451,1 379,8451,1 479,8451,1 579,8451,1 679,8451,1 779,8451,1 879,8451,1 979,8451,1 1079,8451,1 1179,8451,1 1279,8451,1 1379,8451,1 1479,8551,1 79,8551,1 179,8551,1 279,8551,1 379,8551,1 479,8551,1 579,8551,1 679,8551,1 779,8551,1 879,8551,1 979,8551,1 1079,8551,1 1179,8551,1 1279,8551,1 1379,8551,1 1479,8651,1 79,8651,1 179,8651,1 279,8651,1 379,8651,1 479,8651,1 579,8651,1 679,8651,1 779,8651,1 879,8651,1 979,8651,1 1079,8651,1 1179,8651,1 1279,8651,1 1379,8651,1 1479,8751,1 79,8751,1 179,8751,1 279,8751,1 379,8751,1 479,8751,1 579,8751,1 679,8751,1 779,8751,1 879,8751,1 979,8751,1 1079,8751,1 1179,8751,1 1279,8751,1 1379,8751,1 1479,8851,1 79,8851,1 179,8851,1 279,8851,1 379,8851,1 479,8851,1 579,8851,1 679,8851,1 779,8851,1 879,8851,1 979,8851,1 1079,8851,1 1179,8851,1 1279,8851,1 1379,8851,1 1479,8951,1 79,8951,1 179,8951,1 279,8951,1 379,8951,1 479,8951,1 579,8951,1 679,8951,1 779,8951,1 879,8951,1 979,8951,1 1079,8951,1 1179,8951,1 1279,8951,1 1379,8951,1 1479,81051,1 79,81051,1 179,81051,1 279,81051,1 379,81051,1 479,81051,1 579,81051,1 679,81051,1 779,81051,1 879,81051,1 979,81051,1 1079,81051,1 1179,81051,1 1279,81051,1 1379,81051,1 1479,81151,1 79,81151,1 179,81151,1 279,81151,1 379,81151,1 479,81151,1 579,81151,1 679,81151,1 779,81151,1 879,81151,1 979,81151,1 1079,81151,1 1179,81151,1 1279,81151,1 1379,81151,1 1479,8 解决方案 An Algorithm using Image Transformations and ClusteringI 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 TransformWe 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@"http://i.stack.imgur.com/hiSjj.png";b = BottomHatTransform[Binarize@a, BoxMatrix[30]]The result is 2. Run a Hit Miss Transform to isolate the circlesThe 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 imageThis 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 circleCluster 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!EditI 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 2These 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: 这篇关于最佳圆拟合算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！