The Experts below are selected from a list of 834 Experts worldwide ranked by ideXlab platform

Jennifer L Leopold - One of the best experts on this subject based on the ideXlab platform.

  • A More Efficient Representation of Obscuration for VRCC-3D+ Relations
    2016
    Co-Authors: Nathan Eloe, Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    Abstract—VRCC-3D+ is an implementation of a region connection calculus that qualitatively determines the spatial relation between two 3D objects in terms of connectivity and obscuration. The eight connectivity relations are conceptually the same as RCC8, but calculated in 3D rather than 2D. The fifteen obscuration relations are calculated using the projection of the 3D objects on a particular 2D plane and the distance of the objects from the viewpoint. Herein we present a smaller, more precise set of VRCC-3D+ obscuration relations that retains the qualities of being jointly exhaustive and pairwise disjoint. However, this new set of relations overcomes two problems that existed in the previous set of fifteen relations: (1) lack of a precise mathematical definition for a key predicate, InFront, and (2) lack of an intuitive mapping of converse relations. Index Terms—Computer vision, qualitative spacial reasoning, VRCC-3D, region connection calculus, spatial relations. I

  • Evolution of region connection calculus to VRCC-3D+
    New Mathematics and Natural Computation, 2014
    Co-Authors: Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    Qualitative spatial reasoning (QSR) is useful for deriving logical inferences when quantitative spatial information is not available. QSR theories have applications in areas such as geographic information systems, spatial databases, robotics, and cognitive sciences. The existing QSR theories have been applied primarily to 2D. The ability to perform QSR over a collection of 3D objects is desirable in many problem domains. Here we present the evolution (VRCC-3D+) of RCC-based QSR from 2D to both 3D (including occlusion support) and 4D (a temporal component). It is time consuming to construct large composition tables manually. We give a divide-and-conquer algorithm to construct a comprehensive composition table from smaller constituent tables (which can be easily handcrafted). In addition to the logical consistency entailment checking that is required for such a system, clearly there is a need for a spatio-temporal component to account for spatial movements and path consistency (i.e. to consider only smooth transitions in spatial movements over time). Visually, these smooth movement phenomena are represented as a conceptual neighborhood graph. We believe that the methods presented herein to detect consistency, refine uncertainty, and enhance reasoning about 3D objects will provide useful guidelines for other studies in automated spatial reasoning.

  • evolution of region connection calculus to vrcc 3d
    New Mathematics and Natural Computation, 2014
    Co-Authors: Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    Qualitative spatial reasoning (QSR) is useful for deriving logical inferences when quantitative spatial information is not available. QSR theories have applications in areas such as geographic information systems, spatial databases, robotics, and cognitive sciences. The existing QSR theories have been applied primarily to 2D. The ability to perform QSR over a collection of 3D objects is desirable in many problem domains. Here we present the evolution (VRCC-3D+) of RCC-based QSR from 2D to both 3D (including occlusion support) and 4D (a temporal component). It is time consuming to construct large composition tables manually. We give a divide-and-conquer algorithm to construct a comprehensive composition table from smaller constituent tables (which can be easily handcrafted). In addition to the logical consistency entailment checking that is required for such a system, clearly there is a need for a spatio-temporal component to account for spatial movements and path consistency (i.e. to consider only smooth transitions in spatial movements over time). Visually, these smooth movement phenomena are represented as a conceptual neighborhood graph. We believe that the methods presented herein to detect consistency, refine uncertainty, and enhance reasoning about 3D objects will provide useful guidelines for other studies in automated spatial reasoning.

  • qualitative spatial reasoning in 3d spatial metrics for topological connectivity in a region connection calculus
    MIKE, 2014
    Co-Authors: Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    In qualitative spatial reasoning, there are three distinct properties for reasoning about spatial objects: connectivity, size, and direction. Reasoning over combinations of these properties can provide additional useful knowledge. To facilitate end-user spatial querying, it also is important to associate natural language with these relations. Some work has been done in this regard for line-region and region-region topological relations in 2D, and very recent work has initiated the association between natural language, topology, and metrics for 3D objects. However, prior efforts have lacked rigorous analysis, expressive power, and completeness of the associated metrics. Herein we present new metrics to bridge the gap required for integration between topological connectivity and size information for spatial reasoning. The new set of metrics that we present should be useful for a variety of applications dealing with 3D objects.

  • MIKE - Qualitative Spatial Reasoning in 3D: Spatial Metrics for Topological Connectivity in a region connection calculus
    Mining Intelligence and Knowledge Exploration, 2014
    Co-Authors: Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    In qualitative spatial reasoning, there are three distinct properties for reasoning about spatial objects: connectivity, size, and direction. Reasoning over combinations of these properties can provide additional useful knowledge. To facilitate end-user spatial querying, it also is important to associate natural language with these relations. Some work has been done in this regard for line-region and region-region topological relations in 2D, and very recent work has initiated the association between natural language, topology, and metrics for 3D objects. However, prior efforts have lacked rigorous analysis, expressive power, and completeness of the associated metrics. Herein we present new metrics to bridge the gap required for integration between topological connectivity and size information for spatial reasoning. The new set of metrics that we present should be useful for a variety of applications dealing with 3D objects.

