图像理解 课件 06-典型分割技术

典型分割技术图像理解之六2图割方法基于图论的图象分割技术本质上采用了基于边缘的串行分割思路将待分割图象I映射为一个对弧加权的有向图G，它在尺寸上和维数上都与I对应确定目标和背景的种子，并针对它们构建两个特殊的图结点，即源结点s和汇结点t；然后将所有种子根据它们的目标或背景标号分别与源结点或汇结点相连接计算弧代价函数，并对图G中的各个弧赋予一定的弧代价使用最大流图优化算法来确定对图G的图割，从而区分对应目标和背景象素的结点图割方法的一个重要特性是提供了一种借助交互以有效方法改进先前获得的分割结果的能力3图割方法构建图G将边缘象素和边界段（弧）用图表示4图割方法构建图G对任一段弧(ni,nj)都可定义一个代价（或费用），记为C(ni,nj)，它可看作是对弧的加权对给定的待分割图象I，要将其转化表示为一个对弧加权的图G其中，将图象I中每个象素看成图G中的一个结点，即结点集合N由所有象素构成；而将象素间的邻接关系用图G中的弧来表示，即结点对集合A表示象素间的（加权）联系5图割方法构建源结点和汇结点6图割方法构建源结点和汇结点如上可获得一个弧加权图Gst=[N∪{s,t},A]，结点集N对应图象I中的象素，s和t是两个特殊的终端结点弧集合A中的元素可分为两类：连接一对相邻象素的弧与将象素和终端结点连接起来的弧在Gst中的一个割将图中结点分成两组，它的代价是这个割所对应的弧（割所穿过/跨越的弧）的代价之和代价最小的割称为最小s-t割，它将结点分成两组不重叠的子集S(s∈S)和T(t∈T)，且从s到t没有有向的通路7图割方法弧的代价代价最小s-t割的代价是其所对应的所有弧的代价之和Lk∈{o,b}是像素ik的标号，o表示目标，b表示背景L={L1,

L2,

…,

L|I|}：二值分割结果区域性质项：弧两个端结点所对应象素的灰度边界性质项：弧两个端结点所对应象素间的灰度差8图割方法第一种弧：相邻像素之间的弧一方面，给定一个像素，根据其灰度将其标为o或b都会有代价Rp(o)表示将像素p标为目标的代价，Rp(b)表示将像素p标为背景的代价当亮目标在暗背景上时，Rp(o)的值在暗像素（低Ip值）处大而在亮像素处小；当暗目标在亮背景上时，Rp(b)的值在亮像素（高Ip值）处大而在暗像素处小另一方面，对两个相邻的像素p和q，根据其灰度将其赋予不同的标号也会有一定的代价若它们都属于o或b，则弧（p,q）的代价F(p,q)应比较大；若它们一个属于o而另一个属于b，即跨越o和b的边界，则弧（p,q）的代价F(p,q)应比较小例如，可取两个相邻像素p和q之间弧（p,q）的代价与它们间的梯度幅度成反比9图割方法第二种弧：像素与终端节点之间的弧由一系列相邻像素的弧所构成，其总代价是这些相邻像素的弧的代价之和，加1目的是使弧不饱和（B和O分别表示背景和目标像素集合）将上述结果结合起来，赋予各种弧的代价函数为：10图割方法图割的计算对偶：计算最小s-t割⇔计算s到t的最大流最大流的值等于最小割的代价通过弧的水流由其容量或代价决定从s到t的最大流能使一组弧饱和，这些饱和的弧对应最小割，将节点分为不重合的两部分S和T增加通路算法考虑推动从源s到汇t的流直至达到最大流开始时将流的状态初始化为0（保留在残留图Gr中）沿未饱和的弧来确定最短的s→t通路借助推动最大可能的流而使得弧达到饱和11图割方法图割的计算宽度优先搜索确定最短通路算法复杂度O(mn2)，n是结点数而m是弧数12分水岭分割算法分水岭（watershed，也称分水线/水线）把图象看成3-D地形的表示，即2-D的地基（对应图象空间）加上第3维的高度（对应图象灰度）计算过程是串行的，得到的是目标的边界（但利用了区域的一致性）13基本原理和步骤分水岭在两个圆的两个相交点画一直线，该直线的位置为从两个山峰流下来的水汇聚的地方，该直线可称为分水线如果在分水线位置将两个重叠圆形目标分隔开可给出一种最优的分割结果14基本原理和步骤分水岭建立不同目标间的分水岭（涨水法）15基本原理和步骤分水岭计算步骤设待分割图象为f(x,y)，其梯度图象为g(x,y)用M1,M2,…,MR表示g(x,y)中各局部极小值的象素位置，C(Mi)为与Mi对应的区域中的象素坐标集合用n表示当前灰度阈值，T[n]代表记为(u,v)的象素集合，g(u,v)<n，T[n]={(u,v)|g(u,v)<n}对Mi所在的区域，其中满足条件的坐标集合Cn(Mi)可看作一幅二值图象Cn(Mi)=C(Mi)∩T[n]16基本原理和步骤分水岭计算步骤用C[n]代表在灰度阈值为n时图象中所有满足条件的象素（被淹没）C[max+1]将是所有区域的并集C[n–1]是C[n]的子集，C[n]是T[n]的子集，所以C[n–1]又是T[n]的子集17基本原理和步骤分水岭计算步骤令S

代表T[n]中的连通组元集合，对每个连通组元s∈S[n]，有3种可能性：(1)s∩C[n–1]是1个空集(2)s∩C[n–1]里包含C[n–1]中的一个连通组元(3)s∩C[n–1]里包含C[n–1]中一个以上的连通组元分别处理：(1)C[n]可由把连通组元s

加到C[n–1]中得到(2)C[n]可由把连通组元s

加到C[n–1]中得到(3)需要在s

中建分水岭18基本原理和步骤遇到部分或整个区分两个或以上区域的分界线遇到一个新的极小值s属于某些极小值的区域19算法改进和扩展利用标号控制分割过分割（over-segmentation）受图象中噪声和其它不规则结构影响利用标号（marker）图象中的一个连通组元内部标号：对应目标外部标号：对应背景（分水岭）20算法改进和扩展利用标号控制分割(a)表示部分覆盖的两个区域(b)表示经过距离变换的结果（两个局部极小值）(c)检测出的分水线21算法改进和扩展分水岭算法的扩展DaiSY,ZhangY-J.“ColorImageSegmentationinbothFeatureandImageSpace”.AdvancesinImageandVideoSegmentation,ZhangY-Jed.,IRMPress,Chapter10(209-227),200622算法改进