Abstract

In this work, I present a generalized dependency parsing scheme using the Computation Paninian Grammar (CPG). This is done by incorporating the grammatical notions of CPG in both constraint based parsing and data-driven parsing. These are reflected as design decisions, constraint formation, feature selection, etc. in these parsers. In the constraint based setup I extend an existing parsing paradigm for CPG to cover additional language phenomenons. A layered parsing approach is motivated, in particular, two stages based on the notion of clause is introduced in parsing. I show how different grammatical constructs are parsed at appropriate stages. Use of different types of constraints such as licensing, eliminative and preferential are introduced to help negotiate language variability with generic grammatical notions. This setup is then integrated with the insights from graph-based dependency parsing and labeling for the task of prioritization. This constraint based system (GH-CBP) is illustrated using Hindi, Telugu and Bangla. It has been evaluated for Hindi and Telugu. I then show how the insights gained from building GH-CBP can be applied to data driven approaches. This is done by (a) incorporating targeted features during the training process, (b) by introducing ‘linguistically constrained’ modularity during the parsing process, and (c) by exploring ‘linguistically rich’ graph-based parsing. I finally discuss the error analysis and make concluding observations.

Abstract

There are three major tasks that a robot must be able to perform for it to be truly autonomous. Firstly, it should be able to ascertain where it is. This is the problem of localization. Secondly, it should be able to acquire the map of its surroundings even when its actuators and sensors are slightly faulty. This is the problem of Simultaneous Localization And Mapping (SLAM). Finally, given the map of its surroundings and a start and end position, the robot should be able to compute the path that it should take. This is the problem of path planning. Depending upon the constraints the robot faces at that point of time (like the kind of data available, the assumptions that are valid etc.), each of these problems can be further divided into subproblems. This thesis concentrates on these three problems in unstructured environments. Traditionally, robots are assumed to operate in environments where easily discernible features are available. This simplifies the actual implementation but places a restriction on the kinds of environments in which the robot can operate. In order to remove the dependence on the information regarding the features, the entire raw data obtained from the sensors can be used directly, to solve the above problems. The contributions of this thesis can be summed up as follows: 1. Scan Correlation : The process of scan correlation or scan matching is very useful in map building and localization in environments without any easily discernible landmarks. It involves estimating the relative transform between two given scans of data (represented as point sets). The problem of scan correlation has been well studied by both the Mobile Robotics and Computer Vision communities. But the applicability of scan correlation, especially the question of which metric to use in which environment remains largely unanswered. The goal of this chapter is threefold. First, it presents an analytic view of two major metrics in use today, namely the Least Mean Squared Error and the Gaussian Mixture Model correlation metric, discussing the relative merits and demerits of both. Secondly, it explains why scan correlation becomes harder as the amount of structure reduces in the environment. And thirdly, it proposes a novel Particle Filtering scheme to combine the above two metrics. Simulation results are then provided to verify the effectiveness of this method. 2. SLAM : Traditionally, for dealing with the problem of SLAM, two popular methods exist. Firstly, the Information Filter is an offline method that accumulates the obtained sensor and motion infor- mation into a graph of linear constraints, which is later optimized when the map and the trajectory is needed. The second method, based on the Particle Filter, treats the SLAM problem as Monte Carlo Markov Chain process and represents the posterior using a weighted sample set obtained by importance sampling. The major problem with the former is its assumption that the constraints are linear and whereas the latter exhibits sample impoverishment (where the majority of the re- tained trajectories have a common ancestry), which restricts its ability to close large loops in the environment. As the second contribution of this work, we present two approaches to combine the two mapping strategies described above. The first method describes how the Particle Filter can be incorporated into the Information Filter framework by building local sub-maps using the Particle Filter and combining them using a Information Filter to obtain a global map. Using the Particle Filter locally reduces the linearization errors and is useful in handling ambiguous data associations, while the Information Filter keeps track of the uncertainty over long periods of time, thereby avoiding the Particle Filter’s tendency to become overconfident. The second method considers the converse case and shows how the Information Filter can be used in the Particle Filter framework as a simple means of remembering the filter’s uncertainty. This can then be used to repopulate particles while closing loops. This not only handles non-linearities but is also robust for loop closing because, unlike the Particle Filter, the Information Filter does not exhibit forgetfulness of the trajectory’s past. Thus we have both an offline method (the first method) and an online approach (the second method) combining the Particle Filter and the Information Filter. 3. Collision Avoidance in dynamic environments with a k step look ahead : The problem of dynamic collision avoidance has been the mainstay of reliable navigation systems in dynamic environ- ments. One of the main problems with certain standard dynamic collision avoidance schemes, is that they fail to take into account the dynamics and kinematics of the robot while determining the best action. The resulting action, therefore, is often infeasible for the robot to execute. Other collision avoidance schemes, that tak

