图像理解 课件 全套 01-16 绪论 -研究示例

绪论图像理解之一考核方式共3个主题，每个25分每个主题：组内讨论、成果展示：20分组间互动：5分报告写作25分，包括全部主题2教学方法课下自学课上讨论案例导引成果展示汇报形式-Poster（海报）345初识图像理解67教材和主要参考书图像工程（第3版）与前两册的关系本册书主要介绍图象工程的第三层次——图象理解的基本概念、基本原理、典型方法、实用技术以及国际上有关研究的新成果本册书主要介绍图象理解的内容，相比图象处理和图象分析更专业化应先修：上册和中册，尤其是与图象理解密切相关的内容8图象工程的发展图象用各种观测系统以不同形式和手段观测客观世界而获得的，可以直接或间接作用于人眼并进而产生视知觉的实体图象技术图象技术在广义上是各种与图象有关的技术的总称图象（广义/抽象）⊃图像（狭义/具体）图象工程图象工程学科是将数学、光学等基础科学的原理，结合在图象应用中积累的技术经验而发展起来的一个对整个图象领域进行研究应用的新学科一个对各种图象技术进行综合集成的研究和应用的整体框架9图象工程的发展图象工程三层次框图图象工程整体框架10图象工程的发展11图象理解图象工程高层在图象分析的基础上，结合人工智能和认知理论，进一步研究图象中各目标的性质和它们之间的相互联系，并理解图象内容的含义以及解释原来的客观场景，从而指导和规划行动目前研究成果和应用实例相对比较少限于目前计算机系统的能力和图象理解技术的水平，“系统”完成较低层的工作，而人需要接着系统完成剩下的较高层的工作12计算机视觉人类视觉过程：一个复杂的从感觉（感受到的是对3-D世界之2-D投影得到的图象）到知觉（由2-D图象认知3-D世界内容和含义）的过程计算机视觉是指用计算机实现人的视觉功能仿生学的方法：参照人类视觉系统的结构原理建立相应的处理模块完成类似的功能和工作工程的方法：从分析人类视觉过程的功能着手，并不去刻意模拟人类视觉系统内部结构，而仅考虑系统的输入和输出，并采用任何现有的可行的手段实现系统功能13其他相关学科模式识别图象模式识别、分类人工智能指由人类用计算机模拟、执行或再生某些与人类智能有关功能的能力和技术视觉功能是人类智能的一种体现机器视觉更关注图象的获取，系统的构造和算法的实现计算机图形学14图象理解的应用领域工业视觉人机交互（应用领域和实例）视觉导航虚拟现实（模拟训练）图象自动解释、判读对人类视觉系统和机理、人脑心理和生理的研究等15马尔视觉计算理论马尔1982年出版了《视觉》一书MarrD.Vision−−AComputationalInvestigationintotheHumanRepresentationandProcessingofVisualInformation.W.H.Freeman,1982一个理解视觉信息处理的框架要先理解视觉目的再去理解其中细节16马尔视觉计算理论视觉是一个复杂的信息加工过程视觉是一个远比人所想象更为复杂的信息加工任务和过程，而且其难度常不为人们所正视为理解视觉这个复杂的过程，要解决两个问题视觉信息的表达问题：某些信息是突出的和明确的，另一些信息则是隐藏的和模糊的视觉信息的加工问题：对信息处理、分析、理解，将不同表达形式转换，逐步抽象17马尔视觉计算理论视觉信息加工的三个要素：计算理论；算法实现；硬件实现计算理论可计算性问题：一个任务要用计算机完成，它应该是可以被计算的一般对于某个特定的问题，如果存在一个程序，对于给定的输入，这个程序都能在有限步内给出输出，这个问题就是可计算的视觉问题是否可用现代计算机计算？对计算机给定输入，能否得到人类视觉可获得的类似结果两方面的研究内容：计算的是什么以及为什么要计算它们；提出一定的约束条件，它们可唯一地确定最终得到的运算结果18马尔视觉计算理论视觉信息加工的三个要素：计算理论；算法实现；硬件实现算法实现需要给加工所操作的实体选择一种合适的表达选择加工的输入和输出表达，确定完成表达转换的算法一般情况下可以有许多可选的表达算法的确定常取决于所选的表达给定一种表达，可有多种完成任务的算法硬件实现有了表达和算法，在物理上如何实现算法也是必不可少的实时性要求⇒专用硬件实现算法的确定常依赖于物理上实现算法硬件的特点同一个算法也可由不同的技术途径实现19马尔视觉计算理论视觉信息的三级内部表达基素表达（primalsketch）一种2-D表达，它是图象特征的集合，描述了物体上属性发生变化的轮廓部分只用基素表达不能保证得到对场景的唯一解释20马尔视觉计算理论视觉信息的三级内部表达2.5-D表达（2.5-Dsketch）将物体可见表面正交投影分解成单元表面用法线（针）代表单元表面的取向将各法线画出，叠加于物体轮廓内可见面上本征图，表示了物体表面面元的朝向既表达了一部分物体轮廓的信息（这与基素表达类似），又表达了以观察者为中心、可观察到的物体表面的取向信息与人所理解的3-D物体一致（可见物体轮廓以内目标的3-D信息，如边界、深度，反射特性等）21马尔视觉计算理论视觉信息的三级内部表达3-D表达（3-Dsketch）以物体为中心（即也包括了物体不可见部分）的表达形式在以物体为中心的坐标系中描述3-D物体的形状及其空间组织

