Object localization based on directional information case of 2D vector data

ABSTRACT

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.

REFERENCES

• 1: R. Krishnapuram, J.M. Keller, and Y. Ma, "Quantitative Analysis of Properties and Spatial Relations of Fuzzy Image Regions", IEEE Trans. on Fuzzy Systems, 1993, vol. 1, no. 3, pp. 222--233
• 2: Jayant Sharma , Douglas M. Flewelling, Inferences from Combined Knowledge about Topology and Directions, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.279-291, August 06-09, 1995
• 3: D. Papadias, and Y. Theodoridis, "Spatial Relations, Minimum Bounding Rectangles, and Spatial Data Structures", Int. J. of Geographical Information Science, 1997, vol. 11, pp. 111--138
• 4: Pascal Matsakis , Laurent Wendling, A New Way to Represent the Relative Position between Areal Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.7, p.634-643, July 1999 [doi>10.1109/34.777374]
• 5: Frederick E. Petry , Maria A. Cobb , Dia Ali , Rafal Angryk , Marcin Paprzycki , Shahram Rahimi , Lixiong Wen , Huiqing Yang, Fuzzy spatial relationships and mobile agent technology in geospatial information systems, Applying soft computing in defining spatial relations, Physica-Verlag GmbH, Heidelberg, Germany, 2002
• 6: D. J. Peuquet , Ci-Xiang Zhang, An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane, Pattern Recognition, v.20 n.1, p.65-74, 1987 [doi>10.1016/0031-3203(87)90018-5]
• 7: Roop K. Goyal , Max J. Egenhofer, Similarity of Cardinal Directions, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.36-58, July 12-15, 2001
• 8: Christophe Claramunt , Marius Thériault, Fuzzy semantics for direction relations between composite regions, Information Sciences—Informatics and Computer Science: An International Journal, v.160 n.1-4, p.73-90, 22 March 2004 [doi>10.1016/j.ins.2003.07.013]
• 9: A. U. Frank, "Qualitative spatial reasoning: Cardinal directions as an example", International Journal of Geographical Information Systems (10) 3, 1996, pp. 269--290
• 10: Isabelle Bloch, Fuzzy Relative Position Between Objects in Image Processing: A Morphological Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.7, p.657-664, July 1999 [doi>10.1109/34.777378]
• 11: G.D. Logan, and D.D. Sadler, "A Computational Analysis of the Apprehension of Spatial Relations", in P. Bloom, M.A. Peterson, L. Nadel, and M.F. Garrett (Eds.), Language and Space, Cambridge, MA: MIT Press, 1996
• 12: Klaus-Peter Gapp, Basic meanings of spatial relations: computation and evaluation in 3D space, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.1393-1398, October 1994, Seattle, Washington, United States
• 13: P. Olivier, and J.-I. Tsuji, "Quantitative Perceptual Representation of Prepositional Semantics", in Artificial Intelligence Review (Special Issue on Integration of Natural Language and Vision Processing), 1994, vol. 8, pp. 147--158
• 14: Pascal Matsakis , JingBo Ni , Xin Wang, Object Localization Based on Directional Information: Case of 2D Raster Data, Proceedings of the 18th International Conference on Pattern Recognition, p.142-146, August 20-24, 2006 [doi>10.1109/ICPR.2006.879]
• 15: J. Freeman, "The Modeling of Spatial Relations", Computer Graphics and Image Processing, 1975, vol. 4, pp. 156--171
• 16: K.-P. Gapp, "Angle, Distance, Shape, and Their Relationship to Projective Relations", 17th Annual Conf. of the Cognitive Science Society, Pittsburgh, PA, 1995, Proceedings, Mahwah, NJ: Lawrence Erlbaum, pp. 112--117
• 17: N. Franklin, L.A. Henkel, and T. Zengas, "Parsing Surrounding Space Into Regions", Memory and Cognition, 1995, vol. 23, pp. 397--407
• 18: P. Matsakis, Relations Spatiales Structurelles et Interprétation d'images, PhD Thesis, Institut de Recherche en Informatique de Toulouse, France, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Feature representation
      I.4.8 Scene Analysis
          Subjects: Object recognition
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Fuzzy set; Geometric
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Algorithms

Keywords:
directional relationships, directional templates, f-templates, spatial relationships, spatial templates