【作者】 曹玉东；

【导师】 郭军；

【作者基本信息】 北京邮电大学 ， 信号与信息处理， 2011， 博士

【摘要】 随着因特网的普及和数字技术的进步,包括图像在内的大量多媒体资源散布于因特网的各个节点上,如何有效的组织和检索多媒体数据成为一个重要的研究课题。本文着重研究了图像检索中的特征表示和高维数据的索引方法。图像检索可以分为两类：基于文本的图像检索和基于内容的图像检索。早期的图像检索以基于文本为主,该方法主要是通过输入关键词的形式搜索相关的图片资源,这种方法必须事先以文字信息标注图像,所以工作量较大,标注信息也影响检索的准确性。随后基于内容的图像检索(CBIR)逐渐得到发展,该方法直接提取图像的视觉信息特征,并直接利用这些视觉特征建立索引或检索。本文首先重点研究了图像的视觉特征表示方法,图像的视觉特征通常分为全局特征和局部特征,局部特征能够捕捉图像的细微变化,对遮挡、变形都有一定的鲁棒性,其中SIFT特征(Scale Invariant Feature Transform)和MSER特征(Maximally Stable Extremal Regions)因其卓越的性能和检测速度快的优点而被广泛使用。本文详细地分析和研究了这两种局部特征的检测方法和描述算子,在此基础上提出了一种图像的融合特征表示。融合特征把三种局部特征SIFT、MSER和moment invariants有效地结合在一起,极大地提高了特征的区分性和显著性。针对融合特征的具体特点,本文又提出了高效的由粗到精的分级匹配策略。本文研究的另一个重点内容是高维图像数据的索引机制。通常,图像的特征表示都是几十甚至上百维的高维矢量,使用合理的高维数据索引方法将提高大规模图像数据库的检索效率,但是,由于受到“维数灾难”问题的影响,传统的索引方法(例如R-tree等)在处理图像的高维数据时,性能急剧下降,甚至出现不如线性搜索(又称顺序搜索或穷尽搜索)的情况,而局部敏感哈希(locality sensitive hashing, LSH)索引则表现出卓越的性能,成为最受欢迎的高维数据索引方法之一。LSH完全从另外一个角度建立索引结构：首先将高维数据点投影到某个特征空间,然后从哈希函数簇中随机选择k个哈希函数,如果两个(或者更多的)高维数据点在这k个哈希函数上映射为相同的值,则会被认为可能是近邻而散列到同一个哈希桶中,对查询数据点做相同的散列,线性搜索与查询点发生冲突的桶,将会以较大的概率得到查询点的近邻。哈希函数的表达形式与图像问的相似性测度是对应的,第2章介绍了四种常见的哈希函数形式。结合机器学习中的弱监督学习技术(weakly supervised learning technology),本文提出了两种构造LSH函数的算法,第一个算法是在M.Datar等人提出的欧氏LSH的基础上,利用少量的相似样本对(similar sample pairs)优化选择哈希函数,进而构建更好的局部敏感哈希函数。第二个算法利用少量的相似样本对直接生成哈希函数,该方法去除了哈希函数的随机性。本文又提出了一种基于数据分布信息生成哈希函数的方法,该方法不需要标记样本,而是根据数据点的分布情况选择哈希函数的投影轴,减少了哈希函数的随机性,同时保证了投影轴之间的正交性,该方法也有效地降低了算法的空间复杂度。本文提出三种改进的LSH索引方法具有现实意义,虽然互联网提供了大量的图像资源,但是这些图像往往没有标注,或者标注信息不具体、不准确。集中标注大量的数据往往要付出高昂的代价或者是不现实的,实际的情况经常是直接使用没有标记的数据,或者同时使用大量的未标记数据和少量的标记数据,基于数据驱动和基于弱监督的LSH方法则适应了这一特点。大规模图像检索对存贮资源的需求相对较多,而内存的容量是有限的,如果实现完全在内存中完成索引的存贮和查找将会极大地提高图像检索速度。本文的实验结果表明改进的LSH方案有效的降低了内存的使用量,性能也很接近线性搜索方法。更多还原

【Abstract】 Many multimedia resources including image have scattered around network nodes with the development of Internet and digital technology. So it is of importance how to organize and retrieve multimedia data effectively. The research on representation of image feature and high dimensional data indexing method is presented in this thesis.Image retrieval comprises two types:text-based retrieval and content-based retrieval. Early text-based image retrieval system searches similar images in Internet using key words, which are input by users. The text-based method requires that the images must be labeled with text information beforehand. The work of labeling image is complex and the accuracy of label affects the effect of image retrieval. Subsequently the content-based image retrieval (CBIR) reveals its importance, which indexes and retrieves directly images with extracted visual features.An important and detailed research is given firstly on visual feature representation of image in this thesis, which includes global feature and local feature. The local feature can capture tiny difference in images and has robustness to attack of clutter and deformation. Among these local features, SIFT (Scale Invariant Feature Transform) and MSER (Maximally Stable Extremal Regions) have been widely used in image retrieval task. The detailed analysis and study on detectors and descriptors of SIFT and MSER are presented in this thesis; then, the fusional feature representation on image is designed based on SIFT, MSER and moment invariants. The fusional feature is more discriminating and robust than single local feature because it merges three local features together perfectly. The two-level matching strategy from coarseness to fineness is designed for the fusional feature, which is effective and efficient.Another focus of the research is index of image data. Generally, the image feature is a high dimensional vector comprising tens and hundreds of elements. A good indexing high dimensional data method can improve the speed of retrieval. However, the performance of traditional indexing method (say, R-tree) goes very bad on processing high dimension data because of the affect of "curse of dimensionality" problem. Evenly, it goes worse than linear search (also called sequence search or exhausted search). LSH (locality sensitive hashing algorithm) is quite popular in high dimensional data indexing method because of its perfect performance. LSH scheme indexes image data from a different perspective. The data is projected on a special feature space. Then, the k hash functions are selected randomly from a family of hash functions, and the two or more data points will be viewed as the near neighbors and be put into the one bucket because of the same projection values on k hash functions. A query point can also be hashed into buckets with the same method and its near neighbors can be acquired through linear scanning the bucket containing query point with a constant probability. The design of hash function depends on the similarity measure between images and the four type hash functions are introduced in Chapter 2.Two methods of constructing LSH function is proposed with weakly supervised learning technology of machine learning, one of which selects better hash functions using some similar sample pairs based on the Euclidean LSH of M. Datar, and the other of which generates directly hash functions using some similar sample pairs. The later method can eliminate stochastic character of hash function.Another method of constructing LSH function is presented based on image data distribution information, which selects the axis of projection without using labeled sample and these axes of projection were orthogonal. According to experiments, the presented method deduced space complexity effectively.The proposed three methods of improving LSH are practical. The labeled information is not accuracy and specific although many images can be downloaded on the Internet. Often, there is not the label information with the uploaded images and it is expensive or unreal to label a large of images. The unlabeled data is used directly or a small quantity of labeled data and a large quantity of unlabeled data are used together in the data-dependent or weakly supervised LSH methods. Image retrieval in a large database demands more storage space but memory capacity is limit. The image retrieval will be accelerated if the process of indexing data and searching are only performed in memory.The experimental results show that the improved LSH schemes, whose performance is access to that of linear search algorithms, deduced effectively the usage of memory.更多还原