Abstract

Clustering algorithms have wide applications in Computer Vision, Data mining, Data Visualization, etc. Clustering is an important step for indexing and searching of documents, images, video, etc. Clustering large numbers of high-dimensional vectors is very computation intensive. CPUs are unable to handle such load and consume sometimes days and even weeks to cluster large data. GPUs are being used for general purpose computing of wide range of problems which require high computational power. Today’s GPUs deliver as high as 1.5 TFLOPs. The GPU has evolved over the time not only by increasing number of cores but also major architectural changes like faster access of data, more shared memory, threads per block, etc. Such changes have enabled the GPU programmers to exploit its architectural features to the fullest and achieve high performance. In this thesis, we focus on K-Means algorithm which is a widely used unsupervised clustering algorithm. We develop a GPU based K-Means implementation for large datasets; also we have used this implementation to develop a video organizing application. We present the design and implementation of theK-Means clustering algorithm on the modern GPU. All steps are performed entirely on the GPU efficiently in our approach. We also present a load balanced Multi-node, Multi-GPU implementation which can handle up to 6 million, 128-dimensional vectors. We use efficient memory layout for all steps to get high performance. The GPU accelerators are now present on high-end workstations and low-end laptops. Scalability in the number and dimensionality of the vectors, the number of clusters, as well as in the number of cores available for processing are important for usability to different users. Our implementation scales linearly or near-linearly with different problem parameters. We achieve up to 2 times increase in speed compared to the best GPU implementation for K-Means on a single GPU. We obtain a speed up of upto 170 on a single Nvidia Fermi GPU compared to a standard sequential implementation. We are able to execute single iteration of K-Means in 136 seconds on off-the-shelf GPUs to cluster 6 million vectors of 128 dimensions into 4K clusters and in 2.5 seconds to cluster 125K vectors of 128 dimensions into 2K clusters. Video data is increasing rapidly along with the capacity of storage devices owned by a lay user. Users have moderate to large personal collections of videos and would like to keep them in an organized manner based on its content. Video organizing tools for personal users are way behind even the primitive image organizing tools. We present a mechanism in this thesis to help ordinary users organize their personal collection of videos based on categories they choose. We cluster the PHOG features extracted from selected key frames usingK-Means to form a representation for each user-selected category during the learning phase. During the organization phase, labels from aK-NN classifier on these cluster centers for each key frame are aggregated to give a label to the video while categorizing. Video processing is computationally intensive. To perform the computationally intensive steps involved, we exploit the CPU as well as the GPU that is common even on personal systems. Effective use of the parallel hardware on the system is the only way to make the tool scale reasonably to large collections that will be available soon. Our tool is able to organize a set of 100 sport videos of total duration of 1375 minutes in about 9.5 minutes. The process of learning the categories from 12 annotated videos of duration 165 minutes took 75 seconds on a GTX 580 card. These were on a standard desktop with an off-the-shelf GPU. The labeling accuracy is about 96% on all videos. The ideas, approaches proposed in this thesis have been implemented and validated with experimental results. For large data-sets we developed a scalable, efficientK-Means clustering on GPU along with a Multi GPU framework and used it to develop a video organizer application providing high accuracy.

Abstract

With the advent of Web 2.0, Internet has been subdued by a group of applications which facilitate the creation and exchange of user-generated content. Such groups are collectively represented as Social Media which changed the phase of communication between individuals. Blogs, Internet forums, user reviews, chats, activities on social networking sites etc., are some of notable online forms of current social media. As the content of social interactions on these social media forms is increasing rapidly, it led to the problem of information overload. A user may find it difficult to go through millions of lines of different users to grasp the status of a topic. This problem can be dealt wisely by presenting crux of the content rather than the whole user generated text. Automatic extraction of important topics or attributes, and summarization of these topics may help in saving considerable human effort in understanding the content. Automatic summarization is always a classical solution for information overload problem. Summarization of news articles has been explored from theory to building satisfactory models, but summarization of user generated content has not been given much attention. This may be because of the amount of user content on the Internet is once not so signicant but later exponentially increased. In this thesis we study the text in user generated content focusing on its summarization using new extraction methodologies. We initially focus on deriving information extraction techniques for social interactions do-main. We identify extraction of important topics or attributes of a discussion as the first step towards successful summarization of social interactions. There have been developed many ways of extraction from structured text using natural language processing tools. But not much have been developed for information extraction in unstructured social media text. Hence we rst fo- cus on deriving extraction methodologies which can later enhance summarization. We refrained from using language processing resources in our extraction procedures to make sure their success in all domains of social interactions rather than the selected domain of experimentation. We made use of knowledge from external resources like Wikipedia and Web in harnessing the extraction quality. We used machine learning (regression) in judging the extracted output. We choose the scenario of online customer reviews for testing our extraction engine. As the online retail market is growing immense, it poses a large arena of products, their descriptions, customer and professional reviews that are pertinent to them. Reviews contain useful opinionated information about products and their attributes. Most of the product attribute extraction techniques in literature work on structured descriptions using several text analysis tools. However, attributes in these descriptions are limited compared to those in the customer reviews of a product, where users discuss more deeper and specic attributes. In this thesis, we propose a novel supervised domain independent model for product attribute extraction from user reviews. The user generated content contains unstructured and semi-structured text where conventional language grammar dependent tools like parts-of-speech tagger, named-entity recognizers, parsers do not perform to their expected levels. We used Wikipedia and Web to identify the product attributes from customer reviews. In later parts of this thesis we focus on summarization of user generated content taking help from our extraction modules. Our summarization work can be classied as extractive summarization where text units from the original content are used in summary production. The text units we choose for a summary are sentence level units. Our trained system picks sentences from the content and then rank them to produce summary. Sentence ranking is done by estimating the sentence importance through a combination of word level and sentence level features. We choose a scenario where summarization is very much needed. Sales/service chats in the present day E-commerce are crucial for customer support and growth of a company. These chats should be clearly analyzed and followed for product, service, agent and customer validation. Hence summarization of these chats can minimize considerable human eort. Here, we suggest a novel approach to eectively summarize sales/service chats by analyzing their structure and using Wikipedia. Our system outperformed classic text summarization systems when applied for social interactions.

Abstract

