基于矩形代数和公共模式方法的相似图像检索
2012-11-26刘大有王生生
刘大有,董 婥,王生生
吉林大学计算机科学与技术学院,长春130012
基于空间关系的CBIR算法[1](content-based image retrieval,CBIR),主要依据图像中对象之间的空间关系进行相似性检索.近十多年来,一些基于空间关系的CBIR算法陆续被提出.Gudivada等[2]提出的SIMR算法及 El-Kwae等[3]扩展SIMR得到的SIMDTC算法,将对象抽象成几何中心点,利用两点之间的角度描述对象间的空间关系,忽略了对象自身大小.WANG[4-5]等提出基于2D BE-string排序的最大公共子序列(longest common subsequence,LCS)算法.基于LCS的算法考虑物体在两个维度的排列顺序,无法精确描述区域间的空间拓扑关系.Hsieh等[6]提出公共模式方法(common pattern method,CPM),随后又提出将图像中所有对象及对象间方位关系表示为空间关系图(spatial relationship graph,SRG),用两个SRG的公共顶点和公共边的总数度量相似性[7].这两个方法同样将对象抽象成几何中心点,仅利用两点之间的方位排序进行检索,不仅导致检索出了不相关的图像,且耗时,无法满足互联网上快速响应的需求.Chiang等[8]提出将对象抽象成最小边界矩形(minimum bounding rectangle,MBR),将MBR一维上的空间关系映射为ING(interval neighbor group)的一个顶点,对象间距即为两个维度上ING顶点的最短路径之和,对象间距离越远说明相似性越低.Wang等[9]在MBR表示物体的基础上,考虑对象间z轴方向的距离,得到复合的方位关系并计算方位距离.以上两种方法需计算所有对象间距,当图像中对象规模为n时,需进行n×(n-1)/2次计算.这些方法中.CPM是一个平均比较时间最短,且具兼容性的方法,尤其是在对象较多或符号重复率较高的情况下,仍满足多项式时间复杂性[6],是目前较……