Abstract

Points-based models have gained popularity in recent years. The most attractive feature of the pointbased primitives is its simplicity. No information about connectivity or topology of the surface is stored explicitly. Adaptive modication and dynamic sampling of the surface do not suffer from complexity and robustness like triangle mesh. The level of detail is simple, fast and almost continuous. However, points based methods suffer from surface normal discontinuities in representation. Shading is also not independent from sampling rate. Point based models can be visualized by rendering the points directly. Each sample in the representation has certain attributes (normal, color, material properties) for rendering and shading them as a continuous surface. Typically, a point sample also has a radius to dene an area around it. Such samples are called surfels and approximate the shape of the surface linearly in their neighborhood. Since linear splats can only be at shaded, such representations require a large number of samples for a good shading quality. This slows the rendering due to increase in rendering computation and related memory bus activity. Point-based rendering suffer from the limited resolution of the xed number of samples representing the model. At some distance, the screen space resolution is high relative to the point samples, which causes under-sampling. A better way of rendering a model is to re-sample the surface during the rendering at the desired resolution in object space, guaranteeing a sampling density sufcient for image resolution. Output sensitive sampling samples objects at a resolution that matches the expected resolution of the output image. This is crucial for hole-free point-based rendering. Many technical issues related to point-based graphics boil down to reconstruction and re-sampling. A point based representation should be as small as possible while conveying the shape well. In the rst part of this thesis, we present a compact representation for point based models using non-linear surface elements. In the second part, we present a method for fast ray casting of a dynamic surface dened by large number of attributed points called Metaballs. Algebraic Splats: Higher-order approximations of the local neighborhood have the potential to represent the shape using fewer primitives, simultaneously achieving higher rendering speeds and quality. In this thesis, we present algebraic splats, which are low-order polynomials that approximate the local neighborhood of a pointset. We adapt the Moving Least Squares (MLS) approximation to generate algebraic splat representations for a given point set. Quadratic and cubic splats as basic rendering primitive are able to approximate point-based models using 10% or fewer points than linear splats, for equivalent viii ix visual quality. Though rendering a non-linear patch is slower compared to a linear splat, the overall speed of rendering of an object could be faster. The approximation error can also be less using a small number of higher order primitives. We represent a given point set with a user-specied small number of algebraic splats with optimal rendering quality. This is done by decimating the point set and jointly approximating each using a local algebraic surface based on the Moving Least Squares (MLS) approximation. Our rendering provides smooth surfaces with normals everywhere. We can render polynomials directly on today's GPUs using ray-tracing because of the semi-implicit nature of the splats in the local reference domain. The major contributions of this work are: (i) A compact and lightweight representation for point geometry using nonlinear surface elements, called algebraic splats; (ii) A multi-resolution representation which provides continuous Level of Detail; and (iii) A ray-tracing approach to render the algebraic splats on the GPU. The method includes an adaptive anti-aliasing step to obtain smooth silhouettes. The David 2mm model can be represented using about 30K (or 0.8% of original) algebraic splats with little or low reduction in visual quality. We can raycast the David model with adaptive antialiasing (33 grid) at 130-150 fps and 80-90 fps with shadowing. Our method is faster by a factor of 10 on most models and require about 90% less diskspace in comparision to linear splats. Metaballs: Since the available computational power is steadily growing, more and more science areas rely on simulations of ever-growing problem sizes producing huge amount of data to be analyzed. Simulation and experimental measurement in life sciences, physics, chemistry, materials, and thermodynamics yield large and often also time-dependent datasets. Interactive visualization is the key service that facilitates the analysis of such datasets and thus enables the researchers in those elds to quickly assess and compare the results of a simulation or measurement, verify and improve their mod

Abstract

