模式识别讲稿1.ppt

1、模 式 识 别,上海大学计算机学院 叶飞跃 2011年9月,预处理、去噪、校正、能量均衡、光补偿、归一化、测量空间 特征空间、特征向量、特征选择、分支界定算法、模拟退火、遗传算法、群算法 特征提取、主成分分析、K-L变换、降维方法、Fisher算法 相似度度量、n维空间、空间距离、模板匹配 模式分类、分类器、感知器算法、LMSE算法 几何分类、线性可分、线性不可分、势函数 概率分类、Bayes法则、最小错误决策、最小风险决策、最小最大决策 正态分布、概率密度函数、均值向量、方差矩阵、对分类的影响,聚类与分类、维数相关性、聚类准则 最近邻法、k近邻法、最大最小距离法、层次分类法、最小张树法 K-

2、均值算法、ISO-DATA算法 概念合取聚类法 模糊分类、隶属函数、择近原则、贴近度 智能模式识别、感知器模型、前馈网络、误差反向传播网络BP、RBF网络、Hopfield网络 支持向量机SVM、广义线性分类面、核函数、径向基 结构模式识别、基元提取、基元编码、模式文法（0型、I型、II型、III型） 串的识别、有限自动机、下推自动机,参考书目,沈清等，模式识别导论，国防科技大学出版社 蔡元龙，模式识别，西北电讯工程学院出版社 边肇祺，模式识别，清华大学出版社 舒宁，模式识别的理论与方法，武汉大学出版社 杨正光，模式识别，中国科技大学出版社 傅京孙，模式识别及其应用，科学出版社,参考书目,An

3、drew R. Webb Statistical Pattern Recognition Richard O. Duda, Petter E. Hart, David G. Stork Pattern Classification John Shaw-Taylor,Nell Cristicoini, Kernal Method for Pattern Analysis,讲 课 内 容,概述 统计模式识别-几何可分时 统计模式识别-概率分类法 聚类分析 结构模式识别,第一章 概 述,概念 模式识别系统 模式识别的方法 模式信息的采集 预处理,一、概 念,识别能力是人的本能 客体 具体客体： 视觉

4、-帅哥、靓妹 听觉-汽车刹车 嗅觉-臭豆腐 味觉-红烧肉 触觉-瞎子摸象 抽象客体：论点、思想、信仰,一、概 念,广义的模式识别的定义 模式是一些供模仿用的标本。模式识别就是识别出特定客体所模仿的标本。 （存在于时间和空间可观察到的事物，如我们可区分它们是否相同或相似，都可以称之为模式。模式识别，就是在于面对具体事物，将其正确的归入某一类别。）,一、概 念,狭义的定义 模式是对某感兴趣的客体的定量或结构描述，模式类是具有某些共同特征的模式的集合。模式识别是研究一种自动技术，依靠这种技术，机器将自动（或人尽量少的干涉）把待识别模式分配到各自的模式类中去,一、概 念,例：汉字“山”，按水平、垂直方

5、向投影量化为 （0，1，2，2，3）（2，1，3，1，2） 或按网格黑白点量化为 （0000000，0001000， 1001001，1001001， 1001001，1001001， 1111111）,模式（特征向量）,一、概 念,识别 ： 山 山,一、概 念,模式不是具体事物本身 模式往往表现为具有时间或空间分布的信息 信息要取样、量化 计算机中信息表示一般为向量或数组，下标对应时间或空间，但并不唯一（例如：医院化验项目和结论） 广义的时间和空间，我们泛指特征空间,一、概 念,模式识别的另一定义 模式是对某个具体客体进行观察所得到的具有时间和空间分布的信息，而把模式所属的类别或同一类中模式

6、的总体称为模式类，而给每个类命名，并用特定的符号来表示这个名字，那么模式识别就可以看成是具有时间和空间分布的信息向着符号集所作的映射。 （也有人把模式类称为模式，把具体的个别模式称为样本）,二、模式识别系统,模式识别系统由设计和实现两过程组成 设计：用一定数量的样品（也叫训练集或学习集）进行分类器的训练 实现：用设计的分类器对待识别样品进行分类决策,信息获取,预处理,特征提取和选择,分类器设计,分类决策,二、模式识别系统,1. 信息获取 （1）一维波形（曲线） （2）二维图象（曲面） （3）物理参数量、逻辑值 采样、量化、用矩阵或向量表示 2. 预处理 去噪（干扰） 加强有效信号 复原（纠偏）

