Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: Monocular structure from motion (SfM) is a widely researched problem, however many of the existing approaches prove to be too computationally expensive for use on mobile devices. In this thesis we investigate how inertial sensors can be used to increase the performance of SfM algorithms on mobile devices. Making use of the low cost inertial sensors found on most mobile devices we design and implement an extended Kalman filter (EKF) to exploit their complementary nature, in order to produce an accurate estimate of the attitude of the device. We make use of a quaternion based system model in order to linearise the measurement stage of the EKF, thus reducing its computational complexity. We use this attitude estimate to enhance the feature tracking and camera localisation stages in our SfM pipeline. In order to perform feature tracking we implement a hybrid tracking algorithm which makes use of Harris corners and an approximate nearest neighbour search to reduce the search space for possible correspondences. We increase the robustness of this approach by using inertial information to compensate for inter-frame camera rotation. We further develop an efficient bundle adjustment algorithm which only optimises the pose of the previous three key frames and the 3D map points common between at least two of these frames. We implement an optimisation based localisation algorithm which makes use of our EKF attitude estimate and the tracked features, in order to estimate the pose of the device relative to the 3D map points. This optimisation is performed in two steps, the first of which optimises only the translation and the second optimises the full pose. We integrate the aforementioned three sub-systems into an inertial assisted pose estimation pipeline. We evaluate our algorithms with the use of datasets captured on the iPhone 5 in the presence of a Vicon motion capture system for ground truth data. We find that our EKF can estimate the device’s attitude with an average dynamic accuracy of ±5°. Furthermore, we find that the inclusion of sensors into the visual pose estimation pipeline can lead to improvements in terms of robustness and computational efficiency of the algorithms and are unlikely to negatively affect the accuracy of such a system. Even though we managed to reduce execution time dramatically, compared to typical existing techniques, our full system is found to still be too computationally expensive for real-time performance and currently runs at 3 frames per second, however the ever improving computational power of mobile devices and our described future work will lead to improved performance. From this study we conclude that inertial sensors make a valuable addition into a visual pose estimation pipeline implemented on a mobile device. / AFRIKAANSE OPSOMMING: Enkel-kamera struktuur-vanaf-beweging (structure from motion, SfM) is ’n bekende navorsingsprobleem, maar baie van die bestaande benaderings is te berekeningsintensief vir gebruik op mobiele toestelle. In hierdie tesis ondersoek ons hoe traagheidsensors gebruik kan word om die prestasie van SfM algoritmes op mobiele toestelle te verbeter. Om van die lae-koste traagheidsensors wat op meeste mobiele toestelle gevind word gebruik te maak, ontwerp en implementeer ons ’n uitgebreide Kalman filter (extended Kalman filter, EKF) om hul komplementêre geaardhede te ontgin, en sodoende ’n akkurate skatting van die toestel se postuur te verkry. Ons maak van ’n kwaternioon-gebaseerde stelselmodel gebruik om die meetstadium van die EKF te lineariseer, en so die berekeningskompleksiteit te verminder. Hierdie afskatting van die toestel se postuur word gebruik om die fases van kenmerkvolging en kameralokalisering in ons SfM proses te verbeter. Vir kenmerkvolging implementeer ons ’n hibriede volgingsalgoritme wat gebruik maak van Harris-hoekpunte en ’n benaderde naaste-buurpunt-soektog om die soekruimte vir moontlike ooreenstemmings te verklein. Ons verhoog die robuustheid van hierdie benadering, deur traagheidsinligting te gebruik om vir kamerarotasies tussen raampies te kompenseer. Verder ontwikkel ons ’n doeltreffende bondelaanpassingsalgoritme wat slegs optimeer oor die vorige drie sleutelraampies, en die 3D punte gemeenskaplik tussen minstens twee van hierdie raampies. Ons implementeer ’n optimeringsgebaseerde lokaliseringsalgoritme, wat gebruik maak van ons EKF se postuurafskatting en die gevolgde kenmerke, om die posisie en oriëntasie van die toestel relatief tot die 3D punte in die kaart af te skat. Die optimering word in twee stappe uitgevoer: eerstens net oor die kamera se translasie, en tweedens oor beide die translasie en rotasie. Ons integreer die bogenoemde drie sub-stelsels in ’n pyplyn vir postuurafskatting met behulp van traagheidsensors. Ons evalueer ons algoritmes met die gebruik van datastelle wat met ’n iPhone 5 opgeneem is, terwyl dit in die teenwoordigheid van ’n Vicon bewegingsvasleggingstelsel was (vir die gelyktydige opneming van korrekte postuurdata). Ons vind dat die EKF die toestel se postuur kan afskat met ’n gemiddelde dinamiese akkuraatheid van ±5°. Verder vind ons dat die insluiting van sensors in die visuele postuurafskattingspyplyn kan lei tot verbeterings in terme van die robuustheid en berekeningsdoeltreffendheid van die algoritmes, en dat dit waarskynlik nie die akkuraatheid van so ’n stelsel negatief beïnvloed nie. Al het ons die uitvoertyd drasties verminder (in vergelyking met tipiese bestaande tegnieke) is ons volledige stelsel steeds te berekeningsintensief vir intydse verwerking op ’n mobiele toestel en hardloop tans teen 3 raampies per sekonde. Die voortdurende verbetering van mobiele toestelle se berekeningskrag en die toekomstige werk wat ons beskryf sal egter lei tot ’n verbetering in prestasie. Uit hierdie studie kan ons aflei dat traagheidsensors ’n waardevolle toevoeging tot ’n visuele postuurafskattingspyplyn kan maak.

