Abstract

Image fusion is the process of combining images from different sensors, viewpoints or foci to form a composite image without introducing any artifacts. The sensors can have different characteristics like viewpoints, focus or are from different sensors like visible light cameras, infrared camera or X-ray cameras. Most of the fusion algorithms require the input images to be spatially aligned for efficient results. Thus the process of image registration is a vital precursor to fusion and helps to bring these images onto a common representation. Image fusion enhances the information content within a single composite image and thus aids in human perception and machine processing of such images. Image fusion and registration have found many applications in medical imaging in MRI scanner, super resolution, object identification and object tracking and many other applications. Often such applications are used in on field camera systems which require real time results for quick decisions. The modern algorithms for image registration like scale invariant feature transform (SIFT) and speeded up robust features (SURF) suffer from low execution speeds on generic hardware like PC and graphics processor unit (GPU). Moreover, the high memory access and intensive computation require high power for the execution of these designs on generic hardware. The possibility of data parallelization and ability to manage high memory requirements make these algorithms an ideal candidate for field programmable gate array (FPGA) based implementations. This work presents a novel architecture of feature detection using SIFT and image fusion using Laplacian pyramid decomposition on Xilinx Virtex 5 ML505 FPGA. In this work we focus on fusing images from multiple sensors. In the feature detection part, parallelization of processing has been exploited in feature generation and a look up table based approach in gradient property calculation has led to significant gains in speed while simultaneously reducing complexity and maintaining good results. For the Laplacian fusion, data parallelization has been exploited along with a re-usable cache based design to reduce device utilization and provide effective results. The design has been optimized to provide an output of 30 fps for an image of 320x256 for registration and fusion while providing lower power consumption than GPU based architectures.

Abstract

Raytracing has been primarily used for generating photo-realistic imagery. Once considered as an offline algorithm, raytracing has primarily become realtime or near realtime with the advancement in computer hardware power. GPU computing has enabled the general purpose usage of graphics cards which were primarily designed for for graphics rendering purposes. Raytracing could be considered as a very embarrassingly parallel process in which each pixel's contribution to the final image is computed independent of one another. The tremendous power of GPUs has been been utilized for vastly improving the performance of almost all the functions in a raytracing pipeline. The raytracing pipeline for rendering images fundamentally consists of three phases. The first is an acceleration structure construction phase which involves creating a data structure. It provides very fast results for intersection queries for the rays traced within the scene and all the objects contained within the scene. The second is the traversal phase in which each ray is traced within the scene employing the aforementioned data structure. The final optional phase is shading in which each hit point is shaded based on a shading algorithm. The shading algorithm determines the color of the pixel of the image for which a particular ray was traversed and the shading performed for all the rays for all the pixels computes the final rendered image. In this thesis we examine two problems associated with the GPU raytracing pipeline and provide two new approaches for them. In the first work, we develop a novel parallel algorithm for performing raytracing without constructing any explicit acceleration structure on the GPU. This decouples the long standing notion of creating and storing a separate acceleration structure followed by tracing rays through the structure. Our algorithm creates an implicit hierarchical acceleration structure and traverses the implicit structure at each phase of the algorithm in tandem. Parallel construction algorithms for acceleration structures are difficult to implement on the GPU and also have a large memory footprint to store the resulting structure. Compared to CPUs the amount of memory available to GPUs is limited and hence methods that work on very small memory footprints are of utmost importance. Our algorithm is conceptually very simple, utilizing efficient parallel GPU primitives such as sort and reduce. Further our algorithm has small memory requirements compared to methods that construct acceleration structures thereby making it a suitable candidate for the GPU. Since our method employs a traverse-while-construct method, it is particularly very useful for animated scenes in which the acceleration structure has to be created for each frame in a traditional raytracing pipeline. We implement our algorithm on a CUDA enabled machine and show that our algorithm can perform much better than the serial CPU version of the algorithm. Our second work is targeted towards the problem in the shading phase of the raytracing pipeline. Traditional renderers employed in the production rendering are primary unidirectional path tracers which traces rays from the camera into the scene. However the path tracing algorithm has difficulty in rendering scenes with complicated lighting scenarios which provide very good aesthetic value to certain kinds of scenes. Bidirectional path tracing on the other hand traces rays from both the camera and the lights within the scene and hence able to render scenes with complicated lighting scenarios much more effectively than path tracing. Current production renderers are primarily CPU based and only a few have started to employ GPUs for the entire pipeline. Limited memory compared to CPUs was the original factor for not employing GPUs. However with current generation GPUs having much more memory than earlier generations, GPUs have been slowly adopted for path tracing based pipelines. However bidirectional path tracers that are GPU based are yet to be fully employed in a full production rendering scenario. Our work is aimed providing a solution that tries to bridge the gap that enables bidirectional path tracing to be used in the production rendering scenario which involves complex materials. We specifically provide a new connection mechanism employed in the light vertex cache - bidirectional path tracing algorithm (LVC-BDPT) for improving shading efficiency as well as a sort based pipeline for improving the runtime performance of the algorithm on the GPU. We show that we perform much better than the unoptimized version of the algorithm as well as providing much better quality for the same amount computations performed.