7、,二、模式识别系统,3. 特征提取和选择 对原始数据进行交换，得到最能反映分类本质的特征。 测量空间：原始数据组成的空间 特征空间：模式识别进行的空间 变换：把维数较高的测量空间中表示的模式变为维数较低的特征空间中表示的模式。 特征空间中的一个模式（样本），往往可表示为一个向量(特征向量)，即看成是特征空间中的一个点。 4. 分类决策,三、模式识别方法,模式识别方法分类： 统计模式识别 结构（句法）模式识别 随着发展和与其它学科的渗透： 模糊模式识别 智能模式识别（逻辑推理法 神经网络法） 支持向量机 基于认知的模式识别,“古典”的方法,三、模式识别方法,1. 统计模式识别举例 例：19名男女

8、参加体检，测量了身高，体重，血型事后发现4人忘记了填写性别，试问他们是男是女？,三、模式识别方法,这里，待识别的模式类是：男，女 测量空间：身高，体重，血型 特征空间(2维)：身高，体重 特征向量： (170, 68), (150,48) 训练集：15名已知的样本特征（集） 目的：建立一数学模型（判别函数），对4个未知模式进行识别 为直观起见，我们绘出特征空间分布图,三、模式识别方法,希望找出一个判别函数 d(x1,x2)=0 当 d(x1,x2) 0 则 男 模式识别： 就是通过统计的方法获得最优的判别函数（常用线形的或二次的）,身高,体重,100,200,25,50,。,。,。,。,。,。

9、,。,。,。,。,。,。,。,？,？,？,？,模式样本在特征空间的分布图,判别边界,三、模式识别方法,2. 结构（句法）模式识别举例 例：识别英语句子“this boy runs quickly” - 句子用简单子句表示 - 子句用更简单子句、短语、语组、单词 - 这些基元按一定结构关系组织 - 多数采用树形结构表示,句子,名词短语,动词短语,冠词,名词,动词,副词,The The,boy girl,runs plays,quickly cheerfully,三、模式识别方法,训练时： 用已知结构句为训练样本，先识别基元和相互连接关系，再用构造文法描述该句型的文法。 识别时： 先对未知结构句进

10、行基元识别及结构分析，然后用训练得到的文法作句法分析，如果能够被某个文法规则分析出来，那该句就是相同的句型。 统计方法与句法（结构）方法在模式识别中是相互补充的。,模式识别课选题,模式识别基础理论 特征提取、降维与特征选择 统计模式识别 结构模式识别 无监督学习、聚类 人工神经网络 支持向量机、核方法 基于认知的识别方法 模型选择、贝叶斯学习 集成学习 半监督学习等,模式识别课选题,模式识别应用1-图像与视频处理 图像处理与增强 图像与视频分割 图像特征提取 基于内容的图像/视频检索 图形学与可视化 信息隐藏与数字水印,模式识别课选题,模式识别应用2-计算机视觉 视觉信息加工模型 摄像机标定、

11、三维视觉 机器人定位和视觉导航 目标描述与识别 运动目标检测与跟踪 运动目标行为分析 视频内容语义理解 场景理解,模式识别课选题,模式识别应用3-语音语言信息处理 语音识别与说话人识别 语音合成 机器翻译、口语翻译、人机对话 自然语言处理的基础研究 文本检索 自动文摘 信息抽取 文字识别与文档分析 语料库与语言知识库建设,模式识别课选题,模式识别其它应用 多模态人机交互 情感计算 医学图像与脑成像 遥感图像分析 生物特征识别 生物信息学 网络内容管理、搜索与安全 智能机器人 工业应用,模式识别课参考文献,课后邮件发给大家,四、模式信息的采集,三种类型的数据： （1）一维波形 （2）二维图象 （

