如何找到两条直线交点旁边的4个点？

Question

假设我有一些位图数据（黑色）上面手绘了一些矢量格式的线条（绿色）。这些线条大致跟随位图数据的形状。在某些地方，线条会相交。

因此，我想做的是，知道绿线交叉的位置，如何找到A、B、C和D的位置？

请参见下面的示例：

考虑到线的随机位置有时甚至不在黑色形状内，我不确定如何解决这个问题。然而，我想肯定有方法。有什么建议吗？

- laurent

---

你能更精确一些吗：绿线交点应该在A、B、C、D内部还是无论绿线交点在哪里，A、B、C、D都如图所示？ - user180100

使用位图可能会变得困难/缓慢。你不能将输入作为矢量图形获取吗？ - Markus Jarderot

我无法看出绿色线条如何有所帮助；在图片2中，它们在B和C右侧相交。 - Kirk Broadhurst

@RC，用户快速跟踪这些绿线作为粗略指南。然后我需要找到靠近交点的4个点。因此，交点不一定在ABCD形状内 - 它可能在外面，就像第二个示例一样。 - laurent

@MizardX，输入确实是位图，但我想我可以将其转换为矢量格式。 - laurent

Answer 1

我能想到的最简单方法是：

1. 过滤图像以去除绿线。一个简单的方法是使用一些细化技术，将其填充为相邻像素的背景颜色。

2. 现在你应该有一个只包含黑色（粗）线和白色背景的图像。

3. 再次使用角点检测算法对图像进行过滤，例如哈里斯探测器。这将给出四个角点。

注意事项:

1. 根据输入数据的不同，可能会提取出多于四个的角点。无论如何，最好验证提取出的四个角点是否确实是交叉口的可能角点。

2. 同样，这是一种相当粗略的方法，但如果输入数据像您的示例图片一样清晰，绿线和黑线之间的距离不太大，我认为它可能有效。

- Hannes Ovrén

Answer 2

我假设您知道如何获取（绿色）向量线交叉点的坐标（x，y），因此我将省略该部分。

从最靠近（x，y）的像素开始，逐渐向外按方形螺旋（或其他您喜欢的搜索模式）从像素到像素移动。在每一步中，检查您是否位于具有一个且仅有一个白色Moore邻居的黑色像素上。如果是，则黑色像素及其白色邻居接触的地方（可能是公共角落）是您的一个点（称之为A）。继续前进，直到找到三个更多的点（B，C，D）。这些将是离绿色交叉点最近的四个这样的点 - 这在您在问题中显示的四个示例中可以很好地工作。

但是，如果绿色交叉点在两个黑色交叉点之间，这个算法就会失败；在这种情况下，它将混合来自两个黑色交叉点的点。如果您关心这一点，在找到点A后，立即重新启动以A为中心的螺旋行军，一直行军到找到B、C、D为止。这实际上是“捕捉”到最接近的黑色交叉点。

您可以添加更多的智能来避免重复搜索同一区域；在找到B后重新启动或重新聚焦您的搜索模式，然后在找到C后再次进行，依此类推... 这取决于您想要/需要变得多么花哨。

- Jean-François Corbett

Answer 3

你应该能够通过侵蚀（缩小到点）的过程找到绿线交叉点以及黑线交叉点的中点。然后使用最近点对算法来找出哪些黑线交叉点是最靠近绿线交叉点的。

接下来，你可以从黑线交叉点开始进行搜索。你需要一个优先队列，按照离黑线交叉点的距离进行处理，最近的点先处理。将四个相邻点放入队列中。对于队列中的每个点，你需要检查它是否是白色像素（我们想要这些），检查它之前是否被访问过（如果是则跳过），然后将其四个相邻像素添加到队列中。前四个白色像素应该是你想要的（假设你有一个好的骨架化/缩小方法来找到交叉点），但你应该一直取白色像素，直到找到第一个不相邻的四个像素。

- Justin Peel

Answer 4

首先，让我说一下，我对这个主题一无所知，也没有任何经验。所以这只是我的猜测。但我会从忽略绿线开始——顺便说一句，它们也不像是“线条”。

顺便问一下，这与道路有关吗？

那么，去掉绿线。在此之后，取一个小正方形，就像你得到的上面的4个中的任意一个，直到你遍历完所有的正方形，并寻找具有最大黑/白像素比的正方形。那些应该是“十字路口”。通过映射那些与白色像素相邻的黑色像素，你应该能够得到道路/田地的边界。在那之后，确定这些点应该很容易。

就像我说的，这只是一个猜测。有趣的问题——想知道有知识的人会想出什么。

- Rook

Answer 5

首先，您需要从原始图像中提取边缘，以获取描述黑白边界的多边形。

然后，您需要迭代这些边缘的点，并计算与两条绿线交点的点间距离。最小的四个距离来自您要查找的点。

这回答了您的问题吗？还是我误解了什么？

如果您只想要4个角落，那么您不需要绿线：只需使用Savitzky-Golay滤波器平滑边缘提取的边界，并计算点间曲率。然后提取具有最大曲率的点即可。

- rocksportrocker

Answer 6

你需要对二值图像进行向量化处理。我们的大学项目正好与此主题相关 - 角点工具箱允许以压缩形式处理二值图像（不要被标题“压缩”所迷惑 - 这里的“压缩”指的是将二值图像首先转换为所谓角点的链接列表）。

1）将图像转换为角点（请参阅上述链接的第4章）。然后，您可以使用角点之间的直线插值（第5.5章） - 您可以修改我们的算法来查看较大的线段中的大斜率变化（约90度）。

2）您不需要绿线。您可以使用骨架化算法找到黑色部分的骨架（请参阅上述链接的第5.4章），并将该骨架与直线进行插值（请参阅第5.5章）。

如果您对这个项目感兴趣，我可以问问同事们是否能提供源代码。

- Tomas

Answer 7

最简单的方法是骨架化。首先将绿色和黑白图像分开。在两个图像上运行骨架算法（这也是OpenCV中的一种相当简单的形态学操作），并确定交点（可以通过在骨架图像中进行简单的8邻域像素计数来完成：即对于每个黑色像素，计算水平、垂直或对角线连接的像素数，如果该值>=4，则为交点）。现在对这些骨架化点进行最近邻匹配，就完成了。

- thiton