①空间占有数组，②单元分解，③几何模型广义圆柱体表达方法从计算机或信息加工的角度来说，视觉可计算性问题可分成几个步骤，步骤之间是某种表达形式，而每个步骤都是把前后两种表达形式联系起来的计算/加工方法22马尔视觉计算理论视觉信息处理按照功能模块的形式组织把视觉信息的系统看成由一组功能相对独立的模块所组成的思想，不仅有计算方面进化论和认识论的论据支持，而且某些功能模块已经能用实验的方法分离出来人通过使用多种线索或从它们的结合来获得各种本征视觉信息。这启示计算机视觉系统应该包含许多模块，每个模块获取某一特定的视觉线索，结合不同的模块来最终完成视觉任务23马尔视觉计算理论计算理论形式化表示必须考虑约束条件图象采集过程中，原始场景中信息会发生变化当3-D的场景被投影为2-D图象时，丢失了物体深度和不可见部分的信息图象是从特定视角获取的，同一物体的不同视角图象会不同，另外由于物体遮挡也会丢失信息成象投影使得照明、物体几何形状和表面反射特性、摄象机特性、光源与物体和摄象机之间的空间关系等都被综合成单一的图象灰度值，很难区分在成象过程中不可避免地会引入噪声和畸变24马尔视觉计算理论计算理论形式化表示必须考虑约束条件适定的问题：如果它的解是：①存在的；②唯一的；③连续地依赖于初始数据原始场景中信息发生变化的原因，使得将视觉处理问题作为光学成象过程逆问题的求解方法不适定，成了病态问题利用约束条件可改变病态问题通过给计算问题加上约束条件可使它含义明确从而能够获解25对马尔理论框架的改进四个有关整体框架的问题框架中输入是被动的框架中加工目的不变，总是恢复场景中物体的位置和形状等框架未足够重视高层知识的指导作用整个框架中信息加工过程基本自下而上，单向流动，没有反馈26对马尔理论框架的改进四个方面的相应改进增加了图象获取模块根据视觉目的进行决策利用高层知识可解决低层信息不足的问题增加了反馈控制流向27主要讲授内容图象处理主要讲述图像处理的基本概念、基本原理、典型方法、实用技术以及有关研究的新成果，重点包括基于点操作的空域增强技术以及基于模板操作的空域增强技术等图象分析主要讲述图像分析的基本概念、基本原理、典型方法、实用技术以及有关研究的新成果，重点包括图像分割的基础知识和基本方法，目标的表达描述技术和特性分析技术，以及图像模式识别的原理和方法等图象理解主要讲述图像理解的基本概念、基本原理、典型方法、实用技术以及有关研究的新成果，重点包括采集表达的基本原理和方法，3-D表面表达和实体表达，立体视觉模块，从运动求取结构，知识表达与逻辑推理，目标匹配与场景分类等内容图象基础知识图像理解之二29什么是图象图象用各种观测系统以不同形式和手段观测客观世界而获得的，可以直接或间接作用于人眼并进而产生视知觉的实体图象和信息人类从外界（客观世界）获得的信息约有75%来自视觉系统图象（广义/抽象）⊃图像（狭义/具体）30图象的表示和显示图象类型广义：图片，动画，绘图，文字/档，…狭义：单幅⇒序列图象，...静止⇒运动图象（视频），...2-D⇒3-D，彩色，立体对，多光谱，多视场图象，...灰度⇒深度，纹理图象，...图象单元一幅图象是许多图象单元的集合体2-D图象：象素（pictureelement），英文用pixel表示3-D图象：体素（volumeelement），英文用voxel表示f(x,y)→f(x,y,z),f(x,y,t)31图象的表示和显示图象表示2-D数组：f(x,y)x，y：2-D空间XY中坐标点的位置f：代表图象在(x,y)的性质F的数值f，x，y

的值在计算机内取整数性质F:可对应不同物理量，灰度图象里用灰度表示矩阵矢量

32图象的表示和显示图象显示33图象的表示和显示图象表示平面上的离散点集（二值图）象素区域（二值图）类似矩阵的结果（也可灰度图）34空间分辨率和幅度分辨率图象图象（水平）尺寸M：图象（垂直）尺寸N：象素灰度级数G(k-bit)：图象所需的位数b：

35空间分辨率和幅度分辨率采样1000×1000单元的传感器矩阵只有10–3的相对分辨率，而长度、电压，频率等测量的相对分辨率远高于10–6，但图象给出了信号的（多点）空间变化信息量化级数的选择人类视觉系统的分辨率（看得到连续的亮度变化而不要看出间断的量化级数）满足具体应用所需要的分辨率（如打印图象可只16个灰度级<屏幕显示的灰度级）36图象技术和图象工程图象技术图象技术在广义上是各种与图象有关的技术的总称主要功能/作用对图象的各种加工基于加工结果的判断决策和行为规划为此进行的硬件设计及制作图象工程一门系统地研究各种图象理论、技术和应用的新的交叉学科不同层次图象技术的有机结合及应用37图象处理系统的构成38图象采集图象采集装置对某个电磁能量谱波段（如X射线、紫外线、可见光、红外线等）敏感的物理器件，它能产生与所接收到的电磁能量成正比的（模拟）电信号数字化器，它能将上述（模拟）电信号转化为数字（离散）的形式39图象显示图象显示图象处理的结果多是供观察的图象数据⇒亮度模式显示显示设备电视显示器，液晶显示器，LED阴极射线管（CRT)打印设备转换到幻灯片、照片或透明胶片上40图象存储数据量度单位比特（bit），字节（byte=8bit）千（103）字节（Kbyte）兆（106）字节（Mbyte）吉（109）字节（Gbyte）太（1012）字节（Tbyte）图象存储器处理过程中使用的快速存储器：计算机内存，帧缓存较快重新调用的在线或联机存储器：磁盘，磁光盘不经常使用的数据库（档案库）存储器：磁带，光盘，光盘塔41图象存储格式（表示格式和文件格式）矢量格式：用线段或线段的组合体来表示图象光栅格式：用许多图象点的集合来表示图象图象存储格式BMP格式（BitMaP）：位图①位图文件头（也称表头）②位图信息（常称调色板）1:单色，4:16色，8:256色，24:真彩色③位图阵列（即图象数据）R:8bit，G:8bit，B:8bit42图象存储图象存储格式GIF格式（GraphicsInterchangeFormat）8位文件格式，最多只能存储256色图象图象数据均为压缩过的（LZW算法）一个GIF文件中可以存放多幅图象以实现网页上的动画TIF格式（TaggedImageFormatFile）独立于操作系统和文件系统文件可分4类：二值图象，灰度图象，调色板彩色图象，全彩色图象JPEG格式（JointPhotographicExpertGroup）适用于静止的灰度或彩色图象43图象处理对图象的增强以改善图象视觉质量对退化图象的恢复以消除各种干扰的影响根据对景物的投影来获得景物内部的图象对图象进行编码以减少表达图象的数据量，以有利于存储和传输给图象加入数字水印以保护图象的所有权空域增强──点操作图像理解之三45基本坐标变换坐标(x,y)，如用齐次坐标，则记为(x,y,1)46基本坐标变换平移变换47基本坐标变换缩放变换48基本坐标变换旋转变换49坐标变换扩展变换级联对一个坐标为v的点的平移、放缩、绕Z轴旋转变换（级联起来）可表示为：等价于用单个变换矩阵A对点v进行变换这些矩阵的运算次序一般不可互换级联示例50坐标变换扩展反变换逆矩阵拉伸变换剪切变换51坐标变换扩展变换示例平移变换放缩变换旋转变换拉伸变换剪切变换52坐标变换扩展旋转变换的分解53图象间运算——算术和逻辑运算算术运算加法：记为p+q减法：记为p–q乘法：记为p∗q（也可写为pq或p×q）除法：记为p÷q对整幅图象的算术和逻辑运算是逐象素进行的，即在两幅图象的对应（位置）象素间进行逻辑运算补（COMPLEMENT）：记为NOTq与（AND）：记为pANDq或（OR）：记为pORq异或（XOR）：记为pXORq组合逻辑运算54图象间算术运算的应用图象间加法的应用——去除采集噪声模型：运算：均值：均方差：55图象间算术运算的应用图象间减法的应用——两图相减可把差异凸显出来图象间乘法和除法的应用56灰度映射原理灰度映射函数57典型灰度映射图象求反——照片和底片58典型灰度映射增强对比度各段斜率不同59典型灰度映射动态范围压缩60典型灰度映射伽马校正指数变换：变换的结果是输入中较窄的低灰度范围被映射到输出中较宽的灰度范围，而同时输入中较宽的高灰度范围被映射到输出中较窄的灰度范围

