Efficient subsequence matching over large video databases

Video similarity matching has broad applications such as copyright detection, news tracking and commercial monitoring, etc. Among these applications, one typical task is to detect the local similarity between two videos without the knowledge on positions and lengths of each matched subclip pair. However, most studies so far on video detection investigate the global similarity between two short clips using a pre-defined distance function. Although there are a few works on video subsequence detection, all these proposals fail to provide an effective query processing mechanism. In this paper, we first generalize the problem of video similarity matching. Then, a novel solution called consistent keyframe matching (CKM) is proposed to solve the problem of subsequence matching based on video segmentation. CKM is designed with two goals: (1) good scalability in terms of the query sequence length and the size of video database and (2) fast video subsequence matching in terms of processing time. Good scalability is achieved by employing a batch query paradigm, where keyframes sharing the same query space are summarized and ordered. As such, the redundancy of data access is eliminated, leading to much faster video query processing. Fast subsequence matching is achieved by comparing the keyframes of different video sequences. Specifically, a keyframe matching graph is first constructed and then divided into matched candidate subgraphs. We have evaluated our proposed approach over a very large real video database. Extensive experiments demonstrate the effectiveness and efficiency of our approach.     

基于极值点特征的时间序列相似性查询方法*

为了提高时间序列子序列匹配的准确度和效率,提出了基于极值点特征的时间序列相似性查询方法。首先识别出时间序列中的极值特征点,根据极值点使用多层次极值划分法对长序列进行划分;然后对划分得到的多层次子序列集使用改进的动态时间弯曲方法与查询序列进行相似性匹配;最后找到与查询序列最相似的子序列。实验表明,此方法在保证准确度的情况下大大提高了相似性搜索过程的效率。     

Batch Nearest Neighbor Search for Video Retrieval

To retrieve similar videos to a query clip from a large database, each video is often represented by a sequence of high- dimensional feature vectors. Typically, given a query video containing m feature vectors, an independent nearest neighbor (NN) search for each feature vector is often first performed. After completing all the NN searches, an overall similarity is then computed, i.e., a single content-based video retrieval usually involves m individual NN searches. Since normally nearby feature vectors in a video are similar, a large number of expensive random disk accesses are expected to repeatedly occur, which crucially affects the overall query performance. Batch nearest neighbor (BNN) search is stated as a batch operation that performs a number of individual NN searches. This paper presents a novel approach towards efficient high-dimensional BNN search called dynamic query ordering (DQO) for advanced optimizations of both I/O and CPU costs. Observing the overlapped candidates (or search space) of a pervious query may help to further reduce the candidate sets of subsequent queries, DQO aims at progressively finding a query order such that the common candidates among queries are fully utilized to maximally reduce the total number of candidates. Modelling the candidate set relationship of queries by a candidate overlapping graph (COG), DQO iteratively selects the next query to be executed based on its estimated pruning power to the rest of queries with the dynamically updated COG. Extensive experiments are conducted on real video datasets and show the significance of our BNN query processing strategy.     

An elastic partial shape matching technique

We consider the problem of partial shape matching. We propose to transform shapes into sequences and utilize an algorithm that determines a subsequence of a target sequence that best matches a query. In the proposed algorithm we map the problem of the best matching subsequence to the problem of a cheapest path in a directed acyclic graph (DAG). The approach allows us to compute the optimal scale and translation of sequence values, which is a nontrivial problem in the case of subsequence matching. Our experimental results demonstrate that the proposed algorithm outperforms the commonly used techniques in retrieval accuracy.     

一种通过视频片段进行视频检索的方法

视频片段检索是基于内容的视频检索的主要方式,它需要解决两个问题:(1) 从视频库里自动分割出与查询片段相似的多个片段;(2) 按照相似度从高到低排列这些相似片段.首次尝试运用图论的匹配理论来解决这两个问题.针对问题(1),把检索过程分为两个阶段:镜头检索和片段检索.在镜头检索阶段,利用相机运动信息,一个变化较大的镜头被划分为几个内容一致的子镜头,两个镜头的相似性通过对应子镜头的相似性计算得到;在片段检索阶段,通过考察相似镜头的连续性初步得到一个个相似片段,再运用最大匹配的Hungarian算法来确定真正的相似片段.针对问题(2),考虑了片段相似性判断的视觉、粒度、顺序和干扰因子,提出用最优匹配的Kuhn-Munkres算法和动态规划算法相结合,来解决片段相似度的度量问题.实验对比结果表明,所提出的方法在片段检索中可以取得更高的检索精度和更快的检索速度.     

Composition and Retrieval of Visual Information for Video Databases

