Abstract

The current state-of-the-art text-to-speech systems use either statistical parametric synthesis or hybrid systems (a combination of statistical parametric synthesis and unit selection synthesis). In statistical based techniques, phones (along with their context) are used as basic units. A major issue is to model the trajectories and reduce the over smoothing effect. Longer units such as syllables are not straight-forward to model when compared to phones. In this thesis, we show how syllable HMMs are effective in generating a HMM based TTS system HTS). We will explore the issues in modeling these sub-word units, clustering them with different categories of features including contextual information of the phone, position and manner of articulation, linguistic and syntactic features. We will also present the advantage of using syllable based models in explicitly capturing the prosodic based characteristics. Later, we will propose an approach using longer size units such as syllable, and build a statistical template for each syllable using dynamic programming to inherently capture the trajectories. Two types of statistical templates are being used for synthesis: average and median. The technique can also avoid source modeling, as one could use median templates as exemplars to build concatenative speech synthesis system. Also, the effects of using local constraints in DTW has been explained with respect to average template based speech synthesis system. Experiments are conducted on Telugu, Kannada, Hindi and English speech databases. The subjective evaluations show that the statistical template based approach performs reasonably good. Finally, different prosody modification approaches such as time-domain and frequency-domain with their limitations are described. Mainly, prosody modification using instants of significant excitation and Mel-cepstral vocoder are explained in detail and a comparison of both the techniques over non-linear modification is discussed for integrating into TTS systems.

Abstract

In this thesis we present a mathematical model for applications in the area of energy. The mathematical model is based on Kalman Filter prediction and correction technique. Kalman Filter has been applied to predict the maximum power point of a solar photovoltaic array and also to forecast the load and schedule the load for smart grid. Maximum Power Point Tracking has been the key area for solar photovoltaic array. A lot of research has been going on in this area so that efficient solar inverters can be built for power transmission with minimum loss. MPP tracking requires a prediction and correction model when done in real time; hence we opted for Kalman Filter algorithm. Two types of Kalman Filter algorithms have been used for MPPT. The one is considering the whole system to be linearly varying i.e. considering somewhat ideal behavior of the panels hence we have used Discrete Kalman Filter approach for this purpose. However, in the real situation the behavior varies with irradiance and temperature hence ideally the system shows a non linear behavior. Hence, for that purpose we have used Unscented Kalman Filter approach. Using either of these approach the maximum power point tracking (MPPT) becomes much faster than using the conventional Perturb &Observe approach specifically in case of sudden weather changes. In this thesis comparative analysis of both the algorithms being implemented on FPGA is presented. Simulations have been performed under optimal conditions as well as under cloudy conditions i.e. falling irradiance levels. Using the linear Kalman filter the maximum power point of a solar PV array has been tracked with an efficiency of 97.11% while using the Unscented Kalman filter technique the maximum power point of the same solar PV array is tracked with higher efficiency of 98.3%. However, the maximum power point has been tracked at a much faster rate i.e. 4.5 ms using the linear Kalman filter approach as compared to the unscented Kalman filter approach which tracks maximum power point at 11 ms which is in turn faster than existing generic Perturb and Observe approach which takes 15ms to track the maximum power point . The system has been implemented on Altera EP2C20F484C7 FPGA board to check the number of resources being used. The FPGA based Kalman Filter has been used for load forecasting and that to focusing on short term load forecasting which leads to load scheduling for smart grid. With smart grids the forecasting becomes much easier as we would be receiving load consumption data at the household level. The information of load consumption can be obtained from smart meters already installed in smart grid. This problem also requires a good prediction and correction model so we again took Kalman Filter algorithm in consideration. For this case we have used only Discrete Kalman Filter algorithm based upon the parameters we have considered for load forecasting approach. The algorithm proposed in this paper uses load consumption and temperature of previous few days as parameters for estimation and this forecasted data is used for scheduling purpose. Estimation is done separately for Weekdays & Weekends/Public Holidays. Using the proposed algorithm the load has been estimated with absolute mean percentage error around 1.5% and the algorithm for load scheduling has been successfully implemented on the logic of FPGA.