61直方图均衡化灰度统计直方图1-D的离散函数（以灰度值为自变量）提供了图象象素的灰度值分布情况62直方图均衡化直方图与图象的视觉效果密切相关63直方图均衡化直方图均衡化原理借助直方图变换实现（归一的）灰度映射均衡化（线性化）基本思想变换原始图象的直方图为均匀分布==>大动态范围使象素灰度值的动态范围最大==>增强图象整体对比度（反差）归一化直方图ps(sk)=nk/n,0≤sk≤1,k=0,1,…,L-1增强函数EH(s)：单值单增函数，0≤s≤L-1，各灰度级在变换后仍保持排列次序0≤EH(s)≤L-1，变换前后灰度值动态范围一致64直方图均衡化满足条件的增强函数——累积直方图1-D的离散函数提供了图象象素灰度值的累积分布情况tk是k

的单值单增函数灰度取值范围一致，0≤tk≤1将s的分布转换为t

的均匀分布65直方图均衡化66直方图均衡化67直方图均衡化68直方图规定化借助直方图变换实现规定/特定的灰度映射对原始直方图进行灰度均衡化规定所需要的直方图，计算能使规定直方图均衡化的变换将原始直方图对应映射到规定直方图两种映射/对应规则单映射规则组映射规则I(l)：整数函数69直方图规定化70直方图规定化直方图规定化示例单映射规则vs.组映射规则71直方图规定化直方图规定化vs.直方图均衡化直方图均衡化自动增强效果不易控制总得到全图增强的结果直方图规定化有选择地增强须给定需要的直方图可得到特定增强的结果空域增强──模板操作图像理解之四73象素的邻域和邻接象素的邻域一个象素的邻域包含与该象素关系最密切的邻近象素/近邻象素4-邻域：N4(p)对角邻域：ND(p)8-邻域：N8(p)象素的邻接象素之间的一种空间关系，两个邻接的象素之间有接触。4-邻接：边接触对角-邻接：顶点接触8-邻接：边接触/顶点接触74象素间的连接和连通象素间的连接象素间的一种空间和属性关系两个象素是否连接：是否它们空间接触（邻接）是否它们的灰度值满足某个特定的相似准则（如它们灰度值相等，或同在一个灰度值集合中取值）4-连接：2个象素p和r在V中取值且r在N4(p)中8-连接：2个象素p和r在V中取值且r在N8(p)中75象素间的连接和连通象素的连通连通是连接的推广，连接是连通的特例通路：由一系列依次邻接的象素组成从具有坐标(x,y)的象素p到具有坐标(s,t)的象素q的一条通路由一系列具有坐标(x0,y0)，(x1,y1)，…，(xn,yn)的独立象素组成。这里(x0,y0)=(x,y)，(xn,yn)=(s,t)，且(xi,yi)与(xi-1,yi-1)邻接，其中1≤i≤n，n为通路长度连通：p到q有一条通路，且通路上两两邻接的象素也连接，则p和q连通4-连通，8-连通4-通路，8-通路

76象素间的连接和连通象素集合的连接和连通（部分）象素的集合构成图象中的子集在一个图象子集中与同一个象素相连通的所有象素构成该图象子集中的一个连通组元如果子集S中只有1个连通组元，即S中所有象素都互相连通，则称S是一个连通集对2个图象子集S和T来说，如果S中的一个或一些象素与T中的一个或一些象素邻接，则可以说2个图象子集S和T是邻接的对2个图象子集S和T来说，如果S中的一个或一些象素与T中的一个或一些象素连接，则可以说2个图象子集S和T是连接的一幅图象里的每个连通集构成该图象的一个区域。一个区域的边界也称区域的轮廓，一般认为是该区域的一个子集，它将该区域与其他区域分离开。组成一个区域的边界象素本身属于该区域而在其邻域中有不属于该区域的象素77象素间的距离距离度量函数性质：3个象素p、q、r，坐标(x,y)、(s,t)、(u,v)(1)D(p,q)≥0(D(p,q)=0当且仅当p=q)两个象素之间的距离总是正的(2)D(p,q)=D(q,p)距离与起终点的选择无关(3)D(p,r)≤D(p,q)+D(q,r)最短距离是沿直线的78象素间的距离距离度量函数类型(1)欧氏（Euclidean）距离(2)城区（city-block）距离(3)棋盘（chessboard）距离79象素间的距离范数和距离函数f(x)的范数两点间的Minkowski距离用距离定义邻域：考虑在空间点(xp,yp)的象素p4-邻域：N4(p)={r|D4(p,r)=1}8-邻域：N8(p)={r|D8(p,r)=1}80模板运算

81模板运算82模板运算模板卷积的主要步骤将模板在输入图象中漫游，并将模板中心与图象中某个象素位置重合将模板上的各个系数与模板下各对应象素的灰度值相乘将所有乘积相加（为保持灰度范围，常将结果再除以模板系数之和）将上述结果（模板的输出响应）赋给输出图象中对应模板中心位置的象素模板排序的主要步骤将模板在输入图象中漫游，并将模板中心与图象中某个象素位置重合读取模板下输入图象中各对应象素的灰度值将这些灰度值进行排序，一般将它们从小到大排成一列（单增）根据运算目的从排序结果中选一个序，取出该序象素的灰度值将取出的灰度值赋给输出图象中对应模板中心位置的象素83模板运算图象边界处的模板运算当模板中心对应输入图象的边界象素时，其邻域范围可能扩展到输入图象的边界之外忽略这些边界处的象素：仅处理图象内部的象素将输入图象进行扩展：如果用半径为r的模板进行模板运算，则在图象的四条边界外各增加/扩展一个r行或r列的带模板运算功能分类84线性平滑滤波邻域平均模板系数都是正的，且都为1为保持灰度值范围，卷积值应除以系数总个数例：33模板，应除以系数总个数985线性平滑滤波加权平均离中心近的象素应对滤波结果有较大的贡献模板：中心系数大，周围系数小权86线性平滑滤波高斯平均根据高斯分布来确定各模板系数模板分解，减少计算量87线性锐化滤波拉普拉斯算子积分可以平滑图象，微分可以锐化图象模板系数在中心为正而周围远离中心处为负拉普拉斯算子是各向同性的二阶微分算子既可考虑4-邻域，也可考虑8-邻域可增强图象中的灰度不连续边缘，减弱灰度值缓慢变化区域的对比度，将结果叠加到原始图象上，就可以得到锐化后的图象88线性锐化滤波高频提升滤波锐化：叠加图象微分结果减除图象积分结果

