Interactive 3D animation of human figures is very common in video games, animation studios and virtual environments. However, it is difficult to produce full body animation that looks realistic enough to be comparable to studio quality human motion data. The commercial motion capture systems are expensive and not suitable for capture in everyday environments. Real-time requirements tend to reduce quality of animation. We present a motion graph based framework to produce high quality motion sequences in real-time using a set of inertial sensor based controllers. The user's action generates signals from the controllers that provide constraints to select appropriate sequence of motions from a structured database of human motions, namely \emph{motion graph}. Our local search algorithm utilizes noise prone and rapidly varying input sensor signals for querying a large database in real-time. The ability to waive the controllers for producing high quality animation provides a simple 3D user interface that is intuitive to use. The proposed framework is low cost and easy to setup. / Master of Science

動作擷取法是現今相當受到歡迎的角色動作產生方法，而一般多是使用已擷取好的動作，以人工的方式將數個不同的動作混合以產生出所需的動作。但想要大量產生符合需求的混合動作仍相當不容易，因此有人提出了「動作圖」這個方法。動作圖是一種根據使用者所給定的動作擷取資料集合，經過自動化的計算找出各個動作資料之間可以連接的動作片段。藉由這個自動化的程序，各個動作擷取資料可以相互連接起來，達到在不同的動作間平順轉換，且同時保有原動作擷取資料擬真特性的目的。但縱使有上述的好處，目前動作圖的技術僅能就所擷取的全身動作進行串接，品質與彈性往往決定於一開始動作擷取資料的準備，因此如何讓既有的全身動作資料得以分解再利用，以發揮最大的價值，是一個重要的問題。在本研究中，我們提出了一個階層式的動作圖結構名為多層式動作圖，在這個多層式動作圖的結構中，我們將身體的動作區分成數個部位，分別計算各自的動作圖後再合併成一個多層式的架構，而合併的過程中我們提出「整體動作相似度」的計算方式，以做為兩個動作是否容易轉接的比較依據。我們也提出了在不同階層間動作圖運作的規則，以使計算的複雜度及系統的可用性取得合理的平衡。此外，我們更進一步提出名為Motion Script的簡易語意描述語言，來輔助控制這個具有高複雜度的動作圖結構。實驗的結果顯示，我們的方法可以即時根據使用者的指令，搜尋並產生出原動作資料所沒有的動作組合。與傳統的動作圖相比，我們的方法能更進一步的發揮原動作擷取資料的價值，以有系統的方式讓動作組合自動產生更具豐富性及彈性。 / Motion capture is a popular method for generating realistic character animation. In most applications, a motion usually is prepared by manually blending existing captured motion clips to generate a desired motion clip. However, finding a good transition points manually for two motion clips is a time-consuming task and cannot be scaled up easily. Motion Graph is a technique that has been proposed to automate this process by finding suitable connection points and the corresponding transition motions between motion data. With this automatic procedure, motions captured separately can be smoothly connected while keeping the realism of the captured motions. However, most motion graph techniques only consider the transition of full-body motions in two motion clips, and therefore, the resulting motion .depends on the variety of motions available in the motion database. It is an important issue to be able to compose new motion clips as much as possible with given motion capture database. In this research, we propose a hierarchical motion graph structure called Multi-Layered Motion Graph. In this structure, we divide motion data into layers of parts depending on the articulated structure of human body, and then compute a motion graph for each part of the motion. We then combine these motion graphs into an interconnected hierarchical structure. In order to facilitate the composition of motions for different parts from different motion clips, we propose a new metric called Overall Motion Similarity to find reasonable composition of motions in run time. We also propose several rules about how to traverse the motion graphs in different layers to generate feasible motions. Furthermore, we have designed a scripting language called Motion Script to facilitate the specification and search of desirable animation to be generated. Our experimental results reveal that our method is able to compose animations that the original motion graph cannot generate in real time. Compared to the traditional motion graph method, our method is able to make good use of existing motion capture library to compose new motions in a systematic way.

Unmanned vehicle systems, specifically unmanned air vehicles (UAVs) and unmanned ground vehicles (UGVs), have become a popular research topic. This thesis discusses the potential of a UAV-UGV system used to track a human moving through complex urban terrain. This research focuses on path planning problems for both a UAV and a UGV, and presents effective solutions for both problems. In the UAV path planning problem, we desire to plan a path for a miniature fixed-wing UAV to fly through known urban terrain without colliding with any buildings. We present the Waypoint RRT (WRRT) algorithm, which accounts for UAV dynamics while planning a flyable, collision-free waypoint path for a UAV in urban terrain. Results show that this method is fast and robust, and is able to plan paths in difficult urban environments and other terrain maps as well. Simulation and hardware tests demonstrate that these paths are indeed flyable by a UAV. The UGV path planning problem focuses on planning a path to capture a moving target in an urban grid. We discuss using a target motion model based on Markov chains to predict future target locations. We then introduce the Capture and Propagate algorithm, which uses this target motion model to determine the probabilities of capturing the target in various numbers of steps and with various initial UGV moves. By applying some different cost functions, the result of this algorithm is used to choose an optimal first step for the UGV. Results demonstrate that this algorithm is at least as effective as planning a path directly to the current location of the target, and that in many cases, this algorithm performs better. We discuss these cases and verify them with simulation results.