Fast Algorithms for Area Morphology

Acton, S. T., Fast Algorithms for Area Morphology, Digital Signal Processing11 (2001) 187–203Efficient algorithms are developed for area morphology. As opposed to traditional morphological operations that alter grayscale images via a concatenation of order statistic filters, the area morphological operators manipulate connected components within the image level sets. Essentially, the area morphology filters are capable of removing objects based on the object area solely. These operators can then be effectively used in important multiscale and scale space tasks such as object-based coding and hierarchical image searches. Unfortunately, the traditional implementation of these filters based on level set theory precludes real-time implementation. This paper reviews previous fast algorithms and introduces a pyramidal approach. The full pyramidal algorithm is over 1000 times faster than the standard algorithm for typical image sizes. The paper provides supporting simulation results in terms of computational complexity and solution quality.     

Fast Computation of the Bezout and Dixon Resultant Matrices

Efficient algorithms are derived for computing the entries of the Bezout resultant matrix for two univariate polynomials of degree n and for calculating the entries of the Dixon–Cayley resultant matrix for three bivariate polynomials of bidegree (m, n). Standard methods based on explicit formulas requireO (n³) additions and multiplications to compute all the entries of the Bezout resultant matrix. Here we present a new recursive algorithm for computing these entries that uses onlyO (n²) additions and multiplications. The improvement is even more dramatic in the bivariate setting. Established techniques based on explicit formulas requireO (m⁴n⁴) additions and multiplications to calculate all the entries of the Dixon–Cayley resultant matrix. In contrast, our recursive algorithm for computing these entries uses onlyO (m²n³) additions and multiplications.     

Digital IIR Filter Design Using Adaptive Simulated Annealing

Chen, S., Istepanian, R., and Luk, B. L., Digital IIR Filter Design Using Adaptive Simulated Annealing, Digital Signal Processing11 (2001) 241–251Adaptive infinite-impulse-response (IIR) filtering provides a powerful approach for solving a variety of practical problems. Because the error surface of IIR filters is generally multimodal, global optimization techniques are required in order to avoid local minima. We apply a global optimization method, called the adaptive simulated annealing (ASA), to digital IIR filter design. An important advantage of the ASA is the simplicity in software programming. Simulation study involving system identification application shows that the proposed approach is accurate and has a fast convergence rate, and the results obtained demonstrate that the ASA offers a viable tool to digital IIR filter design.     

Alternating Analysis and Synthesis Filters: A New Pseudo-QMF Bank

Cruz-Roldán, F., Amo-López, P., Martín-Martín, P., and López-Ferreras, F., Alternating Analysis and Synthesis Filters: A New Pseudo-QMF Bank, Digital Signal Processing11 (2001) 329–345The process of designing a prototype filter for a pseudo quadrature mirror filter (QMF) cosine-modulated bank can require the optimization of a highly nonlinear cost function to obtain its coefficients or the calculation of a spectral factor of a valid 2Mth band filter. This article presents a new method for designing pseudo-QMF banks in which none of the aforementioned procedures are required. To obtain the coefficients of the prototype filter we can use any technique which enables us to design linear-phase Type I or Type II FIR filters. The result is a system in which amplitude distortion is very low, there is no phase distortion at all, and aliasing is slightly higher than the stopband attenuation of the prototype filter obtained. Several examples are included.     

SqFreeEVAL: An (almost) optimal real-root isolation algorithm

Let f be a univariate polynomial with real coefficients, f∈R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of f in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm.The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple O(d(L+lnd)) bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial f of degree d and whose coefficients can be written with at most L bits.Our proof uses two amortization-based techniques: first, we use the algebraic amortization technique of the standard Mahler-Davenport root bounds to interpret the integral in terms of d and L. Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds.     

Process and die profile design for tube extrusion of γ iron

This study is related to material modeling and die and process design of tube extrusion of γ iron. Strain dependent rate power law is used for material modeling whose coefficients are arrived at through genetic algorithm (GA). Die profile of the tube extrusion process is optimized to produce microstructurally sound product at maximum production speed and minimum left out material in the die. The design problem is formulated as a nonlinear programming problem which is solved using GA. Selection of the processing parameters is carried out using dynamic material modeling (DMM). Using this approach tube extrusion process of γ iron is successfully designed.     

