您好、欢迎来到现金彩票网!
当前位置:彩63彩票app下载 > 高维索引 >

高维多媒体数据索引算法研究(可编辑)

发布时间:2019-04-23 21:54 来源:未知 编辑:admin

  高维多媒体数据索引算法研究浙江工业大学硕士学位论文 高维多媒体数据索引算法研究 作者姓名: 陈红艳 指导教师: ,导下,独立进行研究工作本论文不包含其他个人或 集体已经发表或撰写过的研究成果,也不含为获得浙江工业大学或其它教育 机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体,均已 在文中 以明确方式标明。本人承担本声明的法律责任。 日期:砂年月日 作者签名:储、斟纱高维多媒体数据索引算法研究 随着数据采集制作设备的日益普及,人们越来越方便地生产图像、图形、音频、视频、 动画和三维模型等多媒体数据,这些多媒体数据具有异构、非结构化、高维 和动态变化等 特征,给后续处理例如分类、聚类、挖掘、理解和查询检索带来巨大困难。 基于内容检索 方法的出现为多媒体数据查找开辟了一条新的途径,而高维数据索引是加速 相似性检索的 关键技术之一,也是多媒体和数据库领域的研究热点和难点。本文就是对高 维索引进行深 入研究,并取得了一定成果。主要包括以下两个方面: .对基于高维索引结构.的查询算法和范围查询算法的近似化,分别提出基 于.结构的算法和算法。.结构虽然使用过滤机制过滤不必要的 分支,大大减少了计算量,但当维数较高时,性能还是急速下降。而近似检索 则被认为是 适合高维的算法,所以对基于.的查询算法的近似化能更好的适用高维数据, 以精度 换取效率。算法扩展了查询的过滤的条件,更大程度上的过滤分支,减少不必 态的查询半径,最后通过分析实验数据,证明了近似检索算法的有效性。.对近似高维结构中心点选取方法的优化和选取数量的确定,提出维数区分 方法以 高效的查询。高维索引结构预计算数据集对于锚对象集距离顺序,对数据 库进行预测规整,只需精确计算少量数据就到得到大部分的正确结果。其中 选取很大程度上影响了索引结构的性能,而结构中的随机选取方法并不能保证效率的可 靠性,而选取的数量也是影响效率和准确率的一个很大因素,选取越 多准确率越高,但同时其效率大大下降,而选取的越少效率提高了,但其准确 率又得不到 保证。本文就针对这两个问题作了研究,基于最佳的两两之间的距离尽可能 效性。最后提出了维数区分方法,得到最优的选取数量,实验数据表明此方法在得到一个可接受的准确率下,确保选取的数目最少,效率最高。 关键词: 基于内容的检索,高维索引结构,.,索引结构,近似检索黟,. 基于内容的多媒体检索系统的研究....基于内容的检索系统的体系结构..基于内容检索的关键技术?.. 高维索引技术?..高维索引的基本定义?. ..聚类技术的分析. ..高维索引的关键技术?. ..高维索引技术发展趋势 算法..兴趣点检测 实验结果和分析.本章小结第章 基于高维索引结构.的近似检索?. 的插入算法..的查询算法. 基于.结构查询算法的局限性 基于的近似检索算法..基于的算法?一 ..基于:的算法?.. 本章小结第章高维索引结构构建方法的优化. 高维索引结构.. 索引结构的构建?.. 索引结构的查询算法 ..排序关系的相似性度量 的不同选择方法..维度区分方法?.实验结果和分析.. 的不同选择方法的实验分析?.. ..维度区分方法的实验分析.本章小结第章总结与展望?。 总结?.展望? 参考文献. 攻读学位期间参加的科研课题及成果?.现形式,通常将文本、图技术的飞速发展,多媒体 广告、家庭生活、公共信 们能访问的多媒体信息量 效的多媒体信息索引机制 已经成为迫切需要解决的问题,这也是国内外的研究的热点。 .多媒体检索技术的发展 传统的检索方法是基于文本的查询方法,它建立在信息手工注释上,充分利 用已有的 成熟的数据库技术检索,但它的不足之处也是明显的,手工注释工作量太大 和注释信息的 不全面。可见,在大量信息充斥的今天,基于文本的检索已越来越不能适应网 络信息检索 的要求。 随之发展而来的基于内容的检索,通过提取多媒体对象的颜色、纹理、形状、 空间关 系等特征,并应用特征表示和转化技术把提取的特征转化为高维数据点,通 过两个对象的 相似性匹配,得到所需的多媒体数据。基于内容的检索技术有以下的几个特 基于内容的检索是突破了传统的基于关键字的检索的局限,它直接对图像、视频、 音频等内容进行分析,抽取特征和语义,利用这些内容特征建立索引,并进行 检索。 基于内容的检索是一种相似匹配。在检索过程中,它不像传统检索方法仅支 持精确 匹配,更主要的是支持相似匹配,如范围查询和最邻近查询,得到最相似对 象。因为,即 使是相同内容的图像会因为表现形式的不同而不近相同,如远景拍摄和近景 拍摄,或不同 角度拍摄,都是相同的对象,但并不是完全一样。 加入相关反馈手段优化检索。计算机语言所能表示对象的颜色和相似性等跟 知认识存在一定距离,加入人工反馈机制,检索系统通用学习用户的认识和意图来指导检 索过程,提高检索系统的准确性。. 基于内容的多媒体检索 涉及多 个领域,如人工智能,模式识别,数据挖掘,图形处理,信息检索等‘】【】。基 于内容的检图. 系统的执行机制 提供输入接口供用户输入查询的多媒体对象,然后提取各对象的特征值,不 的多媒体对象特征提取的方法也不相同。如图像检索的主要特征有颜色、形状、纹理空间 关系等,音频、视频则包含更多的特征信息,如频率,运动等。对特征值的高 维检索后返 回相关结果给用户,用户可对结果是否满意做出评价,再反馈给系统,系统自 动修正检索 机制。 由于目前的多媒体技术有限,很难建立通用的系统,针对不同的应用实现引 一些与领域相关的高层知识是十分必要的。例如,在医用图像检索系统中,如果能够结合 医学领域的专业知识来提取图片信息就更加有实用价值。在人脸识别系统中, 如果能够结 合人脸部特性,检索的准确率则会大大提高。 ..基于内容的检索系统的体系结构 系统可以划分为两个子系统:特征提取子系统和查询子系统。如下图所示: 的体系结构预处理主要是对多媒体信息的格式转换和统一,并进行放大和去噪等功能。 目标识别是标识出用户感兴趣的区域,针对此区域进行特性的提取。用户可 以参与 标识工作,以便更完整的解读图像、视频镜头的代表帧、视频序列等媒体信 以的局部性的用户感兴趣的区域。数据库包括多媒体库、特征库和知识库。多媒体库存储着多媒体信息文本、 图片、 视频、音频等,特征库包含多媒体库中对象的特征,知识库中的知识是用来优 化检索系 查询接口指的就是交互界面,用户通过这个接口来使用查询系统,并通过这个接口 得到查询结果。 检索引擎主要实现多媒体对象的相似性度量。 索引/过滤采用一定的过滤机制过滤掉那些与查询对象无关的对象,然后再 进行匹 ..基于内容检索的关键技术...多媒体对象特征提取 特征的提取是基于内容检索系统的关键技术之一,从本质上来看,实际上是 于特征的检索。特征提取模块提取出多媒体数据本质的特征,这些特征通常用特征向量或 描述子来表示。选择适当的特征是很重要的,这直接影响数据检索的好坏, 因为它是对象 识别的唯一依据。特征向量必需有如下【】特点: 可区分性。作为多媒体对象的唯一标识,必需能代表对象,区分对象之间的不 可靠性。对于相似的对象,特征向量也应该是相似的。独立性。所有的特征之间即特征向量的每个维度是相互独立的,因为相关特 可以用其它特性表示。如有起始时间、结束时间、时间间隔三个特性时,时间间隔不是需 要的,它可以由起始时间和结束时间间接得到。特征之间相关性越高,信息冗 余越大。 数目极小性的特点。数据检索的复杂性随数据的维数迅速增加,为了检索的 效率, 特征数越少越好。 这些特点体现对象最本质、最主要的特性,保证了不同的多媒体对象特征显 著不同, 而相似的对象特征相似的,并且特征值尽量不冗余。 ...多媒体查询 ....索引结构 由于多媒体对象本身包含丰富信息,如颜色,位置,形状,纹理,频率,运动等 特征浙江工业人学硕士学位论文 索到有“老虎”的内容,这可能也是我们想要得到的。但基于内容的多媒体 检索时用户输 入的是一张自己拍摄的某种花卉的照片,目的是查看这种花卉的相关信息, 在数据库中是 无法找到一模一样的图片的,但可能会返回与有此花卉的类似图像。所以基 于内容检索主 要支持的是相似性查询,常用的相似性查询方法有:. 查询和范 围查询【 】。查找返回的是与查询对象最相似的个对象,而范围查询则是查找与查 询对象距离小于给的值,.的所有对象。 基于内容检索技术的研究始于年代初,发展至今已有十多年了,基于一些商 研究目的,人们开发了许多基于内容的图像检索系统【】。其中比较有影响的系统有 的难点分析在系统中具有挑战性的问题包括特征提取,数据预处理,高维数据检索,性能 评价准则,查询优化和相似性查询。 特征提取 查询的前提是数据已经存在并以能被检索的状态表示,这就是特征提取的工 作。颜色特 征是应用最广泛的视觉特征之一,很多的特征提取方法都是基于颜色的,如 颜色直方图【】、 颜色集【】,颜色矩【。纹理】和形状【】也是普遍使用的特征。 数据预处理 数据预处理主要采用数据聚类的分析方法。聚类需要抓住数据的‘自然’结 构,通过 聚类分析方法聚类数据,把数据划分成有意义或有用的簇。每个簇距离相近、 性质相似, 具有一定的整体性质,一般采用一个数据对象选取方法可能不同代表簇,查 代表来进行判断,提高检索效纠。聚类技术旧主要有分裂法、层次法、基于 密度的方法、 基于网格的方法和基于模型的方法。 高维数据索引 高维数据索引通过对多媒体数据集以某种有效的方向进行构建,使之能快速 查询。在 高维检索领域中最大的难题就是“维数灾难”,“维数灾难是指在维数较高 时高维查询的 效率随维度增加迅速降低,甚至低于线性查询的一种现象。线性查询在很多 树型高维结构 中用来作为比较索引方法是否有效的尺码【】【性能评价准则 合适的评价准则是系统重要的一部分。性能评价准则应该能反映系统的准浙 江丁业大学硕士学位论文 确率和效率。查准率.召回率曲线是一种比较成熟的评价方法,适用 于任何索引方法。标准化的和/时间测量性能也是一种常用的方法。还有一 合特定结构的评价标准,如向量选择率用来评价向量近似方法,分支裁剪率特定用于树型 索引结构。评价标准是不同类别的不同索引结构之间的桥梁, 评价标准通常 是提高检索 性能的指导者【。 查询优化 计算机视觉模式识别和图像检索系统最基本的不同是人类在其中的作用。对 于图像检 索系统而言,用户参与是必不可少的。最近的研究重点是人机交互系统,用反 馈技术优化 查询结构。一个反馈系统允许用户修正图像查询结果,指出哪些是相关的, 哪些是不相关 的。通过反馈结构,系统自动修正检索机制以提高查询结果的质量【】【。 相似度度量 选择一个有效的、茁壮度量方法是至关重要的。基于内容的多媒体检索则通 过计算查 向量的相似性可以用多种方法 询对象和候选对象之间在特征向量上的相似度进行匹配。 进行度量,一般分为距离度量和非距离度量两大类,最常用的是距离度量【冽 .高维索引技术..高维索引的基本定义 基于距离的相似性度量,顾名思义就是计算特征空间中对象与对象之间的距 /距离也叫印距离,其中当时,为距离,也叫妒距离: 用印距离度量的特征值是相关独立、正交的,因为大多数的特征向量满足这个特征, 所以印距离在检索系统中有很广泛的应用。其中最常用的是欧氏距离,因为 它比较简单, 且具有空间不变形的特性,本文中的相似性度量都采用欧氏距离度量。 ..聚类技术的分析 聚类技术是基于数据对象间关系信息将对象划分成多个簇的过程。同一簇中 的对象具 有很大相似性,而不同簇中的对象之间则有很大差异性。聚类技术主要有以 下几种: ...基于中心对象的方法 .算法就是最典型的基于中心对象的方法。.算法以设定一个参数, 把所有数据对象分成个簇,以使簇内对象相似度较高,而簇间的相似度较 算法的划分过程如下:首先随机地选择个对象,每个对象代表初始簇的中心。然后根据数据对象与 心对象的距离划分,每个对象划分到它最近的簇中。接下来对划分的簇重新计算中心值, 数据重新分配。如此反复,直到簇中对象不再发生改变。其中一般采用欧式 距离来衡量对 象之间远近。 当数据簇是密集的,而簇与簇之间差异比较大时,.算法的效果比较好。但 .算法并不在任何情况下都有较高效率,当数据独立分布时,聚类往往不能达 人满意的结果。对于处理大数据集,该算法有较高的效率。.的最大问题是值的确 定,它的选取一般都基于一些经验值和实验结果,还有.算法对噪声和孤立点 比较 敏感,这类数据会严重影响聚类的结果。 ...层次法 层次法是将数据集通过聚类构建成一个树形结构的过程。层次法可以分为两 向下的方法和自底向上的方法。自底向上的聚类:该方法首先将每一个数据对象作为一个单独的类,然后将 这些 单个数据的类一步步归并,形成越来越大的类,当所有数据对像都在同一个 类中,或者达 后逐步细分,划分成为越来越小 的类,当每个数据对象都在单独的一个类中,或者达到某一终止条件时结束。 层次聚类法典型的是算法【】。算法在开始时每一个数据对象都是一个簇, 然后将距离相近的簇合并成一个簇,直到簇的个数是所要求的为止。 ...基于密度的方法 基于中心对象方法和层次法基本上都是基于数据与中心对象的距离来衡量 数据和此 簇之间的相似程度,所以簇的形状基本是圆形的,而基于密度的方法可以解 决只发现“圆 形簇的缺点。算法【】就是一个基于密度的聚类算法,基本思想是给定一个 最小 对象个数/,在给定半径区域的对象数不少于/。但算法的缺点是对给定的 和半径参数很敏感,且这两个参数很难确定。 ..高维索引的关键技术 和度量空间 高维索引技术大致可以分为两类:向量空间检索 检索 构主要利用三角不等式性质,裁剪查询支路,加快检索效率。而向量空间是度量空间的特 例,向量空间满足度量空间的所有性质,但向量空间多了坐标信息。所以向量 空间可以看 做是一个带有坐标信息的特殊度量空间。 根据度量空问的定义,度量空间只有距离函数可用,不管是在构建索引结构 还是查询 过程中,唯一用到的就是三个距离函数的性质。在相似性查询时,算法的主要 代价是计算 相似性的代价,因此,度量空间索引结构的设计考虑的是尽可能减少对象的 比较次数。而 在向量空间中,除了可以利用距离函数的性质外,更主要的是坐标信息,通过 坐标能直接 定位,在划分的空间中迅速查找。它的查询代价主要是/读取的代价,所以向 量空间主要 考虑的是减少/次数。很多结构都是基于向量空间的,如.【,幸.,., ..引。由于度量空间的索引结构适应更普遍的应用需求,近年来,度量空间检 浙江工业大学硕士学位论文速发展起来,如.,.,。 ...向量空间检索技术 ..是一种高维二叉树,它的结点分为叶子结点和非叶子结点,非叶子结点包 性、属性划分值和指向左右子树的两个结点指针,通过属性划分值将此维度上的特征对象 分成大于属性划分值的部分和小于属性划分值的部分,并分布将特征值划入 左右子树中。 叶子结点则覆盖了所有数据对象。在维情况下,..第一层按第一维划分,第二 第二维划分,依次类推,递归地将空间划分成不相交的子区域。因为子区域之间不相交, 每个数据只属于一个子区域,这样对象的查询路径就是从根结点到叶子结点 的分支,但当 数据量很大时,树高较高,查询耗时,特别是当维数增加时,由于高维数据分 布的集中性, 会导致..结构创建一些空或者几乎接近空的叶子结点,因而,空间利用率较 .是.在高维空间上的应用和发展,它是高维索引中最重要的一种结构,很多索引结构都是在它的基础上演变出来的。是一种动态平衡树,有比较高的空 间利用 率。.有两种结点,叶子结点和中间结点。中间结点存储空间索引范围,具体 数据对 象保存在叶子结点中。采用最小外接矩形来划分数据,根结点表示整个数 据空间,其每个孩子结点代表其中的一部分子空间,如此划分下去直至叶结 点。因为. 的允许重叠,当维数较高时,之间的重叠迅速增加,查询时访问结点数和访问 的树结构浙江工业人学硕十学位论文 .是.的变种,它在结构上与基本相同,但它在插入和分裂过程中进 行了改进。.在插入新对象时,按“覆盖面积最小化的原则选择子树,而幸. 入算法不仅考虑了“覆盖面积”,还考虑到目录矩形的重叠,选择最小重叠 代价的子树插 入,然后再考虑最小覆盖面积的子树。在分裂过程中引入“强制在插入策略, 结点分裂前对分布边缘的数据对象重新插入,是它们有可能分布在不同的结点,优化树结 构,改善了的性能。的像检索系统就是采用了此结构。 .是对对.的改进。.在低维检索中性能和木.不相上下,但在维度较高 时检索性能远优于,.是一种比较适合高维检索的数据结构,这是因为它的算 法做了两方面的改进:一是无重叠分裂;二是采用超结点。超结点在属性上与 普通节点类 似,但它的容量更大,大大增加了树的扇出,降低了树高,减少分裂次数,保持 定性。...度量空间检索技术 是一种二叉树,它先选取一个元素,即优势点,作为根结点,根据与根结点的距离把剩下的元素分成两部分,再在这两个子树中选取各自 的优势点划分 数据对象,依次类推,递归的分割数据集。查询时,.禾用三角不等式裁剪数据, 滤掉不必要的分支,减少相似性查询的开销。但由于数据的扇出数小,树结构高度比较 高,导致查询操作耗时。是一种能反映潜在数据固有几何的数据 结构。更明确说,就是层次化结构的顶节点应该给出一个简要的度量空间的 数据摘要,而 且随着处理层次结构的深入,得到越来越准确具体的数据几何。是基于域 空间的,给定一些点,五,恐,...,%, 薯的域空间是指空间中所有离一比,近的点 缛.,。需要对数据集进行预处理,对数据集中数据预先构建。构建时先选取 个不同的分裂点,然后将剩下的数据点分配到各分裂点的域中。每个域再继续递归构建。的另一个特点是充分利用已经计算过的相似性距离。因此, 依靠 结构来查询,通过在构建时存储的从分裂点到关联点距离值的范围修剪分 果查询点落在外面,则修剪。预处理时间长是树的最大缺点。..高维索引技术发展趋势 上述的高维索引结构都是“精确”的相似性查询,精确的返回查询对象与数 似性的数据对象。这种高维索引结构在维数较低的情况下具有良好的查询效率,但大多数 浙江工业大学硕十学位论文 在维数高于维时,检索性能呈指数级的下降,甚至会低于线性搜索】,导致“维 数灾难 现象。为了解决高维索引结构遇到的“维数灾难”问题,近似检索的概念被 提出,并且出 现了一系列的近似检索的索引结构。近似检索是指查询的结果允许存在一定 的误差,查询 数据集返回近似的结果。近似查询是对查询结果精度和效率的折中,牺牲一 定的准确率换 取更优的性能。在多媒体应用领域,“精确查询并不一定是精确的,它有很强 的主观性。 不同用户对多媒体信息的相似性的感觉不同,不同的特征提取方法解读信息 的角度不同, 而不同的相似性度量方法又造成信息的相似程度不同,由于用户感觉的相似 与计算机实际 定义的相似之间的差距,所以精确查询的结果不一定与用户意图相一致,这 就是近似检索 适用于多媒体查询的原因所在。近似检索是公认的能克服“维数灾难’’的 一种手段 【】【】【】【】,通过引入一定的误差率,缩小查询范围,提高查询效率。 近似检索一般从减少数据库的查询量和降维来提高系统的响应速度【。 ...减少数据库查询量 避免考虑在精确查询中要检索的所有对象。 一般来说,检索得到的数据对象占数据库很小的比例,但在精确查询过程中, 会比较 数据库中所有的数据对象来判断它是否是所需对象,这个过程中运算和/读 取的代价 都是很具大,系统需要很长的响应时间。为了减少不必要对象的查询,可以利 用聚类算法 把数据集分为几个簇,计算查询对象属于每个簇的概率,然后只对所属概率 高的簇进行搜 索。经过聚类处理过的数据集只需要访问少数几个簇就能完成检索,变换域 聚类方法【 就是基于聚类的近似检索方法。 在满足某种条件下比精确检索提早结束查询。 对于大型的图像数据库,不必对数据库中所有数据进行比较,用户可以参与 查询过程, 当己查询的结果符合用户要求时,可以提前结束查询过程。这是根据用户的 主管判断来结 束查询,还可以根据某些特定终止条件来判断是否需要结束查询。 .树方法就是比较典型的例子。 是树型的索引结构,采用.近似检索,利用优先查询判断下一对象是否还足够 定位包含查询对象的叶子结点,然后以与查询对象距离递增的顺序枚举叶子结点,进行优 先查询。查询过程中只记录前一结点与查询对象的距离,当下一个访问结点 与查询对象的 距离超过前一结点与查询对象的距离的 夕倍,停止搜索。一般来说,检索 能提早结束 是因为继续查找不能显著提高查询结果的正确性。浙江工业人学硕学位论文 ...降维方法 降维方法是通过一些特定方法将高维数据映射到更低维的空间上,利用低维 空间的特 性对数据进一步处理。这样就能避免“高维灾难”的问题,充分利用已有的 成熟索引结构, 提高基于内容的多媒体检索系统的检索性能。当然降维后的数据难免会舍弃 一些不重要的 维度的属性,造成原有信息的缺失,损失一定的精度。目前的降维方法大致可 以分为以下 四类:基于低维投影映射的降维,基于数据间相似性的降维,基于神经网络的 降维和基于 分形的降维。前三类方法比较常用,下面就这三类降维方法进行介绍。 基于低维投影映射的降维 基于低维投影映射的降维方法中最具代表的算法是主成分分析方法, 和投影寻踪方法。方法是目前应用最为广泛的降维方法之一, 主要处理线性问题。方法把数据投影到几个主成分上,以降低各特征维之间 的相关性, 进而达到降维的目的。投影寻踪方法【】是寻找一个合适投影,把高维数据 投影到低维空间 中,并且经过映射后的低维空间来反映高维空间数据的特性。 基于数据间相似性的降维 基于数据间相似性的降维方法根据高维数据间的相似性寻找对应的低维空 间,即寻找 一个合适的映射函数,映射后的空间依然能反映高维数据间的相似性。用欧 式距离度量相 似性的度量空间的数据,这些数据映射到低维空间后,要保留高维数据之间 距离远近性。 如数据、、,在高维空间中,离:离远,,,则经过映射函数 ,’。如多维尺度法 映射后的低维空间中也要满足这个关系, ,随机邻居嵌入,局部线性嵌入 基于神经网络的降维神经网络是近几年的研究热点,研究内容很广泛,涉及多个学科领域。基于神 经网络 的降维方法主要有自动编码网络,生成建模,子组织特征的映射,它们是根据 自身网络结 构的不同而分类的。 .本文的组织结构 第一章:即本章,全文的绪论部分。介绍了多媒体检索技术的发展历史,从基 于文本 浙江工业大学硕士学位论文 的检索到现在的基于内容的检索,并着重描述了基于内容检索的结构和关键 技术。基于内 容检索的现今热点问题,存在几大难点,本文研究的就是其中一难点:高维数 据检索。然 后对阐述了高维数据检索的一些经典技术,主要的基于向量空间和基于度量 空间的关键技 术,最后叙述了高维索引技术的发展趋势。 第二章: 高维数据检索算法是基于特征的检索算法,特征提取也是基于内容检索的 一大关键技术。本章主要介绍图像局部特征提取算法一算法。算法因为对图 像旋转, 尺寸缩放,光照变化和噪声信息的良好的不变性,及对视觉变化、仿射变换也 保持一定程 度的稳定性而在模式识别等领域广泛应用。本章详细叙述了算法从图像中提 取特征的 过程,并实验证明了算法的不变形,还检测了算法识别和定位能力。 第三章:对精确高维索引结构.查询算法近似化,包括查询算法的近似和范 围查询的近似,提/出算法和算法,有效结合.结构的优点和近似思想的高 维适用性,扩展了.近似检索算法的应用范围。.是一种基于数据的划分,用超 对数据层次化的分割,预先计算各超球的路径对象和覆盖半径,及与父对象的距离。查询 时,利用已计算好的距离信息和三角不等式过滤不包含结果集的分支,避免 大量无用计算, 有着.更高效的响应时间。我们提出.近似检索算法,采用.近似检索思想, 更快的收敛动态的查询半径。最后实验证明分析了近似检索算法的有效性。第四章:索引结构是一种全新的高维近似索引结构,是基于锚对象选 取的策略,对数据进行预处理,代替传统距离矩阵的存储,仅仅存储相对中 的排序矩阵,节省了在空间上的开销。查询时,通过排序的相似性度量预测相似数据, 只需扫描少部分数据集就能得到大部分所需的返回值。索引结构的选取至关 重要,本章主要研究如何选取高效的中心点及最合适的中心点数量,提出了 几种有效的选 取方法和用来确定不同数据集中心点数量的维数区分方法,保证在足够准确 率的基础上, 减少中心点数目,提高检索效率。最后通过实验分析不同选取方法的可行性 和有效性,并 在实际数据上验证维数区分方法的实用性。 第五章:总结和展望。对主要研究工作的总结和对下一步工作的计划与展望。 描述图像的 ,一是图像分割,另一个是兴趣点描述。图像分割是把图像空间分割成几个互不重叠的 区域,这些被 分割的区域有自己独立的特征域,且具有实际意义。图像分割技术是一个开 放领域,待进 一步的研究。兴趣点提取描述方法先检查用户有兴趣的区域,一般都是图像 中最能表示图像含义的对象,然后再用局部特征描述来描述图像特征。 算法就属于这种提取局部特征的算法,它在尺度空间中寻找极值点,并提取 对尺度缩放、旋转,平移等无关的局部描述子即特征向量。由于算法的快速准确 的匹配能力,高的扩展性,经优化后达到的实时性,所以它广泛应用许多领域, 如模式识 别,笔记鉴定,三维建模、视频跟踪和人脸识别等,是目前最为流行的不变量 局部特征提 取方法。 算法算法是年 .教授在现有的不变量的特征检测方法上提出的,并在 年进一步发展和完善。算法具有高的可靠性和稳定性,对于图像之间的的平 旋转、尺度变化,关照变化,噪音等有良好的不变形,对视觉变化、仿射变换也保持一定 程度的稳定性。 在测试局部描述子不变性的对比实验中,对 的兴趣点提取的局部描述子进行测试,结果证明及其扩展算法在尺度变化和仿射变换的 不变性中具有最强的健壮性【】。特征提取主要包括兴趣点检测和兴趣点描 述两部分。 兴趣点检测尺度空间的构建 算法是尺度不变的特征转换,在尺度空间中获取兴趣点的尺度不变性。根据 等人尺度空间理论,高斯核是唯一可以产生多尺度空间的核;尺度规范化的 空间具有真正的尺度不变性。为了有效的在尺度空间检测到稳定的特征点, 算法引入 浙江工业大学硕士学位论文 了一种新的尺度空间即高斯差分, 尺度空间。由相邻 尺度的高斯差分核和图像的卷积生成。定义如下: 是的近似,但它计算更简单。卷积是没有尺寸不变性的,使用同一对滤波因子的滤波器对同一物体不同尺寸的两幅图像求局部特征点有可 能出现一方求 得特征点而另一方却没有的情况。采用高斯差分金字塔来解决这一问题。每 个图像都 进行金字塔构建,金字塔的每一个截面与原图像相似,由底部最大一直到顶 部最小图像的 无穷个截面组成,那么两个金字塔中必然会有包含大小一致的截面。 高斯差分金字塔的构建:图像金字塔共组,每组有层,下一组的图 像由上一组图像降采样得到。如下图所在: 金字塔的构建兴趣点的检测 兴趣点检测就是在不同尺度空间的图像下检测出的具有方向信息的局部极 值点,为了 定位局部极值点,每个采样点都需要与它所有的相邻点进行比较,包括尺度 空间同 尺度上的相邻的个点,和上下相邻尺度上个个点,共个点,以确保检测到 在尺度域和图像域中所有的极值点。如果采样点比相邻点都大或都小,则这 中兴趣点的检测浙江工业大学硕士学位论文把式.代入式式,取前两项得: 宕:一望兰盒 、如果的绝对值大于某阈值,则此特征点可以保留,否则就舍弃。根据、的 验显示阈值取.比较合适。图.去除噪声敏感兴趣点后的结果 去除边缘点 函数通常在横跨边缘的地方有较大的主曲率, 而垂直边缘的地方有较小的 率,可以用的矩阵求主曲率。矩阵: 其中见表示金字塔某一尺度方向求导两次。的主曲率与的特征值成正比,为了避免直接计算的特征值而只考虑两个特征值之间的比率,的定义如 用式求的值,其中为的最大特征值,为的最小特征值,其中图.去除边缘点后的结果 兴趣点方向分配 同一图像经过旋转可能会获得不同的兴趣点,为了使图像具有选择不变形, 需要为 个提取的兴趣点指定方向参数。 公式?和表示特征点,处的模值和方向,其中的尺度是兴趣点所在尺空间的尺度。然后在高斯空间中对兴趣点的领域空间进行采用,用直方图统 计这些兴趣 的梯度方向。梯度直方图的范围是度,共柱,每柱度。直方图的主峰值就 所要的兴趣点的方向,而主峰值%的峰值作为兴趣点的辅助方向。一个兴趣点 有一个 方向,可能还会有多个辅方向,这样可以显著提高匹配的鲁棒性。 图.兴趣点方向分配 浙江.业大学硕士学位论文 兴趣点描述在兴趣点计算后,用一组向量把兴趣点描述出来,这里的描述不单单描述兴 包括兴趣点周围对其不变性有贡献的领近区域。兴趣点描述先对其周围像素区域分块,计 算块内梯度直方图,最后绘制唯一的描述子特征向量。图.是兴趣点描述子生 的例子。以兴趣点黑点为中心取的邻近区域,图中每个小格是尺度空间的一个像 素,箭头方向表示该像素的梯度方向,箭头长度表示梯度模值,大的圆圈是高 斯加权的范 围越靠近关键点的像素,梯度方向信息贡献越大。 把兴趣点的领域分成块,每块占个小格,计算这小块在个方向上的梯 度方向直方图,每个梯度方向的幅值累积,形成一个种子点,如图.右部分所 示。每个 种子点包含个方向的向量信息。此时描述子已经去除了尺度变化、旋转等几 何变形 因素的影响。 将的共个种子点具有个方向的向量信息组合成一个维的特征向量。 的实验表明描述子采用的维向量来表示,综合效果最优。 算法采用的领域方向性信息联合思想增强了算法抗噪声的能力,而且对于含 有定位误差的 特征匹配也提供了较好的容错性。 描述子的匹配当描述子生成后下一步就是对采取到的兴趣点进行匹配。目前有三种匹配策 第一种是阈值的匹配,如果两个兴趣点的描述子的相似度距离低于某个阈值,则这两个兴 趣点匹配,这种匹配方法可能会使一个兴趣点有多个匹配;第二种是最邻近 匹配,对于兴 浙江丁业大学硕学位论文 趣点,如果兴趣点是的最邻近点,且它们之间的距离小于某阈值,则接受这一 匹配 对,这时的匹配是一对一的;第三种是最邻近/次邻近之比匹配,算法的匹配 就是采用 这个匹配方法,如下所述: 查询图像的描述子:,墨,..?, 数据库中图像的描述子:,巧,..?, 任意两个描述子相似性的度量公式为:, 取图像的兴趣点,在图像中找到与之最近的两个兴趣点,如果最近兴趣点的距离 除以次近兴趣点的距离小于某一阈值,则这一对兴趣点是匹配的。的大 小直接影响匹配点的数目,降低阈值,数目会减少,但匹配更稳定。对大量任 转,尺度、亮度变化的两幅图像匹配,实验结果表明在..之间最佳,小于.则匹配点很少,大于.的则存在大量错误匹配点。 因为一幅图像进行算法特征提取后,一般会产生多个兴趣点特征向量,有时 甚至 会有上千个兴趣点,两幅图像的兴趣点匹配最普通的就是穷举法,但在数据 量大时需要很 长的响应时间,一般采用..索引结构。 算法的扩展算法提取兴趣点数大,特征向量维数高,在大规模的数据处理中内存消耗大, 并且 给后续的匹配和检索带来了很大的困难,于是很多研究者对算法进行改进, 以求在不影 响算法的不变形和稳定性的前提下尽可能提高它的匹配速度和检索效率,其 中最具代表 的是.算法和算法,二者都在兴趣点描述阶段采用不同的描述方法来改进 算法。 .算法 .算法【】把用于特征提取算法中,是一种典型的把高维映射到低维的 降维方法,通过采用对描述子降维,形成远小于算法得到的维的向量。. 算法兴趣点检测方法与算法没有什么不同,最主要的变化的描述子生成的不 浙江工业大学硕士学位论文.算法生成描述子分为两边:一是生成.投影矩阵,利用形成一个 的投影可以基于特征值动态选择,也可以是一个根据经验设置的固定值,一 子。对每一个检测到的兴趣点,以其为中心选择周围的像素的斑,分别计算垂直和 水平的梯度,得到一个大小为的向量,并通过归一化方法减少光照的影 然后用预先计算好的的投影矩阵与此向量相乘,最后形成一个维的.描述子。.算法在保持了算法不变性的条件下,大大减少的特征维数,有效提高 了检索效率。 算法 为了获得特征更强的鲁棒性和独立性,等人提出了描述子【。也与所采用的 兴趣点检测方法相同,只是 这描述子生成时利用对数极坐标系,形成仿射状同心圆的个子区域。再计算 梯度直方图 量化为种,这样就形成了维的描述子,后利用降维到。 .实验结果和分析 本文实现基于的算法,其中实验中机配置的软件环境为操作系统。本 实验主要实现了以下几点: 不同取值的下特征点匹配情况。 测试算法对图像尺度缩放,旋转,亮度变换的不变性。 算法识别和定位能力。 实验中采用最邻近/次邻近之比匹配的匹配方法,通过实验查看取不 同值时匹配情况。 取不同值时的匹配情况图.是取不同值时两幅图的匹配情况,蓝线表示两幅图的匹配特征向量,我 们可以看到匹配点随值增大而增大,并且当值大于.错误匹配比较严重 算法不变性的测试图.是算法图像的缩放、旋转和亮度不变性的测试的结果,通过实验我们能看 算法对图像的缩放、旋转有很好的不变性,但对亮度的变换则不如前面两者的不变性好。 算法在模式识别中有很大的应用,因为算法是局部特征提取方法,通过局部 特征向 量的匹配来有效识别,如图实验中能看出算法对对象有很好的识别性,能精 确查询到相 匹配的局部特性。 枷图.局部特征检测介绍了算法的实现原理,包括兴趣点的检测和描述,后对得到的描述子的匹配方 法进行分析。然后描述了那些能有效改进算法的相关算法,.算法和 算法,它们都是对原算法进行降维处理。最后通过实验验证算法对图像尺度 缩放、旋 转,平移等有良好的不变形,并检测算法识别和定位能力。浙江工业人学硕十 学位论文 第章基于高维索引结构.的近似检索 .高维索引结构. .是一个动态的分页平衡树,适用于任意度量空间。它基于对象之间的相关距 划分,采用自底向上的建树方法,用固定大小的结点存储数据对象,每个结点是一个带有 覆盖半径的超球,根据距离关系划分数据对象,递归地把数据细分到某超球 大的特点是在查询过程中充分利用三角不等式和预先计算过的范围距离值过滤不满足条 件的分支,减少计算次数,加快查询。 .的索引结构.索引结构由层次化节点构建。每个节点包含固定数目的入口项。.有两种类 型的节点:中间节点和叶子节点,对应两种类型的入口项。中间节点的入口项 包含四个属 性:路径对象、覆盖半径和指向子树在下一层的节点的指针,还有路径对象与 其父节 点中心的距离。路径对象是子树的质心对象,覆盖半径是子树中所有对象和 路径对象的最 远距离。叶子节点的入口项中记录三个属性:对象的标识符,特征向量,与其 父节点的距 离。叶子节点的入口项的结构为【,,徊圳】,其为路径对象的特征向 量,是对象标识符,尸徊圳是和其父对象尸徊的距离。中间节点入口 项的结构为,,,讲优徊训】,指路径对象,是此节点的覆 盖半径,是指向子树的指针,尸徊圳是研和其父对象的距离。 如下图..的树结构所示:下面的结点包含五个入口项,不管是叶子结点还是 围。如中间项’,它表示以为中心点,即路径对象,抱为覆盖半径覆盖半径取与路径 对象距离最大值的超球,指向结点 ,由于 是根结点,没有父对象,所以 等剩下的结点都是叶子结点,存储叶子项,叶子项中的对象包含了具体的数据,特征向量和标识符,还存储了与父对象的距离,如对象,它 与其父对 .的插入算法.的插入算法递归地把新对象插入到最合适的叶子结点中,当结点己满时触 发结 点分裂操作。.选择子树根据按覆盖半径最小化原则来决定的,最先考虑的是

  高维多媒体数据索引算法研究(可编辑),高维那,高维空间,高维那 坑爹,剩女的诱惑 高维那,吴秀波前女友高维那,高维宇宙,高维数据,matlab 高维矩阵,高维碎块,斯高维

http://bed-plans.net/gaoweisuoyin/16.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有