Abstract

In the last few years, web technologies and thus social media have shown an immense growth. Social media allow users to share their experiences with others and influence connected people. Users can post their views and opinions in the form of blogs, reviews, status updates, tweets, etc. This large volume of data calls for quick and powerful automatic analytics system in order to gain useful insights about user’s tastes. Sentiment Analysis is a study of human behavior in which we extract user opinions and emotions from plain text. Sentiment Analysis is a combination of natural language processing, computational linguistics and information extraction and is applied to extract subjective information from text. Every textual information can be categorized into two main classes: Opinions and Facts. Facts are objective sentences describing some events or people or organizations which are not deniable. A good example of factual data are news articles. News articles contains the exact and correct information about the event. Opinions on the other hand are usually subjective expressions which describe people’s sentiments, feelings or emotions. The key task in sentiment analysis is to extract the attitude of the speaker or writer towards a subject. Sentiment classification can be considered as a two class (subjective vs objective) classification at top level which can be further segmented to two more classes (Positive and Negative). In general literature, sentiment analysis is primarily done as positive vs negative classification task with little (almost zero) focus on subjective vs objective classification. Web has proved to be a good source of subjective information (opinionated text) in form of reviews, blogs, forum posts, etc. but there are some cases where we face the problem of information overload. In this research, we worked on Product and Movie Reviews, Blogs and Tweets. Each of these genres of user-generated content exhibit some unique qualities which differentiate them from each other. Reviews range from few words to few paragraphs and generally talk about the specific object. Tweets on the other hand are just 140 characters and due to this character limit they are noisy, unstructured but object specific. Blogs are document like big and generally talk about one or more objects simultaneously. We can find hundreds of websites providing opinionated user-generated content, it is difficult to go through all and then make some decision. Thus, automated sentiment detection and summarization is an important task. From product and movie reviews, we extracted N-Gram based features with and without part-of-speech information and devised a scoring function to find the subjectivity expressed in the text. We also tested the same set of features on various supervised machine learning algorithms like SVM, NB, MLP, etc and proved the close correctness of our proposed scoring function. Sentiment lexicons also prove to be a useful resource in identifying the polarity of opinion expressed in text. We use SentiWordNet as our base lexicon to identify the opinion expressed in reviews. Our methods outperform the previous benchmark accuracies by 3-5%. Tweets are 140 character status updates and suffer largely in their structure and other grammatical errors. Its hard to apply NLP tools or basic rules to extract sentiment information from tweets because of its anomalies. We present a basic method to pre-process, restructure tweets and mine opinions expressed in them. We use two different datasets and perform 5 fold cross validation of our approach. Also we tested our approach on cross dataset training and testing. Proposed methods in this research show an improvement of 2-4% in classification accuracy. For English blog analysis, we propose a novel approach to perform sentiment mining and summarization based on objects (entities) in the blog. It is difficult to perform sentence level or document level sentiment classification in blogs because of their long size (in general) and contextual flow. Using basic NLP tools available, we first identify potential objects and then associated opinion towards each of these objects. Major contribution made in thesis are • Scoring function for review classification: This function can be used as a replacement to heavy duty machine learning algorithms. • Feature segregation as NLP-based and Twitter-specific features, correct pre-processing techniques for tweets. • A novel approach towards entity centric opinion mining from blogs along with entity specific opinionated dataset for English blogs. Keywords: Sentiment Analysis, Opinion Mining, User-generated Content, Blogs, Twitter, Movie Reviews, Product Reviews

Abstract

