4.1 模式
什么是模式？广义的说，存在于时间和空间中观察的事物，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。模式所指的不是事物本身，而是我们从事物获得的信息。因此，模式往往表现为具有时间或空间分布的信息。模式的直观特性：可观察性、可区分性、相似性。
信息进入计算机之前通常要经过取样和量化，在计算机中具有时空分布的信息表现为向量即数组。数组中元素的序号可以对应时间与空间，也可以对应其他的标示。例如，医生根据各项化验指标判断疾病种类的模式识别过程中，各种化验项目并不对应时间或空间。因此，对于上面所说的时间与空间应作更广义、更抽象的理解。
人们为了掌握客观事物，按事物相似的程度组成类别。模式识别的作用和目的就在于面对某一具体事物时将其正确地归入某一类别。例如，数字“4”可以有各种不同的字体或写法，但它们都属于同一类，即使我们看到从未见过的某种写法的“4”，也能正确地将其分到“4”这一类别中。从不同的角度看人脸，视网膜上的成像也不同，但我们可以识别出这个人是谁，把所有不同角度的像都归入某个人这一类。如果给每个类命名，并且用特定的符号来表达这个名字，那么模式识别可以看成是从具有时间和空间分布的信息向着符号所作的映射。
通常，我们把通过对具体的个别事物进行观测所得到的具有时间和空间分布的信息称为模式，而把模式所属的类别和同一类中模式的总体称为模式类（或简称类）。也有人习惯于把模式类称为模式，而把个别具体的模式称为样本。
4.2 模式识别
模式识别(Pattern Recognition)是指对表征事物或现象的各种形式的(数值的、文字的和逻辑关系的)信息进行处理和分析，以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分。
一般来说，模式识别问题指的是对一系列过程或事件的分类与描述。要加以分类的一系列过程或事件可以是一系列物理的对象，或者是一些比较抽象的如心理状态。具有某些相类似的性质的过程或事件就分为一类。对于一个特定的问题，关于模式类的总数是由特定的应用所决定的。例如，考虑识别英文字母的问题，应该是一个26 个类的问题；对于本论文所研究的问题——彩色城市地图道路识别与提取来说，由于地图的非路即区域的特征，这是一个两类的模式识别问题，即分类的结果是把地图图像像素分为道路和区域两类。对于某些问题，开始时可能并不知道到底有多少类，而需要观测许多具有代表性的模式之后才能决定。在这种情况下，我们需要查明，当我们观测越来越多的模式时，新的类别出现的可能性。
我们在生活中时时刻刻都在进行模式识别。人类所具备的这些模式识别的能力看起来极为平常，谁也不会对此感到惊讶。因此过去的心理学家也没有注意到模式识别的能力是个值得研究的问题，就像苹果落地一样见惯不惊。只有在计算机出现之后，当人们试图用计算机来实现人或动物所具备的模式识别的能力时，它的难度才逐步为人们所认识。由于计算机的模式识别在多数方面还远不如人，因此研究人脑中的模式识别过程对提高机器的能力是有益的；反之，研究机器模式识别的能力对于理解人脑中的过程也有很大帮助，认知心理学的很多新模型即得益于此。
4.2.1 模式识别的应用
今天，模式识别的应用非常广泛，包括：
生物学 - 自动细胞学、染色体特性研究、遗传研究；
天文学 - 天文望远镜图像分析、自动光谱学；
经济学 - 股票交易预测、企业行为分析；
医学 - 心电图分析、脑电图分析、医学图像分析；
工程 - 产品缺陷检测、特征识别、语音识别、自动导航系统、污染分析；
军事 - 航空摄像分析、雷达和声纳信号检测和分类、自动目标识别；
安全 - 指纹识别、人脸识别、监视和报警系统；
……
4.2.2 模式分类的方法
模式分类的方法很多，包括：数据聚类、统计分类、结构模式识别、神经网络等。
数据聚类的目标是用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据集，它是一种非监督学习的方法，解决方案是数据驱动的。
统计分类是基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。特征向量分布的获得是基于一个类别已知的训练样本集。它是一种监督分类的方法，分类器是概念驱动的。
结构模式识别，通过考虑识别对象的各部分之间的联系来达到识别分类的目的。识别采用结构匹配的形式，通过计算一个匹配程度值（matching score）来评估一个未知的对象或未知对象某些部分与某种典型模式的关系如何。当成功地制定出了一组可以描述对象部分之间关系的规则后，可以应用一种特殊的结构模式识别方法 – 句法模式识别，来检查一个模式基元的序列是否遵守某种 则，即句法规则或语法。
神经网络是受人脑组织的生理学启发而创立的。它是由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以在不同的神经元之间传递增强或抑制信号。增强或抑制是通过调整神经元相互间联系的权重系数来（weight）实现的。神经网络可以实现监督和非监督学习条件下的分类。
4.2.2.1 模板匹配和特征匹配
模式识别中模板匹配法是最常见的最简单的方法[75-78]，首先将一组模板或模型存在机器中，对于一个未知类别的输入模式，把它与每个类的模板加以比较，根据预先选定的匹配准则或者相似准则来加以分类。
最开始时，模板的左上角点和图象的左上角点是重合的，拿模板和原图象中同样大小的一块区域去对比，然后平移到下一个象素，仍然进行同样的操作，…… 所有的位置都对完后，差别最小的那块就是我们要找的物体[79]。
模板匹配法原理简单，但缺点就是识别范围相对于待识别的模式非常大时，计算量非常大，导致效率极低。
所以在很多时候，人们倾向于使用特征匹配法[80-84]或者是模板匹配和特征匹配相结合的方法[85]进行相关的模式识别。
特征匹配和模板匹配不同的是它并非对整个待识别模式进行全局匹配，而是抽取模式的最主要的特征---- 一个物体区别于另一个物体的属性，用于匹配计算，这样就避免了模板匹配法计算量大，效率低的缺点。
在某些时候，为了节省计算量，提高识别效率，将特征进行分组，先对第一组特征进行匹配（一级匹配），然后再对第二组进行匹配（二级匹配），…… ，直到可以完全正确地分类（识别），也就是说既没有过识别也没有欠识别的现象发生。通过这种多级匹配，可以大大地减少运算量，节省运算时间。
4.2.2.2 特征选择与提取
在模式识别中，特征的选择与提取是非常重要的，它强烈地影响着后面的分类器的设计及其性能。假使对不同类别这些特征差别很大，那就比较容易设计出具有较好性能的分类器。因此，特征选择是模式识别中的一个关键问题。由于在很多实际问题中常常不容易找到那些最重要的特征，或受条件限制不能对它们进行测量，这就使特征选择和提取的任务复杂化而成为构造模式识别系统最困难的任务之一。
特征选择与提取的基本任务是如何从许多特征中找出那些最有效的特征。因此研究如何把高维特征空间压缩到低维特征空间以便有效的设计分类器就成为一个重要的课题。任何识别过程的第一步，不论用计算机还是由人去识别，都要首先分析各种特征的有效性并选出最有代表性的特征。显然特征选择和提取这一任务应在设计分类器之前进行。
可以把特征分为三类：①物理的，②结构的，③数学的。人们通常利用物理和结构特征来识别对象，因为这样的特征容易被视觉、触觉以及其他感觉器官所发现。但在使用计算机去构造识别系统时应用这些特征有时比较复杂，因为一般来说来用硬件去模拟人类感觉器官是很复杂的，而机器在抽取数学特征的能力方面则又比人强得多。这种数学特征的例子有统计平均值、相关系数、协方差矩阵的本征向量等等。
我们讨论的重点是根据学习样本来选择并提取数学特征。物理和结构特征的测量及其有效性的分析和具体对象联系十分密切，涉及到研究对象本身的各种物理规律，因此这里不对它们进行专门讨论。应当指出，在很多实际问题中，物理和结构特征对分类是非常重要的，在实际构造一个识别系统时常常把它们作为基本特征而用到分类器的设计中。
在大多数情况下，不能直接在测量空间中进行分类器的设计，一方面是因为测量空间的维数很高，不适宜于分类器的设计，更重要的是这样一种描述并不能直接反映对象的本质。因此，为了进行分类器的设计，需要把图像从测量空间变换到维数大大减少的特征空间，被研究的图像或现象在这个特征空间中就由一个特征向量来表示。
实际上这样一种变换常常分成几个步骤进行，以下对几个常用的术语作些说明。
特征形成 根据被识别的对象产生出一组基本特征，它可以是计算出来的（当识别对象是波形或数字图像时），也可以是用仪表或传感器测量出来的（当识别对象是实物或某种过程时），这样产生出来的特征叫做原始特征。
特征提取 原始特征的数量可能很大，或者说样本是处于一个高维空间中，通过映射（或变换）的方法可以用低维空间来表示样本，这个过程叫特征提取。映射后的特征叫二次特征，它们是原始特征的某种组合（通常是线性组合）。所谓特征提取在广义上就是指一种变换。若Y 是测量空间，X 是特征空间，则变换
就叫做特征提取。
特征选择 从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的，这个过程叫特征选择。
以细胞自动识别为例，通过图像输入得到一批包括正常及异常细胞的数字图像，我们的任务是根据这些图像区分哪些细胞是正常的，哪些是异常的。首先要找出一组能代表细胞性质的特征。为此可以计算细胞总面积、总光密度、胞核面积、核内纹理等，这样可得到很多原始特征，这一过程就是特征的形成。这样产生出来的原始特征可能很多，或者说原始特征空间维数很高，需要压缩维数以便分类。一种方式是用映射（或称变换）的方法把原始特征变换为较少的新特征，这就是特征提取。另一方式就是从原始特征中去挑选出一些最有代表性的特征来，这就是特征选择。最简单的特征选择方法是根据专家的知识挑选那些对分类最有影响的特征，另一个可能则是用数学的方法进行筛选比较，来找出最有分类信息的特征。
有时特征提取和选择并不是截然分开的。例如，可以先将原始特征空间映射到维数较低的空间，在这个空间中再进行选择以进一步降低维数。也可以经过选择去掉那些明显没有分类信息的特征，再进行映射以降低维数。
4.2.3 模式识别系统的构成
图4-1 模式识别系统的基本构成
数据获取：用计算机可以运算的符号来表示所研究的对象，如，
- 二维图像：文字、指纹、地图、照片等
- 一维波形：脑电图、心电图、季节震动波形等
- 物理参量和逻辑值：体温、化验数据、参量正常与否的描述
预处理单元：去噪声，提取有用信息，并对输入测量仪器或其它因素所造成的退化现象进行复原。
特征提取和选择：对原始数据进行变换，得到最能反映分类本质的特征，如，
- 测量空间：原始数据组成的空间
- 特征空间：分类识别赖以进行的空间
- 模式表示：维数较高的测量空间->维数较低的特征空间
分类决策：在特征空间中用模式识别方法把被识别对象归为某一类别。基本做法：在样本训练集基础上确定某个判决规则，使得按这种规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。
一种直观的吸引人的模式识别的方法是“模板匹配”法，对于这种情形，有一组模板或模型存在机器中，对于一个未知类别的输入模式，把它与每个类的模板加以比较，根据预先选定的匹配准则或者相似准则来加以分类。
