第四章 图象分割 (Image Segmentation)

Presentation on theme: "第四章 图象分割 (Image Segmentation)"— Presentation transcript:

1 第四章 图象分割 (Image Segmentation)
定义：所谓图象分割就是按一定的规则将图象划分成若干有意义的 区域。 研究重点：(1)按什么样的规则。 (2)什么叫有意义。一般是符合特定场合的应用的才称为 有意义。因此图像分割是个病态问题(ill-posed problem)， 一种方法可能非常符合甲的需求，但与乙的需求矛盾。 说明：规则和需求的多样性导致了图像分割方法的多样性，到目前 为止，有人说有1800多种方法，可见其方法之多。同时也说 明不存在通用的图像分割方法。 在本章中，我们讲述边缘提取和基于直方图的图像分割，希望大家能够掌握一些基本的概念和处理问题的手段。 2002, Ver1.0 任明武，南京理工大学计算机系

2 4.1 边缘检测(Edge Extraction, Edge detection)
定义：边缘点是指其周围象素的灰度有阶跃变化(step edge)或屋顶状变化(roof edge)的象素、常存在于目标与背景之间、目标与目标之间、目标与其影子之间。 分析手段：因为灰度的变化，可以反映为导数；因此，根据边缘的形状，可以通过求导的方法来寻求边缘。边缘的参数包括：边缘强度(edge intensity)和边缘方向(edge direction) 比如： 窗口中象素的灰度值 窗口中象素的梯度值 由此，可以看出求导和边缘检测的关系。 2002, Ver1.0 任明武，南京理工大学计算机系

3 屋顶状边缘： 阶跃边缘： 一阶导数过零点，二阶导数最小值 一阶导数最大值，二阶导数过零点 g(i) g(i) i i 极值点 一阶导数
2002, Ver1.0 任明武，南京理工大学计算机系

4 说明：在实际应用中，一般仅考虑阶跃边缘，因为只要采样分辨率足够或者说窗口足够小，边缘都可以看成是阶跃边缘。
分析手段：边缘是指图象中灰度发生急剧变化的区域。图象灰度的变化情况可以用灰度分布的梯度来反映，给定连续图象f(x,y)，其方向导数在边缘法线方向上取得局部最大值。 因此，边缘的检测转化为求f(x,y)在(x,y)处的方向导数问题。 f(x,y)沿任意方向r的方向导数为： 其中，θ为x轴到方向r的转角。fx和fy为f(x,y)的偏导数。与方向导数有关联的一个概念是函数的梯度，对于平面的每一个点p(x,y)都可定出一个向量(包括幅值和方向)，该向量称为(x,y)处的梯度。 向量为： 梯度为： 可以证明，当方向r与梯度方向一致时，方向导数达到最大值，该最大值即为梯度的模。 2002, Ver1.0 任明武，南京理工大学计算机系

5 因此，(x,y)处的边缘强度取其方向导数的最大值，即梯度的模; 边缘方向取x轴到梯度的方向θ。实际上也可以直接从方向导数的公式直接推导得到：
梯度的模为： x轴到梯度的转角的正切为： 因此，(x,y)处的边缘强度取其方向导数的最大值，即梯度的模; 边缘方向取x轴到梯度的方向θ。实际上也可以直接从方向导数的公式直接推导得到： 即： 得到： 2002, Ver1.0 任明武，南京理工大学计算机系

6 为了能得到图像中间任意方向伸展的边缘，还希望对图像的某种导数运算是各向同性。可以证明偏导数的平方和是各向同性，即：
注1：对各向同性的说明 假设图像f(x,y)的所有导数都存在并且连续，那么在对f(x,y)求导数时只依赖于点(x,y)附近的一个任意小的邻域内的像素的值，因此可以将这种运算认为是位移不变运算。 为了能得到图像中间任意方向伸展的边缘，还希望对图像的某种导数运算是各向同性。可以证明偏导数的平方和是各向同性，即： 式中(x,y)是某个象素图像旋转前的坐标，(x’,y’)是该向素图像旋转后的坐标。 梯度运算符合位移和旋转不变性。 注2：数字图像中的导数运算 在图象中，导数的计算有两种方式： (1)先将数字图像通过曲面拟合的方法得到连续空间中的描述，然后在连续空间中，自然可以求导。 2002, Ver1.0 任明武，南京理工大学计算机系

