Search

Abstract: The recent video coding standard H.264/AVC show extremely higher coding efficiency compare to any other previous standards. H.264/AVC can achieve over 50% of bit rate saving with same quality using the rate–distortion process, but it brings high computational complexity. In this paper, we propose an algorithm that can reduce the complexity of the codec by reducing the block mode decision process adaptively. Block mode decision process in H.264/AVC consists of inter mode decision process and intra mode decision process. We deal with reduction method for inter and intra mode decision. In this paper an efficient method is proposed to reduce the inter mode decision complexity using the direct prediction methods based on block correlation and adaptive rate distortion cost threshold for early stopping. The fast intra mode reduction algorithm based on inter mode information is also proposed to reduce the computational complexity. The experimental results show that the proposed algorithm can achieve up to 63.34–77.39% speed up ratio with a little PSNR loss. Increment in bit requirement is also not much noticeable. [Copyright &y& Elsevier]

Abstract: System identification consists in finding a model of an unknown system starting from a finite set of noise-corrupted data. A fundamental problem in this context is to asses the accuracy of the identified model. In this paper, the problem is investigated for the case of nonlinear systems within the Set Membership—Information Based Complexity framework of [M. Milanese, C. Novara, Set membership identification of nonlinear systems, Automatica 40(6) (2004) 957–975]. In that paper, a (locally) optimal algorithm has been derived, giving (locally) optimal models in nonlinear regression form. The corresponding (local) radius of information, providing the worst-case identification error, can be consequently used to measure the quality of the identified model. In the present paper, two algorithms are proposed for the computation of the local radius of information: The first provides the exact value but requires a computational complexity exponential in the dimension of the regressor space. The second is approximate but involves a polynomial (quadratic) complexity. [Copyright &y& Elsevier]

Abstract: In a previous paper, the author introduced a class of multivariate rational interpolants, which are called optimal Padé-type approximants (OPTA). The main goal of this paper is to extend classical results on convergence both in measure and in capacity of sequences of Padé approximants to the multivariate case using OPTA. To this end, we obtain some estimations of the size of multivariate polynomial lemniscates in terms of the Hausdorff content, which we also think are of some interest. [Copyright &y& Elsevier]

Abstract: In this paper, we present a novel approach to imaging sparse and focal neural current sources from MEG (magnetoencephalography) data. Using the framework of Tikhonov regularization theory, we introduce a new stabilizer that uses the concept of controlled support to incorporate a priori assumptions about the area occupied by focal sources. The paper discusses the underlying Tikhonov theory and its relationship to a Bayesian formulation which in turn allows us to interpret and better understand other related algorithms. [Copyright &y& Elsevier]

Abstract: Hough Transform (HT) is one of the most common methods for detecting shapes (lines, circles, etc.) in binary or edge images. Its advantage is its ability to detect discontinuous patterns in noisy images, but it requires a large amount of computing power. This paper presents a fast and enhanced version for computing the Incremental HT that was developed for digital device implementation. This algorithm does not require any Look Up Table or trigonometric calculations at run time. A number of the values generated in parallel is defined at the beginning of this algorithm. This algorithm leads to a significant reduction of the HT computation time and can be therefore used in real-time applications. This paper also provides some results obtained by this algorithm on several images. [Copyright &y& Elsevier]

The aim of this paper is to exploit the algorithms of paper Experimental Math. 8 (1999) in order to produce a new algebraic method for computing efficiently absolute Lagrange resolvent, a fundamental tool in constructive algebraic Galois theory. This article is composed of two parts.The main idea of the first part is to break up the calculation of absolute resolvent into smaller computations. Since a multi-resolvent is a factor of a resolvent, the whole resolvent may be computed by means of several multi-resolvents.The idea of the second part is that an irreducible polynomial over Z might be reducible over Z /pZ for certain integer p. So the first part can be applied and then, the Chinese remainder theorem allows to lift up the resolvent over Z. [Copyright &y& Elsevier]