State estimation in power systems has carved itself a pivotal niche over the years in what is known as the Energy Management Systems (EMS). Its ability to compute the voltage magnitude and angle at every system node and thus the state of the system at a given operating point classified it as a major player in real time monitoring. However, research in the domain of state estimation is no more limited to the likes of estimating the system states alone. Nor it is limited to the network boundaries of the transmission system anymore. State estimation has really come of age today, especially with the role power engineers see it capable of playing in the modern smart grid when implemented on a larger scale. Its application is now done in a much wider perspective. It has gained significant ground in system security requirements, specifically applications like the contingency analysis which feed off the basic state estimator. The unprecedented stature it has gained over the years has understandably led to a compelling demand for its accountability. With the inevitable step-up in reliability requirements, the dependability of the power system network database which the state estimator is built on becomes a key factor. A simple or conventional state estimator however imparts very high or rather infinite confidence on the branch or line parameters of the power system network considered to be fixed. The state estimator consequently settles to a solution corresponding to the information regarding system conditions as of then and the known network parameters. This assurance makes the state estimator totally unaware of any existing network errors which actually culminate in erroneous interpretation of the state. The failure in updating the parameter database thus leads to inaccurate estimation which could bear heavily on post estimation analysis like security assessment. This led to the dawning of the concept known as network parameter estimation not very long ago. Literature on network parameter estimation is understandably not very large, but nevertheless, has thrown up quite a few techniques and algorithms. In this thesis, a particularly unique approach has been developed and implemented for a state estimator with network parameter errors. A 2 bus π equivalent model is contrived for every two buses in the power network which are connected. It claims a huge advantage of generic structure devoid of any anomaly like existence of a transformer tap or a multiple parallel line structure. The equivalent model parameters for any branch are the same and are thus much easier to estimate rather than evaluating different network components including transformer tap on different line structures. Thus the estimator implemented is independent of the type of connection between two buses as well as the type of component present on it. The correct information regarding the equivalent branch parameters is sufficient for an accurate state estimation. To provide a touch of completeness, there is a convenient provision for original parameters to be estimated from the equivalent once the correct state is estimated. The network parameter estimator requires a significant level of local measurement redundancy around the branch suspected to have the parameter error. Remote Terminal Units (RTU) on the field cannot telemeter points to the extent that power injections and power flows are available at will everywhere. In addition, the data communicated via RTU are not void of noise and communication delays. On the other hand, phasor measurement units (PMUs) have developed remarkably into a crucial link to reliable power system monitoring in EMS since their advent in early 80’s. A PMU capable of measuring the voltage phasor directly on the bus is not only more accurate compared to the conventional RTU, but also measures line currents which can be used to calculate the voltage phasors on the other end. The PMU can thus not only effectively improve estimator accuracy but double it up with measurement redundancy thus making it very applicable in the context of the problem in focus. The proposed state and parameter estimator is thus implemented in the combined presence of a pre-specified set of RTU measurements and strategically placed PMU. A comparative study is proposed to assess the improvement in the performance of the parameter-state estimator when modelled with PMU. Since PMU installations at every node of a power system is unlikely today as well as in a few years to come, optimally placing PMUs to observe the system completely would ensure uniform local redundancy for the parameter state estimator. The other significant contribution of the thesis is thus entirely dedicated to explore this angle in the form of novel techniques proposed to strategically place PMU to account for entirely different or rather contrasting scenarios. While one calls for redundancy in PMU installations at selected points, the other calls for addressing the more pra

Abstract

Natural languages are ambiguous at various levels of processing e.g. phonological, morphological, syntactical and semantically (Jurafsky and Martin, 2000). While the human brain is able to process language despite its ambiguity, computer systems face problems in dealing with ambiguity. In the context of natural language processing, machine translation, information extraction and Q&A, the study of relation is very important as it helps to understand the structure of language and find the correct relation for genitive constructions. Anchoring this research to study of relations, this study develops rules based on semantic and syntactic information to disambiguate the parsing of recursive genitive constructions. Hindi follows “Head-Last” rule (Christiansen and Devlin, 1997) where the last noun behaves as the head noun and the preceding nouns act as the modifiers of the head noun. Since in recursion, we have more than one preceding noun, there is ambiguity about which noun(s) is/are modifier(s) of the head noun. This research is set out to handle the ambiguity arising due to recursion in Hindi language. In this work, we limit ourselves to examine recursive genitive construction with maximum two modifiers occurring before the head noun. We argue that semantic and syntactic information can be used to disambiguate parsing of recursive genitive constructions. We develop six syntactic agreement rules and four semantic rules for parsing the construction under consideration. We implement the rules and achieve an overall accuracy level of 86.6%. In the process of developing semantic rules we identify some semantic relations that exist between noun and its genitive modifiers. In the present work, we postulate 35 semantic relations for noun-noun and five for noun–verbal noun. We utilize these relations to develop the semantic rules which are used to determine the correct parsing of recursive genitive constructions. The syntactic and semantic rules work in the following manner: a. First syntactic agreement rules are applied for parsing. b. If they fail, semantic constraints are checked. c. If the constraints are satisfied, semantic rules determine the parse.

Abstract

Associative Classification leverages Association Rule Mining (ARM) to train Rule-based classifiers. The classifiers are built on high quality Association Rules mined from the given dataset. Associative Classifiers are very accurate because Association Rules encapsulate all the dominant and statistically significant relationships between items in the dataset. They are also very robust as noise in the form of insignificant and low-frequency itemsets are eliminated during the mining and training stages. Moreover, the rules are easy-to-comprehend, thus making the classifier transparent. Conventional Associative Classification and Association Rule Mining (ARM) algorithms are inherently designed to work only with binary attributes, and expect any quantitative attributes to be converted to binary ones using ranges, like “Age = [25, 60]”. In order to mitigate this constraint, Fuzzy logic is used to convert quantitative attributes to fuzzy binary attributes, like “Age = Middle-aged”, so as to eliminate any loss of information arising due to sharp partitioning, especially at partition boundaries, and then generate Fuzzy Association Rules using an appropriate Fuzzy ARM algorithm. These Fuzzy Association Rules can then be used to train a Fuzzy Associative Classifier.

Abstract

Large scale reconstructions of camera matrices and point clouds have been created using structure from motion from community photo collections. Such a dataset is rich in information; we can interpret it as a sampling of the geometry and appearance of the underlying space. In this dissertation, we encode the visibility information between and among points and cameras as visibility probabilities. The condi- tional visibility probability of a set of points on a point (or a set of cameras on a camera) can be used to select points (or cameras) based on their dependence or independence. We use it to efficiently solve the problems of image localization and feature triangulation. We show how the conditional probability can be combined with other measures to prioritize a set of points (or cameras) for matching and use it for fast guided search of points for the image localization problem. We define the problem of feature triangulation as the estimation of 3D coordinate of a given 2D feature using the SfM data. Our approach can guide the search to quickly identify a subset of cameras in which the feature is visible. Other than image localization and feature triangulation, bundle adjustment is a key component of the reconstruction pipeline and often its slowest and the most computational resource intensive. It hasn’t been parallelized effectively so far. We also a present a hybrid implementation of sparse bundle adjustment on the GPU using CUDA, with the CPU working in parallel. The algorithm is decomposed into smaller steps, each of which is scheduled on the GPU or the CPU. We develop efficient kernels for the steps and make use of existing libraries for several steps. Our implementation outperforms the CPU implementation significantly, achieving a speedup of 30-40 times over the standard CPU implementation for datasets with upto 500 images on an Nvidia Tesla C2050 GPU.

Abstract

Capturing the shape and texture of large structures such as monuments and statues at very high resolution is extremely expensive, both in terms of time as well as storage space. In many cases the inner details are generated by surface properties of the material, and the appearance is statistically uniform. In this paper, we present an approach to add surface details to a coarse 3D model of an object based on two additional information: a set of images of the object and a high resolution model of the material that the object is made of. The material model that we employ is the Polynomial Texture Map (PTM), which captures the appearance of a surface under various illumination conditions. We use the observed images of the object as constraints to synthesize texture samples for each triangle of the object under any given illumination. The primary challenge is to synthesize a polynomial model of the texture, where the constraints arise in the image domain. We use the knowledge of object illumination to map the texture models into image space and compute the opti- mal patch. The texture transfer then happens as a complete 3D texturemodel. We also consider the problems of pose, scale, reflectance and smoothness of surface while carrying out the texture transfer. We synthesize the texture of an object at a per-triangle basis while carrying out operations such as normalization and blending to take care of discontinuities at the edges.

Abstract

