用多边形近似一个形状

Question

从包含透明区域和彩色区域的PNG图像中，我想生成一个具有N条边(N是可配置的)的多边形，以近似图像的最佳边缘。我想让这个多边形由一系列向量定义

例如，考虑下面的图像:+链接到+。我可以通过计算每个像素周围透明像素的数量来检测图像的边缘。我得到了下面的矩阵:

0000000000000000
0000053335000000
0000030003000000
0000030003000000
0000020002000000
0533210001233500
0300000000000300
0300000000000300
0300000000000300
0533210001233500
0000020002000000
0000030003000000
0000030003000000
0000053335000000
0000000000000000
0000000000000000

我认为，基于这个矩阵，我应该能够得到所有角的坐标，从而得到向量，但我不知道怎么做。在本例中，我希望我的程序返回:

[7,2]->[11,2]
[11,2]->[11,6]
[11,6]->[15,6]
... 

你们有什么建议或链接吗?

最后，我还想要90和0以外的近似角度，但这实际上是第二阶段。

Answer 1

我想你会发现CV工具包中的一些工具对你有用。您最好利用这些资源，而不是推出自己的解决方案。

我想你会有兴趣提取的两个特征是边和角。

边，就像你想要的，可以让你接近形状的轮廓。你现在可能对边缘检测技术不感兴趣。这些将把你的图像转换成边缘/空间的二值图像。相反，你会想看看霍夫变换，它可以为你的图像中的每条线提供端点。如果你处理的是轮廓清晰、实心的直线，就像你看起来的那样，这应该很有效。你已经把你的问题标记为Ruby，所以也许你可以看看OpenCV (OpenCV是用C写的，但有Ruby - OpenCV和javacv项目绑定)。这里是OpenCV的霍夫变换文档。然而，你可能会发现，霍夫变换并没有给出连接的线。这取决于图像中实际线条的规则性/不规则性。因此，您可能需要手动将行的端点连接到一个结构中。

角对于您提供的图像可能工作得很好。标准算法是哈里斯角点检测。与霍夫变换类似，您可以使用此技术返回图像中"最重要"的特征。这项技术以提供一致的结果而闻名，即使对同一事物的不同图像也是如此。因此，它经常用于模式识别等。但是，如果您的图像与所提供的图像一样简单，则可以用这种方式提取形状的所有角。得到图像的形状只需要在给定N条边的情况下以有意义的方式连接这些点。

你应该绝对玩这两个特征空间，看看它们是如何工作的，你可以可能同时使用它们以获得更好的结果。

顺便说一句，如果你的图像真的是透明的颜色/强度，你可以将你的图像转换为"二进制图像"。注意，这不仅仅是二进制数据。相反，它意味着你只代表两种颜色，一种由0代表，另一种由1代表。这样就打开了一套处理灰度和二值图像的工具。例如，上面手动计算的数字矩阵称为距离变换，可以使用OpenCV等工具轻松有效地完成。

Answer 2

霍夫变换是查找给定一组点的直线、多边形和其他形状的标准技术。这可能正是你要找的。你可以使用霍夫变换找到图像中所有可能的线段，然后将附近的线段组合在一起，得到一组近似图像的多边形。

希望这对你有帮助!

Answer 3

在这种简单的情况下，您可以执行以下三个步骤:找到形状的质心，根据x轴与当前点与质心形成的直线之间的夹角对感兴趣的点进行排序，遍历排序后的点。

在给定的情况下，质心的x坐标等于每个兴趣点的x坐标之和除以兴趣点的总数(分别为质心的y坐标)。要计算角度，只需使用几乎任何语言的atan2即可。你的兴趣点是那些显示为1或5的点，否则它就不是角(基于你的输入)。

不要以为Hough会解决你的问题，也就是说，它不会给出你想要的排序坐标。这也是一种昂贵的方法。此外，给定您的矩阵，您已经拥有了如此完美的信息，以至于没有其他方法可以胜过(当然，问题是重复您所呈现的如此好的结果——在这些情况下，霍夫可能证明是有用的)。

我的Ruby很糟糕，所以把下面的代码作为你的问题的指导:

include Math
data = ["0000000000000000",
    "0000053335000000",
    "0000030003000000",
    "0000030003000000",
    "0000020002000000",
    "0533210001233500",
    "0300000000000300",
    "0300000000000300",
    "0300000000000300",
    "0533210001233500",
    "0000020002000000",
    "0000030003000000",
    "0000030003000000",
    "0000053335000000",
    "0000000000000000",
    "0000000000000000"]
corner_x = []
corner_y = []
data.each_with_index{|line, i|
    line.split(//).each_with_index{|col, j|
        if col == "1" || col == "5"
            # Cartesian coords.
            corner_x.push(j + 1)
            corner_y.push(data.length - i)
        end
    }
}
centroid_y = corner_y.reduce(:+)/corner_y.length.to_f
centroid_x = corner_x.reduce(:+)/corner_x.length.to_f
corner = []
corner_x.zip(corner_y).each{|c|
    dy = c[1] - centroid_y
    dx = c[0] - centroid_x
    theta = Math.atan2(dy, dx)
    corner.push([theta, c])
}
corner.sort!
corner.each_cons(2) {|c|
    puts "%s->%s" % [c[0][1].inspect, c[1][1].inspect]
}

结果是:

[2, 7]->[6, 7]
[6, 7]->[6, 3]
[6, 3]->[10, 3]
[10, 3]->[10, 7]
[10, 7]->[14, 7]
[14, 7]->[14, 11]
[14, 11]->[10, 11]
[10, 11]->[10, 15]
[10, 15]->[6, 15]
[6, 15]->[6, 11]
[6, 11]->[2, 11]

从最左下角的点(笛卡尔坐标从(1,1)开始，最左下角的位置)逆时针顺序的顶点