Fast similarity search and clustering of video sequences on the world-wide-web

Sen Ching S. Cheung, Avideh Zakhor

Research output: Contribution to journalArticlepeer-review

55 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)524-537
Number of pages14
JournalIEEE Transactions on Multimedia
Volume7
Issue number3
DOIs
StatePublished - Jun 2005

Bibliographical note

Funding Information:
Manuscript received October 9, 2002; revised November 29, 2003. This work was supported by the Air Force Office of Scientific Research (AFOSR) under Grant F49620-00-1-0327 and by the National Science Foundation (NSF) under Grant ANI-9905799. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Kai-Kuang Ma.

Funding Information:
The authors thank the anonymous reviewers for providing valuable comments on the initial drafts of this paper. For S.-C. Cheung, part of the revision of this paper was performed under the auspices of the U.S. Department of Energy by the University of California, Lawrence Livermore National Laboratory, under Contract W-7405-Eng-48.

Keywords

  • Clustering
  • Dimension reduction
  • Similarity search
  • Video signature
  • Web search

ASJC Scopus subject areas

  • Signal Processing
  • Media Technology
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Fast similarity search and clustering of video sequences on the world-wide-web'. Together they form a unique fingerprint.

Cite this