A novel and efficient algorithm is presented in this paper to deal with DNS of turbulent reacting flows under the low-Mach-number assumption, with detailed chemistry and a quasi-spectral accuracy. The temporal integration of the equations relies on an operating-split strategy, where chemical reactions are solved implicitly with a stiff solver and the convection–diffusion operators are solved with a Runge–Kutta–Chebyshev method. The spatial discretisation is performed with high-order compact schemes, and a FFT based constant-coefficient spectral solver is employed to solve a variable-coefficient Poisson equation. The numerical implementation takes advantage of the 2DECOMP&FFT libraries developed by [1] , which are based on a pencil decomposition method of the domain and are proven to be computationally very efficient. An enhanced pressure-correction method is proposed to speed up the achievement of machine precision accuracy. It is demonstrated that a second-order accuracy is reached in time, while the spatial accuracy ranges from fourth-order to sixth-order depending on the set of imposed boundary conditions. The software developed to implement the present algorithm is called HOLOMAC , and its numerical efficiency opens the way to deal with DNS of reacting flows to understand complex turbulent and chemical phenomena in flames. [ABSTRACT FROM AUTHOR]

We consider the problem of counting (stable) equilibriums of an important family of algebraic differential equations modeling multistable biological regulatory systems. The problem can be solved, in principle, using real quantifier elimination algorithms, in particular real root classification algorithms. However, it is well known that they can handle only very small cases due to the enormous computing time requirements. In this paper, we present a special algorithm which is much more efficient than the general methods. Its efficiency comes from the exploitation of certain interesting structures of the family of differential equations. [ABSTRACT FROM AUTHOR]

Abstract: A subgraph T of a digraph D is an out-branching if T is an oriented spanning tree with only one vertex of in-degree zero (called the root). The vertices of T of out-degree zero are leaves. In the Directed Max Leaf problem, we wish to find the maximum number of leaves in an out-branching of a given digraph D (or, to report that D has no out-branching). In the Directed k-Leaf problem, we are given a digraph D and an integral parameter k, and we are to decide whether D has an out-branching with at least k leaves. Recently, Kneis et al. (2008) obtained an algorithm for Directed k-Leaf of running time . We describe a new algorithm for Directed k-Leaf of running time . This algorithms leads to an -time algorithm for solving Directed Max Leaf on a digraph of order n. The latter algorithm is the first algorithm of running time for Directed Max Leaf, where . In the Rooted Directed k-Leaf problem, apart from D and k, we are given a vertex r of D and we are to decide whether D has an out-branching rooted at r with at least k leaves. Very recently, Fernau et al. (2008) found an -size kernel for Rooted Directed k-Leaf. In this paper, we obtain an kernel for Rooted Directed k-Leaf restricted to acyclic digraphs. [Copyright &y& Elsevier]

Abstract: It is no longer believed that DNA computing will outperform digital computers when it comes to the computation of intractable problems. In this paper, we emphasise the in silico implementation of DNA-inspired algorithms as the only way to compete with other algorithms for solving NP-complete problems. For this, we provide sticker algorithms for some of the most representative NP-complete graph problems. The simple data structures and bit-vertical operations make them suitable for some parallel architectures. The parallel algorithms might solve either moderate-size problems in an exact manner or, when combined with a heuristic, large problems in polynomial time. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to study multidimensional continued fraction algorithm over the field of formal power series. In the case of the Brun algorithm by using its homogenous version, we prove that it converges. [Copyright &y& Elsevier]

Abstract: In this paper we analyze O''Hara''s partition bijection. We present three type of results. First, we show that O''Hara''s bijection can be viewed geometrically as a certain scissor congruence type result. Second, we obtain a number of new complexity bounds, proving that O''Hara''s bijection is efficient in several special cases and mildly exponential in general. Finally, we prove that for identities with finite support, the map of the O''Hara''s bijection can be computed in polynomial time, i.e. much more efficiently than by O''Hara''s construction. [Copyright &y& Elsevier]

Abstract: Leonard and Pellikaan developed the qth power algorithm to compute module bases for the integral closure of the polynomial ring in a class of function fields. In this paper, their algorithm is adapted to efficiently obtain an -basis for a class of Riemann–Roch spaces without having to compute the entire integral closure. This reformulation allows one to determine the complexity of the algorithm. Further, we obtain a simple characterization of the integral closure. [Copyright &y& Elsevier]