Abstract

Processing a sentence for any practical application requires complete understanding of the syntactic and semantic structure of the sentence. Natural language parsers, are used to perform formal analysis of a sentence into its constituents(words or phrases), resulting in a parse tree showing their syntactic relation to each other. For example, which groups of words in a sentence go together as phrases and which words are the subject or object of a verb. Natural language parsers are generally two types, Rule based parsers- often constructs a parser given a grammar and data-driven parsers - construct a parser given a treebank (sentences with the whole syntactic information annotated in them in the form of tags and dependent relations). The accuracy of these parsers, both rule based and data driven often depends on the complexity of the sentence they are parsing. The complexity varies from the ambiguous structures/words, out of vocabulary words, loosely annotated syntactic information of a sentence like Parts-of-speech tags, syntactic relation between phrases or words etc. In case of data-driven parsers, they use knowledge of language processes from the sentences they learn on to produce the most likely analysis of new sentences, hence it is very important for the parsers to extract enough and proper information from the sentence before it parse. Consider an example like below where all the syntactic information like subject, object, verb etc is present in the sentence and it is easy for any application to extract complete information. Jon and Mary went to hospital Now, consider the following example ‘John can sing a song, and Mary can too’ Sentences like these are very common to appear in the treebanks, as the treebanks are created from a wide range of sources like articles, books, discourses. As mentioned earlier, to accurately predict the syntactic structure of these sentences, it needs the syntactic information annotated in them. Now, if we look at the example above, the complete syntactic information expected from the parsers are ‘John can sing a song, and Mary can (sing) too’ In the first example, ‘John can sing a song, and Mary can too’ Whether or not the verb ‘sing’ is included in this sentence is up to the speaker and to communicative aspects of the situational context in which the sentence is uttered. But, for the parser, the verb ‘sing’ along with its information like POS tag and its relation with other elements in the sentence, very important to be part of the sentence to parse it properly. The missing elements not only create a problem for parsing the sentence, but for any application that requires sentence syntactic understanding, for instance, information extraction, question-answering, and related semantic tasks, machine translation, parts-of-speech tagging, morphology etc. The more precise and detailed our predicate argument structures are (including empty categories), the more complete our event descriptions will be, and therefore the more effective our semantic processing techniques will be. We call these missing words/phrases as ‘Empty Categories’ or ‘Null Elements’. In this work, empty categories are retrieved in two ways: 1. Retrieve empty categories in sentence itself 2. Retrieve empty categories in parse trees while parsing Inserting in the sentence is handled statistically with the help of machine learning algorithms and by leveraging this method as a postprocessing step, i.e empty categories are inserted on the parser output. Then we will see how to detect and retrieve empty categories in a data-driven parser itself. We will then move to handle empty categories in Hindi dependency treebank by analysing and classifying the empty categories and then identify various discovery procedures to automatically detect the existence of these categories in a sentence. For this we make use of lexical knowledge along with the parsed output from a constraint based parser. Through this work we show that it is possible to successfully discover certain types of empty categories while some other types are more difficult to identify. This work leads to the state-of-the-art system for automatic insertion of empty categories in the Hindi input sentence and a generic approach to handle empty categories in any language dependency treebanks.

Abstract

