数字图像处理--第6章 图象分割-2

1、 边缘是一个“局部”概念, 一个区域的边界是一个具有整体性的概念。边界跟踪是一种串行图像分割技术。 图像由于噪声以及光照不均等因素，边缘点可能是不连续的，边界跟踪可将它们变为有意义的信息。边界跟踪步骤： 1）确定边界的起始搜索点。 2）确定合适的边界判别准则和搜索准则。 3）确定搜索的终止条件。 假定图像为二值图像，其中只有一个具有闭合边界的目标。按四连通方向搜索边界的方法： 按从左到右、从上到下的顺序搜索；找到的第一个亮点一定是最左上方的边缘点， 把它作为起始搜索点。记为s；同时记下起始搜索点的搜索方向，记为D。这里1为边缘点。 按上、右、下、左的顺序寻找下一边缘点N。C点为当前点，单元格中

2、的数字表示搜索顺序如果N点为1，则该点为边缘点，搜索到下一个时，把N作为当前点C，同时改变搜索方向。 重复步骤2，如果C就是S点且搜索方向为D，则表明已经转了一圈，程序结束。 C 2CNCNC NCN314原始图像四连通边界跟踪结果CPCPCCPCPCPCPCPPl）起始搜索点。梯度图像、灰度最大的为起始点2）边界判别和搜索准则。八邻域搜索第二大的点为边界点3）搜索的终止条件。当找出来的点小于某一阈值时，结束。 哈夫（哈夫（HoughHough）变换是利用图象全局特性）变换是利用图象全局特性 而将边缘象素连接起来组成区域封闭边界的一而将边缘象素连接起来组成区域封闭边界的一 种方法种方法 。6.

3、3.2问题的提出 对于边界上的n个点的点集，找出共线的点集和直线方程。 对于任意两点的直线方程：y=ax+b构造一个参数a,b的平面，从而有如下结论： xy平面上的任意一条直线y=ax+b ，对应在参数ab平面上都有一个点过xy平面一个点(x,y)的所有直线，构成参数ab平面上的一条直线 如果点(x1,y1)与点(x2,y2)共线，那么这两点在参数ab平面上的直线将有一个交点在参数ab平面上相交直线最多的点，对应的xy平面上的直线就是我们的解. 在图象空间中共线的点对应在参数空间里相在图象空间中共线的点对应在参数空间里相 交的线。反过来，在参数空间中相交于同一点的交的线。反过来，在参数空间中相

4、交于同一点的 所有直线在图象空间里都有共线的点与之对应。所有直线在图象空间里都有共线的点与之对应。 这就是点一线的对偶性。这就是点一线的对偶性。Hough变换算法实现 由于垂直直线a为无穷大，改用极坐标形式： 参数平面为, ，对应不是直线而是正弦曲线使用交点累加器，或交点统计直方图，找出相交线段最多的参数空间的点, 然后找出该点对应的xy平面的直线线段 xycossin 如图如图: :在左图中给出图象在左图中给出图象XYXY平面的的5 5个点，在个点，在参数空间里对应参数空间里对应5 5条曲线，这里条曲线，这里 的取值范围为的取值范围为-90-900 0,+90,+900 0, , 取值为取值

5、为 , n, n为为图象长度图象长度Hough变换算法1. 1. 适当地量化参数空间选择表示适当地量化参数空间选择表示曲线的曲线的原始函数原始函数2. 2. 假定参数空间的每一个单元都是一个累假定参数空间的每一个单元都是一个累加器，把累加器初始化为零加器，把累加器初始化为零3. 3. 对图像空间的每一点对图像空间的每一点 ，在其所满足的参，在其所满足的参数方程对应的累加器上加数方程对应的累加器上加1 14. 4. 累加器阵列的最大值对应模型的参数累加器阵列的最大值对应模型的参数原灰度图像参数空间映射图像 圆的一般方程：圆的一般方程： （x-a)2 + (y-b)2 = r2 参数参数a,b,r

