Parallel SfM-based 3D reconstruction for unordered UAV images

doi:10.11947/j.AGCS.2024.20230335

Abstract

Abstract:

Efficient incremental structure from motion (ISfM) has become the core technique for (unmanned aerial vehicle, UAV) image orientation. However, the characteristics of large volume, high overlap, and high resolution cause the deficiency in match pair retrieval and the accumulated error and low efficiency in bundle adjustment (BA) optimization, which degenerate its performance for large-scale scenes. This study proposes a parallel SfM for UAV images via global descriptors and graph-based indexing. On the one hand, to cope with the deficiency caused by a large number of local descriptors and the large size of a codebook, an efficient match pair retrieval is designed via the global descriptor and graph-based indexing, which could dramatically accelerate feature matching; on the other hand, to address the deficiency of correspondence searching and low accuracy of transformation estimation in parallel SfM, this study designs an efficient cluster merging algorithm based on the on-demand correspondence graph and bi-directional reprojection error, which achieves efficient and accurate parallel SfM. The proposed algorithm is verified by using three UAV datasets, and the experimental results demonstrate that the proposed method can increase match pair retrieval with speedup ratios ranging from 36 to 108, and dramatically improves the SfM efficiency with the speedup ratio better than 30 and with the comparative accuracy. The accuracy of relative and absolute orientation is comparative to that of traditional methods.

Key words: digital photogrammetry, UAV remote sensing, structure from motion, image retrieval

CLC Number:

P231

San JIANG, Yichen MA, Qingquan LI, Wanshou JIANG, Bingxuan GUO, Lizhe WANG. Parallel SfM-based 3D reconstruction for unordered UAV images[J]. Acta Geodaetica et Cartographica Sinica, 2024, 53(5): 946-958.

Figures/Tables 21

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Tab. 1

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Tab. 2

Fig. 12

Fig. 13

Tab. 3

Fig. 14

Tab. 4

Fig. 15

Tab. 5

Fig. 16

References 28