7 (2)用差分代替求导，如下： x f(i , j) = f(i+1 , j) - f(i , j)
y f(i , j) = f(i , j+1) - f(i , j) α f(i , j) =x f(i , j) cosα+y f(i , j) sinα 通过研究边缘类型及其导数的表现，可以设计不同的检测算法。下面，我们讲述几种常用的边缘检测算法。 4.1.1梯度算子(Gradient) 定义梯度为： 若G(i ,j) > Threshold, 则(i ,j)点为边缘点。 缺点：时间复杂度高。 改进：令G(i ,j)=| x f(i , j) |+ | y f(i , j) | 2002, Ver1.0 任明武，南京理工大学计算机系

8 例： 得到 4.1.2罗伯特算子(Roberts) 定义为： R(i ,j)=max{ |f(i,j)- f(i+1,j+1)|, |f(i+1,j)- f(i-1,j+1)| } i, j i+1, j i, j+1 i+1, j+1 1 -1 1 -1 例： 得到 2002, Ver1.0 任明武，南京理工大学计算机系

9 定义为：S (i ,j)=|(P3+2*P2+P1)-(P5+2*P6-P7)|+ |(P3+2*p4+p5)-(P1+2*P0+P7)|
4.1.3索伯算子(Sobel) 定义为：S (i ,j)=|(P3+2*P2+P1)-(P5+2*P6-P7)|+ |(P3+2*p4+p5)-(P1+2*P0+P7)| i-1, j-1 i, j-1 i+1, j-1 i-1, j i, j i+1, j i-1, j+1 i, j+1 i+1, j+1 1 -1 2 -2 1 2 -1 -2 P3 P2 P1 P4 i, j P0 P5 P6 P7 2002, Ver1.0 任明武，南京理工大学计算机系

10 1 -1 1 2 -1 -2 1 2 缺点：得到双线宽的边缘，因为该算子涉及到3*3的邻域。 优点： (1)加权（距离越近，贡献越大）
(2)实质上是平滑去噪，后求差分。在边缘检测可以说是通用模式， 即：在用Gradient或Robert等其他算子求边缘象素前，最好先对图象进行平滑，因为噪声的灰度值一样是变化很大。 思考1：在图像平滑时，模板中各系数之和1且都不小于0；在边缘检测算子中，各系数之和是0且有正有负。 思考2：对图像I使用模板l，等价于对I先使用模板2再使用模板3吗? 1 -1 1 2 -1 -2 I @ 1 2 @ I @ 模板2 模板3 模板l 2002, Ver1.0 任明武，南京理工大学计算机系

11 00 900 450 1350 1 -1 1 -1 1 -1 1 -1 4.1.4方向模板(Prewitt) 2002, Ver1.0
任明武，南京理工大学计算机系

12 一般性原则：给定图象f(x,y)在两个正交方向H1、H2上的梯度g1(x,y)和g2(x,y)定义如下：
4.1.5小结 一般性原则：给定图象f(x,y)在两个正交方向H1、H2上的梯度g1(x,y)和g2(x,y)定义如下： 则边缘的强度和方向由下式给出： 为了加快速度，有时： 2002, Ver1.0 任明武，南京理工大学计算机系

13 Original Image(Lena) Prewitt Image Sobel Image 2002, Ver1.0
任明武，南京理工大学计算机系

14 对数字图像的每个象素f(x,y)，取它的二阶导数为关于x轴方向和y轴方向的二阶导数之和，得到：
注： Prewitt Image 和Sobel Image 都是Gradient Image，从中看不到具体的有何明显改进。实际上，Gradient Image仅是中间结果，而且各种算子得到的梯度图像相差不大，即可能都不能满足你实际的需要，或直接满足你的需要。这需要在边缘检测完成后，使用相关的约束条件得到目标的位置或尺寸。而梯度图像还需要一个阈值(如何取阈值是一个值得研究的问题)，才能判断一个像素是否是边缘点。 4.1.6二阶微分算子 前面讲过，对阶跃边缘边缘而言，边缘点处的二阶导数过0点，或二阶导数在边缘点处出现零交叉(Zero-Crossing)，即边缘点两旁的二阶导数异号。因此下面我们讲述基于该原理的边缘点检测，即拉普拉斯(Laplacian)算子。 对数字图像的每个象素f(x,y)，取它的二阶导数为关于x轴方向和y轴方向的二阶导数之和，得到： 2x f(i , j)+ 2y f(i , j) = f(i+1 , j) + f(i-1 , j) + f(i , j+1)+ f(i , j-1)-4f(i,j) 2002, Ver1.0 任明武，南京理工大学计算机系