Abstract: A vertex ranking of an undirected graph G is a labeling of the vertices of G with integers such that every path connecting two vertices with the same label i contains an intermediate vertex with label . A vertex ranking of G is called optimal if it uses the minimum number of distinct labels among all possible vertex rankings. The problem of finding an optimal vertex ranking for general graphs is NP-hard, and NP-hard even for chordal graphs which form a superclass of block graphs. In this paper, we present the first polynomial algorithm which runs in time for finding an optimal vertex ranking of a block graph G, where n and denote the number of vertices and the maximum degree of G, respectively. [Copyright &y& Elsevier]

Abstract: This paper presents an algorithm for fast sorting of large lists using modern GPUs. The method achieves high speed by efficiently utilizing the parallelism of the GPU throughout the whole algorithm. Initially, GPU-based bucketsort or quicksort splits the list into enough sublists then to be sorted in parallel using merge-sort. The algorithm is of complexity , and for lists of 8 M elements and using a single Geforce 8800 GTS-512, it is 2.5 times as fast as the bitonic sort algorithms, with standard complexity of , which for a long time was considered to be the fastest for GPU sorting. It is 6 times faster than single CPU quicksort, and 10% faster than the recent GPU-based radix sort. Finally, the algorithm is further parallelized to utilize two graphics cards, resulting in yet another 1.8 times speedup. [Copyright &y& Elsevier]

Abstract: The fast multipole method (FMM) and smooth particle mesh Ewald (SPME) are well known fast algorithms to evaluate long range electrostatic interactions in molecular dynamics and other fields. FMM is a multi-scale method which reduces the computation cost by approximating the potential due to a group of particles at a large distance using few multipole functions. This algorithm scales like for N particles. SPME algorithm is an method which is based on an interpolation of the Fourier space part of the Ewald sum and evaluating the resulting convolutions using fast Fourier transform (FFT). Those algorithms suffer from relatively poor efficiency on large parallel machines especially for mid-size problems around hundreds of thousands of atoms. A variation of the FMM, called PWA, based on plane wave expansions is presented in this paper. A new parallelization strategy for PWA, which takes advantage of the specific form of this expansion, is described. Its parallel efficiency is compared with SPME through detail time measurements on two different computer clusters. [Copyright &y& Elsevier]

Abstract: The Singular Value Decomposition (SVD) is a vital problem that finds a place in numerous application domains in science and engineering. As an example, SVDs are used in processing voluminous datasets. Many sequential and parallel algorithms have been proposed to compute SVDs. The best known sequential algorithms take cubic time. This amount of time may not be acceptable especially when the data size is large. Thus parallel algorithms are desirable. In this paper, we present a novel technique for the parallel computation of SVDs. This technique yields impressive speedups. We discuss implementation of our technique on parallel models of computing such as the mesh and the PRAM. We also present an experimental evaluation of our technique. [Copyright &y& Elsevier]

Abstract: The spatiotemporal dynamics of cortical oscillations across human brain regions remain poorly understood because of a lack of adequately validated methods for reconstructing such activity from noninvasive electrophysiological data. In this paper, we present a novel adaptive spatial filtering algorithm optimized for robust source time–frequency reconstruction from magnetoencephalography (MEG) and electroencephalography (EEG) data. The efficacy of the method is demonstrated with simulated sources and is also applied to real MEG data from a self-paced finger movement task. The algorithm reliably reveals modulations both in the beta band (12–30 Hz) and high gamma band (65–90 Hz) in sensorimotor cortex. The performance is validated by both across-subjects statistical comparisons and by intracranial electrocorticography (ECoG) data from two epilepsy patients. Interestingly, we also reliably observed high frequency activity (30–300 Hz) in the cerebellum, although with variable locations and frequencies across subjects. The proposed algorithm is highly parallelizable and runs efficiently on modern high-performance computing clusters. This method enables the ultimate promise of MEG and EEG for five-dimensional imaging of space, time, and frequency activity in the brain and renders it applicable for widespread studies of human cortical dynamics during cognition. [Copyright &y& Elsevier]

Abstract: Two kinds of decompositions of a -module are introduced in this article, a Loewy-decomposition and a primary decomposition. Algorithms are described which allow to construct decompositions for finite-dimensional -modules. Both decompositions rely on the concept of the -module of relative syzygies introduced in the paper. Furthermore an algorithm is described which tests whether two given -modules are isomorphic under the relevant type of transformations. [Copyright &y& Elsevier]

