图像分割

一般的图像处理过程,图像处理有两大类目的： 1改善像质（增强、恢复） 2图像分析：对图像内容作出描述,第五章 图像的分割与描述,图像分析：（也叫景物分析或图像理解） 可看作是一种描述过程，主要研究用自动或半自动装置和系统，从图像中提取有用测度，数据或信息生成非图的描述或表示。 图像分割：将图像中有意义的特征或需要应用的特征提取出来。 （简单而又难于实现的最基础的识别工作。人的视觉系统对图像分割是十分复杂的，也是相当有效的。但分割原理和模型都未搞清楚。）,第五章 图像的分割与描述,5.1 阈值分割 5.2 边缘检测 5.3 区域分割 5.4 Hough变换 5.5 近邻法分割 5.6 基于动态聚类的分割 5.7 基于神经网络的分割 5.8 轮廓提取与边缘跟踪,第五章 图像的分割与描述,非理想情况，各段的分界不明显， 3种误差 a）增加了新的区域，b）失去了原有的区域， c）区域分割边界定位不准确 动态门限：把图像分成子图像，子图像做直方图，再定不 同的门限,5.1 阈值分割,1 阈值分割原理,假设图像中目标及背景的灰度为正态分布，其灰度分布概率密度函数分别p(z), q(z).设对象物占整体图像的比例为t，此时整体图像的灰度概率密度由下式决定,现在用阈值T分开：当zT 时为背景，反之则是对象物。,目标和背景概率密度分布,2 阈值的选取,最小误差阈值选取法,求上式最小值时的T，便是阈值.即对上式求微分,该方法必须用两个已知正态分布的曲线合成来近似直方图的分布，还要给定两个正态分布合成的比例t, 实现起来比较复杂,把背景误认为对象物的概率: 把对象物误认为背景的概率: 错误区分的概率:,根据假设，当t, p(z), q(z) 已知时，可求解阈值T.,最小误差阈值选取法,也叫大津阈值,把直方图在某一阈值处分割成两组，当被分成的两组间方差为最大时，决定阈值。设一幅图像的灰度值为1m级，灰度值i的像素数为ni，则像素总数为 ，各值的概率 ，用T将其分成两组C0=1T和C1=T+1m，各组产生的概率如下：,最大方差阈值选取法,C0产生的概率为：,C1产生的概率为：,两组间的方差：,从1m之间改变T，求上式为最大值时的T，既是最大方差阈值,最大方差阈值选取法,C0的平均值：,C1的平均值：,是整体图像的灰度平均值,其中,实现过程: 从T从1m逐一改变,每变一次,对应一个 ， 具有最大 的T即是最佳阈值. 讨论： * 此方法可操作性强； * 无论图像有无双峰都可得到较满意结果； * 局部图像二值化效果更好 * 可推广到双阈值图像分割,最大方差阈值选取法,可以将最大方差阈值推广到双阈值分割,根据上面的公式推广为:,最大方差阈值选取法,如:目标占整幅图像面积百分比,概率统计的阈值选取法,简单情况下取直方图谷值点作分割阈值。 图像中有噪声干扰，先平滑处理，后取门限 光照不均匀： 先修正光照不均匀，再取门限。 b 分区分割以减少光照不均匀而影响的分割效果,3 影响因素,噪音、照度不均匀，结构特征等。,多波段： R、G、B多幅直方图同时出现谷值。 取局部特征：如纹理粗糙度 此结构特征优于灰度特征，与结构有关，若取局部特征，并对局部特征图平滑之后，再取阈值，则效果更好。,3 影响因素,多特征阈值分割 a 灰度及平均灰度(33区)二维直方图 若集中于对角线区则表示灰度均匀区。 若远离对角线者（灰度与平均灰度不同）是区域边界。 （近对角线构成直方图有明显峰值及阈值，远离对角线者可用灰度平均值作为阈值，用于区分两个区）。,灰度,3 影响因素,灰度,b 灰度与灰度梯度图,c 多波段： R、G、B可分别组成R-B, G-B, R-B两维直方图，图上强的地方反映一个区。,多特征阈值分割,3 影响因素,从数学上看，图像的模糊相当于图像被平均或积分，为实现图象的锐化，必需用它的反运算“微分”加强高频分量作用，使轮廓清晰。,5.2 边缘检测,1 边缘检测原理,其导数在边缘方向取得极值,梯度对应一阶导数，对于一个连续图像函数f(x,y):,梯度的幅度:,梯度矢量定义:,梯度的方向:,1 边缘检测原理,离散域上微分改成差分,而且由水平和垂直两个方向模板组成 一阶: x f(i,j) = f(i,j) - f(i,j-1) y f(i,j) = f(i,j) - f(i-1,j) 二阶：x2 f(i,j) = x f(i,j+1) - x f(i,j) = f(i,j+1) - f(i,j) ( f(i,j) - f(i,j-1) y2f(i,j) = f(i+1,j) + f(i-1,j) - 2f(i,j),1 边缘检测原理,a) Roberts算子,近似式：,1,0,0,-1,0,1,-1,0,Roberts算子,2 典型算子,b) Sobel算子,c) Prewitt算子,2 典型算子,d) Kirsch算子,2 典型算子,由K0K7八个方向模板组成，将K0K7的模板算法分别与图像中的33区域乘，选最大一个值，作为中央像素的边缘强度,其中：,若 最大，说明 处有 方向的边缘通过,k0,k1,k2,k3,k4,k5,k6,k7,d) Kirsch算子,2 典型算子,e) 定向滤波： 沿特定方向增强，有朔像效果,-1,-c,-1,1,c,1,-1,-c,c,1,-1,1,c,1,1,-1,-1,-c,-1,1,1,c,-c,-1,注意：边缘检测对噪声敏感，常在作边缘检测前对图像进行某些预处理，如平滑处理或边缘增强等。,2 典型算子,f) 二阶微分算子- laplace算子,特点:对噪声敏感, 常产生双像素宽的边缘，无方向性,2 典型算子,g) Canny算子,2 典型算子,一个边缘算子必须满足三个准则： 1） 低错误率：边缘算子应该只对边缘响应，并能找到所有的边，而对于非边缘应能舍弃。 2） 定位精度：被边缘算子找到的边缘象素与真正的边缘象素间的距离应尽可能的小。 3） 单边响应：在单边存在的地方，检测结果不应出现多边。,区域分割：利用的是图像的空间性质，认为分割出来的属于同一区域的像素应具有相似的性质. 1 区域生长法：,T=3时的生长结果,5.3 区域分割,算法描述 先对每个需要分割的区域找一个种子像素作为生长的起点，然后将种子像素周围邻域中与种子像素有相似性质的像素合并到种子像素所在的区域中。将这些新像素当作新的种子像素继续进行上面的过程，直到再没有满足条件的像素可被包括进来。,5.3 区域分割,1 区域生长法,关键问题 a) 选择或确定一组能正确代表所需区域的种子像素 人机交互 通过直方图峰值 b) 确定在生长过程中能将相邻像素包括进来的准则 基于区域灰度差 基于区域内灰度分布统计性质,5.3 区域分割,1 区域生长法,区域生长法生长准则 基于区域灰度差方法,5.3 区域分割,1 区域生长法,Step1：对像素进行扫描，找出尚没有归属的像素； Step2：以该像素为中心检查它的邻域像素，即将邻域中的像素逐个 与它比较，如果灰度差小于预先确定的阈值T，将它们合并； Step3：以新合并的像素为中心，返回到步骤2，检查新像素的邻 域，直到区域不能进一步扩张； Step4：返回到步骤1，继续扫描直到所有像素都有归属，则结束整 个生长过程。,区域生长法生长准则 基于区域灰度差方法,5.3 区域分割,1 区域生长法,讨论：生长准则与欠分割或过分割现象,T=1,T=6,区域生长法生长准则 基于区域内灰度分布统计性质,5.3 区域分割,1 区域生长法,考虑以灰度分布相似性作为生长准则来决定区域的合并，具体步骤为： 把像素分成互不重叠的小区域； 比较邻接区域的累积灰度直方图，根据灰度分布的相似性进行区域合并；,区域生长法生长准则 基于区域内灰度分布统计性质,5.3 区域分割,1 区域生长法, Kolmogorov-Smirnov检测:, Smoothed-Difference 检测:,如果检测结果小于给定的阈值，就把两个区域合并。,灰度直方图h(x)的累积灰度直方图被定义为：,实际中常先把图像分成任意大小且不重叠的区域，然后再合并或分裂这些区域以满足分割的要求,即分裂合并法.一致性测度可以选择基于灰度统计特征(如同质区域中的方差),假设阈值为T ,则算法步骤为: 对于任一Ri，如果 ，则将其分裂成互不重叠的四 等分； 对相邻区域Ri和Rj，如果 ，则将二者合并； 如果进一步的分裂或合并都不可能了，则终止算法。,5.3 区域分割,2 分裂合并法,分裂合并法分割图像示例,简单的区域分裂过程,5.3 区域分割,2 分裂合并法,5.4 Hough变换,Hough变换是一种检测、定位直线和解析曲线的有效方法。它是把二值图变换到Hough参数空间，在参数空间用极值点的检测来完成目标的检测。下面以直线检测为例，说明Hough变换的原理。,图像空间和参数空间中点和线的对偶性,5.4 Hough变换,Hough变换是一种检测、定位直线和解析曲线的有效方法。它是把二值图变换到Hough参数空间，在参数空间用极值点的检测来完成目标的检测。下面以直线检测为例，说明Hough变换的原理。,极坐标表示的点线对偶性,5.4 Hough变换,图像的Hough变换如下图,pmin,pmax,qmin,qmax可以根据先验知识设定,累加数组的大小由检测分辨率以及pmin, pmax, qmin和qmax来决定。,图像,参数空间累加数组,5.4 Hough变换,随着检测分辨率的提高, 时间以及空间花费越来越大，可以采用分级变换加以解决,分级Hough变换流程图,Hough变换的优点是抗噪声能力强，能够在信噪比较低的条件下，检测出直线或解析曲线。缺点是需要首先做二值化以及边缘检测等图像预处理工作，损失掉原始图像中的许多信息。,Hough变换检测二次曲线-以圆为例 圆的方程:,5.4 Hough变换,5.4 Hough变换,Hough变换的改进: 分块处理 随机hough变换 Hough变换的应用： 银行票据纠偏,5.5 近邻法分割,1、最近邻法 假定有个类别 的待分类别，每类有标明类别的样本 个。我们可以规定 类的判别函数为 其中 的角标 表示 类， 表示 类 个样本中的第 个。按上式决策规则可以写为 若 则决策 其直观解释是相当简单的，对于未知样本 ，只要比较其与 个已知类别样本之间的欧氏距离，决策 与离它最近的样本同类。,关键点：初始样本点如何标明类别，距离函数的制定,5.5 近邻法分割,2、K-近邻法,取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。具体说就是在N个已知样本中，找出x的k个近邻。设这N个样本中，来自 类的样本有 个，来自 类的有 个，来自 类的有 个，若 分别是k个近邻中属于 类的样本数，则我们可以定义判别函数为 决策规则为：若 则决策 。,关键点：初始样本点如何标明类别，距离函数的制定,1 k-均值聚类 又称“C-均值算法”，算法的基础是误差平方和准则。若 是第 聚类 中的样本数目， 是这些样本的均值，即,5.6 动态聚类分割,把 中的各样本与均值 间的误差平方和对所有类相加后为,1 k-均值聚类,是误差平方和聚类准则， 度量用了个聚类中心 代表个样本子集 时所产生的总的误差平方。对于不同的聚类，使 极小的聚类是误差平方和准则下的最优结果。,1 k-均值聚类,分析，把样本y从 类移入 类对误差平方和的影响：,1 k-均值聚类,分析，把样本y从 类移入 类对误差平方和的影响：, 的移动只影响 和 两类,对其他类无任何影响,因此只需要计算这两类的新的误差平方和 和,如果,则把样本 从 移入到 就会使误差平方和减少.只有当 离 的距离比离 的距离更近时才满足上述不等式.,1 k-均值聚类,k-均值算法流程,Step1:确定C个初始聚类群，计算相应的聚类中心 Step2:选择一个备选样本 ，设 现在在 中 Step3:若 ,则转2,否则继续,假设聚c类，则：,1 k-均值聚类,k-均值算法流程,Step5:对于所有的 ,若 ,则把 从 移到 中 Step6:重新计算 和 的值,并修改 Step7:若连续叠代N次 不改变,则停止,否则转到步骤2,Step4:计算,1 k-均值聚类,Step1:确定C个初始聚类群，并计算相应的聚类中心 。 Step2:对于每个待聚类样本，计算其与C个聚类中心的距离，把 待聚类样本归到离其最近的一个聚类群中。 Step3:当每个待分样本都被分到C个聚类中后，重新计算聚类中 心 。 Step:重复、步，直到C个聚类中心不变为止。,k-均值简化算法,选择C个初始聚类中心，按最近距离测度将待分样本归类,k-均值聚类示例,1 k-均值聚类,关键问题,第一步: 代表点的选择 凭经验选择代表点 将全部数据随机地分成C类，计算每类重心 用前C个样本点作为代表点 第二步: 确定代表点后进行初始分类 其余的点离哪个代表点最近就归入哪一类 每个代表点自成一类，将样本依顺序归入与其最近 的代表点那一类，并立即重新计算该类的重心以代替原来的代表点。然后再计算下一个样本的归类直至所有的样本都归到相应的类为止,1 k-均值聚类, 样本集初始划分,关键问题,距离测度的选择影响分类的结果，常见用空间、颜色特征产生距离函数，或者同时考虑对两种特征加权。,1 k-均值聚类, 距离测度的选择, 类别数的确定,根据经验人为确定类别数 通过算法自动产生,Je-c曲线 聚类有效性评价函数, 类别数的确定Je-c曲线,1 k-均值聚类,类别数的确定聚类有效性评价函数,1 k-均值聚类,聚类有效性评价包括聚类质量的度量、聚类算法适合某种特殊数据集的程度，以及某种划分的最佳聚类数目。到目前为止，已提出了多种聚类有效性标准，其共同目标是使分类结果达到类内紧密、类间远离。, 类别数的确定聚类有效性评价函数,1 k-均值聚类,聚类平均散布性：,聚类总体分离性：,其中：,则SD聚类有效性函数：,以SD有效性函数为例， 代表方差， 代表均值，则：,具有最小SD值所对应的c即是最佳的类别数, 类别数的确定,1 k-均值聚类,类别数的确定问题是k均值目前仍然无法完美解决的问题，一般需要具体问题具体分析。,2 模糊c均值聚类,K-均值算法是误差平方和准则下的聚类算法，它把每个样本严格地划分到某一类，属于硬划分的范畴。实际上，样本并没有严格的属性，它们在性态和类属方面存在着中介性，为了解决这一类问题，研究者们将模糊理论引入K-均值算法（C-均值），由此，K-均值由硬聚类被推广为模糊聚类，即模糊C均值算法(Fuzzy C-Means，简称FCM )。,2 模糊c均值聚类,是有n个样本的集合，c为预定的类别数目， 为每个聚类的中心， 是第i个样本对于第j类的隶属度函数。用隶属度函数定义的聚类损失函数可以写为：,其中， 是一个可以控制聚类结果的隶属程度的常数。,在不同的隶属度定义方法下最小化该损失函数，就得到不同的模糊聚类方法。,2 模糊c均值聚类,FCM算法的步骤： Step1：设定聚类数目c和参数b； Step2：初始化各个聚类中心 Step3：重复下面的运算，直到各个样本的隶属度值稳定： 用当前的聚类中心计算隶属度函数； 用当前的隶属度函数更新个类聚类中心。,当算法收敛时，即可根据各类的聚类中心和各个样本对于各类的隶属度值完成模糊聚类划分。如果需要，还可以将模糊聚类结果进行去模糊化，把模糊聚类划分转化为确定性分类。,2 模糊c均值聚类,关键问题： 隶属度函数的选取 类别数的确定 特征的选取 距离函数的选取,两个聚类 和 之间相似性度量 的计算方法是分级聚类算法的基础。最常见的相似性度量有以下几种：,3 分级聚类方法,（3）均值距离,其中 可以是任何一种距离度量,（1）最近距离,（2）最远距离,初始时设置 ,N是样本数，即初始时设每一个样本为一类。 （1）在集合 中找到一对满足条件 的聚类集合 和 。 （2）把集合 并入集合 ，并去掉 。 （3）把 从指标集 中除掉，若 的基数仅等于2时， 则终止计算；否则转向1,3 分级聚类方法,5.7 基于神经网络的分割,神经网络由于其在聚类方面的优越性，非常擅长于解决模式识别领域中的模式分类问题，并且因其具有较强的适应性、灵活性和普遍的非线性输入输出能力等突出优点，在图像分割领域得到很好的应用。,1、基于自组织神经网络的聚类分割,SOM网络是由输入层和竞争层两层节点组成的前向网络，网络的输入层节点构成一维阵列，其节点数为输入模式样本的特征个数，网络的竞争层节点构成二维平面阵列。,SOM网络结构,1、基于自组织神经网络的聚类分割,网络的基本原理 当输入某模式后，通常只有一个或局部区域的竞争层神经元对该模式有积极响应，这时与竞争层相应节点连接的权值向量就向输入模式的方向修正。这样，网络通过对输入模式的反复学习，可使连接权矢量空间分布密度与输入模式的概率分布趋于一致，即连接权空间分布可反映输入模式的统计特征。,1、基于自组织神经网络的聚类分割,SOM网络的算法步骤, 对所有输入节点到输出节点的连接权值 初始化，可以随机地取一些较小的值; 将每一像素点的颜色和位置信息结合起来，即给每个像素点赋予1个具有5个特征值的特征向量，作为自组织神经网络的输入信号;,1、基于自组织神经网络的聚类分割,SOM网络的算法步骤, 选出竞争层中最匹配的神经元，匹配函数采用欧氏距离法来度量，设输入向量为 ，而神经元的权值向量为 ，则有:,位于区域Nc内的神经元权值将得到修改，其中区域Nc是以神经元c为中心的、半径为R范围内的全部神经元集合.权值的修改公式:,其中a(t)为一取值在0,1区间内、随时间衰减的函数.,1、基于自组织神经网络的聚类分割,SOM网络的算法步骤, 判断所有像素点是否已输入完毕，否则转第2步; 修改学习参数a(t)和Nc(t)，调整输入向量的次序，反复 学习，直到达到预定学习次数，各像素点逐渐在输出层中形成固定的映射关系.,1、基于自组织神经网络的聚类分割,SOM聚类的后处理,一般SOM聚类后还需要做合并处理。,2、自生成神经网络分割,自生成神经网络SGNN(Self-Generating Neural Network,SGNN)不需要指定网络结构与网络参数,而且也不需要迭代学习，正是由于其简单的网络设计而倍受关注。 SGNN是利用竞争学习机制的一种非监督学习神经网络，它以一种树结构来实现,其中整个结构包括神经元、神经元之间的联系和权值,都是在学习中采用非监督学习方法自动生成。,2、自生成神经网络分割,SGNN算法描述,输入节点：2 4 5 1,2,5,1,2,4,根节点,节点神经元,叶节点神经元,一棵神经树,自生成神经树的生成过程(SGNT：Self-Generating Neural Tree),2、自生成神经网络分割,SGNN算法描述,输入节点：2 4 5 1 8 令T=2.5,8,2、自生成神经网络分割,SGNN算法描述,1)给定样本集ei(i =1,2,L),距离公式,误差阈值. 2)生成一个新节点nj,用输入数据ei的属性值作为新节点nj的权 值Wj.如果i=1(第一个输入数据),则转至6),否则执行3). 3)计算节点nj与nnode(nnode(node=1,2j-1)是当前SGNT中的神 经元节点)之间的最小距离,并找出获胜神经元节点nwin.如果 距离大于阈值d(nj,nwin),则执行4),否则nj被并入nwin,转至5) 执行.,2、自生成神经网络分割,SGNN算法描述,4)将nj连接到当前SGNT神经树上.如果nwin是当前树中的叶子节 点,则创建一个新节点nj+1,令其权值Wj+1等于nwin的权值Wwin, 连接nj和nj+1作为nwin的孩子节点,否则仅连接nj作为nwin的孩 子节点. 5)使用公式 更新节点nr的权值向量.其中nr是 从节点nj到根节点所经过路径上的所有节点,cr是以节点nr为 根的子树的叶子节点的个数. 6)如果i=L,则结束算法,否则i= i+1, 转至2)继续执行.,2、自生成神经网络分割,SGNN用于图像分类,图像每个像素看作也个样本叶子，根据SGNN算法生成SGNT,最终生成树有几个孩子，就分成几类，每个孩子所覆盖的那些叶子节点赋予同一个标号，完成聚类分割。,2、自生成神经网络分割,SGNN存在问题, 如果叶子节点过多，则生成的神经数庞大，运算量和存储空间大 对孤立点敏感 如果输入网络的顺序不同，则分类结果也可能不同,原图 生长