第七章图像分割

东北大学信息学院陈东岳魏颖图像处理分析与识别7.1图像分割概述7.2图像特征概述7.3阈值法7.4区域法7.5聚类法7.6边界法7.7图论法第七章图像分割

7.1图像分割概述图像分割在数字图像处理技术以及认知系统中的角色

目的：根据目标对象在图像空间中的分布对图像进行分解，得到一些对图像理解更有意义的图像区域。定义：令集合R代表整个图像区域，对R的图像分割可以看作是将R分成N个满足以下条件的非空子集R1，R2，….，RN：图像分割与图像标记的关系图像分割可以看做是图像标记(Image

labeling)的一种特例。图像分割的核心问题是如何为像素f(x,

y)打上准确的离散化标签g(x,

y)。7.1图像分割概述

f

(x,

y)：图像特征

g

(x,

y)：图像标号依据图像特征与空间策略的分类方法

7.1图像分割概述基于方法论的分类阈值法区域法边界法聚类法分类法图论法概率模型法7.1图像分割概述医学影像计算机辅助诊断7.1图像分割概述——应用光学字符识别7.1图像分割概述——应用工件视觉检测7.1图像分割概述——应用遥感图像处理7.1图像分割概述——应用自然图像理解7.1图像分割概述——应用亮度直方图变换系数边缘纹理关键点7.2

图像特征概述亮度空间连续性，稠密性，直观，敏感性直方图统计特征，抗线性几何变换变换系数频域统计特征，提供一种完全不同的视角边缘符合视觉习惯，是形状信息的基础纹理局部不连续性和全局相似性的统一关键点鲁棒局部特征，抗变形能力强，适用于匹配7.2图像特征概述思路将分割问题视为面向每一个像素的分类问题，通常使用简单的阈值不等式判断像素的类别。条件待分割区域与背景区域在像素级特征上存在明显的差异，而两个区域内部像素在统计上各自具有较强的相似性。从特征直方图上看，具有明显的双峰分布的图像比较适合使用阈值法进行分割7.3阈值法——全局阈值法阈值法分类全局阈值法(Global

thresholding)自适应阈值法(Adaptive

thresholding)带阈值法(Band

thresholding)多阈值法(Multi-thresholding)7.3阈值法——全局阈值法数学模型7.3阈值法——全局阈值法如何确定阈值T？迭代法大津法(OTSU)最优阈值法最大熵法众数法矩不变法……7.3阈值法——全局阈值法迭代阈值法

1）选取一个的初始估计值T；

2）用T分割图像。这样便会生成两组像素集合：G1由所有灰度值大于T的像素组成，而G2由所有灰度值小于或等于T的像素组成。

3）对G1和G2中所有像素计算平均灰度值u1和u2。

4）计算新的阈值：T=1/2(u1+u2)。

重复步骤（2）到（4），直到T值更新后产生的偏差小于一个事先定义的参数T0。从优化的角度看，迭代阈值法的目标函数：7.3阈值法——全局阈值法大津法（OTSU）寻找使类间离散度最大化的阈值T类间离散度的数学定义P0(T),

P1(T):

两类像素各自在总像素数量中所占的比例；u0(T),

u1(T):

两类像素各自的特征(例如亮度)均值；u:

图像中所有像素的均值Matlab函数：T

=

graythresh(I)7.3阈值法——全局阈值法最优阈值法将目标和背景的像素特征分布看做是两个相互独立的随机变量，则整个图像的像素特征概率分布函数可以描述为：当给定一个阈值T，假设前景较亮而背景较暗，根据概率模型可以估计出背景被错判为前景的概率Eb(T)和背景被错判为前景的概率Ef(T)。两者的概率加权和即为总的错误概率E(T)，使得总错误概率最小的阈值即为最优阈值7.3阈值法——全局阈值法7.3阈值法——全局阈值法7.3阈值法——全局阈值法7.3阈值法——全局阈值法最优阈值法为了求解方程：

