算法：椭圆匹配

Question

我有很多像下面这样的图片（只有白色和黑色）：

我的最后一个问题是找到匹配良好的椭圆。不幸的是，实际使用的图像并不总是像这样好。它们可能会变形一点，这使得椭圆匹配可能更难。

我的想法是找到"break points"。我在下面的图片中标记它们：

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

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

非常感谢

Answer 1

您可能需要这样的东西：

https://en.wikipedia.org/wiki/Circle_Hough_Transform

你的边缘点只是黑色像素，至少有一个白色 4-neighbor。

不幸的是，你说你的省略号可能是“倾斜的”。通用椭圆由二次方程描述，如

x² + Ay² + Bxy + Cx + Dy + E = 0

B² < 4A (⇒ A > 0)。这意味着，与圆问题相比，您没有 3 个维度而是 5 个维度。这导致 Hough 变换相当困难。幸运的是，您的示例表明您不需要高分辨率。

另请参阅：algorithm for detecting a circle in an image

编辑

上述算法的想法是 too optimistic，至少如果以直接的方式应用的话。好消息是，两位聪明人（谢永红和季强）似乎已经为我们做了功课：

https://www.ecse.rpi.edu/~cvrl/Publication/pdf/Xie2002.pdf

Answer 2

我不确定我是否会创建自己的算法。为什么不利用其他团队所做的工作来找出位图的所有曲线拟合？

INKSCAPE (App Link)

Inkscape 是一种开源工具，专门用于矢量图形编辑，并且还具有处理光栅（位图）部分的能力。

这是 Inkscape API 的起点 link:

http://wiki.inkscape.org/wiki/index.php/Script_extensions

看来您可以在 Inkscape 中编写脚本，或通过外部脚本访问 Inkscape。

您也可以从 inkscape 命令行界面使用零脚本来做一些事情：

http://wiki.inkscape.org/wiki/index.php/Frequently_asked_questions#Can_Inkscape_be_used_from_the_command_line.3F

COREL DRAW (App Link)

Corel Draw 被公认为业界首屈一指的矢量图形解决方案，并且有一些很棒的工具可以将光栅化图像转换为矢量图像。

这是他们 API 的 link:

https://community.coreldraw.com/sdk/api

这里有一个link对Corel Draw批量图像处理（非脚本解决方案）：

http://howto.corel.com/en/c/Automating_tasks_and_batch-processing_images_in_Corel_PHOTO-PAINT

Answer 3

采样圆周点数

只需扫描您的图像，然后 select 全黑像素与任何白色相邻像素。您可以通过将剩余的黑色像素重新着色为任何未使用的颜色（蓝色）来做到这一点。

完成整个图像后，您可以将内部背面从未使用的颜色（蓝色）重新着色为白色。
形成每个cluster/ellipse
的有序圆周点列表
只需扫描您的图像并找到第一个黑色像素。然后使用 A* 对圆周点进行排序并将路径存储在某个数组或列表中 pnt[] 并将其作为循环数组处理。

找到"break points"

它们可以通过发现点的相邻点之间的角度峰值来检测。像

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 直到找不到更多的黑色像素。
如何从 selection 点拟合椭圆？
1. 代数
  
  使用具有"evenly"个分散已知点的椭圆方程组成方程组来计算椭圆参数(x0,y0,rx,ry,angle)。
2. 几何
  
  例如，如果您检测到坡度为 0、90、180 或 270 度，则您处于与圆周的半轴相交处。因此，如果您有两个这样的点（每个半轴一个），这就是您拟合所需的全部（如果它是轴对齐的椭圆）。
  
  对于非轴对齐的椭圆，您需要有足够大的可用圆周部分。您可以利用边界框的中心也是椭圆的中心这一事实。所以如果你得到整个椭圆，你也知道中心。半轴与圆周的交点可以用最大和最小的切线变化来检测。如果你有中心和两分，这就是你所需要的。如果你只有部分中心（只有 x 或 y 坐标），你可以结合更多的轴点（找到 3 或 4）......或近似缺失的信息。
  
  半个 H,V 线轴与椭圆中心相交，因此如果不是 pnt[] 列表中的整个椭圆，它可以用来检测它。
3. 近似搜索
  
  您可以在 #4 和 select 中找到的限制范围内遍历 "all" 可能的椭圆参数组合，最接近您的点。那将是非常慢的粗糙所以使用像我的方法一样的二进制搜索 approx class。另见
  关于它如何用于与您的相似。
4. 混合
  
  您可以结合几何方法和近似方法。首先用几何方法计算你能做什么。然后用近似搜索计算其余部分。您还可以提高找到的值的精度。
在极少数情况下，当两个椭圆在没有断点的情况下合并时，拟合的椭圆将与您的点不匹配。因此，如果检测到这种情况，您必须将使用的点细分为组，直到它们的匹配匹配...

这就是我的想法：

算法：椭圆匹配

Algorithms: Ellipse matching

image

algorithm

ellipse

INKSCAPE (App Link)

COREL DRAW (App Link)