DVIP13 表示与描述课件

1、第13章 表示与描述Representation and Description 门爱东教授表示与描述在将一幅图像分割成不同区域后，经常需要使用一种更适合于计算机进一步处理的形式，对得到的分割像素集合进行表示和描述。基本上，表示一个区域包括两种选择：可以用其外部特征来表示区域（如它的边界）当关注的重点是形状特征时，例如长度、连接端点的直线方向以及边界上的凹陷的数目等，可选择一种外部表示；可以用其内部特征来表示区域（如组成区域的像素）当关注的重点是内部属性时，例如颜色和纹理等，可选择一种内部表示；有时，需要同时使用这两种表示。无论哪种情形，作为描绘子的特征都应该对大小、平移和旋转等不敏感。2本章

2、内容表示边界追踪链码具有最小周长的多边形近似其它多边形近似方法标记图边界线段骨架边界描绘子区域描绘子使用主分量进行描绘关系描绘子3表示边界追踪一些图像表示和描述的算法要求以顺时针或逆时针方向对区域边界或包含在区域中的像素进行排序，这就涉及到边界跟踪算法。假设：处理的是二值图像，目标和背景分别标为 1 和 0；图像已使用值为 0 的边界填充，消除了目标和图像边界合并的可能性；这里仅讨论单个区域，但通过单个地处理各个区域，这些方法可扩展到多个不相交的区域。追踪二值区域 R 的边界或给定边界的算法步骤：5表示边界追踪追踪二值区域 R 的边界或给定边界的算法步骤：原始图像如图 a 所示，通常令图像左上

3、角标记为 1 的点为起始点 b0；令 c0 表示 b0 左侧的邻点，c0 总是背景点，见图 b 所示。从 c0 开始按顺时针方向考察 b0 的 8 个邻点，令 b1 表示遇到的第一个值为 1 的邻点，并直接令 c1 表示序列中 b1 之前的点，存储 b0 和 b1 的位置，以便后续使用；令 b=b1，c=c1，见图 c 所示；从 c 开始按顺时针方向考察 b 的 8 个邻点 n1、. nk-1、nk、n8，找到第一个值为 1 的邻点 nk;令 b=nk 和 c=nk-1 (直接令 c 为序列中 b 之前的点);重复步骤 3 和 4，直到 b=b0 且找到的下一个边界点为 b1。当算法停止时，所

4、找到的 b 点序列就构成了排序后的边界点的集合。abcde6表示边界追踪有时上述算法称为 Moore 边界追踪算法 1968；算法步骤 5 中停止规则的必要性为了防止在 b=b0 处错误的停止，增加了“找到的下一个边界点为 b1”。如下图 a，毛刺去除不彻底会导致边界上侧的线段。从左上角开始，得到如图 b 所示的结果。在图 c 中，可以看到又回到了起始点 b0，如果就此停止，那显然不会找到剩余的边界，而使用步骤 5 中的停止规则，可允许算法继续进行。abc7表示边界追踪如果给定的是一个区域，而不是其边界，该算法也工作良好，得到一个二值区域的外边界。如果要表示一个区域内孔洞的边界（该区域的内边界

5、），一个简单的方法是提取这些孔洞后，把它们当做 0 值背景上的 1 值区域来处理，对这些区域采用上述边界追踪算法得到原始区域的内边界。上面描述了基于顺时针方向跟踪一个边界的算法，也可以逆时针方向描述。所以，会经常遇到按如下假设进行表述的算法：“边界点已在某个方向上排序”。形态学方法进行孔洞填充8表示链码数字图像通常以一种网格形式来获取或处理。在这种网格形式中，x 和 y 方向的间距相等。链码可以通过在网格中追踪一个边界产生，即以顺时针方向沿着边界线，对连接每对像素的线段赋予一个方向的方法产生。但有两个原因，通常无法采用这种方法：得到的链码往往太长噪声或是边界线段的缺陷，都会导致编码的变化，而这

6、种变化与边界的主要形状特性可能不相关。经常用来防止产生上述问题的一种方法是，选择更大间隔的网格对边界进行重新取样，如下图 a 所示。10表示链码边界的链码取决于起始点，但可以通过一个简单的过程实现链码起始点的归一化：将链码看做方向编号的循环序列，并重新定义起始点，得到方向编号序列的最小整数值；也可用链码的一次差分代替链码本身进行归一化，以便适应旋转变化（称为旋转归一化，4 或 8 方向整数倍的旋转角度）。计算链码中相邻两个直线段按顺时针或逆时针改变的方向数。只有旋转和尺度变化，而边界自身不变时，这些归一化才能保持其转换的准确性，实际中很少出现这种情况。例如，同一个物体按两个不同方向数字化后，通

7、常会有不同的边界形状。差异与图像分辨率成正比。按其长度与像素间距成正比选择链码，和/或沿物体的主轴或沿其本征轴选择重取样网格的方向，从而降低这种影响。例如：有一 4 向链码 10103322，头两个相邻的直线段方向编号为 1 和 0，如右图所示，按逆时针顺序，1 和 0 之间变化数量为 3，因此，它们之间的差分为 3；第 2 和 3 直线段方向编号为 0 和 1，得其差分为 1；同理，可得最终的差分为 3133030。12Freeman 链码举例简化后边界的 8 方向 Freeman 链码是 0000 6066 6666 6644 4444 2422 2220 2202该边界的起始点位于子取样

8、网格中的坐标（2,5）处，位于图 f 的左上角；该链码的一次差分为 0006 2600 0000 0600 0006 2600 0062 0626该链码具有最小整数值，使用该链码表示边界时，可有效减少存储该边界的数据量；另外，提供了一种统一的方法来分析边界的形状；可由链码恢复子采样的边界。表示链码(d)(e)(f)14表示具有最小周长的多边形近似数字边界可以用多边形以任意精确性来近似。对一条闭合曲线，当多边形的边数等于边界上的点数时，这种近似是精确的。此时，每对相邻的点定义了多边形的一条边。多边形近似的目的是使用尽量少的边数来获得给定边界的基本形状。通常该问题不易求解，求解过程会转化为耗时的迭