15 -1 -1 8 4 写成模板形式就是： 或 使用Laplacian，在某种尺度(下面会讲何为尺度)下得到的边缘点 2002, Ver1.0
-1 4 -1 8 或 使用Laplacian，在某种尺度(下面会讲何为尺度)下得到的边缘点 2002, Ver1.0 任明武，南京理工大学计算机系

16 补充内容1：过零点检测（Marr-Hildreth算子）(马尔-希尔德累思算子)
根据图象边缘处的一阶微分（梯度）应该是极值点的事实，图象边缘处的二阶微分应为零，确定过零点的位置要比确定极值点容易得多也比较精确。但是显然二阶微分对噪声更为敏感。 　　算法：为抑制噪声，可先作平滑滤波然后再作二次微分，通常采用高斯函数作平滑滤波，故有LoG(Laplacian of Gaussian)算子。在实现时一般用两个不同参数的高斯函数的差DoG（Difference of Gaussians）对图象作卷积来近似，这样检测出来的边缘点称为f(x,y)的过零点（Zero-crossing）。 理论：过零点的理论是Marr,Hildreth提出来的，是计算视觉理论中的有关早期视觉的重要内容。 将高斯函数G(x,y; )与图像f(x,y)进行卷积，可以得到一个平滑的图像fs(x,y)，由于感兴趣的是图像的边缘，于是需要对fs(x,y)进行拉普拉斯运算。而图像f(x,y)与高斯函数G(x,y; )相卷积的拉普拉斯运算可以表示为G(x,y; )的拉普拉斯变换与f(x,y)的卷积，因此，有算子如下： 2002, Ver1.0 任明武，南京理工大学计算机系

17 根据LOG函数的特点，已经有专用的硬件，使用DOG函数来近似实现LOG函数。即：
其中： 　　根据LOG函数的特点，已经有专用的硬件，使用DOG函数来近似实现LOG函数。即： 2002, Ver1.0 任明武，南京理工大学计算机系

18 　　从工程的观点来看，当　　　　　　　时，DOG逼近LOG。另外，在软件实现中，考虑到LOG算子的对称性，可采取分解的方法来提高运算速度，即把一个二维的滤波器分解为独立的行列滤波器。有：
其中： 2002, Ver1.0 任明武，南京理工大学计算机系

19 　　高斯函数的标准差　是一个尺度参数，它越小，则相当于邻域越小，即在一个很小的局部范围内平滑，边缘定位越准确；反之，则表示在较大的范围内平滑，边缘定位越不准。
　　LOG算子的优点是：边缘定位精度高，连续性好；缺点是：在抗干扰和检测出复杂形状的边缘之间仍存在较尖锐的矛盾，平滑尺度的选择也没能很好地解决。当边缘宽度小于算子的窗口时(即边缘相对于窗口而言成了屋顶状边缘)时，边缘丢失。 补充内容２：多尺度方法和边缘聚焦 研究最优算子的一些学者指出，窗口的大小(或尺度)参数的自动调整是很困难的。伯津斯Berzins对LOG算子提取边缘的精度进行了定量分析，知道一般来说边缘定位的误差与高斯函数中的 成比例，因此可以采用连续改变 的方法得到一系列的图像边缘序列，实现由粗到精的边缘检测过程。从理论上讲，这一边缘序列包含了原始图像的全部信息，由此可完全恢复原始图像(又叫指纹定理)。然而，由于图像数据量非常庞大，离散尺度的综合仍然是一个尚未解决的问题。 威特金(Witkin)等人进一步讨论了 从0到无穷大时零交叉的变化情况，这便是“尺度空间滤波”的方法。(《自动化学报》1990, Vol.16, No.3, pp ) 2002, Ver1.0 任明武，南京理工大学计算机系