Chaman L Sabharwal - One of the best experts on this subject based on the ideXlab platform.

  • A More Efficient Representation of Obscuration for VRCC-3D+ Relations
    2016
    Co-Authors: Nathan Eloe, Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    Abstract—VRCC-3D+ is an implementation of a region connection calculus that qualitatively determines the spatial relation between two 3D objects in terms of connectivity and obscuration. The eight connectivity relations are conceptually the same as RCC8, but calculated in 3D rather than 2D. The fifteen obscuration relations are calculated using the projection of the 3D objects on a particular 2D plane and the distance of the objects from the viewpoint. Herein we present a smaller, more precise set of VRCC-3D+ obscuration relations that retains the qualities of being jointly exhaustive and pairwise disjoint. However, this new set of relations overcomes two problems that existed in the previous set of fifteen relations: (1) lack of a precise mathematical definition for a key predicate, InFront, and (2) lack of an intuitive mapping of converse relations. Index Terms—Computer vision, qualitative spacial reasoning, VRCC-3D, region connection calculus, spatial relations. I

  • Evolution of region connection calculus to VRCC-3D+
    New Mathematics and Natural Computation, 2014
    Co-Authors: Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    Qualitative spatial reasoning (QSR) is useful for deriving logical inferences when quantitative spatial information is not available. QSR theories have applications in areas such as geographic information systems, spatial databases, robotics, and cognitive sciences. The existing QSR theories have been applied primarily to 2D. The ability to perform QSR over a collection of 3D objects is desirable in many problem domains. Here we present the evolution (VRCC-3D+) of RCC-based QSR from 2D to both 3D (including occlusion support) and 4D (a temporal component). It is time consuming to construct large composition tables manually. We give a divide-and-conquer algorithm to construct a comprehensive composition table from smaller constituent tables (which can be easily handcrafted). In addition to the logical consistency entailment checking that is required for such a system, clearly there is a need for a spatio-temporal component to account for spatial movements and path consistency (i.e. to consider only smooth transitions in spatial movements over time). Visually, these smooth movement phenomena are represented as a conceptual neighborhood graph. We believe that the methods presented herein to detect consistency, refine uncertainty, and enhance reasoning about 3D objects will provide useful guidelines for other studies in automated spatial reasoning.

  • evolution of region connection calculus to vrcc 3d
    New Mathematics and Natural Computation, 2014
    Co-Authors: Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    Qualitative spatial reasoning (QSR) is useful for deriving logical inferences when quantitative spatial information is not available. QSR theories have applications in areas such as geographic information systems, spatial databases, robotics, and cognitive sciences. The existing QSR theories have been applied primarily to 2D. The ability to perform QSR over a collection of 3D objects is desirable in many problem domains. Here we present the evolution (VRCC-3D+) of RCC-based QSR from 2D to both 3D (including occlusion support) and 4D (a temporal component). It is time consuming to construct large composition tables manually. We give a divide-and-conquer algorithm to construct a comprehensive composition table from smaller constituent tables (which can be easily handcrafted). In addition to the logical consistency entailment checking that is required for such a system, clearly there is a need for a spatio-temporal component to account for spatial movements and path consistency (i.e. to consider only smooth transitions in spatial movements over time). Visually, these smooth movement phenomena are represented as a conceptual neighborhood graph. We believe that the methods presented herein to detect consistency, refine uncertainty, and enhance reasoning about 3D objects will provide useful guidelines for other studies in automated spatial reasoning.

  • qualitative spatial reasoning in 3d spatial metrics for topological connectivity in a region connection calculus
    MIKE, 2014
    Co-Authors: Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    In qualitative spatial reasoning, there are three distinct properties for reasoning about spatial objects: connectivity, size, and direction. Reasoning over combinations of these properties can provide additional useful knowledge. To facilitate end-user spatial querying, it also is important to associate natural language with these relations. Some work has been done in this regard for line-region and region-region topological relations in 2D, and very recent work has initiated the association between natural language, topology, and metrics for 3D objects. However, prior efforts have lacked rigorous analysis, expressive power, and completeness of the associated metrics. Herein we present new metrics to bridge the gap required for integration between topological connectivity and size information for spatial reasoning. The new set of metrics that we present should be useful for a variety of applications dealing with 3D objects.

  • MIKE - Qualitative Spatial Reasoning in 3D: Spatial Metrics for Topological Connectivity in a region connection calculus
    Mining Intelligence and Knowledge Exploration, 2014
    Co-Authors: Chaman L Sabharwal, Jennifer L Leopold
    Abstract:

    In qualitative spatial reasoning, there are three distinct properties for reasoning about spatial objects: connectivity, size, and direction. Reasoning over combinations of these properties can provide additional useful knowledge. To facilitate end-user spatial querying, it also is important to associate natural language with these relations. Some work has been done in this regard for line-region and region-region topological relations in 2D, and very recent work has initiated the association between natural language, topology, and metrics for 3D objects. However, prior efforts have lacked rigorous analysis, expressive power, and completeness of the associated metrics. Herein we present new metrics to bridge the gap required for integration between topological connectivity and size information for spatial reasoning. The new set of metrics that we present should be useful for a variety of applications dealing with 3D objects.