Advances in cameras and web technology have made it easy to capture and share large amounts of video data over to a large number of people. Also, an increasing number of video cameras observe public spaces like airports, train stations, shopping malls, streets, and other public places today. Video surveillance is an important tool to prevent, detect and reduce crime and disorder. It is also widely used to monitor people’s conduct, detect their presence in an area and/or possibly study their actions too. However, many civil rights and privacy groups have expressed their concern that by allowing continual increases in surveillance of citizens, we will end up in a mass surveillance society, with extremely limited, or non-existent political and/or personal freedoms. With the widespread use of surveillance today, we are becoming used to “being watched”. As time goes on, the more accustomed we become to video surveillance, we are not as likely to fight to maintain our right to privacy. Critics believe that in addition to its obvious function of identifying and capturing individuals who are committing undesirable acts, surveillance also functions to create in everyone a feeling of always being watched, so that they become self-policing. At the same time prices of hardware have fallen, and the capabilities of systems have grown dramatically. The day is not far when it would be easy to convert even the lowcost video surveillance units into “intelligent” human recognition systems. These raise concerns on the unintentional and unwarranted invasion of the privacy of individuals caught in the videos. The data collected during video surveillance consist mainly of images and sounds which allow identification of people captured, whether directly or indirectly, in addition to monitoring their conduct. While there may be a possible security need to identify the individuals in these videos, identifying the action suffices in most cases. The actor needs to be identified only rarely and only to authorized personnel. The privacy concerns related to the processing and distribution of the collected videos are genuine and will grow with wider adaptation of video technology. To address these concerns, automated methods to de-identify individuals in these videos are necessary. De-identification does not aim at destroying all information involving the individuals. Its ideal goals are to obscure the identity of the actor without obscuring the action. There is a natural trade-off between protecting privacy and providing sufficient detail. The goal is to protect the privacy of the individuals while providing sufficient feel for the human activities in the space being imaged. The policies on the privacy issues are still unclear and are fast evolving. The need of the hour is to be cautious as digital data has the potential to be replicated with little control, especially when placed on the cloud. This thesis outlines the scenarios in which de-identification is required and the issues vi vii brought out by those. We also present an approach to de-identify individuals from videos. Our approach involves tracking and segmenting individuals in a conservative voxel space involving x, y and time. A de-identification transformation is applied per frame using these voxels to obscure the identity. A robust de-identification scheme with a randomization module was designed in order to make reconstruction and comparison based identification attacks impossible. Face, silhouette, gait, and other characteristics need to be obscured, ideally. We show results of our scheme on a number of videos and for several variations of the transformations. We present the results of applying algorithmic identification on the transformed videos. We also present the results of a user-study to evaluate how well humans can identify individuals from the transformed videos. The results showed that as the parameter controlling the amount of deidentification increased, the actors became less identifiable (more privacy), while the video started losing the context and detail. The studies also suggest that an action can be recognized with more accuracy than the actor in a de-identified video, which is the guiding principle of de-identification. We also created a suitable dataset for the purpose of user studies, as the standard datasets available online are not challenging enough for such an evaluation.

Abstract