Abstract

Road infrastructure in countries like India is expanding at a rapid pace and along with it the need to build and maintain a comprehensive road information system (RIS). Even though static information like road names and road geometry can be collected by a one-time survey, road characteristics like road condition, traffic density, directionality, surface type etc., keep changing over time, posing a challenge to maintain an up to date RIS database. The common satellite based approaches are not sufficient to cover a number of road characteristics. Current ground based data collection schemes are either not affordable due to the use of expensive equipment or not scalable due to its time consuming paper-and-pen data collection approach. This necessitates the search for alternative technologies for road data collection. New systems need to be built using such technologies, which integrates information extraction methods and algorithms best suited for road data collection. Unmanned aerial vehicles (UAVs) are increasingly being used as a low altitude remote sensing platform. Providing cheap, on-demand high resolution aerial imagery and video makes them a unique data collection platform when compared to satellites and big aircrafts. An innovative data collection scheme that utilizes the trajectory information of the moving vehicles from the aerial video of UAVs, to robustly extract road characteristics like road traffic density and directionality has been proposed. The road directionality extraction procedure correctly extracted all node to node directionality attributes on the final evaluation dataset. Also the road density estimation procedure produced the density estimates with a least error percentage of 5%, strongly contending for the use of UAVs in road data collection. Another technology that has the potential to be used as a tool for extensive data collection, is the smartphone. The availability of a number of sensors, networking capabilities and being ubiquitous make them an ideal data collection platform. A smartphone based prototype system MAARGHA, was developed to collect road condition and road surface type. MAARGHA has been tested across different road conditions and sensor data characteristics to assess its potential applications in real world scenarios. The developed system achieves higher information levels when compared to state of the art road condition estimation systems like Roadroid, while achieving road surface type classification accuracy range of 60% to 100%. While the proposed aerial and ground based systems have initially targeted the collection of few road characteristics, they can be extended further to collect many other data as well. Together, the systems provide a unique solution which is more feasible to be used for extensive and frequent RIS data collection. Hence they can be called as persistent surveillance systems. Such data collection infrastructure for RIS can have significant impact on road transport domains like the road infrastructure management, autonomous vehicle navigation, and intelligent routing services.

Abstract

