image - 算法: Ellipse matching

Question

我有很多类似以下的图像(只有白色和黑色):



我的最后一个问题是找到匹配良好的椭圆。不幸的是，真正使用过的图像并不总是那么好。它们可能会变形一些，这使得椭圆匹配可能更困难。

我的想法是找到“断点”。我在下图中标记了它们:



也许这些要点可能有助于使椭圆匹配。最终结果应该是这样的:



有人知道可以使用什么算法找到这些断点吗？甚至更好地进行良好的椭圆匹配？

非常感谢你

Answer 1

采样圆周点

只需扫描图像，然后选择所有白色邻居的全黑像素即可。您可以通过将剩余的黑色像素重新着色为任何未使用的颜色(蓝色)来实现此目的。

完成整个图像后，您可以将内部背面从未使用的颜色(蓝色)重新着色为白色。

形成每个簇/椭圆的有序圆周点列表

只需扫描图像并找到第一个黑色像素即可。然后使用A*对圆周点进行排序，并将路径存储在某个数组中，或者列出pnt[]并将其作为圆形数组进行处理。

查找“断点”

可以通过找到的点的相邻点之间的夹角中的峰值来检测它们。就像是

float a0=atan2(pnt[i].y-pnt[i-1].y,pnt[i].x-pnt[i-1].x);
float a1=atan2(pnt[i+1].y-pnt[i].y,pnt[i+1].x-pnt[i].x);
float da=fabs(a0-a1); if (da>M_PI) da=2.0*M_PI-da;
if (da>treshold) pnt[i] is break point;

或使用在断裂点上的坡度角变化符号的事实:

float a1=atan2(pnt[i-1].y-pnt[i-2].y,pnt[i-1].x-pnt[i-2].x);
float a1=atan2(pnt[i  ].y-pnt[i-1].y,pnt[i  ].x-pnt[i-1].x);
float a2=atan2(pnt[i+1].y-pnt[i  ].y,pnt[i+1].x-pnt[i  ].x);
float da0=a1-a0; if (da0>M_PI) da0=2.0*M_PI-da0; if (da0<-M_PI) da0=2.0*M_PI+da0;
float da1=a2-a1; if (da1>M_PI) da1=2.0*M_PI-da1; if (da1<-M_PI) da1=2.0*M_PI+da1;
if (da0*da1<0.0) pnt[i] is break point;

适合椭圆

因此，如果找不到断点，则可以将整个pnt []设置为单个椭圆。例如，查找边界框。它的中心是椭圆的中心，它的大小为您提供半轴。

如果找到断点，则首先找到整个pnt[]的边界框，以获取半轴和中心位置区域搜索的限制。然后将pnt[]划分为断点之间的部分。将每个零件作为椭圆和合适的单独零件来处理。

安装完所有pnt[]部分之后，检查某些椭圆是否不相同，例如，如果它们与另一个椭圆重叠，则将它们分开...因此合并相同的椭圆(或取平均值以提高精度)。然后将所有pnt[i]点重新着色为白色，清除pnt[]列表并循环＃2 ，直到找不到更多黑色像素为止。

如何通过选择点来拟合椭圆？

代数

使用具有“均匀”分散的已知点的椭圆方程来形成方程系统以计算椭圆参数(x0,y0,rx,ry,angle)。

几何

例如，如果您检测到0,90,180或270度的坡度，则您处于与圆周的半轴相交处。因此，如果您得到两个这样的点(每个半轴一个)，则需要进行拟合(如果它是与轴对齐的椭圆)。

对于非轴对齐的椭圆，您需要有足够大的周长可用部分。您可以利用边界框的中心也是椭圆的中心这一事实。因此，如果您获得整个椭圆，那么您也知道中心。可以以最大和最小的切线变化检测具有圆周的半轴相交。如果您获得了中心和两分，则只需要一个。如果只有部分中心(只有x或y坐标)，则可以与更多轴点结合(找到3或4)...或近似缺少的信息。

同样，H，V线的一半轴与椭圆中心相交，因此，如果不是pnt[]列表中的整个椭圆，则可以使用它来检测它。

近似搜索

您可以在＃4 中找到的限制内，遍历椭圆参数的“所有”可能组合，然后选择最接近您的点的椭圆参数。粗略地会很慢，因此请使用二进制搜索，例如我的approx class之类的方法。另请参阅

Curve fitting with y points on repeated x positions (Galaxy Spiral arms)

关于如何将其用于与您的产品相似的匹配。

混合

您可以结合使用几何方法和近似方法。首先通过几何方法计算出您可以做的事情。然后使用近似搜索计算其余部分。您还可以提高找到的值的精度。

在极少数情况下，当两个椭圆合并而没有断点时，拟合的椭圆将与您的点不匹配。因此，如果检测到这种情况，则必须将使用的点分割为组，直到其适合为止...
这就是我要记住的: