Abstract

Carbon nanotubes were discovered in 1991 by Sumio Ijima. These molecular scale tubules of a carbon allotrope, have generated a lot of interest recently because of their extraordinary mechanical, electrical and chemical properties and because of their ability to serve as nano sized containers for various media.
This work deals primarily with the study of the dynamics of water inside a nanotube. The applications of water dynamics inside nanotubes is spread across various fields like design of devices and materials, sea water desalination and biological activities. From the perspective of biological activities, Aquaporins, which are proteins embedded in cell membranes, control the transport of water and ions across a cell. Aquaporins have dimensions similar to a nanochannel. The conclusions drawn from the understanding of the mechanism of water dynamics inside a nanochannel would also be applicable to water flow across Aquaporin pore. The phenomenon of water confinement in narrow channels whose diameter is comparable to that of water molecules alters physico-chemical properties of water and it is this alteration that presents new frontiers for research.
In past mainly two types of studies have been conducted for understanding water dynamics where flux inside nanochannel varies namely 1) System without application of external electric field or pressure and 2) System with application of external electric field or pressure. These investigations have been done on both single walled nanotube and double walled nanotube. In this study, we focus on systems without application of external electric field for investigating the dynamics of water molecules in and around nanochannel six configurations of nanosystems, five of them with nanonchannel pore (single walled nanotube in the first, and double walled nanotube in the rest) embedded in graphene sheets and the last one being graphene sheets without a nanonchannel, were simulated using Molecular Dynamics.
This study aims to investigate properties of the above systems without application of external electric field or pressure difference, to explore if there is any inherent asymmetry in the system during flow of water across the channel. Also, we have focused on hydrophobic interactions on and around graphene sheets and nanotubes. More precisely, the effect of hydrophobic interactions on formation of liquid vapor surface over graphene sheets and the resulting changes in structure of water molecule inside nanochannel.
To gain insight on water flow mechanism we want to study the correlation between various attributes of water molecules present inside nanochannel to determine if one attribute is being influenced or is dependent on another. We found that force experienced by water molecules inside the channel and average orientation angle of molecules had a very high degree of correlation. Also, there is high degree of correlation between z-coordinate of neighboring water molecules inside nanochannel.

Abstract

With the discovery of regulatory roles of RNA molecules, several scientific efforts have been made to understand its structural diversity. It has been shown that, apart from the normal and modified base and noncanonical base pairs involving them, protonated bases and protonated base pairs play an important role in shaping up the complex folded structure of the RNA molecule. But the process of protonation of nucleobases is energetically unfavourable in physiological pH. It is therefore expected that, in order to compensate the cost of protonation, the protonation induced charge redistribution and geometric changes will help the protonated base to participate in different higher order interactions such as base pair, base triple, base stack, etc. Quite a few efforts has been made in recent years to understand the kinetics and thermodynamics of the process of protonation and stabilization of the protonated bases. We have observed that there is a lack of relevance with the physiological context in the methods adopted in most of those studies. Moreover, these studies mainly focus on describing the process of protonation as a function of the difference between pH of the local environment and average pKa of the nucleobase. Significance of local pKa values of different titrable sites of different RNA bases and influence of protonation on their stabilizing factors like noncovalent interactions, have not got much attention. For the sake of comparative analysis and completeness, in our study, we have considered deprotonation of RNA bases as well.
On the basis of the results obtained from advanced ab-initio quantum mechanical calculations, in this study, we therefore have proposed a physicochemically relevant method of studying the thermodynamics of the process of protonation in terms of estimation of site specific protonation propensities of RNA bases. It considers water molecule as proton donor. We have further tried to correlate the site specific protonation propensity data with the occurrence frequency of the protonated bases. We have noticed that the stability and hence the occurrence frequency of protonated bases do not depend only on their protonation propensity but the protonation induced modifications of stabilizing factors, such as, hydrogen bonding and pi-stacking potentials play a role of greater importance. We have extensively studied the case of protonated base pairs involving N7 protonated purines. Our study revealed that, although the N7 site of Guanine has a good protonation propensity, N7 protonated Guanine can not occur in the stable planar base pairs due to reasons explained by the protonation induced charge redistribution in Guanine. N7 protonated Adenine, on the other hand, can form stable and planar base pairs and we have explored two new geometries of base pairs involving N7 protonated Adenine -- A(+):G H:H Cis and Trans. Based on the charge redistribution over both the participating bases in a protonated base pair, we have also explained the stability of base triples involving protonated bases.
Our study therefore provides a systematic estimation of site specific protonation propensities of RNA bases and evaluates the influence of protonation on hydrogen bonding and pi-stacking via them. On the basis of the both it explains stability and occurrence frequency of protonated bases and base pairs involving them.

