《图像分析基础》PPT课件.ppt

1、2020/7/29,1,第七章 图像分析基础,2020/7/29,2,本章主要内容： 1.图像分割 2.图像描述 3.图像分析,2020/7/29,3,1.图像分割,图像分割的概念 把图像分解成构成它的部件和对象的过程 有选择性地定位感兴趣对象在图像中的位置和范围,2020/7/29,4,1.图像分割,图像分割的基本思路 从简到难，逐级分割 控制背景环境，降低分割难度 把焦点放在增强感兴趣对象，缩小不相干图像成分的干扰上,2020/7/29,5,1.图像分割,图像分割的基本策略 分割算法基于灰度值的两个基本特性：不连续性和相似性 检测图像像素灰度级的不连续性，找到点、线（宽度为1）、边（不定宽

2、度）。先找边，后确定区域。,2020/7/29,6,1.图像分割,图像分割的基本策略 检测图像像素的灰度值的相似性，通过选择阈值，找到灰度值相似的区域，区域的外轮廓就是对象的边,2020/7/29,7,1.图像分割 1.1边界分割法,点的检测 线的检测 边的检测,2020/7/29,8,1.图像分割 1.1边界分割法,点的检测 用空域的高通滤波器来检测孤立点 例：R = (-1 * 8 * 8 + 128 * 8) / 9 = (120 * 8) / 9 = 960 / 9 = 106 设 ：阈值：T = 64,8,8,8,8,128,8,8,8,8,-1,-1,-1,-1,8,-1,-1,-

3、1,-1,图像,模板,2020/7/29,9,1.图像分割 1.1边界分割法,点的检测 如果R的值等于0，说明当前检测点与的灰度值与周围点的相同 当R的值足够大时，说明该点的值与周围的点非常不同，是孤立点。通过阈值T来控制如T = 32、64、128等 |R| T 便检测到一个孤立点,2020/7/29,10,1.图像分割 1.1边界分割法,-1,-1,-1,2,2,2,-1,-1,-1,-1,-1,2,-1,2,-1,2,-1,-1,-1,2,-1,-1,2,-1,-1,2,-1,2,-1,-1,-1,2,-1,-1,-1,2,线的检测 通过比较典型模板的计算值，确定一个点是否在某个方向的线

4、上,2020/7/29,11,1.图像分割 1.1边界分割法,1,1,1,5,5,5,1,1,1,1,1,1,5,5,5,1,1,1,1,1,1,5,5,5,1,1,1,线的检测 R1 = -6 + 30 = 24 R2 = -14 + 14 = 0 R3 = -14 + 14 = 0 R4 = -14 + 14 = 0,2020/7/29,12,1.图像分割 1.1边界分割法,边的检测 边界的定义：一段边是两个具有相对不同灰度值特性的区域的边界线 适用于：假定问题中的区域是非常类似的，两个区域之间的过渡，仅仅根据灰度的不连续性便可确定 不适用于：当假定不成立时，阈值分割技术一般来说比边缘检测

5、更加实用,2020/7/29,13,1.图像分割 1.1边界分割法,边的检测,分割对象,分割对象,2020/7/29,14,1.图像分割 1.1边界分割法,边的检测 基本思想： 计算局部微 分算子,一阶微分,二阶微分,边界图像,截面图,2020/7/29,15,1.图像分割 1.1边界分割法,边的检测 一阶微分：用梯度算子来计算 特点：对于亮的边，边的变化起点是正的，结束是负的。对于暗边，结论相反。常数部分为零。 用途：用于检测图像中边的存在,2020/7/29,16,1.图像分割 1.1边界分割法,边的检测 二阶微分：通过拉普拉斯来计算 特点：二阶微分在亮的一边是正的，在暗的一边是负的。常数

6、部分为零。 用途： 1）二次导数的符号，用于确定边上的像素是在亮的一边，还是暗的一边。 2）0跨越，确定边的准确位置,2020/7/29,17,1.图像分割 1.1边界分割法,边的检测 梯度算子 函数f(x,y)在(x,y)处的梯度为一个向量： f = f / x , f / y 计算这个向量的大小为： f = mag(f ) = (f / x)2 +(f / y)21/2 近似为: f |x| + |y|,z2,z8,z5,z3,z9,z6,z1,z7,z4,2020/7/29,18,1.图像分割 1.1边界分割法,边的检测 梯度算子 梯度的方向角为： (x,y) = tan(y / x)

7、Sobel算子为： x = (z7 + 2z8 + z9) - (z1 + 2z2 + z3) y = (z3 + 2z6 + z9) - (z1 + 2z4 + z7),-2,2,0,-1,1,0,-1,1,0,0,0,0,-1,-1,-2,1,1,2,x,y,2020/7/29,19,1.图像分割 1.1边界分割法,边的检测 Sobel梯度算子的使用与分析 1. 直接计算y、x可以检测到边的存在， 以及从暗到亮，从亮到暗的变化 2. 仅计算|x|，产生最强的响应是正交 于x轴的边； |y|则是正交于y轴的边。 3. 由于微分增强了噪音，平滑效果是Sobel 算子特别引人注意的特性,2020

