A Quantitative Calculation Method of Spatial Direction Similarity Based on Direction Relation Matrix

doi:10.11947/j.AGCS.2015.20140198

Acta Geodaetica et Cartographica Sinica ›› 2015, Vol. 44 ›› Issue (7): 813-821.doi: 10.11947/j.AGCS.2015.20140198

Previous Articles Next Articles

A Quantitative Calculation Method of Spatial Direction Similarity Based on Direction Relation Matrix

CHEN Zhanlong^1,2, ZHOU Lin¹, GONG Xi¹, WU Liang¹

1. Department of Information Engineering, China University of Geosciences, Wuhan 430074, China;
2. State Key Laboratory of Geography Information Engineering, Xi'an 710054, China

Received:2014-04-23 Revised:2015-03-19 Published:2015-07-28
Supported by:
The National Natural Science Foundation of China (No. 41401443);The National Key Technology Research and Development Program of the Ministry of Science and Technology of China (No. 2011BAH06B04);Open Research Fund of State Key Laboratory of Geography Information Engineering(No.SKLGIE2013-Z-4-1);Open Research Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing (No. 13I02);Research Funds for the Central Universities Basic Special Projects (No.CUGL130260)

Abstract

Abstract:

This article introduces a new model for direction relations between spatial objects at multiple scales and a corresponding similarity assessment method. The model is an improvement of direction relation matrix, which quantitatively models direction relations on object scale, and by means of the solution of the Transportation Problem to solve the minimum conversion cost between direction matrices, namely distance between a pair of matrices, thus quantified the difference between a pair of directions, finally obtain the similarity values between arbitrary pairs of spatial objects and compare the results. Experiments on calculating similarity between objects at different scales show that the presented method is efficient, accurate, and capable of obtaining results consistent with human cognition.

Key words: multi-scales, spatial objects, direction similarity, direction relation matrix, neighborhood graph

CLC Number:

P208