Kernel methods are among the important recent developments in the eld of machine learning with applications in computer vision, speech recognition, bio-informatics, etc. This new class of algorithms combine the stability and efciency of linear algorithms with the descriptive power of nonlinear features. Kernel methods allow data to be mapped (implicitly) to a different space, which is often very high dimensional compared to the input space, so that complex patterns in the data become simpler to detect and learn. Kernel function maps the data implicitly into a different space. Support Vector Machines (SVMs) are one of the kernel methods which is widely successful for classication task. The performance of algorithm depends on the choice of the kernel. Sometimes, nding the right kernel is a complicated task. To overcome this, learning the kernel is the new paradigm which is developed in the recent years. For this, the kernel is parameterized as a weighted linear combination of base kernels. The weights of the kernel are jointly optimized with the objective of the task. Learning both the SVM parameters and the kernel parameters is a Multiple Kernel Learning (MKL) problem. Many formulations of MKL are presented in literature. However, all these methods restrict to linear combination of base kernels. In this thesis, we show how the existing optimization techniques of MKL formulations can be extended to learn non-linear kernel combinations subject to general regularization on the kernel parameters. Although, this leads to non-convex problem, the proposed method retains all the efciency of existing large scale optimization algorithms. We name the new MKL formulation as Generalized Multiple Kernel Learning (GMKL). We highlight the advantages of GMKL by tackling problems like feature selection and learning discriminative parts for object categorization problem. Here, we show how the proposed formulation can lead to better results not only as compared to traditional MKL but also as compared to state-of-the-art wrapper and lter methods for feature selection. In the problem of learning discriminative parts for object categorization, our objective is to determine minimal sets of pixels and image regions required for the task. We use the Multiple kernel learning to select the most relevant pixels and regions for classication. We then show how the framework can be used to enhance our understanding of the object categorization problem at hand, determine the importance of context and highlight artifacts in the training data. We also tackle the problem of recognizing characters in images of natural scenes in MKL framework. Traditionally it is not be handled well by OCR techniques. We assess the performance of various features ( using bag-of-visual-words representation ) based on nearest neighbor and SVM classication. Besides this, we investigate the appropriate representation schemes for recognition using MKL. In short, the contributions of this thesis are: 1. Proposing new MKL formulation that can learn non-linear kernel combinations subject to general regularization on the kernel parameters. 2. Exploring the utility of multiple kernel learning formulations for feature selection and to the problem of learning informative parts for object category recognition. 3. Recognition of character images taken in natural scenes using the state of the art object recognition schemes. And also exploring the appropriate representation schemes for recognition using MKL.

Abstract

Blind modulation classi¯cation deals with identi¯cation of modulation formats from received signal without the knowledge of the type of modulation transmitted. The problem becomes more challenging in real world scenarios when there are synchro- nization errors such as frequency o®set and timing o®set, and multi-path fading. We consider the problem of modulation classi¯cation in the presence of carrier frequency o®set. Several algorithms, based on higher-order cumulants of di®erentially processed re- ceived signal and cyclic cumulants of the received signal, have been recently proposed for blind classi¯cation in the presence of frequency o®set. Since the variance of the estimates of these features is high, more data and/or high SNR is required for good classi¯cation performance. We consider 9-class and 10-class problems and propose hierarchical classi¯cation using a combination of moments of the received and di®erentially processed received signal, unlike in previous work where only the cumulants of the di®erentially processed received signal are used. The motivation for our approach comes from the fact that for a given data size, the estimates of the moments of the received signal have less variance compared to the cumulants of di®erentially processed received signal. Simulations are used to illustrate the performance of the proposed algorithm.

Abstract

There has been a recent interest in the application of Multiple-Input Multiple-Output (MIMO) communication concepts to radars. While traditional phased-array radars, also referred to as Single-Input Multiple-Output radars, transmit coherent waveforms from their many antenna elements, MIMO radars can transmit incoherent waveforms from their transmitters, which offer additional benefits like spatial diversity and spa- tial resolution. In the recent literature, optimization of orthogonal frequency hopping waveforms for MIMO radars has been discussed. This optimization is based on a ‘cost function’ derived from a newly formulated MIMO radar ambiguity function. Existing literature however makes the assumption of small target Doppler. In this thesis, we first extend the scope of this ambiguity function to large values of target Doppler. We then introduce the concept of hit-matrix in the MIMO context. This is based on the hit-array, which has seen extensive use in the context of frequency- hopping waveforms for phased-array radars. We then propose new methods to obtain optimal waveforms in both the large and small Doppler scenarios. Under the large Doppler scenario, we propose the use of a cost function based on the hit-matrix which offers a significantly lower computational complexity as compared to an ambiguity based cost function, with no loss in code performance. In the small Doppler scenario, we present an algorithm for directly designing the waveform from certain properties which can be obtained from the ambiguity function in conjunction with the hit-matrix. Finally, we address the problem of designing frequency-hopping waveforms which yield a desired ambiguity function. This method is called “weighted optimization” wherein we mask the cost function used in the heuristic search algorithm to reflect the properties of the required ambiguity function.

Abstract