8、/7/29,20,1.图像分割 1.1边界分割法,边的检测 拉普拉斯 二维函数f(x,y)的拉普拉斯是一个二阶的微分定义为： 2f = 2f / x2 , 2f / y2 可以用多种方式被表示为数字形式。对于一个3x3的区域，经验上被推荐最多的形式是： 2f = 4z5 (z2 + z4 + z6 + z8),z2,z8,z5,z3,z9,z6,z1,z7,z4,2020/7/29,21,1.图像分割 1.1边界分割法,边的检测 拉普拉斯 定义数字形式的拉普拉斯的基本要求是，作用于中心像素的系数是一个正数，而且其周围像素的系数为负数，系数之和必为0。,-1,-1,4,0,0,-1,0,0,-1

9、,2020/7/29,22,1.图像分割 1.1边界分割法,边的检测 拉普拉斯算子的分析： 缺点：对噪音的敏感；会产生双边效果；不能检测出边的方向 应用：拉普拉斯算子不直接用于边的检测，通常只起第二位的角色； 检测一个像素是在边的亮的一边还是暗的一边 利用零跨越，确定边的位置,2020/7/29,23,1.图像分割 1.2边缘连接法,局部处理法 Hough变换,2020/7/29,24,1.图像分割 1.2边缘连接法,边缘连接法 由于噪音的原因，边界的特征很少能够被完整地描述，在亮度不一致的地方会中断。 因此典型的边检测算法后面总要跟随着连接过程和其它边界检测过程，用来归整边像素，成为有意义的

10、边。,2020/7/29,25,1.图像分割 1.2边缘连接法,局部连接处理 连接处理的时机和目的 连接处理的原理 局部连接算法描述,2020/7/29,26,1.图像分割 1.2边缘连接法,局部连接处理 连接处理的时机和目的： 时机：对做过边界检测的图像进行 目的：连接间断的边 连接处理的原理： 用比较梯度算子的响应强度和梯度方向确定两个点是否同属一条边,2020/7/29,27,1.图像分割 1.2边缘连接法,局部连接处理 连接处理的原理： 通过比较梯度，确定两个点的连接性： 对于点(x,y)，判断其是否与邻域内的边界点 (x,y)相似，当： |f (x,y) f (x,y)| T 其中T

11、是一个非负的阈值,2020/7/29,28,1.图像分割 1.2边缘连接法,局部连接处理 连接处理的原理： 比较梯度向量的方向角 对于点(x,y)，判断其是否与邻域内的边界点 (x,y)的方向角相似，当： | (x,y) (x,y)| A 其中A是一个角度阈值,2020/7/29,29,1.图像分割 1.2边缘连接法,局部连接处理 连接处理的原理： 当梯度值和方向角都是相似的，则点(x,y)，与边点界(x,y)是连接的,2020/7/29,30,1.图像分割 1.2边缘连接法,局部连接处理 局部连接算法描述： 1）设定A、T的阈值大小，确定邻域的大小 2）对图像上每一个像素的邻域点进行分析，

12、判断是否需要连接。 3）记录像素连接的情况，另开一个空间， 给不同的边以不同的标记。 4）最后，删除孤立线段，连接断开的线段。,2020/7/29,31,1.图像分割 1.2边缘连接法,Hough变换 问题的提出 Hough变换的基本思想 算法实现 Hough变换的扩展,2020/7/29,32,1.图像分割 1.2边缘连接法,Hough变换问题的提出 在找出边界点集之后，需要连接，形成完整的边界图形描述,2020/7/29,33,1.图像分割 1.2边缘连接法,Hough变换的基本思想 对于边界上的n个点的点集，找出共线的点集和直线方程。 对于任意两点的直线方程：y = ax + b，构造一

13、个参数ab的平面，从而有如下结论：,a,b,2020/7/29,34,1.图像分割 1.2边缘连接法,Hough变换的基本思想 xy平面上的任意一条直线，对应在参数ab平面上都有一个点。 过xy平面一个点(x,y)的所有直线，构成参数ab平面上的一条直线。 如果点(x1,y1)与点(x2,y2)共线，那么这两点在参数ab平面上的直线将有一个交点。 在参数ab平面上相交直线最多的点，对应的xy平面上的直线就是我们的解。,2020/7/29,35,1.图像分割 1.2边缘连接法,Hough变换的基本思想,a,b,A,2020/7/29,36,1.图像分割 1.2边缘连接法,Hough变换算法实现

14、由于垂直直线a,为无穷大，我们改用极坐标形式：xcos + ysin = 参数平面为 ，对应不是直线而是正弦曲线 使用交点累加器，或交点统计直方图，找出相交线段最多的参数空间的点，然后找出该点对应的xy平面的直线线段。,2020/7/29,37,1.图像分割 1.2边缘连接法,Hough变换的扩展 Hough变换不只对直线，也可以用于圆： （x c1）2 + (y - c2)2 = c32 这时需要三个参数的参数空间。,2020/7/29,38,1.图像分割 1.3阈值分割法,阈值分割法 通过交互方式得到阈值 通过直方图得到阈值 通过边界特性选择阈值 简单全局阈值分割 分割连通区域 基于多个变

