Abstract

Wireless Sensor Networks (WSNs) has been a research topic for more than a decade, and the range of potential applications has spanned beyond the military domain into commercial domains such as industrial/building/home automation, lighting control, energy management, to name a few. Emerging wireless technologies such as Zigbee and IEEE 802.15.4 have enabled the development of interoperable commercial products, which is important to meet the scalability and low cost requirements. A key feature for current WSN solutions is operation in unlicensed frequency bands, for instance, the worldwide available 2.4 GHz band. However, the same band is shared by other very successful wireless applications, such as Wi- Fi and Bluetooth, as well as other proprietary technologies. There is evidence that unlicensed spectrum is becoming overcrowded. As a result, coexistence issues in unlicensed bands have been subject of extensive research, and in particular, it has been shown that IEEE 802.11 networks can significantly degrade the performance of Zigbee/802.15.4 networks when operating in overlapping frequency bands. Till now WSNs are working in fixed spectrum allocation strategy. Using this strategy makes WSNs to interfere with other technologies in the same band. Studies sponsored by the Federal Communications Commission (FCC) pointed out that the current static spectrum allocation has led to overall low spectrum utilization where up to 70% of the allocated spectrum remains unused (called white space) at any one time even in a crowded area. The white space is defined by time, frequency and maximum transmission power at a particular location. Consequently, Dynamic Spectrum Access (DSA) has been proposed so that unlicensed spectrum users or Secondary Users (SU)s are allowed to use the white space of licensed users or Primary Users (PU)s spectrum, conditional on the interference to the PU being below an acceptable level. This function is realized using Cognitive Radio (CR) technology that enables an SU to change its transmission and reception parameters including operating frequencies. There are two prominent features of CR. Firstly, sensing is performed across a wide range of spectrum to identify the white space. Secondly, data packets are allocated opportunistically to the white space at different channels. This means that whenever a PU accesses a channel which has been regarded as white space by the SUs, the SUs must vacate the spectrum as soon as possible. Cognitive Radio based Sensor Networks (CRSN) are introduced to use DSA. In this networks sensor node is aided with cognitive radio. In CRSN SUs are WSN. WSN operates on battery power. Once they drain out of batter it is very difficult to replace them. Hence energy efficiency is more crucial in CRSN. This thesis addresses the problem of reducing energy consumption in Cognitive Radio based Sensor Networks (CRSN). For energy efficiency in CRSN, a spectrum aware architecture is proposed. In proposed architecture spectrum sensing network is decoupled from data aggregating network. Data gathering network is Wireless Sensor Networks (WSN). For data gathering Network energy efficient routing protocol and TDMA based MAC (Medium Access Control) protocol is proposed. In addition to this, a Fault Repair Algorithm using Localization and Controlled mobility to fill Network Holes is proposed. A cross layer design for routing and MAC layer, by using a light weight token-packet passing is proposed. A routing protocol by placing uniform virtual grid for topology aware WSN is also proposed. All these protocols are shown energy efficient when compared to existing protocols. On top of this, energy efficient network architecture for WSN using a novel Non-Uniform Sampling technique is proposed.

Abstract

A truly autonomous robot should be able to build a representation of the environment on its own and be able to navigate between any two points in the environment based on the representation it has built. Also, it should be able to determine its location in the environment from its sensor readings. The representation built by the robot is called a map, and there are different mapping paradigms, which vary from capturing the topology of the environment, to getting fine metric details. Each paradigms have their own pros and cons. To build the map on its own, the robot has to explore. The exploration strategy should be such that the robot builds the map completely in reasonable amount of time. Exploration is a vital cog in the automation of the mapping process. The effectiveness of the exploration strategy affects the quality of the maps produced. This thesis explores the merits of using the higher level knowledge called semantics during the pro- cess of exploration. The semantics is also incorporated in the map begin produced, thereby producing a three level hybrid map. The hybrid level mapping is especially interesting from the Personal Robotics stand point as it is now possible to interact with the robot at a higher semantic level, rather then a metric level. For eg; by the understanding that the environment consists of labs, offices and corridors, the robot can be asked to move from Lab A to office A, rather than saying move from Point A to Point B. This definitely decreases the difficulty in interacting with the robot by many folds. But at the same time, the map needs to have metric properties to enable safe navigation. Semantic understanding alone is not sufficient for the robot to carry out all the tasks. Hence the map should have all the properties which can ease human robot interaction as well as support safe navigation. A hybrid map is needed incorporating both metric and semantic properties and this thesis presents such a hybrid mapping framework. At the top level the map is a graph of semantic constructs. Each node in the graph is a semantic con- struct or label such as a room or a corridor, the edge represented by a transition region such as a doorway that links the two semantic constructs. Each semantic node embeds within it a topological graph that constitutes the map at the middle level. The topological graph is a set of nodes, each node representing an image of the higher semantic construct. At the low level the topological graph embeds metric values and relations, where each node embeds the pose of the robot from which the image was taken and any two nodes in the graph are related by a transformation consisting of a rotation and translation. The exploration algorithm explores a semantic construct completely before moving or branching onto a new construct. Within each semantic construct it uses a local feature based exploration algorithm that uses a combination of local and global decisions to decide the next best place to move. During the process of exploring a semantic construct it identifies transition regions that serve as gateways to move from that construct to another. The exploration is deemed complete when all transition regions are marked vis- ited. Loop detection happens at transition regions and graph optimization techniques are used to close loops when detected to obtain a consistent metric embedding of the robot poses. Semantic constructs are labeled using a visual bag of words(VBOW) representation with a probabilistic SVM classifier.

