最后一次，我写了一篇关于寻找二值图像中物体的最大费莱特直径的文章，最后得到了这个图:

我已经计算了所有像素角的凸壳，然后我计算了每一对凸壳顶点之间的成对距离，以找到最大距离。

这个过程在很多情况下都很有效，但是用这种方法找到最大距离所需的时间随着凸包顶点数量的平方而增长。使用现代数字图像分辨率，不难想象有数千个顶点和数百万个成金宝搏官方网站对距离需要计算。

有一个方法可以减少我们可以考虑的顶点对的数量。它基于以下定理:

凸形的直径是支撑平行线之间的最大距离。金宝app定理4,18,Preparata and Shamos，计算几何, 1985)

一个支撑线金宝app对于多边形是一条包含多边形顶点的线，多边形完全位于线的一侧。

让我给你们看一张用上次课上的凸壳点做的图。

船体= [2.5000 5.5000 3.5000 4.5000 6.5000 2.5000 9.5000 1.5000 10.5000 1.5000 10.5000 3.5000 9.5000 5.5000 5.5000 5.5000 7.5000 2.5000 7.5000 2.5000 5.5000];情节(船体(:1)船体(:,2),“r”，“线宽”, 2)在情节(船体(:1)船体(:,2),的r *)举行从轴平等的轴ij轴([0 15 0 10])为theta = -55:5:-35 drawFullLine(gca，[9.5 5.5]，theta，“颜色”,(。6．6．6]);结束

上图显示了通过(9.5,5.5)顶点绘制的五条不同的支撑线。金宝app现在我将通过(2.5,7.5)顶点添加一些支持线。金宝app

为drawFullLine(gca，[2.5 7.5]，theta，“颜色”,(。6．6．6]);结束

可以看到，(2.5,7.5)顶点的支撑线与(9.5,5.5)顶点的支撑线是金宝app不平行的。这就排除了这对顶点来计算Feret的最大直径。

现在我要为另一对顶点画支持线。金宝app

情节(船体(:1)船体(:,2),“r”，“线宽”, 2)在情节(船体(:1)船体(:,2),的r *)举行从轴平等的轴ijdrawFullLine(gca，[6.5 2.5]，-30，“颜色”,(。6．6．6]); drawFullLine(gca,[9.5 5.5],-30,“颜色”,(。6．6．6]);

因为顶点(6.5,2.5)和(9.5,5.5)有平行线支撑，所以它们被称为金宝app映顶点。在Preparata and Shamos书中有一个算法(上面提到的)，它可以找到凸多边形的所有对映顶点。在这篇文章的底部有一个函数实现了这个算法。我要用它来求凸包顶点的对映对。

pq = antipodalPairs(船体);

重要提示:中的算法antipodalPairs假设它的输入是凸的。此外，它假设输入不包含位于两个相邻顶点之间直线上的任何顶点。为了满足这个条件，使用调用来计算凸包:k = convhull(P，'Simplify'，true)。

现在我们来画出连接对映对的线段。

情节(船体(:1)船体(:,2),“r”，“线宽”, 2)在情节(船体(:1)船体(:,2),的r *)轴平等的轴ij轴([0 15 0 10])为k = 1:尺寸(pq, 1) x =[赫尔(pq (k, 1), 1)船体(pq (k, 2), 1)];Y = [hull(pq(k,1)，2) hull(pq(k,2)，2)];情节(x, y,“颜色”,(。6．6．6]);结束持有从

为了找到最大的Feret直径，我们只需要检查这10个线段的距离，而不是像之前那样10*9 = 90个线段。

P1 = hull(pq(:，1)，:);P2 = hull(pq(:，2)，:);V = p1 - p2;D = hypot(v(:，1)，v(:，2));[d_max,idx] = max(d);P1_max = p1(idx，:);P2_max = p2(idx，:);持有在Plot ([p1_max(1) p2_max(1)]，[p1_max(2) p2_max(2)]，“b”，“线宽”, 2)从

d_max

D_max = 10

这是最大费里特距离。

我确信，在许多情况下，通过蛮力比较凸包顶点的所有对来找到最大距离会更快。毕竟，计算对映对确实需要一些时间。我还没有做过性能研究来进一步调查这个问题。然而，对映对对的计算对于另一个测量是有用的:最小费里特距离。

我下次再讲。

岗位结束

上述代码使用的算法、可视化和实用程序函数

