三维空间对象拓扑关系的研究

在数字地球、数字城市、地理信息系统等涉及地理数据等许多应用中,三维空间对象的拓扑关系的研究是一个十分重要的问题;弄清三维空间对象的拓扑关系,对于三维空间对象的操作以及操作的算法研究至关重要。由于三维空间对象的复杂性,它们之间拓扑关系的判定大多只是从简单的概念来进行判断,还没有从理论上全面地给定它的判定准则。该文试图在三维空间中,详细地研究空间对象之间拓扑关系成立的条件与结论,利用这些规则,可以全面地得到三维空间对象之间可能存在的所有拓扑关系。     

Mathematical framework for topological relationships between ribbons and regions

In a map, there are different relationships between spatial objects, such as topological, projective, distance, etc. Regarding topological relations, if the scale of the map is changed and if some spatial objects are generalized, not only the shapes of those objects will change (for instance, a small area becomes a point and then disappears as the scale diminishes), but also their topological relations can vary according to scale. In addition, a mathematical framework which models the variety of this category of relationships does not exist. In the first part of this paper, a new topological model is presented based on ribbons which are defined through a transformation of a longish rectangle; so, a narrow ribbon will mutate to a line and then will disappear. Suppose a road is running along a lake, at some scales, they both appear disjointed whereas at some smaller scales, they meet. So, the topological relations mutate according to scale. In this paper, the different components of this mathematical framework are discussed. For each situation, some assertions are defined which formulate the mutation of the topological relationships into other ones when downscaling.     

多重粗糙模糊集模型

为了充分揭示知识颗粒间的重叠性、对象的重要度差别及其多态性,基于多重集合,对Dubois粗糙模糊集意义下的粗糙模糊集模型的论域进行了扩展,提出了基于多重集的粗糙模糊集模型,给出了该模型的完整定义、相关定理和重要性质,其中包括多重粗糙模糊近似集、近似精度和可定义集的定义及其各种性质的证明、多重集意义下的粗糙模糊近似算子之间的关系及其与Dubois意义下的粗糙模糊近似算子之间的关系等。多重粗糙模糊集可用于从具有一对多依赖性关系的且具有模糊特性的数据中挖掘知识。     

A formal framework to represent spatial knowledge

Visual representations are an essential element in human–computer interaction and can be conceived as a collection of graphical objects arranged in a two-dimensional space. It is quite natural to model visual representations through the qualitative relationships holding between their objects, and therefore, qualitative spatial relations are a fundamental way of representing spatial knowledge. To this aim, in this paper we present a framework of qualitative spatial relations providing a general, domain-independent approach to specify visual representations.     

Approximate analysis of binary topological relations between geographic regions with indeterminate boundaries

 The development of formal models of spatial relations is a topic of great importance in spatial reasoning, geographic information systems (GIS) and computer vision, and has gained much attention from researchers across these research areas during the past two decades. In recent years significant achievements have been made on the development of models of spatial relations between spatial objects with precisely defined boundaries. However, these models cannot be directly applied to spatial objects with indeterminate boundaries which are found in many applications in geographic analysis and image understanding. This article develops a method for approximately analyzing binary topological relations between geographic regions with indeterminate boundaries based upon previous work on topological spatial relations and fuzzy sets. In addition, examples are given to demonstrate the method and related concepts. It is shown that the eight binary topological relations between regions in a two-dimensional space can be easily determined by the method.     

On the ternary spatial relation "between".

The spatial relation "between" is a notion which is intrinsically both fuzzy and contextual, and depends, in particular, on the shape of the objects. The literature is quite poor on this and the few existing definitions do not take into account these aspects. In particular, an object B that is in a concavity of an object A1 not visible from an object A2 is considered between A1 and A2 for most definitions, which is counter intuitive. Also, none of the definitions deal with cases where one object is much more elongated than the other. Here, we propose definitions which are based on convexity, morphological operators, and separation tools, and a fuzzy notion of visibility. They correspond to the main intuitive exceptions of the relation. We distinguish between cases where objects have similar spatial extensions and cases where one object is much more extended than the other. Extensions to cases where objects, themselves, are fuzzy and to three-dimensional space are proposed as well. The original work proposed in this paper covers the main classes of situations and overcomes the limits of existing approaches, particularly concerning nonvisible concavities and extended objects. Moreover, the definitions capture the intrinsic imprecision attached to this relation. The main proposed definitions are illustrated on real data from medical images.     

不确定性空间关系

空间关系在空间查询语言、基于内容的数据检索及空间分析中有重要作用。不确定性是空间关系的固有特性，但至今没有受到研究人员的足够重视。为了使人们对该理论有个概略了解，首先给出了空间关系不确定性的定义、内涵及其对空间关系应用的影响；然后从数据的不确定性、认知的不确定性以及空间关系分析处理的不确定性等3个方面详细地分析了空间关系不确定性的来源，同时提出了空间关系不确定性的处理方式，并以空间关系不确定性的3个来源为标准，评价并指出了定性空间关系表达方法的不足之处；最后，给出了用模糊集方法研究模糊空间关系的框架和主要内容，以便为不确定性空间关系的研究奠定基础。     

