Typescript (photocopy). / Digitized by Kansas Correctional Industries

The current methods used by forensic experts to analyse blood spatter neglects the influence of gravitation and drag on the trajectory of the droplet. This research attempts to suggest a more accurate method to determine the trajectory of a blood droplet using multi-target tracking. The multi-target tracking problem can be rewritten as a linear programming problem and solved by means of optimization and numerical methods. A literature survey is presented on relevant articles on blood spatter analysis and multi-target tracking. In contrast to a more advanced approach that assumes a background in probability, mathematical modelling and forensic science, this dissertation aims to give a comprehensive mathematical exposition of particle tracking. The tracking of multi-targets, through multi-target tracking, is investigated. The dynamic programming methods to solve the multi-target tracking are coded in the MATLAB programming language. Results are obtained for different scenarios and option inputs. Research strategies include studying documents, articles, journal entries and books. / MSc (Applied Mathematics), North-West University, Potchefstroom Campus, 2014

The current methods used by forensic experts to analyse blood spatter neglects the influence of gravitation and drag on the trajectory of the droplet. This research attempts to suggest a more accurate method to determine the trajectory of a blood droplet using multi-target tracking. The multi-target tracking problem can be rewritten as a linear programming problem and solved by means of optimization and numerical methods. A literature survey is presented on relevant articles on blood spatter analysis and multi-target tracking. In contrast to a more advanced approach that assumes a background in probability, mathematical modelling and forensic science, this dissertation aims to give a comprehensive mathematical exposition of particle tracking. The tracking of multi-targets, through multi-target tracking, is investigated. The dynamic programming methods to solve the multi-target tracking are coded in the MATLAB programming language. Results are obtained for different scenarios and option inputs. Research strategies include studying documents, articles, journal entries and books. / MSc (Applied Mathematics), North-West University, Potchefstroom Campus, 2014

Pathfinding, as a process of selecting a fixed route, has long been studied in Computer Science and Mathematics. Decision making, as a similar, but intrinsically different, process of determining a control policy, is much less studied. Here, I propose a problem that appears to be of the first class, which would suggest that it is easily solvable with a modern machine, but that would be too easy, it turns out. By allowing a pathfinding to anticipate and respond to information, without setting restrictions on the \structure" of this anticipation, selecting the \best step" appears to be an intractable problem. After introducing the necessary foundations and stepping through the strangeness of “safest-with-sight," I attempt to develop an method of approximating the success rate associated with each potential decision; the results suggest something fundamental about decision making itself, that information that is collected at a moment that it is not immediately “consumable", i.e. non-incident, is not as necessary to anticipate than the contrary, i.e. incident information. This is significant because (i) it speaks about when the information should be anticipated, a moment in decision-making long before the information is actually collected, and (ii) whenever the model is restricted to only incident anticipation the problem again becomes tractable. When we only anticipate what is most important, solutions become easy to compute, but attempting to anticipate any more than that and solutions may become impossible to find on any realistic machine.

This thesis concerns the application of mixed-integer programming techniques to solve special classes of network flow problems and stochastic integer programs. We draw tools from complexity and polyhedral theory to analyze these problems and propose improved solution methods. In the first part, we consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are required to take values above a prespecified minimum threshold whenever they are not zero. These problems find applications in management and supply chain models where orders in small quantities are undesirable. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We also consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed polyhedral results in solving randomly generated instances of semi-continuous transportation problems. In the second part, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of optimizing a linear function on the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem and finds applications in stochastic integer programming. We observe that the complexity of the problem depends on how P and X are specified. For instance, P can be explicitly given by its linear description, or implicitly by an oracle. Similarly, X can be explicitly given as a list of vectors, or implicitly as a face of P. While removing vertices turns to be hard in general, it is tractable for tractable 0-1 polytopes, and compact extended formulations can be obtained. Some extensions to integral polytopes are also presented. The third part is devoted to the integer L-shaped method for two-stage stochastic integer programs. A widely used model assumes that decisions are made in a two-step fashion, where first-stage decisions are followed by second-stage recourse actions after the uncertain parameters are observed, and we seek to minimize the expected overall cost. In the case of finitely many possible outcomes or scenarios, the integer L-shaped method proposes a decomposition scheme akin to Benders' decomposition for linear problems, but where a series of mixed-integer subproblems have to be solved at each iteration. To improve the performance of the method, we devise a simple modification that alternates between linear and mixed-integer subproblems, yielding significant time savings in instances from the literature. We also present a general framework to generate optimality cuts via a cut-generating problem. Using an extended formulation of the forbidden-vertices problem, we recast our cut-generating problem as a linear problem and embed it within the integer L-shaped method. Our numerical experiments suggest that this approach can prove beneficial when the first-stage set is relatively complicated.