Abstract

With the rapid advancements of communication and computational technology, theWorldWideWeb has witnessed a rapid growth in the user-generated content with more and more users actively creating, publishing and sharing content over the web. As a result, the web is now overloaded with information on varied topics contributed by diverse set of contributors. This phenomenon has given rise to the “big data” wherein lies a key problem of intelligently extracting the most relevant and accurate information specific to a user. With this, it is essential to provide more personalized web experiences to the user, where every user query is catered and satisfied according to her preferences. However, doing so would require extraction and understanding of the context and semantics of the content, which currently is not readily available. Moreover, automated systems show limited capabilities in performing the same task. This thesis is an attempt to utilize collective human intelligence to support extraction and understanding of the content over the web, which will in turn help to create personalized web experiences. In particular, we propose crowdsourcing based systems for the following tasks: 1) extracting user preferences, 2) extracting named entities, and 3) renarration of the web documents. First, we propose a friend sourcing based approach called as Crowd Consensus where we extract user preferences from the collected opinions from her friends and tested it with an online game called as Power of Friends. The current method of eliciting information is to pose direct questions to friends and expect a truthful response in return. Power of Friends, on the other hand, involves a novel way of identifying the unanimous opinion of all the friends about a question related to an individual. Next, we describe a system called as uPick, which extracts named entities and their relations from a given text and crowdsource these extracted named entities for validation. The existing systems built around the task of identifying associated relations among named entities within a text document lack human precision and they also struggle to handle erroneous documents. uPick helps to improve the accuracy of the generated relations by gathering judgments from the interested users and validate the relations based on the majority responses. Finally, we worked on a renarration framework to the web called as Alipi to make the multi-lingual documents accessible to the users. This framework supports alternative descriptions for a web page or parts of it via rewriting for a given target audience by volunteers. We developed a browser plugin to enable users to re-narrate any page and to render the requested page dynamically based on the user preferences. Our developed prototypes along with the studies show that leveraging human energy and skills have potential to provide solution to the problems that machines cannot accomplish solely. We hope our work would inspire system designers to consider crowdsourcing based systems for creating personalizing web experiences and to think beyond system efficiency and accuracy by focusing on the task experience and invested efforts by the users.

Abstract

Computational Geometry is regarded as an emerging subfield of computer science. In computational geometry the standard range searching problems are studied widely because they have many real-world applications in spatial informatics, VLSI design, geographical information systems, information retrieval, databases, computer vision, computer graphics and other areas. In the standard range searching problem on an object set S we either report points or count the number of points in a given query region q. But just reporting and counting points in the query region is not sufficient for real world applications like data mining where data analysis is the major concern. In order to support applications which require data analysis to capture significant features we compute an aggregation function over the given query region like Sum, Max, Average, etc. Range Queries with such aggregate functions are called range-aggregate queries. But to capture intricate geometric properties on the data set we do geometric aggregation. Some of the examples of geometric aggregation functions are skyline, convex hull, closest pair, Voronoi diagram, triangulation and so on. However, advances in the creation and archival of digital information have led to an information explosion and therefore the number of objects inside a query range can be huge. In such cases, reporting a sample of the result set is preferred. In this work we present solutions to two such geometrical problems which give such samples. Both skyline and convex hull concepts have wide applications to other problems like outlier detection, clustering and so on. Abstractly both skyline and convex hull concepts provide some type of ordering in higher dimensions. Intuitively we all know that ordering on a set of objects makes it more efficient for answering relevant queries by capturing significant features. Let S be a set of n points in the two dimensional plane. A point p = (p x ; p y ) is said to dominate another point q = (q x ; q y ) if p x > qx and p y > qy . Points not dominated by any point in the set are called maximal or skyline points. We preprocess S into a data structure such that we can efficiently compute maximal points or skyline for any given query q. We propose a linear space data structure which takes O(log n + k) query time for any given query q in the word RAM model where k is the total number of points that are reported. We solve this problem for 2-sided quadrant queries and 3-sided range queries. We not only report points inside the given query region but we also count the number of points in S q.

