Abstract

Healthy heart is a key for healthy life. Unfortunately in many cases the heart function deteriorates over a person’s lifetime, often with tragic consequences. A class of diseases involving heart functionality is termed cardiovascular disease. Among a number of such cardiovascular diseases, cardiac arrhythmia and coronary artery disease (CAD) are two of the most common and potentially life threatening diseases and are the our work is focussed around them. A primary reason for a high casualty figures caused by these diseases can be attributed to the fact that the diagnosis is not done on time. Often, the symptoms are noticeable only at a stage where the person needs immediate medical attention. Accurate diagnosis can only be done at specialized healthcare facilities by trained personnel. The diagnosis is also expensive. This limits its accessibility for major portion of population especially in rural areas. State of the art diagnosis for coronary artery disease typically involves an invasive procedure. Though this procedure is conclusive, it is still painful and risky. Assessing these challenges, there is a need for a widely accessible, inexpensive and preferably non invasive alternative. While looking for alternatives, electrocardiography or ECG has advantages of being accessible, non-invasive, and inexpensive. It is used for diagnosing cardiac arrhythmia, and as a screening test for coronary artery disease. However this screening is inconclusive and other techniques are recommended. Another non invasive technique, phonocardiography or PCG suffers from complex design and sensitive equipment. Which brings us to yet another well known technique, most commonly used for pulse oximetry, the photoplethysmography (PPG). Photoplethysmography can be defined as study of blood volume changes through light. It is non invasive, inexpensive and can easily be made portable thus making an ideal candidate for further investigation. PPG is also very suitable for use in wearable devices technology and such devices are used for ambulatory monitoring. Having all the desired characteristics, PPG is further investigated towards diagnosing cardiac diseases. As PPG as a technique already exists and is widely used, this work is aimed at developing techniques to analyse the PPG data towards possible diagnosis of cardiac diseases. Phtoplethysmography has its own challenges. It has high sensitivity and susceptibility to motion. This is particularly concerning for detecting arrhythmia and coronary artery disease alike as it wrongly affects heart beat detection as well as degrades the natural characteristics of the signal. First contribution of this work is a technique to estimate heart rate in presence of motion induced artifcats using fuzzy entropy of the signal. Once accurate heart rate is estimated, the input signal is tested for possible cardiac arrhythmias such as tachycardia, bradycardia, asystole, ventricular tachycardia and ventricular fibrillation. The fuzzy entropy based method poses some implementation limitations as it is computationally inefficient and requires initial user input. Another approach is developed to overcome these limitations. A quality index is assigned to each pulse. The artifact portion is removed using an appropriate threshold. The remaining clean portion of the signal is used for arrhythmia detection. This technique is faster and more accurate than fuzzy entropy based technique and much more useful for arrhythmia detection. Another important contribution of this work is to explore PPG for detecting coronary artery disease. This involves analysing the morphology of the PPG signal and its second derivative. Characteristic points are obtained from the PPG waveform and its second derivative. Temporal position of these characteristic points is used as a distinguishing feature to classify between healthy subjects and CAD patients. This analysis is carried out using invasive arterial blood pressure (ABP) signal as well. Supervised classification using support vector machine is employed for classifying healthy subjects and CAD patients. It is observed that higher classification accuracy was obtained using PPG signal compared to ABP. Despite certain limitations, we present proof to suggest that PPG can be effective in detecting certain cardiac arrhythmias and coronary artery disease.

Abstract