15、量的阈值,2020/7/29,39,1.图像分割 1.3阈值分割法,阈值分割法 阈值分割法的基本思想： 确定一个合适的阈值T（阈值选定的好坏是此方法成败的关键）。 将大于等于阈值的像素作为物体或背景，生成一个二值图像。 If f(x,y) T set 255 Else set 0 在四邻域中有背景的像素，既是边界像素。,0,255,255,0,255,0,255,255,255,2020/7/29,40,1.图像分割 1.3阈值分割法,阈值分割法 阈值分割法的特点： 适用于物体与背景有较强对比的情况，重要的是背景或物体的灰度比较单一。（可通过先求背景，然后求反得到物体） 这种方法总可以得到封闭

16、且连通区域的边界。,灰度值,f(x0,y0),T,2020/7/29,41,1.图像分割 1.3阈值分割法,通过交互方式得到阈值 基本思想： 在通过交互方式下，得到对象（或背景 ）的灰度值，比得到阈值T容易得多。 假设：对象的灰度值(也称样点值)为f(x0,y0),且： T = f(x0,y0) R 有： f(x,y) T f(x,y) f(x0,y0) R |f(x,y) f(x0,y0)| R 其中R 是容忍度，可通过试探获得。,2020/7/29,42,1.图像分割 1.3阈值分割法,通过交互方式得到阈值 实施方法： （1）通过光标获得样点值f(x0,y0) （2）选取容忍度R （3）i

17、f |f(x,y)f(x0,y0)| R set 255 else set 0,2020/7/29,43,1.图像分割 1.3阈值分割法,通过直方图得到阈值 基本思想 边界上的点的灰度值出现次数较少,T,2020/7/29,44,1.图像分割 1.3阈值分割法,通过直方图得到阈值 取值的方法： 取直方图谷底，为最小值的灰度值为阈值T 缺点：会受到噪音的干扰，最小值不是预期的阈值，而偏离期望的值； 改进：取两个峰值之间某个固定位置，如中间位置上。由于峰值代表的是区域内外的典型值，一般情况下，比选谷底更可靠，可排除噪音的干扰,2020/7/29,45,1.图像分割 1.3阈值分割法,通过直方图得到

18、阈值,T,2020/7/29,46,1.图像分割 1.3阈值分割法,通过直方图得到阈值 对噪音的处理 对直方图进行平滑处理，如最小二乘法，等不过点插值。,2020/7/29,47,1.图像分割 1.3阈值分割法,通过边界特性选择阈值 基本思想： 如果直方图的各个波峰很高、很窄、对称，且被很深的波谷分开时，有利于选择阈值。 为了改善直方图的波峰形状，我们只把区域边缘的像素绘入直方图，而不考虑区域中间的像素。 用微分算子，处理图像，使图像只剩下边界中心两边的值。,2020/7/29,48,1.图像分割 1.3阈值分割法,通过边界特性选择阈值 基本思想： 这种方法有以下优点： 1)在前景和背景所占区

19、域面积差别很大时，不会造一个灰度级的波峰过高，而另一个过低 2)边缘上的点在区域内还是区域外的概率是相等的，因此可以增加波峰的对称性 3)基于梯度和拉普拉斯算子选择的像素，可以增加波峰的高度,2020/7/29,49,1.图像分割 1.3阈值分割法,通过边界特性选择阈值 算法的实现： 1）对图像进行梯度计算，得到梯度图像。 2）得到梯度值最大的那一部分（比如10%） 的像素直方图 3）通过直方图的谷底，得到阈值T。 如果用拉普拉斯算子，不通过直方图，直接得到阈值，方法是使用拉普拉斯算子过滤图像，将0跨越点对应的灰度值为阈值T.,2020/7/29,50,1.图像分割 1.3阈值分割法,简单全局

20、阈值分割 基本思想：用前述方法获得阈值T，并产生一个二值图，区分出前景对象和背景 算法实现： 规定一个阈值T，逐行扫描图像。 凡灰度级大于T的，颜色置为255；凡灰度级小于T的，颜色置为0。 适用场合：明度图像是可以控制的情况，例如用于工业监测系统中。,2020/7/29,51,1.图像分割 1.3阈值分割法,分割连通区域 基本思想：用前述方法获得阈值T，并产生一个二值图，区分出单独的连通前景对象和背景区域 算法实现： 规定一个阈值T，上下左右4个方向进行逐行扫描图像 凡灰度级大于T的，颜色置为255；凡灰度级小于T的，颜色置为0。,2020/7/29,52,1.图像分割 1.3阈值分割法,分

