Graph Cuts初步理解
一些知识点的初步理解_8(Graph Cuts,ing...)
Graph cuts是一种十分有用和流行的能量优化算法,在计算机视觉领域普遍应用于前背景分割(Image segmentation)、立体视觉(stereo vision)、抠图(Image matting)等。Graph Cuts理论最早是出现在流网络优化领域的,比如说水管网络,通信传输网络,城市车流网络等。此时的Graph Cuts算法是用来确定网络流的最小分割,即寻找一个容量最小的边的集合,去掉这个集合中的所有边就可以阻挡这个网络了。需要注意的是,通常所说的Graph Cuts算法是指的采用最大流-最小分割来优化的模型,其它的Graph Cutting算法一般用graph partitioning这个名词来代替。
首先还得先理解Graph Cuts中的Graph和Cuts的意思。此处的Graph和普通的Graph稍有不同。普通的图由顶点和边构成,如果边的有方向的,这样的图被则称为有向图,否则为无向图,且边是有权值的,不同的边可以有不同的权值,分别代表不同的物理意义。而Graph Cuts图是在普通图的基础上多了2个顶点,这2个顶点分别用符号”S”和”T”表示,统称为终端顶点。其它所有的顶点都必须和这2个顶点相连形成边集合中的一部分。所有Graph Cuts中的边也分为两种,一种是普通顶点与相邻点或者与之有关联的点之间的连线,一种是刚讲的普通顶点和2个终端顶点之间的连线。 Graph Cuts中的Cuts是指这样一个边的集合,很显然这些边集合包括了上面2种边,该集合中边的断开会导致残留”S”和”T”图的分开,且这些边的集合中所有权值之和是最小的。因此也称为最小割。关于Graph Cuts的示意图如下所示:
图割在图像分割中应用得很广,那么应该怎样将图割理论和计算机视觉联系起来呢?图割模型和图像该怎么建立联系呢?有一位网友在他的博文图割小结做了个小结,比喻得还不错,可以让大家图割在图像分割中的作用有个初步的印象。
在参考了iccv2001的文章Interactive graph cuts for optimal boundary & region segmentation of objects in ND images后,或许能够找到上述问题的一点答案。首先,一张image可以看作是一个矩阵,图中的每个像素就是矩阵中的一个位置,这个像素可以看做是图中的一个顶点。然后我们把相邻顶点之间用短线(有向或无向都行)连接起来,这就形成了边,现在这幅image有顶点和边了,也就构成一幅Graph了。至于边的权值怎么计算,则是很理论的东西。看了下论文中的解释,图像中边的权值一般由2部分构成,平滑项和数据项,这2部分的比重用1个系数来平衡,其中平滑项主要体现顶点像素和其相邻区域像素之间值的变化强度,如果变化剧烈说明这两者很有可能出于边缘部分,则被分割开的可能性比较大,而按照最小割的分割原理,这时2者的平滑项权值应该较小。而数据项部分则表示对应顶点属于前景或者背景的惩罚项。其论文中的数学公式为:
其中R(A)表示的是区域数据项,B(A)表示的是边界平滑项,E(A)表示的是权值,即损失函数,也叫能量函数,图割的目标就是优化能量函数使其值达到最小。
另外由于Graph Cuts需要有2个终端节点”S”和”T”,分别表示初始的目标区域和背景区域,在计算机视觉的图像分割领域时,需要人工指定初始的s顶点和t顶点,如果有HCI的话,可以用鼠标分别直接点这2个区域。其中一个区域代表所需分割目标上的一个像素位置,另一个为背景上的一个像素位置。有了能量函数的定义和初始的终端顶点,就可以采用图割理论来不断迭代对目标进行分割了。
最新文章
- 「标准」的 JS风格
- ubuntu下面更改用户名的方法
- 《C#高级编程》读书笔记
- spark streaming 与 kafka 结合使用的一些概念理解
- Android开发之补间动画、XML方式定义补间动画
- 百度语音识别(Baidu Voice) Android studio版本
- ZeroMQ(java)之I/O线程的实现与组件间的通信
- HDU4135 Co-prime(容斥原理)
- Ruby跳出多层循环 catch...throw
- java接口与抽象类的区别
- javascript动态创建对象
- c#Ulong用一个高位Uint和低位Uint表示
- MVC+UnitOfWork+Repository+EF
- 设置div,td失去焦点
- HTML学习(八)列表和块
- Zab: A simple totally ordered broadcast protocol(译)
- [Git] git log命令
- CSS小技巧使用
- qsort()函数详解
- Javascript 组合继承 原型链继承 寄生继承
热门文章
- PHP变量入门教程(1)基础
- http_build_query 的一个问题
- PHP上传(单个)文件示例
- /etc/rc.d/rc与/etc/rc.d/init.d的关系
- ubuntu16.04下安装cuda8.0
- NVelocity介绍,NVelocity中文手册文档及实例下载
- python的一道面试题 __call__ 的使用.
- iOS开发UI篇—核心动画(转场动画和组动画)
- 使用 PowerDesigner 和 PDMReader 逆向生成 MySQL 数据字典
- python之常用内置函数