Research On The Techniques Of Qualitative Spatial Reasoning And Application

Various kinds of geospatial information technologies that have recently come to lifeextend the public's ability to quickly and easily access geo-referenced informationbeyond the confines of desktop GIS (Geographic Information System). The World WideWeb, wireless communication and information technologies, and telematicstechnologies represent the new face of geospatial applications. Through space-awaredevices, location-based services promise to offer users a profusion of information ontheir local environment in the field or on the street, which in turn enables them to answerall sorts of space-related questions in their daily life.To keep pace with these new application demands, we must research new spatialinformation processing techniques. For example, the old paradigms of relevance todesktop GISs have to be retooled. A particular challenge for the design of spatialinformation systems of the next generation is to equip GISs to handle common-sensegeographic queries made by users without specific training in spatial technologies.Because the view of the geographic world held by the general public is in the form ofmental images or narrative descriptions, rather than in a digital form as stored incomputer databases, people often perceive spatial relations through qualitativedescriptions instead of metric measurements. Therefore, it is much more practical forthem to formulate spatial queries using qualitative terms in order to interact with spatialdatabases. This intuitive interaction entails providing facilities for the representation ofqualitative spatial information and making inferences, i.e. Qualitative Spatial Reasoning(QSR).Although many research achievements have been obtained in QSR, some problemshave not been solved yet. The researches on QSR integrating multi-aspect spatialinformation are being paid more and more attention by scholars, because it is very rareto deal with only one aspect of spatial information in practice. Some researcher has everstudied on the QSR integrating topology and direction information based on intervalcalculus. The cardinal direction model proposed by Goyal and Egenhofer considers thereal shape of the primary spatial object, which leads to strong expressivity and favorableproperties of computing and reasoning. But the techniques of QSR combining Goyal andEgenhofer's cardinal direction model and topological model have not been given enoughstudies. In the QSR research field, the research on direction relations between fuzzyregions is much less compared to topological relation between fuzzy regions, while thefuzziness in real world is pervasive. Spatio-temporal reasoning research relatedintimately to QSR is becoming a hot topic, which has triggered many problems aboutrepresentation and reasoning. This thesis focuses on a particular problem inspatio-temporal reasoning. The theoretical and practical researches on QSR are equallyimportant. This thesis carries out research on the algorithms in two typical applications,i.e. spatial configuration information retrieval and spatial data mining, which arepotential applications in GIS and other spatial information systems.The goals of this thesis are to develop QSR algorithms and investigate thecomputational properties combining the spatial topological calculus RCC8 and cardinaldirection calculus, to analyze the deficiency of Goyal and Egenhofer's cardinal directionmodel and provide a quantitative computational model handling cardinal directionsbetween both crisp and fuzzy regions, to investigate the conceptual neighborhoodproblem related to motion continuity in spatio-temporal reasoning and introduce thegeneralized conceptual neighborhood graph and the algorithm, to investigate the spatialconfiguration retrieval methods, to develop the scheme of retrieval considering thetopological and cardinal direction relations and the efficient retrieval algorithmsevaluated by some experiments, to investigate the spatial data mining techniques andprovide a new method.The major contributions, ideas and research results included in the thesis are asfollows:Firstly, Research on QSR techniques combining RCC8 and cardinal directioncalculus based on region.To combine the two calculi, we must consider the interaction between them.Because the number of cardinal direction relations based on region is 512, it's notrealistic to investigate the composition tables of the two calculi and the interaction rulesshould be considered which can be used by a computer program to generate compositiontables. Based on the semantics of RCC8 and cardinal direction calculus based on region,the interaction rules are derived. This thesis regard QSR as a special form of ConstraintSatisfaction Problems (CSPs): Qualitative Spatial Constraint Satisfaction Problems(QS-CSPs), whose domains are infinite. So the methods handling CSPs with infinitedomains can be applied. We define the consistency deciding problem and consistentscenarios problems, which are critical in QS-CSPs. We introduce the path consistencyconcept and the path consistency algorithm related to consistency deciding. Therelationship between path consistency and global consistency is also given. The solvingmethods of CSPs with infinite domains are described and the research results oncomputational properties achieved in RCC8 and cardinal direction calculus based onregion are outlined. In RCC8, three maximal tractable subsets whose consistencydeciding problem can be determined by path consistency algorithm are identified;In thecardinal direction calculus based on region, the algorithm solving the consistencydeciding problem based on constraint set consisting of basic cardinal direction relationsis worked out.This thesis designs a path consistency algorithm handling the CSPs combiningRCC8 and cardinal direction relations. Generally, path consistency algorithm operateswithin a CSP, but it should be extended to communicate interactions between RCC8component and cardinal direction component. To ensure the respective path consistencyof RCC8 component and cardinal direction component in a CSP that includes RCC8relations and cardinal direction relations and implement the interactions between them,our new algorithm uses two queues, which maintain two kinds of constraint relationsrespectively. Our algorithm pick out a constraint relation from one of the two queues inturn and this constraint relation affect not only the constraint relations within its queue,but also the constraint relations in the other queue according to the interaction rules. Thealgorithm doesn't terminate until the two queues are all empty or the empty constraintrelation is derived. The computational complexity of our algorithm does not improvemuch compared to traditional path consistency algorithm. A simple exampledemonstrates that the idea of combining RCC8 and cardinal direction calculus and theproposed new algorithm are very useful.Based on the achievements on the computational properties of RCC8 and cardinaldirection calculus based on region, this thesis analyzes the computational complexity ofthe CSPs combining RCC8 and cardinal directional relations based on differentconstraint subsets and concludes that the computational complexity of the consistencydeciding problem of the CSPs based on the constraint set composed of any maximaltractable subset in RCC8 and basic cardinal directional relations is still polynomialthough a little higher. The analysis on the computational complexity is very importantbecause the analysis results can guide us to design correct and efficient consistencydeciding algorithms. For CSPs whose constraint relations are not based on the tractableconstraint subsets, path consistency algorithm cannot decide its consistency problem,because path consistency is necessary but not enough condition for global consistency ofa CSP. So we must have a comprehensive algorithm deciding the consistency problemof CSPs based on any constraint set. The thesis designs a comprehensive consistencydeciding algorithm for CSPs combining RCC8 and cardinal direction relations. Thealgorithm uses aforementioned path consistency algorithm for pruning, and if the pathconsistency algorithm is run using tractable subsets, the efficiency of the comprehensivealgorithm can be improved.The research ideas and approaches used for combining RCC8 and cardinal directioncalculus can be generalized to the QSR combining other spatial aspects. The research onthe QSR techniques is very meaningful to GIS, computer vision and robot navigation,etc.Secondly, Modeling cardinal directions between fuzzy regions based onfuzzy-morphology.Traditional cardinal direction model based on region approximate reference regionusing Minimum Bounding Rectangle (MBR), which leads that the model cannot identifythe correct cardinal directions in some cases. For example, a region A does not overlapwith another region B, but located in the convex hull of region B. The dilation operationin mathematics morphology can handle these cases naturally. This thesis defines acomputational model using the dilation operation in mathematics morphology andappropriate structure element, and illustrates that this new model can complement thedeficiency in current model through some examples. Our work does not discard thecurrent model, but a refinement of it, because the current cardinal direction model basedon region has a favorable property of qualitative reasoning.Traditionally, most of the spatial data models assume that the extent of the spatialobject, i.e. the boundary of it, is exactly defined and extensively acknowledged. Thiskind of model is crisp spatial model. Researchers are realizing that many spatial objectshave not crisp boundaries, or the boundaries cannot be exactly identified in the realworld. This thesis combines fuzzy set theory and mathematics morphology theory tomodel the cardinal direction relations between fuzzy regions. A fuzzy region is regardedas a set composed of a finite (or infinite) number of crisp regions, and each crisp regionis assigned a probability value that it is the "true" representative of the whole fuzzyregion. For any two fuzzy regions, each pair of crisp regions in the sets can be workedout the cardinal direction relation using the aforementioned computational model basedon mathematics morphology and all the resulting cardinal direction relations areaggregated using a special schema. After comparing the two models, i.e. the modelhandling the crsp regions and the model handling the fuzzy regions, we conclude that thefuzzy model can be reduced to the crisp model when handling crisp regions, i.e. weprovide a uniform computational model handling cardinal direction relations betweenregions quantitatively.The computational model of this thesis can deal with both the continuous anddiscrete space, and the approaches handling cardinal direction relations between fuzzyregions can be applied to other spatial models. The experiment results confirm thecognitive plausibility of our computational models.Thirdly, Research on generalized conceptual neighborhood graph inspatio-temporal reasoning.The simple integration of space and time is not enough in spatio-temporal datamanagement. This thesis introduces a spatio-temporal model taking space-time historiesof objects as primitive entities, the topology of space-time, temporal order, and spacerelations. The concepts of time slice and spatio-temporal continuity are presented. Basedon spatio-temporal continuity and time slice, spatial conceptual neighborhood isredefined. When we want to judge whether a spatio-temporal scenario can betransformed to another spatio-temporal scenario under the condition of spatio-temporalcontinuity, the traditional spatial conceptual neighborhood graph is not applicable. Sothis thesis presents the concept of generalized conceptual neighborhood graph, andproposes the computational method. The algorithm is computationally expensive. Thegeneralized conceptual neighborhood graph can be applied to spatio-temporal reasoning,especially consistency checking.Fourthly, Research on spatial configuration information retrieval algorithms.Spatial configuration information retrieval has potential applications in many fields,such as GIS, Multimedia database, Computer vision and VLSI (Very Large ScaleIntegration), etc. This thesis regards the spatial configuration retrieval problems as CSPswith finite domains, which are different from the aforementioned QS-CSPs based oninfinite domains. So the traditional algorithms for CSPs can be applied. This thesidefines the formulas computing the inconsistency degree and similarity degree, whichare used by the retrieval algorithms.In real applications, spatial regions often have complex geometric shapes. If wecompute the spatial relations between them directly, the expense will be very large andsometimes expensive computations will result in nothing. If we use MBR toapproximate the real shapes of the regions, the computational expense will be greatlyreduced because only the spatial relations between rectangles are calculated. Theretrieval of spatial configurations can be divided into two steps: first, the combinationsof rectangles which are not possible to satisfy the query conditions are eliminated;second, the combinations of real spatial objects corresponding to the remainingcombinations of rectangles are calculated using computational geometry techniques tocheck if they satisfy the query conditions. The thesis presents the method for computingthe inconsistency degree between two spatial relations through encoding spatial relationsbetween two rectangles as two binary strings along the horizontal and vertical axes. Thesimilarity degree is calculated according to the conceptual neighborhood graph ofinterval calculus.The thesis outlines search algorithms which can solve spatial configurationinformation retrieval problems, and designs four systematic search algorithms, i.e.SFC-DVOSolver which combines forward checking and dynamic variable ordering usedto solve traditional CSPs, RSFC-DVOSolver which is based on SFC-DVOSolver butemploys R-tree to accelerate pruning in forward checking, HRSFC-DVOSolver which isbased on RSFC-DVOSolver and uses hash index technique to accelerate rectanglematching process, RMLSFC-DVOSolver which combines R-tree and SFC-DVOSolverto realize constraint solving level by level. To implement the algorithms using R-tree,this thesis investigates the mapping relationship between spatial relations (includingtopological and cardinal direction relations) of spatial objects and spatial relations oftheir MBRs, and the mapping relationship between spatial relations (includingtopological and cardinal direction relations) of intermediate nodes in R-tree and spatialrelations of the MBRs.Through experiments, this thesis concludes that algorithms SFC-DVOSolver andHRSFC-DVOSolver are the feasible ones for solving spatial configuration retrievalproblems, and fixes on the parameters of the two algorithms and the conditions underwhich the two algorithms can be applicable. If the constraint power of the querycondition is weak, the algorithm SFC-DVOSolver should be used;if the constraintpower is normal or strong, the algorithm HRSFC-DVOSolver is better. The judgment ofthe constraint power of the query condition should be based on the knowledge base, andthen we can decide to use SFC-DVOSolver or HRSFC-DVOSolver.When the number of query variable is large (usually larger than 20) or the spatialdata volume is very large (usually larger than one hundred and thousand), the systematicalgorithms will not be applicable and the local search algorithms or other optimizationalgorithms. The research on spatial configuration retrieval algorithms is valuable to theapplication systems related to spatial data.Fifthly, Research on spatial data mining techniques.Spatial Data Mining (SDM) is to abstract the implicit knowledge, spatial relationsor other meaningful patterns in spatial databases. The main difference SDM has from thetraditional data mining is that SDM considers not only the non-spatial attributes, but alsothe spatial attributes. For the problem of multi-layer (or multi-thematic) spatial datamining, we propose a multi-relational aggregation operator and an algorithm frame forspatial data mining based on this operator. The algorithm derives a relation table fromthe spatial data information (including spatial and non-spatial information) related toseveral layers. Then the traditional data mining techniques based on relational databasecan be directly applied. The algorithm can define spatial predicates according to actualneeds. We apply this frame to a real spatial data classification problem, which runsefficiently and achieves good classification results.To sum up, the study results of this thesis are of both theoretical and practicalbenefit to further researches in qualitative spatial reasoning, fuzzy spatial reasoning,spatio-temporal reasoning, spatial information retrieval, spatial data mining andgeographic information system.