从图像中提取轮廓路径

Question

假设我有一个16x16黑白位图图像

​

​

在这里，白色像素表示空空间，黑色像素表示填充空间。

我想要提取所有围绕黑色像素的轮廓线，包括洞和嵌套轮廓线。(见第二张图片)

让我们为像素定义一个坐标空间

• 左上角像素->指数(0,0)
• 右上角像素->指数(15,0)
• 左下角像素->指数(0,15)
• 右下角像素->指数(15,15)

等高线也有它们的坐标空间。

• 左上角像素->索引左上角(0,0)
• 右上角像素->索引的右上角(16,0)
• 左下角像素->指数(0,16)
• 右下角像素->指数(16,16)

最后，将等高线定义为该坐标空间中的一系列点。

​

​

在第二个图像上，我标记了3个等高线，以演示所需的输出应该是什么样子。

Path1 (RED): 1(1,0) 2(2,0) 3(2, 3) 4(3,3) 5(0,3) ... 23(4,4) 24(1, 4)
    Hole1 of Path1 (BLUE): 1(7,5) 2(7,6) 3(6,6) ... 13(11,6) 14(11,5)

Path2 (RED again): 1(8,6) 2(10,6) 3(10,8) 4(8,8)
...

请注意，点在等高线上的顺序是重要的。孔的绕组差异并不重要，但我们应该在某种程度上表示该轮廓的“孔”性质。

我使用ClipperLib解决了这个问题，但在我看来，如果我们忽略ClipperLib内部发生的事情，这更像是一种蛮力的方法。

以下是对算法的简要描述。

First, define a 16x16 subject polygon from which we will be subtracting all white pixels 
Scan the image matrix row by row
    On each row extract all contiguous white rectangle shapes as a clipping polygon
Do the polygon clipping by subtracting all collected white rectangular polygons from initial 16x16 subject polygon
Extract path data (including holes) from ClipperLib's PolyTree solution

我想知道是否有更好的方法来解决这个问题？

Answer 1

在这里，使用ClipperLib似乎有些过分，因为它通过复杂的交集检测和拓扑重构算法来处理一般多边形，而您的问题则更“可预测”。

您可以分两个步骤进行：

• 使用标准的轮廓算法，如cv.findContours所使用的。(它是“Suzuki和其他人的一种实现。数字化二值图像的拓扑结构分析，由边界跟踪。计算机视觉、图形和图像处理，30(1)：32-46,1985”)。
• 从连接像素中心到像素中心的等高线，导出沿像素边缘的轮廓。这可能可以通过研究沿轮廓的三个像素序列的不同配置来实现。

Answer 2

为此，您可以使用边界追踪算法。我个人使用摩尔邻域追踪，因为它是直观和直观的实现。首先找到边界轮廓，然后提出一个洞搜索算法(您可能需要结合部分扫描线填充算法)。一旦你找到一个洞，你可以应用同样的边界跟踪算法，但方向相反。

您肯定可以使用像OpenCV这样的库来查找等高线，但据我的经验，它可能会产生与其他库不兼容的退化输出，例如用于将多边形分解为三角形的poly2tri。

如果我们取你的输入样本图像，那么红色路径可以被认为是自相交的(顶点7和23是接触的)，这可能导致多边形分解失败。如果存在问题，您可能需要找到一种方法，将这些对象作为单独的对象来查找和处理。然而，最新的Clipper2将有三角测量单元，可以处理这种退化的输入，如果你需要解决这个问题的道路上。