Abstract

Raytracing dynamic scenes at interactive rates to realtime rates has received a lot of attention recently. In this dissertation, We present a few strategies for high performance ray tracing on an off-theshelf commodity GGraphics Processing Unit (GPU) traditionally used for accelerating gaming and other graphics applications. We utilize the Grid datastructure for spatially arranging the triangles and raytracing efficiently. The construction of grids needs sorting, which is fast on todays GPUs. Through results we demonstrate that the grid acceleration structure is competitive with other hierarchical acceleration datastructures and can be considered as the datastructure of choice for dynamic scenes as per-frame rebuilding is required. We advocate the use of appropriate data structures for each stage of raytracing, resulting in multiple structure building per frame. A perspective grid built for the camera achieves perfect coherence for primary rays. A perspective grid built with respect to each light source provides the best performance for shadow rays. We develop a model called Spherical light grids to handle lights positioned inside the model space. However, since perspective grids are best suited for rays with a directions, we resort back to uniform grids to trace arbitrarily directed reflection rays. Uniform grids are best for reflection and refraction rays with little coherence. We propose an Enforced Coherence method to bring coherence to them by rearranging the ray to voxel mapping using sorting. This gives the best performance on GPUs with only user managed caches. We also propose a simple, Independent Voxel Walk method, which performs best by taking advantage of the L1 and L2 caches on recent GPUs. We achieve over 10 fps of total rendering on the Conference model with one light source and one reflection bounce, while rebuilding the data structure for each stage. Ideas presented here are likely to give high performance on the future GPUs as well as other manycore architectures. vi

Abstract

As complementary metal-oxide-semiconductor (CMOS) devices approach the nano-scale in feature size, the impact of noise in deep submicron devices pose challenges to reliable computing. An accompanying challenge to CMOS design is to achieve low-energy computation, which has been traditionally addressed by voltage scaling. However, the utility of voltage scaling is decreasing, as reduced voltage levels reduce noise immunity even further. Probabilistic computing provides a way to achieve low power computations in the presence of probabilistic behavior of devices by embracing a little error in the computations. Quick and accurate error-rate calculation is crucial for systematic design and performance evaluation of probabilistic circuits. Obtaining error-rates for probabilistic circuits using traditional circuit simulators, such as SPICE, is a prohibitively time consuming process, hence, this thesis develops methodologies for quick and accurate error-rate prediction of such circuits. We use the methodology developed by Lau et al. to predict the error-rates of probabilistic circuits. The most important factor on which the success of the methodology depends is the characterization of probabilistic circuit elements. While characterizing, one should look at the characteristics of noise, interconnection of circuit elements and their affect on the error-rates. This thesis studies the major features of noise in time domain, delay characteristics of the circuits and the loading effects in circuits while characterizing circuit elements. Considering all these factors, a modified model for characterizing circuit elements, which we call the three stage model, is proposed. Even though the three stage model enables one to estimate errors at the design level itself, the simulation/calculation time for obtaining error-rates of probabilistic circuit elements is quite large, thus, solving only one part of the problem, that is, accurate error-rate prediction. Therefore, a new method of characterization of circuit elements is proposed which is based on dynamic noise analysis of the three stage model and noise characteristics. A new statistical analysis of time domain noise, which we call structural analysis of noise, is proposed. We use the information gained by structural analysis of noise and dynamic noise performance of the three stage model of the circuit element under characterization to obtain its error-rates. It has been shown that the new procedure not only produces accurate results but is also computationally efficient than the previous approach, thus, enabling the methodology proposed by Lau et al. to not only predict error-rates of probabilistic circuits accurately but also quickly. Thus, this research proposes a quick and accurate method of predicting error-rates of noisy digital systems which may be of considerable interest to the modern digital design community as they may have to tolerate certain amount of errors while they try to minimize the power consumption.

Abstract

