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.

Abstract

With technological advancements, more and more content is becoming available in digital form on a regular basis. Such overwhelming amount of available data has lead to the problem of information overload. This has led to an increased interest in developing methods that can help users to effectively navigate, summarize and organize this information. The ultimate goal is to help users find what they are looking for. Significant efforts have been made to encounter challenges posed by information overload in web-domain. These efforts include exploitation of text-content as well as links (present as URL in web-pages). Interestingly, phenomenon of data explosion isn’t limited to web-domain but also observed in various other domains as well. Though the nature of challenges induced by information load is quite the same across all domains, uniqueness of a domain demands specialized solution. Unsurprisingly, efforts have been made to build information retrieval system in other domains by extending the popular notions developed for web-domain retrieval systems. In this thesis, we made an effort to address one of the challenges in legal domain and investigated the problem of finding similar legal judgments. In legal domain, information overload has adverse effect on finding similar judgments, which is a crucial task for a lawyer to prepare his arguments. Due to enormous number of judgments available, a lawyer needs to browse through hundreds of legal judgments to find a set of legal judgments similar to a given judgment ‘J’ and hence finds this task tiring and time consuming. In order to find similar legal judgment, he starts browsing legal database using his knowledge and experience. Once he finds an older judgment (say judgment ‘J’) which adequately satisfies his requirements, he starts looking for more judgments similar to judgment ‘J’ for comprehensive analysis of the legal principle applied in those judgments. Since number of judgments in legal database is enormous and, in general, size of each judgment is huge, an automated mechanism for finding similar legal judgments turns out to be a non-trivial problem. Textual information and its accessibility play a particularly important role in legal domain. The amount of available text-data in legal domain is vast and continuously growing which makes it challenging to deal with. Apart from the size of data, the inherent complexity of legal domain demand better and more sophisticated methods to process legal documents to satisfy information need of legal practi- tioners. To begin with, we investigated the issue of finding similar legal judgment by exploiting various attributes of legal judgments. We conducted our experiment on real world dataset and found that, text-content of judgments is not as effective as links (known as case-citations) available in legal-judgments, for finding similar legal judgments.

Abstract

Queue is required when service provider is not able to handle jobs arriving over the time. In real life, job execution often requires human intervention in it’s execution. In a highly flexible and dynamic environment, some jobs might demand for faster execution especially when resources are limited and jobs are competing for acquiring resources. Thus, user may demand for speed up (reduced wait time / faster execution) for some of the jobs present in the queue at run time. In such cases, it is required to accelerate (directly sending the job to the server) jobs requesting for speed up ahead of other jobs present in the queue to facilitate earlier completion of urgent jobs. Since no additional resources are used, therefore such acceleration of jobs might result in slowing down of other jobs present in the queue. In this thesis, we model the problem of Speed Up Scheduling without acquiring any additional resources for the scheduling of on-line speed up requests posed by the user at run-time. Speed Up scheduling needs to speed up all the jobs that requested for it without unnecessarily slowing down the other jobs. Note that it might not be possible to achieve speed up for all the jobs that requested for it as well as it might be the case that while speeding up jobs, even some of the jobs that requested for speed up were slowed down. In order to address Speed Up problem, we provide implicit Speed Up techniques where the notion of acceleration is incorporated in the priority function. We use concepts of queuing theory and discrete event based simulation model for the design and evaluation of our speed up algorithms. We apply the idea of Speed Up Scheduling to two different applications - Web Scheduling and CPU Scheduling. We demonstrate our results with a simulation based model using trace driven workload and synthetic datasets to show the usefulness of Speed Up in these domains. We further examine how different scheduling algorithms can be compared based on speed up/slow down characteristics.

Abstract