In this thesis, the primary powertrain components of a power split hybrid electric vehicle are modeled. In particular, the dynamic model of the energy storage element (i.e., traction battery) is exactly linearized through an input transformation method to take advantage of the proposed optimal control algorithm. A lipschitz continuous and nondecreasing cost function is formulated in order to minimize the net amount of consumed fuel. The globally optimal solution is obtained using a dynamic programming routine that produces the optimal input based on the current state of charge and the future power demand. It is shown that the global optimal control solution can be expressed in closed form for a time invariant and convex incremental cost function utilizing the interval back propagation approach. The global optimality of both time varying and invariant solutions are rigorously proved. The optimal closed form solution is further shown to be applicable to the time varying case provided that the time variations of the incremental cost function are sufficiently small. The real time implementation of this algorithm in Simulink is discussed and a 32.84 % improvement in fuel economy is observed compared to existing rule based methods.

The world health organization has identified cardiovascular disease as the leading cause of non-accidental deaths in the world. The heart is identified as diseased when it is not operating at peak efficiency. Early diagnosis of heart disease can impact treatment and improve a patient's outcome. An early sign of a diseased heart is a reduction in its pumping ability, which can be measured by performing functional evaluations. These are typically focused on the ability of the ventricles to pump blood to the lungs (right ventricle) or to the rest of the body (left ventricle). Non-invasive imaging modalities such as cardiac magnetic resonance have allowed the use of quantitative methods for ventricular functional evaluation. The evaluation still requires the tracing of the ventricles in the end-diastolic and end-systolic phases. Even though manual tracing is still considered the gold standard, it is prone to intra- and inter-observer variability and is time consuming. Therefore, substantial research work has been focused on the development of semi- and fully automated ventricle segmentation algorithms. In 2009 a medical imaging conference issued a challenge for short-axis left ventricle segmentation. A semi-automated technique using polar dynamic programming generated results that were within human variability. This is because a path in a polar coordinate system yields a circular object in the Cartesian grid and the left ventricle can be approximated as a circular object. In 2012 there was a right ventricle segmentation challenge, but no polar dynamic programming algorithms were proposed. One reason may be that polar dynamic programming can only segment circular shapes. To use polar dynamic programming for the segmentation of the right ventricle we first expanded the capability of the technique to segment non-circular shapes. We apply this new polar dynamic programming in a framework that uses user-selected landmarks to segment the right ventricle in the four chamber view. We also explore the use of four chamber right ventricular segmentation to segment short-axis views of the right ventricle.

