In this paper, we study the problem of recovering the camera motion in a multiview setting given observation of tracked features in a three-dimensional environment. We propose a novel algorithm to simultaneously recover the pose (orientation and translation to within a scale) of every camera directly using a manifold optimization approach. Our contributions are four-fold. We present a new analytic method based on singular value decomposition that yields a closed-form solution for the multiview motion estimation problem in the noise-free case. Secondly, we use this method to derive a good initial estimate of a solution in the noisy case. This initialization step may, independently, be of use in any general iterative scheme. Thirdly, we present an iterative scheme based on Gauss-Newton's method on a product manifold that exhibits local quadratic convergence. Finally, we also present a simple linear least squares approach to recover the individual camera centers from relative translations obtained after the iteration process. Our algorithm has been implemented, and we demonstrate the efficacy of our scheme on both synthetic data and real data.

This paper is concerned with approximation of Wonham filters. A focal point is that the underlying hidden Markov chain has a large state space. To reduce computational complexity, a two-time-scale approach is developed. Under time scale separation, the state space of the underlying Markov chain is divided into a number of groups such that the chain jumps rapidly within each group and switches occasionally from one group to another. Such structure gives rise to a limit Wonham filter that preserves the main features of the filtering process, but has a much smaller dimension and therefore is easier to compute. Using the limit filter enables us to develop efficient approximations and useful filters for hidden Markov chains. The main advantage of our approach is the reduction of dimensionality.

Multinomial representations are derived for majority logic operations on bipolar binary data. The coefficients are given simply in terms of the readily computed lower Cholesky factor of Pascal matrices of order n for codes of block length n

There is a robotic balancing task, namely real-time dextrous-hand grasping, for which linearly constrained, positive definite programming gives a quite satisfactory solution from an engineering point of view. We here propose refinements of this approach to reduce the computational effort. The refinements include elimination of structural constraints in the positive definite matrices, orthogonalization of the grasp maps, and giving a precise Newton step size selection rule.

A family of axially symmetric mirror shapes are proposed for panoramic imaging. These shapes keep the resolution in the image invariant to changes in elevation in the scene. In other words, this family of shapes achieves solid angle pixel density invariance. An analysis of range finding using two coaxial axially symmetric resolution invariant mirrors in a coaxial pair is presented. The resolution invariance property of these mirrors mean that when the image captured is unwarped the resultant image will not suffer from variable image quality. This problem is present in unwarped images captured with any mirror shape not designed for resolution invariance. The resolution invariance of these mirrors is especially important in the case of stereo panoramic mirrors where one view of the scene is captured within the other and thus will have lower resolution. It is necessary to clearly identify two was of an object to undertake range-finding. The proposed mirror shapes will be useful for mobile robotics and machine vision. Other applications areas such as visual sensing for control of traffic lights at street intersections could be considered.

The classical Viterbi algorithm (ML sequence estimation) can be computed using a forward-backward structure, similar to that of the classical hidden Markov model forward-backward algorithm (MAP state estimation). This similarity is exploited to develop a hybrid algorithm which provides a mathematical connection between ML sequence estimation and MAP state estimation.

This paper concerns quadratic programming problems subject to quadratic equality constraints such as arise in broadband antenna array signal processing and elsewhere. At first, such a problem is converted into a semidefinite programming problem with a rank constraint. Then, a rank preserving flow is used to accommodate the rank constraint. The associated gradient formulas are carefully developed. The convergence of the resulting algorithm is also guaranteed. Our approach is demonstrated by a numerical experiment.

In dextrous robotic hand grasping the external object force needs to be balanced with contact forces maintaining grasp stability. Redundancy in the grasp yields the optimization problem to minimize the grasp effort subject to nonlinear friction stability constraints. We reformulate the optimization problem as a semidefinite program with affine constraints. In this paper, two versions of strictly convex cost functions including a barrier term, one of them self-concordant, are considered. For the general class of such cost functions Dikin-type algorithms are considered. It is shown that the proposed algorithms guarantee convergence to the unique solution of the underlying semidefinite program. Numerical examples demonstrate the simplicity of implementation and the good numerical properties of the approach.