20 　 有学者发现，当 增大时，零交叉点的个数不会增加，但可能会减少，这性质称为单调性质。他们还发现，为了使零交叉满足单调性质，所用的平滑函数必须是高斯函数。这一类结果被称为尺度定理。　 “边缘聚焦”是由粗到精检测边缘，将高精度的边缘定位和良好噪声一直相结合，应用这一方法可以精确地重建不同种类的结合点，这在三维景物重建和识别中有一定的应用。比如，在医学图像处理中，为了确定心脏的位置，图像首先被模糊，然后逐步聚焦确定心室的形状。 实现边缘聚焦的一种方法是比较不同分辨率尺度下的一些边缘图，然后匹配边缘线段。或者另一种方法，即在尺度空间使用很短的步长，以满足连续两步间边缘片断移动距离不超过一个像素。(当然还有其它的方法)。 补充内容３：沈俊算子(递归滤波器) 与上面介绍的马尔的方法一样，沈俊同样提出了先滤波后求导的边缘检测方法。他在阶跃边和可加白噪声模型下，就信噪比最大准则，证明了最佳滤波器是对称的指数函数。形式如下： 2002, Ver1.0 任明武，南京理工大学计算机系

21 a0越大，即越接近于1，则F(x,y)越窄，压制噪声的能力减少，但定位精度越高。沈俊还进一步证明了：
其中： a0越大，即越接近于1，则F(x,y)越窄，压制噪声的能力减少，但定位精度越高。沈俊还进一步证明了： (1)用上述指数函数滤波，可以等价于分别按行和按列各进行两次正反向的递归滤波来实现，即对 ，按行进行： 其中，p2(x,y)即为按行进行了正反两次递归滤波的输出，对它再进行按列进行正反两次递归滤波，即对 ： 2002, Ver1.0 任明武，南京理工大学计算机系

22 基于上述的结果，可以给出如下的边缘提取方法: (1)用上述正、反向递归滤波器的结果与原图像作差，得到拉普拉斯图像。
其中，p4(x,y)即为所求，即： (2) 基于上述的结果，可以给出如下的边缘提取方法: (1)用上述正、反向递归滤波器的结果与原图像作差，得到拉普拉斯图像。 (2)对拉普拉斯图像二值化，即将所有正值都赋以1，其他的赋以0。 (3)在二值化的拉普拉斯图像中，求出零交叉点(即它的值为1，且至少有一个邻居的值为0)。 2002, Ver1.0 任明武，南京理工大学计算机系

23 在如下的三个标准意义下，Canny边缘检测算子对受白噪声影响的阶跃型边缘是最优的：
(1)检测标准 … 不丢失重要的边缘，不应有虚假的边缘； (2)定位标准 … 实际边缘与检测到的边缘位置之间的偏差最小； (3)单响应标准 … 单一边缘仅有唯一响应。即单个边缘产生多个响应的概率要低。 Canny 边缘检测算子是基于如下的几个概念： (1)边缘检测算子是针对1D信号表达的，对前两个标准最优，即检测标准和定位标准； (2)如果考虑第三个标准(多个响应)，需要通过数值优化的办法得到最优解。该最优滤波器可以有效地近似为标准差为σ的高斯平滑滤波器的一阶微分，其误差小于20%，这是为了便于实现。这与LoG边缘检测算子很相似。 (3)将边缘检测算子推广到两维情况。阶跃边缘由位置、方向和可能的幅度（强度）来确定。 2002, Ver1.0 任明武，南京理工大学计算机系

24 英文原文： 1. optimal for step edges corrupted by white noise
2. optimality related to three criteria detection criterion ... important edges should not be missed, there should be no spurious responses localization criterion ... distance between the actual and located position of the edge should be minimal one response criterion ... minimizes multiple responses to a single edge (also partly covered by the first criterion since when there are two responses to a single edge one of them should be considered as false) 坎尼算子中，当一个像素满足以下3个条件时，则被认为是图像的边缘点： (1)该点的边缘强度大于沿该点梯度方向的两个相邻象素点的边缘强度。 (2)与该点梯度方向上相邻两点的方向差小于45度。 (3)以该点为中心的3x3邻域中的边缘强度极大值小于某个阈值。 2002, Ver1.0 任明武，南京理工大学计算机系

