基于新的空间关系特征的图像检索方法

郭倩 杨红菊 梁新彦

摘要：图像与图像之间没有清晰的空间结构，这样就不能有效利用图像间空间结构上的相关性信息，针对此问题提出一种基于新的空间关系特征的图像检索方法。首先，提取待查询图像在内的全部图像的特征向量。然后，计算特征向量每两个之间的相似性，形成相似性矩阵。将相似性矩阵的列集合作为新特征向量，命名为新的空间关系特征向量，从而将原来的特征向量映射到一个欧氏空间上。最后，在新特征空间上计算相似性，特征向量之间的相似性问题就转化为新的空间关系特征向量之间的相似性问题。在新特征空间上，图像与图像之间的空间结构变得清晰了，有利于图像检索准确度的提高。在Corel数据库上进行实验，所提方法在平均检索查准率、查全率查准率和可视化评价指标上都优于基于颜色直方图的图像检索方法。结果表明，基于新的空间关系特征的图像检索方法有效利用了图像间空间结构上的相关性信息，具有更好的检索效果。

关键词：

空间结构；特征向量；相似性矩阵；特征空间；图像检索

中图分类号： TP391.413 文献标志码：A

0引言

随着互联网时代的到来，图像数量飞速增长，要从数以万计的图像中寻找需要的图像是一件困难的事情，这就促进了图像检索相关技术的飞速发展。图像检索可分为基于文本的图像检索[1]和基于内容的图像检索[2]。基于文本的图像检索技术是通过人工对图像进行标注，然后通过这些标注来实现图像检索的过程。此方法由于人工工作量大及标注的因人而异，使用起来具有很大的局限性。基于内容的图像检索技术则通过提取图像的颜色、纹理以及形状等底层特征[3]形成特征库，将查询图像的特征提取出来与特征库里的特征进行匹配，返回匹配的图像，从而实现图像的自动化查询检索。基于内容的图像检索技术由于其自动化的检索过程，越来越多地受到人们的青睐。

特征提取是图像检索的重要过程，现有的特征提取方法一般是提取图像的颜色、纹理及形状等底层特征[3]。颜色直方图作为常用的颜色特征，可以表现图像的全局颜色分布，因其平移、旋转和缩放不变性被广泛应用于图像检索中，文献[4]提出一种模糊空间颜色直方图，这种特征包括图像内部的颜色和空间两种信息，其特点是模糊量化，当精确分割不可用时可以选择性集成前景图像。Yu等[5]在2013年提出了尺度不变特征转换（ScaleInvariant Feature Transform， SIFT）局部二值模式（Local Binary Pattern， LBP）的特征表征方法。该方法使底层纹理特征与SIFT结合，具有较好的检索效果。方向梯度直方图（Histogram Of Gradient， HOG）是经典的形状特征提取方法之一，Dalal等[6]在2005年经典方法HOG+支持向量机（Support Vector Machine， SVM）中首次提出了HOG。Kato等[7]于2015年提出Segmental HOG描述子，其灵活的模板可以自动适应输入图像从而使检测更加鲁棒。除了单独提取颜色、纹理和形状等底层特征[3]作为特征向量，不少方法还将三者中至少两者相结合，并得到了不错的效果。Sandhu等[8]提出将颜色、纹理和形状特征相结合的方法，从而可以充分利用图像内部颜色、纹理的空间分布进行图像检索。以上方法虽然有些利用了图像内部的空间分布信息，但未利用图像间空间结构上的相关性信息。

符号数据与数值型数据不同，符号数据缺乏一个清晰的空间结构，针对这种情况，Qian等[9]提出了空间结构与符号数据聚类的方法。该方法提出一种新的数据表示方式，它将一系列的符号对象映射到一个欧氏空间，在这个新特征空间上，就可以计算符号数据之间的距离，从而进行符号数据的聚类。