必须对背景和前景的概率分布函数以及事件概率有准确的估计。一般假设前景和背景都服从高斯分布，则全部未知量共5个，分别是前景和背景各自的均值和方差，以及前景的事件概率Po。以上5个未知量一般根据最小均方误差原则进行估计。即令估计得到的概率密度函数参数方程与图像直方图的均方误差最小化。7.3阈值法——全局阈值法全局阈值法设计与实现的一般性原则根据图像灰度分布的统计特性建立一个关于阈值T的评价函数，通过对该函数的优化获取全局阈值。评价函数迭代法：两类中心的均值与阈值的差（误差概率的特例）；大津法：类间离散度；最优阈值法：错误概率；众数法：灰度极小值；最大熵法：两类的熵的和；矩不变法：分类后数据的前4阶矩的变化值。7.3阈值法——全局阈值法众数法T=0.2549最优阈值法T=0.11482迭代阈值法T=0.3652大津法T=0.3626最大熵法T=0.1177矩不变法T=0.4667算法特点总结阈值法——全局阈值法众数法最优阈值法迭代阈值法Otsu法KSW法/最大熵法矩不变法复杂度一般复杂简单简单简单复杂计算量较小大较小较小较小较大抗噪能力差好较好一般较差一般效果理想度较差好一般较好好一般从一个例子开始全局阈值法无法解决目标与背景的灰度范围过度重叠的情况（该情况通常由不均匀的光照所引起）7.3阈值法——自适应阈值法思路将原图像分割为多块子图像。将每一个存在边缘的子图像作为一整张图像使用全局阈值法；将不存在明显边缘的子图像按照其平均灰度，判别为目标或背景7.3阈值法——

自适应阈值法三个问题 1）如何确定一个子图像内是否存在边缘 2）如何处理块状效应 3）对于平坦区域灰度均值的判别能否保证准确解决方案

1）图像预处理（去噪，去光照） 2）采用具有重叠区域的图像分块策略 3）根据子图像的方差、灰度直方图的双峰特性、梯度直方图等统计信息判别其是否包含边缘区域。 4）根据包含边缘区域的阈值对平坦区域的阈值进行插值补足。7.3阈值法——

自适应阈值法优点算法简单，速度快，直接形成闭合区域。缺点：适应性差，抗噪能力差，忽略了像素之间的空间联系。切记没有一种阈值法是“万能”的，解决问题的关键是如何灵活的选取和搭配最适合该问题的方法。7.3阈值法——

自适应阈值法思路综合考虑待分割区域内部像素的特征同质性和近邻性，通过反复地将相邻且特征相似的像素或区域纳入同一分割区域，最终实现分割。两种区域分割算法框架区域生长法区域分裂与合并7.4区域法（region-basedapproach）基本思想（步骤）1.寻找一组生长点，可以是单个像素，也可以是某个小区域。可以是人工指定，也可以设计专门的初始化算法。2.搜索生长点的邻域，比较邻域像素与生长点像素的特征相似性，若满足合并条件，则合并为同一区域，形成新的生长点。3.重述步骤2直到没有新的生长点出现。7.4区域法——区域生长法7.4区域法——

区域生长法关键问题1）选择一组能正确代表所需区域的生长点像素； 2）选择有意义的特征，也就是确定在生长过程中将相邻区域像素包括进来的； 3）确定相似性准则，即获取生长过程停止的准则。基本概念 1）特征相似性：生长或合并区域的准则的依据与基础，如灰度差； 2）像素相邻性：生长或合并区域时所取的邻域方式； 3）生长准则：如何利用特征相似性与特征相邻性进行区域生长与合并的方式，如单一型，质心型混合型等。7.4区域法——区域生长法Matlab实现Matlab自带的形态学处理工具箱函数IPT工具箱函数7.4区域法——区域生长法7.4区域法——

区域生长法原始图像阈值图像种子图像分割结果基本的区域生长法的优缺点这种方法简单，但如果区域之间的边缘灰度变化很平缓或边缘交于一点时，如图，两个区域会合并起来。区域生长法的改进原则区域生长的算法核心是生长准则，所有针对区域生长法的改进均着眼于如何修改生长准则几种基本的改进方法双阈值法：在生长准则中加入一个阈值条件，即新生长区域的灰度与初始种子点的灰度的差应小于某一个阈值；质心法：对基本方法的阈值进行改变，即新生长区域的灰度与已经生长得到的区域的平均灰度值的差应小于某一个阈值；混合型：对生长过程的顺序进行修改，即每次只生长与相邻像素差值（或与种子点灰度的差值）最小的像素，但需要制定结束条件7.4区域法——区域生长法区域1区域2灰度区域1区域2（a）平缓的边缘（b）边缘的缝隙边缘对区域扩张的影响思路首先将图像分割成一系列任意不相交的区域，然后将他们进行合并或分裂得到各个区域。四叉树是该方法中最常用到空间结构7.4区域法——区域分裂与合并分裂(合并)条件的数学描述判别函数P(R)P(R)是一个判别函数，输出为True