25 补充内容5：边缘锐化 (Edge Sharpen)
含义：边缘锐化指的是在图像中令处于目标边界上的像素黑的更黑、白的更白，即灰度值小的更小，灰度值大的更大。也即对位于边界上的像素而言，灰度值小的要加上一个负数，灰度值大的要加上一个正数；对不位于边界上的像素而言，加上0。 实现：g’(x,y)=g(x,y)+d，其中d<0,.d>0或d=0。如何确定d的值呢？考虑到d的值肯定与边缘检测有某种关系，对不位于边界上的像素而言，其梯度值肯定为零。在边界上，当灰度值刚开始由小到大时，g(x,y)肯定小于其邻域的均值u(x,y)，即g(x,y)-u(x,y)<0；当灰度值由小到大结束时，g(x,y)肯定大于其邻域的均值u(x,y)，即g(x,y)-u(x,y)>0。 例： g(x,y) : u(x,y) : g(x,y)-u(x,y): g(x,y)+(g(x,y)-u(x,y)): 图示形式如下，由图可见，很多文献中称之为“边缘过冲”(ring)是很形象的。(过冲即上冲或下冲得过分了)。 2002, Ver1.0 任明武，南京理工大学计算机系

26 g 2g-u 1 -1 8 结论：d=g(x,y)-u(x,y)，边缘锐化即g(x,y)+d=2g(x,y)-u(x,y)。
考虑：下面的卷积模板有什么作用，各系数之和是多少，系数的正负情况如何。 /8 1 -1 8 (1) (2) 2002, Ver1.0 任明武，南京理工大学计算机系

27 -1 9 -1 5 (3) (4) 1 -9 1 -5 (5) (6) 2002, Ver1.0 任明武，南京理工大学计算机系

28 (Histogram Based Image segmentation) 回顾：1. 边缘检测不能保证边缘点是一一相连，即得到闭合的轮廓线。
4.2基于直方图的图象分割 (Histogram Based Image segmentation) 回顾：1. 边缘检测不能保证边缘点是一一相连，即得到闭合的轮廓线。 2. 如果把图象分割成区域，则能得到闭合的边界。 3. 根据不同的区域的的灰度值或纹理等统计特征值的差异来划分出若干个区域。 4. 实际应用采用的特征太多，描述形式多样，数学手段也很多。 研究重点：直方图能反映图象的统计特征和目标的分布，且仅需要很少的存储空间，这意味着基于直方图的图象分割简单而又实用。其研究重点有两个：直方图的构造 和 阈值的选取。 阈值：阈值是在分割时作为区分物体与背景象素的门限，大于或等于阈值的象素属于物体，而其它属于背景。这种方法对于在物体与背景之间存在明显差别(对比)的景物分割十分有效。实际上，在任何实际应用的图象处理系统中，都要直接或间接用到阈值化技术。为了有效地分割物体与背景，人们发展了各种各样的阈值处理技术，包括全局阈值、自适应阈值、最佳阈值等等。 2002, Ver1.0 任明武，南京理工大学计算机系

29  全局阈值：全局阈值是指整幅图象使用同一个阈值做分割处理。适用于背景和前景有明显对比的图象。
 全局阈值：全局阈值是指整幅图象使用同一个阈值做分割处理。适用于背景和前景有明显对比的图象。  自适应阈值：在许多情况下，物体和背景的对比度在图象中不是各处一样的，这时很难用统一的一个阈值将物体与背景分开。这时可以根据图象的局部特征分别采用不同的阈值进行分割。实际处理时，需要按照具体问题将图象分成若干子区域分别选择阈值，或者动态地根据一定的邻域范围选择每点处的阈值，进行图象分割。  最佳阈值：阈值的选择需要根据具体问题来确定，一般通过实验来确定。对于给定类型的图象，可以通过设定模型和评价指标，求解得到最佳阈值。 原始灰度图像 直方图 分割结果-二值图像 2002, Ver1.0 任明武，南京理工大学计算机系

30 = + 基于直方图选取阀值的原则一般有最小误差、一维熵、二维熵、可分离性等，尽管没有一种方法是万能的。 4.2.1 最小误差法
问题来源：假定有两类目标，其直方图如下： = + P1(z) P2(z) t E21(t) E12(t) 目标1的直方图 目标2的直方图 目标1和2的直方图 评价指标：总错误概率最小。 评价函数：设定阈值为T，则目标2错分成目标1的错误概率为： 2002, Ver1.0 任明武，南京理工大学计算机系

