Algorithms: ellipse matching

Question

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

My last problem is finding suitable ellipses. Unfortunately, the images used are not always so good. They can be deformed a little, which makes matching an ellipse more difficult.

My idea is to find breakpoints. I mark them in the following figure:

Perhaps these points can help make comparisons for ellipses. The end result should be something like this:

Does anyone know which algorithm can be used to find these break points? Or is it even better to make a good ellipse?

Thank you very much

Answer 1

• Circle points example

  Just scan your image and select “All Black Pixels” with any white neighbor. You can do this by repainting the remaining black pixels in any unused color (blue).

  After completing the whole image, you can recolor the inner back from an unused color (blue) to white.

• create a list of ordered circle points per cluster / ellipse

  Just scan your image and find the first black pixel. Then use A * to order the points of the circle and save the path in some array or pnt[] list and treat it like a round array.

• Find Breakpoints

  They can be detected by a peak in the angle between the neighbors of the found points. sort of

   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 at the breakpoint the sign of the deviation of the angle of inclination:

   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; 

• matching ellipses

  therefore, if no breakpoints are found, you can put the whole pnt [] as a single ellipse. For example, find the bounding box. This is the center of the center of the ellipse, and its size gives you half shafts.

  If breakpoints are found, first find the bounding box of integers pnt[] to get limits for the half axis and search around the center area. Then split pnt[] into pieces between the break points. Treat each part as a separate part of the ellipse and fit.

  After all parts of pnt[] installed, check if some ellipses are not the same, if they overlap with another ellipse, they will be separated ... Thus, the merging is identical (or the average value to increase accuracy). Then pnt[i] all pnt[i] points to white, clear the pnt[] list and loop # 2 until more black pixels are found.

• How to shift the ellipse from the choice of points?

  • algebraically

    use the ellipse equation with "uniformly" distributed known points to form a system of equations for calculating the ellipse parameters ( x0,y0,rx,ry,angle ).

  • geometrically

    for example, if you find a slope of 0.90.180 or 270 degrees, then you are at the intersection of the semiaxis with a circle. So if you have two such points (one for each axis), then this is all you need to fit (if it is an ellipse oriented along the axis).

    for ellipses not oriented along the axis, you need to have a fairly large part of the circle. You can use the fact that the center of the bounding box is also the center of the ellipse. So, if you got the whole ellipse, you also know the center. Half-axis intersections with a circle can be detected with the largest and smallest tangential change. If you have a center and two points, that's all you need. If you have only a partial center (only x or y coordinate), you can combine with a large number of center points (find 3 or 4) ... or approach the missing information.

    Also, half the axis of the H, V lines intersects the center of the ellipse, so it can be used to detect, if not the entire ellipse in the pnt[] list.

    

  • close search

    You can do the “all” possible combination of ellipse parameters within the limits found in # 4 and choose the one that is closest to your points. That would be insanely slow rude, so use a binary search, for example, an approach similar to my approximation class . Also see

    • Fixing a curve with y points at repeating x positions (galactic spiral arms)

    about how it is used to match yours similarly.

  • hybrid

    You can combine a geometric and approximate approach. First, figure out what you can do using a geometric approach. And then calculate the rest using the approximate search. You can also increase the accuracy of the values ​​found.

  In rare cases, when two ellipses merge without a breakpoint, the set ellipse will not match your points. Therefore, if such a case is detected, you need to divide the used points into groups until their matches match ...

Here is what I mean:

Answer 2

You will probably need something like this:

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

Your boundary points are just black pixels with at least one white 4-neighbor.

Unfortunately, you are saying that your ellipses may be “tilted”. Common ellipses are described by quadratic equations of type

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

with B² <4A (⇒ A> 0). This means that, compared to the circle problem, you do not have 3 dimensions, but 5. This leads to the fact that the Hough transform will be much more complicated. Fortunately, your example tells you that you don't need high resolution.

---

See also: circle detection algorithm in the image

---

EDIT

The above idea of ​​the algorithm was too optimistic , at least if it is applied in a straightforward manner. The good news is that two smart guys (Yonghong Xie and Qiang Ji) have already done their homework for us:

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

Answer 3

I'm not sure that I will create my own algorithm. Why not influence the work that other teams have done to find out if all the bitmap critical adjustments are all?

INKSCAPE (application link)

Inkscape is an open source tool that specializes in editing vector graphics with some ability to work with raster (raster) parts.

Here is a reference to the starting point for the Inkscape API:

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

It looks like you can script in Inkscape or access Inkscape through external scripts.

You can also do something with a null script from the inkscape command line interface:

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

COREL DRAW (application link)

Corel Draw is recognized as the industry leading vector graphics solution and has great tools for converting rasterized images to vector images.

Here is a link to their API:

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

Here's a link to Corel Draw batch image processing (non-w371>):

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