加载中…
个人资料
等待笑容
等待笑容
  • 博客等级:
  • 博客积分:0
  • 博客访问:22,561
  • 关注人气:9
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

图割小结

(2012-04-27 16:00:50)
标签:

图割

graph

cuts

分类: 2012_4
不规范定义 : 
一个数据结构所谓的图中有点,点之间有边,边上有权值.
一个"特殊的图",有两个特殊的点,一为源点,取源头之意,一为汇点,取汇聚之意.
一个"特殊的图"的划分称之为割,割是边的集合.划分出两部分,一含源点,一含汇点,两部分不重合.
一个特殊的割,边的总权值最小,成为最小割,也就是图割的结果.

不恰当例子 : 
围棋棋盘有九个星位,任取一个为源点,一个为汇点.横线或竖线为图的边.
想象边的权值为该线的高度,棋盘如山脉,有的地方高耸入云,有的地方低入谷底.
图割的结果是一条山谷,将山脉分为两部分,一部分包含源点,一部分包含汇点.

例 : 图片分割问题 -> 将图片中前景物体(obj)从背景(bkj)中提取出来.

第一回合
建立图
顶点为图片上每一个像素点.
任意两相邻像素(顶点)之间有边.
因为要分割前景,所以希望前景边缘为谷地,谷地权值小.
假设边缘对比度强烈,所以希望对比越强烈,权值越小.
可以设delta为两顶点像素差,权值为exp(-delta*delta).
此函数范围(0,1],易伸缩,对山峰区域(1附近)敏感(变化率大),谷底区域(0附近)不敏感(变化率小).
在图中手动标定源点,汇点.
建图完毕.
使用图割.
分割完毕.

第一回合评价 : 
与flood fill算法没有本质上的区别,利用相邻像素间像素对比度,划分区域.
假设还知道猫身上颜色的范围,猫在图像上可能出现的区域,无法利用这些信息.   ---(1)

第二回合
源点和汇点不选为图像中的某个像素点
在虚空之中建立源点和汇点.
源点(或汇点)和所有顶点之间有边.这些边的权重是该顶点作为源点(或汇点)的可能性.利用了(1)的信息

第二回合评价 :
可利用的信息多了一些,效果自然好一些.最差也和第一回合相同.

求解图割的算法也就是解最小割的算法 : 
1) Goldberg-Tarjan
2) Ford-Fulkerson
3) 上诉两种方法的改进算法

以上内容来自:
1) Fast Approximate Energy Minimization via Graph Cuts.(如何用图建模,定义,证明,性质)
2) An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision.(改进求解图割的算法,提供算法包)
3) 自己的思考.


0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有