基于IPDSH兴趣点空间区域划分的图像检索

张 旭，郭宝龙，孟繁杰，孙 伟

（西安电子科技大学 智能控制与图像工程研究所，西安 710071）

利用局部特征的图像检索主要分为基于图像分割的方法和基于兴趣点的方法。由于目前尚未找到一个通用的算法来有效分割图像中的目标区域和背景，且易受到来自于光照、背景、仿射变换等许多因素的干扰，导致检索准确度下降。而兴趣点作为认知心理学中的注视焦点，可以对物体形状粗略表征。另外它具有计算量小、信息含量高的特点，可以灵活地描述图像的细节。将其应用于图像检索技术中，利用局部特征描述方法对其局部区域进行特征提取，最后再进行相似度匹配，可以有效提高检索精度，且具有很好的通用性和稳定性［1-4］。符祥等［5］在兴趣点局部计算Zernike矩，通过比较兴趣点局部Zernike矩的欧氏距离来提取最优匹配点对，在去除不匹配的兴趣点后利用兴趣点的空间离散度来估计图像内容的相似度；陈绵书等［6］将MPDD算法应用于图像检索，先将图像均匀细分成小块，然后用图像的颜色特征和纹理特征表示图像块内容，采用K均值法对图像块进行聚类，产生包示例，最后应用MPDD算法对图像进行检索；Zheng等［7］在对图像的每个区域检测出兴趣点后，结合兴趣点的边缘类型直方图和不变量进行检索；陈慧婷等人［8］将纹理概率统计模型和全局主颜色方法有机地结合起来，在对纹理和颜色特征线性加权的基础上对组合后的纹理和颜色特征进行二次检索；曾智勇等［9］以显著兴趣点为线索，设计了一种基于显著兴趣点的环形颜色直方图，在利用兴趣点局部特征的同时，又考虑了兴趣点的空间分布结构。

以上研究成果更多地考虑到兴趣点的空间分布信息，大大提高了图像检索的准确度，但是终究不能达到理想状况，因为面对各式各样的图片种类时，某种单一的算法往往失去了通用性，因此距其实际应用还有很大差距。为了进一步提高图像检索准确度，本文提出了一种新的基于IPDSH和区域划分的图像检索方法，该方法降低了传统算法提取出的不稳定兴趣点对图像检索结果产生的干扰，考虑了图像中感兴趣区域的内部颜色特征和该区域在图像中所处的空间位置，将其划分为凸包和环形区域，提高了区域划分方法的可靠性。

1 系统描述

首先对图像在尺度空间中采用IPDSH算法检测兴趣点，然后按照兴趣点的分布将图像划分成一系列同心圆环和凸包，最后统计每个圆环内部兴趣点邻域内的伪泽尼克矩（Pseudo－Zernike moments）和凸包内像素的颜色直方图（Color histogram），并经过加权处理生成特征向量。

图像数据库中每幅图像的特征向量只需要计算一次，方法与查询图像相同，得到的集合就组成了特征数据库。查询图像只需要与特征数据库进行特征相似度匹配即可。经过计算查询图像特征向量与图像数据库中每幅图像的特征向量的相似度，并按照欧氏距离的大小进行排序，最后将相似度高的图像显示出来，就得到了相应的检索结果。检索流程如图1所示。由于IPDSH兴趣点和伪泽尼克矩的幅度都具有旋转不变的性质，且环形区域划分的方法也具有几何对称性，因此这种方法也具有旋转、平移不变性。

图1 图像检索流程图Fig.1 Image retrieval structure system title

2 基于IPDSH兴趣点的检测

兴趣点主要的一类是角点，其中，Harris角点检测［10］是一种比较有效的方法，但是它对尺度变化非常敏感，这样在对角点响应函数执行非极大值抑制确定局部极大值时，角点提取的效果就完全依赖于阈值的设定。阈值大会丢失角点信息，阈值小又会提取出伪角点。针对这些问题，本文利用IPDSH兴趣点检测算法可以提高兴趣点检测的快速性和准确性。

对于输入图像f（x，y），利用二维高斯核对其进行卷积，得到多尺度空间序列：

其中，二维高斯核为

再使用DoG（Difference of Gaussian）函数对图像卷积求取尺度空间极值，函数表达式为

定义尺度空间的自相关矩阵A为