We describe the Symbiotic Software Engineering approach to produce field deployable and maintainable software systems using diverse modules developed out of distributed effort loosely tied together. These systems are heterogeneous made of different modules written in different programming languages and at different level of software engineering. This approach has been successfully applied on Machine Translation (MT) systems for nine major Indic languages in eighteen directions developed by a consortium of eleven academic/research institutions. As a result, we have engineered and deployed Sampark MT systems at http://sampark.org.in. Further a tool called Dashboard, has been developed which is based on pipe-line blackboard architecture for integration and testing of Natural Language Processing (NLP) applications. The Dashboard helps in testing of a module in isolation, as well as integration and testing of complete integrated systems. Functional module developer can avail and configure, if they so desire, the dynamic cache facility offered by the tool. It is also equipped with a user-friendly visualization tool to build, test, and integrate a system (or a subsystem) and view its component-wise performance, and step-wise processing as well. This caching facility improves performance of modules up to 20%. We have also described an approach to make MapReduce framework applicable for computationally intensive application like MT system. This framework helps to enhance the throughput of MT system uniformly by deploying it on large cluster of physical or virtual machines. Cloud gives us on-demand computing resources, so with the availability of elastic computing resources through cloud environment the completion time of any MT job irrespective of its size can be delivered within a short time.

Abstract

Learning representations for computer vision tasks has been the holy grail for the vision community for long. Research in computer vision is dedicated towards developing machines that understand image data, which takes a variety of forms such as images, video sequences, views from multiple cameras, high dimensional data from medical scanners and so on. Good representations of the data intend to discover the hidden structure in it; better insights into the nature of the data can help choose or create better features, learn better similarity measures between data points, build better predictive and descriptive models, and ultimately drive better decisions from data. Research into this field has shown that good representations are more often than not task specific: there is no single universal set of features that solves all the problems in computer vision. Consequently, feature learning for computer vision tasks is not a problem, rather a set of problems, a full fledged field of research per se. In this thesis, we seek to learn good, semantically meaningful representations for some of the popular computer vision tasks, such as visual classification, action recognition and so on. We study and employ a variety of existing feature learning approaches, and devise novel strategies for learning representations on these tasks. Additionally we compare our methods with the traditional approaches. We discuss the design choices we make, and the effects of varying the parametric variables in our approaches. We provide empirical evidence to show our representations are better at solving the tasks at hand than the traditional ones. To solve the task of action recognition, we devise a novel PLS kernel that employs Partial Least Squares (PLS) regression to derive a scalar measure of similarity between two video sequences. We use this similarity kernel to solve the tasks of hand gesture recognition and action classification. We demonstrate that our approach significantly outperforms the state of the art approaches on two popular datasets: Cambridge hand gesture dataset and UCF sports action dataset. We use a variety of approaches to tackle the popular task of visual classification. We describe a novel hierarchical feature learning strategy that uses low level Bag of Words visual words to create “higher level” features by making use of the spatial context in images. Our model uses a novel Naive Bayes Clustering algorithm to convert a 2-D symbolic image at one level to a 2-D symbolic image at the next level with richer features. On two popular datasets, Pascal VOC 2007 and Caltech 101, we demonstrate the superiority of our representations to the traditional BoW and deep learning representations. Driven by the hypothesis that most data, such as images, lies in multiple non-linear manifolds, we propose a novel non-linear subspace clustering framework that uses K Restricted Boltzmann Machines (K-RBMS) to learn non-linear manifolds in the raw image space. We solve the coupled problem of finding the right non-linear manifolds in the input space and associating image patches with those manifolds in an iterative Expection Maximization (EM) like algorithm to minimize the overall reconstruction error. Our clustering framework is comparable to the state of the art clustering approaches on a variety of synthetic and real datasets. We further employ K-RBMs for feature learning from raw images. Extensive empirical results over several popular image classification datasets show that such a framework outperforms the traditional feature representations such as the SIFT based Bag-of-Words (BoW) and convolutional deep belief networks. This thesis is an account of our efforts to do our bit to contribute to this fascinating field. We admit that research in this field will continue for a long time, for solving computer vision is still a distant dream. We hope that we have earned the right to say one day, in retrospect, that we were on the right track.

Abstract

