【作者】 张培珍；

【导师】 付萍；

【作者基本信息】 吉林大学 ， 通信与信息系统， 2004， 硕士

【摘要】 所谓基于内容的图像检索系统，具有与传统基于文本的检索系统完全不同的框架。图像依赖其视觉特征(颜色、纹理、形状等)而非文本描述进行索引，查询根据图像视觉特征的相似度进行。用户可通过样本图像进行查询，然后查找视觉内容相似的图像，按相似度的大小排列返回给用户。通常图像可视化特征，用高维空间点或向量来描述，向量之间的接近程度反映了对象内容的相似程度，因此基于内容的图像检索就简化为空间中点快速搜索问题。速度是图像检索中的关键问题之一。但由于图像资源非常丰富，图像库中的图像通常是海量的，顺序检索的计算量是十分巨大的，因而也是十分耗时的。为进一步提高检索速度，索引作为检索的有力支持工具，已经开展了大量的研究。IBM公司最早推出的QBIC系统，它利用K－L变换来降低特征维数，再用树来构造索引。哥伦比亚大学开发的VisualSeek系统，采用了二进树算法构造索引，支持空间位置关系的查询。已经提出的索引方法还包括多维二叉树算法和Cell索引算法、Quad树、k-d树以及Grid树索引算法等等。这些早期研究的索引算法，虽然结构比较简单，但是不适合于构建目前多媒体数据库的索引。目前，比较流行的高维索引方法有R树、线性四叉树以及栅格文件。其中R树及其变体R+树 、R*树 、SS树 、SR树等组成的R树系列空间索引是最为有效的多维索引方法。但是当向量维数超过20时，应用R树索引方法的效率均迅速降低，几乎等价于顺序查找。为了能够有效地利用以上的索引方法，必须将高维特征向量转换为20以内的维数。但维数的降低不可避免地会带来信息的丢失，导致查询结果中有较多的错误记录。另外，由于R树的构造基于几何意义上的覆盖关系，它只限于以欧氏距离作为相似度量的查询。上述方法仅仅适用于对图像检索中的高维数据进行索引，而没有涉及<WP=72>到非欧氏距离的相似性度量问题。针对以上索引方法的局限性，有人提出了基于聚类的索引技术，这种技术具有动态的结构，能够处理高维数据，同时支持非欧氏距离的查询。这种索引方法将特征空间分类，相似的类别拓扑相近，支持K－近邻查询和范围查询，大大地减少了搜索的次数。目前，国内外对基于内容检索的索引技术主要集中于研究各种聚类算法的实现上。现有的聚类算法很多，比较经典的有均值算法、ISODATA算法、传递闭包法、最大树法、动态直接聚类法、编网法以及自适应算法等等。K-均值聚类算法是一种应用最广泛的一种分割聚类算法，它能有效地处理大数据集，迭代速度快，但其缺点是聚类数预先设定、聚类效果与初始聚类和事件的顺序有关，这与现实的图像数据库的特点是不符的。而模糊C均值算法，利用伪随机数产生初始类中心，造成聚类效果不稳定。本文提出了一种改进的模糊C均值聚类在图像检索中的应用算法,该算法有效地解决了初始值的选取问题，同时具有动态的删除、分裂、合并、融合、插入等功能。能够有效地对图像库进行聚类处理。实验表明通过聚类的方法索引方法，搜索时间不会随图像数据库中的图像数量线性增加，从而提高了检索效率，更加具有实效。但较高的特征维数，直接影响了聚类和检索的速度。为解决这一问题，在采用索引技术前，首先应对高维特征进行降维和去相关处理。其中，Karhunen-Loeve 变换(KLT)方法是最小均方误差意义上的最佳变换，同时具有很好的去相关特性。它基于图像统计特性的变换，提供了最大能量的压缩，而且在统计上是最优的。但缺点是不能进行基于距离空间进行，数据库规模对变换速度影响较大。这里我们提出了一种基于FastMap映射算法的降维方法，而FastMap映射算法在克服以上缺点的同时具有下列优点：它是一种基于距离函数的映射，能够与SAM相结合实现有效地检索；可视化和数据挖掘，目标能够用2－D或3－D的点来描述，能够使用户方便地<WP=73>发现图像数据库的模拟分布情况。通过实验表明，在利用不同的特征维数时，FastMap映射算法能够较好的准确度。使用该算法能够在提高了聚类和检索速度的同时，获得更高的查准率和查全率,优于传统的KLT降维方法。因此FastMap映射算法的降维能力使其对图像的检索非常有效。已有的解决高维数据聚类可视化方法主要是通过降维[6]，把高维数据投影到二维或三维空间上，从而达到可视化的目的。对于用高维特征向量来表示的图像，降维将会造成信息的严重丢失。基于上述考虑，本文采用了基于近邻方法的聚类可视化方法，直观地描述了图像数据库聚类的状况，有利于图像检索效果的评价。对于单一特征检索,由于其约束信息不足,检索效果有时会与人的视觉感受不相吻合。综合特征检索是解决这类问题的有效办法，但是，确定不同特征之间或是同一特征的不同分量之间的权重是很困难的问题。本系统实现了与操作者的检索交互中进行学习的方法, 调整权重以达到不同特征的优势互补的效果，使检索性能更接近人类视觉的特性，同时又可以提高检索的灵活性和系统的性能。文中详细地介绍了相似度衡量及多特征权重调整的算法。最后，本文研究并设计了基于聚类索引的检索工作系统。系统基于Windows2000环境，程序采用C++Builder 5.0开发，实现聚类和检索两大模块，经测试，系统运行稳?更多还原