This paper presents improved algorithms for the following problem: given an unweighted directed graph and a sequence of on-line shortest-path/reachability queries interspersed with edge-deletions, develop a data-structure that can answer each query in optimal time, and can be updated efficiently after each edge-deletion. The central idea underlying our algorithms is a scheme for implicitly storing all-pairs reachability/shortest-path information, and an efficient way to maintain this information. Our algorithms are randomized and have one-sided inverse polynomial error for query. [Copyright &y& Elsevier]

Abstract: For a canonical threefold X, we know for a sufficiently large n. When , there are few known results about the integer n. This paper introduces an algorithm for computing plurigenera. Furthermore, when is small, especially 1 and 2, plurigenera are computed. This produces for and for when . Also, for and for with 8 possible exceptional cases when . [Copyright &y& Elsevier]

Abstract: In this paper, we introduce and study a new system of nonlinear A-monotone multivalued variational inclusions in Hilbert spaces. By using the concept and properties of A-monotone mappings, and the resolvent operator technique associated with A-monotone mappings due to Verma, we construct a new iterative algorithm for solving this system of nonlinear multivalued variational inclusions associated with A-monotone mappings in Hilbert spaces. We also prove the existence of solutions for the nonlinear multivalued variational inclusions and the convergence of iterative sequences generated by the algorithm. Our results improve and generalize many known corresponding results. [Copyright &y& Elsevier]

Abstract: Video summarization can provide a fine representation of the content of video stream and reduce a large amount of data involved in video indexing, browsing, and retrieval. Moreover, Key frame selection is an important step in the research of content-based video analysis and retrieval. Although there exist a variety of methods for key frame selection, they are heuristic and closed systems, which cannot dynamically generate video summary with user’s preference. In this paper, an M-estimator and epipolar line distance constraint camera motion estimation algorithm is introduced as camera parameters is an important motion feature for key frame selection, and Broyden-Fletcher-Goldfarb-Shanno (BFGS) method is applied to optimize estimated parameters. Moreover, since Interactive Computing is a novel-computing model that represents the transition of algorithm to interaction, an interactive model of key frame selection (IKFS) is presented as a result of improving the model of key frame selection (KFS). The model of KFS and IKFS are proved to satisfy the criterion of induction and coinduction, respectively. Experimental results show that the processing scheme generates flexible and desirable summarizations whose distortion rate is lower than current method. Above all, IKFS is an extension to KFS. [Copyright &y& Elsevier]

Abstract: In 1992, V. Weispfenning proved the existence of Comprehensive Gröbner Bases (CGB) and gave an algorithm for computing one. That algorithm was not very efficient and not canonical. Using his suggestions, A. Montes obtained in 2002 a more efficient algorithm (DISPGB) for Discussing Parametric Gröbner Bases. Inspired by its philosophy, V. Weispfenning defined, in 2002, how to obtain a Canonical Comprehensive Gröbner Basis (CCGB) for parametric polynomial ideals, and provided a constructive method. In this paper we use Weispfenning’s CCGB ideas to make substantial improvements on Montes’ DISPGB algorithm. It now includes rewriting of the discussion tree using the discriminant ideal and provides a compact and effective discussion. We also describe the new algorithms in the DPGB library containing the improved DISPGB as well as new routines for checking whether a given basis is a CGB or not, and for obtaining a CGB. Examples and tests are also provided. [Copyright &y& Elsevier]

Abstract: In this paper a new algorithm for computing the intersection of two rational ruled surfaces, given in parametric/parametric or implicit/parametric form, is presented. This problem can be considered as a quantifier elimination problem over the reals with an additional geometric flavor which is one of the central themes in V. Weispfenning research. After the implicitization of one of the surfaces, the intersection problem is reduced to finding the zero set of a bivariate equation which represents the parameter values of the intersection curve, as a subset of the other surface. The algorithm, which involves both symbolic and numerical computations, determines the topology of the intersection curve as an intermediate step and eliminates extraneous solutions that might arise in the implicitization process. [Copyright &y& Elsevier]

