从8连接的像素列表中提取分段
目前情况 ：我试图从图像中提取细分。 感谢openCV的findContours()方法，我现在有一个8连接点的列表，每个轮廓。 但是，这些列表不能直接使用，因为它们包含很多重复项。
问题 ： 给定一个可以包含重复的8连接点的列表，从中提取段。
可能的解决scheme ：
- 起初，我使用了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()提取的段是不幸的不重复（即：它们相互重叠，但并不严格平等，所以我不能只是说“删除重复”，而不是像素）
- 也许，我有一个解决scheme，但它很长（虽然有趣）。 首先，对于所有的8连接列表，我创build一个稀疏matrix （效率），如果像素属于列表，则将matrix值设置为1。 然后，我创build一个graphics ，其中节点对应于像素，以及相邻像素之间的边缘。 这也意味着我添加所有像素之间的缺失边缘 （复杂性小，可能因为稀疏matrix）。 然后我删除所有可能的“方块” （4个相邻节点），这是可能的，因为我已经在研究非常薄的轮廓。 然后我可以启动一个最小生成树algorithm。 最后，我可以用openCV的
approxPolyDP()来近似树的每一个分支
分割http://img197.imageshack.us/img197/4488/segmentation.png
这里是原始列表的梦幻般的图片（谢谢油漆！），和相关的图表。 然后，当我添加邻居之间的边缘。 最后，当我删除边缘，并作出最小生成树（这里没有用）
总结：我有一个乏味的方法，我还没有实现，因为它似乎容易出错。 但是，我问你 ，StackOverflow的人：还有其他现有的方法，可能有很好的实现？
编辑：为了澄清，一旦我有一棵树，我可以提取“分支”（分支开始在叶子或节点链接到3个或更多的其他节点）然后，在openCV的approxPolyDP()algorithm是Ramer-Douglas-Peuckeralgorithm ，这里是维基百科的图片：
有了这张照片，很容易理解为什么它失败时点可能是相互重复的
另一个编辑：在我的方法，有一些可能是有趣的要注意。 当考虑位于网格中的点（如像素）时，一般来说，最小生成树algorithm是无用的，因为有许多可能的最小树
XXXX | XXXX
与基金会非常不同
XXXX | | | | XXXX
但都是最小的生成树
然而，就我而言，我的节点很less形成簇，因为它们被认为是轮廓，并且已经有了一个细化的algorithm，事先在findContours() 。
回答Tomalak的评论：
如果DPalgorithm返回4段（从第2点到中心的那段两次），我会很高兴！ 当然，如果参数很好，我可以进入一个“偶然”的状态，我有相同的段，我可以删除重复。 但是，显然，algorithm不是为它devise的。
这是一个真正的例子，有太多的细分市场：
使用Mathematica 8，我从图像中的白色像素列表创build了一个形态图。 它在你的第一张图片上工作正常：
创build形态图：
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]
魔鬼是在细节，但是这听起来像一个坚实的起点，如果你想开发自己的实现。
尝试math形态学。 首先，你需要dilate或close你的形象来填补空白。
cvDilate(pimg, pimg, NULL, 3); cvErode(pimg, pimg, NULL);
我有这个形象
下一步应该是应用细化algorithm。 不幸的是，它并没有在OpenCV实现（MATLAB有bwmorph ，参数thin ）。 以MATLAB为例，我将图像细化为这个图像：
然而， OpenCV都需要基本的形态操作来实现细化（ cvMorphologyEx ， cvCreateStructuringElementEx等）。
另一个想法。
他们说距离变换在这样的任务中似乎非常有用。 也许是这样。 考虑cvDistTransform函数。 它创build一个像这样的图像：
然后使用像cvAdaptiveThreshold ：
那是骨架 我想你可以遍历所有连接的白色像素，find曲线，并过滤出小段。
之前我已经实现了一个类似的algorithm，而且我用一种增量最小二乘方式来实现。 它工作得很好。 伪代码有点像：
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似乎要less得多，并将取决于图像中线段的平均大小。 0.1或0.2像素为我工作在相当大的图像。
我一直在使用Canny算子预处理的实际图像，所以我唯一的结果就是这样。 这是上面的algorithm在图像上的结果： 
也可以使algorithm更快。 我有C ++实现（闭源由我的工作强制执行，对不起，否则我会给你）在大约20毫秒处理上述图像。 这包括应用Canny算子进行边缘检测，所以在你的情况下应该更快。