9、代搜索。几种适度复杂的多边形近似技术还是很适合图像处理应用的。最小周长多边形（Minimum Perimeter Polygon，MPP），是最有吸引力的技术。聚合技术拆分技术15表示具有最小周长的多边形近似直观解释假设用一系列彼此连接的单元将一条边界包住，如左图a所示。这条由单元组成的包围圈看起来像边界内外的两面墙，将边界想象为一条包围在墙中的橡皮条。如果允许橡皮条收缩，橡皮条会受到内外墙的约束，最终收缩会生成一个具有最小周长的多边形，如左图b，它被限制在单元墙封闭的区域内。注意，在图中，所有 MPP 的顶点与内墙或外墙的角点一致。(a) 物体的边界(黑色曲线); (b) 由 (灰色) 单元

10、围成的边界；(c) 收缩得到的最小周长多边形MPP16表示具有最小周长的多边形近似单元的大小决定着多边形近似的精度；在极限情况下，假设每个(方形)单元对应于边界上的一个像素，则边界和 MPP 近似值之间最大误差为 2d，其中 d 是像素间最小距离；若每个单元和像素的中心一致，则误差减半。在给定应用中，目的是使用合适的最大可能的单元，以便用最少的顶点数产生 MPP。术语凸顶点是一组三个点的中心点，它定义了 0180范围内的一个角；类似地，凹顶点是一组三个点的中心点，它定义了 1800。为便于描述 MPP，定义符号 sgn(a,b,c) det(A)： 20表示具有最小周长的多边形近似MPP 算法

11、的数据表数据列表的行是每一个顶点的坐标和一个表示顶点是 W 还是 B 顶点的备注项；如前所述，凹顶点被镜像为按顺序排列的顶点很重要，排序可由前述的追踪边界算法完成；令 V0 表示左上角的第一个顶点，有性质 5 可知它是 MPP 的 W 顶点；假设顶点按逆时针方向排列；寻找 MPP 的算法使用两个“爬行”点：白色爬行点 (Wc)，沿凸顶点 (W) 爬行；黑色爬行点 (Bc)，沿凹顶点 (B) 爬行。这两个爬行点找到的最后一个 MPP 顶点和正被考察的顶点都是实现该过程所必要的顶点。序列 (c, a, b）或 (b, c, a) 得出和 (a, b, c) 相同的 det(A) 或 sgn，因此它

12、们追踪的方向相同，但几何上的解释是不同的，例如 sgn(c, a, b) 0 说明 b 位于直线 ca 的正侧。 21表示具有最小周长的多边形近似MPP 算法举例如图，假设网格间距为 1，起始顶点为左上角，则逆时针顶点列表中的前几行为右所示：列表中的第一个元素总是第一个 MPP，因此，首先令 Wc=Bc=V0=VL=(1,4)。原点(0, 0)yxV0V1V2V3V4V5下一个顶点是 V1=(2,3)，计算符号函数得得 sgn(VL,Wc,V1)=0， 且 sgn(VL,Bc,V1)=0，则条件 (b) 成立。因为 V1 是凹顶点（B），则令 Bc=V1= (2, 3) ，Wc 和 VL 保持

13、不变，仍在 (1, 4) 处。此时， Bc=(2, 3), Wc = VL=(1,4) ，V1 是 MPP 候选顶点，未找到新的的 MPP 顶点；从列表中的下一个顶点 V2= (3, 3) 继续执行， sgn(VL,Wc,V2)=0， 且 sgn(VL,Bc,V2)=1，则条件 (b) 成立。因为 V2 是凸顶点（W），则令 Wc=V2= (3, 3) ，Bc 和 VL 保持不变。此时， Wc = （3, 3)， Bc=(2, 3), VL=(1,4) ，V2 是 MPP 候选顶点，未找到新的的 MPP 顶点；23表示具有最小周长的多边形近似原点(0, 0)yxV0V1V2V3V4V5从列表中

14、的下一个顶点 V3= (3, 2) 继续， sgn(VL,Wc,V3) = -2，且 sgn(VL,Bc,V3)=0，则条件 (b) 成立。因为 V3 是凹顶点（B），则令 Bc=V3= (3, 2) ，Wc 和 VL 保持不变。此时， Bc=(3, 2), Wc = （3, 3)， VL=(1,4) ，V3 是 MPP候选顶点，未找到新的的 MPP 顶点；从列表中的下一个顶点 V4= (4, 1) 继续， sgn(VL,Wc,V4) = -3，且 sgn(VL,Bc,V4)=0，则条件 (b) 成立。因为 V4 是凸顶点（W），则令 Wc=V4= (4, 1) ，Bc 和 VL 保持不变。此

15、时， Bc=(3, 2), Wc = （3, 3)， VL=(1,4) ，V4 是 MPP候选顶点，未找到新的的 MPP 顶点；从列表中的下一个顶点 V5= (7, 1) 继续， sgn(VL,Wc,V5) = 9，则条件 (a) 成立，找到一个新的 MPP 顶点，令 VL=Wc=(4,1)。令 Wc=Bc=VL= (4, 1) 重新初始化算法，并从新找到的 VL=V4=(4,1) 后的下一个顶点 V5 重新开始，即再次用新值计算 V5；24表示具有最小周长的多边形近似MPP 应用举例566566的枫叶二值图像，主要特征有叶柄和三个圆裂片；8 连接边界，边界点数为 1900 个；i) 分别是使