As we move towards an increasingly globalized and knowledge-based economy, the ability to discover and share information across language and cultural boundaries has become more and more crucial. With the advent and rapid development of the Internet, the amount of information generated in different languages and disseminated via the World Wide Web (WWW) and social media platforms is growing exponentially. As the Internet becomes more ubiquitous and pervasive, its users have become linguistically more diverse and culturally more heterogeneous. It is thus of utmost importance to ensure that online information resources and services are efficiently and equitably accessible to all users, regardless of their linguistic and cultural backgrounds. Unfortunately, owing to language barriers and linguistic digital divide, the majority of the world's populations, including native speakers of resource-scarce African languages, have long been denied the opportunity to access and benefit from online resources. Since most of the current major search engines and commercial Information Retrieval (IR) systems have primarily focused on wellresourced European and Asian languages, they have paid little attention to the development of Cross- Language Information Retrieval (CLIR) for resource-scarce African languages. The need for exploring and building more specialized information systems that enable speakers of African languages to discover valuable information beyond linguistic and cultural barriers has, therefore, become more urgent today than ever before. Taking these facts into consideration, this study is aimed at exploring and building an experimental CLIR between one of the severely under-resourced African languages, (i.e. Afaan Oromo) and one of the most commonly used online languages, (i.e. English). We have focused on developing and evaluating the first Oromo-English CLIR (hereafter also referred to as OMEN-CLIR), which is designed to make effective use of limited linguistic resources to search and retrieve relevant information across language and cultural boundaries. Although Afaan Oromo is one of the major indigenous African languages that is widely spoken by more than 35 million people in the Horn of Africa, it is still considered as one of the most under-resourced languages, especially where being resourced is measured by the extent to which a given language is supported by computational linguistic resources and information access technologies. Afaan Oromo poses a huge challenge to the development of natural language processing and information access technologies, not only because it is one of the most resource-scarce languages, but also because it has very rich and complex morphological processes. Unlike English, Afaan Oromo is a highly synthetic language with a very productive inflectional and derivational morphology. In this study, we have focused on exploring and building basic linguistic resources and IR tools required for designing and developing OMEN-CLIR. Some of the major linguistic resources and translation tools that we have designed and developed during the course of this study include a generic computational model of Afaan Oromo morphology, a machinereadable bilingual dictionary, a rule-based Afaan Oromo stemmer, lists of Afaan Oromo suffixes and stopwords. While our machine-readable Oromo-English dictionary has been adopted and used as a main source of knowledge for query translation, our Afaan Oromo stemmer has played a key role in identifying and normalizing word form variations. Apart from designing and building the components of OMEN-CLIR, for which the necessary linguistic resources and translation tools have been crafted from scratch, another major contribution of this study is to assess and evaluate the performance of the proposed retrieval system. In order to assess the performances of OMEN-CLIR, we had participated in one of the well-recognized international Cross- Language Evaluation Forums (i.e., CLEF campaign) over the past couple of years. The main focus of our evaluation in two different CLEF annual campaigns was to assess how well OMEN-CLIR performs in international and standard evaluation competitions like the ad-hoc track of the CLEF campaign. Besides a number of official runs that we had submitted to the ad-hoc tracks of the CLEF-2006 and CLEF-2007 campaigns, we have conducted various additional retrieval experiments to improve the performances of OMEN-CLIR. The evaluation results have been found to be very promising and encouraging, given the disparity of the languages involved and the limited amount of linguistic resources used for developing OMEN-CLIR. In one of our official retrieval experiments in which we have applied our Afaan Oromo stemmer, our CLIR system has achieved an average mean precision (AMP) of 29.90%, which is about 67.95% of a monolingual baseline. In general, the evaluation results show that it is viable to design and develop a CLIR system for

Abstract

Many tasks in computer vision, such as action classification and object detection, require us to rank a set of samples according to their relevance to a particular visual category. The performance of such tasks is often measured in terms of the average precision (AP). Yet it is common practice to employ the support vector machine (SVM) classifier, which optimizes a surrogate 0-1 loss. The popularity of SVM can be attributed to its empirical performance. Specifically, in fully supervised settings, svm tends to provide similar accuracy to AP-SVM, which directly optimizes an AP-based loss. However, we hypothesize that in the significantly more challenging and practically useful setting of weakly supervised learning, it becomes crucial to optimize the right accuracy measure. In order to test this hypothesis, we propose a novel latent AP-SVM that minimizes a carefully designed upper bound on the AP-based loss function over weakly supervised samples. Using publicly available datasets, we demonstrate the advantage of our approach over standard loss-based learning frameworks on three challenging problems: action classification, character recognition and object detection.