Abstract: Recent developments in stream ciphers point towards an interest in word-based or vectorized stream ciphers. Such stream ciphers suggest the study of the joint linear complexity of multisequences. In this paper, using the first author''s multisequence linear feedback shift-register synthesis algorithm based on a lattice basis reduction algorithm in function fields, we present a method to determine the value of , the number of m-fold multisequences of length n over a finite field with nth joint linear complexity L. Furthermore, a closed-form expression for and formulas for the expected value of the joint linear complexity and its variance are given when . [Copyright &y& Elsevier]

Abstract: In this paper we describe an algorithm that takes as input a description of a semi-algebraic set , defined by a Boolean formula with atoms of the form for , and outputs the first Betti numbers of , . The complexity of the algorithm is , where and , which is singly exponential in for any fixed constant. Previously, singly exponential time algorithms were known only for computing the Euler–Poincaré characteristic, the zeroth and the first Betti numbers. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a three-state alternator algorithm for uniform ring with n processors, where . The proposed algorithm is a randomized algorithm and operates correctly for synchronous mode. An alternator is a self-stabilization system that satisfies the following properties. (1) The safety property: if a processor executes the critical step, no neighbor executes the critical step at the same computing phase. (2) The liveness property: along any infinite computing phases, every processor executes the critical step infinitely often. An alternator is 1-fair if between any two consecutive critical steps of a processor, all other processors execute the critical step exactly once. The proposed alternator is 1-fair. It allows each processor to execute the critical step every three phases. The proposed algorithm has the snap property in the sense that the system satisfies the safety property of the alternator even if some transient fault occurs. The worst-case stabilization time of the algorithm is an expected number of two phases plus a deterministic number of at most phases. [Copyright &y& Elsevier]

Abstract: This paper describes a new blind deconvolution method implemented by means of an evolutionary algorithm (EA). The EA is designed following a multi-objective optimisation problem approach. The last generation of the EA is assessed by different quality metrics for determining the solution that provides the best performance. It is shown that different restored images can be obtained from a given testing image. The selection of the best result is accomplished though the use of quality metrics. However, the existence of many quality metrics entails a difficult problem for determining the best output. Here, we present a new robust quality metric, based on the use of the local space-frequency information extracted from the Wigner distribution. We empirically compared its performance with other well-known perceptual metrics. In addition to that, a fusion procedure between all candidate restored output images from the EA is also proposed as an alternative to the selection process. The fusion method is also based on the use of this new measure recently developed by the authors with excellent experimental results. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a framework to carry out supervised classification of images containing both textured and non textured areas. Our approach is based on active contours. Using a decomposition algorithm inspired by the recent work of Y. Meyer, we can get two channels from the original image to classify: one containing the geometrical information, and the other the texture. Using the logic framework by Chan and Sandberg, we can then combine the information from both channels in a user definable way. Thus, we design a classification algorithm in which the different classes are characterized both from geometrical and textured features. Since natural images are combinations of both textured and non textured patterns, this integrative approach enlarges the scope of possible applications for active contours-based classification algorithms. [Copyright &y& Elsevier]

Abstract: In image restoration, the region of support of the point spread function is often much smaller than the size of the observed degraded image and this property is utilized in many image deconvolution algorithms. For the constrained total least squares (CTLS)-based algorithm, it means that the solution of the CTLS algorithm should retain the block-circulant and sparse structure of the degradation matrix simultaneously. In real image restoration problems, the CTLS method often involves large-scale computation and is often solved using Mesarovic et al.’s algorithm. However, there is concern about whether their algorithm preserves the sparse structure of the degradation matrix. In this paper, we prove that by imposing an extra constraint, the sparse structure in their algorithm can be preserved. Then, we use the projection onto convex sets algorithm to find a solution to this extended formulation. Our experimental study indicates that the proposed method performs competitively, and often better, in terms of visual and objective evaluations. [Copyright &y& Elsevier]

