c++ - 从 8 个连接的像素列表中提取片段

Question

当前情况:我正在尝试从图像中提取片段。感谢 openCV 的 findContours()方法，我现在有每个轮廓的 8 个连接点的列表。但是，这些列表不能直接使用，因为它们包含很多重复项。

问题:给定一个包含 8 个连接点的列表，其中可以包含重复项，从中提取段。

可能的解决方案:

一开始我用的是openCV的approxPolyDP()方法。然而，结果很糟糕......这是放大的轮廓:

这是approxPolyDP()的结果:(9段!有些重叠)



但我想要的更像是:



这很糟糕，因为 approxPolyDP()可以在“几段”中转换“看起来像几段”的东西。但是，我所拥有的是一个倾向于对其自身进行多次迭代的点列表。

例如，如果我的观点是:

0 1 2 3 4 5 6 7 8 
  9   

然后，点列表将是 0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 9 ...如果点数变大(> 100)然后由approxPolyDP()提取的线段|不幸的是不是重复的(即:它们彼此重叠，但并不严格相等，所以我不能只说“删除重复项”，而不是例如像素)

也许，我有一个解决方案，但它很长(虽然很有趣)。首先，对于所有8-连通表，我创建一个稀疏矩阵 (为了效率)，如果像素属于列表，则将矩阵值设置为 1。然后，我创建了一个 图 ，节点对应像素，相邻像素之间的边缘。这也意味着我 添加像素之间所有缺失的边缘 (复杂度小，可能因为稀疏矩阵)。然后我删除所有可能的“正方形” (4 个相邻节点)，这是可能的，因为我已经在处理非常薄的轮廓。然后我可以启动一个最小生成树算法。最后，我可以使用 openCV 的 approxPolyDP() 来近似树的每个分支。

总结一下:我有一个乏味的方法，我还没有实现，因为它似乎容易出错。不过，请问你 , Stack Overflow 的人:还有其他现有的方法，可能有很好的实现吗？

编辑:澄清一下，一旦我有一棵树，我就可以提取“分支”(分支从叶子或节点开始，链接到 3 个或更多其他节点)然后，openCV 中的算法 approxPolyDP()是 Ramer–Douglas–Peucker algorithm ，这是它的作用的维基百科图片:



有了这张图，很容易理解为什么当点可能彼此重复时它会失败

另一个编辑:在我的方法中，可能需要注意一些有趣的事情。当您考虑位于网格中的点(如像素)时，通常，最小生成树算法没有用，因为有许多可能的最小树

X-X-X-X
|
X-X-X-X

根本不同于

X-X-X-X
| | | |
X X X X

但两者都是最小生成树

但是，就我而言，我的节点很少形成集群，因为它们应该是轮廓，并且在 findContours() 中已经有预先运行的细化算法。 .

回答 Tomalak 的评论:



如果 DP 算法返回 4 个段(从点 2 到中心的段两次)，我会很高兴!当然，通过良好的参数，我可以“偶然地”获得相同的段，并且可以删除重复项。然而，很明显，该算法不是为它设计的。

这是一个包含太多段的真实示例:

Answer 1

使用 Mathematica 8，我从图像中的白色像素列表创建了一个形态图。它在您的第一张图片上运行良好:





创建形态图:

graph = MorphologicalGraph[binaryimage];

然后您可以查询您感兴趣的图形属性。

这给出了图中顶点的名称:

vertex = VertexList[graph]

边列表:

EdgeList[graph]

这给出了顶点的位置:

pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex

这是第一张图像的结果:

In[21]:= vertex = VertexList[graph]

Out[21]= {1, 3, 2, 4, 5, 6, 7, 9, 8, 10}

In[22]:= EdgeList[graph]

Out[22]= {1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4,  3 \[UndirectedEdge] 4, 
          3 \[UndirectedEdge] 5, 4 \[UndirectedEdge] 6,  6 \[UndirectedEdge] 7, 
          6 \[UndirectedEdge] 9, 8 \[UndirectedEdge] 9,  9 \[UndirectedEdge] 10}

In[26]:= pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex

Out[26]= {{54.5, 191.5}, {98.5, 149.5},  {42.5, 185.5}, 
          {91.5, 138.5}, {132.5, 119.5}, {157.5, 72.5},
          {168.5, 65.5}, {125.5, 52.5},  {114.5, 53.5}, 
          {120.5, 29.5}}

鉴于文档，http://reference.wolfram.com/mathematica/ref/MorphologicalGraph.html ，命令 MorphologicalGraph 首先通过形态细化计算骨架:

skeleton = Thinning[binaryimage, Method -> "Morphological"]

然后检测顶点；它们是分支点和终点:

verteximage = ImageAdd[
                  MorphologicalTransform[skeleton, "SkeletonEndPoints"],   
                  MorphologicalTransform[skeleton, "SkeletonBranchPoints"]]

然后在分析它们的连通性之后将顶点链接起来。

例如，可以先打破顶点周围的结构，然后寻找连接的组件，揭示图形的边缘:

comp = MorphologicalComponents[
           ImageSubtract[
               skeleton, 
               Dilation[vertices, CrossMatrix[1]]]];
Colorize[comp] 

问题在于细节，但如果您希望开发自己的实现，这听起来是一个可靠的起点。