No description available.

Mechanical systems operate under parametric and external excitation uncertainties. The polynomial chaos approach has been shown to be more efficient than Monte Carlo approaches for quantifying the effects of such uncertainties on the system response. This work uses the polynomial chaos framework to develop new methodologies for the simulation, parameter estimation, and control of mechanical systems with uncertainty. This study has led to new computational approaches for parameter estimation in nonlinear mechanical systems. The first approach is a polynomial-chaos based Bayesian approach in which maximum likelihood estimates are obtained by minimizing a cost function derived from the Bayesian theorem. The second approach is based on the Extended Kalman Filter (EKF). The error covariances needed for the EKF approach are computed from polynomial chaos expansions, and the EKF is used to update the polynomial chaos representation of the uncertain states and the uncertain parameters. The advantages and drawbacks of each method have been investigated. This study has demonstrated the effectiveness of the polynomial chaos approach for control systems analysis. For control system design the study has focused on the LQR problem when dealing with parametric uncertainties. The LQR problem was written as an optimality problem using Lagrange multipliers in an extended form associated with the polynomial chaos framework. The solution to the Hâ problem as well as the H2 problem can be seen as extensions of the LQR problem. This method might therefore have the potential of being a first step towards the development of computationally efficient numerical methods for Hâ design with parametric uncertainties. I would like to gratefully acknowledge the support provided for this work under NASA Grant NNL05AA18A. / Ph. D.