This paper presents a new visual aggregation model for representing visual information about moving objects in video data. Based on available automatic scene segmentation and object tracking algorithms, the proposed model provides eight operations to calculate object motions at various levels of semantic granularity. It represents trajectory, color and dimensions of a single moving object and the directional and topological relations among multiple objects over a time interval. Each representation of a motion can be normalized to improve computational cost and storage utilization. To facilitate query processing, there are two optimal approximate matching algorithms designed to match time-series visual features of moving objects. Experimental results indicate that the proposed algorithms outperform the conventional subsequence matching methods substantially in the similarity between the two trajectories. Finally, the visual aggregation model is integrated into a relational database system and a prototype content-based video retrieval system has been implemented as well.     

Searching for variable-speed motions in long sequences of motion capture data

Motion capture data digitally represent human movements by sequences of body configurations in time. Subsequence searching in long sequences of such spatio-temporal data is difficult as query-relevant motions can vary in execution speeds and styles and can occur anywhere in a very long data sequence. To deal with these problems, we employ a fast and effective similarity measure that is elastic. The property of elasticity enables matching of two overlapping but slightly misaligned subsequences with a high confidence. Based on the elasticity, the long data sequence is partitioned into overlapping segments that are organized in multiple levels. The number of levels and sizes of overlaps are optimized to generate a modest number of segments while being able to trace an arbitrary query. In a retrieval phase, a query is always represented as a single segment and fast matched against segments within a relevant level without any costly post-processing. Moreover, visiting adjacent levels makes possible subsequence searching of time-warped (i.e., faster or slower executed) queries. To efficiently search on a large scale, segment features can be binarized and segmentation levels independently indexed. We experimentally demonstrate effectiveness and efficiency of the proposed approach for subsequence searching on a real-life dataset.     

A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases

In this paper, an algorithm is proposed for subsequence matching that supports normalization transform in time-series databases. Normalization transform enables finding sequences with similar fluctuation patterns even though they are not close to each other before the normalization transform. Simple application of existing subsequence matching algorithms to support normalization transform is not feasible since the algorithms do not have information for normalization transform of subsequences of arbitrary lengths. Application of the existing whole matching algorithm supporting normalization transform to the subsequence matching is feasible, but requires an index for every possible length of the query sequence causing serious overhead on both storage space and update time. The proposed algorithm generates indexes only for a small number of different lengths of query sequences. For subsequence matching it selects the most appropriate index among them. Better search performance can be obtained by using more indexes. In this paper, the approach is called index interpolation. It is formally proved that the proposed algorithm does not cause false dismissal. The search performance can be traded off with storage space by adjusting the number of indexes. For performance evaluation, a series of experiments is conducted using the indexes for only five different lengths out of lengths 256512 of the query sequence. The results show that the proposed algorithm outperforms the sequential scan by up to 2.4 times on the average when the selectivity of the query is 10^–2 and up to 14.6 times when it is 10^–5. Since the proposed algorithm performs better with smaller selectivities, it is suitable for practical situations, where the queries with smaller selectivities are much more frequent.     

Structure and attribute index for approximate graph matching in large graphs

The increasing popularity of graph data in various domains has lead to a renewed interest in developing efficient graph matching techniques, especially for processing large graphs. In this paper, we study the problem of approximate graph matching in a large attributed graph. Given a large attributed graph and a query graph, we compute a subgraph of the large graph that best matches the query graph. We propose a novel structure-aware and attribute-aware index to process approximate graph matching in a large attributed graph. We first construct an index on the similarity of the attributed graph, by partitioning the large search space into smaller subgraphs based on structure similarity and attribute similarity. Then, we construct a connectivity-based index to give a concise representation of inter-partition connections. We use the index to find a set of best matching paths. From these best matching paths, we compute the best matching answer graph using a greedy algorithm. Experimental results on real datasets demonstrate the efficiency of both index construction and query processing. We also show that our approach attains high-quality query answers.     

基于局部排序的视频拷贝检测

排序法是一种常用的视频拷贝检测方法.为获得更佳的检测性能,提出一种基于排序特征的视频拷贝检测方案.该方案将帧进行分块,并按照Hilbert曲线顺序分别计算曲线上相邻块的灰度关系排序特征,生成用于检测的哈希码;为了准确地在目标视频中定位可疑内容,提H{了哈希匹配方案,将序列相似度作为匹配的依据,并引入动态规划的方法提高匹配精度;最后构造了拷贝测试样本,并与传统的排序签名检测方案进行性能对比实验.结果表明,文中方案拥有较好的检测性能,适用于视频内容的拷贝检测.