As a part of regular conversation, one often will refer to the spatial relationships between objects by way of their positioning relative to each other. Relative Position Descriptors (RPDs) are a type of image descriptor tuned to extract this spatial relationship information from pairs of objects within an image. Of the existing RPDs, the Φ-descriptor encapsulates the widest variety of spatial relationships. Currently, algorithms exist for its computation in the case of both 2D raster and 2D vector objects. However, the algorithm for its calculation in the 2D vector case can only handle pairs of simple polygons and lacks some key features, including support for objects made of disjoint parts, objects with holes, objects sharing vertices or with parallel overlapping edges, and various spatial relationships. This thesis presents an approach for complex polygonal object Φ-descriptor computation built upon the previous vector approach. The new algorithm breaks the problem down into the analysis of object boundaries, polygon edges that represent changes in the membership of objects and spatial relationships, and brings it more in-line with the design of the 2D raster approach.

The force histogram is a quantitative representation of relative position between two objects. For 2D data, two algorithms are defined: a well-functioning line-based algorithm, and Fast Fourier Transform (FFT) based algorithm that has a high computational cost. The line-based algorithm has previously been extended to the 3D case, but found to be unstable, and affected by a variety of factors. This thesis presents an extension of the FFT-based algorithm to the 3D case along with an analysis that demonstrates that, with the exception of a few special cases, the computational time of the 3D FFT-based algorithm is less than the line-based version. In addition, the results included here shown that the FFT-based algorithm is independent of the number of directions, the types of forces, and the shapes of the objects (convex, concave, disjoint or overlapping).

Verbal descriptions of relative positions of objects in space are extremely common in everyday life. They are built around terms that denote spatial relationships (such as `inside,' `above,' `far') and that are often accompanied by qualifiers (such as `completely,' `somewhat,' `very'). Several systems for the generation of such descriptions from digital image objects can be found in the literature. The new fuzzy system presented in this paper considers a much richer set of spatial relationships and qualifiers. The system relies on one of the most recent relative position descriptors, i.e., the Φ-descriptor.

A relative position descriptor is a basis from which fuzzy models of spatial relationships can be derived. Several descriptors have been proposed in the literature, and they have found a variety of applications. The PHI-descriptor, introduced in previous work, allows the modeling of a large number of relationships. We show here that it can be used to develop crisp and fuzzy models of topological relationships. None of the other descriptors, most of which focus on directional or set relationships, have that capability.

Colour, texture, shape, and relative position descriptors are fundamental visual descriptors. In particular, a relative position descriptor is a quantitative representation of the relative position of two spatial objects, and a basis from which models of spatial relationships (like inside, above, around, near) can be derived. The affine properties of visual descriptors have been the subject of much attention. Here, we focus on the PHI-descriptor, introduced in recent work. We show that it is a relative position descriptor with remarkable affine properties, and we illustrate these properties with two experiments.

In daily conversation, people use spatial prepositions to denote spatial relationships and describe relative positions. Various quantitative relative position descriptors can be found in the literature. However, they all have been designed with 2D objects in mind, most of them cannot be extended to handle 3D objects in vector form, and there is currently no implementation able to process such objects. In this paper, we build on a descriptor called the histogram of forces, and we present the first algorithm for quantitative relative position descriptor calculation in the case of 3D vector objects. Experiments validate the approach.

In this paper, we introduce a system able to generate an intuitive, human‐like linguistic description of the topological relationships between two objects. The description includes approximate terms commonly found in daily communications. It attempts to capture the essential characteristics of the relationships, while leaving out superfluous and possibly overwhelming detail. The objects are 2‐D image objects. They need not be convex, nor connected, and they may have holes in them. Each description is built around Allen relations, based on information extracted from F‐histograms. It consists of a topological component that indicates the primary topological relationships, directional estimates of where these relationships are most prominent, and a self‐assessment component which reflects the complexity of the situation. Experiments on synthetic and real data validate the approach.

A directional map (or spatial template, fuzzy landscape) is an image where the value of each pixel represents the degree to which the pixel satisfies some directional relationship (e.g., right, left, above, below) to some reference object (i.e., a given set of pixels). There exists a simple quantitative model of such relationships, and the computation of directional maps is usually based on algorithmic implementations of this model. We show here that the model has important flaws, and we respond to the issue with a new, promising approach: all directional maps induced by the reference object are generated from a force field that the object (which is seen as a physical entity) creates around itself. Preliminary experiments illustrate and show the interest of the approach.