Generally in most of the applications of estimation theory using the Method of Maximum Likelihood Estimation (MMLE) to dynamical systems one deals with a situation where only the measurement noise alone is present. However in many present day applications where modeling errors and random state noise input conditions occur it has become necessary for MMLE to handle measurement noise as well as process noise. The numerical algorithms accounting for both measurement and process noise require significantly an order of magnitude higher computer time and memory. Further more, implementation difficulties and convergence problems are often encountered. Here one has to estimate the quantities namely, the initial state error covariance matrix Po, measurement noise covariance matrix R, the process noise covariance matrix Q and the system parameter 0 and the present work deals with the above. Since the above problem is fairly involved we need to have a good reference solution. For this purpose we utilize the approach and results of Gemson who considered the above problem via the extended Kalman filter (EKF) route to compare the present results from the MMLE route. The EKF uses the unknown parameters as additional states unlike in MMLE which uses only the system states. Chapter 1 provides a brief historical perspective followed by parameter identification in the presence of process and measurement noises. The earlier formulations such as natural, innovation, combined, and adaptive approaches are discussed. Chapter 2 deals with the heuristic adaptive tuning of the Kalman filter parameters for the matrices Q and R by Myers and Tapley originally developed for state estimation problems involving satellite orbit estimation. It turns out that for parameter estimation problems apart from the above matrices even the choice of the initial covariance matrix Po is crucial for obtaining proper parameter estimates with a finite amount of data and for this purpose the inverse of the information matrix for Po is used. This is followed by a description of the original Controlled Random Search (CRS) of Price and its variant as implemented and used in the present work to estimate or tune Q, R, and 0 which is the aim of the present work. The above help the reader to appreciate the setting under which the present study has been carried out. Chapter 3 presents the results and the analysis of the estimation procedure adopted with respect to a specific case study of the lateral dynamics of an aircraft involving 15 unknown parameters. The reference results for the present work are the ones based on the approach of Gemson and Ananthasayanam (1998). The present work proceeds in two phases. In the first case (i) the EKF estimates for Po, Q, and R are used to obtain 0 and in the second case (ii) the estimate of Po and Q together with a reasonable choice of R are utilized to obtain 0 from the CRS algorithm. Thus one is able to assess the capability of the CRS to estimate only the unknown parameters. The next Chapter 4 presents the results of utilizing the CRS algorithm with R based on a reasonable choice and for Po from the inverse of the information matrix to estimate both Q and 0. This brings out the efficiency of MMLE with CRS algorithm in the estimation of unknown process noise characteristics and unknown parameters. Thus it demonstratesthofcdifficult Q can be estimated using CRS technique without the attendant difficulties of the earlier MMLE formulations in dealing with process noise. Chapter 5 discusses the - implementation of CRS to estimate the unknown measurement noise covariance matrix R together with the unknown 0 by utilizing the values of Po and Q obtained through EKF route. The effect of variation of R in the parameter estimation procedure is also highlighted in This Chapter. This Chapter explores the importance of Po in the estimation procedure. It establishes the importance of Po though most of the earlier works do not appear to have recognized such a feature. It turned out that the CRS algorithm does not converge when some arbitrary value of Po is chosen. It has to be necessarily obtained from a scouting pass of the EKF. Some sensitivity studies based on variations of Po shows its importance. Further studies shows the sequence of updates, the random nature of process and measurement noise effects, the deterministic nature of the parameter, play a critical role in the convergence of the algorithm. The last Chapter 6 presents the conclusions from the present work and suggestions for further work.

The thesis outlines the development and application of a few novel dynamic state estimation based methods for estimation of parameters of vibrating engineering structures. The study investigates strategies for data fusion from multiple tests of possibly different types and different sensor quantities through the introduction of a common pseudo-time parameter. These strategies have been developed within the framework of Kalman and particle filtering techniques. The proposed methods are applied to a suite of problems that includes laboratory and field studies with a primary focus on finite element model updating of bridge structures and vehicle structure interaction problems. The study also describes how finite element models residing in commercially available softwares can be made to communicate with database of measurements via a particle filtering algorithm developed on the Matlab platform. The thesis is divided into six chapters and an appendix. A review of literature on problems of structural system identification with emphasis on methods on dynamic state estimation techniques is presented in Chapter 1. The problem of system parameter idenfification when measurements originate from multiple tests and multiple sensors is considered in Chapter 2. and solution based on Neumann expansion of the structural static/dynamic stiffness matrix and Kalman filtering is proposed to tackle this problem. The question of decoupling the problem of parameter estimation from state estimation is also discussed. The avoidance of linearization of the stiffness matrix and solution of the parameter problems by using Monte Carlo filters is examined in Chapter 3. This also enables treatment of nonlinear structural mechanics problems. The proposed method is assessed using synthetic and laboratory measurement data. The problem of interfacing structural models residing in professional finite element analysis software with measured data via particle filtering algorithm developed on Matlab platform is considered in Chapter 4. Illustrative examples now cover laboratory studies on a beam structure and also filed studies on an existing multi-span masonry railway arch bridge. Identification of parameters of systems with strong nonlinearities, such, as a rectangular rubber sheet with a concentric hole, is also investigated. Studies on parameter identification in beam moving oscillator problem are reported in Chapter 5. The efficacy of particle filtering strategy in identifying parameters of this class of time varying system is demonstrated. A resume of contributions made and a few suggestions for further research are provided in Chapter 6. The appendix contains details of development of interfaces among finite element software(NISA), data base of measurements and particle filtering algorithm (developed on Matlab platform).