图像与图像之间没有清晰的空间结构，本文利用文献[9]的方法，提出一种基于新的空间关系特征的图像检索方法。首先，计算特征向量两两之间的相似性，形成相似性矩阵，将相似性矩阵归一化到[0，1]，相似性矩阵的列集合作为新特征向量即新的空间关系特征向量，这样就将没有清晰空间结构的特征向量映射到一个欧氏空间上；最后，在新特征空间上重新计算相似性，特征向量之间的相似性问题就转化为新的空间关系特征向量之间的相似性问题。在新特征空间上，图像与图像之间的空间结构变得清晰了，这样做有利于图像检索准确度的提高。

1新的空间关系特征

Qian等[9]提出的空间结构与符号数据聚类的方法，其具体过程如下：

给定一个符号数据集，如表1所示。其中U={x1，x2，…，xn}是n个符号对象，A={a1，a2，…，am}是m个权重为W={w1，w2，…，wm}的符号特征，ai（xj）是对象xj的特征ai的符号值。现给出符号对象的一种新的数据描述方式，计算符号对象两两之间的相似性，其定义为：

本文得到一种通过描述符号对象之间相似性的新的空间结构。为讨论方便，假设各特征的权重相等（虽然这样会使其失去一般性），用新维度{ci=xi，1≤i≤n}描述对象，xi（cj）是映射到新维度cj上的对象xi，如表2所示。

空间结构与符号数据聚类方法[9]的工作原理在例1中阐明。

例1给出一个包括3个六面体的符号数据集，每个六面体包括6个特征，如表3所示。

假设这些特征有相同的权重w1=w2=…=w6=1/6，使用经典集合理论，可以获得三个对象之间的六个特征的集合关系，它可以描述数据集在每个特征上的类结构，如图1（a）所示。然而，在整个特征空间上，这种方法不能很好地发现潜在的类结构。在下文中，建立它的空间结构。首先，通过表3，可以计算符号数据集中任意两个对象xi=xj的概率，通过计算，它们的结果如表4所示。

通过空间结构矩阵，原始结构数据集通过三个新特征c1=x1、c2=x2和c3=x3转换到一个欧氏空间，如图1（b）所示，从这三个对象的几何结构可以看出对象x1和对象x2之间的距离比起对象x1和对象x3之间的距离、对象x2和对象x3之间的距离都近多了。

将Qian等[9]提出的空间结构与符号数据聚类的思想应用到图像检索上，每幅图像对应着一个符号对象，图像的特征向量维数对应着符号对象的特征个数，则图像的特征向量就对应着符号对象的特征集合。

现给出图像的一种新的数据描述方式即新的空间关系特征，其定义为：

计算图像的特征向量两两之间的相似性，形成相似性矩阵，称相似性矩阵的列集合为新的空间关系特征，某图像的新的空间关系特征向量表示的是该图像与全部图像之间的相似性关系。

将图像的特征向量通过新的空间关系特征映射到一个欧氏空间后，图像的新维度就对应着符号对象的新维度，图像的新的空间关系特征向量就对应着符号对象的新维度集合。没有清晰空间结构的特征向量之间的相似性问题就转化为新特征空间下有清晰空间结构的新的空间关系特征向量之间的相似性问题，通过图像在新特征空间下的几何关系就可以得到图像的相似图像。

2基于新的空间关系特征的图像检索

2.1图像检索的查询方式

由于图像特征本身的复杂性，图像的查询方式也有多种[10]。特征查询指的是查询时用户可以选择颜色、形状以及纹理等单个特征或按某权值的特征组合，如单一特征“检索40%绿色、50%红色、10%蓝色的图像”，如多个特征“检索包含绿色和花朵纹理的图像，其中蓝色的权重为15%、纹理为85%”。草图查询指的是用户画出与查询的图像颜色、形状或纹理相似的草图。浏览检索指的是用户浏览图像库中的图像，找到与自己的目标图像相近的图像后再把其作为要查询图像的例子，这种方式适用于用户检索目的不明确或对图像库中的信息结构、类型等不太了解的情况。示例查询指的是用户给出要查询图像的例子，提取特征后与图像库中图像比较，找出和要查询图像特征相似的图像。示例查询既方便又简单，所以大部分图像检索系统都采用这种查询方式，这也是本文采用的查询方式。

