用分布粒子拟合图像中自由区域的最大圆 [英] Fitting largest circle in free area in image with distributed particle

问题描述

我正在处理图像以检测和拟合包含分布粒子的图像的任何自由区域中可能的最大圆:

I am working on images to detect and fit the largest possible circle in any of the free areas of an image containing distributed particles:

(能够检测粒子的位置).

(able to detect the location of particle).

一个方向是定义一个接触任意3点组合的圆，检查圆是否为空，然后在所有空圆中找到最大的圆.然而，它导致了大量的组合，即C(n,3)，其中n是图像中粒子的总数.

One direction is to define a circle touching any 3-point combination, checking if the circle is empty, then finding the largest circle among all empty circles. However, it leads to a huge number of combination i.e. C(n,3), where n is the total number of particles in the image.

如果有人能给我提供任何我可以探索的提示或替代方法，我将不胜感激.

I would appreciate if anyone can provide me any hint or alternate method that I can explore.

推荐答案

让我的朋友来做一些数学题吧，因为数学总会走到最后！

Lets do some maths my friend, as maths will always get to the end!

维基百科:

在数学中，Voronoi 图是将平面划分为基于到平面特定子集中的点的距离的区域.

In mathematics, a Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane.

例如:

rng(1)
x=rand(1,100)*5;
y=rand(1,100)*5;


voronoi(x,y);

这张图的好处在于，如果您注意到，这些蓝色区域的所有边/顶点与它们周围的点的距离都相等.因此，如果我们知道顶点的位置，并计算到最近点的距离，那么我们就可以选择距离最大的顶点作为我们的圆心.

The nice thing about this diagram is that if you notice, all the edges/vertices of those blue areas are all to equal distance to the points around them. Thus, if we know the location of the vertices, and compute the distances to the closest points, then we can choose the vertex with highest distance as our center of the circle.

有趣的是，Voronoi 区域的边也被定义为由 Delaunay 三角剖分生成的三角形的外心.

Interestingly, the edges of a Voronoi regions are also defined as the circumcenters of the triangles generated by a Delaunay triangulation.

因此，如果我们计算该区域的 Delaunay 三角剖分及其外心

So if we compute the Delaunay triangulation of the area, and their circumcenters

dt=delaunayTriangulation([x;y].');
cc=circumcenter(dt); %voronoi edges

并计算外心与定义每个三角形的任何点之间的距离:

And compute the distances between the circumcenters and any of the points that define each triangle:

for ii=1:size(cc,1)
    if cc(ii,1)>0 && cc(ii,1)<5 && cc(ii,2)>0 && cc(ii,2)<5
    point=dt.Points(dt.ConnectivityList(ii,1),:); %the first one, or any other (they are the same distance)
    distance(ii)=sqrt((cc(ii,1)-point(1)).^2+(cc(ii,2)-point(2)).^2);
    end
end

然后我们有所有可能没有点的圆的中心(cc)和半径(distance).我们只需要最大的！

Then we have the center (cc) and radius (distance) of all possible circles that have no point inside them. We just need the biggest one!

[r,ind]=max(distance); %Tada!

现在开始绘制

hold on

ang=0:0.01:2*pi; 
xp=r*cos(ang);
yp=r*sin(ang);

point=cc(ind,:);

voronoi(x,y)
triplot(dt,'color','r','linestyle',':')
plot(point(1)+xp,point(2)+yp,'k');
plot(point(1),point(2),'g.','markersize',20);

注意圆心如何在 Voronoi 图的一个顶点上.

Notice how the center of the circle is on one vertex of the Voronoi diagram.

注意:这将在 [0-5],[0-5] 内找到中心.您可以轻松修改它以更改此约束.您还可以尝试在感兴趣的区域(而不是仅中心)内找到适合其整体的圆.这将需要在获得最大值的最后进行少量添加.

NOTE: this will find the center inside [0-5],[0-5]. you can easily modify it to change this constrain. You can also try to find the circle that fits on its entirety inside the interested area (as opposed to just the center). This would require a small addition in the end where the maximum is obtained.

这篇关于用分布粒子拟合图像中自由区域的最大圆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！