[1]	JIANG San, JIANG Wanshou, WANG Lizhe. Unmanned aerial vehicle-based photogrammetric 3D mapping: a survey of techniques, applications, and challenges[J]. IEEE Geoscience and Remote Sensing Magazine, 2022, 10(2): 135-171.
[2]	LI Qingquan, HUANG Hui, YU Wenshuai, et al. Optimized views photogrammetry: precision analysis and a large-scale case study in Qingdao[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2023, 16: 1144-1159.
[3]	李清泉, 黄惠, 姜三, 等. 优视摄影测量方法及精度分析[J]. 测绘学报, 2022, 51(6): 996-1007.DOI: 10.11947/j.AGCS.2022.20210685.
	LI Qingquan, HUANG Hui, JIANG San, et al. Optimized views photogrammetry and its precision analysis[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(6): 996-1007.DOI: 10.11947/j.AGCS.2022.20210685.
[4]	MURTIYOSO A, GRUSSENMEYER P. Documentation of heritage buildings using close-range UAV images: dense matching issues, comparison and case studies[J]. The Photogrammetric Record, 2017, 32(159): 206-229.
[5]	JIANG San, JIANG Wanshou, HUANG Wei, et al. UAV-based oblique photogrammetry for outdoor data acquisition and offsite visual inspection of transmission line[J]. Remote Sensing, 2017, 9(3): 278.
[6]	裴慧坤, 姜三, 林国安, 等. 依托无人机倾斜摄影的电力走廊三维重建[J]. 测绘科学, 2016, 41(12): 292-296.
	PEI Huikun, JIANG San, LIN Guoan, et al. 3D reconstruction of transmission route based on UAV oblique photogrammetry[J]. Science of Surveying and Mapping, 2016, 41(12): 292-296.
[7]	WANG Xuan, XIANG Hanyu, NIU Wenyuan, et al. Oblique photogrammetry supporting procedural tree modeling in urban areas[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2023, 200: 120-137.
[8]	于英, 张永生, 薛武, 等. 一种稳健性增强和精度提升的增量式运动恢复结构方法[J]. 测绘学报, 2019, 48(2): 207-215.DOI: 10.11947/j.AGCS.2019.20170665.
	YU Ying, ZHANG Yongsheng, XUE Wu, et al. A incremental structure from motion method of robustness enhancement and accuracy improvement[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(2): 207-215.DOI: 10.11947/j.AGCS.2019.20170665.
[9]	陈武, 姜三, 李清泉, 等. 无人机影像增量式运动恢复结构研究进展[J]. 武汉大学学报(信息科学版), 2022, 47(10): 1662-1674.
	CHEN Wu, JIANG San, LI Qingquan, et al. Recent research of incremental structure from motion for unmanned aerial vehicle images[J]. Geomatics and Information Science of Wuhan University, 2022, 47(10): 1662-1674.
[10]	ALIAKBARPOUR H, PALANIAPPAN K, SEETHARAMAN G. Fast structure from motion for sequential and wide area motion imagery[C]//Proceedings of 2015 IEEE International Conference on Computer Vision Workshop. Santiago: IEEE, 2015: 1086-1093.
[11]	XU Zhihua, WU Lixin, GERKE M, et al. Skeletal camera network embedded structure-from-motion for 3D scene reconstruction from UAV images[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2016, 121: 113-127.
[12]	JIANG San, JIANG Wanshou. Efficient structure from motion for oblique UAV images based on maximal spanning tree expansion[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017, 132: 140-161.
[13]	JIANG San, JIANG Wanshou. Efficient match pair selection for oblique UAV images based on adaptive vocabulary tree[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2020, 161: 61-75.
[14]	SCHONBERGER J L, FRAHM J M. Structure-from-motion revisited[C]//Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas: IEEE, 2016: 4104-4113.
[15]	WU Changchang, AGARWAL S, CURLESS B, et al. Multicore bundle adjustment[C]//Proceedings of 2011 CVPR. Colorado: IEEE, 2011: 3057-3064.
[16]	SUN Yanbiao, SUN Huabo, YAN Lei, et al. RBA: reduced bundle adjustment for oblique aerial photogrammetry[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2016, 121: 128-142.
[17]	JIANG San, LI Qingquan, JIANG Wanshou, et al. Parallel structure from motion for UAV images via weighted connected dominating set[J]. IEEE Transactions on Geoscience and Remote Sensing, 2022, 60: 1-13.
[18]	张力, 刘玉轩, 孙洋杰, 等. 数字航空摄影三维重建理论与技术发展综述[J]. 测绘学报, 2022, 51(7): 1437-1457.DOI: 10.11947/j.AGCS.2022.20220130.
	ZHANG Li, LIU Yuxuan, SUN Yangjie, et al. A review of developments in the theory and technology of three-dimensional reconstruction in digital aerial photogrammetry[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(7): 1437-1457.DOI: 10.11947/j.AGCS.2022.20220130.
[19]	CHEN Yu, SHEN Shuhan, CHEN Yisong, et al. Graph-based parallel large scale structure from motion[J]. Pattern Recognition, 2020, 107: 107537.
[20]	许彪, 董友强, 张力, 等. 分区优化混合SfM方法[J]. 测绘学报, 2022, 51(1): 115-126.DOI: 10.11947/j.AGCS.2021.20210105.
	XU Biao, DONG Youqiang, ZHANG Li, et al. A hybrid SfM method based on partition optimization[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(1): 115-126.DOI: 10.11947/j.AGCS.2021.20210105.
[21]	屈文虎, 刘振东, 蔡昊琳, 等. 顾及场景连通性的混合式SfM方法[J]. 测绘学报, 2023, 52(6): 966-979.DOI: 10.11947/j.AGCS.2023.20220448.
	QU Wenhu, LIU Zhendong, CAI Haolin, et al. A hybrid SfM method considering scene connectivity[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(6): 966-979. DOI: 10.11947/j.AGCS.2023.20220448.
[22]	JEGOU H, PERRONNIN F, DOUZE M, et al. Aggregating local image descriptors into compact codes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(9): 1704-1716.
[23]	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.
[24]	WU Changchang. Towards linear-time incremental structure from motion[C]//Proceedings of 2013 International Conference on 3D Vision.New York: ACM Press, 2013: 127-134.
[25]	ARAI K, BARAKBAH A R. Hierarchical K-means: an algorithm for centroids initialization for K-means[J]. Reports of the Faculty of Science and Engineering, 2007, 36(1): 25-31.
[26]	SHI Jianbo, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.
[27]	UMEYAMA S. Least-squares estimation of transformation parameters between two point patterns[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(4): 376-380.
[28]	ZHU S, SHEN T, ZHOU L, et al. Parallel structure from motion from local increment to global averaging[EB/OL]. [2023-07-08].https://arxiv.org/pdf/1702.08601.pdf.

项目	数据1	数据2	数据3
飞行高度/m	80	—	90
相机型号	DJI FC6310R	DJI Zenmuse P1	Sony ILCE-7R
相机数量	1	1	5
焦距长度/mm	24	35	35
倾斜角度/(°)	0	—	下视/倾斜：0/45
影像数量	3743	4030	21 654
影像尺寸/像素	5472×3648	8192×5460	6000×4000
地面分辨率/cm	2.6	1.2	1.2
数据存储空间/GB	30	53	462

指标	数据1	数据2	数据3
效率/min	1.2	1.8	9.6
精度/(%)	90.6	89.8	93.5

指标	数据1	数据2	数据3
精度/像素	0.542	0.668	0.752
完整度	928 745 (3724)	1 518 474 (4029)	8 921 339 (21 568)

指标	方法	数据1	数据2	数据3
效率/min	ColMap	1 435.4	4 427.1	—
	BoW	32.9	145.2	1753
	Dbow2	31.1	125.5	1445
	Metashape	50.0	186.0	—
	Pix4Dmapper	298.2	636.4	—
	本文方法	32.5	144.0	1778
精度/像素	ColMap	0.531	0.696	—
	BoW	0.542	0.667	0.766
	Dbow2	0.490	0.645	0.782
	Metashape	0.957	1.140	—
	Pix4Dmapper	0.318	0.327	—
	本文方法	0.542	0.668	0.752
完整度	ColMap	1 034 379(3737)	1 611 067(4029)	—
	BoW	1 001 797(3716)	1 507 983(4029)	9 253 968(21 647)
	Dbow2	925 530(3720)	1 506 702(4027)	9 047 089(21 625)
	Metashape	1 764 717(3741)	1 536 021(4030)	—
	Pix4Dmapper	468 254(3620)	726 366(3909)	—
	本文方法	928 745(3724)	1 518 474(4029)	8 921 339(21 568)

方法	均值			标准差
方法	\|X\|	\|Y\|	\|Z\|	\|X\|	\|Y\|	\|Z\|
BoW	0.066	0.063	0.033	0.059	0.074	0.036
Dbow2	0.048	0.021	0.058	0.081	0.030	0.044
Pix4Dmapper	0.010	0.012	0.015	0.013	0.016	0.019
本文方法	0.023	0.022	0.055	0.029	0.026	0.040