13.5 General Spatial Reasoning and Geometric Reasoning Issues

Chapter Contents (Back)
Spatial Reasoning. Spatial Relations. Geometric Reasoning. Some of this is in the invariants chapter. See also Invariants -- Eigen Representations, General Appearance Based Methods. See also Digital Geometry.

Lane, E.,
Projective Differential Geometry of Curves and Surfaces,
University of ChicagoPress, 1932. BibRef 3200

Freeman, J.,
The Modelling of Spatial Relations,
CGIP(4), No. 2, June 1975, pp. 156-171.
WWW Version. Basic introduction to the use of spatial relations in descriptions. BibRef 7506

Sadananda, R., Mahabala, H.N.,
Conceptference: A System That Develops Concepts and Infers on Pictorial Data,
SMC(8), 1978, pp. 232-236. BibRef 7800

Sinha, R.M.K., Mahabala, H.N.,
Towards Design of a Natural Picture Description Language,
PRIP78(416-420). BibRef 7800

Haralick, R.M., Wang, S., Elliott, D.B., Campbell, J.B., and Ehrich, R.W.,
Spatial Reasoning in Remotely Sensed Data,
GeoRS(21), No. 1, January, 1983, pp. 94-101. BibRef 8301

Peuquet, D.J., Zhan, C.X.[Ci-Xiang],
An Algorithm to Determine the Directional Relationship between Arbitrarily-Shaped Polygons in the Plane,
PR(20), No. 1, 1987, pp. 65-74.
WWW Version. BibRef 8700

Fleming, A.[Alan],
Geometric Relationships Between Toleranced Features,
AI(37), No. 1-3, December, 1988, pp. 403-412.
WWW Version. BibRef 8812

Arnon, D.S.[Dennis S.],
Geometric reasoning with logic and algebra,
AI(37), No. 1-3, December, 1988, pp. 37-60.
WWW Version. BibRef 8812

Mitchell, J.S.B.[Joseph S. B.],
An algorithmic approach to some problems in terrain navigation,
December 1988, Pages AI(37), No. 1-3, December, 1988, pp. 171-201.
WWW Version. BibRef 8812

Srihari, S.N., Xiang, Z.,
Spatial Knowledge Representation,
PRAI(3), 1989, pp. 67-84. BibRef 8900

Mulgaonkar, P.G.[Prasanna G.], Shapiro, L.G., and Haralick, R.M.,
Spatial Reasoning Using Modular Inference Engines,
ASR-I90(8). BibRef 9000

Magee, M., Wolfe, W.J., Mathis, D., and Weber, C.,
Model-Based Spatial Reasoning for Hierarchically Organized Structured Objects,
ASR-I90(Ch. 5). BibRef 9000

Magee, M., Nathan, M.,
A Viewpoint Independent Modeling Approach to Object Recognition,
RA(3), 1987, pp. 351-356. BibRef 8700

Magee, M.[Michael], and Nathan, M.[Mitchell],
A Rule Based System for Pattern Recognition that Exploits Topological Constraints,
CVPR86(62-67). BibRef 8600

Koczy, L.T.,
On the Description of Relative Position of Fuzzy Objects,
PRL(8), 1988, pp. 21-28. Uses the inverse of a relation. BibRef 8800

Dutta, S.,
Approximate Spatial Reasoning: Integrating Qualitative and Quantitative Constraints,
ApproximateR(5), 1991, pp. 307-331. Qualitative spatial relationships. BibRef 9100

Miyajima, K., Ralescu, A.,
Spatial Organization in 2D Segmented Images: Representation and Recognition of Primitive Spatial Relations,
FuzzySets(65), 1994, pp. 225-236. Histogram of angles. BibRef 9400

Cohn, A.G., Gooday, J.M., Bennett, B., Gotts, N.M.,
A Logical Approach to Representing and Reasoning about Space,
AIR(9), No. 4-5, October 1995, pp. 255-259. BibRef 9510

Cohn, A.G.,
The Challenge of Qualitative Spatial Reasoning,
Surveys(27), No. 3, September 1995, pp. 323-325. Survey, Spatial Reasoning. BibRef 9509

Retz-Schmidt, G.,
Various Views on Spatial Prepositions,
AIMag(9), No. 2, Summer 1988, pp. 95-105. BibRef 8800

Retz-Schmidt, G.,
Deictic and Intrinsic Use of Spatial Prepositions: A Multidisciplinary Comparison,
SRMSF87(371-380). BibRef 8700

Tambouratzis, T.,
Using Geometrical Information for Accurate Scene Understanding in an Artificial Vision System,
IJIS(11), No. 10, October 1996, pp. 833-863. 9610
BibRef

