模式识别郝旷荣Chap1(MSSB-HKR).ppt

1,模式识别PATTERN RECOGNITION,信息科学与技术学院郝矿荣E-mail:,2,教材及参考书目：模式识别 边肇祺、张学工等 清华大学出版社图像处理、分析与机器视觉 Image Processing,Analysis and Machine Vision Milan Sonka 等著 人民邮电出版社,模式识别PATTERN RECOGNITION,3,第一章 绪论第二章 贝叶斯决策理论与统计判别方法第三章 概率密度函数的估计第四章 非参数判别分类方法第五章 描述量选择及特征的组合优化第六章 非监督学习法,授课内容,4,模式识别PATTERN RECOGNITION,考核形式：大作业 30%期末考试 70%,5,第一章 绪论,1.1 模式识别和模式的概念1.2 模式的描述方法1.3 模式识别系统1.4 有关模式识别的若干问题1.5 本书内容及宗旨,6,第一章 绪论,本章要点、难点本章重点是要弄清“模式识别”的名词含义，从而弄清这门课能获得哪方面的知识，学了以后会解决哪些问题。,7,第一章 绪论,重点：1、模式识别的含义，模式的概念2、模式的描述方法3、模式识别系统的组成4、模式识别利用训练样本设计分类 器的原理，两种最基本的分类方 法的原理,8,第一章 绪论,难点：1、模式的特征向量表示与结构表示2、利用特征向量表示进行分类的基本原理3、训练和学习的概念、算法，分类器设计 是如何利用训练样本数据提供的信息的4、模式识别系统的组成，特征选择与提取 的含义和重要性5、相似性的度量方法,9,1.1 模式识别和模式的概念,模式识别的发展历程；诞生于20世纪20年代；随着计算机和人工智能的兴起，在60年代初发展成一门学科。模式识别的应用领域；所研究的理论和方法在很多科学和技术领域中得到了广泛的重视，如人工智能技术及图像处理、信号处理、计算机视觉、多媒体技术等多种领域。天气预报、卫星航空图片的解析 等,10,1.1 模式识别和模式的概念,模式识别研究内容 1、研究生物体如何感知对象，属于认知科学的范畴。2、在给定任务下，如何用计算机实现模式识别的理论和方法，通过数学家、信息学家和计算科学工作者等 3、使机器能做以前只能由人类才能做的事，具备人所具有的、对各种事物与现象进行分析、描述与判断的部分能力。,11,1.1 模式识别和模式的概念,模式识别(Pattern Recognition)实际上人类却在日常生活的每个环节，从事着模式识别的活动模式识别就是机器识别，计算机识别，或机器自动识别。如检测病理切片中是否有癌细胞，文字识别，话语识别，图像中物体识别等等。,12,1.1 模式识别和模式的概念,机器识别事物在目前也是很简单与低级的，因此机器识别事物的能力还很差。原因是人们在学习与认识事物中会总结出规律，并把这些规律性的东西抽象成“概念”。但机器目前的抽象能力是很差的。要让机器准确地把握事物的本质，弄清分辨事物的关键，从而正确辨别事物，实质上是要使人能够研究出好的方法，提出好的算法，从而构造出好的系统，使机器辨别事物的本领更强。,13,1.1 模式识别和模式的概念,模式类与模式样本：所见的具体事物，模式：而它们所属的事物类别，代表这些事物的“概念”是模式。模式：也有另一种说法把所见到的事物称为模式，模式类：而将它们的归属类别称为模式类。因此模式这个词。,14,1.1 模式识别和模式的概念,模式类与模式或者模式与样本在集合论中是子集与元素之间的关系。等价类：当用一定的度量来衡量两个样本，而找不出它们之间的差别时，它们在这种度量条件下属于同一个等价类。它们属于同一子集，是一个模式，或一个模式类。而不同的模式类之间应该是可以区分的，它们之间应有明确的界线。但对实际样本，分属不同的类别的样本却表现出相同的属性，因而无法确凿无误地对它们进行区分。,15,1.1 模式识别和模式的概念,计算是让机器辨别事物的最基本方法，原则上讲是对计算机要分析的事物与作为标准的“模板”的相似程度进行计算。因此首先通过计算要能从度量中看出不同事物之间的差异，才能分辨当前要识别的事物(称为测试样本)跟哪类事物更接近。因此找到有效地度量不同类事物的差异的方法是最关键的。,16,1.2 模式的描述方法,特征：用来决策事物类别的特点、属性就称之为物体所具有的特征。在模式识别技术中，模式就是用它们所具有的特征描述的。对一种模式与它们的样本来说，将描述它们的所有特征用一特征集表示其中O表示模式或样本名称，f 则是它们所具有的特征。特征包括定性与定量两种描述。,17,1.2 模式的描述方法,模式的描述方法：一种是对事物的属性进行度量，属于定量的表示方法。另一种则是对事务所包含的成分进行分析，称为定性的描述或结构性描述。,18,1.2 模式的描述方法,定量的表示方法用各种尺度对事物进行度量。例如对水果进行分类，水果的重量、大小、颜色、香味乃至味道等。譬如用水果的重量，近似球体直径。这两个指标按规定的先后排起来，如一只苹果重0.3斤，直径10厘米，则可表示成(0.3,1.0)。这种表示方法就称为向量表示法，该向量有两个分量，每个分量有自己特定的含义。,19,1.2 模式的描述方法,定量的表示方法一个苹果的颜色用什么方式表示？如果颜色只能用某些典型色来表示，如红、橙、蓝、绿、紫，那么，这种情况只能用代号表示，如令红为1号，橙为2号，等等。苹果如加上颜色描述，则可用一个三维向量，(0.35,10,1)t。颜色的另一种表示方法，可以用常用的RGB表示。R，G，B就是一个三维向量，如与重量、尺度汇合在一起，就是一个五维的向量。,20,1.2 模式的描述方法,定性的表示方法有一些事物用向量表示是不方便的，例如一幅景色图像中的房屋用向量描述就不一定方便，对房屋而言，它有屋顶、墙、门窗等组成，各种成分之间又有相互关系，则墙在屋顶之下，门与窗都在墙上等。这种由组成成分与相互关系表示的表示方法，最好用结构性的表示，常用的有串、树、图等。,21,1.2 模式的描述方法,在本课中，我们主要使用向量表示方法。向量的每个元素称为特征，该向量也因此称为特征向量。,22,1.2 模式的描述方法,图像、像素的定义：在计算机里分析的称为数字图像，它由排列整齐的二维网格组成，分为若干行与若干列，相当于一个二维数组，或称矩阵。我们称每个元素为像素，例如处在第三行第四列的元素的灰度值为155，则可表示成I(3,4)=155。在本门课中都是对向量进行分析的，因此在概念上要把图像也表示成向量，譬如将图像像素一列一列串起来。,23,1.2 模式的描述方法,实际上，只要记住向量的运算是建立在各个分量基础上的，例如：图像的运算也是按行列来进行，不要弄错行列。时域信号：如语音信号这种随时间变化的信号。元素之间的时间先后顺序很重要，因此可用向量的形式将它们排列起来。严格一些，对语音信号进行采样，然后将在不同时刻采样值排列起来，组成向量,24,1.3 模式识别系统(一),执行模式识别的计算机系统称为模式识别系统。设计人员按需要设计模式识别系统，而该系统被用来执行模式分类的具体任务。一般由数据获取，预处理，特征提取选择、分类决策及分类器设计五部分组成。分类器设计在训练过程中完成，利用样本进行训练，确定分类器的具体参数。而分类决策在识别过程中起作用，对待识别的样本进行分类决策。,25,1.3 模式识别系统(一),汽车车牌识别的例子。这个例子表示了一个汽车车牌识别的全过程。,26,1.3 模式识别系统(二),成功的车牌识别系统有着非常广泛的应用前景，例如公路上的自动收费站，十字路口的违章车辆监视等等。目前的车牌识别系统大都是按照以上的流程。这个流程又可以在整体上划分为两大部分车牌的提取和定位，以及字符识别部分。我们将针对每一个模块，具体说明车牌识别的过程。,27,1.3 模式识别系统(二),图1 车牌识别系统(a)原始图像，(b)特征提取结果(c)粗略定位(d)精细定位(e)确定牌照类型(f)车牌号码输出,28,1.3 模式识别系统(三),车牌识别系统车牌定位模块目的是从整幅图像中定位出车牌的精确位置。主要利用的信息是车牌部分的纹理分布、水平和竖直两个方向上的边缘。在车牌部分，边缘分布比较密集，可以利用这一点提取出候选的车牌区域，在图中用方框标出。粗略定位的结果往往不是很准，我们还可以利用颜色的连续性信息对定位的结果进行修正。之后输出的就是候选的车牌位置。上述位置中，只有一个是真正的车牌。而究竟哪一个是对的，要到字符识别阶段才能有结果。,29,1.3 模式识别系统(三),车牌识别系统车牌字符识别通过输出评价，去掉伪车牌区域，只把最正确车牌的结果作为最终结果输出出来。字符识别分两部分，其中字符分割要把车牌中的一个个字符逐一切分开，下一步的识别对每一个字符分别处理。分割的方法就是利用灰度图像往水平方向的投影。可以很好的将字符分割开来。对这个区域是不是车牌区域作个评价。如果字体太宽或太窄，说明是其它的字符。,30,1.3 模式识别系统(三),车牌识别系统车牌字符识别字符识别的方法：神经元网络，PCA，特征提取及匹配等，模板匹配和特征提取是比较常用。其中模板匹配是把样本字符与输入的待识别字符作匹配，如果两个字符很像，说明匹配成功，把这个模板的对应字符作为输出结果。而特征提取的方法是对样本和待测图像都先提取一些明显的特征，例如对“5”和“9”考虑其右上角是否封口，这样作的好处是可以用维数较低的向量来描述图像，而且这些特征都是有代表性，可以用来区分不同样本的。,31,1.3 模式识别系统(三),车牌识别系统不足之处特征提取的方法不足之处是特征需要手工设计，工作量较大。PCA(Principal Components Analysis)方法在一定程度上解决了这个问题。它可以从大量样本中训练得到每一类的特点。但是它也有不足之处，就是样本的对齐(align)问题，如果训练时没有对齐，对训练结果会有影响，而如果识别时没有对齐，也会产生错误的识别结果。,32,1.3 模式识别系统(四),信息获取计算机都只能处理某种形式的电信号，而待识别的样本大都是非电信息，例如癌细胞病理切片，语音信号，待识别文本，图像等。将以各种不同形式表现的信息通过传感器转换成电信号。如用话筒将声音信号转换成电信号，表现出电压(电流)随时间变化的复杂波形。景物信息在摄像机靶面成像并转换成二维的象素矩阵，每个像素(矩阵元素)的电信号与物体表面反射的光强或颜色信息呈现函数关系。信号获取环节主要是由不同形式的传感器构成，实现信息获取与信息在不同媒体之间的转换。,33,1.3 模式识别系统(四),预处理预处理主要是指去除所获取信息中的噪声，增强有用的信息，及必要的使信息纯化的处理过程。这个环节内容很广泛，与要解决的具体问题有关，例如，从图象中将汽车车牌的号码识别出来，就需要先将车牌从图像中找出来，再对车牌进行划分，将每个数字分别划分开。做到这一步以后，才能对每个数字进行识别。以上工作都应该在预处理阶段完成。,34,1.3 模式识别系统(四),特征选择和提取测量空间：由所使用的量测仪器或传感器获取的原始数据组成的空间。因此特征的选择与提取模块的功能是：对所获取的信息实现从测量空间到特征空间的转换。特征提取模块将原始量测数据转换成有效方式表示的信息，从而使分类器能根据这些信息决定样本的类别。前面说过待识别的样本及模式都是用特征进行描述的，识别与训练都是在特征空间中进行的。,35,1.3 模式识别系统(四),特征选择和提取-举例印刷体数字大多通过扫描仪输入，或从图像中获取。这样一来，一个数字往往用一个NM的数组表示。如果N5，M7，则一个数字就用57共35个网格是黑是白来表示。如令是黑为“1”，是白为“0”，那么一个数字就可用35维的二进制向量表示。这就是典型的特征向量表示法。,36,1.3 模式识别系统(五),分类决策模式识别系统工作有两种方式，即训练方式和分类决策方式。训练方式是指在已确定的特征空间中，对作为训练样本的量测数据进行特征选择与提取，得到其在特征空间的分布，依据这些分布决定分类器具体参数。,37,1.3 模式识别系统(五),分类决策-分类决策方式。由事物的属性得到它的特征向量，在特征空间中表示成一个点，称为数据点。在特征空间的分布中往往表现出同类事物的特征向量聚集在一起。因此待识别的事物，如果它的特征向量出现在某一类事物经常出现或可能出现的区域，该事物就被识别为该类事物。在特征空间中哪个区域是某类事物典型所在区域需要用数学式子划定，满足这种数学式子与否就成为分类决策的依据。确定这些数学式子就是分类器设计的任务。,38,1.3 模式识别系统(五),本课程将着重围绕模式识别的基本原理及分类器设计的基本问题进行讨论。在许多应用领域中模式识别并不一定作为独立的环节存在。常见的独立工作的模式识别系统有语音识别系统，文字识别系统等等。在汽车车牌号码识别例子中我们也可以看到多个模式识别结合在一起的现象。这个例子中包括了车牌区域的识别，车牌类型的识别以及车牌号码的识别，是一环接一环的，前一项识别也可看成是后一项识别的预处理。每个识别过程都可用这个框图表示，但各自所用的具体方法不同。,39,1.4 有关模式识别的若干问题,一、学习确定分类决策的具体数学公式是通过分类器设计这个过程确定的，在模式识别学科中一般把这个过程称为训练与学习的过程。但是在模式识别系统中，一般说来人工神经元网络的学习能力比传统的模式识别方法要强。但目前看来，在人类尚无法了解自身的智力活动过程的现阶段，人类还不具备设计有高度智力的机器的能力。,40,1.4 有关模式识别的若干问题,图中两类训练样本的分布体现出近似圆形的分布。因此如能把这两个圆形区域确定下来，将它们的边界用某种数学式子近似。只要条件允许就要使用较简单的方法是一条基本原则。决定使用什么类型的分类函数往往是人为决定的。但数学式子中的参数则往往通过学习来确定，这一点与人们学习新事物的方式很相似。,41,1.4 有关模式识别的若干问题,模式识别中学习与训练：从训练样本提供的数据中找出某种数学式子的最优解，这个最优解使分类器得到一组参数，按这种参数设计的分类器使人们设计的某种准则达到极值。,42,1.4 有关模式识别的若干问题,二、模式的紧致性分类器设计难易程度与模式在特征空间的分布方式有密切关系，例如图1.4(a)、(b)与(c)分别表示了两类在空间分布的三种状况。,43,1.4 有关模式识别的若干问题,二、模式的紧致性例如如果A由111，101，110，011组成，而A由其余四个点组成，则只需要一个平面就可将它们分开。若要分开A=111,001,100,010与=000,011,101,110这样两个集合，则需要三个平面。,44,1.4 有关模式识别的若干问题,二、模式的紧致性,45,1.4 有关模式识别的若干问题,紧致集定义，它具有下列性质：(1)临界点的数量与总的点数相比很少；(2)集合中任意两个内点可以用光滑线连接，在 该连线上的点也属于这个集合；(3)每个内点都有一个足够大的邻域，在该领域 中只包含同一集合中的点。许多问题在测量空间时不满足紧致性。但如果可分意味着可以通过一种变换，使它们在相应的特征空间中界线分明，也就是具有了紧致性。模式识别系统设计的任务就是要寻找这样一种变换，即选择一种特征空间，使不同类别的样本能正确地分开。,46,1.4 有关模式识别的若干问题,三、相似性度量,47,1.4 有关模式识别的若干问题,三、相似性度量在特征空间中用特征向量描述样本的属性，就是把相似性度量用距度离量表示。在找到合适的特征空间情况下，同类样本应具有聚类性，或紧致性好。统计模式识别各种方法实际上都是直接或间接以距离度量为基础的。常用的距离度量是D维特征空间中的欧氏距离其中Xk,Xj表示两个样本的特征向量。,48,1.4 有关模式识别的若干问题,三、相似性度量除此之外还有其它形式的距离度量，如,49,1.4 有关模式识别的若干问题,欧氏距离是最常用的，它表示两个向量的差向量的模。这种计算在衡量几何距离时最为合适。但在模式识别中特征向量的各个分量的含义往往是不同的，就像苹果的例子中，两者的单位都不一样，因此使用欧氏距离并不合理。各个分量的分布范围在数量级上比较相近为好。分量差的绝对值总和表示距离往往是对欧氏距离的简化，将平方计算改为了绝对值计算。第三种方法主要反映两个特征向量的夹角，而没有反映特征向量幅值的差别。这些不同的相似度度量都有各自的优缺点，使用时要注意。,50,本章小节,1、模式识别也就是机器自动进行判断，如对语音自动识别其词，断语乃至句子。2、为了机器能自动识别事物(书中用样本这个词)。要对样本进行度量或成分描述，表示成特征向量形式，便于样本间直接进行相似性比较来确定其类别，或通过特征空间划分来判别测试样本的类别。3、模式识别系统包括以下几个环节信息获取、预处理、特征提取与选择、分类器设计、分类决策。,51,本章小节,4、机器自动识别与分类的设计是依据范例(称为训练样本)提供的信息，分类的方法可以归纳为两大类，一类是与不同类范例的相似性(常称模板匹配)，另一种则是通过训练样本集确定不同类样本在特征空间中的分布。可以拟作划分势力范围，从而按测试样本落入哪个势力范围来确定其类别。这种过程常叫做训练学习过程，最常用的是通过错误的自学习过程。5、样本间相似性度量是模式识别中常用的计算内容，不同的相似性度量要考虑其合理性和计算简单性等。,52,本章小节,