Fast similarity search and clustering of video sequences on the world-wide-web
Fast similarity search and clustering of video sequences on the world-wide-web
复制标题
DOI：
10.1109/tmm.2005.846906
复制
发表时间：
2005-06
影响因子：
7.3
通讯作者：
S. Cheung;A. Zakhor
中科院分区：
文献类型：
--
作者：
S. Cheung;A. Zakhor
我们将相似的视频内容定义为具有几乎相同内容的视频序列，但可能以不同的质量压缩，重新格式化为不同的大小和帧速率，在空间或时间域中进行轻微编辑，或总结为关键帧序列。构建搜索引擎以识别万维网中的此类相似内容需要：1）鲁棒的视频相似性测量; 2）大型数据库上的快速相似性搜索技术;以及3）搜索结果的直观组织。在以前的论文中，我们提出了一种称为视频签名（ViSig）方法的视频相似性测量的随机技术。在本文中，我们专注于剩下的两个问题，提出了一个快速相似性搜索的特征提取方案，和一个聚类算法识别相似的集群。与许多其他基于内容的方法类似，ViSig方法使用高维特征向量来表示视频。为了保证一个快速的响应时间为高维向量的相似性搜索，我们提出了一种新的非线性特征提取方案，在任意度量空间，结合三角不等式与经典的主成分分析（PCA）。我们的实验表明，该技术优于PCA，Fastmap，三角形不等式修剪，Haar小波签名数据。为了进一步提高检索性能，并提供更好的组织相似性搜索结果，我们引入了一个新的图论聚类算法的大型数据库的签名。该算法将所有签名视为一个抽象的阈值图，其中距离阈值是基于局部数据统计来确定的。然后将相似的聚类识别为图中的高度连接区域。通过测量对地面真理集的检索性能，我们表明，我们提出的算法优于简单的阈值，单链接和完整的链接层次聚类技术。
We define similar video content as video sequences with almost identical content but possibly compressed at different qualities, reformatted to different sizes and frame-rates, undergone minor editing in either spatial or temporal domain, or summarized into keyframe sequences. Building a search engine to identify such similar content in the World-Wide Web requires: 1) robust video similarity measurements; 2) fast similarity search techniques on large databases; and 3) intuitive organization of search results. In a previous paper, we proposed a randomized technique called the video signature (ViSig) method for video similarity measurement. In this paper, we focus on the remaining two issues by proposing a feature extraction scheme for fast similarity search, and a clustering algorithm for identification of similar clusters. Similar to many other content-based methods, the ViSig method uses high-dimensional feature vectors to represent video. To warrant a fast response time for similarity searches on high dimensional vectors, we propose a novel nonlinear feature extraction scheme on arbitrary metric spaces that combines the triangle inequality with the classical Principal Component Analysis (PCA). We show experimentally that the proposed technique outperforms PCA, Fastmap, Triangle-Inequality Pruning, and Haar wavelet on signature data. To further improve retrieval performance, and provide better organization of similarity search results, we introduce a new graph-theoretical clustering algorithm on large databases of signatures. This algorithm treats all signatures as an abstract threshold graph, where the distance threshold is determined based on local data statistics. Similar clusters are then identified as highly connected regions in the graph. By measuring the retrieval performance against a ground-truth set, we show that our proposed algorithm outperforms simple thresholding, single-link and complete-link hierarchical clustering techniques.