The past decade has witnessed the emergence of participatory Web and social media, bringing together people in many creative ways. Millions of users are playing, tagging, working, and socializing online, demonstrating new forms of collaboration, communication, and intelligence that were hardly imaginable just a short time ago. Social Media refers to interaction among people in which they create, share and exchange information and ideas in virtual communities and networks. Social Media also helps reshape business models, sway opinions and emotions, and opens up numerous possibilities to study human interaction and collective behavior in an unparalled scale. In the study of complex networks, a network is said to have community structure if the nodes can be easily grouped into sets of nodes (even overlapping) such that each set of nodes is densely connected internally. Community structure are quite common in real networks. Social Networks often include community groups based on common location, interests, occupation etc. Metabolic Networks have communities based on functional groupings. Citation Networks form communities by research topic. Being able to identify these sub-structures within a network can provide insight into how network function and topology affect each other. In this thesis, we design an end-to-end framework for identifying communities from raw, noisy social media data. The framework is composed of two important phases. First, we introduce a new method of converting the raw, noisy social media data into a weighted entity-entity co-occurrence based consistency network. This includes a simple iterative noise removal procedure for cleaning the entity consistency network by removing noisy entity pairs. Secondly, we propose an approach for identifying coherent communities from the weighted entity network, by introducing novel notions of community-ness and community, based on eigenvector centrality. We use this framework to solve three different problems from two distinct domains. The first problem involves detecting communities from raw social media data and showing the application of the communities discovered in a recommendation engine setting. We use the framework for converting the raw data into a clean network and propose a highly parallelizable seed based greedy algorithm to detect as many communities as possible from the weighted entity consistency network. Our framework for community detection is unsupervised, domain agnostic, noise robust, computationally efficient and can be used in different Web Mining applications like Recommendation Systems, Topic Detection, User Profiling etc. We also design an recommendation system to evaluate our framework with existing state-of-art frameworks~cite{LDA,Farkas,bigclam} on a variety of large real-world social media data - Flickr, IMDB, Wikipedia, Bibsonomy, Medline. Our results outperform other frameworks by a huge margin. The second problem is, given a set of communities of discovered by traditional community detection methods~cite{Palla,Lancichinetti09}, we need to identify loose communities among them and partition them into compact ones. Here, we use the second phase of our framework to identify such loose communities using our notion of community-ness and propose an algorithm for partitioning such loose communities into compact ones. We illustrate the results of our algorithm over Amazon Product and Flickr Tag data and compare its superiority over the traditional community detection methods in a recommendation engine setting. The third problem is about showing the application of such framework in an Image Annotation scenario in presence of noisy labels. The problem of image annotation is defined to be, given an unknown image, we need to predict labels which best describes the semantics of the image. This problem is best solved in a supervised nearest neighbor setting, and we show how our framework can be used to address this problem, when the labels associated with training images can be noisy and redundant.

Abstract

Image matching is a well studied problem in the computer vision community. Starting from template matching techniques, the methods have evolved to achieve robust scale, rotation and translation invariant matching between two similar images. To this end, people have chosen to represent images in the form of a set of descriptors extracted at salient local regions that are detected in a robust, invariant and repeatable manner. For efficient matching, a global descriptor for the image is computed either by quantizing the feature space of local descriptors or using separate techniques to extract global image features. With this, effective indexing mechanisms are employed to perform efficient retrieval on large image databases. Successful systems have been put in place in desktop and cloud environments to enable image search and retrieval. The retrieval takes fraction of a second on a powerful desktop or a server. However, such techniques are typically not well suited for less powerful computing devices such as mobile phones or tablets. These devices have small storage capacity and the memory usage is also limited. Computer vision algorithms run slower, even when optimized for the architecture of mobile processors. These handheld devices, or so-called smart devices are increasingly used for simple tasks that seem too trivial for a desktop or a laptop and can be easily accessed on a smaller display. Further, they are more popularly used for taking pictures (gradually replacing the space of digital cameras) owing to the improved embedded camera sensors. Hence, a user is more likely to use a query image from the mobile phone, rather than from the desktop. This increases the scope of applications that demand real-time search and retrieval result delivered on a mobile phone. Many applications (or apps) on mobile smart phones communicate with the cloud to perform tasks that are infeasible on the device. People have attempted to retrieve images in this cloud-based model by either sending the image or its features to the server and receiving back relevant information. We are interested to solve this problem on the device itself with all the necessary computations happening on the mobile processor. It allows a user to not bother for a consistent network connection and the communication overheads associated with the search process. We address the range of applications that need simple text annotations to describe the image queried on the mobile. An interesting use case is a tourist/student/historian visiting a heritage site and can get all information about the monuments and structures on his mobile phone. Once the app is initialized on the device, the camera is opened and just pointing the camera or with a single click all the useful info about the monument is displayed on the screen instantly. The app doesn’t use the internet for communicating with any server and should do all computations on the mobile phone itself. Our methods optimize the process of instance retrieval to enable quick and light-weight processing on a mobile phone or a tablet. Firstly, we obtain a dataset of images relevant to the application’s scope, which is then curated and annotated for the task. This may seem a trivial task, but involves a great deal of manual labour when dealing with datasets of thousands of images. We efficiently address this with a batch annotation approach that results in detailed and part-wise image annotations. Then, we look into the primary problem of performing image retrieval on a mobile phone and propose variants of the Bag-of-words approach. A new indexing mechanism helps us to reduce the memory footprint by a large extent. It also reduces the computational requirements. Finally, we develop the mobile app using existing computer vision libraries for smart phones, keeping in mind a simple and user-friendly design for seamless use by a wide range of users. We validate our approach by using the standard benchmark datasets of Oxford-5K for our experimental purposes and also show results on Paris-5K and UKBench datasets. We demonstrate a working mobile app designed for a heritage site that successfully retrieves relevant information about a monument captured by the mobile phone.