This paper considers on-line identification of hidden Markov models via multiple-prediction-horizon recursive prediction error (RPE) methods. Working with multiple-prediction-horizons ensures that there is consistent parameter estimation, under appropriate excitation conditions. Simulation studies are included to illustrate the advantages of the proposed approach when compared to standard methods (which do not ensure consistent parameter estimation).

In this paper, we use an annealed neural network to solve a timetabling problem with contiguity and availability constraints. A novel feature of the problem is that it may not be possible to satisfy the complete set of scheduling requirements, forcing the network to exhibit selection capability. We formulate the problem in a manner consistent with neural computation, describe our implementation of the annealed neural network, and report computational results for a series of randomly-generated problems. Solution quality varies depending on the size and difficulty of the problem, as well as on the values of the penalty parameters used to weight the various constraints.

A key goal in dextrous robotic hand grasping is to balance external forces and at the same time achieve grasp stability and minimum grasping energy by choosing an appropriate set of internal grasping forces. Since it appears that there is no direct algebraic optimization approach, a recursive optimization, which is adaptive for application in a dynamic environment, is required. One key observation in this paper is that friction force limit constraints and force balancing constraints are equivalent to the positive definiteness of a certain matrix subject to linear constraints. Based on this observation, we formulate the task of grasping force optimization as an optimization problem on the smooth manifold of linearly constrained positive definite matrices for which there are known globally exponentially convergent solutions via gradient flows. There are a number of versions depending on the Riemannian metric chosen, each with its advantages, Schemes involving second derivative information for quadratic convergence are also studied. Several forms of constrained gradient flows are developed for point contact and soft-finger contact friction models. The physical meaning of the cost index used for the gradient flows is discussed in the context of grasping force optimization. A discretized version for real-time applicability is presented. Numerical examples demonstrate the simplicity, the good numerical properties, and optimality of the approach.

For dextrous robotic hand grasping a key goal is to balance external and internal grasping forces to assure a stable grasp and low grasping energy. In this paper, the authors view the task of grasping force optimization as a linearly constrained semidefinite programming problem for which there are known globally exponentially convergent solutions via gradient flows. A key observation is that the nonlinear friction constraint at each contact point is equivalent to the positive definiteness of a suitable matrix containing the contact wrench intensities. A recursive version is presented, and numerical examples demonstrate the simplicity, the good numerical properties, and optimality of the approach.

A key problem in robotics is the estimation of the location and orientation of objects from surface measurement data. This is termed pose estimation. A fundamental task is the pose estimation of known quadratic surfaces from, possibly noisy, data. A solution for this task facilitates pose estimation for more complex objects. Current algorithms frequently converge to local minima of the performance index and/or pay a high computing cost and/or are sensitive to noise, that are unsuited for online applications because of the intensive computer effort required. The goal is to develop a fast and robust algorithm for pose estimation using range data. Here, pose estimation is carried out using algebraic techniques in a two stage optimization procedure involving least squares estimation, or better the method of instrumental variables, and 3/spl times/3 matrix diagonalizations. The procedure leads to zero pose estimation error in the noise free finite data case, and in the case of infinite data with additive white noise.

Kalman filtering (KF) and hidden Markov model (HMM) signal processing techniques are coupled to demodulate signals transmitted through noisy fading channels. The demodulation scheme presented can be applied to both digital M-ary differential phase shift keyed (MDPSK) and analog frequency modulated (FM) signals. Adaptive state and parameter estimation algorithms are devised based on the assumption that the transmission channel introduces time-varying gain and phase changes, modelled by a stochastic linear system, and has additive Gaussian noise. Our technique is to use an HMM filter, for signal estimation, coupled with a KF, for channel parameter tracking. The approach taken can easily be generalised for other transmission schemes, such as continuous phase modulated (CPM) signals.>

