当前位置:文档之家› 基于模板匹配算法的字符识别系统研究与实现_毕业论文

基于模板匹配算法的字符识别系统研究与实现_毕业论文

基于模板匹配算法的字符识别系统研究与实现_毕业论文
基于模板匹配算法的字符识别系统研究与实现_毕业论文

合肥学院

毕业设计(论文)

设计(论文)题目基于模板匹配算法的字符识别系

统研究与实现

院系名称计算机科学与技术系

专业(班级)计算机科学与技术

姓名(学号)

指导教师

系负责人

摘要

自从计算机问世以来,让机器具有模式识别能力一直是计算机科学家们的努力方向。研究表明,对视觉和听觉信息的处理过程,不仅仅是一个感知过程,也是一个认知过程。因此,研究模式识别,是理解人类智能的本质的重要途径。字符识别是一个传统和典型的模式识别问题,脱机手写数字识别是一个典型的大类别的模式识别问题。手写体数字具有不同字符字型相差不大、相同字符有多种不同写法、数字没有上下文关系等等特点,使得脱机手写体数字识别成为识别领域最大的难题和最终的目标。在这种大类别识别的研究中,传统上大多采用模板匹配的方法来解决问题。而在模板匹配算法中,得计算其特征值。图像需要经过二值化,细化等预处理。

关键字模板匹配;特征值;细化;二值化

ABSTRACT

Since computer appeared, it has been an effort direction for scientist to let the computer has the ability of pattern recognition. Researching indicates that the procedure to deal with seeing and hearing not only a procedure of perception but also cognition. Therefore, studying pattern recognition is an important way in understanding the mankind’s intelligence and ability. Character recognition is a traditional and typical pattern recognition problem, and Handwritten Numeral Recognition is a typical large vocabulary pattern recognition problem. Different characters do not vary much, the same character can be written in many ways, there is no context between characters, and so on. Because of so many characteristics, Handwritten Numeral Recognition is a very difficult problem and commonly regarded as one of the ultimate goals of character recognition research. And the template matching algorithm, in its calculation of eigenvalues. Image require two value, thinning and other pretreatment.

引言

手写数字识别(Handwritten Numeral Recognition)是光学字符识别技术(Optical Character Recognition,简称OCR)的一个分支,它研究的对象是:如何利用电子计算机自动辨认人手写在纸上的阿拉伯数字。

在整个OCR领域中,最为困难的就是脱机手写字符的识别。到目前为止,尽管人们在脱机手写英文、汉字识别的研究中已取得很多可喜成就,但距实用还有一定距离。而在手写数字识别这个方向上,经过多年研究,研究工作者已经开始把它向各种实际应用推广,为手写数据的高速自动输入提供了一种解决方案。

手写数字识别作为模式识别领域的一个重要问题,也有着重要的理论价值:(1).阿拉伯数字是唯一的被世界各国通用的符号,对手写数字识别的研究基本上与文化背景无关,这样就为各国,各地区的研究工作者提供了一个施展才智的大舞台。在这一领域大家可以探讨,比较各种研究方法。(2).由于数字识别的类别数较小,有助于做深入分析及验证一些新的理论。这方面最明显的例子就是人工神经网络------相当一部分的ANN模型和算法都以手写数字识别作为具体的实验平台,验证理论的有效性,评价各种方法的优缺点。(3).尽管人们对手写数字的识别已从事了很长时间的研究,并已取得了很多成果,但到目前为止机器的识别本领还无法与人的认知能力相比,这仍是一个有难度的开放问题。(4).手写数字的识别方法很容易推广到其它一些相关问题棗一个直接的应用是对英文这样的拼音文字的识别。事实上,很多学者就是把数字和英文字母的识别放在一块儿研究的。

人类认知事物的过程中,视觉起到了举足轻重的作用。视觉是人类最高级的感知器官,它不仅指对光信号的感受,还包括了对视觉信息的获取、传输、处理、存储与理解的全过程。随着工业自动化的发展,机器视觉作为一种应用系统逐渐得到完善和发展。机器视觉就是用机器代替人眼来做测量和判断。其特点是能够提高生产的柔性和自动化程度,在一些不适合人工作业的危险工作环境或人工视觉难以满足要求的场合,常用机器视觉来替代人工视觉;同时在大批量工业生产过程中,用人工视觉检查产品质量效率低且精度不高,用机器视觉检测方法可以大大提高生产效率和生产的自动化程度。而且机器视觉易于实现信息集成,是实现计算机制造的基础技术。在机器视觉中,常常需要从图像背景中把感兴趣的物体检测出来,模板匹配是最常用也是最基本的方法。随着信号处理技术和计算机技术的不断发展,模板匹配在工业检测、卫星遥感、半导体封装、文字识别、导航制导、医学X射线图片处理、气象云图分析、光学和雷达的图像模板跟踪、工业流水线的自动监控、工业仪表的自动监控、资源分析、交通管理、图像数据库检索以及景物分析中的变化检测等领域应用越来越广泛。可见,匹配技术己经成为机器视觉和众多领域中不可或缺的组成部分,对图像匹配技术进行探索研究势在必行。

在下面各章我将以一个字符识别系统为例,就字符识别概述、模板匹配算法及改进、图像预处理、系统的具体实现等方面进行描述。

第一章绪论。

第二章模板匹配算法及改进。

第三章图像的预处理。

第四章系统的设计与实现。

第五章系统运行及测试。

结束语部分对本次毕业设计做出总结。

目录

摘要 (2)

ABSTRACT (3)

引言 (4)

第一章绪论

1.1 课题研究背景意义 (7)

1.2 字符识别概述 (7)

1.3 字符识别分类 (8)

1.4 研究对象及目标 (8)

1.4.1 研究的对象 (8)

1.4.2 研究的目标 (8)

第二章模板匹配算法及改进

2.1 模板匹配算法描述 (9)

2.2 模板匹配算法的数学描述 (10)

2.3 算法的改进及图示 (11)

第三章图像的预处理

3.1 图像的平滑去噪 (14)

3.2 BMP图像的存储结构 (15)

3.3 颜色处理 (17)

3.4 图像的二值化 (17)

3.5 图像的细化 (18)

3.5.1 细化算法的定义 (18)

3.5.2 细化的要求 (19)

3.5.3 Hilditch算法描述 (19)

第四章系统的设计与实现

4.1 Visual C++ 6.0介绍 (21)

4.1.1 环境安装及选择的原因 (21)

4.1.2 MFC概述 (21)

4.2 系统界面按扭的生成 (21)

4.3 模板计算的实现 (23)

4.3.1 模板计算设计思想 (23)

4.3.2 代码实现 (23)

4.4 样本测试的实现 (25)

4.4.1 样本测试设计思想….…………………………………………………..… ..25

4.4.2 代码实现 (25)

第五章系统运行及测试

5.1 系统的运行 (28)

5.2 系统的测试 (28)

5.3 系统的评价 (30)

结束语 (30)

参考文献 (30)

致谢语 (31)

附录部分代码清单 (31)

第一章字符识别概述

1.1 课题研究背景意义

在机器视觉中,常常需要从图像背景中把感兴趣的物体检测出来,模板匹配是最常用也是最基本的方法。随着信号处理技术和计算机技术的不断发展,模板匹配在工业检测、卫星遥感、半导体封装、文字识别、导航制导、医学X射线图片处理、气象云图分析、光学和雷达的图像模板跟踪、工业流水线的自动监控、工业仪表的自动监控、资源分析、交通管理、图像数据库检索以及景物分析中的变化检测等领域应用越来越广泛。可见,匹配技术己经成为机器视觉和众多领域中不可或缺的组成部分,对图像匹配技术进行探索研究势在必行。

手写数字识别有着极为广泛的应用前景,这也是受到研究者重视的一个主要原因。比如说在大规模的数据统计(如行业年鉴、人口普查等)中,在财务、税务、金融领域中,在邮件分拣中均有着应用。

1.2 字符识别概述

计算机硬件的迅速发展以及计算机应用领域的不断开拓,急切地需要计算机能够更有效的感知诸如声音、文字、图像等人类赖以发展自身、改造环境所运用的信息资料。但就一般意义来说,目前计算机却无法感知他们,键盘,鼠标等输入设备,对于五花八门的外部世界显得无能为力。虽然电视摄象机、图文扫描仪、话筒等设备已解决了上述非电信号的转换,并与计算机联机,但这并不能使计算机真正知道所接受的究竟是什么信息。计算机对外部世界感知能力的低下,成为开拓计算机应用的瓶颈,也与其高超的运算能力形成强烈的对比。因此,着眼与提高计算机感知外部信息能力的学科----模式识别得到了迅速的发展。在模式识别领域中,手写字符的识别是一个非常活跃的研究方向。但这方面的研究工作已有很多,其中不少成果得到了广泛的应用。但是由于手写字符拓扑结构的多样性,目前已有的手写字符识别体统在对无限制手写字符进行分类时,始终存在这样或那样的缺陷。