21、割连通区域 适用场合：印前等。 先左后右，先上半部分、后下半部分,2020/7/29,53,1.图像分割 1.3阈值分割法,基于多个变量的阈值 基本思想：把前面的方法扩展到多维空间，则寻找波谷的过程，变为寻找点簇的过程。 算法实现： 各维分量波谷之间进行逻辑与运算，从波谷重合的点，得到实际的阈值T。 应用场合：有多个分量的颜色模型，如RGB模型、CMYK模型、HSI模型,2020/7/29,54,1.图像分割 1.4面向区域的分割,基本概念 通过像素集合的区域增长 区域分裂与合并,2020/7/29,55,1.图像分割 1.4面向区域的分割,基本概念 目标：将区域R划分为若干个子区域R1,R2

22、,Rn，这些子区域满足5个条件： 1)完备性： 2)连通性：每个Ri都是一个连通区域 3)独立性：对于任意ij，RiRj= ,2020/7/29,56,1.图像分割 1.4面向区域的分割,基本概念 4)单一性：每个区域内的灰度级相等， P（Ri）= TRUE，i = 1,2,n 5)互斥性：任两个区域的灰度级不等， P（RiRj）= FALSE，ij,2020/7/29,57,1.图像分割 1.4面向区域的分割,通过像素集合的区域增长 算法实现： 1）根据图像的不同应用选择一个或一组种子，它或者是最亮或最暗的点，或者是位于点簇中心的点。 2）选择一个描述符（条件） 3）从该种子开始向外扩张，首

23、先把种子像素加入集合，然后不断将与集合中各个像素连通、且满足描述符的像素加入集合 4）上一过程进行到不再有满足条件的新结点加入集合为止。,2020/7/29,58,1.图像分割 1.4面向区域的分割,通过像素集合的区域增长 算法实现：,区域A,区域B,种子像素,2020/7/29,59,1.图像分割 1.4面向区域的分割,区域分裂与合并 算法实现： 1）对于图像中灰度级不同的区域，均分为四个子区域。 2）如果相邻的子区域所有像素的灰度级相同，则将其合并。 3）反复进行上两步操作，直至不再有新的分裂与合并为止。,2020/7/29,60,1.图像分割 1.4面向区域的分割,区域分裂与合并 算法实

24、现：,2020/7/29,61,1.图像分割 1.4面向区域的分割,区域分裂与合并 算法实现：实际应用中还可作以下修改： P(Ri)的定义为： 1）区域内多于80%的像素满足不等式 |zj-mi|=2i， 其中：zj是区域Ri中第j个点的灰度级， mi是该区域的平均灰度级， i是区域的灰度级的标准方差。 2）当P(Ri)=TRUE时，将区域内所有像素的灰度级置为mi。,2020/7/29,62,1.图像分割 1.5数学形态学,形态学（Morphology）原是对于动植物调查时采取的某种形式的研究。数学形态学（Mathematical Morphology）是分析几何形状和结构的数学方法，它建立

25、在集合代数的基础上，是用集合论方法定量描述集合结构的学科。1985年之后，数学形态学逐渐成为分析图像几何特征的工具。,2020/7/29,63,1.图像分割 1.5数学形态学,数学形态学包括一组基本的形态学运算子：腐蚀（Erosion）、膨胀（Dilation）、开（Opening）、闭（Closing）等。运用这些算子及其组合来进行图像形状和结构的分析及处理。,形态学的理论基础是集合论。在图像处理中形态学的集合代表着黑白和灰度图像的形状，如黑白图像中的所以黑像素点组成了此图像的完全描述。通常我们选择图像中感兴趣的目标图像区域像素集合来进行形态学变换。,2020/7/29,64,1.图像分割

26、1.5数学形态学,基本运算,集合关系,设A和S为R2的子集，A为为物体区域，B为某种结构单元，则B结构单元对A的关系有三类：,S包含于A,S包含于A,S击不中(MISS)A，,平移,，记A平移x为Ax，定义为,2020/7/29,65,1.图像分割 1.5数学形态学,膨胀,S为结构单元，广义的膨胀定义为,当S为33结构元时，广义膨胀就为一般意义上的膨胀。,一般意思上的膨胀是将与物体边界接触的背景像素合并到物体中的过程。 如果物体是个圆，进行一次膨胀后，它的直径会增大两个像素。 如果两个物体在某处用少于三个像素分开，膨胀后这两个物体就合并成为一个物体了。,2020/7/29,66,1.图像分割

27、1.5数学形态学,腐蚀,S为结构单元，广义的腐蚀运算定义为,当S为33结构元时，广义腐蚀就为一般意义上的腐蚀。,简单的腐蚀运算是将一个物体沿边界减小的过程，在物体的周边较少一个像素。 如果物体是一个圆，则进行一次腐蚀运算后，它的直径减少2。,2020/7/29,67,1.图像分割 1.5数学形态学,腐蚀和膨胀示意图,腐蚀,二值图,膨胀,2020/7/29,68,1.图像分割 1.5数学形态学,开和闭运算,腐蚀运算后再进行膨胀运算的组合运算称为开运算（Opening）。,开运算的效果： 删除小物体； 将物体拆分为小物体； 平滑大物体边界而不明显改变它们的面积；,膨胀运算后再进行腐蚀运算的组合运算

