《模式识别绪论》PPT课件.ppt

模式识别 2012年2月22日 自动化学院 袁立 1 出勤：10% 实验：4学时，两个实验，10 考试：80，开卷 课程要求 * 2 教材：张学工等编， 模式识别 清华大学出版社， 2010年，第3版 参考书： Ruchard O.Duda等 模式分类 （Pattern Classification） 机械工业出版社，2004年 课程要求 * 3 1.模式与模式识别的概念 2.模式识别的主要方法 3.监督模式识别与非监督模式识 别 4.模式识别系统的典型构成 5.模式识别系统应用举例 第一章第一章 绪论绪论 4 一、模式识别 1.1 模式与模式识别的概念 直观，无所不在 儿童认数字：数字符号的识别 读书看报：文字识别 汽车、火车，狗叫、人语：声音识别 人群中寻找一个人：根据面像、形体或其他特征进行识别 人类的模式识别能力是极其平常的， 时刻在完成某种模式识 别的任务。 随着社会活动以及生产科研的发展，需要识别的对象种类越 来越多，内容越来越复杂和深入，要求越来越高。 为了减轻工作强度，希望计算机代替人来完成识别工作；有 些场合环境恶劣、存在危险或人类不能接近，需要借助机器 、运用分析算法进行识别。 * 5 第一章第一章 绪论绪论 * 6 1. 模式识别(Pattern Recognition): 使计算机模仿人的感知能力，从感知数据中提取信息（判别物体和 行为）的过程。 模式识别作为一门学科，是研究用机器完成自动识别事物的工作； 研究内容：使计算机做以前只能由人类才能做的事，具备人所具有 的、对各种事物或现象进行分析、描述与判断的部分能力。 模式识别学科形成于5060年代，与众多学科有联系，尤其与人工智 能和图像处理关系密切。 1.1 模式与模式识别的概念 2. 模式与模式类： l 模式：需要识别且可测量的对象的描述。 这些对象与实际的应用有关，如： 字符识别的模式每个字符图像 人脸识别的模式每幅人脸图像 l 模式类：当用一定的度量来衡量两个模式，而找不出它们之间的差别时， 它们在这种度量条件下属于同一等价类，就说它们是同一模式类。 例如：数字识别有10个类别，每个数字就是一个类。 不同模式类之间是可以区分的，应有明确界限。 * 7 1.1 模式与模式识别的概念 3. 识别最基本的方法：计算 计算机根据已研制的识别算法，把输入的未知模式划入正确类 别中，从而实现自动分类。识别算法中的关键环节就是要对待 识别事物与标准 “模板”的相似程度进行计算。 特征向量表示法：将对事物进行度量的指标排成向量的形式。 一维表示 X1=1.5 X2=3 二维表示 X1=(x1,x2)T=(1,2)T X2=(x1,x2)T=(2,1)T 三维表示 X1=(x1,x2, x3)T=(1,1,0)T X2=(x1,x2 , x3)T=(1,0,1)T 苹果（重量，直径，颜色 ） 4. 模式描述方法 图像的向量表示方法： 在计算机里分析的称为数字图像，它由排列整齐的二维网格组成，分 为若干行与若干列，相当于一个二维数组，或称矩阵。我们称每个元 素为像素。 左图为57的数字图像； 一个数字就用57共35个网格是黑是白来表示； 如令是黑为“1”，是白为“0”，那么一个数字就可用 35维的二进制向量表示。这就是典型的特征向量表示 法 1.1 模式与模式识别的概念 结构表示法：由事物的组成成分与相互关系表示 在右侧的图中八个基元分别表示 0，1，2，3，4，5，6，7，八个方向 和基元线段长度。 则右侧样本可以表示为 X1=006666 这种方法将在句法模式识别中用到。 二、模式识别简史 1929年 G. Tauschek发明阅读机 ，能够阅读0-9的数字。 30年代 Fisher提出统计分类理论，奠定了统计模式识别的基础。统计模式 识别是模式识别的主要理论。 50年代 Noam Chemsky 提出形式语言理论傅京荪 提出句法结构模式识 别。 60年代 L.A.Zadeh提出了模糊集理论，模糊模式识别方法得以发展和应用 。 80年代以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复 活，并在模式识别得到较广泛的应用。 90年代小样本学习理论，支持向量机受到了很大的重视。 2000年，流形学习（manifold learning）：流形学习就是从高维采样数据 中恢复低维流形结构，即找到高维空间中的低维流形，并求出相应的嵌入 映射，以实现维数约简或者数据可视化. 2005年，稀疏表示（sparse representation）：近年来有关生理学的研究 成果表明：人类的视觉系统具有对图像的稀疏表示特性,神经元对于输入图 像的激活机制具有高度的稀疏性. 1.1 模式与模式识别的概念 三.关于模式识别的国内、国际学术组织 1973年 IEEE发起了第一次关于模式识别的国际会议“ICPR”，成立了 国际模式识别协会-“IAPR”，每2年召开一次国际学术会议。 1977年 IEEE的计算机学会成立了模式分析与机器智能（PAMI）委员会 ，每2年召开一次模式识别与图象处理学术会议。 国内组织：中国自动化学会：模式识别与机器智能(PRMI)专业委员会 ，1981年成立，IAPR成员组织；人工智能与模式识别专业委员会；中 国人工智能学会 国内学术机构：中科院模式识别国家重点实验室，中科院计算所，微 软研究院，清华大学等。 * 10 1.1 模式与模式识别的概念 模式识别学科位置 模式识别：计算机科学与电子工程交叉学科 中国：“控制科学与工程”一级学科 二级学科：控制理论与控制工程、模式识别与智能系统、系统工程 等 西方：没有自动控制系 自动控制：电子工程系、机械工程系 模式识别：电子工程系、计算机科学系 四、模式识别的应用 多媒体数据检索（文档、图像、视频、音乐检索 ） 字符识别（印刷体字符的识别；手写体字符的识别（脱机/联机 ），信函分拣、支票查对、自动排板、稿件输入等） 医疗诊断（心电图，脑电图，染色体，癌细胞识别，疾病诊断 等） 工程（产品缺陷检测、自动导航系统、污染分析） 军事（航空摄像分析、雷达和声纳信号检测和分类、自动目标 识别等） 安全监控（基于生物特征的身份识别、视频监控、交通监控、 音视频监听） 1.1 模式与模式识别的概念 现有生物特征识别类型 * 12 1.1 模式与模式识别的概念 1.2 模式识别的主要方法 l 基于知识的方法 (Knowledge-based) AI、专家系统(Expert Systems) 句法（结构）模式识别 (Syntax PR or Structural PR) （基于结构性描述） l基于数据的方法 (Data-based) 统计模式识别方法（Statistical PR）（基于特征向量表 示方法） 人工神经网络(ANN) 支持向量机(SVM) 统计模式识别方法：在确定了描述样本所采用的特征之后 ，收集一定数量的已知样本，用这些样本作为训练集来训 练一定的模式识别机器，使之在训练后能够对未知样本进 行分类。这是基于数据的机器学习中研究最多的一个方向 。 统计模式识别用函数表示： Y = F(X) X的定义域取自特征集 Y的值域为类别的标号集 F是模式识别的判别方法 有监督模式识别分类（classification） 给出若干已知答案的样本（训练样本 training samples ） 由机器从这些样本中进行学习（训练 training/learning ） 学习的目的在于从这些样本中总结规律，使之能够对新 的样本进行判断 无监督模式识别聚类（clustering） 所面对的只有未知答案的样本 由机器从这些样本中进行学习（自学习） 学习的目的在于从这些样本中发现规律，这种规律应该 是某种固有的关系，或者依据这种规律对对象的分类有 某种功用 1.3 监督模式识别与非监督模式识别 1. 模式识别系统：执行模式识别的计算机系统。 1.4 模式识别系统的典型构成 2. 模式识别系统组成：信息获取与预处理，特征提取与选择、 分类或聚类、后处理等四个部分。 第一章第一章 绪论绪论 1.4 模式识别系统的典型构成 1.4 模式识别系统的典型构成 1.4 模式识别系统的典型构成 监督模式识别系统组成：数据获取，预处理，特征提取选择、 分类器设计以及分类决策五部分。 训练过程：对作为训练样 本的量测数据进行特征选 择与提取，得到它们在特 征空间的分布，依据这些 分布决定分类器的具体参 数，也就是设计分类器的 过程。 识别过程：分类决策的过 程，则是在特征空间中用 统计方法把被识别对象归 为某一类别。 3. 监督模式识别系统构成及功能 （1）信息获取：用不同形式的传感器构成，实现信息获取与信 息在不同媒体之间的转换，非电信号转换成电信号。 用话筒将声音信号转换成电信号，表现出电压(电流)随时 间变化的复杂波形。 景物信息在摄像机靶面成像并转换成二维的象素矩阵，每 个像素(矩阵元素)的电信号与物体表面反射的光强或颜色信 息呈现函数关系 一般输入对象的信息有三种类型： 二维图象，如文字、指纹、地图、照片等 一维波形，如脑电图、心电图、机械震动波形等 物理参量和逻辑值，如疾病诊断中病人体温，各种化 验数据；或对症状有无描述，如疼与不疼（0/1） 1.4 模式识别系统的典型构成 （2）预处理 去除所获获取信息中的噪声，增强有用的信息，及一切必要的使信 息纯纯化的处处理过过程。 预处预处 理这这个环节环节 内容很广泛，与要解决的具体问题问题 有关，例如 ，从图图象中将汽车车车车 牌的号码识别码识别 出来，就需要先将车车牌从图图 像中找出来，再对车对车 牌进进行划分，将每个数字分别别划分开。做 到这这一步以后，才能对对每个数字进进行识别识别 。以上工作都应该应该 在 预处预处 理阶阶段完成。 （3）特征选择和提取 p功能：对对所获获取的信息实现实现 从测测量空间间到特征空间间的转换转换 。 将所将所获获获获取的原始量取的原始量测测测测数据数据转换转换转换转换 成能反映事物本成能反映事物本质质质质，并将其最有效分，并将其最有效分 类类类类的特征表示的特征表示。 输输入：原始的量测测数据(经过经过 必要的预处预处 理)，例如由声波变变 换换成的电电信号，表现为电压电现为电压电 流幅度随时间时间 的变变化，二维图维图 像每个像素所具有的灰度值值等。 输出：将原始量测测数据转换转换 成有效方式表示的信息，从而使分 类类器能根据这这些信息决定样样本的类别类别 。 1.4 模式识别系统的典型构成 l特征选择和提取:选择什么样的方法来描述事物，从而可以 有效、牢靠地把事物正确地区分开。 如令是黑为“1”，是白为“0”，那么一个数字就可用35维 的二进制向量表示。这就是典型的特征向量表示法。 另一种方法则是将数字用笔划表示，也就是将它分成一横加上一斜杠表 示。这种表示方法属于结构表示法范畴。这种方法没有前一种方法的缺 点，但提取这种结构信息也不是一件容易方便的事。 缺点：这种表示与网格的尺寸有关，与字的笔划粗细有关， 更主要的是字在网格中的不同位置与转向有关。这个字在网 格中略为偏一点，其特征向量表示就会有很大的不一样。这 就说明了这种表示的稳定性差。 例：印刷体数字大多通过扫描仪输入，或从图像中获取。这样，一个数字往往用 一个NM的数组表示。如果N5，M7，则一个数字就用57共35个网格是黑是 白来表示。 1.4 模式识别系统的典型构成 （4）分类器设计与分类决策 分类类器设计设计 ：将该该特征空间间划分成由各类类占据的子空间间 ，确定相应应的决策分界和判决规则规则 ，使按此类类判决规则规则 分类时类时 ，错误错误 率最低。把这这些判决规则规则 建成标标准库库。 分类类决策：分类类器在分界形式及其具体参数都确定后，用 相应应的决策分界对对待分类样类样 本进进行分类类决策的过过程。 1.4 模式识别系统的典型构成 1.5 模式识别系统实例 19名男女同学进行体检，测量了身高和体重，但事后发现 其中有4人忘记填写性别，试问（在最小错误的条件下） 这4人是男是女？体检数值如下： * 24 待识别的模式：性别（男或女） 测量的特征：身高和体重 训练样本：15名已知性别的样本特征 模式识别系统实例（一） 目标：希望借助于训练样本的特征建立判别函数（即数学 模型） 由训练样本得到的特征空间分布图： * 25 从图中训练样本的分 布情况，找出男、女 两类特征各自的聚类 特点，从而求取一个 判别函数（直线或曲 线）。 只要给出待分类的模 式特征的数值，看它 在特征平面上落在判 别函数的哪一侧，就 可以判别是男还是女 了。 1.5 模式识别系统实例 * 26 鱼类罐头加工厂：将传送带上的鱼按品种自动分类，即 把不同的鱼分开。 鱼的分类：鲑鱼（salmon）, 鲈鱼（sea bass） 模式识别系统实例（二） 数据采集：用光学感知手段，定时 拍摄鱼的数字图像，将其传入计算 机。 预处理：增强图像中感兴趣的部分 ，抑制图像中的噪声，将不同的鱼 、鱼与背景分离开来。 特征提取（feature extraction）： 待分对象鲑鱼和鲈鱼确实存在一些 差异，比如长度、宽度、光泽和形 状等。利用类别之间的这些差异来 分类。 1.5 模式识别系统实例 * 27 模式识别系统实例（二） 特征提取（feature extraction）： 待分对象鲑鱼和鲈鱼确实存在一些差异，比如长度、宽度 、光泽和形状等。利用类别之间的这些差异来分类。 特征：从模式中提取的、对分类有用的特征。 特征选择是模式识别的核心问题之一。 分类判别（classification）单一特征 先验知识：鲈鱼一般比鲑鱼长。因此可以选择长度为分类 特征；长度l超过预定阈值l*时判定为鲈鱼，否则判定为鲑鱼 。 如何获得长度阈值l*呢？（预定） 1.5 模式识别系统实例 * 28 模式识别系统实例（二） 利用特征直方图获得长度阈值l* 直方图表明：无论怎样确定长度阈值l*，都不能将两类鱼 截然分开，分类错误比较严重。通常，单一特征不足以很 好分类。 1.5 模式识别系统实例 * 29 模式识别系统实例（二） 尝试利用其他特征：鱼的光泽度，用x表示。 1.5 模式识别系统实例 * 30 模式识别系统实例（二） 利用多个特征进行分类 形成特征空间：以每个特征为坐标轴形成的空间。特征的 个数，就是特征空间的维数。 特征向量：特征空间中的一个点。X=(x1,x2)T表示一条鱼， x1代表长度，x2代表光泽度。 分类器设计：要找到一个判定边界 两类问题判定线 判定线把特征空间分 为两个区域，识别时 特征向量落在那个区 域就判定为相应类别 。其总分类错误比单 一特征分类器好一些 ，但仍存在一些错误 的分类。 1.5 模式识别系统实例 * 31 模式识别系统实例（二） 分类器的推广能力：即分类器对未知模式的正确分类的能力 复杂的分类算法导致复杂的判定边界。判决曲线被过分调谐 到这些训练样本上，虽然所有训练样本都被正确分类，但其推 广能力却很差。 比如：图中的?新模式更像鲑鱼，却被分到鲈鱼类了。 1.5 模式识别系统实例 * 32 模式识别系统实例（二） 简化分类器设计方案 分类器设计无需上面那样复杂，即便对训练样本不能完美识 别，只要对新模式有足够的推广能力就可以接受。 分类器如何自动产生比较简单的判决边界，使其比上面的直 线和复杂边界更优秀？如何预测分类器对新模式的推广能力？ 这些都是模式识别要研究的问题。 1.5 模式识别系统实例 模式识别系统举例（三）：汽车车牌识别 应用领域：自动收费站，十字路口的违章车辆监视等。 主要步骤：（1）图像获取 （2）车牌的提取和定位 （3）字符识别部分 1.5 模式识别系统实例 1.5 模式识别系统实例 * 35 1.5 模式识别系统实例 车牌定位模块 目的：从整幅图像中定位出车牌的精确位置。 利用的信息：是车牌部分的纹理分布，主要利用的是水平和竖 直两个方向上的边缘。在车牌部分，边缘分布比较密集，可以 利用这一点提取出候选的车牌区域，在图中用方框标出。 粗略定位的结果往往不是很准，我们还可以利用颜色的连续性 信息对定位的结果进行修正。 之后输出的就是候选的车牌位置，这些位置中，只有一个是真 正的车牌。而究竟哪一个是对的，要到字符识别阶段才能有结 果。 * 36 1.5 模式识别系统实例 字符识别模块 目的：输入包括每一个候选车牌区域，而通过它们的输出评价 ，来把不合适的伪车牌区域去掉，只把最正确车牌的结果作为 最终结果输出出来。 第一部分：字符分割，要把车牌中的一个个字符逐一切分开， 这样才能在下一步的识别中对每一个字符分别处理。 分割方法：利用灰度图像往水平方向的投影。在有数字或字符 的部分，这个投影值应该比较大，而在字符之间的间隙处，投 影的累计值就几乎为零了。 确定是否车牌：如果划分结果比较合理，划分出的每个字符的 宽度都差不多，那么说明这个区域比较像车牌。如果字体太宽 ，说明是其它的字符。 * 37 1.5 模式识别系统实例 模板匹配：是把样本字符与输入的待识别字符作匹配，如 果两个字符很像(在某种距离度量下距离很小)，说明匹配成 功，把这个模板的对应字符作为输出结果。 特征提取：是对样本和待测图像都先提取一些明显的特征 ，例如对“5”和“9”考虑其右上角是否封口，这样作的好处 是可以用维数较低的向量来描述图像，而且这些特征都是有 代表性，可以用来区分不同样本的。 * 38 第二部分：字符识别，方法很多：神经元网络，PCA，特 征提取及匹配等，模板匹配和特征提取是比较常用的方法 。 1.5 模式识别系统实例 字符识别模块的训练和识 别过程 * 39 车牌定位模块的训练 和识别 1.5 模式识别系统实例 * 40 其它应用举例： 人脸检测与跟踪 人脸识别 视频监控 异常行为分析 智能交通 1.5 模式识别系统实例 智能视觉物联网（Smart Visual Internet of Things，SVIOT） 物联网是指通过各种信息传感设备，如射频识别（RFID）、红外感应 器、药理传感器、声音传感器、图像视频传感器等，实时采集其声、 光、热、电、力学、化学、生物、位置等各种需要的信息，与互联网 结合形成的一个巨大网络。其目的是实现物与物、物与人，所有的物 品与网络的连接，方便识别、管理和控制。 “智能视觉物联网”涉及物联网的视觉感知部分，利用各类图像获取传感 器，包括监控摄像机、手机、数码相机，获取人、车、物图像或视频 ，并采用智能分析技术对视觉信息进行处理，为后续利用提供支撑。 智能视觉物联网它是未来物联网中重要组成部分，对视觉感知范围内 的人、车或其他物件等目标赋以“身份”标签并识别目标的实际“身份”， 并利用网络化特点对大范围中的目标标签进行关联，有效地分析目标 标签物体的实时状态，感知各类异常事件，就异常事件的发生向相关 受体提出自动警示。 * 41 1.5 模式识别系统实例 * 42 1.学习 l 机器的学习过程： 使用一批包括各类别的训练样本 勾画出各种事物在特征空间分布的规律性 确定使用分类的具体数学公式及其参数 1.6 模式识别的若干问题 第一章第一章 绪论绪论 分类器设计：求优化解的过程 l 模式识别中的学习与训练是从训练样本提供的数据中找出某种数学 式子的最优解，这个最优解使分类器得到一组参数，按这种参数设 计的分类器使人们设计的某种准则达到极值。 l 分类器参数的选择或学习过程得到的结果取决于设计者选择什么样 的准则函数。不同准则函数的最优解对应不同的学习结果，得到性 能不同的分类器。 例：两类训练样本分布 图中两类训练样本的分布体现出近似圆形的分布。因 此如能把这两个圆形区域确定下来，将它们的边界用 某种数学式子近似，那么落在某一个圆形内的样本就 可以用这种数学式子来判断。 当不一定非要精确地表达不同类样本分布地聚集区时 。用一条直线(线性方程)也许可以达到同样的目的。 满足直线的方程是一个线性方程，写成 f(x1,x2)=ax1+bx2+c=0，而不在该直线上的点则用 f(x1,x2)是否大于零或小于零来分辨。 1.31.3模式识别的若干问题模式识别的若干问题 一般来说，决定使用什么样的分类函数往往是人为决定的。对一 个实际分类问题，快速计算、快速分类是十分重要的。 两类样本在二维特征空间中有