从图割到图像分割 - 最大流算法

2024-04-12 22:32

本文主要是介绍从图割到图像分割 - 最大流算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


从图割到图像分割(一)——最大流算法

《算法导论》对最大流的介绍是:最大流问题是关于流网络的最简单的问题,它提出这样的问题:在不违背容量限制的条件下,把物质从源点传输到汇点的最大速率是多少?

更多关于网络流的介绍请看网络流wiki

我最初接触最大流问题是在2011年,那时候我大四,刚保研完,去问导师我需要看哪些方面的书,老板说去把《算法导论》图论相关,以及把最大流最小割算法仔细看一遍。

图论算法在众多算法中算是比较复杂的了,首先读入数据需要构建邻接矩阵,然后再进行求解,求解过程显得并不是很直观。当时我对最大流最小割算法本身就不是很明了,更不明白如何可以应用到图像分割中,现在终于有些体会。


最大流算法

从算法导论书中,最大流算法分为两种:

  1. Ford-Fulkerson方法:书上对该“方法”进行了解释,之所以称作“方法”而不是“算法”,是因为Ford-Fulkerson方法是一种思想,而对这思想的实现,有不同的优化方法

以Ford-Fulkerson方法为思想的最快算法为:

Dinic算法时间复杂度为: O(n2m) ,其中n为顶点数,m为边数

  1. 压入重标记方法(push-relabel):这同样也是一种思想,具体实现也有不同的优化实现方法。

基于压入重标记方法(push-relabel)方法的最快的方法有两种:

H_PRF时间复杂度为(最坏) O(n2m)

Q_PRF时间复杂度为(最坏) O(n3)


最大流=>最小割

决定最大流算法能够应用在图像分割的原因,就在于这条定理了

割的定义:

流网络 G=(V,E) (S,T) V 划分为 S T=VS 两部分,使得 sS,tT 。如果 f 是一个流,则穿过割 (S,T) 的净流被定义为 f(S,T) ,割 (S,T) 的容量为 c(S,T) 。一个网络的最小割也就是网络中所有割中具有最小容量的割。

最大流最小割定理
如果 f 是具有源点 s 和汇点 t 的流网络 G=(V,E) 中的一个流,则下列条件是等价的:

  • f G 的一个最大流
  • 残留网络$Gf$不包含增广路径
  • 对于 G 的某个割 (S,T) ,有 f=c(S,T)

其中第三条,说明最大流的值实际上等于某一最小割的容量,即可以用最大流来求取最小割:
$$|f|=f(S,T)=\sum{u\in{S}}\sum{v\in{T}}f(u,v)\leq\sum{u\in{S}}\sum{v\in{T}}c(u,v)$$


为何可以用最小割算法来分割图像?

这个问题我刚接触图割的时候,就想了很久,刚开始我在直观上比较难理解

首先,要理解,最大流算法得到的最小割有什么意义?如果写过最大流算法,或者看明白最大流算法的都知道,在一个增广路径中,限制流容量增加的,就是其中具有最小流量的路径,如果将流从 S T 推送,最终将形成由“最小容量”的一个割,这个割就是最小割,由这些“最小容量”的容量加起来即为最大流(实际上称作最大净流好些)

其次,图像是可以看作由一个个像素组成的巨大图,假设我将像素一一用边连接起来,则这些像素点会成为这个巨大图网络的顶点,如果能利用最大流算法,求取其最小割,通过最小割分开的顶点就是边权值相对较小的点,假设我边的权值与顶点间的相似度成正比,那么最小割分开的顶点就是相似度最小的点,即,通过最大流算法,我们将图像分成了一块块相似的像素区,这不就是图像分割吗?

最后,那么从源点能流出多少流呢?从汇点又能接收多少流呢?如果都是无穷大,那还会形成分割吗?显然这是需要限制的。如果从像素点中选出两个点,一个作为源点,一个作为汇点,图像中其它点与源点的相似度作为流入的流量,与汇点的相似度作为流出的流量,则应用最大流算法得到的结果,即将点分为两部分,一部分属于“相似于”源点,一部分“相似于”汇点,而又由于像素点两两相连,为保证像素间的光滑性,会产生相对光滑的分界。