31 目标1错分成目标2的错误概率为： 总的错误概率为：
使E0取最小值的T即为最佳的阈值。取最小值即取一阶导数等于0时的T。假设p1(z)和p2(z)均为正态分布，得到如下结论(中间求导和解的过程忽略，可自己推导)，当p1(z)和p2(z)的方差相等时： 其中，P1和P2分别目标1和目标2所占整个图像的面积比，P1+P2=1。显然当P1=P2时，T=(u1+u2)/2。在一般情况下，同时满足 ,P1=P2是很难的。 2002, Ver1.0 任明武，南京理工大学计算机系

32 在一般情况下，上述参数是未知的，因此需要从图像的直方图来估计它们。在两个正态分布下的混合密度函数为：
实际的直方图为h(z)，因此h(z)和p(z)的均方误差(实际值与估计值之间的误差)为： 显然可以看出，该方法分割效果依赖于： (1)是否真是或基本是2类目标。 (2)是否真是或接近是正态分布。 令E取最小值，得到所需参数。 4.2.2 目标/背景最大差距法 问题来源：假定有两类目标，称之为背景和目标，定义它们之间的差距度量(差异程度的度量，常用类间的距离表示)为： 2002, Ver1.0 任明武，南京理工大学计算机系

33 其中，W0(t)和W1(t) 分别是当阈值等于t时，目标和背景分别占的比例，显然W0(t)+W1(t)=1。
评价函数：(1)基于分割出的目标和背景之间的差距最大 即在(gmin,gmax)之间穷举t，使得diffObj_Bkg取最大值的t即为所求。此乃Otsu方法。 (2)基于分割出的目标和背景与原图像之间的差距最大 ①二者之和最大 此仍Otsu方法 ②二者之积最大 其中， 思考：设t1和t2分别是在原始直方图和原始直方图平滑后得到的直方图上求得的阈值，t1等于t2吗？ 2002, Ver1.0 任明武，南京理工大学计算机系

34 Otsu：A Threshold Selection method from gray-level histogram,IEEE on
SMC-9,1979(3): 62-66 差距度量：计算机研究与发展，2001.5，Vol.28.No.5, pp 4.2.3基于熵的阀值选取（Entropy） 一维最大熵阈值分割 根据信息论，熵定义为： 式中p(x)是随机变量x的概率密度函数。对于数字图像来说，这个随机变量x 可以是灰度级值、区域灰度、梯度等特征。所谓灰度的一维熵最大，就是选择一个阈值，是图像用这个阈值分割出的两部分的一阶灰度统计的信息量最大。设为数字图像中灰度级i的像素点数，为灰度级i出现的概率，则 i=1,2,…,L 式中：N×N为图像总的像素数；L为图像的总的灰度级数。 2002, Ver1.0 任明武，南京理工大学计算机系

35 假设图中灰度级低于t的像素点构成目标区域(O)，灰度级高于t 的像素点构成背景区域(B),那么各概率在其本区域的分布分别为
O区： i=1,2,…,t B区： i=t+1,t+2,… ,L 其中： 对于数字图像，目标区域和背景区域的熵分别定义为 i=1,2,…,t i=t+1,t+2,…,L 则熵函数定义为 2002, Ver1.0 任明武，南京理工大学计算机系

36 当熵函数取得最大值时对应的灰度就是所求的最佳阈值，即：
二维最大熵阈值分割 由于灰度一维最大熵基于图像原始直方图，仅仅利用了点灰度信息而未充分利用图像的空间信息，所以当信噪比降低时，分割效果并不理想。在图像的特征中，点灰度无疑是最基本的特征，但它对噪声较敏感，区域灰度特征包含了图像的部分空间信息，且对噪声的敏感程度要低于点灰度特征。综合利用点灰度和区域灰度特征就可以较好地表征图像的信息，因此可采用利用图像点灰度和区域灰度均值的二维最大熵阈值法,即在二维直方图中求最佳阈值。 2002, Ver1.0 任明武，南京理工大学计算机系

37 其中N×N为图像的大小，那么{ , g,u=1,2,…,L}就是该图像关于点灰度－区域灰度均值的二维直方图。
二维直方图的构造 所谓的二维直方图就是象素的值g和其邻域的均值u的联合分布直方图h(g,u)。首先以原始灰度图像(L个灰度级)中各像素及其4邻域的4个像素为一个区域，计算出区域灰度均值图像(L个灰度级)，这样原始图像中的每一个像素都对应于一个点灰度－区域灰度均值对，这样的数据存在L×L种可能的取值。设为图像中点灰度为i及其区域灰度均值为j的像素点数，为点灰度－区域灰度均值对(i,j)发生的概率，则 其中N×N为图像的大小，那么{ , g,u=1,2,…,L}就是该图像关于点灰度－区域灰度均值的二维直方图。 在实际应用中，常采用递推算法来获得较高的运算速度。 关于基于熵的直方图阈值选取方法可见“图像分割方法综述”的参考文献，《模式识别与人工智能》.1999年9月第12卷第3期: 2002, Ver1.0 任明武，南京理工大学计算机系