Abstract

Traditional methods of computing and utilization of computing resources involved having dedicated hardware. Each company or individual had to purchase hardware and set it up for each task. If the utility of the hardware and its requirements were fixed, then this approach made sense, however in most cases the utility and the requirements kept varying. Sometimes people required large amounts of resources for short amounts of time (like in the case of scientific computation) or sometimes people needed the ability to scale up and down the number of systems based on the demand and dedicated systems were not profitable in such a case as it involved high upfront costs and becomes a resource burden once the work is done. Resources can be of different types like computation(CPU), storage(distributed filesystem storage), network, key-value stores, databases, etc. Enter the realm of cloud computing. It provides a profitable way of renting resources at the time of need and disposing them off by releasing those resources to be used by others and we get charged only for what we use. With data centers spread across the globe and the help of cloud computing, we can localize resources closer to the end user to improve performance and experience. Cloud Computing is based on the utilization of commodity hardware, one of the reasons that makes it profitable. True homogeneity of the different resources will make it less profitable. Hence, more than often, the systems are heterogeneous in nature. They will have different CPU clock rates, different memory performances, different storage capablities (like tape, Solid-State Disks, Hard-Disks, etc.) , different network capabilities, different kinds of switches connecting them. Even if somehow, one manages to acquire truly homogeneous systems, the dynamic nature of today’s systems and softwares will inherently make them heterogeneous in nature. There will be difference in the load and utilization of the different resources and this might introduce heterogeneity in them. Some network links might be over-utilized, some under-utilized, some disks might store more data ,some nodes might become hotspots due to the uneven distribution of data/computation. This kind of heterogeneity is dynamic. We need to develop systems that are aware of this type of inherent heterogeneity and enable it to adapt to the constantly changing environment. Storage in a distributed environment has multiple attributes to optimize on. We have different kinds of storage , each with different amount of capacity and performance characteristics. We need to use solid state drives and memory more judiciously compared to tapes or hard disks. Each one of these devices have different power consumption, cooling requirements and network requirements. So how do we decide where to place the data such that we optimize on a combination of these factors. We studied tackling this problem in 2 different kinds of storages.  Distributed block based file systems such as Hadoop Distributed File System(HDFS)  Distributed Key-Value stores We studied 2 different approaches for these two areas. For block based distributed file systems, we proposed an approach of modelling the different parameters of heterogeneity such as latency, bandwidth, power usage, etc as a distance measure in a multi-dimentional space and then performing dimensionality reduction on it to finally reduce it to a simple optimization problem. For the Key-Value store, we concentrated on modifying how the partitioning and assignment of servers occur in consistent hashing and optimized it on the different parameters by treating it as a bidding problem with the different systems in the consistent hash ring being the bid items and the partitions being the bidders. In both cases, we developed a prototype and benchmarked them thoroughly using both standard benchmarks and different load scenarios to test their adaptive nature. They showed better performance and interesting load-balancing and placement characteristics. The next area that we dealt with is networking. In a datacenter, the network contains data flows from different kinds of applications. Each kind of flow has a requirement. For example, Youtube is sensitive to bandwidth, VoIP traffic is sensitive to latency and network jitter, etc. In traditional networks, reacting to these flows were very hard, as the protocols defined were meant to be generic. However, with the advent of software defined networking, we are no longer restricted to these legacy protocols. We can define protocols that are tailored to a network. We created a SDN controller based on openflow which uses a pre-defined profile for each one of these data flows. We intelligently route the different flows from different applications based on this information thereby optimizing on the combination of parameters defined in the profile. We tested it under different load scenarios and showed how the heterogeneity awareness h

Abstract