28、称为闭运算（Closing）。,闭运算的效果： 填充物体的小洞； 连接相近的物体； 平滑物体的边界而不明显改变它们的面积。,2020/7/29,69,1.图像分割 1.5数学形态学,腐蚀和膨胀的衍生运算,腐蚀的反复进行会导致物体消失，而膨胀的反复进行的结果是所以物体都合并到一起了。 我们可以改变这些过程来产生一些别的效果以适应实际的应用。,收缩,保持单个像素的物体不变的腐蚀运算称为收缩(Shrinking)。,细化,我们可以修改腐蚀计算过程来保持物体不被分开。首先我们进行有条件的常规的腐蚀过程，我们只是将要删除的像素打上标记而并不真正删除；然后逐步访问打上标记的像素，如果删除该标记像素不会分开

29、物体，就删除它，否则就保留它。以上过程就是细化(Thinning)。,细化的结果是把曲线型物体变成一个像素宽的线型图。,2020/7/29,70,1.图像分割 1.5数学形态学,骨骼化,和细化相关的一个算子是骨骼化，也被称为中轴变换或火烧草场算法。中轴是和边界上至少两点相切的圆的圆心的轨迹。可以用火烧草场来说明，设物体区域上铺满了草料，火从物体边界同时均匀地烧起，最后草场全部烧光火熄灭的地方就是它的骨骼或骨架。,中轴变换的火烧草场算法示意图,修剪,在很多情况下，细化或骨骼化过程会留下很多短刺，这些是有两三个像素点的分支。这些短刺是由于边界上的单个像素的摆动引起的。短刺可以用33的算子来移去端点

30、，然后重新建立删去的分支。,2020/7/29,71,1.图像分割 1.5数学形态学,加厚,不把相近物体合并的膨胀过程称为加厚(Thickening)。和细化过程一样，它也可以分两步完成。和它互补的操作是对背景进行细化，任何一种腐蚀类的操作都伴随着膨胀类的操作作用与互补的图像区域上。,一些分割技术使用非常紧凑的边界来包围物体来保证不出现物体的错误合并。通常，用来分割物体最好的边界总是太紧，给后续的测量带来困难。加厚操作可以对此进行修正，它增大边界而不合并物体。,2020/7/29,72,2.图像描述,描述的基本概念 表示法设计 边界描述 关系描述,2020/7/29,73,2.图像描述 2.1

31、 描述的基本概念,基本概念 在用前一章的方法，把图像分割后，为了进一步的处理，分割后的图像一般要进行形式化的描述 解决形式化表达问题一般有两种选择： 1）根据区域的外部特征来进行形式化表示 2）根据区域的内部特征（比较区域内部的象素值）来来进行形式化表示,2020/7/29,74,2.图像描述 2.1 描述的基本概念,基本概念 选择表达方式，要本着使数据变得更有利于下一步的计算工作。下一步工作是基于所选的表达方式描述这个区域，一般情况下： 1）如果关注的焦点是形状特性，选择外部表示方式 2）如果关注的焦点是反射率特性，如颜色、文理时，选择内部表示方式。 3）所选表示方式，应该对尺寸、变换、旋转

32、等变量尽可能的不敏感,2020/7/29,75,2.图像描述 2.2 表示法设计,链码 多边形逼近 外形特征 边界分段 区域骨架,2020/7/29,76,2.图像描述 2.2 表示法设计,链码 定义：1）链码是一种边界的编码表示法。 2）用边界的方向作为编码依据。为简化边界的描述。一般描述的是边界点集。,0,1,2,3,0,1,4,7,2,3,5,4-链码,8-链码,2020/7/29,77,2.图像描述 2.2 表示法设计,链码 算法： 给每一个线段一个方向编码。 有4-链码和8-链码两种编码方法。 从起点开始，沿边界编码，至起点被重新碰到，结束一个对象的编码。,2020/7/29,78,

33、2.图像描述 2.2 表示法设计,链码举例：,4-链码：000033333322222211110011,2020/7/29,79,2.图像描述 2.2 表示法设计,链码 问题1： 1）链码相当长。 2）噪音会产生不必要的链码。 改进1： 1）加大网格空间。 2）依据原始边界与结果的接近程度，来确定新点的位置。,2020/7/29,80,2.图像描述 2.2 表示法设计,链码举例：,4-链码：003332221101,2020/7/29,81,2.图像描述 2.2 表示法设计,链码 问题2： 1）由于起点的不同，造成编码的不同 2）由于角度的不同，造成编码的不同 改进2： 1）从固定位置作为起

34、点(最左最上)开始编码 2）通过使用链码的首差代替码子本身的方式,2020/7/29,82,2.图像描述 2.2 表示法设计,链码 循环首差链码：用相邻链码的差代替链码 例如：4-链码 10103322 循环首差为：33133030 循环首差：1 - 2 = -1(3) 3 - 0 = 3 0 - 1 = -1(3)3 - 3 = 0 1 - 0 = 12 - 3 = -1(3) 0 - 1 = -1(3)2 - 2 = 0,2020/7/29,83,2.图像描述 2.2 表示法设计,链码 应用背景： 如果边界的本身对于旋转和比例修改来说是无变化的，使用链码才是正确的。一般来说这是不可能的，实

