algorithm - 计算二值图像中对象的长度 - 算法

Question

我需要计算二值图像中对象的长度(对象内部像素之间的最大距离)。由于它是二值图像，因此我们可以将其视为具有值 0(白色)和 1(黑色)的二维数组。我需要的是一个聪明的(最好是简单的)算法来执行这个操作。请记住，图像中有许多对象。

要澄清的图像:

示例输入图像:

Answer 1

我认为如果一个对象的边界是凸的并且没有三个顶点在一条线上(即没有顶点可以在不改变多边形的情况下被移除)，我认为问题很简单:那么你可以随机选择两个点并使用简单的梯度下降式搜索以找到最长的线:

Start with random vertices A, B
See if the line A' - B is longer than A - B where A' is the point left of A; if so, replace A with A'
See if the line A' - B is longer than A - B where A' is the point right of A; if so, replace A with A'
Do the same for B
repeat until convergence

所以我建议为每个种子 blob 找到凸包，删除所有“多余”顶点(以确保收敛)并运行上面的算法。

构造一个凸包是一个复杂度为 O(n log n) 的操作 IIRC，其中 n 是边界像素的数量。对于像这样的小物体应该非常有效。 编辑:我只记得需要凸包算法的 O(n log n) 来排序点。如果边界点是连通分量分析的结果，则它们已经排序。所以整个算法应该在 O(n) 时间内运行，其中 n 是边界点的数量。 (不过，这是很多工作，因为您可能必须编写自己的凸包算法或修改一个算法以跳过排序。)

添加:回复评论

如果您不需要 100% 的准确度，您可以简单地为每个 Blob 拟合一个椭圆并计算长轴的长度:这可以从 central moments 计算得出。 (IIRC 它只是协方差矩阵的最大特征值的平方根)，所以它是一个 O(n) 操作，可以在对图像的单次扫描中有效地计算出来。它还有一个额外的优势，即它考虑了 Blob 的所有像素，而不仅仅是两个极值点，即它受噪声的影响要小得多。