图像识别与模式识别.ppt
图像（模式）识别概念,模式识别：对表征事物或现象的各种形式的（数值的，文字的和逻辑关系的）信息进行处理和分析，以对事物或现象进行描述、辨认、分类和解释的过程，是信息科学和人工智能的重要组成部分。什么是模式 （Pattern）？,“模式”是一个客观事物的描述，是指建立一个可用于仿效的完善的标本。,图像识别与模式识别,模式识别的研究内容 1）研究生物体（包括人）是如何感知对象的，属于认知科学的范畴 2）在给定的任务下，如何用计算机实现模式识别的理论和方法,典型模式识别系统 图像识别系统,人脸识别系统,8图像识别,8.1 概述模式可以定义为物体的描述。由于描述这个词的意义比较广泛，有人把它推广到图像数据本身，因为图像数据也是相应事物的一种描述，只不过这样的描述不够抽象和简要而已。前章中我们已经讨论过图像的各种特征和描述的提取方法。因此，我们将模式解释为物体的较抽象的特征和描述。,模式可以是以矢量形式表示的数字特征；也可以是以句法结构表示的字符串或图；还可以是以关系结构表示的语义网络或框架结构等。对于上述三种类型的模式，必须分别使用不同的识别和推理方法：统计模式识别，句法模式识别和人工智能方法。,统计模式识别基本原理是：有相似性的样本在模式空间中互相接近，并形成“集团”，即“物以类聚”。主要方法有：决策函数法， k近邻分类法，支持向量机，特征分析法，主因子分析法等参考书籍：统计模式识别(Andrew R.Webb) Jain A K, Duin R P W, Jianchang Mao. Statistical pattern recognition: a review. Pattern Analysis and Machine Intelligence, 2000. 22(1) : 437.,句法（或结构）模式识别 基于形式语言理论的概念为基础。模式按其结构分解为子模式或模式基元，模式基元的连接关系以文法形式进行描述。,一个场景的示意图 场景结构的分析,模糊模式识别模糊集理论，Zadeh，1965模糊集理论在模式识别中的应用神经网络模式识别特点：具有信息分布式存储、大规模自适应并行处理、高度的容错性以及学习能力缺点：实际应用中仍有许多因素需要凭经验确定，比如如何选择网络节点数、初始权值和学习步长等；局部极小点问题、过学习与欠学习问题等,特征选择 所要提取的应当是具有可区别性、可靠性、独立性好的少量特征。因此特征选择可以看作是一个(从最差的开始)不断删除无用的特征和组合有关联的特征的过程，直到特征的数目减少到易于驾驭的程度，同时分类器的性能仍能满足要求为止。,每类的每一个特征均值： 假设训练样本中有个不同类别的样本。令表示第类的样本数，第类中第个样本的两个特征分别记为和。每类的每一个特征均值：和注意：仅是两个值基于训练样本的估计值，而不是真实的类均值。,特征方差第类的特征和特征的方差估值分别为： 和 在理想情况下同一类别中所有对象的特征值应该很相近。,特征相关系数第类特征和特征的相关系数估计为 它的取值范围为。如果=0，说明这两特征之间没有相关性；接近+1表示这两个特征相关性强；为-1表示任一特征都与另一特征的负值成正比。因此，如果相关系数的绝对值接近1，则说明这两个特征可以组合在一个特征或干脆舍弃其中一个。,类间距离一个特征区分两类能力的一个指标是类间距离，即类均值间的方差归一化间距。显然，类间距离大的特征是好特征。对特征来说，第类与第类之间的类间距为：,降维有许多方法可以将两个特征和合成为一个特征，一个简单的方法是用线性函数：由于分类器的性能与特征幅值的缩放倍数无关，可以对幅值加以限制，如因此 其中是一个新的变量，它决定和在组合中的比例。,如果训练样本集中每一对象都对应于二维特征空间(即平面)中的一个点，上式描述了为所有到在轴(与轴成角)上的投影。显然应选取使得类间距最大的或者满足评价特征质量的其它条件的。,8.2 统计模式识别,8.2.1 基本概念这里我们讨论数字特征的识别。其前提是，假定我们所处理的模式每一个样本都表示为N维特征矢量，写为： 显然，特征矢量 可以表示为N维特征矢量空间 中的一个点，这样统计模式识别的概念及方法就可以在特征空间中予以研究。,基本概念,模式分类：根据识别对象的观测值确定其类别样本与样本空间表示：,类别与类别空间：c个类别（类别数已知）,决 策,把样本x分到哪一类最合理？解决该问题的理论基础之一是统计决策理论决策：是从样本空间S，到决策空间的一个映射，表示为 D: S - ,假设我们要把一个样本集合 分成M类 ；如上所述，该样本集合可以表示为N维特征空间 中的一个点集，它的分类问题表述为将该特征空间划分为M个子空间，每一子空间为一类，子空间中的样本点属于相应类别。这样，分类问题的关键就在于如何找到一个正确子空间划分，即划分子空间的界面。,下图为二维特征空间，三类问题。,决策区域与决策面(decision region/surface)：,数学上，统计模式识别问题可以归结为：对一组给定的样本集合，找出其最佳的分类判决函数 ，并作判决：若对所有的 均有： 则作判决：,因为处理的是分类问题，因此最佳的意义是分类误差最小。 由于求解最佳判决函数的出发点和途径不同，因此产生了各种不同的分类方法：判别函数方法贝叶斯分类器：判别函数表示为似然比，也称为最大似然率分类器或最小损失分类器集群分类方法：它几乎不需要有关待分样本的先验知识。,分类器是某种由硬件或软件组成的“机器”：计算c个判别函数gi(x)最大值选择,8.2.2 判别函数方法在很多分类问题中，往往必须知道待分样本的先验知识。这里假设我们已经知道判别函数的形式，剩下的问题是如何求判别函数的待定参量以及进行分类判决。诚然，由分类者随心所欲地选择判别函数的形式，是件快事。但是，类别函数选择不合适，会导致分类误差的增加。,一、 线性判别函数线性判别函数的一般形式为： 其中， ， 分别称为扩充了的特征矢量和权矢量。,使用线性判别函数的分类判决有下述两种情况：l 第一种情况：每一类可以用一个判决平面与其它所有类隔开，在这种情况下，有M个判决函数：,l 第二种情况：每一类与其它所有各类可以由不同的判决平面一一隔开，也就是说，各类是可分段可分的，共有 个判决面。 判决函数可以写成 若对于所有的 均有： 则作判决：,死区问题 ？,DAG,在判决函数完全获得定义之后，分类器的设计才算结束，可以用于分类。通常，线性判别函数中的权系数 是用训练或称学习的方法获得的。为了讨论上的方便，先考虑两类问题。,所谓训练，就是给定一组已经标定好类号的训练样本，求出判别函数中的各参数。若以 表示第一类的训练样本，以 表示第二类的训练样本，则对所有训练样本，有 以及 求解这一系列不等式，就可以解得权系数A。,这显然是线性判决函数，前面所述的线性判别函数的各种处理方法也适用于最小距离分类器。,下图是最近邻域分类器的一个例子。,当然，判别函数的形式可以取其它很多种形式，例如高次多项式等。,以两类分类问题为例：已知先验分布P(i)和观测值的类条件分布p(x|i)，i=1,2问题：对某个样本x，抉择x 1? x 2？,该决策使得在观测值x下的条件错误率P(e|x)最小。 Bayes决策理论是最优的。,以后验概率为判决函数：决策规则：,即选择P(1|x)，P(2|x)中最大值对应的类作为决策结果,后验概率P (i| x)的计算,Bayes公式： 假设已知先验概率P(i)和观测值的类条件概率密度函数p(x|i)，i=1,2。,比较大小不需要计算p(x)：,对数域中计算，变乘为加：,判别函数中与类别i无关的项，对于类别的决策没有影响，可以忽略。,Bayes最小错误率决策例解,两类细胞识别问题：正常(1)和异常(2)根据已有知识和经验，两类的先验概率为：正常(1)： P(1)=0.9异常(2)： P(2)=0.1对某一样本观察值x，通过计算或查表得到： p(x|1)=0.2， p(x|2)=0.4如何对细胞x进行分类？,利用贝叶斯公式计算两类的后验概率：,决策结果,p(1|x),p(2|x),类条件概率密度函数,后验概率,决策的错误率,条件错误率：,（平均）错误率是条件错误率的数学期望,（平均）错误率：,条件错误率P(e|x)的计算:以两类问题为例，当获得观测值x后，有两种决策可能：判定 x1 ，或者x2。条件错误率为：,Bayes最小错误率决策使得每个观测值下的条件错误率最小，因而保证了（平均）错误率最小。Bayes决策是一致最优决策。,设t为两类的分界面，则在特征向量x是一维时，t为x轴上的一点。形成两个决策区域:R1(-，t)和R2(t，+),例子,SSL,http:/,自动化学院首页教学工作教学下载课程讲义下载图象处理,课件与大作业网址：,8.3.1 形式语言的基本概念形式语言最初的设想是实现计算机的自然语言(如英语)理解，这一设想虽然至今尚未全部完成，但是，在形式语言的基础上，成功地建立起学科分支：编译器设计、自动机理论、计算机语言以及我们现在讨论的句法模式识别。这里仅就与句法模式识别有关的基本概念作一介绍。,一、 基本定义字符集是一任意的有限符号集合。在某一字符集上的句子是任一有限长度字符串，该字符串由取自于这一字符集上的字符组成。如，给定一字符集0,1，它上面的有效句子集合为：0,1,00,01,10,.。,语言定义为某一字符集上的任一句子集合，该集合不一定是有限的。给定了字符集、句子、语言的基本定义之后，仅仅明确了下述问题：字符组成句子，句子组成语言。字符究竟是按照什么规则组成句子，进而组成语言？这有待于对语法的研究。与任何一种自然语言一样，语法在形式语言中起中心作用。句法模式识别中的各个环节，都是围绕着语法进行研究的。,8.3.2 高维语法 经典形式语言中定义的语法，原是为自然语言理解设计的，因此，它只处理字符串组成的语言。字符串是一维级联的，难以表达结构信息，为了更好地描述物体的各部分空间联接关系，提出了不少高维语法。这里简单介绍图像描述语言(PDL)和树语法。,一、 图像描述语言(PDL),图像描述语言主要用于图形形状结构，其基元是有向线段，该线段有头和尾，线段之间的连接方式与矢量运算相仿。表示成图中的加、“x”乘和“*”乘。,例子：,其中“ ”表示有向线段d的反向。显然，该语法产生的语言是： 它描述的图形结构为,P：,8.4 模糊模式识别简介 在现实世界中，模糊性和随机性是两大不确定性。尽管两者有本质的区别，但是，二者之间却可以相互交叉。同一研究对象往往不仅含有模糊性而且含有随机性。例如，人们说常“明天是好天气的可能性有多大”，“他交好运的概率很小”，“他很少能较早来上班”，这里“好天气”，“好运”，“较早”都是模糊概念，而“可能性有多大”，“很小”，“很少”都是指事件发生的“概率”。对这类问题已经超出了经典概率论的范围。为此，引入模糊集合的概念。,在定义模糊子集的基础上，可以得到一系列的模糊运算、模糊等价关系、模糊相似关系、模糊数、模糊测试等，为模糊模式识别提供了基础。,从本质上来说，模式识别所要讨论的核心问题，便是如何使机器能模拟人脑的思维方法，来对客观事物进行更为有效的识别和分类。一方面现有的广为运用的统计模式识别方法与人脑进行模式识别的方法相比，其判别还很大，另一方面有待识别的客观事物又往往具有不同程度的模糊性。因此，许多学者运用模糊子集理论来解决模式识别的问题，并已经获得了可喜的应用成果。,目前，模糊模式识别的基本方法主要有：(1)基于最大隶属原则的识别(2)基于择近原则的识别(3) 基于模糊等价关系的模式分类(4) 基于模糊相似关系的模式分类,8.5 人工神经网络在模式识别中的应用8.6模式识别方法的比较 教材P324表8.5 各具特点，现在有许多组合的方法，如模糊神经网络分类器等等。,
