基于CBIR技术的计算机拼图教育软件平台设计（可编辑）

基于CBIR技术的计算机拼图教育软件平台设计（可编辑） 首都师范大学 硕士学位论文 基于CBIR技术的计算机拼图教育软件平台设计 姓名:刘宁 申请学位级别:硕士 专业:计算机应用技术 指导教师:葛庆平 20080407基于技术的计算机拼图教育软件平台设计 摘要 基于内容的图像检索是当前信息领域的重要研究热点。从研究内容来看,它 与数学、物理学、心理学等诸多学科密切相关,从技术基础上,主要包括图像技术、机器 视觉技术和数据库技术,而从发展应用来看,它与工业、通信、娱乐、医学、遥感等是密 切相关的。随着科学技术的进步,在数据快速增长、信息急剧膨胀情况下它会得到更多的 推广和应用。 基于其在社会经济效益的重要价值,计算机拼图教育游戏软件运用了的基本技 术,采用集教育性和娱乐性为一身的拼图游戏的形式,浅显易懂 地介绍和展示了基本的机 ’ 器视觉技术原理。 针对这样的背景,本课题研究图像中拼块形状的分析技术,并对利用拼块边缘特征进 行计算机自动拼接拼块进行了探讨,以及详细阐述了基于机器视觉技术的计算机拼图教育 游戏软件平台设计。并且我们将不同特征,如颜色、纹理和形状的分析方法做成动态链接 库供计算机拼图教育游戏平台调用,从而实现了系统平台代码和算法实现的独立性,为日 后维护和升级平台系统和添加验证新的算法提供了方便,具有良好的通用性和扩展性。本 文中介绍的技术 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 有较高的参考价值,有可能应用于破碎物品修复、考古瓷器碎片复原、 碎纸屑拼接等领域,具有广泛的市场前景。 论文的研究内容主要包括以下几个方面: .软件系统结构与设计,创建可以复用的类,便于在项目中很好地承前启后以及程 序的不断升级与维护。运用合理的设计模式进行软件结构的设计。 .计算机拼图教育游戏软件的实现与应用,其软件系统的代码量 达上万行。 .计算机拼图教育游戏软件中的形状分析算法研究。针对本系统的实际需要选择了 一种适合于拼块匹配的形状分析方法,包括拼块图像角点的检测和链码算法,应 用在拼块形状分析中的链码匹配技术。 .计算机教育拼图游戏软件中的特有问题,包括不规则拼块图像的自动生成和自动 拼接之核心控制算法??如何综合运用颜色、纹理、形状分析算法并统一到平台 中。 关键词:形状分析、链码、基于内容的图像检索、软件设计、拼图游戏 基于技术的计算机拼图教育软件平台设计 ? . ,’ , , . . ’ , , . , . ’ 盯., .’. ,. ,. . ., . ?基于技术的计算机拼图教育软件平台设计 .既 , , . .: . . .. . 也 . ,. .., , . .卯 . 血 ,.: ,首都师范大学学位论文原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立 进行研究工作所取 得的成果。除文中已经注明引用的内容外,本论文不含任何其他 个人或集体已经发表或撰 写过的作品成果。对本文的研究做出重要贡献的个人和集体,均 已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名: 叹、宁 日期: 彦 日 谚年 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定,学校有权保留学位论文 并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用于非赢利 目的的少量复制并允许论文进入学校图 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 馆被查阅。有权将学位论文的内容编入有关数据 库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规 定。 学位论文作者签名: 雷宁 日期:蜴年岁月败日基于技术的计算机拼图教育软件平台设计 第一章引言 .课题的研究背景 在全国中小学信息技术教育工作会议上.教育部决定从年起用到年左右的 时间在全国中小学普及信息技术教育.这对于科教兴国战略的实施具有十分深远的战略意 义。在信息技术教育的各个环节中,学生利用信息的态度、途径、方法即学生的信息素养, 在很大程度上关系到信息技术教育的成败。近年来.世界各国都普遍重视学生信息素养的 培养。我国基础教育课程改革纲要试行》中也渗透了把培养学生信息素养作为我国中小 学信息技术课程重要内容的观点。当前,我国正在进行新一轮中学课程改革,其中高中信 息技术课程的一个重要日标就是对高中生进行信息素养教育。 基于提高学生信息素养的宗旨,首都师范大学信息工程学院的诸位老师联合申请了院 级项目“北京市中学信息技术教育平台的建设。计算机拼图教育游戏软件的开发就是其 子项目之一。 基于内容的图像检索是当前计算机视觉、图像数据库与知识挖掘 等领域最活跃的研究热点之一.从研究内容来看,它与数学、物理学、心理学等 诸多学科密切相关,从技术基础上,主要包括图像技术、机器视觉技术和数据库技术,两 从发展应用来看,它与工业、通信、娱乐、医学、遥感等是密切相关的。随着科学技术的 进步,在数据快速增长、信息急剧膨胀情况下它会得到更多的推广和应用妇。 近年来,每年都有与相关的国际会议召开,如的, 等,还有一些新创刊的杂志,如: ,这方面的研究是这些杂志发表的论文的重要组成部分。近几年, 许多 . 国际上重要的杂志,都以此内容发表了专刊。如: ,, , 。目前,国内外很 多机构都在进行相关的研究工作,并取得了很多令人瞩目的成就。如:的舢,的,的等,国内的一些研究单位,如中科 院自动化所国家模式识别实验室、清华大学、上海交通大学、复旦大学等单位也进行了研基于技术的计算机拼图教育软件平台设计 究并开发了一些实验系统乜。 基于其在社会经济效益的重要价值,计算机拼图教育游戏软件运用了的基本技 术,采用集教育性和娱乐性为一身的拼图游戏的形式,浅显易懂地介绍和展示了基本的机 器视觉技术原理,揭开了科学的神秘面纱,激发学生对信息技术领域的兴趣,推动信息技 术教育普及和应用工作。 .理论价值和实际意义 ,是一种认知性游戏,它对于游戏者的 拼图游戏又称为七巧板,英文为 感知觉、观察能力、逻辑推理能力以及精细动作能力都有锻炼和提高的作用。它要求游戏 者洞悉“部分一与。全部一的关系,培养平面组合的意识,学习假 设、判断和想象能力, 提高挫折耐受力,建立自信培养耐心。电子游戏中的动作技能游戏、结构游戏、角色扮演 游戏可以锻炼游戏者的反应能力和手眼协调能力,而认知性游戏则可以使游戏者发展智 力、获得知识。 自上世纪年代初,国外学术界对拼图自动拼接问题开展了大量科学研究‘?,然而 先前的做法,主要是考虑到几何形状信息,没有考虑到其他有用的信息,如颜色、纹理作 为额外线索。鉴于这个事实,本课题将要进行拼图教育游戏即: 方面的研究,提出一种新的拼图求解器,其中用到颜色、纹理以及部分 边界信息。其主要过程为,摄像机读取散乱的图像拼块,经过图像采集卡将模拟信号转换 为数字信号并输入计算机,计算机进行图像预处理和图像分割后,分析各个拼块的颜色、 。 ~ 纹理和形状特征,根据其特征将分散的图像拼块拼接成一幅完整的图像。同时为了构建高 质量的软件,将按照软件工程的行业标准,运用最新的计算机编 程思想和技术,完成一个 易于使用、维护和升级的软件系统。 系统完成后可以为中学信息技术课程演示信息技术领域中人工智能技术和计算机视觉 技术的最新发展,展现计算机视觉的功能和应用。通过计算机自动拼图的过程,讲解计算 机视觉原理,使学生了解图像识别、图像匹配、图像融合等许多信息技术领域的前沿技术, 开拓学生的眼界,激发投身科学研究的兴趣,为本市的中学信息素质教育贡献出一份力量。 从深远角度上来看,系统中应用的技术方案,有可能应用于破碎物品修复、考古瓷器 碎片复原、碎纸屑拼接等领域,具有广泛的市场前景。 基于技术的计算机拼图教育软件平台设计 .课题的研究内容 本论文拟对以下几个问题开展研究: .软件结构与设计,创建可以复用的类,屏蔽不同颜色分析、纹理分析、形状 .分析算法,做到对外接口的统一,便于在项目中很好地承前启后,便于程序 的不断升级与维护。运用合理的设计模式进行软件结构的设计。 .不规则拼块图像的制作。 .自动拼接之核心控制算法一综合形状、纹理、颜色等因素的匹配程度衡量。 .拼块图像的常规处理,如拼块旋转、拼块拖拽、拼块间磁性粘贴等。 .形状分析算法,包括拼块图像角点的检测和链码算法,链码匹配等技术在形 状分析中的应用。 .本文的主要工作 本课题的主要任务和目的是针对计算机拼图教育游戏软件的特点,进行软件平台的软 件结构设计,解决项目中遇到的软件复用问题。利用计算机数字图像处理技术和计算机视 觉技术,研究适用于该系统的图像处理与分析算法。 解决的关键问题包括以下几点: .项目中的特有问题,包括如下几点: 不规则拼块图像的制作。 拼块形状分析算法。 自动拼接之核心控制算法一综合形状、纹理、颜色等因素的匹配程度。 .软件平台、结构与设计问题:由于接口、数据类型的不统一,造成软件成果很难复 用。采用适当的设计模式,构建可复用的类,提高软件开发的效 率。 .本文的组织结构 本文的第一章是引言部分,主要介绍该课题的背景及实际意义。第二章介绍了与 计算机拼图教育平台紧密相关的的关键技术。第三章介绍了二维形状分析的基 本理论,包括描述算法的评价以及基于轮廓和区域的分析方法,并且详细阐述了应用 摹于技术的计算机拼图教育软件平台设计 在计算机教育拼图游戏软件中的形状分析方法。第四章设计并实现了基于技术 的 教育拼图游戏软件,并对该系统的设计和实现的几大关键模块进行了详细 的阐述。第五章是对全文的总结及以后工作的展望。 基于技术的计算机拼图教育软件平台设计 第二章 基本技术 系统的关键技术可以分为以下几个:特征的提取与描述、特征索引组织与高维特 征向量的降维处理、图像相似性度量方法。本章介绍与计算机拼图教育平台紧密相关的特 征提取与描述和相似性度量技术。如前所述,为了提高图像检索的效果,引入了相关反馈 技术,因此本章也介绍了相关反馈的一些基本技术。 .特征提取与描述 特征提取是的基础。从广义上讲,图像特征包括基于文本的特征关键词、文本 标注等、视觉特征颜色、纹理、形状等以及语义特征。基于文本的特征主要是第一 代检索系统的技术,现在的第二代检索方法中主要使用的特征是第二种。而语义特征的提 取现在还是一个很困难的问题,没有一个成熟的解决方案。 视觉特征也可以分为两类;?类是通用的视觉特征,包括颜色、纹理、形状、空间关 系等,这类特征是所有数字图像中都客观存在的。另一类是面向领域的视觉特征,比如人 脸、指纹等等,这类特征往往与具体的应用有关,需要一定的领域知识。 图像视觉特征提取出来之后,需要用某种方式来描述它,这就是特征描述,特征描述 在中是一个必不可少的环节。通常特征描述采用向量模型,对图像特征进行分析得 到一个特征向量,然后用这个特征向量来表示图像内容。在图像相似性度量中往往就是直 接对这些向量的距离进行度量,特征向量之间的距离就反映了图 像之间的相似性程度:距 离越大,相似性越低:距离越小,相似性越高。 需要说明的是,虽然从图像中可以提取很多的视觉特征,但是由于人类视觉的主观性, 并不存在一种最佳的特征描述方法适用于任何应用。实际上,每种视觉特征都存在着许多 不同的描述方法,这些方法从不同的角度表达了特征信息。 一般来讲,一个好的描述方法应该能够具有足够的鲁棒性,即对图像噪声、图像处理 过程中产生的一些图像质量的变化等具有一定的不变性。同时,好的描述方法应该具有好 的区分性能,即对不同的图像应该能正确的区分开。这两个方面往往会有一些冲突,因此 需要在这两者中做一个折中。 特征描述可以分为两类:全局描述和局部描述。前者对图像的整体的特征进行描述, 基于技术的计算机拼图教育软件平台设计 而后者只是针对图像中的部分区域或目标进行描述。 最常用的视觉特征及其主要描述方法主要有: 颜色特征九田:颜色直方图、颜色聚合向量、颜色相关图、颜色矩。 纹理特征:灰度共生矩阵?、边缘方向直方图、基于小波变换的 纹理描述符刁、 纹理嘲。 形状特征:包括全局特征和局部特征。参见第三章。 . 空间关系特征射:像元、二维符号串、空间四叉树、符号图等。 .相似性度量 图像检索一般不是精确匹配,而是检索与例子图像最相似的一些图像。检索过程主要 就是计算查询图像的特征向量与数据库中的图像的特征向量之间的距离,用这种距离来衡 量图像之间的相似程度。常用的相似性度量方法有‘删“?:闵可夫斯基距离、二次式距离、 马氏距离。 .相关反馈 基于内容的图像检索通过图像的颜色、纹理、形状等特征来表示图像内容,根据这些 特征进行检索。虽然这些视觉特征能在一定的程度上反映图像的内容,但是它还远远不能 保证图像检索的效果。其主要问题就是底层图像特征与高层语义特征之间的鸿沟。因为, 视觉特征向量比如颜色直方图等的相似性度量与图像的语义和人类视觉的主观性并不相 符。人对图像的感知和认识是很主观的、并且受人所在的环境的 影响。不同的人对同一幅 图像有不同的认识、同一个人在不同的场合下对同一幅图像的认识也很可能不相同。而任 何视觉特征向量都只是对图像视觉内容的某个方面的一个简单反映,它不能描述图像的所 有视觉特征、更不可能反映人类视觉的主观性。所以通过图像底层特征进行检索的结果往 往不太准确,计算机认为相似的图像人可能并不认为相似,相反,人认为相似的图像反而 可能没有被检索到。 相关反馈技术正是为了解决这个问题而被提出的。它的关键的思想就是让人的感知主 动性参与到检索的过程中,让用户能够根据自己的检索要求对检索结果进行评价,并把这 种评价反馈给检索系统,系统根据用户的反馈修改系统的参数,从而改善检索的效果。 相关反馈技术最早是在文档检索中应用的一种技术“铂,它是一种有监督的主动学习技 基于技术的计算机拼图教育软件平台设计 术,用来提高检索系统的效果。在图像检索系统中,它通过由用户提供的正、负图像来改 善系统的性能。其工作过程如下:用户提交一个查询,系统返回检 索到的一系列图像,用 户对这些图像进行评判,标记出哪些是符合要求的正图像,哪些是不符合的负图像。 然后系统根据这个评判修改一些参数,使得下次查询的结果更加符合用户的要求。因此, 相关反馈需要解决的一个关键问题就是怎样根据正负反馈来修正系数。 最早的相关反馈算法是基于向量模型的,可以分为两类:查询向量优化 和相似性度量优化 。除了这两大类算法之外, 还有很多其它的算法,比较常见的有基于贝叶斯的反馈算法嘲等。下面介绍查询向量优化 算法和相似性度量优化算法。 查询向量优化算法根据用户反馈信息来调整查询点,使之更加接近理想的查询点,然 后用调整后的查询点去重新计算检索结果。常用的计算公式来调整查询向量田: 设珥和二分别表示用户反馈的正相关和负相关图像,则优化之后的查询向量’可以 通过下式计算: 一 .吧‖走乏一‘瓦互鳓 .中的图像数目。 其中,口,肛厂是常数,%,??.分别是反 相似性度量优化通过动态的调整图像特征的权重来改进检索结 果,它不需要将图像的 特征向量转变为权重向量,而是首先由归一化操作来统一不同特 征的权重,然后根据相关 反馈动态的调整它们的权重以改善检索结果嗍. 设权重矩阵定义为‘坞: ? ?缈.,?旧一 当一幅图像是正相关时,它的权重按下式调整: ? 国,彩‘,万一瞑,万厂一厂 其中万是万的平均值。 如果一幅图像是负相关时,它的特征权重按下式调整: ? 缈吼一艿 有关相关反馈算法的深入介绍参见嘲。 基于技术的计算机拼图教育软件平台设计 .检索性能的评价 常用的图像检索性能评价指标有两个,它们最早是用于传统数据 库检索评价,这两个 标准是查准率和查全率。给定一个查询,图像库中与其相似的图像 的集合记为,检索到的图像的集合记为,检索出的图像中正确相关图像的集 合记为,查准率就定义为一次查询过程中,系统返回的查询结果中正确图像数目在 所有返回图像数目中的比例。显然查准率越高则检索效果越好。查全率是指系统返回的结 果中正确图像的数目占图像库中所有正确图像数目的比例。查全率越高则系统检索效果越 好。这两个指标的定义式为: ? 查准率之丽 ’ ? 查全率躐 实际系统中往往要在这两个指标之间做一个折中,因为提高一个指标往往会降低另一 个指标。而且,如果图像库中相似图像比检索出来的图像数目还要多,那么查全率就没什 么意义了。 .本章 小结 学校三防设施建设情况幼儿园教研工作小结高血压知识讲座小结防范电信网络诈骗宣传幼儿园师德小结 本章对基于内容的图像检索中的几个关键技术做了一个简单的介绍,这些技术包括视 觉特征提取与描述、相似性度量、系统性能评价。 系统中广泛使用的视觉特征是颜色、纹理、形状、空间关系。每种特征有许多不 同的描述方法,不同的方法适用于不同的应用。没有一种对任何图像都适合的特征描述方 法。 相似性度量也是图像检索的一个重要步骤,传统的基于向量模型的相似性度量方法已 经被证明不适合于人眼的视觉特征。因此有一些新的相似性度量方法比如特征对比模型 被提出。但是由于新的度量方法还只是理论性的模型,不太易于实现,因此实际系统中基 本上还是采用向量模型来衡量相似性。 相关反馈是图像检索中的一种用户交互技术,它试图通过让用户的主观感知参与到检 索过程中来提高检索的效果。许多实验和实际系统也证明了相关反馈是一种行之有效的方 基于技术的计算机拼图教育软件平台设计 法。相关反馈的算法除了传统的查询优化和相似性度量优化之外,还有一些新的算法比如 基于贝叶斯理论的算法等等。 检索系统的性能评价也是所有检索系统应该关注的问题之一。用的最广泛的评价指标 就是查全率和查准率,也有一些其它的评价方法,比如中推荐的 等。 基于内容的图像检索目前主要还是采用图像的底层视觉特征来进行检索,由于语义鸿 沟的存在,使得现有的系统的检索效果还不令人满意。基于语义的图像检索仍然处在探索 阶段,还没有一个真正意义上的语义图像检索系统。尽管有相关反馈技术可以提高图像检 索的效果,但是并不能从根本上解决这个问题。因此图像检索到目前还没有达到可以实用 的阶段,仍然需要更深入的研究和探索、需要很多相关领域的合作和有关部门和企业的大 力支持。 基于技术的计算机拼图教育软件平台设计 第三章二维形状分析 .基本理论 二维形状分析技术可以分为三类:一类是根据形状的轮廓进行描述,称为基于轮廓的 形状分析,另一类是根据形状所占的整个区域来描述,称为基于 区域的形状分析。还有一 类方法不是针对图像中的目标来进行分析,而是根据图像中的边缘信息获得对整个图像的 形状特征的描述。 本章首先介绍形状分析方法的评价标准,然后介绍这三类方法中前两类的主要算法。 ..形状描述方法的评价标准 在形状描述研究中一个很重要的问题就是怎样评价一个描述算法的好坏。对于形状描 述算法的评价还没有一个统一的标准【】。 .标准中已经提出了几个形状描述符的评价准则,这些准则是:检索精确 、特征压缩 、通用性 、低 复杂度、鲁棒的检索性能 以及 由粗到精的描述 。 文献中一般都使用不变性旋转不变性、平移不变性、尺度变换不变性作为形状描 述的一个基本的评价标准,另~个评价标准是识别率查准率,即用某种描述符对形状 进行识别的效果。在本文中将使用检索系统中的查准率来分析和比较形状描述符的性能。 ..基于轮廓的形状分析方法 链码 链码通过一个具有单位长度和方向的线段序列来表示边界。典型的链码有禾方向链码 和.方向链码,通过给每个方向一个数字编码,就可以对线段序列中的每个线段进行编码, 从目标边界上某个点起始点开始,按顺时针逆时针方向遍历整个边界,就可以得 基于技术的计算机拼图教育软件平台设计 到对该目标区域的链码描述【,具体介绍请参照第三章第三节。 边界的链码与所选择的起始点有关,通常需要对链码进行规格化。 在某些场合,还采用链码的一阶微分来表示一个边界。只要简单的算出链码序列中相 邻两个数字所表示的方向之问的相差的方向数按逆时针计算即可。使用这种链码的好 处是它与边界的旋转无关。 等人研究利用链码直方图以及归一化直方图的方法来识别目标【?。归 一化的链码直方图是旋转无关的。 曲线段序列 复杂的边界可以用一组线段来近似的表示。具体介绍请参照第三 章第三节。 一个区域可以用一个多边形来表示,这些多边形的顶点就形成了对该区域的描述,这 可以通过边界的分割来获得。根据不同的精度要求,可以增加或者减少多边形的边数。用 一系列的线段来表示边界,主要的问题在于怎样有效的确定这些线段的端点。主要方法有 边界生长法【翻、容许区间法翻等。 还可以通过计算轮廓上的一些关键点来提取近似多边形顶点。这类方法主要是利用边 界曲率局部极大值,比如余弦法【】和弦长比法【。刘玉兰等提出了一种间接提取轮廓关 键点的算法,该算法把数字曲线分解为两条一维离散蓝线,分别找出这两条曲线上的尖点, 然后进行综合得到原始曲线上的尖点的集合,这些尖点可以作为边界近似多边形的顶点。 另一种边界描述方法是用曲线段来描述,称之为“常曲率一 方法 ,边界通常被分割成二次曲线,比如椭圆曲线、抛物线等。如果这些曲线段类型是已知 的,则可以对每一种曲线段赋予一个编码,这样就可以得到整个边界的一个编码串类似 于链码。 傅立叶描述符 当一个区域边界上的点被确定时,利用这些点就可以用来鉴别不同区域的形状。设 平面上有一条由个点组成的数字化边界,其中每一个边界点用其坐标‘,表示。从 任意点。,。开始,沿着逆时针方向遍历整个边界,依次经过坐标 五,。,屯,:??巾州。可以把这个区域看作是在复平面上,沿边界跟踪一周就基于技术的计算机拼图教育软件平台设计 可以得到一个复数序列叽。这个复数序列的傅立叶变换称为傅立叶描述子 乏,具体介绍请参照第三章第三节。 通常取前个傅立叶系数来描述轮廓。高频傅立叶分量描述的是图像的细节部分,而 低频分量描述的是全局的形状,因此,肘越小,在边界中所丢失的细节也就越多。 王涛等人提出了一种利用轮廓的近似多边形进行傅立叶描述的算法,并针对傅立叶描 述子对起始点的敏感性提出了一种解决办法【。 广义上的傅立叶描述符可以通过对边界函数进行傅立叶变换得到。边界函数可以是上 文说的边界复坐标,也可以是边界曲率函数、边界近似多变形、质心距离等。 小波描述符 设给定的轮廓函数为厂功,则的小波变换系数盯口,就可以用来作为轮廓的描 述【。有关小波变换请参考文献。 与傅立叶轮廓描述符相比,小波轮廓描述符能通过较少的点数以较高的精度来描述轮 廓信息,而且对小波描述符进行平移与尺度归一化之后不受轮廓的平移与尺度变化的影响 。同时,相对于傅立叶描述符,小波描述符受轮廓局部畸变的影响小【】【】。 杨翔英等【给出了小波轮廓描述符的平移归一化、尺度归一化算法,讨论了小波系数 的截断问题。 边界矩特征 一个区域的边界是一条闭合曲线,曲线上从某点开始逆时针遍历一周得到一个点的序 列.用复数表示为七尼耖七..?。则边界的,.阶矩为【】【】: 朋,专静纠 阶中心矩为: 七, 胪专势铲‖ 其中是边界上采样点数。对和辫归一化得:一,/群班,万‖,班。 归一化的矩特征具有不变性。基于技术的计算机拼图教育软件平台设计 ..基于区域的形状分析方法 简单的描述方法 对于目标的区域有以下几种简单的描述: 面积。面积是区域的一个客观属性,它反映了区域的大小。区域的面积可以由该区域 内所包含的像素的数目来表示。面积可以由其边界链码计算出来圈。 圆形度。圆形度定义为:/么。其中表示区域的周长,么表示区域的面积。它反 映了一个区域的致密性。对于圆形区域圆形度最小。 离心度。离心度定义为目标区域的两个互相垂直的最长弦的长度之比圈。 欧拉数。欧拉数是目标形状的一个简单的拓扑不变性的描述。设表示区域中连通分 量的数目,?表示目标中的洞的数目,则欧拉数定义为【: . 毒? 区域不变矩 函数的矩是概率论中的一个概念。从矩可以导出一些数字特征用于描述 形状。 二元有界函数厂的矩定义为划: 乓 一 矩不变量 是基于区域的形状描述方法。设图像已经分割成独立 的二值目标,设足表示图像中的一个目标,的垡阶中心矩定义为: ‖.?。,。覃 ,最 其中,,是目标的中心: :监 朋 . :塑 ‖,.,是旋转敏感的,以下归一化的肼是旋转无关的: 基于技术的计算机拼图教育软件平台设计 ‰象仃学, 在文献【习中根据这些归一化矩给出了个对目标的平移、旋转、 以及缩放无关的 矩不变量: 织‖。‖。 ??。一‖,‖己 丸?,..以’一珈. 协, 套笺瓷裟鬈篮.。厶:弧,慨】 ?以.? .似,‖.眇。‖’?。‖。 ‖”。‖.,‖.札.‖.?伽.‖’ 九伽.一‖.‖抽‖.一似.,‖.‖.伽.‖灿’/ ?‖一‖.‖,‖.‖.‖.‖. .形状特征提取 物体的形状是边缘轮廓形式的表现,图像分析的许多应用都可以简化为形状分析。形 状分析的目的就是简化原始图像并保留原来形状的主要特征。而物体轮廓边界的点众多, 为了减少信息冗余,因此选取角点作为关键特征。角点是图像的轮廓线上局部曲率变化最 大的点,和周围的邻点有着明显差异,能够充分描述边界形状的变化,含有图像中重要信 息,.并且数量少,对加快图像的处理速度具有重要意义。 在拼图教育游戏软件中,判断两个拼块是否相邻的主要依据就是某个拼块的上、下、 左、右方向上的边缘特征是否与另一个拼块的下、上、右、左方向上的边缘特征相同或者 大致相似。所以我们首先要提取出拼块图像的边缘形状特征。 ..角点计算方法 在提取拼块图像的上、下、左、右四边的边缘形状特征中,前提条件就是已知拼块图 像的上、下、左、右四边。所以角点的提取是形状分析的第一步。此前,人们提出过许多 检测角点的方法,如:利用链码跟踪到的轮廓点计算曲率来判定角点【】,运用方向导数来 检测角点阿等。根据应用中的拼块图案的复杂程度,本文采用了一种基于空间模板匹配的 角点检测算法。同时为了处理更为复杂、一般化的拼块图案,实验了改进的特 征检测原则提取二值图像中的角点检测算法,取得了一定效果。 鉴于?技术舶计算机拼图教育鞔件平台设计 基于空问模板匹配的角点检测算法 在项目前期,出于对问题的简化,每个拼块的角点成度直角.即在角点处,边的走 向由水平方向变到垂直方向,反之亦然。图 所示的是此类拼块图案。 窜 图.系统所用拼块 砷空间域中所用模板 判断左上角点检测模板为目标象素为白色,背景象素为黑色,为强调象素边界.特 用红色绘制轮廓: 角点坐标 , 舟点坐标 ,? 捕点坐标 ?标,产?标,酽删标 下角点检测模板为: 栅 角点坐标 角点坐标卸 角点坐标. 、 应用在简单拼块图案的角点检测算法 首先把拼块图像进行二值化,然后开始角点检测,大致步骤为: 从上到下.从左到右依次扫描二值化图像。 如果第一次发现满足左上角点模板的三种情况之一,则横向扫描最后一个白色 点,即右上角点,然后跣到步骤,否则继续扫描图像。 从下到上,从左到右依次扫描二值化图象。 如果第一次发现满足左下角点模板的三种情况之一,则横向扫描最后一个白色 点,即右下角点结束检测,否则继续扫描图像。基于技术的计算机拼图教育软件平台设计 改进的基于特征的角点检测算法,..与..提出的 即最小同值分割吸收核方法是一种直接利用图像灰度信息进行角点检测的方法,具有方 法简单,定位准确,抗噪能力强等特点。具体方法是:用圆形模板在图像上移动,若模板 内的象素与模板中心象素核灰度的差值小于一定阈值,如图.所示,则认为该点与 核具有相同或相近的灰度,满足此条件的象素所组成的区域称为“’’,统计 区域面积,最后将区域面积与一个几何门限比较以判断是否为角点。在二值图像中, 分别用和代表背景象素和目标象素,对于边界点的,其构成元素均为目标象素, 因此可直接统计以边界点为核的面积,即统计目标象素的个数,公式如下: ’ ?一 芝:,, ’ 其中,是以为圆心的模板,为模板中的目标象素。 ,一模板位予角点 一镁板位子背景中 一模扳位于目标物体 一模扳位予边界上 图. 原则中模板的位置 设圆形模板的半径为,分析圆形模板在边界线上移动时面积的特点,如图., 当圆形模板在位置时,面积刚好为圆形模板面积的一半:当模板位于时, 面积小于一半;当模板位于时,面积大于一半。图.中的和位于角点位置, 而是位于直线上的点,基于上述分析可知,边界角点的面积小于或大予圆形模板 面积的一半。检测角点方法如下:设需要检测边界曲线上小于等于度,类似图. 位置和大于等于度,类似图.位置的角点,偎表示圆形模板的面积即 圆形内象素的总个数;由扇形和圆的关系可知,面积比等于角度比,所以面积符 合以下条件的边界点为候选角点: ???旦或???旦 .尺 足 基于技术的计算机拼图教育软件平台设计 实际中常按对和进行取值。通常,角点附近会产生若干个候选角点,由于 角点一定发生在面积极值处;因此对小于的,可取面积最小值 处为真正的角点,而大于/的,取面积最大值处为真正的角点。但直接 使用此方法不但对图像边缘而且对其内部同样执行角点检测,而基于形状特征的图像匹配 与检索真正关心的只是目标形状边界上的角点;因此在扫描各点时,只对先确定为边界点 的象素点执行算法,可大大减少运算次数。于是对于原算法进行改进,改 进后算法的基本思想是在扫描原拼块图像的二值化图时,首先判断该像素值是否是,然 后判断八邻接方向的像素值为的个数是否大于,如果满足以上两条件则证明为边界点, 最后在边界点上执行算法,在保证角点提取正确性的同时,又节省了运算时间, 其简略 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 如图.所示。 图.应用算法求角点流程图 ..边缘跟踪及链码计算 边缘跟踪的目的是获得拼块图像的外部轮廓特征,为图像的形状分析做准备。 边缘跟踪效果的好坏主要取决于两个因素啪:第一个因素是跟踪的起始点的选取,起 始点的选取直接影响到跟踪的精确度,同时如果起始点选的不好,还给算法的设计增加难 度;第二个因素是跟踪准则的选取,准则即要便于理解和分析,又 要便于程序分析。常用 的二值图像闭合边界的轮廓跟踪算法是九: 基于技术的计算机拼图教育软件平台设计 ’ 首先按从上到下,从左到右的顺序搜索,找到的第一个黑点一定是最左上方的边界点, 记为。点的右、右下、下、左四个邻域点中至少有一个是边界点,记为。从开始 找起,按右、右上、上、左上、左、左下、下、右下的顺序找相邻点中的边界点。如果 就是点,则表明已经转了一圈,程序结束。否则从继续找,直到找到为止。 这种算法存在如下问题?: 轮廓的某些部分可能被迂回过去,如图.所示; 可能会围绕某个局部封闭的轮廓重复跟踪,回不到起始点; 需要对每个边界像素周围的八个点进行判断,计算量比较大。 右下角凸部被迂同过去 右下角凸部被检测劁 图轮廓跟踪算法【 因而在本论文中采用了“目标领域点边界智能跟踪算法一,该算法执行步骤如下: 第一个边缘点为某个角点。 搜索第个边缘点。 第个边缘点为当前边缘点,坐标为,第个边缘点为下一个边缘点, 坐标为。由于的个邻点是产生的侯选点,因此采用以下由到的 搜索方法: ?判别邻域中一像素的位置,用邻域编号表示。判别顺序为下、左、上、 右。也就是说,当其下邻点为,则;当其下邻点不为,而左邻点为,则; 当下、左邻点都不为,而上邻点为,则;当下、左、上邻点都不为,而右邻点为 ,则。 基于技术的计算机拼图教育软件平台设计 ?由一像素位置出发,逆时针方向在个侯选点中搜索卜像素,最早搜索到的卜 像素即为第个边缘点。邻点中的逆时针方向搜索意味着邻点编号不断加的运算。 搜索第,第,?边缘点,? 当搜索第个边缘点时,当前边缘点由移向,即中心像素为,的 个邻点为搜索的侯选点。由搜索的方法为从前一个边缘点出发,逆时针 方向在个后选点中寻找卜像素,最早搜索到的卜像素即为第个边缘点。用同样的 方法由搜索,由搜索等等,依次类推。 当搜索到另一方向角点时,跟踪结束。 由于该方法能够记忆上一目标领域点,寻找下一目标领域点时不必对领域点全部搜 索,这种智能性大大地缩短了边界跟踪时间,并且可以有效的避免死循环和遗漏小凸部?。 边缘跟踪结束后,我们已经得到了拼块图像四边的边界点横纵坐标。根据前后两点的 坐标值,进一步得到边链码,具体代码如下:数组元素是边界点横坐标,数组元素是 边界点纵坐标,打数组元素是边对应的链码值 . 】一一 一一坩】; 】一嘲】; 】一【】; 】一 一越】:; 一嘲虹】卸; 】一【】 一埘】; 卜嘲【】; 】一【】【】; ; ..链码去噪霸 链码是对目标轮廓的一种逐点表示方式,受噪声等的影响,轮廓上会出现一些不规则 的部分,因此在进行拼块边链码匹配前,需要采取轮廓平滑的手段来消除噪声干扰。平滑 可以通过将原始韵链码序列用较简单的序列代替来实现。我们采用图.的模板,其中虚 基于技术的计算机拼图教育软件平台设计 线箭头指示原始的在像素和像素之间的一连通链码,而实线箭头指示用来替换原始序 列的新序列。新序列与原始序列等价但较短。在图.中,对于轮廓的毛刺都被此法消除 了。 , , ? ?、 , 一 , 、, , , 一 二二二二二二 ????一? ? 图.基于链码的轮廓平滑模板 .形状特征描述 计算机能够正确拼接两拼块的取决因素注重于它们相邻边的形状,而拼块的纹理,颜 色的作用次之。因此如何表示形状以及比较形状问的差异具有非常重要的意义。在诸多形 状描述方法中,我们应当采取适合于拼块图案的一种形状描述符。 ..链码. 假使二值图像中某一目标的边界用值为的象素构成的连通路径包括四连通路径和 八连通路径表示。这里路径可以看成是由连接两个相邻象素线段组成的,如图.所示。 每一条线段都有一个方向,当沿着边界顺时一针遍历目标边界时,边界链上的方向可以按 照图.的方式编码分别对应与四向连通和八向连通链。这样,边界上相连线段的方向 码便构成了链码。如图.所示的四连通路径的链码为: 从路径的 左上角开始。可以看出,链码的形式与起点的设置有关。因为路径是闭合的,所以,由 于起点的设置不同而得到的不同的链码仍然表示同一形状。为了满足目标识别时单一性的 要求,可以循环移动链码,使由链码构成的整数数值最小,取这个最小整数为确定的链码。 链码表示边界的优点是具有平移不变性:缩放不变性,可以通过改变采样栅格的大小来实 现:旋转不变性可以用差分链码来实现,设.?。为链码,。。为差分链码,差分链 码可按下式计算: 一 ,.,?或,确 基于技术的计算机拼图教育软件平台设计 其中差分.是通过计算链码相对于它的前点甜,逆时针方向旋转度或度 的次数得到的。因为边界是封闭的,所以把最后一个元素、看作第一个元素的前点。 差分链码代表方向差分,因而具有旋转不变性旋转/角度的整数倍时具有旋转不变 性。在直角坐标栅格中旋转非特殊角度即不是/角度的整数倍,会改变边界的形状, 因此也改变了差分链码。 。 一?’ 厂 一? ? ’ . ?‘ ??? ?一 土、 图.边界的链码表示 。\ .夕 /。\..多边形近似 在一些应用中,数字图像边界提供的信息具有一定的冗余度,这时可以考虑用近似方 法描述边界。最常见的方法是逐段线性近似多边形近似方法。这种方法用一个与原边界 曲线相近的多边形来表示边界。为了获得满意的近似效果.可采用某种误差指标来衡量多 边形与原曲线相近的近似程度。假设从点到点的数字曲线用直线来近似,如图. ‘ 一 基于技术的计算机拼图教育软件平台设计 所示。令,...融为数字曲线上象素的坐标,.,, ?,为从,??出发 点到直线即矢量。垂直的矢量: . 一一置 距离一面表示直线与曲线上的点,的误差。近似度标准可以用均方误差 或最大误差锨表示: 最?而一硝‰瓣。五一面 /八., 一 。 \ / 图.用直线近似曲线的误差定义 用多边形近似曲线时,也可以使用同样的近似标准当然也可以使用其它多边形逼近准 则,如最大内部面积、最小外部面积、最小面积偏差等等。为了使多边形近似达到最优, 在选择多边形顶点时应使总体误差最小。利用迭代搜索方法可以解决这个问题,但是计算 复杂性高。 近似多边形的顶点数目在很大程度上取决于误差闭值。如果误差 闭值小,则需要大量 的直线段。多边形逼近主要有两种方法,分裂算法和合并算法。在分裂算法中,如果曲线 是闭合的,起点和终点】【要选择曲线上相对两侧上的点,这两个点将曲线分为两段.分 裂算法的优点是可以找到曲线的转折点,并用这些转折点来描述曲线。而合并算法用相反 的方式进行多边形近似。我们从曲线的一点出发,沿顺时针方向或逆时针方向遍历曲线。 对于每一点,检测到的误差,如果超过某一闽值,就将作为多边形顶点并以 为起点,重复上述过程。如果曲线是闭合的,则选择曲线上外凸的转折点作为。 多边形的表示方法对于起始点的选择具有很大的依赖,不仅是多边形的形状,而且多 边形的边数都可能发生较大的变化。而且先前规定的误差也制约着多边形的形状,同一形 基于技术的计算机拼图教育软件平台设计 状,对于两个比较接近的误差值,多边形表示可能存在很大的差异,从某一意义上说,形 状多边形近似形式关于先前规定的误差值不连续。 这种形状表示方法对于一般形状数据压缩具有很显著的优势,是 一种较好的形状数据 保持方法。基于这种表示法的形状识别可以转化为相应的多边形的识别,简化了问题。在 一些实际应用中,基于这种形状描述法的识别效果不是很理想,其中一个原因是由于在形 状表示中不同起始点的选择可能会造成相差较大的多边形表示形式,从而给进一步的形状 识别带来了较大的困难。而且基于这种表示法的形状识别对边界扰动很敏感,对自然界的 同一形状的形状表示不稳定,从而给形状识别带来很大的麻烦。 ..傅立叶描述符 傅立叶描述算法是针对边界的某个标记函数进行傅立叶变换,得到傅立叶系数作为描 述符。通常对于一个轮廓可以有多种标记函数,本节主要介绍基于边界复坐标的傅立叶描 述符。 图.显示了一个平面内的点数字边界。以任意点砘曲为起点,坐标对‰曲, ,,,,...,弘一.为逆时针沿着边界遇到的点。这些坐标可以用下列形式表示: 产和贴。用这个定义,边界可以表示成坐标的序列,贴】,,,,...。 我们还可以将每对坐标对看成一个复数: 矗七七痧七 对,....。即对于复数序列,轴作为实轴,轴作为虚轴。 .疗 几 孔图.一条数字化边界的点复数序列 对离散的傅立叶变换为:基于技术的计算机拼图教育软件平台设计 ? ? 口”吉?砖?删置 其中,,,?。复系数称为边界的傅立叶描绘子。其中是直流分量,只与形状 的位置有关,去掉不用。由剩下的.个傅立叶系数可以得到对形状的描述: 一 ,’...旅一 ..算法比较与分析 针对以上常用的三种特征描述子,我们需要选择一种适合于拼块形状匹配的形状描述 子。从理论上,我们首先排除了傅立叶描述符。这是因为 物体的形状是封闭曲线,可以表示为一个以形状边界周长为周期的函数,才可 以进行傅立叶级数展开。对于拼块形状匹配,我们需要的是拼块四个边缘的局 部轮廓信息,而不是整个拼块的全局轮廓信息。 由于不同拼块的边缘长度不尽相同,甚至差别很大,例如在等同角点距离条件 下,一条有凸包的竖直边长度必定大于无凸包的竖直边。如果直接用轮廓坐标 序列来求傅立叶描述符,则不太适合形状的匹配。因为形状的相似性通过特征 向量之问的距离来表达,这就要求不同轮廓的傅立叶描述符特征向量维数应该 相同。 为了解决问题产生数目相同的傅立叶描述符,往往先对所有轮廓进行采样, ? 得到相同数目的采样点。然后由这个采样点序列求出其傅立叶系数用于形状之 问的比较。但采样算法又不能保证很好的保留原始轮廓的形状信息,尤其当轮 ? ? 一‘ 廓变化很大时,一些关键的拐点很可能没有被采样到,这样就导致了有可能丢 失一些关键的细节信息。 比起多边形近似方法,由于链码表示原始形状无任何误差,具有更好的数据保持 方式;并且计算简单,故我们最后采用了八方向链码表来示各拼块图像的边缘信息。 .形状匹配 ..边界链码直方图 基于链码的形状识别方法易受形状边界噪音的干扰。】提出了边界链码直方图的 基于技术的计算机拼图教育软件平台设计 方法匹配形状,有很好的抗边界扰动能力。这种表示方法的主要思路是对不同形状的边界一 链码值进行统计,并对直方图中或个值按值的大小进行排序,从而建立直方图,设 形状,的边界链码直方图中的或个值分别为【】,,,,或,, ,,,,,,定义形状距离如下: ???????????????????????一 ?一 . ? 、?【七】一四,?碱这种方法对于形状识别实现速度快,但不适 合识别率要求较高的问题。因为在构造链 码直方图时丢失了很多边界信息,对于同一链码直方图有很多对应的拼块形状如图., 故这种识别法仍具有一定的误识率,这种方法应用于拼块形状识别前的粗识别效果很好, 不仅速度快,而且简化了形状后面的进一步识别。 图.具有同一链码直方图的不同边界形状 ..直接比较法 直接比较两拼块相邻边的边链码元素值,同时统计其差异值。两拼块在位置上相邻的 原则就是其相邻边的链码匹配相等,但实际由于误差的引入,即使两边相邻,也不可能两 边链码完全相等,但至少在与其它拼块边链码差异上达到最小。这里需要注意的是,假定 有两个边链码和,需要先对和进行反方向编码,即一个按顺时针编码,一个按逆 时针编码,但邻域搜索的准则是按逆时针编码。需要我们对或取逆后再匹配,即对 于链码的每一个码值加后除以的余数赋给原码值。 ~. 一基于技术的计算机拼图教育软件平台设计 .本章小结 本章介绍了二维形状分析的两个主要方面的内容:描述算法的评价以及两类分析方 法,即基于轮廓的算法和基于区域的算法。 通用的评价方法是旋转、平移、尺度不变性。在检索系统中,这几个不变性是基本的 要求。仅满足这几个不变性还不能足以证明算法的检索性能,所以一般还采用识别率来衡 量检索性能。 然后主要介绍了应用在拼块匹配上的形状分析方法,包括其过程的各个步骤:形状特 征提取、形状特征描述、形状特征匹配。基?【拄术的计算机拼图教育软件平台设计 拼图教育游戏软件 第四章 .系统概述 拼图教育游戏软件为教育游戏软件,它是纸质拼图游戏的计算机版本,提供 手工拼图和自动拼图两种功能。其中手工拼图在计算机屏幕上显示拼图的碎块即拼块,利 用鼠标移动拼块,对照原始图案最终完成拼接整个图案。拼接过程需要游戏者对图案的颜 色、纹理、形状以及图案的内容有较深刻的理解,不断地进行识 别和思考,是一个锻炼思 维能力的益智游戏。第二大功能为计算机拼图,它利用计算机视觉技术,摄取图像,提取 图像特征,针对图像的颜色、纹理和形状等特征进行分析,最终实现计算机的自动拼图。 此功能可以为中小学生演示信息技术领域中基本技术,展现计算机视觉的功能和应用,引 发学生学习兴趣,为提高教学质量和学生素质提供一个有用的工具。 .库和库开发,该软件运 胛拼图教育游戏软件采用. 行后主界面见图。 。 妊:《“’ 一. ~。, ,一二一、。譬? ???? 野一‘?,“?”一“。‘一’ 闰.盯拼图教育游戏软件主界面基于技术的计算机拼图教育软件平台设计 ..软件功能分析 拼图教育游戏软件主要由手工拼图、自动拼图和项目选择三大功能。?项目选 择又分图片选择、难度选择和不规则拼块图像制作;手工拼图又分拼块拖拽、拼块旋转、 拼块磁性粘贴、发音提示、时间 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 、待拼接图预览、历史成绩查询、背景颜色音乐选 择;自动拼图又分驱动采集、图像分割、颜色分析、纹理分析、形状分析、效果演示和原 理简介。对于图像摄取功能和原理简介功能,将在软件后续版本中加入。具体如图.所 示: 图. 教育拼图游戏软件主要功能用例图基于技术的计算机拼图教育软件平台设计 .系统设计 ..体系结构设计 系统结构 典型的系统的框架如图.所示,用户通过人机交互界面选择某幅图像,然后提出 感兴趣目标的几何形状或所需图像背景颜色等发出查询请求,系统将查询要求提取输入图 像的特征向量,再借助这些特征向量与特征库中信息进行匹