Biometrics has a long history, and is possibly as old as the human race itself. It is often used as an advanced security measure to safeguard important artifacts, buildings, information, etc. Biometrics is increasingly being used for secure authentication of individuals and is making its presence felt in our lives. With the fast increase in computational power, such systems can now be deployed on a very large scale. However, efficiency in large scale biometric matching is still a concern as the problem of deduplication (removal of duplicates) of a biometric database with N entries is O(N2), which can be extremely challenging for large databases. To make this problem tractable, many indexing methods have been proposed that would speed up the comparison process. However, the expectation of accuracy in such systems combined with the nature of biometric data makes the problem a very challenging one. Biometric identification often involves explicit comparison of a probe template against each template stored in a database. An effective approach to speed up the process is that of filtering, where a lightweight comparison is used to reduce the database to smaller set of candidates for explicit comparison. However, most existing filtering schemes use specific features that are hand-crafted for the biometric trait at each stage of the filtering. In this work, we show that a cascade of simple linear projections on random lines can achieve significant levels of filtering. Each stage of filtering consists of projecting the probe onto a specific line and removal of database samples outside a window around the probe. The approach provides a way of automatic generation of filters and avoids the need of developing specific features for different biometric traits. The method also provides us with a variety of parameters such as the projection lines, the number and order of projections, and the window sizes to customize the filtering process to a specific application. The experiments are performed on the fingerprints, palmprints and iris. For both iris and palmprint datasets, the representation that we use (before projection) is the popularly used thresholded filter response from pre-defined regions of the image. Experimental results show that using an ensemble of projections reduce the search space by 60% without increasing the false negative identification rate in palmprint. However for stronger biometrics such as iris, the approach does not yield similar results. We further explore this problem to find a solution, specifically for the case of fingerprints. The fundamental approach here is to explore the effectiveness of weak features in a cascade for filtering fingerprint databases. We start with a set of potential indexing features computed from minutiae triplets and minutiae quadruplets. We show that by using a set of random lines and the proposed fitness function, one can achieve better results that optimized projection methods such as PCA or LDA. Exvi vii perimental results on fingerprint datasets show that using an ensemble of projections we can reduce the penetration to 26% at a hit rate of 99%. As each stage of the cascade is extremely fast, and filtering is progressive along the cascade, one can terminate the cascade at any point to achieve the desired performance. One can also combine this method with other indexing methods to improve the overall accuracy and speed. We present detailed experimental results on various aspects of the process on the FVC 2002 dataset. The proposed approach is scalable to large datasets due to the use of random linear projections and direcly lends to pipelined processing. The method also allows the use of multiple existing features without affecting the computation time.

Abstract

The aim of voice conversion is to transform an utterance spoken by an arbitrary (source) speaker to that of a specific (target) speaker. Text-to-speech (TTS), speech-to-speech translation, mimicry generation and human-machine interaction systems are among the numerous applications which can be greatly benefited by having a voice conversion module. Generally voice conversion systems require parallel data between source and target speakers. Parallel data is a set of utterances recorded by both source and target speakers. By having such data, one can build a mapping function at frame level to transform characteristics of source speaker to a specified target speaker using machine learning techniques (GMMs, ANNs, etc,.). These techniques are assumed to perform well as humans typically perceive transformed speech to sound more like the target speaker than the source speaker. But having parallel data is not always feasible, especially in cross-lingual voice conversion where the language of source and target speakers is dierent. In literature, voice conversion techniques have been proposed which do not require parallel data. But they require speech data apriori from source speaker. These techniques cannot be applied when an arbitrary source speaker wants to transform his/her voice to a target speaker without any apriori recording. In this dissertation, we propose a method to perform voice conversion without the need of training data from the source speaker. It alleviates the need for any speech data from source speaker apriori, and can be used for cross-lingual voice conversion system. In this method, we capture speaker-specific characteristics of target speaker. The problem of capturing speaker-specific characteristics can be viewed as modelling a noisy-channel model. The idea behind modelling a noisy-channel is as follows. Suppose, C is a canonical form of a speech signal (a generic and speaker-independent representation of the message in speech signal) passes through the speech production system of a target speaker to produce a surface form S . This surface form S carries the message as well as the identity of the speaker. One can interpret S as the output of a noisy-channel, for the input C. Here, the noisy-channel is the speech production system of the target speaker. We used an artificial neural network (ANN) to model the speech production system of a target speaker, which captures the essential speaker-characteristics of the target speaker. The choice of representation of C and S of a speech signal plays an important role in this method. We used articulatory features (AFs), which represents the characteristics of speech production process, as canonical form or speaker-independent representation of speech signal as they assumed to be speaker independent. But our analysis showed that AFs contain significant amount of speaker information in their trajectories. Thus, we propose suitable techniques to normalize the speaker-specific information in AF trajectories and the resultant AFs are used for voice conversion. We show that the proposed method could be used to alleviate the need for source speaker data, and in cross-lingual voice conversion. Subjective and objective evaluations reveal that the quality of the transformed speech using the proposed approach is intelligible and possess the characteristics of the target speaker. A set of transformed utterances corresponding to results discussed in this work are available for listening at http://researchweb.iiit.ac.in/~bajibabu.b/vc_evaluation.html

