用于构建和求解稀疏分层图的Python包

此包允许使用s-t图割构建和求解图像分割问题，例如马尔可夫随机场 (MRF) 和 稀疏分层图 (SLG)。该包完全用Python编写，并包含用于构建单标签和多标签问题的图的逻辑。为了求解优化问题，它依赖于最小割/最大流算法（见求解器）。

安装

使用pip install slgbuilder安装默认包或克隆仓库。有关更多信息，请参阅依赖项。

这是为什么？

该包主要用于多标签/多目标图像分割问题。常见用途包括

• 表面检测
• 约束多表面检测
• 对象分割
• 交互式多对象分割

CVPR 2020预告片视频

示例

• 示例代码和笔记本
• 实验笔记本（高级2D和3D分割）[CVPR2020]
• 实验笔记本（带有并行QPBO的高级3D分割）[ICCV 2021]

网格图与有序多列图

该软件包支持常见的网格图结构，如Delong和Boykov所使用的结构，以及由Li等人普及的有序多列结构。虽然将图像数据表示为网格结构看似是明显的选择，但如果可能的话，使用有序多列结构进行分割有多个优点（例如，较小的图和“更好”的约束）。然而，这样做需要重新采样数据，这通常需要了解图像中每个对象的位置。

求解器

该软件包目前支持八个不同的求解器。在简单的情况下，默认的BK Maxflow和QPBO求解器应该可以很好地工作。对于亚模块问题，所有求解器都应找到全局最优解。只有QPBO求解器支持非亚模块问题，并且对于此类问题，不能保证找到完整的解决方案。对于大型或时间敏感的任务，可能更喜欢使用非默认求解器，例如HPF或PQPBO。我们目前正在对最小割/最大流算法进行对比研究，这将提供对不同计算机视觉任务上哪种算法表现最好的更深入了解。如果您感兴趣，请查看这个存储库。

BK Maxflow

对于亚模块问题（例如，无排除约束的分割），默认求解器（由MaxflowBuilder使用）是更新版本的Boykov-Kolmogorov最大流算法，通过thinmaxflow软件包访问。MaxflowBuilder与BKBuilder同义。

QPBO

对于非亚模块问题（例如，带有排除约束的分割），由QPBOBuilder使用的求解器是这个版本的QPBO算法，通过thinqpbo软件包访问。

HPF

HPFBuilder是标准MaxflowBuilder的替代方案。它依赖于HPF算法，该算法的性能通常优于BK Maxflow。 HPFBuilder依赖于thinhpf软件包。它支持int32和float32容量/能量，但推荐使用int32。

OR Tools

BK Maxflow求解器的替代方案是Google Maxflow实现，这是一个推标签算法。可以使用ORBuilder类实现。除了性能之外，Google和BK Maxflow算法之间的区别在于，Google实现不支持浮点类型容量。如果MaxflowBuilder在求解时速度慢，请尝试使用ORBuilder。

MBK

通过MBKBuilder可以找到对BK Maxflow算法的略微优化的现代重实现。依赖于shrdr软件包。使用此构建器应与MaxflowBuilder/BKBuilder相比减少内存使用并略微提高性能。

PBK

在shrdr软件包中找到的MBK实现的并行版本。可以在多核系统上显著减少大型问题的求解时间。可以使用类似的PQPBOBuilder的示例Jupyter笔记本可以在该补充材料中找到，该材料来自这篇文章。

MQPBO

使用QPBOBuilder可以找到对QPBO算法的略微优化的现代重实现。依赖于shrdr软件包。使用此构建器应与QPBOBuilder相比略微减少内存使用并提高性能。

PQPBO

在shrdr软件包中发现的并行版本的MQPBO实现。可以在多核系统上显著减少大问题的求解时间。使用示例的Jupyter笔记本可以在本文补充材料中找到，本文链接为此处。

依赖项

为了解决s-t图割优化问题，该软件包依赖于以下软件包之一：

• thinmaxflow（默认安装）- 用于计算s-t图的最小割/最大流的软件包，使用Boyskov-Kolmogorov (BK) 最大流算法。
• thinqpbo（默认安装）- 使用Kolmogorov的二次伪布尔优化（QPBO）算法实现解决子模和非子模优化问题的软件包。基于BK最大流算法的求解器。
• thinhpf- 用于使用Hochbaum伪流（HPF）算法计算s-t图的最小割/最大流的软件包。
• ortools - 用于使用Google OR Tools最小割/最大流实现的软件包计算s-t图的最小割/最大流。
• shrdr - 使用Jensen和Jeppesen优化的串行或并行实现的BK最大流和QPBO算法的软件包，用于计算s-t图的最小割/最大流。

请参阅链接以获取更多详细信息和参考文献。

使用额外依赖项安装

使用HPF求解器安装

pip install slgbuilder[thinhpf]

使用Google OR Tools求解器安装

pip install slgbuilder[ortools]

使用所有额外功能安装

pip install slgbuilder[all]

shrdr软件包目前不在PyPI上提供。请从此处获取！

相关仓库

• shrdr Python软件包（ICCV 2021）
• thinqpbo Python软件包
• thinmaxflow Python软件包
• thinhpf Python软件包
• 最小割/最大流算法的C++实现

贡献

欢迎贡献，只需创建一个问题或一个PR。

许可

MIT许可证（请参阅LICENSE文件）。

参考文献

如果您在学术工作中使用此软件，请考虑引用我们的工作

N. Jeppesen, A. N. Christensen, V. A. Dahl和A. B. Dahl，"用于多对象分割的稀疏层状图"，2020 IEEE/CVF计算机视觉与模式识别会议（CVPR），2020，第12774-12782页，doi: 10.1109/CVPR42600.2020.01279。
[ 论文 ] [ 补充 ] [ CVF ] [ IEEE ]

N. Jeppesen, P. M. Jensen, A. N. Christensen, A. B. Dahl和V. A. Dahl，"使用并行二次伪布尔优化加速多对象分割"，2021 IEEE/CVF国际计算机视觉会议（ICCV），2021，第6240-6249页，doi: 10.1109/ICCV48922.2021.00620。
[ 论文 ] [ 补充 ] [ CVF ] [ IEEE ]

BibTeX

@INPROCEEDINGS{9156301,  author={Jeppesen, Niels and Christensen, Anders N. and Dahl, Vedrana A. and Dahl, Anders B.},  booktitle={2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)},   title={Sparse Layered Graphs for Multi-Object Segmentation},   year={2020},  volume={},  number={},  pages={12774-12782},  doi={10.1109/CVPR42600.2020.01279}}

@INPROCEEDINGS{9710633,  author={Jeppesen, Niels and Jensen, Patrick M. and Christensen, Anders N. and Dahl, Anders B. and Dahl, Vedrana A.},  booktitle={2021 IEEE/CVF International Conference on Computer Vision (ICCV)},   title={Faster Multi-Object Segmentation using Parallel Quadratic Pseudo-Boolean Optimization},   year={2021},  volume={},  number={},  pages={6240-6249},  doi={10.1109/ICCV48922.2021.00620}}