字符识别是模式识别领域中的一个非常活跃的分支。这一方面是由于问题本身的难度使之成为一个极具挑战性的课题。另一方面,是因为字符识别不是一项孤立的应用技术,其中包含了模式识别领域中其它分之都会遇到的一些最基本的和共性的问题。也正是由于字符识别技术的飞速发展,才促使识别领域和图像分析发展为一个成熟的科学领域。

字符识别技术的研究主要集中在特征抽取和模式匹配两个方面,这一直是光学字符识别(OCR)技术的两大关键所在。由扫描仪转化后的字符二值图像中各点的值,可以看成是该字符的一组特征。但由于这组特征的数量较大,而每个特征所含的信息量很少,因此有必要通过映射或变换的方法将信息集中到少量的特征中。这个过程就叫特征抽取。选择稳定的,分类能力强的特征是字符识别系统的核心。

在识别过程中,对待识别的字符进行特征抽取后,就要将这些特征与特征库中的特征进行比较,进行分类,这个过程称为特征匹配。特征匹配方法可分为完全匹配法和近似匹配法。完全匹配法就是将为未知的字符的特征向量X与特征库中的所有特征向量(Yj, j=1,2,…n)逐一进行比较,若X=Yi,则Yi所对应的字符就是识别结果。否则,就拒识。近似匹配法可进一步分为相关性匹配法,驰豫匹配法和树搜索法。

1.3 字符识别的分类

字符识别按输入方式的不同可分为联机识别(也称为在线识别)和脱机识别(也称为离线识别)。联机识别是对所书写的字符进行实时识别,即写即识。所以联机识别技术往往结合字符的笔划顺序来进行识别。脱机识别方法中,首先对已经写在纸上的字符通过扫描仪转化为二值图像,然后再对字符的二值图像进行识别。书写与识别可以分开进行。因此,脱机识别技术中不涉及字符的书写顺序。

字符识别技术根据别识别的字符的类型通常可分为印刷体识别和手写体识别两

大类,而手写体识别又可分为限制手写体识别和无限制手写体识别(也称为自由手写体识别)。印刷体识别是将印刷刊物上的字符扫描转化为二值图象并进行识别,是将已有刊物上的数据大量输入计算机的最有效的方法。

1.4 研究的对象及目标

1.4.1研究的对象

我们的研究对象是无限制手写数字和英文大写字母,这方面目前已经有大量的研究成果。但是,由于手写字符,特别是英文大写字母,拓扑结构变化的多样性,使得目前已有的一些字符识别系统在应用于无限制手写字符的分类时,始终存在这样或那样的缺陷。正因为如此,手写字符识别对于广大研究者来说,是一个充满魅力的领域。

1.4.2研究的目标

本文所要做的工作是:

(1)建立一个无限制手写数字脱机识别系统,要求该系统具有至少90%以上的

识别率,并且具备一定的稳定性。

(2)建立一个无限制手写大写英文字母脱机识别系统,要求该系统作为手写字符

识别系统中的脱机识别部分,要求该系统具有至少85%以上的识别率,并且具备一定的稳定性。

第二章 模板匹配算法及改进

2.1 模板匹配算法的描述

在机器识别事物的过程中,常需把不同传感器或同一传感器在不同时间、不同成像条件下对同一景物获取的两幅或多幅图像在空间上对准,或根据己知模式到另一幅图中寻找相应的模式,这就叫做匹配。若将已知模式的图像称为模板(如图2—1),在左侧的待匹配图像中找到对应于右侧模板图像的过程即为

待匹配图像 模板

图2—1 待匹配图像和模板图像的示意图 模板匹配。因为只有当同一场景的两幅图像在同一坐标系下时,才能进行相似性比较,所以模板匹配的过程实际上也就是把一幅图像变换到另一幅图像的坐标系过程。图像的模板匹配就是先给定一幅图像,然后到另一幅图像中去查找这幅图像,如果找到了,则匹配成功。这看起来好像很简单,因为我们一眼就能看出一幅图中是否包含另一幅图像,遗憾的是电脑并不具有人眼的强大的视觉的功能,因而需要电脑去判定一幅图片中是否包含另一幅图片是件不容易的事情。对于机器视觉系统而言,实现匹配首先要对图像进行预处理。先计算模板图片的特征值,并存储到计算机中。然后计算待测试样板图片的特征值,与计算机中模板进行比较,运用匹配算法实现匹配。整个过程如图2—2所示。

图2—2 图像匹配系统示意图

从上述图像匹配系统结构图中可以看出实现匹配要考虑以下几方面内容:

(1)图像的数据结构类型:即描述像素灰度值和像素光学特征值之间的信息。

(2)图像的特征空间:由特征数据组成,这些特征数据可以是原始像素数据,也可以是经过处理后提取的图像特征数据。

(3)存储:将图像处理的一些相关信息资料存储在计算机中,了解其在计算机中存储的结构。

(4)匹配算法:是实现匹配的基本思想和方法,是解决匹配问题的关键所在。算法的实现涉及到相似性度量函数的正确选择,相似性度量函数是两幅图像相比较的相似性度量,直接影响着匹配的速度和精度。

(5)搜索方法:即遍历图像时的查找策略,正确的选择搜索方法直接影响到匹配的速度。

在基于图像处理的应用领域中,对于图像匹配的研究可以说一直都是数字图像处理技术和计算机视觉理解的重要研究内容。图像匹配在机器视觉、工业自动模式识别、医学图像的定位等方面都有着重要意义。

2.2 图像匹配的数学描述

以传统的相关算法为例对图像匹配进行数学描述。如图2—3所示,搜索图即待匹配图像S为一方形区域,边长为N,模板图像T也是一个方形区域,边长为M 。设模板T叠放在搜索图S上平移,模板覆盖下的那块搜索图(即图中的阴影部分)叫做

子图S j i,, (i,j)为子图S j i,的左下角在搜索图S中的坐标为:

1< i,j

图2—3 被搜索图(a)和模板(b)

匹配过程如下所示:

假设模板T从待匹配图像S的左下角开始逐点遍历图像,比较T和S j i,的内容。

如果两者一致,则差值为零,可以用下面的测度来衡量T 和S j i ,的内容如果两者一致,则差值为零,可以用下面的测度来衡量T 和S j i ,的相似程度,如公式(1—1)所示。

D(i,j)=∑∑==-M m M

