从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个neighouring节点),这是可能的,因为我已经在很薄的轮廓上工作.然后我可以启动最小生成树算法.最后,我可以使用openCV来近似树的每个分支approxPolyDP()

细分http://img197.imageshack.us/img197/4488/segmentation.png

这是原始列​​表的精彩图片(感谢Paint!)和相关图表.然后,当我在邻居之间添加边缘时.最后,当我删除边缘并制作最小生成树(这里没用)

总结一下:我有一个乏味的方法,我还没有实现,因为它似乎容易出错.但是,我问你,StackOverflow的人:是否有其他现有的方法,可能有很好的实现？

---

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

通过这张图片,很容易理解为什么当点可能彼此重复时它会失败

---

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

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] 

魔鬼在细节中,但如果您希望开发自己的实现,这听起来像一个坚实的起点.

Answer 2

尝试数学形态学.首先,您需要dilate或close您的图像填补漏洞.

cvDilate(pimg, pimg, NULL, 3);
cvErode(pimg, pimg, NULL);

我有这个图像

下一步应该是应用细化算法.可惜这不是在实现OpenCV(MATLAB有bwmorph带thin参数).例如,使用MATLAB,我将图像细化为:

然而OpenCV已经全部所需的基本形态的操作来实现细化(cvMorphologyEx,cvCreateStructuringElementEx,等).

另一个想法.

他们说距离变换似乎在这些任务中非常有用.可能是吧.考虑cvDistTransform功能.它创建了一个像这样的图像:

然后使用类似的东西cvAdaptiveThreshold:

那是骨架.我想你可以迭代所有连接的白色像素,找到曲线并滤除小段.

Answer 3

之前我已经实现了类似的算法,并且我采用了一种渐进的最小二乘方式.它运作得相当好.伪代码有点像:

L = empty set of line segments
for each white pixel p
  line = new line containing only p
  C = empty set of points
  P = set of all neighboring pixels of p
  while P is not empty
    n = first point in P
    add n to C
    remove n from P
    line' = line with n added to it
    perform a least squares fit of line'
    if MSE(line) < max_mse and d(line, n) < max_distance
      line = line'
      add all neighbors of n that are not in C to P
  if size(line) > min_num_points
    add line to L

其中MSE(线)是线的均方误差(与最佳拟合线的平方距离线中所有点的总和),d(线,n)是从点n到线的距离.max_distance的良好值似乎是一个像素左右,而max_mse似乎要小得多,并且将取决于图像中线段的平均大小.对于我来说,0.1或0.2像素在相当大的图像中工作.

我一直在使用Canny算子预处理的实际图像上使用它,所以我唯一的结果就是这样.以下是图像上述算法的结果:

也可以快速制作算法.我有C++实现(由我的工作强制执行的闭源,对不起,否则我会给你)在大约20毫秒内处理上面的图像.这包括应用Canny算子进行边缘检测,因此在您的情况下应该更快.