标签: graph

目前的情况:我正在尝试从图像中提取片段.感谢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

在基金会上是非常不同的 …

我熟悉Java Collection Framework,它包含基本的接口:Collection和Map.我想知道为什么框架不包含作为基本集合的树和图形的结构.两者都可以视为子类型Collection.

顺便说一句,我知道TreeSet是由Red-Black Tree底层实现的.但是,TreeSet它不是树而是a Set,因此框架中没有真正的树.

我正在努力为一个介绍级别的CS课程设置一个问题集,并提出一个问题,从表面上看,似乎很简单:

您将获得一份包含父母姓名,出生日期和死亡日期的人员名单.你有兴趣找出谁在他们一生中的某个时刻是父母,祖父母,曾祖父母等等.设计一个算法,用这个信息作为一个整数来标记每个人(0表示这个人从来没有过孩子,1表示该人是父母,2表示该人是祖父母,等等.)

为简单起见,您可以假设族图是DAG,其无向版本是树.

这里有趣的挑战是你不能只看树的形状来确定这些信息.例如,我有8位曾祖父母,但由于我们出生时没有一个人活着,在他们的一生中,他们中没有一个是伟大的曾祖父母.

我能解决这个问题的最佳算法是在时间O(n ²)中运行,其中n是人数.这个想法很简单 - 从每个人开始一个DFS,找到在该人死亡日期之前出生的家谱中最远的后代.但是,我很确定这不是问题的最佳解决方案.例如,如果图形只是两个父母及其n个孩子,那么问题可以在O(n)中平凡地解决.我希望的是一些算法要么胜过O(n ²),要么运行时参数化在图形的形状上,这使得它对于宽图形来说很快,在最坏的情况下优雅地降低到O(n ²)案件.

在Matlab的Python的matplotlib中是否有明确的等效命令hold on？我试图在同一轴上绘制所有图形.一些图表是一个内部产生for循环,而这些是从单独绘制su和sl:

import numpy as np
import matplotlib.pyplot as plt

for i in np.arange(1,5):
    z = 68 + 4 * np.random.randn(50)
    zm = np.cumsum(z) / range(1,len(z)+1)
    plt.plot(zm)
    plt.axis([0,50,60,80])

plt.show()

n = np.arange(1,51)
su = 68 + 4 / np.sqrt(n)
sl = 68 - 4 / np.sqrt(n)

plt.plot(n,su,n,sl)

plt.axis([0,50,60,80])
plt.show()

基本上,我知道如何创建图形数据结构,并在允许副作用的编程语言中使用Dijkstra算法.通常,图算法使用一种结构将某些节点标记为"已访问",但这有副作用,我试图避免这种情况.

我可以想到一种在函数式语言中实现它的方法,但它基本上需要将大量的状态传递给不同的函数,我想知道是否有更节省空间的解决方案.

我正在实现一些算法来教自己关于图形以及如何使用它们.你会推荐什么是在Java中最好的方法？我在想这样的事情:

public class Vertex {

    private ArrayList<Vertex> outnodes; //Adjacency list. if I wanted to support edge weight, this would be a hash map.

    //methods to manipulate outnodes
}

public class Graph {
    private ArrayList<Vertex> nodes;
    //algorithms on graphs
}

但我基本上只是做了这件事.有没有更好的办法？

此外,我希望它能够支持诸如有向图,加权边,多图等香草图的变化.

我读到它是理想的通过邻接列表表示稀疏图形和通过邻接矩阵表示密集图形.但我想了解稀疏图和密集图之间的主要区别.

我正在尝试使用参数normed = 1创建直方图

例如:

import pylab

data = ([1,1,2,3,3,3,3,3,4,5.1])    
pylab.hist(data, normed=1)
pylab.show()

我预计这些垃圾箱的总和将是1.但是,其中一个垃圾箱大于1.这个标准化做了什么？如何创建一个直方图,直方图的积分等于1？

这是为什么大多数图算法不能轻易适应负数的后续问题？.

我认为Shortest Path(SP)在负权重方面存在问题,因为它会沿着路径累加所有权重并尝试找到最小权重.

但我不认为最小生成树(MST)存在负权重问题,因为它只需要单个最小权重边缘而不关心总权重.

我对吗？

如果我有一个无向图(实现为顶点列表),我怎样才能找到它的连通组件？我怎样才能使用快速联合？