Jochen Renz - One of the best experts on this subject based on the ideXlab platform.

  • qualitative spatial reasoning with topological information
    2002
    Co-Authors: Jochen Renz
    Abstract:

    Background.- Qualitative Spatial Representation and Reasoning.- The region connection calculus.- Cognitive Properties of Topological Spatial Relations.- Computational Properties of RCC-8.- A Complete Analysis of Tractability in RCC-8.- Empirical Evaluation of Reasoning with RCC-8.- Representational Properties of RCC-8.- Conclusions.- A. Enumeration of the Relations of the Maximal Tractable Subsets of RCC-8.

  • a canonical model of the region connection calculus
    Journal of Applied Non-Classical Logics, 2002
    Co-Authors: Jochen Renz
    Abstract:

    Although the computational properties of the region connection calculus RCC-8 are well studied, reasoning with RCC-8 entails several representational problems. This includes the problem of represen...

  • maximal tractable fragments of the region connection calculus a complete analysis
    International Joint Conference on Artificial Intelligence, 1999
    Co-Authors: Jochen Renz
    Abstract:

    We present a general method for proving tractability of reasoning over disjunctions of jointly exhaustive and pairwise disjoint relations. Examples of these kinds of relations are Allen's temporal interval relations and their spatial counterpart, the R.CC8 relations by Randell, Cui, and Colin. Applying this method does not require detailed knowledge about the considered relations; instead, it is rather sufficient to have a subset of the considered set of relations for which path-consistency is known to decide consistency. Using this method, we give a complete classification of tractability of reasoning over RCC8 by identifying two large new maximal tractable subsets and show that these two subsets together with H∞, the already known maximal tractable subset, are the only such sets for RCC8 that contain all base relations. We also apply our method to Allen's interval algebra and derive the known maximal tractable subset.

  • IJCAI - Maximal Tractable Fragments of the region connection calculus: A Complete Analysis
    1999
    Co-Authors: Jochen Renz
    Abstract:

    We present a general method for proving tractability of reasoning over disjunctions of jointly exhaustive and pairwise disjoint relations. Examples of these kinds of relations are Allen's temporal interval relations and their spatial counterpart, the R.CC8 relations by Randell, Cui, and Colin. Applying this method does not require detailed knowledge about the considered relations; instead, it is rather sufficient to have a subset of the considered set of relations for which path-consistency is known to decide consistency. Using this method, we give a complete classification of tractability of reasoning over RCC8 by identifying two large new maximal tractable subsets and show that these two subsets together with H∞, the already known maximal tractable subset, are the only such sets for RCC8 that contain all base relations. We also apply our method to Allen's interval algebra and derive the known maximal tractable subset.

  • on the complexity of qualitative spatial reasoning a maximal tractable fragment of the region connection calculus
    Artificial Intelligence, 1999
    Co-Authors: Jochen Renz, Bernhard Nebel
    Abstract:

    The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question for the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the ``region connection calculus'''' RCC-8. We extend Bennett''s encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset path-consistency is sufficient for deciding consistency.

Jason Jingshi Li - One of the best experts on this subject based on the ideXlab platform.

  • Qualitative Spatial and Temporal Reasoning with Answer Set Programming
    2012 IEEE 24th International Conference on Tools with Artificial Intelligence, 2012
    Co-Authors: Jason Jingshi Li
    Abstract:

    Representing and reasoning spatial and temporal information is a key research issue in Computer Science and Artificial Intelligence. In this paper, we introduce tools that produce three novel encodings which translate problems in qualitative spatial and temporal reasoning into logic programs for answer set programming solvers. Each encoding reflects a different type of modeling abstraction. We evaluate our approach with two of the most well known qualitative spatial and temporal reasoning formalisms, the Interval Algebra and region connection calculus. Our results show some surprising findings, including the strong performance of the solver for disjunctive logic programs over the non-disjunctive ones on our benchmark problems.

Etienne Kerre - One of the best experts on this subject based on the ideXlab platform.

  • spatial reasoning in a fuzzy region connection calculus
    Artificial Intelligence, 2009
    Co-Authors: Steven Schockaert, Martine De Cock, Etienne Kerre
    Abstract:

    Although the region connection calculus (RCC) offers an appealing framework for modelling topological relations, its application in real-world scenarios is hampered when spatial phenomena are affected by vagueness. To cope with this, we present a generalization of the RCC based on fuzzy set theory, and discuss how reasoning tasks such as satisfiability and entailment checking can be cast into linear programming problems. We furthermore reveal that reasoning in our fuzzy RCC is NP-complete, thus preserving the computational complexity of reasoning in the RCC, and we identify an important tractable subfragment. Moreover, we show how reasoning tasks in our fuzzy RCC can also be reduced to reasoning tasks in the original RCC. While this link with the RCC could be exploited in practical reasoning algorithms, we mainly focus on the theoretical consequences. In particular, using this link we establish a close relationship with the Egg-Yolk calculus, and we demonstrate that satisfiable knowledge bases can be realized by fuzzy regions in any dimension.

  • Fuzzy region connection calculus
    International Journal of Approximate Reasoning, 2008
    Co-Authors: Steven Schockaert, Martine De Cock, Chris Cornelis, Etienne Kerre
    Abstract:

    One of the key strengths of the region connection calculus (RCC) -- its generality -- is also one of its most important drawbacks for practical applications. The semantics of all the topological relations of the RCC are based on an interpretation of connection between regions. Because of the manner in which the spatial relations are defined, given a particular interpretation of connection, the RCC relations are often hard to evaluate, and their semantics difficult to grasp. Our generalization of the RCC, in which the spatial relations can be fuzzy relations, inherits this limitation of the RCC. To cope with this, in this paper, we provide specific characterizations of the fuzzy spatial relations, corresponding to the particular case where connection is defined in terms of closeness between fuzzy sets. These characterizations pave the way for practical applications in which the notion of connection is graded rather than black-and-white.

  • Fuzzy region connection calculus: Representing Vague Topological Information
    International Journal of Approximate Reasoning, 2008
    Co-Authors: Steven Schockaert, Martine De Cock, Chris Cornelis, Etienne Kerre
    Abstract:

    Qualitative spatial information plays a key role in many applications. While it is well-recognized that all but a few of these applications deal with spatial information that is affected by vagueness, relatively little work has been done on modelling this vagueness in such a way that spatial reasoning can still be performed. This paper presents a general approach to represent vague topological information (e.g., A is a part of B, A is bordering on B), using the well-known region connection calculus as a starting point. The resulting framework is applicable in a wide variety of contexts, including those where space is used in a metaphorical way. Most notably, it can be used for representing, and reasoning about, qualitative relations between regions with vague boundaries.