Automobile accidents are one of the leading causes of death and claim more than 40,000 lives annually in the US alone. A substantial portion of these accidents occur at road intersections. Stop signs and traffic signals are some of the intersection control devices used to increase safety and prevent collisions. However, these devices themselves can contribute to collisions, are costly, inefficient, and are prone to failure. This thesis proposes an adaptive, decentralized, cooperative collision avoidance (CCA) system that optimizes each vehicle's controls subject to the constraint that no collisions occur. Three major contributions to the field of collision avoidance have resulted from this research. First, a nonlinear 5-state variable vehicle model is expanded from an earlier model developed in [1]. The model accounts for internal engine characteristics and more realistically approximates vehicle behavior in comparison to idealized, linear models. Second, a set of constrained, coupled Extended Kalman Filters (EKF) are used to predict the trajectory of the vehicles approaching an intersection in real-time. The coupled filters support decentralized operation and ensure that the optimization algorithm bases its decisions on good, reliable estimates. Third, a vehicular network based on the new WAVE standard is presented that provides cooperative capabilities by enabling intervehicle communication. The system is simulated against today's common intersection control devices and is shown to be superior in minimizing average vehicle delay. / Master of Science

In this dissertation a novel alternative system concept for monocular-inertial egomotion and landmark position determination is introduced. It is mainly motivated by an in-depth analysis of the observability and consistency of the classic simultaneous localization and mapping (SLAM) approach, which is based on a world-centric model of an agent and its environment. Within the novel system concept - a body-centric agent and environment model, - a pseudo-world centric motion propagation, - and closed-form initialization procedures are introduced. This approach allows for combining the advantageous observability properties of body-centric modeling and the advantageous motion propagation properties of world-centric modeling. A consistency focused and simulation based evaluation demonstrates the capabilities as well as the limitations of the proposed concept. / In dieser Dissertation wird ein neuartiges, alternatives Systemkonzept für die monokular-inertiale Eigenbewegungs- und Landmarkenpositionserfassung vorgestellt. Dieses Systemkonzept ist maßgeblich motiviert durch eine detaillierte Analyse der Beobachtbarkeits- und Konsistenzeigenschaften des klassischen Simultaneous Localization and Mapping (SLAM), welches auf einer weltzentrischen Modellierung eines Agenten und seiner Umgebung basiert. Innerhalb des neuen Systemkonzeptes werden - eine körperzentrische Modellierung des Agenten und seiner Umgebung, - eine pseudo-weltzentrische Bewegungspropagation, - und geschlossene Initialisierungsprozeduren eingeführt. Dieser Ansatz erlaubt es, die günstigen Beobachtbarkeitseigenschaften körperzentrischer Modellierung und die günstigen Propagationseigenschaften weltzentrischer Modellierung zu kombinieren. Sowohl die Fähigkeiten als auch die Limitierungen dieses Ansatzes werden abschließend mit Hilfe von Simulationen und einem starken Fokus auf Schätzkonsistenz demonstriert.