or

False

(1或0)在分裂过程中，如果P(R)为True，则认为区域R不需要进一步分割；否则，继续分割。在合并过程中，如果合并后的区域满足P(R)为true，则执行合并；否则不执行。7.4区域法——区域分裂与合并7.4区域法——

区域分裂与合并区域分割与合并基本算法步骤1）从整幅图像开始，如果P(Ri)=FALSE，就将图像分割为4个区域；2）对分割后得到的区域，如果依然有P(Ri)=FALSE，则将Ri继续分为四个区域；依此类推，直到没有任何区域需要继续分割为止。3）对相邻的两个区域Ri和Rj，如果满足P(RiURj)=TRUE，则进行合并。当再也没有可以进行合并的区域，则分割操作完成。设计区域分裂与合并算法的关键在于设计P(R)例子：下图为天鹅星座环x射线频段图像，对改图的分割目的是获取环绕致密中心的稀疏环，该部分的最少有两个特征是与背景不同的，即其局部方差C(Ri)与局部均值M(Ri)，因此算法设计如下：7.4区域法——区域分裂与合并优点考虑了像素特征的空间相关性，能够有效筛除一些背景干扰。提供了人机交互接口和自主分割框架的结合通道。分割结果具有比较清晰的边缘。相对于阈值法具有更自由的参数调节空间。缺点终止准则的设计比较困难。区域生长法过于依赖种子点选择的合理性。生长和合并过程中的串行顺序对最终结果有显著影响。计算时间明显长于阈值法。7.4区域法——总结思路将像素投射到特征空间成为样本点，根据样本点在特征空间的分布特性进行聚类。将类别标号投射回图像空间作为像素的标号，进而实现分割。哪些视觉元素容易被聚为同一类（1F2S2P4C）Proximity

:空间相邻性Similarity

:

特征相似性Common

fate

:运动同向性Common

region

:区域归属Closure

:

趋向于闭合Parallelism

:

平行性Symmetry

:

对称性Continuity

:

连续性

Familiar

pattern

:组合后的熟悉程度

7.5聚类法(Clustering-basedapproach)代表性的聚类分割算法合成聚类与分裂聚类K-means算法模糊C均值聚类Meanshift算法SLIC超像素7.5聚类法(Clustering-basedapproach)合成聚类

（AgglomerativeClustering）分裂聚类（Divisive

Clustering）7.5聚类法——合成聚类与分裂聚类每个样本点作为一个独立的簇。while（聚类结果不满足终止条件）

将两个具有最小簇间距离的簇合并为一个簇

更新簇间距离表。end将所有样本作为一个簇while（聚类结果不满足终止条件）

for所有已经存在的簇

将当前簇分为两个簇，使得簇间距离达到最大。

endendK-means的基本思想将图像中所有的元素视为来源于k个类别，根据样本到类别中心的特征距离判断像素的归属，通过迭代更新的方式在逼近类别模型参数的同时实现像素的分类。K-means的步骤1.为像素选择特征向量（比如YUV色彩特征），将所有像素映射为特征空间中的样本点。2.选择类别数量k，在特征空间随机初始化k个类的中心。3.根据样本点到类中心的距离，为每一个样本点选择距离最近类作为类别标号4.根据新的分类结果，以同一类样本点的特征均值更新类中心。5.重复步骤3-4，直到类中心的位置不再发生变化。7.5聚类法

——

K-meansK-means的实现Matlab工具箱函数像素色彩空间的选择应尽量去除光照分量的影响，对于一般的自然彩色图像，推荐使用LAB，YUV或YCbCr应采用适当的基于图像形态学操作的后处理算法，也可适当结合区域分割算法以获得关于目标的完整区域和轮廓。7.5聚类法