Abstract

Human beings use specific characteristics of people such as their facial features, voice and gait to recognize people who are familiar to us in our daily life. The fact that many of the physiological and behavioral characteristics are sufficiently distinctive and can be used for automatic identification of people has led to the emergence of biometric recognition as a prominent research field in recent years. Several biometric technologies have been developed and successfully deployed around the world such as fingerprints, face, iris, palmprint, hand geometry, and signature. Out of all these biometric traits, fingerprints are the most popular. This thesis is focused on improving the efficiency of fingerprint recognition systems using local minutiae based features. Initially, we tackle the problem of large scale fingerprint matching called fingerprint identification. Large size of databases (sometimes containing billions of fingerprints) and significant distortions between different impressions of the same finger are some of the major challenges in identification. A naive solution involves explicit comparison of a probe fingerprint image/template against each of the images/templates stored in the database. A better approach to speed up this process is to index the database, where a light-weight comparison is used to reduce the database to a smaller set of candidates for detailed comparison. In this thesis, we propose a novel hash-based indexing method to speed up fingerprint identification in large databases. For each minutia point, its local neighborhood information is computed with features defined based on the geometric arrangements of its neighboring minutiae points. The features proposed are provably invariant to distortions such as translation, rotation and scaling. These features are used to create an affine invariant local descriptor called an Arrangement Vector, which completely describes the local neighborhood of a minutiae point. To account for missing and spurious minutiae, we consider subsets of the neighboring minutiae and hashes of these structures are used in the indexing process. Experiments conducted on public databases show that the approach is quite effective and gives better results than the existing state-of-the-art approach using similar affine features. We then extend our indexing framework to solve the problem of matching of two fingerprints. We come up with a novel fixed-length descriptor for a minutia that captures its distinctive local geometry. This distinctive representation of each minutiae neighborhood allows us to compare two minutiae points and determine their similarity. Given a fingerprint database, we then use unsupervised K-means clustering to learn prominent neighborhoods from the database. Each fingerprint is represented as a collection of these prominent neighborhoods. This allows us to come up with a binary fixed length representation for a fingerprint that is invariant to global distortions, and handle small local non-linear distortions.Given two fingerprints, we represent each of them as fixed length binary vectors. The matching problem then reduces to a sequence of bitwise operations, which is very fast and can be easily implemented on smaller architectures such as smart phones and embedded devices. We compared our results with the two existing state-of-the-art fixed length fingerprint representations from the literature, which demonstrates the superiority of the proposed representation. In addition, the proposed representation can be derived using only the minutiae positions and orientation of a fingerprint. This makes it applicable to existing template databases that often contain only this information. Most of the other existing methods in the literature use some additional information such as orientation flow and core points, which need the original image for computation.

Abstract

