图像处理_图像分割.ppt

数字图像处理 DigitalImageProcessing 第七章图像分割 7 1图像分割概述7 2阈值分割7 3边缘检测7 4区域分割7 5Hough变换检测法 7 1图像分割概述 分割的目的是把图象空间分成一些有意义的区域 是实现图像自动识别与理解的必不可少的过程 是计算机视觉的中间层次 例如 一幅航空照片 可以分割成工业区 住宅区 湖泊 森林等等 可以以逐个象素为基础去研究图象分割 也可以利用在规定邻域中的某些图象信息去分割 分割的依据可建立在相似性和非连续性两个基本概念之上 图像分析系统的基本构成如下图 1 图像分割的目标把图像分成互不重叠的区域并提取感兴趣的目标 如下图 1 图像分割的目标把图像分成互不重叠的区域并提取感兴趣的目标 如下图 2 图像分割的定义令集合R代表整个图像区域 对R的分割可看作将R分成N个满足以下五个条件的非空子集 子区域 R1 R2 RN 对所有的i和j i j 有Ri Rj 对i 1 2 N 有P Ri TRUE 对i j 有P Ri Rj FALSE 对i 1 2 N Ri是连通的区域 其中P Ri 是对所有在集合Ri中元素的逻辑谓词 代表空集 3 图像分割的基本策略分割算法基于灰度值的两个基本特性 不连续性和相似性 首先检测图像像素灰度级的不连续性 找到点 线 宽度为1 边 不定宽度 先找边 后确定区域 或者 检测图像区域像素的灰度值的相似性 通过选择阈值 找到灰度值相似的区域 区域的外轮廓就是对象的边 举例1 检测不连续性 举例2 检测相似性 4 图像分割的方法1 基于边缘的分割方法 先提取区域边界 再确定边界限定的区域 2 区域分割 确定每个像素的归属区域 从而形成一个区域图 3 区域生长 将属性接近的连通像素聚集成区域 4 分裂 合并分割 综合利用前两种方法 既存在图像的划分 又有图像的合并 图像阈值分割是一种广泛应用的分割技术 利用图像中要提取的目标物与其背景在灰度特性上的差异 把图像视为具有不同灰度级的两类区域 目标和背景 的组合 选取一个合适的阈值 以确定图像中每个象素点应该属于目标还是背景区域 从而产生相应的二值图像 阈值分割法的特点是 适用于物体与背景有较强对比的情况 重要的是背景或物体的灰度比较单一 而且总可以得到封闭且连通区域的边界 6 2 1图像二值化设原始图像f x y 以一定的准则在f x y 中找出一个合适的灰度值 作为阈值t 则分割后的图像g x y 可由下式表示 7 2阈值分割 另外 还可以将阈值设置为一个灰度范围 t1 t2 凡是灰度在范围内的象素都变为1 否则皆变为0 即 某种特殊情况下 高于阈值t的象素保持原灰度级 其它象素都变为0 称为半阈值法 分割后的图像可表示为 阈值分割图像的基本原理 可用下式表示 阈值的选取时阈值分割技术得关键 如果过高 则过多的目标点被误归为背景 如果阈值过低 则会出现相反的情况 由此可见 阈值化分割算法主要有两个步骤 1 确定需要的分割阈值 2 将分割阈值与象素值比较以划分象素 在利用阈值方法来分割灰度图像时一般都对图像有一定的假设 基于一定的图像模型的 最常用的模型 假设图像由具有单峰灰度分布的目标和背景组成 处于目标或背景内部相邻象素间的灰度值是高度相关的 但处于目标和背景交界处两边的象素在灰度值上有很大的差别 如果一幅图像满足这些条件 它的灰度直方图基本上可看作是由分别对应目标和背景的两个单峰直方图混合构成的 简单直方图分割法 7 2 1双峰法阈值60年代中期 Prewitt提出了直方图双峰法 即如果灰度级直方图呈明显的双峰状 则选取两峰之间的谷底所对应的灰度级作为阈值 双峰法选取阈值的缺点 会受到噪音的干扰 最小值不是预期的阈值 而偏离期望的值 改进办法 1 取两个峰值之间某个固定位置 如中间位置上 由于峰值代表的是区域内外的典型值 一般情况下 比选谷底更可靠 可排除噪音的干扰 2 加强对噪音的处理 对直方图进行平滑处理 如最小二乘法等补点插值 7 2 2通过边界特性选择阈值基本思想 改善直方图的波峰形状 我们只把区域边缘的像素绘入直方图 而不考虑区域中间的像素 用微分算子 处理图像 使图像只剩下边界中心两边的值 这样直方图的各个波峰很高 很窄 对称 且被很深的波谷分开时 有利于选择阈值 优点 1 在前景和背景所占区域面积差别很大时 不会造一个灰度级的波峰过高 而另一个过低 2 边缘上的点在区域内还是区域外的概率是相等的 因此可以增加波峰的对称性 3 基于梯度和拉普拉斯算子选择的像素 可以增加波峰的高度 算法的实现 1 对图像进行梯度计算 得到梯度图像 2 得到梯度值最大的那一部分 比如10 的像素直方图 3 通过直方图的谷底 得到阈值T 另外 也可以用拉普拉斯算子不通过直方图 直接得到阈值 方法是使用拉普拉斯算子过滤图像 将0跨越点对应的灰度值为阈值T 7 2 3最佳阈值所谓最佳阈值是指图像中目标物与背景的分割错误最小的阈值 设某一图像只由目标物和背景组成 已知其灰度级分布概率密度分别为P1 Z 和P2 Z 目标物体象素占全图象素比为 因此该图像总的灰度级概率密度分布P Z 可用下式表示 P Z P1 Z 1 P2 Z 设选用的灰度级门限为Zt 图像由亮背景上的暗物体所组成 因此凡是灰度级小于Zt的象素被认为是目标物 大于Zt的象素皆作为背景 一般的图像很难获得灰度的概率密度函数以及先验概率 在一些特殊的应用场合 如文字 乐谱等图像 可以从大量图像得到一个统计规律 获得符号部分在全图像中的百分比 以此为基础 结合直方图谷点分析 可以得到近似最优的结果 若选为Zt分割门限 则将背景象素错认为是目标象素的概率是 将目标物象素错认为是背景象素的概率是 因此 总的错误概率E Zt 为E Zt 1 E2 Zt E1 Zt 最佳门限就是使E Zt 为最小值时的Zt 将E Zt 对Zt求导 并令其等于零 得 1 P2 Zt P1 Zt 例如 P2 Zt 和P1 Zt 均为正态分布函数 其灰度均值分别为 1和 2 对灰度均值的标准偏差分别为 1和 2 即 代入 1 P2 Zt P1 Zt 两边取对数 由于上式是Zt的二次方程 有两个解 要使分割误差最小 需要设置两个门限 也就是方程的两个根 如果设 则方程存在唯一解 即 再假设 1 1 2时 Zt 1 2 2 7 2 4自适应阈值 自适应阈值是由Chow和Kaneko提出 它是一种基于区域统计特征的分块域值方法 其算法原理是 将一幅图像划分为35 35或65 65的互不重叠的图像块 求出每个子图像块的直方图及阈值 子图像的中心像素点就使用求出的阈值 而区域内的其它像素点的阈值通过插值的方法 自适应 地确定 1111111114444431146777611678875115788751146776611344444111111111 111111111105324121157336411442122114521321171042531113732311111111111 阈值二值化举例 7 3边缘检测 7 3 1边缘检测概念7 3 2基于一阶导数法的边缘检测7 3 3基于二阶导数法的边缘检测7 3 4基于曲面拟合的边缘检测方法7 3 5边缘连接 7 3 1边缘检测概念 1 边缘的定义 图像中像素灰度有阶跃变化或屋顶变化的那些像素的集合 2 边缘的分类阶跃状屋顶状 说明 对阶跃边缘 其一阶导数在图像由暗变明的位置处有1个向上的阶跃 而其它位置都为0 这表明可用一阶导数的幅度值来检测边缘的存在 幅度峰值一般对应边缘位置 其二阶导数在一阶导数的阶跃上升区有1个向上的脉冲 而在一阶导数的阶跃下降区有1个向下的脉冲 在这两个脉冲之间有1个过0点 它的位置正对应原图像中边缘的位置 所以可用二阶导数的过0点检测边缘位置 而用二阶导数在过0点附近的符号确定边缘象素在图像边缘的暗区或明区 对 c 而言 脉冲状的剖面边缘与 a 的一阶导数形状相同 所以 c 的一阶导数形状与 a 的二阶导数形状相同 而它的2个二阶导数过0点正好分别对应脉冲的上升沿和下降沿 通过检测脉冲剖面的2个二阶导数过0点就可确定脉冲的范围 对 d 而言 屋顶状边缘的剖面可看作是将脉冲边缘底部展开得到 所以它的一阶导数是将 c 脉冲剖面的一阶导数的上升沿和下降沿展开得到的 而它的二阶导数是将脉冲剖面二阶导数的上升沿和下降沿拉开得到的 通过检测屋顶状边缘剖面的一阶导数过0点 可以确定屋顶位置 3 边缘检测算子可用一阶 二阶局部微分算子来检测图像中的边缘 下面是几种常用的微分算子 梯度算子Roberts算子Prewitt算子Sobel算子Kirsch算子Laplacian算子Marr算子 1 梯度算子 函数f x y 在 x y 处的梯度为一个向量 f f x f y 计算这个向量的大小为 G f x 2 f y 2 1 2近似为 G fx fy 或G max fx fy 梯度的方向角为 x y tan 1 fy fx 可用下图所示的模板表示 为了检测边缘点 选取适当的阈值T 对梯度图像进行二值化 则有 这样形成了一幅边缘二值图像g x y 特点 仅计算相邻像素的灰度差 对噪声比较敏感 无法抑止噪声的影响 2 Roberts算子 公式 模板 特点 与梯度算子检测边缘的方法类似 对噪声敏感 但效果较梯度算子略好 3 Prewitt算子 公式模板 特点 在检测边缘的同时 能抑止噪声的影响 4 Sobel算子 公式模板特点 对4邻域采用带权方法计算差分 能进一步抑止噪声 但检测的边缘较宽 5 Kirsch算子 方向算子 模板 Kirsch算子特点在计算边缘强度的同时可以得到边缘的方向 各方向间的夹角为45 Kirsch算子分析取其中最大的值作为边缘强度 而将与之对应的方向作为边缘方向 如果取最大值的绝对值为边缘强度 并用考虑最大值符号的方法来确定相应的边缘方向 则考虑到各模板的对称性 只要有前四个模板就可以了 6 Nevitia算子 7 拉普拉斯算子 定义 二维函数f x y 的拉普拉斯是一个二阶的微分定义为 2f 2f x2 2f y2 离散形式 模板 可以用多种方式被表示为数字形式 定义数字形式的拉普拉斯的基本要求是 作用于中心像素的系数是一个负数 而且其周围像素的系数为正数 系数之和必为0 对于一个3x3的区域 经验上被推荐最多的形式是 拉普拉斯算子的分析 优点 各向同性 线性和位移不变的 对细线和孤立点检测效果较好 缺点 对噪音的敏感 对噪声有双倍加强作用 不能检测出边的方向 常产生双像素的边缘 由于梯度算子和Laplace算子都对噪声敏感 因此一般在用它们检测边缘前要先对图像进行平滑 8 Marr算子 Marr算子是在Laplacian算子的基础上实现的 它得益于对人的视觉机理的研究 有一定的生物学和生理学意义 由于Laplacian算子对噪声比较敏感 为了减少噪声影响 可先对图像进行平滑 然后再用Laplacian算子检测边缘 平滑函数应能反映不同远近的周围点对给定像素具有不同的平滑作用 因此 平滑函数采用正态分布的高斯函数 即 其中 是方差 用h x y 对图像f x y 的平滑可表示为 代表卷积 令r是离原点的径向距离 即r2 x2 y2 对图像g x y 采用Laplacian算子进行边缘检测 可得 这样 利用二阶导数算子过零点的性质 可确定图像中阶跃边缘的位置 称为高斯 拉普拉斯滤波算子 也称为LOG滤波器 或 墨西哥草帽 由于Marr算子的平滑性质能减少噪声的影响 所以当边缘模糊或噪声较大时 利用检测过零点能提供较可靠的边缘位置 在该算子中 的选择很重要 小时边缘位置精度高 但边缘细节变化多 大时平滑作用大 但细节损失大 边缘点定位精度低 应根据噪声水平和边缘点定位精度要求适当选取 下面是 10时 Marr算子的模板 7 3 2基于一阶导数法的边缘检测 1 基本思想检测图像一阶导数的峰值或者谷值确定边缘 可用一阶微分算子和图像卷积实现 一阶微分算子有 梯度算子 Roberts算子 Prewitt算子 Sobel算子等 2 模板卷积无论哪种模板 其卷积过程为 R w1z1 w2z2 w9z9 Swkz其中zk是与模板系数wk相联系的象素灰度 R代表模板中心象素的值 3 线的检测通过比较典型模板的计算值 确定一个点是否在某个方向的线上 线检测模板如下 用4种模板分别计算 R水平 6 30 24R45度 14 14 0R垂直 14 14 0R135度 14 14 0 检测线的算法描述依次计算4个方向的典型检测模板 得到Rii 1 2 3 4如 Ri Rj 对于所有的j i 那么这个点被称为在方向上更接近模板i所代表的线 设计任意方向的检测模板 可能大于3x3 模板系数和为0 赶兴趣的方向的系数大 7 3 3基于二阶导数法的边缘检测 1 基本思想检测图像二阶导数的零点确定边缘 可用二阶微分算子和图像卷积实现 并可通过二阶导数的正负判断像素在明区还是暗区 二阶微分算子有 Laplacian算子 Marr算子 Log算子等 2 点的检测用空域的高通滤波器来检测孤立点 例 R 1 8 8 128 8 9 120 8 9 960 9 106可设阈值T 64 R T是孤立点 点检测的算法描述 设定阈值T 如T 32 64 128等 并计算高通滤波值R如果R值等于0 说明当前检测点与的灰度值与周围点的相同 当R的值足够大时 说明该点的值与周围的点非常不同 是孤立点 通过阈值T来判断 R T 则检测到一个孤立点 7 3 4基于曲面拟合的边缘检测方法 1 基本思想基于差分检测图像边缘的算子往往对噪声敏感 因此对一些噪声比较严重的图像就难以取得满意的效果 若用平面或高阶曲面来拟合图像中某一小区域的灰度表面 求这个拟合平面或曲面的外法线方向的微分或二阶微分检测边缘 可减少噪声影响 2 四点拟合灰度表面法用一平面p x y ax by c来拟合空间四邻像素的灰度值f x y f x y 1 f x 1 y f x 1 y 1 定义均方差为 按均方差最小准则 令可解出参数a b c 可推导出 按梯度的定义 由平面p x y ax by c的偏导数很容易求得梯度 a为两行像元平均值的差分 b为两列像元平均值的差分 这种运算可简化为模板求卷积进行 计算a和b对应的模板如下 3 特点 其过程是求平均后再求差分 因而对噪声有抑制作用 梯度算子 Roberts算子 Prewitt算子 Kirsch算子 原始图像 例1 Laplacian算子 曲面拟合法 例2 梯度算子 Roberts算子 Prewitt算子 Sobel算子 Kirsch算子 原始图像 Laplacian算子 Marr算子 曲面拟合法 a 原图 b 2h结果 c 正值为白 负值为黑 d 过零点 例3 利用 2h检测过零点确定边缘 拉普拉斯模板 Sobely方向微分 Sobelx方向微分 Sobel算子梯度 7 3 5边缘连接1 边缘连接的意义和目的由于噪音的原因 边界的特征很少能够被完整地描述 在亮度不一致的地方会中断 因此典型的边检测算法后面总要跟随着连接过程和其它边界检测过程 用来归整边像素 成为有意义的边缘 连接处理的目的是要把间断的边连接起来形成封闭的边界 一般是在边界检测之后进行 2 局部连接处理的原理对边检测后的图象的每个点 x y 的特性进行分析 在一个小的邻域 3x3或5x5 中把所有相似的点被连接 形成一个享有共同特性象素的边界 其相似性可用比较梯度算子的响应强度和梯度方向来确定 并判断两个点是否同属一条边 具体做法是 1 通过比较梯度 确定两个点的连接性 对于点 x y 判断其是否与邻域内的点 x y 相似 当 f x y f x y T其中T是一个非负的阈值 2 比较梯度向量的方向角对于点 x y 判断其是否与邻域内的点 x y 的方向角相似 当 x y x y A其中A是一个角度阈值 3 比较梯度向量的方向角当梯度值和方向角都是相似的 则点 x y 与边点界 x y 是连接的 连接算法步骤 1 设定A T的阈值大小 确定邻域的大小 2 对图像上每一个像素的邻域点进行分析 判断是否需要连接 3 记录像素连接的情况 另开一个空间 给不同的边以不同的标记 4 最后 删除孤立线段 连接断开的线段 3边缘跟踪由于噪音的原因 边界的特征很少能够被完整地描述 在亮度不一致的地方会中断 边缘跟踪可将检测的边缘点连接成线 形成有意义的边界 边缘跟踪有两种方法 光栅跟踪和全向跟踪 1 光栅跟踪它是一种采用电视光栅行扫描顺序 结合门限检测 对遇到的像素进行分析 从而确定是否为边缘的跟踪方法 具体步骤 1 确定一个比较高的阈值d 把高于该阈值的像素作为对象点 称该阈值为 检测阈值 2 用检测阈值d对图像第一行像素进行检测 凡超过d的点都接受为对象点 并作为下一步跟踪的起始点 3 选取一个比较低的阈值作为跟踪阈值 该阈值可以根据不同准则来选择 例如 取相邻对象点之灰度差的最大值作为跟踪阈值 有时还利用其他参考准则 如梯度方向 对比度等 4 确定跟踪邻域 取像素 i j 的下一行像素 i 1 j 1 i 1 j i 1 j 1 为跟踪邻域 5 扫描下一行像素 凡和上一行已检测出来的对像点相邻接的像素 其灰度差小于跟踪阈值的 都接受为对象点 反之去除 6 对于已检测出的某一对象点 如果在下一行跟踪领域中 没有任何一个像素被接受为对象点 那么 这一条曲线的跟踪便可结束 如果同时有两个 甚至三个邻域点均被接受为对象点 则说明曲线发生分支 跟踪将对各分支同时进行 如果若干分支曲线合并成一条曲线 则跟踪可集中于一条曲线上进行 一曲线跟踪结束后 采用类似上述步骤从第一行的其他检出点开始下一条曲线的跟踪 7 对于未被接受为对象点的其他各行像素 再次用检测阈值进行检测 并以新检出的点为起始点 重新使用跟踪阈值程序 以检测出不是从第一行开始的其他曲线 8 当扫描完最后一行时 跟踪便可结束 由结果可以看出 本例原图像中存在着三条曲线 两条从顶端开始 一条从中间开始 然而 如果不用跟踪法 只用一种阈值d或t检测均不能得到满意的结果 注意 检测和跟踪所选择的特征可以不是灰度级 而是其他反映局部性质的量 例如对比度 梯度等 此外 每个点所对应的邻域也可以取其他的定义 不一定是紧邻的下一行像素 稍远一些的领域也许对于弥合曲线的间隙更有好处 跟踪准则也可以不仅仅针对每个已检测出的点 而是针对已检出的一组点 这时 可以对先后检出的点赋予不同的权 如后检出的点给以较大的权 而早先检出的点赋予相对小一些的权 利用被检测点性质和已检出点性质的加权均值进行比较 以决定接收或拒绝 总之 应根据具体问题灵活加以运用 光栅扫描跟踪和扫描方向有关 因此最好沿其他方向再跟踪一次 例如逆向跟踪 并将两种跟踪的结合综合起来能得到更好的结果 另外 若边缘和光栅扫描方向平行时效果不好 则最好在垂直扫描方向跟踪一次 它相当于把图像转置90o后再进行光栅扫描跟踪 2 全向跟踪 如果能使跟踪方向不仅局限于逐行 或列 的光栅式扫描 譬如说 在从上而下 或自左而右 的扫描过程中 也可以向上 或向左 跟踪 那么就会克服光栅跟踪依赖于扫描方向的缺点 这可以通过定义不同邻域的方法来实现 同样 如果我们选取的跟踪准则能够辨别远非紧邻的像素 那么光栅跟踪会漏掉平行于扫描方向曲线的缺点也能得到适当地克服 全向跟踪就是跟踪方向可以是任意方向 并且有足够大的跟踪距离的跟踪方法 显然 全向跟踪是改变了邻域定义和跟踪准则的一种光栅跟踪法 具体步骤 1 按光栅扫描方式对图像进行扫描 用检测阈值找出一个起始跟踪的流动点 沿被检测曲线流动 2 选取一个适当的 能进行全向跟踪的邻域定义 例如八邻域 和一个适当的跟踪准则 例如灰度阈值 对比度和相对流动点的距离等 对流动点进行跟踪 在跟踪过程中 若 a 遇到了分支点或者若干曲线的交点 即同时有几个点都跟踪一个流动点 则先取其中和当前流动点性质最接近的作为新的流动点 继续进行跟踪 而把其余诸点存储起来 以备后面继续跟踪 如果在跟踪过程中又遇到了新的分支或交叉点 则重复上面的处理步骤 当按照跟踪准则没有未被检测过的点可接受为对象点时 一个分支曲线的跟踪便已结束 b 在一个分支曲线跟踪完毕以后 回到最近的一个分支点处 取出另一个性质最接近该分支点的像素作为新的流动点 重复上述跟踪程序 c 当全部分支点处的全部待跟踪点均已跟踪完毕 便返回第一步 继续扫描 以选取新的流动点 不应是已接收为对象的点 3 当整幅图像扫描完成时 跟踪程序便结束 特点是 全向跟踪改进了光栅扫描跟踪法 跟踪时把初始点的八邻点全部考虑进行跟踪 7 4 1区域生长法算法实现步骤 1 根据图像的不同应用选择一个或一组种子 它或者是最亮或最暗的点 或者是位于点簇中心的点 2 选择一个描述符 条件 3 从该种子开始向外扩张 首先把种子像素加入结果集合 然后不断将与集合中各个像素连通 且满足描述符的像素加入集合4 上一过程进行到不再有满足条件的新结点加入集合为止 7 4区域分割 7 4 2分裂合并法算法实现 1 对图像中灰度级不同的区域 均分为四个子区域 2 如果相邻的子区域所有像素的灰度级相同 则将其合并 3 反复进行上两步操作 直至不再有新的分裂与合并为止 实际应用中还可作以下修改 P Ri 的定义为 1 区域内多于80 的像素满足不等式 zj mi 2 i 其中 zj是区域Ri中第j个点的灰度级 mi是该区域的平均灰度级 i是区域的灰度级的标准方差 2 当P Ri TRUE时 将区域内所有像素的灰度级置为mi 7 5Hough变换检测法 7 5 1问题的提出7 5 2Hough变换的基本思想7 5 3算法实现7 5 4Hough变换的扩展 7 5 1问题的提出在找出边界点集之后 需要连接形成完整的边界图形描述 Hough变换是一种能够在检测边界的同时完成边界的封闭变换 7 5 2Hough变换的基本思想其基本思想是 对于边界上的n个点的点集 找出共线的点集和直线方程 对于直角坐标系中的一条直线l 可用 来表示该直线 且直线方程为 其中 为原点到该直线的垂直距离 为垂线与x轴的夹角 这条直线是唯一的 构造一个参数 的平面 从而有如下结论 直角坐标系中的一条直线对应极坐标系中的一点 这种线到点的变换就是Hough变换 7 5 3算法实现使用交点累加器 或交点统计直方图 找出相交线段最多的参数空间的点 然后找出该点对应的xy平面的直线线段 算法步骤 1 在 的极值范围内对其分别进行m n等分 设一个二维数组的