89非线性平滑滤波中值滤波原理设模板尺寸为M，M=2r+1，r为模板半径90非线性平滑滤波2-D中值滤波输出值大于模板中一半象素的值，又小于模板中一半象素的值（序：50%）91非线性平滑滤波中值滤波模板有实验表明，当使用超过9~13个象素的模板来消除图象中的噪声时，计算量的增加比消噪效果的改善更明显，所以常可使用稀疏的5

5模板来减少运算量92非线性平滑滤波计算2-D中值计算2-D中值的方法有3种，结果可能不同直接使用2-D模板先使用第1个1-D模板再使用第2个1-D模板先使用第2个1-D模板再使用第1个1-D模板93非线性平滑滤波序统计滤波更广泛的滤波——百分比（percentile）滤波最大值滤波最小值滤波中点滤波94非线性锐化滤波基于梯度的锐化滤波实际滤波中，常只使用梯度矢量的幅度（即矢量的模）模以2为范数/模计算（对应欧氏距离）以1为范数（城区距离）以为范数（棋盘距离）

95非线性锐化滤波最大-最小锐化变换最大值滤波和最小值滤波结合将一个模板覆盖区域里的中心象素值与该区域里的最大值和最小值进行比较，然后将中心象素值用与其较接近的极值（最大或最小值）替换锐化滤波模板的通用性质零位移：不改变边缘位置消除均值对称性质反对称性96线性和非线性混合滤波将线性滤波运算和中值滤波运算混合串联起来，先对较大的区域进行计算量较小的线性滤波操作，然后再计算线性滤波输出的中值，作为混合滤波的最终输出最简单的结构包括使用相同的平均滤波模板HL和HR以及直通的模板HC[f(i)]=f(i)97局部增强全局增强：把一幅图象作为一个整体局部增强：对图象某些局部区域的细节进行增强局部信息在对整幅图计算时常被忽略掉用全局增强不能保证在所关心的局部区域得到所需要的增强效果局部增强多了一个选择局部区域的步骤直接利用局部信息以达到局部增强的目的98局部增强直方图变换局部增强先将图象分成一系列小区域（子图象）对各子图象分别进行直方图变换99局部增强基于均值和方差的局部增强利用象素邻域内象素灰度的均值和方差增强图象中灰度比较大但方差比较小的区域增强变换图象分割基础图像理解之五101概述102概述前景（感兴趣目标），背景分离区域，提取目标利用区域特性（灰度、颜色、纹理、……）图象分割是由图象处理进到图象分析的关键步骤很多时候关注的仅是图象中的目标或前景（其他部分称为背景），它们一般对应图象中特定的、具有独特性质的区域103图象分割定义和技术分类

104图象分割定义和技术分类图象分割算法分类不连续性和相似性并行处理策略和串行处理策略分类①并行边界类②串行边界类③并行区域类④串行区域类105并行边界技术在灰度图中，两个不同的相邻区域之间灰度值会有不连续或局部突变，从而导致出现边缘边缘及检测原理正交梯度算子二阶导数算子边界闭合106边缘及检测原理剖面上的4个参数位置：边缘（等效的）最大灰度变化处（边缘朝向就在该变化方向上）斜率：边缘在其朝向上的倾斜程度（由于采样等原因，实际图像中的边缘是倾斜的）均值：分属边缘两边（近邻）像素的灰度均值（由于噪声等原因，灰度有波动）幅度：边缘两边灰度均值间的差（反映了不连续或局部突变的程度）107正交梯度算子梯度：对应一阶导数，梯度算子是一阶导数算子。对一个连续函数f(x,y)，它在位置(x,y)的梯度可表示为一个矢量。梯度矢量的幅度和方向角108正交梯度算子梯度图实例图（a）是原始图像，包含各种朝向的边缘图（b）为用索贝尔算子水平模板得到的水平梯度图，对垂直边缘有较强的响应图（c）为用索贝尔算子垂直模板得到的垂直梯度图，对水平边缘有较强的响应图（d）为根据欧式距离得到的索贝尔梯度图图（e）为根据城区距离得到的索贝尔梯度图图（f）为根据棋盘距离得到的索贝尔梯度图109二阶导数算子拉普拉斯算子（并行边界类）110边界闭合连接边缘象素111并行区域技术取阈值进行分割图象模型双峰直方图（对应目标和背景的两个单峰直方图混合而成）大小接近，均值相距足够远，均方差足够小取阈值分割步骤(1)确定阈值（关键/难点）(2)根据阈值划分象素112并行区域技术单阈值分割图象对灰度图（取值在gmin和gmax之间）确定一个灰度阈值T（gmin<T<gmax）113并行区域技术多阈值分割图象分割为多类区域（多个目标）114并行区域技术阈值分割方法分类依赖象素的（全局）阈值方法仅根据f(x,y)来选取阈值依赖区域的（局部）阈值方法根据f(x,y)和q(x,y)来选取阈值依赖坐标的（动态）阈值方法除根据f(x,y)和q(x,y)来选取，还与x,y有关将前两种阈值也称为固定阈值115并行区域技术