16、用 2、3、4、6、8、16和 32 大小的方形单元得到的 MPP (用直线连接起来形成闭合的边界)；当尺寸大于 44 后，叶柄消失。在3232 之前，完好地保留了三个主要的圆裂片，之后这一明显特征也几乎消失了。MPP 表示边界的优势：c)i) 顶点数分别是 206、160、127、92、66、32和13，例如 e) 顶点数 127，数据量降低了 90%，但仍保留了原始边界的所有特征；边界平滑，便于链码表示。(a)(b)(c)(d)(e)(f)(g)(h)(i)26表示聚合技术基于平均误差或其它准则的聚合技术已经应用于多边形近似问题。一种方法沿着边界线寻找聚合点，直到拟合这些聚合点的直线的最小

17、均方误差超过一个预设的阈值，这时存储该直线的参数；将误差设为零，重复该过程，沿边界聚合新的点，知道误差再次超过预设的阈值；最后，相邻线段的交点构成多边形的顶点。主要难点：得到的近似顶点并不总是对应于原始边界中的形变 (如拐点) ，因为在误差超过阈值之前，不会开始一条新的直线，若此时遇到一个拐角，那么该拐角的许多点将被丢弃。在聚合的同时，进行拆分可以缓解这个问题。27表示分裂技术分裂边界线段的一种方法是将一条线段不断地细分为两部分，直到满足规定的准则为止。例如，假设准则为：一条边界线段到连接其两个端点的直线间的最大垂直距离不超过预设阈值。如果满足这个准则，则与直线有着最大距离的点就成为一个顶点，

18、这样就将边界线段细分为了两条子线段。这种方法在寻找变化显著的点 (如拐点) 时具有优势。对一条闭合边界，最好的起始点通常是边界上的两个最远点 (a)(b)(c)(d)分裂技术举例一个物体的原始边界；边界关于最远点的细分，点 c 是顶部边界线段到直线 ab 垂直距离最远的点，点 d 是底部线段上的最远点。分裂结果，阈值为直线 ab 长度的 ；新边界线段上没有超过阈值的点，得到最终多边形。28表示标记图虽然上例中生成的标记图是平移不变的，但是标记图的确取决于旋转和缩放。通过选择相同起始点的方法来生成标记图，可以实现关于旋转的归一化，从而不用考虑形状的方向。选择距离质心最远的点为起始点，假设该点对于

19、感兴趣的每个形状都是唯一的；在本征轴上选取距离质心最远的点为起始点（见后面章节），这种方法计算量更大，但更为稳定，因为本征轴的方向是使用所有轮廓点确定的；获得边界的链码，然后使用前述的链码归一化方法，假定得到的编码足够粗糙，以至于旋转不会影响到它的曲率。缩放归一化假设两个轴缩放比例一致，且以等间隔取样，则形状大小的变化将导致相应标记图的幅值变化。一种归一化方法是对所有函数进行缩放，以便它们具有相同的值域，如 0, 1。优点是简单，但严重缺陷是整个函数的缩放仅依赖于两个值：最小值和最大值。如果形状有噪声的，那么这种依赖性会成为各个物体的误差来源。30表示标记图另一种更为稳定但计算量更大的方法是：

20、将每个样本除以标记图的方差，假设该方差不为零，或者该方差不会小到造成计算困难。使用方差将产生一个可变缩放因子，该因子与尺寸变化成反比，就像自动增益控制那样工作。本质上，无论采用什么方法，基本思想都是消除对尺寸的依赖性，同时保持波形的基本形状不变。切线-基准线法沿着边界线行进，在边界线上的每个点处，画出此点的切线和基准参考线之间的角度。得到的标记图尽管不同于前面的“距离-角度法” r() 曲线，但也携带着基本形状特征的信息。例如，曲线中的水平线对应于沿该边界的直线，因为此处正切角为常数。斜率密度函数是上述“切线-基准线法”的一种变形，该函数是正切角值的直方图。由于直方图是“正切角值”密集程度的度

21、量，故该函数很好地反应了具有恒定正切角的边界部分（直线段或近似直线段），而且角度快速变化的部分（拐角或其它急剧弯曲位置）存在较深的波谷。31表示标记图(a)(b)(c)(d)标记图举例二值物体图像；另一个二值物体图像；相应的外部边界；相应的外部边界；相应的“距离-角度” r() 标记图，水平轴对应于从 0到360之间的角度变化，角度增量为 1，标记图中突出峰值的数量足以区分两个物体的形状；同 e) 。(e)(f)32表示边界线段将边界分解为线段（分段）通常很有用。分段降低了边界的复杂性，从而简化了描述过程。当边界线包含一个或多个携带形状信息的明显凹度时，这种方法尤其有吸引力。此时，使用由边界所

22、围成区域的凸壳就成为边界鲁棒分解的有力工具。如果连接集合 A 内任意两个点的直线段都在 A 的内部，则称 A 是凸形的。一个任意集合 S 的凸壳 H 是包含 S 的最小凸集。集合之差 H-S 称为集合 S 的凸缺（凸形缺陷）D。33表示边界线段使用以上概念对边界进行分段，参见下图 a，图中显示了一个物体 (集合 S) 和它的凸缺（阴影区）。区域边界可按如下方式分割：追踪 S 的轮廓，并标记进入或离开一个凸缺的转变点，图 b 显示了这一情况的结果（图中毛刺线表示转变点）。注意：理论上这种方案与区域的尺寸和方向无关。34表示边界线段实际中，由于数字化、噪声和分割变形的影响，数字边界往往是不规则的，

23、需要后处理。这些影响通常会导致在整个边界上有着随机散布的、无意义的、小的凸缺。与其试图通过后处理分出这些不规则边界，不如在边界分割前用通用的方法平滑边界。有很多方法可以做到这一点：方法 1：追踪边界，并使用一个像素沿该边界的 k 个相邻像素的平均坐标代替这个像素的坐标。这种方法适于处理较小的不规则边界，但它耗费时间，并且难于控制。方法 2：更为稳定的方法是在找到一个区域的凸缺前，先使用多边形近似。感兴趣的数字边界多数都是简单的、无自交叉的多边形Graham 1983 给出了一个寻找此类多边形的凸壳的算法。凸壳及其凸缺的概念对于描述整个区域及其边界同样是有用的。例如，描述一个区域可以基于该区域的