2.2本文方法与一般图像检索方法的区别

图像检索一般分为两个步骤，如图2（a）所示。一般图像检索方法步骤中，在原始特征空间上，图像之间的空间结构不够清晰。本文方法是在图像检索步骤中增加了一步，如图2（b）所示，将提取后的特征映射到一个欧氏空间上，在新特征空间上，可以清晰地看出图像之间的空间结构，从而有利于图像检索准确度的提高。

2.3本文方法的具体实现过程

基于新的空间关系特征的图像检索方法的具体过程如下。

1）特征提取。假设图像库中有n幅图像，分别命名为m1，m2，…，mn，使用该方法对n幅图像进行特征提取，提取出来的特征向量分别为F1，F2，…，Fn，每个特征向量的维数是相等的。

2）将特征向量映射到一个新特征空间（欧氏空间）上。任取图像库中的第i（i∈（1，n））幅图像mi作为查询图像，计算查询图像mi的特征向量Fi与图像库中各图像的特征向量之间的相似性，记作Wi={wi，1，wi，2，…，wi，n}，其中wi， j表示查询图像mi的特征向量Fi与图像库中第j（j∈（1，n））幅图像mj的特征向量Fj之间的相似性，则每幅图像的特征向量与图像库中各图像的特征向量之间的相似性可形成n×n此处的大写N，与后面的小写n，是否需要保持一致？请明确。的相似性矩阵W，将W归一化到[0，1]区间。

W=w1，1w1，2…w1， j…w1，n

w2，1w2，2…w2， j…w2，n

wi，1wi，2…wi， j…wi，n

wn，1wn，2…wn， j…wn，n（2）

其中i， j∈（1，n）。

当数据库较大时，相似性矩阵采用分块存储的方法，相似性计算过程则采用并行计算以缩短检索时间。此时，图像的特征向量就映射到一个欧氏空间，相似性矩阵的每列为图像的一个新维度，称图像的新维度集合为图像的新的空间关系特征向量，相似性矩阵的每行就是相应图像的新的空间关系特征向量Wi={wi，1，wi，2，…，wi，n}（i∈（1，n））。

3）在新特征空间上特征匹配。当待查询图像mi与图像库中的某幅图像mj具有相近的相似图像集和不相似图像集时，则这两幅图像是相似图像的可能性很大。没有清晰空间结构的特征向量之间的相似性问题就转化为新特征空间下有清晰空间结构的新的空间关系特征向量之间的相似性问题，查询图像mi与图像mj是否相似的问题则转换为计算图像mi的新的空间关系特征向量Wi={wi，1，wi，2，…，wi，n}与图像mj的新的空间关系特征向量Wj={wj，1，wj，2，…，wj，n}是否相似的问题（i， j∈（1，n））。返回此特征匹配结果，当本文方法检索准确度高于在原始特征空间上的检索准确度时，说明本文方法有效。

3实验过程与结果分析

3.1实验过程分析

实验以颜色直方图为例，说明本文方法的有效性。颜色直方图是在各图像检索系统中被广泛使用的颜色特征，它描述了一幅图像中不同颜色所占的比例情况。相似内容的图像一般会有相似的颜色比例，颜色直方图就是将颜色空间按某种规律分为若干区间，每个区间为一个柄，对柄内像素个数进行统计并归一化处理后得到的。