最小化116串行区域技术从区域着手顺序进行串行策略特点当前处理借助早期结果优点：抗噪声，抗干扰缺点：较复杂，费时间区域生长分裂合并117区域生长基本思想将相似象素结合起来构成区域基本步骤选择区域的种子象素确定将相邻象素包括进来的准则制定生长停止的规则讨论种子象素的选取生长准则依赖应用118区域生长生长示例根据直方图选取聚类中心的象素为种子根据与种子象素灰度差（>T）判断是否生长根据图象边缘确定生长何时终结119分裂合并令R代表整个图象区域，P代表逻辑谓词把R连续地分裂成越来越小的1/4的正方形子区域Ri，并且始终使P(Ri)=TRUE对任一个区域Ri，如果P(Ri)=FALSE，就将其分裂成不重叠的四等分对相邻的两个区域Ri和Rj，如果P(Ri∪Rj)=TRUE，就将它们合并起来如果进一步的分裂或合并都不可能了，则结束120分裂合并主要步骤先把图象分成任意大小且不重叠的区域然后再（根据准则）合并或分裂这些区域（迭代进行直到实现分割）典型分割技术图像理解之六122图割方法基于图论的图象分割技术本质上采用了基于边缘的串行分割思路将待分割图象I映射为一个对弧加权的有向图G，它在尺寸上和维数上都与I对应确定目标和背景的种子，并针对它们构建两个特殊的图结点，即源结点s和汇结点t；然后将所有种子根据它们的目标或背景标号分别与源结点或汇结点相连接计算弧代价函数，并对图G中的各个弧赋予一定的弧代价使用最大流图优化算法来确定对图G的图割，从而区分对应目标和背景象素的结点图割方法的一个重要特性是提供了一种借助交互以有效方法改进先前获得的分割结果的能力123图割方法构建图G将边缘象素和边界段（弧）用图表示124图割方法构建图G对任一段弧(ni,nj)都可定义一个代价（或费用），记为C(ni,nj)，它可看作是对弧的加权对给定的待分割图象I，要将其转化表示为一个对弧加权的图G其中，将图象I中每个象素看成图G中的一个结点，即结点集合N由所有象素构成；而将象素间的邻接关系用图G中的弧来表示，即结点对集合A表示象素间的（加权）联系125图割方法构建源结点和汇结点126图割方法构建源结点和汇结点如上可获得一个弧加权图Gst=[N∪{s,t},A]，结点集N对应图象I中的象素，s和t是两个特殊的终端结点弧集合A中的元素可分为两类：连接一对相邻象素的弧与将象素和终端结点连接起来的弧在Gst中的一个割将图中结点分成两组，它的代价是这个割所对应的弧（割所穿过/跨越的弧）的代价之和代价最小的割称为最小s-t割，它将结点分成两组不重叠的子集S(s∈S)和T(t∈T)，且从s到t没有有向的通路127图割方法弧的代价代价最小s-t割的代价是其所对应的所有弧的代价之和Lk∈{o,b}是像素ik的标号，o表示目标，b表示背景L={L1,

L2,

…,

L|I|}：二值分割结果区域性质项：弧两个端结点所对应象素的灰度边界性质项：弧两个端结点所对应象素间的灰度差128图割方法第一种弧：相邻像素之间的弧一方面，给定一个像素，根据其灰度将其标为o或b都会有代价Rp(o)表示将像素p标为目标的代价，Rp(b)表示将像素p标为背景的代价当亮目标在暗背景上时，Rp(o)的值在暗像素（低Ip值）处大而在亮像素处小；当暗目标在亮背景上时，Rp(b)的值在亮像素（高Ip值）处大而在暗像素处小另一方面，对两个相邻的像素p和q，根据其灰度将其赋予不同的标号也会有一定的代价若它们都属于o或b，则弧（p,q）的代价F(p,q)应比较大；若它们一个属于o而另一个属于b，即跨越o和b的边界，则弧（p,q）的代价F(p,q)应比较小例如，可取两个相邻像素p和q之间弧（p,q）的代价与它们间的梯度幅度成反比129图割方法第二种弧：像素与终端节点之间的弧由一系列相邻像素的弧所构成，其总代价是这些相邻像素的弧的代价之和，加1目的是使弧不饱和（B和O分别表示背景和目标像素集合）将上述结果结合起来，赋予各种弧的代价函数为：130图割方法图割的计算对偶：计算最小s-t割⇔计算s到t的最大流最大流的值等于最小割的代价通过弧的水流由其容量或代价决定从s到t的最大流能使一组弧饱和，这些饱和的弧对应最小割，将节点分为不重合的两部分S和T增加通路算法考虑推动从源s到汇t的流直至达到最大流开始时将流的状态初始化为0（保留在残留图Gr中）沿未饱和的弧来确定最短的s→t通路借助推动最大可能的流而使得弧达到饱和131图割方法图割的计算宽度优先搜索确定最短通路算法复杂度O(mn2)，n是结点数而m是弧数132分水岭分割算法分水岭（watershed，也称分水线/水线）把图象看成3-D地形的表示，即2-D的地基（对应图象空间）加上第3维的高度（对应图象灰度）计算过程是串行的，得到的是目标的边界（但利用了区域的一致性）133基本原理和步骤分水岭在两个圆的两个相交点画一直线，该直线的位置为从两个山峰流下来的水汇聚的地方，该直线可称为分水线如果在分水线位置将两个重叠圆形目标分隔开可给出一种最优的分割结果134基本原理和步骤分水岭建立不同目标间的分水岭（涨水法）135基本原理和步骤分水岭计算步骤设待分割图象为f(x,y)，其梯度图象为g(x,y)用M1,M2,…,MR表示g(x,y)中各局部极小值的象素位置，C(Mi)为与Mi对应的区域中的象素坐标集合用n表示当前灰度阈值，T[n]代表记为(u,v)的象素集合，g(u,v)<n，T[n]={(u,v)|g(u,v)<n}对Mi所在的区域，其中满足条件的坐标集合Cn(Mi)可看作一幅二值图象Cn(Mi)=C(Mi)∩T[n]136基本原理和步骤分水岭计算步骤用C[n]代表在灰度阈值为n时图象中所有满足条件的象素（被淹没）C[max+1]将是所有区域的并集C[n–1]是C[n]的子集，C[n]是T[n]的子集，所以C[n–1]又是T[n]的子集137基本原理和步骤分水岭计算步骤令S

代表T[n]中的连通组元集合，对每个连通组元s∈S[n]，有3种可能性：(1)s∩C[n–1]是1个空集(2)s∩C[n–1]里包含C[n–1]中的一个连通组元(3)s∩C[n–1]里包含C[n–1]中一个以上的连通组元分别处理：(1)C[n]可由把连通组元s

加到C[n–1]中得到(2)C[n]可由把连通组元s

加到C[n–1]中得到(3)需要在s