Scene Classification has been an active area of research in Computer Vision. The goal of scene classification is to classify an unseen image into one of the scene categories, e.g. beach, cityscape, auditorium, etc. Indoor scene classification in particular is a challenging problem because of the large variations in the viewpoint and high clutter in the scenes. The examples of indoor scene categories are corridor, airport, kitchen, etc. The standard classification models generally do not work well for indoor scene categories. The main difficulty is that while some indoor scenes (e.g. corridors) can be well characterized by global spatial properties, others (e.g. bookstores) are better characterized by the objects they contain. The problem requires a model that can use a combination of both the local and global information in the images. Motivated by the recent success of the Bag of Words model, we apply the model specifically for the problem of Indoor Scene Classification. Our well-designed Bag of Words pipeline achieves the stateof- the-art results on the MIT 67 indoor scene dataset, beating all the previous results. Our Bag ofWords model uses the best options for every step of the pipeline. We also look at a new method for partitioning of images into spatial cells, which can be used as an extension to the standard Spatial Pyramid Technique (SPM). The new partitioning is designed for scene classification tasks, where a non-uniform partitioning based on the different regions is more useful than the uniform partitioning. We also propose a new image representation which takes into account the discriminative parts from the scenes, and represents an image using these parts. The new representation, called Bag of Parts can discover parts automatically and with very little supervision. We show that the Bag of Parts representation is able to capture the discriminative parts/objects from the scenes, and achieves good classification results on the MIT 67 indoor scene dataset. Apart from getting good classification results, these blocks correspond to semantically meaningful parts/objects. This mid-level representation is more understandable compared to the other low-level representations (e.g. SIFT) and can be used for various other Computer Vision tasks too. Finally, we show that the Bag of Parts representation is complementary to the Bag ofWords representation and combining the two gives an additional boost to the classification performance. The combined representation establishes a new state-of-the-art benchmark on the MIT 67 indoor scene dataset. Our results outperform the previous state-of-the-art results [58] by 14%, from 49.40% to 63.10%.

Abstract

Computational geometry is a branch of algorithms that deals with objects that are geometric in nature. In the last four decades, computational geometry has graduated into a rich area encompassing matured techniques designed to deal with geometric data. Range queries are one of the most widely studied topics in computational geometry and is dened as: Given a set S of geometric objects (points, lines etc), preprocess S into a data structure such that given a query object (point, circle, rectangle, square, polygon), we can eciently report the subset S 0 of the objects intersecting the query. Range query problems are generally data structuring problems with focus on query time and/or space-eciency. Output sensitivity also plays an important role in the study of range query problems. Broadly speaking, output sensitive algorithm is an algorithm whose run time depends on the size of the output in addition to the size of the input. Thus, the run time of an output sensitive algorithm (also known as query time for range queries) is expressed as T (n) = f (n) + k  g(n) where n is the number of input elements, f (n); g (n) are some polynomials and k is the number of output elements to be reported. Precisely, the run time of an output sensitive algorithm is divided into two parts namely (i) the computation time which denotes the time needed to compute the results and (ii) the reporting time which denotes the time needed to report each output element. Generally, for range queries, f (n) and g(n) are bounded by O(log c(1) n) and O(log c(2) n) where c(1); c(2) are constants  0. Thus, the query time for a range query is often of the form O(log c(1) n + k log c(2) n). Most of the studies in range aggregate queries attempt to reduce the value of c(2) preferably to zero. In this work, we study seven range query problems with applications in databases, geographical information systems, VLSI Electronic Design Artwork-Design Rule Checking (EDA-DRC) tools. For most of the problems studied in this dissertation, we have succeeded in reducing the constant c(2) to zero.

Abstract