【Abstract】 Content-based image retrieval (CBIR) system　is different from traditional retrieval system based on text mode. Index of image is described by some visual features but not by text, such as, color, texture, shape, and locality feature ect. Users always search similar image according to an example image. Result of retrieval can be feedback with ranked similarity degree, and similarity degree is computed from distance function in feature vector space. Generally, image features are described as high-dimensional space points or vectors, the distances between vectors reflect the similarity of the object images. So that content-based image retrieval can be predigest as searching for the nearest vectors　fast. Speed is an important issue in image retrieval system. Generally, image information is abundantly, and size of image in the database is large. So if images are searched SSA, computation is enormous and time-consuming. Indexing methods have been studied broadly as a useful support tool to enhance retrieval speed. The pioneer system is IBM’s QBIC system,It use Karhunen-Loeve transformation (KLT) to realize dimension reducing, and the then construct index with R* tree algorithm. Visual SEEK system developed by Columbia university, this system construct index with binary tree algorithm and retrieval based on spatial information. Some others indexing algorithm include Quard tree, k-d tree, Grid tree,　multi-binary tree and cell indexing algorithm, ect. These early indexing algorithms are easy but not suit for constructing the index of multimedia system. On the present, the popular indexing algorithms are R tree, linearity Quard- tree, and Grid file. Thereinto, R tree families as R* tree, R+ tree, SR tree, and SS tree are the most effective <WP=75>indexing methods. But with these methods the speed performance is bad and even go near to SSA. So these methods to be used as an effective index in image retrieval system, feature dimension space must be decrease lower than 20, but a lot of useful information will be lost if compact feature dimension blindness. In addition, these indexing methods only support Euclidean distance for similarity retrieval.The indexing methods above are adapted to construct the index of image databases, but haven’t refer to non- Euclidean distance to measure similarity of images. So indexing technique based on clustering is proposed. This technology has a dynamic structure ,it can deal with high-dimensional data and support non- Euclidean distance　retrieval. At the present, content-based indexing techniques are most concentrate on the algorithm study. The classical algorithms are k-means, ISODATA, maxima tree, dynamic clusering, and adaptive algorithm, ect.K-means is used as a clustering algorithm broadly. Of the many methods available for clustering feature vectors, the K-means algorithm is the quickest and simplest. This algorithm can process great data volume effectively. Despite being used in a wide application, the K-means algorithm is not exempt of drawbacks as follows: It is dependent upon the order of the feature vectors and requires number of clusters K to be given. Obviously, it is not necessarily practically in real-world applications. Fuzzy C-means(FCM) algorithm　overcomes drawbacks above, but in this algorithm initial centroids are defined randomly, this lead to the result of clustering unstable, especially when there is a great many images in the database. In this paper, we propose a modified fuzzy C-means (MFCM) scheme, this scheme illustrates how to get reasonable <WP=76>initial centroids according to the real-line images feature vectors, further more, it has capability for us to assign, eliminate, split, unit, merge, and insert feature vector dynamically. Experiments show that Using MFCM scheme, time of image retrieval won’t increase linearly with the size of image database increasing. MFCM can be used in image retrieval system effectively.High-dimensional feature is the main item affect speed of clustering and retrieval. So dimension reducing is another issue in t更多还原