6、a,b,r在参数空间中建一个在参数空间中建一个3D3D的累加数组可写的累加数组可写为为A(a,b,r)A(a,b,r)，让，让a,ba,b依次变换算出依次变换算出r, r,对对A A累加：累加： A(a,b,r)=A(a,b,r)+1A(a,b,r)=A(a,b,r)+1与检测直线上的点相同与检测直线上的点相同例如:已知一圆周点(x,y)位于坐标原点，其圆心的轨迹如图所示（r=5），将式: (x-a)2+(y-b)2 = R2 对x微分得: 2(x-a)+2(y-b)dy/dx=0并代入：dy/dx = tan(-/2)再将微分结果与式: (x-a)2+(y-b)2 = R 2联立并对a,b求

7、解就可得到： a=x-rsin b=y+rcos 该结果也可从图中得到 。 如如r已知则参数为圆锥部分表面：已知则参数为圆锥部分表面：圆检测中梯度信息的利用圆检测中梯度信息的利用 以下图为例不考虑梯度方向图中小方块对应图象空间中的圆周点，而虚线圆为可能的圆心位置。此时由于不知道圆心应在何方，需要检查整个虚线圆周以确定图象空间中的圆心点。考虑梯度指向后，只需考虑梯度所指方向的虚线圆弧就可以了。有无梯度方向两种情况下累加器组的内容已经提出几种方法来改进Hough变换的性能一种方法是使用边界梯度信息来减少参数空间的工作量如果圆的半径r已知，问题进一步简化为2D参数空间。这时参数的轨迹 是半径为r的圆

8、周。这里图象空间和参数空间的轨迹都是圆周，称为圆周圆周对偶性。 例,用哈夫变换检圆. 图a是一幅256256灰度合成图，内有一灰度值160半经为80的圆目标，背景灰度值96。整幅图迭加了在-48,48 间均匀分布的随机躁声。求圆心:设半径已知.图B用Sobel求梯度取阈值得边缘.图C哈夫变换得累加器图象,亮点为圆心.图D因半径已知得圆周 边界点和边界段可以用图（graph）结构表示 通过在图中进行搜索对应最小代价的通道也可以找到闭合边界。这种方法是一种全局的方法，它在图象受噪声大时效果仍较好，当然这种方法比较复杂， 计算量也大。6.4 串行边界技术串行边界技术6.4.1 图搜索图搜索 基本概念

9、:一个图可表示为G=N.A，其中N是一个有限非空的节点集，A是一个无序节点对的集，集A中的每个节点对（ni ,nj ）称为一段弧 （niN,nj N）如果弧是有向的，即从一个节点指向另一个节点，则该弧称为有向弧，该图称为有向图。当弧是从节点ni指向nj时，那么称ni是父节点 nj子节点。确定一个节点的各个子节点的过程称为对该节点的展开或扩展。第0层只含一个节点，称为起始节点。最下一层的节点称为目标节点。对任一段弧（ni,nj）都可定义一个代价，记为c(ni,nj) 如果有一系列节点n1,n2nk,其中每个节点ni都 是节点ni-1 的子节点，则这个节点系列称为从到的一条通路（路径），这条通路的

10、代价为: 定义边缘元素是2个互为4近邻的象素边界。见p、q间竖线和q、r间横线: 设每个由象素p和q确定的边缘元素对应一个代价函数： C(p,q)=H-f(p)-f(q) 其中H为图象中的最大灰度，f(p)和f(q)为象素p、q的灰度值。这个代价函数的取值与象素间的灰度差成正比，灰度差小则代价大，灰度差大则代价小。按梯度概念，梯度小则代价大，梯度大则代价小。代价函数，利用图搜索技术可检测出右图所示的边界。算得的最小代价通路。图中粗线表示根据xxyy 解决这个问题的搜索图如下，每个由象素p和q确定的边缘元素对应一 个代价函数： C(p,q)=H-f(p)-f(q) 如果两个边缘元素前后相连，计算

