问题标签 [connected-components]

是否有一种使用预先计算的 KDTree 查找连接组件数量的优雅方法？现在使用呼吸优先搜索算法找到连接的组件，其邻接矩阵由 k 最近邻的 KDTree 给出，但是有更好的可能性吗？

我

我正在使用 C++ 上的 OpenCV 3.1.0 从数字骨架中提取特征。我正在寻找一种方法，它可以为我提供骨架图像中闭合轮廓的数量（例如 2 表示 8，1 表示 0、6、9，0 表示 1、2、3、4、5、7）。我使用了connectedComponents()具有 8 路连接的 OpenCV 方法，但它没有给我希望的结果。我在所有图像中总是得到 2 个连接的组件。问题是形状的内部和外部是 8 路连接的，因此它们被视为一个组件。

这张图片将解释主要问题：

有没有获得这些功能的解决方案？

我正在寻找 MATLAB 或 C++ 中优化的 4-connectivity 或 8-connectivity Connected Component Labeling 源代码。我在 MATLAB 中看到了许多连接组件标记（4 连接）的实现。

运行速度更快的实现之一是此处解释的递归实现：http: //www.mathworks.com/matlabcentral/fileexchange/38010-connected-component-labeling-like-bwlabel

MATLAB 有一个内置的 bwlabeln 或 bwlabel，它的优化程度要高得多。他们声称使用 Sedgewick's Algorithms in C, Addison-Wesley 中描述的两遍算法中的 union-find 方法。但是，很难找到它的任何源代码。有人知道吗？确实需要优化的代码。

我正在使用联合查找算法来查找无向图的所有连通分量。由于某些未知原因，它给出了错误的答案。我给出的输入图是连接的，但它为该图输出了 2 个不同的标签。

如果有人能解释这个异常，我会很高兴。是否存在一些特殊的无向图，Union-Fid 可能不起作用？

** 图表有点大，所以我添加了一张图片以提高图表的可读性。无法修剪图表，否则问题的本质将消失。**

这里，p 和 rk 分别是父级和排名。

代码

联合函数

查找功能

样本输入

图表照片

请注意，我没有考虑节点 1、2、3 和 18 及其边缘。

无向图

我是 Spark 和 GraphX 的新手，并用它的算法做了一些实验来找到连接的组件。我注意到图表的结构似乎对性能有很大的影响。

它能够计算具有数百万个顶点和边的图，但是对于某组图，该算法没有及时完成，但最终以OutOfMemoryError: GC overhead limit exceeded.

该算法似乎对包含长路径的图有问题。例如，对于此图{ (i,i+1) | i <- {1..200} }，计算失败。但是，当我添加传递边时，计算立即完成：

像这样的图表也没有问题：

这是重现问题的最小示例：

The input.graph file can look this this (10 nodes, 9 edges connecting them):

When it fails, it hangs in ConnectedComponents.run(graph). The error message is:

I am running a local Spark node and start the JVM with the following options:

Can you help me understand why it has problem with this toy graph (201 nodes and 200 edges), but on the other hand can solve a realistic graph with multiple millions of edges in about 80 seconds? (In both examples, I use the same setup and configuration.)

UPDATE:

Can also be reproduced in the spark-shell:

I created a bug report: SPARK-15042

GraphX 带有一种用于查找图的连通分量的算法。

我没有找到有关其实现复杂性的声明。

通常，可以在线性时间内找到连接的组件，例如通过广度优先搜索或深度优先搜索（参见Wikipedia 文章）。但是，这假设您可以将图形保存在内存中。GraphX 实现了一种分布式的核外算法，所以我认为它没有可比性。

你知道他们的算法是如何工作的，复杂度是多少吗？

我有一个 CT 肺 3d 体积，我正在使用 matlab 提取结节并对其进行分类......我需要从体积中消除“删除”气道，为了最大限度地减少可疑结节，matlab 中有一个连接组件功能但它只适用于 2d 图像.. 因此我需要一个 3d 连接组件功能，肺中最大的连接组件将是气道，如果我处理它，我将能够从我的体积中删除它，简而言之，我需要检测体积中最大的连通分量

在matlab中你可以使用

获取每个连接组件的像素列表。什么是python等价物？我试过了

但是，要获取标签，这不附带像素列表。
有什么建议么？

我的目标是根据 R 中两列之间的共享值识别单个数据框中的“连接”行。

在此示例中，有 10 个唯一段（即数据集群），它们由对应于每个唯一段的整数标识。每行代表已经确定在彼此的特定距离阈值内的两个段。列“segA”和“segB”之间没有显着区别，它们仅用于跟踪连接的段对。列“dist”表示这对线段之间的距离，但此时并不真正需要，因为数据帧仅包含那些被视为“连接”的线段对。

我试图找出一种方法来识别在“segA”或“segB”中至少具有一个共享值的所有行，指示行之间的连接段。

我最初的尝试对于循环和逻辑语句很复杂（我是 R 编程的新手），所以我非常感谢任何简洁的解决方案！

例子：

第 1 行和第 2 行是相连的，因为它们都包含段“1”。

第 3 行和第 1 行是相连的，因为它们都包含段“2”等。

尽管第 2 行和第 3 行没有通过共享段的存在直接连接，但总体而言，它们通过第 1 行的相互连接而连接。

所需的最终输出将类似于：

其中 (1)、(2) 和 (3) 表示不同的整体段及其直接/相互连接的组件。

我在大型数组中有许多不同的形式，numpy我想使用 和 计算它们之间的边到边欧几里得numpy距离scipy。

注意：我进行了搜索，这与堆栈上之前的其他问题不同，因为我想获得数组中标记的补丁之间的最小距离，而不是其他问题所问的点或单独数组之间的距离。

我目前的方法使用 KDTree，但对于大型数组来说效率非常低。本质上，我正在查找每个标记组件的坐标并计算所有其他组件之间的距离。最后以平均最小距离为例进行计算。

我正在寻找一种使用 python 的更智能的方法，最好不要使用任何额外的模块。

编辑 刚刚测试了@morningsun 提出的解决方案，这是一个巨大的速度改进。但是返回的值略有不同：

编辑 2

啊，想通了。spatial.distance.pdist 没有返回正确的距离矩阵，因此这些值是错误的。