【doc】分布式计算环境下CBIR检索引擎的实现

【doc】分布式计算环境下CBIR检索引擎的实现 分布式计算环境下CBIR检索引擎的实现 2007年10月 第44卷第5期 四川大学(自然科学版) JournalofSichuanUniversity(NaturalScienceEdition) oct.2007 VlO1.44No.5 文章编号:0490—6756(2007)05—0995—05 分布式计算环境下CBIR检索引擎的实现 文宇峰,周激流2,周扬 (1.Ixt)iI大学公共管理学院,成都610064;2.~t)ll大学计算机学院,成都610064) 摘要:本文探讨了一种基于分布式并行计算环境下视觉CBIR检索(基于内容的图像检索) 引擎的实现.该引擎采用分布式数据库来保存庞大的多媒体数据库,利用Agent技术,采用分 布式图像处理单元来进行多媒体数据的特征提取和索引建立.利用并行处理单元在分布式数 据库上进行检索匹配.讨论了在动态负载平衡下如何进行处理单元(PE)和代理以及分布式数 据库的交互. 关键词:基于内容的图像检索;Agent;分布式数据库 中图分类号:TP311文献标识码:A ImplementationofCBIRengineonthedistributedenvironment WENYu-feng,ZHOUJi—liu,ZHOUYang (1.SchoolofPublicAdministration,SichuanUniversity,Chengdu610064,China; 2.CollegeofComputerScience,SichuanUniversity,Chengdu610064,China) Abstract~AdistributedimplementationofvisualCBIR(Content— BasedImageRetrieva1)enginehasbeenput forwardinthispaper.Basedonagentanddistributeddatabase,theengineusedistributedimag eprocessingu— nitstoextractfeaturesfrommultimediadataandindexesthem.Theparallelunitsintheengine areworking withthedistributeddatabasesduringthematchprocedurewhenretrieveisgoingon.Italsodis cussesthein— teractionamongprocessingunit,agentsanddistributeddatabaseunderthedynamicoverhea dbalancemanage— ment. Keywords:CBIR,agent,distributeddatabase 1引言 基于内容的图像检索CBIR(Content—Based ImageRetrieva1)是检索领域近十年来的一个重要 研究课 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 .对图片和视频,语音等多媒体数据而言, 基于内容的检索摆脱了传统的基于文本的检索模 式,为用户提供了一种基于自动内容理解的强大查 询接VI_lJ,使得图形图像检索对用户而言变得更 加智能化和有效化,同时也促进了对图片,视频数 据自动索引技术的快速发展.基于内容的图像检索 发展到今天也面临着一些亟需解决的难题.例如, 在利用图片的低层特征(如颜色,纹理,形状,空间 布局等)进行检索的时候,往往难以把握人对图形 图像相似性上的感受,同时用户也难以清楚的 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达 其所需要的信息_2J,因而很难将图像低层特征同 图像的语义联系起来实现检索.为解决这个问题, 提出了许多相关反馈技术_3.4J. 另外一个难题是如何处理多媒体数据检索中 涉及到的图片,视频等大量数据.一方面,在建立检 索数据库时,需要对图像数据进行低层特征提取, 这常常涉及大量数据的解压,统计,变换,并根据不 同检索策略来建立索引.另一方面,在响应用户检 收稿日期:2006—11-14 作者简介:文字峰(1978一),男,2005级硕士研究生,主要研究方向为计算机视觉检 索.E-mail:kentkingcn@gmail.com 通讯作者:周激流.E—mail:zhoujiliu@8CU.edu.cn 996四川大学(自然科学版)第44卷 索请求的时候,又需要在短时间内查找数据库,选 取恰当的数据索引,进行匹配检索.特别是在利用 草图或者形状进行检索的系统中,还常常涉及到对 草图或者样图进行识别;同时,检索系统还面临着 大量用户并发访问的问题,所有这些都需要检索系 统具有计算能力强大,反应迅速以及存储量巨大的 数据库. 为了克服这个难题,考虑引入一个分布式计算 环境,利用计算机集群的强大运算和负载能力来提 高CBIR系统的并行处理能力,反应能力和检索能 力;采用智能干预的方法,动态分配计算负载,使系 统可以以弹性的方式动态地引入新的检索方法和 模式识别技术l5].采用分布式数据库来提高系统 的数据安全性,减轻检索引擎负载,从而在整体上 提高图像CBIR系统的实用性. 2分布式系统和智能移动代理 分布式系统是指运行在一系列自治处理单元 PE(ProcessingUnit)上的系统,在这个系统中每个 处理单元有各自的物理存储器空间并且消息的传 输延迟不能忽略不计l6].传统的分布式检索系统 通常采用固定的计算单元(分布式硬件),采用分布 式控制来分配处理单元,并行处理分布式数据. 在传统的分布式系统发展的基础上,智能移动 代理IMA(IntelligentMobileAgent)近年来成为了 分布式计算和数据库访问技术研究中的热点.智能 移动代理是一种可以携带自身代码在网络环境中 移动的程序,在不同的数据服务器上执行检索以 后,可以携带检索结果移动到其它服务器,最后将 检索结果返回给用户.与传统分布式系统的运算节 点相比,可移动的智能代理具有更多的主动性,协 作性和智能性,从而具备更强的问题求解和自治能 力[71. 使用移动代理的检索系统常常由以下一些组 件构成:?检索代理SA(SearchAgent),用于实现 搜索算法,可以在服务器之间移动.?用户接口代 理UIA(UserInterfaceAgent),同用户进行交互, 提供不同的检索方式.?协调代理CA(Correspond— ingAgent),对sA的检索和移动进行协调.?其它 组件,提供诸如添加数据,安全处理以及检索辅助 的功能.其中,SA是最重要的,它在其它代理的辅 助下,智能化的移动并执行检索处理. 在实际系统中,智能移动代理的实现也存在一 些难题,包括:?目前没有关于分布式系统中移动 代理的框架或者规范,实现移动代理的系统往往涉 及到多个不同代理之间的异步传输和协调,编程相 对复杂.?移动代理无论是采用解释性语言编写, 或者采用对象序列化的方法,移动的可执行程序都 会带来安全隐患和移植性的难题.?移动代理采用 的是异步机制,难以保证检索结果的实时性,同目 前广泛使用的其它检索系统相比,这种方法用户难 以接受.?智能代理携带检索结果在网络中移动, 仍然存在通信传输的大数据量问题. 3基于智能干预的分布式CBIR检 索糸统 鉴于移动代理存在的一些问题,我们考虑使用 一 种在传统分布式系统中引入代理形式的智能干 预的CBIR检索系统.在保留移动代理一些优点的 同时,让图像的处理和检索使用固定的处理节点集 群来克服系统复杂性,提高性能(如图1). 各种应用分布式CBIR~擎 Web方式代理 检索服务^_』I像检索代理J开数分 C/S方式 放I像处理代理J据布 式库^_式 检索服务终了1亡=代数 端PE集群理据 各种DBI射片检索节点^_库 HC onnector 图片处理节点 图1系统结构框图 Fig.1Systemarchitecture 分布式检索引擎部署在一系列的物理节点上. 假如我们不考虑这些物理节点的拓扑分布,而从分 布式系统的基本运算单元(即自治处理单元(PE)) 来进行考虑,分布式CBIR引擎可以由以下一些类 型的节点构成: (1)开放式终端:开放式的终端同前端应用进 行集成,为应用程序和web服务器提供统一的接 口(例如COM组件或者JavaBean)以访问检索引 擎,各种应用可以透明的接入检索引擎.DBCon— nector则是同其它检索数据库交互的工具,通过编 写不同的Connector可以将不同数据库中的图像 数据通过统一接口导入CBIR引擎. (2)代理节点(本文第4节):分为图像检索代 第5期文宇峰等:分布式计算环境下CBIR检索引擎的实现997 理和图像处理代理,分别实现图像的检索以及图像 加入系统时的变换处理.开放式终端根据检索和处 理的不同需要分别调用两种代理,但代理节点本身 并不参与检索和图像处理,而是协调处理终端节点 和实际处理节点的关系,以调整系统负载. (3)PE节点:这是实际进行图像佃形处理的 处理节点.与代理一样,PE节点分为检索和图像处 理两种.检索引擎的主要计算处理工作都是由PE 节点来完成的,并且不同的检索策略和图像处理策 略由不同的PE节点完成,而所有的PE节点在一 起构成了一个PE集群.智能代理根据终端的不同 需要分别调用集群中不同的PE节点. 我们根据不同的算法策略来区别不同的PE 节点,如果两个PE节点使用相同的算法策略,我 们可以认为它们是相同的PE节点.相同的PE节 点可以部署在集群内不同的计算机(物理节点)上, 而一台计算机(物理节点)上也可以部署多个不同 的PE节点进行并行计算.PE节点通过物理节点 的存根程序(Stub)同代理进行通讯,并由代理为 PE节点分配任务(如图2). 图2检索代理与PE节点的关系 Fig.2RelationshipbetweenagentandPE (4)数据库代理:检索系统采用分布式数据库 将图像特征索引保存在并行计算机上.为了让PE 节点可以透明地访问数据库资源,并且兼容系统内 的多种数据库,PE节点的数据库访问都应该通过 数据库代理来进行,由代理节点指定PE对数据库 的访问. (5)数据库节点:用于存储分布式数据库,包 括异构的多种数据源. 4交互式智能代理与PE集群 检索引擎的智能代理主要有两个功能:?为终 端选择恰当的检索策略和图像处理策略.?根据 系统状况动态调整系统负载. 以检索为例(如图3),执行检索的时候,检索 代理会先启动一系列的检索PE节点,就如同建立 了一个计算节点池(Poo1).终端首先访问检索代 理,代理接到检索请求以后,先根据检索类型选择 出所有适合的PE节点,然后再根据选出节点的负 载情况挑选出一个最不忙的节点返回给检索终端, 然后由检索终端和检索节点直接连接,最后代理对 该检索节点进行登记,增加它的负载 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 .例如,我 们定义客户端从Agent取得检索PE节点的COM 接口如下. HRESULTGetSearchPE([in]VARIANTin— fo,[out]BSTR*host,[outJlongpeid); 图3终端与检索代理以及PE节点的交互 Fig.3Interactionamongterminal,agentandPE inf0标识了客户端的请求类型,Agent根据请 求类型返回PE节点所在主机物理地址(host),以 及PE节点的ID(peid).因此,系统部署时只有智 能代理知道在哪些物理节点上部署了哪些PE节 点. 一 个物理节点上通常都部署有多个PE节点, 而PE节点通过所在物理节点的存根程序同代理 以及终端进行通讯,PE的部署位置也就与物理节 点无关.这样的好处就是:?智能代理知道到哪些 机器上去调用特定的PE节点;?存根程序知道在 本机上部署了哪些PE节点,以及调用方法;?部 署PE节点的时候,可以将它部署到任意的物理节 点上,这方便了PE节点在部署上的移动性,并且 随时可以添加新的PE节点(新算法). 对于PE节点而言,它实际上是一种图像分析 别算法的实现.我们可以从两种层次上将算法 抽象出来,一种是面向图像高层语义特征的算法, 它的实现节点可以称为上层节点,例如我们可以建 立一种专门检索人脸的处理节点.另外一种是进行 图像低层特征处理的算法,可以称为基本处理节 点,例如专门进行彩色直方图检索的处理节点.很 998四川大学(自然科学版)第44卷 显然,后一种处理节点是构成前一种节点的基础, 也可以说,上层节点的功能由一种或几种基本处理 节点组合在一起完成(如图4).而对于用户来说, ,我们可以定义 两种节点的接口都是一样的,例如 图片检索的PE的接口如下. HRESULTGetRetrievalResult([in]longpeid, [in]VARIANTcond,[out]VARIANT*result); peid是PE节点的ID号,cond是检索结果需 要满足的条件,而result则是检索的结果集合.很 显然,对于图4中人脸检索的结果就是其三种组成 节点检索结果的一个交集. 图4高层检索节点同低层特征检索节点的关系 Fig.4Relationshipbetweenhighersearchnodeandlow— ersearchnode 在上层节点和基本处理节点采用相同接口的 情况下,上层节点执行时可以通过代理来调用基本 处理节点,在综合了下层节点的检索结果后,再返 回给终端最后的处理结果.这样做的好处就是同一 种基本处理节点可以透明地配属给不同的上层节 点使用,上层节点也无需知道它使用的基本处理节 点存放在网络上的哪一台机器上,因而大大增强了 PE节点的自治性(Autonomous)和灵活性,减少了 系统耦合. 在采用了这种PE集群结构以后,我们就可以 动态的向检索引擎中添加新的处理索算法以及 模式分析方法,这就好像搭积木一样,各种图像处 理方法都可以独立实现,然后组合在一起形成新的 高层图像特征处理算法.上层的处理节点也无需知 道基本处理节点实现的细节和物理上的配属位置, 因为节点问的交互采用统一的接口,通过智能代理 来实现调用. 5数据库代理与分布式数据库 应用系统中采用分布式数据库的原因主要是 为了提高系统性能_6J.相对于传统的集中式数据 库,分布式数据库对于前端应用来说,更加透明,可 靠,性能更高且更易于扩展.但这常常是以系统设 计的复杂性为代价 假如采用普通的分布式数据库,将检索系统的 数据平均分配到各个数据库节点上,使用静态负载 平衡算法,其优点是数据负载可以得到平均分担, 缺点是执行一次检索任务就需要访问所有的数据 库节点.如果我们引入数据库代理,让它来管理整 个数据库的访问,那么可以有效地提高数据插入和 访问的效率,进而提高检索的反应速度. 数据库代理的作用包括: (1)数据库代理管理整个分布式数据库,它掌 握着所有数据库的分布情况,包括物理地址和数据 分布情况.因此,整个检索系统对数据库的访问都 必须经由数据库代理来进行. (2)整个分布式数据库可以看成是众多图像 特征表的整体集合.执行图像处理的PE节点将图 像特征数据加入数据库的时候,由数据库代理指定 PE节点插入到指定物理节点上的指定数据库.特 定的图像特征放入特定的特征表中,表的物理位置 对PE节点透明,但是同一个表的数据在物理上集 中存放,访问时不需要访问所有的数据库节点 (3)执行图像检索的PE节点在检索图像时 候,根据使用的算法需要到特定的数据库表上进行 检索.同样,这种访问需要由数据库代理为检索PE 节点指定数据库节点和表的网络物理地址.由于一 个表的数据集中在一个物理节点上,因而只需要查 询一台计算机.这在一定程度上提高了检索速度. 当然,也有可能因此造成数据的集中存放,使得数 据库负载不均衡.这需要数据库管理员对表的物理 分布情况进行合理调整,让经常被访问的表分布到 不同的数据库节点上. 因此,使用分布式数据库提高了检索性能,同 时,使用数据库代理又将检索逻辑与物理存储分隔 开来,提高了PE节点的独立性以及检索系统对数 据库的兼容能力. 6系统实现 目前广泛采用的分布式系统的框架和工具很 多,例如支持并行处理的消息传递框架MPI,基于 组件的分布式对象技术包括微软的D(,0M((M +),Java的RMI,以及OMG的CORBA技术.它 们都有各自的优点.为了方便起见,我们使用 DCOM来实现了自己的CBIR系统,图5是系统对 包含花的图片的检索结果. 第5期文字峰等:分布式计算环境下CBIR检索引擎的实现999 图5系统部分检索结果 Fig.5Partofsystemsearchresult 使用DCOM的优势在于实现简单,配置部署 也相对容易,并得到微软操作系统的紧密支持.使 用COM编写的开放式终端,可以很容易的为C/S, B/S模式的客户端调用;在PE节点上,Stub使用 自动化(Automation)技术来按名字创建对象和调 用方法,可以达到在Java中按名字加载实例一样 的效果. 通过与单机CBIR系统对比(如表1),我们可 以看到,在图片入库的时候(500张图片同时处理 并加入数据库),采用单机和1个节点的处理时间 相差不大,由于网络传输和Agent处理的原因,1 节点比单机的处理时间略多.但是在采用3个和5 个节点的时候,由于系统可以并行处理图片,入库 时间随节点数目的增加而迅速降低.在进行图片检 索的时候(图库中存在5000幅图片),单机系统的 检索时间同多PE节点系统的检索时间相差不大, 但是分布式多节点CBIR支持多用户并发检索,大 大提高了系统的可用性和使用效率. 表1单机CBIR系统与采用不同数目PE节点 ) CBIR系统处理结果比较(平均值 Tab.1Comparimnofprocessingresultbetweensingle andmulti.PEnodesCBIRs~tem 7结语 我们提出了一种易于实现,且扩展性良好的分 布式CBIR检索引擎架构.当今基于内容的视觉检 索技术仍在飞速发展当中,CBIR引擎不仅需要能 使用当前流行的模式识别和检索技术,还要考虑今 后其它图像/图形技术的集成;另一方面,性能问题 是任何检索系统都需要认真考虑的问题.因此,一 个具有开放性和高性能的检索引擎是我们实现的 目标,我们在这方面做了一些有益的探索. 参考文献: [1]NunoV.Content—basedimageandvideoretrieval[J].Signal Processing,2005,85:231. [2]谭晓阳,孙正兴,张福炎.交互式图像检索中的相关反馈技术 研究进展[J].南京大学:自然科学,2004,40(5):640. [3]KimDH,ChungCW,BamardK.Relevancefeedbackusing adaptiveclusteringforimagesimilarityretrieval[J].TheJournal ofSystemsandSoftware,2005,78:9. [4]LeeI,GuanL.Semi—automatedrelevancefeedbackfordistribut— edcontentbasedimageretrieval【Rj/~EEEInternationalCon? ferenceonMultimediaandExpo(ICME),TaiPel,2004:1871. [5]AroraC,NirankaxiP,GhoshH,eta1.Contentbasedimagere? trievalusingmobileagents[C]//FhirdInternationalConference onComputationalIntelligenceandMultimediaApplicationsfIC— CIMA'99).NewDell:IEEEComputerPress,1999:248. [6]wuJ.Distributedsystemdesign[M].Bei]ing:Chinamachine Press.2001. ,曾怡达,陈维荣,等.Web环境下基于移动多Agcnt [7]黄慧汇 技术的CBIR系统[J].计算机应用研究,2005(5):189.