Abstract

In Natural Language, Anaphora is an expression which refers to another expression in its context. This referred expression, called the antecedent provides the information for interpretation of the anaphora. In Natural Language Processing (NLP), Anaphora Resolution is the task of identifying the referent of the anaphora. Anaphora resolution is required in various NLP applications such as information extraction, summarization and Machine translation. While the task of anaphora resolution for English has been studied to a sufficiently great extent and various techniques have been proposed for it, the research for Anaphora resolution for Indian Languages has been very limited. Hence, in this thesis, we aim to develop resources and explore features and techniques for Anaphora Resolution in Hindi. There are three important contributions of this thesis. First, we developed an anaphora annotated corpus which is required for experiments in Anaphora resolution. Towards the development of this corpus, we proposed a scheme or framework for anaphora annotation. Our goal, with this scheme, is to identify and resolve various consistency issues associated with previous schemes or framework which are used for anaphora and co-reference annotation in English and other languages. Using the proposed scheme, we annotated anaphora references over Hindi Dependency Treebank. Second, we present a hybrid approach to resolve Entity-pronoun references in Hindi. Most of the existing approaches, syntactic as well as data-driven, use phrase-structure syntax for anaphora resolution, we instead, explore the utility of dependency structures as a source of syntactic information. In our approach, dependency structures are used by a rule-based module to resolve simple anaphoric references, while supervised learning algorithms are used to resolve more ambiguous instances using grammatical and semantic features. Our results show that, use of dependency structures provides syntactic knowledge which helps to resolve some specific types of references. Semantic information such as animacy and Named Entity categories further help to improve the resolution accuracy. Finally, we also conduct some preliminary experiments in Event anaphora and co-reference resolution. Similar to Entity anaphora resolution, for event and co-reference resolution too, we explore use of dependency structures in a rule based settings. Our experiments show that even with limited data and using simple syntactic and semantic constraints, reasonable resolution accuracy can be achieved for Event anaphora and co-reference resolution.

Abstract

This thesis was based on the idea of developing assistive systems for search and rescue and rehabilitation. Imagine a search and rescue scenario. Say there is an earthquake or a tsunami and there is lot of debris with people stuck under the debris. If we can improve the process of search then the rescue would come even faster and more lives would be saved. One part of the disaster management is to provide people affected with the disaster assistive systems to improve the quality of life. With this intention several robots and assistive systems are presented in this thesis.Real biological snakes have the ability to traverse several kinds of terrain. They can swim in water, climb trees, go over desert sand and go over step like terrain. So if me model robots with the snake structure in design then we can overcome challenging terrain which is typical to a rescue scenario. With that in mind we designed 5 different kinds of modular units of snake robot. We also were able to make the snake transition gaits autonomously from one part of the terrain to another. To over come slope like obstacles we designed a 6 legged robot that has a robotic spine. By controlling the amount of current in the robotic spine, we controlled its effective torque and were able to show compliance to slope while climbing up and climbing down. We also designed a universal simulator and controller plugin to reduce the fabrication time and simulate virtual models very close to its real counterpart robotic prototypes. Working on the modular design of the snake robot we engineered a new modular for modular snake like arms which was later extended to robotic hand. The robotic hand uses modular joints where each joint is composed of a pair of rolling magnetic spheres. In this attempt we ended up designing a robotic hand with the highest degree of freedom in the world. We have been working on assistive systems like camera mouse which allows a physically challenged person to use a computer. This research in HCI lead to controlling a snake robot with natural and intuitive gestures. We also designed a quake and crash alert system. We designed an intelligent flash light which can be used by a rescue worker to move in unknown places. The torch light uses a GPS,a laser projected micro projector and guides a person from a source to a destination. The work done here uses a combination of inputs from HCI and robotic system building to make search and rescue better. It also reduces the time for the human in loop during rescue