12、3）物理参量 其中 （3）已经为数值表示，不需要采集。 （1）（2）需用采集装置（仪器）数值化后计算机才能处理，即非电量转换为电量，再数字化（A/D）的过程。 （我们略去非电量仪器采集的问题，主要讨论数字化过程中的几个问题。）,四、模式信息的采集,1 .傅里叶变换 任何信息的转移有三种形式 传递（transfer）：把信号（图象、声音）原封不动的传递。如透镜成像、话筒拾音。 调制（modulation）：用周期或非周期脉冲相乘的传递方法。例将模拟信号截断为离散点图象，特点是与原图形基本相似。 变换(transform)：对信号进行数学计算（变换）后传递，形成与原信号完全不同，但反变换后依然一样

13、的信号。 傅里叶变换是数学变换中的一种，也是最常用的一种变换。,四、模式信息的采集,富氏变换说明任何一个复杂波都可以分解为许多振幅、相位、周期不同的简谐波的迭加。 例：弹簧衰减震荡波形 用公式表示：,+,+,=,简谐波,四、模式信息的采集,（1）一维富氏变换（声音等） 积分实际上是求和 x(t)确定后X(f)是唯一确定的，同样X(f)确定后x(t)也唯一确定，x(t) X(f)一一对应 富氏变换有明确物理意义，X(f)为x(t)的频谱 X(f)是复函数，故可表示为,四、模式信息的采集,振幅谱 相位谱,f,A(f),f,(f),四、模式信息的采集,（2）二维富氏变换（图象处理） 同样：,四、模式

14、信息的采集,但二维富氏变换的振幅谱和相位谱不式那么直观，是一个曲面,u,v,A(u,v),四、模式信息的采集,2. 采样定理 t 等间距采样， t越小，精度越高， t 越大，越节省电路和存储 t=?,t,四、模式信息的采集,(1)从正弦波谈起（直觉及结果） s(t)= Asin(t) = Asin(2ft+) t=T/2 (或T/2) 无法恢复 s(t) tT/2 =1/2f 可以恢复s(t),t,s(t),T,A,四、模式信息的采集,(2)采样定理,f,A(f),fc fmax,四、模式信息的采集,3. 语音信号的采集 仪器：动圈式话筒、电容式话筒 人耳听到的声音通常在: 20Hz20000

15、Hz 人能够发出： 100Hz8000Hz 以模式识别的应用 语音识别时的采样 t 1/(28000) 6.25-5 60ms 声音识别 t 1/(220000) 2.5-5 25ms,四、模式信息的采集,4. 图象信息采集 仪器：扫描仪、摄像机、数码相机、遥感遥测 以扫描仪为例: 常用黑白扫描仪解析度为300 dpi 反推它的（最大）可视动态 t=1inch/300=25.4mm/300=0.0847mm fmax=1/2t 5.9/mm 也就是说，在这样的分辨率的扫描仪扫出的图象，无论如何处理，最多一毫米内只能够分辨出5条线来。,五、预处理,在特征提取（由测量空间到特征空间）前，对采集的数

16、据的干扰、噪声、能量不均匀、失真、畸变、模糊等进行弥补和校正。,五、预处理,1. (能量)归一化 由于采集仪器距离的改变造成数据能量的改变 如t1-t0=n 那么能量,能量谱,t0,t1,(t0+t1)/2,G(t) x(t),五、预处理,得到能量谱曲线，然后归一化后数据 对于二维图象由于光线照射的倾斜或射角的倾斜而造成的信号强度的衰减，也可以用类似方法解决，但窗口是二维的以半径为参数的圆。,五、预处理,2.图象的几何校正 纠正图形的几何失真。如原坐标系（x,y)，失真坐标系 （x,y），两系统之间的变换方程： x=h1(x,y) y=h2(x,y) 对于透视失真（放大、缩小、位移）变换方程是

17、线形的 x=a11x+a12y+a13 y=a21x+a22y+a23 先用三个已知坐标的点，得到线性方程的系数，再对所有的点进行校正,五、预处理,对于投影失真（变形）变换方程 先在图上找到一些已知准确坐标的点，计算出该系数矩阵，再对所有的点进行校正。,五、预处理,4.干扰与噪声的删除 （1）理想低通、带通、高通滤波器 滤波器： X(f) X(f) X(f) = H(f) X(f),H(f),f,H(f),1,fc,f,H(f),1,fc,f,H(f),1,f0,f0,1 f fc H(f)= 0 f fc,0 f f0,0 f f0 H(f)= 1 f f0,五、预处理,二维的理想低通滤波器