Recursive exponentially weighted PLS and its applications to adaptive control and prediction

A new and fast recursive, exponentially weighted PLS algorithm which provides greatly improved parameter estimates in most process situations is presented. The potential of this algorithm is illustrated with two process examples: (i) adaptive control of a two by two simulated multivariable continuous stirred tank reactor; and (ii) updating of a prediction model for an industrial flotation circuit. The performance of the recursive PLS algorithm is shown to be much better than that of the recursive least squares algorithm. The main advantage of the recursive PLS algorithm is that it does not suffer from the problems associated with correlated variables and short data windows. During adaptive control, it provided satisfactory control when the recursive least squares algorithm experienced difficulties (i.e., ‘blew’ up) due to the ill-conditioned covariance matrix, (X^TX)_t. For the industrial soft sensor application, the new algorithm provided much improved estimates of all ten response variables.     

A multicore solution to Block–Toeplitz linear systems of equations

There exist algorithms, also called “fast” algorithms, which exploit the special structure of Toeplitz matrices so that, e.g., allow to solve a linear system of equations in O(n ²) flops. However, some implementations of classical algorithms that do not use this structure (O(n ³) flops) highly reduce the time to solution when several cores are available. That is why it is necessary to work on “fast” algorithms so that they do not lose track of the benefits of new hardware/software. In this work, we propose a new approach to the Generalized Schur Algorithm, a very known algorithm for the solution of Toeplitz systems, to work on a Block–Toeplitz matrix. Our algorithm is based on matrix–matrix multiplications, thus allowing to exploit an efficient implementation of this operation if it exists. Our algorithm also makes use of the thread level parallelism featured by multicores to decrease execution time.     

The Ising genetic algorithm with Gibbs distribution sampling: Application to FIR filter design

