An efficient least common subgraph algorithm for video indexing

Many tasks in computer vision can be expressed as graph problems. This allows the task to be solved using a well studied algorithm, however many of these algorithms are of exponential complexity. This is a disadvantage when considered in the context of searching a database of images or videos for similarity. Work by Mesaner and Bunke (1995) has suggested a new class of graph matching algorithms which uses a priori knowledge about a database of models to reduce the time taken during online classification. This paper presents a new algorithm which extends the earlier work to detection of the largest common subgraph.

Video indexing and similarity retrieval by largest common subgraph detection using decision trees

While the largest common subgraph (LCSG) between a query and a database of models can provide an elegant and intuitive measure of similarity for many applications, it is computationally expensive to compute. Recently developed algorithms for subgraph isomorphism detection take advantage of prior knowledge of a database of models to improve the speed of on-line matching. This paper presents a new algorithm based on similar principles to solve the largest common subgraph problem. The new algorithm significantly reduces the computational complexity of detection of the LCSG between a known database of models, and a query given on-line.

Improved cryptanalysis of the Common Scrambling Algorithm Stream Cipher

This paper provides a fresh analysis of the widely-used Common Scrambling Algorithm Stream Cipher (CSA-SC). Firstly, a new representation of CSA-SC with a state size of only 89 bits is given, a significant reduction from the 103 bit state of a previous CSA-SC representation. Analysis of this 89-bit representation demonstrates that the basis of a previous guess-and-determine attack is flawed. Correcting this flaw increases the complexity of that attack so that it is worse than exhaustive key search. Although that attack is not feasible, the reduced state size of our representation makes it obvious that CSA-SC is vulnerable to several generic attacks, for which feasible parameters are given.

Weaknesses in the initialisation process of the Common Scrambling Algorithm Stream Cipher

The Common Scrambling Algorithm Stream Cipher (CSASC) is a shift register based stream cipher designed to encrypt digital video broadcast. CSA-SC produces a pseudo-random binary sequence that is used to mask the contents of the transmission. In this paper, we analyse the initialisation process of the CSA-SC keystream generator and demonstrate weaknesses which lead to state convergence, slid pairs and shifted keystreams. As a result, the cipher may be vulnerable to distinguishing attacks, time-memory-data trade-off attacks or slide attacks.

ECG Noise Removal using GA tuned Sign-Data Least Mean Square Algorithm

Adaptive filter is a primary method to filter Electrocardiogram (ECG), because it does not need the signal statistical characteristics. In this paper, an adaptive filtering technique for denoising the ECG based on Genetic Algorithm (GA) tuned Sign-Data Least Mean Square (SD-LMS) algorithm is proposed. This technique minimizes the mean-squared error between the primary input, which is a noisy ECG, and a reference input which can be either noise that is correlated in some way with the noise in the primary input or a signal that is correlated only with ECG in the primary input. Noise is used as the reference signal in this work. The algorithm was applied to the records from the MIT -BIH Arrhythmia database for removing the baseline wander and 60Hz power line interference. The proposed algorithm gave an average signal to noise ratio improvement of 10.75 dB for baseline wander and 24.26 dB for power line interference which is better than the previous reported works

An all-substrings common subsequence algorithm

