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

Abstract

Formerly, locational information and multi-domain geographic data was stored mostly in the form of maps and merged at the desktop level. It has been less than a decade since the data is being exchanged through the internet. Data transferability and interoperability is required for visualizing, analyzing and modelling the data. Spatial data infrastructure (SDI) is a framework which mainly focuses on bringing together geospatial data providers and agencies to share data and services thus reducing the redundancy in data collection and improving the planning and decision making process. Although, there are multiple data formats for spatial data, Geography mark-up language (GML), which is an XML based coding standard for geographic data has come to stay as the standard for these SDIs. GML is mainly used for storage, exchange and querying of geographic data. The standard GML format for storage is in text format leading to large data sizes. Also, GIS uses multiple thematic layers for decision making and visualization. For example, one layer of spatial data showing the the district boundaries of india with 600 districts is around 16MB. With these large data sizes, transferring of data becomes cumbersome consuming a lot of both bandwidth and storage. Client management also becomes difficult. Thus, if the data size is reduced/compressed both the storage and its management will be improved. Also, GML data compression will aid in higher information transfer and allow the users for faster access & quicker visualization.
Recent methods on GML compression have largely focused on the structure of data and used standard text based compression algorithms like gzip which ignore the topological properties like neighbourhood etc. Due to which, there are high chances of data re-occurances. Hence, they fail to provide an effective compression. This compressed data becomes inoperable and the user has to decompress the data in order to get any information.
This thesis work proposes a topology based compression method called GTrees approach (multiple and single tree) which exploits both topological and structural characteristics of the geo-spatial data. In addition, to achieve a lossless compression and for easy storage and retrieval of the complete data, a tree based data structure is adapted to represent the coordinates which further helps in easy storage and retrieval. The experimental results show that these methods applied together achieve a compression of 50% to 70% for data sets ranging from 244 to 16,000 KBytes.
Another compression method based on the tree structure, where a single two way tree structure is created to compress the whole file is also proposed here . This method compresses the coordinate data as well as the attribute data. An overall compression percentage range of 60-75% is achieved here for the same datasets.
Futher, a query system called GTQueries is developed for querying the compressed data. Most of the spatial queries are based on topological relationships. Given that GTrees approach embeds the inherent topological relationships, the queries can be answered without decompressing the data to get the required information.
For testing and evaluation of the proposed system a seamless desktop based user interface application has also been developed. The user interface is used for compression , decompression and viewing of the GML data. For viewing the data, the compressed or decompressed files are converted into SVG. So, it becomes easier for the users to do all the operations. Thus, transferring and viewing of the geographic data becomes simpler.
The work proposed here helps faster data transfer and reduced storage space due to reduced size of data and thus helps SDI access more data and use it appropriately. The data can be decompressed and viewed. Spatial queries are also answered using the compressed data providing important information. Thus, the proposed work is an effort to help improve SDI and its usage when new functionalities are demanded of it.

Abstract