18、,u,v,H(u,v),D,H(u,v),D0,1 D(u,v) D0 H(u,v)= 0 其它 D(u,v)=（u2+v2)1/2 D0 为截止频率,D0,五、预处理,理想滤波器 当已知干扰源的频率时 干扰源频率于有效信号的频率不重叠 可能会影响信号截频附近的清晰（对于声音是噪声，二维图象就是对清晰度的影响） 实际使用的滤波器都要通过镶边来解决由于频率域的突变而对时间域的干扰,五、预处理,（2）n 阶巴特沃思滤波器 H(u,v)（滤波器，传递函数）是一个渐变函数。D=0时，H(u,v)=1； D=D0时，H(u,v)=0.5。N越大滤波器越陡，越接近理想滤波器。 这种滤波器滤去了大部分的噪音

19、，但减少了对图象边缘的影响。一维的n 阶巴特沃思滤波器可类推。 类似的滤器还有梯形滤波器、指数滤波器等。,u,v,H(u,v),D,H(u,v),1 0.5,D0,五、预处理,5.图象边缘的增强 使图形中景物的边缘或轮廓变的清晰，也称为图象的蜕化处理。 （1）梯度蜕化法 思路：把图象看成是各象素点灰度值组成的数据场。 灰度数据场为f(x,y), 其梯度为 g(x,y)=gradf(x,y) 其模：,五、预处理,用差分来计算偏导数 三点法 四点法 三点法 用绝对值近似,. f(x,y) . f(x+1,y) . f(x,y+1),. f(x,y) . f(x+1,y) . f(x,y+1) .

20、f(x+1,y+1),五、预处理,四点法 用绝对值近似 四点法要比三点法精确一些,五、预处理,将各点灰度梯度值视为处理后的灰度值，即令： g(x,y)=gradf(x,y) 结果如图 蜕化后原灰度平缓区域的层次被模糊了，若想得到清晰边界，同时保持内部缓变的层次，可用阈值梯度法 g(x,y)= gradf(x,y) 当gradf(x,y)T f(x,y) 其它 结果：,五、预处理,（2）拉普拉斯算子蜕化法 思路：图象的模糊可以用扩散方程来模拟。即理解为胶片记录图象时，胶片在感光或化学处理过程中，某一强感光点可按扩散方程把感光现象扩散到了临近的象素点上了。 常用的扩散方程式就是拉普拉斯方程 该方程

21、主要用于三维无源静电场的电位分布或恒温温度场的温度计算。,五、预处理,现近似把它用于二维情况其物理意义：平面场中某一点的物理量（灰度值）对时间的偏导数和该点的拉普拉斯算子成正比 设： t= 0 时 图象未模糊， 为 f(x,y,0) t=时 图象模糊，为 f(x,y,),拉普拉斯算子,五、预处理,将函数 f(x,y,t) 用泰勒级数展开,五、预处理,欲恢复的图象 t=0 此式表示，边缘清晰的图象可以用已知的模糊图象与拉普拉斯算子求得。,五、预处理,用差分法来计算拉氏算子（五点法） 代入 g(x,y),. x,y-1 . x-1,y . x,y . x+1,y . x,y+1,五、预处理,g(x

22、,y)=f(x,y) - Kf(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1) - 4 f(x,y) 令K=K 略去f(x,y,)中 g(x,y)=f(x,y) + 5Kf(x,y) -5K(1/5 )f(x,y) + f(x+1,y)+f(x-1,y)+f(x,f+1)+f(x,y-1) =(1+ 5K) f(x,y) -5K favg(x,y) =A f(x,y)-B favg(x,y) 其中：A= (1+ 5K), B= 5K favg(x,y)为 (x,y)周围五点平均灰度值,五、预处理,此式表示，图象某点得灰度值等于已知模糊图象同一点的灰度值，减去邻域象素点的平均灰度值 减去平均值相当于减去了模糊的成分，故能有突出边缘的效果 此公式与梯度蜕化法的公式类似，也为其提供了理论根据 梯度蜕化法：,五、预处理,6. 图象的区域平滑 用于文字识别的预处理 去胡椒、白点 1）Unger平滑算法 3x3 窗口（米字窗口）,xe xh xk xf xi xl xg xj x