Abstract

Transfer Grammar Component is a major module in Rule-based Machine Translation (MT) systems. This module handles various levels of structural differences between the source and target languages. The objective of our system is to provide help to language experts for developing transfer grammar rules for various language pairs. The rule structure varies from shallow parsed, partial parsed to fully parsed structures. So, the aim here is to provide a notation and system which is rich enough to state rules using various levels of information. In this thesis we describe Transfer Grammar Engine (TGE) tool which is a major component of Sampark MT system, an MCIT, Govt. of India funded project for developing bidirectional MT systems for nine Indian language pairs. Further in this thesis we try to handle reordering in English-Hindi Statistical MT (SMT). “Reordering” is a sub part of Transfer Grammar Component which is a common phenomenon in language pairs of distant origins. In statistical machine translation (SMT) it has been an important topic since the beginning of the era. During recent developments syntax-based reordering have seen improvements in translation quality. We follow a pre-translation approach that adjusts the source sentence order to resemble the target order prior to translation. We describe an automated approach for learning reorder rules using the syntactic information of the source side training corpus with the word alignment information in a phrase-based SMT system. Later the source side of the training and the test corpus are reordered and given to the SMT system. Although the approach is examined within a pre-translation reordering framework, it easily extends to other frameworks. We demonstrate the effectiveness of our rules on English→Hindi translation task using EILMT tourism corpus. These reordering rules can be used in both statistical and transfer based MT systems. Major contributions of this thesis are (a) designing a working system for capturing structural differences using various syntactic information (b) an approach for learning reordering rules used for both statistical and rule based systems. The framework and methods presented in this thesis are independent of the language pair.

Abstract

This thesis deals with the problem of classification, detection and segmentation of objects in images. We focus on classes of objects which have considerable deformations, with the categories of cats and dogs as a case study. Many state of the art methods which perform well on the task of detecting a rigid object category, like bus, airplane, boats etc., have a poor performance on these deformable animal categories. The well known difficulty in automatically distinguishing between cats and dogs in images, has been exploited in web security systems: ASIRRA, a system developed by Microsoft Research, requires users to correctly select all cat images from the 12 cats and dogs images shown to them to gain access to a web service. Beyond this, the problem of classifying these animals into their breeds is a challenging problem even for humans. Developing machine learning methods to solve these challenging problems requires the availability of reliable training data. Here, the popularity of cats and dogs as pets provides a chance of collecting this data from various sources on the internet where they are often present in images and videos (together with people). As a part of this work, we propose: a novel method for detecting cats and dogs in the image; and, a model for classifying images of cats and dogs according to the species. We also introduce a dataset for fine grained classification of pet breeds, and develop models to solve the problem of classifying pet images according to the breed. In the process we also segment these objects. For detecting animals in an image, we propose a mechanism based on a combination of a template based object detector and a segmentation algorithm. The template based detector of Felzenszwalb et al. [43] is used to first detect the distinctive part of the object, and then an iterative segmentation pro-cess extracts the animal by minimizing an energy function based over a conditional random field using GraphCuts. We show quantitatively that our method works well and substantially outperforms whole-body template-based detectors for these highly deformable object categories, and indeed achieves accu-racy comparable to the state-of-the-art on the PASCAL VOC competition, which includes other models such as bag-of-words. For the task of subcategory classification, a novel dataset for pet breed discrimination, the IIIT-OXFORD PET dataset is introduced. The dataset contains 7;349 annotated images of cats and dogs of 37 different breeds. These images were selected from various sources on the internet. In addition to the pet breed, annotations include a pixel level segmentation of the body of each animal, and a bounding box marking its head. This data set is the first of its kind for pet breed classification and should provide an important benchmark for researchers working on fine grained classification. vi vii For the classification task, we propose a model to estimate a pet breed automatically from an image. The model combines shape, captured by a deformable part model detecting the pet face, and appear-ance, captured by a bag-of-words model that describes the pet fur. Two classification approaches are discussed: in a hierarchical approach a pet is first classified into the dog or cat species, and then clas-sified into its corresponding breed; and a flat one, in which the breed is obtained directly. For the task of breed classification, on our 37 class dataset, an average accuracy of about 60% was achieved, a very encouraging result considering the difficulty of the problem. Also, these models are shown to improve probabilities of breaking the challenging Asirra test by more than 30%, beating all previously published results

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.