A recursive, numerically stable, and efficient simulation algorithm for serial robots with flexible links

A methodology for the formulation of dynamic equations of motion of a serial flexible-link manipulator using the decoupled natural orthogonal complement (DeNOC) matrices, introduced elsewhere for rigid bodies, is presented in this paper. First, the Euler Lagrange (EL) equations of motion of the system are written. Then using the equivalence of EL and Newton–Euler (NE) equations, and the DeNOC matrices associated with the velocity constraints of the connecting bodies, the analytical and recursive expressions for the matrices and vectors appearing in the independent dynamic equations of motion are obtained. The analytical expressions allow one to obtain a recursive forward dynamics algorithm not only for rigid body manipulators, as reported earlier, but also for the flexible body manipulators. The proposed simulation algorithm for the flexible link robots is shown to be computationally more efficient and numerically more stable than other algorithms present in the literature. Simulations, using the proposed algorithm, for a two link arm with each link flexible and a Space Shuttle Remote Manipulator System (SSRMS) are presented. Numerical stability aspects of the algorithms are investigated using various criteria, namely, the zero eigenvalue phenomenon, energy drift method, etc. Numerical example of a SSRMS is taken up to show the efficiency and stability of the proposed algorithm. Physical interpretations of many terms associated with dynamic equations of flexible links, namely, the mass matrix of a composite flexible body, inertia wrench of a flexible link, etc. are also presented. The work has been carried out in the Dept. of Mechanical Engineering, Indian Institute of Technology Delhi, New Delhi 110016, India.     

Interacting and Annealing Particle Filters: Mathematics and a Recipe for Applications

Interacting and annealing are two powerful strategies that are applied in different areas of stochastic modelling and data analysis. Interacting particle systems approximate a distribution of interest by a finite number of particles where the particles interact between the time steps. In computer vision, they are commonly known as particle filters. Simulated annealing, on the other hand, is a global optimization method derived from statistical mechanics. A recent heuristic approach to fuse these two techniques for motion capturing has become known as annealed particle filter. In order to analyze these techniques, we rigorously derive in this paper two algorithms with annealing properties based on the mathematical theory of interacting particle systems. Convergence results and sufficient parameter restrictions enable us to point out limitations of the annealed particle filter. Moreover, we evaluate the impact of the parameters on the performance in various experiments, including the tracking of articulated bodies from noisy measurements. Our results provide a general guidance on suitable parameter choices for different applications.