本文采用文献[11]提出的（16∶4∶4）非均匀量化方案对六角锥体模型HSV（Hue Saturation Value）颜色空间的图像进行量化，即先将图像转化到HSV颜色空间，将图像的色调（Hue， H）分量量化成16个值，饱和度（Saturation， S）和亮度（Value， V）分量分别量化成4个值。量化后可以获得16×4×4=256种颜色，将三维颜色直方图沿H分量方向将相邻的两个值相加，将相加的和作为新的三维颜色直方图。由于人眼对HSV颜色空间的色彩有较好的感知和鉴别力，现有方法很多都将图像先换转到HSV颜色空间，再对其3个分量分别量化，这样对颜色的轻微变化会具有鲁棒性，而且HSV颜色空间可以方便地与三原色RGB（Red Green Blue）颜色空间进行相互转换，如文献[12]和文献[13]。故先将图像转换到HSV颜色空间，然后通过颜色直方图特征提取方法提取待查询图像在内的全部图像的颜色特征向量，在全局相似性图像检索基准数据库Corel[14]数据库上进行实验。本文选取Corel 5k数据库，该数据库有50类图像，每类图像都有100张，这100张图像相互之间就是相似图像。

本文的所有实验都在基于Windows 7操作系统上的Matlab R2012b编程平台上进行实验，并采用平均检索查准率（Average Retrieval Precision， ARP）[5]评价、查全率查准率评价和可视化评价3个评价指标来验证，以证明本文提出方法的有效性。

3.2实验结果分析

3.2.1ARP评价

设mi为查询的图像，B（mi）为检索结果的相似图像集和不相似图像集之和，A（mi）为检索结果中的相似图像集，则查询图像mi的查准率P（mi）为：

P（mi）=A（mi）∩B（mi）/B（mi）（3）

平均检索查准率定义为：

ARP（IDk）=1N∑id（mi）=IDkP（i）（4）

其中：IDk是图像的类别，k在全局相似性图像检索基准数据库Corel 5k数据库的取值范围为1到50，分别表示这50类图像；id（mi）为查询图像mi的类别；N为IDk类的图像总数，取值为100。在本文中，B（mi）取100，恰好为50类中每类图像的总数。假设某类图像的ARP等于0.6，则表示把该类图像的每张图像都作为查询图像后返回相似性最高的前100张图像，将返回结果中正确的张数相加取平均值，则这个平均值是60幅。

实验结果如表5所示，由表可知采用新的空间关系特征的50类图像平均ARP值要高于采用颜色直方图特征的50类图像平均ARP值。

3.2.2查全率查准率评价

仅从ARP的角度来说明检索效果的好坏缺乏全面性，本文采取查全率查准率评价来说明本实验方法的优越性。查准率衡量的是检索出的相似图像集与检索出的全部图像集（相似图像集与不相似图像集之和）的百分比率。查全率衡量的是检索出的相似图像集与图像库中全部相似图像集的百分比率。查全率和查准率之间是互逆的：如果将图像库中的所有图像返回为结果集合，则查全率为100%，但查准率很低；如果检索结果只返回唯一的相似图像，则查准率为100%，但查全率很低。以此评价指标评价算法时，先按照查全率查准率绘制曲线，假定查全率为某合适值，按照查准率的高低情况来衡量算法是否有效。

实验在每类图像中随机抽取2幅共100幅图像，将50类图像查准率、查全率的平均值作为实验的最终结果。由图3可知：1）在查全率相同时，采用新的空间关系特征比采用颜色直方图特征有更高的查准率。2）从整体看，采用新的空间关系特征比采用颜色直方图特征有更高的图像检索准确率。

3.2.3可视化评价

检索结果的可视化可反映检索结果的空间排列，使用可视化评价可以更直观地展现检索结果，确认检索结果是否符合人们需要。本文取检索返回结果的前15幅作为评价图像，来评价基于新的空间关系特征的图像检索方法的优劣。

根据图4可知，采用颜色直方图特征的查询结果中有五幅是错误的，并且从第2幅图像就开始出错，而采用新的空间关系特征的查询结果中有两幅是错误的，出错图像从第7幅开始。由可视化结果可知，本文方法更有效。

