摘要：基于内容的图像检索是计算机视觉领域的一个研究热点。本文提出了一种利用随机树进行分类的图像检索方法。该检索方法首先提取每幅图像的随机大小的子窗口，并以这些子窗口为特征构建随机树，再利用到达随机树叶子节点的子窗口数量来计算图片之间的相似度，最后检索出图像的相似图片，即得到检索的结果。

　　关键词：随机树；基于内容的图像检索；聚类；图像处理

　　中图分类号：TP391文献标识码：A文章编号：1009-3044（2012）08-1913-03

　　Base-on Randomized Tree Content-based Image Retrieval

　　ZHANG Rui-jun, ZHAO Hong-qiao

　　（University of South China, Computer Science and Technology Institute , Hengyang 421001,China）

　　Abstract: We propose a new method for content-based image retrieval which builds the randomized trees with a set of sub-windows randomly extracted from a sample of images. Firstly, this algorithm extracted a number of variable size sub-windows as a set of features from an image. Then several randomized trees are built on these features, and we can obtain the similarities between images by computing the number of the sub-windows falling in a same leaf. Output the class containing sample image, namely get the retrieval results.

　　Key words: concurrency; object orientation; inheritance anomaly; incremental inheritance; category theory

　　随着图像技术在各领域的应用，大规模存储图像系统逐渐变得不可或缺。而如何有效地组织存储和检索图像就显得的有为的重要。传统的图像检索是基于文本的，即通过图片的名称、文字信息和索引关系来实现查询功能。用户输入一串文字，检索系统给出与该文字直接相关的图片。而基于内容的图像检索系统（CBIR, Content-based image retrieval），是计算机视觉领域中关注大规模数据内检索数字图像的研究分支，即通过对图像进行分析和分类统一建模，根据模型对图像进行特征提取分类存入特征库，同时对特征库建立索引以提高查询效率。用户输入查询图片，不需要对输入图片和查询图片进行进一步的文字描述，系统会查找到具有相同或相似内容的其他图片[1]。

　　通常来说，一张图片包含大量的特征信息，但在查询过程中只是需要足够特征信息，而不是全部特征信息。Maree等人提出了基于对图像随机区域进行特征提取分类的方法[2~3].。他们利用已经标记的图片训练集，对每张图片进行随机提取子区域，对子区域进行特征提取，并建立随机树。该方法能够有效的减少对图像特征提取计算的时间。本文是在其基础上通过利用随机树进行聚类，以解决未经标记的图片数据库。该方法首先通过对图片进行局部采样，形成采样子窗口，通过构建的随机树，将采样子窗口进行分类，从而将图片分类。

　　1随机树的构建

　　图像的全局特征在一定程度上能对目标进行描述和区分，但容易受到目标部分缺损、背景、仿射变换等因素的干扰[1,7,8,9]。为了解决全局特征容易受到目标部分缺损、背景以及仿射变换等因素干扰的问题，目前

　　很多学者提出了利用局部特征对目标图像建立特征描述[4]。图像的局部特征具有更好的唯一性、不变性和鲁棒性，能更好的适应图像背景混杂、局部遮挡、光线变化等情况。将图像的局部特征技术应用到图像检索系统中，对于图像的意义的良好表征、快速正确的图像特征匹配而言具有重要的意义。本文采用在图像中用随机大小的方形窗口进行图像局部采样，然后将采样后的窗口进行双线性插值统一到固定尺寸（16*16）。这样既保证了采样到丰富的图像表征，同时也保证了无论是局部还全局的不同区域的特征采样。

　　由于在领域内搜索计算量大，运行缓慢，尤其是在包含了大量高维数据的局部特征描述，阻碍了系统的快速响应。而一些基于树的数据结构和邻近搜索算法能够有效的用于索引搜索[6~7]。本文采用生成多颗随机树，通过计算树与树之间的相似度进行分类，实现对未标记的图片进行分类和检索。

　　算法1单颗随机树构建（图1示）

　　输入：图像序列N，子窗口数目Nw和阈值nmin

　　输出：随机树T

　　1）将图像序列N的每张图片进行子窗口提取并编号，统一到固定大小16×16。

　　2）生成随机判定式，形成判定结点。

　　3）根据判定结果，将子窗口分别划分到不同的结点中，当叶子节点内的符合条件的子窗口数目小于阈值nmin时停止划分。

　　3利用随机树计算相似度