The relative position between two objects in a 2D raster image is often represented quantitatively by a force histogram. In the general case, force histograms are computed in O(KN√N) time: N is the number of pixels in the image and K is the number of directions in which forces are considered. When the objects are defined as fuzzy sets, this complexity also depends quadratically on the number M of possible membership degrees. In the present paper, an algorithm that runs in O(NlogN) is introduced. Computation times are basically independent of K and M. All objects (convex, concave, crisp, fuzzy) are handled in an equally fast manner. Experiments validate the theoretical analysis.

A directional spatial relationship to a reference object (e.g., "east of the post office") can be represented by a spatial template, i.e., a fuzzy subset of the Euclidean space. For each point of the space, the template indicates to what extent the relationship holds. The objects for which the relationship holds best can then be located. In previous work, we discussed the case of crisp 2D objects in raster form. We introduced a new algorithm for directional spatial template computation, which is faster, gives better results and is more flexible than its competitors. The present paper continues this line of research. The algorithm is extended to handle fuzzy objects and embed distance information. In existing models, only angular deviation is taken into account. Spatial distance, however, also contributes in shaping directional templates.

If you were told that some object A was perfectly (or somewhat, or not at all) in some direction d (e.g., west, above-right) of some reference object B, where in space would you look for A? Cognitive experiments suggest that you would mentally build a spatial template. Using essentially angular deviation, you would partition the space into regions where the relationship "in direction d of B" holds (to various extents) and regions where it does not hold. You would then be able to locate the objects for which the relationship holds best, and find A. Spatial templates, therefore, represent directional spatial relationships to reference objects (e.g., "east of the post office"). Note that other names can also be found in the literature (e.g., fuzzy landscape, applicability structure, potential field). There exists a very simple and yet cognitively plausible way to mathematically model a spatial template without sacrificing the geometry of the reference object (i.e., the object is not approximated through its centroid or minimum bounding rectangle). In case of 2D raster data, exact calculation of the model can easily be achieved but is computationally expensive, and tractable approximation algorithms were proposed. In case of 2D vector data, exact calculation of the model is not conceivable. In previous work, we introduced the concept of the F-template. We discussed the case of 2D raster data and designed, based on this concept, an efficient approximation algorithm for spatial template computation. The algorithm is faster, gives better results, and is more flexible than its competitors. Here, comparable advances are presented in the case of 2D vector data. These advances are of particular interest for spatial query processing in Geographic Information Systems.

In earlier work, we introduced a method for generating linguistic descriptions of the topological relationships between two-dimensional objects. The input to the system is a pair of rasterized objects and the output is a set of propositions about their spatial relationships expressed in natural language. The method relies on finding one or two Allen relations that best describe the relationships along a direction of major object interaction. In this paper, we address some of the issues related to the use of Allen relations for describing two-dimensional object configurations, and we propose two extensions in order to solve problems encountered in the original algorithm. Global subsethood-based information is used to suppress counterintuitive descriptions and an ancillary method for generating alternative descriptions is introduced

In this correspondence, we introduce our work on sketch understanding, focusing here on the analysis of a sketched route map. A route map is drawn to help someone navigate along a path for the purpose of reaching a goal. A hand-sketched route map does not generally contain complete map information and is not necessarily drawn to scale, but yet it contains the correct qualitative information for route navigation. Here we propose a methodology for extracting a qualitative model of a sketched route map, based on human navigation strategies, using spatial relationships. Linguistic descriptions are generated from the sketch, both in the form of detailed descriptions at discrete path steps and also as a high-level route description. To describe the path linguistically, one must first be able to understand the path in a qualitative sense. We assert that the translation of a sketch into linguistic descriptions illustrates that the essential qualitative path knowledge has been extracted. The methodology is demonstrated using example sketches drawn on a handheld PDA.

Previously, we introduced a method for estimating the linguistic direction of motion of an object in a scene by processing a temporal sequence of linguistic descriptions of its position relative to a stationary object. This method relies on the observation of "regular" descriptions generated through a fuzzy logic system based on the histogram of forces. These descriptions may not exist if the distance between the two objects is too close. In this paper, we use fuzzy sets to generate degrees of activation for the estimated directions of motion. Temporal fusion is applied on these values over a fixed time window using weights calculated from linguistic information on the distance between the objects. The new dynamic linguistic descriptions are determined based on the present as well as the past estimates.

Spatial relationships among image objects play a vital role in countless domains of computer vision (e.g., pattern recognition, image understanding, scene description). Some have received considerable attention the last few years (e.g., "to the right of," "above," "to the left of" and "below"), but others have not been the subject of as much investigation. In this paper, we design consistent fuzzy models of three important spatial relationships: "surrounded by," "between" and "among." These models are based on the histogram of forces, which represents the relative position between two objects. Here, force histograms are assimilated to fuzzy sets and processed through their /spl alpha/-cuts. Our goal is to extend the capabilities of a fuzzy system for linguistic scene description introduced in an earlier paper.