We live in the digital age. Computing devices ranging from desktop computers to contemporary mobile devices have become integral part of our daily life. Not surprisingly, designing human computer interfaces (HCI) that are efficient and easy to use has emerged into an important area of research and practice. The holy grail of HCI research is to design intelligent interfaces that can understand the behavioral state of the user and provide an appropriate response. Research on multimodal interfaces is one of the important topics in the field of HCI. Multimodal interfaces are those human–computer interfaces which enable human computer interaction in several modalities, such as, visual, audio, tactile (haptic), etc., simultaneously. Research in this area has been inspired by the fact that human interaction with real world is multisensory and multimodal interfaces would hence allow for more natural interaction. One of the lesser explored subareas is the design of multimodal affective interfaces. These multimodal interfaces are capable of emotionally intelligent behaviour i.e. respond according to the emotional state of the interface user or give feedback to elicit particular emotion. The goal of this thesis is to design multimodal affective feedback – generating feedback that presents emotional cues in multiple modalities that can elicit a target emotion in users. To be able to develop interfaces capable of such feedback, there are many necessary things we still do not understand. One of these is how emotional cues presented through different modalities (visual, audio, haptic, etc.) interact and specially what role haptics play. Understanding the role of haptics in multimodal affective feedback is precisely what this thesis work deals with. First of all, well structured affective visual, audio and haptic datasets are required in order to study the interaction of emotional cues presented through these modalities. Luckily, affective visual and audio datasets exist in literature already but there is no standardized affective haptic dataset. As these visual (IAPS) and audio (IADS) datasets are not verified for Indian participants, validation tasks have been performed first. Then, depending on the target devices, the constraints put by human skin sensitivity and the haptic actuator available for experimentation, a well structured affective haptic dataset is created by varying four parameters – intensity, frequency, waveform and rhythm. Next, a set of experiments explore the visual and haptic modalities for affective cues interaction, first at the level of two emotion dimensions – arousal and valence; and then explore what role low-level features of haptic stimuli play in the found interactions. Based on the results of these experiments, guidelines to help interface designers/researches have been laid down. Similar experimentation procedure is followed for exploration of audio-haptic multimodality and another set of guidelines have been generated based on the results of these experiments with audio-haptic stimuli. Finally, an authoring tool framework has been presented. This authoring tool generates appropriate haptic stimuli to accompany a visual or audio stimuli given a target emotion. This tool utilizes the results and guidelines generated.

Abstract

Computational geometry is the branch of computer science which deals with computation of geometric functions. It has applications to various fields of computer science such as computer graphics, robotics, VLSI, etc. Range query problems are a set of problems where data structure has to be designed to preprocess the input such that given a query range, an operation has to be supported on that particular range of inputs. These problems are significant today because the huge amount of data makes it relevant to have small subsets of it ready to be queried. We consider the planar convex hull range query problem. Convex hull is an important geometric construct because it is performed as a preprocessing step for a large class of problems. Let P be a set of points in the plane. We preprocess these points into a data structure such that given an orthogonal range query, we can report the convex hull of the points in the range in O(log 2 n + h) time, where h is the size of the output. The data structure uses O(n log n) space. This improves the previous bound of O(log 5 n + h) time and O(n log 2 n) space. Given a range query, it also supports extreme points in a given direction, tangent queries through a given point, and line-hull intersection queries on the points in the range in time O(log 2 n) for each orthogonal query and O(log n) time for each additional query on that range. These bounds are independent of h, the number of points on the hull. These problems have not been studied before. We also consider the generalized reporting versions of the planar range maxima problem. We solve the planar range maxima problem for two-sided, three-sided and four-sided queries. We achieve a query time of O(log n + c) using O(n) space for the two-sided case, where n denotes the number of stored points and c the number of colors reported. For the three-sided case, we achieve query time O(log 2 n + c log n) using O(n) space while for four-sided queries we answer queries in O(log 3 n + c log 2 n) using O(n log n) space.

Abstract