式中：δi为积分尺度；δd为微分尺度；fx和fy分别为x和y方向上的导数；为对f做高斯滤波。记A的两个特征值λ1和λ2为自相关函数的主曲率，则不同尺度空间的兴趣点检测公式为

图2 IPDSH和SIFT兴趣点检测结果比较Fig.2 Comparison of detecting results of IPDSH and SIFT

若C的局部极大值坐标落在多尺度空间极值点邻域内，则保留该极值点，否则剔除。然后检测兴趣点邻域是否存在Harris角点，若存在，则保留该点且将其看作稳定兴趣点。其中，α为常数（一般取0.04～0.06），C的局部极大值计算方法是根据λ1和λ2的大小来确定的。图2是一副Lena图像的IPDSH和SIFT算法结果比较。从图中可以看出，IPDSH算法有效地剔除了不稳定的兴趣点。使用IPDSH方法可以有效减少不稳定兴趣点对检索结果的影响，提高了兴趣点区域划分和特征检测的速度及准确度。

3 区域划分和特征提取

3.1 凸包颜色直方图

凸包是包围一个平面兴趣点集所有点的最小凸多边形，应用于图像处理、模式识别等诸多领域。凸包计算方法很多，考虑到运行速度，本文采用格雷厄姆扫描法来获取兴趣点凸包［11］。凸包内部区域即注视焦点的集中所在。由于兴趣点本身具有形状特征属性，因此兴趣点凸包可以实现感兴趣物体和图像背景的分割。图3（a）是区域划分的示意图，图3（b）是一副鲜花图像区域划分的结果。图3（a）中的黑点代表兴趣点，多边形代表兴趣点凸包。从图3（b）中可以看出，图像的兴趣点凸包接近物体的轮廓，具有理想的提取感兴趣区域能力。

图3 空间区域划分示意图Fig.3 Schematic diagram to annular division

考虑到图像中被关注物的整体颜色特征一般会有别于背景，而凸包可以有效描述出事物的大致外形，故本文采用颜色直方图对凸包内像素进行处理。颜色直方图具有旋转，平移和缩放不变性。具体方法为：首先使用非等间隔量化方法对图像HSV空间颜色进行量化，再将色调H空间分成8份，饱和度空间S和亮度空间V分成3份，然后将3个分量合成一个一维特征矢量I，且I＝9 H＋3S＋V。取值范围是［0，71］，每个值都代表一种主要颜色。按照公式Hk＝numk／num（k＝0，1，…，L－1）对凸包内的颜色做直方图统计，可以得到凸包颜色直方图特征向量。其中numk为感兴趣区域颜色为k的像素数量，num为区域内全部像素的数量，L为量化后颜色柄数。

3.2 环形区域伪泽尼克矩

将图像空间按照兴趣点的空间分布划分成n个同心圆环，然后以每个兴趣点为中心展开其周围3×3邻域统计每个圆环内部兴趣点领域的伪泽尼克矩。图3（b）中同心圆环表示环形区域划分示意图，图中蓝色“＋”号表示兴趣点，绿色“＋”号表示同心圆的圆心，即兴趣点的质心。具体划分方法参考文献［12］。由于这n个同心圆环具有对称性，因此这种方法在提取颜色空间信息的同时也具有旋转、平移不变性。伪泽尼克矩是不变矩的一种，具有比泽尼克矩更强的抗噪性。

图像的伪泽尼克矩是将图像映射到一组基函数上得到的，称为伪泽尼克矩的基，记为｛Vnm（x，y）｝，这组基构成了单位圆（x2＋y2≤1）内的一组完备正交集，其定义为

这些多项式相互正交，满足关系：

图像f（x，y）的 （n，m）阶伪泽尼克矩定义为

对于数字图像，在极坐标下式（9）变为

计算图像的伪泽尼克矩时，选图像的兴趣点为极坐标的原点，将单位圆内的像素映射为极坐标，单位圆外的像素在计算时不予考虑。

4 相似性度量

设Q为待查询图像，I为图像库中的一副图像，使用加权特征距离来度量它们内容的相似度。用S1（Q，I）和S2（Q，I）分别表示Q 和I 的颜色特征和伪泽尼克矩的特征向量相似度，kc和kp表示权值（kc＋kp＝1），则相似度度量公式可以写为

式中：N为兴趣点总数目；ωk为第k个圆环兴趣点的数目；H为颜色直方图表达式；P为伪泽尼克矩。

