第一章绪论

Size: px

Start display at page:

Download "第一章绪论"

谷仲
5 years ago
Views:

1 第一章绪论中科大自动化系郑志刚

2 问题求助 : 相近颜色的布料图像的区分 1. 两种米色布料, 颜色相近但有差异, 花纹一样 ; 2. 两种灰色布料, 也是颜色相近, 花纹一样 ; 用 CCD 采集布料的图像, 如何区分上面的各种布料? 不知道有什么好的算法或方法可以区分彼此, 请大虾不吝赐教

3 什么是模式? 广义地说, 存在于时间和空间中可观察的物体, 如果我们可以区别它们是否相同或是否相似, 都可以称之为模式模式所指的不是事物本身, 而是从事物获得的信息, 因此, 模式往往表现为具有时间和空间分布的信息模式的直观特性 : 可观察性可区分性相似性

4 什么是模式 (Pattern)?

5 模式识别的概念模式识别直观, 无所不在, 人以类聚, 物以群分周围物体的认知 : 桌子椅子人的识别 : 张三李四声音的辨别 : 汽车火车, 狗叫人语气味的分辨 : 炸带鱼红烧肉人和动物的模式识别能力是极其平常的, 但对计算机来说却是非常困难的

6 模式识别的例子 (1) 例 1: 医生给一个病人看病 ( 模式识别的完整过程 ) 测量病人的体温和血压, 化验血沉, 询问临床表现 ; 通过综合分析, 抓住主要病症 ; 医生运用自己的知识, 根据主要病症, 作出正确的诊断模式识别技术中, 经常使用的术语有 : 样本模式特征类型等为了便于理解, 可以进一步分析上述例子