Change is inevitable and everywhere. Resources, ecosystem, biophysical environment, and land use/cover on the surface of the earth undergo continuous change over time and space. Land cover is the layer of soil and biomass, including natural vegetation, crops and man made infrastructures that cover the land surface. Land use is the purpose for which human exploit land cover [Verburg et al., 2000]. LULC change is probably the most important form of global environment changes due to its direct relevance with human existence and spatio-temporal nature. The land use changes also have significant implications in climatic changes as well [Scavia et al., 2002], which in turn brings the modification in future land use change. There is also a considerable impact of human intervention on ecology and thus land use land cover change, studying these changes over a considerable time frame reveals the complex yet predictable nature of the change. Modelling of these land use changes can prove to be very much useful in order to understand and predict future scenarios. Land use modelling requires analysing the biophysical and socio-economic drivers for land use change and then incorporating these to study the impact of human dimensions on LULC dynamics. The models help us understand the LULC changes for different socio-economic scenarios within its defined biophysical context. This thesis aims at the study, analyse and model the LULC changes taking place in the Godavari river basin in the country of India, and to predict the LULC map of 2025 for the basin. The whole process involved creation of Land Use, demographic, socio-economic, topographic, climatic, infrastructure and biophysical database, Identifying the various change inducing drivers and processes for each class and then modelling the database using both agent based and statistical techniques. The Godavari river basin encompasses an area of 3,13,346 km square across the States of Maharashtra, Andhra Pradesh, Madhya Pradesh, Orrisa, Chhattisgarh and a small part of Karnataka. The major LULC category in the basin is cropland, which forms almost 57% of the geographical area of the basin. Forests occupy about 35% of the basin area and area are located in the central regions in the states of Maharashtra, M.P. and in the eastern parts of Orrisa. Extensive shrub land areas are found in the central and western part of the basin particularly in the undulating and hilly areas and upland areas of rainfed central region. Satellite data of 1985, 1995 and 2005 was analysed to generate LULC maps at 1: 250,000 scale. Two models were then modified for the purpose of analysing and studying the LULC changes: a process based agent simulation model, Agent-LUC [Rajan and Shibasaki, 2001], , and an empirically fitted statistical regression model ILULCDMP [Ashutosh Kumar Jha, 2015]. In Agent-LUC, land cover change agents are land owners, farmers, migrants and/or policy making bodies, all of whom make decisions or take actions that affect land-use patterns and processes. By simulating the individual actions of many diverse actors, and measuring the resulting system behaviour and outcomes over time (e.g., the changes in patterns of land cover), Agent-LUC can be useful for studying the effects in land-use land cover processes. The model is designed and implemented in C++ along with QT libraries for user interface. Whereas, ILULC-DMP, calculates the correlations between the land use changes happening spatio-temporally with the driver datasets and predicts the future land-use change, by applying statistical regressions on those correlations on the current land-use and driver datasets. The model is designed and implemented in stastical modelling language R. The models first predicted the land use map of 2005 from the database of 1985 and 1995, with accuracies of .96 and .88 respectively for Agent-LUC and ILULC-DMP model when validated with the satellite derived land-use data of 2005. Then the models were run on the 2005 data to predict the land-use map for 2025. As per the further runs of the Agent-LUC model, by 2015 there will be an urban expansion of 404 square kilometres and by 2025, around 818 sq. kms of more urban area would be there in Godavari basin as compared to 2005 data. The agricultural expansion will be of 1345 sq. kms and 2752 sq. kms., both expansions will cause the deciduous forests and shrublands to decrease. The ILULC-DMP predicted map of 2025 shows an increase in built up area by 1840 sq. Kms, cropland by 4900 sq kms, decrease in forest and shrub land by 4422 sq. kms and 4290 sq. Kms. And an increase in waterbody area by 1875 sq. Kms.

Abstract