中建分水岭138基本原理和步骤遇到部分或整个区分两个或以上区域的分界线遇到一个新的极小值s属于某些极小值的区域139算法改进和扩展利用标号控制分割过分割（over-segmentation）受图象中噪声和其它不规则结构影响利用标号（marker）图象中的一个连通组元内部标号：对应目标外部标号：对应背景（分水岭）140算法改进和扩展利用标号控制分割(a)表示部分覆盖的两个区域(b)表示经过距离变换的结果（两个局部极小值）(c)检测出的分水线141算法改进和扩展分水岭算法的扩展DaiSY,ZhangY-J.“ColorImageSegmentationinbothFeatureandImageSpace”.AdvancesinImageandVideoSegmentation,ZhangY-Jed.,IRMPress,Chapter10(209-227),2006142算法改进和扩展分水岭算法的扩展从图象域（灰度、梯度）到特征域特征域（彩色域）算法步骤：(1)选择合适的彩色空间，做出3-D彩色直方图(2)将3-D彩色直方图进行反转变换(3)在不同的彩色聚类之间建立分水岭(4)将聚类结果映射回图象域中(5)进行后处理以得到最终分割图象目标表达图像理解之七144基于边界的表达——技术分类边界点集合：各点间没有顺序参数边界：将目标的轮廓线表示为参数曲线曲线逼近：用几何基元来近似145链码链码表达用线段表示边界上相邻两个象素之间的联系每个线段的长度固定而方向数目取为有限起点用坐标表示，其余点只用接续方向146链码链码归一化起点归一化将链码看作由方向数构成的自然数选取值最小的自然数顺序147链码链码归一化旋转归一化利用链码的一阶差分差分码不随轮廓旋转而变化148链码平滑链码表达轮廓将原始的链码序列用较简单的序列代替虚线箭头：原始的在象素p和q之间的8-连通链码实线箭头：用来替换原始序列的新序列149多边形用多边形去近似逼近边界三种方法(1)基于收缩的最小周长多边形法(2)基于聚合（merge）的最小均方误差线段逼近法(3)基于分裂（split）的最小均方误差线段逼近法150多边形基于收缩的最小周长多边形法将原边界看成是有弹性的线，将组成边界的象素序列的内外边各看成一堵墙，将线拉紧151多边形基于聚合的最小均方误差线段逼近法基于分裂的最小均方误差线段逼近法152基于区域的表达——技术分类区域分解：简单的单元形式围绕区域：外接圆，外包围矩形，……内部特征：内部象素的特定抽象集合153空间占有数组对图象f(x,y)中任一点(x,y)：如果它在给定的区域内，就取f(x,y)为1否则就取f(x,y)为0所有f(x,y)为1的点组成的集合就代表了所要表示的区域154四叉树基本思路分层分解图象利用金字塔式的数据结构四叉树表达法每次将图象一分为四树结构：T={N,A}N：结点集{n1,...}A：弧集{ai,...}155四叉树四叉树表达图示结点数目156金字塔金字塔结构可借助图（graph）来解释金字塔结构由各层内的“兄弟/邻居”关系和各层间的“父子”关系所确定邻域图和二分图用(n×n)/r描述一个金字塔结构缩减率r缩减窗（n×n的方窗）157图像金字塔是图像中多尺度表达的一种，最主要用于图像的分割，是一种以多分辨率来解释图像的有效但概念简单的结构最初用于机器视觉和图像压缩，一幅图像的金字塔是一系列以金字塔形状排列的分辨率逐步降低，且来源于同一张原始图的图像集合。其通过梯次向下采样获得，直到达到某个终止条件才停止采样金字塔的底部是待处理图像的高分辨率表示，而顶部是低分辨率的近似将一层一层的图像比喻成金字塔，层级越高，则图像越小，分辨率越低159图像金字塔高斯金字塔(Gaussianpyramid):用来向下采样，主要的图像金字塔拉普拉斯金字塔(Laplacianpyramid):用来从金字塔低层图像重建上层未采样图像，在数字图像处理中也即是预测残差，可以对图像进行最大程度的还原，配合高斯金字塔一起使用向下与向上采样是对图像的尺寸而言的上采样就是图像尺寸加倍，图像变大，分辨率增大下采样就是图像尺寸减半，图像变小，分辨率减小160图像金字塔两者的简要区别高斯金字塔用来向下降采样图像拉普拉斯金字塔用来从顶层图像中向上采样重建一个图像要从金字塔第i层生成第i+1层（第i+1层表示为Gi+1），我们先要用高斯核对Gi进行卷积，然后删除所有偶数行和偶数列当然，新得到图像面积会变为源图像的四分之一按上述过程对输入图像G0执行操作就可产生出整个金字塔161高斯金字塔是通过高斯平滑和下采样获得一系列图像也就是说第K层高斯金字塔通过平滑、下采样就可以获得K+1层高斯图像高斯金字塔包含了一系列低通滤波器，是每次高斯模糊一次，然后进行下采样。其意义是：模仿图像的不同尺度对于一副图像，近距离观察与在一米之外观察看到的图像效果是不同的，前者比较清晰，后者比较模糊，前者比较大，后者比较小，前者能看到一些细节信息，后者能看到一些轮廓信息，这就是图像的尺度图像的尺度是自然存在的，并不是人为创造的162下采样为了获取层级为Gi+1的金字塔图像，我们采用如下方法:对图像Gi进行高斯内核卷积将所有偶数行和列去除得到的图像即为Gi+1的图像，显而易见，结果图像只有原图的四分之一通过对输入图像G0（原始图像）不停迭代以上步骤就会得到整个金字塔。同时我们也可以看到，向下取样会逐渐丢失图像的信息以上就是对图像的向下取样操作，即缩小图像163拉普拉斯金字塔拉普拉斯金字塔中的图象可用对高斯金字塔中相邻两层图象的相减而近似得到需先将图象在较粗的尺度（较高的层次）上扩展扩展比减少尺寸的压缩困难，因为缺少的信息需要通过插值来得到164对图像的向上取样如果想放大图像，则需要通过向上取样操作得到，具体做法如下：将图像在每个方向扩大为原来的两倍，新增的行和列以0填充使用先前同样的内核（乘以4）与放大后的图像卷积，获得“新增像素”的近似值得到的图像即为放大后的图像，但是与原来的图像相比会发觉比较模糊，因为在缩放的过程中已经丢失了一些信息166图像金字塔可以将拉普拉斯金字塔理解为高斯金字塔的逆形式关于图像金字塔非常重要的一个应用就是实现图像分割图像分割先要建立一个图像金字塔，然后在Gi和Gi+1的像素直接依照对应的关系，建立起父子关系快速初始分割可以先在金字塔高层的低分辨率图像上完成，然后逐层对分割加以优化在某种分辨率下无法发现的特性在另一种分辨率下很容易被发现167围绕区域外接盒（Feretbox）：包含目标区域的最小长方形（朝向特定的参考方向）围盒（minimumenclosingrectangle，MER）：包含目标区域的（可朝向任何方向）最小长方形凸包：包含目标区域的最小凸多边形168基于变换的表达——技术分类线性：采用的变换技术是线性的，则表达也是线性的非线性：采用的变换技术是非线性的，则表达也是非线性的169傅里叶变换表达离散傅里叶变换表达将XY平面中的曲线段转化为复平面UV上的点序列将2-D的问题简化为1-D的问题170傅里叶变换表达从1个封闭边界可得到1个复数序列将序列进行傅里叶变换（数据量不变）取（部分）傅里叶变换系数表达轮廓（节省数据量）171傅里叶变换表达借助傅里叶变换系数近似表达边界172傅里叶变换表达傅里叶变换表达受边界平移、旋转、尺度变换以及计算起点（傅里叶表达与从边界点建立复数序列对的起始点有关）的影响情况目标描述图像理解之八174目标描述表达是直接具体地表示目标好的表达方法应节省储存空间描述是较抽象地表示目标好的描述应对目标的尺度变化、平移、旋转不敏感边界描述（描述区域形状）区域描述（描述区域反射性质）关系描述（描述边界间/区域间的关系）175基于边界的描述利用处在目标区域的边界上的象素集合来（主要）描述边界的特点/特性简单边界描述符形状数边界矩176简单边界描述符边界的长度边界/轮廓长度（区域周长）对区域R，轮廓点P：

P本身属于R