24、面积及其凸缺的面积、凸缺中分量数、这些分量的相对位置等。35表示骨架表示一个平面区域结构形状的重要方法是把它简化为图形。这种简化可以通过一种细化（也称骨架化）算法得到该区域的骨架来实现。细化过程在图像处理中起着核心作用，并有着广泛的应用，从印刷电路板的自动检测到空气过滤器中石棉纤维的计数。在前面章节已讨论过形态学骨架的基础知识，但当时对保持骨架连接没做规定，这里对此作出纠正。一个区域的骨架可以用 Blum 1967 提出的中轴变换（Medial Axis Transformation，MAT）来定义。边界为 B 的区域 R 的 MAT 如下图所示。 对 R 中的每个点 p，在 B 中找到与其最

25、接近的邻点。如果 p 有多个这样的邻点，就认为 p 属于 R 的中轴（骨架）。“最接近”（和得到的 MAT）这个概念取决于距离的定义。右图显示了使用欧氏距离的一些例子。36表示骨架区域的MAT有一个直观的定义，基于所谓的“草原之火” 。把一个图像区域想象成由干草组成的平坦大草原，假设沿草原边界点火，火的前线以相同的速度向区域中心前进。该区域的 MAT 就是同一时刻多个火线到达点的集合。尽管一个区域的 MAT 能生成令人满意的骨架，但直接实现这一定义需要大量的计算，因为潜在地涉及到计算区域内每个点到区域边界上每个点的距离。为改善计算效率，提出了许多改进算法。典型地，这些算法是迭代删除区域边界点的

26、细化算法。删除这些点要遵守如下约束条件：不可删除端点；不可破坏连接性；不可造成区域的过度腐蚀。37表示骨架下面给出细化二值区域的一种算法假设区域点的值为 1，背景点的值为 0。这里，边界点定义为值为 1，且至少有一个相邻像素的值为 0 的像素。这种方法对于给定区域的边界点逐次应用两个基本步骤第一步，参考下图中的 8 邻域表示，如果满足如下条件，则将一个边界点 p1 标为要删除的点：这里 N(p1) 是 p1 的非零相邻像素的数目，即：其中，pi 要么为 0，要么为 1。并且 T(p1) 是排序序列 p2、p3.p9、p2 中从 0 到 1 的变化次数。38表示骨架例如在右图中，有 N(p1)=

27、4， T(p1)=3. 第二步，条件 (a) 和 (b) 不变，但条件 (c) 和(d) 变为：解释当轮廓点 p1 仅有 1 个或 7 个值为 1 的邻域点时，就不满足条件 (a)。仅有一个这样的邻域点意味着 p1 是一个骨架笔画的端点，显然不能删除这个点。如果 p1 有 7 个这样的邻点，则删除 p1 会对该区域产生腐蚀。当对宽度为 1 个像素的笔画上的点应用这种方法时，就不满足条件 (b)。因此，该条件在细化操作期间就防止了骨架线段的断裂。值的最小集合（p4=0 或 p6=0）或（p2=0 和 p8=0）同时满足条件 (c) 和 (d)。这样，满足这些条件及条件 (a) 和 (b) 的点，

28、就是边界中的一个右边界点或下边界点，或边界中左上角的点。无论哪种情况，p1 都不是骨架的一部分，应被删除。类似地，下列值的最小集合（p2=0 或 p8=0）或（p4=0 和 p6=0）同时满足条件 (c) 和 (d)，它们对应左边界点或上边界点，或右下角的点。注意，右上角点有 p2=0 和 p4=0，既满足条件 (c) 和 (d)，也满足条件 (c) 和 (d)。对左下角点有 p6=0 和 p8=0，故也满足前述条件。39表示骨架细化算法的一次迭代的步骤如下：（1）执行步骤 1，标记将被删除的边界点；（2）删除做了标记的点；（3）执行步骤2，标记将被删除的剩余的边界点；（4）删除标记过的点。反

29、复进行这一基本过程，直到再也没有可被删除的点，此时算法终止，生成了该区域的骨架。对于二值区域的每个边界像素使用第 1 步如果不符合条件 (a)(d) 中的一个或多个，则所讨论点的值不变；如果满足所有的条件，则将该点标记为删除点，但该点要等到处理完所有的边界点后才能删除（改为 0 值），这种延迟是为了防止在算法执行期间更改数据结构。然后，以完全同样的方式对所得结果执行第 2 步。40表示骨架一个区域的骨架举例右图显示了一幅人腿骨的分割图像，并叠加了使用上述算法得到的区域骨架。在很大程度上，这个骨架直观上看起来是正确的。在骨骼“右肩部”有两个分支，咋看之下，与左侧对应，右侧也应该只有一个分支。但是

30、请注意，右肩比左侧稍宽，这就是算法生成两个分支的原因。在骨架处理算法中，这种不可预测的现象很常见。人腿骨和叠加在所示区域上的骨架41本章内容表示边界描绘子一些简单的描绘子形状数傅里叶描绘子统计矩区域描绘子使用主分量进行描绘关系描绘子42边界描绘子简单的描绘子边界的长度是最简单的描绘子之一一条边界上的像素数目可以给出其长度的粗略近似。对于在两个方向上以单位间距定义的链码曲线，垂直和水平分量的数量加上2 倍的对角线分量，可以给出曲线的准确长度。边界 B 的直径定义为：式中 D 是距离的度量，pi 和 pj 是边界上的点直径的值和连接该直径的两个端点的直线段（称为边界的长轴）的方向是表示边界的有用描

