最佳圆拟合算法

Question

最佳圆拟合算法

13

我需要一个非常精确的算法来适应数据点集的圆（实际上我需要确定中心）。数据在图像二值化和分割之后得到。我尝试了简单的质心和加权质心算法，还尝试了预制的OpenCV :: fitEllipse函数。虽然我从OpenCV函数中获得了最佳结果，但仍然不够准确。当中心固定在亚像素区域时，结果会受到显著影响。即使处理模拟数据时获得的精度也不足够，这很糟糕，因为最终该过程将不得不处理由相机捕获的数据。您有什么建议，应该寻找什么样的算法，或者是否有任何已准备好的解决方案？我宁愿不链接任何外部库。感谢您的帮助。 alt text

编辑：校准目标可以在视野的任何区域进行定位。以下是我使用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,856 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

编辑后：数值生成的模型和中心点的真实坐标： alt text

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

- Marcin

请提供一个示例图像，展示您正在尝试匹配的圆。同时，提供一张不匹配的圆的图像将有助于理解问题所在。 - sastanin

请发布您的样本图像的预期中心位置以比较结果。 - Dr. belisarius

我是说我已经发布的图像包含“蛋形”。也许我夸大了问题，相机无法将圆形看作理想的圆形。我将在几分钟内发布一张模型图像，其中包含众所周知的中心位置，以测试您的程序。 - Marcin

+1给那个迷幻的点点图片点赞！ :) - Will Ness

5个回答

3

“最佳”取决于输入数据中的噪声类型。如果源数据点没有噪声，那么这个问题是微不足道的：只需选择3个点并计算圆。

如果您预期每个数据点都有正态分布和独立的偏移量，则最小均方算法应该是最优的。数据点应符合以下方程：

(x - xm)^2 + (y - ym)^2 = r^2

其中xm、ym和r都是未知的，因此：

x^2 - 2*x*xm + xm^2 + y^2 - 2*y*ym + ym^2 = r^2

将c代替r^2-xm^2-ym^2，您就得到了一个超定线性方程组：

2*x*xm + 2*y*ym = c - x^2 - y^2

任何好的线性代数库（例如IPP）都可以为您解决这个问题。

如果您预计数据中存在异常值，我建议使用RANSAC策略找到非异常点集，然后使用上述算法找到该集合的精确中心。

- Niki

问题是图像数据来自相机。我正在捕获校准目标类型的图像，其中包含一组圆形标记。经过二值化处理后，边缘不必均匀分布在中心周围。此外，当从一个角度观察圆时，圆会变形成“鸡蛋”形状。也许应该采用另一个模型（而不是圆）来近似中心？ - Marcin

最小二乘拟合与简单的质心算法得到了类似的结果。看起来这个方法并不足够。 - Marcin

如果图像失真是由于光学问题，并且这些问题很重要，那么你需要做的第一件事就是校准和去除畸变（可能还需要矫正图像）。如果你使用OpenCV，请参考http://opencv.willowgarage.com/documentation/camera_calibration_and_3d_reconstruction.html#undistort2。然后，你可以应用任何你喜欢的圆匹配算法。 - sastanin

@Marcin 如果相机倾斜，您不应匹配圆形...此外，如果这是相机校准过程，请在问题中明确说明。 - Dr. belisarius

这是一种测量系统校准程序，通常在标准相机校准之后进行。我在第一个条目中发布了一张样例图片。 - Marcin

3

为了以亚像素精度找到圆的中心，如果圆的半径已知（且恒定），我使用以下方法：

拍摄一张只有一个圆的图像（以下称为标记）。其半径应与您想要查找的圆的半径相同。
检测边缘（Sobel梯度的大小，然后进行一些阈值处理以去除低强度边缘），在测试图像和翻转的标记图像中都进行。此阶段我不会应用边缘变细，并且不确定边缘上的确切点。
将测试图像的边缘与翻转的标记的边缘进行交叉相关。您会得到一些峰值，其中包含圆心的位置。
以亚像素精度找到峰值中心。质心或拟合2D高斯钟可能效果很好。
添加对应于标记中圆心已知位置的位移。

否则，如果已知圆上的点具有足够的精度，则最小均方拟合应解决查找中心的问题（请参见@nikie的答案）。

- sastanin

3

看看霍夫变换。它可以用来检测圆形。

- Alejandro

我之前了解过霍夫变换。我知道它用于检测圆形，但你知道在中心确定方面可以达到什么样的近似精度吗？ - Marcin

@Marcin 这取决于您如何离散化中心/半径空间。好处是您可以利用相邻的圆，因为它们在一条线上且等距离。只需将圆心所在的线的参数添加到您的霍夫空间即可。 - Roman Shapovalov

1

OpenCV 2.4.6.0有一个findCirclesGrid函数，用于查找网格中圆的中心。

- Alessandro Jacopson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dr. belisarius · Accepted Answer

使用图像变换和聚类的算法

我使用图像变换和一些统计方法编写了一个小型算法来检测圆形。让我们看看它是否符合您的误差期望。
任何良好的图像和统计库都可以胜任此任务，我是在Mathematica中实现它的。

按照以下步骤运行：

1.导入您的图像并运行Bottom Hat Transform

我们开始尝试隔离圆。使用盒状核的Bottom Hat Transform能够帮助我们。几乎任何图像库都已经实现了该算法。

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

结果是

alt text

2. 运行Hit Miss Transform以隔离圆形

Hit Miss Transform 在查找明确定义的几何对象方面表现出色。它也很容易编程，并且几乎总是存在于图像库中。

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

结果是：

alt text

我们的圆已经被隔离并缩小到它们的中心核心。

3. 仅从图像中获取白色像素

这是一个依赖于实现的步骤，所以我不会对此进行评论。

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

让我们看看还剩下多少像素

Dimensions@ttfilter  
{3684, 3}

还剩下3684个像素，几乎每个圆周82个。已经足够进行一些统计了。

3. 使用聚类分析来选择每个圆

在这里可能使用聚类分析有点过度，但我已经实现了它，使用它比编写新程序更容易 :). 你可以自己编写或使用统计库。

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

我们已经找到了聚类，现在让我们为每个聚类中的x和y找到平均值。这些是圆心：

means = N[Mean /@ ttc, 5]

结果是一个包含45个坐标的列表，如下所示：

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

我们快要完成了。

让我们检查一下结果。我们叠加了两个图像，在检测到的中心周围画上十字和圆圈。

点击放大，这样你就可以了解到涉及的误差。

希望对你有所帮助！

编辑

我将你表格中的结果与我的结果进行了比较。

假设圆圈在直线上，我使用最小二乘法来跟踪一条线，并计算残差。

从下面的图表中，您可以看到“M”我的拟合线比“Y”你的更好。但这是假设圆圈对齐的情况下... alt text

编辑2

这些是第二张图像中前45个圆圈的计算坐标。我有一个像素的系统偏移。可能是由于我做的某些图像处理造成的，但很容易纠正 :) ... 只需在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.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}}

这是图片：

alt text