在Emgu CV（或OpenCV）中从一组多边形生成Voronoi图

Question

使用Emgu CV从一幅道路网络图像的轮廓中提取出一组封闭多边形。这些多边形代表了道路的轮廓线。下图显示了结果，在OpenStreetMaps地图上绘制（Emgu CV中的'pixel'形式的多边形已被转换为纬度/经度形式以便绘制）。

表示道路轮廓线的多边形集：

我现在想计算这个多边形集的Voronoi图，以帮助我找到道路的中心线。但是在Emgu CV中，我只能找到获取一组点的Voronoi图的方法。这可以通过找到一组点的Delaunay三角剖分（使用Subdiv2D类）然后使用GetVoronoiFacets计算voronoi面得到。

我尝试计算由集合中所有多边形定义的点的Voronoi图（每个多边形都是一个点列表），但是这给我带来了非常复杂的Voronoi图，正如我们所预期的那样。

一组点的Voronoi图：

这张图片显示了第一张图片的一个较小部分（为了清晰起见，因为它非常复杂）。确实，图中的一些线条似乎代表道路的中心线，但还有很多其他线条，很难找到提取“好”线条的标准。

我面临的另一个潜在问题是，正如您可以从第一幅图中看出的那样，有些多边形位于其他多边形的内部，因此我们不处于标准的一组不相交的封闭多边形的情况下。也就是说，有时道路位于一个多边形的外边界和另一个多边形的内边界之间。

我正在寻求关于如何使用Emgu CV（或Open CV）计算多边形集合的Voronoi图的建议，希望能够解决我所提出的第二个问题。如果没有使用Emgu CV的其他方法来实现这一点，我也很乐意接受建议。

- mchristos

---

所以，您需要计算从1）图像开始的街道的“中心”，使用_pixel形式_（简单）或2）使用点坐标lat，lng？对于1），您可以绘制填充的多边形，并使用距离变换。街道的中心将具有最大的距离值。非极大抑制将给出结果。 - Miki

我需要从一张图片中获取信息。使用距离变换是个好主意，谢谢。事实上，我可以将距离变换应用到我的原始二进制图像上，这也是我最初通过找到轮廓来计算多边形的地方！这很棒，因为我不需要处理包含其他多边形的多边形的问题。你能帮我解决非极大值抑制吗？在Emgu CV中我该如何实现它？我通过搜索找到的最接近的方法是Harris边缘检测。 - mchristos

话虽如此，我需要的最终结果是一个代表道路中心线的经纬度图形... 从原则上讲，我可以从中心线像素中找到它，但也许这不是最好的方法。也许沃罗诺伊图仍然是更好的方法。 - mchristos

@Miki，请问你能帮我解决如何实现非极大值抑制吗？ - mchristos

嗨，克里斯，很抱歉这不是一个真正的答案，但你是如何使用Emgu CV在地图上获取道路的呢？这正是我一直在尝试做的事情。你的方法是我找到的最接近的东西。谢谢。 - Isabel Inc

我刚刚使用了一组点的 Voronoi 图，并取出那些落在感兴趣区域内的边缘（在大外多边形内部，但在内部多边形外部）。这将给您一个具有“毛发”外观的图形（就像带有毛发的毛毛虫，其身体是道路中心线）。可以通过删除图中仅有一个邻居的节点来去除“毛发”（我编写了自己的图形数据结构来表示道路）。您可能需要多次执行此操作。 - mchristos

Answer 1

如果您已经有多边形，可以尝试计算Straight Skeleton。

我没有尝试过，但CGAL有一个实现。请注意，此特定函数的许可证是GPL。

可能存在一个问题：

此CGAL包的当前版本只能在具有孔的简单多边形内部构造直骨架，即它不能处理平面上的一般多边形图形。

可能有解决方法。例如，您可以将所有多边形包含在一个更大的矩形中（这样原始多边形将成为新矩形的洞）。如果原始多边形有洞，则可能无法很好地工作。为了解决这个问题，您可以对每个带孔的多边形执行算法，然后将所有多边形放入矩形中，删除所有孔并再次执行算法。

- user2518618