31、绘子。边界的短轴定义为与长轴垂直的直线。长短轴的比值称为边界的偏心率，也是一个有用的描绘子。两个轴与边界相交的 4 个外部点所构成的方框，称为基本矩形，可以完全包围该边界。43边界描绘子简单的描绘子曲率定义为斜率的变化率一般来讲，获得数字边界上某点曲率的可靠量度较为困难，因为这种边界通常都是局部 “粗糙的”。有时使用相邻边界线段的斜率差作为这两条线段交点处的曲率的描绘子，实际证明是可行的。例如，下图所示边界的顶点本身也可以很好的用于描述曲率。当在边界上顺时针方向移动时，如果在顶点 p 的斜率变化量为非负时，称这一点属于凸线段；否则，称 p 属于凹线段。通过使用斜率变化范围，可以进一步精确某点处

32、的曲率。例如，如果斜率变化小于 10，则认为 p 是一条近似直线线段的一部分；如果斜率变化超过 90，则认为 p 是一个角点。必须小心使用这些描绘子，因为它们的解释取决于单条线段相对于整个边界的长度44边界描绘子形状数链码边界的一次差分取决于起点。一条基于下图所示的四方向编码的边界的形状数，定义为最小数量级的一次差分。形状数的阶数 n 定义为其表示的个数。此外，对于闭合边界，n 是偶数，其值限制了不同形状的数目。45边界描绘子形状数下图显示了阶数为 4、6、8 的所有形状，以及它们的链码表示、一次差分和相应的形状数。一次差分是通过将链码作为循环序列计算后得到的。形状数由链码的一次差分得到。对于

33、期望的形状阶数 n，实际上是要找到阶数为 n （即周长为 n）的矩形，该矩形的偏心率最接近基本矩形的偏心率，并使用这个新矩形来建立网格尺寸。例如，若 n=12，则阶数为 12 （即周长为 12）的所有矩形是 24、33 和 15。如果 24 矩形的偏心率最匹配给定边界的基本矩形的偏心率，那么就以这个基本矩形为中心建立 24 网格，并得到链码，再由其一次差分得到形状数。46边界描绘子计算形状数计算形状数举例假设边界的阶数 n=18找到基本矩形和基本矩形最匹配的、阶数为 18 的矩形为 36 。因此，对基本矩形按 36 进行细分，其中链码方向与所得到的网格对齐；得到链码，并用它的一次差分计算形状数

34、。尽管选取网格间距的方法通常会使形状数的阶数等于 n，但低于该间距时，会产生阶数大于 n 的形状数。此时，指定一个阶数小于 n 的矩形，且重复该过程，直到所得形状数的阶数为 n。(a)(b)(c)(d)47边界描绘子傅里叶描绘子下图显示了 xy 平面内的一个 K 点数字边界从任意点 (x0, y0) 开始，以逆时针方向在该边界上扫描时，得到坐标对 (x0, y0)、(x1, y1) (xK-1, yK-1) 。这些坐标可以表示为 x(k)= xk 和 y(k)= yk 的形式。因此，使用这种表示形式，边界本身可以表示为坐标序列 s(k) = x(k), y(k)，k = 0,1,2,，K-1。

35、每个坐标对可当做一个复数来处理，即 s(k) = x(k) + jy(k)x 轴为复数序列的实轴，y 轴为复数序列的虚轴；尽管对该序列的解释是全新的，但并没有改变边界本身的性质。这种表示方法的好处是将二维问题简化成了一维问题。48边界描绘子傅里叶描绘子离散序列 s(k) 的傅里叶变换 (DFT) 为：u=0,1,2,K-1由 a(u) 的傅里叶反变换可恢复 s(k)：k=0,1,2,K-1复系数 a(u) 称为边界的傅里叶描绘子假设仅使用前 P 个 a(u) 变换系数，其它系数置 0，即令 a(u) = 0，uP-1 时。结果 s(k) 的近似值为：k=0,1,2,K-1高频分量表征细节，而低

36、频分量决定整体形状。因此，P 越小，边界丢失的细节就越多。尽管 s(k) 每个分量的计算仅使用了 a(u) 的 P 项，但 k 的范围仍是 0K-1，即在近似边界中存在同样数量的点，只是参与重建的变换系数只有前 P 项。49边界描绘子傅里叶描绘子傅里叶描绘子举例可以看到，P 值必须大于等于 8，这样重建的边界比更像方形；P 约为 56 时，拐角的点开始变得突出，符合拐角定义的变化才开始出现。P=61 时，曲线变直，此时几乎是原始边界的精确复制。左图显示了一个包含 K=64 个点的方形边界和使用各种 P 值重建边界的结果。 可以看出，少数低频系数就能够反映边界的大体形状，而更多的高频系数能更精确

37、地定义形状特征 (比如拐角和直线)。少数的傅里叶描绘子就可用于捕获边界的大体特征，因这些系数携带了形状信息。50边界描绘子傅里叶描绘子傅里叶描绘子举例人类染色体的边界，有 2868 个点组成；用 2868 个描述子的一半来重建边界，与原始边界没有明显差异。 h) 为分别使用 286、144、72、36、18 和 8 个傅里叶描绘子重建的边界，这些数字分别近似为 2868 个点的 5%、2.5%、1.25%、0.63% 和 0.28%。(a)(b)(c)(d)(e)(f)(g)(h)可以看出，当采用 18 个描绘子，约为原来的 0.63%，就能有效地保持了原始边界的主要形状特征： 4 个较长的突

38、出部分和 2 个较深的弯曲部分；使用 8 个描绘子得到的结果是不可接受的，已丧失了主要特征；描绘子进一步减少到 4 个和 2 个，将分别导致一个椭圆和一个圆。51边界描绘子傅里叶描绘子描绘子应尽可能对平移、旋转和尺度变化不敏感。此时，结果将取决于处理边界点的顺序。因此，另一个约束条件是，描绘子对起始点应不敏感。傅里叶描绘子并非直接对上述这些几何变化不敏感，但这些参数变化可能与描绘子的简单变换是相关的。例如，考虑旋转变换。由数学知识可知，s(k) 的每个点乘以 ej 因子，就可使每个点围绕复平面原点旋转角，实现整个序列相对于原点的旋转变换。旋转的序列为 s(k) ej，其傅里叶描绘子为：u =