Abstract

In utility computing, users access services which are delivered in a manner similar to metered traditional utilities such as water, gas and electricity. This model is advantageous as it does not involve the initial cost to acquire computing resources because computation, storage, network and other services are available as metered services which can be provisioned as per the customers’ demands. These services can be broadly classified as: Infrastructure-as-a-Service (IaaS), Platformasa-Service (PaaS) and Software-as-a-Service (SaaS). We are thus approaching a model where everything shall be offered as a service - XaaS. These modern data- centers and clouds are distinguished by a utility pricing model where customers are charged based on their utilization of computational resources, storage and transfer of data. With the recent emergence of cloud computing based services on the Internet, MapReduce has emerged as the paradigm of choice for developing large scale data intensive applications which are distributed in nature. MapReduce works best for embarrassingly parallel workloads, in which little or no effort is required to separate the problem into a number of parallel tasks which can run independently on a cluster of machines. This is often the case when a bigger problem can be divided in a number of smaller problems that can run in parallel and there exists no dependency between those parallel tasks. MapReduce is used by more than a 100 organizations worldwide to perform tasks such as web crawling and indexing, social media monitoring, scientific data processing, data mining and machine learning. The Apache Hadoop framework is the leading open source implementation of the MapReduce model. It provides a distributed file system called HDFS or Hadoop Distributed File System that facilitates high throughput access to application data. The data stored on HDFS is divided into smaller chunks of configurable size anddistributed across the cluster. HDFS creates multiple replicas of data to ensure data availability at all times. Hadoop follows a rack aware data placement policy and ensures data availability under situations ranging from a single node failure to a complete rack disconnect. Hadoop is designed to work on cheap commodity hardware, is scalable and resilient against machine failures and works on clusters comprising a single node to thousands of nodes. It is also adapted by a number of educational institutes for performing research where the budgets are even tighter. The cost to support such an infrastructure is an important factor for consideration while setting up the cluster. Power consumption of datacenters has become a key factor contributing to the costs incurred by a service provider. This power related cost includes investment, operating expenses, cooling costs and environmental impacts. Also given the scale at which these applications are deployed, minimizing power consumption of these clusters can significantly cut down operational costs and reduce their carbon footprint - thereby increasing the utility from a provider’s point of view. For High Performance Computing systems, where the main focus is on improving the performance at any cost, these energy related costs have increased significantly to a point where they are able to surpass the actual hardware acquisition costs. The first problem that we address in this thesis is: Energy conservation for clusters of nodes that run MapReduce jobs. This problem becomes more important as there is no separate power controller in MapReduce frameworks such as Hadoop. We attempt to reduce the energy consumption of datacenters that run MapReduce jobs by reconfiguring the cluster. We propose an algorithm that dynamically re- configures the cluster based on the current workload and turns cluster nodes on or off when the average cluster utilization rises above or falls below administrator specified thresholds, respectively. Our implementation creates a channel between the cluster’s power controller module and the underlying distributed file system to dynamically scale the number of nodes and adapt to the current service demands on the cluster. We evaluate our algorithm on a variety of workloads and our results show that the proposed algorithm achieves substantial energy conservation, as compared to the default HDFS implementation. In our model, the amount of energy saved is proportional to the number of deactivated nodes. We implement the defaultrack aware replica placement policy followed by HDFS and incorporate the cluster reconfiguration decisions suggested by our algorithm to dynamically scale the number of nodes in the cluster. We demonstrate the scale up and scale down operations of our algorithm and their corresponding energy savings and observe that the cluster intelligently reconfigures itself based on the workload imposed, proving the effectiveness of our algorithm. As expected, the energy conserved in case of low workload