Program for searching ellipses and determining their parameters using least squares methods
Hello! I'm new to Harbra. I was hooked by an article from 2011: “Detection of elliptical particles in micrographs. A new algorithm for searching for ellipses in an image.”
Here is a comment to this article (Mrrl Dec 27, 2011 at 07:49): “Why is the ellipse built using 6 points? The equation is homogeneous. For a second-order curve, 5 points were always enough; the coefficients are sought by solving a homogeneous equation. As a sixth point, it makes sense to add a point that obviously does not belong to the ellipse and write F(x,y) = 1 for it – then you will have to solve a more familiar inhomogeneous equation. And if you really need an exact result, then you need to take all the points lying along the line of the approximately found ellipse (it would be better with weights) and feed them to the input of the least squares method. It will allow us to determine parameters with an accuracy of tenths of a pixel (or even more accurately).”
I have developed a program on Matlab that implements the scheme proposed by Mrrl.
A brief description of the program and the results of its application to a specific example from the article cited above.
Loading an RGB image from the article:
Convert to gray image:
We filter with a DOG filter and convert gray to binary, without bothering with the threshold. It's just that the threshold is greater than zero.
There is a lot of garbage in the picture, but there are no breaks in the ellipse and the entire ellipse is presented here as a whole. Using morphological operations, we remove pixels on the contours of objects, preventing objects from breaking. The remaining pixels make up the skeleton of the images.
Using the regionprops function, we find connected regions, the coordinates of the regions, remove small details in the image and find the graph.
Using the cyclebasis function we find closed figures and their coordinates. We discard the small ones. We received several candidates for the title “Ellipse”. Let's involve international corporations in the matter.
We use all the points of each object to find the coordinates of the ellipse that best approximates the data.
xi, yi – columns of coordinates of the i-th object.
General curve equation of 2nd order
A*xi2 + 2*B*xi*yi+C*yi2 + 2*D*xi+ 2*E*yi+ 1 = 0
To find the coefficients of the equation, we solve the overdetermined system of linear equations using the least squares method
ab=[xi.^2 xi.*yi yi.^2 xi yi]; b=ones(size(xi',2),1); sb=ab\b;
A=sb(1); B=sb(2)/2; C=sb(3); D=sb(4)/2; E=sb(5)/2; F=-1;
Using the function h=fimplicit(@(xh,yh) sb(1)*xh.^2+sb(3)*yh.^2+…); find the coordinates of the approximating ellipse
xhh=h.XData'; yhh=h.YData';
To reject candidates, we calculate the variance of the data approximation [xi yi] calculated values [xhh yhh].
dst=dist([xhh yhh],[xi yi]');
mdst=min(dst')';
disper=sum(mdst.^2)/(max(size(mdst))-1)
As an ellipse, we leave the figure with minimal variance.
We calculate the parameters of the ellipse using the invariant method:
http://www.mathprofi.ru/kak_privesti_uravnenie_linii_2_poryadka_k_kanonicheskomu_vidu.html
ab1 and ab2 are the semi-axes of the ellipse, x0 and y0 are the coordinates of the center, alfa is the inclination angle of the axis.
ab1 ab2 x0 y0 alpha 66.051 74.004 129.63 83.043 -63.906 |
Calculate the perimeter of the ellipse
perimetr=sum( sqrt(diff(xhh).^2+diff(yhh).^2))= 440.3419
Area of the ellipse S = π * ab1 *ab2= 15356
Checking the accuracy of parameter calculations
To check the accuracy of calculating the perimeter, we parametrically define a circle
(a special case of an ellipse with equal axes)
t=(0:.001:1)*2*pi; x=80*cos