It is often difficult to find a well-principled approach for the selection of a spatial indexing mechanism for medical image databases. Spatial information concerning lesions in medical images is critically important in disease diagnosis and plays an important role in image retrieval. Unfortunately, images are rarely indexed properly for clinically useful retrieval. One example is the well-known R-tree and its variants which index image objects based on their physical locations in an "absolute" way. However, such information is not meaningful in medical content-based image retrieval systems, and the approaches suffer from problems caused by variations in object size and shape, imprecise image centering, etc. A more appropriate approach, which does not require object registration, is to model the spatial relationships between lesions and anatomical landmarks. To convey diagnostic information, lesions must exist in certain locations with regard to landmarks. In this paper, we show that the histogram of forces (which represents the relative position between two objects) provides an efficient spatial indexing mechanism in the medical domain.

This paper examines object pair matching within LADAR (laser radar) imagery. By manipulating the three-dimensional data contained within a LADAR range image, it is possible to create a version of the scene as seen from above. In the transformed view, a fuzzy region represents each object, and the spatial relationship between two objects is represented by a force histogram. Matching two scenes then comes down to comparing force histograms. Each comparison gives a degree of similarity between the two object pairs considered, as well as an assessment of the pose parameters. These values can finally be combined to find a correct scene matching. Experiments on synthetic data as well as on real data demonstrate the applicability of our approach.

This paper describes a new approach to integrating structural knowledge into the image classification process. First, a fuzzy classifier produces a fuzzy partition of the image. Then, the defuzzified (crisp) partition is tried to be improved. According to the membership degrees in the fuzzy partition, the system selects a set of pixels and associates a set of candidate classes with each of them. The initial crisp partition is improved by reassigning each selected pixel to one of the classes it may belong to. This is performed by a combinatorial optimization strategy. The aim is to maximize the adequacy between the regions defined by the crisp partition and the available structural knowledge. First experiments on synthetic data as well as on simple real data show the applicability of our approach.

We show how linguistic expressions can be generated to describe the spatial relations between a mobile robot and its environment, using readings from a ring of sonar sensors. Our work is motivated by the study of human-robot communication for non-expert users. The eventual goal is to use these linguistic expressions for navigation of the mobile robot in an unknown environment, where the expressions represent the qualitative state of the robot with respect to its environment, in terms that are easily understood by human users. In the paper, we describe the histogram of forces and its application to sonar sensors on a mobile robot. Several environment examples are also included with the generated linguistic descriptions.

Being able to interact and communicate with robots in the same way we interact with people has long been a goal of AI and robotics researchers. In this paper, we propose a novel approach to communicating a navigation task to a robot, which allows the user to sketch an approximate map on a PDA and then sketch the desired robot trajectory relative to the map. State information is extracted from the drawing in the form of relative, robot-centered spatial descriptions, which are used for task representation and as a navigation language between the human user and the robot. Examples are included of two hand-drawn maps and the linguistic spatial descriptions generated from the maps.

Fuzzy set methods have been used to model and manage uncertainty in various aspects of image processing, pattern recognition, and computer vision. High-level computer vision applications hold a great potential for fuzzy set theory because of its links to natural language. Linguistic scene description, a language-based interpretation of regions and their relationships, is one such application that is starting to bear the fruits of fuzzy set theoretic involvement. In this paper, we are expanding on two earlier endeavors. We introduce new families of fuzzy directional relations that rely on the computation of histograms of forces. These families preserve important relative position properties. They provide inputs to a fuzzy rule base that produces logical linguistic descriptions along with assessments as to the validity of the descriptions. Each linguistic output uses hedges from a dictionary of about 30 adverbs and other terms that can be tailored to individual users. Excellent results from several synthetic and real image examples show the applicability of this approach.

In a previous work (1999), we defined a new approach to evaluating directional relations between objects. The approach is based on the computation of a histogram of forces. We show in the present paper that the notion of the histogram of forces can also be useful in pattern recognition. The aim of this this study is to classify orbits and sinuses. Using force histograms instead of geometrical criteria (like compactness or degree of ellipticity) allows more accurate classification to be produced. Moreover, the proposed approach requires low completing time.

The fuzzy qualitative evaluation of directional spatial relationships (such as "to the right of", "to the south of...") between areal objects often relies on the computation of a histogram of angles, which is considered to provide a good representation of the relative position of an object with regard to another. In this paper, the notion of the histogram of forces is introduced. It generalizes and may supersede the histogram of angles. The objects (2D entities) are handled as longitudinal sections (1D entities), not as points (OD entities). It is thus possible to fully benefit from the power of integral calculus and, so, ensure rapid processing of raster data, as well as of vector data, explicitly considering both angular and metric information.