CHEN Zhanlong, ZHOU Lin, GONG Xi, WU Liang. A Quantitative Calculation Method of Spatial Direction Similarity Based on Direction Relation Matrix[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(7): 813-821.

References

[1] HOLT A, BENWELL G L. Using Spatial Similarity for Exploratory Spatial Data Analysis: Some Directions[C]//Proceedings of the 2nd International Conference on GeoComputation. Otago, New Zealand: SIRC, 1997.
[2] YAN Haowen, CHU Yandong. On the Fundamental Issues of Spatial Similarity Relations in Multi-scale Maps[J]. Geography and Geo-Information Science, 2009, 25(4): 42-48. (闫浩文, 褚衍东. 多尺度地图空间相似关系基本问题研究[J]. 地理与地理信息科学, 2009, 25(4): 42-48.)
[3] HAAR R. Computational Models of Spatial Relations[R]. Technical Report: TR-478, MSC-72-03610, Computer Science. College Park,MD: University of Maryland,1976.
[4] ALLEN J F. Maintaining Knowledge about Temporal Intervals[J]. Communications of the ACM, 1983, 26(11): 832-843.
[5] GUESGEN H W. Spatial Reasoning Based on Allen's Temporal Logic[R]. Technical Report: TR-89-049. Berkley, CA:International Computer Science Institute, 1989.
[6] BALBIANI P, CONDOTTA J F, DEL CERRO L F. A New Tractable Subclass of the Rectangle Algebra[C]// Proceedings of the 16th International Joint Conference on Artifical Intelligence. San Francisco: Morgan Kaufmann Publishers Inc., 1999: 442-447.
[7] BALBIANI P, CONDOTTA J F, DEL CERRO L F. A Model for Reasoning about Bidimensional Temporal Relations[C]// Proceedings of Principles of Knowledge Representation and Reasoning (KR). Trento: [s.n.], 1998: 124-130.
[8] CHANG S K, SHI Q Y, YAN C W. Iconic Indexing by 2-D Strings[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987, 9(3): 413-428.
[9] PAPADIAS D, SELLIS T, THEODORIDIS Y, et al. Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees[C]//Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1995: 92-103.
[10] GOYAL R K. Similarity Assessment for Cardinal Directions between Extended Spatial Objects[D]. Maine: The University of Maine, 2000.
[11] GOYAL R K, EGENHOFER M J. Similarity of Cardinal Directions[M]// JENSEN C S, SCHNEIDER M, SEEGER B, et al. Advances in Spatial and Temporal Databases, Lecture Notes in Computer Science Volume 2121. Berlin, Heidelberg: Springer, 2001: 36-55.
[12] SKIADOPOULOS S, KOUBARAKIS M. Composing Cardinal Direction Relations[J]. Artificial Intelligence, 2004, 152(2): 143-171.
[13] DING Hong. A Study on Spatial Similarity Theory and Calculation Model[D]. Wuhan: Wuhan University, 2004. (丁虹. 空间相似性理论与计算模型的研究[D]. 武汉: 武汉大学, 2004.)
[14] GUO Qingsheng, DING Hong. Similarity for Spatial Directions between Areal Objects in Raster Data[J]. Geomatics and Information Science of Wuhan University, 2004, 29(5): 447-450. (郭庆胜, 丁虹. 基于栅格数据的面状目标空间方向相似性研究[J]. 武汉大学学报:信息科学版, 2004, 29(5): 447-450.)
[15] AN Xiaoya. Research on Theory, Methods and Applications of Geometry Similarity Measurement for Spatial Data[D]. Zhengzhou: Information Engineering University, 2011. (安晓亚. 空间数据几何相似性度量理论方法与应用研究[D]. 郑州: 信息工程大学, 2011.)
[16] GUO Li, CUI Tiejun, ZHENG Haiying, et al. Arithmetic for Area Vector Spatial Data Matching on Spatial Direction Similarity[J]. Journal of Geomatics Science and Technology, 2008, 25(5): 380-382. (郭黎, 崔铁军, 郑海鹰, 等. 基于空间方向相似性的面状矢量空间数据匹配算法[J]. 测绘科学技术学报, 2008, 25(5): 380-382.)
[17] YAN Haowen, GUO Renzhong. Research on Formal Description Model of Directional Relationships[J]. Acta Geodaetica et Cartographica Sinica, 2003, 32(1): 42-46. (闫浩文, 郭仁忠. 空间方向关系形式化描述模型研究[J]. 测绘学报, 2003, 32(1): 42-46.)
[18] DU Shihong, WANG Qiao, YANG Yipeng. A Qualitative Description Model of Detailed Direction Relations[J]. Journal of Image and Graphics, 2004, 9(12): 1496-1503. (杜世宏, 王桥, 杨一鹏. 一种定性细节方向关系的表达模型[J]. 中国图象图形学报, 2004, 9(12): 1496-1503.)
[19] DU Shihong, WANG Qiao, YANG Yipeng, et al. Fuzzy Description of Spatial Direction Relations[J]. Journal of Computer-aided Design & Computer Graphics, 2005, 17(8): 1744-1751. (杜世宏, 王桥, 杨一鹏, 等. 空间方向关系模糊描述[J]. 计算机辅助设计与图形学报, 2005, 17(8): 1744-1751.)
[20] DU Shihong, WANG Qiao, WEI Bin, et al. Spatial Orientational Relations Rough Reasoning[J]. Acta Geodaetica et Cartographica Sinica, 2003, 32(4): 334-338. (杜世宏, 王桥, 魏斌, 等. 空间方向关系粗糙推理[J]. 测绘学报, 2003, 32(4): 334-338.)
[21] CAO Han, CHEN Jun, DU Daosheng. Qualitative Extention Description for Cardinal Directions of Spatial Objects[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(2): 162-167. (曹菡, 陈军, 杜道生. 空间目标方向关系的定性扩展描述[J]. 测绘学报, 2001, 30(2): 162-167.)
[22] HE Jianhua, LIU Yaolin. An Integrated Model for Topology & Direction Relation Reasoning[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(2): 156-162. (何建华, 刘耀林. GIS中拓扑和方向关系推理模型[J]. 测绘学报, 2004, 33(2): 156-162.)
[23] WU Jing, CHENG Penggen, CHEN Fei, et al. Qualitative Reasoning for Direction Relation of Spatial Objects[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(2): 160-165. (吴静, 程朋根, 陈斐, 等. 空间目标的方向关系定性推理[J]. 测绘学报, 2006, 35(2): 160-165.)
[24] STRAYER J K. Linear Programming and Its Applications[M]. New York: Springer-Verlag.

A Quantitative Calculation Method of Spatial Direction Similarity Based on Direction Relation Matrix

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

Comments

[1]	DENG Min, CHEN Kaiqi, SHI Yan, CHEN Yuanfang, GUO Yiwen. Point process decomposition method for multi-scale spatial co-location pattern mining [J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(2): 258-268.
[2]	GONG Xi, XIE Zhong, ZHOU Lin, HE Zhanjun. A two-tuple model based spatial direction similarity measurement method [J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(12): 1705-1716.
[3]	GUO Qingsheng, XIE Yuwu, LIU Jiping, WANG Lin, ZHOU Lin. Algorithms for Road Networks Matching Considering Scale Variation and Data Update [J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(3): 381-388.
[4]	CHEN Zhanlong, GONG Xi, WU Liang, AN Xiaoya. A Quantitative Calculation Method of Composite Spatial Direction Similarity Concerning Scale Differences [J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(3): 362-371.