This thesis describes the work done by me in design and development of single-robot and multi-robot exploration systems under constrained scenarios in both - structured and unstructured environments. For single robot exploration, a system was developed for road network exploration in outdoor environments with the constraints being in terms of available hardware (only camera and 2D laser range-finder for environment perception and a single laptop computer for computation) and exploration scope (vehicle moves on and explores roads only). A major challenge in designing such a system is that the uncertainties in the outdoor environment are already very high and when such additional restrictions are added in terms of hardware, the perception of environment becomes even more difficult. Apart from the physical contribution as a new platform for road network exploration, work on this system also contributed to the development of two new road intersection detection algorithms. The work on multi-robot exploration involved development of algorithms or strategies for efficient deployment of multiple robots, under a constraint that the robots should maintain continuous connectivity with a fixed base-station. Along with the continuous base-station connectivity, it is inherently expected that the system should be able to work with minimal robot hardware primarily consisting localization and mapping sensor(s) and driving actuators. Exploration of large areas using multiple robots is made possible under this constraint by using some robots as repeaters and thus, maintaining connectivity via a network with a hop chain or tree to the base station. Two strategies, termed as Hinged Chain Method (HCM) and Hinged Tree Method (HTM) with HTM being an improved version of HCM, have evolved through our work on multi-robotic exploration using this concept. HCM involves a sequential process of extending a hopping chain i.e. a chain of robots acting as repeaters from the base-station to far areas and reconfiguring the chain in a Depth- First Traversal fashion for various directions at every node. On the other hand, HTM is a two-phase parallel method evolved from HCM, which extends a tree and then subtrees in a recursive fashion to the far areas. In extreme cases (exploration tree depths of the order of number of robots), HTM gracefully degrades to HCM due to a heuristic cascade in our implementation. The proposed methods can also be further extended for 3D exploration scenarios, such as a building with multiple floors or rubble as it uses a tree/graph network to represent the connectivity map. These methods are believed to be very useful for the scenarios where a large number of low-cost robots need to be deployed for exploration under hazardous conditions such as Search and Rescue Scenarios, Planetary Exploration and military reconnaissance. The work done in these exploration systems also uncovered some common aspects in the design of constrained exploration systems, which are also presented in the conclusion of the thesis These aspects have a good scope for further research from system design and integration perspective when considering constrained exploration systems.

Abstract

Accurate and Robust estimation of optical flow continues to be of interest due to the deep penetration of digital cameras into many areas including robot navigation and video surveillance applications. The canonical approach to the flow estimation relies on local brightness constancy which has limitations. In this thesis, we re-examine the optic flow problem and formulate an alternate hypothesis that optical flow is an apparent motion of local information across frames and propose a novel framework to robustly estimate flow parameters. Pixel-level matching approach has been implemented according to the proposed formulation in which optical flow is estimated based on local information associated with each pixel. Self information and a variety of divergence measures have been investigated for capturing the local information. Results of benchmarking with the Middlebury dataset show that the proposed formulation is comparable to the top performing methods in accurate flow computation. The distinguishing aspects however are that these results hold for small as well as large displacements and the flow estimation is robust to distortions such as noise, illumination changes, non-uniform blur etc. Thus, the local information based approach offers a promising alternative to computing optical flow. We also developed a method to remove motion blur from frames by using the information measures. The effectiveness of the proposed motion estimation approach is also demonstrated on extraction of structure from motion of synthetic microtexture patterns, cardiac ultrasound sequences and colorization of black and white videos.

Abstract