n j i n m T n m S 112,)],(),([ --公式(1—1)

展开后有:

D(i,j)=∑∑∑∑∑∑===-==+?-M m M

n M m M n j

i M m M n j i n m T n m T n m S n m S 11211,112,)],([),(),(2)],([--公式(1—2) 公式(1—2)右边第三项代表模板的总能量,与(i,j)无关,是一个常数;第一项是子图能量,随(i,j)而改变,T 和S j i ,匹配时这一项的取值最大,可以用下面的互相关系作相似性测度: R(i,j)=项的第项的第12D D =∑∑∑∑?m n

j i m n

j i n m S n m T n m S 2

,,)],([),(),( --公式(1—3) 或归一化为: R(i,j)=∑∑∑∑∑∑?m n m n j

i m n

j i n m T n m S n m T n m S ))],([())],([(),(),(22,, --公式(1—4)

显然R(i,j)越大,模板T 和子图S j i ,就越相似,使得R(i,j)取得最大值的位置即为最佳匹配位置,(i,j)也就是我们要搜索的匹配点。

2.3 算法的改进及图示

根据以上对模板匹配的介绍,可以对字符图像进行识别。但是求相似性度量函数,求待匹配图像和模板之间的相似性映射关系均比较复杂。上一节知识的介绍中,也看到了其过程比较麻烦。

本系统中识别的图像均为20?36大小的。即模板图像和待测图像大小相同。即会从图像的左下角一直顺着搜索一直至全图结束。而且映射关系及相似性函数均比较复杂,不是数量级上的关系。此时识别效率就不明显。显得木讷不灵巧。并非像前面介绍的在待测图片中搜索,并返回得到匹配点。因此需要基于此模板匹配算法原理的基础上,对算法进行改进,才能更有效的去完成识别的功能及简化其识别的过程。提高识别速度。即将图片区域化。

算法改进的思想:将图片(3?4)分为12块区域,具体区域的划分如图2—4所示。

图2—4 算法改进的图像示意图

再加上5条交线。共记有17个特征值。模板训练时,将数字模板图片17个特征值的信息记下并存储在数组中。当进行样本训练的时候,用同样的算法计算图片中数字的17个特征值,并到计算机存储区中去匹配,直接利用象素灰度值的差异,找到特征值最接近的一个图片数字,便完成匹配识别的过程。得到匹配的结果。这样变简单多。算法改进后图像的17个特征值计算的程序代码,如附录中所示。先让计算机学习,先计算素材T中模板图片0~9总共10个数字的特征值,每一个特征值显示如下所示:

数字0的特征值为:

4.000000,9.000000,9.000000,4.000000,6.000000,0.000000,0.000000,6.000000,4.000000,9. 000000,9.000000,4.000000,2.000000,2.000000,2.000000,2.000000,2.000000,

数字1的特征值为:

0.000000,1.000000,0.000000,0.000000,6.000000,9.000000,9.000000,5.000000,0.000000,0. 000000,0.000000,0.000000,1.000000,0.000000,2.000000,1.000000,1.000000,

数字2的特征值为:

2.000000,

3.000000,0.000000,5.000000,6.000000,0.000000,8.000000,6.000000,

4.000000,9. 000000,1.000000,3.000000,4.000000,3.000000,2.000000,1.000000,1.000000,

数字3的特征值为:

3.000000,0.000000,0.000000,3.000000,7.000000,7.000000,0.000000,6.000000,2.000000,2. 000000,9.000000,6.000000,2.000000,

4.000000,1.000000,1.000000,2.000000,

数字4的特征值为:

0.000000,0.000000,8.000000,0.000000,0.000000,10.000000,1.000000,6.000000,5.000000, 5.000000,9.000000,4.000000,3.000000,11.000000,1.000000,2.000000,6.000000,

数字5的特征值为:

5.000000,7.000000,0.000000,2.000000,

6.000000,6.000000,0.000000,6.000000,2.000000,2. 000000,9.000000,4.000000,3.000000,3.000000,1.000000,1.000000,1.000000,

数字6的特征值为:

3.000000,9.000000,9.000000,3.000000,6.000000,6.000000,0.000000,6.000000,3.000000,2. 000000,9.000000,5.000000,3.000000,3.000000,1.000000,2.000000,2.000000,

数字7的特征值为:

3.000000,0.000000,0.000000,0.000000,6.000000,

4.000000,9.000000,4.000000,

5.000000,5. 000000,0.000000,0.000000,1.000000,4.000000,1.000000,1.000000,1.000000,

数字8的特征值为:

3.000000,8.000000,8.000000,

4.000000,6.000000,2.000000,

5.000000,

6.000000,3.000000,8. 000000,9.000000,5.000000,4.000000,4.000000,2.000000,6.000000,2.000000,

数字9的特征值为:

6.000000,8.000000,0.000000,0.000000,6.000000,

7.000000,4.000000,5.000000,3.000000,6. 000000,5.000000,0.000000,2.000000,10.000000,2.000000,1.000000,1.000000,

第三章 图像的预处理

一般说来,被观测的图像中含有这种各样的噪声和畸变,去掉这些噪声和畸变,并将图像变成某种标准形式进行加工,使得特征的提取和识别变的容易进行,这些处理称为字符识别预处理。预处理是识别字符前的重要的一步,预处理的好坏直接影响着识别方法的难易及识别结构的好坏。预处理工作做的好,使反映字符本质特征的部分得到保留甚至突出出来,识别就容易进行,识别率高且识别速度快。反之,就会使识别变的困难,甚至造成识别误识等不良后果。

3.1 图像的平滑去噪

平滑处理:

字符图像经过平滑处理,能够去掉孤立噪声干扰,平滑笔划边沿。可用平滑算法。设有3?3 窗口如图3—1所示:

图3—1平滑算法

其中P 为当前点,N0-N7为其8个邻接点,平滑准则为:

(1) 当P 为白时,N0,N2,N4,N6中至少有三个元素为黑,则,将P 改为黑,否则不变。

(2)当P 为黑时,如果:

(a)N4,N3,N2中至少有1个为黑,同时N6,N7和N0中也至少有一个为黑; (b)N2,N1,N0中至少有一个为黑,同时N4,N5和N6中也至少有一个为黑,则P 不变,否则改为白。

噪声处理

噪声处理是一个重要而复杂的工作,通过扫描得到的字符图像有时含有噪声,这些噪声可能是因为纸张质量,污点,扫描通道的碎物或其它干扰造成的。这些噪声的存在,增加了数字识别的难度,较容易导致误识,拒识。如能较好地滤除噪声,无疑会为正确识别带来方便。

由于阿拉伯数字0~9和英文大写字母均为由连续笔划组成的字符,因此若检测到字符扫描图像中的笔划数超过1,则认为该字符图像中肯定存在噪声或者断笔,需加以去噪声或连断笔处理。将多余的噪声去掉,或将断笔连在主体笔划上。而噪声和断笔的区分则可通过设定阈值来实现。具体的方法如下:

设F(i,j),0≤ i ≤m,0≤j ≤n,,为二值图象,令A 为二值图象平面上的一个N ?N 的窗口区域,令A +为包含A 的(N+2)?(N+2)的窗口区域,若

A j i j i F ∈∑),(),(=∑+∈A j i j i F ),(),(≠0

则我们认为窗口区域A中的笔划为噪声或断笔。通过让窗口A在图像平面上浮动,可检测到的笔划判断为噪声;另N=5,并将检测到的笔划判断为断笔。对于检测到的噪声,只需要对应的窗口区域A中所有的黑点变为白点,即可将噪声去除。

3.2 BMP图像的存储结构

设备无关位图(Device-Independent Bitmap)DIB是标准的Windows位图格式,DIB 自带颜色信息,因此调色板管理非常容易。任何运行Windows的计算机都可以处理DIB,它通常以BMP文件的形式被保存在磁盘中。BMP文件中包含了一个DIB,一个BPM

位图文件头:主要用于识别位图文件,下面是位图文件头结构定义:

Typedef struct tagBITMAPFILEHEADER

{

UNIT bfType;

DWORD bfSize;

UNIT bfReserved1;

UNIT bfReserved2;

DWORD bfOffbits;

} BITMAPFILEHEADER;

其中,bfType表示文件类型,必须是0X424D,即值应该是“BM”,标志该文件是BMP位图文件。bfSize的值是位图文件的大小。bfReserved1和bfReserved2为保留字,不用考虑。bfOffbits为从文件头到实际的位图的数据的偏移字节数。

位图信息头:包含了单个象素所用字节数以及描述颜色的格式,此外还包括位图的宽度、高度、目标设备的位图平面书、图像的压缩格式。以下是位图信息头结构的定义:

Typedef struct tagBITMAPINFOHEADER

{

DWORS biSize;

LONG biWidth;

LONG biHeight;

WORD biplanes;

WORD biBicCount;

DWORD biCompression;

DWORD biSizeImage;

LONG biXPelPerMeter;

LONG biYPelsPerMeter;

DWORD biClrUsed;

DWORD biClrImportant;

} BITMAPINFOHEADER;

表3—2 是对上述结构体中各个成员的说明。

表3—2

其中,biBitCount分别有如下的意义:

0:用在JPEG格式中。

1:单色图,调色板中含有两种颜色,通常说的黑白二色图。

4:16色图。

8:256色图,通常说的灰度图。

16:64K图,一般没有调色板,图像数据中每两个字节表示一个象素。

24:16M真彩色图,没有调色板,图像数据中每3个字节表示一个象素。

32:4G真彩色,一般没有调色板,每4个字表表示一个象素,相对24位真彩色图而言,加入了一个透明度,即RGBA模式。

biClrused:这个值通常为0,表示使用biBitCount确定的全部颜色。

biClrImportant:这个值通常为0,表示所有颜色都是必须的。

调色板(Palette):有些位图需要调色板,有些位图,如真彩色图,不需要调色板,它们的BITMAPINFOHEADER后面直接是位图数据。调色板实际上是一个数组,调色板是由颜色表项组成的,调色板结构如下:

Typedef struct tagRGBQUAD

{

BYTE rgbBlue;

BYTE rgbGreen;

BYTE rgbRed;

BYTE rgbReserved;

} RGBQUAD;

需要注意的是,RGBQUARD结构中的颜色顺序是BGR。

位图数据:在位图头文件、位图信息头、调色板之后,便是位图的主体部分:位图数据。根据不同的位图,位图数据所占据的字节数也是不同的,比如,对于8位位图,每个字节代表了一个象素,对于16位位图,每两个字节代表了一个象素,对于24位位图,每三个字节代表了1个象素,对于32位位图,每4个字节代表了一个象

素。

3.3 图像的颜色处理

在真彩色系统中,图像的颜色与真实世界中的颜色非常自然逼近,人眼难以区分他们的差别,通常使用RGB表示法来表现真彩色图像,每一个象素的值用24位表示,红、绿、蓝三原色的浓度分别用一个字节来表示。但对于仅能同时显示16色或者256色的系统,每一个象素仅能分别采用4位或者8位表示,象素值与真彩色的颜色值不能一一对应,这时就必须采用调色板技术。所谓调色板就是在16色或者256色的显示系统中,由图像出现的最频繁的16中颜色或者256种颜色所组成的频色表,颜色表中的值是某种颜色在颜色查找表中的索引值。当需要对颜色位数进行转换时,可用八叉树颜色量化算法进行转换。这种方法首先扫描所有的象素,每遇到一种新的颜色就把它放到八叉树中,并创建一个叶子节点,图像扫描结束后,如果叶节点的数量大于调色板所需的颜色数,就将某些叶节点合并到其上一层节点中(父节点)去,并将父节点变为叶节点,这样进行下去直到叶节点的数量等于或者小于调色板所需的颜色数,之后遍历八叉树,将叶节点的颜色填入调色板的颜色表中。

3.4图像的二值化

实际上在使用的图像处理系统中,处理的对象主要是二值图像。这是因为在使用的系统中,要求处理的速度高、成本低,所以信息量大的灰阶图像的处理占用太大的部分不是好办法。因此希望尽可能用二值图像的形式进行处理。图像信息和背景信息分别对应图像灰度直方图,因此可以通过灰度直方图选择一个阈值把整个图像分成图像信息和背景信息两部分,从而把灰度图像转化为黑白二值图像。图像的灰度直方图是将图像中的象素按其灰度值大小进行组合,所构成的象素数量随灰度级变化的函数的图形形式。通常,灰度直方图的横轴表示灰度值,纵轴用来表示频度。频度,是指具有某一灰度值的象素在图像中出现的次数或者在图像中占总象素的百分比。如图3—2所示。

图3—2 具有二值倾向的灰度直方图

图像二值化可根据下面的阈值处理来进行:

一般采用设定某一阈值,用阈值将图像的数据分成大于阈值和小于阈值的象素群。例如,输入的函数是f(x,y),输出的图像是f\(x,y)。如果用灰度变换的方法来研

究f(x,y),其灰度变换函数为:

f \(x,y)=???<≥时

,当时,当θθ),(0),(1y x f y x f 其中:θ为阈值。 输出的图像的灰度值大于阈值,其数据点值取1;反之取0。这种灰度变换的方法,成为图像的二值化。二值化处理就是把图像f(x,y)分为对象物和背景两个领域,然后求其阈值。在数字化的图像数据中,无用的背景数据和对象物的数据常常混在一起。除次之外,在图像中还含有其它的各种噪声。所以阈值选取必须根据实际情况进行调节。

这里的关键问题是阈值θ的确定方法。因为灰度图像二值化后可能丢失掉原图像中的一些信息,如果阈值选择不当,二值化后的图像有可能与原图像相差很大,不能正确的反映原图像,这样,二值化就失去了意义/因为图像二值化的目的是要在尽可能多的保留原图像特征的前提下舍弃冗余信息。所以阈值的正确选择很重要。

系统中二值化的代码实现如下:

void CDigitClass::BinaryDigit(BYTE thre)

{

digitWidth = digitdib.GetWidth();

digitHeight = digitdib.GetHeight();

LONG x, y;

for(x=0; x

{

for(y=0; y

{

if(digitarray[x][y] >= thre)

digitarray[x][y]=(BYTE)1;

else

digitarray[x][y]=(BYTE)0;

}

}

}

3.5 图像的细化

3.5.1 细化的定义

经过预处理,待细化的图像是0,1二值图象。象素值为1的是需要细化的部分,象素值为0的是背景区域。一个图像的“骨架”是指图像的中央的骨骼部分,可以理解为图像的中轴。例如一个长方形的骨架是它的长方向上的中轴线;正方形的骨架是他的中心点;圆的骨架是他的圆心;直线的骨架是它自身;孤立点的骨架也是它自身。骨架是描述图像几何及拓扑性质的重要特征之一。求图像骨架的过程通常称为对图像“细化”的过程。

3.5.2 细化的要求

在字符识别系统中,为减少数据量,准确提取特征,常常需要采用细化算法。不过字符经过细化后,将不可避免地丢失部分信息。因此是否细化应根据实际情况而定。但一旦决定对字符进行细化,则对细化结果的好坏,将直接影响着识别率。

一般来说,细化有以下的基本的要求:

(1)细化要保持原有字符的连续性,不能使本来相连的笔划断开。

(2)要细化成1象素的骨架,骨架应接近原笔划的中心线。

(3)不要产生严重的畸变,对噪声不敏感。

(4)保留字符原有的拓扑,几何特征,特别是一些明显的拐角不应被光滑掉。

3.5.3 Hilditch算法描述

Hilditch细化算法描述

Hilditch 提出了一种串行细化算法,由于该算法是Hilditch提出的,就叫做Hilditch 算法。Hilditch详细讲述了该算法的思想,但没有给出这种算法地一个简洁的表达式。

Hilditch细化算法是一种串行算法。这种方法需要对整幅图像作多次扫描,在每一次扫描过程中。一些满足给定条件的象素点将被标记,在本次扫描结束后,再将这些标记的象素点删除,然后开始下一次扫描,直到在某一次扫描过程中,再没有象素点被标记,整个细化过程结束。通常在二值图象中,象素点的值为1或者0,值为1的点,称为黑点,也是前景点,即图形象素;值为0的点,称为白点,也是背景点。在细化算法中,每一次扫描过程中,一个黑点,即图形象素点必须满足下面的条件才能被删除:

(1)该点是一个边界点。

(2)该点不是一个端点。

(3)该点不是一个断点。

(4)该点的删除不应该造成过度侵蚀。

图像未经细化时模板训练的效果如图3—3所示

图片3—3 细化前的效果

如图3—4所示,当前象素点P(值为1)的8领域,以及P为边界点、端点、断点时的一种表现形式。

1)P的8领域2)P为边界点3)P为端点4)P为断点

图3—4 P的几种形式

为了方便讨论,令B(P)为当前象素点P的8领域中的黑象素点,S4(P)为P的4领域之和,S8(P)为P的8领域之和。

次算法在对二值图像的每一次扫描处理过程中,扫描顺序是从左到右,从上到下,一个黑象素点同时满足下列七个条件将被删除:

(1)P=1。这个条件保证当前处理象素点P为黑点,即为图形信息点。

(2)S4(P)<=3。这个条件保证P不是边界点。

(3)S8(P)>=2。这个条件保证P不是端点。

(4)N(P)>=1。N(P)是P的8领域中没有被标记的黑象素的个数,这个条件是为了保证细线的两端不被删除。

(5)N(P)>=1。N(P)的定义为:X(P)为对bi的求和。(i=1,2,3,4),bi取值:当P(2i—1)值为0并且P(2i)的值为1或者P(2i+1)的值取为1,其他情况bi的值为0。Hilditch 定义X(P)为交叉数,交叉数X(P)的取值总是0-4之间,可以从理论上证明可以删除的象素与交叉数为1的情况是一致的。

(6)X4(P)=1或者P4没有被标志。X4(P)的定义为:假设P4为0时,求出交叉数X4(P)。

(7)X8(P)=1或者P6没有被标志。同上一条。这两个条件都是为了防止过度腐蚀。

在每一次扫描结束后,被标记的象素点被删除。在最后一次扫描过程中,若没有象素点被标记,整个细化算法结束。

图片细化之后,模板训练的效果如图3—5所示

图3—5 细化后的效果

字符串的模式匹配算法

在前面的图文中,我们讲了“串”这种数据结构,其中有求“子串在主串中的位置”(字符串的模式匹配)这样的算法。解决这类问题,通常我们的方法是枚举从A串(主串)的什么位置起开始与B串(子串)匹配,然后验证是否匹配。假设A串长度为n,B串长度为m,那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n(验证时只看头一两个字母就发现不匹配了),但是我们有许多“最坏情况”,比如: A=“aaaaaaaaaaaaaaaaaaaaaaaaab”,B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法(前缀暴力匹配算法)的低效吗?也许可以,也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法,最坏情况下是O(m+n),可以大大避免重复遍历的情况,我们把它称之为克努特-莫里斯-普拉特算法,简称KMP算法。 假如,A=“abababaababacb”,B=“ababacb”,我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示,。也就是说,i是不断增加的,随着i 的增加j相应地变化,且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符(j当然越大越好),现在需要检验A[i+1]和B[j+1]的关系。 例子: S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说,“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说,既然“a”不与自己后面的子串中任何一字符相等,那么对于主串S来说,前5位字符分别相等,意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余,下次的起始位置就是第6个字符。 例子: S=“abcabcabc” T=“abcabx”

基于模板匹配算法的数字识别讲解

中南民族大学 毕业论文(设计) 学院: 计算机科学学院 专业: 软件工程年级:2009 题目: 基于模板匹配算法的数字识别学生姓名: 李成学号:09065093指导教师姓名: 李波职称: 讲师 2013年5月

中南民族大学本科毕业论文(设计)原创性声明 本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。 作者签名:2013年月日

摘要 (1) Abstract (1) 1 绪论 (2) 1.1 研究目的和意义 (2) 1.2 国内外研究现状 (2) 2 本文基本理论介绍 (3) 2.1 位图格式介绍 (3) 2.2 二值化 (3) 2.3 去噪 (3) 2.4 细化 (4) 2.5 提取骨架 (4) 3 图像的预处理 (5) 3.1 位图读取 (5) 3.2 二值化及去噪声 (5) 3.3 提取骨架 (6) 4 基于模板匹配的字符识别 (8) 4.1 样本训练 (8) 4.2 特征提取 (8) 4.3 模板匹配 (9) 4.4 加权特征模板匹配 (10) 4.5 实验流程与结果 (10) 5 结论 (16) 5.1 小结 (16) 5.2 不足 (16) 6 参考文献 (17)

基于模板匹配算法的数字识别 摘要 数字识别已经广泛的应用到日常生活中,典型的数字自动识别系统由图像采集、预处理、二值化、字符定位、字符分割和字符识别等几部分组成, 这些过程存在着紧密的联系。传统的模板匹配算法因为图像在预处理之后可能仍然存在较大的干扰,数字笔画粗细不均匀,有较大的噪声,识别效率不高。本文采的主要思想就是对字符进行分类,之后对字符进行细化,提取细化后字符的特征矢量,与模板的特征矢量进行加权匹配,误差最小的作为识别结果。本文在模板匹配法的基础上, 采用了特征值加权模板匹配法, 并且改进了匹配系数的求法。应用该法取得了满意的效果, 提高了识别率。 关键词:模板匹配;数字识别;特征值加权;字符识别; Template matching algorithm-based digital identification Abstract Digital identification has been widely applied to daily life, the typical digital automatic identification system by the image acquisition, pre-processing, binarization, character positioning, character segmentation and character recognition several parts, there is a close link these processes. Traditional template matching algorithm because the image may still exist after pre-greater interference, digital strokes uneven thickness, the noise, the identification efficiency is not high. Adopted herein main idea is to classify the character after character refinement, the characters feature vector extraction refinement, and the template feature vector is weighted matching, the minimum error as a recognition result. Template matching method based on feature weighted template matching method, and improve the matching coefficient method. The application of the method to obtain satisfactory results, to improve the recognition rate. Key words:Template matching; digital identification; characteristic value weighted; character recognition;

模式匹配的KMP算法详解

模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道,是个比较难理解的算法,今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法,所以有必要把原来的模式匹配算法拿出来,其实理解的关键就在这里,一般的匹配算法: int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰,关键是当‘失配’的时候程序是如何处理的?回溯,没错,注意到(1)句,为什么要回溯,看下面的例子: S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况?这是由T串本身的性质决定的,是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的,大没有回溯的必要。

毕业论文选题思路

毕业论文选题思路 一、毕业论文选题思路 确定选题是撰写论文的第一步工作。俗话说:“题好一半文”,就是把选题看作论文写作成功的一半。所以对一个初学论文写作的学生来说,确定好选题,更是论文写作成功的关键。 除了要考虑有无社会价值(围绕现实经济生活中的重点、难点和热点来做选题)、自身的知识结构、专业特点、资料来源的难易程度、时间上的保证等因素外,一个论文选题的确定有它的思路: 1、热门与冷门的选择 热门选题的好处:一是资料容易搜集,一段时间内各种媒体会有较多的相关资料信息出现;二是在现实经济生活中,对于这类问题,你有切身的感受;三是一旦你写得好就有机会被有关报纸、杂志采纳。其缺点是,一个选题有许多学生选,大家搜集资料的来源差不多,写出来的文章七拼八凑,从内容到结构都差不多,难出新意。指导老师看到这类文章自然不可能给出好成绩。如笔者去年指导的高职市场营销毕业班的11篇论文,有415篇,就是一个选题,从品牌到名牌。从中可以看出来,学生搜集资料的来源有网络、杂志,文章中使用的案例也差不多,照搬照抄的为多数,根本没有自己的语言。品牌研究

是前几年最热门的话题,这方面的研究太多,你就很难有自己新的观点。当然,在这个选题下,你从另一个角度(不要与多数论文的角度一样),对标题重新设计,内容突出现在企业最关心品牌的问题作更深人的探讨,穿插具说服力的案例,也许会是一篇好文章。 冷门选题也是相对而言的,对学生来说,也就是选得少或不选,资料搜集较难的选题,但也必须具有学术价值和实际应用价值,而不是指脱离经济生活,太陈旧的选题。如笔者去年出版了《招商学》一书。2002年我们在做这么一个选题时,就发现几年来全国招商引资工作做得红红火火,市场上描写招商引资工作的书也有,但极少,各地招商引资以各部门为主都编辑了手册,但真正把招商引资作为一门学科来研究的尚没有;同时,在搜集资料的过程中,了解到各招商引资机构缺的就是这样一本,能够指导他们具体工作的工具类性质的书。招商引资机构有许多的实例,但很少有人把它上升到理论的高度。这一年中,搜集资料的困难太多了,似无资料可搜集,只能从边缘学科中去参考和借鉴。因此,选择这一类“冷门”的选题更容易获得写作上的成功。 是选“热门”选题,还是选“冷门”选题,这要根据你自身的情况来定。“冷门”选题搜集资料难,你会付出比别人多的劳动,但往往会有好的收获,即论文成绩高于别的同学。

基于HALCON的模板匹配方法总结.

基于HALCON的模板匹配方法总结 基于HALCON的模板匹配方法总结 HDevelop开发环境中提供的匹配的方法主要有三种,即Component-Based、Gray-Value-Based、Shape-Based,分别是基于组件(或成分、元素)的匹配,基于灰度值的匹配和基于形状的匹配。这三种匹配的方法各具特点,分别适用于不同的图像特征,但都有创建模板和寻找模板的相同过程。这三种方法里面,我主要就第三种-基于形状的匹配,做了许多的实验,因此也做了基于形状匹配的物体识别,基于形状匹配的视频对象分割和基于形状匹配的视频对象跟踪这些研究,从中取得较好的效果。在VC下往往针对不同的图像格式,就会弄的很头疼,更不用说编写图像特征提取、模板建立和搜寻模板的代码呢,我想其中间过程会很复杂,效果也不一定会显著。下面我就具体地谈谈基于HALCON的形状匹配算法的研究和心得总结。 1. Shape-Based matching的基本流程 HALCON提供的基于形状匹配的算法主要是针对感兴趣的小区域来建立模板,对整个图像建立模板也可以,但这样除非是对象在整个图像中所占比例很大,比如像视频会议中人体上半身这样的图像,我在后面的视频对象跟踪实验中就是针对整个图像的,这往往也是要牺牲匹配速度的,这个后面再讲。基本流程是这样的,如下所示: ⑴ 首先确定出ROI的矩形区域,这里只需要确定矩形的左上点和右下点的坐标即可,gen_rectangle1()这个函数就会帮助你生成一个矩形,利用 area_center()找到这个矩形的中心;

⑵ 然后需要从图像中获取这个矩形区域的图像,reduce_domain()会得到这个ROI;这之后就可以对这个矩形建立模板,而在建立模板之前,可以先对这个区域进行一些处理,方便以后的建模,比如阈值分割,数学形态学的一些处理等等; ⑶ 接下来就可以利用create_shape_model()来创建模板了,这个函数有许多参数,其中金字塔的级数由Numlevels指定,值越大则找到物体的时间越少,AngleStart和AngleExtent决定可能的旋转范围,AngleStep指定角度范围搜索的步长;这里需要提醒的是,在任何情况下,模板应适合主内存,搜索时间会缩短。对特别大的模板,用Optimization来减少模板点的数量是很有用的;MinConstrast将模板从图像的噪声中分离出来,如果灰度值的波动范围是10,则MinConstrast应当设为10;Metric参数决定模板识别的条件,如果设为’use_polarity’,则图像中的物体和模板必须有相同的对比度;创建好模板后,这时还需要监视模板,用inspect_shape_model()来完成,它检查参数的适用性,还能帮助找到合适的参数;另外,还需要获得这个模板的轮廓,用于后面的匹配,get_shape_model_contours()则会很容易的帮我们找到模板的轮廓; ⑷ 创建好模板后,就可以打开另一幅图像,来进行模板匹配了。这个过程也就是在新图像中寻找与模板匹配的图像部分,这部分的工作就由函数 find_shape_model()来承担了,它也拥有许多的参数,这些参数都影响着寻找模板的速度和精度。这个的功能就是在一幅图中找出最佳匹配的模板,返回一个模板实例的长、宽和旋转角度。其中参数SubPixel决定是否精确到亚像素级,设为’interpolation’,则会精确到,这个模式不会占用太多时间,若需要更精确,则可设为’least_square’,’lease_square_high’,但这样会增加额外的时间,因此,这需要在时间和精度上作个折中,需要和实际联系起来。比较重要的两个参数是MinSocre和Greediness,前一个用来分析模板的旋转对称和它们之间的相似度,值越大,则越相似,后一个是搜索贪婪度,这个值在很大程度上影响着搜索速度,若为0,则为启发式搜索,很耗时,若为1,则为不安全搜索,但最快。在大多数情况下,在能够匹配的情况下,尽可能的增大其值。 ⑸ 找到之后,还需要对其进行转化,使之能够显示,这两个函数 vector_angle_to_rigid()和affine_trans_contour_xld()在这里就起这个作用。前一个是从一个点和角度计算一个刚体仿射变换,这个函数从匹配函数的

图像处理技术--模板匹配

图像处理技术——模板匹配算法 左力2002.3. 认知是一个把未知与已知联系起来的过程。对一个复杂的视觉系统来说,它的内部常同时存在着多种输入和其它知识共存的表达形式。感知是把视觉输入与事前已有表达结合的过程,而识别也需要建立或发现各种内部表达式之间的联系。 匹配就是建立这些联系的技术和过程。建立联系的目的是为了用已知解释未知。 章毓晋《图像工程下册》P.163 一.模板匹配的基本概念 模板就是一幅已知的小图像。模板匹配就是在一幅大图像中搜寻目标,已知该图中有要找的目标,且该目标同模板有相同的尺寸、方向和图像,通过一定的算法可以在图中找到目标,确定其坐标位置。 以8位图像(其1个像素由1个字节描述)为例,模板T( m ? n个像素)叠放在被搜索图S( W ? H个像素)上平移,模板覆盖被搜索图的那块区域叫子图Sij。i,j为子图左上角在被搜索图S上的坐标。搜索范围是: 1 ≤ i ≤ W – M 1 ≤ j ≤ H – N 通过比较T和Sij的相似性,完成模板匹配过程。 注意:图像的数据是从下到上、从左到右排列的。 可以用下式衡量T和Sij相似性: ∑∑ = =- = N n ij M m n m T n m S j i D 12 1 )] , ( ) , ( [ ) ,(被搜索图 S 模板 T m i {

∑∑ ∑∑ ∑∑ ======+?-=N n M m N n ij M m N n ij M m n m T n m T n m S n m S 1 2 1 1 1 1 2 1 )] ,([),(),(2)],([ 上式的第一项为子图的能量,第三项为模板的能量,都与模板匹配无关。第二项是模板和子图的互相关,随( i, j )而改变。当模板和子图匹配时,该项有极大值。将其归一化,得模板匹配的相关系数: ∑∑∑∑∑∑======?= N n M m N n ij M m N n ij M m n m T n m S n m T n m S j i R 1 2 1 1 2 1 1 1 )] ,([)],([) ,(),(),( 当模板和子图完全一样时,相关系数R( i, j ) = 1。在被搜索图S 中完成全部搜索后,找出R 的最大值Rmax( im, jm ),其对应的子图Simjm 即为匹配目标。显然,用这种公式做图像匹配计算量大、速度较慢。 另一种算法是衡量T 和Sij 的误差,其公式为: ∑∑ ==-=N n ij M m n m T n m S j i E 1 1 |),(),(|),( E( i, j )为最小值处即为匹配目标。为提高计算速度,取一个误差阈值E 0,当E( i, j )> E 0时就停止该点的计算,继续下一点计算。 试验结果如下: 注:以上试验是在赛扬600 PC 机上用VC6.0进行的。 结果表明:被搜索图越大,匹配速度越慢;模板越小,匹配速度越快。误差法速度较快,阈值的大小对匹配速度影响大,和模板的尺寸有关。 二.改进模板匹配算法 我在误差算法的基础上设计了二次匹配误差算法: 第一次匹配是粗略匹配。取模板的隔行隔列数据,即四分之一的模板数据,在被搜索图上进行隔行隔列扫描匹配,即在原图的四分之一范围内匹配。由于数据量大幅度减少,匹配速度显著提高。 为了合理的给出一个误差阈值E0,我设计了一个确定误差阈值E0的准则: E 0 = e 0 * (m+1)/2 * (n+1)/2

论文选题方法

毕业论文选题、查资料及写作技巧 毕业论文通常是一篇较长的有文献资料佐证的学术论文,是高等学校毕业生提交的有一定学术价值和学术水平的文章。它是大学生从理论基础知识学习到从事科学技术研究与创新活动的 最初尝试。学生在整个毕业论文写作中需要查找大量的文献资料,文献资料的查找对一篇毕业论文写作的成功至关重要。 1 毕业论文写作的目的和意义 毕业论文是高等学校对学生整个学习过程的一个综合性考查。大学生毕业论文质量的好坏是评价高校教学水平质量高低的一个重要标准,是对学生的培养质量和综合水平的一个总体检验.通过大学毕业论文写作,可以使大学生熟悉科学技术研究论文写作的基本方法、基本的论文格式与规范,初步了解科研创作的一些技巧,了解本专业方向的一些研究内容,掌握文献资料查找的基本方法。 2 毕业论文写作的一般步骤 中学生的一篇语文作文一般在考场上花上几十分钟就可以完成,而一篇较好的毕业论文通常是一篇较长的有文献资料佐证的学术论文,一般需要经过较长时间的写作过程.要完成一篇毕业论文,一般需要经过以下几个过程:

2.1 毕业论文选题 毕业论文题目的选定不是一下子就能够确定的.若选择的毕业论文题目范围较大,则写出来的毕业论文内容比较空洞,难以结合实际;而选择的毕业论文题目范围过于狭窄,又难以查找相关文献资料,会让人感到无从下手.对于毕业论文题目的确定,通常可以采取先选出一个大的研究方向,再围绕该研究方向查找文献资料,通过阅读、思考、分析材料逐渐把毕业论文题目范围缩小的方法。 比如,英语专业的学生如果对英语语法感兴趣,可以先选出大的毕业论文题目“On English Grammar”,然后查找相关的文献。如“如何学习英语语法”、“如何使英语语法教学走出平淡”、“解读报刊英语中的语法隐喻”等文献资料。对师范类英语毕业论文题目应进一步缩小,围绕英语语法教学和学习来选择。比如可以选择“英语语法教学的思考”、“论中学英语语法的教学”、“英语语法教学之我见”、“英语语法教学定位的几点思考”等题目,谈谈英语语法的教学方法和教学技巧,再结合师范专业的特点和在实习中的一些体会来写作,就会感到有内容可写,使得所述内容不至于空洞。 在毕业论文选题过程中,应做好前期准备工作。目前,国内大多数高校将毕业论文的写作安排在最后一学年甚至是最后一学期,这是具有合理性的。首先,本科生通过低年级的基础知识

字符串匹配算法总结

Brute Force(BF或蛮力搜索) 算法: 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。 速度最慢。 那么,怎么改进呢? 我们注意到Brute Force 算法是每次移动一个单位,一个一个单位移动显然太慢,是不是可以找到一些办法,让每次能够让模式串多移动一些位置呢? 当然是可以的。 我们也注意到,Brute Force 是很不intelligent 的,每次匹配不成功的时候,前面匹配成功的信息都被当作废物丢弃了,当然,就如现在的变废为宝一样,我们也同样可以将前面匹配成功的信息利用起来,极大地减少计算机的处理时间,节省成本。^_^ 注意,蛮力搜索算法虽然速度慢,但其很通用,文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了,大学上的算法课程除了最笨的Brute Force 算法,然后就介绍了KMP 算法。也难怪,呵呵。谁让Knuth D.E. 这么world famous 呢,不仅拿了图灵奖,而且还写出了计算机界的Bible (业内人士一般简称TAOCP). 稍稍提一下,有个叫H.A.Simon的家伙,不仅拿了Turing Award ,顺手拿了个Nobel Economics Award ,做了AI 的爸爸,还是Chicago Univ的Politics PhD ,可谓全才。 KMP 的思想是这样的: 利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离 比如 模式串ababac这个时候我们发现在c 处不匹配,然后我们看c 前面那串字符串的最大相等前后缀,然后再来移动 下面的两个都是模式串,没有写出来匹配串 原始位置ababa c 移动之后aba bac 因为后缀是已经匹配了的,而前缀和后缀是相等的,所以直接把前缀移动到原来后缀处,再从原来的c 处,也就是现在的第二个b 处进行比较。这就是KMP 。 Horspool算法。 当然,有市场就有竞争,字符串匹配这么大一个市场,不可能让BF 和KMP 全部占了,于是又出现了几个强劲的对手。

模板匹配

halcon模板匹配 * 在一个图片中获取ROI并在此图片中匹配 dev_close_window () dev_open_window (0, 0, 600, 600, 'black', WindowHandle) * 窗口语句 read_image(Image,'L:/Halcon test/mk2.jpg') *read_image(Image,'L:/Halcon test/mk3.jpg') *read_image(Image,'L:/Halcon test/mk4.jpg') * 这里有4张图片,每一张都说明一个小问题,附图分析。 gen_rectangle1 (ROI1, 57.8333, 49.5, 181.167, 342.833) * 画一个矩形选择ROI,矩形在左上角,覆盖一个完整的,无变形规定尺寸的商标,作为模板。 reduce_domain(Image,ROI1,ImageReduced1) * 大图和这个矩形的ROI相减就会得到一个左上角的商标的图案作为模板,命名ImageReduced。 create_shape_model(ImageReduced1,0,0,rad(360),0,'no_pregeneration','use_polarity',40,10,ModelID1) * 创建一个比例不变(1:1)的匹配的轮廓模型。具体参数下个帖子说明,也可见[Halcon算子学习交流区] Halcon模版匹配算子解析。 find_shape_model(Image,ModelID1,0,rad(360),0.7,13,0.5,'interpolation',0,0.9,Row,Column,Angle,Score) * 寻找与模板的大小尺寸必须是一比一匹配的,只是角度的不同而已,若大小发生变化,则不能匹配 get_shape_model_contours(ModelContours1,ModelID1,1) * 在大图中获取匹配。 for i := 0 to |Row|-1 by 1 vector_angle_to_rigid(0,0,0,Row【i】,Column【i】,Angle【i】,HomMat2D) affine_trans_contour_xld(ModelContours2,ContoursAffinTrans,HomMat2D) endfor * 获取匹配。 disp_message (WindowHandle, '总共匹配了' + |Row| + '个商标', 'window', 12, 12, 'red', 'true') * 输出数量统计。 clear_shape_model(ModelID1) stop()

模板匹配

图像模式识别中模板匹配的基本概念以及基本算法 认知是一个把未知与已知联系起来的过程。对一个复杂的视觉系统来说,他的内部常同时存在着多种输入和其他知识共存的表达形式。感知是把视觉输入与事先已有表达结合的过程,而识别与需要建立或发现各种内部表达式之间的联系。匹配就是建立这些联系的技术和过程。建立联系的目的是为了用已知解释未知。(摘自章毓晋《图像工程》) 1、模板匹配法: 在机器识别事物的过程中,常常需要把不同传感器或同一传感器在不同时间、不同成像条件下对同一景象获取的两幅或多幅图像在空间上对准,或根据已知模式到另一幅图像中寻找相应的模式,这就叫匹配。在遥感图像处理中需要把不同波段传感器对同一景物的多光谱图像按照像点对应套准,然后根据像点的性质进行分类。如果利用在不同时间对同一地面拍摄的两幅照片,经套准后找到其中特征有了变化的像点,就可以用来分析图中那些部分发生了变化;而利用放在一定间距处的两只传感器对同一物体拍摄得到两幅图片,找出对应点后可计算出物体离开摄像机的距离,即深度信息。 一般的图像匹配技术是利用已知的模板利用某种算法对识别图像进行匹配计算获得图像中是否含有该模板的信息和坐标; 2、基本算法: 我们采用以下的算式来衡量模板T(m,n)与所覆盖的子图Sij(i,j)的关系,已知原始图像S(W,H),如图所示: 利用以下公式衡量它们的相似性: 上述公式中第一项为子图的能量,第三项为模板的能量,都和模板匹配无关。第二项是模板和子图的互为相关,随(i,j)而改变。当模板和子图匹配时,该项由

最大值。在将其归一化后,得到模板匹配的相关系数: 当模板和子图完全一样时,相关系数R(i,j) = 1。在被搜索图S中完成全部搜索后,找出R的最大值Rmax(im,jm),其对应的子图Simjm即位匹配目标。显然,用这种公式做图像匹配计算量大、速度慢。我们可以使用另外一种算法来衡量T和Sij的误差,其公式为: 计算两个图像的向量误差,可以增加计算速度,根据不同的匹配方向选取一个误差阀值E0,当E(i,j)>E0时就停止该点的计算,继续下一点的计算。 最终的实验证明,被搜索的图像越大,匹配的速度越慢;模板越小,匹配的速度越快;阀值的大小对匹配速度影响大; 3、改进的模板匹配算法 将一次的模板匹配过程更改为两次匹配; 第一次匹配为粗略匹配。取模板的隔行隔列数据,即1/4的模板数据,在被搜索土上进行隔行隔列匹配,即在原图的1/4范围内匹配。由于数据量大幅减少,匹配速度显著提高。同时需要设计一个合理的误差阀值E0: E0 = e0 * (m + 1) / 2 * (n + 1) / 2 式中:e0为各点平均的最大误差,一般取40~50即可; m,n为模板的长宽; 第二次匹配是精确匹配。在第一次误差最小点(imin, jmin)的邻域内,即在对角点为(imin -1, jmin -1), (Imin + 1, jmin + 1)的矩形内,进行搜索匹配,得到最后结果。

实验三____串的模式匹配

实验三串的模式匹配 一、实验目的 1.利用顺序结构存储串,并实现串的匹配算法。 2.掌握简单模式匹配思想,熟悉KMP算法。 二、实验要求 1.认真理解简单模式匹配思想,高效实现简单模式匹配; 2.结合参考程序调试KMP算法,努力算法思想; 3.保存程序的运行结果,并结合程序进行分析。 三、实验内容 1、通过键盘初始化目标串和模式串,通过简单模式匹配算法实现串的模式匹配,匹配成功后要求输出模式串在目标串中的位置; 2、参考程序给出了两种不同形式的next数组的计算方法,请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法,并与简单模式匹配算法进行比较。 参考程序: #include "stdio.h" void GetNext1(char *t,int next[])/*求模式t的next值并寸入next数组中*/ { int i=1,j=0; next[1]=0; while(i<=9)//t[0] { if(j==0||t[i]==t[j]) {++i; ++j; next[i]=j; } else j=next[j]; } } void GetNext2(char *t , int next[])/* 求模式t 的next值并放入数组next中 */ { int i=1, j = 0; next[1]= 0; /* 初始化 */ while (i<=9) /* 计算next[i+1] t[0]*/ { while (j>=1 && t[i] != t[j] ) j = next[j]; i++; j++;

if(t[i]==t[j]) next[i] = next[j]; else next[i] = j; } } void main() { char *p="abcaababc"; int i,str[10]; GetNext1(p,str); printf("\n"); for(i=1;i<10;i++) printf("%d",str[i]); GetNext2(p,str); printf("\n"); for(i=1;i<10;i++) printf("%d",str[i]); printf("\n\n"); }

毕业论文选题思路2

学位论文选题的8个方法 选题基本途径为从读书和讨论中发现问题,突破学科“空白处”及“空缺 处”,在多学科“交叉口”产生新思想,把握学科发展前景。选题方法则包括 材料提取法、拟想验证法、启发法、社会调查方法、回溯法、比较法、综合法、移植法、怀疑法、换位思考法、类比移植法等。 学位论文题目来自于实践与理论的矛盾,实践中提出的新问题,原有理论难以解决,就构成课题。所以,积极参与社会实践,深入调查研究,是学位论文选题的基本途径,包括以下几方面。 宋代著名学者朱熹曾指出:读书有疑,所有见,自不容不立论。其不立论者, 只是读书不到疑处耳!”在科学研究成果中,常常发现这类词语:在一定条件下在相当程度上”、在某种范围内”、存在这样那样的联系”、多种多样的形式 那么,究竟在什么条件下?多大程度上?何种范围内?存在怎样的联系?有哪些不同形式?这些都可以构成进一步研究的子课题。对这些子课题锲而不舍地探讨,可能产生新的研究成果。 在选题前,应先在自己熟悉或有兴趣的范围内广泛阅读有关文献信息,分析已有 研究成果,开阔思路,扩大视野。 张世英教授曾深有体会地说:“选题过程中,要大量翻阅资料,东翻翻西翻翻,左想想右想想,题目中心也就酝酿得差不多了。” 这是经验之谈。通过读书,了解信息、思考选题,是培养研究生独立科研能力的良好途径。 王力先生也主张通过读书培养选题能力,他说:“提出问题是解决问题的头一步。你连问题都提不出来,怎么谈得上解决呢?首先要注意到哪些问题没有解决…… 要善于发现问题,提出问题。有些人念了很多书,什么问题也没有,那就不好,等于白念。” 学位论文选题有一定难度,有利于挖掘研究生潜力,发扬创新精神,在前人基础上有所突破,表达自己的新见解、新观点,成一家之言。

MySQL中的字符串模式匹配.

MySQL中的字符串模式匹配 本文关键字:MySQL 字符串模式匹配 MySQL提供标准的SQL模式匹配,以及一种基于象Unix实用程序如vi、grep 和sed的扩展正则表达式模式匹配的格式。 标准的SQL模式匹配 SQL的模式匹配允许你使用“_”匹配任何单个字符,而“%”匹配任意数目字符(包括零个字符)。在 MySQL中,SQL的模式缺省是忽略大小写的。下面显示一些例子。注意在你使用SQL模式时,你不能使用=或!=;而使用LIKE或NOT LIKE比较操作符。 例如,在表pet中,为了找出以“b”开头的名字: +--------+--------+---------+------+------------+------------+ | name | owner | species | sex | birth | death | +--------+--------+---------+------+------------+------------+ | Buffy | Harold | dog | f | 1989-05-13 | NULL | | Bowser | Diane | dog | m | 1989-08-31 | 1995-07-29 | +--------+--------+---------+------+------------+------------+ 为了找出以“fy”结尾的名字:

+--------+--------+---------+------+------------+-------+ | name | owner | species | sex | birth | death | +--------+--------+---------+------+------------+-------+ | Fluffy | Harold | cat | f | 1993-02-04 | NULL | | Buffy | Harold | dog | f | 1989-05-13 | NULL | +--------+--------+---------+------+------------+-------+ 为了找出包含一个“w”的名字: +----------+-------+---------+------+------------+------------+ | name | owner | species | sex | birth | death | +----------+-------+---------+------+------------+------------+

模板匹配详解

模板匹配? 目标? 在这节教程中您将学到: ?使用OpenCV函数matchTemplate在模 板块和输入图像之间寻找匹配,获得匹配结 果图像 ?使用OpenCV函数minMaxLoc在给定的 矩阵中寻找最大和最小值(包括它们的位 置). 原理? 什么是模板匹配?? 模板匹配是一项在一幅图像中寻找与另一幅模板图像最匹配(相似)部分的技术. ?我们需要2幅图像: 1. 原图像(I):在这幅图像里,我们希望 找到一块和模板匹配的区域 2. 模板(T):将和原图像比照的图像 块 我们的目标是检测最匹配的区域:

?为了确定匹配区域, 我们不得不滑动模板图像和原图像进行比较: ?通过滑动, 我们的意思是图像块一次移动一个像素(从左往右,从上往下). 在每一个位置, 都进行一次度量计算来表明它是“好” 或“坏” 地与那个位置匹配(或者说块图像和原图像的特定区域有多么相似). ?对于T覆盖在I上的每个位置,你把度量值保存到结果图像矩阵(R)中. 在R 中的每个位置都包含匹配度量值:

上图就是TM_CCORR_NORMED方法 处理后的结果图像R . 最白的位置代表最 高的匹配. 正如您所见, 红色椭圆框住的位 置很可能是结果图像矩阵中的最大数值, 所以这个区域(以这个点为顶点,长宽和模 板图像一样大小的矩阵) 被认为是匹配的. 实际上, 我们使用函数minMaxLoc来定 位在矩阵R中的最大值点(或者最小值, 根据函数输入的匹配参数) . 问得好. OpenCV通过函数matchTemplate实现了模板匹配算法. 可用的方法有6个: 1. 平方差匹配method=CV_TM_SQDIFF 这类方法利用平方差来进行匹配,最好匹配为0.匹配越差,匹配值越大. b. 标准平方差匹配 method=CV_TM_SQDIFF_NORMED

串的模式匹配算法实验报告

竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一:串的模式匹配算法 串的匹配算法——bruteForce(bF)算法 匹配模式的定义 设有主串s和子串T,子串T的定位就是要在主串s中找到一个与子串T相等的子串。通常把主串s称为目标串,把子串T称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串T;不成功则指目标串s中不存在模式串T。bF算法 brute-Force算法简称为bF算法,其基本思路是:从目标串s的第一个字符开始和模式串T中的第一个字符比较,若相等,则继续逐个比较后续的字符;否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推,若从模式串T的第i个字符开始,每个字符依次和目标串s中的对应字符相等,则匹配成功,该算法返回i;否则,匹配失败,算法返回0。 实现代码如下:

/*返回子串T在主串s中第pos个字符之后的位置。若不存在,则函数返回值为0./*T非空。 intindex(strings,stringT,intpos) { inti=pos;//用于主串s中当前位置下标,若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1; } if(j>T[0]) returni-T[0]; else return0; } } bF算法的时间复杂度 若n为主串长度,m为子串长度则 最好的情况是:一配就中,只比较了m次。 最坏的情况是:主串前面n-m个位置都部分匹配到子串的最后一位,即这n-m位比较了m次,最后m位也各比较了一次,还要加上m,所以总次数为:(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数,然后取平均,得到一般情况是o(n+m).

毕业论文研究方法模板 论文研究方法思路模板

毕业论文研究方法模板论文研究方法思路模板 各位读友大家好,此文档由网络收集而来,欢迎您下载,谢谢

毕业论文是高等教育自学考试本科专业应考者完成本科阶段学业的最后一个环节,那它的研究方法是什么呢?下面是由小编整理的毕业论文研究方法模板,谢谢你的阅读。毕业论文研究方法模板 本科专业自考生在各专业课程考试成绩合格后,都要进行毕业论文的撰写及其答辩考核。毕业论文的撰写及答辩考核是取得高等教育自学考试本科毕业文凭的重要环节之一,也是衡量自考毕业生是否达到全日制普通高校相同层次相同专业的学力水平的重要依据之一。但是,由于许多应考者缺少系统的课堂授课和平时训练,往往对毕业论文的独立写作感到压力很大,心中无数,难以下笔。因此,对本科专业自考生这一特定群体,就毕业论文的撰写进行必要指导,具有重要的意义。 本文试就如何撰写毕业论文作简要论述,供参考。

毕业论文是高等教育自学考试本科专业应考者完成本科阶段学业的最后一个环节,它是应考者的总结性独立作业,目的在于总结学习专业的成果,培养综合运用所学知识解决实际问题的能力。从文体而言,它也是对某一专业领域的现实问题或理论问题进行科学研究探索的具有一定意义的论说文。完成毕业论文的撰写可以分两个步骤,即选择课题和研究课题。 首先是选择课题。选题是论文撰写成败的关键。因为,选题是毕业论文撰写的第一步,它实际上就是确定“写什么”的问题,亦即确定科学研究的方向。如果“写什么”不明确,“怎么写”就无从谈起。 教育部自学考试办公室有关对毕业论文选题的途径和要求是“为鼓励理论与工作实践结合,应考者可结合本单位或本人从事的工作提出论文题目,报主考学校审查同意后确立。也可由主考学校公布论文题目,由应考者选择。毕业

KMP字符串模式匹配算法解释

个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了,确实说得很“详细”,耐心地把它看完肯定会有所收获的~~,另外有关模式函数值next[i]确实有很多版本啊,在另外一些面向对象的算法描述书中也有失效函数f(j)的说法,其实是一个意思,即next[j]=f(j-1)+1,不过还是next[j]这种表示法好理解啊: KMP字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数: int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos

2018年毕业论文怎样选题

2018年毕业论文怎样选题 问题的基础上 写论文主要是反映学生对问题的思考,所以假如学生对问题了解甚少或几乎没有什么感想,那么,要挖空心思讨论一个问题就难了,因为他将不知道到底应该持有什么样的见解才是对的。假如学生对一个问题已经有一定的观察和思考,那么,剩下来的事就只是将能够支持其感想的一些理论和事实数据找出来加以整理,用以支持和表达他的论点。俗话说:”有话则长,无话则短”,一篇6000余字的论文没有一点儿自己的感受是很难写成的,除非做裁缝,将他人的文章相互拼凑在一起完事。 也有这样一种获得自己观点的案头方法,即先大量阅读某个方面的学术文章,看别人在这方面有些什么见解,一边看一边将自己的感想记录下来,经过一定的阅读就会在这方面积累相当多的知识,而自己的见解也可能慢慢形成。有时候学生可能对一些观点有所怀疑,不妨将自己的怀疑提出来,用实事去分析它们是否合理,通过对不同的观点所依据的条件的对比分析,就可以找到一些依据,证明自己的怀疑是否成立,这本身就是一种论证过程,写出来也许就是一篇好文章,所谓”大胆假设,小心求证”应该指此。 选题应鼓励学术创新 避免选择已经完全得到解决的常识性问题;选题要注意与时俱进,鼓励解决实际问题。经济学方面的课题经常是很具有时代性的,

一个课题会随着经济形势的变化而变化。比如,”中国证券市场呼唤开放式基金”,这原是一个不错的课题,但是,目前显然已是一个过了时的课题,因为中国证券市场已经推出了开放式基金,对于”是否需要”这类讨论而言,暂时已不具有特别的意义。但是,假如换成”开放式基金运作效果分析”仍不失为一个可以研究的课题。 选题应与自己所学专业相关 选题应符合专业培养目标和教学要求,以学生所学专业课的内容为主,不应脱离专业范围,要有一定的综合性,具有一定的深度和广度。金融学专业的学生,毕业论文必须在专业有关的方向上选取,可以做交叉性的课题,但是,完全不相关的课题则不符合要求,一定要注意避免。 1 毕业论文写作的目的和意义 毕业论文是高等学校对学生整个学习过程的一个综合性考查。大学生毕业论文质量的好坏是评价高校教学水平质量高低的一个重要标准,是对学生的培养质量和综合水平的一个总体检验.通过大学毕业论文写作,可以使大学生熟悉科学技术研究论文写作的基本方法、基本的论文格式与规范,初步了解科研创作的一些技巧,了解本专业方向的一些研究内容,掌握文献资料查找的基本方法。 2 毕业论文写作的一般步骤 中学生的一篇语文作文一般在考场上花上几十分钟就可以完成,而一篇较好的毕业论文通常是一篇较长的有文献资料佐证的学术论文,一般需要经过较长时间的写作过程.要完成一篇毕业论文,一般

相关主题
相关文档 最新文档