算法：椭圆匹配

Question

算法：椭圆匹配

imagealgorithmellipse

5

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

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

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

也许这些要点可以帮助匹配椭圆形。最终结果应该像这样：

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

非常感谢。

- Kevin Meier

你考虑使用哪种编程语言？如果你在谷歌上搜索许多语言名称加上“将位图转换为SVG”，你可以找到一些技巧。这篇帖子很有趣（作为“信息熵”的讨论）：https://dev59.com/9U7Sa4cB1Zd3GeqP4Ifu - Baronz

我也喜欢Walter的想法。更正式地说：椭圆焦点是否具有相同的Y坐标值？ - Baronz

很遗憾，椭圆可能会倾斜（椭圆焦点的y坐标值可能不同）。首先，语言并不重要。感谢提供有关svg技术的链接:) - Kevin Meier

@KevinMeier 这些省略号是否总是与坐标轴对齐？ - Spektre

不好意思，很遗憾。 - Kevin Meier

显示剩余2条评论

3个回答

2

你可能需要这样的东西：

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

“您的边缘点是至少有一个白色4邻域的黑色像素。”

“不幸的是，您说您的椭圆可能是‘倾斜的’。通用的椭圆由二次方程描述，例如”

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

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

参见：图像中检测圆的算法。

编辑

上述算法的想法过于乐观，至少如果直接应用。好消息是，似乎有两个聪明的人（谢永红和季强）已经为我们做好了功课：

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

- Walter Tross

图像分辨率可高达512*512像素，包含约200个椭圆。有时会出现10-20个椭圆的聚类，但这些只是非常困难的情况。感谢您的输入:)！ - Kevin Meier

1

我不确定是否要创建自己的算法。为什么不利用其他团队已经完成的工作，来解决所有的位图曲线拟合问题呢？

INKSCAPE (应用链接)

Inkscape是一款开源工具，专门用于矢量图形编辑，并具有一定的位图处理能力。

以下是Inkscape API的入门链接:

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 (应用链接)

Corel Draw被公认为矢量图形的首选行业解决方案，并具有将光栅图像转换为矢量图像的强大工具。

这是他们API的链接：

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

这是一个关于Corel Draw批量图像处理（非脚本解决方案）的链接：

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

- Baronz

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

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

- Spektre · Accepted Answer

Sample the circumference points

Just scan your image and select All Black pixels with any White neighbor. You can do this by recoloring the remaining black pixels to any unused color (Blue).

After whole image is done you can recolor the inside back from unused color (Blue) to white.
form a list of ordered circumference points per cluster/ellipse

Just scan your image and find first black pixel. Then use A* to order the circumference points and store the path in some array or list pnt[] and handle it as circular array.

Find the "break points"

They can be detect by peak in the angle between neighbors of found points. something like

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;

or use the fact that on break point the slope angle delta change sign:

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;

fit ellipses

so if no break points found you can fit the entire pnt[] as single ellipse. For example Find bounding box. It's center is center of ellipse and its size gives you semi-axises.

If break points found then first find the bounding box of whole pnt[] to obtain limits for semi-axises and center position area search. Then divide the pnt[] to parts between break points. Handle each part as separate part of ellipse and fit.

After all the pnt[] parts are fitted check if some ellipses are not the same for example if they are overlapped by another ellipse the they would be divided... So merge the identical ones (or average to enhance precision). Then recolor all pnt[i] points to white, clear the pnt[] list and loop #2 until no more black pixel is found.
how to fit ellipse from selection of points?
1. algebraically
  
  use ellipse equation with "evenly" dispersed known points to form system of equations to compute ellipse parameters (x0,y0,rx,ry,angle).
2. geometrically
  
  for example if you detect slope 0,90,180 or 270 degrees then you are at semi-axis intersection with circumference. So if you got two such points (one for each semi-axis) that is all you need for fitting (if it is axis-aligned ellipse).
  
  for non-axis-aligned ellipses you need to have big enough portion of the circumference available. You can exploit the fact that center of bounding box is also the center of ellipse. So if you got the whole ellipse you know also the center. The semi-axises intersections with circumference can be detected with biggest and smallest tangent change. If you got center and two points its all you need. In case you got only partial center (only x, or y coordinate) you can combine with more axis points (find 3 or 4)... or approximate the missing info.
  
  Also the half H,V lines axis is intersecting ellipse center so it can be used to detect it if not whole ellipse in the pnt[] list.
3. approximation search
  
  You can loop through "all" possible combination of ellipse parameters within limits found in #4 and select the one that is closest to your points. That would be insanely slow of coarse so use binary search like approach something like mine approx class. Also see
  - Curve fitting with y points on repeated x positions (Galaxy Spiral arms)
  on how it is used for similar fit to yours.
4. hybrid
  
  You can combine geometrical and approximation approach. First compute what you can by geometrical approach. And then compute the rest with approximation search. you can also increase precision of the found values.
In rare case when two ellipses are merged without break point the fitted ellipse will not match your points. So if such case detected you have to subdivide the used points into groups until their fits matches ...

这是我对此的想法:

请注意，这里只是一张图片，没有文字说明。