Holt, R.J., Huang, T.S., Netravali, A.N.,
Algebraic Methods for Image Processing and Computer Vision,
IP(5), No. 6, June 1996, pp. 976-986.
IEEE DOI Link 9607
BibRef

Coenen, F.P., Beattie, B., Shave, M.J.R., Benchcapon, T.J.M., Diaz, B.M.,
Spatial Reasoning Using the Quad Tesseral Representation,
AIR(12), No. 4, August 1998, pp. 321-343. 9808
BibRef

Coenen, F.[Frans],
Tesseral spatio-temporal reasoning for multi-dimensional data,
PR(33), No. 1, January 2000, pp. 9-23.
WWW Version. 0005
BibRef

Papadias, D.[Dimitris], Egenhofer, M.J.[Max J.],
Algorithms for Hierarchical Spatial Reasoning,
GeoInfo(1), No. 3, October 1997, pp. 251-273.
WWW Version. BibRef 9710

Cohn, A.G.[Anthony G.], Bennett, B.[Brandon], Gooday, J.[John], Gotts, N.M.[Nicholas Mark],
Qualitative Spatial Representation and Reasoning with the Region Connection Calculus,
GeoInfo(1), No. 3, October 1997, pp. 275-316.
WWW Version. BibRef 9710

Cohn, A.G.[Anthony G.], Hogg, D.C., Bennett, B.[Brandon], Devin, V., Galata, A., Magee, D.R., Needham, C., Santos, P.,
Cognitive Vision: Integrating Symbolic Qualitative Representations with Computer Vision,
CogVis03(221-246).
Springer DOI Link 0310
BibRef

Schweikard, A.[Achim], Schwarzer, F.[Fabian],
Detecting geometric infeasibility,
AI(105), No. 1-2, October 1998, pp. 139-159.
WWW Version. Geometric reasoning. BibRef 9810

Shekhar, S.[Shashi], Liu, X.[Xuan], Chawla, S.[Sanjay],
An Object Model of Direction and Its Implications,
GeoInfo(3), No. 4, December 1999, pp. 357-379.
WWW Version. 0509
BibRef

Bloch, I.[Isabelle],
Fuzzy Relative Position Between Objects in Image Processing: A Morphological Approach,
PAMI(21), No. 7, July 1999, pp. 657-664.
IEEE Abstract.
IEEE DOI Link BibRef 9907
Earlier:
Fuzzy classification for multi-modality image fusion,
ICIP94(I: 628-632).
IEEE DOI Link 9411
Relative positions using fuzzy sets for structural descriptions. See also Fuzzy Connectivity and Mathematical Morphology. BibRef

Bloch, I.[Isabelle],
Bipolar Fuzzy Mathematical Morphology for Spatial Reasoning,
ISMM09(24-34).
Springer DOI Link 0908
See also Fuzzy Connectivity and Mathematical Morphology. BibRef

Bloch, I.[Isabelle],
Unifying Quantitative, Semi-quantitative and Qualitative Spatial Relation Knowledge Representations Using Mathematical Morphology,
WTRCV02(153-164). 0204
BibRef

Bloch, I.[Isabelle], Maître, H.[Henri],
Extending adjacency to fuzzy sets for coping with imprecise image objects,
CIAP97(I: 30-37).
WWW Version. 9709
BibRef

Bloch, I.[Isabelle], Ralescu, A.[Anca],
Directional Relative Position Between Objects in Image Processing: A Comparison Between Fuzzy Approaches,
PR(36), No. 7, July 2003, pp. 1563-1582.
WWW Version. 0304
BibRef

Bloch, I.,
Fuzzy relative position between objects in images: A morphological approach,
ICIP96(II: 987-990).
IEEE DOI Link 9610
BibRef

Matsakis, P., Keller, J.M., Wendling, L., Marjamaa, J., Sjahputera, O.,
Linguistic description of relative positions in images,
SMC-B(31), No. 4, August 2001, pp. 573-588.
IEEE Top Reference. Fuzzy sets for linguistic descriptions. 0109
BibRef