This work is to investigate the performance of two Kalman Filter Algorithms, namely Linear Kalman Filter and Extended Kalman Filter on control-based human motion prediction in a real-time teleoperation. The Kalman Filter Algorithm has been widely used in research areas of motion tracking and GPS-navigation. However, the potential of human motion prediction by utilizing this algorithm is rarely being mentioned. Combine with the known issue - the delay issue in today’s teleoperation services, the author decided to build a prototype of simple teleoperation model based on the Kalman Filter Algorithm with the aim of eliminated the unsynchronization between the user’s inputs and the visual frames, where all the data were transferred over the network. In the first part of the thesis, two types of Kalman Filter Algorithm are applied on the prototype to predict the movement of the robotic arm based on the user’s motion applied on a Haptic Device. The comparisons in performance among the Kalman Filters have also been focused. In the second part, the thesis focuses on optimizing the motion prediction which based on the results of Kalman filtering by using the smoothing algorithm. The last part of the thesis examines the limitation of the prototype, such as how much the delays are accepted and how fast the movement speed of the Phantom Haptic can be, to still be able to obtain reasonable predations with acceptable error rate.   The results show that the Extended Kalman Filter has achieved more advantages in motion prediction than the Linear Kalman Filter during the experiments. The unsynchronization issue has been effectively improved by applying the Kalman Filter Algorithm on both state and measurement models when the latency is set to below 200 milliseconds. The additional smoothing algorithm further increases the accuracy. More important, it also solves shaking issue on the visual frames on robotic arm which is caused by the wavy property of the Kalman Filter Algorithm. Furthermore, the optimization method effectively synchronizes the timing when robotic arm touches the interactable object in the prediction.   The method which is utilized in this research can be a good reference for the future researches in control-based human motion tracking and prediction. / Detta arbete fokuserar på att undersöka prestandan hos två Kalman Filter Algoritmer, nämligen Linear Kalman Filter och Extended Kalman Filter som används i realtids uppskattningar av kontrollbaserad mänsklig rörelse i teleoperationen. Dessa Kalman Filter Algoritmer har används i stor utsträckning forskningsområden i rörelsespårning och GPS-navigering. Emellertid är potentialen i uppskattning av mänsklig rörelse genom att utnyttja denna algoritm sällan nämnas. Genom att kombinera med det kända problemet – fördröjningsproblem i dagens teleoperation tjänster beslutar författaren att bygga en prototyp av en enkel teleoperation modell vilket är baserad på Kalman Filter algoritmen i syftet att eliminera icke-synkronisering mellan användarens inmatningssignaler och visuella information, där alla data överfördes via nätverket. I den första delen av avhandlingen appliceras både Kalman Filter Algoritmer på prototypen för att uppskatta rörelsen av robotarmen baserat på användarens rörelse som anbringas på en haptik enhet. Jämförelserna i prestandan bland de Kalman Filter Algoritmerna har också fokuserats. I den andra delen fokuserar avhandlingen på att optimera uppskattningar av rörelsen som baserat på resultaten av Kalman-filtrering med hjälp av en utjämningsalgoritm. Den sista delen av avhandlingen undersökes begräsning av prototypen, som till exempel hur mycket fördröjningar accepteras och hur snabbt den haptik enheten kan vara, för att kunna erhålla skäliga uppskattningar med acceptabel felfrekvens.   Resultaten visar att den Extended Kalman Filter har bättre prestandan i rörelse uppskattningarna än den Linear Kalman Filter under experimenten. Det icke-synkroniseringsproblemet har förbättrats genom att tillämpa de Kalman Filter Algoritmerna på både statliga och värderingsmodeller när latensen är inställd på under 200 millisekunder. Den extra utjämningsalgoritmen ökar ytterligare noggrannheten. Denna algoritm löser också det skakande problem hos de visuella bilder på robotarmen som orsakas av den vågiga egenskapen hos Kalman Filter Algoritmen. Dessutom effektivt synkroniserar den optimeringsmetoden tidpunkten när robotarmen berör objekten i uppskattningarna.   Den metod som används i denna forskning kan vara en god referens för framtida undersökningar i kontrollbaserad rörelse- spåning och uppskattning.