Localization/state estimation, a fundamental problem in the field of mobile robotics, is one of the most critical components of robot navigation, without which a robot cannot navigate without losing its bearing and position. This Thesis deals with the implementation of Grid Based Markov Localization to solve the problem of Self-Localization using Reconfigurable architectures like FPGA and suitably modifying the localization algorithm to overcome several constraints like limited memory and resources that are imposed on. Markov Localization, one of the efficient algorithms to solve the problem of localization, uses Bayes theory of probability to estimate the position of the robot in a given environment. Most existing implementations of Markov Localization use either Fixed Base Station PC or laptop mounted on robot as the processing unit where all the computations are done. These implementations are either constrained by the Area or Cost of the equipment. The current work under consideration unequivocally portray the advantages of an FPGA based implementation of the Markov localization. In the current research a reconfigurable technique based on Field Programmable Gate Arrays (FPGAs) has been proposed to implement Markov Localization with the advantage of achieving greater functionality and higher performance with smaller dimensions and less power dissipation. In order to achieve this, the traditional Markov Localization has been modified to make it run in parallel and modules overcome constraints like limited on-chip memory and limited resources. In the current thesis different hardware architectures have been proposed to realize a specific module on FPGA and a comparative analysis between the architectures based on their processing speed or execution time and resource utilization is provided. It will be shown that the execution time of localization can be decreased significantly by updating the probabilities of different grids in parallel and the loss in accuracy, if any, due to the modifications is rather negligible. It has been noticed that this execution time while executing it on Xilinx Spartan-6 FPGA running at clock of 100MHz is comparable to that of while executing it on general purpose processor running at a clock of 2.93GHz. Also critical to this success is the lossless compression of the probability distributions that provides for lesser memory footprint. Two distinct encoding schemes, Successive Deviation Encoding similar to Differential Pulse Code Modulation (DPCM) and the other, Block-wise Mean Deviation Encoding are used to compress the discrete probability distributions of the robot's belief. With the proposed algorithm and the hardware architecture designed, it has been shown how a omni-directional robot completely running on FPGA, equipped with SRF04 sensors, is able to localize in a given map of environment. Extensive emulations on a Xilinx Spartan-6 FPGA on Digilent Nexys3 board and implementations on a robot controlled by such a board confirm the efficacy of the algorithm.

Abstract

Recent years has seen the emergence of thousands of photo sharing websites on the Internet where billions of photos are being uploaded every day. All this visual content boasts a large amount of information about people, objects and events all around the globe. It is a treasure trove of useful information and is readily available at the click of a button. At the same time, significant effort has been made in the field of text mining, giving birth to powerful algorithms to extract meaningful information scalable to large datasets. This thesis leverages the strengths of text mining methods to solve real world computer vision problems. Leveraging such techniques to interpret images is accompanied by its own set of challenges. The variability in feature representations of images makes it difficiult to match images of the same object. Also, there is no prior knowledge about the position or scale of the objects that have to be mined from the image. Hence, there are infinite candidate windows which have to be searched. The work at hand tackles these challenges in three real world settings. We first present a method to identify the owner of a photo album taken off a social networking site. We consider this as a problem of prominent person mining. We introduce a new notion of prominent persons, where information about the location, appearance and social context is incorporated into the mining algorithm to be effectively able to mine the most prominent person. A greedy solution based on an eigenface representation is proposed and We mine prominent persons in a subset of dimensions in the eigenface space. We present excellent results on multiple datasets - both synthetic as well as real world datasets downloaded from the Internet. We next explore the challenging problem of mining patterns from architectural categories. Our mining method avoids the large numbers of pair-wise comparisons by recasting the mining in a retrieval setting. Instance retrieval has emerged as a promising research area with buildings as the popular test subject. Given a query image or region, the objective is to find images in the database containing the same object or scene. There has been a recent surge in efforts in finding instances of the same building in challenging datasets such as the Oxford 5k dataset[46], Oxford 100k dataset and the Paris dataset[48]. We leverage the instance retrieval pipeline to solve multiple problems in computer vision. Firstly, we ascend one level higher from instance retrieval and pose the question: Are Buildings Only Instances? Buildings located in the same geographical region or constructed in a certain time period in history often follow a specific method of construction. These architectural styles are characterized by certain features which distinguish them from other styles of architecture. We explore, beyond the idea of buildings as instances, the possibility that buildings can be categorized based on the architectural style. Certain char acteristic features distinguish an architectural style from others. We perform experiments to evaluate how characteristic information obtained from low-level feature configurations can help in classification of buildings into architectural style categories. Encouraged by our observations, we mine characteristic features with semantic utility for different architectural styles from our dataset of European monuments. These mined features are of various scales, and provide an insight into what makes a particular architectural style category distinct. The utility of the mined characteristics is verified from Wikipedia. We finally generalize the mining framework into an efficient mining scheme applicable to a wider varieties of object categories. Often the location and spatial extent of an object in an image is unknown. The matches between objects belonging to the same category are also approximate. Mining objects in such a setting is hard. Recent methods [55] model this problem as learning a separate classifier for each category. This is computationally expensive since a large number of classifiers are required to be trained and evaluated, before one can mine a concise set of meaningful objects. On the other hand, fast and efficient solutions have been proposed for the retrieval of instances (same object) from large databases. We borrow, from instance retrieval pipeline, its strengths and adapt it to speed up category mining. For this, we explore objects which are “near-instances”. We mine several near-instance object categories from images obtained from Google Street View. Using an instance retrieval based solution, we are able to mine certain categories of near-instance objects much faster than an Exemplar SVM based solution.

