图像分析与识别_课件_3

1图像分析与识别ImageAnalysisandRecognition北京航空航天大学仪器科学与光电工程学院SchoolofInstrumentationScience&OptoelectronicsEngineering第三章图像分析的数据结构图像分析与识别2第三章图像分析的数据结构第三章图像分析的数据结构图像分析与识别3数据和算法是所有程序的两个基本的相关部分；数据的组织通常在很大程度上影响着算法的选择和实现的简洁性；因此，在写程序时数据结构的选择是一个重要的问题。第三章图像分析的数据结构图像分析与识别4在解释不同的图像处理方法之前，本章将介绍有关如何表示图像数据及推导数据的内容。这样就会使不同类型的图像数据表示之间的关系清晰化。第三章图像分析的数据结构图像分析与识别5首先我们来处理图像分析任务中的信息表示的基本层次，然后来讨论传统的数据结构，包括矩阵、链、关系结构，最后我们讨论分层数据结构，如金字塔和四叉树。第三章图像分析的数据结构图像分析与识别6第一节图像数据表示的层次第三章图像分析的数据结构图像分析与识别7一、概述计算机视觉感知的目的是寻找输入图像与真实世界的模型之间的关系。在从原始输入图像向模型转换的过程中，图像信息逐渐浓缩，使用的有关图像数据解释的语义知识也越来越多。第三章图像分析的数据结构图像分析与识别8在输入图像和模型之间，定义了若干层次的视觉信息表示，计算机视觉由如下的设计所组成：第三章图像分析的数据结构图像分析与识别9二、计算机视觉信息表示的组成中间表示（数据结构）；创建这些中间表示所用的算法和它们之间关系的导入。这些中间表示可以分为4个层次：这四个表示层次按照从处于低层次抽象的信号开始到人能够感知的描述为止排列，层次之间的信息流是双向的。第三章图像分析的数据结构图像分析与识别101.第一层是最底层的表示，称为图标图像，由含有原始数据的图像组成，原始数据也就是像素亮度数据的整数矩阵，往往需要进行预处理；2.第二层的表示是分割图像，图像被分割为可能属于同一物体的区域；第三章图像分析的数据结构图像分析与识别113.第三层是几何表示，保存2D和3D形状知识；4.第四层的图像数据表示是关系模型。关系模型使我们能更有效地、并且在更高的抽象层次上处理数据。第三章图像分析的数据结构图像分析与识别12第二节传统图像数据结构第三章图像分析的数据结构图像分析与识别13一、矩阵矩阵是低层图像表示的最普通的数据结构，矩阵中的元素都是整型的数值，对应于采样栅格中的相应像素的亮度或其它属性。第三章图像分析的数据结构图像分析与识别14矩阵中的图像信息可以通过像素的坐标得到，坐标对应于行和列的标号。矩阵是图像的一个完整表示，与图像数据的内容无关，它隐含着图像组成部分之间的空间关系，这些图像组成部分在语义上具有重要性。第三章图像分析的数据结构图像分析与识别15在图像的情况下，空间是两维的，即平面。一个非常自然的空间关系是相邻关系。用矩阵来表示一个分割的图像，通常要比列出所有物体之间的全部空间关系更节省存储空间，但是有时我们需要记录物体间的其它关系。第三章图像分析的数据结构图像分析与识别16二值图像：仅有两个亮度级别的图像，用仅含有O和1的矩阵来表示。多光谱图像：信息可以用几个矩阵来表示，每个矩阵含有一个频带的图像。分层图像数据结构：用不同分辨率的矩阵来获得。矩阵的表示的特殊图像第三章图像分析的数据结构图像分析与识别17多数编程语言用标准的数组数据结构表示矩阵。矩阵中有大量的图像数据，因此其处理需要很长时间。如果首先从原始的图像矩阵得出全局信息，由于全局信息更紧凑并且占用的存储少，那么算法就可以加速。矩阵的表示第三章图像分析的数据结构图像分析与识别18直方图是最普通的全局信息的例子。从概率的角度观察图像，标准化的直方图是如下现象的概率密度的估计：一个图像的像素具有的某个亮度。矩阵的全局信息之一：直方图第三章图像分析的数据结构图像分析与识别19它是具有亮度x的像素(i1，j1)和具有亮度y的像素(i2，j2)的概率估计。假设这个概率仅依赖于亮度x的像素和亮度y的像素之间的空间关系r，那么关于关系r的信息就记录在方形的共生矩阵Cr中，它的维数对应于图像的亮度级别数。矩阵的全局信息之二：共生矩阵第三章图像分析的数据结构图像分析与识别20共生矩阵用两个位置的像素的联合概率密度来定义，它不仅反映亮度的分布特性，也反映具有同样亮度或接近亮度的像素之间的位置分布特性，是有关图像亮度变化的二阶统计特征。它是定义一组纹理特征的基础。第三章图像分析的数据结构图像分析与识别21为了减少矩阵Cr的数目。引进一些简化的假设，首先仅考虑直接的邻居，其次假定关系是对称的(没有方向)。使用如下的算法可以计算图像f(i，j)的共生矩阵Cr。第三章图像分析的数据结构图像分析与识别221.设置Cr(x,y)=0,对于所有的x,y属于[0,L]，其中L是最大亮度；2.对与图像中的所有像素(i1，j1)，找到与像素(i1，j1)有关系r的像素(i2，j2)，做：算法：关系r的共生矩阵Cr(x,y)1),(),,(),(),,(22112211jifjifCjifjifCrr第三章图像分析的数据结构图像分析与识别23关系r的定义举例如下图所示，定义位置算子：C0°C270°C315°C45°第三章图像分析的数据结构图像分析与识别24假设给定如下的仅具有3个灰度级的图像区域，分别记数符合位置算子C0°，C270°，C315°的像素空间组合的数目形成频度矩阵，再将其归一化，即除以符合位置关系的总数就得到归一化的共生矩阵。共生矩阵的阶数与图像的灰度级数相等。第三章图像分析的数据结构图像分析与识别25共生矩阵的计算：例一0000100011001120112211222640043003640043003370005001300340046201300340046201100500073161图像C0°的频度矩阵和归一化共生矩阵C270°的频度矩阵和归一化共生矩阵C315°的频度矩阵和归一化共生矩阵第三章图像分析的数据结构图像分析与识别26共生矩阵的计算：例二10231123212320132102211232122202232103032102900000144100092001230030251C45°的频度矩阵图像C45°的归一化共生矩阵第三章图像分析的数据结构图像分析与识别27对于低对比度的图像，远离对角线的共生矩阵元素等于0或非常小。对于高对比度的图像则相反。考虑共生矩阵的主要原因是其描述纹理的能力。第三章图像分析的数据结构图像分析与识别28二、链链在计算机视觉中用于描述物体的边界。链的元素是一个基本符号，这种方法使得在计算机视觉任务中可以使用形式语言理论。链适合于可以组织成符号序列的数据，链中相邻的符号通常对应于图像中邻接的基元。第三章图像分析的数据结构图像分析与识别29基元是句法模式识别中使用的基本的描述元素。符号和基元的接近(邻近)规则有例外，例如描述一个封闭边界的链，它的第一个和最后一个符号并不是邻近的，但是它们在图像中对应的基元则是。第三章图像分析的数据结构图像分析与识别30链码(chaincode)：常用于描述物体的边界，或者图像中一个像素宽的线条。边界由其参考像素的坐标和一个符号序列来定义，符号对应于几个事先定义好了方向的单位长度的线段。链码本身是相对的，数据是相对于某个参考点表示的。第三章图像分析的数据结构图像分析与识别31从实现的角度，链可以用静态数据结构来表示，例如，一维数组，大小是链的最大期望长度。这样可能非常耗费存储空间，因此动态数据结构更优越。下图给出了一个链码的例子，其中使用的是8-邻接，用4-邻接定义链码也是可以的。第三章图像分析的数据结构图像分析与识别32链码：000077665555556600000006444444442221111112234445652211第三章图像分析的数据结构图像分析与识别33如果需要从链码中得到局部信息，那就必须系统地搜索整个链码。用链码描述图像适合于基于形式语言理论的句法模式识别。在处理真实图像时，就会出现如何处理由噪声引起的不确定性问题。第三章图像分析的数据结构图像分析与识别34行程编码(runlengthcoding)通常用于图像矩阵中符号串的表示(例如，传真机就使用行程编码)。为了简单，首先考虑二值图像。行程编码仅记录图像中属于物体的区域，该区域表示成以表为元素的表。行程编码(runlengthcoding)第三章图像分析的数据结构图像分析与识别35有多种在细节上存在不同的方案。有代表性的一个方案是：图像的每行表示成一个子表，它的第一个元素为行号。然后是坐标对构成的项，第一个为行程的开始，第二个是结束。一行中可以有若干个这样的序列。第三章图像分析的数据结构图像分析与识别36第三章图像分析的数据结构图像分析与识别37行程编码的主要优点是存在计算图像区域的交和并的简单算法。行程编码也可用于含有多个亮度级别的图像。在这种情况下，考虑的是一行中具有相同亮度的邻接像素序列。在子表中不仅要记录序列的开始和结束，而且还要记录亮度。第三章图像分析的数据结构图像分析与识别38三、拓扑数据结构拓扑数据结构将图像描述成一组元素及其相互关系，这些关系通常用图结构来表示。第三章图像分析的数据结构图像分析与识别39图(graph)G={V,E}是一个代数结构，由一组节点V={v1,v2,…,vn}和一组弧E={e1,e2,…,en}构成。每条弧ek代表一对无次序的节点{vi,vj},节点不必有区别。节点的度数等于该节点具有的弧的数目。第三章图像分析的数据结构图像分析与识别40赋值图：是指弧、节点或两者都带有数值的图，这些数值可能表示加权或耗费。赋值图第三章图像分析的数据结构图像分析与识别41区域邻接图区域邻接图：是这类数据结构的一个典型。其中节点对应于区域，相邻的区域用弧连接起来。分割的图像由具有相似性质的区域（亮度、纹理、彩色）构成，这些区域对应着场景中的一些实体，当区域之间具有一些共同边界时相邻关系就成立了。第三章图像分析的数据结构图像分析与识别42区域邻接图的例子，其中图像中的区域用数字标识，标识0代表图像外的像素。在区域邻接图中这些数值用来指出与图像边界接触的区域。第三章图像分析的数据结构图像分析与识别43区域邻接图示例第三章图像分析的数据结构图像分析与识别44区域邻接图通常是从区域图创建的。区域图是一个与原始图像矩阵具有相同维数的矩阵，其元素是区域的识别标号。为了创建区域邻接图，图像中所有的区域边界都要被跟踪出来，所有的相邻区域的标号都要被记录下来。第三章图像分析的数据结构图像分析与识别45区域邻接图明确地存储了图像中所有区域的相邻信息。区域图也含有这样的信息，但是从中得到它却要困难的多。第三章图像分析的数据结构图像分析与识别46如果我们想将区域邻接图与区域图关联起来，只要将区域邻接图的节点，用区域的识别标号和某个代表像素（例如，区域左上角的像素）标注起来就足够了。区域邻接图可以用于区域归并，比如，具有相同图像解释的相邻区域合并成一个区域。第三章图像分析的数据结构图像分析与识别47四、关系结构关系数据库也可以用来表示从图像中得到的信息，这时所有的信息集中在语义上重要的图像组成部分即物体之间的关系上，而物体是图像分割的结果。关系以表的形式来记录。第三章图像分析的数据结构图像分析与识别48如下给出了一个这种表示的例子。其中每个物体有名字和其它特征。比如，图像中对应区域左上角的像素。物体间的关系也在关系表中表示出来。第三章图像分析的数据结构图像分析与识别49第三章图像分析的数据结构图像分析与识别50使用关系结构的描述适合于高层次的图像理解工作。在这种情况下，类似于数据库