A main thrust of this thesis is to develop and explore linearization-based numeric-analytic integration techniques in the context of stochastically driven nonlinear oscillators of relevance in structural dynamics. Unfortunately, unlike the case of deterministic oscillators, available numerical or numeric-analytic integration schemes for stochastically driven oscillators, often modelled through stochastic differential equations (SDE-s), have significantly poorer numerical accuracy. These schemes are generally derived through stochastic Taylor expansions and the limited accuracy results from difficulties in evaluating the multiple stochastic integrals. We propose a few higher-order methods based on the stochastic version of transversal linearization and another method of linearizing the nonlinear drift field based on a Girsanov change of measures. When these schemes are implemented within a Monte Carlo framework for computing the response statistics, one typically needs repeated simulations over a large ensemble. The statistical error due to the finiteness of the ensemble (of size N, say)is of order 1/√N, which implies a rather slow convergence as N→∞. Given the prohibitively large computational cost as N increases, a variance reduction strategy that enables computing accurate response statistics for small N is considered useful. This leads us to propose a weak variance reduction strategy. Finally, we use the explicit derivative-free linearization techniques for state and parameter estimations for structural systems using the extended Kalman filter (EKF). A two-stage version of the EKF (2-EKF) is also proposed so as to account for errors due to linearization and unmodelled dynamics. In Chapter 2, we develop higher order locally transversal linearization (LTL) techniques for strong and weak solutions of stochastically driven nonlinear oscillators. For developing the higher-order methods, we expand the non-linear drift and multiplicative diffusion fields based on backward Euler and Newmark expansions while simultaneously satisfying the original vector field at the forward time instant where we intend to find the discretized solution. Since the non-linear vector fields are conditioned on the solution we wish to determine, the methods are implicit. We also report explicit versions of such linearization schemes via simple modifications. Local error estimates are provided for weak solutions. Weak linearized solutions enable faster computation vis-à-vis their strong counterparts. In Chapter 3, we propose another weak linearization method for non-linear oscillators under stochastic excitations based on Girsanov transformation of measures. Here, the non-linear drift vector is appropriately linearized such that the resulting SDE is analytically solvable. In order to account for the error in replacing of non-linear drift terms, the linearized solutions are multiplied by scalar weighting function. The weighting function is the solution of a scalar SDE(i.e.,Radon-Nikodym derivative). Apart from numerically illustrating the method through applications to non-linear oscillators, we also use the Girsanov transformation of measures to correct the truncation errors in lower order discretizations. In order to achieve efficiency in the computation of response statistics via Monte Carlo simulation, we propose in Chapter 4 a weak variance reduction strategy such that the ensemble size is significantly reduced without seriously affecting the accuracy of the predicted expectations of any smooth function of the response vector. The basis of the variance reduction strategy is to appropriately augment the governing system equations and then weakly replace the associated stochastic forcing functions through variance-reduced functions. In the process, the additional computational cost due to system augmentation is generally far less besides the accrued advantages due to a drastically reduced ensemble size. The variance reduction scheme is illustrated through applications to several non-linear oscillators, including a 3-DOF system. Finally, in Chapter 5, we exploit the explicit forms of the LTL techniques for state and parameters estimations of non-linear oscillators of engineering interest using a novel derivative-free EKF and a 2-EKF. In the derivative-free EKF, we use one-term, Euler and Newmark replacements for linearizations of the non-linear drift terms. In the 2-EKF, we use bias terms to account for errors due to lower order linearization and unmodelled dynamics in the mathematical model. Numerical studies establish the relative advantages of EKF-DLL as well as 2-EKF over the conventional forms of EKF. The thesis is concluded in Chapter 6 with an overall summary of the contributions made and suggestions for future research.

Development of dynamic state estimation techniques and their applications in problems of identification in structural engineering have been taken up. The thrust of the study has been the identification of structural systems that exhibit nonlinear behavior, mainly in the form of constitutive and geometric nonlinearities. Methods encompassing both linearization based strategies and those involving nonlinear filtering have been explored. The applications of derivative-free locally transversal linearization (LTL) and multi-step transversal linearization (MTrL) schemes for developing newer forms of the extended Kalman filter (EKF) algorithm have been explored. Apart from the inherent advantages of these methods in avoiding gradient calculations, the study also demonstrates their superior numerical accuracy and considerably less sensitivity to the choice of step sizes. The range of numerical illustrations covers SDOF as well as MDOF oscillators with time-invariant parameters and those with discontinuous temporal variations. A new form of the sequential importance sampling (SIS) filter is developed which explores the scope of the existing SIS filters to cover nonlinear measurement equations and more general forms of noise involving multiplicative and (or) Gaussian/ non-Gaussian noises. The formulation of this method involves Ito-Taylor’s expansions of the nonlinear functions in the measurement equation and the development of the ideal ispdf while accounting for the non-Gaussian terms appearing in the governing equation. Numerical illustrations on parameter identification of a few nonlinear oscillators and a geometrically nonlinear Euler–Bernoulli beam reveal a remarkably improved performance of the proposed methods over one of the best known algorithms, i.e. the unscented particle filter. The study demonstrates the applicability of diverse range of mathematical tools including Magnus’ functional expansions, theory of SDE-s, Ito-Taylor’s expansions and simulation and characterization of the non-Gaussian random variables to the problem of nonlinear structural system identification.