35、际应用时还需要改进。 用链码后，对象只要用1)起点坐标，2)周长（边界点数）3)链码，4)对象编号，就可以描述。 链码一般用于一幅图像中有多个对象的情况，对单个对象不适用。,2020/7/29,84,2.图像描述 2.2 表示法设计,多边形逼近 基本思想：用最少的多边形线段，获取边界形状的本质。 寻找最小基本多边形的方法一般有两种：点合成法和边分裂法,2020/7/29,85,2.图像描述 2.2 表示法设计,多边形逼近 点合成算法思想举例：,2020/7/29,86,2.图像描述 2.2 表示法设计,多边形逼近 合成点算法： 1）沿着边界选两个相邻的点对，计算首尾连接直线段与原始折线段的误差

36、。 2）如果误差小于预先设置的阈值。去掉中间点，选新点对与下一相邻点对，重复1）；否则，存储线段的参数，置误差为0，选被存储线段的终点为起点，重复1）2）。 3）当程序的第一个起点被遇到，程序结束。,2020/7/29,87,2.图像描述 2.2 表示法设计,多边形逼近 合成点算法的问题： 顶点一般不对应于边界的拐点（如拐角）。因为新的线段直到超过误差的阈值才开始。 下面讲到的分裂法可用于缓解这个问题,2020/7/29,88,2.图像描述 2.2 表示法设计,多边形逼近 边分裂算法思想举例：,2020/7/29,89,2.图像描述 2.2 表示法设计,多边形逼近 分裂边算法： （1）连接边界

37、线段的两个端点（如果是封闭边界，连接最远点）； （2）如果最大正交距离大于阈值，将边界分为两段，最大值点定位一个顶点。重复（1）； （3）如果没有超过阈值的正交距离，结束。,2020/7/29,90,2.图像描述 2.2 表示法设计,外形特征 基本思想： 外形特征是一种用一维函数表达边界的方法。基本思想是把边界的表示降到一维函数,2020/7/29,91,2.图像描述 2.2 表示法设计,外形特征 函数定义质心角函数：边上的点到质心的距离r，作为夹角的的函数。,A,r,r(),2,A,2020/7/29,92,2.图像描述 2.2 表示法设计,外形特征 举例：,A,r,r(),A,2020/7

38、/29,93,2.图像描述 2.2 表示法设计,外形特征 问题：函数过分依赖于旋转和比例的变化 改进： 对于旋转两种改进： a.选择离质心最远的点作为起点 b.选择从质心到主轴最远的点作为起点 对于比例变换： 对函数进行正则化，使函数值总是分布在相同的值域里，比如说0，1,2020/7/29,94,2.图像描述 2.2 表示法设计,边界分段 基本概念： 一个任意集合S（区域）的凸起外缘H是：包含S的最小凸起的集合 H-S的差的集合被称为集合S的凸起补集D,S,S,D,S + D = H,2020/7/29,95,2.图像描述 2.2 表示法设计,边界分段 分段算法： 给进入和离开凸起补集的变换

39、点打标记来划分边界段。 优点：不依赖于方向和比例的变化,S,2020/7/29,96,2.图像描述 2.2 表示法设计,边界分段 问题： 噪音的影响，导致出现零碎的划分。 解决的方法： 先平滑边界，或用多边形逼近边界，然后再分段,2020/7/29,97,2.图像描述 2.2 表示法设计,区域骨架 基本思想 表示一个平面区域结构形状的重要方法是把它削减成图形。这种削减可以通过细化（也称为抽骨架）算法，获取区域的骨架来实现 Blum的中轴变换方法（MAT） 设:R是一个区域，B为R的边界点，对于R中的点p，找p在B上“最近”的邻居。如果p有多于一个的邻居，称它属于R的中轴（骨架）,2020/7/

40、29,98,2.图像描述 2.2 表示法设计,区域骨架 问题：计算量大,p,R,B,2020/7/29,99,2.图像描述 2.2 表示法设计,区域骨架 算法改进思想 在保证产生正确的骨架的同时，改进算法的效率。比较典型的是一类细化算法，它们不断删去边缘，但保证删除满足： （1）不移去端点 （2）不破坏连通性 （3）不引起区域的过度腐蚀,2020/7/29,100,2.图像描述 2.2 表示法设计,区域骨架 一种细化二值区域的算法 假设区域内的点值为1，背景值为0 这个方法由对给定区域的边界点连续进行两个基本操作构成 这里边界点是指任何值为1且至少有一个8邻域上的点为0的象素,2020/7/2

41、9,101,2.图像描述 2.2 表示法设计,区域骨架 基本操作1 对于满足以下四个条件的边界点打标记准备删除： (a) 2N(p1)6 其中N(p1)是点p1的邻域中1的个数，即：N(p1)=p2+p3+p9 (b) S(p1) = 1 其中S(p1)是按p2,p3,p9顺序，0-1转换的个数 (c) p2 * p4 * p6 = 0 （p2 、p4 、p6 至少有一个0） (d) p4 * p6 * p8 = 0 （p4 、p6 、p8 至少有一个0）,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,