Edge detection is an important image processing technique with wide range of applications. Several edge detection algorithms have been developed in the past few decades, however no single algorithm is suitable for all types of applications. Face recognition is one such important application in which edge detection plays a key role. Edge maps help in representing faces as a single unit. Here we survey the existing edge detection techniques and their suitability for extracting edges from facial images under noisy conditions. Then we introduce the proposed algorithm which is optimized for extracting edge maps from facial images under normal and noisy conditions. We employ several improvised techniques suitable for facial images. Composite gradient variation measures help in removing spurious edge points from edge maps. Using weighted wide convolution kernels reduce noise in the image while preserving the genuine edges. Similarly, low thresholding and dual maxima detection extracts edge points along face boundaries, curvatures etc... Also the proposed method is a gradient based technique which employs partial first derivates of the image maps. Generally gradient based techniques are computationally less intensive compared to other methods. The proposed method is optimized for extracting edges from images corrupted by various types of noises. Performance of several existing edge detectors is severely degraded under noisy conditions. However, using the proposed method we are able to consistently detect good quality edge maps under various levels of noises. We demonstrate this by extracting edges from images degraded by Gaussian noise, Speckle noise and Salt and Pepper noise. For performance measurement and evaluation we use Pratt’s Figure of Merit and Signal to Noise statistics. Using these measures we have compared several conventional edge detection methods with the proposed method. Also we have run the proposed method on Berkeley’s BSDS500 image dataset and compared with Pb boundary detection algorithm. Experimental results are promising and show that we are able to extract slightly better quality edge maps both under zero noise conditions and under var- ious levels of noises.

Abstract

Widespread damage caused by some recent earthquakes has posed many new challenges to the research community to study near fault motion and its effects on the ground surface. Earthquakes in different geological regions show drastic variations in their effects, such as large surface upliftment/displacements of soil deposits and distinctly different near fault ground motions in contrast to the far field ground motions. Numerous researchers studied this phenomenon through experiments and tried to establish relationships between various parameters of soil and resulting surface ground motion characteristics. Carrying out the experiments to understand such behaviour itself was difficult, because of complexities involved in replicating the exact site conditions, considering all the necessary parameters of soil deposit and underlying bedrock. Many experiments of high precision are to be conducted to establish relationship between the ground motion and various parameters such as width of affected zone, soil properties, thickness of deposit and dip angle of fault. Moreover, shapes and locations of the surface rupture and its propagation through the soil deposit before reaching the ground surface, are important in city planning, especially in the design of critical structures that may be located near the zone of faulting. Numerical modelling allows investigation of effect of a number of aspects of the fault rupture propagation, which may be difficult to obtain from earthquake case histories or from experiments conducted on physical models. Additionally, the sparse coverage of recording stations limits the ability to capture ground motions close to fault ruptures. Therefore, numerical simulation of near fault ground motions is necessary to understand the severity of near fault ground motion in future earthquakes. In this thesis, the numerical method called Applied Element Method is explained along with its application in the fault motion analysis. Since the problem is related to the fault rupture propagation, a method is needed, which can handle the discontinuities. The methods based on continuum modeling face lots of complications when we want to apply it to the material that has discontinuities. The Applied Element Method (AEM) has many advantages with respect to the fault rupture problem. Using AEM, the crack initiation and propagation can be modeled in reasonable time by using the available parallel computing power. This method is used for studying the spatial variation of ground motion due to seismic bedrock displacement at the bedrock level. In the present study, the Applied Element Method is used to study the dip-slip faults subjected to seismic base fault movement. The method used here has been explained and validated with analytical and experimental studies with good comparable results. The preliminary modelling of dip-slip faults has been done using different slip rate values. Increase in the response on the surface due to decrease in rise time values has been seen. Influence of dip angle has been investigated and the change in the response due to the presence of lower velocity layer on the near fault ground motion has been studied. The results of the numerical simulation have explained many dynamic and geometric aspects of the reverse faulting. In all cases with different fault dip angle, there is greater ground motion on the hanging wall side compared to the ground motion of foot wall side. This effect is intrepreted as being due to two important reasons. First, the points on the hanging wall are closer to the fault plane and secondly, the trapped seismic energy in the wedge shape hanging wall leads to multiple reflections. The results from different dip angles indicate that the near fault ground motion is sensitive to the dip angle. Decrease in the ground motion with increase in the dip angle has been seen. The presence of lower velocity layer leads to the reduction in the ground motion on the surface due to inconsistency in the material properties along the rupture direction and also due to the reduction in the stress drop value, whereas the presence of lower velocity block on the hanging wall leads to the amplification of the ground motion at the place of the lower velocity block. Then, the fault rupture propagation is explored in presence of rock boulders and its effect on the surface peak ground acceleration. Surface faulting has been examined by keeping the boulder at different positions. Presence of boulders in the footwall and in proximity of the rupture zone increases the PGA value on the surface of hanging wall to a large extent, whereas the presence of boulder in hanging wall away from the rupture zone does not affect much on the surface ground motion. It has been seen that there is a considerable change in the rupture pattern in presence of rock boulder in the rupture zone. Recent ground-motion observations suggest that there is a considerable difference in surface-rupturing earthquakes