With the widespread application of digital data, there has been an increasing realization of the importance of multi relational data. Multi relational objects usually capture a variety of relations among different entities. For example, in recommender systems, the rating matrix captures the relation between movies and users, a social network captures relations among users, and the cast of the movie captures the relation between movies and users, the social network captures relation between movies and actors/actressess. The multi relational analysis problems deals with the following tasks  Partition the dataset into multi-relational clusters.  Prediction of values when entries are missing. Clustering and missing value prediction gives us a better understanding of the data. For example, clustering on movie ratings dataset, could help us understand movies watched and the movie ratings provided. This also helps us to recommend movies to users and prediction of missing values. Rapid growth of digital data has brought data involving objects of multiple types. A major challenge is to deal with multiple types of data simultaneously to utilize their interrelatedness. A major challenge in developing simultaneous clustering technique is to effectively use available information contained in multi relational data namely inter type and intra type constraints. In this thesis we are concerned with various relational learning tasks by analyzing Matrix Factorization (MF) models and its extension using the Matrix TriFactorization approach. While MF models have analyzed a single class of relations, we present how TriFactorization models with constraints called inter and intra relations in Sec 4.1 can be included in the model. The experiments have been carried out in tasks discussed in Section 5.1 for link prediction and relation prediction problems. We extend the relation prediction task withentity ranking, i.e given a triple with incomplete or missing information, can we find the missing entity ? These experiments help us establish to learn from multi-relational data and we compare to learning from single relations establishing the benefits of learning from multi relational datasets.

Abstract

The compiler optimizations we enable and the order in which we apply them on a program have a substantial impact on the program execution time. There are an infinite number of possible optimization sequences that can be applied to a program and since the runtime of any program is highly dependent on the optimization sequence that was applied to it, the problem of finding the right optimization sequence is of vital importance and is a long standing issue for compiler writers. Modern optimizing compilers typically have several code-improving phases, most of which can be applied in any order. These phases interact by enabling or disabling opportunities for other optimization phases to be applied. As a result, varying the order of applying optimization phases to a program can produce different code, with potentially significant performance variation amongst them. Moreover, finding the optimal optimization sequence for even a single program is hard as the space of attempted optimization phase sequences is huge and the interactions between different optimizations are poorly understood. In this thesis we propose two different solutions to the problem of finding good optimization sequences. There are broadly two ways to attack this problem: iterative compilation methods or heuristic search techniques and machine learning based prediction models. In heuristic search techniques, we explore the space of optimization sequences by pruning out not promising paths and eventually arriving at a near optimal sequence. This approach requires a large number of iterations before we converge on an optimization sequence. In machine learning based prediction models, we learn the parameters of an optimization prediction model using a set of programs as training data. This is an off-line process. Later we can use the prediction model to determine which optimizations should be enabled or disabled on a given program. The advantage of this approach is that it requires only few runs of the program to identify the suitable optimizations that needs to be enabled on a program. However, this approach solves the problem only partially as the model does not tell the order in which the optimizations have to be applied. Any machine learning based classification algorithm may not be applicable due to the exponentially large number of available optimization sequences. There is no universal optimization sequence that will produce the best code for every program, since the best sequence depends on the characteristics of the program being compiled, the compiler, and the target architecture characteristics. Compilers (like gcc) provide default optimization sequences which can give good program speedup for most of the programs. As the default sequences have to optimize programs with different characteristics, they embed in them multiple subsequences which can optimize different classes of programs. These multiple subsequences may falsely interact with each other and affect the potential program speedup achievable. Instead of searching for a single universally optimal sequence, we can construct a small set of good sequences such that for every program class there exists a near optimal optimization sequence in the good sequences set. If we can construct such a good sequences set which covers all the program classes in the program space, then we can choose the best sequence for a program by trying all the sequences in the good sequences set. This is the basis of our first solution. We developed a down-sampling technique to reduce the infinitely large optimization sequence space to a small set (of size in the order of hundreds). During the down-sampling process, the diversity of the optimization sequences catering to different program classes is retained. Using various techniques we constructed a small set of optimization sequences from the down-sampled sequence set, which cater a large set of programs with varied characteristics. This approach completely circumvents the need to solve the program classification problem. We tested this approach using Mibench and Polybench benchmark suite. Using a sequence set size of around 10 we got an average speedup up to 14% on PolyBench programs and up to 12% on MiBench programs. This approach is quite different from either the iterative compilation or machine learning based prediction modelling techniques proposed in the literature so far. We use different training and test data sets for cross validation as against the Leave-One-Out cross validation technique. Our second solution is a hybrid approach in which we use an iterative compilation technique in the training phase, and a simple prediction model based on nearest neighbourhood technique later on. The feature vector for a program in our prediction model consists of dynamic features of a program which are normalized hardware performance counters extracted through Intel Vtune Amplifier. The heuristic/iterative search is a onetime offline procedure.