38 4.2.4 直方图的构造 基于直方图的图象分割主要研究直方图构造和阈值选择两个问题。直方图构造近年来研究较少，由于缺乏一个实用的模型,基本上没有大的突破；但它直接决定着阈值选择的优劣，研究直方图的构造具有极大的实用价值。 除了使用图象中全部象素的灰度值构造一维直方图外，直方图的构造还有另外两种方式：(1) 二维直方图[2,3]，利用图象中各个象素点的灰度及其邻域的灰度均值构成。 (2) 局部象素直方图[4,5,6]，选择满足一定约束条件的象素的灰度值构造直方图。 二维直方图基于图象的所有象素中，目标点和背景点所占的比例最大，而目标区域和背景区域内部的象素灰度级比较均匀，点灰度与其邻域的灰度值相差不大，所以象素基本集中在二维直方图的对角线附近，偏离对角线的地方，直方图峰的高度急剧下降。二维直方图同时利用了象素的灰度信息和图象的空间信息，使用二维直方图的图象分割具有很好的抗噪能力。然而，这种利用图象中全部象素构造直方图的方法，与传统的一维直方图一样，不适合于图象中目标较小和较少时的情况，因为在此情况下目标象素的数目极少，其在直方图上常常表现为被背景和噪音淹没。相反，局部象素直方图能够很好地克服目标和背景占空比例严重不均的情况。文献[4]提出了仅使用具有较低的边缘强度的象素构造直方图的方法（内部象素直方图），即仅使 2002, Ver1.0 任明武，南京理工大学计算机系

39 用了目标和背景内部的象素，而忽略目标和背景之间的过渡象素。从而在保持直方图的峰值不变的情况下，直方图的谷点更低。后来又将其推广到更一般的形式，构造边缘强度倒数加权的全部象素的直方图（边缘强度倒数加权直方图）。然而，在目标很小时，由于位于目标内部的象素极少，而位于背景内部的象素极多，当背景的灰度分布范围较宽时，内部象素直方图和边缘强度倒数加权直方图上常常不存在对应于目标灰度的波峰，因而同样不适合目标较小和较少时的阈值选取。[5,6]使用相反的方法，仅使用具有较高的边缘强度的象素构造直方图（边缘象素直方图）。如果图象满足在目标和背景之间的象素具有较高的边缘强度而在其它位置的象素的边缘强度较低，则直方图上在目标和背景的灰度之间出现一个波峰，此波峰所对应的灰度值即是阈值。将其推广到更一般的形式，可构造边缘强度加权的全部象素的直方图（边缘强度加权直方图）。可是，在目标很小和很少时，目标和背景之间的边界象素较少，同时图象噪声又表现具有较高的边缘强度，边界象素直方图上得不到显著的波峰。尤其是，边界象素直方图还受到边缘强度算子和边界模式的影响，有时具有较高边缘强度的象素不位于边界上，而是位于目标和背景上，这时边界象素直方图上存在两个波峰，分别对应于目标和背景，而两峰之间的谷点才是真正的阈值。当目标和背景很大时，由于边缘点相对较少，边缘强度加权直方图到得不到显著的正确的波峰作为阈值。 2002, Ver1.0 任明武，南京理工大学计算机系

40 t 例： (1)利用边缘强度（梯度）大的象素构造直方图。 (2) 利用边缘强度小的象素构造直方图 边缘检测 2002, Ver1.0
任明武，南京理工大学计算机系