Matsakis, P.[Pascal], Wendling, L.[Laurent],
A New Way to Represent the Relative Position between Areal Objects,
PAMI(21), No. 7, July 1999, pp. 634-643.
IEEE Abstract.
IEEE DOI Link This paper describes a method for computing relative position relations (e.g. above, to left of, to the east of, etc.) between two-dimensional objects in images. These relations are commonally used in human descriptions of scenes, but there is no precise definition for such relations especially when areal (i.e. a 2-D region) features are involved. The aim of this paper is not to give a precise definition to a relation such as "to the left of," but to provide an efficient and understandable way to compute this property, no matter what exact definition is desired. The authors introduce the idea of a "histogram of forces" that gives a value for each angle of the "force" between the two objects. A high force would indicate support for that relationship. As an example of the results, the system produces a moderately strong value (55 and 65, depending on the force definition used) for the relation "Spain is south of France" and a weaker value (47 and 40) for "Spain is West of France," which corresponds to the general human interpretation of their relationship. See also Modelling of Spatial Relations, The. BibRef 9907

Skubic, M., Matsakis, P., Chronis, G., Keller, J.M.,
Generating Multi-Level Linguistic Spatial Descriptions form Range Sensor Readings Using the Histogram of Forces,
AutRob(14), No. 1, 2003, pp. 51-69. BibRef 0300

Skubic, M., Perzanowski, D., Blisard, S., Schultz, A., Adams, W., Bugajska, M., Brock, D.,
Spatial language for human-robot dialogs,
SMC-C(34), No. 2, May 2004, pp. 154-167.
IEEE Abstract. 0407
BibRef

Matsakis, P.[Pascal], Keller, J.M.[James M.], Sjahputera, O.[Ozy], Marjamaa, J.[Jonathon],
The Use of Force Histograms for Affine-Invariant Relative Position Description,
PAMI(26), No. 1, January 2004, pp. 1-0_6.
IEEE Abstract. 0401
How affine transforms affect the descriptor. Any 2 of applied affine transform, relative position before, relative position after, allows other to be determined. BibRef

Matsakis, P.[Pascal],
Relations Spatiales Structurelles et Interpretation d'Images,
Ph.D.Thesis, Institut de Recherche en Informatique de Toulouse, France, 1998. BibRef 9800

Matsakis, P.[Pascal], Wendling, L.[Laurent], Desachy, J.,
Representation de la Position Relativ d'Objets 2D au Moyen d'un Histogramme de Froces,
Traitement du Signal(15), No. 1, 1998, pp. 25-38. BibRef 9800

Matsakis, P.[Pascal], Ni, J.[JingBo], Wang, X.[Xin],
Object Localization Based on Directional Information: Case of 2D Raster Data,
ICPR06(II: 142-146).
IEEE DOI Link 0609
Directional spatial relations. BibRef

Keller, J.M.[James M.], Wang, X.M.[Xiao-Mei],
A Fuzzy Rule-Based Approach to Scene Description Involving Spatial Relationships,
CVIU(80), No. 1, October 2000, pp. 21-41.
WWW Version. 0010
BibRef

Keller, J.M., Gader, P.D., Wang, X.,
LADAR Scene Description Using Fuzzy Morphology and Rules,
CVBVS99(120).
IEEE DOI Link BibRef 9900

Krishnapuram, R., Keller, J.M., Ma, Y.,
Quantative Analysis of Properties and Spatial Relations of Fuzzy Image Regions,
Fuzzy(1), No. 3, 1993, pp. 222-233. Histogram of angles for relationships. BibRef 9300

Medasani, S., Krishnapuram, R., Keller, J.M.,
Are Fuzzy Definitions of Basic Attributes of Image Objects Really Useful?,
SMC-A(29), No. 4, July 1999, pp. 378.
IEEE Top Reference. BibRef 9907

Xiong, D.M.[De-Min], Lin, H.[Hui],
Spatial Data Handling for ITS: Perspective, Issues and Approaches,
GeoInfo(4), No. 2, June 2000, pp. 215-230.
WWW Version. 0509
BibRef

Jan, S.R., Hsueh, Y.C.,
Primitive spatial relations based on SKIZ,
IVC(18), No. 8, 15 May 2000, pp. 597-605.
WWW Version. 0003
BibRef

Guru, D.S., Nagabhushan, P.,
Triangular Spatial Relationship: A New Approach for Spatial Knowledge Representation,
PRL(22), No. 9, July 2001, pp. 999-1006.
Elsevier DOI Link 0106
BibRef

Lang, D.[Dieter], Winter, S.[Stephan], Frank, A.U.[Andrew U.],
Neighborhood Relations between Fields with Applications to Cellular Networks,
GeoInfo(5), No. 2, June 2001, pp. 127-144.
WWW Version. 0108
BibRef

Gerevini, A.[Alfonso], Renz, J.[Jochen],
Combining topological and size information for spatial reasoning,
AI(137), No. 1-2, May 2002, pp. 1-42.
WWW Version. 0205
BibRef

