图像分割之Graph cut算法.ppt

图像分割之 Graph Cut算法 Introduction算法简介 Graph cuts是一种十分有用和流行的能量优化算法,在计算机枧觉 领域普遍应用于前背景分割( Image segmentation)、立体视觉 (stereo )、抠图( Image matting)等。 Graph Cut算法仅需要在前景和背景处各画几笔作为输入,箅法将 建立各个像素点与前景背景相似度的赋权图,并通过求解最小切割区分 前景和背景。由于它是基于颜色统计采样的方法,因此对前背景桕差较 大的图像效果较佳。 Basics(基础知识) 图论中的图( graph) 一个图定义为一个有序对 (V,G),记为G(V,G),其 (1)V是一个非空集合,称为顶 点集,其元素称为顶点 2)E是由中的点组成的无序 点对构成的集合,称为边集, 其元素称为边 Basics(基础知识) 此处的 Graph和普通的 Graph稍有不同 普通的图由顶点和边构成,如果边的有方向的,这样的图被则称为有向图, 否则为无向图,且边是有权值的,不同的边可以有不同的权值,分别代表不 同的物理意义 Graph Cuts是在普通图的基础上多了2个顶点,这2个顶点分别用符号”s” ”T”表示,统称为终端页点。其它所有的页点都必须和这2个顶点相连形 成边集合中的一部分。所以 Graph Cuts中有两种顶点,也有两种边。 Basics(基础知识) 第一种顶点和边是:第一种普通顶点 对应于图像中的每个缘素。每两个邻 域顶点(对应于图像中每两个邻城缘 素)的连接就是一条边。这种边也叫 h-links 第二种顶点和边是:除图像像素外 还有另外两个终端顶点0和每0m 个普通顶点利这2个终谎顶点之间都 有连按,组成第二种边。这种边也叫 t-links