Abstract: Recently, three learning algorithms, namely non-negative matrix factorization (NMF), local non-negative matrix factorization (LNMF), and discriminant non-negative matrix factorization (DNMF) have been proposed to produce sparse image representations. However, when their input is a database of human facial images, they decompose the images into sparse representations with quite different degree of sparseness. Within a continuum of sparseness ranging from holistic to local image representation, the first algorithm rather tends towards the first extreme, while the second algorithm produces a local representation. The third algorithm provides an image representation that is in between these two extremes. These algorithms decompose the facial images in the database into basis images and their corresponding coefficients. The basis images are learned by the algorithm when human face images are given as input. By analogy to neurophysiology, the basis images could be associated with the receptive fields of neuronal cells involved in encoding human faces. Taken from this point of view, the paper presents an analysis of these three representations in connection to the receptive field parameters such as spatial frequency, frequency orientation, position, length, width, aspect ratio, etc. By analyzing the tiling properties of these bases we can have an insight of how suitable these algorithms are to resemble biological visual perception systems. [Copyright &y& Elsevier]

Abstract: This paper describes a complex scene rendering system that it can comprehensively render larger and more complex 3D scenes in a form of output-sensitive way by means of using distributed visibility culling technique. The process of the proposed visibility calculations is explicitly divided into two distinct phases, one is preprocessing stage, and the other is on-the-fly stage. At the preprocessing stage, the whole scene is partitioned into numerous regions, namely spatial cells, by adopting BSP tree algorithm. Accordingly, the complexity weight of each cell is estimated in advance depending on the number of geometric polygons within the cell. Afterwards we find out possible occluders in each cell for accelerating the real-time occlusion culling at run time. Moreover, instant visibility is taken into account to quickly calculate the tight potentially visible set (PVS) which is valid for several frames during the on-the-fly phase. As dynamic load balancing algorithm is concerned, we employ the cell arrangement mechanism to dynamically assign a specific amount of service demand to each calculating machine. The amount of service demand is estimated when a calculating machine is dynamically inserted into or removed from the distributed calculating cluster. Finally, after the drawing machines gather the PVS results from every calculating machine, they render the scene for users to view it on the next frames. From the simulation results, we can see that the proposed real-time walkthrough environment takes good advantage of the distributed visibility culling technique for displaying large, complex 3D scenes in real time and gets rid of a troublesome computation delay problem. [Copyright &y& Elsevier]

Abstract: This paper presents a computationally efficient, two-dimensional, feature point tracking algorithm for the automated detection and quantitative analysis of particle trajectories as recorded by video imaging in cell biology. The tracking process requires no a priori mathematical modeling of the motion, it is self-initializing, it discriminates spurious detections, and it can handle temporary occlusion as well as particle appearance and disappearance from the image region. The efficiency of the algorithm is validated on synthetic video data where it is compared to existing methods and its accuracy and precision are assessed for a wide range of signal-to-noise ratios. The algorithm is well suited for video imaging in cell biology relying on low-intensity fluorescence microscopy. Its applicability is demonstrated in three case studies involving transport of low-density lipoproteins in endosomes, motion of fluorescently labeled Adenovirus-2 particles along microtubules, and tracking of quantum dots on the plasma membrane of live cells. The present automated tracking process enables the quantification of dispersive processes in cell biology using techniques such as moment scaling spectra. [Copyright &y& Elsevier]

Abstract: In this paper, feedforward active noise control (ANC) using a neural network (NN) based on filtered-error back-propagation (BP) algorithm is considered. The filtered-error BP NN (FEBPNN) algorithm is first derived, and the difference between the FEBPNN algorithm and the filtered-X BP NN (FXBPNN) algorithm is given to show that the FEBPNN algorithm offers computational advantage over the FXBPNN algorithm. Computer simulations are carried out to compare the FEBPNN algorithm with the filtered-X least mean square (FXLMS) algorithm and the FXBPNN algorithm. The controllers based on the FEBPNN algorithm and the FXLMS algorithm are implemented on a Texas Instruments digital signal processor (DSP) TMS320VC33. The simulations and the experimental verification tests show that the FEBPNN algorithm performs as well as the FXLMS algorithm for a linear control problem, and better for a nonlinear control problem, at the same time, the simulations and the experimental verification tests also show that the convergence rate of the FEBPNN is acceptable, and the FEBPNN has better tracking ability under changes of the primal signal, the primary path and the secondary path. The experiments also lead to the conclusion that more work is required to improve the predictability and consistency of the performance of the NN controller based on the FEBPNN algorithm. [Copyright &y& Elsevier]

