算法:椭圆匹配

Question

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

我最后的问题是找到匹配良好的椭圆.不幸的是,真正使用过的图像并不像这样.它们可能会变形一些,这使得椭圆匹配可能更难.

我的想法是找到"断点".我在下面的图片中标记它们:

也许这些点可以帮助匹配省略号.最终结果应该是这样的:

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

非常感谢你

Answer 1

1. 对圆周点进行采样

   只需扫描您的图像并选择带有任何白色邻居的全黑像素。您可以通过将剩余的黑色像素重新着色为任何未使用的颜色（蓝色）来实现此目的。

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

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

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

3. 找到“断点”

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

   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;
   

4. 拟合椭圆

   因此，如果没有找到断点，您可以将整个 pnt[] 拟合为单个椭圆。例如查找边界框。它的中心是椭圆的中心，它的大小给出了半轴。

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

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

5. 如何从点的选择中拟合椭圆？

   1. 代数地

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

   2. 几何地

      例如，如果您检测到坡度 0、90、180 或 270 度，那么您就处于与圆周的半轴相交处。因此，如果您有两个这样的点（每个半轴一个），这就是拟合所需的全部内容（如果它是轴对齐的椭圆）。

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

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

      

   3. 近似搜索

      您可以在#4中找到的限制内循环遍历“所有”可能的椭圆参数组合，并选择最接近您的点的一个。这会非常慢，所以使用像我的approx class这样的二分搜索方法。另请参阅

      • 在重复的 x 位置上使用 y 点进行曲线拟合（银河螺旋臂）

      关于如何使用它来与您的类似。

   4. 杂交种

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

   在极少数情况下，当两个椭圆在没有断点的情况下合并时，拟合的椭圆将与您的点不匹配。因此，如果检测到这种情况，您必须将使用的点细分为组，直到它们适合匹配......

这就是我的想法：