Batteries are electrochemical devices that convert chemical energy into electrical energy. An electrochemical cell of a battery composed of three major components: an anode, a cathode and an electrolyte. The electrolyte is an ionic conductor that provides a medium for transfer of ions between the electrodes of a cell. The amount of energy stored in a battery depends critically on the nature of electrochemical reactions at the electrode-electrolyte interfaces and the choice of the electrolyte. Solid polymer electrolytes (SPEs) consisting of alkali salts dissolved in a solid polymer matrix of poly(ethylene oxide) (PEO) are novel ion transporters that offer several advantages over other conventional electrolytes for use in all-solid-state rechargeable batteries. In order to fully exploit the advantages of SPEs and for rational design of novel SPEs with higher conductivity and higher energy density for future applications, it is necessary to understand the molecular-level details of the mechanism and the critical factors governing the ion conduction in these materials. Direct observation of migration pathways of ions and a quantitative dissection of their en- ergetics in solid polymer electrolytes (SPEs) are essential to understand the molecular origins of barriers limiting the conductivity of these novel materials. Depending upon the interplay between molecular packing and dynamics, SPEs exhibit a wide range of conductivity (10−9 - 10−4 S/cm) at room temperature despite their common polymer matrix. The principal driving forces controlling the degree of conductivity of SPEs including the nature of macromolecular packing, ion-polymer interactions, ion coordination structure, conformational order and mo- bility of polymers are significantly different among the SPEs. However, the precise correla- tions between these molecular factors and the ion transport in SPEs are not well established. It remains unclear whether disordered amorphous or ordered crystalline structures promote conduction of ions in SPEs. The other important challenges that remain in SPE-related re- search are the identification of low-energy ion conduction pathways, characterization of the free energy profiles and the structural and dynamical contributions to the favorable (stable energy wells) and unfavorable (activation energy barriers) ion sites along these conduction pathways. ix Detailed molecular studies are needed to establish a precise correlation between the na- ture of polymer packing, dynamics, energetics, and ion conduction for rational design of SPE-based fast ion conductors. In this regard, molecular dynamics (MD) simulations and enhanced sampling free energy methods play an important role in elucidating the atomistic details of ion transport and the critical ion-ion and ion-polymer interactions in SPEs. In the present thesis, we have employed molecular dynamics (MD) simulation, enhanced sampling methods (for example, the adaptive biasing force (ABF) method, well-tempered metadynam- ics (WTmetaD) simulation, and nudged elastic band (NEB) method) and normal mode analy- sis (NMA) to investigate the structure, dynamics and energetics of crystalline and amorphous phases of poly(ethylene oxide) (PEO) and PEO-based SPEs. Thermal phase behavior of crystalline poly(ethylene oxide) explored using MD simula- tions has shown the possibility of a premelting transition well below the equilibrium melting of the crystal. At temperatures just above the premelting transition temperature, molecules are able to rotate about their long axes, and diffuse along the chain-axis of the crystal. To under- stand the nature of coupling between polymer dynamics and ion transport in SPEs, all-atom molecular dynamics simulations of crystalline PEO3:NaI were carried out and polymer con- formational dynamics, energetics and migration pathways of ions were characterized . The results reveal that in crystalline PEO3:NaI both anions and cations follow helical pathways mirroring the helical symmetry of the polymer. The normal mode analysis (NMA) and the power spectral analysis of MD-derived velocity autocorrelation functions (VACF) have eluci- dated the important roles of backbone twisting of PEO helical chains about their long axes and softening of a few low-frequency collective modes in ion transport in SPEs. The calculated potentials of mean force for cations reveal the existence multiple isoenergetic coordination states separated by low energy barriers in the amorphous SPEs indicating that ion transport is facile and the mechanism of ion conduction is different in the amorphous SPEs than those in the crystalline SPEs.

Abstract

Indoor positioning is gaining momentum for its various applications. As we know that Global Positioning System (GPS) does not work well indoors, while todays more sensitive GPS chips can sometimes get a location x (via receiving signals from enough satellites to determine a location) inside a building. The re- sulting location is typically not accurate enough to be useful. The signals from the satellites are attenuated and scattered by roofs, walls and other objects. Besides, the error range of many GPS chips (tennis court) can be larger than the indoor space itself (small grocery store)! Some indoor positioning solutions work similar to GPS. Many companies tap into Wi-Fi signals that are all around us - including when we are indoors. With a good map of the locations of the access points, a Wi-Fi receiver like a cell phone can be located even indoors. Any application that would depend on indoor positioning may need an exact location. This work on indoor localization in 3D using spherical co-ordinates would have an edge to all the future needs. A combination of Pico, Femto, Wi-Fi, otherwise termed as hybrid localization techniques are used in conjunction with leveling and sectoring. Leveling and sectoring are discussed using base station and Wi-Fi access points and the received signal strength (RSS) nger prints are used to aid in precise localization. Indoor localization applied to physical analytics is also discussed. This thesis work also focuses in an improvement over our above discussed works in terms of achieving more accuracy and reduction of delay in the Wireless Sensor Networks (WSNs). This is achieved by using the Received Channel Power Indi- cator (RCPI) in contrast to RSS. We assume that RCPI shall be used by all chip vendor for all the Wi-Fi devices coming into the market due to its precise way of measuring the Received signal power. This work also focuses on Wireless Sensor Networks (WSN) with respect to the need for optimizing the parallel distributed computational architecture.It also discussed how it can be acheived using our proposed model. This gains impor- tance as identication of an event in WSNs should be done as fast as possible by minimizing the delay. Optimizing the grid based architecture for time complexity, transmission delay and fault tolerance in computing the fusion functions, our work also focuses on localizing an event in an outdoor WSN and respond to the event based on the need as soon as possible. Hence our overall work on 3D localization and wireless sensor networks helps us localize events in both indoor as well as outdoor with reduced time-complexity as well as delay parameters.

