《数字图象处理.pptx》由会员分享，可在线阅读，更多相关《数字图象处理.pptx（143页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、11 12 2.1 .1 概概 述述第1页/共143页2数据获数据获取取判决分判决分类类待识图待识图像像数据处数据处理理结果结果输出输出图图1 12 2.1.1 图像识别系统框图图像识别系统框图图像识别系图像识别系统统第2页/共143页3 统计法（统计法（Statistical ApproachStatistical Approach）句法法（句法法（Syntactic ApproachSyntactic Approach）模糊法（模糊法（Fuzzy ApproachFuzzy Approach）识别方法识别方法第3页/共143页412.2 统计图像识别 第4页/共143页5统计模式表示统计模
2、式表示 特征向量的第特征向量的第i i个分量就是模式的第个分量就是模式的第i i个特征的测量值个特征的测量值 模式的特征向量模式的特征向量第5页/共143页6统计模式表示统计模式表示 图图1 12 2.2.2特征空间划分示意图特征空间划分示意图 第6页/共143页7统计模式识别系统统计模式识别系统 图图1 12 2.3.3统计模式识别系统结构图统计模式识别系统结构图 第7页/共143页8图像模式的特图像模式的特征征 图像模式本身自然含有的图像模式本身自然含有的 如图像的象素灰度级、目标的边缘轮廓及纹理区域等。如图像的象素灰度级、目标的边缘轮廓及纹理区域等。通过某种测量或变换操作人工地得出的通过
3、某种测量或变换操作人工地得出的 如图像象素灰度级分布的直方图，图像的各种变换（如傅里叶如图像象素灰度级分布的直方图，图像的各种变换（如傅里叶变换、余弦变换、沃什变换、哈达码变换等正交变换）系数特征等变换、余弦变换、沃什变换、哈达码变换等正交变换）系数特征等 图像模式的图像模式的特征特征是图像模式场明显可分的本原的特性或属性是图像模式场明显可分的本原的特性或属性第8页/共143页9特征的分布状特征的分布状态态 距离距离向量向量x x与特征集之间与特征集之间两向量之间两向量之间第9页/共143页10特征的分布状特征的分布状态态 距离距离类内距离类内距离类间距离类间距离 特征选择的准则特征选择的准则
4、1 1：类内距离小，类间距离大：类内距离小，类间距离大第10页/共143页11特征的分布状特征的分布状态态 似然比似然比散度散度条件概率条件概率条件概率条件概率第11页/共143页12特征的分布状特征的分布状态态 散度散度将两类互相将两类互相区分的平均区分的平均量度量度散度散度 特征选择的准则特征选择的准则2 2：最大散度最大散度 第12页/共143页13特征的分布状特征的分布状态态 熵熵 特征选择的准则特征选择的准则3 3：总体熵最小总体熵最小 第第i i类的概率密度类的概率密度类内异样性的总体熵类内异样性的总体熵向量的各分量统计独立向量的各分量统计独立第第i i类的总体熵类的总体熵第13页
5、/共143页14特征抽取特征抽取 特征抽取就是对图像模式进行物理测量或变换，得到一组反映其特性特征抽取就是对图像模式进行物理测量或变换，得到一组反映其特性的数字值。特征抽取方法与实际问题是紧密联系的的数字值。特征抽取方法与实际问题是紧密联系的。特特征征抽抽取取有有两两种种类类型型：一一种种是是对对识识别别对对象象的的各各个个重重要要特特性性都都有有充充分分的的理理解解，然然后后把把这这种种特特性性转转换换为为数数字字。与与此此相相反反，另另一一种种并并不不需需要要充充分了解识别对象的各个重要特性，而是根据某些原理进行特征抽取。分了解识别对象的各个重要特性，而是根据某些原理进行特征抽取。要要得得
6、到到某某类类模模式式的的足足够够的的特特征征，那那么么来来自自该该模模式式类类的的样样本本数数就就不不能太少。能太少。特特征征抽抽取取应应对对识识别别对对象象的的各各种种特特性性加加以以考考虑虑，但但不不等等于于说说特特征征空空间间维维数数越越高高越越好好，识识别别精精度度并并不不随随着着特特征征数数量量的的增增多多而而提提高高。在在地地球球资资源源卫卫星星ERS-1ERS-1可可以以取取得得十十二二个个波波段段的的遥遥感感数数据据，但但从从识识别别精精度度来来看看，三三个或四个波段的组合效果最好。个或四个波段的组合效果最好。第14页/共143页15特征选择特征选择 特征选择特征选择是在特征抽
7、取以后，从中挑选出有代表性的或有效的是在特征抽取以后，从中挑选出有代表性的或有效的成份来，使得分类判决的问题能够更有效地进行。成份来，使得分类判决的问题能够更有效地进行。特征选择特征选择可以在前述距离准则，最大散度准则或最小熵准则的可以在前述距离准则，最大散度准则或最小熵准则的指导下进行。指导下进行。第15页/共143页16特征选择特征选择 特征选择就是决定变换矩阵特征选择就是决定变换矩阵 A Amm mm（m m 0为有助于收敛的校正系数，或称学习率学习率 J J 的梯度的梯度第26页/共143页27线性分类器线性分类器 奖惩算法奖惩算法令令第27页/共143页28线性分类器线性分类器 奖惩
8、算法奖惩算法有有即即第28页/共143页29ANN分类器 第29页/共143页30ANN简介 生物神经元功能特性生物神经元功能特性第30页/共143页31ANN简介 生物神经元功能特性生物神经元功能特性第31页/共143页32ANN简介 细胞体：由细胞核、细胞质和细胞膜组成；轴突：即神经纤维，相当于细胞的输出电缆，其端部的神经未梢为信号输出端子，用于传出神经冲动；树突：相当于输入端，接受来自四面八方的传入神经冲动；突触：细胞与细胞之间通过轴突和树突相互连接，接口就称为突触。每个细胞有100010000个突触。突触有两种类型：兴奋型和抑制型膜电位：细胞膜内外之间的电位差，约20 100mv，膜外
9、为正，膜内为负；结构可塑性：由于突触的信息传递性是可变的，随着神经冲动传递方式的变化，其传递作用可以增强，也可以减弱，即细胞之间的连接是柔性的。生物神经元功能特性生物神经元功能特性第32页/共143页33ANN简介 时空整合功能对不同时间通过同一突触传入的神经冲动有整合功能，对同一时间通过不同突触传入的神经冲动有整合功能。兴奋与抑制状态兴奋当传入冲动的时空整合结果，使膜电位升高，超过动作电位的阈值（约40mv）时，细胞进入兴奋状态，产生神经冲动，由轴突输出；抑制当传入冲动的时空整合结果，使膜电位低于动作电位的阈值（约40mv）时，细胞进入抑制状态，无神经冲动输出。生物神经元功能特性生物神经元功
10、能特性第33页/共143页34ANN简介 生物神经元功能特性生物神经元功能特性脉冲与电位转换突触界面有脉冲/电位信号转换功能。由轴突传递的电脉冲为等幅、恒宽、编码的离散脉冲信号，而细胞膜电位变化为连续的电位信号。在突触接口处进行“数/模”转换是通过神经介质以量子化学方式实现的变换过程，即 电脉冲神经化学物质膜电位突触延时和不应期不应期相邻两次冲动之间需要一个时间间隔，在此期间对激励不响应，不能传递神经冲动。学习、遗忘和疲劳由于结构可塑性，突触的传递作用有增强、减弱、饱和，所以细胞有学习、遗忘和疲劳效应。第34页/共143页35ANN简介 人工神经元模型人工神经元模型第35页/共143页36AN
11、N简介 非线性特性非线性特性第36页/共143页37ANN简介 非线性特性非线性特性第37页/共143页38ANN简介 非线性特性非线性特性第38页/共143页39ANN简介 非线性特性非线性特性第39页/共143页40ANN简介 人工神经网络人工神经网络人工神经网络（简称为ANN）由大量神经元互连而成，是现代神经科学研究成果的基础上提出来的，反映人脑功能的基本特性，但不是人脑真实写照，只是它的某种抽象、简化和模拟。第40页/共143页41ANN简介 ANNANN信息处理能力信息处理能力ANN的信息处理功能由下列因素决定网络单元（人工神经元）的输入输出特性网络的拓朴结构连接权的大小（突触联系强
12、度）第41页/共143页42ANN简介 ANNANN信息处理能力信息处理能力大规模并行分布信息处理（现行计算机只能串行离散符号处理）分布式信息存贮：信息存贮体现在神经元互连的分布上，并以并行分布式处理(现行计算机计算与存贮是相互独立的)高度的鲁棒性和容错性，善于联想、概括、类比和推广，任何局部损伤不会影响整体结果。很强的自学习能力，系统可在学习过程中不断完善，具有创新特点。具有集体运算能力。第42页/共143页43ANN简介 ANNANN的学习的学习 人工神经网络的学习模拟人脑的学习方法。人脑在学习过程中究竟哪些部分发生了变化，这是神经系统学习的实质问题。人脑学习学说（两大流派）化学学说认为神
13、经系统把学习后的结果记录在某些生物分子（如蛋白质、核酸、神经递质）上，就象遗传信息记录在DNA上一样。突触修正学说认为学习过程中神经元之间的突触联系发生了变化。人工神经网络按突触修正学说来模拟人脑的学习过程。第43页/共143页44ANN简介 ANNANN的学习准则的学习准则误差修正型学习根据系统的期望输出与实际输出之间的误差作为连接权调整的参考，最后减小这种误差。随机型学习结合随机过程、概率和能量的概念来调整网络的连接权，从而使网络的能量达到最小。赫布型学习如果两个神经元同时兴奋，则它们之间的突触联系应该得以加强。竞争型学习是一种无教师学习。最简单的学习形式是“胜者为王”。第44页/共143
14、页45前向网络分类器 结构结构第45页/共143页46前向网络分类器 工作过程工作过程隐节点隐节点i i的加权输入的加权输入隐节点隐节点i i的输出的输出输出节点输出节点j j的输出的输出输出节点输出节点j j的加权输入的加权输入第46页/共143页47前向网络分类器 学习过程学习过程当输入向量为当输入向量为A Ak k时，期望的输出向量为时，期望的输出向量为C Ck k在模式识别中，期望输出向量实际上就是人工对输入模式的判识结果在模式识别中，期望输出向量实际上就是人工对输入模式的判识结果训练样本对训练样本对第47页/共143页48前向网络分类器 学习过程学习过程全局代价函数全局代价函数单个样
15、本对时的代价函数单个样本对时的代价函数输出节点一般化误差输出节点一般化误差第48页/共143页49前向网络分类器 学习过程学习过程隐节点一般化误差隐节点一般化误差第49页/共143页50前向网络分类器 学习过程学习过程梯度下降规则梯度下降规则:调节现有连接权调节现有连接权w wij ij和和v vhihi减少代价函数减少代价函数E Ek k第50页/共143页51前向网络分类器 学习过程学习过程第51页/共143页52前向网络分类器 学习过程学习过程令令则则第52页/共143页53前向网络分类器 学习算法学习算法第53页/共143页54前向网络分类器 学习算法学习算法第54页/共143页55前
16、向网络分类器 学习算法学习算法第55页/共143页5611.3 11.3 句法图像识别句法图像识别 第56页/共143页57概 述 句法法句法法又称为又称为结构法结构法（Structural ApproachStructural Approach）结构法的识别过程不仅能够把模式分类，而且还可以描述结构法的识别过程不仅能够把模式分类，而且还可以描述模式的结构形态，而统计法只有模式分类的能力模式的结构形态，而统计法只有模式分类的能力 句法法特别适合用来解决图片识别（句法法特别适合用来解决图片识别（Picture RecognitionPicture Recognition）和景物分析（和景物分析（
17、Scene AnalysisScene Analysis）问题问题 结构法以形式语言理论为基础结构法以形式语言理论为基础第57页/共143页58基本思想一个复杂的模式可以由一些简单的模式递归地描述。换言之，对于每个一个复杂的模式可以由一些简单的模式递归地描述。换言之，对于每个复杂的模式，可以用一些较简单的子模式来描述，而每一个比较简单的复杂的模式，可以用一些较简单的子模式来描述，而每一个比较简单的子模式再用一些更为简单的子模式来描述，子模式再用一些更为简单的子模式来描述，最后用一些最简单的识，最后用一些最简单的识别起来比模式本身容易得多的称为模式基元（别起来比模式本身容易得多的称为模式基元（P
18、attern PrimitivePattern Primitive）的子模的子模式来表示式来表示 第58页/共143页59基本思想图12.9 图片P图12.10 图片P的多级结构描述第59页/共143页60基本思想图12.11 英文句子的导出树图12.10 图片P的多级结构描述第60页/共143页61基本思想 自然语言自然语言：单词由语法规则连接起来构成短语，短语最后再根据：单词由语法规则连接起来构成短语，短语最后再根据语法规则构成一个完整的句子。语法规则构成一个完整的句子。模式的多级结构描述模式的多级结构描述：模式基元按一定的规则构成子模式，子模式：模式基元按一定的规则构成子模式，子模式再按
19、照一定的规则构成一个完整的模式。再按照一定的规则构成一个完整的模式。在句法模式识别中，模式是用一种类似于自然语言的在句法模式识别中，模式是用一种类似于自然语言的“模式描述模式描述语言语言”来描述的。由基元组成模式所遵循的那些规则则称为来描述的。由基元组成模式所遵循的那些规则则称为模式文模式文法法或简称文法。或简称文法。模式的多级结构描述与日常所用的句子分析有明显的相似之处模式的多级结构描述与日常所用的句子分析有明显的相似之处第61页/共143页62系统结构图图1 12 2.1212句法模式识别系统结构图句法模式识别系统结构图 第62页/共143页63系统结构 基元选择（基元选择（Primiti
20、ve SelectionPrimitive Selection）是对所考虑的模式集选取那些是对所考虑的模式集选取那些能够通过一定的结构关系紧凑而方便地对模式结构加以描述，并能够通过一定的结构关系紧凑而方便地对模式结构加以描述，并且容易用统计方法加以抽取和识别的基本元素作为模式基元。且容易用统计方法加以抽取和识别的基本元素作为模式基元。基元抽取（基元抽取（Primitive ExtractionPrimitive Extraction）由两部分组成：模式分割和基由两部分组成：模式分割和基元及关系识别元及关系识别 文法推断（文法推断（Grammar InferenceGrammar Inferen
21、ce）是根据相当数量的已知结构信是根据相当数量的已知结构信息的模式样本，推论出分类的文法规则。然后，再用训练样本对息的模式样本，推论出分类的文法规则。然后，再用训练样本对获得的分类文法进行检测，并改进文法规则。获得的分类文法进行检测，并改进文法规则。句法分析（句法分析（Syntax AnalysisSyntax Analysis）是的任务是判断输入模式是否是的任务是判断输入模式是否属于给定的文法描述的模式类。属于给定的文法描述的模式类。第63页/共143页64模式基元在句法模式识别中，输入模式用一个句子（字符串）来描述。句在句法模式识别中，输入模式用一个句子（字符串）来描述。句子的基本单位就是
22、文法中的终止符，而终止符对应模式的基元。子的基本单位就是文法中的终止符，而终止符对应模式的基元。基元是一个模式的基本成份。所以在用句法法处理模式识别问题基元是一个模式的基本成份。所以在用句法法处理模式识别问题时，首先要选好基元、抽取基元和识别基元时，首先要选好基元、抽取基元和识别基元。基元选择注意点基元选择注意点 基元应该是基本的模式元素，能够通过一定的结构关系（如连基元应该是基本的模式元素，能够通过一定的结构关系（如连接关系、位置关系等）紧凑地、方便地对模式加了描述接关系、位置关系等）紧凑地、方便地对模式加了描述 基元用现有的非句法方法（如统计方法）加以抽取、识别。基元用现有的非句法方法（如
23、统计方法）加以抽取、识别。第64页/共143页65模式基元 着眼于边界（轮廓）和骨架的基元，如着眼于边界（轮廓）和骨架的基元，如FreemanFreeman链码链码 着眼于区域的基元，如帕夫里迪斯多边形着眼于区域的基元，如帕夫里迪斯多边形例如手写汉字识别采用笔划作为基元比较方便对于一般的图像、图形模式基元有两种类型对于一般的图像、图形模式基元有两种类型第65页/共143页66程序文法一个一个程序文法程序文法G Gp p是一个五元组是一个五元组G Gp p=（V VN N，V VT T，J J，P P，S S）其中其中V VN N、V VT T和和P P分别是非终止符、终止符和产生式的有限集，分
24、别是非终止符、终止符和产生式的有限集，S S是起始符，是起始符，J J是产生式的标号集。是产生式的标号集。P P中产生式的形式中产生式的形式:（1 1）r r 是产生式的号是产生式的号（2 2）是产生式的核是产生式的核（3 3）S S(u u)表示使用产生式表示使用产生式(r r)成功后的去向范围成功后的去向范围（4 4）F F(u u)表示使用产生式表示使用产生式(r r)失败后的去向范围失败后的去向范围第66页/共143页67程序文法程程序序文文法法的的特特点点是是：在在一一个个导导出出式式中中，对对中中间间句句型型使使用用了了一一个个产产生生式式以后，下一次再用什么产生式就要受到限制。以
25、后，下一次再用什么产生式就要受到限制。推导规则推导规则 必须从标号为必须从标号为(1)(1)的产生式开始；的产生式开始；目目前前的的链链 中中包包含含子子链链，如如果果可可以以用用产产生生式式 来来重重写写子子链链，而而下下一一个个产产生生式式从从中中S S(u u)选选取取；如如果果目目前前的的链链 中中不不包包含含子子链链，则则不能用产生式不能用产生式 (即链即链 不变不变)，而下一个产生式从，而下一个产生式从F F(u u)中选取中选取 如果可用的转移区包含如果可用的转移区包含，则导出过程停止。则导出过程停止。第67页/共143页68程序文法例12.4 第68页/共143页69属性文法属
26、属性性文文法法 就就是是一一些些属属性性加加给给模模式式基基元元和和关关系系，从从而而把把语语义义信信息息包包括括到到模模式式描描述述中中去去。在在属属性性文文法法中中，每每一一个个模模式式基基元元都都有有一一个个符符号号名名称称和和一一个个属性向量，而每一条产生式都有一条语义或属性规则与之相联系。属性向量，而每一条产生式都有一条语义或属性规则与之相联系。一个非属性文法可以变换成一个句法复杂性较低的属性文法。这样一一个非属性文法可以变换成一个句法复杂性较低的属性文法。这样一种句法种句法语义折衷应能使一个模式识别系统具备恰当地调节句法和语义语义折衷应能使一个模式识别系统具备恰当地调节句法和语义的
27、相对复杂性以获得计算效果的灵活性。此时，句法规则往往十分简单，的相对复杂性以获得计算效果的灵活性。此时，句法规则往往十分简单，而语义信息或属性规则在一定程度上被用作一种控制策略（或语义约束）而语义信息或属性规则在一定程度上被用作一种控制策略（或语义约束）来选择和解释适用于这种分析的句法规则。来选择和解释适用于这种分析的句法规则。第69页/共143页70文法推断文法推断文法推断：通过句子的训练样本集合来学习：通过句子的训练样本集合来学习文法文法模式类模式类模式文法模式文法训练样本集训练样本集第70页/共143页71文法推断文法文法文法推断算法训练样本集训练样本集图图1 12 2.1.14 4 文
28、法推断示意图文法推断示意图第71页/共143页72文法推断写出终止符集写出终止符集V VT T；对于每一个句子逐个写出能生成此句子的文法；对于每一个句子逐个写出能生成此句子的文法；构成文法；构成文法；合并重复的产生式和非终止符，其合并重复的产生式和非终止符，其规则规则为：为：如果如果G G中任何产生式出现多次，则保留一个，去除其它；中任何产生式出现多次，则保留一个，去除其它；找找出出这这样样一一对对变变量量（即即非非终终止止符符），如如果果在在G G中中到到处处以以其其中中一一个个替换另一个，就会使某些产生式多次出现，进行代换并用替换另一个，就会使某些产生式多次出现，进行代换并用进行简化进行简
29、化找出这样一对变量（找出这样一对变量（A A，a a），），如果在如果在G G中补充产生式，并在某些中补充产生式，并在某些有选择的情况下以有选择的情况下以A A代替代替a a，将导致产生式的数目由于消去出现多次的将导致产生式的数目由于消去出现多次的产生式而减少。产生式而减少。由训练样本集由训练样本集R R推断文法推断文法G G的方法的方法第72页/共143页73句法分析模式类模式类模式文法模式文法未知模式由句子未知模式由句子 x x 表示，其识别问题实质上就由表示，其识别问题实质上就由“未知模式是否属于未知模式是否属于句法分析句法分析自动机识别自动机识别第73页/共143页74句法分析已知一句
30、子（字符串）x和上下文无关文法G，构成一个三角形，并以一个自身相容的导出树将三角形内部填满。将三角形内部填满的方法：自上而下的剖析 自下而上的剖析成功否则图12.15 句法剖析三角形第74页/共143页75句法分析给定给定x x和上下文无关文法和上下文无关文法G G，自上而下的剖析从自上而下的剖析从S S开始，开始，应用重写最左非终止符的产生式，推导得句型应用重写最左非终止符的产生式，推导得句型y y自上而下的剖析自上而下的剖析直到串直到串x x，并找到并找到x x的最左推导。因为上下文无关文法中，的最左推导。因为上下文无关文法中，因此应用产生式时，句型中的符号数不可能被减少，故而可废弃所有长
31、因此应用产生式时，句型中的符号数不可能被减少，故而可废弃所有长度超过度超过x x的句型，需要研究的只是长度等于或小于的句型，需要研究的只是长度等于或小于x x的句型的有限集合。的句型的有限集合。第75页/共143页76句法分析自下而上的剖析从串自下而上的剖析从串x x本身开始，应用反向的产生式，试图将本身开始，应用反向的产生式，试图将x x归结归结到起始符到起始符S S。自下而上的剖析从自下而上的剖析从x x到到S S，以以x x的最右推导反推出产生式序的最右推导反推出产生式序列。列。给定和上下文无关文法给定和上下文无关文法G G，从从x x着手构成中的一些符号串，这些符号着手构成中的一些符号
32、串，这些符号串是应用可能出现在串是应用可能出现在x x的推导过程中的产生式的反向推演而得到的。的推导过程中的产生式的反向推演而得到的。但在推导过程中不知道哪些序列的串可能是正确的，因此必须同时研但在推导过程中不知道哪些序列的串可能是正确的，因此必须同时研究所有可能的序列。究所有可能的序列。自下而上的剖析自下而上的剖析第76页/共143页77句法分析CKYCKY剖析算法剖析算法 采用树结构的剖析算法本质上是穷举试探，它对任意上下采用树结构的剖析算法本质上是穷举试探，它对任意上下文无关文法所需的剖析时间可能按字符串长度作指数增加文无关文法所需的剖析时间可能按字符串长度作指数增加 CKYCKY剖析算
33、法的时间则正比于输入串长度的三次方剖析算法的时间则正比于输入串长度的三次方 CKY CKY算法要求文法是一个上下文无关文法，其产生式必须算法要求文法是一个上下文无关文法，其产生式必须是乔姆斯基标准形是乔姆斯基标准形 第77页/共143页78句法分析CKYCKY剖析算法剖析算法图12.16 三角形剖析表第78页/共143页79句法分析CKYCKY剖析算法剖析算法第79页/共143页80句法分析CKYCKY剖析算法剖析算法例12.7 设有上下文无关文法第80页/共143页81句法分析CKYCKY剖析算法剖析算法第81页/共143页82句法分析CKYCKY剖析算法剖析算法第82页/共143页83句法
34、分析CKYCKY剖析算法剖析算法第83页/共143页84句法分析CKYCKY剖析算法剖析算法第84页/共143页85自动机识别基本方法基本方法：对于文法：对于文法 G Gi i 构造一个相应的自动机构造一个相应的自动机 MMi i，使自动机使自动机 MMi i 接受的语言等于文法接受的语言等于文法 G Gi i 产生的语言产生的语言T T(MMi i)=)=L L(G Gi i)将字符串将字符串x x作为自动机的输入链，如果作为自动机的输入链，如果x x被自动机被自动机接受否则第85页/共143页86自动机识别有限状态自动机有限状态自动机图12.18第86页/共143页87自动机识别有限状态自
35、动机有限状态自动机图12.19有限状态自动机示意图第87页/共143页88自动机识别有限状态自动机有限状态自动机第88页/共143页89自动机识别有限状态自动机有限状态自动机图12.20 有限状态自动机状态图例12.8第89页/共143页90自动机识别有限状态自动机有限状态自动机由有限状态文法构造对应的自动机由有限状态文法构造对应的自动机第90页/共143页91自动机识别有限状态自动机有限状态自动机例12.9第91页/共143页92自动机识别下推自动机下推自动机第92页/共143页93自动机识别下推自动机下推自动机图图1 12 2.2121下推自动机示意图下推自动机示意图下推存贮有限控制a b
36、 a 输入带z 栈顶第93页/共143页94自动机识别下推自动机下推自动机由终止状态接受的语言由终止状态接受的语言对于来自对于来自+的输入串的输入串x x，MM从从q q0 0开始，下推表顶上的符号为开始，下推表顶上的符号为z z0 0，按照映射按照映射的序列，扫描完整个符号串的序列，扫描完整个符号串x x，若机器停止在终态，则串若机器停止在终态，则串x x为为MM所接受。所接受。由下推表变空接受的语言由下推表变空接受的语言对于来自对于来自+的输入串的输入串x x，MM从从q q0 0开始，下推表顶上的符号为开始，下推表顶上的符号为z z0 0，按照映按照映射的序列，扫描完整个符号串射的序列，
37、扫描完整个符号串x x，若下推表变空，则串若下推表变空，则串x x为为MM所接受所接受第94页/共143页95自动机识别下推自动机下推自动机由上下文无关文法构造对应的自动机由上下文无关文法构造对应的自动机第95页/共143页96自动机识别下推自动机下推自动机例12.10第96页/共143页97有噪声、畸变模式的句法识别识别方法 用相似性和误差校正剖析用相似性和误差校正剖析 采用随机语言与随机自动机采用随机语言与随机自动机 运用模糊技术运用模糊技术第97页/共143页98相似性测度 符号串符号串转换转换代换误差转换代换误差转换T TS S删除误差转换删除误差转换T TD D插入误差转换插入误差转
38、换T TI I第98页/共143页99相似性测度 符号串符号串LevenshteinLevenshtein距离距离定义为从定义为从x x导出导出y y所需的最小转换数目所需的最小转换数目J J是从导出过程所用到的转换序列是从导出过程所用到的转换序列分别表示分别表示J J中的代换、删除和插入转换的数目中的代换、删除和插入转换的数目加权加权LevenshteinLevenshtein距离距离第99页/共143页100相似性测度 例例 12.11 x x=cbabdbbcbabdbb，y y=cbbabbdbcbbabbdb，求求第100页/共143页101误差校正剖析 则称则称x x是是y y的最
39、小距离校正的最小距离校正L L(G G)是一个给定的语言（描述一类模式），是一个给定的语言（描述一类模式），y y是一个待剖析的是一个待剖析的句子（待识别模式），最小距离误差校正剖析的实质就是在句子（待识别模式），最小距离误差校正剖析的实质就是在L L(G G)中寻找一个句子中寻找一个句子x x L L(G G)，使其满足下述最小距离准则使其满足下述最小距离准则第101页/共143页102误差校正剖析 设设y y是一个句子（一个模式），是一个句子（一个模式），L L(G G)是一类语言（一类模式）是一类语言（一类模式）y y与与L L(G G)之间的距离之间的距离就是就是y y与其在与其在L
40、L(G G)中的最小距离校正之间的距离中的最小距离校正之间的距离k k=1=1第102页/共143页103误差校正剖析 最小距离分类准则最小距离分类准则模式模式描述文法描述文法对于未知模式对于未知模式y y，计算计算如果如果第103页/共143页104随机语言 V VN N和和V VT T分别是非终止符和终止符的有限集分别是非终止符和终止符的有限集 S S V VN N是起始符，是起始符，P Ps s是随机产生式的有限集，每个产生式的形式是随机产生式的有限集，每个产生式的形式第104页/共143页105随机语言 以概率以概率第105页/共143页106随机语言 如果对于输入串如果对于输入串x
41、x有有n nx x条推导路径，其生成概率分别为条推导路径，其生成概率分别为生成生成x x的概率为的概率为随机文法随机文法G Gs s产生的随机语言产生的随机语言第106页/共143页107随机语言 因为一个随机文法的产生式除了指派的概率以外，实际上和非随机的文法一样，故由一个随机文法所产生的语言的集合和以非随机的方式产生的相同 第107页/共143页108随机自动机 有限集有限集D D，是赋予是赋予 映射的一组概率值，设当前状态为映射的一组概率值，设当前状态为q q，当前输入符号为当前输入符号为a a，它的下一状态为它的下一状态为 q q1 1,q q1 1,q qn n (q q,a a)=
42、)=q q1 1,q q1 1,q qn n 如果如果MMs s是正确的随机有限状态自动机是正确的随机有限状态自动机第108页/共143页109随机自动机 MMs s从从q q0 0开始，扫描完串开始，扫描完串x x以后停在终止状态以后停在终止状态F F，则接受串则接受串x x如果如果MMs s有有n nx x条不同的状态转换序列来接受输入串条不同的状态转换序列来接受输入串x x，其接受概率分别为其接受概率分别为MMs s接受的语言接受的语言则则MMs s识别输入串识别输入串x x的总概率的总概率第109页/共143页110随机自动机 例例图12.22 随机有限状态自动机状态图第110页/共1
43、43页111随机自动机 例例MMs s接受接受x x的概率为的概率为p p(x x)，MMs s拒绝拒绝x x的概率的概率1-1-p p(x x)当输入串为当输入串为x x=aabbaabb时，时，MMs s检查检查x x的过程的过程第111页/共143页1121 12 2.4.4 模糊图像识别模糊图像识别第112页/共143页113基本思想 模糊性是人类思维和客观事物普遍具有的属性之一。世界模糊性 思维模糊性 第113页/共143页114基本思想 一方面，在客观事物之间存在着中间过渡，存在着一方面，在客观事物之间存在着中间过渡，存在着“亦此亦彼亦此亦彼”现象即现象即模糊现象。模糊现象。另一方
44、面，尽管事物的表现或内在属性有其确定性，但是由于观测手段另一方面，尽管事物的表现或内在属性有其确定性，但是由于观测手段和科研水平所限，在科学发展的一定阶段上，人们对这些属性的认识和科研水平所限，在科学发展的一定阶段上，人们对这些属性的认识带有模糊性。带有模糊性。人类通常运用模糊的词语来交流思想，互通信息，然后进行推理分析，人类通常运用模糊的词语来交流思想，互通信息，然后进行推理分析，综合评判，最后作出分类决策。综合评判，最后作出分类决策。第114页/共143页115基本思想 人脑的重要特点之一就是能对模糊事物进行识别和判断。人们的行为活人脑的重要特点之一就是能对模糊事物进行识别和判断。人们的行
45、为活动通常是从客观事物获取模糊的映象、表象以及模概念的情况下展开和动通常是从客观事物获取模糊的映象、表象以及模概念的情况下展开和作出反应的。人脑对于客观事物的认识，往往只要通过一些模糊信息的作出反应的。人脑对于客观事物的认识，往往只要通过一些模糊信息的综合便可获得足够精确的结论。综合便可获得足够精确的结论。获取模糊轮廓映象联想与回 忆模糊推理和判断人脑认知过程第115页/共143页116基本思想 例一、找人，特征：高个子、大胡子第116页/共143页117基本思想 没有笔划的汉字没有笔划的汉字例二、读书认字象第117页/共143页118模糊集合 正是针对自然环境和人类认知过程中存在的模糊性现象
46、,美国控制论专家、加利福利亚大学教授LAZadeh于1965年在“Information and Control”发表了开创性论文“Fuzzy Sets”,第一次提出了模糊集的概念，这标志着数学的应用范围从精确现象扩大到模糊现象的领域,从而建立了模糊信息处理的新课题。第118页/共143页119模糊集合 U U上的普通集合上的普通集合A A 可以用特征函数来表示可以用特征函数来表示U U上的模糊集合上的模糊集合A A可以用隶属函数来表示可以用隶属函数来表示第119页/共143页120模糊集合 例例：设 ，=“奇数”，=1，3，5，7，9如果用特征函数表示，则第120页/共143页121模糊集合
47、 例例：设 A表示“靠近5的自然数”，则有第121页/共143页122模糊集合 例例年青年青年老年老第122页/共143页123模糊集合的表示 序偶法序偶法 ZadehZadeh法法U U有限集有限集U U无限集无限集 向量法向量法第123页/共143页124模糊集合的运算 U U上的模糊幂集上的模糊幂集第124页/共143页125隶属函数的确定 模糊统计法模糊统计法 二元对比后总体排序法二元对比后总体排序法 经验权重法经验权重法 模糊插值法模糊插值法 用常用的模糊分布去逼近给定模糊集合的隶属函数用常用的模糊分布去逼近给定模糊集合的隶属函数 第125页/共143页126隶属函数的确定模糊统计法
48、模糊统计法包含包含2727的区间有的区间有101101个个包含包含3434的区间有的区间有2626个个引用张南纶和蔡训武同志的做法。他们在武汉建材学院选择了引用张南纶和蔡训武同志的做法。他们在武汉建材学院选择了129129位合适人位合适人选，请他们独自认真考虑了选，请他们独自认真考虑了“青年人青年人”的含义之后，报出他们认为青年人最的含义之后，报出他们认为青年人最适宜的年龄区间，如适宜的年龄区间，如1818，2525，2020，3030，1414，2525，等，共等，共129129个区间。个区间。年龄年龄u u0 0的人对于的人对于“青年人青年人”这个模糊集合的隶属度为这个模糊集合的隶属度为第
49、126页/共143页127模糊识别原则最大隶属原则最大隶属原则第127页/共143页128模糊识别原则最大隶属原则最大隶属原则第128页/共143页129模糊识别原则最大隶属原则最大隶属原则例：例：癌细胞识别癌细胞识别第129页/共143页130模糊识别原则最大隶属原则最大隶属原则第130页/共143页131模糊识别原则最大隶属原则最大隶属原则第131页/共143页132模糊识别原则最大隶属原则最大隶属原则第132页/共143页133模糊识别原则最大关联隶属原则最大关联隶属原则第133页/共143页134模糊识别原则最大关联隶属原则最大关联隶属原则第134页/共143页135模糊识别原则最大关
50、联隶属原则最大关联隶属原则第135页/共143页136模糊识别原则最大关联隶属原则最大关联隶属原则第136页/共143页137模糊识别原则最大关联隶属原则最大关联隶属原则第137页/共143页138模糊识别原则择近原则择近原则第138页/共143页139模糊识别原则择近原则择近原则例：例：颜色的同色异谱程度的模糊判别颜色的同色异谱程度的模糊判别同色异谱：同色异谱：两个样本在同一光源下颜色相匹配，而光谱反向率分布不同第139页/共143页140模糊识别原则择近原则择近原则上述形状贴近度f(A,B)可用于颜色同色异谱程度的模糊判别。第140页/共143页141模糊识别原则择近原则择近原则第141页