42、p4,p7,p6,p5,2020/7/29,102,2.图像描述 2.2 表示法设计,区域骨架 所有条件都满足，才打删除标记。删除并不立即进行，而是等到对所有边界点都打完标记后，再把作了标记的点一起删除。 举例: N(p1) = 4 S(p1) = 3 p2*p4*p6 = 0 p4*p6*p8 = 0 第2个条件没满足不打标记,0,0,p1,1,1,0,1,0,1,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,2020/7/29,103,2.图像描述 2.2 表示法设计,区域骨架 基本操作2 条件(a)、(b)与操作1相同 条件(

43、c)、(d)改为： c) p2* p4* p8= 0 d) p2* p6* p8= 0,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,2020/7/29,104,2.图像描述 2.2 表示法设计,区域骨架 细化算法 细化算法的一轮操作包括： 按操作1，给边界点打标记删除点 按操作2，给边界点打标记删除点 这个基本过程反复进行，直至没有点可以删除为止。此时算法终止。,2020/7/29,105,2.图像描述 2.2 表示法设计,区域骨架 算法分析： 1）条件a)的分析：当轮廓点p1的8邻域上有1个或7个值为1的点时，不满足条件a。 有

44、1个点说明：p1是骨架上的终点，显然不能删除 有7个点说明：如果删除p1会引起区域的腐蚀 2）条件b)的分析：当p1在宽度为1的笔划上时，不满足条件b。因而该条件保证了骨架的连续性。,2020/7/29,106,2.图像描述 2.2 表示法设计,区域骨架 算法分析： （3）当(p4=0 or p6=0)or(p2=0 and p8=0)时，条件c,d同时满足。满足这个条件的点可能是右边、下边、左上角的边界点。任何一种情况下，p1都不是骨架的一部分，应被删除。 当(p4=0 and p6=0)or(p2=0 or p8=0)时，条件c,d同时满足。满足这个条件的点可能是左边、上边、右下角的边界点

45、，应被删除。,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,2020/7/29,107,2.图像描述 2.2 表示法设计,区域骨架 例:,2020/7/29,108,2.图像描述 2.3 边界描述,简单描述子 形状数 傅立叶描述子 矩量,2020/7/29,109,2.图像描述 2.3 边界描述,简单描述子 边界的周长： 是最简单的描述符之一。沿轮廓线计算象素的个数，给出了一个长度的近似估计 边界的直径：边界B的直径是： Diam(B) = maxD(pi, pj) D是欧氏距离或几何距离，pi, pj是边界上的点。直径的长度和直径

46、的两个端点连线（这条线被称为边界的主轴）的方向，是关于边界的有用的描述符。,2020/7/29,110,2.图像描述 2.3 边界描述,简单描述子 边界的直径举例,2020/7/29,111,2.图像描述 2.3 边界描述,简单描述子 边界的曲率： 曲率被描述为斜率的变化率。近似：用相邻边界线段（描述为直线）的斜率差作为在边界线交点处的曲率描述子。 交点a处的曲率为 dk = k1 k2 其中k1、k2 为相邻线段的斜率,a,k1,k2,2020/7/29,112,2.图像描述 2.3 边界描述,简单描述子 边界的凸线段点： 当顶点p上的斜率是非负时，称其为凸线段上的点 边界的凹线段点： 当顶

47、点p上的斜率为负时，称其为凹线段上的点,2020/7/29,113,2.图像描述 2.3 边界描述,简单描述子 边界的凸线段点P1： 边界的凹线段点P2：,P1,P2,2020/7/29,114,2.图像描述 2.3 边界描述,形状数 形状数定义：最小循环首差链码。 循环首差链码：用相邻链码的差代替链码 例如：4-链码 10103322 循环首差为：33133030 循环首差: 1 - 2 = -1(3) 3 - 0 = 3 0 - 1 = -1(3)3 - 3 = 0 1 - 0 = 1 2 - 3 = -1(3) 0 - 1 = -1(3)2 - 2 = 0,2020/7/29,115,2

48、.图像描述 2.3 边界描述,形状数 形状数定义： 例如： 4-链码 ：10103322 循环首差 ：33133|030 形状数 ：03033133 形状数序号n的定义： 形状数中阿拉伯数字的个数，对于封闭边界序号是偶数。如order4、6、8。,2020/7/29,116,2.图像描述 2.3 边界描述,形状数 形状数例如：,序号4,链码：0321 首差：3333 形状：3333,序号6,链码：003221 首差：303303 形状：033033,序号8,链码：00032221 首差：30033003 形状：00330033,2020/7/29,117,2.图像描述 2.3 边界描述,形状数