Abstract

Pneumoconiosis is an occupational lung disease caused by the inhalation of industrial dust. Despite the increasing safety measures and better work place environments, pneumoconiosis is deemed to be the most common occupational disease in the developing countries like India and China. Screening and assessment of this disease is done through radiological observation of chest x-rays. Several studies have shown the significant inter and intra reader observer variation in the diagnosis of this disease, showing the complexity of the task and importance of the expertise in diagnosis. The present study is aimed at understanding the perceptual and cognitive factors affecting the reading of chest x-rays of pneumoconiosis patients. Understanding these factors helps in developing better image acquisition systems, better training regimen for radiologists and development of better computer aided diagnostic (CAD) systems. We used an eye tracking experiment to study the various factors affecting the assessment of this diffused lung disease. Specifically, we aimed at understanding the role of expertize, contralateral symmetric (CS) information present in chest x-rays on the diagnosis and the eye movements of the observers. We also studied the inter and intra observer fixation consistency along with the role of anatomical and bottom up saliency features in attracting the gaze of observers of different expertize levels, to get better insights into the effect of bottom up and top down visual saliency on the eye movements of observers. The experiment is conducted in a room dedicated to eye tracking experiments. Participants consisting of novices (3), medical students (12), residents (4) and staff radiologists (4) were presented with good quality PA chest X-rays, and were asked to give profusion ratings for each of the 6 lung zones. Image set consisting of 17 normal full chest x-rays and 16 single lung images are shown to the participants in random order. Time of the diagnosis and the eye movements are also recorded using a remote head free eye tracker. Results indicated that Expertise and CS play important roles in the diagnosis of pneumoconiosis. Novices and medical students are slow and inefficient whereas, residents and staff are quick and efficient. A key finding of our study is that the presence of CS information alone does not help improve diagnosis as much as learning how to use the information. This learning appears to be gained from focused training and years of experience. Hence, good training for radiologists and careful observation of each lung zone may improve the quality of diagnostic results. For residents, the eye scanning strategies play an important role in using the CS information present in chest radiographs; however, in staff radiologists, peripheral vision or higher-level cognitive processes seems to play role in using the CS information. There is a reasonably good inter and intra observer fixation consistency suggesting the use of similar viewing strategies. Experience is helping the observers to develop new visual strategies based on the image content so that they can quickly and efficiently assess the disease level. First few fixations seem to be playing an important role in choosing the visual strategy, appropriate for the given image. Both inter-rib and rib regions are given equal importance by the observers. Despite reading of chest x-rays being highly task dependent, bottom up saliency is shown to have played an important role in attracting the fixations of the observers. This role of bottom up saliency seems to be more in lower expertize groups compared to that of higher expertize groups. Both bottom up and top down influence of visual fixations seems to change with time. The relative role of top down and bottom up influences of visual attention is still not completely understood and it remains the part of future work. Based on our experimental results, we have developed an extended saliency model by combining the bottom up saliency and the saliency of lung regions in a chest x-ray. This new saliency model performed significantly better than bottom-up saliency in predicting the gaze of the observers in our experiment. Even though, the model is a simple combination of bottom-up saliency maps and segmented lung masks, this demonstrates that even basic models using simple image features can predict the fixations of the observers to a good accuracy. Experimental analysis suggested that the factors affecting the reading of chest x-rays of pneumoconiosis are complex and varied. A good understanding of these factors definitely helps in the development of better radiological screening of pneumoconiosis through improved training and also through the use of improved CAD tools. The presented work is an attempt to get insights into what these factors are and how they modify the behavior of the observers.