This section provides a basic overview of the structural design and work description behind the cache mechanism for machine translation system. This section will also provide a brief and compact representation of our new cache system. Cache memory is a very popular concept in computer science. With the help of cache memory we achieve running time performance of system by maintaining most likely accessed data in fast memory, and we call it cache memory. Cache memory is usually in hardware which is managed by operating system but here we are simulating the behavior of cache memory by selecting appropriate data structure and related mathematical function and placing it in local fast memory. The MT system where this cache is supposed to be used takes natural language sentences online from user and generates in target natural language. As, it is known any machine translation work requires large amount of computation and memory space as well. In such environment, it is clearly possible to reduce processing time using a cache memory.

Abstract

In this thesis, models are proposed for statistical machine translation and word-alignment which are well-suited for translation between English and Hindi (or any other Indian Language (IL)) apart from addressing the limitations of existing machine translation systems. In our models, we allow the flexibility of using linguistically motivated features but leave the learning to machine based on data. The purpose is better translation quality. Some of the issues in building a statistical translation system from English to Hindi are, 1. Large distance word-reordering. 2. Morphological richness of Hindi. 3. Lack of large training dataset. 4. Importance of function words in conveying grammatical roles in ILs. 5. Translation/Word-alignment of multi-word expressions. I address these issues in the statistical machine translation and word-alignment models proposed by us. The main contributions of my work are the two approaches that I propose for machine translation. They are, 1. Discriminative machine translation using global lexical selection (GLS approach): In this system, I propose a novel approach for machine translation using global lexical selection. Global lexical selection allows us to not rely on word-alignment information (which are often unreliable) between sentence pairs. Also, the emphasis in this approach is on lexical selection rather than lexical reordering. Indian languages are relatively free word order and hence, lexical selection (specially the function words) plays the most important role while translating to them. The results of this approach are presented in Chapters 4 and 5 [128, 129]. 2. Dependency based statistical machine translation system (Vaanee): I propose a dependency based statistical system that uses discriminative techniques to train its parameters. The use of syntax (dependency tree) allows us to address the large word-reorderings between English and Hindi. Discriminative training allows us to use rich feature sets, including linguistic features that are useful in the machine translation task. I present results of the experimental implementation of the system in this thesis (see Chapter 6) [134]. The model for discriminative machine translation and reranking using Global Lexical Selection (GLS) performed better than the state-of-art system (Moses). The main reasons for the success of this model are, 1. Not relying on word-alignment information. The dataset available for English-Hindi is small and noisy. This results in a low quality word-alignment between the sentences of this language pair. As the GLS based models do not depend on word-alignment, they performed very well. 2. The GLS based model relies on a global context in the source language to generate words in the target. This helps in an accurate generation of the target language words. In our approach, we used GLS to generate high quality local word groups, where the function words are associated with their corresponding content words. The high accuracy of predicting local word groups results in an accurate generation of function words which are the key grammatical role markers in Indian languages. This, in turn, results in target sentences that have high fluency. The high quality generation of lexical words in target also helps in reranking sentences generated by the state of art translation system. The results obtained are better than the state of art results. In the thesis, we present an experimental implementation of the discriminative machine translation model. This system provides the flexibility to incorporate rich linguistic information into a statistical machine translation system. It should act as an excellent platform for future experiments in syntax based statistical translation. It is available for download at the link: http://shakti.iiit.ac.in/sriram/vaanee.html. However, this model, which uses rich linguistic information doesn’t perform better than the state-of-art machine translation system mainly because of the availability of poor quality training data. Because of the nature of the dataset, the power of this kind of a model hasn’t been as effective as expected. In addition to the main contributions, I present two supporting contributions that are crucial building blocks of my work. The first work is on discriminative word-alignment. In this work, I show that the features representing compositionality of multi-word expressions, syntactic divergence and alignment structure help in the task of word-alignment and subsequently, in the task of machine translation (see chapter 7 [133, 131]). In the second supporting work, I propose various measures for computing the relative compositionality of multi-word expressions, of verb-object type in English and noun+verb type in Hindi (see Chapter 8 [130, 127, 85]). In the Introduction chapter, I build the background on the problem of machine translation and the various approaches

