algorithm:椭圆匹配

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

在这里输入图像描述

我最后的问题是find匹配的椭圆。 不幸的是,真正使用的图像并不总是那么好。 他们可能会变形一点,这使得椭圆匹配可能更难。

我的想法是find“断点”。 我在下面的图片中标记它们:

在这里输入图像描述

也许这些点可以帮助做一个椭圆匹配。 最终的结果应该是这样的:

在这里输入图像描述

有人知道什么algorithm可以用来find这些断点吗? 或者更好的做出好的椭圆匹配?

非常感谢你

  1. 采样圆周点

    只需扫描您的图像,并select与任何白色邻居的所有黑色像素。 您可以通过将剩余的黑色像素重新着色为任何未使用的颜色(蓝色)来实现。

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

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

    只需扫描您的图像,find第一个黑色的像素。 然后使用A *命令圆周点并将path存储在某个数组或列表pnt[]并将其作为圆形数组处理。

  3. find“突破点”

    它们可以被发现点的邻居之间的angular度峰值检测。 就像是

     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; 

    或者用折点上斜angular变化的符号表示:

     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. 适合椭圆

    所以如果没有find断点,你可以将整个pnt []作为单个椭圆。 例如查找边界框。 它的中心是椭圆的中心,它的大小给你半轴。

    如果发现断点,则首先find整个pnt[]的边界框,以获得半轴和中心位置区域search的限制。 然后将pnt[]分成两个断点之间的部分。 处理每个部分作为椭圆的独立部分和适合。

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

  5. 如何从点的select适合椭圆?

    1. 代数

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

    2. 几何

      例如,如果您检测斜率0,90,180或270度,则表示您处于与圆周的半轴交点。 所以,如果你有两个这样的点(每个半轴都有一个),那就是你所需要的拟合(如果它是轴alignment的椭圆)。

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

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

      非轴对齐的椭圆拟合

    3. 近似search

      您可以在#4中find的限制范围内循环遍历所有可能的椭圆参数组合,并select离您的点最近的一个。 这将是疯狂的慢粗,所以使用二进制search就像我的类似的方法大约类 。 另见

      • 用y点重复x位置的曲线拟合(Galaxy螺旋臂)

      关于它如何被用于类似的适合你的。

    4. 混合动力

      您可以结合几何和近似方法。 首先通过几何方法计算你可以做什么。 然后用近似search计算其余部分。 你也可以提高find的值的精度。

    在极less数情况下,当两个椭圆合并而没有中断点时,拟合的椭圆不会与你的点相匹配。 所以,如果发现这种情况下,你必须细分使用的分组,直到他们适合匹配…

这就是我想到的:

概观

你可能需要这样的东西:

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

您的边缘点只是至less有一个白色4邻居的黑色像素。

不幸的是,你说你的椭圆可能是“倾斜的”。 generics椭圆是用二次方程来描述的

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

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


另请参阅: 用于检测图像中的圆的algorithm


编辑

上述的algorithm思路过于乐观 ,至less如果直接应用的话。 好消息是,似乎两个聪明的家伙(谢永红和强记)已经为我们做了功课:

~cvrl/Publication/pdf/Xie2002.pdf

我不确定我会创build自己的algorithm。 为什么不利用其他团队所做的工作来弄清位图的所有曲线拟合?

INKSCAPE (应用程序链接)

Inkscape是一个开源工具,专门从事vectorgraphics编辑,也有一些能够使用光栅(位图)部件的能力。

以下是Inkscape API的起点链接:

http://wiki.inkscape.org/wiki/index.php/Scr​​ipt_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被公认为vectorgraphics的主要行业解决scheme,并具有一些用于将光栅化图像转换为vector图像的强大工具。

这里是他们的API的链接:

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

以下是Corel Draw批处理image processing(非脚本解决scheme)的链接:

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