标签: connected-components

我使用scikit-image中提供的measure.regionprops方法来测量连接组件的属性.它计算了一堆属性(Python-regionprops).但是,我只需要每个连接组件的区域.有没有办法只计算一个属性并节省计算？

我正在尝试使用连接的组件，但缩放时遇到问题。我的这里就是我所拥有的-

// get vertices
val vertices = stage_2.flatMap(x => GraphUtil.getVertices(x)).cache

// get edges
val edges = stage_2.map(x => GraphUtil.getEdges(x)).filter(_ != null).flatMap(x => x).cache

// create graph  
val identityGraph = Graph(vertices, edges)

// get connected components
val cc = identityGraph.connectedComponents.vertices

在哪里，GraphUtil具有帮助程序功能以返回顶点和边。在这一点上，我的图有大约100万个节点和200万个边（顺便说一句，预计将增长到1亿个节点）。我的图非常稀疏，因此我希望有很多小图。

当我执行上述操作时，我会不断得到java.lang.OutOfMemoryError: Java heap space。我已经尝试executor-memory 32g并运行了15个节点的集群，其纱线容器大小为45g。

这是异常详细信息：

16/10/26 10:32:26 ERROR util.Utils: uncaught error in thread SparkListenerBus, stopping SparkContext
java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOfRange(Arrays.java:2694)
    at java.lang.String.<init>(String.java:203)
    at java.lang.StringBuilder.toString(StringBuilder.java:405)
    at com.fasterxml.jackson.core.util.TextBuffer.contentsAsString(TextBuffer.java:360)
    at com.fasterxml.jackson.core.io.SegmentedStringWriter.getAndClear(SegmentedStringWriter.java:98)
    at com.fasterxml.jackson.databind.ObjectMapper.writeValueAsString(ObjectMapper.java:2216)
    at org.json4s.jackson.JsonMethods$class.compact(JsonMethods.scala:32)
    at …

我的桌子有account_id和device_id.一个account_id可以有多个device_ids,反之亦然.我试图计算每个连接的多对多关系的深度.

例如:

account_id | device_id
1 | 10
1 | 11
1 | 12
2 | 10
3 | 11
3 | 13
3 | 14
4 | 15
5 | 15
6 | 16

如何构建一个知道将1-3帐户组合在一起,4-5组合在一起,并自行离开6的查询？帐户1-3的所有7个条目应该组合在一起,因为它们在某个时刻都触及了相同的account_id或device_id.我试图将它们组合在一起并输出计数.

帐户1在设备10,11,12上使用.这些设备也使用其他帐户,因此我们希望将它们包含在组中.他们使用了额外的帐户2和3.但帐户3被另外2个设备进一步使用,因此我们也将其包括在内.群组的扩展会带来任何其他帐户或设备,这些帐户或设备也"触及"该群组中已有的帐户或设备.

图表如下所示:

我有一个二进制3D numpy数组，我想为其寻找连接的组件，即ID值为1的邻居元素。

data = np.random.binomial(1, 0.4, 1000)
data = data.reshape((10,10,10))

或者，我可以获取值为1的每个元素的坐标，并获取包含三个元素的一组列表，以获取相邻的簇

coordinates = np.argwhere(data > 0)

connected_elements = []
for node in coordinates:
  neighbors = #Get possible neighbors of node
  if neighbors not in connected_elements:
    connected_elements.append(node)
  else:
    connected_elements.index(neighbor).extend(node)

如何执行此操作，或为3D设置实现2D connected_components函数？

我有一个灰度图像，其值介于 0（黑色）和白色（255）之间。我有一个target与灰度图像大小相同的矩阵。我需要从灰度图像中的一个随机像素开始，一次遍历图像一个像素（以深度优先搜索方式），将其值复制到target矩阵中的相应位置。我显然只需要对非白色像素执行此操作。我怎样才能做到这一点？本以为可以得到灰度图像的连通分量，将每个像素点一个一个地遍历，但是找不到合适的连通分量的实现。有任何想法吗？

例如，如果我的灰度图像是：

[[255,255,255,255,255,255,255]
[255,255, 0 ,10 ,255,255, 1 ]
[255,30 ,255,255,50 ,255, 9 ]
[51 ,20 ,255,255, 9 ,255,240]
[255,255,80 ,50 ,170,255, 20]
[255,255,255,255,255,255, 0 ]
[255,255,255,255,255,255, 69]]

然后可能的遍历[0,10,50,9,170,50,80,20,51,30]后跟[1,9,240,20,0,69]to give [0,10,50,9,170,50,80,20,51,30,1,9,240,20,0,69]。不同对象之间的顺序无关紧要。