Abstract

FPGA based robotics is seen to gain popularity due to low cost, portability, seamless interface to hardware and most importantly due to inherent parallelism enshrined in various robotics algorithm. FPGA makes it possible to implement highly parallel architectures which, when compared to conventional sequential implementations, show clear advantages in terms of response time, over-all processing time and power dissipation. The parallelism makes it possible to do processing of data and collection of data simultaneously in a hybrid parallel-pipelined fashion. Such architecture makes the response time on FPGA much less than that on a processor with considerable higher clock frequency. Obstacle avoidance is one of the most fundamental problems in robotics. When the robot is the only mobile object on the map we call the problem as static obstacle avoidance. When the environment has other mobile entities apart from the robot that environment is a dynamic environment. The collision avoidance in such environment is called as dynamic obstacle avoidance. There are many strategies and corresponding algorithms to perform dynamic obstacle avoidance. Collision avoidance using velocity obstacle is one of the strategies followed for the dynamic avoidance. When acceleration constraints are also considered the approach is called as acceleration velocity obstacle. When only robots are there and they share the responsibility in the task of avoidance it is called as reciprocal collision avoidance. This algorithm is chosen as candidate for verifying and evaluating of the proposed architecture and system because this algorithm has a great scope of parallelization in it when implemented at gate level. This algorithm clearly brings out the advantage of a pure hardware gate-level implementation over the sequential fetch-decode-execute mechanism of a general purpose processor. There are two principal contributions of this thesis. Firstly, a novel hybrid parallel-pipelined architecture is designed and implemented on FPGA. This architecture has been designed based on the algorithm and simulations are done. Comparison between the proposed architecture and conventional sequential architecture is done. Secondly, a FPGA based distributed robotic system is built. The algorithm is implemented on this system and some real world testing is done so that the real world constraints can be taken into consideration. Comparison is done between proposed system and a general purpose processor based system. The advantage of gate-level implementation over the processor based implementation is that now we do not have to wait for the fetch-decode-execute cycle for each small instruction. FPGA can directly act on the data made available from sensors using the multipliers, adders etc., which are implemented using basic gate level designs. In such an implementation the only delays are the gate delays, which are negligible, making the system to work at a faster speed at a considerably lower clock frequency. A considerable advantage in terms of power dissipation is also observed in this FPGA based implementation. The specific advantages of developing a Field Programmable Gate Array (FPGA) based robotic system are portrayed in this thesis. This has been demonstrated through a multi-robot collision avoidance based on Acceleration Velocity Obstacle (AVO). FPGA offers highly parallel hardware architectures realized as gate level implementations that are not possible on conventional high end processors or other embedded controllers. A significant reduction in computation is observed on a slower 50 MHz RISC processor running on Xilinx Spartan 3E FPGA when compared with a 1.3 GHz Intel Atom processor used in cell phones. Substantial power savings are also reported. Implementation of this architecture on a distributed set of robots each controlled by an onboard Xilinx Spartan 3E-500 FG320 FPGA further confirms the efficacy of the architecture as well as fidelity of FPGA as a popular choice for control of robotic systems.

Abstract

