三维图像上连接的组件支持多个标签。
connected-components-3d的Python项目详细描述
连接部件3D
使用26、18或6连通邻域在三维中实现连通分量。该软件包使用了rosenfeld和pflatz的两遍法的3d变体，并在wu、otoo和suzuki的2d8连通工作的基础上增加了union-find和决策树。此实现与包含许多不同标签的图像兼容，而不仅仅是二进制图像。它可以用于二维或三维图像。
我写这个包是因为我正在研究密集标记的脑组织三维生物医学图像（例如512x512x512体素）。我回顾的其他现成实现仅限于二进制图像。这使得这些其他包对于我的用例来说太慢了，因为它需要屏蔽每个标签并每次运行一次连接组件算法。作为参考，在一个给定的卷中通常有成百上千个标签。此软件包的好处是，它可以一次性标记所有连接的组件，从而将性能提高一个或多个数量级。
pythonpipinstallaction
如果您的平台上有兼容的二进制文件，则安装非常简单。
pip install connected-components-3d
如果兼容的二进制文件不可用，您可以从源代码安装，如下所示。
< EM >需要C++编译器。<／P>
pip install numpy pip install connected-components-3d --no-binary :all:
偶尔，您可能会成功安装cc3d，但在导入时，您会看到一个错误，其中包括：numpy.ufunc size changed，可能表示二进制不兼容。cc3d是针对numpy 1.16+编译的，不幸的是，numpy1.15和1.16之间存在向后不兼容。在这种情况下，您可以尝试升级numpy或从源代码处编译。
python手动安装
< EM >需要C++编译器。<／P>
pip install -r requirements.txt python setup.py develop
python使用
importcc3dimportnumpyasnplabels_in=np.ones((512,512,512),dtype=np.int32)labels_out=cc3d.connected_components(labels_in)# 26-connectedconnectivity=6# only 26, 18, and 6 are allowedlabels_out=cc3d.connected_components(labels_in,connectivity=connectivity)# You can extract individual components like so:N=np.max(labels_out)forsegidinrange(1,N+1):extracted_image=labels_out*(labels_out==segid)process(extracted_image)# We also include a region adjacency graph function # that returns a set of undirected edges. It is not optimized # (70-80x slower than connected_components) but it could be improved.graph=cc3d.region_graph(labels_out,connectivity=connectivity)
如果您大致知道要生成多少个标签，则可以通过指定一个大于该范围的安全系数来节省一些内存。输入标签中的最大标签ID必须小于max_labels
labels_out=connected_components(labels_in,max_labels=20000)
注：C和FORTRAN顺序数组将分别按行主顺序和列主顺序进行处理，因此标签的编号将被"转置"。因为数组的维数不会改变，所以这里有吓人的引号。
C++使用
#include"cc3d.hpp"// 3d array represented as 1d arrayint*labels=newint[512*512*512]();uint32_t*cc_labels=cc3d::connected_components3d<int>(labels,/*sx=*/512,/*sy=*/512,/*sz=*/512);
算法描述
本软件包中包含的算法是对Rosenfeld和Pflatz（RP）在1968年[1]所描述的二维图像连接组件算法的三维图像的精化（这一点在此youtube视频）使用等效列表实现为tarjan's union find disjoint set with path compression and balancing[2]，并使用基于wu、otoo和suzuki（wos）工作的决策树进行扩充。[3]下面的描述描述了26连接的算法，但是一旦您理解了它，就很容易得到18和6。
二维第一原理
在RP的二进制二维图像的4连接双通道方法中，该算法进行光栅扫描，每次它第一次遇到前景像素（其顶部和左侧的像素是背景像素）时，它都会用一个新标签标记它。如果附近有一个先前存在的标签改用那个标签。当两个标签相邻时，它记录它们是等价的，以便在第二遍中可以一致地重新标记它们。这种等价表可以用多种方法构造，但目前常用的方法有联合查找、秩平衡路径压缩和selkow算法（可以避免管道阻塞）。[4]然而，selkow的算法是为深度为2的两棵树设计的，适合于二值图像。我们希望同时处理多个标签，使Union查找更可取。
在第二个过程中，使用等价表重新标记像素。union find建立一个标签作为树的根标签，根被认为是代表性标签。然后用代表性标签标记每个像素。因此，联合查找适合于表示不相交集。路径压缩和平衡从根本上降低了树的高度，从而加速了第二次传递。
wos解决了在二值图像上加速8连通二维连通分量的问题。8-连接标签是通过将RP的前向传递掩码扩展到左上角和右上角像素来实现的。在基于联合查找的连通组件算法中，第一步的统一步骤是代价最高的步骤。wos展示了如何使用利用本地拓扑结构的决策树来优化掉大部分调用。例如，由于当前像素的上中心邻接点也与其他掩模元素相邻，所有掩模元素都已通过光栅扫描方向进行了处理，因此如果存在，则足以复制其值并继续移动。如果不存在，请从剩余的前景像素中选择一个，复制它们的值，并对右侧的遮罩元素使用unify，因为现在知道它与左侧不相邻。WOS的算法继续以这种方式进行，直到找到匹配项或处理所有遮罩元素，此时将创建一个新标签。
多年来，这种算法是世界上最快的，尽管它已经被一项新的工作所取代，该工作将静态决策树转换为动态决策树，或者在其他改进中预先计算生成决策树。然而，wos的工作对于它的简单性和速度都是非常重要的，因此也是这个库的灵感来源。
扩展到三维
下面介绍的方法与Sutheebanjard[6]的方法非常相似。若要移动到三维26连接的邻域，必须将遮罩延伸到三维才能连接相邻平面。请注意，8连接的遮罩覆盖了邻域的后半部分（已经处理过的部分），以便当前像素可以依赖这些标签。因此，26个连通邻域的遮罩仅覆盖三个潜在平面中的两个：整个下平面（9个体素）和与当前平面上的wos（4个体素）相同的遮罩。虽然可以进行进一步的优化，但首先，可以从概念上将问题分解为两个部分：建立到底平面的9连接链接，然后建立到当前平面的8连接链接。这是因为当前像素用作集线器，将连接信息从9连接的步骤传输到8连接的步骤。
图1：8连接平面的遮罩。如果J、K、L和M都被删除，则只保留N并分配新标签。
<表><广告>算法所针对的第一个z平面（z=0）是特殊的：边缘效果忽略了遮罩的底面。因此，由于剩余的蒙版仅为8连接的2d蒙版的压缩，因此经过此过程后，图像的底部是8连接的。当z=1时，面罩的9连接部分启动，形成连接作用于z=0，使当前平面（8+9）17连接。在z=2时，9连接的底部遮罩现在在顶部形成从z=1到z=2的连接，使z=1（17+9）26连接。通过归纳法，当这一过程进行到完成时，会产生26个相连的卷标签。
在wos的启发下，我们在密贴标签的底平面上构造了一个决策树，以最小化我们需要执行的统一操作的数量。
图2。三维下平面的遮罩。
<表><广告>由于e连接到所有其他体素（如果存在），因此可以简单地复制它。如果不存在e，则b和h完全覆盖遮罩。如果不存在b，则h，a，c构成覆盖物。如果不存在h，则b，g，i是一个。下面是覆盖物的列表，因此列表中的每个后续条目假定上面条目中的第一个字母是背景。
eb，（hg，i）h，a，cd，（fc，i）f，g，aa，c，g，ic，g，ig，ii< > >- A.Rosenfeld和J.Pfaltz。"数字图像处理中的顺序操作"。ACM杂志。第13卷，第4期，1966年10月，第471-494页。doi:10.1145/321356.321357（链接）
- R.E.Tarjan。"一个好的但不是线性集合合并算法的效率。ACM杂志，22:215-2251975。（链接）
- 吴家俊，东洋俊，铃木俊。"两种加速连接元件标记算法的策略"。劳伦斯伯克利国家实验室。LBNL-291022005年。（链接）
- 塞尔科夫。"树到树的编辑问题"。信息处理信件。第6卷，第6期。1977年6月。doi:10.1016/0020-0190（77）90064-3（链接）
- C.格拉纳，D.博尔盖萨尼，R.库奇亚拉。"基于块的连接元件优化决策树标记"。图像处理的ieee事务。第19卷，国际空间站。6。2010年6月。doi:10.1109/tip.2010.2044963（链接）
- 萨特班贾德。"三维连通元件标注决策树"。PROC2012年医学与教育信息技术国际研讨会。doi:10.1109/itime.2012.6291402（链接） < > >
然后构造决策树，以便使用尽可能少的统一性来评估每个覆盖物。注意到e和b都完全连接到上面的2d掩码，可以进一步优化这一点。因此，如果它们中的任何一个存在，我们可以跳过8连接的统一步骤。如果b是背景，也可以先尝试df覆盖，这样就可以比hac节省一个统一性，即使是给定的统计数据，但是在我尝试的数据集上，它似乎稍微慢一些。要从二进制数据移动到多标签数据，我只需将前台和后台的测试替换为匹配标签的测试。
为了实现一个相当快的实现，我实现了联合查找和路径压缩。我保守地使用了一个等于图像大小的ids数组作为union-find数据结构，而不是稀疏映射。union-find数据结构加上输出标签意味着内存消耗将是输入+输出+秩+等价。如果输入标签是32位的，则内存使用量将是输入大小的4倍。当使用64位标签时，这会变得更麻烦，但是如果您知道一些有关数据的信息，可以减小union-find数据结构的大小。我以前按大小使用union，但由于某些原因，它只会降低性能并增加内存使用量，因此被删除。
有关连接组件算法历史的更多信息，以及2d8连接组件的更快方法，请参阅grana等人关于基于块的决策树的论文。〔5〕
参考文献
欢迎加入QQ群-->： 979659372