39、0,1,2,K-1因此，旋转变换只是通过原来的变换系数 a(u) 乘以常数项 ej，就等同地影响了所有系数。52符号xy 定义为：xy = x + yst(k) 定义为：st(k) = s(k) + xy = x(k)+ x + jy(k)+ y ，即平移变换是对边界上的所有坐标加上一个常数位移。除了 u=0 时变为冲激函数 (u) 外，平移对描绘子没有影响。sp(k) = s(k-k0) 表示将序列的起点从 k=0 移到 k=k0。表的最后一列表明，起始点的变化会以不同的方式影响到所有的描绘子，在此意义上，乘项 a(u) 取决于 u。边界描绘子傅里叶描绘子的基本性质经过旋转、平移、缩放和起始

40、点变化的边界序列 s(k) 的傅里叶描绘子。53边界描绘子统计矩边界线段（和标记图波形）的形状可以使用统计矩进行定量描述，如均值、方差和高阶矩。例如：图 (a) 显示了一段边界。图 (b) 显示了以任意变量 r 的一维函数 g(r) 描述的线段，该函数是通过连接线段的两个端点，并将线段旋转至水平方向得到的。此时，所有点的坐标也旋转了相同的角度。将幅度 g 看做一个离散随机变量 v，并形成一个幅度直方图 p(vi)，i=0,1,2, A-1，这里 A 是分割幅度尺度的离散幅度增量数。p(vi) 是值 vi 出现的概率估计，则随机变量 v 的第 n 阶矩为：54边界描绘子统计矩其中 这里 m 是

41、v 的均值或平均值，2 是 v 的方差。通常几乎不需要用一阶矩来区分形状明显不同的信号。一种替代方法是将 g(r) 归一化为单位面积，并把它当做直方图来处理，即将 g(ri) 作为值 ri 出现的概率。此时，将 r 作为随机变量，则 n 阶矩为： 上式中，K 是边界点的数目，n(r) 直接与 g(r) 的有关。例如，二阶矩 2(r) 用来衡量关于 r 的均值的扩展程度，三阶矩3(r) 衡量曲线关于均值的对称性。基本上，要完成的任务就是将描述简化为一维函数。“矩” 法显然是使用最为普遍的方法，但它们并不是实现这一目的的唯一描绘子。其中55本章内容表示边界描绘子区域描绘子一些简单的描绘子拓扑描绘子

42、纹理不变矩使用主分量进行描绘关系描绘子56区域描绘子某些简单的描绘子下面考虑描述图像区域的不同途径。实践中普遍的做法是边界和区域描绘子结合使用。区域描绘子区域面积：区域中像素的数目区域周长：边界的长度致密性：(周长)2/面积致密性是无量纲的量，对均匀尺度变化和方向不敏感圆盘形区域的致密性最小圆度率：一个区域的面积与具有相同周长的一个圆（最致密的形状）的面积之比周长为 P 的圆面积是 P2/4，则圆度率为：其中，A 是所讨论区域的面积。对于圆形区域，圆度率为 1；对于方形区域，圆度率为 /4。其他简单的区域描绘子灰度的均值和中值最小和最大灰度值大于和小于均值的像素数尽管有时面积和周长也用作描绘子

43、，但它们主要应用于感兴趣区域尺寸不变的情形。这两个描绘子更常用于度量一个区域的致密性。57区域描绘子某些简单的描绘子用面积从图像中提取信息举例即使是像归一化面积这样的简单区域描绘子，对于从图像中提取信息也是非常有用的；左图显示了美洲的卫星红外图像，这些图像提供了人类定居地的整体数量。用于收集这些图像的传感器能够探测可见光和近红外发射光，如灯光、火光和闪光。图像旁边的表格（按从上到下的区域）给出了 4 个区域中白色（灯光）面积与所有发光面积之比。可以用于估计某些区域消耗的电能。通过关于每个区域的陆地面积、人口数等将其归一化，可进一步细化数据。卫星拍摄的美洲红外线图像58区域描绘子拓扑描绘子拓扑特

44、性对于图像平面区域的整体描述是很有用的。拓扑学在图像没有任何撕裂或粘连（有时称为橡皮膜变形）的情况下，研究未受任何变形影响的图形的性质。孔洞数拓扑描绘子如果一个拓扑描绘子由该区域内的孔洞数量来定义，那么这种描绘子明显不受拉伸或旋转变换的影响。然而，一般来讲，如果该区域被撕裂或折叠，那么孔洞数量可能会发生变化。由于拉伸会影响距离，故拓扑特性与距离或基于距离度量概念的任何特性无关。带有 2 个孔洞的区域另一个对区域描述有用的拓扑特性是连通分量的数量。下图显示了一个具有 3 个连通分量的区域。有 3 个连通分量的区域59区域描绘子拓扑描绘子欧拉数 E = C - H其中 E 为欧拉数，为连通分量的数

45、量，为孔洞的数量；欧拉数也是一种拓扑特性下图显示的区域分别有和 -的欧拉数，因为 “” 有一个连通分量和一个孔洞；“” 有一个连通分量和两个孔洞。多边形网络使用欧拉数，可非常简单地解释由直线线段表示的区域（称为多边形网络），如上图所示的多边形网络。将这样一个网络的内部区域分类为面 (Face)、边 (Edge)、顶点 (Vertex) 和孔洞 (Hole) 通常是很重要的。60区域描绘子拓扑描绘子欧拉公式 V- Q + F = C - H其中 V 为顶点数，Q 为边数，F 为面数，为连通分量数，为孔洞数；欧拉数 E = C H = V- Q + F左图网络有 7 个顶点、11条边、 2 个面、