Chen, J.[Jun], Zhao, R.[Renliang], Li, Z.L.[Zhi-Lin],
Voronoi-based k-order neighbour relations for spatial analysis,
PandRS(59), No. 1-2, August 2004, pp. 60-72.
WWW Version. 0411
Spatial relationships. BibRef

Bloch, I.[Isabelle],
Fuzzy Spatial Relationships for Image Processing and Interpretation: A Review,
IVC(23), No. 2, 1 February 2004, pp. 89-110.
WWW Version. 0412
BibRef

Lazebnik, S.[Svetlana], Ponce, J.[Jean],
The Local Projective Shape of Smooth Surfaces and Their Outlines,
IJCV(63), No. 1, June 2005, pp. 65-83.
Springer DOI Link 0501
BibRef
Earlier: ICCV03(83-89).
IEEE DOI Link 0311
Projective invariant features of curves and surfaces. BibRef

Dehak, S.M.R.[Sidi Mohammed Reda], Bloch, I.[Isabelle], Maitre, H.[Henri],
Spatial Reasoning with Incomplete Information on Relative Positioning,
PAMI(27), No. 9, September 2005, pp. 1473-1484.
IEEE DOI Link 0508
Inferring relative position of 2 points knowing their relative position to a third point. E.g. map locations. BibRef

Yoo, J.S.[Jin Soung], Shekhar, S.[Shashi],
In-Route Nearest Neighbor Queries,
GeoInfo(9), No. 2, June 2005, pp. 117-137.
Springer DOI Link 0509
BibRef

Shirabe, T.[Takeshi],
Classification of Spatial Properties for Spatial Allocation Modeling,
GeoInfo(9), No. 3, September 2005, pp. 269-287.
Springer DOI Link 0509
BibRef

Bloch, I., Colliot, O., Cesar, Jr., R.M.,
On the Ternary Spatial Relation 'Between',
SMC-B(36), No. 2, April 2006, pp. 312-327.
IEEE DOI Link 0604
BibRef

Yan, H.[Haowen], Chu, Y.D.[Yan-Dong], Li, Z.L.[Zhi-Lin], Guo, R.Z.[Ren-Zhong],
A Quantitative Description Model for Direction Relations Based on Direction Groups,
GeoInfo(9), No. 2, June 2006, pp. 177-196.
Springer DOI Link 0605
BibRef

Skiadopoulos, S.[Spiros], Koubarakis, M.[Manolis],
On the consistency of cardinal direction constraints,
AI(163), No. 1, March 2005, pp. 91-135.
Elsevier DOI Link 0605
BibRef

Laub, J.[Julian], Roth, V.[Volker], Buhmann, J.M.[Joachim M.], Müller, K.R.[Klaus-Robert],
On the information and representation of non-Euclidean pairwise data,
PR(39), No. 10, October 2006, pp. 1815-1826.
WWW Version. 0606
Non-Euclidean pairwise data; Embedding; Visualization; Multidimensional scaling As opposed to vector representations. BibRef

Pham, T.V.[Thang V.], Smeulders, A.W.M.[Arnold W.M.],
Learning spatial relations in object recognition,
PRL(27), No. 14, 15 October 2006, pp. 1673-1684.
WWW Version. 0609
Articulated object; Bayesian network; Deformable model; Part-based approach; Shape; Spatial relation Deformable relations and pairwise pixel relations. BibRef

Liu, Y.[Yu], Guo, Q.H.[Qing-Hua], Kelly, M.[Maggi],
A framework of region-based spatial relations for non-overlapping features and its application in object based image analysis,
PandRS(63), No. 4, July 2008, pp. 461-475.
WWW Version. 0804
Region-based spatial relations; Single-valued space; Object based image analysis BibRef

Du, S.H.[Shi-Hong], Guo, L.[Luo], Wang, Q.[Qiao], Qin, Q.M.[Qi-Min],
Efficiently computing and deriving topological relation matrices between complex regions with broad boundaries,
PandRS(63), No. 6, November 2008, pp. 593-609.
WWW Version. 0811
Geographical information system; Complex regions with broad boundaries; Topological relations; Reasoning about topological relations BibRef

Schockaert, S.[Steven], de Cock, M.[Martine], Kerre, E.E.[Etienne E.],
Spatial reasoning in a fuzzy region connection calculus,
AI(173), No. 2, February 2009, pp. 258-298.
Elsevier DOI Link
WWW Version. 0804
Spatial reasoning; Region connection calculus; Fuzzy set theory BibRef

