1

我必须在 C++ 中使用 maxflow 算法进行前景/背景分割。（http://wiki.icub.org/iCub/contrib/dox/html/poeticon_2src_2objSeg_2src_2maxflow-v3_802_2maxflow_8cpp_source.html）。我根据它们的 RBG 从 png 文件中获取像素数组，但下一步是什么。我怎么能用这个算法来解决我的问题？

4

1 回答 1

14

我非常了解那个来源。那是 Boykov-Kolmogorov Graph Cuts 库。我建议您首先阅读他们的论文。

Graph Cuts 是一种交互式图像分割算法。您将图像中的像素标记在您认为属于对象（也称为前景）和不属于对象（也称为背景）的像素上。这就是你首先需要的。完成此操作后，Graph Cuts 算法会最好地猜测图像中其他像素的标签。它基本上会遍历每个未标记的其他像素，并确定它们是否属于前景和背景。

Graph Cuts 背后的整个前提是图像分割类似于能量最小化。图像分割可以表述为具有两项总和的成本函数：

  1. 自罚：这是将每个像素分配为前景或背景的成本。这也称为数据成本。
  2. 相邻惩罚：这强制相邻像素或多或少应该共享相同的分类标签。这也称为平滑成本。

这种公式被称为最大后验马尔可夫随机场分类问题（MAP-MRF）。目标是最小化该成本函数，以便您实现最佳图像分割。这实际上是一个NP-Hard问题，并且实际上是 Clay Math Institute 提供资金的问题之一。

Boykov 和 Kolmogorov 从理论上证明了 MAP-MRF 问题可以转化为图论，解决 MAP-MRF 问题类似于将您的图像形成一个具有源和汇链接以及连接相邻链接的图像素在一起。要求解 MAP-MRF，请执行最大流/最小割算法。有很多方法可以做到这一点，但 Boykov / Kolmogorov 找到了一种比更成熟的算法（如 Push-Relabel、Ford-Fulkenson 等）更快的更有效的方法。

自我惩罚就是所谓的t个链接，而相邻惩罚就是所谓的n 个链接。您应该阅读论文以弄清楚这些是如何计算的，但是t链接描述了分类惩罚。基本上，将每个像素分类为属于前景或背景的成本是多少。这些通常基于图像的负对数概率分布。您所做的是创建被分类为前景的分布的直方图和被分类为背景的直方图。

通常，前景和背景的每个颜色通道的统一量化就足够了。然后您将这些转换为 PDF，但除以每个直方图中的元素总数，然后当您计算每个像素的 t 链接时，您可以访问颜色，然后查看它在直方图中的位置，然后取负对数。这将告诉您将该像素分类为前景或背景的成本。

相邻像素成本更直观。人们通常只取一个像素和相邻像素之间的欧几里得距离，并将这个距离应用于高斯。为简单起见，通常使用 4 像素邻域（北、南、东和西）。

弄清楚如何计算成本后，请遵循以下过程：

  1. 将像素标记为前景或背景。
  2. 使用他们的库创建图形结构
  3. 计算前景和背景像素的直方图
  4. 计算 t-links 并添加到图中
  5. 计算 n 链接并添加到图中
  6. 调用maxflow图上的例程来分割图像
  7. 遍历每个像素并确定该像素是属于前景还是背景。
  8. 创建一个反映这一点的二进制映射，然后复制二进制映射为真的图像像素，当它为假时不要这样做。

的原始来源maxflow可以在这里找到：http: //pub.ist.ac.at/~vnk/software/maxflow-v3.03.src.zip

它还有一个自述文件，因此您可以通过一些示例图像了解该库应该如何工作。

你有很多东西要消化，但 Graph Cuts 是目前最强大的交互式分割工具之一。

祝你好运！

于 2014-06-06T02:19:42.657 回答