Abstract

In recent years, we have witnessed a tremendous growth in the volume of text documents available on the Internet, digital libraries, news sources, company-wide intranets and so on. This has led to an increased interest in developing methods that can help users to effectively navigate, summarize, and organize this information. The ultimate goal is to help users find what they are looking for. There are mainly two approaches to enhance the task of document organization: supervised approach, where pre-defined category labels are assigned to documents based on the likelihood suggested by a training set of labeled documents; and unsupervised approach, where there is no need for human intervention or labeled documents at any point in the whole process. Fast and high-quality document clustering algorithms play an important role towards the goal of document organization, as they have been shown to provide both an intuitive navigation/browsing mechanism by organizing large amounts of information into a small number of meaningful clusters. It can be noted that the performance of information retrieval method depends on feature selection and weight assignment methods which are being employed to extract the features from the documents. Normally, features from a document are selected based on some criteria (e.g. Frequency). These features are weighed by TF-IDF (Term frequency and inverse document frequency) method. There are research efforts to improve the performance of feature extraction methods by extending the concepts from the areas of ontology, open web directories and so on. The vector space model is one of the most widely used models to represent text document for computing similarity. Cosine similarity is a popular method to calculate similarity between two vectors. The similarity computation by cosine similarity method is influenced by common features (and their weight) between two document vectors. It can be observed that the cosine similarity is unable to find similarity based on the meaning or semantics. For example, consider two documents, one with a word “BMW” and the other having a word “Jaguar”. The similarity computation with cosine similarity between these two documents equals to zero. Even though these two documents have different vocabulary, they are semantically same as both refer car models. In the thesis, we made an effort to capture the context of the document to incorporate it into similarity computation. We exploit the generalization ability of hierarchical knowledge repositories such as “Open Web Directory”, in which, a given term relates to a context, and the context, in turn, relates to a collection of terms, then we can extract related terms for each term in the document. In a simple generalization hierarchy of web directory, a term at a higher level is a generalized concept for all the terms under this node e.g. sport is a generalized concept for football, cricket, baseball etc. We can add these generalize terms along with their weight to the document vector. By enriching tthe document with generalized contextual terms there is a scope to increase the number of common terms, thus the similarity between two documents. An improved approach is also proposed in which these generalized terms are later removed from the document vector leaving behind only the document terms. So, as output, we get a document vector with boosted weights and the dimension space of the document vector remains same. In addition to feature extraction and feature weighting of a document vector, we propose a method to improve clustering quality by assigning weight to the feature vector of a cluster. The contribution of this thesis is threefold: 1. We propose a framework that performs feature generation (using open web directory) and enriches the feature vector with new, more informative and discriminative features. We use topic paths of a term to obtain related contextual and generalized terms. 2. We propose an improved term weighting method called BoostWeight by considering the semantic association between the terms. BoostWeight method increases the weight of terms if they have common generalized term. 3. We propose a methodology to refine a given set of clusters by incrementally moving documents between clusters. More weight is given to the representative and discriminative features of a cluster. To compare the performance of proposed approaches with existing weighting approaches, we have conducted clustering experiments on two data-sets: WebData and Reuters21578 news corpus dataset. Experimental results show that the proposed approach improves clustering performance over other term extraction and weighting approaches.

Abstract

Multicarrier Code Division Multiple Access (MC-CDMA) is an attractive technique for high speed wireless data transmission in view of its advantages over orthogonal frequency division multiplexing. In this thesis, we analyze the performance of fully loaded downlink MC-CDMA systems with minimum mean square error (MMSE) equalizer in the presence of residual frequency offset (RFO) in multipath Rayleigh fading channels. We first show that as the SNR is increased beyond a value, referred as threshold SNR, the performance degrades. We then analyze the cause for this behavior and propose a remedy to prevent the degradation by regularizing the co- efficient(s) of the equalizer, and use the regularized equalizer for SNRs beyond the threshold value. The threshold SNR depends on the RFO and the profile of multipath channel. We suggest two methods for estimating this SNR, one gives close to the true value but requires the knowledge of RFO and the channel state information (CSI), while the other gives an approximate value but requires only CSI. We first show that if the actual value of RFO is less than the assumed, the threshold SNR estimate based on the assumed RFO will still be appropriate. Next, we show that the regularization based on the approximate value also prevents the degradation, but the performance at higher SNRs is slightly poorer compared to that with the better estimate. Numerical and simulation results are provided to support the analysis.

