特色分割算法课件

特色分割算法课件第5章特色分割算法

5.1 SUSAN检测算子

5.2 主动轮廓模型

5.3 特色的取阈值技术

5.4 分水岭分割算法章毓晋(TH-EE-IE)第5章特色分割算法 5.1 SUSAN检测算子章毓晋5.1 SUSAN边缘检测原理 USAN:UnivalueSegmentAssimilatingNucleus 核同值区：相对于模板的核，模板中有一定 的区域与它有相同的灰度章毓晋(TH-EE-IE)5.1 SUSAN边缘检测原理章毓晋(TH-EE-IE)5.1.1USAN原理 USAN的面积携带了关于图象中核象素处结 构的主要信息 当核象素处在图象中的灰度一致区域， USAN的面积会达到最大。该面积当 核处在直边缘处约为最大值的一半， 而当核处在角点处则为最大值的1/4 使用USAN面积作为特征起到了增强边缘和 角点的效果

章毓晋(TH-EE-IE)5.1.1USAN原理 USAN的面积携带了关于图象中核5.1.2SUSAN边缘检测SUSAN：最小（Smallest）核同值区 检测模板：37个象素,半径为3.4象素

章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测SUSAN：最小（Small5.1.2SUSAN边缘检测 检测对模板中的每个象素进行 得到输出的游程和（runningtotal） 边缘响应 几何阈值G=3Smax/4，其中Smax是S所能取的最大值

章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测 检测对模板中的每个象素进5.1.2SUSAN边缘检测边缘方向的确定 根据非零强度的象素确定边缘的方向 点A和B都是标准的边缘点，各落在边缘的一边 从USAN重心到模板核的矢量与边缘局部方向垂直