49、 形状数例如：,序号6,链码：033211 首差：330330 形状：033033,序号6,链码：003221 首差：303303 形状：033033,2020/7/29,118,2.图像描述 2.3 边界描述,形状数 问题： 虽然链码的首差是不依赖于旋转的，但一般情况下边界的编码依赖于网格的方向。 改进： 规整化网格方向，具体方法如下：,2020/7/29,119,2.图像描述 2.3 边界描述,形状数 几个基本概念： 边界最大轴a:是连接距离最远的两个点的线段 边界最小轴b:与最大轴垂直，且其长度确定的包围盒刚好包围边界。 边界离心率c：最大轴长度与最小轴长度的比 c = a / b 基本

50、矩形: 包围边界的矩形。,2020/7/29,120,2.图像描述 2.3 边界描述,形状数 基本概念举例,边界最大轴a,边界最小轴b,基本矩形,2020/7/29,121,2.图像描述 2.3 边界描述,形状数 规整化网格方向算法的思想： 大多数情况下，将链码网格与基本矩形对齐，即可得到一个唯一的形状数。 对一个给定的形状序号，处理步骤如下： （1）我们找出一个序号为n的矩形，它的离心率最接近于给定形状的基本矩形的离心率。,2020/7/29,122,2.图像描述 2.3 边界描述,形状数 （2）然后再用这个矩形构造网格。 例如: 如果n=12，所有序号为12的矩形（即周长为12）为2*4，

51、3*3，1*5。如果2*4矩形的离心率最接近于给定边界的基本矩形的离心率，我们建立一个2*4的网格。 （3）再得到链码。 （4）最后，再得到循环首差。 （5）首差中的最小循环数即为形状数。,2020/7/29,123,2.图像描述 2.3 边界描述,形状数 规整化网格方向算法举例：,链码：000033222121 首差：300030300313 形状：000303003133,0,1,2,3,2020/7/29,124,2.图像描述 2.3 边界描述,傅立叶描述子 基本思想： （1）对于XY平面上的每个边界点，将其坐标用复数表示为： s(k) = x(k) + jy(k) k=0,1,N-1,

52、y0,y1,x0,x1,jy,x,x(k) = xk y(k) = yk,2020/7/29,125,2.图像描述 2.3 边界描述,傅立叶描述子 基本思想： （2）进行离散傅立叶变换 N-1 a(u) =1/N s(k)exp(-j2uk/N) u=0,1,N-1 u=0 N-1 s(k) = a(u)exp(j2uk/N) k=0,1,N-1 u=0 a(u)被称为边界的傅立叶描述子,2020/7/29,126,2.图像描述 2.3 边界描述,傅立叶描述子 基本思想： （3）选取整数 MN-1，进行逆傅立叶变换（重构） M-1 s(k) = a(u)exp(j2uk/N) k=0,1,N-

53、1 u=0 这时，对应于边界的点数没有改变，但在重构每一个点所需要的计算项大大减少了。如果边界点数很大，M一般选为2的指数次方的整数。,2020/7/29,127,2.图像描述 2.3 边界描述,傅立叶描述符 M的选取与描述符的关系 在上述方法中，相当于对于u M-1的部分舍去不予计算。由于傅立叶变换中高频部分对应于图像的细节描述，因此M取得越小，细节部分丢失得越多。,2020/7/29,128,2.图像描述 2.3 边界描述,傅立叶描述符 优点 1）使用复数作为描述符，对于旋转、平移、放缩等操作和起始点的选取不十分敏感。 2）以上几何变换均可以通过对描述子函数作简单变换来获得。,2020/7

54、/29,129,2.图像描述 2.3 边界描述,矩量 基本思想： 将描述形状的任务减少至描述一个一维函数，边界段和特征的形状可以用矩量来量化地描述 矩量的定义： 把边界当作直方图函数：g(r),r,g(r),2020/7/29,130,2.图像描述 2.3 边界描述,矩量 矩量的定义： L n(r) = (ri- m)ng(ri) i=1L 其中 m = rig(ri) i=1 这里L是边界上点的数目, n(r)是边界的矩量,2020/7/29,131,2.图像描述 2.3 边界描述,矩量 矩量的优点： 实现是直接的 附带了一种关于边界形状的“物理”解释 对于旋转的不敏感性 为了使大小比例不敏

55、感，可以通过伸缩r的范围来将大小正则化。,2020/7/29,132,2.图像描述 2.4 关系描述,基本思想 阶梯关系编码 骨架关系编码 方向关系编码 内角关系编码 树结构关系编码,2020/7/29,133,2.图像描述 2.4 关系描述,基本思想： 通过挖掘各个成分之间的结构关系来描述边界 图像中各个部分间的结构关系是二维的，而串是一维的，期望找到一种方法把二维关系转化为一维的串 主导思想是考虑物体各个部分的连接线段,2020/7/29,134,2.图像描述 2.4 关系描述,阶梯关系编码 对于如下阶梯形边界，定义两个基本元素a,b,a,b,a,a,a,b,b,b,2020/7/29,135,2.图像描述 2.4 关系描述,阶梯结构关系 定义如下产生规则： (1) S-aA (2) A-bS (3) A-b 其中S、A是变量 举例：,(1,3),(1,2,1,3),(1,2,12,1,3)