Abstract

Monitoring or surveillance by machines has become very popular nowadays because of the advantages that it provides over monitoring by human beings. Remote sensing has a huge potential to monitor the events on a large scale that millions of cameras put together on the surface of earth cannot monitor. Remote sensing data analysis involves examining the data using various viewing and interpretation devices to analyze the remotely sensed digital data. Reference data about the resources being studied are used when and where available to assist in the data analysis. Results of data analysis are then compiled generally in the form of hardcopy maps and tables or as computer files that can be merged with other ‘layers’ of information in a geographic information system (GIS). Finally, the information is presented to users who apply it to their decision making process. Image classification is one of the most widely used techniques on remote sensing data. The overall objective of image classification procedures is to automatically categorize all pixels in an image into land cover classes or themes. Land cover can be defined as the physical material at the surface of the earth. The range of projects, programs and organizations that use land cover maps to meet their planning, management, development and assessment objectives is expanding every day and the remote sensing community has been challenged to produce regional- to global-scale data sets on a repetitive basis that characterize ‘current’ Land Use Land Cover (LULC) patterns and also document all the LULC changes, however large or small they be. Spectral pattern recognition refers to the family of classification procedures that utilize the pixel-by-pixel spectral information as the basis for automated land cover classification. That is, different feature types manifest different combinations of digital numbers based on their inherent spectral reflectance and emittance properties. Spatial pattern recognition involves the categorization of image pixels on the basis of their spatial relationship with pixels surrounding them. Temporal pattern recognition uses time as an aid in feature identification. The multitemporal data that is now available because of better revisit times of the satellites allows us to characterize objects based on their dynamic processes rather than static properties like color, shape, etc and this is being successfully demonstrated in this research for a few classes. In case of multi-temporal studies, atmospheric influences and sensor malfunctioning leads to data gaps and data anomalies that have to be corrected for and is usually a preprocessing stage in all time series studies. This research has adopted a technique called local maximum fitting to smooth the noisy time series. Local maximum fitting combines temporal window operation and harmonic series fitting to provide a faithful representation of the ground process. We have viewed the classification of the pixel-time trajectories as a curve matching problem comparing the unknown time series of a pixel to the temporal signatures available in the library derived from the training samples obtained either through our proposed automatic method or any other method. An important part of curve matching problem is the definition of similarity measure. We have used various similarity measures and concluded that constrained dynamic time warping is best suited for classifying enhanced vegetation index (EVI) time series. Conventional classification methods inherently use Euclidean distance as a similarity measure even for time series classification. Through our empirical experiments, we have concluded that a Sakoe-chiba radius of 4 (equivalent to 2 months) for constraining DTW (Dynamic Time Warping) provides the best classification accuracy which is reasonable as there can be a maximum shift of this period in growing practices. The classification accuracy for Dharwad district was 86.57% with Euclidean distance as compared to 90.89% with constrained dynamic time warping distance measure for the moderate resolution imaging spectroradiometer (MODIS) dataset. The results obtained though the proposed classification procedure were also being compared with the conventional kNN and SVM classifiers. kNN classifer with k = 5 provided a classification accuracy of 79.75% and SVM classifier, an accuracy of 83.89%. The low classification accuracy of these classifiers for time series satellite image classification can be attributed to the use of Euclidean distance in the feature space. Whereas the actual supervised classification of satellite image is a highly automated process, assembling the training data needed for such classification is anything but automatic. In many ways, the training data needed for land cover classification is both an art and a science. It requires close interaction between the image analyst and the image data thus making the clas