其他可能的遍历是： [1,9,240,20,0,69,0,10,50,9,170,50,80,20,51,30]或[1,9,240,20,0,69,0,10,50,9,170,50,80,20,30,51]或 [1,9,240,20,0,69,10,50,9,170,50,80,20,30,0,51]

等等。

我想找到图形的所有连通组件,其中组件具有多个元素.

使用the clusters赋予不同集群的成员资格并使用cliques不提供连接的组件.

这是一个跟进

R中的多个列表交集

我的主要目标是找到所有具有相互共同元素的列表组.

提前致谢!

我很难想出一个描述我想要解决的问题的标题，所以如果你有更好的标题，请发表评论！

解决方案可以是R、Python 或 SQL（准确地说是 Aster TeraData SQL，尽管任何 SQL 语言的解决方案对于学习目的都非常有帮助）

问题：给定一组没有特定顺序的项目对，生成一个输出，将与至少一个链接相关的所有项目对链接在一起。

这是一个使用 R 的简单示例：

colone = c("a","b","u","e","f","f","j","z")
coltwo = c("b","c","c","a","g","h","h","y")
d <- data.frame(colone, coltwo)
d
  colone coltwo
1      a      b
2      b      c
3      u      c
4      e      a
5      f      g
6      f      h
7      j      h
8      z      y

所需的输出（在任何易于阅读的数据结构中）：

(a,b,c,e,u)
(f,g,h,j)
(y,z)

本质上，输入表示节点和边的图。所需的输出是图中连接的所有对象的列表。

任何帮助或想法将不胜感激！

数字形状是二进制图像(blob)中的一组连接像素.

它可以通过行程编码紧凑地表示,即将像素分组为水平线段并存储起始端点坐标和长度.通常,RLC表示以光栅顺序存储运行,即逐行和从右到右.

对于平滑的形状,存储要求从O(N²)下降到O(N).

形状的轮廓是一个封闭的像素链,当其内部被填充时(通过填充算法)恢复形状.它也是O(N)表示.Wen的形状可用作位图,轮廓可以通过轮廓算法获得.

我正在寻找一种算法,该算法直接计算给定其RLC表示的形状轮廓,而不是在中间位图中绘制它.期望算法在运行次数中以时间线性运行.

你有遇到过解决方案吗？

我正在尝试优化我们的一些计算机视觉算法，并决定cv::connectedComponents对cv::findContours(和cv::drawContours) 进行基准测试以实现类似的结果。

本质上，我们需要做的就是在二值图像中找到斑点，然后选择最大的斑点 - 这是一个相当标准的操作。

我对 OpenCV 的效率有点不太了解，过去几年我只将它用于 Python 中的算法原型设计，所以我决定运行上述两种方法的基准测试。

我对我的结果有点困惑，因为这个评论似乎表明findContours应该慢得多，这与我观察到的相反（结果在帖子的下方）。我怀疑，事实上我的结果表明，findContours在二进制图像上使用，然后将每个轮廓绘制为不同的索引比运行完整的连接组件分析要快一些。

他们还表明，仅计算这些轮廓的面积，而不是计算完整的统计数据，速度connectedComponentsWithStats要快得多。

我是否误解了这里发生的事情？我希望这两种方法会产生相似的结果。

计时结果：

Starting simple benchmark (100000 iterations) ...
2668ms to run 100000 iterations of findContours
3358ms to run 100000 iterations of connectedComponents
Starting area calculation benchmark (100000 iterations) ...
2691ms to run 100000 iterations of findContours
11285ms to run 100000 iterations of connectedComponentsWithStats
AVERAGE TIMES (ms): 
findContours:           0.0267
connectedComps:         0.0336
findContours (areas):   0.0269
connectedComps …

设置

我们假设以下无向图：

import networkx as nx

G = nx.from_edgelist([(0, 3), (0, 1), (2, 5), (0, 3)])
G.add_nodes_from(range(7))

甚至添加 (1, 3) 边（这里并不重要）：

连接的组件是：

list(nx.connected_components(G))
# [{0, 1, 3}, {2, 5}, {4}, {6}]

问题

是否可以G直接从连接组件列表生成图形networkx？或者使用简单的方法？

到目前为止，我发现的唯一解决方案是生成每组的连续边或节点的所有组合并将其提供给nx.from_edgelist，然后使用以下命令添加单个节点add_nodes_from：

from itertools import pairwise, chain

l = [{0, 1, 3}, {2, 5}, {4}, {6}]

G = nx.from_edgelist(chain.from_iterable(pairwise(e) for e in l))
G.add_nodes_from(set.union(*l))

或对于所有边：

from itertools import combinations, chain

l = [{0, 1, 3}, {2, 5}, {4}, {6}]

G …