46、1 个连通区域和 3 个孔。因此 欧拉数为 -2 = 7-11+2 = 1 3。拓扑描绘子提供了一个附加特征，该特征在表征某个场景中的区域时通常很有用。使用连通分量在已分割图像中提取最大特征的举例目的是说明如何使用连通分量完成分割。原始图像是美国华盛顿特区的 512512 的 8bit 图像，由 NASA 地球资源（LandSat）卫星拍摄的近红外波段图像。假设只使用这幅图像来分割河流（和使用多光谱图像相反，它可简化任务）。由于河流在图像中是相当暗的均匀区域，因此值得尝试下阈值处理。61区域描绘子拓扑描绘子使用连通分量在已分割图像中提取最大特征的举例512512 的原始近红外波段图像；人为设定

47、阈值处理后的图像。在使河流变成一个不连通区域之前，用尽可能最高的阈值处理。可以看出，仅靠河流本身的一个阈值处理无法把其它区域清理干净的，不可能将河流分离出来；图 b) 中的图像有 1591 个连通分量（使用 8 连通得到），其欧拉数为 1552，由此推断出有 39 个孔洞，图 c) 显示了带有最大元素数目（8479）的连通分量。这就是期望的结果，非常清晰；如果要度量河流的每个支流的长度，可以使用该连通分量的骨架。骨架中每个分支的长度就是它所表示的河流分支的合理近似。(a)(b)(c)(d)62区域描绘子纹理区域描绘的一种重要方法是量化该区域的纹理内容。尽管没有纹理的正式定义，但直觉上，这种描绘

48、子能够提供了诸如平滑度、粗糙度和规律性等特性的度量。白色方块从左到右表示平滑、粗糙、规则的纹理。三幅图像依次是超导体、人类胆固醇、微处理器的光学显微镜图像。(a)(b)(c)63区域描绘子纹理统计方法描述区域纹理的三种主要方法：统计方法，生成诸如平滑、粗糙、粒状等纹理特征。结构化方法，处理图像元的排列，如基于规则间距的平行线的纹理描述。频谱方法，基于傅里叶频谱特性，主要用于通过识别频谱中能量的窄波峰，从而检测图像中的全局周期性。统计方法描述纹理的最简单方法之一是使用一幅图像或一个区域的灰度级直方图的统计矩。令 z 为表示灰度的一个随机变量，并令 p(z) 为对应的直方图，这里 i = 0,1,

49、2,L-1，L 是可区分的灰度级数目。 z 关于其均值的 n 阶矩定义为： 这里 m 是 z 的均值（平均灰度）：注意64区域描绘子纹理统计方法注意，0 阶矩 0=1，一阶矩1=0；二阶矩（方差2(z) =2(z)）在纹理描述中特别重要，它是灰度对比度的量度，可用于建立相对平滑度的描绘子。例如，度量对于恒定灰度区域，方差为 0，则 R(z) 为 0；而对于较大的方差2(z) 值，R(z) 接近于 1；对于灰度图像，因为方差随着灰度值范围增大而增大，例如，对于 0, 255 范围的灰度图像，最好将其方差归一化到区间 0, 1 内，即将方差2(z) 除以 (L-1)2，以便如上式 R(z) 使用。

50、标准差(z) 也常用于纹理的度量，因为其更为直观。 65区域描绘子纹理统计方法三阶矩是对直方图偏斜度的度量，偏斜度表明了对称程度，是向左偏斜（负值）还是向右偏斜（正值）。四阶矩是直方图相对平坦度的度量。五阶矩和更高阶矩不容易与直方图形状联系起来，但它们的确提供了纹理内容的进一步量化辨别。另外一些有用的、基于直方图的纹理度量的方法：“一致性” 度量：熵度量：因为 p 在区域 0, 1 内取值，且其和为 1，所以度量 U(z) 对所有灰度级都相等（等概）的图像有最大值（极大一致性），并从最大值开始降低。熵是可变性的度量，对恒定图像其值为零。66区域描绘子纹理统计方法基于直方图的纹理度量的举例下表总

51、结了如图三种纹理的的纹理度量值均值仅告诉了每个区域的平均灰度，仅用作灰度的大致概念，不是真正的纹理；标准差提供的信息更丰富，数字清楚地表明第一种纹理的灰度变化明显小于其它两种纹理，即第一个纹理更平滑。用这个度量可以很清楚地检测粗糙纹理；对 R(z) 的结论同标准差，因为它度量的内容基本上和标准差相同；三阶矩确定直方图的偏斜度，给出了灰度级是偏斜均值的暗端还是亮端的粗略概念。就纹理而言，仅当度量间的变化较大时，由三阶矩得到的信息才是有用的。一致性度量再次说明第一幅图像更平滑均匀，且最大随机（最低一致性）对应于粗糙纹理。熵值的变化与一致性度量相反，结论相同，第一幅图像的灰度级变化最小，第二幅粗糙图

52、像最大，第三幅规则图像介于两者之间。67区域描绘子纹理统计方法仅使用直方图计算的纹理度量不携带像素位置信息，但在描述纹理时，位置信息很重要。因此，此类方法的应用受到限制。需要一种纹理分析方法，不仅要考虑灰度分布，还要考虑图像中像素的相对位置。共生矩阵考虑一幅 L 级灰度的图像 f，令 Q 是定义两个像素相对位置的算子，而 G 为一个矩阵，其元素 gij 是灰度 zi 和 zj 的像素对出现在 f 中由 Q 指定位置处的次数，其中 1 i, j L。按这种方法形成的矩阵 G 称为灰度（或灰度级）共生矩阵，当含义明确时，简称为共生矩阵。 下图显示了一个构造共生矩阵的例子，其中 L=8，位置算子 Q

