基于内容图像检索中的索引技术

1、收稿日期:2005201201; 修返日期:2005203209基金项目:国家自然科学基金资助项目(60473117基于内容图像检索中的索引技术3贺玲, 吴玲达, 蔡益朝(国防科学技术大学信息系统与管理学院, 湖南长沙410073摘要:首先总结了基于内容图像检索中索引技术的研究现状, 指出了其中存在的问题以及今后发展趋势, 然后提出了一个新的聚类算法和降维算法, 并将两者结合起来提出了一个可用于基于内容图像检索的索引机制。关键词:基于内容图像检索; 维度灾难; 索引; 降维; 聚类中图法分类号:TP391141文献标识码:A :3695( 2I ndexing Techniques I L i

2、ng, I Yi 2chao(m &M N U niversity of D efense Technology, Changsha Hunan 410073, China Abstract:p r a survey of current indexing techniques in content 2based i m age retrieval at first, then the p r ob 2le m s t o be s and the ne w directi ons in the future in this domain are pointed out . I n t

3、he end, it p r oposes a ne w indexing scheme with the combinati on of a new clustering algorith m and a ne w idea of di m ensi onality reducti on . Key words:Content 2based I m age Retrieval; Curse of D i m ensi onality; I ndexing; D i m ensi onality Reducti on; Clustering1引言近年来, 随着多媒体技术和计算机网络的飞速发展,

4、 全世界的数字图像的数量正以惊人的速度在增长。为了使这些庞杂的图像中所包含的信息被有效的访问和利用, 必然需要一种能够快速而且准确地查找访问图像的技术, 即图像的检索技术。此外, 随着大规模数字图像库的出现, 传统的依赖于人工标注进行的基于文本的图像检索技术已经无法满足用户日益增长的要求, 基于内容的图像检索技术(Content 2Based I m ageRetrieval, CB I R 便应运而生。CB I R 的一般做法是先提取出图像的特征建立特征数据库, 这样就把图像库中的一个实例转换成了特征空间中的一个点。而图像特征一般都是高维的矢量数据, 所以对图像基于内容的相似检索就转换为对高

5、维特征矢量的最近邻检索。与此同时, 对于大规模的图像数据库而言, 其特征数据库也是大规模的。因此传统的顺序扫描方式必然满足不了用户的检索要求, 这就迫切需要有合适的索引机制来辅助、加速检索的进程。但是, 传统的多数索引机制当处理的数据维数超过5时, 其性能会急剧下降, 甚至不如顺序扫描, 这也就是通常所说的“维度灾难”。本文即以此为出发点, 总结了C B I R 中高维索引技术的研究现状、指出了其中存在的问题及今后的发展趋势, 提出了一个新的索引机制。2已有的索引技术对于大规模图像数据库来说, 线性扫描已经满足不了用户的需求, 因此需要利用相应的技术和数据结构来组织特征向量并管理搜索过程, 从

6、而加快查询的速度, 这就是索引应对实现的基本功能。多媒体数据库的索引机制与一般索引结构的一个重要区别在于它面临着“维度灾难”带来的影响。围绕着这个问题, 近年来有很多研究者提出了很多的解决方法, 这些方法可以分成五类:多维索引方法、降维的方法、近似最近邻方法、多重填充曲线方法和基于过滤的方法。211多维索引方法多维索引方法(M ultidi m ensi onal I ndexing Method, M I M 通过划分数据空间, 根据划分对数据进行聚类并利用划分对搜索空间进行剪枝以提高查询效率。这类方法在处理低维数据时效果很好, 但在高维时其性能甚至差于顺序扫描。最为成功的M I M 方法是

7、基于树结构的索引方法。这些方法用某种策略把数据集里的数据点分成不同的簇, 然后用某种覆盖对象(Boun 2ding Object 来近似表示每个簇, 所有的覆盖对象通过树结构的方式进行组织。在检索的时候这些覆盖对象能够提供簇内数据点到查询向量距离的下界(就是用覆盖对象到查询向量的最小距离作为簇内数据点到查询向量距离的下界, 因此覆盖对象是簇的“近似”表示 , 并利用这些距离下界对树结构(也就是数据空间 进行剪枝, 使得用户在不访问所有簇的情况下就能得到相似度检索的结果。多维索引方法又可以分成两大类:一类是由K 2D 2树演化而来的; 另一类则是由R 2树演化而来。它们的关键区别在于对数据空间的

8、划分方法不同。前者使用空间划分方法, 沿着预先定义的超平面来划分数据空间, 而不考虑数据的分布。这样得到的区域是相互分离的, 它们的合集则是整个空间。后者使用数据划分方法、根据数据的分布对数据空间进行划分。这样的划分会产生一定的重叠。除了这两类方法以外, 还有一些技术结合了多种方法以提高相应的性能。R 2树1以及其为基础的各种层次结构是现在最常用的对912第11期贺玲等:基于内容图像检索中的索引技术空间数据进行索引的数据结构, 也是对高维数据索引的较早尝试。1984年Gutt m an 首次提出R 2树的概念。它是B +树在空间上的扩展, 其数据以空间中的最小包围矩形(M ini m al B

9、oun 2ding Rectangle, MBR 来表示。有实验数据表明, 当数据维数超过5时, R 2树的性能急剧下降。SS 2树2是一个类似R 2树的索引结构, 但它使用的是最小包围球(MBSs , 而不是最小包围矩形; SR 2树3则是对SS 2树的扩展, 并结合了SS 2树和R 32树方法的概念。它共同使用MBSs 和MBR s 作为近似区域。该结构的性能超过了R 32树和SS 2树。X 2树4是R 32树对高维数据的扩展, 它通过记录树的划分历史来进行无重叠的划分。其性能超过了R 32树和T V 2树5。Hybrid 2树6则结合了空间划分和数据划分各自的优点,并使用一个单独的维来划

10、分节点, SR 2树B 树。而A 2树7。Bercht old 策略8。d 2d 个金字塔, 这些金字塔共同的顶点位于数据空间的中心点, 然后每一个金字塔都被分成与底边平行的一些面片, 从而形成数据页面。金字塔技术为每一个高维点关联一个值, 这个值被作为B +2树中的一个键值。对于均匀分布的数据, 金字塔技术超过了X 2树和顺序扫描。但该索引结构对于近似最近邻搜索效果并不好, 它只适用于范围查询。总之, 对于上述众多的多维索引方法, 其性能优劣没有一个固定的先后排序。在不同的应用中, 根据不同的评判原则, 其性能之间的比较会产生不同的结果。212近似最近邻方法对于图像检索而言, 由于图像特征本

11、身就是图像的近似表示, 特征向量意义上的最近邻并不是图像语义意义上的最近邻, 所以即使精确最近邻检索的方式也并不保证给出图像检索的精确结果。因此研究者也提出了很多基于近似最近邻的索引方法来试图解决维度灾难的问题9。这里的“近似”是在对图像的特征向量进行最近邻搜索的意义上的, 即在特征向量的最近邻检索结果中引入一定的错误率, 然后进行近似的, 而不是精确的最近邻检索。其主要思想是通过某种“近似”的方式放松对最近邻条件的要求, 如用近似距离代替精确距离, 放松最近邻距离的限制以及减少访问的向量等。213降维降维的方法是解决维度灾难的一个最直接的途径10, 其主要思想是利用降维后的向量计算出来的近似

12、距离代替精确距离。它的基本过程是先利用单值分解、离散小波变换、离散余弦变换等方法对数据集进行降维处理, 然后利用传统的多维索引方法对降维后的数据建立索引。i M in M ax (11则利用了降维的思想来建立索引。它通过高维点的最大或最小坐标值把它们映射成一个一维的值。通过改变的值, 该方法能被优化以适应于不同分布的数据集, 与其他的降维方法一样, 该机制使用B +2树对映射后的一维值进行索引。i M in M ax 主要用于范围查询, 不过也支持近似最近邻查询, 但要以较多的运行时间来换取高的准确度。对于范围查询, 该方法超过了VA 2File 和金字塔技术。214多重空间填充曲线基于多重空

13、间填充曲线的索引方法是利用多R d R 1个的映射来降低需要访问的向量数, 这种映射被称为空间填充曲线。它将R d 的数据点映射到实数轴上, 从而提供了一种将d 维数据向量进行排序的方式。在检索时, 查询向量q 也先通过空间填充曲线映射到实数轴上, 然后通过二分查找或者搜索树就可以很容易找到q 的近邻点。然而该映射的本质决定了某些在R d 上近邻的点在实数轴上会互相远离, 从而单个映射会给检索结果带来较大的错误率。, 需要。而这些都。1, 它可以通过多种途径实现。向量近似文件(Vect or App r oxi m ati on File, VA 2File 12及在其基础上发展起来的一系列变

14、体都属于这类方法, 这也是相对于近似最近邻搜索而言的唯一一种精确最近邻搜索方法。以VA 2File 为基础, 针对该索引机制还有一系列的改进版本。Manjunath 针对数据分布的不均匀性, 在各维上分别用高斯混合模型拟合数据的边缘概率分布, 然后根据模型参数对数据各维进行独立划分13; Ferhat os manoglu 14提出了用VA +2File 方法来处理非均匀分布的数据集, 该方法首先使用K LT (Karhunen 2Loeve Transf or m 变换来去除各维之间的相关性,然后根据变换后各维的能量进行不均匀的位数分配; Bercht ole 提出了三层的I Q 2树15,

15、 它结合了压缩方法和索引结构来寻求两者最好的结合点; Guang 2Ho Cha 则先后提出了GC 树16和LPC 文件(Local Polar Coordinate file, LPC 2file 17方法来改进近似向量的表示形式, 前者使用了分层结构的树来组织覆盖对象, 后者除了使用原始数据所处的区域之外, 还使用了数据在该区域的局部极坐标来生成近似向量, 以提高近似向量的过滤能力。216小结总之, 研究者已经提出了很多的方法试图解决“维度灾难”的问题, 其中一些方法取得了一定的进展, 能够获得比顺序查找更快的检索速度。但从另一个方面来讲, 目前对高维索引机制的研究还处于非常初步的阶段,

16、还存在很多的问题和需要进一步研究的地方。总结起来, 这些问题主要表现在以下几个方面:(1 大多数现有的索引机制当维数超过十维时, 性能急剧下降;(2 对高维数据进行划分时, 或者认为数据是均匀分布的, 或者对数据的分布进行一些假设, 而这些假设通常与数据的真实分布相差甚远;(3 大多数索引结构不支持数据库的动态更新, 或者更新代价昂贵;(4 大多数索引结构, 尤其是高维索引结构, 其计算复杂度很高;(5 多数索引结构只能处理维数固定的数据;(6 通常一个新的索引机制的提出只是对某一个或一类022计算机应用研究2005年原有机制的改进, 几乎没有考虑多种不同形式的有效结合;(7 大部分研究工作都

17、只从提高索引性能的角度来提高基于内容检索的效率, 而很少考虑从改善搜索算法的性能着手。3聚类与降维相结合的高维索引机制对大规模图像数据库来说, 任何一种单一的索引形式都很难产生好的索引性能, 考虑多种索引方式的结合, 是大规模图像数据库索引发展的必然趋势。聚类和降维都是索引机制中常用的方法, 以聚类作为前期的过滤处理, 再分别对每个类中的数据降维之后建立有效的索引, 将具有比单独的聚类或单独的降维效果更好。311基于网格划分的聚类算法在VA 2File , 配b i 位, b i , di =1=d, 据空间的维数2b 个超立方体形状的单元(Cell 2file 再为每个单元分配一个长度为唯一

18、位串, 并用这个位串近似表示落在该单元内部的原始特征向量。以图1为例, 将点1和点2分别记作A 和B , 并且沿着X 轴和Y 轴的区间编号分别记为0, 1, 2, 3。很显然A 点位于X 轴方向的第三个区间、Y 轴方向的第0个区间, 而B 点则在X 轴的第2、Y 轴的第三个区间, 即两个点分别可以表示成(3, 0 和(2, 3 。于是这两个点之间的距离可以由如下公式计算。D (A, B =2用通用的形式表示, 设数据为n 维, 每维分配b i 位, 那么每维被划分为2b i 个区间, 这些区间依次编号为0, 1, , 2b i -1。设点A 和B 在每一维上所处的区间编号分别为x k 和y k

19、 , 其中k 1, n ,且0x k , y k 2bi -1。于是有D (A, B =nk |x k -y k |n采用简单的k 均值聚类思想18, 并以此公式作为新的距离度量方式, 则构成了本文提出的基于网格划分的聚类算法。312降维降维也是高维索引的常用方法之一。现有的大多数降维方式, 其实现算法往往过于复杂, 有时候这种复杂度甚至远远超过算法对性能的提升。鉴于此, 本文将介绍一种实现简单的降维思路, 以期用于辅助大规模图像数据库的基于内容检索。设d 维空间中的任意一点记为X =(x 0, x 1, , x d -1 , 则其欧氏范数计算公式为X =x 20+x 21+x 2d -1。于

20、是, 可以利用该范数作为关键值, 将d 维的点用一维的索引结构B +树来进行索引。图2所示是二维空间的降维结果。由图2可见, 该降维方法实现起来非常简单方便, 同时B +树作为一种成熟高效的一维索引机制, 用其来组织降维后的范数值, 也能具备良好的索引性能。之所以采用这种降维方式, 源于以下几个因素:(1 欧氏距离是目前向量空间中采用最为广泛的一种度量方式;(2 真实的数据在数据空间中会成若干聚类状分布, 这样数据点的欧氏范数将会有一个均匀平坦的分布;(3 最近邻的结果集合会落在一个小范围的范数值中, 这样就减小了搜索过程中需要检测的数据点的数目;(4 一些应用领域需要处理大规模的可变维的数据

21、, 这就要求能有满足这种要求的合适方法, 而该方式能够适应维度的任意变化。在具体的应用中, 还可以该降维方式为基础, 对其进行相应的改进。主要的改进手段就是在范数的计算中引入相关的权值系数, 这个系数与用户所选取的图像特征的表达形式以及。这也是本文下一313小结以聚类作为数据过滤的预处理, 在此基础上再通过一个简单的降维机制对各类数据进行降维处理, 然后用B +树来组织这些降维后的特征点, 是本文索引机制的基本思想。而多种形式的索引方式的结合, 以形成新的索引结构, 则是CB I R 中的索引机制发展的一个必然趋势。4总结与展望本文总结了C B I R 中的索引技术的研究现状, 指出了其中存在

22、的主要问题以及今后发展的主要方向, 并提出了一个基于聚类和降维的新的高维索引机制。“维度灾难”一直是CB I R 中的索引机制所面临的一个关键问题, 也是促使该领域内的研究不断向前推进的一个主要动力。为了解决这个问题, 很多研究者提出了很多的方法和算法, 这些算法都在某一个特定的应用领域、从一定程度上解决了高维索引中的某些问题。由于索引机制的评价主要取决于其对应的搜索算法的性能, 而不同应用背景中的搜索形式又各不相同, 所以至今没能有一个通用的评价模型来对现有的索引机制进行优劣评判, 这也是该领域的研究者正试图解决的关键问题之一。多种形式的索引方式的结合, 以形成新的索引结构, 从而充分利用不

23、同索引形式的互补优势, 是CB I R 中索引机制发展的另一个必然趋势。除此之外, 通过前面的总结不难发现, 为提高CB I R 的性能, 绝大多数的研究都集中在如何建立一个最优的索引机制, 但很少有研究者致力于通过引入并行搜索机制来改善搜索性能。然而, 结合适当的索引机制, 同时采用并行搜索算法对搜索性能的提高, 将比单纯依靠索引机制的提高要大得多。因此这也是今后该领域的重点研究方向之一。本文下一步的工作主要包括两个方面的任务:以一个大规模图像数据库为研究对象, 实现对该数据库的(下转第224页122第11期贺玲等:基于内容图像检索中的索引技术法。最终约简后的属性为15,2, 18, 20,

24、 24, 9, 3。结果对比如表2所示。表2结果对比参加分类的属性分类效果(正确率训练准确率测试准确率约简过的属性95. 6%97. 3%未约简过的属性86. 4%90. 2%其中离散化程度是指均值法中离散化后的属性值占原属性值的百分数, 求得的核是指约简结果即核的成员, 分类效果是指用核中的元素进行分类运算的分类正确率。6总结与分析从表2可以看出合适的离散化后进行属性约简得出核, 应用核里的元素进行分类, 分类效果有所提高, 余属性, 提高了计算效率。和属性约简方法, , , 。粗糙, 怎样应用于医学影像, 是进一步研究的课题。参考文献:1胡晓翔1浅谈医学影像的本质和特点J .医学与社会,

25、1997, 10(2 :54255. 2徐光明, 徐元洪. 医学影像技术的新进展J .感光材料, 1998,(5 :43246.3蓝春生, 蓝鹏, 曹煜媛. 医学影像综合处理与外科策划J .中国体视学与图像分析, 2001, 6(3 :1712176. 4Pa wlak Z . Rough SetsJ .I nternati onal Journal of Computer and I n 2f or mati on Sciences, 1982, 11:3412356.5Pa wlak Z . Rough Sets, Theoretical A s pects of Reas oning a

26、bout DataJ .上海交通大学学报, 2002, 36(4 :4782481. 7Q iang Sh, A lexi os Ch . Amodular App r oach t o Gen 2Erating Fuzzy Rules with Reduced A ttributes f or the Monit oring of Comp lex Syste m s J .Engineering App licati on of A rtificial I ntelligence, 2000, 13(3 :2632278.8王珏, 王任, 苗夺谦, 等. 基于“数据浓缩”J .计, 199

27、8, 2129, L i of Rough Set and Sta 2J .I nt 1J. of Man 2Machine53273., 胡桂荣. 知识约简的一种启发式算法J .计算机研究与发展, 1999, 36(6 :6812684. 11陈湘晖, 朱善君, 吉吟东. 基于熵和变精度粗糙集的规则不确定性量度J .清华大学学报, 2001, 41(3 :1092113.12刘振华, 刘三阳, 王珏. 基于信息量的一种属性约简算法J .西安电子科技大学学报(自然科学版 , 2003, 30(6 :8352838.作者简介:王小凤(19792 , 女, 硕士研究生, 研究方向为数据挖掘和图形图

28、像处理等; 周明全(19542 , 男, 教授, 博士生导师, 研究方向为可视化技术、图形图像处理等; 耿国华(19552 , 女, 教授, 博士生导师, 研究方向为智能信息处理、数据库、数据挖掘等。(上接第221页 索引; 集中在寻求合适的结合点、建立多种形式相结合的索引方式, 同时使其在特定的应用中得以实现, 并通过其从实践中反应出来的性能优劣, 进行改进。参考文献:1Ant omn Guatt m an . R 2tree:A Dyna m ic I ndex Structure f or Spatial SearchingC .AC M Sig mod I nt . Conf . on

29、 Manage ment of Data . Bos 2t on, 1984147257.2David A W hite, Ra mesh Jain . Si m ilarity I ndexing with the SS 2treeC .Pr oc . of the 12th I EEE I nt . Conf . on Data Engineering . 1996. 3Nori o Katayama, Shin ichi Sat oh . SR 2tree:An I ndex Structure f or H igh D i m ensi onal Nearest Neighbor Qu

30、eriesC .Pr oc . of the I nt . Conf . on Management of Data, 1997.4Stefan Bercht old, Daniel Kei m , Hans 2Peter Kriegel . The X 2tree:AnI ndex Structure for H igh 2D i m ensi onal Data C .Pr oc . of the 22nd I nt . Conf . on Very Large Data Bases,Mumbai, 1996.5King 2I p L in, H V Jagadish, et al . T

31、he T V 2tree:An I ndex Structure f orH igh 2D i m ensi onal DataJ .VLDB , 1994, 3(10 :5172549. 6Kaushik Chakrabarti, Sharad Mehr otra . The Hybrid Tree:An I ndex Structure f or H igh 2D i m ensi onal Feature Spaces C .Pr oc . of the15th I nt . Conf . on Data Engineering, 1999. 7Yasushi Sakurai, Masa

32、t oshi Yoshika wa, Shunsuke Uemura . The A 2tree:An I ndex Structure f or H igh 2D i m ensi onal Spaces U sing Relative App r oxi m ati on C .Pr oc . of the 26th I nt . Conf . on Very Large Data 2bases (VLDB 00 , 2000.8Stefan Bercht old, Christian Bohm, Hans 2Peter Kriegel . The Pyra m idTechnique:T

33、 owards B reaking the Curse of D i m ensi onality C .Pr oc . of the I nt . Conf . on Manage ment of Data AC M Press, 1998. 9Paol o Caicca, Marco Patella . App r oxi m ate Si m ilarity Queries:A Sur 2veyR .Italy:University of Bol ogna, 2001.10M Beatty, B S Manjunath . D i m ensi onality Reducti on U

34、sing Multidi 2mensi onal Scaling f or I m age SearchC .Pr oc . of the I EEE I C I P . San 2ta Barbara, vol . , 1997.11Cui Yu, Stephane B ressan, et al . Querying H igh 2D i m ensi onalData inSingle D i m ensi onal SpaceJ .VLDB Journal, 2002.12Roger W eber, Hans 2J Schek, Stefan B l ott . A Quantitative Analysisand Perf or mance Study f or Si m ilarity 2search Methods in H igh 2D i m en 2si onal SpacesC .NewYork, US A:Pr oc . of the 24th I nt . Conf . on Very Large Data Bases (VLDB 98 , 1998. 1942205.13Peng W u, B S Manjunath . An A