3D C-string: a new spatio-temporal knowledge representation for video database systems

In video database systems, one of the most important methods for discriminating the videos is by using the objects and the perception of spatial and temporal relations that exist between objects in the desired videos. In this paper, we propose a new spatio-temporal knowledge representation called 3D C-string. The knowledge structure of 3D C-string, extended from the 2D C⁺-string, uses the projections of objects to represent spatial and temporal relations between the objects in a video. Moreover, it can keep track of the motions and size changes of the objects in a video. The string generation and video reconstruction algorithms for the 3D C-string representation of video objects are also developed. By introducing the concept of the template objects and nearest former objects, the string generated by the string generation algorithm is unique for a given video and the video reconstructed from a given 3D C-string is unique too. This approach can provide us an easy and efficient way to retrieve, visualize and manipulate video objects in video database systems. Finally, some experiments are performed to show the performance of the proposed algorithms.     

A model of fuzzy spatio-temporal knowledge representation and reasoning based on high-level Petri nets

In many application areas there is a need to represent human-like knowledge related to spatio-temporal relations among multiple moving objects. This type of knowledge is usually imprecise, vague and fuzzy, while the reasoning about spatio-temporal relations is intuitive. In this paper we present a model of fuzzy spatio-temporal knowledge representation and reasoning based on high-level Petri nets. The model should be suitable for the design of a knowledge base for real-time, multi-agent-based intelligent systems that include expert or user human-like knowledge. The central part of the model is the knowledge representation scheme called FuSpaT, which supports the representation and reasoning for domains that include imprecise and fuzzy spatial, temporal and spatio-temporal relationships. The scheme is based on the high-level Petri nets called Petri nets with fuzzy spatio-temporal tokens (PeNeFuST). The FuSpaT scheme integrates the theory of the PeNeFuST and 117 spatio-temporal relations.The reasoning in the proposed model is a spatio-temporal data-driven process based on the dynamical properties of the scheme, i.e., the execution of the Petri nets with fuzzy spatio-temporal tokens. An illustrative example of the spatio-temporal reasoning for two agents in a simplified robot-soccer scene is given.     

Quantitative analysis of properties and spatial relations of fuzzyimage regions

Properties of objects and spatial relations between objects play an important role in rule-based approaches for high-level vision. The partial presence or absence of such properties and relationships can supply both positive and negative evidence for region labeling hypotheses. Similarly, fuzzy labeling of a region can generate new hypotheses pertaining to the properties of the region, its relation to the neighboring regions, and, finally, hypotheses pertaining to the labels of the neighboring regions. A unified methodology that can be used to characterize both properties and spatial relationships of object regions in a digital image is presented. The methods proposed for computing the properties and relations of image regions can be used to arrive at more meaningful decisions about the contents of the scene     

Put: language-based interactive manipulation of objects

Our approach to scene generation capitalizes the expressive power of natural language by separating its aptness in specifying spatial relations from the difficulties of understanding text. We are implementing an object-placement system called Put that uses a combination of linguistic commands and direct manipulation. The system is language-based, meaning that its design and structure are guided by natural language. Our approach (inspired by research in cognitive linguistics) is to analyze the natural use of spatial relations, define a well-understood class of fundamental relationships, and gradually build a coherent and natural spatial-manipulation system. Just a few simple spatial relationships, such as in, on, and at, parameterized by a limited number of environmental variables can provide comfortable object manipulation. These natural commands can be used to quickly prototype a complex scene and constrain object placement. We believe that we have an extensible, predictable, and computationally feasible environment for object manipulation. We have focused first on spatial relationships because they are fundamental to many conceptual domains beyond object placement, including motion and time. These particular domains are very important to areas of computer graphics such as animation. Uses of spatial relationships in these areas can be quite complex. We briefly introduce the complexities of understanding spatial relations and summarize related work. Then we describe the core of the Put placement system, followed by its linguistic, procedural, and interactive interfaces. We conclude by discussing future enhancements to the system     

Content-based Access in Image Database by Quantitative Relationships

In this paper, we describe a novel technique to perform content-based access in image databases using quantitative spatial relationships. Usually, spatial relation-based indexing methods fail if the metric spatial information contained in the images must be preserved. In order to provide a more robust approach to directional relations indexing with respect to metric differences in images, this paper introduces an improvement of the virtual image index, namely quantitative virtual image, using a quantitative methodology. A scalar quantitative measure is associated with each spatial relation, in order to discriminate among images of the image database having the same objects and spatial relationships, but different degree of similarity if we also consider distance relationships. The measure we introduce does not correspond to any significant increase of complexity with respect to the standard virtual image providing a more precise answer set.     