函数h = drawFullLine(ax,point,angle_degrees,varargin)绘制一条跨越整个绘图的线％% drawFullLine(ax,point,angle_degrees)在%经过指定点的指定轴%指定角度(以度为单位)。画这条线是为了张成%整个地块。％% drawFullLine(___，Name,Value)传递名称-值参数对%到行函数。史蒂夫·艾丁斯极限=轴(ax);Width = abs(limits(2) - limits(1));高度= abs(极限(4)-极限(3));D = 2*hypot(宽度，高度);X1 = point(1) - d*cosd(angle_degrees);X2 = point(1) + d*cosd(angle_degrees);Y1 = point(2) - d*sind(angle_degrees);Y2 = point(2) + d*sind(angle_degrees);H = line(ax，“XData”(x1, x2)),“YData”(y1 y2),变长度输入宗量{:});结束函数pq = antipodalPairs(S)简单凸多边形的对跖顶点对。％% pq = antipodalPairs(S)计算一个简单的，%凸多边形。S是(x,y)顶点坐标的Px2矩阵%的多边形。S必须是简单且凸的，没有重复的顶点。它是%未检查是否满足这些条件。S可以是封闭的，或者%。输出，pq，是一个Mx2矩阵，表示中的顶点对第k个对映对的坐标是S(pq(k,1)，:)和% S (pq (k, 2):)。％%的术语％对于一个凸多边形，对映顶点对是指你%可以通过每个顶点绘制不同的支撑线，这样金宝app%的支撑线是平行的。金宝app％一条支撑线是一条穿过多边金宝app形顶点的线多边形的内部完全位于直线的一侧。％%的例子％计算多边形的对映顶点并绘制相应的图%线段。％% x = [0 0 1 3 5 4 0];% y = [0 1 4 5 4 10];% S = [x' y'];% pq = antipodalPairs(S);％%的阴谋(S (: 1), (2):,)%坚持住% for k = 1:size(pq,1)% xk = [S(pq(k,1)，1) S(pq(k,2)，1)];% yk = [S(pq(k,1)，2) S(pq(k,2)，2)];%的阴谋(xk,即“线型”,“——”,“标记”,“o”,“颜色”,[0.7 0.7 0.7])%结束%推迟%轴相等％%算法说明％此函数使用“对跖对”算法，prepareata和Shamos，计算几何:导论，Springer-Verlag, 1985，% p. 174。史蒂夫·艾丁斯n = size(S,1);如果isequal (S (1:), S (n,:))%输入多边形关闭。中移除重复的顶点%。S(n，:) = [];N = N - 1;结束该算法假定输入顶点是逆时针顺序的。如果顶点按顺时针顺序排列，则反转顶点。顺时针= simplePolygonOrientation(S) < 0;如果顺时针S =流体(S);结束%设置以下变量，包括两个匿名函数% up跟随Preparata和第174页伪代码中的符号%沙漠。p和q是标识s的顶点的指标(基于1)，p0和% q0标识算法的起始顶点。面积(i,j,k)是面积S(i，:)， S(j，:)，%和S(k，:)。next(p)返回S的下一个顶点的索引。％在准备和Shamos文本中缺少p0的初始化。面积= @ (i, j, k) signedTriangleArea((我,:),年代(j:), S (k,:));Next = @(i) mod(i,n) + 1;% mod((i-1) + 1,n) + 1P = n;P0 = next(p);Q = next(p);对映顶点列表将建立在向量pp和qq中。Pp = 0 (0,1);Qq = 0 (0,1);对跖对，步骤3。而(面积(p (p),下一个(q)) >区域(p (p), q)) q =下一个(q);结束Q0 = q;%步骤4。而(q ~= p0)%步骤5。P = next(P);%步骤6。%步骤7。(p,q)是对映对。Pp = [Pp;p];Qq = [Qq;问);%步骤8。而(面积(p (p),下一个(q)) >区域(p (p), q)) q =下一个(q);%步骤9。如果~ isequal ([p q], [q0, p0])%步骤10。Pp = [Pp;p];Qq = [Qq;问);其他的这个循环中断在准备和Shamos中被省略%的文本。打破结束结束步骤11。检查平行边。如果(area(p,next(p)，next(q)) == area(p,next(p)，q))如果~isequal([p q]，[q0 n])%步骤12。(p，下(q))是对映对。Pp = [Pp;p];Qq = [Qq;下一个(q)];其他的这个循环中断在准备和Shamos中被省略%的文本。打破结束结束结束如果顺时针方向补偿多边形顶点的翻转。Pp = n + 1 - Pp;Qq = n + 1 - Qq;结束Pq = [pp qq];结束函数s = vertexOrientation(P0,P1,P2)顶点相对于线段的方向。％% s = vertexOrientation(P0,P1,P2)返回一个正数，如果P2是%从P0到P1这条线的左边。如果P2在%。如果P2在直线的右边，它返回一个负数。％换句话说，正输出对应于a%从P0到P1再到P2逆时针移动。％% P0, P1和P2是包含(x,y)坐标的二元向量。％%参考:http://geomalgorithms.com/a01-_area.html，函数isLeft()史蒂夫·艾丁斯s = (P1(1) - P0(1)) * (P2(2) - P0(2)) -…(p2 (1) - p0 (1)) * (p1 (2) - p0 (2));结束函数s = simplePolygonOrientation(V)确定简单多边形的顶点顺序。％% s = simplePolygonOrientation(V)返回一个正数多边形V是逆时针的。它返回一个负数%多边形是顺时针的。对于简并情况，它返回0。V是Px2(x,y)顶点坐标的%矩阵。％%参考:http://geomalgorithms.com/a01-_area.html，功能% orientation2D_Polygon ()史蒂夫·艾丁斯n = size(V,1);如果N < 3 s = 0;返回结束找到多边形的最右最低顶点。x = V(:，1);y = V(:，2);Ymin = min(y，[]，1);Y_idx = find(y == ymin);如果Isscalar (y_idx) idx = y_idx;其他的[~，x_idx] = max(x(x_idx)，[]，1);= y_idx(x_idx(1));结束如果离开V(idx，:)的边在左边，则多边形为逆时针%进入边缘。如果idx = = 1 s = vertexOrientation (V (n:), (1):), V (2:));elseifidx = = n s = vertexOrientation (V (n - 1:) (n:), V (1:));其他的s = vertexOrientation (V (idx-1:), V (idx:), V (idx + 1,:));结束结束

版权所有2017 MathWorks, Inc。
获取MATLAB代码

使用MATLAB®R2017b发布