Représentation de la position relative d'objets 2D au moyen d'un histogramme de forces
The Notion of Histogram of Forces : a New Way to Represent the Relative Position of 2D-Objects
OPEN ACCESS
The assessment of the directional spatial relations (such as "to the right of", "to the south of" . . .) between 2D-objects relies generally on the computation of a histogram of angles, which is supposed to provide a reasonably good representation of the relative position of an object with regard to another. In this paper, we introduce the notion of histogram of forces. It generalizes and supersedes the one of histogram of angles. The objects are handled as longitudinal sections (1D-entities). It is thus possible to benefit in full by the power of integral calculus and to ensure a rapid processing of raster data as well as of vector data under explicit consideration of both angular and metric information.
Résumé
L'évaluation des relations spatiales directionnelles (telles que « à droite de », « au sud de » . . .) entre objets 2D repose généralement sur la constitution d'un histogramme d'angles . Un tel histogramme est supposé constituer une bonne représentation de la position relative d'un objet par rapport à un autre . Dans cet article, nous introduisons la notion d'histogramme de forces. Elle généralise et supplante celle d'histogramme d'angles. La manipulation des objets (entités de dimension 2) est ramenée à celle de leurs sections longitudinales (entités de dimension 1), non pas à celle de points. Il est ainsi possible de bénéficier de la puissance du calcul intégral et d'assurer un traitement incomparablement plus rapide aussi bien de données rasters que vecteurs, tout en tenant compte explicitement aussi bien de l'information angulaire que de l'information métrique.
Pattern recognition, parameter extraction, spatial relationships, fuzzy subsets
Mots clés
Reconnaissance des formes, extraction de paramètres, relations spatiales, sous-ensembles flous
[Blo96] I . Bloch, "Fuzzy relative position between objects in images : a morphological approach, ICIP'96, Lausanne, Vol . II, 987-990, 1996.
[Dub87] D.Dubois, M .C.Jaulent, "A general approach to parameter evaluation in fuzzy digital pictures", Pattern Recognition Letters 6, pp.251-259, 1987.
[Dub80] D.Dubois, H . Prade, "Fuzzy Sets and Systems : Theory and Applications", Mathematics in science and engineering, vol 144, pp4O, 1980.
[Fre75] J.Freeman, "The modelling of spatial relations", Computer Graphics and Image Processing, vol .4, pp.156-171, 1975.
[Ke190] J .M. Keller, L. Sztandera, "Spatial relations among fuzzy subsets of an image", Proc. of the First Int. Symposium on Uncertainty Modeling and Analysis, College Park, University of Maryland, pp.207-211, 1990.
[Ke195] J.M. Keller, X. Wang, "Comparison of spatial relation definitions in computer vision",ISUMA-NAFIPS'95, College Park MD, pp .679-684, 1995.
[Ke196] J .M . Keller, X . Wang, "Learning Spatial Relationships in Computer Vision", FUZZ-IEEE, 1996.
[Koc88] L . T. Kòczy, "On the description of relative position of fuzzy patterns" , Pattern Recognition Letters 8, pp2l-28, 1988.
[Kri93] R .Krishnapuram, J .M .Keller, Y.Ma, "Quantitative analysis of properties and spatial relations of fuzzy image regions", IEEE Transactions on Fuzzy Systems, vol .l, no .3, pp .222-233, 1993.
[Mat98] P. Matsakis, "Relations spatiales structurelles et interprétation d'images" , Thèse de Doctorat, Université Paul Sabatier, Toulouse III, janvier 1998 .
[Miy94] K .Miyajima, A .Ralescu, "Spatial organization in 2D segmented images : representation and recognition of primitive spatial relations", Fuzzy Sets and Systems, vol .65, iss .2/3, pp .225-236, 1994.
[Peu87] D .J.Peuquet, Z.CI-Xiang, "An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane", Pattern Recognition, vol.20, no.1, pp .65-74, 1987.
[Ret88] G .Retz-Schmidt, "Various Views on Spatial Prepositions", AI Magazine 9, pp .95-105, 1988.
[Rog88] D .F.Rogers, Algorithmes pour l'infographie, McGraw-Hill, Paris, 1988.
[Ros82] A.Rosenfeld, A .C .Kak, Digital picture processing, vol.2, Academic Press, pp .263-264, 1982.
[Ros85] A . Rosenfeld, R . Klette, "Degree of adjacency and surroundedness" , Pattern Recognition, vol . 18, pp . 169-177, 1985.
[Wen97] L . Wendling, J. Desachy, "Isomorphism between Strong Fuzzy Relational Graphs based on k-formulae", Workshop Graph Based Representation, IAPR, à paraître dans Lecture Notes in Computer Advances, 1997.
[Win75] P.H.Winston, The psychology of computer vision, McGraw-Hill, New York, 1975.
[Wor95] M. EWorboys, GIS - A computing perspective, Taylor & Francis, 1995.