4结语

本文提出一种基于新的空间关系特征的图像检索方法，该方法在一般图像检索步骤的基础上，增加了将提取后的特征映射到一个欧氏空间上这一步，在新特征空间上再进行特征匹配，返回检索结果。在新特征空间上，可以充分利用图像间空间结构上的相关性信息，实验结果表明本文的图像检索方法比在原始特征空间上的图像检索方法更有效。下一步考虑继续从更多方面使用合适的机器学习思想完善图像检索的各个步骤，使得检索准确度有更进一步的提高。

参考文献：

[1]

BACH J R， FULLER C， GUPTA A， et al. Virage image search engine： an open framework for image management [C]// Storage and Retrieval for Image and Video Databases IV. San Jose， CA： SPIE， 1996， 2670： 76-87.

[2]

DATTA R， JOSHI D， LI J， et al. Image retrieval： ideas， influences， and trends of the new age [J]. ACM Computing Surveys， 2008， 40（2）： 2007.

[3]

YONG R， HUANG T S， CHANG S F. Image retrieval： current techniques， promising directions， and open issues [J]. Journal of Visual Communication & Image Representation， 1999， 10（1）： 39-62.

[4]

XIANG Z J， CHEN Q， LIU Y. Person reidentification by fuzzy space color histogram [J]. Multimedia Tools and Applications， 2014， 73（1）： 91-107.

[5]

YU J， QIN Z， WAN T， et al. Feature integration analysis of bagoffeatures model for image retrieval [J]. Neurocomputing， 2013， 120（10）： 355-364.

[6]

DALAL N， TRIGGS B. Histograms of oriented gradients for human detection [C]// CVPR 2005： Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2005： 886-893.

[7]

KATO T， RELATOR R， NGOUV H， et al. Segmental HOG： new descriptor for glomerulus detection in kidney microscopy image [J]. BMC Bioinformatics， 2015， 16（1）： 1-16.

[8]

SANDHU A， KOCHHAR A. Content based image retrieval using texture， color and shape for image analysis [J]. International Journal of Computers & Technology， 2012， 3（1）： 149-152.

[9]

QIAN Y， LI F， LIANG J， et al. Space structure and clustering of categorical data [J]. IEEE Transactions on Neural Networks & Learning Systems， 2015， PP（99）： 1-13.

[10]

黄祥林，沈兰荪.基于内容的图像检索技术研究[J].电子学报，2002，30（7）：1065-1071.（HUANG X L， SHEN L S. Research on contentbased image retrieval techniques [J]. Acta Electronica Sinica， 2002， 30（7）： 1065-1071.）

[11]

陈秀新，贾克斌.三维量化颜色直方图在彩色图像检索中的应用[J].计算机应用与软件，2012，29（9）：31-32.（CHEN X X， JIA K B. Application of threedimensional quantised color image retrieval [J]. Computer Applications and Software， 2012， 29（9）： 31-32.）

[12]

周明全，韦娜，耿国华.交互信息理论及改进的颜色量化方法在图像检索中的应用研究[J].小型微型计算机系统，2006，27（7）：1331-1334.（ZHOU M Q， WEI N， GENG G H. Research to the application of mutual information and improved color quantization method in content based image retrieval [J]. Journal of Chinese Computer Systems， 2006， 27（7）： 1331-1334.）

[13]

张水利，郑秀萍，雷文礼.基于量化颜色空间的彩色图像检索算法[J].计算机仿真，2011，27（10）：194-196.（ZHANG S L， ZHENG X P， LEI W L. Method of color image retrieval based on quantified color space [J]. Computer Simulation， 2011， 27（10）： 194-196）.

[14]

WANG J Z， LI J， WIEDERHOLD G. SIMPLIcity： semanticssensitive integrated matching for picture libraries [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2001， 23（9）： 947-963.