This dissertation addresses the problem of inferring scene depth information from a collection of calibrated images taken from different viewpoints via stereo matching. Although it has been heavily investigated for decades, depth from stereo remains a long-standing challenge and popular research topic for several reasons. First of all, in order to be of practical use for many real-time applications such as autonomous driving, accurate depth estimation in real-time is of great importance and one of the core challenges in stereo. Second, for applications such as 3D reconstruction and view synthesis, high-quality depth estimation is crucial to achieve photo realistic results. However, due to the matching ambiguities, accurate dense depth estimates are difficult to achieve. Last but not least, most stereo algorithms rely on identification of corresponding points among images and only work effectively when scenes are Lambertian. For non-Lambertian surfaces, the "brightness constancy" assumption is no longer valid. This dissertation contributes three novel stereo algorithms that are motivated by the specific requirements and limitations imposed by different applications. In addressing high speed depth estimation from images, we present a stereo algorithm that achieves high quality results while maintaining real-time performance. We introduce an adaptive aggregation step in a dynamic-programming framework. Matching costs are aggregated in the vertical direction using a computationally expensive weighting scheme based on color and distance proximity. We utilize the vector processing capability and parallelism in commodity graphics hardware to speed up this process over two orders of magnitude. In addressing high accuracy depth estimation, we present a stereo model that makes use of constraints from points with known depths - the Ground Control Points (GCPs) as referred to in stereo literature. Our formulation explicitly models the influences of GCPs in a Markov Random Field. A novel regularization prior is naturally integrated into a global inference framework in a principled way using the Bayes rule. Our probabilistic framework allows GCPs to be obtained from various modalities and provides a natural way to integrate information from various sensors. In addressing non-Lambertian reflectance, we introduce a new invariant for stereo correspondence which allows completely arbitrary scene reflectance (bidirectional reflectance distribution functions - BRDFs). This invariant can be used to formulate a rank constraint on stereo matching when the scene is observed by several lighting configurations in which only the lighting intensity varies.

Nous présentons une approche de reconnaissance d'écriture manuscrite à partir de champs de Markov cachés et fondée sur une analyse entièrement bidimensionnelle de l'écriture. Son originalité réside dans la combinaison d'une analyse fenêtrée de l'image, d'une modélisation markovienne et dans la mise en oeuvre de la programmation dynamique 2D qui permet un décodage rapide et optimal des champs de Markov. Un aspect important de ces travaux est la méthodologie de développement employée qui est centrée sur l'évaluation systématique des apports algorithmiques et des paramètres utilisés. Ces algorithmes sont en partie empruntés aux techniques utilisées dans le domaine de la reconnaissance de la parole et sont très génériques.<br /><br />L'approche proposée est validée sur deux applications correspondant à des bases de données standard et librement disponibles. L'application de cette méthode extrêmement générique à une tâche de reconnaissance de chiffres manuscrits a permis d'obtenir des résultats comparables à ceux de l'état de l'art. L'application à une tâche de reconnaissance de mots manuscrits a permis de confirmer que l'extension de cette approche à des tâches plus complexes était naturelle.<br /><br />L'ensemble de cette recherche a démontré la validité de l'approche développée qui apparaît comme candidate au statut d'approche standard pour plusieurs problèmes de vision. En outre, elle ouvre la voie à de très nombreux développements concernant la tâche de traitement de l'écriture manuscrite et des améliorations significatives pourraient encore être apportées en recourant à d'autres principes issus du traitement de la parole et du langage. D'autres tâches comme la segmentation d'image devraient tirer avantage de la robustesse et de la faculté d'apprentissage de la modélisation que nous proposons.

This dissertation contains a discussion concerning the validity of the principle of optimality and the dynamic programming algorithm in the context of discrete time and state multistage decision processes. The multistage decision model developed for the purpose of the investigation is of a general structure, especially as far as the reward function is concerned. The validity of the dynamic programming algorithm as a solution method is investigated and results are obtained for a rather wide class of decision processes. The intimate relationship between the principle and the algorithm is investigated and certain important conclusions are derived. In addition to the theoretical considerations involved in the implementation of the dynamic programming algorithm, some modeling and computational aspects are also investigated. It is demonstrated that the multistage decision model and the dynamic programming algorithm as defined in this study provide a solid framework for handling a wide class of multistage decision processes. The flexibility of the dynamic programming algorithm as a solution procedure for nonroutine reservoir control problems is demonstrated by two examples, one of which is a reliability problem. To the best of the author's knowledge, many of the theoretical derivations presented in this study, especially those concerning the relation between the principle of optimality and the dynamic programming algorithm, are novel.