根据语义的图像信息检索-毕业论文

本科毕业论文(科研训练、毕业设计)题 目：根据语义的图像信息检索姓 名：学 院：软件学院系：专 业：软件工程年 级： 学 号：指导教师（校内）： 职称： 指导教师（校外）： 职称： 年 月摘 要随着网络上图像信息量的爆炸性增长，如何从海量的资源中迅速找到自己所需要的图像，也成为了一项具有挑战性的任务，而图像检索技术正是因此而逐渐产生。图像检索技术自从它兴起至今，经历了好几个阶段，这个历程说明图像检索只有结合图像的多种信息，特别是语义信息，才能使检索系统的能力尽可能符合人们的要求。本文主要介绍了基于语义图像检索的历史和现状，阐述了构建语义检索系统的几个关键技术，对本小组所开发的图像检索系统中对本体模型的检索方法和显示做了相关的介绍。特别以OWL定义产品信息的知识模型，用知识模型标记图像检索系统中的信息，通过度量语义标记的相似性来获得产品图片信息的相似性。同时，文中还介绍了此系统界面的详细设计方案，以及各小组成员所负责工程部分的容合。关键词：基于语义图像检索 本体 OWL 界面设计AbstractImage information exist in Internet is growing on a violent speed these years. So, finding the way which can get the picture that someone actually need in a jillion resources is now a challenging work, in that condition the image retrievaling technology come into being. From a historical point of view, we find that only if we use all kinds of image content, especially image semantics, that the capability of retrieval system can close to humans image understanding ability.This paper first introduces the history and present situation of the Semantics-based Image Retrieval and elaborates several key technologies of building Semantic Retrieval System. You can see a detailed presentation of the Ontology Model Retrieval as well as the display of the ImageSearch System. Particularly the knowledge model of the product information is defined in the OWL language, the information of the ImageSearch System is marked by the knowledge model and the productphoto information similarity is obtained through measuring the similarity of the semantic mark. The similarity of Ontology concept contains three elements: the concept of Ontology, semantic and similarity. The system has a friendly and natural user interface. Experiments show that, the ImageSearch System is able to retrieve images in a higher hit rate. Simultaneity, the design of interface is also will be introduced in this paper, at last this paper will intrdouse the conformity of the ImageSearch Systeam. Key words ：Semantic-based Image Retrieval Ontology Owl; the design of interface.目 录第1章 引 言81.1 基于语义的图像检索技术的诞生和发展81.2 选题目景9第2章 系统相关概念简介102.1 本体及本体中的概念102.1.1 基本概念102.1.2 本体的主要构成102.1.3 本体的作用112.1.4 知识本体语言112.2 本体中的概念122.3 语义相似性度量12第3章 系统设计143.1 设计思路143.1.1 系统目标143.1.2 核心算法设计143.2 对界面的构思153.3 结果处理模块设计153.4 系统结构设计163.5 本章小节16第4章 算法的实现174.1 语义相似性度量在系统中的应用174.1.1 OWL个体的相似性及排序算法174.1.2 Vector排序算法214.2 知识服务在查询浏览中的应用224.2.1 基于OWL个体的查询方式234.2.2 相似查询与浏览23第5章 界面设计255.1 详细介绍25第6章 结果处理模块的实现276.1 设计目标276.2 具体实现27结束语29致 谢30参考文献31ContentsChapter 1 Introduction81.1 Birth and development of sematic-based image retrievaling technolog81.2 Background of the topic9Chapter 2 Introduction of Relative Concept102.1 Ontology102.1.1 Basic Concept102.1.2 The Composing of ontology102.1.3 The use of ontology112.1.4 Ontology Language112.2 Some concepts in ontology122.3 Semantic similarity metric12Chapter 3 Systematic design143.1 Design ideas143.1.1 The goal of the system143.1.2 Design of the core algorithm143.2 Thought of the interface design153.3 Results Processing Module design153.4 Systematic structure design163.5 Summary16Chapter 4 Implementation of the algorithm174.1 The application in the system of the Semantic similrity metric174.1.1 The similarity and sortint algorithm of individual OWL174.1.2 The sorting algorithm of Vector214.2 The application of knowledge service in query and browse224.2.1 The query approch based on individual OWL234.2.2 Similarity query and browse23Chapter 5 Interface design255.1 Details25Chapter 6 Implementation of the Results Processing Module276.1 The goal of the Design276.2 Details27Concluding Remarks29Acknowledgement30References31第1章 引 言1.1 基于语义的图像检索技术的诞生和发展视觉信息是人类从客观世界获得信息的主要来源，也是人类认知世界的重要功能手段它占人类依靠五官由外界获得的信息总量的80%，人类对五彩缤纷的大干世界的认识上至宇宙星云，下至细胞、基因、原子，无一不是通过视觉形象信息获得深刻的感知进而得到正确的认识的多媒体技术及Internet迅速发展的今天，将数字图像鼬理、模式识别技术、计算机视觉技术与传统的数据库技术结合起来，建立有效的图像描述和检索机制也就必然成为迫切需要解决的问题实际上 20世纪70年代末，基于文本的图像检索技术就已经产生，它通过对图像进行手工注解，利用文本检索技术进行关键字的检索但是，基于文本的图像检索方式存在着两大难题 ：一是完全手工注解的工作量太大；二是文本注解的不可避免的主观性和不精确性不可否认，文本标注在描述高层的、抽象的语义概念时，有其简单、清楚的优点但如何提供相应的手段，扬长避短发挥其优势，是一个重要的课题。2O世纪90年代初，大规模图像集合不断涌现，研究者们提出了基于内容的图像检索(content basedimage retrievalCBIR)CBIR使用颜色，纹理、形状及区域等视觉特征 ，而这些视觉特征是唯一可以独立、客观地直接从图像中获得的信息这一方法成为20世纪90年代图像检索技术研究的主流1这类系统主要支持基于范例检索(exarctplc basedretrieva1)、基于草图检索(sketchbased retrieva1)和随机浏览其组台的工作方式CBIR的主要特点是利用图像本身包含的客观视觉特征图像相似性体现在视觉相似性上，不需要来解释也就不需要或者仅需要少量的人工干预，尤其是在需要自动化的场合取得了大量应用然而，人们判断图像的相似性并非仅仅建立在图像视觉特征的相似性上。二是用户在进行图像检索时总是存在一个大致概念，这个概念建立在图像所描述的对象、事件以及表达的情感等含义上理想的状况下，用户主要根据图像的含义，而不是颜色、纹理、形状等特征，直观地进行分类并判别图像满足自己的需要程度这些图像的含义就是图像的高层语义特征，它包含了人对图像内容的理解，这种理解是无法直接从图像的视觉特征获得的而要根据人的知识来判断人与计算机的本质不同就在于人观察图像时结合了日常生活中积累的大量的经验，观察图像的过程同时也是一个利用知识推理图像语义的过程图像必须附加包括语义在内的各种内容信息，才能真正支持语义检索，重要的是要提供建立这些内容信息的过程利用计算机视觉和机器学习的方法来让系统对于某些特定情况做出特定反应，是长期以来很多研究者努力的方向，对象识别和场景识别即是其中的一部分使计算机检索图像的能力接近人的理解水平这就是语义图像检索的目的语义图像检索是更合理的图像检索方式虽然目前CBIR作为一项倍受关注的技术在研究和商业方面都取得了一定成果，但由于它只利用了图像本身固有的物理信息，因此它只在特定的应用领域如指纹识别、商标检索等方面获得成功2而要使图像检索技术真正满足用户个性化的需要必须把图像检索看作一个系统，考虑包括人在内的各种因素对于系统的影响其中主要的工作和面临的困难来自3个方面： 必须提供图像语义的有效描述方式；必须有提取图像语义描述的方法，语义检索系统的语义处理方法为此，本文将从这几个方面对图像语义的建模和表示、图像语义的抽取方法和语义检索系统的设计等研究状况进行归纳和总结，并由此提出图像语义的进一步研究方向和思想1.2 选题目景针对此次本科毕业设计的选题，我们导师有小组成员主要从以下几个出发点来考虑： 紧靠本专业四年大学生活所学知识体系； 所选题目具有一定的难度但又不会超过学生所掌握知识的范畴； 所选题目具有一定的研究价值，最好是当前比较热门的研究课题； 能够一定程度上起到考查学生和锻炼学生的作用。基于以上几点，我们老师为我们选定一个工程类型的毕业设计。此项目名为ImageSearch，项目产品为一个适合用于进行个人图像标记和检索的工具软件。项目关注于基于语义的图像检索技术，其中牵涉到最多的主要概念为本体，OWL-DL语言和语义相似度。项目采用Java语言，使用eclipse开发工具，junit单元测试工具和CVS版本同步工具进行开发。此选题最大的优势是：在研究语义图像检索技术的同时也得到了软件工程能力上的锻炼 第2章 系统相关概念简介2.1 本体及本体中的概念2.1.1 基本概念本体论是西方哲学中形而上学的一个分支学科，研究的是关于自然和存在的关系3。在二十世纪的分析哲学中，本体论是研究实体存在性和实体存在本质等面的通用理论。在中国古代哲学中，本体论又被称为“本根论”，是指探究天地万物产生、存在、发展变化的根本原因和根本依据的学说4。在近十多年来，本体在知识工程和信息系统领域占据了越来越重要的地位。知识是知识工程研究的焦点。但是在知识工程中知识是泛指的，包括不同领域、不同性质和不同目的的知识。为了利用这些不同的知识，人们提出了各种各样的知识表示和推理方法，开发出了各种基于知识的系统。但随着这些基于知识的系统的增加，人们发现由于采用不同的知识表示和推理机制，这些系统间的知识难以共享，系统间难以互操作。而本体论的哲学思想在于，本体论研究实体的存在性和实体存在的本质，是独立于任何语言而存在的深层次的本质上的知识。因此本体论把知识工程中的知识向更深入、更本质的方向推进了一步。在知识工程领域中存在着多种本体定义。其中Studer在Gruber和Burst的定义基础上给出了一个较全面的本体定义7。“本体是概念化的一个显式的，共享的形式化表示。概念化表示本体是一个用由一组相互关联的概念构成的抽象模型，它被用于解释现实世界某些现象。显式表明构成模型的概念类型和约束是被显式定义的。形式化指本体应是计算机可理解的。共享反映了本体表述的知识是共性和开放的知识。”2.1.2 本体的主要构成通常意义上，本体包括概念的定义、概念之间的关系、公理和实例，它们共同限制着术语在特定领域中的解释和应用。1. 本体中的概念是广义上的概念，除了可以是一般意义上的概念外，也可以是任务、功能、行为、策略、推理过程等。本体中的这些概念构成了一个分类层次。2. 本体中的关系表示概念间的关联，其中最典型的二元关联是概念间的蕴涵关系。它使概念形成一个层次结构。3. 公理用于描述一些永真式，它是在领域中任何条件下都成立的断言。4. 实例是指概念的具体实例，本体中的所有实例构成了本体概念的特定领域的指称域。2.1.3 本体的作用构造本体的目的都是为了实现某种程度的知识共享和重用。综合参考文献12, 13认为本体的作用主要有以下三个方面：1. 本体提供了一种新的知识获取手段，规范化的描述有利于确定知识系统的需求，澄清领域知识的结构。2. 采用形式化描述的本体作为核心，能提高知识系统的重用和可靠性，为知识更新和演化打下坚实的基础。3. 采用统一的术语和概念，使不同系统间的知识共享成为可能。本体使数据的语义能用一种计算机可以理解的方式描述。文献17认为，目前本体研究正处于类似于上个世纪数据库从单机版向共享版跨越的那样一个时刻。2.1.4 知识本体语言为了让计算机能理解本体，通常采用具有推理能力的形式化描述语言来表述本体。虽然框架（Frame），概念图，描述逻辑都被用于描述本体，但在过去几年中，占统治地位的是OIL，DAML+OIL和OWL等基于描述逻辑的知识本体语言。在这三者中，本文以OWL DL描述的本体概念为研究对象。OWL（Web Ontology Language）是W3C组织推荐的本体表述语言，它建立在描述逻辑基础之上，提供多种形式语义的词汇，具有良好的机器可理解性。OWL包含三个表达能力依次递增的子语言：OWL Lite，OWL DL和OWL Full。OWL Lite是三个子语言之中最简单的一个，它以分类层次和简单约束来描述本体；OWL DL的表达能力比OWL Lite要丰富许多，它支持构建具有强大表达能力的推理系统。这个推理系统可以保证计算完备性（所有的结论都确保是可计算出的）和可判定性（所有的计算都能在有限的时间内完成）。OWL Full是OWL的三种子语言中表达能力最强的一个。它支持完全自由的RDF（Resource Description Framework）语法，适用于需要非常强的表达能力，且不太关心可判定性或计算完备性的场合。但也正是因为具有太强的表达能力，以OWL Full表述的本体不能进行自动推理。2.2 本体中的概念分析本体的四个组成部分，我们认为公理和实例的主要作用是保证概念的一致性，概念定义的内容是用已存在的概念来描述新引入的概念，即新概念与已存在概念间的关系构成了新概念的定义。所以本文分析的重点是概念的定义，它是概念语义的载体。概念定义与知识本体语言密切相关。本体中的概念由基概念、命名概念和复合概念组成。其中基概念是构建本体定义的原子概念，其语义由本体构建者主观赋予；命名概念和复合概念是用描述逻辑所规定的方法所表述的概念。2.3 语义相似性度量在现实世界中，人们处理海量信息的方法是将其分门别类的管理，并通过检索功能查到所需的信息。现有的信息检索技术仅限于关键词的简单逻辑组合，只有查询词出现在产品信息中时，才有可能被检索到18。但在实际应用中，同一个概念经常会有多种不同的表达方式，因而可能出现与用户查询含义的用词不同而无法被检索出来的情况。造成这一问题的原因是现有技术检索的是信息的相同性而不是相似性。相同性是刚性的，只有相同和不相同两种结果；而相似性是人对信息所产生的一种心理认识。相似与不相似是一种比较的结果，它是模糊且没有绝对的界线。因此在产品信息检索中，将相似性而不是相同性作为匹配的条件是更符合设计者需求的选择。考察人进行信息检索的行为，可以发现设计者查找产品信息的过程是一个不断修正的过程，每得到一个查询结果时，会根据结果中的内容对查询条件进行修正，然后进行新的查询以求找到满足需求的产品信息。如果按照用户的个性化需求，把系统中的相似产品信息组织起来，则可以大大节省设计者寻找产品信息的时间。由于编码规则仅包含了有限且刚性的形状特征集和特征放置信息，不能满足用户这种模糊的、个性化的分类服务。数据只是无意义的符号，信息是结构化的数据，而知识是则是信息背后的内容。我们用基于OWL DL的领域本体描述特征的知识模型，借鉴语义网的语义标记（Semantic Annotation）方法111, 112，用基于知识模型的OWL个体（Individual）解释系统中的信息。以知识模型中的本体概念和OWL个体为计算对象，系统能计算个性化的产品信息相似性，并以此作为查询和聚集信息的标准。它运用知识表达技术，能将设计的功能、行为和原理表现为知识，并在此基础上完成搜索、分类和推理等其他任务。系统中知识的俘获是通过分析系统的信息，归纳出隐藏在信息背后的知识；知识的存储是用OWL DL概念描述这些知识，并将其以XML文件的方式存储；知识的重用是将知识服务于系统，它是系统智能性的重要表现。需要特别指明的是，在我们完成的项目中，俘获的是图片的信息，归纳出隐藏在图片背后的信息。第3章 系统设计3.1 设计思路3.1.1 系统目标根据语义的图像检索系统顾名思义，要求系统能够根据用户输入的语义信息搜索出相关语义的图像，并反馈给最终用户。从大体上看，我们小组成员需要解决的主要是两大块：核心算法和界面设计。另外，如何做到让底层算法与上层界面顺畅的交互以及对算法计算获和的结果的处理也是我们有待我们小组成员好好钻研的。3.1.2 核心算法设计根据对系统的整体设计考虑，核心算法方面我们可以看到基于语义的检索系统需要解决的几个主要问题：1某一领域本体的建立对于某一个方面的领域本体，如果希望能够得到一个比较合理的本体，应首先是由相关的领域专家给出抽象的本体结构定义，再由计算机专业人士通过相关的技术手段转换成为计算机能够理解的数据形式。在本系统的设计中我们采用w3c最新的推荐标准描述语言OWL，至于OWL描述语言的生成工具现在常用的有斯坦福大学的Protg或者是Jena等，其中Protg拥有一个图形化的使用界面，并可以将本体的定义以OWL格式输出。因此我们的系统中所用到的Pizza.owl就是参考Protg而生成的。2资源数据的标注我们需要检索的传统数据原本不是具有基本的语义信息的，这就需要我们对这些原始数据根据我们的需要进行一定的改造。由于本系统还处在探讨阶段，因此我们采用手工标注的方法对文件图片进行标注。3设计实现语义分析推理的推理检索引擎这一功能的实现应当是实现语义检索功能的关键部分。其功能就是根据所建立的关系模型，对用户提交的搜索词汇的语义进行分析，借助于某种推理规则进行语义扩展，比如近似/同义词的推理分析，或者层次/继承的推理分析，以及词汇语义在分类结构上的扩展，并根据此扩展从数据标注数据库ontology.dat中检索相应的数据并返回给用户界面部分。3.2 对界面的构思在界面上允许为所有图片添加标记(标记内容为描述图片中语义内容的关键字)，删除标记，以及根据语义单词来实现对图片资源的检索。界面要求整体给人感觉美观大方，对应各种功能需求，要求都要有其功能按钮。要能够在窗口的固定区域预览一个目录下的所有图片。预览的图片要求缩放显示成固定的大小，并整齐的排列在预览的区域内。要求实现类似windows Explorer浏览文件的模式，显示当前目录下的所有子目录，可以双击目录跳转到新的目录去，也可以点击“向上”按钮跳转回父目录。同时显示在一个文本框显示当前目录，此文本框允许用户在文本框里输入特定的目录之后按enter就能实现跳转。对于不喜欢手动输入路径的用户，应该提供按钮一个选择目录的对话框，以便用户方便地选择目标目录。3.3 结果处理模块设计底层搜索模块计算结果完毕并返回后，将调用结果处理模块。此时，此模块需要利用算法得到的搜索结果将相关的图像寻找出来，并在界面上正确的显示。设计此模块需要考虑的有以下几点： 可能存在的若干种底层算法返回的结果，例如：多个关键字，或者无返回等等；用什么样的存储结构暂时存储返回结果； 利用什么方法在存有图像标记的XML文件中寻找与返回结果匹配的图像文件路径。3.4 系统结构设计系统主要分为以下四大部分：1.用户界面：系统提供给用户一个友好易用的用户界面，可以设计为简单的使用关键字方式进行检索输入。2.查询处理器部分：作为系统的核心部分，查询处理器接受用户界面的查询信息，进行查询并返回查询结果。3.本体库及管理子系统：负责将此领域专家设计的本体模型转化为计算机的内部存储结构，并提供相应的接口方便本体库的存储管理。4.资源数据库及管理子系统：负责将原始数据按照本体模型进行语义化标注，并以某种格式进行存储，同本体库管理一样也提供相应的接口方便资源的添加管理。3.5 本章小节 本章主要介绍了本小组成员在系统开发初期对“根据语义的图像检索系统”做的一个整体上的构思和在今后几个月内需要着手解决和完成的若干任务。具体的实现方法和细节设计将在接下来的章节做详细说明。第4章 算法的实现4.1 语义相似性度量在系统中的应用4.1.1 OWL个体的相似性及排序算法OWL个体的相似性是实现下图相似性匹配的关键，以下分别列出几个OWL相似性计算方法：算法ConsineSimilarity算法思想：把欲比较的两个字符串Str1, Str2转化为相对应的两个Map型的就是pc1, pc2。再分别对pc1，pc2进行比较，若pc1包含两者共同的键，则把它的值保存在相应的一个相对应下标Double数组weightPC1i，否则此Double数组的元素weightPC1i为。同样，pc2对应的Double数组为weightPC2i，它的计算方法与pc1相同。最后再对这两个Double数组进行计算。若(weightedPC1.length=0) & (weightedPC2.length=0)，则Str1与Str2的相似度为，否则若(weightedPC1.length=0) | (weightedPC2.length=0)，则Str1与Str2的相似度为。否则，它们的相似度为MathUtils.vectorDotProduct(weightedPC1,weightedPC2)/(MathUtils.vectorNorm(weightedPC1) * MathUtils.vectorNorm(weightedPC2) )，其中MathUtils.vectorDotProduct()表示两个数组对应下标的积的和，(MathUtils.vectorNorm()表示数组中每个元素的平方和的根。算法Jaccard similarity 23算法思想：Jaccard similarity在许多领域都有着广泛的应用，如：numerical taxonomy 和 GT等。Jaccard similarity系数在i, j两个数据中的定义如下，并且它的取值范围是0,1之间。 a表示：the number of orders that need items i and jb表示：the number of orders that need item i onlyc表示：the number of orders that need item j onlyd表示：the number of orders that need neither i nor j.算法JensenShannonMeasure算法思想：利用JensenShannonMeasure进行两个字符串的相似度比较的时候，首先对这两个String进行PrimitiveConceptTokenizer格式重构，使得这两个String都各自生成相对应的Map变量pc1, pc2。合并这两个Map的键集合union(pc1.keySet(),pc2.keySet() - size然后对pc1的每个键值进行比较，若pc1含有相对应的位置i的size元素的话，则把pc1相对应的数值保存在r1i中，否则r1i的值为0。同理，pc2的操作同pc1一样，最后数据保存在int r2中。对r1，r2的各个元素进行如下操作：若r1i!=0 & r2i!=0，则对tmp = h(v1i+v2i) - h(v1i) - h(v2i);，其中h()的意义是：-x*Math.log(x)。然后对这些数据tmp值进行累加保存到temp中，最后-0.5 * temp /Math.log(2)即为我们所求的相似。具体数学描述如下图： 算法JiangConrath 24算法描述：若计算Double元素的相似度的时：则计算的表达式如下：p_z = numCommons / N;p_x = numElemX / N;p_y = numElemY / N;similarity = new Double(-2d * Math.log(p_z) -(Math.log(p_x) + Math.log(p_y);numCommons表示：number of common/shared elements between two elements x and ynumElemX表示：number of occurrence of element xnumElemY表示：number of occurrence of element yN表示：total number of elements in reference set/structure/tree/graph若计算的是本体模型树的两个结点的相似度时：则其计算表达式为：double size = graphAccessor.size();int nX = graphAccessor.getSuccessors(x, false).size() + 1;p_x = nX / new Double(size);int nY = graphAccessor.getSuccessors(y, false).size() + 1;p_y = nY / new Double (size);IGraphNode mrca = graphAccessor.getMostRecentCommonAncestor(x,y);int nXY =graphAccessor.getSuccessors(mrca,false).size() + 1;p_z = nXY / new Double (size);similarity = new Double (-2d * Math.log (p_z)-(Math.log (p_x) + Math.log (p_y);graphAccess表示：tree accessor to access the corresponding treex表示：first tree nodey表示：second tree nodegetSuccessors()的功能：Returns the set of graph nodes that have an incoming (directed) edge from node. In a tree, the successors of a node are its children.getMostRecentCommonAncestor()的功能是：Returns the node in the graph which (1) connects nodeA and nodeB (i.e., from which there exists a directed path to nodeA and nodeB) and (2) whose sum of path lengths to nodeA and nodeB is minimal. 算法Resembalance算法描述：Resembalance算法的主要功能是计算两个集合Sets1,s2的相似程度，主要思想是：首先对这两个集合s1,s2进行取交集操作，并计算交集里的元素的个数n1。其次再对这两个集合s1,s2进行取并集操作，并计算并集里的元素的个数n2。最后n1/n2即为所求的相似度，算法具体实现如下：double score(Set s1, Set s2) double intersection = SetUersection(s1, s2).size();double union = SetUtils.union(s1, s2).size();return intersection / union;,其中SetUersection()的功能是对集合s1,s2进行交集运算；SetUtils.union()的功能是对集合s1,s2进行并集运算。算法ConceptSimilarity 19算法描述：若ConceptSimilarity的计算参数为三个double类型的参数时，其相似度为：(2d * N3) / (N1 + N2 + 2d * N3)。其中N1表示：length of path from node1 to the most recent common ancestor of node1 and node2；N2表示：length of path from node2 to the most recent common ancestor of node1 and node2；N3表示：length of path from the most recent common ancestor of node1 and node2 to the root of the tree。若ConceptSimilarity的参数为：( IGraphAccessor accessor, IGraphNode nodeN1,IGraphNode nodeN2 )，则其相似度的计算方法步骤为： getMostRecentCommonAncestor(nodeN1, nodeN2)，即get the node in the graph which (1) connects nodeA and nodeB (i.e., from which there exists a directed path to nodeA and nodeB) and (2) whose sum of path lengths to nodeA and nodeB is minimal。 getRoot()，即get the first node found in the graph having no predecessors (root) but only successors。 N3 getShortestPath(mrca, root),即get the length of the shortest path connecting mrca and root。 N1N2 getShortestPath(nodeN1, nodeN2)，即get the length of the shortest path connecting nodeN1 and nodeN2。 若N30则 similarity = new Double(1d / (N1N2 + 1d)，否则similarity = new Double(2d * N3) / (N1N2 + 2d * N3)。小结许多算法都是在OWL中计算本体相似度有着广泛的应用。由于本文主要应用ConceptSimilarity，所以在本文中，只列出了其中的几个算法进行分析并进行比较。从上面的算法描述中，我们可以看出，ConceptSimilarity在计算本体相似度中实现是比较简单的，但是它又能在更大程度上满足我们在实际操作中的相似度计算的要求，使得我们在系统的开发中能够以比较令人满意的结果检索出我们所希望得到的文件（即图片）。4.1.2 Vector排序算法算法直接插入排序算法描述：直接插入排序是一种简单的排序方法，具体做法是：在插入第i个记录时，R1,R2，Ri-1已经排好序，这时将关键字ki（即SimilarityOntoloyg.getSimilarity()）依次与关键字ki-1,ki-2,k1进行比较，从而找到应该插入的位置，然后将ki插入，插入位置及其后的记录依次向后移动。算法冒泡排序算法描述：n个记录进行冒泡排序的方法是：首先将第一个记录的关键字k1（即SimilarityOntoloyg.getSimilarity()）和第二个记录的关键字k2进行比较，若k1k2则交换两个记录的值（即SimilarityOntoloygobj），然后比较第二个记录和第三个记录的关键字，依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟排序，其结果是关键字最小的记录被安置到第n个位置上，然后进行第二趟排序冒泡排序，对前n-1个进行同样的操作，其结果是关键字次小的记录被安置到第n-1个位置上，当进行完第n-1趟时，所有记录有序排列。算法希尔排序算法描述：希尔排序又称“缩小增量排序”，是对直接插入排序方法的改进。它的基本思想：先将整个待排记录序列分割成若干序列，然后分别进行插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接排序。具体做法是：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，将所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2d1，重复上述分组和排序工作，依此类推，直至所取的增量di=1(didi-1d2d1),即所有记录放在同一组进行直接插入排序为止。算法快速排序算法描述：快速排序的基本思想：通过一趟排序将待排的记录分割为独立的两部分，其中一部分记录的关键字均比另一部门记录的关键字大，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。一趟快速排序的具体做法是：附设两个指针low和high，它们的分别指向文件的第一个记录和最后一个记录。设枢轴记录（第一个记录）的关键字为pivotkey，则首先从high所指位置起向前搜索，找到第一个关键字大于pivotkey的记录并与枢轴记录互相交换，然后从low所指的位置起向后搜索，找到第一个关键字小于pivotkey的记录并与枢轴记录互相交换，重复这两步直至low=high为止。小结若待排序的记录数目n较小时，可采用插入排序和选择排序。由于直接插入排序和选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息较大时，用直接选择排序方法较好。若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序。若n较大时，则应采用时间复杂度为O(nlogn)的排序方法快速排序，它是目前排序方法中被认为是最好的方法，当待排序的关键字为随机分布时，快速排序的平均运行时间最短。因为本系统中待排序的记录的关键字数目较多，且分布比较随机，所以在ImageSearch系统中，我们采用快速排序算法来对Vector进行排序。 知识服务在查询与浏览中的应用4.2 知识服务在查询浏览中的应用以前面章节提到的OWL个体相似性算法为基础，我们在ImageSearch系统中实现了近似查询功能，着力解决关键字查询所不能实现的近似查询问题。在传统的查询机制中，主要采用如图4-1的描述方法，图4-1 传统查询方式但是这种方法的查询方式比较单一，且不能查询同义词或相似概念的文件，因此我们提出了如图4-2的解决方案。 图4-2 基于OWL个体的查询方式4.2.1 基于OWL个体的查询方式基于本体的信息检索的常用方法是以概念作为信息的索引项，或用本体中近似的概念来松弛查询条件，或用概念的结构近似性来查询信息。这些方法都能有效地解决多义词的问题，并且扩大搜索的范围。但是索引项并不能完整表现文档的内容和结构，从而造成查询结果的不精确性。与传统的方法不同，我们用OWL个体描述用户的查询需求，将信息查询转换为OWL个体间相似性的匹配（如图4-3所示）。4.2.2 相似查询与浏览 图4-3 产品信息相似查询框图图4-3所示是ImageSearch系统中的产品信息相似查询的框图。查询接口是用于输入查询条件的界面。查询预处理模块将这查询转化为OWL个体。概念词表记录了每个概念所对应的单词，查询预处理模块根据概念词表，将查询条件中的单词转换为OWL个体中的本体概念。概念相似表记录了已计算出的概念间相似度。相似度计算模块用xmu.software.simpack.file包中的WriteInfo.java文件中描述的算法计算在信息语义标记库中所有标志之间两两之间的相似度，并保存在数据库ontology.dat中。根据查询条件，查询数据库，结果转换模块根据OWL个体与产品信息的一一对应关系将结果转化为产品信息，并输出给用户。 图4-4 产品信息相似浏览框图图4-4所示是ImageSearch系统中产品信息相似浏览的框图。相似浏览接口接受其他模块提交的信息，并将其转换成OWL个体，再查询数据库ontology.dat中的相关信息，并输出给用户。 第5章 界面设计5.1 详细介绍界面类已经成为程序的核心，因为所有的模块和功能的调用都是在这里进行的。界面由javax.swing包下的各种组件构成，其中包括：界面窗口继承自JFrame,所有组件都属于此窗口并在窗口中显示；窗口菜单包括File,Edit,和Help下拉菜单；File下拉菜单中只有一个openDirectory菜单项；Edit下拉菜单中有addFlag和removeFlag菜单项；Help下拉菜单中有HelpTopic和About菜单项；对应于每个菜单项都有一个功能函数