Abstract

Many of the real world networks can be represented as graphs. One of the most important problems related to the graphs is to find similar graphs. Due to a large number of properties each graph can possess, it is often difficult to find a similarity measure that captures all the properties of graphs. In this thesis, we discuss a notion of graph similarity based on the composition. The composition of a graph is the set of its important subgraphs and their frequency of occurrence in the original graph. Existing measures for graphs or trees do not capture the idea of the compositions. Our major contributions are directed towards extraction of compositional features of the graphs and trees. To find compositional features we need to find efficient algorithms to enumerate the frequencies of the subgraph templates in the graph. In this work, we present four contributions: (i) Grammars to recognize and enumerate subtree templates, (ii) idea of compositional similarity, (iii) Clique Conversion Coefficient, and (iv) an effective pre-processing step for listing Maximal Cliques. We designed grammars to enumerate the sub-tree templates in ordered trees. These grammars represent a tree using a string of length O(n), where n is the number of nodes in the tree. The frequencies of sub-tree templates are deduced using an algorithm. The results show that with good design of a grammar that can encode the structure of trees and a compatible algorithm assist in efficient enumeration of such compositional features. In this work, we introduce a measure for graphs, Clique Conversion Coefficient(CCC), which captures the clique forming tendency of nodes in a graph. CCC can be used either as a weighted average of a sequence of values or the sequence of values itself. We define the measure with three variants: global, local, and average. CCC is closely related to both Clustering Coefficient and Density of a graph as in they are all designed to find how well the nodes in a graph group together. But as per our experimental results, CCC, in some cases, provided additional information about a graph, which is the measure of the extent to which the nodes in the graph tend to form cliques. Also, we motivate the need for CCC by clustering some real world graphs with CCC as a feature in combination with other features. Our results show that graphs with similar clique forming tendencies are clustered together with the use of CCC as a feature, while without CCC this kind of grouping is not necessarily possible. This kind of Clustering would have many applications in the areas like Social Network Analysis, Protein-Protein Interaction Analysis, etc., where the existence of Cliques plays an important role. In this thesis, we also discussthe clustering of ego networks of large YOUTUBE network using the sequence of values in CCC as features. The quality of these results is verified by contrasting the frequent subgraphs in each cluster obtained. This experiment highlights the utility of CCC in clustering subgraphs of a large graph based on their clique forming tendencies. Also, we designed an algorithm to list all the maximal cliques. Our contribution in this algorithm is the pre-processing step, where we break the graph into biconnected components and prune the nodes having a lower degree and do these two steps iteratively in this order. This method experimentally showed to be very effective for breaking the workload of listing maximal cliques in many sparse graphs.

Abstract

