毕业设计（论文）说明书
题目：复杂背景图像中文本定位算法设计
系名信息工程系
专业电子信息工程
学号6008202349
学生姓名杨宇
指导教师冀中
2012年6月8日
摘要
随着多媒体技术的飞速发展，复杂背景图像中的文本定位研究不仅丰富了图像处理理论，而且在诸如Internet环境下的图像检索、交通管理中的车牌识别等具有重大的价值。复杂背景文本定位是一个具有较大难度性的研究课题，原因是文本图像的背景非常复杂，图像大多在室外拍摄，光照条件变化较大，其中不同文字的颜色、亮度、字体、大小、间距、对比度、排列方向和背景纹理等有很大差别。要提取具有复杂背景的文本，首先要找到包含文本的区域，然后才能利用文本识别模块进行识别。本文综述了现有的主要文本定位方法，分析了其中的优缺点，实现了一种基于边缘检测和支持向量机的图像文本定位方法。其中，基于边缘检测的文本定位主要由金字塔分解、基于改进Canny算子的边缘检测、边缘提取和二值化、连通区域分析、以及文本区域鉴定与合并几部分组成。首先运用改进的Canny边缘检测算法检测出文本边缘，然后对检测结果进行连通区域分析、文本区域鉴定与合并得到候选的文本区域。进一步，通过将定位出的候选文本区域运用支持向量机的分类器训练的方法来提高文本定位的准确性。实验结果表明，该文本定位方法不但可以较准确的定位出相应的文本区域，而且具有一定的意义和较大的实用价值。
关键词：文本定位；边缘检测；特征提取；支持向量机
ABSTRACT
With the development of the multimedia technology, the study of locating texts under complicated background has not only enriched image processing theoretically, but also has enormous value in practical application. For example, the image retrieval under Internet environment and the discernment of the plate number in traffic administration. The location and extraction of text from complex background is an important research problem in the computer vision．The variation of the text in terms of characters font, size, style, orientation alignment, texture color and complex background makes the problem of text localization very difficult. The scene content is unconstrained and maybe both indoor and outdoor scenes under any lighting or contrast conditions．
To extract complex background text, text areas should be located first．Current text location methods ale researched in this paper, and the advantage and disadvantage of them are analyzed．Then text location method based on edge detection and support vector machines is implemented.
Edge detection based text location method is composed by Pyramid decomposition, improved Canny algorithm-based edge detection, edge abstracting and binary, connected component analysis, text region identifying and combination. First, the improved Canny algorithm is used to detect the text edge, then connected component and text region identifying and combination is used to get the candidate text region．This paper uses the method of support vector machines classifier training to improve the correctness of text location. The support vector machine is applied to reduce the number of examples effectively, and the result of the experiment is good．The result of the experiment shows that this algorithm can well and exactly locate the text, this algorithm is valuable in theory and application.
Keywords: text location；edge detection；feature extraction；support vector machines
目录
第一章绪论 (1)
1.1 研究背景及意义 (1)
1.2 文本定位研究的现状 (2)
1.3 论文的主要研究内容及结构 (4)
第二章复杂背景图像中的文本定位的一般方法 (6)
2.1 文本特征及类别 (6)
2.2 文本流程定位 (7)
2.3 文本定位方法 (9)
2.4 本章小结 (13)
第三章基于边缘检测的文本定位方法研究 (14)
3.1 引言 (14)
3.2 边缘检测 (14)
3.3 连通区域分析 (23)
3.4 文本区域定位与合并 (24)
3.5 实验结果 (25)
3.6 本章小结 (27)
第四章总结 (28)
参考文献 (29)
外文资料
中文翻译
致谢
第一章绪论
1.1 研究背景及意义
图像中的文本定位是以数字图像处理为基础的，涉及到模式识别、神经网络、信号检测、认识科学等多门学科。随着光学字符识别(OCR)技术的兴起，许多学者开始进行文档图像中文字定位与提取的研究。图像文本定位作为OCR系统的一个预处理部分，对识别嵌入在复杂图像中的文本具有重要的作用。近年来，随着多媒体技术和计算机网络的飞速发展，全世界的数字图像的容量正以惊人的速度增长。每天都会产生海量的图像，这些数字图像中包含了大量有用的信息。目前的计算机视觉和人工智能技术都无法自动对图像进行标注，而必须依赖于人工对图像做出标注。这项工作不但费时费力，而且手工的标注往往是不准确或不完整的，还不可避免地带有主观偏差。所以如何从含有复杂背景的图像和视频中快速而准确地定位和提取文本，现在成为国际上热门的研究课题。
复杂背景是指：图像中的背景含有丰富的纹理；有时文本是嵌入在纹理中的，甚至有时文本本身就是纹理；文本的可能出现的位置、所受光照、字体、大小和颜色都不尽相同，而且这些在文本定位前都是先验未知的，这三点也正是这一研究的挑战所在。如果能够找到解决这些问题的方法，构造出解决复杂背景下的文本定位模型，对于丰富图像处理理论，对于基于内容的视频检索技术的发展，具有重要的理论意义和实用价值。
复杂背景下的文本定位的应用：
(1)实时车牌定位。通过摄像头捕获高速公路上的车牌图像，经过车牌识别系统进行分析和处理，可以实时对交通情况进行监督，实时识别出交通事故涉及车辆的号码，提高运输监管部门的工作效率。
(2)互联网应用。Web服务器的数量正以惊人的速度增长，文本构成了Web页的重要组成部分，在有的网页上图像中的文字居然占去了总的文字量的一半以上，这个比例是相当惊人的，Web页中的图像包含了许多的像素文本信息。
(3)图像、视频检索。随着多媒体技术和计算机网络的飞速发展，越来越多的信息以数字图像的形式传播和存储，图像、视频检索成为计算机领域研究的热点之一。传统的基于关键词的检索技术已不能满足人们的需求，基于内容的图像检索应运而生，而图像中的文字是图像高层语义内容的重要来源。
(4)实时处理护照、票据、身份证等。用扫描、照相等方式获得它们的数字图像后，定位并识别图像中的文字可以快速的获得它们所包含的关键信息。
(5)网络过滤。一些不良网络信息的提供者将文本嵌入到图像文件中，或直接以图像文件的形式显示文本以绕开网络过滤系统。基于图像内嵌文本的语义分
析可以实现基于图像内容的检索和过滤。
文本区域定位就是找出图像中文本所在的位置或刚好包围文本的矩形区域，是文本识别非常关键的一步，文本定位的精确与否直接决定整个识别系统准确率的高低。但文本定位受语种、文字的颜色、分辨率、字符间距、背景、光照、倾斜等影响较大，并且某些纹理、图案等很难与文字区分开来。由于数据采集设备的原因，可能会出现离焦模糊、运动模糊、传感器噪声等，这些都给文本定位带来了较大的困难，它到目前为止依然是一个有很好解决的问题。
如何从复杂背景中准确快速的定位出文本区域以及如何降低遗漏的文字，这就是目前复杂背景图像中的文本定位在图像领域的一个研究热点和难点。
1.2 文本定位研究的现状
复杂背景图像中文本定位问题的产生，是由于将OCR技术扩展到其它应用领域中而产生的问题。在很多领域中，文本是嵌入在复杂背景图像中的，要想很好的识别首先必须进行文本区域的定位，因此提出了复杂背景图像中的文本定位问题的研究。
文本定位的目的主要可以分为：视频图像中的文本定位用于基于内容的视频索、场景图像中的文本定位用于场景理解等。国内外很多的学术机构都开展了这一方面的研究工作。国外主要有美国的加州大学、IBM公司、MIT以及韩国和日本的主要研究机构等。国内主要从事这一研究的有中国科学院自动化研究所，中国科学院计算所进行的视频中文字定位研究，清华大学也在从事这方面的研究工作。
为了能很好的分析现有文本定位方法的异同点，本文从图像中的文本具有的一般特点出发对文本定位方法进行分类。复杂背景图像中的文本具有以下的特点：
(1)文本区域中的字符一般成有规律的排列，字符间隔一致，排列方向一致，一般以水平排列居多。
(2)字符一般大于一定的大小，太小的字符因无法识别而不去进行定位，而字符大小的上限一般没有限制。
(3)字符一般由一致宽度的笔画构成，笔画的密集程度在中文各个字符中并不一致，在英文字符中笔画的密度变化不是很大。
(4)一般情况下，文本与背景之间总有一定的颜色差。但是可能受到光照条件的影响，使颜色差变得很小。
(5)同一文本区域中的字符一般具有统一的颜色、大小、字体。对于场景文本，这种颜色的一致性可能由于光照条件的变化而出现一些变化，字符的大小也可能因为拍摄的方向变化而变化。但是对人工文本一般都具有一致的颜色和大小。
(6)字符的背景复杂多变，无法预测。有的字符的背景单一，但是大部分的图像和视频中文字的背景都很复杂的，有很多的自然界中的物体与字符的笔划很相似，比如树叶、窗格等，还有一些情况既是背景又是文本。
人类有着非常强的识别能力，当人类看到一幅图像，可以很快地发现文字区域并很快的识别出这些文字。但对于计算机来说，要完成这个过程就很困难了，因为计算机只能依靠如方差、水平边缘、垂直边缘等可以量化的视觉特征，而文字的特征远不止这些，特别是中国汉字。图像文本定位的研究涉及到模式识别、图像处理、生理学、心理学、认知神经科学等，和其它的检测技术、计算机人机交互领域都有着十分密切的联系。诸多因素使得复杂背景图像中的文本定位成为一项极具挑战性的研究课题。本文对复杂背景图像中的文本定位研究的主要方法概述如下：
第一个文本定位算法是1995年由Yu Zhong等[1]提出的，实验对象是杂志封面。他们提出计算图像的局部水平方差图，用Canny算子提取水平方差图上的水平方向的边缘，通过检测成对出现的边缘得到文本区域的候选矩形框。对原来输入的图像颜色聚类，如果候选矩形框附近的像素的颜色与候选矩形框内的颜色在一个阈值范围之内，则将该像素合并到候选矩形框内。该方法的不足之处在于，如果图像的对比度很低，则无法得到候选区域；其次如果字符的颜色变化很大，则颜色聚类就没有效果。在文献[2]中作者提出了9条人工文字的特征，在对输入图像做了分割和合并算法之后，根据9条特征去除非文本区域，然后将文本区域按一定的规则合并成文字区域，通过纹理分析去除虚假区域。但是该方法对小的字符效果不是很好，这与其中的Split and.Merge算法有关。在文献[3]，[4]中也提出了类似的方法。总的来说基于图像分割或颜色分层的文本定位方法对于高清晰度的图像，如杂志、封面等效果比较理想，而对于分辨率比较低，并且字符的字体比较小的图像，则效果比较差。
针对以上方法的不足，一些研究者提出了基于边缘检测和纹理分析的方法，该方法对分辨率低的图像取得了满意的效果。诺基亚中国研发中心一直致力于数码相机拍摄的图像中文字的提取，并取得了一定效果。在文献[5]中作者提出基于梯度的文本提取方案，在经过滤波的彩色图像中提取四个不同方向、不同尺度大小的梯度图像，然后对该图像进行二值化和聚类，最后进行连通域分析，得到单个字符。该方法对中文、韩文等方形文字有很好的效果。但是该算法用了很多的规则，这就大大降低了算法的鲁棒性，限制了算法的应用范围。文献[6]采用了一种适应性的文本检测方法，该方法的实验对象是场景文字(Scene Text)，应用多尺度边缘检测方法来弥补对比度和噪声带来的影响，采用了基于高斯混合颜色模型的搜索策略，对提取出来的候选区域进行排列分析，该方法对对比度强的场景文字效果比较突出，但是对透明的文字、相对较小的文字效果就不是很理想，
并且虚检率很高。文献[7]提出了在YUV颜色空间上的边缘提取和选择性二值化文本提取算法，接着对文本区域进行增强、弱化、噪声的影响。应用该方法定位出来的文本块空间位置比较精确，但是该方法有很大的局限性，对于字体很大的文本、对比度小的文本，效果就很差了。文献[11]采用了计算水平梯度和Otsu二值化的方法，对二值图像进行形态学上的处理，得到比较好的定位效果。该方法的不足之处与文献[7]类似。微软亚洲研究院也在进行相关方面的研究，并取得一定的成就。
复杂背景图像中的文本定位是计算机视觉领域的一个非常具有挑战性的课题，有着十分广泛的应用前景，设计一个在任何复杂背景下的文本定位系统是无数研究者们追求的梦想，但从目前的研究情况来看，这样的系统在短期内是不可能设计出来的。总的来讲，有：文本定位、算法集成、算法评价。复杂背景图像的文本定位的难点主要下面分别介绍：
(1)文本定位：由于所处理对象是复杂背景图像，这些样本受环境的影响大，噪声干扰大，图像中文字的语种、颜色、亮度、对比度、字体、大小、间隔、排列方向和背景纹理等因素复杂多变，由于拍摄时的投影关系，有的文字可能会发生形变，这些困难如何克服；同一幅图像中既有人工文本也有场景文本，我们如何区分，采用什么特征；采用基于知识的文本定位方法时，知识如何定义，定义的知识是否准确、有效和全面，是否具有通用性；采用基于学习的文本定位方法时，特征如何选取，选取的特征是否具有很好的推广能力，训练样本如何收集，如何进行训练，所有的这些因素都制约着复杂背景图像中的文本定位算法的研究和发展。
(2)算法集成：多种算法集成难点主要在于集成方案选取上，即如何制订不同算法的选择策略，这将影响到整个系统的性能，另外还有一个必须要考虑的因素就是尽可能快的处理速度。
(3)算法评价：对文本定位算法评价的研究目前还非常的不够，还没有一种国际通用的方法，也没有一个通用的评测数据库，导致了算法间无法客观、公正地进行比较。要定义一个通用的算法，必须考虑很多的因素；期望输出结果(Ground-truth)如何定义，定位结果与期望输出结果之间采用何种匹配方案，如何体现图像中文字的定位难度的不同，如何保证评价标准的公正性、客观性，同时还要保证评价的方法高效、简单易懂。
1.3 论文的主要研究内容及结构
复杂背景图像中的文本定位研究涉及了图像处理、计算机视觉、模式识别和人工智能等多种学科，使用到的相关技术主要包括图像分割技术、人工神经网络、小波分析、图像形态学、Hough变换、支持向量机等。本文在国内外学者研究的基础上，对复杂背景图像中文本的定位进行了进一步的研究。本文实现了一种基
于边缘检测的文本定位方法，并且将其扩展到统计模型支持向量机的框架下来提高文本定位的准确性，取得了较好的效果。
论文的内容、章节安排如下：
第一章：绪论，介绍了复杂背景图像中文本定位的研究背景及意义，简述了文本定位研究的现状，阐明了本文的主要研究内容及结构。
第二章：介绍了复杂背景图像中文本的类别，文本定位的流程，并对多种复杂背景下文本的定位方法做了详细介绍、比较和分析。
第三章：实现了一种基于边缘检测的文本定位方法。首先对图像进行金字塔分解；然后在Canny算子边缘检测的研究基础上，提出了一种改进的Canny算子；随后进行连通区域分析，对文本区域进行鉴定与合并，定位出候选文本区域。
第四章：对全文进行总结，并展望进一步的工作。
第二章复杂背景图像中的文本定位的一般方法
2.1 文本特征及类别
在现实生活中，人们可以很快地辨认出文本区域而不用逐个识别每个字符，因为文本具有很多统计特征，使其不同于场景的其他部分，可以归纳如下
(1)文本和背景之间有较大的对比度；
(2)文本拥有很多频率和方向信息；
(3)文本具有空间聚合性：在一定距离内的字符都沿着某条虚拟的直线对齐，并且同一个字符串内的字符都有相似的高度、方向和大小。
从上面列出的特征中，我们可以发现有很多信息帮助我们处理文本。通常，我们把这些特征分为两类来讲：用来进行文本检测的特征和用来验证文本的特征。前者帮助我们设计方法来从图像中找出候选的文本区域；后者则从候选区域中剔除错误，找到真正包含文本的区域。然而，不论哪种方法都必须牢记以下两点：
(1)复杂背景下文本的对比度在图像的不同位置会有所变化。复杂背景通常比简单背景要求更强的对比度来保证文本的可读。
(2)由于光照的不均匀、噪声和压缩的影响，文本的色彩也是不一致的，因此文本区域内部色彩的同一性不能被严格地假设。
复杂背景图像中的文本可以根据产生的原因划分为：场景文本(Scene Text)和人工文本(Artificial Text)。
场景文本是指实际拍摄场景中所包含的文本，随同拍摄场景一起被拍摄到图像或视频中，它属于场景的一部分。例如：拍摄图像中的车站站牌、汽车车牌等等。场景文本容易受到光照条件、拍摄设备参数的影响，而且方向没有任何的限制，字符有可能受到照相机拍摄角度的影响而发生形变，文字本身可能与场景中的其它物体发生相连等情况。
人工文本是指通过数码相机、摄像机、扫描仪等工具得到图像，再通过图像处理工具(软件或硬件)对图像或视频进行编辑，加上一些相关的文字信息所得到的。例如，在新闻视频n引中添加的新闻标题、电影视频中的字幕等等。人工本不是拍摄场景的一部分，被认为是后期添加的结果。人工文本一般比较规整，与背景之间具有较大的对比度，为了便于让人阅读，字符一般都具有一定的大小，字符的颜色比较一致。这一类字符相对容易识别。
一般来说，真实场景中的文本定位相对要比人工文本定位难。两者都可以统一在复杂背景图像的文本定位中。因此文本后续的研究中，对本文将不具体区分是定位人工文本还是场景文本，仅仅关注图像背景的复杂性。
2.2 文本流程定位
复杂背景图像中的文本定位一般由特征提取、特征分类、特征聚集、候选文本区域提取和文本区域验证等五个步骤组成，如图2-1所示。
选择区分文本与背景
的特征（文本特征选
择）
文本特征提取
特征聚集形成区域
候选文本区域提取
文本区域验证
图2-1 文本定位步骤
首先，选择某个或某些能够把文本与背景区别开来的文本特征；其次，采用某种算法提取文本特征；接着，聚集空间相邻的特征点形成区域：然后，用文本的另一些特征除去一些不可能是文本的区域得到候选文本区域；最后，再用文本的一些特征对候选文本区域进行验证得到真正的文本区域。
2.2.1 文本特征选择
文本具有尺寸、颜色与灰度值、边缘、纹理、对比度、排列方式、符间隙、运动、稳定性、背景变化、阴影和透明效果等特征，应该选那些容易把文本与背景区分开来的特征，以使文本与背景在特征空间内，类间距离较大而类内距离较小。
2.2.2 文本特征提取
对于不同的文本特征需要采用不同的图像处理技术提取，各种文本定位方法文本特征提取与分类所用的技术，如表2-1所示。
表2-1文本特征和文本特征提取与分离所用的技术
文本定位的
方法基于区域的
方法
基于纹理的
方法
基于边缘的
方法
基于学习的
方法
选择的文本特征颜色与灰度
值
纹理被边缘与梯
度
图像块中像
素灰度值或
灰度值的多
阶中心距，彩
色梯度
文本特征提取与分离所用的技术
局部阀值方
法，颜色聚
类，颜色量化
k-mean方法
Soble边缘检
测，Canny边
缘检测
人工神经网
络，支持向量
机
2.2.3 文本特征聚集形成区域
图像中的文本特征通常是分散的点、线段和小区域，不能构成一个完整的文本区域，因此需要聚集这些分散的文本特征形成连续的区域。连通成分分析(Connected Component)和排列分析、形态学运算、均值偏移算法(Mean Shift Algorithm)、水平或垂直投影方法和变异直方图方法等是一些常用的方法。连通成分分析和排列分析方法合并排列方向相同、尺寸相似的相邻连通成分形成连通区域；形态学膨胀运算、均值偏移算法利用边缘点或小区域之间的空隙形成连通区域；水平或垂直投影方法和变异直方图方法统计图像水平或垂直方向全部或部分文本特征的值，然后对投影曲线或变异直方图进行分析提取文本区域。
2.2.4 候选文本区域提取
文本特征聚集形成区域里有一些明显不是文本区域，根据区域的高、宽、高宽比、面积和区域内边缘点的密度可以除去这些噪声区域。
2.2.5 文本区域验证
在候选文本区域提取中，为了尽量减少文本的漏检率，对文本区域的限制条件般并不严格。因此候选文本区域会有一些区域不是文本区域，需要进一步对它们进行验证。文本区域验证可以使用更多的特征，采用更严格的限制条件。文本区域验证的方法有：用候选文本区域的高、宽、高宽比和面积进行文本区域验证：用候选文本区域的尺寸、偏心率、饱和度、强度变化与用置信度加权的排列值
(Align Value)进行文本区域验证；用候选文本区域内边缘点的密度进行文本区域验证；用候选文本区域的直方图分布、字符的结构、字符的排列信息和字符识别进行文本区域验证；用支持向量机进行文本区域验证。
2.3 文本定位方法
复杂图像中的文本定位属于模式识别问题，类似于人脸检测。可以将文本定位作为一个两类的分类问题(文本和非文本)。现在解决特定模式分类问题的关键就是提取有效的目标特征，然后选择适当的分类算法。大多数文本定位方法都是利用文本特征进行文本的定位。基于字符颜色的一致性，提出了基于区域的分析方法；基于字符一致排列而呈现一定的纹理特征，提出了基于纹理的文本区域定位方法；基于文本区域含有较多的边缘，提出了基于边缘的文本定位方法。2.3.1 基于区域的文本定位方法
基于区域的文本定位方法一般假设字符区域具有一致的颜色，根据字符颜色的一致性和字符颜色与背景较大的对比度分割图像，然后对分割后的每个颜色层进行连通域的分析，得到各个候选的连通分量，将各个连通分量作为候选的字符连通分量，对每个连通分量利用一些几何特征以及利用字符的排列关系等排除一些非文本连通分量，并最终得到文本区域。根据不同的颜色分割方法，不同的确认字符连通分量的方法，以及是否利用规则方法或者机器学习的方法，得到了各种基于区域的文本定位方法。
基于区域的文本定位方法主要使用的分割方法有：颜色聚类，颜色量化，利用直方图的分割等。判断各种分割方法对基于连通域的文本定位的好坏主要是考查各种分割方法能否有效的将字符与背景区分开来：同时分割方法能够有效的抑制噪声连通分量的产生，从而减少后续连通分量的判别：另外分割方法的计算速度也是一个应该考虑的问题。根据这些原则还可以尝试各种更为有效的分割方法。
Kim[20]等人利用RGB空间的颜色聚类来分割图像，然后去除明显的非文本区域，如细长的水平线段、图像边框等；文本区域通过投影分析来提取；最后将这些文本区域基于知识规则进行合并。一些门限值需要根据经验来决定，所以这个方法通用性不强。利用这种方法进行的实验采用了50幅视频图像，这些图像中包含不同大小和风格的文字，准确率为87％。
Lienhart等人把文本区域看做是颜色相似的连通区域，用分离和合并算法对图像进行分割，并把分割得到的太大和太小的块都去掉；在形态学膨胀后，再利用相邻帧的运动估计增强文本提取效果；最后用文本的启发性知识滤除非文本区。他们的实验对象为2247帧视频图像，实验表明该算法能提取视频帧中86％-100％的标题文本。
Jain和Yu先把24bits的真彩色图像降低为6bits的彩色图像，再用颜色聚类的方法把原图像分解成不同颜色的子图像；检查每幅子图像中是否包含满足特定启发式搜索的文本；最后将每幅子图像中检测到的文本区域进行合并So-chang 2Pei等人首先用一个SOFM神经网络对输入图像进行颜色量化，然后分析三维彩色直方图；当某一颜色处的梯度大于阈值时，则认为该颜色可能是文本颜色，并将该颜色所占区域赋值为1，其它为0，从而得N--值子图像。再对各二值子图像进行形态学处理、连通域分析，得到候选文本区域。该算法的鲁棒性较强。实验采用的图像具有不同分辨率和背景复杂度，其中的文字大小、风格也各不相同，达到87.26％的准确率。
基于区域的文本定位方法对于具有较大文本与背景对比度的较大字符相对有较好的定位效果，实现简单，计算速度也较快，定位的文本框准确，并同时可以提取文本的颜色，方便后续的文本提取操作。但是这种方法容易受到复杂背景的影响，一些类似字符的背景目标很难被区分，所以准确率相对较低。同时受到噪声污染的文本区域可能与背景物体相连而很难得到定位。
2.3.2 基于纹理的文本定位方法
基于纹理的文本定位方法认为文本具有特定的纹理属性，这种纹理是由于字符特定的排列方向以及字符颜色与背景颜色周期性变化而产生。这类方法通常将整幅图像分割成互不重叠的子块，然后使用各种方法，如Gabor滤波、空间方差、小波变换等来得到子块中的纹理特征，然后使用一个适当的分类器对每个子块进行分类(文本和非文本)，通常使用的分类器有：神经网络、支持向量机、Adaboost 等。为了能够有效的对不同大小的字符进行检测，基于纹理的方法一般都使用基于金字塔或者小波分解的方法，对不同分辨率的图像都进行类似的处理得到文本区域，然后融合到原始图像上。
Park[19]等人“们利用文本的空间差异定位车辆牌照，他们采用两个时延神经网络在HSI空间检测纹理。两个神经网络中一个用于检测水平方向的纹理，一个用于检测垂直方向的纹理。最后将两个神经网络的输出结果加以合并，并结合投影分析得到牌照的矩形区域。Wu等人提出了一种多尺度纹理分割方法用于文本定位。他们用三种不同尺度的二阶高斯滤波器对图像滤波，并对滤波后的图像作非线性变换；变换后的结果作为每个像素的特征并用K-means聚类的方法进行纹理聚类、分割。由于该方法是基于不同尺度纹理检测的方法，因此对图像分辨率高低不敏感，但是处理速度较慢。
Mao等人利用小波变换检测图像纹理，再通过纹理分析进行文本定位。他们先对一幅图像进行Haar小波分解，并计算不同尺度图像的局部能量差异，再将局部能量差异图阈值化从而得N-值图像(通常边缘处的像素局部能量差异大，而边缘内部的像素局部能量差异小)；然后在不同尺度的二值图像中进行连通域分析，
利用文本的几何特性限制去除非文本区域；最后将不同尺度图像中检测到的文本区域进行合并。
基于纹理信息的文本定位方法通常对文字的大小和风格很敏感，很难手工设计出一个适用于各种情况的通用的纹理分类器。因此，人们提出了基于学习的方法以自动分类纹理。
Li等人利用基于学习的方法定位图像中的文字。他们先用Haar小波分解得到文本和非文本的纹理特征；然后用16×16的窗口扫描整个图像，采用三层BP神经网络作为分类器识别分类文本区域和非文本区域。为了解决训练样本的不足，采用fly Sung、提出的Bootstrap(自举)方法进行样本训练。由于通过纹理检测所得到的文本区域不够准确，最后再对候选文本区进行水平和竖直的投影分析，以进一步确认文本区域。Kim[20]将支持向量机(SVM)用于分析图像中文本的纹理特性。该方法不需要专门提取纹理特征，而是直接将像素的灰度值作为支持向量机的输入，经支持向量机处理后输出分类结果(即文本或非文本)；然后再通过消除噪声和合并文字区域就可得到定位结果。支持向量机对于文本定位有很好的鲁棒性，并且可在有限的样本中进行训练。
基于纹理的方法有针对子窗口或者象素点提取纹理特征两种。大部分方法还是将图像分为不重叠的子窗口提取子窗口的纹理特性，并进行判断是否为文本区域。由于纹理方法的特征相对连通分量特征没有直观的意义，很难用基于规则的方法进行判断，一般使用较为复杂的分类器进行分类。而且基于纹理的文本定位方法由于假设文本是一种特殊的纹理，要求字符是成块的出现，字符数越少越难于进行有效的识别，也容易受复杂图像中具有纹理特性的背景影响，虚检率较高。但是这类方法能够很好的对很小的字符进行有效的定位。基于纹理的方法一般很难准确的定位字符区域的边框，一般在利用纹理进行定位之后，还需提取定位窗口中的连通分量进行更为准确的定位和抽取。
基于纹理的方法通常具有较高的鲁棒性，能够检测到字符与背景对比度较小、背景复杂的文本，但定位不够准确。另外纹理分析的计算量大、复杂度高，所以此类算法比较耗时。
2.3.3 基于边缘的文本定位方法
基于边缘的方法，认为文本与背景颜色之间有一定的对比度，通过边缘检测的方法可以有效的检测到字符的边缘，而且文本区域通常含有较高的边缘密度。由于场景中的文本一般为了能够使读者方便阅读，制作时文本与背景在颜色上有很大的差别，所以有些研究者假设文本的边缘比较陡峭，梯度也较大。基于边缘的方法经常根据文本的水平排列特性进行有效的分析，确认文本区域。
Hasan和Karam先将彩色图像转换成灰度图像；然后提取灰度图像的边缘，并将边缘图像二值化，再对二值边缘图像作形态学处理；最后利用大小、高宽比、
密度等启发性知识滤除非文本区域。该方法对噪声不敏感，能够定位不同排列方向的文本，包括倾斜和弯曲的文本。但是有些颜色虽然在RGB空间有明显的差异，但转换到灰度空间后灰度值却相似，这种情况下该算法处理起来就较为困难，Datong Chen等人先用Canny算子提取图像边缘，利用形态学膨胀的方法将边缘连接成块；再利用基线定位和启发性知识限制获得文本行：最后利用支持向量机进一步确认文本行。他们的实验对象为18000幅视频帧及50幅JPEG图片(包括杂志封面、地图)。他们公开的实验结果为98.7％的准确率及1.7％的误检率。Lyu[21]等人也提出了一种提取视频中文字的方法。他们用多分辨分析的方法解决字符大小不同的问题，对多分辨分解后不同尺度的图像进行相同的定位算法处理，即先采用一种改进的Sobel算子提取边缘；再用一种局部自适应阈值的方法将边缘图像转换为二值图像；然后用投影分析的方法定位文本区域。
基于边缘的方法中，有些方法假设字符边缘是一个整体，用连通域分析得到候选字符区域后再进行判别；有些方法认为字符区域的边缘非常密集，所以经常用形态学操作将整个文本区域连接成一个整体再进行判断；有些方法将文字的边缘作为一种纹理特征进行处理。但仅仅利用边缘很难有效的区分文本区域和背景区域，因为很多的图像中背景也含有非常多的边缘。所以一般来说基于边缘的方法对文本非常密集(图像中的人工文本)的图像有较好的效果。
2.3.4 其它方法
使用三种方法(对应三类特征)分别进行文本定位，然后再将这些定位的结果组合到一起的组合策略为：如果各个文本框之间有80％是重合的就认为是文本区域，否则再用一个基于SVM的方法进行确认。使用的三种文本定位方法分别是：基于边缘的亮度变化，连通域分析，先去除较长的线，通常还要用到形态学的操作，然后利用一些特征去除非文本区域；基于颜色方差的方法，用窗口统计其中的颜色方差，认为文本区域有较大的颜色方差，并对水平和垂直进行AND操作的合并，然后利用一些规则去除，如大小等；基于颜色一致性的方法，用颜色量化和聚类得到候选的文本区域，然后用一些规则去除噪声连通分量。
除了以上的方法之外，Tran等人[22]，提出了一种利用Ridge定位文本的方法，他们先在两种不同尺度上提取图像的Ridge。大尺度的称为Central Ridge，小尺度的称为Skeleton Ridge。然后用Ridge的长度限制及两种Ridge的位置关系限制来定位文本区域。该算法可处理各种大小、类型和排列方向的文字，但是当背景复杂时效果不佳。文中实验采用四组不同类型的数据，得出平均查全率为90.7％，查准率为78.3%。Jun等利用灰度图像局部领域技术识别复杂场景下的字符，识别率为71.1％。还有Zhong[23]等人，在视频文本的检测中使用了8×8压缩域DCT方法。Jie [24]等人在视频文本的检测中，在对候选文本区进行投影分析之前，采用数学形态学方法对边缘图进行二值膨胀。Liang等采用形态学方法，从规则的背景图
像中提取出文本，而字符形状几乎没有损耗。Tan[25]等采用金字塔方法从地图中分离字符，适用于GIS领域。Hwang[26]等分析了OCR中字符受噪声干扰的原因采用小波分析方法提取字符，获得的字符笔画完整无损耗。Zhou、Loprestitt[27]应用遗传算法从灰度图像中提取文本。
混合的方法对基于区域、纹理、边缘的方法进行了融合的尝试，充分利用这三类定位的优点进行融合，是实现鲁棒的文本定位的关键，但是如何进行融合、如何提取三类方法中的有效特征并组合到一个框架中是一个难点。
2.4 本章小结
复杂背景中的文字背景是复杂多变的，本文区域定位是复杂背景中文字识别的首要环节，随着文字识别技术的逐步成熟和发展，复杂背景中文本区域定位已成为文字识别应用推广的瓶颈。
复杂背景中的文字相对于其背景来说还是有着自身显著的特征，充分利用这些特征，寻找行之有效的检测算法。经过大量实验和翻阅不少相关的文献，通过各种方法的比较、分析以及复杂背景中文本的特点，本文提出了：基于边缘检测的文本定位方法定位出候选文本区域，然后根据文本的特征对文本块进行筛选，去除虚假文本块，定位出候选文本区域。由于统计模型在模式识别研究中体现的优势，本文通过将定位出的候选文本区域运用支持向量机的分类器训练的方法来提高文本定位的准确性，取得了不错的效果。
第三章基于边缘检测的文本定位方法研究
3.1 引言
从视觉的角度来看，人们在观察一幅图像时，最先得到的信息就是图像的轮廓，也就是图像的边缘信息。同样，在图像处理领域中，图像的边缘信息也非常重要，有很多提取图像边缘的算法，也有很多的图像处理算法应用图像的边缘信息。基于边缘的文本定位方法，认为文本与背景之间有一定的对比度，边缘检测的方法可以有效的检测到字符的边缘，而且文本区域通常含有较高的边缘密度。基于边缘的方法经常根据文本的水平排列特性进行有效的分析，确认文本区域。
本文针对图像中文本定位问题首先对图像进行金字塔分解，然后利用改进的Canny算子对文本进行边缘检测，连通区域分析，最后定位出候选文本区域。3.2 边缘检测
边缘检测的实质是采用某种算法来提取出图像中对象与背景间的交界线。我们将边缘定义为图像中灰度发生急剧变化的区域边界。图像灰度的变化情况可以用图像灰度分布的梯度来反映，因此我们可以用局部图像微分技术来获得边缘检测算子。经典的边缘检测方法，是对原始图像中像素的某小邻域来构造边缘检测算子。
3.2.1 金字塔分解
由于图像文本大小经常变化，有的单一字符占到整幅图像面积的50%以上，而有的不到0.1%。目前，几乎所有的文本定位算法都对字符大小很敏感，为了能够找出大小不一的文本区域，本文采用金字塔模型[29]。所谓P阶金字塔模型(p-step Pyramid)是指对原始图像分辨率逐次进行P次缩小。例如，4阶金字塔模型，总共对图像缩小4次，在每一阶都将原来图像长宽缩小为原来的1/2，对每一阶子图分别采用相同的文本定位算法，然后将不同子图上检测到的文本区域放大到原始图像大小．最后综合每幅子图的定位结果就可以找出大小不同的文本区域。如图3-l中，小的字符在底层子图上被检测到，而在高层的子图上找到了较大的字符，最后的定位结果中包含了不同大小的文本区域。
图3-1 金字塔分解
3.2.2 经典的边缘检测算子
1)高斯一拉普拉斯算子边缘检测
一阶微分是一个矢量，既有大小又有方向，和标量相比它的存储量大。另外，在具有等斜率的宽区域上，有可能将全部区域都当作边缘检测出来。因此，有必要求出斜率的变化率，即对图像函数进行二阶微分运算。拉氏(Laplacian )算子是对二维函数进行运算的二阶导数标量算子。其定义为：
2
?=),(y x f 22),(x y x f ??+22),(y y x f ?? （3-1） 在数字图像中，可用差分近似微分运算，其离散形式为：
2?==),(),(y x L y x f []{][}),1(),(),(),1(y x f y x f y x f y x f ----+ +[]{][})1,(),(),()1,(----+y x f y x f y x f y x f （3-2） 也可以写成：
),(4)1,()1,(),1(),1(),(y x f y x f y x f y x f y x f y x L --+++-++= (3-3) 由于拉普拉斯算子是一个二阶导数，它将在边缘处产生一个陡峭的零叉，所以它是一个良好的锐化滤波器。但是它对图像中的噪声很敏感，也产生双像素宽的边缘，且也不能提供边缘方向的信息。因此，它比较少直接用于边缘检测，而主要用于已知边缘像素后确定该像素是在图像的黑暗区还是明亮区。
高斯滤波器是一个良好的平滑滤波器，它能比较好的把噪声点消除。高斯一拉普拉斯滤波器先平滑掉噪声，再进行边缘检测，所以效果不错。常用的高斯一拉普拉斯算子是5×5的模版，如图3-2所示。
-2 -4 -4 -4 -2
-4 0 8 0 -4
-4 8 24 8 -4
-4 0 8 0 -4
-2 -4 -4 -4 -2
图3-2 拉普拉斯算子的5?5模版
2)Roberts 边缘检测
由Roberts 提出的算子是一种利用局部差分算子寻找边缘的算子，它在2×2邻域上计算对角导数：
[][]22),1()1,()1,1(),(),(y x f y x f y x f y x f y x g +-++++-= (3-4)
G (x ，y )又称为Roberts 交叉算子，在实际应用中为了简化计算，用梯度函数的Roberts 绝对值来近似：
=),(y x g ),1()1,()1,1(),(y x f y x f y x f y x f +-++++- (3-5) 另外还可以用Roberts 最大值来计算：
=),(y x g max （),1()1,()1,1(),(y x f y x f y x f y x f +-++++-） (3-6)
上式能够提供较好的不变性边缘取向。对于同等长度但取向不同的边缘，应用Roberts 最大值算子比应用Roberts 交叉算子所得到的合成幅度变化小。Roberts 边缘检测算子的卷积算子为：
1 ， 0 0 ， 1
0 ， -1
-1 ， 0
3)Sobel 边缘检测
Roberts 算子的一个主要问题是计算方向差分时对噪声敏感。Sobel 提出一种将方向差分运算与局部平均相结合的方法，即Sobel 算子。该算子是在以f (x ，y )为中心的3×3邻域上计算x 和y 方向的偏导数，即：
(){}{})1,1(),1(2)1,1()1,1(1,12)1,1(+---+----++-++-+=y x f y x f y x f y x f y x f y x f S x {}{}
)1,1()1,(2)1,1()1,1()1,(2)1,1(-+--+---++++++-=y x f y x f y x f y x f y x f y x f S y (3-7)
专业综合实验报告----数字图像处理 专业：电子信息工程 班级： ：
学号： 指导教师： 2014年7月18日 车牌图像定位与识别 一、设计目的 利用matlab实现车牌识别系统，熟悉matlab应用软件的基础知识，利用其解决数字信号处理的实际应用问题，从而加深对理论知识的掌握，巩固理论课上知识的同时，加强实践能力的提高，理论联系实践，提高自身的动手能力。同时不断的调试程序也提高了自己独立编程水平，并在实践中不断完善理论基础，有助于自身综合能力的提高。 二、设计容和要求 车牌识别系统应包含图像获取、图像处理、图像分割、字符识别、数据库管理等几个部分，能够完成复杂背景下汽车牌照的定位分割以及牌照字符的自动识别。这里，只要求对给定的彩色车牌图像变换成灰度图像，用阈值化技术进行字符与背景的分离，再提取牌照图像。 三、设计步骤 1．打开计算机，启动MATLAB程序； 2．调入给定的车牌图像，并按要求进行图像处理； 3．记录和整理设计报告 四、设计所需设备及软件
计算机一台；移动式存储器；MATLAB 软件。 五、设计过程 车辆牌照识别整个系统主要是由车牌定位和字符分割识别两部分组成，其中车牌定位又可以分为图像预处理及边缘提取模块和牌照的定位及分割模块；字符识别可以分为字符分割和单个字符识别两个模块。 (一）对图像进行图像转换、图像增强和边缘检测等 1.载入车牌图像： 2.将彩图转换为灰度图并绘制直方图： 灰度图 灰度直方图 3.用roberts 算子进行边缘检测： 图像中车辆牌照是具有比较显著特征的一块图象区域，这此特征表现在：近似水平的矩形区域；其中字符串都是按水平方向排列的；在整体图象中的位置较
北京联合大学毕业设计（论文）任务书 题目：基于MATLAB的车牌定位算法设计 专业：电子工程系指导教师：章学静 学院：信息学院学号： 2009080403104 班级： 20090804031 姓名：林本存 一、课题的任务与目的 自从2010年以来，北京的交通拥堵问题成为社会普遍关注和谈论的话题。而其他交通问题也呈现增长趋势。由于车辆牌照是我们标定车辆的唯一ID，因此，车牌的定位识别对于处理突发的交通事件就显得尤为重要。车牌定位识别系统是近几年发展起来的计算机视觉和模式识别技术在智能交通领域应用的重要课题之一。所谓车牌定位(License Plate Location)，就是把车牌区域完整的从一幅具有复杂背景的车辆图像中分割出来。它是进行车牌识别的首要任务和关键技术，能否将牌照的位置找出来，决定着车牌识别的后续工作能否继续进行，如果不能正确找到牌照的位置，那么就无法将它分割出来，字符分割和字符识别工作将无从谈起。同时，车牌定位的效率也直接影响着整个识别系统的效率，一个高效率的车牌识别系统首先必须是建立在高效的车牌定位算法的基础之上。因此，研究与开发车牌定位的算法具有十分重要的实用意义。例如，在公安执法系统、高速公路自动收费系统、城市道路监控系统、智能停车场管理系统等诸多智能交通系统中都有应用。车牌定位的目的是对摄像头获取的汽车图像进行预处理，确定车牌位置。 此次设计的任务就是在MATLAB中对采集到车辆图像进行色彩直方图分析，匹配车牌背景颜色的峰值从而实现车牌在图像位置中的定位。然后将此算法移植到DSP中，在DSP中验证移植的算法正确性。 二、调研资料情况 目前国外车牌定位识别系统已经有很多成熟的产品，以色列Hi—Tech公司的See/CarSystem系列，新加坡optasia公司的IMPS系列都是比较成熟的产品。但是，这些产品基本上只适合于自己国内的状况。而我国的情况与国外有很大的不同，比如车牌的形状，颜色，字符的颜色以及我国车牌中包含着汉字等。同时，目前的牌照识别系统具有一定的识别率，在天气条件差的情况下或夜晚时，识别率会明显下降，此外，也受到其他许多客观干扰的影响，例如天气、背景、车牌磨损、图像倾斜等。因此现有的识别系统要达到完全实用化仍然有很长的路要走。现有的比较好的车牌定位方法主要有J.Barroso等提出的基于水平线搜寻的定位
《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
基于VisionPro的数字图像识别与定位 【摘要】本文利用VisionPro视觉软件进行数字图像识别与定位研究。首先利用该软件实现了图像采集和摄像机标定，然后基于VisionPro运用VB编写人机交互界面，利用采集得到的图像进行了目标识别定位。同时利用视觉处理中常用的工具Opencv对采集的图像进行了相同的目标识别定位。对两种方法得到的识别效果和定位数据进行了对比，结果表明，基于VisionPro的视觉系统得到的识别效果更好，定位数据更准确。 【关键词】机器视觉；VisionPro；识别定位；https://www.doczj.com/doc/795487215.html, 1.引言 自20世纪80年代以来，机器视觉技术开始高速发展，已经从实验室走向了人们生产生活的各个方面。机器视觉系统的特点是提高生产的柔性和自动化程度。在一些不适合于人工作业的危险工作环境或人工视觉难以满足要求的场合，常用机器视觉来替代人工视觉；同时在大批量工业生产过程中用机器视觉检测方法可以大大提高生产效率和生产的自动化程度。而且机器视觉易于实现信息集成，是实现计算机集成制造的基础技术。现今，在机器视觉领域已经有了一些成熟的视觉开发软件，其封装了很多可靠、高效的算法和工具。本文选用美国康耐视公司的VisionPro软件，这是一套基于PC架构的视觉系统软件开发包，主要应用于各种复杂的机器视觉领域。它集成了用于定位、检测、识别和通讯等任务的工具库，可用C#、VB和VC等语言进行二次开发。本文基于VisionPro利用https://www.doczj.com/doc/795487215.html,语言进行视觉定位系统的软件开发[1]。 2.视觉定位系统 2.1 硬件组成 在图像处理前首先要得到清晰、有效的图像，这就需要有一套完整的硬件设备。一般主要包括照明用的光源、调节图像清晰度的镜头、将图像转换为数字信号的摄像机和进行图像处理的计算机。其中摄像机与计算机之间的接口也比很重要的，主要分为IEEE1394和采集卡，USB2.0或Gigabit Ethernet千兆网三种[2]。 本视觉系统采用的是日本FUJINON工业摄像头，德国BASLER工业像机ACA1600-20GM，GigE千兆网接口。 2.2 基于VisionPro的软件开发 本视觉定位系统利用https://www.doczj.com/doc/795487215.html,编写适合实验需要的界面，界面中只包含需要的操作功能和数据，使整个界面看起来更加清楚简单，操作起来更方便。 （1）图像采集
三边算法在气体源定位上的应用 摘要：无线传感网络是由低成本、低功耗的微型无线传感网络通过自组织通信形式的分布式网络，具有在微小体积内集成信息采集、数据处理和无线通信等多种功能。在环境监测、军事、工业控制和医疗救助等领域具有重要的应用价值。其中节点定位在气体源研究领域已成为关键技术并具有重要的理论意义与实用价值。 本文从无线传感网络的研究背景与意义着手，分别对特点、传感器节点的组成、WSN体系结构和其主要应用领域进行探讨。着重提出网络实施节点定位的主要方法和技术原理，介绍几种典型的无需测距的节点定位算法和特点并对其进行系统分类和优缺点分析。最后重点针对气体源定位的三种三边算法进行研究，对直接三边算法（DT）、组合三边算法（CT）、加权组合三边算法（WCT）的原理和算法实施的具体过程进行讨论，并使用Matlab仿真软件对算法进行仿真，通过仿真实验说明各种算法之间的优越性。最后对全文进行总结。 关键字：无线传感网络；气体源；节点定位；三边算法 Abstract A Wriless Sensor Network(WSN)consists of low-cost,low-power miniature wriless sensor network.It’s composed of self-organzied communication form a distributed network.With within a small volume of integrated information collection,data processing and wireless commurications and other funcations. It is importantly used in environment monitoring fields,military,industrial controlling and medical assistance.The study for node localization of the plume source research area tends to be an curcial technology not only in the theory but also in practice. The thesis discussed the necessity of this research starting from background and significance of WSN.Beside,some issues concerning the research were investigated,for instance,its characteristics,sensor nodes composition,WSN architecture and its key application ares.Focused on the network node location methods and the main technical principle.It introduced a few classical rang-free localization algorithms and its characteristics. The technical highlight is the sort and review of some algorithms for node positioning .At last, focused on researching three kinds investigation of trilateral localazation algorithm, and discussed the principle and procedures of DT , CT and WCT .Furthermore ,it used Matlab for algorithm simulation in the paper, and analyzed a large number of simulation experiment to proved its validity on location accuracy compared with other similar algorithms .Finally, this thesis was concluded. Keyword: wireless sensor network , node localization ,plume source , trilateration
现代设计方法 现代设计方法是随着当代科学技术的飞速发展和计算机技术的广泛应用而在设计领域发展起来的一门新兴的多元交叉学科。以满足市场产品的质量、性能、时间、成本、价格综合效益最优为目的,以计算机辅助设计技术为主体,以知识为依托,以多种科学方法及技术为手段,研究、改进、创造产品和工艺等活动过程所用到的技术和知识群体的总称。 现代设计方法有:并行设计、虚拟设计、绿色设计、可靠性设计、智能优化设计、计算机辅助设计、动态设计、模块化设计、计算机仿真设计、人机学设计、摩擦学设计、反求设计、疲劳设计。 一、并行设计 并行设计是一种对产品及其相关过程(包括设计制造过程和相关的支持过程)进行并行和集成设计的系统化工作模式。强调产品开发人员一开始就考虑产品从概念设计到消亡的整个生命周期里的所有相关因素的影响，把一切可能产生的错误、矛盾和冲突尽可能及早地发现和解决，以缩短产品开发周期、降低产品成本、提高产品质量。 二、虚拟设计 在达到产品并行的目的以后，为了使产品一次设计成功，减少反复，往往会采用仿真技术，而对机电产品模型的建立和仿真又属于是虚拟设计的范畴。所谓的虚拟制造(也叫拟实制造)指的是利用仿真技术、信息技术、计算机技术和现实制造活动中的人、物、信息及制造过程进行全面的仿真，发现制造过程中可能出现的问题，在真实制造以前，解决这些问题，以缩减产品上市的时间，降低产品开发、制造成本，并提高产品的市场竞争力。 三、绿色设计 绿色设计是指以环境资源保护为核心概念的设计过程，其基本思想就是在设计阶段就将环境因素和预防污染的措施纳人产品设计之中，将环境性能作为产品的设计目标和出发点，力求使产品对环境的影响为最小。 产品设计的基本流程为：市场调研--草图构思--方案设计。 四、可靠性设计 机电产品的可靠性设计可定义为:产品在规定的条件下和规定的时间内，完成规定功能的能力。可靠性设计是以概率论为数学基础，从统计学的角度去观察偶然事件，并从偶然事件中找出其某些必然发生的规律，而这些规律一般反映了在随机变量与随机变量发生的可能性(概率)之间的关系。用来描述这种关系的模型很多，如正态分布模型、指数分布模和威尔分布模型。 五、智能优化设计 随着与机电一体化相关技术不断的发展，以及机电一体化技术的广泛使用，我们面临的将是越来越复杂的机电系统。解决复杂系统的出路在于使用智能优化的设计手段。智能优化设计突破了传统的优化设计的局限，它更强调人工智能在优化设计中的作用。智能优化设计应该以计算机为实现手段，与控制论、信息论、决策论相结合，使现代机电产品具有自学习、自组织、自适应的能力，其创造性在于借助三维图形，智能化软件和多媒体工具等对产品进行开发设计。 六、计算机辅助设计 机械计算机辅助设计（机械CAD）技术，是在一定的计算机辅助设计平台上，对所设计的机械零、部件，输入要达到的技术参数，由计算机进行强度，刚度，稳定性校核，然后输出标准的机械图纸，简化了大量人工计算及绘图，效率比人工提高几十倍甚至更多。 七、动态设计 动态设计法是在计算参数难以准确确定、设计理论和方法带有经验性和类比性时，根据施工
Cognex VisionPro 软件简介及其目标识别定位功能 1、VisionPro主要功能：图像预处理、图像拼接、图像标定、几何校 正、定位、OCV\ID、图像几何测量、结果分析等，该软件可以直接和国际大多数相机相连，包括模拟、1394、千兆网相机等，且可以直接输出检测结果，提供二次开发接口、支持点net。在其QuickBuild环境中无需任何代码编程，只需拖拉操作就可以完成检查文件的设置，检测结果输出，可进行快速开发。 QuickBuild能与用户自己编写的点net程序无缝连接，实现数据共享，用户可以使用自己的I/O板。 2、VisionPro软件与Halcon对比： 开发方式：VIsionPro可以拖拉式图形编程，非常形象，同时也可以使用API函数编程，增加灵活性。VisionPro的QuickBuild提供更加高效快速的编程界面，能够迅速融合到用户程序中。QuickBuild提供许多成熟的视觉检测工具和设置界面，使用QuickBuild做评估测试和开发的效率远高于Halcon的Hdevelop。而Halcon只能用函数编程，没有图形编程界面，开发效率低于VisonPro。 视觉工具和函数：VisonPro的PatMax定位工具和颜色识别工具优于Halcon的类似工具。特别是PatMax定位工具可在图像模糊、对比度低、目标形变严重的情况下实现更稳定的定位和目标识别功能，得到了行业内广泛的认可。 支持的相机：两种开发软件都支持大多数相机，都可以编写自定义的 驱动。编写自定义驱动，Halcon提供更好的接口。 Cognex VisionPro软件的测试版可在下载 VisionPro定位工具简介： 安装完VisionPro后，有很多演示例程可以运行，且可以进行图像仿真。 以下是其中的一小部分以及我们客户中使用到的一些。 存在透视形变情况下的定位与高度识别 PatMax定位识别功能演示，形变、模糊、强干扰都不受影响 晶元定位 强干扰图像定位 对多目标在各种对比度情况下的稳定定位 严重缺失情况下的定位 强干扰下的OCV
无线传感网技术实验报告（三） 班级：微电子1101学号：0301110115姓名：杨海平 一，实验目的： 通过仿真实验掌握无线传感器网络的定位算法—质心定位算法。 二，实验内容： 在100*100M2的正方形区域里，有n个信标节点和一个未知节点，未知节点和新表节点的通信半径均为R，则： （1），当通信半径R=50M，信标节点个数n=6,12,18,24,30时，利用Monte Carlo方法，分别计算未知节点的实际位置与估计未知的平均误差； （2），当信标节点个数n=20，通信半径R=5,10,15,20,25,30,35,40,45,50m时，利用Monte Carlo方法，分别计算未知节点的实际位置与估计位置的平均误差； 三，实验方法： （1），在边长为100m的正方形中，产生一个信标节点为n，未知节点为1的随机分布图； （2），确定与未知节点相连的信标节点； （3），利用质心算法，对未知节点的位置进行估计； （4），每一组数据（信标节点个数n，通信半径R）需要仿真800次，得出该组数据下未知节点的实际位置与估计位置的平均误差。 四，实验分析过程： （1），实验内容一：当通信半径R=50M，信标节点个数n=6,12,18,24,30时，按照实验一的方法随机产生X，Y坐标为0~100的n个信标节点的坐标，再随机产生一个未知节点的X，Y坐标，然后判断n个信标节点是否能与未知节点通信，把能与未知节点通信的信标节点X，Y坐标相加，除以能与未知节点通信的节点数，即为用质心定位算法估计的未知节点个数，误差即为未知节点与估计未知节点坐标的距离。每组信标节点个数仿真800次，累加每次仿真的误差，取平均值即得到估计误差。 （2），实验内容二：思想方法与实验内容一相同，当信标节点个数n=20，通信半径R=5,10,15,20,25,30,35,40,45,50m时，每组通信半径仿真800次，累加每次仿真的误差，取平均值即得到估计误差。 五，程序 （1），实验内容一程序如下： clear all; close all; nbeacon=[612182430];%信标节点个数n=6,12,18,24,30 nbeaconi=5; error=zeros(1,nbeaconi);%误差数组error nunknow=1;%知节点个数为1 r=50;%通信半径r为50 optimes=800; for ni=1:1:5;%每组信标节点得到一个平均误差 errorsum=0; validtimes=0;%800次仿真中至少有一个信标与未知节点通信的次数 for optimei=1:1:optimes
《算法设计与分析实用教程》参考解答 1-1 加减得1的数学游戏 西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。 例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。 （1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2）算法描述 // 两数若干次加减结果为1的数学游戏 #include
图像定位及跟踪技术大解析 在科学技术日新月异的今天，人们对机器设备的智能性、自主性要求也越来越高，希望其完全替代人的角色，把人们从繁重、危险的工作任务中解脱出来，而能否像人一样具有感知周围环境的能力已成为设备实现智能化自主化的关键。 广义的“图像跟踪”技术，是指通过某种方式(如图像识别、红外、超声波等)将摄像头中拍摄到的物体进行定位，并指挥摄像头对该物体进行跟踪，让该物体一直被保持在摄像头视野范围内。狭义的“图像跟踪”技术就是我们日常所常谈到的，通过“图像识别”的方式来进行跟踪和拍摄。 因为红外、超声波等方式，都受环境的影响，而且要专门的识别辅助设备，在实际应用中已经逐步被“图像识别”技术所替代。“图像识别”是直接利用了摄像头拍摄到的图像，进行NCAST图像差分及聚类运算，识别到目标物体的位置，并指挥摄像头对该物体进行跟踪。 图像跟踪系统采用特有的NCAST目标外形特征检测方法，被跟踪者无需任何辅助设备，只要进入跟踪区域，系统便可对目标进行锁定跟踪，使摄像机画面以锁定的目标为中心，并控制摄像机进行相应策略的缩放。系统支持多种自定义策略，支持多级特写模式，适应性强，不受强光、声音、电磁等环境影响。 目标物体的边缘检测 物体的形状特征在大多数情况下变化不多，基于目标形状轮廓的跟踪方法与基于区域的匹配方法相比，可以更精确的分割目标。 边缘是运动目标的最基本特征，表现在图像中就是指目标周围图像灰度有阶跃变化或屋顶变化的那些像素集合，它是图像中局部亮度变化最显著的部分。 边缘检测就是采用某种算法来定位灰度不连续变化的位置，从而图像中目标与背景的交界线。图像的灰度变化可以用灰度梯度来表示。
定位算法调研 一、定位算法的研究意义 对于大多数应用，不知道传感器位置而感知的数据是没有意义的。传感器节点必须明确自身位置才能详细说明在什么位置或区域发生了特定事件,实现对外部目标的定位和追踪。用无线传感器网络进行目标的跟踪定位，就是综合传感器自身位置信息和网络节点与目标的关系信息，确定目标所处的地理位置。对于移动目标而言，连续不断的定位就是跟踪。传感器自身的位置信息，是实现目标定位跟踪的基础,而网络节点与目标的关系信息，则是实现目标定位跟踪的关键。另一方面，了解传感器节点位置信息还可以提高路由效率,可以为网络提供命名空间,向部署者报告网络的覆盖质量,实现网络的负载均衡以及网络拓扑的自配置等。b5E2RGbCAP 尽管现有的许多定位系统和算法能够较好的解决WSN自身定位问题。但依然存在如下一些问题: (1> 未知节点必须与锚点直接相邻,从而导致锚点密度过高。(2> 定位精度依赖于网络部署条件。 (3> 没有对距离/角度测量误差采取抑制措施,造成误差传播和误差积累,定位精度依赖于距离/角度测量的精度。(4> 依靠循环求精过程抑制测距误差和提高定位精度，虽然循环求精过程可以明显地减小测距误差的影响,但不仅产生了大量的通信和计算开销,而且因无法预估循环的次数而增加了算法的不确定性。(5> 算法收敛速度较慢。因此必须采用一定的机制改进或者避免以上问题，从而实现更高精度的WSN自身定位。p1EanqFDPw
二、定位算法的研究现状 从1992年AT&T Laboratories Cambridge开发出室内定位系统Active Badge至今,研究者们一直致力于这一领域的研究。事实上,每种定位系统和算法都用来解决不同的问题或支持不同的应用,它们在用于定位的物理现象、网络组成、能量需求、基础设施和时空的复杂性等许多方面有所不同。DXDiTa9E3d 根据定位算法中对节点位置的不同计算方式，可以分为集中式定位算法以及分布式定位算法。集中式定位算法把所需信息传送到某个中心节点,并在那里进行节点定位计算的方式。Doherty等[1]假定网络中存在一定比例的锚点，根据凸规划(convex optimization>来估计不确定节点的位置。MDS-MAP[2]则采用了多维定标的方法来提高定位精度。这两种算法都是典型的集中式定位算法，其后一系列的算法对该算法进行改进以提高节点定位精度。分布式定位算法是指依赖节点间的信息交换和协调,由节点自行进行定位计算的方式。质心算法中[3]，每个节点通过计算它所侦听到的锚点的中心位置来确定自身位置，如果锚点布置的比较好，则定位误差能够得到很好的改善。APIT算法[4]中的节点侦听自己附近锚点的信号，根据这些信号，APIT算法把临近这个节点的区域划分为一个个相互重叠的三角形区域。然后采用划分网格的方法找出自己所在的区域，如果能够侦听到足够多的锚点信息，这个区域可以变得很小，从而提高算法的定位精度。RTCrpUDGiT
Ex.1(p20)若将y ← uniform(0, 1) 改为y ← x, 则上述的算法估计的值是什么？解：若将y ← uniform(0, 1) 改为y ← x，此时有，则k++，即，此时k++，由于此时x ← uniform(0, 1)，所以k/n=，则此时4k/n=2。所以上述算法估计的值为2。Ex.2(p23) 在机器上用估计π值，给出不同的n值及精度。解：由ppt上p21可知，的大小，其中k为落入圆内的数目，n为总数，且π=，即需要计算4k/n。我们先令x ← un iform(0, 1)，y ← uniform(0, 1)。计算 的值，如果小于等于1，那么此时k++。最后计算4k/n的值即可估计此时的π值。代码的主要部分为： 执行结果为：
结果分析：随着N的取值不断地增加，得到的π值也就越来越精确。 Ex.3(p23) 设a, b, c和d是实数，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一个连续函数，写一概率算法计算积分： 注意，函数的参数是a, b, c, d, n和f, 其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。 解：的值为y=，y=0，x=a，x=b围成的面积。根据之前的例子我们可以知道 = k(b-a)d/n。其中k是落在函数y=，x=a，x=b以及y=0所包围区间内的个数。代码的主要部分为： 运行结果为：
结果分析： 随着N的取值不断地增加，得到的积分值越来越精确。 Ex4(p24). 设ε,δ是(0,1)之间的常数，证明：若I是的正确值，h是由HitorMiss算法返回的值，则当n ≥ I(1-I)/ε2δ时有： Prob[|h-I| < ε] ≥ 1 –δ 上述的意义告诉我们：Prob[|h-I| ≥ ε] ≤δ, 即：当n ≥ I(1-I)/ ε2δ时，算法的计算结果的绝对误差超过ε的概率不超过δ，因此我们根据给定ε和δ可以确定算法迭代的次数 () 解此问题时可用切比雪夫不等式，将I看作是数学期望。 证明：由切比雪夫不等式可知： P( | X - E(X) | < ε ) ≥ 1 - D(X) / ε2 由题目知，E(X)=I。且根据题意，我们可知，在HotorMiss算法中，若随机选取n个点，其中k个点在积分范围内，则。且k的分布为二项分布B(n，I)（在积分范围内或者不在 积分范围内），则。又因为k=x*n，所以D(X)=I(1-I)/n。再将E(X)和D(X)带入切比雪夫不等式中即可得到 Ex5(p36). 用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。解：由题知，集合的大小，通过计算新生成的集合中元素的个数来估计原集合的大小，代码的主体部分如下：
1有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下的，正面朝下的翻成正面朝上的；以此类推，直到翻得牌超过104张为止。统计最后有几张牌正面朝上以及它们的位置号。 问题分析：52张牌都有一个初始状态，即全部朝上。第一轮开始时，2的倍数位置改变，非2的倍数保持原样；第二轮开始时，3的奇数倍朝下，3的偶数倍朝上；第三轮开始时，4的倍数朝上，即2的偶数倍朝下，以此类推，直到牌数超过104，则进行状态统计。 算法设计：根据题意，首先对第一轮进行记录，算法则应该是依次对位置进行改变，用循环求解翻转问题。 算法分析：这个算法使用循环对牌进行逐层比较，算法复杂度为O（n+1），使用了52个空间的一维数组。 数据结构设计：用一维数组a[52]表示52张牌，设其初始状态为0。计数小于104时，第一轮开始进行翻转，下一轮即n+1轮开始分情况进行翻转，用整型shang 进行朝上个数的统计，位置则由i来确定。
算法如下： #include
现代设计方法综述及在农业机械领域的应用 令狐采学 随着科技的发展，许多新的成果被引人优化设计，特别是信息化技术的发展推动了设计方法的革命，开发了系列软件，其中包括：CAD、AN SYS、AD AM S、VB、VC等，这些软件各有特色，在应用上相互交叉。其中CAD软件是应用最广，对产业发展影响最大的软件，完全代替了传统的设计方法，使设计更加快捷方便，且具有记忆功能，使传输、保存、调用更加方便。ADAMS软件不但具备虚拟制造、试验和测试功能，而且通过二次开发还可以优化参数，VB和VC软件具有较强的可视性，适合机构的运动学和动力学目标的优化。优化是现代设计的核心技术。现代设计思想和方法大大推动了制造业的发展；反过来，每个设计者必须掌握现代设计方法，并熟练使用各种软件工具。 在国际上，航空、航天、汽车、军工制造业等率先使用现代设计的新技术，农机制造业相对滞后，一般来说在上个世纪相差3—5年，到本世纪时差缩短到l 一3年。在上世纪80年代后期，中国开始引入CAD技术。到本世纪已经推广到高校、研究院所和企业，随着应用和推广，CAD技术不断完善和拓宽，功能更加强大，现在任何机械设计单位如果在设计中不使用CAD软件几乎不可思议。其他软件也有了不同程度的应
用，中国技术力量的构架决定现代设计方法和软件工具首先被研究型高等院校应用，之后是普通院校和大型研究所，最后逐渐转入生产企业。但是现代设计的核心——系统的优化设计技术在国内应用较少，仅仅局限在个别的学科领域，这是因为系统优化首先要建立理论模型、采用适宜的优化方法、设计相关的优化软件的基础上，是一个难度很大的系统工程。例如，应用较为普遍的航空、导弹理论研究面对的介质是空气，其物理性质相对变化较小；而农业机械所处理各种物料，其物理性质差异很大，理论研究和优化方法有其特殊性，不能照搬其他理论和方法。现代设计方法的应用如果包括了系统优化则必须建立设计平台。本文在介绍现代设计方法的同时也将介绍课题组在建设平台方面所做的探索性工作。 1 平台的内容 1．1创新方法的建立 农业机械的创新有特殊性也有其普遍性。农业机械的创新首先是机构的创新，新的机构能够完成传统机构所不能完成的技术要求。机构创新由两部分组成：发现机构创新元素和找到实现创新元素的实施方案。两者都非常重要，但是对不同的项目，相对难度有所不同：有的发现创新元素难度大，有的寻求实施方案难度更大。 1．2理论研究成果
无线定位算法综述 一无线传感网络与节点定位 1. 无线传感网络中的关键技术 无线传感器网络作为当今信息领域新的究热点，涉及多学科交叉的研究领域，涉及到非常多的关键技，主要包括：拓扑控制；网络协议；网络安全；时间同步；定位技术；数据融合；嵌入式操作系统；无线通信技术；跨层设计和应用层设计。2. 无线传感器网络节点定位机制 无线传感器网络节点定位问题可表述为：依靠有限的位置己知节点即信标节点(锚节点)，确定布设区中其它未知节点的位置，在传感器节点间建立起一定的空间关系的过程。无线定位机制一般由以下三个步骤组成： 第一步，对无线电信号的一个或几个电参量(振幅、频率、相位、传播时间) 进行测量，根据电波的传播特性把测量的电参量转换为距离、距离差及到达角度等，用来表示位置关系； 第二步，运用各种算法或技术来实现位置估计； 第三步，对估计值进行优化。 3. 节点间距离或角度的测量 在无线传感器网络中，节点间距离或角度的测量技术常用的有RSSI、TOA、TDOA和AOA等。 4. 计算节点位置的基本方法 (1) 三边测量法
(2) 三角测量法； (3) 极大似然估计法。 5. 无线传感器网络定位算法的性能评价
几个常用的评价标准：定位精度；规模；锚节点密度；节点密度；覆盖率；容错性和自适应性；功耗；代价。 6. 无线传感器网络定位技术分类 （1）物理定位与符号定位； （2）绝对定位与相对定位； （3）紧密耦合与松散耦合； （4）集中式计算与分布式计算； （5）基于测距技术的定位和无须测距技术的定位； （6）粗粒度与细粒度； （7）三角测量、场景分析和接近度定位。 二典型的自身定位系统与算法 到目前为止，WSN 自身定位系统和算法的研究大致经过了两个阶段。第1 阶段主要偏重于紧密耦合型和基于基础设施的定位系统。对于松散耦合型和无须基础设施的定位技术的关注和研究可以认为是自身定位系统和算法研究的第2 阶段。 1. Cricket定位系统 未知节点使用TDOA技术测量其与锚节点的距离，使用三边测量法提供物理定位。 2. RADAR系统 建立信号强度数据库，通过无线网络查询数据库，选择可能性最大的位置定位自身。 在三边测量定位方式下，未知节点根据RSSI计算与多个基站的距离，然后使用三边测量法定位， 3. AHLos系统 AHLos算法中定义了3 种定位方式——原子式、协作式和重复式最大似然估计定位(atom,collaborative和iterative multilateration)。
计算机算法设计与分析习 题及答案 Prepared on 24 November 2020
《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。
实验四动态规划算法设计与应用 一. 实验目的和要求 1.加深对动态规划算法的基本原理的理解，掌握用动态规划方法求解最优化问题的方法步骤及应用； 2.用动态规划设计整数序列的最长递增子序列问题的算法，分析其复杂性，并实现； 3.用动态规划设计求凸多边形的三角剖分问题的算法，分析其复杂性，并实现。 4.选做题：用动态规划设计求解0/1背包问题的算法，分析其复杂性，并实现。 二．基本原理 动态规划是一种非常重要的程序设计方法，常用于求解最优化问题。最优化问题：给定若干个约束条件和一个目标函数，在某指定集合中求满足所有约束条件的且使得目标函数值达最大或最小的元素和相应的目标函数值，即：问题的最优值和最优解。 适用动态规划求解的问题的基本要素： (1)满足最优性原理：即一个最优化问题的最优解包含了其子问题的最优解。 (2)无后向性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也即，某状态以后的过程不会影响以前的状态，只与当前状态有关，这种特性也被称为无后效性。 (2)具有重叠的子问题：即问题被分解成的子问题存在互相重叠。动态规划方法对于这些重叠的子问题只求解一次，以提高算法的效率。 三．该类算法设计与实现的要点 动态规划算法求解最优化问题的步骤： (1) 找出问题的最优子结构。分析问题的最优解（最优值）的结构特征。 (2) 递归地定义最优值。根据最优子结构，确定最优值所满足的递归公式。 (3) 计算最优值。根据最优值的递归公式，采用自底向上的迭代或自顶向下的递归，计算最优值。 (4) 构造最优解。在求解最优值的过程中要记录下得到最优值的相应最优解的信息，并根据该信息构造最优解。 注意：在计算最优值时应保存相应的信息： (a) 已经求出的子问题的最优值（避免重复计算）。 (b) 最优解的有关信息。 动态规划算法求解其它问题的步骤： (1) 根据最优化原理分析问题的解的结构。 (2) 递归地定义问题的解。 (3) 计算问题的解。根据解的递归公式，自底向上或自顶向下地计算解，计算过程中注意保存已经求出的子问题的解。 其中，自底向上方法通过迭代来实现，适用于所有的子问题都需要解的情况，实现时要注意根据递归公式正确确定子问题的求解顺序。自顶向下方法通过递归来实现，适用于不必解所有的子问题的情况，实现时要注意标记子问题是否计算过，同一个子问题只在第一次递归调用时计算并存储结果。 四．实验内容 (一) 最长递增子序列问题
《算法设计与分析》课程报告 课题名称：工作分配问题算法 课题负责人名（学号）： XX 同组成员名单（角色）： 指导教师： XX 评阅成绩： 评阅意见： 提交报告时间：2013年6 月18 日
工作分配问题算法 计算机科学与技术专业 学生XX 指导老师XX [摘要]回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。 用回溯算法解决问题的一般步骤： 1 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。 2 确定易于搜索的解空间结构,使得用回溯算法方便地搜索整个解空间。 3 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。 关键词：工作分配问题回溯算法 问题描述：设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。试设计一个算法，为每一个人都分配1 件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。
由文件input.txt给出输入数据。第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。将计算出的最小总费用输出到文件output.txt。例如： input.txt output.txt 3 9 10 2 3 2 3 4 3 4 5 代码： #include
相关主题
文本预览