章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测边缘方向的确定章毓晋(T5.1.2SUSAN边缘检测边缘方向的确定 根据非零强度的象素确定边缘的方向 点C落在两个边缘的中间

USAN是沿边缘方向的细条，找最长的对称轴

章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测边缘方向的确定章毓晋(T5.1.2SUSAN边缘检测特点

有噪声时的性能较好

不需要计算微分

对面积计算中的各个值求和（积分）

非线性响应特点

易自动化实现

控制参数的选择简单

参数的任意性较小章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测特点章毓晋(TH-EE-I5.2 主动轮廓模型 给定对图象中目标轮廓的一个近似（初始轮廓），主动轮廓模型可用来检测准确的轮廓 主动轮廓模型逐步改变封闭曲线的形状以逼近图象中目标的轮廓。在这个过程中，目标轮廓的各部分常用线，边缘等表示。 主动轮廓模型也称Snakes，因为在对目标轮廓的逼近过程中，封闭曲线像蛇爬行一样不断改变形状。章毓晋(TH-EE-IE)5.2 主动轮廓模型 给定对图象中目标轮廓的一个近似（初始轮5.2.1主动轮廓

主动轮廓是图象上一组排序的点的集合 处在轮廓上的点可通过解一个最小能量问题来迭代地逼近目标的边界 Eint(vi)是依赖于轮廓形状的能量函数

Eext(vi)是依赖于图象性质的能量函数章毓晋(TH-EE-IE)5.2.1主动轮廓 主动轮廓是图象上一组排序的点的5.2.2设计能量函数

1 内部能量

推动主动轮廓形状的改变 并保持轮廓上点间的距离(1) 连续能量 迫使不封闭的曲线变成直线而封闭的曲线变成圆环

(2) 膨胀力

强制轮廓在没有外来影响的情况下扩展或收缩

章毓晋(TH-EE-IE)5.2.2设计能量函数1 内部能量章毓晋(TH5.2.2设计能量函数

2 外部能量 将变形模板向感兴趣的特征吸引

构建能量函数：如目标的尺寸和形状(1) 图象灰度能量

将轮廓吸向高或低的灰度区域

(2) 图象梯度能量 将轮廓推向特征（边缘）

章毓晋(TH-EE-IE)5.2.2设计能量函数2 外部能量章毓晋(TH5.3 特色的取阈值技术

5.3.1 多分辨率阈值选取

5.3.2 类间最大交叉熵阈值

5.3.3 类内最小模糊散度阈值

5.3.4 借助过渡区选择阈值章毓晋(TH-EE-IE)5.3 特色的取阈值技术 5.3.1 多分辨率阈值选取5.3.1多分辨率阈值选取

1. 确定分割区域的类数 利用在粗分辨率下的直方图细节信息 尺度函数f(x)：低通滤波器

图象直方图H(x)的低通分量为 直方图的多分辨率小波分解表示 {S2i[H(x)],W2i[H(x)],1≤i

≤I}

章毓晋(TH-EE-IE)5.3.1多分辨率阈值选取1. 确定分割区域的类数章毓5.3.1多分辨率阈值选取

1. 确定分割区域的类数 在分辨率为21时确定初始的区域分割类数

判断直方图中独立峰的个数 独立峰应满足三个条件？ (1) 具有一定的灰度范围 (2) 具有一定的峰下面积 (3) 具有一定的峰谷差章毓晋(TH-EE-IE)5.3.1多分辨率阈值选取1. 确定分割区域的类数章毓5.3.1多分辨率阈值选取

2. 确定最优阈值(1) 用从负值变化到正值的零交叉点确定峰的起点(2) 用从正值变化到负值的零交叉点确定峰的终点(3) 用起点和终点间的最大值点确定峰的位置(4) 用前一个峰的终点和后一个峰的起点间的最小值点确定这两个峰之间谷点的位置

章毓晋(TH-EE-IE)5.3.1多分辨率阈值选取2. 确定最优阈值章毓晋(5.3.1多分辨率阈值选取

2. 确定最优阈值 分辨率增加阈值数目也增加 设在两相邻尺度2i+1和2i

所对应的阈值分别为和 在尺度2i+1的阈值对应在尺度2i的阈值 跟踪在最低分辨率一层选取的所有阈值 选取相应的最高分辨率一层的对应阈值

章毓晋(TH-EE-IE)5.3.1多分辨率阈值选取2. 确定最优阈值章毓晋(1. 交叉熵

交叉熵是一种用来度量两个概率分布 P={p1,p2,…,pN}，Q={q1,q2,…,qN}

之间信息量差异的量 对称交叉熵是交叉熵的对称形式5.3.2类间最大交叉熵阈值章毓晋(TH-EE-IE)1. 交叉熵5.3.2类间最大交叉熵阈值章毓晋(TH-2. 类间最大交叉熵 目标与背景应有尽可能大的差异 整幅图象的类间差异性 搜索获得基于类间最大交叉熵的最优阈值5.3.2类间最大交叉熵阈值章毓晋(TH-EE-IE)2. 类间最大交叉熵5.3.2类间最大交叉熵阈值章毓晋1. 过渡区和有效平均梯度5.3.4借助过渡区选择阈值章毓晋(TH-EE-IE)1. 过渡区和有效平均梯度5.3.4借助过渡区选择阈值章2. 有效平均梯度的极值点和过渡区边界5.3.4借助过渡区选择阈值章毓晋(TH-EE-IE)2. 有效平均梯度的极值点和过渡区边界5.3.4借助过5.4分水岭分割算法

分水岭（watershed，也称分水线/水线）

把图象看成3-D地形的表示，即2-D的地基 （对应图象空间）加上第3维的高度（对应 图象灰度）

计算过程是串行的，得到的是目标的边界 5.4.1 基本原理和步骤 5.4.2 算法改进和扩展章毓晋(TH-EE-IE)5.4分水岭分割算法 分水岭（watershed5.4.1基本原理和步骤

1. 分水岭 建立不同目标间的分水岭谷底孔分水岭章毓晋(TH-EE-IE)5.4.1基本原理和步骤1. 分水岭谷底孔分水5.4.1基本原理和步骤

2. 分水岭计算步骤 待分割图象f(x,y)，其梯度图象为g(x,y) 用M1,M2,…,MR表示g(x,y)中各局部极小值的象素位置，C(Mi)为与Mi对应的区域中的象素坐标集合。 用n表示当前灰度阈值，T[n]代表记为(u,v)的象素集合，g(u,v)<n， 对Mi所在的区域，其中满足条件的坐标集合Cn(Mi)可看作一幅二值图象

章毓晋(TH-EE-IE)5.4.1基本原理和步骤2. 分水岭计算步骤章5.4.1基本原理和步骤

2. 分水岭计算步骤章毓晋(TH-EE-IE)5.4.1基本原理和步骤2. 分水岭计算步骤章5.4.1基本原理和步骤

2. 分水岭计算步骤 用C[n]代表在灰度阈值为n时图象中所有满足条件的象素

C[max+1]将是所有区域的并集 C[n–1]是C[n]的子集，C[n]是T[n]的子集，所以C[n–1]又是T[n]的子集

章毓晋(TH-EE-IE)5.4.1基本原理和步骤2. 分水岭计算步骤章5.4.1基本原理和步骤

2. 分水岭计算步骤 令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中建分水岭章毓晋(TH-EE-IE)5.4.1基本原理和步骤2. 分水岭计算步骤章5.4.1基本原理和步骤

2. 分水岭计算步骤原始图阈值分割分水岭叠加轮廓章毓晋(TH-EE-IE)5.4.1基本原理和步骤2. 分水岭计算步骤章5.4.2算法改进和扩展

1. 利用标记控制分割 过分割（over-segmentation） 受图象中噪声和其它不规则结构影响 利用标记（marker）

图象中的一个连通组元 内部标记：对应目标 外部标记：对应背景（分水岭）章毓晋(TH-EE-IE)5.4.2算法改进和扩展1. 利用标记控制分割章毓晋5.4.2算法改进和扩展

1. 利用标记控制分割流程框图章毓晋(TH-EE-IE)5.4.2算法改进和扩展1. 利用标记控制分5.4.2算法改进和扩展

1. 利用标记控制分割 示例 (a)表示部分覆盖的两个区域 (b)表示经过距离变换的结果（两个局部极小值）

(c)检测出的分水线章毓晋(TH-EE-IE)5.4.2算法改进和扩展1. 利用标记控制分5.4.2算法改进和扩展

2. 分水岭算法的扩展 特征域算法示例(1) 选择合适的颜色空间，做出3-D颜色直方图(2) 将3-D颜色直方图进行反转变换(3) 在不同的颜色聚类之间建立分水岭(4) 将聚类结果映射回图象域中(5) 后处理得到最终分割图象章毓晋(TH-EE-IE)5.4.2算法改进和扩展2. 分水岭算法的扩

通信地址：北京清华大学电子工程系

邮政编码：100084

办公地址：清华大学东主楼，9区307室

办公电话：(010)62781430

传真号码：(010)62770317

电子邮件：zhangyj@

个人主页：/~zhangyujin/

实验室网：联系信息章毓晋(TH-EE-IE)通信地址：北京清华大学电子工程系联系信息章毓晋特色分割算法课件第5章特色分割算法

5.1 SUSAN检测算子

5.2 主动轮廓模型

5.3 特色的取阈值技术

5.4 分水岭分割算法章毓晋(TH-EE-IE)第5章特色分割算法 5.1 SUSAN检测算子章毓晋5.1 SUSAN边缘检测原理 USAN:UnivalueSegmentAssimilatingNucleus 核同值区：相对于模板的核，模板中有一定 的区域与它有相同的灰度章毓晋(TH-EE-IE)5.1 SUSAN边缘检测原理章毓晋(TH-EE-IE)5.1.1USAN原理 USAN的面积携带了关于图象中核象素处结 构的主要信息 当核象素处在图象中的灰度一致区域， USAN的面积会达到最大。该面积当 核处在直边缘处约为最大值的一半， 而当核处在角点处则为最大值的1/4 使用USAN面积作为特征起到了增强边缘和 角点的效果

章毓晋(TH-EE-IE)5.1.1USAN原理 USAN的面积携带了关于图象中核5.1.2SUSAN边缘检测SUSAN：最小（Smallest）核同值区 检测模板：37个象素,半径为3.4象素

章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测SUSAN：最小（Small5.1.2SUSAN边缘检测 检测对模板中的每个象素进行 得到输出的游程和（runningtotal） 边缘响应 几何阈值G=3Smax/4，其中Smax是S所能取的最大值

章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测 检测对模板中的每个象素进5.1.2SUSAN边缘检测边缘方向的确定 根据非零强度的象素确定边缘的方向 点A和B都是标准的边缘点，各落在边缘的一边 从USAN重心到模板核的矢量与边缘局部方向垂直

章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测边缘方向的确定章毓晋(T5.1.2SUSAN边缘检测边缘方向的确定 根据非零强度的象素确定边缘的方向 点C落在两个边缘的中间

USAN是沿边缘方向的细条，找最长的对称轴

章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测边缘方向的确定章毓晋(T5.1.2SUSAN边缘检测特点

有噪声时的性能较好

不需要计算微分

对面积计算中的各个值求和（积分）

非线性响应特点

易自动化实现

控制参数的选择简单

参数的任意性较小章毓晋(TH-EE-IE)5.1.2SUSAN边缘检测特点章毓晋(TH-EE-I5.2 主动轮廓模型 给定对图象中目标轮廓的一个近似（初始轮廓），主动轮廓模型可用来检测准确的轮廓 主动轮廓模型逐步改变封闭曲线的形状以逼近图象中目标的轮廓。在这个过程中，目标轮廓的各部分常用线，边缘等表示。 主动轮廓模型也称Snakes，因为在对目标轮廓的逼近过程中，封闭曲线像蛇爬行一样不断改变形状。章毓晋(TH-EE-IE)5.2 主动轮廓模型 给定对图象中目标轮廓的一个近似（初始轮5.2.1主动轮廓

主动轮廓是图象上一组排序的点的集合 处在轮廓上的点可通过解一个最小能量问题来迭代地逼近目标的边界 Eint(vi)是依赖于轮廓形状的能量函数

Eext(vi)是依赖于图象性质的能量函数章毓晋(TH-EE-IE)5.2.1主动轮廓 主动轮廓是图象上一组排序的点的5.2.2设计能量函数

1 内部能量

推动主动轮廓形状的改变 并保持轮廓上点间的距离(1) 连续能量 迫使不封闭的曲线变成直线而封闭的曲线变成圆环

(2) 膨胀力

强制轮廓在没有外来影响的情况下扩展或收缩

章毓晋(TH-EE-IE)5.2.2设计能量函数1 内部能量章毓晋(TH5.2.2设计能量函数

2 外部能量 将变形模板向感兴趣的特征吸引

构建能量函数：如目标的尺寸和形状(1) 图象灰度能量

将轮廓吸向高或低的灰度区域

(2) 图象梯度能量 将轮廓推向特征（边缘）

章毓晋(TH-EE-IE)5.2.2设计能量函数2 外部能量章毓晋(TH5.3 特色的取阈值技术

5.3.1 多分辨率阈值选取

5.3.2 类间最大交叉熵阈值

5.3.3 类内最小模糊散度阈值

5.3.4 借助过渡区选择阈值章毓晋(TH-EE-IE)5.3 特色的取阈值技术 5.3.1 多分辨率阈值选取5.3.1多分辨率阈值选取

1. 确定分割区域的类数 利用在粗分辨率下的直方图细节信息 尺度函数f(x)：低通滤波器

图象直方图H(x)的低通分量为 直方图的多分辨率小波分解表示 {S2i[H(x)],W2i[H(x)],1≤i

≤I}

章毓晋(TH-EE-IE)5.3.1多分辨率阈值选取1. 确定分割区域的类数章毓5.3.1多分辨率阈值选取

1. 确定分割区域的类数 在分辨率为21时确定初始的区域分割类数

判断直方图中独立峰的个数 独立峰应满足三个条件？ (1) 具有一定的灰度范围 (2) 具有一定的峰下面积 (3) 具有一定的峰谷差章毓晋(TH-EE-IE)5.3.1多分辨率阈值选取1. 确定分割区域的类数章毓5.3.1多分辨率阈值选取

2. 确定最优阈值(1) 用从负值变化到正值的零交叉点确定峰的起点(2) 用从正值变化到负值的零交叉点确定峰的终点(3) 用起点和终点间的最大值点确定峰的位置(4) 用前一个峰的终点和后一个峰的起点间的最小值点确定这两个峰之间谷点的位置

章毓晋(TH-EE-IE)5.3.1多分辨率阈值选取2. 确定最优阈值章毓晋(5.3.1多分辨率阈值选取

2. 确定最优阈值 分辨率增加阈值数目也增加 设在两相邻尺度2i+1和2i

所对应的阈值分别为和 在尺度2i+1的阈值对应在尺度2i的阈值 跟踪在最低分辨率一层选取的所有阈值 选取相应的最高分辨率一层的对应阈值

章毓晋(TH-EE-IE)5.3.1多分辨率阈值选取2. 确定最优阈值章毓晋(1. 交叉熵

交叉熵是一种用来度量两个概率分布 P={p1,p2,…,pN}，Q={q1,q2,…,qN}

之间信息量差异的量 对称交叉熵是交叉熵的对称形式5.3.2类间最大交叉熵阈值章毓晋(TH-EE-IE)1. 交叉熵5.3.2类间最大交叉熵阈值章毓晋(TH-2. 类间最大交叉熵 目标与背景应有尽可能大的差异 整幅图象的类间差异性 搜索获得基于类间最大交叉熵的最优阈值5.3.2类间最大交叉熵阈值章毓晋(TH-EE-IE)2. 类间最大交叉熵5.3.2类间最大交叉熵阈值章毓晋1. 过渡区和有效平均梯度5.3.4借助过渡区选择阈值章毓晋(TH-EE-IE)1. 过渡区和有效平均梯度5.3.4借助过渡区选择阈值章2. 有效平均梯度的极值点和过渡区边界5.3.4借助过渡区选择阈值章毓晋(TH-EE-IE)2. 有效平均梯度的极值点和过渡区边界5.3.4借助过5.4分水岭分割算法

分水岭（watershed，也称分水线/水线）

把图象看成3-D地形的表示，即2-D的地基 （对应图象空间）加上第3维的高度（对应 图象灰度）

计算过程是串行的，得到的是目标的边界 5.4.1 基本原理和步骤 5.4.2 算法改进和扩展章毓晋(TH-EE-IE)5.4分水岭分割算法 分水岭（watershed5.4.1基本原理和步骤

1. 分水岭 建立不同目标间的分水岭谷底孔分水岭章毓晋(TH-EE-IE)5.4.1基本原理和步骤1. 分水岭谷底孔分水5.4.1基本原理和步骤

2. 分水岭计算步骤 待分割图象f(x,y)，其梯度图象为g(x,y) 用M1,M2,…,MR表示g(x,y)中各局部极小值的象素位置，C(Mi)为与Mi对应的区域中的象素坐标集合。 用n表示当前灰度阈值，T[n]代表记为(u,v)的象素集合，g(u,v)<n， 对Mi所在的区域，其中满足条件的坐标集合Cn(Mi)可看作一幅二值图象

章毓晋(TH-EE-IE)5.4.1基本原理和步骤2. 分水岭计算步骤章5.4.1基本原理和步骤

2. 分水岭计算步骤章毓晋(TH-EE-IE)5.4.1基本原理和步骤2. 分水岭计算步骤章5.4.1基本原理和步骤

2. 分水岭计算步骤 用C[n]代表在灰度阈值为n时图象中所有满足条件的象素

C[max+1]将是所有区域的并集 C[n–1]是C[n]的子集，C[n]是T[n]的子集，所以C[n–1]又是T[n]的子集

章毓晋(TH-EE-IE)5.4.1基本原理和步骤2. 分水岭计算步骤章5.4.1基本原理和步骤

2. 分水岭计算步骤 令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