算法：椭圆匹配 [英] Algorithms: Ellipse matching

问题描述

我有很多像以下图片（只有白色和黑色）：

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

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

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

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

非常感谢

解决方案

1. 对圆周点进行采样

   
   
   

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

   
   
   

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




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

   
   
   

   只需扫描图像即可找到第一个黑色像素。然后使用




3. 近似搜索

   
   
   

   您可以在＃4 中的限制范围内循环全部可能的椭圆参数组合，并选择最接近的那个对你的观点。这将非常慢，所以使用二进制搜索就像我的

   
   

   I have many images like the following (only white and black):

   My final problem is to find well matching ellipses. Unfortunately the real used images are not always that nice like this. They could be deformed a bit, which makes ellipse matching probably harder.

   My idea is to find "break points". I markes them in the following picture:

   Maybe these points could help to make a matching for the ellipses. The end result should be something like this:

   Has someone an idea what algorithm may be used to find these break points? Or even better to make good ellipse matching?

   Thank you very much

   解决方案

   1. 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.

   2. 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.

   3. 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;
      

   4. 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.

   5. 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 ...

   This is what I have in mind with this:

   这篇关于算法：椭圆匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！