Given two strings A and B of lengths n(a) and n(b), n(a) <= n(b), respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B` of B, the length of the longest string that is a subsequence of both A and B. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n(a)n(b)) time and O(n(a) + n(b)) space. After this preparation, it is possible to build that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and a matrix of size O(n(b)(2)) the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem. (C) 2007 Elsevier B.V. All rights reserved.

Comparison between known propagation models using least squares tuning algorithm on 5.8 GHz in Amazon region cities

ABSTRACT: This paper presents a performance comparison between known propagation Models through least squares tuning algorithm for 5.8 GHz frequency band. The studied environment is based on the 12 cities located in Amazon Region. After adjustments and simulations, SUI Model showed the smaller RMS error and standard deviation when compared with COST231-Hata and ECC-33 models.

Analysis and performance of a UPC implementation of a parallel longest common subsequence algorithm

An important problem in computational biology is finding the longest common subsequence (LCS) of two nucleotide sequences. This paper examines the correctness and performance of a recently proposed parallel LCS algorithm that uses successor tables and pruning rules to construct a list of sets from which an LCS can be easily reconstructed. Counterexamples are given for two pruning rules that were given with the original algorithm. Because of these errors, performance measurements originally reported cannot be validated. The work presented here shows that speedup can be reliably achieved by an implementation in Unified Parallel C that runs on an Infiniband cluster. This performance is partly facilitated by exploiting the software cache of the MuPC runtime system. In addition, this implementation achieved speedup without bulk memory copy operations and the associated programming complexity of message passing.

Determination of ethenzamide and acetoaminophen in quaternary powdered samples by near infrared spectroscopy and searching combination moving window partial least squares algorithm: effects of spectral resolution and signal-to-noise ratio

The present study reports an application of the searching combination moving window partial least squares (SCMWPLS) algorithm to the determination of ethenzamide and acetoaminophen in quaternary powdered samples by near infrared (NIR) spectroscopy. Another purpose of the study was to examine the instrumentation effects of spectral resolution and signal-to-noise ratio of the Buchi NIRLab N-200 FT-NIR spectrometer equipped with an InGaAs detector. The informative spectral intervals of NIR spectra of a series of quaternary powdered mixture samples were first located for ethenzamide and acetoaminophen by use of moving window partial least squares regression (MWPLSR). Then, these located spectral intervals were further optimised by SCMWPLS for subsequent partial least squares (PLS) model development. The improved results are attributed to both the less complex PLS models and to higher accuracy of predicted concentrations of ethenzamide and acetoaminophen in the optimised informative spectral intervals that are featured by NIR bands. At the same time, SCMWPLS is also demonstrated as a viable route for wavelength selection.

A common Tabu search algorithm for the global optimization of engineering problems

A novel common Tabu algorithm for global optimizations of engineering problems is presented. The robustness and efficiency of the presented method are evaluated by using standard mathematical functions and hy solving a practical engineering problem. The numerical results show that the proposed method is (i) superior to the conventional Tabu search algorithm in robustness, and (ii) superior to the simulated annealing algorithm in efficiency. (C) 2001 Elsevier B.V. B.V. All rights reserved.

Lovasz theta function, SVMs and Finding Dense Subgraphs

In this paper we establish that the Lovasz theta function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-theta graphs, on which Lovasz theta function can be approximated well by a Support vector machine (SVM). We show that Erdos-Renyi random G(n, p) graphs are SVM-theta graphs for log(4)n/n <= p < 1. Even if we embed a large clique of size Theta(root np/1-p) in a G(n, p) graph the resultant graph still remains a SVM-theta graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the theta function is the notion of orthogonal labellings. We introduce common orthogonal labellings which extends the idea of orthogonal labellings to multiple graphs. This allows us to propose a Multiple Kernel learning (MKL) based solution which is capable of identifying a large common dense subgraph in multiple graphs. Both in the planted clique case and common subgraph detection problem the proposed solutions beat the state of the art by an order of magnitude.

Analysis of Extended Partial Least Squares for Monitoring Large-Scale Processes

This paper theoretically analysis the recently proposed "Extended Partial Least Squares" (EPLS) algorithm. After pointing out some conceptual deficiencies, a revised algorithm is introduced that covers the middle ground between Partial Least Squares and Principal Component Analysis. It maximises a covariance criterion between a cause and an effect variable set (partial least squares) and allows a complete reconstruction of the recorded data (principal component analysis). The new and conceptually simpler EPLS algorithm has successfully been applied in detecting and diagnosing various fault conditions, where the original EPLS algorithm did only offer fault detection.

A mixed cost-function adaptive algorithm for ADSL time-domain equalization

We propose a mixed cost-function adaptive initialization algorithm for the time domain equalizer in a discrete multitone (DMT)-based asymmetric digital subscriber line. Using our approach, a higher convergence rate than that of the commonly used least-mean square algorithm is obtained, whilst attaining bit rates close to the optimum maximum shortening SNR and the upper bound SNR. Furthermore, our proposed method outperforms the minimum mean-squared error design for a range of time domain equalizer (TEQ) filter lengths. The improved performance outweighs the small increase in computational complexity required. A block variant of our proposed algorithm is also presented to overcome the increased latency imposed on the feedback path of the adaptive system.

A hybrid mixed cost-function TEQ initialization algorithm for ADSL modems

In this paper, we present a hybrid mixed cost-function adaptive initialization algorithm for the time domain equalizer in a discrete multitone (DMT)-based asymmetric digital subscriber loop. Using our approach, a higher convergence rate than that of the commonly used least-mean square algorithm is obtained, whilst attaining bit rates close to the optimum maximum shortening SNR and the upper bound SNR. Moreover, our proposed method outperforms the minimum mean-squared error design for a range of TEQ filter lengths.