Abstract: A reciprocal polynomial is such that and if then . The non-reciprocal part of a monic polynomial is divided by the product of its irreducible monic reciprocal factors (to their multiplicity). This paper presents an algorithm for testing the irreducibility of the non-reciprocal part of a 0,1-polynomial (a polynomial having each coefficient either 0 or 1). The algorithm runs in time where r is the number of non-zero terms of the input polynomial and n is its degree. Thus, the algorithm efficiently handles lacunary (or sparse) 0,1-polynomials. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new method for brightness elimination in chromatic images by means of the extension of the morphological reconstruction for colour images. We use the HSI colour space for morphological processing, after solving certain inconveniences present in this colour model. We investigate the connected filters of the mathematical morphology and, in particular, the so-called filters by reconstruction. These filters are formally defined for colour images. The power of the morphological reconstruction for brightness elimination in colour images is presented. We also describe a new algorithm to control the over-simplification of images and to reduce the high processing cost of the geodesic operations. Examples of its application are shown. The new method proposed here achieves good results, which are similar to those obtained from other techniques, yet does not require either costly multiple-view systems or stereo images. [Copyright &y& Elsevier]

Abstract: In machine vision applications that involve comparing two images, it is necessary to match the capture conditions, which can affect their graylevels. Illumination and exposure are two important causes for lighting variation that we should compensate for in the resulting images. A standard technique for this purpose is to map one of the images to achieve the smallest mean square error (MSE) between the two. However, applications in defect detection for manufacturing processes are more challenging, because the existence of defects would affect the mapping significantly. In this paper, we present a robust method that is more tolerant to defects, and discuss its formulation as a linear programming to achieve fast implementations. This algorithm is also flexible and capable of incorporating further constraints, such as ensuring non-negativity of the pixel values. [Copyright &y& Elsevier]

Recently external memory graph problems have received considerable attention because massive graphs arise naturally in many applications involving massive data sets. Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open.The results in this paper fall in two main classes. First we develop an improved algorithm for the problem of computing a minimum spanning tree (MST) of a general undirected graph. Second we show that on planar undirected graphs the problems of computing a multi-way graph separation and single source shortest paths (SSSP) can be reduced I/O-efficiently to planar breadth-first search (BFS). Since BFS can be trivially reduced to SSSP by assigning all edges weight one, it follows that in external memory planar BFS, SSSP, and multi-way separation are equivalent. That is, if any of these problems can be solved I/O-efficiently, then all of them can be solved I/O-efficiently in the same bound. Our planar graph results have subsequently been used to obtain I/O-efficient algorithms for all fundamental problems on planar undirected graphs. [Copyright &y& Elsevier]

Abstract: This paper presents a real-time implementation of Motion-JPEG2000 encoder using a fixed-point DSP chip. Among several modules in JPEG2000 encoder, the lifting algorithm for discrete wavelet transform (DWT) and the embedded block coding with optimized truncation (EBCOT) comprise more than 85% of the encoding complexity. Thus, it is very important to design and optimize these two modules in order to increase the performance of the hardware implementation. First we propose an overlapped block transferring (OBT) method that can significantly improve the performance of the lifting algorithm for DWT by increasing the cache hit rate. We show that the execution time of the lifting scheme can be further reduced by programming the DSP software using the single instruction multiple data (SIMD) instructions and the super scalar pipeline structure. Moreover, we introduce a parallel-pass method for fast implementation of EBCOT. This method reduces the processing time of EBCOT by processing the three coding passes of the same bit-plane in parallel. Experimental results show that our developed Motion-JPEG2000 DSP system meets the common requirement of the real-time video coding [30 frames/s (fps)] and is proven to be a practical and efficient DSP solution. [Copyright &y& Elsevier]

This paper discusses the application of Bayes's theorem to those cases where the true state of the world is not known with certainty. An algorithm is proposed that relaxes the requirement of Bayes's theorem that the true data state be known with certainty by postulating a true but unobservable elementary event, ω, which gives rise to posterior probabilities which reflect the uncertainty of the data. A derivation is presented for the calculation of Bayesian posterior probabilities which uses as its input these probabilities, rather than the true event, o, which is assumed to be unavailable. Suggestions are made as to the application of this modification of Bayes's theorem to cascaded inference processes. [ABSTRACT FROM AUTHOR]