Search

We study the problem of video shot boundary detection using an adaptive edge-oriented framework. Our approach is distinct in its use of multiple multilevel features in the required processing. Adaptation is provided by a careful analysis of these multilevel features, based on shot variability. We consider three levels of adaptation: at the feature extraction stage using locally-adaptive edge maps, at the video sequence level, and at the individual shot level. We show how to provide adaptive parameters for the multilevel edge-based approach, and how to determine adaptive thresholds for the shot boundaries based on the characteristics of the particular shot being indexed. The result is a fast adaptive scheme that provides a slightly better performance in terms of robustness, and a five fold efficiency improvement in shot characterization and classification. The reported work has applications beyond direct video indexing, and could be used in real-time applications, such as in dynamic monitoring and modeling of video data traffic in multimedia communications, and in real-time video surveillance. Experimental results are included.

A novel scheme for efficient shape classification using region descriptors and extreme learning machine with kernels is proposed. The skeleton and boundary of the input shape image are first extracted. Then the boundary is simplified to remove noise and minor variations. Finally, region descriptors for the local skeleton, and the simplified shape signature are constructed to form a hybrid feature vector. Training and classification are then performed using kernel extreme learning machine (k-ELM) for efficient shape classification. Experimental results show that the proposed scheme is very fast and can archive high classification accuracy of 91.43 % on the challenging MPEG-7 dataset, outperforming existing state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Given a text or database T, the circular pattern discovery (CPD) problem is to identify 'interesting' circular patterns in T. Here, no specific input pattern is provided, and what is interesting is typically defined in terms of constraints in the search. We propose two algorithms for the CPD problem. The first algorithm uses suffix trees and suffix links to solve the exact CPD problem in O(m2²N) time, where m2 is the maximum length of the circular patterns and N is the total length of the sequence database. The second algorithm uses suffix arrays to solve the more challenging approximate CPD (ACPD) problem in O(km2²N²) worst case, and O(km2²N²) on average, where k is the maximum allowed error(s). By exploiting the nature of the ACPD problem, the complexity is reduced to O(m2²N²) time in the worst case, and O(m2²N) on average. [ABSTRACT FROM AUTHOR]

Given a text T=T[1 … n] and a circular pattern P=P[1 … m], the circular pattern matching (CPM) problem is to find all occurrences of P in T. We present the first algorithm that exploits suffix links to solve the exact CPM (ECPM) problem in O(n log |Σ|) time and O(n) space, where Σ is the symbol alphabet. Then, we present a q-gram-based algorithm for the approximate CPM (ACPM) problem using the idea of bidirectional edit distance. Our algorithm finds all k-approximate occurrences of P in T. We then extend each algorithm to solve the all-against-all variant of the CPM problem for both exact and k-approximate matches. Although the CPM problem has been studied since the 1980s, this is the first attempt on the all-against-all variant, without using a trivial application of standard CPM algorithms. Given a database S=S1$1S2$2 … SZ$Z of Z sequences, our algorithms solve the all-against-all ACPM problem in O(kmaN) time on average and O(kmmN2) worst case, where k is the error parameter, N=∑i=1Z(|Si|+1), ma=N/Z and mm=maxi=1,2,… Z{|Si|}. Space complexity is O(N). These can be compared with the O(N2malog ma) average and O(N3log mm) worst case time required by the best available ACPM algorithm. [ABSTRACT FROM PUBLISHER]

This review provides a survey of techniques for pattern matching in compressed text and images. Normally compressed data needs to be decompressed before it is processed, but if the compression has been done in the right way, it is often possible to search the data without having to decompress it, or at least only partially decompress it. The problem can be divided into lossless and lossy compression methods, and then in each of these cases the pattern matching can be either exact or inexact. Much work has been reported in the literature on techniques for all of these cases, including algorithms that are suitable for pattern matching for various compression methods, and compression methods designed specifically for pattern matching. This work is surveyed in this review. The review also exposes the important relationship between pattern matching and compression, and proposes some performance measures for compressed pattern matching algorithms. Ideas and directions for future work are also described. [ABSTRACT FROM AUTHOR]

We introduce the VST (virtual suffix tree), an efficient data structure for suffix trees and suffix arrays. Starting from the suffix array, we construct the suffix tree, from which we derive the virtual suffix tree. Later, we remove the intermediate step of suffix tree construction, and build the VST directly from the suffix array. The VST provides the same functionality as the suffix tree, including suffix links, but at a much smaller space requirement. It has the same linear time construction even for large alphabets, Σ, requires O(n) space to store (n is the string length), and allows searching for a pattern of length m to be performed in O(m log |Σ|) time, the same time needed for a suffix tree. Given the VST, we show an algorithm that computes all the suffix links in linear time, independent of Σ. The VST requires less space than other recently proposed data structures for suffix trees and suffix arrays, such as the enhanced suffix array [1], and the linearized suffix tree [17]. On average, the space requirement (including that for suffix arrays and suffix links) is 13.8n bytes for the regular VST, and 12.05n bytes in its compact form. [ABSTRACT FROM AUTHOR]

Abstract Background Successfully modeling high-dimensional data involving thousands of variables is challenging. This is especially true for gene expression profiling experiments, given the large number of genes involved and the small number of samples available. Random Forests (RF) is a popular and widely used approach to feature selection for such "small n, large p problems." However, Random Forests suffers from instability, especially in the presence of noisy and/or unbalanced inputs. Results We present RKNN-FS, an innovative feature selection procedure for "small n, large p problems." RKNN-FS is based on Random KNN (RKNN), a novel generalization of traditional nearest-neighbor modeling. RKNN consists of an ensemble of base k-nearest neighbor models, each constructed from a random subset of the input variables. To rank the importance of the variables, we define a criterion on the RKNN framework, using the notion of support. A two-stage backward model selection method is then developed based on this criterion. Empirical results on microarray data sets with thousands of variables and relatively few samples show that RKNN-FS is an effective feature selection approach for high-dimensional data. RKNN is similar to Random Forests in terms of classification accuracy without feature selection. However, RKNN provides much better classification accuracy than RF when each method incorporates a feature-selection step. Our results show that RKNN is significantly more stable and more robust than Random Forests for feature selection when the input data are noisy and/or unbalanced. Further, RKNN-FS is much faster than the Random Forests feature selection method (RF-FS), especially for large scale problems, involving thousands of variables and multiple classes. Conclusions Given the superiority of Random KNN in classification performance when compared with Random Forests, RKNN-FS's simplicity and ease of implementation, and its superiority in speed and stability, we propose RKNN-FS as a faster and more stable alternative to Random Forests in classification problems involving feature selection for high-dimensional datasets.

We investigate off-line dictionary oriented approaches to DNA sequence compression, based on the Burrows-Wheeler Transform (BWT). The preponderance of short repeating patterns is an important phenomenon in biological sequences. Here, we propose off-line methods to compress DNA sequences that exploit the different repetition structures inherent in such sequences. Repetition analysis is performed based on the relationship between the BWT and important pattern matching data structures, such as the suffix tree and suffix array. We discuss how the proposed approach can be incorporated in the BWT compression pipeline.