Efficient video similarity measurement with video signature
- 28 February 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems for Video Technology
- Vol. 13 (1) , 59-74
- https://doi.org/10.1109/tcsvt.2002.808080
Abstract
The proliferation of video content on the Web makes similarity detection an indispensable tool in Web data management, searching, and navigation. We propose a number of algorithms to efficiently measure video similarity. We define video as a set of frames, which are represented as high dimensional vectors in a feature space. Our goal is to measure ideal video similarity (IVS), defined as the percentage of clusters of similar frames shared between two video sequences. Since IVS is too complex to be deployed in large database applications, we approximate it with Voronoi video similarity (VVS), defined as the volume of the intersection between Voronoi cells of similar clusters. We propose a class of randomized algorithms to estimate VVS by first summarizing each video with a small set of its sampled frames, called the video signature (ViSig), and then calculating the distances between corresponding frames from the two ViSigs. By generating samples with a probability distribution that describes the video statistics, and ranking them based upon their likelihood of making an error in the estimation, we show analytically that ViSig can provide an unbiased estimate of IVS. Experimental results on a large dataset of Web video and a set of MPEG-7 test sequences with artificially generated similar versions are provided to demonstrate the retrieval performance of our proposed techniques.Keywords
This publication has 15 references indexed in Scilit:
- A distance measure for video sequence similarity matchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the complexity of probabilistic image retrievalPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient video similarity measurement and searchPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Distributional clustering for efficient content-based retrieval of images and videoPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Multimodal pattern matching for audio-visual query and retrievalPublished by SPIE-Intl Soc Optical Eng ,2001
- Monitoring multivariate aviation safety data by data depth: control charts and threshold systemsIIE Transactions, 2000
- Similarity measuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- Syntactic clustering of the WebComputer Networks and ISDN Systems, 1997
- Finding Groups in DataPublished by Wiley ,1990
- SLINK: An optimally efficient algorithm for the single-link cluster methodThe Computer Journal, 1973