Matching pair retrieval method of UAV images based on the graph structure bag of words model

doi:10.13474/j.cnki.11-2246.2023.0110

Abstract

Abstract: Matching pair selection is a key technology to improve feature matching efficiency and 3D reconstruction reliability of UAV images. However, the classical tree index structure word bag model has low efficiency in finding words, low precision in similarity calculation, and high time cost in image retrieval. This study designs the navigation small world (NSW) graph index structure and TF-IDF-Match4 algorithm, and proposes matching pair retrieval method based on the Graph Structure Bag of Words (GSBoW) model. Firstly, the SIFT GPU algorithm is used to extract features of UAV images, which are used to generate visual words through hierarchical K-means clustering. Secondly, visual words are indexed by using a NSW graph index structure, which is achieved by iteratively selecting a random word and inserting it into the NSW graph, and searching its M nearest vertices that are used to build the edge connection. Finally, the NSW graph structure is implemented on GPU for nearest word searching, and match pair selection is achieved by an efficient algorithm, termed TF-IDF-Match4, for the calculation image similarity scores. The experiments are carried out using three large-scale UAV datasets and compared with the bag of words model algorithms in Colmap and DBoW. The results show that the proposed match pair retrieval algorithm can respectively achieve the speed up ratio of 45 and 18 times compared with Colmap and DBoW, which is provided matching pairs for higher accurate 3D reconstruction.

Key words: image retrieval, vocabulary tree, navigation small world, TF-IDF-Match4 weighted, GPU, the nearest neighbor search

CLC Number:

P237

LIU Sikang, GUO Bingxuan, JIANG San, YAN Maosheng. Matching pair retrieval method of UAV images based on the graph structure bag of words model[J]. Bulletin of Surveying and Mapping, 2023, 0(4): 93-98.

References

[1] 李宇昊. 无人机在林业调查中的应用实验[J]. 林业资源管理, 2007(4):69-73.
[2] 王根铎,韩婷娜,郭国明,等. 无人机航空遥感系统在灾害应急救援中的应用探讨[J]. 科技传播,2014,6(14):197,147.
[3] 曲林,冯洋,支玲美,等. 基于无人机倾斜摄影数据的实景三维建模研究[J]. 测绘与空间地理信息,2015,38(3):38-39.
[4] SJA B,CHENG J C,WJD E. Efficient structure from motion for large-scale UAV images:a review and a comparison of SfM tools[J]. ISPRS Journal of Photogrammetry and Remote Sensing,2020,167:230-251.
[5] 姜三,许志海,张峰,等. 面向无人机倾斜影像的高效SfM重建方案[J]. 武汉大学学报(信息科学版),2019,44(8):1153-1161.
[6] DATTA R,JOSHI D,LI Jia,et al. Image retrieval[J]. ACM Computing Surveys,2008,40(2):1-60.
[7] HALAWANI A,TEYNOR A,SETIA L,et al. Fundamentals and applications of image retrieval:an overview[J]. Datenbank-Spektrum,2006,18:14-23.
[8] NISTÉR D,STEWÉNIUS H. Scalable recognition with a vocabulary tree[J]. Proceedings of 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06).[S.l.]:IEEE,2006:2161-2168.
[9] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision,2004,60(2):91-110.
[10] LEPETIE V,LAGGER P,FUA P. Randomized trees for real-time keypoint recognition[C]//Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). San Diego,CA,USA:IEEE,2005.
[11] OBDRZALEK S,MATAS J. Sub-linear indexing for large scale object recognition[C]//Proceedings of the British Machine Vision Conference 2005. Oxford:British Machine Vision Association,2005.
[12] SIVIC J,ZISSERMAN A. Video Google:a text retrieval approach to object matching in videos[C]//Proceedings of the 9th IEEE International Conference on Computer Vision. Nice,France:IEEE,2008:1470-1477.
[13] BRODER A Z. On the resemblance and containment of documents[C]//Proceedings of Compression and Complexity of Sequences 1997. Salerno:IEEE,2002:21-29.
[14] RAM P,GRAY A G. Maximum Inner-Product Search using Tree Data-structures[EB/OL].[2022-03-29]. https://arxiv.org/abs/1202.6101v1.
[15] FU CONG,XIANG CHAO,WANG CHANGXU,et al. Fast approximate nearest neighbor search with the navigating spreading-out graph[EB/OL].[2022-03-29]. https://arxiv.org/abs/1707.00143.
[16] MALKOV Y A,YASHUNIN D A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2020,42(4):824-836.
[17] MALKOV Y,PONOMARENKO A,LOGVINOV A,et al. Approximate nearest neighbor algorithm based on navigable small world graphs[J]. Information Systems,2014,45:61-68.
[18] PONOMARENKO A,MAL Y,KOV,et al. Approximate nearest neighbor search small world approach[C]//Proceedings of the International Conference on Information and Communication Technologies and Applications. Florida:[s.n.],2011.