In this paper the design of maximally flat linear phase finite impulse response (FIR) filters is considered. The problem with using the genetic algorithm (GA) in this kind of problems is the high cost of evaluating the fitness for each string in the population. The designing of optimum FIR filters under given constraints and required criteria includes exhaustive number of evaluations for filter coefficients, and the repetitive evaluations of objective functions that implicitly constitutes construction of the filter transfer functions. This problem is handled here with acceptable results utilizing Markov random fields (MRF's) approach. We establish a new theoretical approach here and we apply it on the design of FIR filters. This approach allows us to construct an explicit probabilistic model of the GA fitness function forming what is called the “Ising GA” that is based on sampling from a Gibbs distribution. Ising GA avoids the exhaustive design of suggested FIR filters (solutions) for every string of coefficients in every generation and replace this by a probabilistic model of fitness every gap (period) of iterations. Experimentations done with Ising GA of probabilistic fitness models are less costly than those done with standard GA and with high quality solutions.     

A novel rotation/scale invariant template matching algorithm using weighted adaptive lifting scheme transform

This paper presents a novel algorithm for detecting user-selected objects in given test images based on a new adaptive lifting scheme transform. Given an object as a template, we first select a set of coefficients as object features in the wavelet transform domain and then build an adaptive transform based on the selected features. The goal of the new adaptive transform is to vanish the selected features in the transform domain. After applying both non-adaptive and adaptive transforms to a given test image, the corresponding transform domain coefficients are compared for detecting the object of interest. In addition, the proposed detection algorithm is combined with the proper log-polar mapping model in the parametric template space to attain rotation/scale invariance property. Finally, we have verified the properties of our proposed algorithm with experimental results.     

Parsimonious additive models

A new method for function estimation and variable selection, specifically designed for additive models fitted by cubic splines is proposed. This new method involves regularizing additive models using the l₁-norm, which generalizes the lasso to the nonparametric setting. As in the linear case, it shrinks coefficients and produces some coefficients that are exactly zero. It gives parsimonious models, selects significant variables, and reveals nonlinearities in the effects of predictors. Two strategies for finding a parsimonious additive model solution are proposed. Both algorithms are based on a fixed point algorithm, combined with a singular value decomposition that considerably reduces computation. The empirical behavior of parsimonious additive models is compared to the adaptive backfitting BRUTO algorithm. The results allow to characterize the domains in which our approach is effective: it performs significantly better than BRUTO when model estimation is challenging. An implementation of this method is illustrated using real data from the Cophar 1 ANRS 102 trial. Parsimonious additive models are applied to predict the indinavir plasma concentration in HIV patients. Results suggest that this new method is a promising technique for the research and application areas.     

The Nonlinear Prefiltering and Difference of Estimates Approaches to Edge Detection: Applications of Stack Filters

The theory of stack filtering, which is a generalization of median filtering, is used in two different approaches to the detection of intensity edges in noisy images. The first approach is a generalization of median prefiltering: a stack filter or another median-type filter is used to smooth an image before a standard gradient estimator is applied. These prefiltering schemes retain the robustness of the median prefilter, but allow resolution of finer detail. The second approach, called the Difference of Estimates (DoE) approach, is a new formulation of a morphological scheme [Lee et al., IEEE Trans. Robotics Automat. RA-3, Apr. 1987, 142-156, Maragos and Ziff, IEEE Trans. Pattern Anal. Mach. Intell. 12(5), May 1990.] which has proven to be very sensitive to impulsive noise. In this approach, stack filters are applied to a noisy image to obtain local estimates of the dilated and eroded versions of the noise-free image. Thresholding the difference between these two estimates yields the edge map. We find, for example, that this approach yields results comparable to those obtained with the Canny operator for images with additive Gaussian noise, but works much better when the noise is impulsive. In both approaches, the stack filters employed are trained to be optimal on images and noise that are "typical" examples of the target image. The robustness of stack filters leads to good performance for the target image, even when the statistics of the noise and/or image vary from those used in training. This is verified with extensive simulations.     

Real-time content filtering for live broadcasts in TV terminals

In this paper, we propose a new real-time content filtering framework for live broadcasts in TV terminals. Content filtering in TV terminals is a necessary provision of personalized broadcasting services in that it enables a TV viewer to obtain desired scenes from multiple channel broadcasts. In this paper, a stable and reliable filtering structure and an algorithm for multiple inputs are proposed. Moreover, real-time filtering requirements such as frame sampling rate per channel, number of input channels, and buffer condition are analyzed to achieve real-time processing in terminals with limited computing power. Based on queueing theory, we model the system and resolve the filtering requirements. To verify the proposed system and analysis, a filtering algorithm for soccer videos is applied which is modified for real-time processing. Through analysis of visual features (e.g., dominant color and edge components) and detection of spatial objects (e.g., a score board), it recognizes a temporal pattern between successive video frames and filters desired scenes. Experiments on soccer videos have been performed and the results validate the effectiveness of the proposed approach and system.

Galois Action on Solutions of a Differential Equation

Consider a second-order differential equation of the form y″ + ay ′ + by = 0 with a, b ϵ Q(x). Kovacic's algorithm tries to compute a solution of the associated Riccati equation that is algebraic and of minimal degree over Q̄ (x). The coefficients of the monic irreducible polynomial of this solution are in C(x), where C is a finite algebraic extension of Q. In this paper we give a bound for the degree of the extension C ⊃ Q. Similar results are obtained for third-order differential equations.     

Explorations in evolutionary design of online auction market mechanisms

This paper describes the use of a genetic algorithm (GA) to find optimal parameter-values for trading agents that operate in virtual online auction ‘e-marketplaces’, where the rules of those marketplaces are also under simultaneous control of the GA. The aim is to use the GA to automatically design new mechanisms for agent-based e-marketplaces that are more efficient than online markets designed by (or populated by) humans. The space of possible auction-types explored by the GA includes the continuous double auction (CDA) mechanism (as used in most of the world’s financial exchanges), and also two purely one-sided mechanisms. Surprisingly, the GA did not always settle on the CDA as an optimum. Instead, novel hybrid auction mechanisms were evolved, which are unlike any existing market mechanisms. In this paper we show that, when the market supply and demand schedules undergo sudden ‘shock’ changes partway through the evaluation process, two-sided hybrid market mechanisms can evolve which may be unlike any human-designed auction and yet may also be significantly more efficient than any human designed market mechanism.     

A function space model for digital image sampling and its application in image reconstruction

A general mathematical model for digital signal processing, which is based onL^p function spaces, is introduced. This model is used to derive a new class of reconstruction filters for the reconstruction ofN-dimensional images which are not necessarily band-limited. A basic proposition in this work is that the best reconstruction algorithm will depend on the pre-sample filter (or point spread) function. The reconstruction filters described here are optimal in the sense that they result in a reconstructed image which is as close as possible, with respect to a given measure of fidelity, to the unsampled image. The filter is similar in form to the optimal filter derived byPeterson and Middleton (Inform. and Control5, 1962, 279–323) in their comprehensive paper on multidimensional sampling. However the reconstruction filter of Peterson and Middleton is optimal for random fields, whereas the filter described here is optimal for individual images. The optimal reconstruction filter has certain practical advantages over empirically derived reconstruction methods such as cubic interpolation. One of these advantages is that the method produces positive-valued images without loss of image resolution. The performance of the optimal reconstruction filter can be understood without reference to aliasing and truncation errors and is quantified in terms of a simple error metric.     

Enhancing the tracking capability of recursive least p-norm algorithm via adaptive gain factor

The main drawback of the recursive least p-norm (RLpN) adaptive-filtering algorithm is a poor tracking performance in the presence of abrupt changes in the model. In this paper, a new method to enhance tracking capability of the RLpN (ET-RLpN) algorithm is proposed, which uses the adaptive gain factor in the cross-correlation vector and the input-signal autocorrelation matrix to enhance tracking capability. Simulation results in system identification and echo cancellation applications are presented, which demonstrate that the ET-RLpN achieves improved tracking capability compared to the conventional RLpN and controlled adaptive combination of two RLpN filters (CAC-RLpN).     

A hybrid MapReduce-based <Emphasis Type="Italic">k</Emphasis>-means clustering using genetic algorithm for distributed datasets

Clustering a large volume of data in a distributed environment is a challenging issue. Data stored across multiple machines are huge in size, and solution space is large. Genetic algorithm deals effectively with larger solution space and provides better solution. In this paper, we proposed a novel clustering algorithm for distributed datasets, using combination of genetic algorithm (GA) with Mahalanobis distance and k-means clustering algorithm. The proposed algorithm is two phased; in phase 1, GA is applied in parallel on data chunks located across different machines. Mahalanobis distance is used as fitness value in GA, which considers covariance between the data points and thus provides a better representation of initial data. K-means with K-means\( ++ \) initialization is applied in phase 2 on intermediate output to get final result. The proposed algorithm is implemented on Hadoop framework, which is inherently designed to deal with distributed datasets in a fault-tolerant manner. Extensive experiments were conducted for multiple real-life and synthetic datasets to measure performance of our proposed algorithm. Results were compared with MapReduce-based algorithms, mrk-means, parallel k-means and scaling GA.     

Fast online algorithm for nonlinear support vector machines and other alike models

Paper presents a unique novel online learning algorithm for eight popular nonlinear (i.e., kernel), classifiers based on a classic stochastic gradient descent in primal domain. In particular, the online learning algorithm is derived for following classifiers: L1 and L2 support vector machines with both a quadratic regularizer w ^t w and the l ₁ regularizer |w|₁; regularized huberized hinge loss; regularized kernel logistic regression; regularized exponential loss with l ₁ regularizer |w|₁ and Least squares support vector machines. The online learning algorithm is aimed primarily for designing classifiers for large datasets. The novel learning model is accurate, fast and extremely simple (i.e., comprised of few coding lines only). Comparisons of performances of the proposed algorithm with the state of the art support vector machine algorithm on few real datasets are shown.     

Nonlinear system fault diagnosis based on adaptive estimation

An approach to fault diagnosis for a class of nonlinear systems is proposed in this paper. It is based on a new adaptive estimation algorithm for recursive estimation of the parameters related to faults. This algorithm is designed in a constructive manner through a nontrivial combination of a high gain observer and a recently developed linear adaptive observer, without resort to any linearization. Its global exponential convergence is ensured by an easy-to-check persistent excitation condition. A numerical example is presented for illustration.