In recent times, online advertising have become the prominent source of revenue for a major part of the Internet economy. Various modes of user interaction like - search engines, social networking, QA systems etc. has evolved forming different channel of advertising like Sponsored Search, Contextual Advertising, Micro-blog Targeting etc. The ad-publishers and the ad-networks need to be watchful about user’s interest when targeting them for their brand or product promotion through these channels. Exploiting user’s interest is of paramount importance while placing the advertisements, as it involves the higher probability of a click on the ad, which offers benefit to all the entities involved. Browsing content, a user is going through, is one of the indication of the things which interests user, which is used by the ad-networks for targeting. The ad relevant to the user’s interest increases the probability of an ad-click, which is beneficial for the entities involved. The field of On line Advertising which deals in placing ads by targeting the content is prominently known as ‘Content-targeted advertising’. The short-text of ads and unavailability of word-distributions on search engines/social-media builds on the vocabulary difference between the user and the publisher/advertiser. This vocabulary gap is one of the major problem while retrieving the relevant ads for the content being targeted. In this research work, our main focus was to bridge the ‘vocabulary-gap’ between the ad-text and browsing-content. Due to vocabulary mis-match we can not retrieve all the ads relevant to the content. In this thesis we have proposed different Semantic Solutions to solve the problem of vocabulary-mismatch between the texts. The two texts (ad and the content to be targeted) in their original forms do not share same vocabulary, so, we can consider them as two different syntactic-spaces. Measuring the relatedness between the two texts with different vocabularies is difficult and not-precise. The solutions proposed involve transforming these two texts to a common semantic space and then measure the similarity between them with higher precision than their actual representation. We proposed solutions for two categories of content-targeted advertising: • Micro-blog Targeting: This is about targeting ads relevant to micro-blogs in social media platforms. • Contextual Advertising: This is about retrieving relevant ads for the web page based on its content. Both categories come with their own challenges, micro-blogs are sparse in nature , involving slangs and inaccurate grammatical sentences with spelling mistakes. Retrieving ads for micro-blogging content is a hard problem. As the micro-blogging content is short and noisy and the ads are short too, there is a high amount of lexical mismatch between the micro-post and the ads. To bridge this lexical mismatch, we have proposed a ‘conceptual approach’ that transforms the content into a conceptual space that represents the latent concepts of the content. The conceptual distribution of the content have been used to measure the relatedness between the micro-blog and the ad. Web-page has a lot of text which needs to be targeted against the ad (very short text), we have proposed a solution which deals with the inherent latent topics of the text. The approach ‘topic models’ transforms the text into the distribution of predefined topics, and then we compare the topical distributions of the content and the ad-text to measure the similarity between them. To build the topic-model, we have used ODP (Open directory project) which has web-pages for numerous categories like, Finance, Automobile, Shopping etc. Our work on the microblog targeting is one of the initial work in the field. In this thesis, we have investigated some of the factors which are helpful while targeting microblogs. We have also compared our proposed approaches with various state-of-the-art techniques like vector-space model and language modeling (syntactic-match), using a taxonomy classification approach for semantic-ad matching, a machine learning approach etc. We empirically show that the proposed semantic models and the ensemble of this models with syntactic models have performed better than all the baselines and also have the substantial and significant improvement in the precision at all the precision levels over the baseline models.

Abstract