A detailed study of Oja's learning equation in neural networks is undertaken in this paper. Not only are such fundamental issues as existence, uniqueness, and representation of solutions completely resolved, but also the convergence issue is resolved. It is shown that the solution of Oja's equation is exponentially convergent to an equilibrium from any initial value. Moreover, the necessary and sufficient conditions are given on the initial value for the solution to converge to a dominant eigenspace of the associated autocorrelation matrix. As a by-product, this result confirms one of Oja's conjectures that the solution converges to the principal eigenspace from almost all initial values. Some other characteristics of the limiting solution are also revealed. These facilitate the determination of the limiting solution in advance using only the initial information. Two examples are analyzed demonstrating the explicit dependence of the limiting solution on the initial value. In another respect, it is found that Oja's equation is the gradient flow of generalized Rayleigh quotients on a Stiefel manifold.

In adaptive equalization, there is a tradeoff between convergence rate of the equalizer tap coefficients, the computational speed for each adjustment, the implementation complexity, and algorithm robustness. Parameter update schemes called quantized state (QS) schemes, and fast versions of these schemes termed fast quantized state (FQS) schemes developed within a related context, are here applied to achieve attractive tradeoff options not previously available for adaptive equalization. Three novel simplifications to the QS schemes are introduced and justified by their performance characteristics in adaptive equalization. One simplification is to abandon the likeness to the method of instrumental variables (IV), where the "instrumental variable" is the quantized state vector, and introduce more quantization. Another simplification is to replace asymptotically Toeplitz matrices, or their inverses, by Toeplitz matrices to take advantage of fast schemes for updating QS schemes or taking their inverses.

Convenient recursive prediction error algorithms for identification and adaptive state estimation are proposed, and the convergence of these algorithms to achieve off-line prediction error minimization solutions is studied. To set the recursive prediction error algorithms in another perspective, specializations are derived from significant simplifications to a class of extended Kalman filters. The latter are designed for linear state space models with the unknown parameters augmenting the state vector and in such a way as to yield good convergence properties. Also, specializations to approximate maximum likelihood recursions, Kalman filters with adaptive gains, and connections to the extended least squares algorithms are noted.

In this paper, a theory of optimal nonlinear estimation from sampled data signals where the a posteriori probability densities are approximated by Gaussian sums is adapted for application to phase and frequency estimation in high noise. The nonlinear estimators (demodulators) require parallel processing of the received signal. In the limit as the number of parallel processors becomes infinite the FM demodulators become optimum in a minimum mean square error sense and the PM demodulators become optimum in some well defined sense. For the clearly suboptimal case of one processor, the demodulators can be readily simplified to the familiar phase-locked loop. On the other hand, for the intermediate case, significant extension of the phaselocked loop threshold is achieved where (say) six parallel processors are involved.

Simulation results are presented which are very convincing in favor of FM demodulators driven by in-phase and quadraturephase signals. Application of the extended Kalman filtering algorithms to the appropriate signal model directly yields demodulators in which the error covariance equations are uncoupled from the state estimate equations. These demodulators perform a little better than others derived using different nonlinear filtering techniques and the necessary approximations to achieve "decoupling." More significantly, these demodulators using in-phase and quadrature-phase sampled signals are readily augmented to achieve demodulation with delay by the application of fixed-lag smoothing algorithms. Simulations highlight the attractive trade-offs between demodulation complexity and performance results for this class of demodulator.

The estimation of unknown parameters of deterministic time-varying signals contaminated with additive Gaussian white noise is considered, and an upper bound is obtained for the mean-square estimation error. As an example, the theory is applied to the synchronous demodulation of pulse frequency-modulated (PFM) signals in Gaussian white noise.

Novel demodulator structures are derived for quasioptimal on-line demodulation of pulse-frequency modulated (PFM) signals in the presence of white Gaussian channel noise. The basic demodulator consists of a phase-locked loop with its integrators appropriately reset as each new pulse is received. This modulator may be augmented with additional integrators and gain elements to achieve quasi-optimal demodulation with delay. The quasi-optimal demodulation approaches optimal demodulation, in the minimum mean-square error sense, as the signal-to-noise ratio increases. The various quasi-optimal receivers are derived by application of the extended Kalman filter theory to a state-space signal model.