——

K-means7.5聚类法

——

K-means思路将聚类问题中的类定义为模糊集合，用模糊集的隶属度函数定量描述样本点与类之间的从属关系，并通过寻找使目标函数最小化的隶属度函数，实现聚类。算法关键点隶属度函数的数学定义模糊类中心的更新7.5聚类法

——模糊C均值聚类变量定义数据集X={x1,

x2,

…

,

xn}，c个模糊类，样本xk对第i类的模糊隶属度为uik，隶属度矩阵U={uik}，第i类的类中心为vi，聚类中心矩阵为V={v1,

v2,

…,

vc}建立基于隶属度矩阵U和聚类中心矩阵V的目标函数Jm(U,V)。7.5聚类法

——模糊C均值聚类模糊C均值聚类算法步骤1.初始化聚类中心矩阵V2.计算隶属度矩阵U3.更新聚类中心V4.重复步骤(2)、(3)直至类中心收敛。7.5聚类法

——模糊C均值聚类7.5聚类法

——模糊C均值聚类思路将特征空间的聚类问题转化为概率密度函数估计，认为概率密度局部极大值对应某一类的类中心，而能够通过均值漂移收敛于该局部极大值的样本点将被分为该类。特征空间中的类=

概率密度函数的局部极大值？7.5聚类法

——

meanshift7.5聚类法

——

meanshift假设

:样本点来源于某种潜在的概率密度函数假设的潜在PDF真实的样本点数据点的密度暗示了概率密度函数!彩色图像的特征空间7.5聚类法

——

meanshiftL*u*vspacerepresentation样本点将被吸引到不同的mode2D(L*u)色彩空间Meanshift聚类结果理解meanshift分割方法的要点定义在特征空间上的概率密度函数估计。聚类结果取决于该样本点收敛于哪个一个mode，而不是距离哪个mode更近。如何让每一个样本点以迭代的方式找到它的mode核心迭代公式g函数7.5聚类法

——

meanshiftDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionDistributionofidenticalbilliardballsRegionofinterestCenterofmassObjective:FindthedensestregionMeanshift聚类算法步骤对每个样本点xi：应用均值漂移，从y(0)

=

xi开始，直到收敛到某个mode点yj,所有收敛到yj的样本点将形成一个样本特征空间中的紧致区域。对表征一小块紧致区域的yj进行聚类：一般采用合并聚类，通过为两个紧致区域之间的『类距离』设定阈值形成聚类的终止条件。则多个yj将形成一个类。将yj

所属的类别作为xi

的类别标号输出7.5聚类法

——

meanshiftMeanshift分割算法与标准的meanshift聚类算法相比，meanshift分割算法在特征空间的构造上一般会纳入位置信息。因此在核函数（局部权值）的设计上会出现一定的变化：上式尽管在形式上变得更复杂，但是在实际编程中，空间位置的核函数限制可以大大减少参与加权计算的样本点的数量，而且在这些样本点的选取上可以采用矩形框的方式，避免在高维特征空间中进行逐点的搜索，因此具有非常重要的实际意义。7.5聚类法

——

meanshift思路SLIC超像素聚类的本质是一种局部K-means算法。通过在局部聚类过程中纳入位置信息形成一种保持拓扑结构的局部分割块的网格分布。为进一步的全局分割、特征提取和目标识别服务。要素特征的选择相似性度量聚类规则7.5聚类法——SLIC超像素分割特征选择每个像素用像素的LAB色彩分量和坐标(x,

y)构成的5维特征向量。网格初始化将需要分割的图像初分割为大小相同的小块，并将每个小块的中心设置为初始中心点。在实际操作上为了方面初切割，可以将原始图像缩放，使其高、宽像素数均为小块边长l的整数倍。为了避免小块的中心落在图像边缘或噪声处，需要在以该中心点为中心的3×3的区域内计算梯度最小的像素位置，并将其作为小块中心的初始化结果。7.5聚类法——SLIC超像素分割相似性度量分别计算第i个中心点周围指定区域ϕi内的像素与中心点的特征距离聚类1.每一个像素对以该像素为中心的指定区域ϕ内的所有中心点，逐个计算相似性度量D，并选择最小的D对应的中心点对应的类。2.