P的邻域中有象素不属于R177简单边界描述符边界的长度区域的轮廓点和内部点要采用不同的连通性来定义内部点8-方向连通，轮廓为4-方向连通内部点4-方向连通，轮廓为8-方向连通1784-连通和8-连通两种邻域：4-邻域和8-邻域两种连通：4-连通和8连通连通悖论：对准确测量带来影响边界点和内部点目标点和背景点179简单边界描述符边界的长度4-方向连通轮廓B48-方向连通轮廓B8使用单位长链码180简单边界描述符边界的直径边界上相隔最远2点之间的距离距离度量：DE(·)，D4(·)，D8(·)181简单边界描述符曲率斜率、曲率、角点（局部特性）斜率：轮廓点的（切线）指向曲率：斜率的改变率曲率大于零，曲线凹向朝着法线正向曲率小于零，曲线凹向朝着法线负向角点：曲率的局部极值点182基于离散曲率的描述符曲率描述了边界上各点沿边界方向变化的情况曲率与几何特征183基于离散曲率的描述符离散曲率离散目标中沿离散点序列组成的轮廓上方向的变化给定一个离散点集合P={pi}i=0,…,n，它定义了一条数字曲线（曲线两个端点像素各只有一个近邻像素，其他每个像素都恰好有两个近邻像素），在点pi∈P处的k-阶曲率ρk(pi)=|1-cosθki|，其中θki=angle(pi-k,pi,pi+k)是两个线段[pi-k,pi][pi,pi+k]之间的夹角，而阶数k∈{i,…,n-i}。下图给出对数字曲线Ppq={pi}i=0,…,17在点p10处计算3-阶离散曲率ρ3(p10)的情况184基于离散曲率的描述符离散曲率引入阶数k是为了减少曲率受边界方向局部变化的影响，比较高阶的离散曲率能比较准确的逼近由离散点序列所确定的整体曲率185基于离散曲率的描述符离散曲率的计算对一个参数曲线c(t)=[x(t),y(t)]，它的曲率函数k(t)定义为先对x(t)和y(t)进行采样再求导数设需要计算在点c(n0）处的曲率，先在两边获取一定数量的采样点，如图10.4.5所示利用有限差分法计算将上述结果代入（10.4.3）就可算得曲率，实现简单，但对噪声很敏感186基于曲率的描述符目标轮廓上各点的曲率本身就可用作描述符，但数据量太大且冗余。在计算出各点曲率后，可进一步对整个目标轮廓计算以下曲率描述符（测度）曲率的统计值曲率最大、最小点、拐点弯曲能187形状数轮廓差分码中其值最小的1个序列形状数示例4-方向链码：10103322差分码：33133030形状数：03033133188形状数形状数的阶形状数序列的长度闭合曲线阶是偶数凸形区域形状数的阶对应区域边界外包矩形的周长189形状数阶给定时边界形状数的计算从所有满足给定阶要求的矩形中选取出长短轴比例最接近图(a)所示已给边界的包围矩形（围盒），图(b)根据给定阶将选出的矩形划分为图(c)所示多个等边正方形保留50%以上面积包在边界内的正方形，得到与边界最吻合的多边形，图(d)根据上面选出的多边形，以图(d)中黑点（可任取）为起点计算链码，得到：11010030030322322212求出链码的差分码：30313031031330130031循环差分码使其最小，就得到所给边界的形状数：00313031303103133013190边界矩矩是一个物理量目标的边界可看作由一系列曲线段组成通过定量描述曲线段而进一步描述整个边界可把曲线段表示成1个1-D函数f(r)把f(r)的线下面积看成1个直方图191边界矩矩的计算均值对均值的n阶矩μn与f(r)的形状有直接联系μ2描述了曲线相对于均值的分布μ3描述了曲线相对于均值的对称性192基于区域的描述利用处在目标区域内的象素集合来描述区域（侧重整个目标或目标内部）的特点/特性简单区域描述符拓扑描述符区域不变矩193简单区域描述符区域面积基于对象素个数的计数求区域面积的不同计算方法194简单区域描述符区域面积网格多边形（顶点在采样网格上）区域Q的面积A(Q)=NI+NB/2-1NI是Q的内部点的个数NB是正好处在Q的轮廓上离散点的个数令R为Q中所包含点的集合，总点数|R|=NI+NB195简单区域描述符区域面积多边形区域面积计算示例

NI=71，NB=10，A(Q)=75多边形Q所定义的面积轮廓（点集）所定义的面积196简单区域描述符区域重心对非规则物体，其重心坐标和几何中心坐标常不相同

197简单区域描述符区域密度多种影响因素⇒综合结果透射率（transmission）

T=穿透目标的光/入射的光光密度（opticaldensity）入射的光与穿透目标的光的比（透射率的倒数），取以10为底的对数

OD=lg(1/T)=–lgT积分光密度（integratedopticaldensity）区域中各象素光密度的和积分光密度是直方图中各灰度值的加权和

198拓扑描述符拓扑学研究图形不受畸变变形（不包括撕裂或粘贴）影响的性质拓扑性质：全局性质，与距离无关欧拉数E=C-H欧拉数描述了区域的连通性H：区域内的孔数C：区域内的连通组元个数199拓扑描述符对一幅二值图象A，可以定义两个欧拉数4-连通欧拉数E4(A)4-连通的目标个数减去8-连通的孔数E4(A)=C4(A)-H8(A)8-连通欧拉数E8(A)8-连通的目标个数减去4-连通的孔数E8(A)=C8(A)-H4(A)200拓扑描述符多边形网全由直线段（包围）构成的区域集合欧拉公式V−B+F=E=C−HV：顶点数B：边线数F：面数201区域不变矩区域矩：用所有属于区域内的点计算f(x,y)的p+q

阶矩f(x,y)的p+q

阶中心矩f(x,y)的归一化的中心矩202区域不变矩不变矩计算示例同一幅图象得到的不同变型203对目标关系的描述多个边界/区域间的关系目标标记和计数点目标的分布字符串描述树结构描述204目标标记和计数象素标记检查当前象素与之前若干近邻象素的连通性考虑4-连通的情况（从左上向右下扫描）205目标标记和计数游程连通性分析206点目标的分布当图象中有许多个同类的目标时，为方便研究它们之间的关系，常将各个目标抽象为点目标对点目标集合，目标间相互关系常比单个目标在图象中的位置或单个目标本身的性质更重要207点目标的分布208点目标的分布根据分布的统计值来区分不同分布距离计算⇒目标计数将视场分成一些子区域μ：子区域内目标数的均值σ2：子区域内目标数的方差

σ2=μ：泊松分布

σ2>μ：聚类分布

σ2<μ：均匀分布209字符串描述描述语法/重写（替换）规则：

S→aA起始符号S用元素a和变量A来替换

A→bS变量A用元素b和起始符号S来替换

A→b变量A用单个元素b来替换210字符串描述运用重写规则产生结构字符串：对应头尾连接的线段用有向线段（抽象）描述图象区域，除头尾连接，还可用其他运算来结合211字符串描述利用有向线段并结合运算描述复杂结构212树结构描述树中有2类重要的信息：关于结点的信息，可用一组字符来记录关于一个结点与其相连通结点的信息，可用一组指向这些结点的指针来记录213树结构描述定义预期A在区域B的左边可以有多种方法A中的所有像素都必须在B中的所有像素的左边，图(a)A中至少一个像素必须在B中的若干像素的左边，图(b)A的重心必须在B的重心的左边，图(c)A的重心必须在B的最左边像素的左边，且A的最右边像素必须在B的最右边像素的左边，图(d)图象识别图像理解之九215图象识别传统的模式识别一般指对客观事物进行分析，做出判断的过程现在常用模式识别指用计算机就人类对周围世界的客体、过程和现象的识别功能进行自动模拟的学科模式识别主要有三个分支统计模式识别结构（句法）模式识别模糊模式识别216模式和分类模式和模式矢量模式是一个广泛的概念，模式由一个或多个模式符（也可叫特征）组成模式类由具有共同特性的模式组成图象模式可定义为对图象中的目标或其它感兴趣部分定量或结构化的描述矢量是一种定量描述模式的表达方式x=[x1

x2…

xn]T217模式和分类模式识别和分类对给定的M个模式类s1,s2,…,sM，确定M个决策函数d1(x),d2(x),…,dM(x)。如果一个模式x属于类si，则di(x)>dj(x)j=1,2,…,M;j≠i如果对x的值，有di(x)=dj(x)，则得到将类i与类j分开的决策边界dij(x)=di(x)

dj(x)=0218统计模式识别根据模式统计特性确定决策函数选取特征表达描述模式设计分类器（根据特征）进行分类最小距离分类器最优统计分类器自适应自举219最小距离分类器每个模式类用一个均值矢量表示利用欧氏距离来确定接近程度如果Dj(x)是最小的距离，则将x赋给类sj等价于计算决策函数在dj(x)给出最大值时将x赋给类sj220最小距离分类器类si和sj之间的决策边界给出一个连接mi和mj线段的垂直二分界M=2，垂直二分界是一条线M=3，垂直二分界是一个平面M>3，则垂直二分界是一个超平面仅由d12(x)的符号就可判断模式属于哪个类221自适应自举弱分类器：分类效果在两类样本时仅略高于50%需要将多个这样的独立分类器结合起来以取得更好的效果自举：将这些分类器依次分别用于不同的训练样本子集自举算法将多个弱分类器结合成一个比其中每个弱分类器都要好的新的强分类器如何选择输入到各个弱分类器的训练样本子集；如何结合它们以构成一个强分类器222自适应自举自适应自举初始化K，K为需使用的弱分类器数量令k=1，初始化权重W1(i)=1/m对每个k，使用训练集合和一组权重Wk(i)来训练弱分类器Ck，对每个模式xi赋一个实数，即Ck：X→R选择系数ak>0∈R更新权重，相对增加错分样本的权重223自适应自举自适应自举设置k=k+1如果k≤K，回到步骤(3)最后的强分类器是在每个步骤，要确定弱分类器Ck以使其性能与权分布Wk(i)相适应。在二分类情况下，弱分类器训练要最小化的目标函数为224感知机最基本的感知机建立能将两个线性可分训练集分开的线性决策函数225感知机对模式矢量增加第n+1个元素构建一个扩充模式矢量y，让yi=xi，i=1,2,…,n，且后面加一个元素yn+1=1其中y=[y1

y2…yn1]T是一个扩充模式矢量，w=[w1

w2…wnwn+1]T是一个权矢量关键问题：用模式矢量的给定训练集确定w226感知机线性可分类由两个线性可分训练集获取权矢量令w(1)代表一个任意选定的初始权矢量如果y(k)∈s1，wT(k)y(k)≤0w(k+1)=w(k)+cy(k)如果y(k)∈s2，wT(k)y(k)≥0w(k+1)=w(k)−cy(k)否则：w(k+1)=w(k)如果：y(k)∈s1，wT(k)y(k)>0；y(k)∈s2，wT(k)y(k)<0227感知机线性可分类两个训练集，每个包括两个模式先将模式扩充，对类s1得到训练集{[001]T,[011]T}，对类s2得到训练集{[101]T,[111]T}228感知机线性不可分类最小化实际响应和希望响应间的误差沿J(w)负梯度的方向逐步增加w以寻找上述函数的最小值。最小值应在r=wTy时出现通用的梯度下降算法可写成：229感知机线性不可分类写成德尔塔（Delta）校正算法的形式权矢量的误差误差的变化量（权矢量由w(k)变为w(k+1)）改变权重能将误差减少

||y(k)||2，下一轮继续230支持向量机线性可分类线性分类器的设计目的：要设计一个超平面g(x)=wTx+w0=0满足条件的超平面一般不惟一离开两个类都比较远的超平面分类的结果会更好些，可能的错误率也会更小一些231支持向量机线性可分类对每个朝向，与两个类距离相等的超平面应该是与两个类都有最大距离的超平面确定能给出类距离最大的朝向的超平面从一个点到一个超平面的距离d=|g(x)|/||w||232支持向量机

233支持向量机线性可分类结果为最优解的向量参数w是Ns个（Ns≤N）与λi≠0相关的特征向量的线性组合（支持向量）支持向量机：最优的超平面分类器234支持向量机线性不可分类训练特征向量可以分成以下三类：向量落在分类带之外且被正确地分了类向量落在分类带之内且被正确地分了类0≤ti(wTx+w0)<1向量被错误地分了类ti(wTx+w0)<0统一ti(wTx+w0)≥1−ri235结构模式识别句法模式识别一组模式基元，一组确定这些基元相互作用的规则（句法）和一个识别器（称为自动机）字符串结构识别树结构识别236字符串结构识别字符串文法文法（语法）：一组句法规则，控制字符集中符号产生句子的过程语言：由一个文法G所产生的一组句子，记为L(G)句子：符号的串，代表模式，语言对应模式类文法G1中的句法规则只允许产生对应类s1中模式的句子，文法G2中的句法规则只允许产生对应类s2中模式的句子，……识别：对一个表示未知模式的句子，决定在哪个语言中该模式表示了一个可成立的句子237字符串结构识别字符串文法定义一个四元组：G=(N,T,P,S)N

为一个有限的变量集，称为非终结符号集用大写字母A,B,…,S,…代表非终结符号T

为一个有限的常量集，称为终结符号集用小写字母a,b,c,…表示终结符号P

是一组称为产生式的重写规则集S

在N中，称为起始符号238字符串结构识别字符串文法例：文法G=(N,T,P,S)N={A,B,C}，T={a,b,c}P={S→aA,A→bA,A→bB,B→c}S⇒aA⇒abA⇒abbA⇒abbbA⇒abbbbA⇒abbbbbB⇒abbbbbc语言：L(G)={abnc|n≥1}，bn代表b的n次重复239字符串结构识别语义应用句法确定了目标的结构，而语义主要与其正确性有关通过使用语义信息，可用较少的句法规则以描述较广泛（但是有限）的模式类240字符串结构识别用自动机作为字符串识别器自动机能识别一个输入模式字符串是否属于与自动机关联的语言有限自动机：由规则语法产生的语言识别器Af=(Q,T,δ,q0,F)Q是一个有限非空状态集；T是一个有限输入字符集；δ是一个从Q×T（即由Q和T的元素组成的排序对集合）到所有Q子集的映射；q0是初始状态；F（Q的一个子集）是一个最终或可接收的状态集合241字符串结构识别用自动机作为字符串识别器有限自动机状态图Q={q0,q1,q2}T={a,b}F={q0}映射规则δ(q0,a)={q2}，