Visualization of geographical data is one of the important aspects of a geographical information system. Whilst 2D visualization techniques have been employed for decades, capturing dynamic phenomenon like floods over static urban areas within a space-time framework is gaining importance in GIS systems. This is because viewing geospatial data in higher (3 or 4) dimensions enables visualization of insightful information concerning events that may have been either limited or missing before. In certain phenomenon, the dynamics of it is better visualized and understood when the 3-dimensions of space and the time dimension (both forward and backward) can be employed to highlight its trajectory and object states over the region of interest. For instance, the phenomenon like ocean currents, atmospherics systems, airplane tracking, GPS tracks on terrain, etc. In the recent past, with the availability of three-dimensional geospatial data and the advancements in GPU processing power, various computer graphics applications have emerged including its adoption for Geospatial applications like virtual globes, city visualization, etc. While efforts at the visualization of space-time dependent phenomena like floods over natural surfaces have been attempted, but doing so in the presence of 3D non-natural objects and developing it from a GIS perspective is still a challenge. From a geospatial perspective, depicting a space-time process requires not only the time state information of the phenomenon but also its integration with the surface model. This throws up the challenge of capturing the phenomenon in the right geospatial context, i.e., the projection system. Other challenges include the ability to transform the data model to visualize the static or dynamic objects over the terrain and creating a computational framework that can integrate the process models with such geospatial visualization approaches. We make use of the publicly available 3D Berlin CityGML dataset for creating static urban models. As CityGML is an information model rather than visualization model, using them for rendering is non-trivial, along with their integration with virtual globes. We handle such issues by making use of 3DCityDB along with a tiling based approach which helps in rendering large CityGML datasets. Further, to make building models more realistic, we try to map the building textures with real world textures. We try to achieve this by automated draping of building textures from geo-tagged images which are captured by a cell phone camera with a built-in GPS. We use the properties of the images to tag them to the corresponding footprint by using the camera pose, and the position of the camera to automate the process. The challenge of integrating the dynamic phenomenon and the static urban model is handled by creating digital surface models of the region of interest. And using these surface models as the base for hydrological simulation. Some attempts have been made using methods of animation to depict the dynamic phenomenon like floods, snow avalanches, etc. While these approaches do provide a good visualization of the effect, they are based on simulated scenarios with an effort towards a smooth visual appearance of the depicted phenomenon. In this process, they overlook the locational interactions, which a near-real process simulation of the phenomenon capture. In this work, we present a 4D GIS system to visualize space-time dependent phenomena - simulated hydrological water flow model over an urban area. This work attempts to use the calculated water depth information to present a nearreal visual rendering of the same, with the emphasis on the visual interaction of the 3D objects (buildings) with such phenomenon captured in 4D (space and time). The developed system is built using the NASA’s WorldWind Globe and uses a depth filling algorithm as its input for time-step generated water depth maps, the dynamic layer. The urban scene is derived from a static CityGML LOD2 buildings layer overlaid on the digital elevation map. The dynamic flow visualization is enabled through an appropriate color mapping scheme so that the user can have a fair sense of water depth at various areas of the city over the time period. While visualization helps to understand the phenomenon and its progress, it is also important to provide an appropriate mechanism to derive or extract the relevant technical information from such a system. Towards this, in the developed system, analytical tools like querying for water depth at any given time, displaying of hydrographs showing the variation of height over time at a given location and a slider to control the time parameter of the system, have been incorporated. As the system uses 3DcityDB as the storage model, it is highly expendable for answering complex queries like ”which buildings of a specific area of the city will get flooded and when ?”. Such queries are n

Abstract

Computer vision solutions such as face detection and recognition, facial reenactment, facial expression analysis and gender detection have seen fruitful applications in various domains such as security, surveillance, social media and animation. Many of the above solutions have common pre-processing steps such as fiducial detection, appearance modeling, face structural modelings etc. These steps can be considered as fundamental problems to be solved in building any computer vision solutions concerning face images. In this thesis, we propose exemplar based approaches to solve two fundamental problems, such as face fiducial detection and face frontalization. Exemplar based approaches have been proved to work in various computer vision problems, such as object detection, image impainting, object removal, action recognition, gesture recognition. This approach directly utilizes the information residing in the examples to achieve a certain objective, instead of coming up with a model representing all the examples and has shown to be effective. Face fiducial detection involves detecting key points on the faces such as eye corner, nose tip, mouth tips etc. It is one of the main pre-processing step done for face recognition, facial animation, gender detection, gaze identification and expression recognition systems. Number of different approaches like active shape models, regression based methods, cascaded neural networks, tree based methods and exemplar based approaches have been proposed in the recent past. Many of these algorithms only address part of the problems in this area. We propose an exemplar based approach which takes advantage of the complimentarity of different approaches and obtain consistently superior performance over the state-of-the-art methods. We provide extensive experiments over three popular datasets. Face frontalization is the process of synthesizing frontal view of the face given a non-frontal view. Method proposed for frontalization can be used in intelligent photo editing tools and also aids in improving the accuracy of face recognition systems. Methods previously proposed involve estimating the 3D model or assuming a generic 3D model of the face. Estimating an accurate 3D model of the face is not a completely solved problem and assumption of generic 3D model of the face results in loss of crucial shape cues. We propose an exemplar based approach which does not require 3D model of the face. We show that our method is efficient and performs consistently better than other approaches.

Abstract

