Shape similarity measurement based on DNA alignment for buildings with multiple orthogonal features

doi:10.11947/j.AGCS.2021.20200227

Abstract

Abstract: Shape similarity between buildings is useful for building matching, classification, retrieval, etc. As buildings tend to be designed with square angles, we proposed a method to measure shape similarity for buildings with multiple orthogonal features based on Needleman-Wunsch (NW) and Smith-Waterman (SW) algorithms. While encoding building shape into a sequence, adjacent two angles are taken as codes. Type, angle and length characteristics of the codes are described, and their similarity are then defined. NW and SW algorithms are applied to compute similarities between two encoding sequences of buildings. Shape-based query experiments show that proposed method in this paper can effectively measure the shape similarity between buildings. And the experimental results are also in line with human visual perception.

Key words: buildings, shape similarity, spatial cognition, sequence analysis

CLC Number:

P208

WEI Zhiwei, GUO Qingsheng, CHENG Lu, LIU Yang, TONG Ying. Shape similarity measurement based on DNA alignment for buildings with multiple orthogonal features[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(12): 1683-1693.

References

[1] VELTKAMP R C. Shape matching:similarity measures and algorithms[C]//Proceedings of 2001 International Conference on Shape Modeling and Applications. Genova, Italy:IEEE, 2001:188-197.
[2] 付仲良,逯跃锋.利用弯曲度半径复函数构建综合面实体相似度模型[J].测绘学报, 2013, 42(1):145-151. FU Zhongliang, LU Yuefeng. Establishment of the comprehensive model for similarity of polygon entity by using bending radius complex function[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(1):145-151.
[3] 晏雄锋,艾廷华,杨敏.居民地要素化简的形状识别与模板匹配方法[J].测绘学报, 2016, 45(7):874-882. DOI:10.11947/j.AGCS.2016.20150162. YAN Xiongfeng, AI Tinghua, YANG Min. A simplification of residential feature by the shape cognition and template matching method[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(7):874-882. DOI:10.11947/j.AGCS.2016.20150162.
[4] 艾廷华,帅赟,李精忠.基于形状相似性识别的空间查询[J].测绘学报, 2009, 38(4):356-362. DOI:10.3321/j.issn:1001-1595.2009.04.012. AI Tinghua, SHUAI Yun, LI Jingzhong. A spatial query based on shape similarity cognition[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(4):356-362. DOI:10.3321/j.issn:1001-1595. 2009. 04. 012.
[5] 安晓亚,刘平芝,金澄,等.手绘地图开域空间方向关系检索法[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.
[6] AI Tinghua, CHENG Xiaoqiang, LIU Pengcheng, et al. A shape analysis and template matching of building features by the Fourier transform method[J]. Computers, Environment and Urban Systems, 2013, 41:219-233.
[7] 王斌.一种基于多级弦长函数的傅立叶形状描述子[J].计算机学报, 2010, 33(12):2387-2396. WANG Bin. A Fourier shape descriptor based on multi-level chord length function[J]. Chinese Journal of Computers, 2010, 33(12):2387-2396.
[8] ZHANG Dengsheng, LU Guojun. A comparative study of curvature scale space and Fourier descriptors for shape-based image retrieval[J]. Journal of Visual Communication and Image Representation, 2003, 14(1):39-57.
[9] ARKIN E M, CHEW L P, HUTTENLOCHER D P, et al. An efficiently computable metric for comparing polygonal shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(3):209-216.
[10] FU Zhongliang, FAN Liang, YU Zhiqiang, et al. A moment-based shape similarity measurement for areal entities in geographical vector data[J]. ISPRS International Journal of Geo-Information, 2018, 7(6):208.
[11] WEI Zhiwei, GUO Qingsheng, WANG Lin, et al. On the spatial distribution of buildings for map generalization[J]. Cartography and Geographic Information Science, 2018, 45(6):539-555.
[12] BAI Xiang, JAN LATECKI L. Path similarity skeleton graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(7):1282-1292.
[13] BELONGIE S, MALIK J, PUZICHA J. Shape matching and object recognition using shape contexts[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(4):509-522.
[14] XU Chunjing, LIU Jianzhuang, TANG Xiaoou. 2D shape matching by contour flexibility[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(1):180-186.
[15] WANG Junwei, BAI Xiang, YOU Xinge, et al. Shape matching and classification using height functions[J]. Pattern Recognition Letters, 2012, 33(2):134-143.
[16] CHEN Longbin, FERIS R, TURK M. Efficient partial shape matching using Smith-Waterman algorithm[C]//Proceedings of 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. Anchorage, AK:IEEE, 2008.
[17] 危辉,李俐瑢.拱序列的曲线描述与匹配[J].中国图象图形学报, 2017, 22(8):1045-1055. WEI Hui, LI Lirong. Curve description and matching using arch sequence[J]. Journal of Image and Graphics, 2017, 22(8):1045-1055.
[18] MOUNT D W. Bioinformatics:sequence and genome analysis[M].2nd ed. New York:Cold Spring Harbor Press, 2004.
[19] 郭庆胜.以直角方式转折的面状要素图形简化方法[J].武汉测绘科技大学学报, 1999, 24(3):255-258. GUO Qingsheng. The method of graphic simplification of area feature boundary as right angle[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1999, 24(3):255-258.
[20] 郭庆胜,黄远林,郑春燕,等.空间推理与渐进式地图综合[M].武汉:武汉大学出版社, 2007. GUO Qingsheng, HUANG Yuanlin, ZHENG Chunyan, et al. Spatial reasoning and progressive map generalization[M]. Wuhan:Wuhan University Press, 2007.
[21] 许文帅,龙毅,周侗,等.基于邻近四点法的建筑物多边形化简[J].测绘学报, 2013, 42(6):929-936. XU Wenshuai, LONG Yi, ZHOU Tong, et al. Simplification of building polygon based on adjacent four-point method[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(6):929-936.
[22] 陈文瀚,龙毅,沈婕,等.利用约束D-TIN进行建筑物多边形凹部结构识别与渐进式化简[J].武汉大学学报(信息科学版), 2011, 36(5):584-587, 592. CHEN Wenhan, LONG Yi, SHEN Jie, et al. Structure recognition and progressive simplification of the concaves of building polygon based on constrained D-Tin[J]. Geomatics and Information Science of Wuhan University, 2011, 36(5):584-587, 592.
[23] SESTER M. Optimization approaches for generalization and data abstraction[J]. International Journal of Geographical Information Science, 2005, 19(8-9):871-897.
[24] 苏为华.多指标综合评价理论与方法问题研究[D].厦门:厦门大学, 2000. SU Weihua. Research on multiple-objective-comprehensive-evaluation[D]. Xiamen:Xiamen University, 2000.
[25] HU Rongxiang, JIA Wei, ZHAO Yang, et al. Perceptually motivated morphological strategies for shape retrieval[J]. Pattern Recognition, 2012, 45(9):3222-3230.
[26] YAN Haowen, WEIBEL R, YANG Bisheng. A multi-parameter approach to automated building grouping and generalization[J]. Geoinformatica, 2008, 12(1):73-89.