7 样本 : 医院里的众多患者, 每个患者都是一个样本单一样本 : 请医生给出诊断的某一个患者, 就是众多患者中的一个样本样本的测量值 : 患者的体温血压等测量值模式 : 样本的各测量值的综合模式样本 : 具有某种模式的样本模式采集 : 获取某样本的各测量值的过程样本特征 : 患者的主要病症特征提取特征选择 : 模式样本各测量值经过综合分析找出主要病症分类判决 : 医生运用自己的知识作出诊断判决准则判决规则 : 医生的知识判决结果 : 把患者区别成某种疾病的患者 ( 也就是把样本 ( 患者 ) 区别为相应类型 ( 疾病 )

8 模式识别的例子 (2) 例 2: 选取做家具的松木 ( 松木桦木 ) 观察 : 颜色花纹亮度密度 ( 样本测量值 ), 得到样本模式综合分析 : 提取选择主要特征根据主要区别 : 区分各单一样本 ( 松木桦木 )

9 模式识别的研究手段 : 利用计算机对物理对象进行分类, 在错误概率最小的条件下, 使识别的结果尽量与客观物体相符合 Y = F(X) 目的 X 的定义域取自特征集 Y 的值域为类别的标号集 F 是模式识别的判别方法

10 模式识别简史 (1) 1929 年 G. Tauschek 发明阅读机, 能够阅读 0-9 的数字 30 年代 Fisher 提出统计分类理论, 奠定了统计模式识别的基础因此, 在 60~70 年代, 统计模式识别发展很快, 但由于被识别的模式愈来愈复杂, 特征也愈多, 就出现维数灾难但由于计算机运算速度的迅猛发展, 这个问题得到一定克服统计模式识别仍是模式识别的主要理论 50 年代 Noam Chemsky 提出形式语言理论傅京荪提出句法结构模式识别

11 模式识别简史 (2) 60 年代 L.A.Zadeh 提出了模糊集理论, 模糊模式识别方法得以发展和应用 80 年代以 Hopfield 网 BP 网为代表的神经网络模型导致人工神经元网络复活, 并在模式识别得到较广泛的应用 90 年代小样本学习理论, 支持向量机也受到了很大的重视

12 关于模式识别的国内国际学术组织 1973 年 IEEE 发起了第一次关于模式识别的国际会议 ICPR, 成立了国际模式识别协会 --- IAPR, 每 2 年召开一次国际学术会议 1977 年 IEEE 的计算机学会成立了模式分析与机器智能 (PAMI) 委员会, 每 2 年召开一次模式识别与图象处理学术会议国内的组织有电子学会, 通信学会, 自动化协会, 中文信息学会.

13 模式识别的应用 1. 字符识别 : 包括印刷体字符的识别 ; 手写体字符的识别 ( 脱机 ), 各种 OCR 设备例如信函分拣文件处理卡片输入支票查对自动排板期刊阅读稿件输入 ; 在线手写字符的识别 ( 联机 ), 各种书写输入板 2. 医疗诊断 : 心电图, 脑电图, 染色体, 癌细胞识别, 疾病诊断, 例如关幼波肝炎专家系统 3. 遥感 : 资源卫星照片, 气象卫星照片处理, 数字化地球, 图象分辨率可以达到 1 米

14 4. 指纹识别脸形识别 5. 检测污染分析, 大气, 水源, 环境监测 6. 自动检测 : 产品质量自动检测 7. 语声识别, 机器翻译, 电话号码自动查询, 侦听, 机器故障判断 8. 军事应用

15 一些工业应用生物特征识别人脸识别车号识别 Robocup 小型组足球机器人视觉系统

16 生物特征识别定义通过计算机与光学声学生物传感器和生物统计学原理等手段密切结合, 利用人体固有的生理特性,( 如指纹人脸虹膜等 ) 和行为特征 ( 如笔迹声音步态等 ) 来进行个人身份的鉴定一些应用指纹识别人脸识别虹膜识别步态识别

17 Fingerprint matching techniques Minutiae-based Correlation-based Ridge Feature-based

18 Minutiae types

19 Minutiae-based fingerprint verification system

20 Minutiae Extraction Orientation field estimation Fingerprint area location Ridge extraction Thinning Minutia extraction

21 Minutia extraction algorithm

22 指纹识别原图 22

23 指纹识别分割后 23

24 指纹识别图像增强 24

25 指纹识别二值化 25

26 指纹识别细化 26

27 指纹识别细节点, 即模式识别的特征 27

29 Motivation for fingerprint enhancement Minutia extracted from a good quality input image Minutia extracted from a poor quality input image

30 Fingerprint regions Well defined region Recoverable corrupted region Unrecoverable corrupted region

31 指纹识别系统软件界面 31

32 实验室示例 - 人脸识别系统 32

33 列车车号识别系统

34 列车车号识别系统输入图像中值滤波图像二值化计算连通域输出结果字符识别字符分割车号定位软件流程图 34

35 列车车号识别系统 35

36 列车车号识别系统 36

37 Robocup 小型组足球机器人系统总体框图摄像头视觉处理机器人 5 机器人 4 机器人 3 机器人 1 机器人 2 决策程序

38 摄像机鱼眼模型

39 比赛视频 39

40 模式空间特征空间和类型空间物理上可以察觉到的世界 : 在客观世界里存在一些物体和事件, 它们都可被适当的和足够多的函数来描述, 也就是说它们在物理上是可以被测量的, 他们的可测数据的集合就称为物理上觉察到的世界显然, 这些可测数据, 或者说这个世界的维数是无限多的样本 : 在物理上可以觉察到的世界中, 所选择出的某些物体和事件

41 模式空间特征空间和类型空间模式采集 : 由物理上可觉察到的世界到模式空间所经历的过程模式空间的维数 : 与选择的样本和测量方法有关, 也与特定应用有关维数很大, 但是是一个有限值在模式空间里, 每个模式样本都是一个点, 点的位置由该模式在各维上的测量值确定

42 模式空间特征空间和类型空间特征提取和特征选择 : 从模式空间到特征空间所需的变换和选择判决规则 : 由某些知识和经验可以确定的分类准则根据适当的判决规则, 把特征空间里的样本区分成不同的类型, 从而把特征空间塑造成了类型空间决策面 : 不同类型之间的分界面

43 模式识别过程

44 模式识别方法模式识别系统的目标 : 在特征空间和解释空间之间找到一种映射关系, 这种映射也称之为假说特征空间 : 从模式得到的对分类有用的度量属性或基元构成的空间解释空间 : 将 c 个类别表示为其中为所属类别的集合, 称为解释空间

45 假说的两种获得方法监督学习概念驱动或归纳假说 : 在特征空间中找到一个与解释空间的结构相对应的假说在给定模式下假定一个解决方案, 任何在训练集中接近目标的假说也都必须在未知的样本上得到近似的结果依靠已知所属类别的的训练样本集, 按它们特征向量的分布来确定假说 ( 通常为一个判别函数 ), 只有在判别函数确定之后才能用它对未知的模式进行分类 ; 对分类的模式要有足够的先验知识, 通常需要采集足够数量的具有典型性的样本进行训练

46 假说的两种获得方法 ( 续 ) 非监督学习数据驱动或演绎假说 : 在解释空间中找到一个与特征空间的结构相对应的假说这种方法试图找到一种只以特征空间中的相似关系为基础的有效假说在没有先验知识的情况下, 通常采用聚类分析方法, 基于物以类聚的观点, 用数学方法分析各特征向量之间的距离及分散情况 ; 如果特征向量集聚集若干个群, 可按群间距离远近把它们划分成类 ; 这种按各类之间的亲疏程度的划分, 若事先能知道应划分成几类, 则可获得更好的分类结果

47 模式分类的主要方法数据聚类统计分类结构模式识别神经网络

48 数据聚类目标 : 用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据集是一种非监督学习的方法, 解决方案是数据驱动的

49 统计分类基于概率统计模型得到各类别的特征向量的分布, 以取得分类的方法特征向量分布的获得是基于一个类别已知的训练样本集是一种监督分类的方法, 分类器是概念驱动的

50 结构模式识别该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目的识别采用结构匹配的形式, 通过计算一个匹配程度值 (matching score) 来评估一个未知的对象或未知对象某些部分与某种典型模式的关系如何当成功地制定出了一组可以描述对象部分之间关系的规则后, 可以应用一种特殊的结构模式识别方法句法模式识别, 来检查一个模式基元的序列是否遵守某种规则, 即句法规则或语法

51 神经网络神经网络是受人脑组织的生理学启发而创立的由一系列互相联系的相同的单元 ( 神经元 ) 组成相互间的联系可以在不同的神经元之间传递增强或抑制信号增强或抑制是通过调整神经元相互间联系的权重系数来 (weight) 实现神经网络可以实现监督和非监督学习条件下的分类

52 模式识别系统模式识别系统的基本构成数据获取预处理特征提取和选择分类器设计分类决策

53 模式识别系统组成单元数据获取 : 用计算机可以运算的符号来表示所研究的对象二维图像 : 文字指纹地图照片等一维波形 : 脑电图心电图季节震动波形等物理参量和逻辑值 : 体温化验数据参量正常与否的描述预处理单元 : 去噪声, 提取有用信息, 并对输入测量仪器或其它因素所造成的退化现象进行复原

54 模式识别系统组成单元特征提取和选择 : 对原始数据进行变换, 得到最能反映分类本质的特征目的 : 实现由模式空间到特征空间的转变, 有效压缩维数分类决策 : 在特征空间中用模式识别方法把被识别对象归为某一类别基本做法 : 在样本训练集基础上确定某个判决规则, 使得按这种规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小

55 模式识别过程实例在传送带上用光学传感器件对鱼按品种分类品种鲈鱼 (Seabass) 鲑鱼 (Salmon)

56 识别过程数据获取 : 架设一个摄像机, 采集一些样本图像, 获取样本数据预处理 : 去噪声, 用一个分割操作把鱼和鱼之间以及鱼和背景之间分开

57 识别过程特征提取和选择 : 对单个鱼的信息进行特征选择, 从而通过测量某些特征来减少信息量长度亮度宽度鱼翅的数量和形状嘴的位置, 等等分类决策 : 把特征送入决策分类器

64 模式分类器的获取和评测过程数据采集特征选取模型选择训练和测试计算结果和复杂度分析, 反馈

66 训练和测试训练集 : 是一个已知样本集, 在监督学习方法中, 用它来开发出模式分类器测试集 : 在设计识别和分类系统时没有用过的独立样本集系统评价原则 : 为了更好地对模式识别系统性能进行评价, 必须使用一组独立于训练集的测试集对系统进行测试

67 实例 : 统计模式识别 19 名男女同学进行体检, 测量了身高和体重, 但事后发现其中有 4 人忘记填写性别, 试问 ( 在最小错误的条件下 ) 这 4 人是男是女? 体检数值如下 :

68 实例 : 统计模式识别 ( 续 ) 待识别的模式 : 性别 ( 男或女 ) 测量的特征 : 身高和体重训练样本 :15 名已知性别的样本特征目标 : 希望借助于训练样本的特征建立判别函数 ( 即数学模型 )

69 实例 : 统计模式识别 ( 续 ) 由训练样本得到的特征空间分布图

70 实例 : 统计模式识别 ( 续 ) 从图中训练样本的分布情况, 找出男女两类特征各自的聚类特点, 从而求取一个判别函数 ( 直线或曲线 ) 只要给出待分类的模式特征的数值, 看它在特征平面上落在判别函数的哪一侧, 就可以判别是男还是女了

71 实例 : 统计模式识别 ( 续 )

72 实例 : 统计模式识别 ( 续 )

73 实例 : 统计模式识别 ( 续 ) R G B H S V

74 实例 : 统计模式识别 ( 续 )

76 实例 : 工业检测的例子

77 实例 : 句法模式识别问题 : 如何利用对图像的结构信息描述, 识别如下所示图片 :

78 实例 : 句法模式识别 ( 续 ) 将整个场景图像结构分解成一些比较简单的子图像的组合 ; 子图像又用一些更为简单的基本图像单元来表示, 直至子图像达到了我们认为的最简单的图像单元 ( 基元 ); 所有这些基元按一定的结构关系来表示, 利用多级树结构对其进行描述 ( 这种描述可以采用形式语言理论 )

79 实例 : 句法模式识别 ( 续 ) 多级树描述结构

80 实例 : 句法模式识别 ( 续 ) 训练过程 : 用已知结构信息的图像作为训练样本, 先识别出基元 ( 比如场景图中的 X Y Z 等简单平面 ) 和它们之间的连接关系 ( 例如长方体 E 是由 X Y 和 Z 三个面拼接而成 ), 并用字母符号代表之 ; 然后用构造句子的文法来描述生成这幅场景的过程, 由此推断出生成该场景的一种文法

81 实例 : 句法模式识别 ( 续 ) 识别过程 : 先对未知结构信息的图像进行基元提取及其相互结构关系的识别 ; 然后用训练过程获得的文法做句法分析 ; 如果能被已知结构信息的文法分析出来, 则该幅未知图像与训练样本具有相同的结构 ( 识别成功 ), 否则就不是这种结构 ( 识别失败 )

82 模式识别的基本问题一. 模式 ( 样本 ) 表示方法 1. 向量表示 : 假设一个样本有 n 个变量 ( 特征 ) Ⅹ= (X 1,X 2,,Xn) T 2. 矩阵表示 : N 个样本,n 个变量 ( 特征 ) 变量样本 x 1 x 2 x n X 1 X 11 X 12 X 1n X 2 X 21 X 22 X 2n X N X N1 X N2 X Nn

83 3. 几何表示一维表示 X 1 =1.5 X 2 =3 二维表示 X 1 =(x 1,x 2 ) T =(1,2) T X 2 =(x 1,x 2 ) T =(2,1) T 三维表示 X 1 =(x 1,x 2, x 3 ) T =(1,1,0) T X 2 =(x 1,x 2, x 3 ) T =(1,0,1) T

84 4. 基元 ( 链码 ) 表示 : 在右侧的图中八个基元分别表示 0,1,2,3, 4,5,6,7, 八个方向和基元线段长度则右侧样本可以表示为 X 1 = 这种方法将在句法模式识别中用到

85 二. 模式类的紧致性 1. 紧致集 : 同一类模式类样本的分布比较集中, 没有或临界样本很少, 这样的模式类称紧致集

86 2. 临界点 ( 样本 ): 在多类样本中, 某些样本的值有微小变化时就变成另一类样本称为临界样本 ( 点 ) 3. 紧致集的性质 1 要求临界点很少 2 集合内的任意两点的连线, 在线上的点属于同一集合 3 集合内的每一个点都有足够大的邻域, 在邻域内只包含同一集合的点 4. 模式识别的要求 : 满足紧致集, 才能很好的分类 ; 如果不满足紧致集, 就要采取变换的方法, 满足紧致集.

87 三. 相似与分类 1. 两个样本 x i, x j 之间的相似度量满足以下要求 : 1 应为非负值 2 样本本身相似性度量应最大 3 度量应满足对称性 4 在满足紧致性的条件下, 相似性应该是点间距离的单调函数 2. 用各种距离表示相似性 : 1 绝对值距离已知两个样本 x i =(x i1, x i2, x i3,,x in ) T x j =(x j1, x j2, x j3,,x jn ) T

88 d ij n k 1 X ik X jk 2 欧几里德距离 d ij n Xik Xjk k 1 3 明考夫斯基距离 d ij ( q) n k 1 X ik X 2 jk q 1 q 其中当 q=1 时为绝对值距离, 当 q=2 时为欧氏距离

89 4 切比雪夫距离 d ij ( ) max 1 k n X ik X jk q 趋向无穷大时明氏距离的极限情况 5 马哈拉诺比斯距离 d ij ( M ) ( X i X j ) T 1 ( X i X j ) 其中 x i, x j 为特征向量, 样本符合正态分布为协方差使用的条件是

90 6 夹角余弦 C ij n k 1 n k 1 X ik X 2 ik X jk n k 1 X jk 2 X i, X j 为 x i x j 的均值即样本间夹角小的为一类, 具有相似性例 : x 1, x 2, x 3 的夹角如图 : x 2 x 3 x 1 x 2 x 1 因为 x 1, x 2 的夹角小, 所以 x 1, x 2 最相似

91 7 相关系数 rij n n k 1 X ki Xi Xkj Xj 2 n Xki Xi Xkj Xj k 1 k 1 2 X, i Xj 为 x i x j 的均值注意 : 在求相关系数之前, 要将数据标准化 3. 分类的主观性和客观性 1 分类带有主观性 : 目的不同, 分类不同例如 : 鲸鱼, 牛, 马从生物学的角度来讲都属于哺乳类, 但是从产业角度来讲鲸鱼属于水产业, 牛和马属于畜牧业 2 分类的客观性 : 科学性判断分类必须有客观标准, 因此分类是追求客观性的, 但主观性也很难避免, 这就是分类的复杂性

92 四. 特征的生成 1. 低层特征 : 1 无序尺度 : 有明确的数量和数值 2 有序尺度 : 有先后好坏的次序关系, 如酒分为上, 中, 下三个等级 3 名义尺度 : 无数量无次序关系, 如有红, 黄两种颜色 2. 中层特征 : 经过计算, 变换得到的特征 3. 高层特征 : 在中层特征的基础上有目的的经过运算形成例如 : 椅子的重量 = 体积 * 比重体积与长, 宽, 高有关 ; 比重与材料, 纹理, 颜色有关这里低中高三层特征都有了

93 五. 数据的标准化 1. 极差标准化, 一批样本中, 每个特征的最大值与最小值之差极差 R i max Xij min X ij 极差标准化 Xij X ij X i R i 2. 方差标准化 Xij S i 为方差标准化的方法很多, 原始数据是否应该标准化, 应采用什么方法标准化, 都要根据具体情况来定 X ij X i S i

94 相关数学概念随机向量及其分布随机向量如果一个对象的特征观察值为 {x 1, x 2,, x n }, 它可构成一个 n 维的特征向量值 x, 即 x = (x 1, x 2,, x n ) T 式中, x 1, x 2,, x n 为特征向量 x 的各个分量一个特征可以看作 n 维空间中的向量或点, 此空间称为模式的特征空间 R n

95 相关数学概念随机向量及其分布随机向量在模式识别过程中, 要对许多具体对象进行测量, 以获得许多次观测值每次观测值不一定相同, 所以对许多对象而言, 各个特征分量都是随即变量, 即许多对象的特征向量在 n 维空间中呈随机性分布, 称为随即向量

96 相关数学概念随机向量及其分布随机向量的参数 [ 数学期望 ] [ 协方差矩阵 ]

97 相关数学概念正态分布 [ 一维正态密度函数 ]

98 相关数学概念正态分布 [ 多维正态密度函数 ]

99 小结模式和模式识别的概念模式识别的发展简史和应用模式识别的主要方法模式识别的系统和实例模式识别的基本问题几个相关的数学概念

100 小结

数字带通带阻高通滤波器的设计把一个归一化原型模拟低通滤波器变换成另一个所需类型的模拟滤波器, 再将其数字化直接从模拟滤波器通过一定的频率变换关系完成所需类型数字滤波器的设计先设计低通型的数字滤波器, 再用数字频率变化方法将其转换成所需类型数字滤波器

数字带通带阻高通滤波器的设计把一个归一化原型模拟低通滤波器变换成另一个所需类型的模拟滤波器, 再将其数字化直接从模拟滤波器通过一定的频率变换关系完成所需类型数字滤波器的设计先设计低通型的数字滤波器, 再用数字频率变化方法将其转换成所需类型数字滤波器数字带通带阻高通滤波器的设计把一个归一化原型模拟低通滤波器变换成另一个所需类型的模拟滤波器, 再将其数字化直接从模拟滤波器通过一定的频率变换关系完成所需类型数字滤波器的设计先设计低通型的数字滤波器, 再用数字频率变化方法将其转换成所需类型数字滤波器模拟原型方法 : 模拟低通 - 模拟带通 H ( j) H ( j) 3 3 3 模拟原型方法 : 模拟低通 - 模拟带通 H ( j) 模拟低通

第一章 绪论

第一章绪论