S的值越大，则视为越相似。一般来说，图像的形状信息对于图像检索更为关键，所以通常取kp＞kc，本文通过大量实验发现，当kp＝0.7、kc＝0.3时，检索效果较好。

5 实验结果

本文使用的图像库是SIMPLIcity测试集，它是从Corel图像库中抽取的1000幅图像，这些图像分属10个类，编号为：1－土著居民和村庄；2－海滩；3－建筑和雕塑；4－公共汽车；5－恐龙；6－大象；7－花卉；8－马；9－山地和冰川；10－食物。每类100幅，共1000幅图（后续实验中将以此编号作为种类编号）。图4是从每类图像中随机抽取的一张图片作为示意图。

图4 图像数据库示例Fig.4 Examples Images in the Database

为了验证本文算法的检索性能，在相同的软硬件平台下（软件环境：Matlab7.1；硬件环境：Core 2Q8200CPU为2.33GHz，4.0GB内存），分别用本文算法与基于凸包和基于环形区域划分的算法做了比较。实验时提取的兴趣点数为150个，颜色特征量化为HSV空间中的72维。兴趣点环形划分数为6。在1000幅图像的测试集中对每一类图像随机抽取20幅，计算出返回图像总数为20幅时的检索准确度为

式中：T为输出图像总数；n为查准图像数目。

图5为三种算法的准确度比较曲线图。从图中可以看出，相对于单独地使用凸包算法或环形区域划分算法，将二者结合处理得到的检索准确度更高。

图5 不同算法检索准确度比较Fig.5 Comparison of different algorithms’precision

图6 不同方法对鲜花的检索结果Fig.6 Retrieval result of flower using different methods

图6（a）是使用凸包颜色直方图进行检索的结果，图6（b）是使用环形区域中稳定兴趣点邻域内的伪泽尼克矩进行检索的结果，图6（c）是本文算法检索的结果。每幅图中左上角的图像为查询图像，其余图像是查询结果。从左到右，从上到下，相似度依次减小。分析发现，当返回的图像数为20时，采用本文方法的20幅图像都是花卉图像，准确度为100%，如图6（c）所示；凸包颜色直方图的检索结果有3幅图像不正确，检索准确度为85%，如图6（a）所示；环形区域中稳定兴趣点邻域内的伪泽尼克矩的检索结果中有4幅图像不正确，检索准确度为80%，如图6（b）所示。证明本文算法将凸包内的颜色直方图与稳定兴趣点环形区域中兴趣点邻域内伪泽尼克矩有效结合，并将加权特征作为特征向量进行检索，能获得更高的准确度。

为了进一步说明本文方法的检索性能，还将本文算法与文献［13］和文献［14］中算法做了实验对比，其具体步骤为：随机抽取20幅图像作为查询图像，在图像库中进行相似度检索，统计返回图像数分别为10、20、30幅时的检索准确度P10、P20、P30，然后对每一类图像分别计算平均检索准确度、，得到的结果见表1。

从表1中可以看出，利用本文算法进行图像检索的平均检索准确度较文献［13］的方法提高了7.0%，较文献［14］的方法提高了15.1%，本文方法明显较优。

为了检验算法的复杂度，本文从特征提取时间复杂度和图像检索时间复杂度两个方面将本文算法与文献［13－14］中算法进行比较。

（1）特征提取时间复杂度。实验中在Corel图像库中任意取100幅图像，利用本文方法提取特征所需的平均时间为24.43s，采用文献［13］提取特征所需的平均时间为42.58s，采用文献［14］提取特征所需的平均时间为44.68s。

（2）图像检索时间复杂度。实验中在Corel图像库中检索出与查询图像相似度最大的20幅图像并显示，本文算法的平均检索时间为1.72s；文献［13］算法的平均检索时间为2.35s；文献［14］算法的平均检索时间为3.59s。从实验结果可以看出，本文算法的特征提取时间复杂度和检索时间复杂度都小于其他两种算法。

表1 本文算法与其他算法的检索性能比较Table 1 Precision of different methods

6 结束语

使用IPDSH方法可以有效提取尺度空间稳定的兴趣点。通过这些兴趣点集合来求取凸包和划分环形区域，并在此基础上提取凸包颜色直方图和图像的环形区域中稳定兴趣点邻域内的伪泽尼克矩，加权处理后得到图像的特征向量，最后利用相似度检索方法来检索图片。该检索方法计算简单，并且具有旋转、平移和缩放不变性。实验结果表明，该方法与传统的基于兴趣点的检索方法相比，算法的复杂度小，检索速度快，并能大幅度提高图像检索的准确度。在今后的工作中，将把相关反馈的技术结合到本算法中，从而更有效地提高检索精度。另外，使用数量更大、种类更全的数据库来进行检索，也将是下一步工作的重点。

