비디오 데이터 세트의 하이퍼 사각형 표현에 기초한 비디오 유사성 검색 알고리즘
Similarity Search Algorithm Based on Hyper-Rectangular Representation of Video Data Sets
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
이 연구에서는 대용량 비디오 데이터 스트림에 대한 유사성 검색 알고리즘을 제시한다. 수많은 프레임으로 이루어진 비디오 스트림은 각 프레임을 다차원 벡터(multidimensional vector)로 나타냄으로써 다차원 데이터 공간 상에서 시퀀스로 나타낼 수 있다. 이 시퀀스의 특성을 분석함으로써 각 시퀀스를 비디오 세그먼트(video segment)와 이 세그먼트의 집합인 비디오 클러스터(video cluster)로 표현한다. 본 연구에서는 이러한 비디오 세그먼트와 클러스터를 사용하여 두 비디오 스트림 사이의 유사성 함수(similarity function)를 제시하고, 이 함수에 근거하여 비디오 세그먼트의 하이퍼 사각형과 대표 프레임에 기초한 두 가지의 유사성 검색 알고리즘을 제안한다. 전자는 정해성(correctness)을 보장하는 알고리즘이며, 후자는 정해성을 약간 희생하는 대신 상당한 효율성을 얻을 수 있는 알고리즘이다. 다양한 유형의 비디오 스트림 및 가상으로 생성된 스트림 데이터에 대한 실험을 통하여 제시한 알고리즘의 성능을 분석한다.
Abstract
In this research, the similarity search algorithms are provided for large video data streams. A video stream that consists of a number of frames can be expressed by a sequence in the multidimensional data space, by representing each frame with a multidimensional vector. By analyzing various characteristics of the sequence, it is partitioned into multiple video segments and clusters which are represented by hyper-rectangles. Using the hyper-rectangles of video segments and clusters, similarity functions between two video streams are defined, and two similarity search algorithms are proposed based on the similarity functions：algorithms by hyper-rectangles and by representative frames. The former is an algorithm that guarantees the correctness while the latter focuses on the efficiency with a slight sacrifice of the correctness. Experiments on different types of video streams and synthetically generated stream data show the strength of our proposed algorithms.
참고문헌 (21)
- R. Agrawal, "Efficient Similarity Search in Sequence Databases", (is), pp.69~84 (1993)
- N. Beckmann, "The R*-tree：an efficient and robust access method for points and rectangles Proc. of ACM SIGMOD", pp.322~331 (1990)
- S. Berchtold, "The X-tree：an index structure for high-dimensional data", pp.28~39 (1996)
- C. Faloutsos, "Fast Subsequence Matching in Time-Series Databases", minnesota, pp.419~429 (1994)
- M. Flickner, "Query by Image and Video Content：The QBIC System", 28(9), pp.23~32 (1995)
- A. Guttman, "R-trees：a dynamic index structure for spatial searching", massachusetts, pp.47~57 (1984)
- A. Hampapur, "Virage Video Engine", pp.pp.188~-197 (1997)
- A. K. Jain, "Query by Video Clip", 7, pp.369~384 (1999)
- N. Katayama, "The SR-tree：an index structure for high-dimensional nearest neighbour queries", pp.369~380 (1997)
- E. J. Keogh, "Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases", pp.151~162 (2001)
- S. W. Kim, "An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases", (2001), pp.607~614
- S. L. Lee, "Similarity Search for Multidimensional Data Sequences", pp.599~608 (2000)
- S. L. Lee, "Hyper-Rectangle Based Segmentation and Clustering of Large Video Data Sets", Vol.141(no.1-2), pp.139~168 (2002)
- John Chung-Mong Lee,Qing Li,and Wei Xiong, "VIMS：A Video Information Management System", 4(1), pp.7~28 (1997)
- Virginia E. Ogle, "Chabot：Retrieval from a Relational Database of images", 28(9), pp.40~48 (1995)
- J. H. Oh, "Efficient and Cost-effective Techniques for Browsing and Indexing Large Video Databases", pp.pp.415-~426 (2000)
- D. Rafiei, "Similarity-Based Queries for Time Series Data", pp.13~25 (1997)
- J. R. Smith, "VisualSEEk：A Fully Automated Content-based Image Query System", Columbia University
- Y. Taniguchi, "PanoramaExcerpts：Extracting and Packing Panoramas for Video Browsing", pp.427~436 (1997)
- B. K. Yi, "Fast Time Sequence Indexing for Arbitrary Lp Norms", pp.385~394 (2000)
- H. J. Zhang, "An Integrated System for Content-Based Video Retrieval and Browsing", 30, pp.643~653 (1997)