【作者】 郭勇；

【导师】 崔江涛；

【作者基本信息】 西安电子科技大学 ， 计算机系统结构， 2010， 硕士

【摘要】 多媒体内容检测是多媒体数据库中的一项重要应用。内容检测时提取的特征向量往往具有高维特性,传统的多维索引结构在高维空间中会面临着“维数灾难”问题。本文针对高维空间中的查询效率问题,提出了一种新的基于单维映射的高维索引方法,能够加速多媒体数据的相似性检测。本文首先分析了高维索引技术的发展历程和各类索引结构的特点。面向向量空间中的κ近邻搜索,提出了一种新的结合主分量和距离过滤的单维映射方法-pcDistance。首先将高维数据点集进行聚类划分,对每个聚类进行主分量分析,将数据点与聚类中心的距离映射为一维数据,并采用B+-Tree索引这些一维数据。在κ近邻搜索中,根据查询向量与主分量坐标轴的空间关系对数据点进行过滤,并且采用部分失真搜索算法加速搜索过程。实验结果表明,与其他索引方法相比,新方法能够显著降低搜索过程中的数据访问数量,提高κ近邻搜索性能。本文最后将pcDistance方法应用到雷同视频片段检测中,采用pcDistance索引视频片段特征-有界坐标系(Bounded Coordinate System),通过在5万规模的视频片段库中进行实验表明,采用pcDistance方法能够加快雷同视频片段的检测速度。更多还原

【Abstract】 An important research in the field of multimedia databases is the detection of similar multimedia objects such as images, sound and videos. The dimensionality of feature vectors extracted from the multimedia objects is often very high, when traditional indexing methods face the difficulty of’curse of dimensionality’. For the efficiency of query in high-dimensional space, a new index structure is presented to speed up the similarity query of multimedia.In this paper, we analyze the development of high-dimensional indexing technology and characteristics of various high-dimensional index structures, especially one-dimensional mapping method. For k-nearest neighbor (KNN) search in the high-dimensional vector space, a new one-dimensional mapping approach based on Principal Component and distance, named pcDistance, is proposed. The new approach partitions the dataset, and selects a reference point for each partition. Then Principal Component Analysis is performed on each partition in the dataset, and the data points are transformed into a single dimensional value based on their distance to the reference point. And we use B+-Tree to index the single dimensional values. When performing k-nearest neighbor search, points can be pruned according to the relationship between the query and the axis determined by the first principal component, and partial distortion searching algorithm can also be used to speed up the query processing. Experiment results show that the new approach can reduce the number of data points accessed during the query, and can provide a faster search speed than existing high-dimensional indexing methods. Finally, we apply pcDistance to the Video Copy Detection. In this system, pcDistance is employed to manage and index the compacted video feature, BCS (Bounded Coordinate System). Our extensive performance study on a large database of more than 50,000 video clips demonstrates that pcDistance can improve the performance in detecting copy video.更多还原