41 参考文献：0.任明武, 杨静宇, 孙涵,一种基于图象边缘模式的直方图构造新方法, 计算机研究与发展，2001, 38(8):972-976
1.Zhang Y.J. A survey of Evalution Methods for Image Segmentation. Pattern Recognition, 1996,Vol.29,No.8, pp 2.A.S.Abutaleb, “Automatic thresholding of Gray-Level Pictures Using Two-Demensional Entropy”, Computer Vision, Graphics, and Image Processing, 1989,vol.47,pp 3.A.D.Brink, Thresholding of Digital Images Using Two-Dimensional Entropies, Pattern Recognition, 1992, Vol.25, No.8, pp 4.D.P. Panda and A. Rosenfeld, “Image Segmentaion by pixel classificatiob in (gray level,gradient) space”,IEEE Trans. on Comput.,1978, Vol.27, pp 5.J.S.Weszka and A.Rosenfeld, “A Threshold Selection Technique”, IEEE Trans.on Comput.,1974, vol.23, pp 66. “A Survey of Threshold Selection Techniques”, Computer Graphics and Image Processing, 1978, Vol.7, pp: 2002, Ver1.0 任明武，南京理工大学计算机系

42 注：本文直方图指的是参考文献[0]得到的直方图。
2002, Ver1.0 任明武，南京理工大学计算机系

43 问题来源：光照不均，一个整体阀值不能解决问题。 解决方法：认为每一块是均匀的，或在某一块内光线的变化比较小， 不至于导致分割错误。 算法：
4.2.5 其他方法 1.双门限法 如：0<=黑<64 64<=红<192 192<=白<256 2.分块阈值 问题来源：光照不均，一个整体阀值不能解决问题。 解决方法：认为每一块是均匀的，或在某一块内光线的变化比较小， 不至于导致分割错误。 算法： ①重叠分块 ②算每一块的阀值，作为块中心象素的阀值 ③经过内插得出每一个象素对应的阀值 4.3 区域增长(region growing)(Split-Merge algorithm) 思想：(1)交互式给出种子(seeds) (2)规定某种增长规则，进行增长，得到若干个满足规则的区域(即分裂过程)。 2002, Ver1.0 任明武，南京理工大学计算机系

44 (3)分析区域之间的关系，包括空间和灰度上的关系，按某种规则进行合并，得到最终结果(即合并过程)。
例： 4.4 基于聚类的图像分割(clustering) 思想来自于模式识别理论。例，动态均值法 — k均值法的算法如下： (1) 随机地选K个样本，以它们的值代表每一类的均值u0， u1 ,uk-1。 (2) 按最近距离将数据分类。 (3)每次分类后计算均值u0， u1 ,uk-1 。若与上一次的值相等，则分类结 束；否则转到(2)。 2002, Ver1.0 任明武，南京理工大学计算机系

45 出发点：基于一个目标会在一定的灰度范围内稳定存在。 手段：序贯二值化。(得到若干个二值图像) 综合：从一系列二值图像中寻找某种稳定的东西。
例， 设 k=2 ，u0=1，u1=2 第一次： 第二次： 第三次： 4.5 基于某种稳定性的图像分割 出发点：基于一个目标会在一定的灰度范围内稳定存在。 手段：序贯二值化。(得到若干个二值图像) 综合：从一系列二值图像中寻找某种稳定的东西。 参考文献： 1. Ren Mingwu, Yang Jingyu, Sun Han, Tang Zhenmin, Split-and-Merge Segmentation using Relation Stable-state, Optical Engineering, 2003, vol.42, No.8, pp (SCI and EI indexed) 2. A.Pikaz, A.Averbuch. “Digital image thresholding based on topological stable-state”, Pattern Recognition. 29(5), pp , 1996. 2002, Ver1.0 任明武，南京理工大学计算机系

46 3.O'Gorman Lawrence, “Binarization and Multithresholding of Document Images Using Connectivity”, Graphics Models and Image Processing. 56(6), pp , 1994. 例： t 目标个数 120 1 2 . 80 2 . 80 个数 2 81 82 . 119 1 . 1 阈值 通过直方图可知目标的种类数和 灰度分界线(即最佳阈值) 2002, Ver1.0 任明武，南京理工大学计算机系

47 以上问题导致图象分割是图象处理、计算机视觉中最困难的问题，也许是“永远解决不了的问题”。
4.6 图像分割小结 图象分割面临的问题： (1)参数不直观 (2)参数很多 (3)光照不均 (4)目标的种类数未知 (5)不同的应用侧重点不一样 以上问题导致图象分割是图象处理、计算机视觉中最困难的问题，也许是“永远解决不了的问题”。 2002, Ver1.0 任明武，南京理工大学计算机系