A two-tuple model based spatial direction similarity measurement method

doi:10.11947/j.AGCS.2021.20200361

Abstract

Abstract: Aiming at problems that in direction relation matrix model, recognition ability for distinguishing direction changes in the same cardinal direction is insufficient, the direction distance references for different cardinal directions are defined incompletely, and the distance calculation between arbitrarily direction relation matrices is not accurate enough, this paper proposes a direction relation two-tuple model, which combines grid-based direction relation matrix and centroid-based direction relation matrix to concern both distribution ratio variations and centroid position variations for objects, thus distinguishing the direction difference in the same cardinal direction. Meanwhile, the traditional neighborhood graph is optimized based on human spatial cognition, and a centroid direction distance reference suitable for arbitrarily direction relationships is established. Finally the Earth mover's distance (EMD) is utilized to further improve the accuracy of distance calculation between direction relation two-tuples. Experiments indicate the method is simple and feasible, the measurement results are more consistent with human cognition, and can be better applied to tasks like cartographic generalization results evaluation.

Key words: spatial direction, similarity measurement, grid-based direction relation matrix, centroid-based direction relation matrix, Earth mover's distance

CLC Number:

P208

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.

References

[1] LI Bonan, FONSECA F. TDD:a comprehensive model for qualitative spatial similarity assessment[J]. Spatial Cognition&Computation, 2006, 6(1):31-62.
[2] 闫浩文,褚衍东.多尺度地图空间相似关系基本问题研究[J].地理与地理信息科学, 2009, 25(4):42-44, 48. 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-44, 48.
[3] NEDAS K A, EGENHOFER M J. Spatial-scene similarity queries[J]. Transactions in GIS, 2008, 12(6):661-681.
[4] BRUNS H T, EGENHOFER M J. Similarity of spatial scenes[C]//Proceedings of the 7th International Symposium on Spatial Data Handling. Delft:Taylor&Francis, 1996:31-42.
[5] GOYAL R K, EGENHOFER M J. Similarity of cardinal directions[C]//Proceedings of the 7th International Symposium on Spatial and Temporal Databases. Berlin:Springer, 2001:36-55.
[6] 陈占龙,吕梦楼,吴亮,等.基于特征矩阵和关联图的空间场景相似性度量方法[J].武汉大学学报(信息科学版), 2017, 42(7):956-962. CHEN Zhanlong, LÜ Menglou, WU Liang, et al. Space scene similarity metrics based on feature matrix and associated graph[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7):956-962.
[7] 安晓亚,刘平芝,金澄,等.手绘地图开域空间方向关系检索法[J].测绘学报, 2017, 46(11):1899-1909. DOI:10.11947/j.AGCS.2017.20170001. AN Xiaoya, LIU Pingzhi, JIN Cheng, et al. A hand-drawn map retrieval method based on open area spatial direction relation[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(11):1899-1909. DOI:10.11947/j.AGCS.2017.20170001.
[8] 田泽宇,门朝光,汤亚楠.基于形状及空间关系的场景相似性检索[J].电子学报, 2016, 44(8):1892-1898. TIAN Zeyu, MEN Chaoguang, YANG Yanan. Spatial-scene similarity retrieval based on shape and spatial relation[J]. Acta Electronica Sinica, 2016, 44(8):1892-1898.
[9] EGENHOFER M J. Spatial-query-by-sketch[C]//Proceedings of 1996 IEEE Symposium on Visual Languages. Boulder, CO:IEEE, 1996:60-67.
[10] EGENHOFER M J. Query processing in spatial-query-by-sketch[J]. Journal of Visual Languages&Computing, 1997, 8(4):403-424.
[11] ZHANG Xiang, AI Tinghua, STOTER J, et al. Data matching of building polygons at multiple map scales improved by contextual information and relaxation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 92:147-163.
[12] 陈占龙,张丁文,谢忠,等.利用多等级相关性反馈进行空间场景匹配[J].武汉大学学报(信息科学版), 2018, 43(9):1422-1428. CHEN Zhanlong, ZHANG Dingwen, XIE Zhong, et al. Spatial scene matching based on multilevel relevance feedback[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9):1422-1428.
[13] XU Yongyang, CHEN Zhanlong, XIE Zhong, et al. Quality assessment of building footprint data using a deep autoencoder network[J]. International Journal of Geographical Information Science, 2017, 31(10):1929-1951.
[14] WANG Min, SONG Tengyi. Remote sensing image retrieval by scene semantic matching[J]. IEEE Transactions on Geoscience and Remote Sensing, 2013, 51(5):2874-2886.
[15] WANG M, WAN Q M, GU L B, et al. Remote-sensing image retrieval by combining image visual and semantic features[J]. International Journal of Remote Sensing, 2013, 34(12):4200-4223.
[16] HAAR R. Computational models of spatial relations[R]. College Park, MD:University of Maryland, 1976.
[17] PAPADIAS D, SELLIS T, THEODORIDIS Y, et al. Topological relations in the world of minimum bounding rectangles:a study with R-trees[J]. ACM SIGMOD Record, 1995, 24(2):92-103.
[18] ALLEN J F. Maintaining knowledge about temporal intervals[J]. Communications of the ACM, 1983, 26(11):832-843.
[19] 曹菡,陈军,杜道生.空间目标方向关系的定性扩展描述[J].测绘学报, 2001, 30(2):162-167. 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.
[20] 杜世宏,王桥,杨一鹏.一种定性细节方向关系的表达模型[J].中国图象图形学报, 2004, 9(12):1496-1503. 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.
[21] GOYAL R K. Similarity assessment for cardinal directions between extended spatial objects[D]. Orono, ME:The University of Maine, 2000.
[22] 李靖涵,巩现勇,武芳,等.一种改进的面目标间方向关系相似性计算模型[J].武汉大学学报(信息科学版), 2016, 41(7):925-931, 951. LI Jinghan, GONG Xianyong, WU Fang, et al. An improved model for calculating the similarity of spatial direction relations between areal objects[J]. Geomatics and Information Science of Wuhan University, 2016, 41(7):925-931, 951.
[23] 郭庆胜,丁虹.基于栅格数据的面状目标空间方向相似性研究[J].武汉大学学报(信息科学版), 2004, 29(5):447-450, 465. 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, 465.
[24] 陈占龙,周林,龚希,等.基于方向关系矩阵的空间方向相似性定量计算方法[J].测绘学报, 2015, 44(7):813-821. DOI:10.11947/j.AGCS.2015.20140198. CHEN Zhanlong, ZHOU Lin, GONG Xi, et al. A quantitative calculation method of spatial direction similarity based on direction relation matrix[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(7):813-821. DOI:10.11947/j.AGCS.2015.20140198.
[25] 陈占龙,龚希,吴亮,等.顾及尺度差异的复合空间对象方向相似度定量计算模型[J].测绘学报, 2016, 45(3):362-371. DOI:10.11947/j.AGCS.2016.20150099. CHEN Zhanlong, GONG Xi, WU Liang, et al. A quantitative calculation method of composite spatial direction similarity concerning scale differences[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(3):362-371. DOI:10.11947/j.AGCS.2016.20150099.
[26] RUBNER Y, TOMASI C, GUIBAS L J. A metric for distributions with applications to image databases[C]//Proceedings of the 6th International Conference on Computer Vision (IEEE Cat. No.98CH36271). Bombay, India:IEEE, 1998:59-66.
[27] STRAYER J K. Linear programming and its applications[M]. New York:Springer, 1989.
[28] HILLIER F S, LIEBERMAN G J, LIBERMAN G. Introduction to mathematical programming[M]. New York:McGraw-Hill Science, 1995.
[29] RUSSELL E J. Letters to the editor:extension of Dantzig's algorithm to finding an initial near-optimal basis for the transportation problem[J]. Operations Research, 1969, 17(1):187-191.
[30] RUBNER Y. Code for the Earth movers distance (EMD)[EB/OL].(1999-01-30)[2020-07-29]. http://ai.stanford.edu/~rubner/emd/default.htm.