［1］Schmid C，Mohr R.Local gray value invariants for image retrieval［J］.IEEE Transaction on PAMI，1997，19（5）：530－535.

［2］Mikoljczyk K，Schmid C.Indexing based on scale－Invariant feature［C］∥Proc of International Conference on Computer Vision，Vancouver，2001.

［3］Shao H，Ferrari V，Svoboda T，et al.Fast indexing for image retrieval based on local appearance with re－ranking［C］∥Proceedings of IEEE International Conference on Image Processing，Barcelona，Spain，2003.

［4］汪华章，何小海，宰文姣.基于局部和全局特征融合的图像检索［J］.光学精密工程，2008，16（6）：1098－1104.Wang Hua－zhang，He Xiao－hai，Zai Wen－jiao.Image retrieval based on combining local and global features［J］.Optics and Precision Engineering，2008，16（6）：1098－1104.

［5］符祥，曾接贤.基于兴趣点匹配和空间分布的图像检索方法［J］.中国激光，2010，37（3）：774－778.Fu Xiang，Zeng Jie－xian.A novel image retrieval method based on interest points matching and distribution［J］.Chinese Journal of Lasers，2010，37（3）：774－778.

［6］陈绵书，杨树媛，赵志杰，等.多点多样性密度算法及其在图像检索中的应用［J］.吉林大学学报：工学版，2011，41（5）：1456－1460.Chen Mian－shu，Yang Shu－yuan，Zhao Zhi－jie，et al.Multi－points diverse density learning algorithm and its application in image retrieval［J］.Journal of Jilin University（Engineering and Technology Edition），2011，41（5）：1456－1460.

［7］Zheng X，Zhou M，Wang X C.Interest point based medical image retrieval［C］∥Lecture Notes in Computer Science.Beijing：Springer Verlag，2008.

［8］陈慧婷，覃团发，唐振华，等.综合纹理统计模型与全局主颜色的图像检索方法［J］.北京邮电大学学报，2011，34：100－103，118.Chen Hui－ting，Qin Tuan－fa，Tang Zhen－hua，et al.A method of image retrievals based on texture probability statistics and global dominant color［J］.Journal of Beijing University of Posts and Telecommunications，2011，34：100－103，118.

［9］曾智勇，张学军，崔江涛，等.基于显著兴趣点颜色及空间分布的图像检索新方法［J］.光子学报，2006，35（2）：308－311.Zeng Zhi－yong，Zhang Xue－jun，Cui Jinag－tao，et al.A novel image retrieval algorithm based on color and distribution of prominent interest points［J］.Acta Photonica Sinca，2006，35（2）：308－311.

［10］全燕鸣，黎淑梅.大型工件测量系统中的快速图像拼接方法［J］.华南理工大学学报：自然科学版，2011，39（8）：60－65.Quan Yan－ming，Li Shu－mei.Fast image mosaic method for large－scale workpiece measurement system［J］.Journal of South China University of Technology（Natural Science），2011，39（8）：60－65.

［11］Preparata F P，Shamos M I.Computational Geometry：an Introduction［M］.New York：Springer－Verlag，1985.

［12］孟繁杰，郭宝龙.一种基于兴趣点颜色及空间分布的图像检索方法［J］.西安电子科技大学学报：自然科学版，2005，32（2）：256－259.Meng Fan－jie，Guo Bao－long.A novel image retrieval algorithm based on the color and distribution of interest points［J］.Journal of Xidian University（Natural Science），2005，32（2）：256－259.

［13］王向阳，陈景伟，于永健.一种基于彩色边缘综合特征的图像检索方法［J］.华南理工大学学报，2010，23（2）：216－221.Wang Xiang－yang，Chen Jing－wei，Yu Yong－jian.Edge－based color image retrieval by using multiple features［J］.Pattern Recognition and Artificial Intelligence，2010，23（2）：216－221.

［14］Wu J H，Wei Z R，Li C Y.Color and texture feature for content based image retrieval［J］.International Journal of Digital Content Technology and Its Applications，2010，4（3）：43－49.