Traditionally speech signals are analyzed using sinusoidal basis function as in Fourier analysis. While Fourier representation are possible for a wide variety of arbitrary signals, they are best suited for periodic signals. The aperiodicity and the damping in natural signals such as speech may not be best captured with sinusoidal basis function. Thus aperiodic and damped sinusoidal basis function such as Bessel function may be a better and natural choice for analysis and representation of speech signals. An orthogonal set of basis function can resolve the various components of a signal better if it has structural similarity with the signal components. Unwanted noise components with different structure may be discriminated better. The vocal tract system of the speech production mechanism can be modeled as a series of cylindrical acoustic tubes. Bessel functions being solutions to cylindrical wave equation, are therefore a better choice for representing the speech signals. The Bessel or Fourier-Bessel representation being a real transform unlike the complex Fourier representation, the phase and magnitude part of the components are captured simultaneously. Unlike Fourier representation where the phase information is normally ignored, the phase information provided by the FB representation may be of use in building a speech systems. In this thesis, the feasibility of using FB expansion for analysis and representation of speech signals is studied extensively. In the AM-FM modeling of speech signal, the instantaneous frequency (IF) and the amplitude envelope (AE) of individual speech resonances are estimated by the discrete energy separation algorithm (DESA). For this, first need to isolate single resonances without introducing any distortion in the amplitude or in the phase of a single resonance. The FB decomposition along with DESA technique gives accurate tracking of the IF and the AE of the formants. The proposed approach has been used for the detection of voice onset time (VOT). The method uses the Bessel expansion to emphasize the vowel and the consonant regions of stop consonant vowel (SCV) units. AM-FM signal has been emphasized after appropriate consideration of the range of Bessel coefficients, separately for the vowel and consonant regions of SCV units. The reconstructed signal from the Bessel expansion is a narrow-band AM-FM signal, therefore the AE function for the emphasized signal can be estimated using discrete energy separation algorithm (DESA). For the detection of VOT, the AE of both vowel and consonant emphasized signal have been analyzed. Detection of VOT is analyzed for the continuous speech corpus. An approach is proposed for detection of glottal closure instants (GCIs) based on FB expansion, amplitude and frequency modulated (AM-FM) signal analysis. Using appropriate range of Bessel coefficients, the narrow band, band-limited signals are obtained for the given signal. Amplitude envelope function of the AM-FM signal model has been estimated by DESA. The proposed approach, to detect GCIs is experimentally evaluated on CMU-Arctic database. Speech signals are highly redundant. It may be desirable and possibly necessary to represent the signal with a fewer number of samples for economy of storage and for transmission bandwidth limitations. Pattern recognition techniques rely on the ability to generate a set of coefficients from the raw data (time-domain samples) that are more compact (i.e. fewer samples) and are more closely related to the signal characteristics of the interest. In this thesis we are expanding a speech signal into a Fourier-Bessel series. The resulting coefficients set will then be used as feature vector for pattern recognition. Fourier-Bessel cepstral coefficients (FBCC) are explored as features for robust textindependent speaker recognition, and employed the method of Gaussian mixture for modeling the speaker characteristics. Developed the speaker models from the Fourier-Bessel features extracted from the speech samples, as an alternative to Mel-frequency cepstral coefficients (MFCC) and linear prediction cepstral coefficients (LPCC). The method has been proposed to extract the cepstrum based feature vectors called FBCC from zero and f irst order Bessel coefficients taking into account the perceptual characteristics of human auditory system for speech recognition applications. Recognition accuracy is measured using the CMU SPHINX-III speech recognition system on DARPA Resource Management (RM) speech corpus for training and testing. Multispeaker speech signals is analyzed in this thesis, the technique to determine the number of speakers from multispeaker mixed speech signals collected simultaneously from a pair of spatially separated microphones is proposed. The arrival of the speech signals from speaker to microphones gives the time delays of given speaker. The time delays can be estimated by performing the cross-corr

Abstract

Stroke is one of the leading causes of death and disability in the world. Early detection of Stroke (both hemorrhagic and ischemic) is very important as it can ensure up to full recovery. Timely detection of stroke, especially ischemic stroke is difficult as the changes in abnormal tissue only become visible after the damage has already been done. The detection is even more difficult on CT scan compared to other imaging modalities but the dependence of a large fraction of population on CT, makes the need to find a solution to the problem even more imperative. Though the detection accuracy of radiologists for early stroke depends on various factors like experience, available technology, etc., earlier estimates put the accuracy around 10% [45]. Even with considerable advancement in CT technology the performance has still only increased to around 70% or thereabouts [21]. Any kind of assistance to radiologists which can improve their detection accuracy would therefore be much appreciated. This thesis presents a framework for automatic detection and classification of different types of stroke. We characterize stroke as a distortion in the otherwise contralaterally similar distribution of brain tissue. Classification depends on the severity of the distortion with hemorrhage and chronic infarcts exhibiting the maximum distortion and hyperacute stroke showing the minimum. The detection work on hemorrhagic stroke and early ischemic stroke has clinical value whereas the work on later stages of ischemic stroke has mainly academic use. The automatic detection approach was tested on a dataset containing 19 normal (291 slices) and 23 abnormal (181 slices) datasets. The algorithm gave a high recall rate for hemorrhage (80%), chronic (95%), acute (91.80%) and hyperacute (82.22%) stroke at slice level. The corresponding precision figures were 93.3%, 90.47%, 87.5% and 69.81% respectively. The performance of the system in a normal vs. stroke-affected scenario was 83.95% precision and 86.74% recall. The lower precision value in case of hyperacute scans is because of large number of normal slices with slight disturbances in contra-lateral symmetry being identified as stroke cases. We also present a novel approach for enhancement of early ischemic stroke regions using image-adaptive window parameters, to aid the radiologists in the manual detection of early ischemic stroke. The enhancement approach increased the average accuracy of radiologists in clinical conditions from around 71% to around 90% (p=0.02, two tailed student’s t test) with the inexperienced radiologists benefitting more from the enhancement. The average reviewing time of the scans was also reduced from about 9 to 6 seconds per slice. Out of the two approaches, automatic detection and enhancement, results show the enhancement process to be more promising.