在聚类结果的的基础上，以均值更新每个类的中心点3.重复步骤1-2，直到所有小块的中心点的迭代位移小于阈值。7.5聚类法——SLIC超像素分割算法本质聚类算法的本质是一种面向特征空间的无监督学习，通过自动寻找像素样本点在特征空间分布的内在模式，获取类别标记。优点稳定性强部分聚类算法速度较快缺点容易出现局部遗漏通常需要指定类别数对于具有复杂纹理的图像容易产生过分割7.5聚类法——总结基本思路将待分割的区域看做是由一个闭合边界包围的像素集合，因此边界法实现分割的前提是边界的提取。关键技术边缘检测边界跟踪霍夫变换7.6边界法（Boundary

Technique）从不连续性开始“不连续性”是图像局部特征的突变(色彩，纹理，亮度等）“不连续性”检测是一切基于边界的分割算法的基础7.6边界法——边缘检测如何衡量不连续性？特征变化的一阶导数（斜率）特征变化的二阶导数（曲率）7.6边界法——边缘检测二维图像的一阶导数：梯度用算子测量梯度最原始的梯度算子7.6边界法——边缘检测我们需要什么样的算子？7.6边界法——边缘检测边缘敏感性与抗噪能力的纠结算子成长史1.梯度算子2.Robert算子3.Prewitt&Sobel算子4.Laplacian算子5.Kirsch算子6.Marr算子7.Canny算子7.6边界法——边缘检测Laplacian算子边界法——边缘检测backKirsch算子1.八组算子（对应八个方向）2.取最大值（确定方向）7.6边界法——边缘检测back，

Marr算子(LOG算子)Marr和Hildreth将Gaussian滤波器和Laplacian边缘检测结合在一起，形成了LoG(LaplacianofGaussian)算法。即先用高斯函数对图像进行平滑，然后再用拉普拉斯算子进行运算，特点：抗噪声能力强各向同性

图像模糊化7.6边界法——边缘检测backCanny算子1.

2D高斯模板滤波（平滑图像，去噪）；2.求梯度（幅度与方向）；3.非极大值抑制（每个像素与其梯度方向相邻像素(两个)比较，如其灰度非极大值，则该点置0）4.双阈值判别（根据灰度直方图计算两个阈值）7.6边界法——边缘检测back7.6边界法——边缘检测梯度RobertPrewittSobelLapKirschMarrCanny计算量小小较小较小较大中较大方向表征性较好较好较好差好差较差抗噪能力较差较差中差中较好好边缘敏感性较好较好中好中较差中算子性能比较边界跟踪定义以边缘检测为基础的一种目标轮廓获取方法。通常是指从梯度图中一个边界点出发，通过对相邻边缘点的检测，逐步连接得到边界的方法。基本步骤：1.确定起点（哪里？几个？）2.数据结构（连通方式）与搜索策略3.终止条件常用的轮廓跟踪技术有两种:探测法和梯度图法。7.6边界法——边界跟踪算法步骤右图描述了边界跟踪的顺序。1）根据光栅扫描，发现像素p0，其坐标为(3,5)。2）反时针方向研究像素p0的8-邻接像素(3,4)，(4,4)，(4,5)，由此发现像素p1。3）反时针方问从p0以前的像素，即像素(3,4)开始顺序研究p1的8-邻接像素，因此发现像素p2。这时，因为p0≠p1，所以令pk=p2，返回第三步。反复以上操作，以p0,p1,…,pn的顺序跟踪8-邻接的边界像素。

7.6边界法——边界跟踪在一个边缘点的邻域内选择与其梯度幅值和方向都相似的边缘点进行连接7.6边界法——边缘连接霍夫变换(Hough

Transform)已知图像中的n个点，如何判断其中哪些点在一条直线上。7.6边界法——霍夫变换♦直角坐标系的“困扰”

♦极坐标系的“优势”7.6边界法——霍夫变换7.6边界法——

霍夫变换思路将数字图像视为具有矩形网格结构的图(graph),将像素视为点(vertex)，将相邻像素之间的联系视为边(edge)，定义某种基于类别标记的目标函数，通过对目标函数的优化实现分割。图论分割算法基于图的合并聚类基于图的