Lower Bounds for Kernelizations and Other Preprocessing Procedures

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR” and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with |y|=k ^O(1)⋅|x|^1−ε (here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of preprocessing procedures, namely the various notions of kernelizations, self-reductions and compressions.     

Branch and Recharge: Exact Algorithms for Generalized Domination

In this paper we present branching algorithms for infinite classes of problems.     

Synthetic speech in foreign language learning: an evaluation by learners

Can synthetic speech be utilized in foreign language learning as natural speech? In this paper, we evaluated synthetic speech from the viewpoint of learners in order to find out an answer. The results pointed out that learners do not recognize remarkable differences between synthetic voices and natural voices for the words with short vowels and long vowels when they try to understand the meanings of the sounds. The data explicates that synthetic voice utterances of sentences are easier to understand and more acceptable by learners compared to synthetic voice utterances of words. In addition, the ratings on both synthetic voices and natural voices strongly depend upon the learners’ listening comprehension abilities. We conclude that some synthetic speech with specific pronunciations of vowels may be suitable for listening materials and suggest that evaluating TTS systems by comparing synthetic speech with natural speech and building a lexical database of synthetic speech that closely approximates natural speech will be helpful for teachers to readily use many existing CALL tools.     

Discretization for naive-Bayes learning: managing discretization bias and variance

Quantitative attributes are usually discretized in Naive-Bayes learning. We establish simple conditions under which discretization is equivalent to use of the true probability density function during naive-Bayes learning. The use of different discretization techniques can be expected to affect the classification bias and variance of generated naive-Bayes classifiers, effects we name discretization bias and variance. We argue that by properly managing discretization bias and variance, we can effectively reduce naive-Bayes classification error. In particular, we supply insights into managing discretization bias and variance by adjusting the number of intervals and the number of training instances contained in each interval. We accordingly propose proportional discretization and fixed frequency discretization, two efficient unsupervised discretization methods that are able to effectively manage discretization bias and variance. We evaluate our new techniques against four key discretization methods for naive-Bayes classifiers. The experimental results support our theoretical analyses by showing that with statistically significant frequency, naive-Bayes classifiers trained on data discretized by our new methods are able to achieve lower classification error than those trained on data discretized by current established discretization methods.     

Local and Nonlocal Discrete Regularization on Weighted Graphs for Image and Mesh Processing

We propose a discrete regularization framework on weighted graphs of arbitrary topology, which unifies local and nonlocal processing of images, meshes, and more generally discrete data. The approach considers the problem as a variational one, which consists in minimizing a weighted sum of two energy terms: a regularization one that uses the discrete p-Dirichlet form, and an approximation one. The proposed model is parametrized by the degree p of regularity, by the graph structure and by the weight function. The minimization solution leads to a family of simple linear and nonlinear processing methods. In particular, this family includes the exact expression or the discrete version of several neighborhood filters, such as the bilateral and the nonlocal means filter. In the context of images, local and nonlocal regularizations, based on the total variation models, are the continuous analog of the proposed model. Indirectly and naturally, it provides a discrete extension of these regularization methods for any discrete data or functions.     

Software transactional memories: an approach for multicore programming

The recent advance of multicore architectures and the deployment of multiprocessors as the mainstream computing platforms have given rise to a new concurrent programming impetus. Software transactional memories (STM) are one of the most promising approaches to take up this challenge. The aim of a STM system is to discharge the application programmer from the management of synchronization when he/she has to write multiprocess programs. His/her task is to decompose his/her program into a set of sequential tasks that access shared objects, and to decompose each task in atomic units of computation. The management of the required synchronization is ensured by the associated STM system. This paper presents two existing STM systems, and a new one based on time-window mechanism. The paper, which focuses mainly on STM principles, has an introductory and survey flavor.     

A framework for the control of stable aperiodic walking in underactuated planar bipeds

This paper presents a new definition of stable walking for point-footed planar bipedal robots that is not necessarily periodic. The inspiration for the definition is the commonly-held notion of stable walking: the biped does not fall. Somewhat more formally, biped walking is shown to be stable if the trajectory of each step places the robot in a state at the end of the step for which a controller is known to exist that generates a trajectory for the next step with this same property. To make the definition useful, an algorithm is given to verify if a given controller induces stable walking in the given sense. Also given is a framework to synthesize controllers that induce stable walking. The results are illustrated on a 5-link biped ERNIE in simulation and experiment.     

Vesicles and Amoebae: On Globally Constrained Shape Deformation

Modeling the deformation of shapes under constraints on both perimeter and area is a challenging task due to the highly nontrivial interaction between the need for flexible local rules for manipulating the boundary and the global constraints. We propose several methods to address this problem and generate “random walks” in the space of shapes obeying quite general possibly time varying constraints on their perimeter and area. Design of perimeter and area preserving deformations are an interesting and useful special case of this problem. The resulting deformation models are employed in annealing processes that evolve original shapes toward shapes that are optimal in terms of boundary bending-energy or other functionals. Furthermore, such models may find applications in the analysis of sequences of real images of deforming objects obeying global constraints as building blocks for registration and tracking algorithms.     

Linear Regression and Adaptive Appearance Models for Fast Simultaneous Modelling and Tracking

This work proposes an approach to tracking by regression that uses no hard-coded models and no offline learning stage. The Linear Predictor (LP) tracker has been shown to be highly computationally efficient, resulting in fast tracking. Regression tracking techniques tend to require offline learning to learn suitable regression functions. This work removes the need for offline learning and therefore increases the applicability of the technique. The online-LP tracker can simply be seeded with an initial target location, akin to the ubiquitous Lucas-Kanade algorithm that tracks by registering an image template via minimisation.     

Primal Discontinuous Galerkin Methods for Time-Dependent Coupled Surface and Subsurface Flow

This paper introduces and analyzes a numerical method based on discontinuous finite element methods for solving the two-dimensional coupled problem of time-dependent incompressible Navier-Stokes equations with the Darcy equations through Beaver-Joseph-Saffman’s condition on the interface. The proposed method employs Crank-Nicolson discretization in time (which requires one step of a first order scheme namely backward Euler) and primal DG method in space. With the correct assumption on the first time step optimal error estimates are obtained that are high order in space and second order in time.     

Parallel spatiotemporal autocorrelation and visualization system for large-scale remotely sensed images

Current studies on large-scale remotely sensed images are of great national importance for monitoring and evaluating global climate and ecological changes. In particular, real time distributed high-performance visualization and computation have become indispensable research components in facilitating the extraction of remotely sensed image textures to enable mining spatiotemporal patterns and dynamics of landscapes from massive geo-digital information collected from satellites. Remotely sensed images are usually highly correlated with rich landscape features. By exploiting the structures of these images and extracting their textures, fundamental insights of the landscape can be derived. Furthermore, the interdisciplinary collaboration on the remotely sensed image analysis demands multifarious expertise in a wide spectrum of fields including geography, computer science, and engineering.     

Model and procedure for performance and availability-wise parallel warehouses

Consider data warehouses as large data repositories queried for analysis and data mining in a variety of application contexts. A query over such data may take a large amount of time to be processed in a regular PC. Consider partitioning the data into a set of PCs (nodes), with either a parallel database server or any database server at each node and an engine-independent middleware. Nodes and network may even not be fully dedicated to the data warehouse. In such a scenario, care must be taken for handling processing heterogeneity and availability, so we study and propose efficient solutions for this. We concentrate on three main contributions: a performance-wise index, measuring relative performance; a replication-degree; a flexible chunk-wise organization with on-demand processing. These contributions extend the previous work on de-clustering and replication and are generic in the sense that they can be applied in very different contexts and with different data partitioning approaches. We evaluate their merits with a prototype implementation of the system.     

Faster Combinatorial Algorithms for Determinant and Pfaffian

Computation of a determinant is a very classical problem. The related concept is a Pfaffian of a matrix defined for skew-symmetric matrices. The classical algorithm for computing the determinant is Gaussian elimination. It needs O(n ³) additions, subtractions, multiplications and divisions. The algorithms of Mahajan and Vinay compute determinant and Pfaffian in a completely non-classical and combinatorial way, by reducing these problems to summation of paths in some acyclic graphs. The attractive feature of these algorithms is that they are division-free. We present a novel algebraic view of these algorithms: a relation to a pseudo-polynomial dynamic-programming algorithm for the knapsack problem. The main phase of Mahajan-Vinay algorithm can be interpreted as a computation of an algebraic version of the knapsack problem, which is an alternative to the graph-theoretic approach used in the original algorithm. Our main results show how to implement Mahajan-Vinay algorithms without divisions, in time $\tilde{O}(n^{3.03})$ using the fast matrix multiplication algorithm.     

Geodesic Matting: A Framework for Fast Interactive Image and Video Segmentation and Matting

An interactive framework for soft segmentation and matting of natural images and videos is presented in this paper. The proposed technique is based on the optimal, linear time, computation of weighted geodesic distances to user-provided scribbles, from which the whole data is automatically segmented. The weights are based on spatial and/or temporal gradients, considering the statistics of the pixels scribbled by the user, without explicit optical flow or any advanced and often computationally expensive feature detectors. These could be naturally added to the proposed framework as well if desired, in the form of weights in the geodesic distances. An automatic localized refinement step follows this fast segmentation in order to further improve the results and accurately compute the corresponding matte function. Additional constraints into the distance definition permit to efficiently handle occlusions such as people or objects crossing each other in a video sequence. The presentation of the framework is complemented with numerous and diverse examples, including extraction of moving foreground from dynamic background in video, natural and 3D medical images, and comparisons with the recent literature.     

Projective Splines and Estimators for Planar Curves

Recognizing shapes in multiview imaging is still a challenging task, which usually relies on geometrical invariants estimations. However, very few geometric estimators that achieve projective invariance have been devised. This paper proposes a projective length and a projective curvature estimators for plane curves, when the curves are represented by points together with their tangent directions. In this context, the estimations can be performed with only three point-tangent samples for the projective length and five samples for the projective curvature. The proposed length and curvature estimator are based on projective splines built by fitting logarithmic spirals to the point-tangent samples. They are projective invariant and convergent.     

Orientation-Matching Minimization for Image Denoising and Inpainting

In this paper, we propose an orientation-matching functional minimization for image denoising and image inpainting. Following the two-step TV-Stokes algorithm (Rahman et al. in Scale space and variational methods in computer vision, pp. 473–482, Springer, Heidelberg, 2007; Tai et al. in Image processing based on partial differential equations, pp. 3–22, Springer, Heidelberg, 2006; Bertalmio et al. in Proc. conf. comp. vision pattern rec., pp. 355–362, 2001), a regularized tangential vector field with zero divergence condition is first obtained. Then a novel approach to reconstruct the image is proposed. Instead of finding an image that fits the regularized normal direction from the first step, we propose to minimize an orientation matching cost measuring the alignment between the image gradient and the regularized normal direction. This functional yields a new nonlinear partial differential equation (PDE) for reconstructing denoised and inpainted images. The equation has an adaptive diffusivity depending on the orientation of the regularized normal vector field, providing reconstructed images which have sharp edges and smooth regions. The additive operator splitting (AOS) scheme is used for discretizing Euler-Lagrange equations. We present the results of various numerical experiments that illustrate the improvements obtained with the new functional.