Abstract

Parsing morphologically rich, free word order languages like Hindi, Czech, Turkish, etc. is a challenging task. Unlike English, most of the parsers for such languages have adopted the dependency grammatical framework, which is better suited for the task.(Shieber, 1985; Meluk, 1988; Bharati et. al, 1995). Due to the availability of manually annotated corpora in recent years, data-driven dependency parsing has achieved considerable success. In this work, we explore the performance of three data-driven dependency parsers, Malt, MST and Partial parser, for Hindi dependency parsing. Our system uses a hindi corpus that has manually annotated dependency relations and automatically extracted features like POS, chunk, morphological information, etc. and does complete word level parsing. We achieved an accuracy of 86.5% Unlabeled Attachment Score(UAS) and 77.9% Labeled Attachment Score(LAS), which is the state-of-the-art for automatic hindi dependency parsing. We tried to improve the parsing accuracy by using two bootstrapping techniques, self-training and co-training. Self-training is a simple process of incorporating unlabeled data into the training data of the parser. It uses the parser’s own output on the unlabeled data to improve its performance. Co-training is a technique that uses the output of two or more parsers of comparable accuracy on unlabeled data to provide additional training data for each other. Considering the automatic hindi dependency parser as our baseline, we applied self-training by using a large raw corpus. We also performed co-training between the state-of-the-art parser(Malt), another parser with comparable accuracy(MST) and a parser which can learn from partial structures(Partial parser). We experimented with various parameters to select top sentences for bootstrapping like the average classifier score of sentence, product of classifier score, etc. We also extracted highly confident sub-parses using different techniques which were used to improve the performance of the Partial parser. Both self-training and co-training were performed using two different types of raw corpora, one from the same domain as the training and test data and another from a different domain. We present a comparative analysis of the effect of domain of raw corpora on bootstrapping techniques. We also compare the effect of using automatically parsed data via bootstrapping and additional gold data on parser accuracy. By bootstrapping, we achieved the best accuracy of 87.1% Unlabeled Attachment Score(UAS) and 78.8% Labeled Attachment Score(LAS), which is a significant improvement over the state-of-the-art accuracy for automatic parsing. Using highly confident sub-parses, we were able to improve the performance of the Partial parser from 79.85% UAS to 84.5% UAS, which is comparable to the state-of-the-art accuracy for automatic parsing.

Abstract

Translation is the task of transforming text from one natural language to another while preserving the meaning and structure of the original text. Current phrase-based models for statistical machine translation are extremely restrictive and lack the flexibility to incorporate necessary contextual features in discriminating translations for source phrases. In this thesis, we propose a contextual translation model trained using discriminative learning techniques. The contextual model is integrated with a phrase based decoder to translate a given input sentence. We show that a discriminative translation model trained using lexical and shallow syntactic contextual features results in better translations both in terms of improved lexical selection and sentence construction. The work in this thesis also discusses methods to extract syntactic grammars from an annotated treebank and create a syntactic lexicon to be used in training a Supertagger. We extend the set of contextual features used by incorporating rich syntactic contextual features in the form of “supertags” on the source and target side to improve translation performance. Evaluation is done using both empirical methods and subjective evaluation. Given that the current syntax-based models for machine translation use a cubic-time decoding algorithm to construct translations, the proposed method of incorporating rich syntactic information into phrase-based models while retaining the linear-time complexity of the decoding algorithm is one of the prime contributions of my thesis. Improvements obtained using contextual models are limited when faced with the problem of limited training data- a scenario commonly found in the case of Indian languages. It is possible to allocate certain resources to create parallel corpora resources either by hiring translators to manually translate documents from a source language or through increasingly fashionable crowdsourcing. The created resources should allow one to develop real-time machine translation systems with a satisfactory level of performance. In the second half of my thesis, I present a method to enrich the existing SMT models. These models use information from other sources like a transfer grammar from a rule-based machine translation system to improve the reordering quality while translating from English to Indian languages, which can easily be applied to other low-resource languages. Finally, I propose a novel method to predict what the learning curve of an SMT system would look like, to estimate how much parallel corpus is required in order to achieve a satisfactory translation performance. Given the enormity of the task to create parallel corpora for different Indian languages, we believe the learning curves predicted using our method can be used to develop parallel corpora resources efficiently.