Abstract

Many image retrieval schemes generally rely only on a single mode, (either low level visual fea- tures or embedded text) for searching in multimedia databases. In text based approach, the annotated text is used for indexing and retrieval of images. Though they are very powerful in matching the context of the images but the cost of annotation is very high and the whole process suffers from the subjectivity of descriptors. In content based approach, the indexing and retrieval of images is based on the visual content of the image such as color, texture, shape, etc. While these methods are robust and effective they are still bottlenecked by semantic gap. That is, there is a significant gap between the high-level concepts (which human perceives) and the low-level features (which are used in describing images). Many ap- proaches(such as semantic analysis) have been proposed to bridge this semantic gap between numerical image features and richness of human semantics Semantic analysis techniques were first introduced in text retrieval, where a document collection can be viewed as an unsupervised clustering of the constituent words and documents around hidden or latent concepts. Latent Semantic Indexing (LSI), probabilistic Latent Semantic Analysis (pLSA), Latent Dirichlet Analysis (LDA) are the popular techniques in this direction. With the introduction of bag of words (BoW) methods in computer vision, semantic analysis schemes became popular for tasks like scene classification, segmentation and content based image retrieval. This has shown to improve the performance of visual bag of words in image retrieval. Most of these methods rely only on text or image content. Many popular image collections (eg. those emerging over Internet) have associated tags, often for human consumption. A natural extension is to combine information from multiple modes for enhancing effectiveness in retrieval. The enhancement in performance of semantic indexing techniques heavily depends on the right choice of number of semantic concepts. However, all of them require complex mathematical compu- tations involving large matrices. This makes it difficult to use it for continuously evolving data, where repeated semantic indexing (after addition of every new image) is prohibitive. In this thesis we intro- duce and extend, a bipartite graph model (BGM) for image retrieval. BGM is a scalable datastructure that aids semantic indexing in an efficient manner. It can also be incrementally updated. BGM uses tf-idf values for building a semantic bipartite graph. We also introduce a graph partitioning algorithm that works on the BGM to retrieve semantically relevant images from a database. We demonstrate the properties as well as performance of our semantic indexing scheme through a series of experiments. Then , we propose two techniques: Multi-modal Latent Semantic Indexing (MMLSI) and Multi- Modal Probabilistic Latent Semantic Analysis (MMpLSA). These methods are obtained by directly extending their traditional single mode counter parts. Both these methods incorporate visual features and tags by generating simultaneous semantic contexts. The experimental results demonstrate an improved accuracy over other single and multi-modal methods. We also propose, a tri-partite graph based representation of the multi model data for image re- trieval tasks. Our representation is ideally suited for dynamically changing or evolving datasets, where repeated semantic indexing is practically impossible. We employ a graph partitioning algorithm for re- trieving semantically relevant images from the database of images represented using the tripartite graph. Being ”just in time semantic indexing”, our method is computationally light and less resource intensive. Experimental results show that the data structure used is scalable. We also show that the performance of our method is comparable with other multi model approaches, with significantly lower computational and resources requirements