11、出粗线箭头表示的最小代价通路。 通常为求得最小代价所需的计算量常是很大的。如果不利用所需解决问题的一些特性知识，对结点的扩展次序将完全是任意的。由于每个结点都要展开，需扩展的结点数量常很大，在许多情况下为加快运算速度常常只求亚最优。一种启发性知识减少搜索的方法6.4.2 动态规划 令r(n)为从起始结点s出发经结点n到达目标结点的最小代价通路的估计代价。可表示成从起始结点s到结点n的最小代价通路的估计代价g(n)与从结点n到目标结点的通路的估计代价h(n）之和： r(n)n(n)h(n） 其中g(n)可借某些启发性知识(例如根据到达某结点的代价确定是否展开该结点)得到。 进行图搜索的算法（称为

12、A”算法）由以下几个步骤构成： （1 1）将起始结点标记为）将起始结点标记为OPENOPEN，并置，并置g(s)=0g(s)=0；（2 2）如果没有结点）如果没有结点OPENOPEN，失败退出，否则继续；，失败退出，否则继续；（3 3）将根据）将根据r(n)r(n)n(n)n(n)h(n)h(n)算得的估计代价算得的估计代价r(n)r(n)为最小的为最小的OPENOPEN结点标记为结点标记为CLOSECLOSE；（4 4）如果）如果n n是目标结点；找到通路是目标结点；找到通路( (可由可由n n借指针上溯至借指针上溯至s s）退出，否则继续；退出，否则继续；（5 5）展开结点）展开结点n n

13、，得到它的所有子结点（如果没有子结点，得到它的所有子结点（如果没有子结点，返回第（返回第（2 2）步）；）步）；（6 6）如某子结点）如某子结点n ni i还没有标记；置还没有标记；置r(nr(ni i) )g(n)g(n)c(n,nc(n,ni i），标），标记它为记它为OPENOPEN并将指向它的指针返回到结点并将指向它的指针返回到结点n n；（7 7）如果子结点）如果子结点n ni i巳标记为巳标记为OPENOPEN或或CLOSECLOSE；根据；根据g(ng(ni i) )minming(ng(ni i),g(n),g(n)c(n,nc(n,ni i ) )更新它的值。将其更新它的值。

14、将其gg值减小的值减小的CLOSECLOSE子结点标记为子结点标记为OPENOPEN；并将原指向所有其；并将原指向所有其gg值减小的子结点的指针重新指值减小的子结点的指针重新指向向n n。返回到第（。返回到第（2 2）步。）步。 该算法通常并不能保证发现全局最小代价通路。其主要优点是借助启发性知识加快搜索速度。但已证明如从结点n到目标结点的最小代价通路的代价下界，则该算法确实可以发现最小代价通路。 以上算法实际上是将边缘检测和边界连接结合起来了。可用于在给定起点和终点的条件下连接它们之间的边缘段。在图象分割中需检测的区域边界常是闭合的，此时除需确定起始点外还要解决判断搜索结束的问题。 当边界包

15、围的区域比较紧凑时可以通过对图象进行极坐标变换而达到同时解决确定起始点和判断搜索结束这两个问题，并保证所得边界无卷绕重叠且为单象素宽。这种方法是将动态搜索技术用于状态空间而得到的，主要步骤如下： 图图6.16 6.16 边界监测算法的步骤边界监测算法的步骤 （1 1）先在原图中确定一个包含目标的感兴趣区域（）先在原图中确定一个包含目标的感兴趣区域（BOIBOI），浅色椭圆为），浅色椭圆为目标区域，而目标区域，而ROIROI则是则是2 2个粗线圆中间的部分。个粗线圆中间的部分。 （2 2）将得到的）将得到的ROIROI借助极坐标变换（即用图中的箭头旋转扫描）转换成借助极坐标变换（即用图中的箭头旋

16、转扫描）转换成一个矩形区域。一个矩形区域。 (3(3）在顶端选一起点，利用动态搜索技术逐行向下搜索到达炬形区域底）在顶端选一起点，利用动态搜索技术逐行向下搜索到达炬形区域底端。搜索中要保持各结点的连通性，边界的闭合性由起点和终点的横坐端。搜索中要保持各结点的连通性，边界的闭合性由起点和终点的横坐标来保证。标来保证。 （4 4）将动态搜索得到的通路反极坐标变换回去，得目标闭合边界。）将动态搜索得到的通路反极坐标变换回去，得目标闭合边界。 取阈值是最常见的并行的直接检测区域的分割方法.利用取阈值方法来分割灰度图象是一般都对图象有一定的假设，即基于一定的图象模型的。6.5 并行区域技术常见的图象模型

17、描述如下：假设图象具有单峰灰度分布的目标和背景组成，在目标或背景内部的相邻象素间的灰度值是高度相关的。但在目标和背景交界处，两边的灰度值有较大差别。最简单的取阈值法最简单的取阈值法( (基本全局阈值法）分割灰度图象步骤如下：基本全局阈值法）分割灰度图象步骤如下：1.1.确定灰度阈值确定灰度阈值T.T.2.2.图象每个象素与图象每个象素与T T比较，灰度值大于比较，灰度值大于T T的归为一类，小于的归为一类，小于T T的归为另一类。可将整个灰度图象划分为前景和背景。如下的归为另一类。可将整个灰度图象划分为前景和背景。如下实例图实例图可见：确定合适的阈值T是算法的关键。原图的原图的直方图直方图 如

18、果图象中有多个灰度值不同的区域则可选择一系列阈值将每个象素分到合适的类别中去，称为多阈值方法。可表示为： g(x,y)=k if Tk-1f(x,y) 0 假设一幅图像仅包含两个主要的灰度级区域。令假设一幅图像仅包含两个主要的灰度级区域。令z 表示灰表示灰度级值，则两个灰度区域的直方图可以看作它们概率密度度级值，则两个灰度区域的直方图可以看作它们概率密度函数函数(PDF)的估计的估计p(z) p(z)是两个密度的和或混合。一个是图像中亮区域的密度，是两个密度的和或混合。一个是图像中亮区域的密度，另一个是暗区域的密度另一个是暗区域的密度. 如果如果p(z)已知或假设，则它能够确定一个最佳阈值（具

19、有已知或假设，则它能够确定一个最佳阈值（具有最低的误差）将图像分割为两个可区分的区域最低的误差）将图像分割为两个可区分的区域 假设假设2个个PDF中较大的一个对应背景的灰度级，较小的一中较大的一个对应背景的灰度级，较小的一个描述了图像中对象的灰度级，则混合个描述了图像中对象的灰度级，则混合PDF是是P1是属于对象像素的概率，是属于对象像素的概率，P2是属于背景像素的概率，假设是属于背景像素的概率，假设图像只包括对象和背景，则图像只包括对象和背景，则 P1+p2=1 在区间a,b内取值的随机变量的概率是它的概率密度函数从a到b的积分，即在这两个上下限之间PDF曲线围住的面积，因此，将一个背景点当

20、作对象点进行分类时，错误发生的概率为： 这是在曲线p2(z)下方位于阈值左边区域的面积将一个对象点当作背景点进行分类错误发生的概率为这是在曲线p1(z)下方位于阈值右边区域的面积 为了找到出错最少的阈值，使用莱布尼兹法则把E(T)对T求微分并令结果等于0，得到出错率的整体概率是如果P1=P2，则最佳阈值T位于曲线 p1(z)和p2(z) 的交点处上式解出T，即为最佳阈值.高斯密度可以用两个参数均值和方差描述出错最少的阈值T的解:6.5.3 根据区域选取阈值 当图象受到噪声影响时，原本分离的谷可能被填充，使得峰谷的检测比较困难。 可利用图象象素本身及邻域的局部信息选取阈值。1.直方图变换 利用象

21、素邻域的局部性质将原来的直方图变换成一个新的，利于检测的直方图。常用的局部信息是象素的梯度值。 图图b给出图象中一段边缘的剖面（横轴为空间座标，给出图象中一段边缘的剖面（横轴为空间座标，竖轴为灰度值）分三部分各自给出统计值竖轴为灰度值）分三部分各自给出统计值灰度统灰度统计值计值梯度统梯度统计值计值边缘剖面边缘剖面的梯度的梯度统计值的获取统计值的获取 （1） d)曲线上对应目标或背景内部的灰度统计值得图曲线上对应目标或背景内部的灰度统计值得图a) （2）在）在d)曲线上对应目标或背景内部的梯度值小而目标或曲线上对应目标或背景内部的梯度值小而目标或背景过渡区的梯度值大。对梯度值进行统计得图背景过渡

22、区的梯度值大。对梯度值进行统计得图C）梯度直）梯度直方图方图C)中的两个峰值分被对应目标或背景内部区和过渡区中的两个峰值分被对应目标或背景内部区和过渡区目标或背景变换的直方图可分为两类：目标或背景变换的直方图可分为两类： （1） 具有低梯度值象素的直方图具有低梯度值象素的直方图,在边界上的象素具有较在边界上的象素具有较高的梯度值。峰谷变深。（高的梯度值。峰谷变深。（a)图图 （2）具有高梯度值象素的直方图，对目标和背景的边界象）具有高梯度值象素的直方图，对目标和背景的边界象素灰度级处有一个峰素灰度级处有一个峰,这个峰由边界象素组成，对应这个峰这个峰由边界象素组成，对应这个峰的灰度值可选作分割用

23、的的灰度值可选作分割用的阈值(b) 图图6.5.4根据坐标选取阈值 当图象各处的对比度不同时，如果只用一个固定的阈值对整个图象进行分割，则不能兼顾各处的情况。 使用与坐标相关的阈值，称为动态阈值。这种方法称为变化阈值法。基本思想： 将图象分解成一系列子图，子图可重叠也可只不过相邻。将图象分解成一系列子图，子图可重叠也可只不过相邻。如果子图象比较小，由对比度不一致带来的问题就较小，再如果子图象比较小，由对比度不一致带来的问题就较小，再对每个子图使用任一固定阈值法。通过对子图所得的阈值进对每个子图使用任一固定阈值法。通过对子图所得的阈值进行插值。得图象中每个象素进行分割所需的域值。分割就是行插值。

24、得图象中每个象素进行分割所需的域值。分割就是将每个象素都和与之对应的域值相比较而实现。对应每个象将每个象素都和与之对应的域值相比较而实现。对应每个象素的域值组成的图象素的域值组成的图象( (幅度轴）上的一个曲面叫幅度轴）上的一个曲面叫域值曲面域值曲面步骤：1 1、将图象分成一系列相互有、将图象分成一系列相互有5050重叠的子图象重叠的子图象2 2、做各子图象的直方图、做各子图象的直方图3 3、检测双峰，是：处理；否：不处理、检测双峰，是：处理；否：不处理4 4、插值得全部子图象的、插值得全部子图象的T T5 5、据各子、据各子T T插值得所有像素的插值得所有像素的T(T(曲面曲面) )，然后对

25、图象进行分，然后对图象进行分割割例、根据坐标的阈值分割T曲面原图原图全域值分割：围全域值分割：围巾和背景未分开巾和背景未分开作图的分区网格作图的分区网格对各分区域值进对各分区域值进行插值后得的域行插值后得的域值曲面图值曲面图用域值曲面用域值曲面图分割原图图分割原图后结果后结果 串行区域分割的特点是将过程分解为顺序的多个串行区域分割的特点是将过程分解为顺序的多个步骤后序的处理依结果断定。其准则多为灰度特性。步骤后序的处理依结果断定。其准则多为灰度特性。6.6.1 区域生长区域生长 将处理过程分解为顺序的多个步骤，每个步骤是根据其上个步骤的结果作出。判断的依据可以是图象的灰度信息或纹理信息。6.6

26、串行区域技术6.6.1区域生长 区域增长的算法： 1）根据图像的不同应用选择一个或一组种子，它或者 是最亮或最暗的点，或者是位于点簇中心的点2）选择一个描述符（条件） 3）从该种子开始向外扩张，首先把种子像素加入结果集合，然后不断将与集合中各个像素连通、且满足描述符的像素加入集合4）上一过程进行到不再有满足条件的新结点加入集合为止实际应用时需要解决三个问题：1.选择一组能代表所需区域的种子象素；2.确定合并允许的准则；（准则：考虑的象素与种子象素灰度值差的绝对值小于某个门限T，将该象素包括进种子素灰所在区域。3.制定生长停止条件。区域生长示意图：区域生长示意图：生长准则选举依赖于具体问题，也与图象的数据有关。如当为彩色就不能用单色的准则。还要考虑象素间的连通性和邻近性.6.6.2 分裂合并 同生长法不同层次。本方