　　利用随机树进行分类的思想是图像间相似部分的子窗口会在随机树上到达同一叶子处，利用在随机树的不同叶子上所包含图像的子窗口的数量不同来进行分类的。其表达式是

　　其中WT代表是两张图像在树T叶子L处的相似度，i , i’分别代表两张图像，NL代表叶子L上包含子窗口的数目。式1说明了如果两张图像相似，则会形成一个子集，体现在树上就是包含相似部分的子窗口会到达同一叶子。由于单颗随机树的准确性往往不够精确，通常将式1扩展到N棵树上，扩展为（i,i’）（2）

　　其中相似的度量控制是依赖于自定义的阈值参数nmin。当nmin越大时，叶子节点内会出现更多的相似子窗口图像，表现出两图像的相似度更高。换言之，阈值参数nmin控制了相似的速率，树的数量控制了相似的平滑度。

　　4图像检索算法

　　在图像检索中，我们首先定义NR为数据库图像集合，IQ为查询图像。我们按照以下步骤来进行查询：1）对NR中的每一张图像随机抽取Nls个随机大小的子窗口，统一到固定大小16 x 16，建立随机树

　　2）根据式2来计算W（），IQ，计算出前N张相似图像。定义Nts为查询图像IQ提取的子窗口数目，则图像IQ和图像IRi的相似度计算可以重写为：

　　5实验结果与分析

　　本文实验采用的是UK-Bench图像数据集。UK-Bench图像数据集是由美国肯塔基大学提供的用于测试是别的图像数据集。图像集包含了大约2550类物体的4种不同角度方向照片，每张图像大小为640x480的彩色图片。图像集中包含了植物，人，书籍，户内外的物体，通常用于建立实验图像数据库。

　　在实验过程中，分别验证参数图像提取子窗口数目Nls，随机树数目T，叶子节点最小到达阈值nmin对图像检索精度的影响，得到图2，默认情况下Nls=1000，T=10，nmin=15。从图2（a）中可以看出当参数Nls超过1000时，图像的检索的准确率提高速率放慢，过多的增加图像提取子窗口数目只会增加检索计算量，而对检索率的提高却是极其有限。从图2（b）中可以看出当参数T超过6时，图

　　像的检索的准确率提高速率放慢，过多的增加随机树T数量并不会对检索率的有很大的提高。从图2（c）中可以看出当参数nmin越大时，图像的检索越低，但是分类结果更为精确。从实验结果中，我们可以看出当Nls=1000，T=5，4　　6结束语

　　基于图像内容的检索是目前计算机视觉领域的一个研究热点，但是计算复杂，且准确度不理想。本文采出了利用随机树对从图像中提取出来的随机大小子窗口进行分类的方法进行图像检索。该方法能有效的避免大量高维数据的局部特征的计算，能够快速的进行图像检测。

　　参考文献：

　　[1] Datta, R., Joshi, D., Li, J. and Wang, J.Z.: Image Retrieval: Ideas, Influences, and Trends of the New Age[J].AC M Computing Surveys, 2007,40（2）：1-60.

　　[2] Maree, R., Geurts, P., Visimberga, G., Piater, J. and Wehenkel, L.: An empirical comparison of machine learning algorithms for generic image classification[C].Proc. Conference on innovative techniques and applications of artificial intelligence, 2003:169-182.

　　[3] Maree, R., Geurts, P., Piater, J. and Wehenkel, L.: Random Sub-windows for Robust Image Classification[J].Proc. IEEE CVPR, 2005（1）： 34?40.

　　[4] Schmid, C. and Mohr, R.: Local Grey value Invariants for Image Retrieval[J].IEEE PAMI, 1997,19（5）：530-534.

　　[5] Friedman, J H, Bentley J L, Finkel R An algorithm for finding best matches in logarithmic expected time[J].ACM Transactions o n Mathe? matical l Software, 1977,3（3）：209?226.

　　[6] Geurts P, Ernst D,Wehenkel L. Extremely Randomized Trees, Machine Learning, 2006,36,（1）：3-42.

　　[7]刘忠伟，章毓晋。利用局部累加直方图进行彩色图像检索。中国图像图形学报。1998,3（7）：533-53.

　　[8]伯晓晨，刘建平。基于颜色直方图的图像检索[J].中国图像图形学报。1999,4A（1）：33-37.

　　[9]曹莉华，柳伟，李国辉。基于多种主色调的图像检索算法研究与实现[J].计算机研究与发展。1999,36（1）96-100.