Vision based SLAM [11, 21, 23, 33, 51] and SfM systems [17] have been the subject of much research and are nding applications in many areas like robotics, augmented reality, city mapping. But almost all these approaches assume a static environment, containing only rigid, non-moving objects. Moving objects are treated the same way as outliers and ltered out using robust statistics like RANSAC. Though this may be a feasible solution in less dynamic environ- ments, but it soon fails as the environment becomes more and more dynamic. Also accounting for both the static and moving objects provides richer information about the environment. A robust solution to the SLAM problem in dynamic environments will expand the potential for robotic applications, like in applications which are in close proximity to human beings and other robots. Robots will be able to work not only for people but also with people. This thesis presents a realtime, incremental multibody visual SLAM system that allows choosing between full 3D reconstruction or simply tracking of the moving objects. Motion re- construction of dynamic points or objects from a monocular camera is considered very hard due to well known problems of observability. We attempt to solve the problem with a Bearing only Tracking (BOT) and by integrating multiple cues to avoid observability issues. The BOT is accomplished through a particle lter, and by integrating multiple cues from the reconstruc- tion pipeline. With the help of these cues, many real world scenarios which are considered unobservable with a monocular camera is solved to reasonable accuracy. This enables build- ing of a unied dynamic 3D map of scenes involving multiple moving objects. Tracking and reconstruction is preceded by motion segmentation and detection which makes use of ecient geometric constraints to avoid dicult degenerate motions, where objects move in the epipolar plane. Results reported on multiple challenging real world image sequences verify the ecacy of the proposed framework.

Abstract

Acoustic-phonetic speech segmentation is the process of detecting the acousticphonetic boundaries and labeling each segment with a phonetic symbol in the spoken utterance. In the scope of this thesis, we address issues related to acoustic-phonetic boundary detection. The first part of this thesis is focused on the different approaches for acoustic-phonetic boundary detection. Previous works indicate that, acousticphonetic boundary detection approaches can be broadly classified into two types, i.e., signal processing based approaches and classification based approaches. Signal processing based approaches typically rely on peak-picking algorithms on temporal trajectories of signal energy, sub-band energy etc.,. So, these approaches can operate independent of language and transcription. However, signal processing approaches are sensitive to parameters used and are less robust than supervised classifiers. On the other hand, supervised classifiers require hand labeled data to train classification models. Apart from the above approaches, there are also approaches which combine both acoustic-phonetic boundary detection and acousticphonetic segment labeling using hidden Markov model (HMM) forced alignment based approach which can be termed as constrained acoustic-phonetic speech segmentation approach. It should be noted that, signal processing based approaches are found to be highly sensitive to the parameters used and hence are less robust. Supervised classifier based approaches are limited by requirement of large amount of manually segmented data to train the classifier. Constrained acousticvi phonetic speech segmentation approaches are limited by requirement of a good transcription for both training and testing, which is very difficult to obtain. In order to over come these limitations, we are proposing a unsupervised discriminative classifier approach which does not require manually segmented data and phonetic transcription. The input to the discriminative classifier is obtained from boundaries automatically detected by signal processing based boundary detection approaches. We show that unsupervised classification based approaches perform better than signal processing based approaches and HMM based approaches. The second part of the thesis focuses on significance of linear prediction residual for acoustic-phonetic boundary detection in continuous speech. Alternate features extracted from LP residual (excitation based features) are explored to improve the performance of boundary detection.

Abstract

Analyzing the dominance relationship amongst points has become an important task in various applications such as tourism industry, sports and movie ranking. The goal of comparing the points in a dataset is not just computing the best points but also to look at interesting sets of points. Skyline queries address the problem of computing the interesting points by suggesting points which are not dominated by any other point in the dataset. In this thesis, we address the problem of computing strong and weak dominant set and dominated set over subsets of dimensions.

Abstract