Modern day organizations use databases to manage information for their business operations. Since the introduction of DBMSs in the mid-1960s, database technology has made significant advances in terms of functionality and performance. As a result, modern day database systems can process a large number of complex queries on any database. An important area of database research focuses on improving the usability of databases. Research efforts are ongoing to develop efficient user interfaces to access information from databases, focusing not only on the design of user-interfaces but more importantly, improving the process of user interaction and the underlying architecture. Information Requirement Elicitation (IRE) was proposed in the literature, which recommends a framework for developing interactive interfaces, allowing users to access database systems without having prior knowledge of a query language. An approach called ‘Query-by-Object’ (QBO) has been proposed in the literature for IRE by exploiting simple calculator like operations. In QBO, the database is represented with the help of objects and operators are provided to relate information between objects. However, the QBO approach was proposed by assuming that the underlying database is simple and contains a few tables, each of small size. Large databases have complex database schemas. Given a large number of tables in a schema, the number of objects is also large. Locating information of interest and how it is related to other objects becomes a challenging task for the user. Also, the number of possible operations between objects increase significantly. In this thesis, we investigate opportunities for a better organization of options available to the user for interacting with the database without making any changes to the organization of data at the physical layer. First, we try to determine entities in the schema that collectively represent a conceptual unit or topic in the database. Similarly, we try to organize instances of an object by organizing them into a hierarchy based on attribute values. The organization of objects into topics allows the user to relate information at a higher level of abstraction and leverages the number of operational pairs that needed to be defined in QBO. We also evaluate the research decisions through system analysis and usability studies, which were conducted with the help of a fully functional prototype developed for a real, complex database. An important process in the proposed approach is discovering topical structures in the database schema. The problem has gained attention recently in the database community as the problem of Schema Summarization. Schema summarization for a relational database schema is a challenge that involves identifying semantically correlated elements in a database schema. Research efforts are being made to propose schema summarization approaches by exploiting database schema and data stored in the database. Existing efforts for schema summarization are data oriented. In scenarios where data is inconsistent or insufficient, existing approaches suffer. In this thesis, we explore the database documentation as an information source. We aim to utilize the schema and database documentation to provide an efficient schema summary. We propose a notion of table similarity by exploiting the referential relationship between tables and the similarity of passages describing the corresponding tables in the database documentation. Using the notion of table similarity, we propose a clustering based approach for schema summary generation. Experimental results on a benchmark database show the proposed approach, although independent of data stored in the database, is as efficient as the data-oriented approaches.

Abstract

The primary computing device interfaces are moving away from the traditional keyboard and mouse inputs towards touch and stylus based interactions. To improve their effectiveness, the interfaces for such devices should be made robust, efficient, and intuitive. One of the most natural ways of communication for humans has been through handwriting. Handwriting based interfaces are more practical than keyboards, especially for scripts of Indic and Han family, which have a large number of symbols. Pen based computing serves four functionalities: a. pointing input b. handwriting recognition c. direct manipulation d. gesture recognition. The second and fourth problems fall under the broad umbrella of pattern recognition problems. In this thesis we focus on efficient representations for handwriting. In the the first part of this thesis we propose a representation for online handwriting based on ballistic strokes. We first propose a technique to segment online handwriting into its constituent ballistic strokes based on the curvature profile. We argue that the proposed method of segmentation is more robust to noise, compared to the traditional speed profile minima based segmentation. We, then, propose to represent the segmented strokes as the arc of a circle. This representation if validated by the Sigma-lognormal theory of handwriting generation. These features are encoded using a bag-of-words representation, which we name bag-of-strokes. This representation is shown to achieve state- of-art accuracies on various datasets. In the second part, we extend this representation to the problem of signature verification. To define a verification system, a similarity metric is to be defined. We propose a metric learning algorithm based on the Support Vector Machine (SVM) hyperplanes learned to separate the training data. This results in a very simple metric learning strategy that capable of being modified to increase the number of users registered by the verification system. We experiment with this technique on the publicly available SVC-2004 database and show that this method results in accuracies applicable to practical scenarios. (more...)