计算二进制图像中的对象长度 - 算法

Question

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

图像澄清:

alt text http://cl.ly/489019a048c1bf20c6bb/content

示例输入图像:

alt text http://cl.ly/f5c379e59deef435f365/content

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

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

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

添加：回复评论

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