软件X 10（2019）100335原始软件出版物Higra：层次图分析B. Perreta， G. Chierchiaa，J. Coustya，S.J. F. Guimaresesb，a，Y.肯莫奇湖纳杰曼aaUniversité Paris-Est，MaterialatoirebPUC Minas - ICEI - DCC - VIPLAB，巴西ar t i cl e i nf o文章历史记录：接收19七月2019收到修订版2019年9月10日接受2019年9月26日保留字：图层次聚类构件树a b st ra ctHigra - Hierarchical Graph Analysis是一个用于高效稀疏图分析的C++/Python库，特别关注能够处理大量数据的分层方法。在Higra中解决的层次图分析的主要方面是层次表示的构建（聚集聚类、数学形态学层次等），分析和处理这些表示（过滤、聚类、表征等），和他们的评价。Higra的目标受众很广，从学生和想要一个可访问的图书馆进行快速实验的从业者，到开发图形数据分层分析新方法的研究人员。Higra是图形分析的通用工具箱，可用于机器学习、数据科学、模式分析和计算机视觉等各种应用领域此外，它包含一个图像分析模块，通过提供专用于该领域的高效算法来简化像素网格图的处理©2019作者由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据版本0.4.1用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX_2019_243Code Ocean compute capsule NA法律代码许可证Cecill-B使用git的代码版本控制系统使用C++、Python的软件代码语言、工具和服务编译要求、操作环境依赖性C++ 14编译器、Python、Numpy如果可用开发人员文档/手册链接https://higra.readthedocs.io支持电子邮件，用于问题benquiry. esiee.fr1. 动机和意义图形在机器学习、数据科学、模式分析和计算机视觉中越来越受欢迎，因为它们为结构化或网络数据提供了自然的表示。在图分析方法中，分层方法试图以一致的方式捕获各种尺度下的图的结构，方法是将图顶点顺序地合并到越来越大的聚类中，直到保留单个聚类。这样的方法已经被证明在数据可以被建模为图的各种各样的应用领域中是有用的，例如图像分析、群落检测、网格分析、生物遗传树构建等。*通讯作者。电子邮件地址：benjam.perret@ esiee.fr（B. Perret）。https://doi.org/10.1016/j.softx.2019.100335Higra-Hierarchical Graph Analysis是一个C++/Python库，用于高效的稀疏图分析，特别关注分层方法。它旨在为能够处理大量数据（目前高达数百万个顶点）的层次图分析提供标准和最先进的算法在传统的台式计算机上）。它可以处理层次聚类和组件树，其中层次结构的每个级别表示空间的部分聚类。此外，Higra的设计使用户能够轻松地在层次聚类的双重表示之间切换Higra是一个用于分层图表示构建、处理和评估的通用工具箱：因此，它并不专注于特定的应用或领域，其基本功能可以用于各种情况。2352-7110/©2019作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx2B. 佩雷湾Chierchia，J.Cousty等人粤公网安备44010802000019号Higra提供了一个Python API来简化其使用，并从Python生态系统中大量可用的科学库所创造的协同效应中这个API被认为是学生和专家研究人员愿意快速开发新的应用程序，实验新的方法，或开发概念的证明可用。分层表示上的矢量化操作使Python能够有效地编写各种算法。它还被认为可以与经典的Python数据分 析 管 道 （ 如 Scikit-Learn ） 和 现 代 优 化 框 架 （ 如 PyTorch 和TensorFlow）无缝集成。Python接口由C++模块备份，其中实现了核心算法以确保高性能。C++模块也可用作独立库，因为它对Python运行时没有任何依赖性。图形是数据的常见表示形式，存在许多用于分析它们的文档。关于使用Python接口进行图形处理的通用工具箱，主要的公开可用的工具箱是graph-tool[1]，NetworkX[2]和igraph[3]。虽然他们提出了许多用于图分析的算法，但它们很少或根本不支持层次分析。在主要的Python数据分析库中，Scipy[4]有一个专门用于分层聚类的模块相反，Scikit-Learn[5]有一个专门用于凝聚聚类的模块，可以处理稀疏图。虽然它可以使用经典的凝聚聚类算法从稀疏图中创建平面聚类（也称为分区）库mlpack[6]，是一个与Python绑定的C++机器学习库，还提供了一些分层的点分类方法它还拥有许多算法，使用度量空间的分层分层聚类方法在图像分析中也很流行，有几个库实现了专用于应用领域的算法，有时还提出了Python绑定，如Pink[7]，Olena[8]，Vigra[9]或更专业的iamxt[10]。据我们所知，Higra因此是第一个C++/Python库，提供了大量致力于分层图分析的算法，而不是针对特定的应用程序。本文的组织结构如下。第2节介绍了图书馆建筑的主要方面，并概述了其主要功能。第3节提供了两个说明性的例子库的图形简化和图像过滤。一些标准的凝聚层次聚类算法的计算性能第4节分析了拟议图书馆的预期影响。第五节是文章的结尾。2. 软件描述在本节中，我们将描述库的结构和实现的主要功能2.1. 软件构架Higra由一个核心的、仅头部的、C++ 14模块组成，其中实现了性能关键的数据结构和算法，以及一个Python模块，该模块公开了C++模块API并提出了更高级别的功能。在Higra中，通过它们的分层表示来分析图。图的分层表示对应于树，其中每个节点是输入图的聚类，也称为区域库的两个主要数据结构是因此，图类实现为邻接列表，树类实现为父数组[11]。这些类与它们的关联数据、图的顶点和边权重以及树的节点权重低耦合。这些数据使用C++中的xtensor库[12]和Python中的Numpy[13]数组由多维数组表示，因此可以使用标准数组编程轻松有效地操作它们。这种分离是通过强制图的所有元素（顶点和边）和所有树的元素（节点）由范围从0到元素数减1的整数索引来标识。此外，为了便于图和其作为树的层次表示之间的数据交换，我们还强制要求树叶的索引正好是图的顶点的索引。换句话说，表示图上的顶点特征的数组可以用作表示树上的叶节点特征的数组。核心C++模块的所有依赖项都是Header Only C++库，从而确保该库可以在各种系统上轻松编译和扩展。C++函数和数据结构通过Pybind 11映射到Python类型[14]。请注意，xtensor数组无缝映射到Numpy数组。该库经过仔细测试，超过98%（分别为。90%）的C++代码行（分别为Python）模块。持续集成用于避免主要系统（Linux，Mac和Windows）上的回归问题2.2. 软件功能Higra包含了大量的经典和最近的算法，用于构建，操作和分析分层图表示：有效的方法和数据结构来处理层次聚类的双重表示：树[15]（密度图）和显着图[16]（超度量距离）;层次聚类：准平坦区层次结构[17]，层次分水岭[18，19]，凝聚聚类[20]（单链接[11，21]，平均链接，完全链接，指数链接[22]，Ward或用户提供的链接规则），约束连接层次结构[23];组件树：最小和最大树[24，25];操作和探索层次结构：简化[26，27]，聚类，聚类提取，各种属性[28]（大小，体积，动力学，周长，紧凑性，矩等），水平和非水平切割，对线拱[29];层次优化：最优切割，能量层次[30，31];图上的算法：顶点，顶点和簇的不相似性，区域邻接图，最小生成树和森林，流域削减[32];评估：图形聚类和层次聚类的监督评估[33，34];图像工具箱：网格图的特殊方法，形状树[35]，专用于图像分析的分层聚类方法[36]，Mumford-Shah能量优化3. 说明性实例本节介绍了Higra使用和性能的说明性示例第一个例子演示了如何使用高度简化来提高聚类性能。第二个例子展示了如何使用Higra来执行图像过滤。最后，最后一个例子比较了········B. 佩雷湾Chierchia，J.Cousty等人粤公网安备44010802000019号3[客户端]=Higra凝聚聚类算法与Scikit-Learn等价。这些插图可以通过下载Python notebook复制。13.1. 层次聚类简化图1演示了一个单一的连锁结构的聚类和它的简化集群大小crite- rion [26]。一个经典的问题与单链接聚类是非常小的集群分支非常高的层次结构中的存在。这样的集群是不相关的，可以被发送回层次结构的最底层。在这个例子中，第7行中的层次结构是从由3个聚类组成的图中我们可以看到，在Higra中，层次结构实际上是一个由2个元素组成的元组：一棵树和一个数组，该数组将树的每个节点与海拔高度相关联（在文献中也称为树距离）。从第10行上的层次结构中提取到三个类的平坦聚类。层次结构在第15行被简化：所有大小小于7个元素的集群都被删除。最后，在线16上计算简化层次的树状图，在线19上提取新的3类聚类。我们可以看到，简化的层次结构不再包含任何小的聚类，相应的扁平聚类为3类大大提高。3.2. 基于分水岭层次的图中的例子。2演示了使用分层聚类进行图像滤波[38]。这里遵循的策略是首先通过表示为边缘加权图的图像梯度的区域[18，19分水岭分割的基本思想[39]是将边加权图视为地形表面，并将该地形表面的每个集水盆地与聚类相关联。直观地说，然后通过顺序过滤具有增加大小的区域闭合的图的边缘权重[40]，然后计算这些过滤的边缘权重的分水岭分割然后，从层次表示中提取出一个包含k个聚类的扁平聚类最后，在滤波图像中，包含在聚类中的每个像素的颜色被替换为原始图像中聚类内像素的由梯度构造了一个4-邻接边加权图第5行和第6行的图像然后，在第9行上构造图的区域的分水岭层次为了说明的目的，在第10行上计算了高分辨率的显着图，该显着图通过图的端点之间的超度量距离对图的每个边缘进行加权，并在第12行上绘制在2D Khalimsky网格[41，42]中这种表示，有时称为超度量轮廓图[43]，能够将在4-邻接图上构建的层次聚类可视化为轮廓图像，其中轮廓的强度然后，在线16上计算分层结构的每 个 区 域 内 的 平 均 图 像 颜 色 。 在 第 19 行 实 例 化 的 类HorizontalCutExplorer的对象简化了给定层次结构的水平切割（平面集群）它用于提取包含不同数量的区域的若干切割（线19），并且使用它们的区域的平均图像颜色来重建与这些切割对应的图像（线20）。1https://higra.readthedocs.io/en/latest/notebooks.html。3.3. 与Scikit-Learn的图中比较了Higra和Scikit-Learn的凝聚层次聚类算法的性能。3 .第三章。 我们使用k-最近的方法邻居算法（k10）在0， 12中均匀采样点上。对于每个生成的图，我们运行单个，完整，平 均 ， 和 来 自 Higra 的 Ward 链 接 凝 聚 聚 类 算 法 （ 函 数binary_partition_tree_X_linkage，其中X被链接规则的名称替换）和Scikit-Learn（函数linkage_tree用于单个，完整和平均链接规则，ward_tree用于Ward链接）7次，并且我们计算每个图大小的平均值和标准差运行时间。 我们可以看到，Higra总是比Scikit- learn快4到10倍，并且随着图形大小的增加，差距似乎会增加。4. 影响据我们所知，Higra是第一个在一个地方收集如此多的分层图分析算法的库。因此，提供经典和最先进算法的参考实现将通过促进这些方法在社区中的传播、简化可重复的研究以及帮助创建方法之间的相关比较来提供巨大的好处。由于Higra工作在通用图上，并且不承担特定的应用程序，因此它可以用于各种各样的领域。虽然它的使用需要一些关于分层表示的知识，但它提供了一个易于使用的Python接口，该接口有大量文档。这可以进一步帮助在科学界推广使用拟议的方法，并作为教师的教学工具虽然一些算法仍然必须用C++编写以确保高性能，但我们发现，库中提供的一组基本运算符与层次结构上许多操作的向量化结合使用，确实能够以Numpy风格直接在Python中有效地编写许多作用于层次结构的算法。这使得与经典C/C++编程相比，大大简化和加快了新方法的开发Higra是一个新的图书馆，因此，仍然有一个有限的基础贡献者和用户。它的一些核心功能已经在我们的研究小组使用了很长时间，并导致了几十个出版物[11，16，19，32，34，44我们计划将我们未来所有关于分层图表示的研究工作纳入图书馆，我们希望Higra将从社区的大量采用中受益，从而吸引外部用户和贡献者。5. 结论我们介绍了Higra，一个用于层次稀疏图分析的库，其中包含该领域的许多标准和最先进的Higra由一个核心C++模块和一个用户友好的Python界面组成。Higra的预编译二进制文件可用于Linux，Mac和Windows 64位系统的Python包索引- Pypi，并可以使用简单的命令安装：pipinstall higra。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作4B. 佩雷湾Chierchia，J.Cousty等人粤公网安备44010802000019号Fig. 1. 层次聚类简化。从左到右：具有真实顶点标签的输入图、单链接层次的树状图、由单链接层次中的3个聚类组成的水平切割、简化的单链接层次的树状图以及由简化的单一链接层次结构中的3个集群图二. 使用分水岭层次结构进行图像简化。从左到右：原始图像、梯度、按梯度面积的分水岭层次的显著性图、从分别具有25、50和100个区域的层次重建的简化图像B. 佩雷湾Chierchia，J.Cousty等人粤公网安备44010802000019号5图3.第三章。 Higra和Scikit-Learn在单个、完全、平均和Ward链接凝聚聚类上的性能比较。确认作者感谢CNPq（Universal 421521/2016- 3和PQ 307062/2016-3）、FAPEMIG（PPM-00006-16和PPM-00006-18）和PUC Minas为这项工作提供财政支持。本研究部分由 Coordenação de Aper- feiçoamento de Pessoal de NívelSuperior-Brasil （ CAPES ） -Fi-nanceCode001 和CAPES/COFECUB 88887.191730/2018资助。00. 我们还感谢欧盟的地平线2020研究和创新计划根据玛丽·斯科洛多夫斯卡-居里赠款协议第721463号向SUNDIAL ITN网络提供的财政支持引用[1]图形工具。https://graph-tool.skewed.de/网站。[在线; 2019年6月27日访问]。[2] NetworkX. https://networkx.github.io/网站。[在线; 2019年6月27日访问]。[3]igraph。 https://igraph.org/网站。 [在线; 2019年6月27日访问]。[4]Jones E，Oliphant T，Peterson P，et al. SciPy：Open source scientific tools对于Python。http://www.scipy.org/网站。[在线; 2019年6月27日访问[5] Scikit-Learn https://scikit-learn.org/网站。[在线; 2019年6月27日访问]。[6]李文辉，李文辉. mlpack 3：快速、灵活的机器学习库。J Open Source Softw2018;3：726. http://dx.doi.org/10.21105/joss.00726，URL https://doi.org/10。21105/joss.00726。[7]粉红色花. https://perso.esiee.fr/coupriem/Pink/doc/html/网站。[在线; 2019年6月[8]奥莱娜https://www.lrde.epita.fr/wiki/Olena网站。[在线; 2019年6月27日访问]。[9]维格拉https://github.com/ukoethe/vigra网站。[在线; 2019年6月27日访问]。[10] Souza R，Rittner L，Machado R，Lotufo R.iamxt：用于图像处理和分析的Max-tree工具箱SoftwareX2017;6：81-4.http://dx.doi.org/10.1016/j.softx.2017.03.001.[11]放大图片Najman L，Cousty J，Perret B.玩Kruskal：边加权图中形态树的算法。In：Hendriks CLL，Borgefors G，Strand R，editors.数学形态学及其在信号与图像处理中的应用。计算机科学讲义，第7883卷，柏林，海德堡：施普林格; 2013年，第135-46页。http://dx.doi.org/10.1007/978-3-642-38294-9_12。[12] 扩展器。https://github.com/QuantStack/xtensor网站。[在线; 2019年6月27日访问[13]奥 列 芬 特 NumPy ： NumPy 指 南 。 美 国 ： Trelgol Publishing; 2006 年 ，URLhttp://www.numpy.org/。[在线; 2019年6月27日访问[14]Pybind 11. https://github.com/pybind/pybind11网站。[在线; 2019年6月27日访问]。[15]Carlsson G，Mémoli F.系统 聚类方法 的特征 、稳定 性和收敛 性。J MachLearn Res2010;11：1425-70.[16]Cousty J，Najman L，Kenmochi Y，Guimarces S.图层次分割：准平坦区，最小生成树和显着图。J Math Imaging Vision2018;60（4）：479-502.[17]Meyer F，Maragos P. Morphological scale-space representation withleveling.In：Nielsen M，Johansen P，Olsen OF，Weickert J，editors.计算机视觉中的尺度空间理论。Berlin，Heidelberg：Springer; 1999，p.187比98[18]迈耶F.最小值和轮廓的动力学。In：Maragos P，Schafer RW，Butt MA，editors.数学形态学及其在图像和信号处理中的应用。US，Boston，MA：Springer; 1996，p.329比36 网址：//dx.doi.org/10.1007/978-1-4613-0469-2_38网站。[19]作者：J.层次最小生成森林的增量算法和分水岭割集的显著性。In：Soille P，Pesaresi M，Ouzounis GK，editors.数学形态学及其在图像和信号处理中的应用。Berlin，Heidelberg：Springer; 2011，p.272比83[20]Murtagh F ， Contreras P. 层 次 聚 类 算 法 ： 概 述 。 Data Min KnowlDiscov2012;2（1）：86-97.[21]高尔JC，罗斯GJS。最小生成树与单连锁聚类分析。J R Stat Soc C 1969;18（1）：54[22]杨 文 ， 李 文 ， 李 文 . 指 数 链 接 的 监 督 层 次 聚 类 。 In ： Chaudhuri K ，Salakhutdinov R，editors. 第36届机器学习国际会议论文集。Proceedings ofmachine learning research，vol.97，Long Beach，California，USA：PMLR;2019，p. 6973-83[23]Soille P.用于分层图像分割和简化的约束连接。IEEE TransPattern Anal MachIntell 2008;30（7）：1132-45. http://dx.doi.org/10.1109/TPAMI.2007.70817网站。[24]放大图片作者：J. 用于图像和序列处理的反扩展连接操作IEEE TransImageProcess 1998;7（4）：555-70. http://dx.doi.org/10.1109/83.663500网站。[25] 琼 斯 河 使 用 组 件 树 的 连 接 过 滤 和 分 割 。 Comput Vis Image Underst1999;75（3）：215-28. http://dx.doi.org/10.1006/cviu.1999.0777.[26]张文辉，张文辉.层次聚类和分割中的非显著区域去除。 2019年，第 1-7，提交出版。[27]1999年，Albertos IB，da Fonseca GB，Najman L，Kenmochi Y，Perret B，Cousty J等人，《探索层次简化用于非显著区域去除》。In：32th SIBGRAPIconference on graphics ， patterns and images ， Rio de Janeiro ， Brazil ，October，2019; 2019.第1-7页。（接受出版）。6B. 佩雷湾Chierchia，J.Cousty等人粤公网安备44010802000019号[28]张丹，陆刚.形状表示和描述技术的回顾。模式识别2004;37（1）：1-19.[29]Pont-Tuset J，Arbeláez P，Barron JT，Marques F，Malik J.用于图像分割和对 象 建 议 生 成 的 多 尺 度 组 合 分 组 。 IEEE Trans Pattern Anal Mach Intell2017;39（1）：128-40. http://dx.doi.org/10.1109/TPAMI.2016.2537320。[30]Guigues L，Cocquerez JP，Le Men H.尺度集图像分析。Int J Comput Vis2006;68（3）：289-317. http://dx.doi.org/10.1007/s11263-005-6299-0网站。[31]Kiran BR ， Serra J. 通 过 分 层 切 割 和 攀 登 能 量 的 全 局 局 部 优 化 。 PatternRecognit2014;47 （ 1 ） ： 12-24.http://dx.doi.org/10 的 网 站 。1016/j.patcog.2013.05.012。[32]杨文辉，李文辉，李文辉.分水岭切割：最小跨度森林和水滴原则。IEEE TransPattern AnalMach Intell2009;31（8）：1362-74.[33]Heller KA，Ghahramani Z.贝叶斯层次聚类。第22届机器学习国际会议论文集。ICML http://dx.doi.org/10.1145/1102351.1102389网站。[34]Perret B，Cousty J，Guimarces SJ，Maia DS.评价分级流域。IEEE TransImageProcess2018;27 （ 4 ） ： 1676-88.http://dx.doi 的 网 站 。org/10.1109/TIP.2017.2779604。[35]Géraud T，Carlinet E，Crozet S，Najman L.一种计算nD图像形状树的准线性算法。In：Hendriks CLL，Borgefors G，Strand R，editors.数学形态学及其在信号与图像处理中的应用。Berlin，Heidelberg：Springer; 2013，p.98比110[36]Maninis K，Pont-Tuset J，Arbeláez P，Gool LV.卷积边界：从图像分割到高级任务。IEEE TransPattern Anal Mach Intell2018;40（4）：819-33.[37] Mumford D，Shah J.分段光滑函数的最佳逼近和相关的变分问题。CommPureApplMath1989;42（5）：577-685.http://dx.doi.org/10.1002/cpa.3160420503网站。[38]作者：J.二叉划分树作为一种有效的图像表示方法，在图像处理、分割和信息检索中有着广泛的应用. IEEETransImage Process2000;9（4）：561-76.[39]伯谢S，MeyerF.的形态方法到分割：分水岭变换。数学形态学图像处理1993;34：433-81.[40]文森特湖灰度图像的形态区域打开和关闭。In：O Y-L，Toet A，Foster D，Heijmans HJAM，Meer P，editors.图片中的形状。Berlin，Heidelberg：Springer; 1994，p.197-208.[41]Kovalevsky VA. 有 限 拓 扑 应 用 于 图 像 分 析 。 Comput VisGraph ImageProcess1989;46（2）：141-61.[42]Khalimsky E，Kopperman R，Meyer PR.有限序集上的计算机图形学和连通拓扑。拓扑应用1990;36（1）：1-17.[43]张文，张文，等.图像分割与轮廓检测.北京：科学出版社，2000，24（1）：100 - 101. IEEE Trans Pattern Anal Mach Intell 2011;33 （ 5 ） ： 898-916.http://dx.doi.org/10.1109/TPAMI.2010.161网站。[44] Perret B，Collet C.具有多变量属性的连接图像处理Comput Vis ImageUnderst 2015;133 ： 1-14. http://dx.doi.org/10.1016/j.cviu.2014.09.008 网站。[45][10]杨文，李文.流域等级组合的评价。In：Angulo J，Velasco-Forero S，Meyer F，editors.数学形态学及其在信号和图像处理中的应用：第13届国际研讨会，ISMM 2017，法国枫丹白露，2017年5月15日至17日，会议记录。SpringerInternationalPublishing;2017，p.133-45.http://dx.doi.org/10.1007/978-3-319-57240-6_11。[46]Maia Santana D，Cousty J，Najman L，Perret B.认识分层次的流域。In：Couprie M，Cousty J，Kenmochi Y，Mustafa N，editors. 计算机图像的离散几何。Cham：Springer InternationalPublishing; 2019，p. 300比13[47]Santana Maia D ，Cousty J，Najman L， Perret B.分水岭等级制度。In：Burgeth B，Kleefeld A，Naegel B，Passat N，Perret B，editors.数学形态学及其在信号与图像处理中的应用。Cham：SpringerInternational Publishing;2019，p. 124比36[48][10]杨文，李文，李文.三维反射共聚焦显微镜成像中表征真皮-表皮连接的自对偶模式光谱。In：Burgeth B，Kleefeld A，Naegel B，Passat N，Perret B，editors. 数 学 形 态 学 及 其 在 信 号 与 图 像 处 理 中 的 应 用 。 Cham ： SpringerInternational Publishing; 2019，p. 508-19[49]Chierchia G，Perret B.梯度下降超度量拟合。在：神经信息处理系统的进展，第32卷。NeurIPS，2019，出版中。arXiv：1905.10566。
我的内容管理
展开