Kalman filtering theory is applied to yield an optimal causal demodulator for pulse-amplitude-modulated (PAM) signals in the presence of white Gaussian noise. The discrete-time data (or sampled continuous-time data) are assumed to be either a stationary or non-stationary Gaussian stochastic process, in general nonwhite. Optimal demodulation with delay is also achieved by application of Kalman filtering theory. The resulting demodulators (fixed-lag smoothers) are readily constructed and their performance represents in many cases a significant improvement over that for the optimal demodulator without delay. The fixed-lag smoothing results are in contrast to those for amplitude-modulated signals (AM) where only approximate fixed-lag smoothing is possible, and this with considerable design effort. The performance of the optimal PAM demodulator is shown to be equivalent to that of an optimal discrete filter for the discrete data.

At present, many metropolitan sewer systems do not meet existing and proposed standards on water pollution. Existing systems were designed to overflow at prescribed locations in order to protect the sewage treatment plants whenever severe overload conditions exist (usually during storms). This discharge of untreated overflows into natural receiving waters is of growing concern to water pollution control authorities. The model considered in this paper is representative of the combined storm-sewer systems in cities such as Minneapolis-St. Paul, Minn., Seattle, Wash., and San Francisco, Calif. The objective is to utilize the total storage capacity available in the system in such a manner as to minimize the water pollution resulting from overflows at individual points within the system. In addition, it is required that no abrupt changes in control be admitted, as this is likely to lead to undesirable surges. The nonlinear model is shown to fit within the framework of an optimal regulator problem with derivative constraints. The optimal feedback control law is derived and compared with the optimal bang-bang controller. The solution technique that is presented may be applied to many combined storm-sewer systems in which the flows through the systems to the treatment plants may be controlled. It may be used by city engineers to determine necessary modifications to existing systems in order to meet the new standards regarding water pollution.

The Gram-Charlier series representation of the noiseprobability density function is used to determine an optimum detector for signals in non-Gaussian but near-Gaussian (NGNG) noise. Solutions are obtained for coherent and incoherent detection. Optimal detectors for several typical transmitting systems are determined. Generally these detectors consist of the standard detector for Gaussian noise with the addition of a few, not too sophisticated, nonlinear elements. The performance of a detector, specified by the upper bound on the probability of error, is assessed and is seen to depend on the signal shape, the time-bandwidth product, and the signal-to-noise ratio. The optimal signal to minimize the probability of error is determined and is seen to result as a solution to Duffing's second-order nonlinear differential equation.

This paper considers the solution of a Fredholm equation occurring in detection theory problems. A solution procedure, based on solving differential equations with nonmixed boundary conditions, is described for the case when the kernel of the integral equation is known to be the output covariance of a linear finite-dimensional system excited by white noise. Solutions with discontinuities are considered.

The notion is exploded that to build a Kalman-Bucy filter, one needs to know the whole structure of the signal generating process. It is shown that the filter is constructible knowing precisely those covariances required to construct a Wiener filter, and no more, and that the filter is independent of the particular models of the processes generating these covariances. Performance of the Kalman-Bucy filter does depend on the models, however. Results are also obtained for the smoothing problem.

Extensions to a straightforward, always convergent method for solving polynomial equations given in a previous paper are considered. The extensions consist of additional simple calculations and logic instructions which considerably improve convergence rate for the cases when multiple roots exist or when roots are close together. It is believed that in terms of simplicity and convergence properties, the approach is more efficient than presently available methods.

The determination of the state-space equations of a time-varying finite-dimensional linear system with a prescribed output covariance matrix is considered when the system is excited by Gaussian white-noise inputs. It is shown that a symmetric state covariance matrix provides the key link between the state-space equations of a system and the system output covariance matrix. Furthermore, such a matrix satisfies a linear matrix differential equation if the state-space equations of the system are known, and a matrix Riccati equation if the output covariance matrix of the system is given. Existence results are given for the Riccati equation solution, and discussion of asymptotic solutions of the differential equations is also included.

The method of steepest descent is applied in a convergent procedure to determine the zeros of polynomials having either real or complex coefficients. By expressing the polynomials in terms of the Siljak functions, the methods are readily programmed on a digital computer. The significance of the procedures is that their application is straightforward, and not only is convergence rapid in the region of a zero but convergence is guaranteed independent of the initial values.