Abstract

In the area of data mining, the process of frequent pattern extraction and association rule finds interesting information about the association among the items in a transactional database. The notion of support is employed to extract the frequent patterns. Several algorithms have been proposed to efficiently extract frequent patterns from the transactional databases. The frequent pattern mining often leads to the generation of huge number of frequent itemsets which might be found insignificant depending upon application or user-requirement. In this connection, the researchers have made efforts to mine the subset of interesting frequent patterns according to the needs and demands of the users. In the literature, various properties like periodicity, pattern-length, cost (utility) of a frequent pattern etc have been used to filter out the unwanted frequent patterns. Similiarly, for mining interesting association rules, several measures like 2, lift, relative-support have been proposed in the literature. In this thesis, we introduce a concept of extracting a subset of frequent patterns based on the notion of diversity. Normally, a frequent pattern may contain items which belong to different categories of a particular domain. For certain types of applications, it may be useful to distinguish between the frequent patterns with items belonging to different categories and the frequent patterns with items belonging to the same category. However, the existing approaches do not consider the notion of diversity while extracting the frequent patterns. We have conceptualized the problem of extracting diverse-frequent patterns from the transactional databases. As a part of this effort, we have proposed the interestingness measure, DiverseRank, to rank the frequent patterns based on the diversity within the items categories. Given a set of frequent patterns and a concept hierarchy, we propose an efficient approach to extract the diverse-frequent patterns. First, we propose an approach to extract diverse-frequent patterns by considering a balanced concept hierarchy. Later, we extended the approach to extract diverse-frequent patterns by considering an unbalanced concept hierarchy. We have employed an item-encoding technique to efficiently mine the complete set of diverse-frequent patterns. Experiments on the real-world and simulated data sets show that the class diverse-frequent patterns is a different type of knowledge patterns as compared to the frequent patterns.

Abstract

In this thesis, we present a methodology for coordination of multi-robot systems in an unknown environment with obstacles. The robotic systems need to coordinate and cooperate by following a strategy which helps them to move from one location to another in the environment, under the influence of one or many constraints. The multi agent systems explore the whole unknown environment during the course. The key task we have here is to allocate new points to the multi-robot systems such that maximum exploration is completed in minimum time, while maintaining the communication constraint with a moving base station the whole time. For this, we have experimented with two different frontier based exploration techniques. In the first case, we present a deployment strategy which maximizes the area coverage of the whole network while maintaining communication between each other. The method is based on the concept of artificial force fields, which is distributed, scalable and does not require prior information about the environment to be explored. This force field based method is used to control the robots motion while avoiding obstacles. Robots tend to move towards frontier points, from where they experience an attractive force, while they move away from obstacles, which exert a repulsive force. Care is also taken to ensure that no two robots move to the same location, so as to avoid common areas or sub maps during the exploration. Here, we also present an approach to deal with the deadlock and local minimum situations. Simulation results performed on different maps have shown that the robot pack is able to cover the map efficiently, while keeping the communication constraint intact. In our second technique, which is an adaptation, built to overcome the shortcomings of the first one, we present a frontier based multi-robot exploration algorithm akin to a depth first strategy that samples frontier points according to a metric function, which aims to maximize the information gain while minimizing the distance to be traveled to the frontier points. The algorithm is designed in such a way so as to accommodate the requirement of communication maintenance. Through an optimized framework, we also prove that the communication requirement between the multi-robot system is also maintained during transition from one point to another during the exploration process. Extensive simulations have been performed to show the adeptness of this method. This method is also compared to another frontier based exploration approach, which is based on population generation and utility calculation over the population. This method was extended to include the sensory visible areas and results computed. On comparison, it was found that our method fairs much better to the one based on utility function. This has been shown with the help of various graphs and simulations performed on various environments.