The Internet is driven by a common internetworking protocol suite called TCP/IP. Within the suite, a network layer protocol named Internet Protocol version 4 (IPv4) exists. IPv4, with 32-bit address fields, was designed without anticipating the forthcoming flood of global community. At the time, the 232 address space was sufficient to support the few users. As the Internet grew with diverse networking demands and technologies, IPv4’s ability to support the size and the demands thereof was surpassed. The latest IANA’s address exhaustion reports project that the end days of unallocated IPv4 address space is a matter of months. Furthermore, the original design assumed trusted users; security was thus hardly an issue. The design favored interoperability over security and did not contain features that protected the confidentiality, integrity or availability of communications. Such incidents as the outbreak of the Morris worm that marked the dawn of a new era of Internet security are prime witnesses. Therefore, addressing these plagues was necessitated. For these nuisances, both short-term and long-term solutions have been put forward. Short-term ’solutions’ such as Classless Inter-Domain Routing (CIDR) and Network Address Translation (NAT) have prolonged the lifetime of IPv4 to some extent. As expected, these are time-bounded and ’patch- and-prolong’ solutions. To address the security issues, a protocol suite named Internet Protocol Security (IPsec) was then introduced to be used optionally,and not as a mandatory feature. On the other hand, IETF’s quest for a long-term solution gave birth to a new and backward-incompatible network layer successor protocol, Internet Protocol version 6 (IPv6). Put simply, IPv6 is the next generation Internet protocol designed to handle the unprecedented growth of the Internet and cope up with the very current networking requirements such as end-to-end security, Quality of Service (QoS), scalability and ubiquity. IPv6 is already gaining global momentum, even in production and mission-critical environments. Nations that did not benefit from the disproportionate IPv4 address allocation (e.g. Asia, Europe) have shifted their gears and efforts towards embracing it to the fullest. Even in parts where IPv4 relatively has a higher life expectancy (e.g. US), the effort is towards catalyzing the transition. For instance, the US federal agencies are mandated to be IPv6-ready from 2008 onwards. The bottom line is that a global migration to the IPv6 Internet is inevitable. IPv6 being on the horizon, studying its security notions is critically important. With increased addi- tion of unimaginable morphs of nodes (e.g. smart home appliances, cars, sensors, body-worn miniature devices, etc) to the Internet and the attacks thereof, the worth of this study can not be emphasized further. In this thesis, we have taken the initial stride of studying the security ramifications of IPv6’s key features, in the hope of laying a foundation for security of the next generation Internet. Generally, the research is centered around the following key objectives: 1. To identify vulnerability points of the protocol as early as possible. 2. To assess some of the proposed solutions in view of the threats identified. 3. To show the road map towards a more secure IPv6 world from the perspective of network protec- tion devices (NPDs) and existing as well as IPv6-specific [projected] security practices. To meet the first two objectives, in part I of the thesis, we have done an extensive threat analysis on prominent features such as Neighbor Discovery, Autoconfiguration, Extension Headers, Mobile IPv6 (MIPv6) as well as on deployment-related aspects like transition mechanisms. For a so-obvious reason, the analysis could not be exhaustive. In addition, we have done a comparative analysis of well-known existing attacks in the light of IPv6. The viability as well as the resistance to potential attacks of some of the proposed solutions such as Secure Neighbor Discovery (SEND), authentication solutions of MIPv6 and automatic IPv6-in-IPv4 tunneling protocols have also been analyzed. In part II of the thesis, we show the road map towards the detection and prevention strategies, in view of the threats analyzed in the preceding part. In this part, the inter IPv6-NPD issues and chal- lenges are explored and assessed in a reasonable detail from the perspective of veteran security devices: packet filters and deep packet inspection devices. Moreover, we present potential futuristic security architectures of the IPv6 world. We also forward recommendations and Best Security Practices (BSPs) based on the threat analysis done. These practices would pretty much serve as a stepping stone for more comprehensive next generational security practices.

Abstract

In a distributed network, where some of the nodes may be corrupt, a sender node s intends to com- municate securely with a distant receiver node r. If the network has sufficient connectivity, a protocol can be designed which enables this communication irrespective of the behaviour of corrupt nodes. In this thesis we consider two very different kinds of networks: synchronous neighbour networks and asynchronous unicast networks. We consider the case where some of the nodes in these networks, whose identities are not known a priori, can behave arbitrarily (or, even maliciously). We investigate the minimum connectivity required to facilitate the design of a protocol which enables a node to com- municate reliably with another node in a network of the former type, and to communicate reliably and privately in a network of the latter type.

Abstract

Synthesis of complex consonant clusters is a challenge in TTS systems, as it is dicult to ensure proper coarticulation. This problem surfaces in the synthesis of missing units in unit concatenation systems. Back-o techniques are used to synthesize these missing units. The current back-o techniques, which use smaller sub-word units to synthesize the missing unit, are found unsuitable for frequent usage causing severe degradation in synthesis quality. However missing units are a frequent occurrence when synthesizing unrestricted text. Hence to build open domain TTS systems, ecient back-o techniques are necessary. This problem is further aggravated when working with under-resourced languages as they lack the manually annotated speech corpora which enable the development of these high quality synthesis techniques. In this thesis we propose a two pronged strategy to improve the quality of back-o techniques. The two pronged strategy consists of rening the boundaries of units in the acoustic inventory to reduce phone insertion errors during back-o and use of a novel back-o technique to ensure coarticulation consistency. A boundary renement algorithm which removes necessity for manually labelled data by relying on a knowledge base of cost functions derived from landmark specic acoustic cues was proposed, to increase the quality of unit boundaries. However increase in accuracy of unit boundaries was insucient when context-dependent units are not available in the database. Hence a back-o technique which synthesizes complex consonant clusters even when the required context-dependent units are not available, was proposed. This technique is motivated from a phenomenon observed during second language acquisition and emulates native speaker intuition in synthesis of these clusters. The technique was proven to be better than the conventional backo  techniques. Further it was proven to be robust to segmentation errors, reducing the reliance on high quality segmentation techniques which require manually labelled data.