algorithm - 在二值图像中找到曲线的末端

Question

我正在寻找一种算法来检测曲线的末端。我要将二值图像转换为点云作为坐标，我需要找到线的末端以便开始另一个算法。

我正在考虑对每个点最近的 N 个“1”像素的向量取平均值，并说具有最长向量的像素必须是一个端点，因为如果一个点位于一条线的中间，那么矢量的平均值将抵消。但是，我认为这一定是图像处理中众所周知的问题，所以我想我会把它扔在这里看看是否有人知道“正确”的算法。

Answer 1

如果线条只有一个或两个像素粗，您可以使用 Malcolm McLean 在评论中建议的方法。

否则，一种方法是为每个红色像素计算距离最远的同一组件中的红色像素，以及该最远像素的距离。 (在图论术语中，这两个像素之间的距离是每个像素的偏心度。)靠近长线末端的像素将具有最大的偏心度，因为它们之间的最短路径指向线的另一端很长。 (请注意，无论最大偏心率是多少，至少会有两个像素具有它，因为从 a 到 b 的距离与从 b 到 a 的距离相同。)

如果您有 n 个红色像素，则可以在 O(n^2) 时间内计算出所有偏心率(以及对应的最远像素):对于每个像素，依次在该像素处启动 BFS，并取您找到的最深节点作为它最远的像素(可能有几个；任何一个都可以)。每个 BFS 的运行时间为 O(n)，因为任何像素上只有固定数量的边(4 或 8，取决于您对像素连接建模的方式)。

为了稳健性，您可以考虑采用前 10 或 50 个(等)像素对并检查它们是否形成 2 个分离良好、定义明确的聚类。然后，您可以将每个集群中的平均位置作为您的 2 个端点。