模糊栅格区域的层次拓扑关系模型

空间区域拓扑关系建模是空间推理和地理信息系统(GIS)等领域的一个主要研究内容,近年来模糊空间区域建模及其拓扑关系分析显现出越来越重要的作用．根据栅格数据模型下模糊区域的特征和实际应用领域中拓扑关系分析的特点,提出了一种模糊栅格区域的层次拓扑关系模型,该模型利用3个谓词的真值来分析栅格区域间的拓扑关系,将分明栅格区域作为特例统一处理,能够根据谓词的多种真值实现模糊栅格区域在多个层次上的拓扑关系分析．该模型表达能力强、易于实现,并且在实际应用中得到了令人满意的结果．     

Modeling and querying fuzzy spatiotemporal databases

Modeling spatiotemporal data, in particular fuzzy and complex spatial objects representing geographic entities and relations, is a topic of great importance in geographic information systems, computer vision, environmental data management systems, etc. Because of complex requirements, it is challenging to represent spatiotemporal data and its features in databases and to effectively query them. This article presents a new approach to model and query the spatiotemporal data of fuzzy spatial and complex objects and/or spatial relations. In our case study, we use a meteorological database application in an intelligent database architecture, which combines an object-oriented database with a knowledgebase for modeling and querying spatiotemporal objects.     

Spatial relations between 3D objects: The association between natural language,topology, and metrics

With the proliferation of 3D image data comes the need for advances in automated spatial reasoning. One specific challenge is the need for a practical mapping between spatial reasoning and human cognition, where human cognition is expressed through natural-language terminology. With respect to human understanding, researchers have found that errors about spatial relations typically tend to be metric rather than topological; that is, errors tend to be made with respect to quantitative differences in spatial features. However, topology alone has been found to be insufficient for conveying spatial knowledge in natural-language communication. Based on previous work that has been done to define metrics for two lines and a line and a 2D region in order to facilitate a mapping to natural-language terminology, herein we define metrics appropriate for 3D regions. These metrics extend the notions of previously defined terms such as splitting, closeness, and approximate alongness. The association between this collection of metrics, 3D connectivity relations, and several English-language spatial terms was tested in a human subject study. As spatial queries tend to be in natural language, this study provides preliminary insight into how 3D topological relations and metrics correlate in distinguishing natural-language terms.     

多重概率粗糙集模型

基于多重集合,对Z.Pawlak粗集意义下的概率粗糙集模型的论域进行了扩展,提出了基于多重集的概率粗糙集模型,即多重概率粗糙集模型,给出了该模型的完整定义、相关定理和重要性质,其中包括多重论域定义、多重概率粗糙近似集的定义及其各种性质的证明、多重概率粗糙集的近似精度定义、可定义集与属性约简的定义、多重集意义下的粗糙近似算子之间的关系及其与Z.Pawlak意义下的粗糙近似算子之间的关系等。多重概率粗糙集可充分反映知识颗粒间的重叠性,对象的重要度差别及其多态性,这样有利于用粗糙集理论从保存在关系数据库中的具有一对多、多对多依赖性的且具有不完全性或存在统计性的数据中挖掘知识。     

Image database design based on 9D-SPA representation for spatial relations

Spatial relationships between objects are important features for designing a content-based image retrieval system. We propose a new scheme, called 9D-SPA representation, for encoding the spatial relations in an image. With this representation, important functions of intelligent image database systems such as visualization, browsing, spatial reasoning, iconic indexing, and similarity retrieval can be easily achieved. The capability of discriminating images based on 9D-SPA representation is much more powerful than any spatial representation method based on minimum bounding rectangles or centroids of objects. The similarity measures using 9D-SPA representation provide a wide range of fuzzy matching capability in similarity retrieval to meet different user's requirements. Experimental results showed that our system is very effective in terms of recall and precision. In addition, the 9D-SPA representation can be incorporated into a two-level index structure to help reduce the search space of each query processing. The experimental results also demonstrated that, on average, only 0.1254 percent /spl sim/ 1.6829 percent of symbolic pictures (depending on various degrees of similarity) were accessed per query in an image database containing 50,000 symbolic pictures.     

地理信息系统中空间对象间拓扑关系的推理

首先讨论了地理信息系统中空间对象的空间数据模型,然后定性地分析了空间对象点与点、点与线和点与区域之间的拓扑关系,并给出了空间对象拓扑关系的推理算法.最后,将模糊技术与空间对象之间的拓扑关系的推理算法结合起来,使其可以方便地处理地理信息系统中的模糊性和不确定性.     

模糊熵、距离测度和相似性测度之间的关系

模糊熵、距离测度和相似性测度是模糊集合的三种重要度量,许多学者对三者之间的关系进行了研究。采用更为严格的定义,通过定义模糊集合之间新的运算研究了三者之间的关系,给出了三者之间的相互诱导公式。对部分公式进行了举例说明。