使用maxflow进行图像分割

Question

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

Answer 1

我很清楚地认识到这个来源.那是Boykov-Kolmogorov Graph Cuts库.我建议你先做的是阅读他们的论文.

Graph Cuts是一种交互式图像分割算法.您可以在图像中标记您认为属于对象(即前景)的内容以及不属于该对象(也称为背景)的内容.这就是你首先需要的.执行此操作后,Graph Cuts算法最佳地猜测图像中其他像素的标签.它基本上遍历未标记的每个其他像素,并确定它们是否属于前景和背景.

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

1. Self-Penalty:这是将每个像素分配为前景或背景的成本.这也称为数据成本.
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-links并添加到图表中
6. 调用maxflow图表上的例程来分割图像
7. 浏览每个像素并确定像素是属于前景还是背景.
8. 创建一个反映这一点的二进制映射,然后复制二进制映射为true的图像像素,并且当它为false时不要执行此操作.

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

它还有一个自述文件,因此你可以看到图书馆应该如何工作给定一些示例图像.

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

祝好运!