53、 定义为”直接面对右边的一个像素“（即一个像素的相邻像素定义为紧靠右边的像素）。68区域描绘子纹理统计方法左侧阵列是图像 f，右侧是共生矩阵 G。G 的元素 (1, 1) 是 1，因为在 f 中，值为 1 的像素的右侧值也为 1 的像素仅出现了 1 次；类似地，G 的元素 (6, 2) 是 3，因为在 f 中，相邻两个像素值为（6, 2）的组合出现了 3 次；按这种方式，可计算出 G 的其它元素。如果位置算子 Q 定义为 “左边一个像素和上面一个像素”，则共生矩阵 Q 为：G 的元素 (1, 1) 是 0，因为在 f 中，不存在左边一个值为 1和上面一个值为 1 的情况；G 的元素 (1, 3

54、)、(1, 5)、(1, 7) 都是 1，因为在 f 中由 Q 定义的位置处，上面像素分别为 3、5 和 7 而左面像素值都为 1的组合各出现了 1 次。69区域描绘子纹理统计方法图像中可能的灰度级数决定了共生矩阵 Q 的大小。对于一幅 8bit 图像（256 个可能的灰度级），G 的大小为 256256。当使用一个矩阵时，这不成问题，但有时会使用共生矩阵序列，就不便使用。为了减少计算负担，经常将灰度级量化为几段，以便于管理矩阵 G 的大小，例如在256级灰度时，通过令前 32 个灰度级等于 1，接下来的 32 个灰度级等于 2，以此类推，完成这种量化后，得到一个 88 大小的矩阵。满足 Q

55、的像素对的总数 n 等于 G 中元素数值之和（上例中 n=30）。pij = gij/n 是满足 Q 的一个值为（zi，zj）的点对的概率估计，其值域为 0, 1，且它们的和为 1：因为 G 取决于位置算子 Q，因此选择一个合适的位置算子 Q 并分析 G 的元素，可以检测灰度纹理模式的存在情况。其中，K 是方阵 G 的行 (或列) 数70区域描绘子纹理统计方法下表给出了一组表征共生矩阵 G 的有用描绘子。区域描绘子纹理统计方法上表中第二行 “相关描绘子” 中参数定义如下：如果令71区域描绘子纹理统计方法则上述公式可以写为：区域描绘子纹理统计方法mr 是沿归一化 G 的行计算的均值，mc 是沿归

56、一化 G 的列计算的均值；类似地， r 和 c 是分别沿归一化 G 的行和列计算的标准差；这些项都是标量，与 G 的大小无关。注意：表中 “邻居”与定义 Q 的方式有关，即 “邻居” 不必一定是邻近的；pij 只不过是在 f 内像素发生次数的归一化计数，该像素具有灰度 zi 和 zj，并与 Q 指定的位置有关。72区域描绘子纹理统计方法区域描绘子纹理统计方法使用描绘子表征共生矩阵举例 c）显示了分别由随机模式、水平周期（正弦）模式和混合像素模式组成的图像。本例有两个目的：1）对（从上到下）对应于这些图像的 3 个共生矩阵 G1、G2 和 G3 ，说明上表中描绘子的值；2）说明如何使用共生矩阵序

57、列来检测图像中的纹理模式。(a)(b)(c)像素具有 (a) 随机模式；(b) 周期模式；(c) 混合模式的图像，每幅图像 263800像素73区域描绘子纹理统计方法区域描绘子纹理统计方法使用描绘子表征共生矩阵举例共生矩阵定性描述以灰度图像形式显示了共生矩阵 G1、G2 和 G3。这些矩阵是用 L=256 和位置算子 Q “右侧紧邻一个像素” 得到的。在这些图像中，坐标 (i, j) 处的值是在 f 内具有灰度 zi 和 zj 的像素对由 Q 指定位置处出现的次数。 共生矩阵 G2 显示的一个有趣的、明显的特征是关于主对角线对称的。由于正弦波的对称性，像素对 (zi, zj) 和 (zj ,

58、zi) 的计数相同，故产生对称的共生矩阵。G2 的非零元素是稀疏的，因为水平正弦波中水平相邻像素间的差值相对较小。数字化后的正弦波是阶梯状的，每个阶梯的高度和宽度取决于表示函数中使用的频率和幅度级数。共生矩阵 G3 的结构更复杂，沿主对角线也聚集了更高密度的计数值，表明图像灰度值有丰富的变化，但相邻像素之间的灰度有很少有较大的跳变。图像中存在几个由较小灰度变化表征的较大区域。灰度的高跳变出现在物体的边界处，但与整个较大区域上的中等灰度跳变相比，这些计数较小。因此，由于显示器同时显示高值和低值能力的限制，使得它们不太明显了。大小为 256256 的共生矩阵 G1、G2 和 G3，从左到右对应于上

59、图中的图像。(a)(b)(c)74区域描绘子纹理统计方法区域描绘子纹理统计方法使用描绘子表征共生矩阵举例描绘子定量描述使用描绘子定量表征三幅图像的共生矩阵，对共生矩阵要归一化；最大概率：第三共生矩阵 G3 最大，说明这个局长具有最大数量的的计数（像素对在图像内由 Q 指定位置处出现最大次数），与前面对 G3 的分析一致；相关：G2 的相关最高，说明第二幅图像中灰度是高度相关的，与反复出现的正弦模式表现一致。G1 的相关性近乎为零，这表明随机图像的相邻像素不相关的特性；对比度：G1最高，G2最低，可以看出图像的随机性越低，其对比度往往也越低。因为 (i-j)2 项是 1i, jL 的整数差，故它

60、们对于任何 G 都是相同的。因此，归一化共生矩阵 G 中元素的概率就成为决定对比度的因子。虽然 G1 有最小的最大概率，但其它两个矩阵有许多零和接近零的概率（暗色区域）。值 G/n 之和为 1，故容易了解对比度描绘子随随机性增加而增大的原因。使用类似的方式，可以解释剩余的三个描绘子。75区域描绘子纹理统计方法区域描绘子纹理统计方法使用描绘子表征共生矩阵举例描绘子定量描述一致性：随概率平方值的增大而增加，这样，图像中的随机性越低，一致性描绘子就越高。同质性：它度量 G 值关于主对角线的集中度。分母项 (1+|i-j|) 对所有三个共生矩阵是相同的，且分母项的值在 i 和 j 接近（即接近对角线）