第七章 图像分割版权所有,1997 (c) Dale Carnegie & Associates,Inc.
CHAPTER 7
IMAGE SEGMENTATION
§ 1 概述（分割的定义、图像的特征等）
§ 2 并行边界技术
§ 3 串行边界技术
§ 4 并行区域技术
§ 5 串行区域技术
§ 7.1 概述
§ 7.1.1 图像分割的定义令集合 R代表整个图像区域，对 R的分割可看作将 R分成若干个满足以下 5个条件的非空的子集（子区域） R1,R2,… R n 。
1） ∪ Ri = R；（ i=1,…,n ）； 整个图像不重叠
2） 对所有的 i和 j,i≠j,有 Ri ∩Rj =? ； 互不重叠；
3）对 i=1,…,n,有 P(Ri) = TRUE；
P(Ri)是对 Ri中元素的逻辑谓词； TRUE表示相同特性；
4） 对 i≠j,有 P(( Ri ∪ Rj )) = FLASE； 区域不同，特性不同；
5） 对 i=1,…,n,Ri是连通的区域；
图像中，区域内部的像素一般具有相似性；区域之间的边界上具有灰度不连续性；因此，图像分割的方法出现了基于边界（ Border
） 的方法和基于区域（ Range） 的方法；
又按处理策略可以分类为并行 Parallel算法和串行 Serial算法；
所以，综合起来有 PB,PR,SB,SR四种方法。
§ 7.1.2 图像的特征
§ 7.1.2 图像的特征图像的特征指图像场中的原始特性（或属性）、自然特征、人为特征等。
一、幅度特征（基本特征）
如平均幅度、各种变换形成的变换系数的幅度等；
二、直方图特征直方图的形状可给出图像特性的许多信息；
如分布狭窄的直方图反映图像的对比度很低；
双峰形的直方图反映图像中存在两个不同灰度区；
§ 7.1.2 图像的特征（续 1）
三、变换系数特征（频域中的变换系数）
把变换系数进行累计，可突出某些图像特征；
设 M(u,v) 为某变换的平方，则条带、环、扇区等均可用其表达；
四、线条和角点特征
线条的特征 截面上的幅度分布凸凹变化反映了线条的特征；
可以用不同的模板检测出线条；
角点的特征 角点的幅值与其邻域的幅度有显著的不同；
若能从图像中提取线条和角点，则可以实现压缩，便于描述、推理等；
§ 7.1.2 图像的特征（续 2）
五、灰度边缘特征
边缘：图像灰度级的局部不连续性，未闭合的边界；
边界：在切线方向成大范围不连续线段；反映了图像中物体或区域所占的物理限度；
边缘检测是图像处理中的一个重要内容；
六、彩色边缘特征
定义一：只要在亮度场中存在边缘，便是彩色边缘；
定义二：在 RGB三个分量中检测到某处存在边缘，就判定是一个彩色边缘；
定义三：用三个分量的矢量表示的彩色像点，如果两点的矢量差超过某阈值，则存在一个彩色边缘；
§ 7.1,2 图像的特征（续 3） 量
七、纹理特征
纹理包括自然纹理和人工纹理；
自然纹理 具有重复性排列现象的自然景象，无规则；
人工纹理 符号（线、点、字母等）排列组成，有规则；
检测纹理的边界、纹理的粗糙度等，
如空间重复周期大，纹理粗；空间重复周期小，纹理细；
分析纹理 采用结构模型 当纹理基元的分布较规律时
采用统计模型 对自然纹理，规律性不强的纹理
§ 7.2 并行边界技术
§ 7.2.1 边缘检测边缘检测是所有基于边界的分割方法的第一步；
因为边缘是灰度值不连续的结果，利用求导数（差分）可检测；
空域微分算子已在图像增强中介绍过；
借助空域微分算子，通过模板卷积完成边缘检测；
一,罗伯特交叉算子,二个像素之差值；
优点：抽取轮廓效果较好；
二,蒲瑞维特算子 (Prewitt),采用曲面逆合法分割边界导出；
二行 (列 )平均后再求差分，可抑制噪声；
§ 7.2.1 边缘检测 (续 1)
三、索贝尔算子
二行 (列 )加权和求平均后再求差分；
由于引入了平均因素，对噪声有一定平滑作用；
四、拉普拉斯算子
主要用于已知边缘像素后确定该像素是在图像的暗区或明区一边；
对突出孤点、线端及边界的效果明显；
能对任何走向的边界线和直线进行边缘提取；
五、综合正交算子
即可检测边缘，又可检测直线 ;
§ 7.2.2 边界闭合
一、边界闭合
边界闭合是将孤立或小线段的边缘像素连接起来，组成区域；
二,实现方法
如果像素 (s,t)在像素 (x,y)的邻域且它们的梯度幅值和梯度方向分别满足以下 2 个条件，就可连接起来；
条件 1,| ▽ f(x,y) - ▽ f(s,t) | ≤ T,T为幅度阈值；
条件 2,|? (x,y) -? (s,t) | ≤ A,A为角度阈值；
对所有边缘像素都进行上述判断和连接，就能得到闭合的边界。
§ 7.2.3 哈夫 Hough变换一、功能哈夫变换利用图像全局特性，实现边缘像素连接，区域闭合；
还适合检测某些已知形状的曲线，确定边界到亚像素精度；
设给定图像中的 n个点，要从中确定连在同一条直线上的点的子集，可看作已检测出一条直线上的若干个点，要求出它们所在的直线。
二、哈夫变换的方法基本思想是运用点 -线对偶性（ duality）；
在图像空间里，所有过点 (x,y)的直线都满足方程
y=px+q； 式中,p为斜率,q为截距；移项得 q = -px + y ；
前式为 XY空间过 (x,y)的一条直线，后式为 PQ空间过点 (p,q)的一条直线；
§ 7.2.3 哈夫 Hough变换 (续 1)
如图，在 XY空间一条直线上的两个点，
在 PQ空间为相交于点 (p’,q’)的 2条直线
Y? (xj,yj) Q q=-pxi+yi
(xi,yi) q=-pxj+yj
X P
由此可见,XY空间中过 (xi,yi)和 (xj,yj) 直线上的每个点都对应在参数空间 PQ里的一条直线，均相交于 (p’,q’),即点 -线对偶性：
图像空间中共线的点对应参数空间里相交的线，
反之，参数空间中相交于同一个点的所有直线，在图像空间都有共线的点与之对应；
§ 7.2.3 哈夫 Hough变换 (续 2)
三、哈夫变换的实现根据点 -线对偶性把检测问题转换到参数空间，通过简单的累加统计完成检测任务；
1,在参数空间 PQ里建立一个 2D累加数组 A(p,q),初始化为 0；
2,对 XY空间中的每一个给定点，让 p 在 [ pmin,pmax]区间取所有可能的值，按 q = -px + y 求出 q，
3,根据 p,q取整数值在 A(p,q)处累加，累加结果可知多少点是共线的,(p,q)的值也给出了直线方程的参数；
几点说明,[ pmin,pmax]是预期的斜率取值范围；
精度取决于累加数组的尺寸；
Q
A(p,q)
pmin Pmax
§ 7.2.3 哈夫 Hough变换 (续 3)
四、检测二次曲线采用直线的极坐标方程,?=x cos? + y sin? ；
图像空间中的点，对应参数空间的一条正弦曲线，即点 -正弦曲线对偶性：检测共点的线是在参数空间里检测正弦曲线的交点；
方法：让?取遍轴上所有可能的值，算出所对应的?，再根据?和
的值对累加数组 A累加；
优点：通过顶点（端点）的对应曲线，可得到任意其它点的变换范围；
五、曲线检测满足解析式 f(x,c)=0形式的各类曲线都可用 Hough变换检测。
§ 7.3 串行边界技术串行边界技术是 1）先检测边缘,2）再串行连接成闭合边界；
一、图搜索类似数据结构中最小路径解的工程问题；
方法：将边界点和边界段用图结构表示，通过在图中进行搜索对应最小代价的通路找到闭合路径（边界）；
二,动态规划解决图搜索方法中最小代价计算量大的问题；
将边缘点的检测和最小代价的计算结合起来，动态搜索，提高搜索速度；
§ 7.4 并行区域技术
§ 7.4.1 思路和实现方法一、思路：利用像素的特征，进行阈值分割；
条件：图像是由具有单峰灰度分布的目标和背景组成，目标的相邻像素的灰度值是高度相关的；但在目标和背景交界处两边的像素灰度值差别很大，
直方图上是两个单峰直方图混合而成的。
阈值分割方法的关键问题是选取合适的阈值；
二、实现方法分直方图门限、递归门限、多门限分割方法，及单 (多 )阈值分割方法；
阈值一般形式 T = T [x,y,f(x,y),p(x,y)]； f (x,y)是灰度值,p(x,y)是该点邻域附近的性质；
分类 1）仅根据 f(x,y)来选取阈值，全局阈值；
2）根据 f(x,y)和 p(x,y)选取阈值，局部阈值；灰度加性质
3） 根据 x,y,f (x,y) 和 p (x,y)选取阈值，动态阈值；与坐标有关；
§ 7.4.2 阈值选取方法一、依赖像素的阈值选取选取直方图中的某一灰度值作为分割阈值；
1,将极小值点作为阈值；
2,最优阈值（取二个区域中平均灰度值的中值作为阈值）；
二、依赖区域的阈值选取利用像素邻域的局部性质，给具有低梯度值的像素加权大一些，变换原直方图以得到一个新的直方图，让谷更低，峰谷差别加大，容易检测。
三、依赖坐标的阈值选取只用一个固定的全局阈值对整幅图进行分割，分割效果欠佳；
采用与坐标有关的一系列子阈值（动态阈值），变化阈值法；
1,将图像分解成一系列子图像，子图像可相邻或重叠，如 50%重叠；
2,对每个子图像计算一个阈值（直方图 -阈值，插值得到所有子图像的阈值）；
3,对图像进行分割（每个像素与对应的阈值相比较实现分割）。
§ 7.5 串行区域方法一、区域生长法基本思想：将具有相似性质的像素集合起来构成区域；
步骤,1,先对要分割的区域找一个种子像素生长的起点；
2,将种子像素的邻域中具有相同和相似性质的像素合并到种子的区域中，赋予一个标志 L；
3,将新像素当作新的种子像素继续进行上面的过程，
生成一个区域；
需解决 3个问题,1,种子，选择很重要；
2,准则，相同和相似准则；
3,停止条件，不能无限循环；
§ 7.5 串行区域方法 (续 1)
二、分裂合并法
基本思想：从整幅图像开始，通过不断分裂，得到各个区域；
常用四叉树或金字塔式分割技术；
将图像分成互不重叠的小区域，如 16*16的块，
1,对任一个区域 Ri,不满足条件时，将其分裂成不重叠的 4等份；
2,如果相邻 2个区域，满足合并的条件，就将它们合并起来；
3,进一步分裂或合并，直到像素级；
这是一个递归算法；同样存在分裂和合并准则问题，停止问题。
CHAPTER 7
IMAGE SEGMENTATION
§ 1 概述（分割的定义、图像的特征等）
§ 2 并行边界技术
§ 3 串行边界技术
§ 4 并行区域技术
§ 5 串行区域技术
§ 7.1 概述
§ 7.1.1 图像分割的定义令集合 R代表整个图像区域，对 R的分割可看作将 R分成若干个满足以下 5个条件的非空的子集（子区域） R1,R2,… R n 。
1） ∪ Ri = R；（ i=1,…,n ）； 整个图像不重叠
2） 对所有的 i和 j,i≠j,有 Ri ∩Rj =? ； 互不重叠；
3）对 i=1,…,n,有 P(Ri) = TRUE；
P(Ri)是对 Ri中元素的逻辑谓词； TRUE表示相同特性；
4） 对 i≠j,有 P(( Ri ∪ Rj )) = FLASE； 区域不同，特性不同；
5） 对 i=1,…,n,Ri是连通的区域；
图像中，区域内部的像素一般具有相似性；区域之间的边界上具有灰度不连续性；因此，图像分割的方法出现了基于边界（ Border
） 的方法和基于区域（ Range） 的方法；
又按处理策略可以分类为并行 Parallel算法和串行 Serial算法；
所以，综合起来有 PB,PR,SB,SR四种方法。
§ 7.1.2 图像的特征
§ 7.1.2 图像的特征图像的特征指图像场中的原始特性（或属性）、自然特征、人为特征等。
一、幅度特征（基本特征）
如平均幅度、各种变换形成的变换系数的幅度等；
二、直方图特征直方图的形状可给出图像特性的许多信息；
如分布狭窄的直方图反映图像的对比度很低；
双峰形的直方图反映图像中存在两个不同灰度区；
§ 7.1.2 图像的特征（续 1）
三、变换系数特征（频域中的变换系数）
把变换系数进行累计，可突出某些图像特征；
设 M(u,v) 为某变换的平方，则条带、环、扇区等均可用其表达；
四、线条和角点特征
线条的特征 截面上的幅度分布凸凹变化反映了线条的特征；
可以用不同的模板检测出线条；
角点的特征 角点的幅值与其邻域的幅度有显著的不同；
若能从图像中提取线条和角点，则可以实现压缩，便于描述、推理等；
§ 7.1.2 图像的特征（续 2）
五、灰度边缘特征
边缘：图像灰度级的局部不连续性，未闭合的边界；
边界：在切线方向成大范围不连续线段；反映了图像中物体或区域所占的物理限度；
边缘检测是图像处理中的一个重要内容；
六、彩色边缘特征
定义一：只要在亮度场中存在边缘，便是彩色边缘；
定义二：在 RGB三个分量中检测到某处存在边缘，就判定是一个彩色边缘；
定义三：用三个分量的矢量表示的彩色像点，如果两点的矢量差超过某阈值，则存在一个彩色边缘；
§ 7.1,2 图像的特征（续 3） 量
七、纹理特征
纹理包括自然纹理和人工纹理；
自然纹理 具有重复性排列现象的自然景象，无规则；
人工纹理 符号（线、点、字母等）排列组成，有规则；
检测纹理的边界、纹理的粗糙度等，
如空间重复周期大，纹理粗；空间重复周期小，纹理细；
分析纹理 采用结构模型 当纹理基元的分布较规律时
采用统计模型 对自然纹理，规律性不强的纹理
§ 7.2 并行边界技术
§ 7.2.1 边缘检测边缘检测是所有基于边界的分割方法的第一步；
因为边缘是灰度值不连续的结果，利用求导数（差分）可检测；
空域微分算子已在图像增强中介绍过；
借助空域微分算子，通过模板卷积完成边缘检测；
一,罗伯特交叉算子,二个像素之差值；
优点：抽取轮廓效果较好；
二,蒲瑞维特算子 (Prewitt),采用曲面逆合法分割边界导出；
二行 (列 )平均后再求差分，可抑制噪声；
§ 7.2.1 边缘检测 (续 1)
三、索贝尔算子
二行 (列 )加权和求平均后再求差分；
由于引入了平均因素，对噪声有一定平滑作用；
四、拉普拉斯算子
主要用于已知边缘像素后确定该像素是在图像的暗区或明区一边；
对突出孤点、线端及边界的效果明显；
能对任何走向的边界线和直线进行边缘提取；
五、综合正交算子
即可检测边缘，又可检测直线 ;
§ 7.2.2 边界闭合
一、边界闭合
边界闭合是将孤立或小线段的边缘像素连接起来，组成区域；
二,实现方法
如果像素 (s,t)在像素 (x,y)的邻域且它们的梯度幅值和梯度方向分别满足以下 2 个条件，就可连接起来；
条件 1,| ▽ f(x,y) - ▽ f(s,t) | ≤ T,T为幅度阈值；
条件 2,|? (x,y) -? (s,t) | ≤ A,A为角度阈值；
对所有边缘像素都进行上述判断和连接，就能得到闭合的边界。
§ 7.2.3 哈夫 Hough变换一、功能哈夫变换利用图像全局特性，实现边缘像素连接，区域闭合；
还适合检测某些已知形状的曲线，确定边界到亚像素精度；
设给定图像中的 n个点，要从中确定连在同一条直线上的点的子集，可看作已检测出一条直线上的若干个点，要求出它们所在的直线。
二、哈夫变换的方法基本思想是运用点 -线对偶性（ duality）；
在图像空间里，所有过点 (x,y)的直线都满足方程
y=px+q； 式中,p为斜率,q为截距；移项得 q = -px + y ；
前式为 XY空间过 (x,y)的一条直线，后式为 PQ空间过点 (p,q)的一条直线；
§ 7.2.3 哈夫 Hough变换 (续 1)
如图，在 XY空间一条直线上的两个点，
在 PQ空间为相交于点 (p’,q’)的 2条直线
Y? (xj,yj) Q q=-pxi+yi
(xi,yi) q=-pxj+yj
X P
由此可见,XY空间中过 (xi,yi)和 (xj,yj) 直线上的每个点都对应在参数空间 PQ里的一条直线，均相交于 (p’,q’),即点 -线对偶性：
图像空间中共线的点对应参数空间里相交的线，
反之，参数空间中相交于同一个点的所有直线，在图像空间都有共线的点与之对应；
§ 7.2.3 哈夫 Hough变换 (续 2)
三、哈夫变换的实现根据点 -线对偶性把检测问题转换到参数空间，通过简单的累加统计完成检测任务；
1,在参数空间 PQ里建立一个 2D累加数组 A(p,q),初始化为 0；
2,对 XY空间中的每一个给定点，让 p 在 [ pmin,pmax]区间取所有可能的值，按 q = -px + y 求出 q，
3,根据 p,q取整数值在 A(p,q)处累加，累加结果可知多少点是共线的,(p,q)的值也给出了直线方程的参数；
几点说明,[ pmin,pmax]是预期的斜率取值范围；
精度取决于累加数组的尺寸；
Q
A(p,q)
pmin Pmax
§ 7.2.3 哈夫 Hough变换 (续 3)
四、检测二次曲线采用直线的极坐标方程,?=x cos? + y sin? ；
图像空间中的点，对应参数空间的一条正弦曲线，即点 -正弦曲线对偶性：检测共点的线是在参数空间里检测正弦曲线的交点；
方法：让?取遍轴上所有可能的值，算出所对应的?，再根据?和
的值对累加数组 A累加；
优点：通过顶点（端点）的对应曲线，可得到任意其它点的变换范围；
五、曲线检测满足解析式 f(x,c)=0形式的各类曲线都可用 Hough变换检测。
§ 7.3 串行边界技术串行边界技术是 1）先检测边缘,2）再串行连接成闭合边界；
一、图搜索类似数据结构中最小路径解的工程问题；
方法：将边界点和边界段用图结构表示，通过在图中进行搜索对应最小代价的通路找到闭合路径（边界）；
二,动态规划解决图搜索方法中最小代价计算量大的问题；
将边缘点的检测和最小代价的计算结合起来，动态搜索，提高搜索速度；
§ 7.4 并行区域技术
§ 7.4.1 思路和实现方法一、思路：利用像素的特征，进行阈值分割；
条件：图像是由具有单峰灰度分布的目标和背景组成，目标的相邻像素的灰度值是高度相关的；但在目标和背景交界处两边的像素灰度值差别很大，
直方图上是两个单峰直方图混合而成的。
阈值分割方法的关键问题是选取合适的阈值；
二、实现方法分直方图门限、递归门限、多门限分割方法，及单 (多 )阈值分割方法；
阈值一般形式 T = T [x,y,f(x,y),p(x,y)]； f (x,y)是灰度值,p(x,y)是该点邻域附近的性质；
分类 1）仅根据 f(x,y)来选取阈值，全局阈值；
2）根据 f(x,y)和 p(x,y)选取阈值，局部阈值；灰度加性质
3） 根据 x,y,f (x,y) 和 p (x,y)选取阈值，动态阈值；与坐标有关；
§ 7.4.2 阈值选取方法一、依赖像素的阈值选取选取直方图中的某一灰度值作为分割阈值；
1,将极小值点作为阈值；
2,最优阈值（取二个区域中平均灰度值的中值作为阈值）；
二、依赖区域的阈值选取利用像素邻域的局部性质，给具有低梯度值的像素加权大一些，变换原直方图以得到一个新的直方图，让谷更低，峰谷差别加大，容易检测。
三、依赖坐标的阈值选取只用一个固定的全局阈值对整幅图进行分割，分割效果欠佳；
采用与坐标有关的一系列子阈值（动态阈值），变化阈值法；
1,将图像分解成一系列子图像，子图像可相邻或重叠，如 50%重叠；
2,对每个子图像计算一个阈值（直方图 -阈值，插值得到所有子图像的阈值）；
3,对图像进行分割（每个像素与对应的阈值相比较实现分割）。
§ 7.5 串行区域方法一、区域生长法基本思想：将具有相似性质的像素集合起来构成区域；
步骤,1,先对要分割的区域找一个种子像素生长的起点；
2,将种子像素的邻域中具有相同和相似性质的像素合并到种子的区域中，赋予一个标志 L；
3,将新像素当作新的种子像素继续进行上面的过程，
生成一个区域；
需解决 3个问题,1,种子，选择很重要；
2,准则，相同和相似准则；
3,停止条件，不能无限循环；
§ 7.5 串行区域方法 (续 1)
二、分裂合并法
基本思想：从整幅图像开始，通过不断分裂，得到各个区域；
常用四叉树或金字塔式分割技术；
将图像分成互不重叠的小区域，如 16*16的块，
1,对任一个区域 Ri,不满足条件时，将其分裂成不重叠的 4等份；
2,如果相邻 2个区域，满足合并的条件，就将它们合并起来；
3,进一步分裂或合并，直到像素级；
这是一个递归算法；同样存在分裂和合并准则问题，停止问题。
