三维模型检索（精选八篇）
三维模型检索 篇1
关键词：三维模型,结构,骨骼,图编辑距离
1 背景
随着计算机计算能力的飞速发展，三维模型在计算机中越来越多的出现，如何让用户像查找文字一样方便的查找到所需的三维模型信息，迫切的需要找到一种快速高效的三维模型检索方法。三维模型检索方法的关键在于模型的特征提取与匹配。其中，三维模型特征提取方法主要分为基于三维模型表面和基于三维模型结构两类特征提取方法，基于模型结构的方法作为一种新兴的方法，由于受模型表面细微特征影响小，而可以作为一种很好的三维模型检索方法。
2 基于结构的表示方法
在三维模型特征提取中，另一种不同的思路是不考虑模型外部表示，而只考虑模型的结构，生成新的构造结构图来表示一个模型。由于和模型表面具体的顶点无关而不需要考虑模型表面细节，采用节点和边来重新表示模型：用节点表示模型划分的某个部件，用边表示这些部件间的关系。基于结构的特征提取方法主要分为以下四类方法。
1）基于骨骼(Skeletons)的方法
基于骨骼的方法主要分为了中轴法(Medial Axis)和震波图(Shock Graph)两大类的方法，这种方法是基于结构的三维模型检索方法的主要方法。其中，中轴法[1]首先求出点的最大包围球的中心轨迹，然后计算到表面等距离点轨迹，最后求出距离变形中的局部极大值;震波图[2]方法把骨骼区域按照如震波一样从一阶到四阶来表征(根部，可弯曲区域，颈部，突出伸展区域);这种方法的特点是，基于局部对称的特性分解图形到拓扑图;分支可以被区分优先次序、裁剪或者给定属性;变形不变性。其局限性有：计算开销很大;对噪声很敏感;可能导致结构复杂化。
2）基于本原图(Primitive Graphs)的方法
本原图[3]方法是通过简单图元覆盖的方法把原生模型分割成零件。这种方法的特点是：基于原始零件上把形状分解图元;图元可以被区分优先次序、裁剪或者指定属性;变形的不可变形。其局限性是：计算代价昂贵;对噪声敏感;对原始次序和停止规则敏感。
3）提取特征图(Feature Graphs)的方法
特征图[4]方法是表示三维形状特征值之间的几何关系。这种方法的特点是：基于模型中的特征值把形状分解为图;特征值可以按优先排序，裁剪和制定属性;对模型变形具有不变性。其局限性有：计算代价昂贵;对噪声敏感;健壮性依赖于特征值的检测。
4）基于表面分割图(Surface Segmentation Graphs)的方法
表面分割图[5]方法是用表面分解来表示形状：用节点表示一系列的表面来构建图;通过构建图生成匹配图。这种方法的特点有：基于面块组把表面分解为图;分层有属性的;对模型变形具有不变性。其局限性为：计算代价昂贵;对噪声敏感;对结束规则敏感。
基于结构的表示方法对表面坐标变化产生的影响小，既保留表面特征又使用结构的方法来体现各特征间的关系，是一种比较好的三维模型特征提取方法。基于结构的表示方法总结如表1。
3 基于结构特征的特征提取
在几种基于结构的三维模型特征提取方法中，本文采取的是基于提取三维模型骨骼的方法，找到三维模型的结构特征作为匹配的特征值。主要过程为：
第一步，首先读入三维模型库中的模型，得到网格化三维模型的表示，如图1A;
第二步，然后通过原始的点坐标信息产生包围盒结构，通过最接近的盒结构体素化整个三维模型，如图1B;
第三步，继续细化体素后的三维模型，这一步主要的作用是使模型成为封闭的模型，防止原模型中因为体素化而造成的空洞或断层，如图1C;
第四步，通过三角化方法提取骨骼的图像，如图1D;在体素化的包围盒的基础上，如图2。
第五步，简化骨骼图像，去掉不必要的细节信息，保留主要的骨骼图像，如图1E;如图3，判断规则为，递归每个节点，判断节点以下每个分支是否还有延续，如果都没有，这所有分支都为主干，如果其中之一有延续，则其他没有延续的分支为可以简化的分支，应当剔除;
第六步，通过规定各节点权重，给骨骼各节点分配属性，方便下一步匹配，如图1F。
通过六步操作得到三维模型的逻辑骨骼图，根据最后一步得到的权重属性进行下一步的匹配操作。
4 基于结构特征的匹配
基于结构的表示方法由于是借于原图的拓扑结构，因此不存在对齐的问题，只需要进行表示之后的匹配，本文采用图编辑距离的方法进行骨骼特征之间的匹配。该方法在两个图像的最佳总权重间，找到一个相应的节点的匹配。在不同两个模型A和B的拓扑结构间改变的最少的消费序列来表示A到B之间变形距离，变形距离越小说明AB越相似，如图4。
5 总结
基于结构的三维模型检索技术作为一种新兴的检索方法，不同于基于表面特征的三维模型检索方法，基于结构的检索方法关注得更多的是内部特征，基于局部对称的特性分解图形到拓扑图，分支可以被区分优先次序、裁剪或者分配属性，具有变形不变性等优点。
但是，基于结构这种搜索方式仍然存在一些问题：第一，让结构匹配更具有实用性;第二，在匹配时应用计算量更小的拓扑匹配方法;第三，减少生成骨骼时的噪声;第四，减少因为细化时造成的表面退化问题;第五也是最重要的问题，就是提高处理得到骨骼的计算速度。这些都是未来工作中需要解决的问题。
参考文献
[1]Blum H.A transformation for extracting new descriptors of shape[J].Models for the perception of speech and visual form,1967,19(5):362-380.
[2]Kimia B A.Tannenbaum and S Zucker,Shapes,shocks,and deformations I:the components of two-dimensional shape and the reaction-diffusion space[J].Interna-tional Journal of Computer Vision,1995,15(3):189-224.
[3]Cornea N,D Silver,Min P.Curve-skeleton properties,applications,and algorithms[J].IEEE Transactions on Visualization and Computer Graphics,2007,13(3):530-548.
[4]Ip C.Using shape distributions to compare solid models[C].New York:ACM,2002.
三维模型检索 篇2
缸体零件图如图56所示，
图56 缸体零件图图形分析该缸体零件图形由缸体、座、腔体以及缸体顶上两个半圆凸台和孔所组成。从左主视图中可看出缸体和其内的腔体均为回转面生成，底座为长方体并有一个矩形通槽，四角圆角半径为R=10mm，并且有4个沉孔和2个定位孔组成。其创建的操作方法如下：（1）利用“旋转”命令，将主视图右边的凸台、以及下面座图形去掉，旋转生成圆形缸体和内部直径为40和35mm的腔体造型。（2）将左视图中的上面圆的图形去掉，然后，连接上边线，拉伸生成座的造型。（3）将沉孔以中心线为准绘制成沉孔图形的一半封闭图形，旋转求差生成沉孔造型。再利用引性阵列生成其余3个沉孔。具体的创建操作如下：（1）除轮廓线（粗实线）图层打开，关闭其他所有的图层，或者保留可见轮廓线，而将其余全部删除。图57 修改后的图形（2）绘制封闭的图形。 将修改后的图形经过添加线段而构成封闭和图形后，然后，生成5个面域，如图57所示。（3）旋转生成缸体和腔体造型。 单击“建模”工具条上的“旋转”按钮，选择“图形1”，以图形最下边的线段为旋转轴，按回车键后，创建出如图58所示的缸体和腔体造型。图58 创建缸体造型 图59 创建底座造型（4）创建底座造型。单击“建模”工具条上的“拉伸”按钮，选择“图形4”，输入拉伸值为60mm，创建底座造型如图59所示。（5）旋转生成实体。单击“建模”工具条上的“旋转”按钮，分别选择“图形2”、“图形3”、“图形5”，以各自的旋转轴线旋转生成回转实体。如图60所示。图60 旋转生成实体（6）圆形阵列。 单击“修改”工具条上的“阵列”按钮，在“阵列”对话框中选择“环形阵列”类型，以缸体的原心为环形阵列的中心点，设置数量为“6”，选择图形3生成的旋转实体，单击“确定”按钮，生成环形阵列。（7）运用“差集”命令，先选择缸体实体，回车后，再选择环形阵列创建的6个圆柱体，回车将6个圆柱体减去后，生成缸体前端面上的6个M6深14mm的螺纹底孔造型如图61所示。图61 创建前端螺纹底孔 图62 调整缸体至合适的位置（8）创建缸体上的两个半圆形凸台。其操作如下：① 调整视图方向。单击“视图”工具条上的“西南等轴测”按钮，然后，单击“动态观察”工具条上的“自由动态观察”按钮，旋转视图至一个合适的位置如图62所示的位置，② 建立UCS（用户）坐标系。 在命令行中输入：UCS 按回车键，再输入：N 新建用户坐标系，再按回车键，输入：3 即用3点确定坐标原点。用鼠标捕孔的中心点，将坐标原点设置在圆心处，如图63所示。图63 建立UCS坐标系 图64 绘制图形③ 绘制图形。以坐标原点为圆心，画一个半径为15mm的圆，绘制的图形如图64所示。④ 创建一个面域。 用“面域”命令，选择图形，回车后，生成一个面域。⑤ 将生成的面域和旋转生成镜像至右边。如图65所示。提示：镜像可在前视平面内进行。图65 镜像实体 图66 创建半圆形凸台造型⑥ 拉伸面域创建半圆形凸台。选择左边的面域向下拉伸4mm。 再选择右边的面域向下拉伸15mm,再利用“并集”命令，创建缸体上左、右两边的半圆形凸台造型，如图65所示。⑦ 利用“差集”命令，将旋转生成的实体从缸体中减去，创建孔造型，如图67所示。移动前 移动后 图67 完成缸体部分的创建 图68 实体的平移（9）创建底座上的沉孔造型的操作：① 移动图形5旋转生成的实体。利用“M”（移动）命令，将实体向前移动10mm,结果如图68所示。② 实体的矩形阵列。单击“修改”工具条上的“阵列”按钮，选择“线性”阵列类型，设置参数如图69所示。选择移动后的实体，单击“确定”按钮，创建的实体线性阵列如图70所示。③ 利用“差集”命令，将线性阵列后的4个实体从底座上减去，创建4个沉孔造型。④ 底座4条垂直边圆角，圆角半径R=10mm，完成的底座造型如图71所示。图69 设置矩形阵列的参数图70 生成矩形阵列 图70 完成底座的创建（10）缸体与底座的合成操作：① 在“前视平面”内，利用“RO”命令，将底认旋转90度。② 标注尺寸后，以标注的尺寸为移动的依据，如图71所示。③ 以缸体右边的边线为基准，移动后完成整个缸体的创建，如图72所示。图71 标注的尺寸 图72 缸体零件实体模型三维模型检索 篇3
随着三维扫描技术以及三维建模软硬件的不断发展成熟,使得三维模型的创建过程变得越来越容易,产生了越来越多的三维模型库,为用户实现资源共享提供了更多的便利条件,同时涉及到的领域也越来越广,比如工业设计、虚拟现实、CAD应用、计算机视觉、游戏产业和医疗等[1],具有广阔的应用前景。其中有专门针对特定领域的数据库:美国国家癌症研究所建立的NCI DIS 3D模型库[2],此模型库拥有400 000个模型;美国MDL信息系统有限公司的化学品三维结构ACD-3DMDL模型库[3],此数据库拥有300 000个模型;最常用的是美国普林斯顿大学建立的三维模型数据库(PSB)[4],此数据库拥有60 000个模型,是通用模型库。针对这种三维模型数量迅速增加的现象,如何在这众多的数据库中帮助用户准确快速地检索出需要的目标模型,实现三维模型的重利用,逐渐产生了三维模型检索技术,是近年来一个研究热点,并与多种学科交叉,如人工智能、人机交互、模式识别、计算机图形学等。
1 研究现状
传统的三维模型检索系统[5]包括两个部分,如图1所示:在线部分和离线部分。在线部分与用户交互,用户可以浏览数据库,通过接口给服务器发送一个三维请求,系统接收查询模型,并与所有相似模型的特征值比较。离线部分提取模型特征并计算三维模型的形状索引以及相似度。其中特征提取和相似性匹配是决定检索结果的重要步骤。
2 特征提取
能否使用同一特征向量快速准确地判别出对于不同形状的三维模型评价此特征向量优劣的标准,因而模型的特征提取是三维模型检索中的关键问题。
2.1 形状以及相似性计算方法
2.1.1 形状
形状是三维模型最重要的特性,与颜色、纹理相比能够更细致地描述模型。而且形状是无量纲的,任何旋转,平移都不改变其特性。从整个三维模型的特征中计算形状模型,提供全局信息如面积、体积、周长、半径等。既不需要初始分割步骤也不需要预处理[6]。常用的形状有面积和体积,以三维多边形模型为例,计算这些特征如下:
V是包含三角面i的顶点坐标向量。
2.2.2 相似性计算方法
相似性度量指在得到三维模型的形状特征后需要计算这些特征的相似性,通过比较输入模型与数据库中模型之间的差别,选取出令用户满意的模型。在与三维模型检索领域类似的二维图像检索领域,已有很多方法计算特征值的相似性,常用的是计算距离法有以下三种距离:Duclidean距离、Manhattan距离、Hausdorff距离[7]。设任意的两个特征向量表示为X=(x1,x2,…,xm),Y=(y1,y2,…,ym),则它们对应的三种距离分别表示为:
Duclidean 距离:
Manhattan距离:
Hausdorff 距离:
因为三维模型的形状特征很容易计算,并且旋转和平移都具有不变性,所以常常被选用。但是应该指出的是有一些形状特征用同样的方法不能将模型分类。以半径延长量索引为例,认为图2中的两个模型类似,因为它们具有几乎一样的半径,尽管体积形状索引认为它们是不同的。因此结合其他特征来计算最大相似性是十分必要的,比如空间拓扑结构。
2.2 空间拓扑结构
拓扑结构也是三维模型的一个重要特征,大量实体需要描述三维模型的空间关系以正确表现三维模型内容。不用分割模型,使用空间关系计算局部特性,根据模型特征定义空间关系,区别相似外形模型,包括位置和距离,可以提高检索和识别模型的质量[8]。因此需要将其他内容添加到三维形状特征中来描述三维模型实体的位置、距离和定位。结合形状特征和模型的拓扑结构来表示三维模型如图3所示。
已提出的用三维模型的空间拓扑结构表示三维模型特征的方法有多分辨率Reeb图法和骨架图法。多分辨率Reeb图法即在三维模型上定义一个连续函数f,首先计算每个顶点的f 函数值,然后根据f 值将模型上的顶点进行分类,f值相同且位于同一连通分量上的点归为一类,最终得到原顶点集的一个分类集合,即商集。将商集中的点根据原有模型点间的邻接关系连接起来,就得到原有模型的一个骨架[9]。骨架图法即首先计算出模型的骨架节点,然后通过各节点构造出相应的骨架图,通过中轴线更简洁地再现三维几何的形状及拓扑变化,这是一个有向的非循环图[10]。实体间的拓扑关系涉及到对象如何互连。通过拓扑结构得到模型的全局特征,有助于提高检索的质量和效率。本文中采用的拓扑关系如表1所示。
3 语义标注
3.1 基于聚类的语义
一个三维形状索引在通用三维数据库中不足以描述三维模型,因此有必要结合几种三维形状索引来增强基于语义概念的知识。基于外形的特征值提取处在形状这一低层次的特征空间,这种检索方式只是寻找模型在外观相近的模型,所获得的检索结果会含有形状相似语义绝不相同的模型,与使用者的检索目标一定相差甚远。而检索者的需求往往是处于较高的语义空间,二者之间差异巨大,这也就是模型的外型特征存在从形状到语义的“语义鸿沟”问题[11]。
针对目前基于语义的三维模型检索方式的研究,发现模型的语义标注对三维模型检索的检索效果起着至关重要的作用,对模型语义标注越完善,覆盖面越广在进行语义检索时检索效果就越好[12]。现有的模型标注获取方法将模型库内的模型作为单个个体,对每一个模型进行单独的语义标注,并且是手工标注的,在进行语义检索时通过将检索词与标注进行比对找出检索目标。这种三维模型语义标注方式工作量巨大,在加入新模型时需要对新模型进行详细的语义标注,标注量与检索的准确性是成正比的,为了达到好的检索结果,需要进行尽可能详细的标注。而手工进行三维模型语义标注的标注量毕竟是有限的,相对的检索者的语义检索范围是近乎无限的,想利用有限的标注来覆盖近乎无限的检索目标可以说是不可能的,因此现有的三维模型语义检索方式对模型的标注不但工作量巨大,而取得的检索效果并不理想。要解决这一问题,我们引入K-mean聚类算法将形状特征和语义结合,提高三维模型检索的查全率和查准率。
3.2 K-mean聚类
K-mean是目前最普遍使用的聚类算法,因其思想简单、具有很好的局部收敛性[13]。过程如下:
(1) 假设要聚成k类,由人为决定k类中心Z1(1) ,Z2(1),……,Zk(1);
(2) 在第k次叠代中,样本集{Z}用如下方法分类:
对所有的i=1,2,…,k;i≠j,若‖Z-Zj(k)‖<‖Z-Zi(k)‖,则Z∈Si(k);
(3) 令由(2)得到的Si(k)新的类中心为Zj(k+1),令
(4) 对于所有的j=1,2,…,k;若Zj(k+1)=Zj(k) 则终止,否则返回(2)。
4 实验结果
我们以普林斯顿形状基准数据库实验,如图1所示在线过程中用户向三维集合提交查询模型的请求,如图4所示是要查询的模型,此过程中计算形状索引可以直接检索模型如图5所示。通过引入语义标注的三维模型检索,在连接三维形状的低层特性和高层语义的语义概念检索之前标记查询,提取出12个最相似的模型并将结果通过二维图像反馈给用户如图6所示。
通过实验可以验证用我们提出的方法提供了检索结果的准确性。图4是要检索的模型,图5是未引入语义标注得到的模型,图6是引入语义标注得到的模型,对比得出在图5结果中只有4个符合我们所希望得到的模型,而图6结果中11个都符合检索结果,说明我们的方法对于提高三维模型检索的准确性具有可行性。
摘要：随着网络上使用或存储在数据库中的三维模型数量迅速增加,如何从大量的三维模型中检索到相似的三维模型变得十分必要。由于目前基于形状的三维模型检索不包含语义概念,因而检索的结果已不能满足用户的需要。针对此现象提出一种新方法,即结合语义和形状特征的三维模型检索。使用K-means算法把形状特征聚类到语义群中,空间关系消除具有相似外观模型之间的歧义。利用普林斯顿形状基准数据库进行实验,结果证明了该方法的可行性。
三维模型检索 篇4
企业不断发展,积累了大量的机械零件三维模型,怎样从大量的模型中检索出所需要的相似零件,重用已有的企业资源,避免重复劳动,是目前比较热门的一个研究课题。针对机械零件三维模型的相似性,文献[1]研究了基于几何和拓扑相似性的三维机械零件模型的匹配以及检索方法,该方法将零件模型转换为STEP格式提取零件的结构数据,构造零件模型图,基于模型图进行零件相似性比较,但计算量大,实际应用有一定困难。文献[2-3]结合D2形状分布图和NFD树结构方法,先把模型分解成几何基本体的树结构,然后分层次地评定两模型的相似性,对于较复杂的零件模型,不同的分解生成不同的树结构,得出的相似性存在较大的误差。Chuang等[4]用广义势场法提取简单的规则多面体的骨架,以物体凸起的角点作为种子点,在力的引导下生成不同的骨架段,处理对象不涉及曲面,不能完全适用于机械零件的检索。王飞等[5]提出了拓扑和形状特征相结合的三维模型检索方法,从整体和局部相结合两方面比较模型的相似性,但并未给出提取骨架实际可行的方案,且其相似性算法较复杂,难于实现。王家乐等[6]提出利用模型表面面片的法向量方向分布特征构建具有旋转不变性的N2形状描述符来比较模型的相似性,两种模型的相似性距离计算使用的权值估计算法较繁杂,实现起来有一定的困难。
本文用电场法提取机械零件三维模型的骨架,并将骨架转换成特征曲线,运用灰色关联分析方法计算特征曲线的相似关联度,从而得到机械零件三维模型的相似度。本文方法能快速地获得零件的骨架,应用灰色关联分析进行相似度计算, 算法准确且简单,易于实际应用。骨架和灰色关联分析的结合能准确快速地检索出相似的机械零件三维模型。
1机械零件三维模型的简化
零件的特征建模过程,由特征按照一定的顺序叠加而成,这种叠加以交、并、差布尔运算的形式进行。其中机械零件上的一些附加特征,也称为辅特征,如键槽、内外螺纹、倒角、倒圆、孔等,这些特征都是在零件已有的特征或实体上添加的具有特定工艺属性的结构,主要是对零件局部进行修饰,它们的存在与否并不影响模型的整体拓扑结构。模型的相似性主要取决于它们的主干结构,故在提取模型骨架前计算机先自动识别提取这些附加特征并把它们过滤。过滤简化后尽可能得到一个无中空结构的连贯实体模型,这样有利于后续骨架的提取过程。
图1a所示零件,模型中的倒圆、倒角、孔等附加特征的存在与否没有影响模型的整体结构分布,简化时被过滤,得到的无中空结构的连贯模型如图1b所示。
2骨架的提取
线性骨架是物体的一种降维表示,它通常由一组曲线段相互连接构成,每一条曲线段一般只有一个像素点的宽度,因而它是物体的一种直观的、简洁的表示,提取出的模型骨架在很大程度上保留了三维模型的形状特征和拓扑结构特征,有良好的稳定性,被广泛应用于三维实体建模、计算机动画、医学可视化、形状分类和识别等领域[7]。 本节针对机械零件的三维模型研究骨架的提取。
2.1骨架起始点的确定
模型简化后,对其主干结构进行骨架提取,将机械零件转换成既包含形状特征又包含拓扑特征的骨架。
机械零件模型的顶点对于模型的空间形状分布具有非常重要的作用,它决定了模型的结构分布,进而决定了骨架的空间分布。简化后的机械零件模型表面主要由平面和曲面构成,且曲面通常由圆柱面、圆锥面和球面等规则曲面拟合而成。 当表面为平面时,模型上的顶点很容易选择,如图2中的A、B、C、D点,都是由平面相交构成的顶点; 当模型上某一边界表面为曲面时,本文将曲面的转向轮廓线的端点定义为顶点,如图2中的E、 F、G点是模型的顶点。本文选择无限接近模型顶点的内部点作为骨架起始点,选择的原因见下文。
2.2运用电场法提取骨架
假设简化后零件模型边界表面上均匀分布着正电荷,这些电荷在模型内部产生了一个稳定的电场,电场方向垂直于边界表面且指向模型内部。 若某表面为平面,则电场方向垂直该平面且指向模型内部; 若为曲面,则电场方向垂直于曲面上某点的切面且指向模型内部。根据物理静电力学知识,沿着电场线方向电势( 位势) 降低,即位势随着模型内部点到边界点距离的增大而减小,取边界表面处的位势为无穷大,可知在模型内部某点存在最小位势点。最小位势点是获得模型骨架的关键点。
2. 1节中选择无限接近模型顶点的内部点作为骨架起始点,而不直接选择模型顶点作为起始点,是因为在边界处电势存在突变,起始点在边界处的受力难以控制,计算进程难以进行。起始点在电场中受到电场斥力的作用,其合力的方向取决于所有通过该点且与边界面垂直的各个电场斥力的矢量和。
定义模型内P点的斥力计算公式为
其中,P为起始点沿着合力方向前进的某一点; Bi为通过P点的电场力的方向线与边界表面的交点,即电场线与边界面( 切面) 的垂直点; R为点Bi与点P之间的距离; n为P点的受力个数; m为力的阶数; 分力的大小为1 /Rm,与Rm成反比。根据式( 1) ,力的阶数m不同,斥力FP的衰减程度就不同,起始点受到的合力方向就会有所不同,获得的最小位势点就会与理想情况下的点有所偏差。m在一定范围内取得越大,外界对力的影响就越小[8],获得的骨架就越理想。经过多次实验计算,当m = 6时计算速度较m < 6时降低10% ,而查准率 - 查全率提高30% ; m = 6时较m > 6时, 速度提高20% ,查准率 - 查全率降低3% ; 因此综合考虑,当m = 6时获得的实验效果最好,所以本文取m = 6。
各个分力的大小和方向都已确定,内部某点所受合力为各个分力的矢量和,模型内部的合力方向即可确定。例如,取无限接近图2中顶点A的内部点P作为起始点,对该点进行受力分析,如图3所示。
图3中B1为通过P点的电场力方向线与模型的上表面的交点; 力Fi( i = 1,2,…,6) 分别为模型边界面上对应点对P点的电场斥力。图3中P点受六个分力的作用,其大小和方向根据式( 1) 来计算,Fi对应式( 1) 中的各分力FBiP,FP为各分力合成的合力,合力的方向代表起始点下一步前进的方向。得到合力的方向后,起始点按照步长前进,在下一点同样进行电场受力分析,如此重复计算,直到到达最小位势点。
起始点的受力作用使用式( 1) 表示的各个分力来合成计算,根据力的跟踪法,沿着合力的方向按一定步长逐步移动,直到移动到最小位势点,起始点移动的轨迹构成模型骨架的一个分支。步长的选择要保证骨架的连续性和光滑性,若步长选择过小,则计算量过大; 若步长选择过大,则无法保证得到连续的骨架,本文选择模型最大长度的1 /100作为一步长。起始点在到达最小位势点之前, 沿着合力的方向一步一步地往前移动; 如果移动后导致力的方向相反( 当前后两个力的方向超过90° 时,则认为这两个力的方向是相反的) ,则认为最小位势点找到了,即可停止该方向上的计算。
如果起始点在到达最小位势点之前到达已生成的骨架分支则停止该起始点沿力的方向的计算进程,该起始点接下来的沿力方向前进的计算合并到已生成骨架分支上,直到到达最小位势点,这样可以减少重复计算,减少总体计算时间。图4a是图4b的局部放大图,图4a中A、B、C、D几个起始点在到达最小位势点之前发生骨架分支合并, 相交于M点。然后A、B、C、D几个起始点的计算进程合并到M点,只需计算从M点沿力方向的进程,直到到达最小位势点。
如果两个最小位势点的连线没有和物体边界或已经生成的骨架分支有交叉点,则认为这两个点均是最小位势邻接点。获得模型骨架的最小位势点后,将最小位势邻接点连接起来,和起始点路径形成的骨架分支结合起来即获得完整模型骨架。模型获得的完整骨架如图4b所示。
2.3骨架生成特征曲线图
提取出的骨架是由一组空间直线、曲线组成的,其中组成骨架的每一条线段或曲线段都是骨架的一个分支。要比较模型骨架的相似性,就要先将模型骨架信息转换成便于比较计算的计算机能识别的符号数据。本文将每一骨架分支看作空间中的一个向量,向量的大小用向量的模来表示,向量的方向用向量与坐标平面xoy的夹角表示( 方向角) 。向量的模描述了骨架分支的形状特征,向量与坐标平面的夹角描述了骨架分支的拓扑结构特征,用这两个量能准确地表达骨架。当骨架分支为曲线时,曲线的长度即向量的模,曲线两端点切线的角度变化值作为向量的方向角。将向量的模和向量方向角的余弦值这两个数据组合写成点的形式,这样每一骨架分支就对应一个点数据,这个点数据就是骨架的特征点。
以向量的模和方向角余弦值分别作为直角坐标系的横坐标和纵坐标,在坐标系中将各骨架分支对应的特征点标出,然后平滑连接成曲线。连接形成的曲线包含了骨架的长度和方向性两方面的特征,是骨架的特征曲线。
由图4b零件骨架的特征数据绘制出的骨架特征曲线如图5所示。
3基于灰色理论的骨架相似度计算
灰色关联分析是灰色系统理论中十分活跃的一个分支,其基本思想是根据序列曲线几何形状的相似程度来判断其联系是否紧密。曲线越接近, 相应序列之间的关联度就越大,即相似性越大,反之就越小[9]。本文运用基于相似性和接近性视角的灰色关联度模型[9]来进行骨架特征曲线的相似性比较,从而得到机械零件三维模型的相似度。
设系统行为序列
的始点零化像分别为
设序列Xi与Xj长度相同,则两序列的基于相似性视角的灰色关联度( 简称相似关联度) 为
需检索零件的特征曲线为参考曲线,对应序列为参考序列Xi,待检索零件的特征曲线为比较曲线,对应序列为比较序列Xj,特征曲线的相似关联度为 εi j。
灰色相似关联度 εi j具有的性质如下: 10 < εi j≤ 1; 2εi j仅与Xi和Xj的几何形状有关,而与其空间相对位置无关,或者说,平移变换不改变相似关联度的值; 3Xi与Xj在几何形状上越相似, εi j越大,反之就越小; 4εi i= 1[9]。
获得骨架的特征曲线后,在曲线对应点上取出序列,特别要取曲线转折点对应的数据,因为曲线的转折点是表征特征曲线形状的关键点,它包含曲线几何形状的更多信息,如图5中特征曲线上的A、B、C、D、E等点都是特征曲线的关键点。取图5中特征曲线的序列为X0= ( x0( 1) ,x0( 2) , …,x0( n) )=( 0. 62,0. 55,0. 48,0. 54,0. 54, 0. 75,0. 84,0. 67,0. 65,0. 45,0. 00,0. 45,0. 37, 0. 44,0. 50,0. 57,0. 70,0. 85,0. 87,1. 00) 。图5所示特征曲线对应的序列为参考序列,而其他机械零件特征曲线对应点上取出的序列作为比较序列Xj,参考序列和比较序列根据式( 2) ~ 式( 7) 计算曲线的相似关联度,进而获得骨架的相似度。系统根据计算出来的相似度值的大小按照从大到小次序排列,用户设置相似度阈值或输入需要返回的相似模型数目,系统返回与待检索模型最相似的若干模型。
4实例应用
以图6a所示的零件为例说明上述相似性比较过程。首先简化机械零件三维模型,将不影响零件整体拓扑结构分布的一些附加特征简化,如简化模型中的倒圆、倒角、孔等,简化得到的连贯实体如图6b所示。假设简化模型表面均匀分布着正电荷,在模型内部产生了稳定的电场,选取模型的顶点作为起始点,由于电场的作用,起始点受到电场斥力的作用按照给定的步长沿着合力的方向前进,直到到达最小位势点,起始点的移动轨迹构成骨架的一个分支,最后将最小位势邻接点连接起来,形成完整的骨架,零件生成的骨架如图6c所示。
生成骨架后,计算骨架各分支对应的向量的模和向量的方向角余弦值,数值统计成特征点的形式,然后根据特征点数据绘制骨架特征曲线; 最后运用灰色关联分析计算比较骨架特征曲线的相似关联度。
根据图6c所示骨架计算得到的点数据绘制的骨架特征曲线如图7所示。
采用同样方法绘制的图8a所示零件的骨架特征曲线如图8b所示。
运用灰色关联分析计算比较图7和图8b两骨架特征曲线的相似关联度。在两个特征曲线上取相同长度的序列X1,X2。
图7骨架特征曲线对应的参考序列X1= ( 0. 41,0. 63, 0. 71, 0. 32, 0. 54,0. 66, 0. 96, 1. 00, 0. 98, 0. 93,1. 00, 0. 84, 0. 81, 0. 79, 0. 61,0. 60,0. 55,0. 45,0. 59,0. 09) ,X1始点零化像X01= ( 0,0. 22,0. 30,- 0. 09,0. 13,0. 25, 0. 55,0. 59, 0. 54, 0. 52, 0. 59, 0. 43, 0. 40, 0. 38,0. 20,0. 19,0. 14,0. 04,0. 18,- 0. 32) 。
图8b所示骨架特征曲线对应的比较序列X2= ( 0. 35, 0. 40, 0. 58, 0. 71, 0. 65, 0. 42, 0. 50,0. 54, 0. 44, 1. 00, 0. 96, 0. 90, 0. 87, 0. 90,0. 76,0. 74,0. 64,0. 50,0. 47,0. 2) ,X2始点零化像X02= ( 0,0. 05,0. 23,0. 36,0. 30, 0. 07,0. 15, 0. 19, 0. 09, 0. 65, 0. 61, 0. 55, 0. 52,0. 55, 0. 41, 0. 39, 0. 29, 0. 15, 0. 12, - 0. 15) 。
将以上数据代入式( 7) 得| s1- s2| = 0. 205,代入式( 6) 得两骨架特征曲线的相似关联度 ε12= 0. 830,即两个零件的相似度为0. 830。
采用本文方法计算得到零件库中部分零件与图6a所示零件的相似度见表1。
从表1可以看出,运用本文方法计算得到的结果与人类认知相符合,零件的主体拓扑结构越相似,得到的相似度值越大。
若用户设置相似度阈值为0. 8,则系统返回与示例零件相似度大于或等于0. 8的模型,表1中前3个零件为与示例零件相似的机械零件; 若用户设置需要返回的模型数目为5,则系统返回表1中前5个零件作为与示例零件相似的机械零件。
5实验分析
实验主要从计算量和查准率-查全率曲线( Pr曲线) 两方面验证本文方法的可行性与准确性。 将本文方法与D2形状分布算法、N2形状描述符算法、球面调和描述符[10]三种算法进行对比。
从计算量上看,单一考虑形状特征的D2形状分布算法只需要计算模型表面随机采样点间的距离,计算复杂度不高,计算量最小; 本文的骨架提取算法,斥力计算公式和灰色关联度计算复杂度都不高,计算量稍大于D2算法; N2算法是在D2算法的基础上,增加计算每对采样点所在的两个多边形面片的法向量夹角余弦值,计算复杂度稍高于前两种算法; 球面调和算法需要先对网格模型进行体素化预处理,然后计算体素模型和球面的相交图像,复杂度高,计算量大。本文使用ESB( engineering shape benchmark)[11]作为测试数据库,在同一台计算机上采用4种算法检索同一个相似零件模型,所用的计算时间见表2。
min
从表2可以看出,本文算法计算复杂度不高, 计算耗时仅次于D2算法,远短于球面调和算法。
查准率 - 查全率曲线是分析检索系统准确性高低的重要评价手段,本文仍然使用ESB作为测试数据库。图9所示为4种算法的P-r曲线,可以看出,查准率和查全率之间存在制约关系: 随着查全率的提高,查准率会下降。查全率为0. 4时, D2算法的查准率只有0. 15,N2算法查准率为0. 18,本文算法为0. 27,球面调和描述符算法为0. 38; 而当查全率为0. 6时,D2算法查准率下降到0. 11,N2算法为0. 12,本文算法为0. 18,球面调和描述符算法为0. 25。由图9可以看出,本文方法的检索准确性要优于D2形状分布算法和N2形状描述符算法,仅次于球面调和算法。
综合考虑计算量和查准率-查全率两方面可以看出,球面调和描述符算法准确性虽然高于本文算法,但其计算过程复杂,系统实现困难,本文检索方法的综合性能优于球面调和描述符算法、 D2算法及N2算法。
6结语
本文提出的机械零件三维模型检索方法首先简化模型,忽略倒圆、倒角、孔等附加特征,得到无中空结构的连贯模型,实验证明,模型虽然被简化,但是保留了三维模型的形状特征和拓扑结构特征,不影响检索的查准率和查全率,而且提高了生成骨架的速度,即提高了检索的速度。在简化模型的基础上应用电场法提取三维模型的骨架, 起始点的选取以及斥力计算简单清晰,便于最小位势点的获取,生成骨架快速准确。将生成的骨架转化成便于比较的数据,生成特征曲线,采用灰色关联度分析比较特征曲线的相似关联度,从而得到机械零件三维模型的相似度,将灰色理论应用于机械零件检索,尤其在实例库为小样本时,具有极高的准确性和有效性。
本文所阐述的模型骨架提取方法特别适用于有明显空间结构分布的机械零件,目前已在自行开发的检索原型系统中得到应用,实例库有近500个零件。然而,对于另外一些零件,如中空薄壁类零件,若简化为无中空结构,零件的结构会发生较大变化,影响检索的查准率,因此,本文的骨架提取对该类零件不适用,对于该类零件的相似性比较正在进一步研究改进中。
摘要：提出了一种将模型骨架和灰色关联分析相结合的机械零件三维模型检索方法。首先简化机械零件三维模型,忽略倒圆、倒角、孔等附加特征,得到无中空结构的连贯模型;然后基于电场法提取简化后的机械零件三维模型的骨架,所提取的骨架表达了零件模型的形状和拓扑结构特征,并将骨架转换成特征曲线;最后运用灰色关联分析方法计算特征曲线的相似关联度,从而得到机械零件三维模型的相似度。实例验证和实验分析表明,该方法能准确地检索出相似的机械零件三维模型。
全文检索模型的检索性能研究 篇5
全文检索系统包括如何建立和维护全文索引以及在此基础上如何实现快速有效的检索[4,5]两个方面。因此，对全文检索模型的检索性能研究就是一项基础而重要的工作。
本文首先对几种常见的检索模型进行定性的分析，然后给出模型的关键实现，接着对检索模型的检索性能进行实验验证，最后给出全文的总结。
1 关于检索模型
目前常用的全文检索模型有单索引检索模型、单索引+数据库检索模型、分布式检索模型。其中分布式检索系统，如Google等大型通用搜索引擎，其基本思想是将海量的数据进行分散存储，通过多机集群的处理能力，集中解决协同索引和检索的问题。但其实现技术难度大，由分布式并行处理所带来的性能几乎为解决索引与检索同步问题所抵消[6]，因此本文不对该模型进行更多的研究，重点对前两种模型进行分析研究。
1.1 单索引检索模型
如图1所示的单索引检索模型中，系统只建立一个全文索引库，在创建索引的同时保存被索引信息。该模型的优点是，在进行全文检索时，相关信息直接从索引库中获得，与数据库库无关，可省去数据库的查询时间。其缺点是，索引库相当庞大，会比只对索引域建索引大2倍以上，造成数据大量冗余，增加系统存储压力，同时也降低该模型的检索速度;另外，索引总是滞后于数据库中的信息变化，造成检索信息的“失真”现象。
1.2 单索引+数据库检索模型
单索引+数据库的检索模型如图2所示。创建全文索引时，只建索引，不保存被索引信息。检索过程为：先进行全文检索，再根据全文检索结果(记录ID)反查数据库，在数据库中根据相应条件过滤数据。此模型的好处是：索引库较小，减少了数据冗余，减轻了系统存储压力，全文检索的速度有所提高。其不足之处是：增加了一次数据库查询的时间开销，整体查询速度方面并未改善;索引依然滞后于数据库中的信息变化，影响系统的查准率、召回率。
2 检索模型关键实现
全文索引库是检索模型的核心，索引库的性能决定了检索模型的性能，图3全文索引库的实现流程图。
3 检索模型性能实验与分析
前面已经对各个模型做了定性的分析，为了通过实验来测试单索引模型和单索引+数据库模型的检索性能，首先实现了一个简单的检索系统。实验基本环境：单台PC机，Pentium(R)4 2.80GHz的CPU,1.5GB内存，7200转速80GB硬盘;操作系统为windows XP 2002专业版，Tomcat6.0的应用服务器，IE7.0的浏览器，使用开源数据库管理系统MySQL5.0;在测试库中导入1000条图书记录，记录包含编号、标题、摘要、内容等多个字段，图书内容长度800—5000个汉字不等，摘要长度最大200个汉字，标题最长50个汉字。测试结果如表1所示。
从表1实验数据来分析：1)从时间上看，单索引模型整体优于单索引+数据库模型，但从平均响应时间来对比，单索引模型优势并不明显，110ms左右的最大时间差不会明显影响系统检索性能;2)从索引库大小来看，单索引却处于明显劣势，随着记录的增加，会给系统带来很大的存储压力，同时索引的维护代价必然远远超出后者;3)单索引模型中，两种检索策略的使用，带来40ms左右的平均检索性能差异;4)单索引+数据库模型中，使用不同检索策略，也产生40ms左右的平均检索性能的差异。
综上所述，采用的检索模型与检索策略的不同，系统检索性能会有一定差异，为具体项目选择检索模型与策略提供了一定的实验依据，同时也为改进系统检索性能，提供了一些思路，如对检索策略、首次检索速度及索引本身进行改进。
4 结束语
本文对多种全文检索模型进行了分析与研究，实现了具体的检索系统原型，通过实验对不同检索模型的检索性能进行了验证，为今后检索模型的选择及检索性能的改进与优化提供了实验依据及思路。
摘要：对比研究了多种全文检索模型,实现了相应的系统原型,并通过实验对模型的检索性能进行了验证,为检索模型的选择与检索性能优化提供参考。
关键词：全文检索,检索模型,检索性能
参考文献
[1]王珊,文继荣.数据库与信息检索技术的融合[J].中国计算机协会通讯,2006,2(4).
[2]罗良道.高校图书馆Web站点站内搜索引擎的调研与建设[J].情报科学,2002,20(9):946-948.
[3]龙怡,刘俊熙,等.我国省级政府门户网站搜索引擎现状调研报告[J].现代情报,2008,1:212-215.
[4]徐小刚,王俊杰,等.全文索引的研究[J].计算机工程,2002,28(2):101-103.
[5]郎小伟,王申康.基于Lucene的全文检索系统研究与开发[J].计算机工程,2006,32(2):94-96.
基于语言模型的信息检索研究 篇6
1 理论基础
语言模型在信息检索中的应用通常基于以下贝叶斯规则:
其中, P (D) 表示离散随机变量“文档”, P (Q) 表示离散随机变量“查询”。根据这一公式, 对P (D|Q) 的估计可以转化为对P (Q|D) 和P (D) 的估计, 而前者在一定程度上可以看成是语言模型的研究对象。
因为对P (Q|D) 的估计将与真实值间存在可预见的差距, 另外在没有任何文档关联数据和用户使用数据的情况下, 对P (D) 的估计暂时缺少有效的方法, 所以研究者通常将所有文档的P (D) 值视作相等。由此对P (D|Q) 的估计就完全转化为对P (Q|D) 的估计。需要指出的是, 可能存在有效的估计P (D) 的方法, 尤其是在检索系统所广泛应用的Web文档环境中, 或者在有充足的用户访问数据的情况下, 对P (D) 引入某种估计 (例如链接分析和查询反馈) 就相对容易, 且完全可能有助于改善检索效果。因而包含P (D) 的完整评估是基于语言模型的信息检索更具一般性的基本框架。
2 Ponte与Croft先驱性工作的本质及修正
Ponte与Croft的基本思路是在事件独立假设条件下, 对词项在文档所生成的查询中的出现概率作整体估计, 其估计P (Q|D) 值的计算实质为:
其中, t表示词项, Uq表示查询q中词项的集合, V表示整个文档集中所有词项的集合。基于此, Ponte与Croft设计了一套复杂的计算步骤用于文档评分。经过一定的分析可发现, 其具体实现中存在一些问题, 在此针对这些问题作出如下细节修正:
1) 显然若要保证数学上的严谨性, 对于任意一个特定的查询, 每份文档评分的因子数均等于整个文档集的词项总数, 这无疑将使检索系统陷入过于巨大的计算量中, 因而实际的系统必然需要将公式2简化为:
其中, Wd表示文档d中词项的集合。
2) 原文对词项t在所有含有t的文档中的平均出现频率f軃 (t) 采用如下公式计算:
其中, f (t, d) 表示t在d中的出现频率, dct表示含有t的文档数。不难发现若使用该公式, 则由之所得到的和值与cct值不相等 (ld为d的长度, cct为t在整个文档集中的出现次数) , 这是数学上的一处漏洞, 因而在这一细节上也需要将公式修正为:
3) P&C方法对P (t∈Uq|D=d) 值的估计十分繁琐, 本文将比较采用如下简化公式与P&C方法的实验效果的差别:
其中, cf (t) 表示t在整个文档集中的出现频率。
需要特别说明的是, 上述第一和第二项修正系分别针对计算复杂性和数学严密性所作的必要调整, 不影响最终的对比实验结论。而第三项简化改进则是本文对P&C方法有效性考察的关键点。
3 成为主流的另一条路线
在同年稍晚些进行的TREC-7会议上, 两个参与检索评测的小组——BBN和Twenty-One——采用了与P&C方法相似但不同的思路。他们对P (Q|D) 值使用下式进行估计:
这里的P (Qi=t|D=d) 与P (t∈Uq|D=d) 并不是同一个概念。后者指的是文档d生成的查询q中包含词项t的概率, 而前者指的是文档d生成的查询q的第i个词项为t的概率。
Zhai指出, P&C方法使用的是n元伯努利模型, 而两个小组以及之后的一系列相关研究采用的是多项式模型, 也是真正意义上的一元语言模型[2]。值得注意的是, 两者对贝叶斯规则 (公式1) 所作用的查询-文档匹配环境而言, 前者的查询长度不限 (可以为0) , 而后者将查询长度锁定为一个特定值。
4 对两种构架的进一步比较分析
尽管两种方法在理论基础上存在上一节所述的本质区别, 但由于在实际操作中对各自的核心概念均采用基于词频的演化公式进行估计, 因而在计算上具有很大的相似性。只是后一种方法增加了一项约束条件:
而针对零概率问题, 研究人员在上述约束条件下采取了某些平滑措施, 以下是其中较为典型的两种:
1) Jelinek-Mercer方法
2) 贝叶斯平滑
在公式9中令, 则恰好可以得到公式10, 因而可以发现, 这两种典型的平滑方法事实上是等价的。我们的实验将对平滑的有效性进行验证。
5 实验和结论
对两种构架进行了一系列实验, 使用的数据集为五个英文标准测试文档集ADI、CACM、CISI、CRAN、MED。所采用的评测指标为所有查询在每个可测召回率点上查准率的平均值。表1给出了对P&C方法进行各项修正后的评测结果。
*号表示对同一文档集相对最佳的评测值, 下同。
简化改进前后的评测效果相差无几 (甚至有三个文档集在简化后评测效果更佳!) , 证明P&C将计算复杂化并不能进一步有效改善检索, 这也是之后的研究者没有继续沿承其细节的原因。但P&C方法无疑对信息检索语言模型提供了一个很有意义的思路和方向。
针对第二种构架, 由于两种平滑方法的等价性, 本文的实验只针对Jelinek-Mercer方法进行。表2给出了λ取值从0.1到0.9的实验结果。
与表1所示的数据相比较后可以发现, 第二种构架不仅在计算效率上高, 而且能够在整体上获得一定的检索性能的提升。
后两个文档集对统计方法的变化不敏感, 体现了单纯基于词频的统计方法的局限。可以预见, 引入基于词项关联性等的语义统计方法能够更进一步提升检索评测结果。
参考文献
[1]J.Ponte and W.B.Croft.A Language Modeling Approach to Information Retrieval[A].Proceedingsof the ACM SIGIR[C], 1998.
经典信息检索模型的分类比较 篇7
信息检索技术在许多领域中都有相应的应用,例如:Web搜索引擎、图形图像检索、视频检索、构件检索等。在这些领域中,采用的主要检索模型都是以信息检索中的经典模型为主。从数学理论角度来看,信息检索模型可以分为集合论模型、代数论模型和概率论模型。其中,集合论模型以布尔模型为基本模型,加入集合论理论进行扩展;代数论模型是在向量模型的基础上,添加特殊假设前提构造不同的信息检索模型;概率论模型以概率模型为基础,增加推理网或信任网理论。图1显示了从数学理论角度对信息检索模型进行的分类。
在信息检索中,信息对象和用户的信息需求都是使用一组索引术语集合标识的。因此,存在信息丢失或遗失的现象,信息检索结果的精确度并不是很高。为了提高检索结果的准确率,就需要预知文档和检索需求的相关度,这就依赖于对检索结果中的文档进行排序的算法(ranking algorithm)。不同的计算文档相关度的假设前提就会导致不同的信息检索模型。由图1可以看出,经典信息检索模型主要有三类:布尔模型、向量模型和概率模型。在经典模型中,使用一组关键字(称为索引术语)来描述每篇文档。一般索引术语是一个名词或名词词组。假设ki是一个索引术语,dj是集合中的一份文档,则使用wi,j≥0说明描述文档dj的术语ki的重要程度。用户的信息需求Q也表示成索引术语的集合。不同的检索模型中,相似度函数sim(dj,qi)是不同的。
1 布尔模型
布尔模型是基于集合论和布尔代数的检索模型。因此,查询请求表示为由not、and和or构成的索引术语的布尔表达式,例如,[q=ka∧(kb∨kc)],它可以转换为析取范式(DNF),并且,索引术语ki与文档dj相关联的权重是二元的,即wi,j∈{0,1}。
对于布尔模型,索引术语权重的取值范围为wi,j∈{0,1}。查询请求q是一个传统的布尔表达式,是查询请求q的析取范式。此外,假设的任意合取构成因子。文档dj和查询请求的相似度被定义为:
在布尔模型中,如果sim(dj,q)=1,则表示文档dj和查询请求q是相关的;否则,是不相关的。
2 向量模型
由于二元权重并不能对检索出来的文档进行相关度排序,因此,需要使用非二元的权重计算文档和查询请求的相关度。向量模型就是这样一个信息检索模型,索引术语的权重是非二元的,并且使用索引术语的权重计算索引术语和文档的相关度,以及索引术语和用户查询请求的相关度。向量模型可以对检索结果中的文档按照与查询请求的相似度的不同进行排序。
向量模型中,权重wi,j是一个和(ki,dj)相关联的非二元的正数。查询请求中的索引术语也带有权重。假设wi,q是一个和(ki,q)相关联的权重,其中wi,q≥0。定义查询请求向量,其中,t是系统重索引术语的总数。文档dj的向量可以表示为。
因此,文档dj和用户的查询请求q都被表示成一个t维向量。文档dj和用户的查询请求q的相似度可以表示为向量dj和向量之间的夹角θ的余弦cosθ。即:
在向量模型中,如何计算索引术语的权重是一个重要问题。目前有许多方法计算索引术语的权重。其中,TF-IDF是最常见的方法。表1给出了TF-IDF方法中使用的符号及其定义。其中,tfi,j是一个度量术语ki描述文档dj效果的因子,idfi是一个体现术语ki在系统的术语集中的重要程度的因子。根据TF-IDF方法,索引术语和文档的相关度为TF和IDF的乘积,即wi,;j=fi;j×idfi。然而,索引术语和查询请求q的相关度为。
3 概率模型
概率模型是基于一个基本假设(概率原理)的:给定一个用户的查询请求和集合中的一篇文档dj,概率模型尽量评估用户找到相关的文档dj的概率。模型假设相关的概率只依赖于查询请求和文档的描述。并且,假设针对查询请求q,存在一个结果集的子集。
概率模型中,索引术语的权重也都是二元的,即wi;j∈0,1;wi,q∈{0,1}。查询请求q是一个索引术语的子集。假设R是已知的相关的文档的集合,是R的补集(即不相关的文档的集合)r定义为文档dj和查询请求q相关的概率,为dj和q不相关的概率。则文档dj和查询请求q的相似度为:
根据贝叶斯概率公式,相似度函数可以变为:
其中,表示从集合R中随机选择文档dj的概率,P(R)表示从文档全集随机选择文档是相关的概率。由于,对于文档全集而言,随机选择文档相关的概率和不相关的概率是一样的,即,所以有。假设索引术语之间是相互独立的,所以可以使用术语ki表示集合R中文档的概率(记为P(ki|R))来转化相似度函数:,对上式取对数,并且考虑,得:
其中,P(ki|R)和可以使用下面的递归迭代的方法进行计算:
其中,ni是包含索引术语ki的文档数,N是集合中文档总数,V是进行检索的构件子集,Vi代表集合V中包含索引术语ki的文档的集合。初始的设定为V=1和Vi=0,终止条件为V=N,Vi=ni。
4 经典模型的比较
根据定义信息检索模型的定义和模型的优缺点,我们给出布尔模型、向量模型和概率模型的简要比较,如表2所示。经典模型中,文档都使用向量来描述,只是术语的权重取值不同。
5 扩展的集合论模型
5.1 扩展的集合论模型
在布尔模型中,权重的取值只有二元(0和1),然而二元权重并不能对检索出来的文档进行相关度排序。扩展的集合论模型也主要是从权重计算的角度对布尔模型进行扩展。模糊集合模型采用模糊集合论对查询请求和文档进行建模,采用计算术语之间的关联性的方法扩展术语的权重;扩展的布尔模型一种在布尔模型中使用向量模型的术语权值计算的检索模型,采用了对布尔操作符进行运算扩展,将相似度计算转换为欧几里得距离,以避免布尔模型的权重二元的缺点。
5.2 扩展的代数模型
在向量模型中,要求术语之间相互独立,但是,往往选取的索引术语并不可能相互独立,因此需要对向量模型进行扩展。广义向量空间模型的核心思想是引入相互正交的向量集合,代替原有的索引术语在,广义向量空间模型中将不相互正交的t个术语转换为2t个子项,每个子项对应一个2t-维向量,这些向量之间彼此相互正交;潜在语义索引模型核心思想是将文档和查询请求映射到一个较低纬度的概念空间,即对术语-文档矩阵提取特征向量和奇异值,进行降维运算,从而得到低维的文档-文档关联矩阵,根据该矩阵直接进行检索;神经网络模型将“查询请求-术语-文档”的匹配转换为神经网络模型,通过信号传递的过程,可以进行用户反馈参与的检索。
5.3 扩展的概率模型
扩展的概率模型主要采用的是贝叶斯网络。贝叶斯网络是一个有向无环图,节点代表随机变量,边代表变量之间的因果关系,使用条件概率表示因果程度。其中,推理网络模型和信任网络模型是最常见的两种基于贝叶斯网络的概率模型。推理网络模型是从“文档-术语-查询请求”的贝叶斯网络,因此,其样本空间不确定;信任网络模型是“文档-术语”和“查询请求-术语”结合的贝叶斯网络,其样本空间确定,即为术语的集合。
6 结论
目前,信息检索的研究已经趋于成熟,并且大多技术和方法都已经应用到许多领域中。信息检索的主要问题之一就是检索模型问题,即如何计算文档和查询请求的相似度,根据文档和查询请求的相似度检索文档,产生相应的排序序列。信息检索中,基本的检索模型为布尔模型、向量模型、概率模型以及这三个模型的扩展模型。这几种模型在具体使用的时候各有优劣,因此,在设计具体的检索系统时,需要分析检索对象的特点,采取合适的检索模型。
摘要：信息检索的模型,主要是用于检索和排序的计算用户查询请求和信息的匹配程度的问题。目前已有的检索模型有布尔模型、向量模型、概率模型以及以上三个经典模型的变形模型。通过对经典模型进行分析比较,以便在设计具体的检索系统时,根据检索对象的特点,采取合适的检索模型,提高检索效率。
关键词：信息检索,经典模型,扩展模型
参考文献
[1] Salton, G. and Buckley, C. Term weighting approaches in automatictext retrieval. Information Processing and Management, 24(5):513–523. (1988).
[2] Fuhr, N. Probabilistic models in information retrieval. The Computer Journal,35(3):243-255. (1992).
[3] Ogawa, Y., Morita, T., and Kobayashi, K. A fuzzy document retrieval system using the keyword connection matrix and a learning method. Fuzzy Sets and Systems,39:163-179. (1991).
[4] Salton, G., Fox, E., and Wu, H. Extended boolean information retrieval.Communications of the ACM, 26(11):1022-1036. (1983).
[5] Zadeh, L. Readings in Fuzzy sets for intelligent systems, chapter Fuzzy sets.Morgan Kaufmann. (1993).
[6] Wong, S., Ziarko, W., and Wong, P. Generalized vector space model in information retrieval. In Proceedings of the 8th ACM SIGIR Conference on Research and Development in Information Retrieval, pages 18-25, New York, USA. (1985).
基于本体的语义信息检索模型研究 篇8
随着互联网技术的快速发展,人类已进入信息时代,尤其是当前大数据背景下网络信息资源的数量越来越庞大,其已成为全球最大的信息库,且网络信息资源随之呈现出更加复杂的特性,暴露出一些亟待解决的问题[1,2,3]。然而,传统信息检索模式面对文本字符串匹配的语法层面,缺乏针对信息表示及处理和理解的语义层面分析,即信息是丰富的,而知识却是贫乏的,所以依赖传统的信息检索方式已很难满足用户需求,而本体及其相关理论技术的出现为解决这一问题提供了可能。
本文将利用本体建立标签之间的语义关系,并引入语义与Agent技术,实现标注系统的语义检索,通过语义模型丰富的描述能力和强大的逻辑推理能力准确描述信息资源,以Agent组织完成用户交互、信息检索、信息过滤、结果返回,构建一种基于本体学习的能够实现语义层面分析的检索模型,以弥补传统信息检索的不足,进而从信息查全率和查准率方面改善信息检索的效率。
2 基于本体的语义检索模型构建(Construction of semantic retrieval model based on ontology)
基于领域本体的语义检索,可依据领域本体知识库对信息资源或文档进行语义标注,本体概念的语义信息可借助本体概念定义及本体概念之间的关系进行描述,因为特定专业领域的概念可通过领域本体进行描述,这样可使文档或信息资源更具有语义,且可揭示出用户检索词的语义,把从文档和用户查询抽取的关键词转换为具有语义的本体概念,实现基于关键词的语法检索到基于本体概念的语义检索的提升,其中,语义检索与传统基于关键词匹配的检索方式不同,因为语义检索基于信息理解的语义层面对信息资源及用户提交的检索请求进行分析,语义检索方式对检索条件、信息组织以及检索结果均赋予了语义成分,可从语义层面提高检索精度[4,5,6,7]。
2.1 领域本体的语义检索理念
基于领域本体的语义信息检索,其理念在于使信息资源或文档进行语义描述,借助领域本体知识库完成对文档和信息资源对象的语义标注,进而揭示出文档和信息资源对象的语义理解,及其用户检索词的语义信息,同时可实现领域本体检索词的语义扩展,最终完成理想检索结果的获取,具体检索过程为:
step1:构建并描述领域本体概念。描述领域本体概念,构建领域本体知识库。
step2:提取文档或信息资源对象特征并进行资源映射。借助领域本体概念描述及知识库构建和管理,对获取的信息资源或文档进行语义标注及资源映射,对信息资源或文档语义内涵进行揭示。
step3:制定本体概念扩展及查询语义扩展策略。在领域本体概念描述的基础上,对用户查询请求的语义信息进行揭示,并对用户检索词进行语义扩展,检索系统完成对生成的备选检索词集的检索工作。
step4:实现领域本体概念相似度算法。依赖本体概念结构图,实现本体概念语义距离计算算法、本体概念节点深度计算算法及语义综合相似度计算算法,以此服务于查询结果排序环节。
step5:对检索系统的检索结果进行排序。基于相关相似度计算算法及规则,完成用户原始检索词及检索系统返回检索结果的相似度比较,基于相似度对检索系统的检索结果进行排序并反馈给用户。
2.2 领域本体语义检索模型
领域本体语义检索模型,如图1所示。
图1 领域本体语义检索模型 Fig.1 Domain ontology semantic retrieval model
(1)领域本体及其分类体系作为数据资源语义表征的核心,可对文档或数据资源描述给予指导。领域知识也作为查询扩展和查询结果排序的基本依据。因此,领域知识的构建和维护,如领域本体、推理规则的构建和维护,离不开领域知识管理。
(2)数据资源或文档的语义可通过标注进行语义揭示,再借助文档特征提取技术,从领域本体词汇中获取本体概念,建立数据资源或文档的语义特征域,完成数据资源库文档的自动标注,并完成标注和索引信息资源或文档的非语义特征,由此生成文档索引库和元数据库。
(3)基于文档或数据资源标注信息构建索引库,以此为依据,检索出能满足用户需求的文档或数据资源信息。
(4)实现查询扩展及结果排序,就是以领域本体生成的本体词汇库为依据,完成用户查询输入文字的分词工作,将用户查询分成本体概念集合和非本体概念集合。然后,分别对这两个集合按相似度扩展,得到两个查询候选集合,以此为依据,借助相关相似度排序算法获得排序后的查询集,最后,完成查询请求到索引库及检索库的提交环节,将查询结果按查询请求的相似度排序后,将结果推送给用户。
3 关键算法实现(Key algorithm implementation)
3.1 四元组本体内涵及其数学描述
基于四元 组的本体 概念描述 为 :F=(U,T,J,Y)基于四元 U={u1,u2,...,u|u|}组的本体 概念描述 为 : , 其中 , 表示用户 , 描述使用 标签管理资源的用户,并且每个用户有唯一的ID号标识。T={t1,t2,...,t|T|} 表示标签,描述集合U中用户使用过的标签,标签可以是任意的字符串(单词或短语),现定义标签为一组词语序列,t=(term1,term2,...,tremm) ,t∈T , 公式t=(term1,term2,...,tremm)描述 标签t映射 成一组术 语 , 术语可以 是任意单 词 。J={i1,i2,...,i|J|}。表示资源,描述所有领域相关资源, 其内容取决于用户标注集的类型,用户标注集主要由用户、标签、资源三个要素组成,即用(U,T,J)进行描述表示三元关系,其中(u,t,i)元素描述用户u使用标签t标注收藏的资源i 。函数式F(u,i)描述用户u使用一组标签定义一个资源i:其中u∈U,i∈J 。
为了理解用户标签含义及标签之间的关系,构建主干本体,用二元组进行描述: BackloneONTO=(C,R), 其中C={c1,c2,… ,c|C|} 表示 概念集,概念c=(id,synset,gloss,categorg) ,id是概念c的唯一标识, synset是同义词集合,包含了概念c的同义术 语集合 , gloss是描述概念c的短语 , category是将概念c分类到泛化类中的词类,也可将四个元素分别记为:id(c),synset(c),gloss(c),category(c);R={r1,r2,…,r|R|} 表示概念集之间的 关系 。为一组同 义词集合,资源w∈S,定义w一组同义词集合及synset里资 源 ,con(w)={c|w∈synset(c) , 每个资源w∈sybset(c)用二元组 表示为 :(w,freqc(w)) , 其中 , freqc(w)为资源的 频率分配 。 三元组r=(type,x,y)表 示关系集合R中的关系 , 其中 ,x,y 是关系r的两个关系项。
3.2 资源映射方案设计
一个标签可以映射成一个或多个概念,也有可能只有部分标签可以映射成一个或多个概念,现提供几种资源映射方法。
(1)直接映射
直接映射描述标签到概念的映射,即将每个标签映射到本体中的概念,可表示为:
其中,概念集合中的每个t都是synset中的一 个资源 ,Tag_Concept(t)描述标签 到概念的 直接映射(Tag-to-Concept)。
此外,标签t也可认为是概念的映射:其中是标签集合。
(2)部分映射
当标签不能直接映射时,从开始到结束的时间,可按如下步骤完成部分映射。
step1:将短语逐步缩短成一个词。
step2:基于英语语法,从短语的左边开始,尝试在哪个阶段可以映射缩短短语,然后从右边进行完善修改。
(3)资源映射
现定义用 于描述标 签和概念 之间映射强度的Term_Concept矩阵:在映射过程中将产生初始矩阵,初始矩阵的映射强度是相关联的synset资源单词频率:
映射结束后,初始矩阵的值表示语料库中ti和cj的映射强度。
3.3 本体概念扩展策略制定
(1)本体概念扩展
本体概念扩展步骤如下。
step1:对每个本体概念进行扩展。
令为领域本体概念集, 为两个本体概念的相似度。如果对本体概念C1进行语义扩展可形成其中集合 中每个元素C1k(0＜k＜i)要么为 空 , 要么
也就是说,可基于相关相似度计算算法扩展单个本体概念c ,选择相似度大于给定阈值的本体概念,并且被选取的本体概念同其他用户本体概念之间的相似度,比该被选取本体概念同当前单个本体概念之间的相似度小。
step2:构建本体概念查询集。对用户本体概念集的元素进行扩展,其中的每个概念元素都可扩展为一个扩展集 ,可分别从每个中进行本体概念的选取,构建本体概念查询集,查询本体概念集的组员就是从每个本体概念扩展集中选取的概念,查询本体概念集描述为:
其中 , f1在ε(C1)中选取 , f2在ε(C2)中选取 。 所有本体 概念查询 集可描述 为每个本体概念集fc={f1,f2,…,fn}与用户输入的未扩展的本体概念集CS={C1,C2,…,Cn}相似度可由下式计算:
其中, φ为调节参数,其值一般为0。
令为用户输入的未扩展的本体概念集CS中的元素个数,所以sim_semantic(fc,CS)可描述为:
其中,允许多个φ存在于每个本体概念扩展集中,且φ=0,则sim(φ,C)=0,也就是说,空集与任何本体概念集,其相似度为0。
(2)扩展关键词集合
关键词的扩展相对简单,因为关键词不是本体概念, 所有扩展的集合所组成的集合为原关键词集的幂集,记为P(HS) ,其中的元素本身也是集合,且与用户输入的原关键词集之间的相似度计算也并不复杂,现令P为幂集P(HS)中的元素,则P与HS之间的相似度计算模型为:
其中, φ为调节因子,通常也取值为0。
如果HS集合中的元素个数为m,则上式可化简为:
3.4 本体概念相似度算法
领域本体可描述特定领域中的概念及其关系,并可形成本体概念结构图,该本体图可计算本体概念相似度,其实本体概念结构图可看作为带有根节点的有向无环图,本体概念用图中的节点进行表示,概念之间的关系通过有向边进行表示,且该本体概念结构图具有树型结构的层次结构特性,及有向边和多重继承的特性。具体算法步骤如下:
step1:本体概念语义距离的计算。
基于本体概念图,本体概念的语义距离表现为连接两个概念节点的有向边的数量,记为disk(Ca,Cv)。本体概念语义距离与本体概念语义相似度之间的关系为:两本体概念语义之间的距离越大,则这两个本体概念之间的相似度越小;反之,两本体概念语义之间的距离越小,则其之间的相似度就越大,即两者成反比关系。
step2:本体概念父节点深度的计算。
基于本体概念所体现的层次结构特点,对本体概念节点进行自顶向下的组织,及由大到小的分类,依据本体概念最近共同父节点所在层次,可知其层次越深,本体概念分类越细,从其父节点继承的语义信息就越多,其共同语义信息就越多,即Ca,Cv这两个本体概念间的相似度就越大。现用depth(father(Ca,Cv))描述两概念的最近共同父节点深度,father(Ca,Cv) 表示两概念最近共同父节点。
step3:计算语义重合度。
本体概念之间的语义重合度计算可依据两本体概念间所包含的相同父节点个数来完成,但如果同时对本体概念语义距离和本体概念语义重合度加以考虑,则存在重复计算的可能性,因为本体概念语义距离中隐含着本体概念语义重合度信息,所以可基于本体概念语义距离和共同父节点在本体概念结构图中的深度,计算出本体概念相似度,令两本体概念a、v ,则 a、v 的语义相似度可通过 a、v 的语义综合距离和a 、 v共同父节点的综合深度对相似度影响的加权归一化进行表示,计算如下:
其中, α为语义距离加权值, 表示共同父节点的加权值,且满足α+β=1,语义距离决定的相似度可通过调节参数k进行调节,maxdepth表示本体概念树的最大深度。
step4:本体概念综合相似度计算。
如果对用户检索词集中的本体概念进行语义扩展,可生成查询语义扩展集,记为FC(CS) ,如果对用户检索词集中的非本体概念的关键词集进行扩展,可生成关键词集的幂集, 记为P(HS),现从FC(CS)中取一元素,记为fc ,该元素是一个扩展概念集,再从P(HS)中取一元素,记为p,该元素为一个扩展关键词集,便可形成一个提交给检索系统的检索请求,表示为(fc,p),令用户检索词集为(CS,HS),每一个扩展的检索请求记为(fc,p ),则通过(CS ,HS )和(fc,p)相似度的计算,可得到用户检索词集和检索结果的相似度。现基于扩展关键词集相似度、扩展本体概念集相似度、分类概念集相似度,可计算出综合相似度,数学描述如下:
其中,λ1、λ2为调节参数,λ1代表本体概念集相似度与综合相似度的比值,λ2代表关键词集相似度与综合相似度的比值,且λ1+λ2=1 。
4 实验与结果分析(Experiment and result analysis)
本实验环境为:Windows 7操作系统,SQL SERVER 2008数据库平台,模型数据库动态链接查询实现工具为某专业数据库数据及WEB技术。建立领域本体的开发工具为: 5.0的PROPERTY BROWSER环境,每个词条类的构建借助Object Property属性实现,因为Object属性可在类与类之间建立不同层次的关系描述,而且两个Object属性之间存在多种关系。如果基本父类建立完成后,还可为每个父类添加不同的子类和属性,同时还具有继承特性,即所有子类都可继承其父类的基本属性。
实验步骤为:
step1:对选取知识本体的专业领域及范围进行确定,基于自顶向下的顺序,构建本体概念和术语清单。
step2:对基础词库进行完善。
step3:依据分类体系层次,对本体实例进行添加,构建整个领域本体。
本体概念语义信息检索模型测试指标通过查准率和查全率进行衡量,分别描述为:
同时,借助M对检索结果进行评价及对比分析,以便于全面衡量其检索效果,M的计算公式描述为:
它为检验本体概念语义信息检索模型,将其与传统关键词检索模型进行实验对比分析,对抽取的某领域的标准词条进行测试,从中随机选择四个词条实验样本,分别以相同词条在本文模型和基于关键词模型中检索,实验结果详见表1、表2和图2所示。
图2 实验结果 Fig.2 M test results
由以上实验结果可知,领域本体概念的语义信息检索模型效率高于传统关键词信息检索模型,且语义检索的也高于传统关键词检索,表明本体概念语义检索模型具有一定的理论及实用价值。
5 结论(Conclusion)