Deruyver, A.[Aline], Hodé, Y.[Yann],
Qualitative spatial relationships for image interpretation by using a conceptual graph,
IVC(27), No. 7, 4 June 2009, pp. 876-886.
Elsevier DOI Link
WWW Version. 0904
BibRef
Earlier: A2, A1:
Qualitative Spatial Relationships for Image Interpretation by Using Semantic Graph,
GbRPR07(240-250).
Springer DOI Link 0706
Image interpretation; Spatial relationships; Conceptual graph; Arc-consistency analysis BibRef

Deruyver, A.[Aline], Hodé, Y.[Yann],
Arc-Consistency Checking with Bilevel Constraints: An Optimization,
GbRPR09(174-183).
Springer DOI Link 0905
BibRef

Deruyver, A., Hode, Y.,
Semantic graph and arc consistency in 'true' three dimensional image labelling,
ICIP95(II: 619-622).
IEEE DOI Link 9510
BibRef

Deruyver, A.[Aline], Hode, Y.[Yann], Brun, L.[Luc],
Image interpretation with a conceptual graph: Labeling over-segmented images and detection of unexpected objects,
AI(173), No. 14, September 2009, pp. 1245-1265.
Elsevier DOI Link
WWW Version. 0910
Image interpretation; Conceptual graph; Arc-consistency analysis BibRef

Bejaoui, L.[Lotfi], Pinet, F.[François], Schneider, M.[Michel], Bédard, Y.[Yvan],
OCL for formal modelling of topological constraints involving regions with broad boundaries,
GeoInfo(14), No. 3, July 2010, pp. xx-yy.
Springer DOI Link 1003
BibRef

Takemura, C.M.[Celina Maki], Cesar, Jr., R.M.[Roberto M.], Bloch, I.[Isabelle],
Modeling and measuring the spatial relation 'along': Regions, contours and fuzzy sets,
PR(45), No. 2, February 2012, pp. 757-766.
Elsevier DOI Link
WWW Version. 1110
Spatial relations; Spatial reasoning; Structural pattern recognition BibRef

Liu, W.M.[Wei-Ming], Li, S.J.[San-Jiang],
Reasoning about cardinal directions between extended objects: The NP-hardness result,
AI(175), No. 18, December 2011, pp. 2155-2169.
Elsevier DOI Link
WWW Version. 1112
Qualitative spatial reasoning; Cardinal direction calculus; NP-hardness; Consistency checking; Reduction BibRef

Uijlings, J.R.R., Smeulders, A.W.M., Scha, R.J.H.,
The Visual Extent of an Object: Suppose We Know the Object Locations,
IJCV(96), No. 1, January 2012, pp. 46-63.
WWW Version. 1201
BibRef
Earlier:
What is the spatial extent of an object?,
CVPR09(770-777).
IEEE DOI Link 0906
Depends on the recognition method. Region, whole image. Rigid object primarly recognized by shape, non-rigid by texture. With unknown location, the surrounding context is less significant. BibRef

Chang, C.L.[Chin-Lung], Chang, Y.H.[Yi-Hong], Chuang, T.R.[Tyng-Ruey], Deng, D.P.[Dong-Po], Huang, A.W.C.[Andrea Wei-Ching],
Narrative Geospatial Knowledge in Ethnographies: Representation and Reasoning,
GS09(188-203).
Springer DOI Link 0912
Analyze narrative descriptions to get more accurate geospatial information. BibRef

Frank, A.U.[Andrew U.],
Multi-cultural Aspects of Spatial Knowledge,
GS09(1-8).
Springer DOI Link 0912
Cultural differences for GIS system implementations. BibRef

Cheong, H.Y.[Hye-Yeon], Ortega, A.[Antonio],
Quantization based nearest-neighbor-preserving metric approximation,
ICIP09(1589-1592).
IEEE DOI Link 0911
BibRef

O'Regan, D.[Deirdre], Kokaram, A.[Anil],
Implicit spatial inference with sparse local features,
ICIP08(2388-2391).
IEEE DOI Link 0810
BibRef

Mallenby, D.[David], Bennett, B.[Brandon],
Applying Spatial Reasoning to Topographical Data with a Grounded Geographical Ontology,
GS07(210-227).
Springer DOI Link 0711
BibRef

Gill, D.[Daniel], Ninio, Y.[Yaniv],
Learning Shape Metric: From Alignment to Recognition,
Faces08(xx-yy). 0810
BibRef

Gill, D.[Daniel], Ritov, Y.[Ya'acov], Dror, G.[Gideon],
Is Pinocchio's Nose Long or His Head Small? Learning Shape Distances for Classification,
ISVC07(I: 652-661).
Springer DOI Link 0711
BibRef