Natural Language Interface to Database (NLIDB) systems convert a Natural Language (NL) query into a Structured Query Language (SQL) and then use the SQL query to retrieve information from a database. The main advantage with this function of an NLIDB system is that it makes information retrieval much easier and more importantly, it also allows non-technical users to query a database. In this work, we present an effective usage of tokens in an NL query to address various problems in an NLIDB system. The conversion of an NL query to SQL query is framed as a token classification problem, using which we unveil a novel method of mapping an NL query to an SQL query. Our approach reasonably addresses domain dependency which is one of the major drawbacks of NLIDB systems. Concepts Identification is a major component of NLIDB systems (Gupta et al., 2012; Srirampur et al., 2014). We improve Concepts Identification (Srirampur et al., 2014) by making use of Stanford Parser Dependencies. Our approach is more robust than previously proposed methods. In addition, we also discuss how Concepts Identification can be applied to address Ellipsis in a dialogue process. In addition to providing results to a user, it is essential to provide a relevant and a compact set of results. We propose a new problem of generating a compact set of results to a user query. At a higher level, user-system interactions are modeled based on patterns frequently observed between a user’s current query and his previous queries, while interacting with a system. Using these models, we propose a novel method of system prompting to help a user obtain a smaller and a relevant set of results. In addition to providing a compact and a relevant set of results, it is imperative that answers of an NLIDB system are comprehensible even by the people who are less familiar with a common language like English. NLIDB systems use Natural Language Generation (NLG) modules to provide answers in the form of sentences. It is important to make sure that an answer generated by an NLG module is very simple to understand. This brings in the problem of text simplification, wherein, one of the most crucial and initial sub-problems is Complex Word Identification (CWI). We address the problem of CWI by distinguishing words as simple and complex. A plethora of classifiers were explored to identify the complex words. This information helps us in improving the simplification of an NLIDB system’s final output to a user. To summarize, in addition to addressing problems within an NLIDB system, this work touches postNLIDB problems like results processing. All the proposed issues are tackled using tokens in an NL query as the basic and a driving unit of force.

Abstract

Road extraction from very high (VHR) and high resolution (HR) satellite imagery is one of the important problems in the remote sensing area. Road network database is one of the essential features for various GIS applications like traffic management, transportation management and urban planning. Generally the road map is generated using the on-field survey techniques and GPS (Global Positioning System) based tracking methods. But recently the techniques which uses the remote sensing aerial and satellite imagery for road extraction are being developed. Since road region appear as linear segment in low resolution images, earlier research on road extraction focused on extracting road center-line from low resolution images. On the other hand, very high resolution satellite images provide an opportunity to extract entire road area along with road network. However, factors like variation in road surface characteristics and changing road geometry (widths and curvatures), occlusion due to trees building shadows and vehicles, the neighbouring non-road regions which become more apparent in very high resolution satellite images, make road extraction a challenging problem. Difference in the surface characteristics of the road in an image become too obvious in VHR images. Because of this complexity of the sensor and ground characteristics it makes difficult to have an automatic road technique which may extract the road area well in some scenarios but fails in most of the cases. In those cases semi automatic techniques where user provides some intial seeds which represents the road surface characteristics can be helpful in solving the issue. In this thesis a semi automatic road extraction algorithm based on adaptive spectral and texture matching (ASTM-R) with occlusion handling, which is a variant of region growing approach is presented. The algorithm developed in this thesis is robust to variations in radiometric resolution of input images, road surface characteristics and road geometry (widths and curvatures) and is able to reduce the false detection of neighbouring non-road regions. In addition to that, the proposed algorithm here can jump over the occlusions and can proceed with road tracking, resulting in using minimum number of user given seeds by being able to handle the occluded areas. The algorithm is tested on various satellite images, which comprises of PAN-sharpened QuickBird, IKONOS, Orbview3 and WorldView-2 images. Images are chosen to include road regions with varying width, curvatures, different ground characteristics. Experiments are conducted on images with disconnected road segments, road regions occluded with trees, vehicles. The measures used to evaluate the algorithm performance are road area completeness, correctness of road area and road network completeness. The algorithm is able to consistently extract 70% to 90% of the road area completeness and correctness. Reduction in the number of seeds is the another measure used in order to evaluate the occlusion handling performance of the algorithm. The algorithm is able to handle the occlusions and has considerably reduced manual intervention in road extraction process by minimizing 60-80% of the user seeds.