实际中,像素点连接源点或汇点的边叫做T-Link、像素点相互连接的边叫做N-Link、T-link的构造当然要比上述我说的要复杂,而N-Link也不要求要两两相连,T-Link约束了像素点与给顶点的相似性,而N-Link约束了像素点之间的光滑性。

在Paper中,对构图的描述方式不一样,一般描述为目标函数为一个能量函数,而这个能量函数的优化,可以转化为一个最小割方法来求解。


Min-Cut/Max-Flow

讲到最大流最小割算法,不得不提到大名鼎鼎的Boykov和Kolmogorov,这两位牛人在2004年图像领域最顶级杂志TPAMI的一篇文章:An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision,讲述了如何将图像分割转化为一个能量函数优化问题,并且如何用最大流最小割算法对其进行优化,此外,他们提供了开源的代码库,提供了非常友好的接口给相关研究者调用,从而使得基于图割的图像分割思想广泛应用,其中包括后来大名鼎鼎的Lazy Snapping和Grab Cut。像Photoshop,美图秀秀等基于交互式分割得到目标的功能基本源于图割方法。

图割方法在之前的图像分割领域并非没有用过,之所以后来应用广泛,我认为很大一部分原因得益于开源代码库:实现一个最大流算法并非特别难的事,但如何高效实现,以及由于图像像素点很多,如何有效管理实现过程中的内存分配,及如何提供一个简单易用的接口,恐怕是绝大部分之前的人研究遇到的难点。

Boykov和Kolmogorov在文章中提出的maxflow算法是一种增广路径算法,其方法的时间复杂度为 O(n2m|C|) 。从理论上讲,其时间复杂度大于以上三种,但实际的表现效果,优于以上所有(我猜应该是与图像所构成的图的特殊结构有关)。

算法可分为三个步骤:

  • “growth” stage: search trees S and T grow until they touch giving an s → t path
  • “augmentation” stage: the found path is augmented, search tree(s) break into forest(s)
  • “adoption” stage: trees S and T are restored.

伪代码

      
1
2
3
4
5
6
7
      
initialize: S = {s}, T = {t}, A = {s, t}, O = ∅
while true
grow S or T to find an augmenting path P from s to t
if P = ∅ terminate
augment on P
adopt orphans
end while

步骤分为三步,基本与增广路径算法一致,其从S和T分别开始搜索,实际就是双向广搜,分别维持着一个属于S的队列和一个属于T的队列,当S的队列找到下一个节点,并发现下一个节点属于T的队列时,进行增广,并记录瓶颈流(bottleneck flow)所在位置,由于这些瓶颈流在增广后被移除,变为0后,需要重新看还有否必要将这些节点放入到队列中,这一步叫做adoption。名字还挺不错:)

具体可见代码实现,由于其给出的库是由Template方式编写,而且用了一些自己定义数据结构,所以代码不易看懂,需要耐心体会。


这篇关于从图割到图像分割 - 最大流算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/898410

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

使用Python开发一个图像标注与OCR识别工具

《使用Python开发一个图像标注与OCR识别工具》:本文主要介绍一个使用Python开发的工具,允许用户在图像上进行矩形标注,使用OCR对标注区域进行文本识别,并将结果保存为Excel文件,感兴... 目录项目简介1. 图像加载与显示2. 矩形标注3. OCR识别4. 标注的保存与加载5. 裁剪与重置图像

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

使用Python实现批量分割PDF文件

《使用Python实现批量分割PDF文件》这篇文章主要为大家详细介绍了如何使用Python进行批量分割PDF文件功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、架构设计二、代码实现三、批量分割PDF文件四、总结本文将介绍如何使用python进js行批量分割PDF文件的方法

基于WinForm+Halcon实现图像缩放与交互功能

《基于WinForm+Halcon实现图像缩放与交互功能》本文主要讲述在WinForm中结合Halcon实现图像缩放、平移及实时显示灰度值等交互功能,包括初始化窗口的不同方式,以及通过特定事件添加相应... 目录前言初始化窗口添加图像缩放功能添加图像平移功能添加实时显示灰度值功能示例代码总结最后前言本文将

使用Python将长图片分割为若干张小图片

《使用Python将长图片分割为若干张小图片》这篇文章主要为大家详细介绍了如何使用Python将长图片分割为若干张小图片,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果1. Python需求