The shared whiteboard model for distributed computing is one of the recent interesting models proposed by Becker et al. in [3]. In its basic form, this model allows all nodes to write a message of no more than O(log n) bits on a whiteboard that every node can read. However, each node can write at most once. In this model, a variety of problems from graphs are shown to be either possible or impossible. In this work, we extend the work of Becker et al. [3], to allow for nodes to write on the shared whiteboard more than once. However, each node can write at most O(log n) bits at any one instant. Interestingly, in this model, we show that allowing just two rounds of writing on the whiteboard, one can color the vertices of a planar graph using 6 colors and that of a d-degenerate graph using d + 1 colors in the free asynchronous (FreeAsync) model. Similarly, we show that in two rounds we can find maximal independent set (MIS), whereas 2-ruling sets can be computed in one round in simultaneous synchronous (SimSync) models. We further show that for finding connected components in a graph, even O(1) rounds is not enough in general. We show that any deterministic algorithm that follows certain rules requires at least Ω(log(n)/ log(log(n))) rounds to find the connected components of an n-vertex graph. At the same time, we show the existence of a O(log(n)) round algorithm for the same in the SimSync model. On the other hand, in the free models, one round is enough to compute connected components. For a special class of graphs, where one graph is formed by replicating the other k times, we show that any problem π which cannot be solved in one round on the larger graph, cannot be solved even in k rounds on the smaller graph in the FreeAsync and FreeSync model. Thus, our results indciate that the multi-round shared whiteboard model has interesting consequences.

Abstract

Field Programmable Gate Array (FPGA) is gaining popularity in robotics applications due to low cost, portability, low power dissipation, high speed and seamless interface to hardware. On the other hand, robotics algorithms are mostly arithmetic in nature so they can be easily parallelized and implemented on FPGA. Asynchronous FPGAs have gained remarkable research interest over the last decade. Asynchronous circuits do not require clock signal and hence they consume much less power than their synchronous counter-parts. Response time can be improved by parallelizing the independent operations in the system. Among all kinds of asynchronous design styles, Globally Asynchronous-Locally Synchronous (GALS) design is considered a very promising way to implement asynchronous FPGAs. GALS architectures bring together the advantage of both synchronous and asynchronous architectures in one package. The current research focuses on a FPGA based GALS architecture implemented using three different design styles viz. sequential, resource constraint pipelined and hybrid parallel-pipelined model. Normally, in a GALS architecture, the top level sub-systems communicate asynchronously with each other, although each sub-system essentially, is synchronous in nature. The design shown in this thesis, has the sub-systems implemented using the GALS architecture too, and thus envisages a two-tier GALS architecture. A Controller based GALS is also proposed which helps in synchronization and generalization of the GALS architecture. Controller based GALS architecture helps in the reduction of power dissipation as it has the capability of switching off the sub-system which is not in use for the time being. The synchronization advantage of Controller is explained with some simulation results. Both structural and behavioral implementation of the main control unit is explained and the advantage of structural model over behavioral model is also portrayed. The thesis focuses on the implementation of a system on FPGA with the objective of parallelizing the computation over the configurable logic blocks (CLBs) of FPGA. The GALS architecture when realized on FPGA shows its efficiency in terms of power, resources and response time in comparison with the conventional architecture. The GALS architecture based system has been implemented with three standard architecture design styles viz., hybrid pipelined, resource constrained and sequential and compared with conventional state machine architectures. Due to the asynchronous design, a good amount of logic in the hardware becomes combinational logic and hence the total resource utilization of the architecture is 35% less as compared to the conventional state machine architectures. The power-delay product (PDP) in case of GALS architecture based on the different design styles is nearly half of that of the conventional architectures. A significantly reduction in the computation time on a slower 50 MHz RISC processor running on Xilinx Spartan 3E FPGA has been observed when compared with a 1.30 GHz Intel Atom processor used in cell phones on the basis of its performance based on Reciprocal Collision Avoidance algorithm. FPGA also has much better response time when compared with a Intel Core i7 Extreme Edition 965 CPU at 3.20 GHz with 4 SMT CPUs. Using the same algorithm, the power dissipation of the Intel Atom Processor increases exponentially with the increase in the number of robots while, on the other hand, the rise is marginal for FPGA. These comparisons show the clear advantage of using the FPGA instead of a general purpose processor for robotic system design.The GALS architecture was also used to successfully implement the Collision Avoidance algorithm on an FPGA, even in case of an 8-robot problem, in-spite of the resource limitation on an FPGA.