A hybrid SfM method considering scene connectivity

doi:10.11947/j.AGCS.2023.20220448

Abstract

Abstract: SfM method has achieved great success in 3D sparse reconstruction, but it still meets serious challenges in large-scale scene reconstruction. Aiming at solving the problem of loose image distribution, low efficiency of subcluster expansion and weak robustness of subcluster merging in existing hybrid SfM methods, a hybrid SfM method considering scene connectivity isproposed in this paper. Firstly, a multifactor joint scene division algorithm based on normalized cut is proposed, which effectively solves the problem of loose image space distribution in subclusters after scene division; Secondly, a subcluster balanced expansion algorithm considering partition connectivity is proposed to improve the expansion efficiency and connectivity between subclusters; Then, a quality check and secondary reconstruction mechanism in the local reconstruction stage are introduced to eliminate the influence of subclusters with unqualified local reconstruction quality on merging, and a subcluster merging algorithm considering the connectivity between clusters is proposed to implement the robust merging among subclusters. Finally, experimental validation is conducted using multiple open datasets and multi-view datasets, and the results show that the method proposed in this paper is superior to state-of-the-art methods in terms of robustness and efficiency, and has better feasibility and advancement.

Key words: hybrid SfM, connectivity, scene partitioning, subcluster merging

CLC Number:

P227

QU Wenhu, LIU Zhendong, CAI Haolin, ZHANG Shaizhe. A hybrid SfM method considering scene connectivity[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(6): 966-979.

References

[1] JIANG S, JIANG C, JIANG W. 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.
[2] SHANG Y, SUN X, ZHANG Y, et al. Research on 3D target pose tracking and modeling[J]. Journal of Geodesy and Geoinformation Science, 2019(2): 60-69.
[3] AGARWAL S, FURUKAWA Y, SNAVELY N, et al. Building rome in a day[J]. Communications of the ACM, 2011, 54(10): 105-112.
[4] WU Changchang. Towards linear-time incremental structure from motion[C]//Proceedings of 2013 International Conference on 3D Vision-3DV.Seattle:IEEE, 2013: 127-134.
[5] SWEENEY C, HOLLERER T, TURK M. Theia: a fast and scalable structure-from-motion library[C]//Proceedings of the 23rd ACM international conference on Multimedia.Brisbane: ACM Press, 2015: 693-696.
[6] SCHONBERGER J L, FRAHM J M. Structure-from-motion revisited[C]//Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Las Vegas:IEEE, 2016: 4104-4113.
[7] CHAN K H, TANG C Y, HOR M K, et al.Robust trifocal tensor constraints for structure from motion estimation[J]. Pattern Recognition Letters,2013, 34(6): 627-636.
[8] 吴子敬, 邓非. SFM的倾斜航空影像空中三角测量[J]. 测绘科学, 2017, 42(11): 97-101. WU Zijing, DENG Fei. Aerial triangulation of oblique aerial images based on SFM[J]. Science of Surveying and Mapping, 2017, 42(11): 97-101.
[9] 卢俊. 基于无序多视影像的三维重建关键技术研究[D]. 郑州: 信息工程大学,2015. LU Jun. Research on key technologies of 3D reconstruction based on disordered multi-view images[D]. Zhengzhou: Information Engineering University,2015.
[10] 于英, 张永生, 薛武, 等. 一种稳健性增强和精度提升的增量式运动恢复结构方法[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.
[11] CORNELIS K, VERBIEST F, VAN GOOL L. Drift detection and removal for sequential structure from motion algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(10): 1249-1259.
[12] TRIGGS B, MCLAUCHLAN P F, HARTLEY R I, et al. Bundle adjustment:a modern synthesis[C]//Proceedings of 1999 International Workshop on Vision Algorithms: Theory and Practice. New York: ACM, 1999: 298-372.
[13] ÖZYEŞIL O, SINGER A. Robust camera location estimation by convex programming[C]//Proceedings of 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR).Boston:IEEE, 2015: 2674-2683.
[14] CUI Zhaopeng, TAN Ping. Global structure-from-motion by similarity averaging[C]//Proceedings of 2015 IEEE International Conference on Computer Vision (ICCV). Santiago:IEEE, 2016: 864-872.
[15] SWEENEY C, SATTLER T, HOLLERER T, et al. Optimizing the viewing graph for structure-from-motion[C]//Proceedings of 2015 IEEE International Conference on Computer Vision (ICCV).Santiago:IEEE, 2015.
[16] WANG Xin, XIAO Teng, GRUBER M, et al. Robustifying relative orientations with respect to repetitive structures and very short baselines for global SfM[C]//Proceedings of 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW).Long Beach:IEEE, 2019.
[17] WANG X, XIAO T, KASTEN Y. A hybrid global structure from motion method for synchronously estimating global rotations and global translations[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2021, 174: 35-55.
[18] 何海清, 陈敏, 陈婷, 等. 低空影像SfM三维重建的耦合单-多旋转平均迭代优化法[J]. 测绘学报,2019,48(6):688-697. DOI: 10.11947/j.AGCS.2019.20180063. HE Haiqing, CHEN Min, CHEN Ting, et al. Single and multiple rotation averaging iterative optimization coupled 3D reconstruction for low-altitude images using SfM algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(6): 688-697. DOI: 10.11947/j.AGCS.2019.20180063.
[19] CRANDALL D J, OWENS A, SNAVELY N, et al. SfM with MRFs: discrete-continuous optimization for large-scale structure from motion[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(12): 2841-2853.
[20] WILSON K, BINDEL D, SNAVELY N. When is rotations averaging hard?[C]//Proceedings of 2016 European Conference on Computer Vision.Amsterdam:Springer, 2016.
[21] FARENZENA M, FUSIELLO A, GHERARDI R.Structure-and-motion pipeline on a hierarchical cluster tree[C]//Proceedings of 2009 IEEE 12th International Conference on Computer Vision Workshops(ICCV). Kyoto:IEEE, 2010: 1489-1496.
[22] GHERARDI R, FARENZENA M, FUSIELLO A. Improving the efficiency of hierarchical structure-and-motion[C]//Proceedings of 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Francisco:IEEE, 2010: 1594-1600.
[23] CUI Hainan, GAO Xiang, SHEN Shuhan, et al. HSfM: hybrid structure-from-motion[C]//Proceedings of 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR).Honolulu:IEEE, 2017: 2393-2402.
[24] ZHU Siyu, ZHANG Runze, ZHOU Lei, et al. Very large-scale global SfM by distributed motion averaging[C]//Proceedings of 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition.Salt Lake City:IEEE, 2018: 4568-4577.
[25] XIE Xiuchuan, YANG Tao, LI Dongdong, et al. Hierarchical clustering-aligning framework based fast large-scale 3D reconstruction using aerial imagery[J]. Remote Sensing, 2019, 11(3): 315.
[26] 许彪, 董友强, 张力, 等. 分区优化混合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.
[27] 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.
[28] TOLDO R, GHERARDI R, FARENZENA M, et al. Hierarchical structure-and-motion recovery from uncalibrated images[J]. Computer Vision and Image Understanding, 2015, 140: 127-143.
[29] NI Kai, DELLAERT F. HyperSfM[C]//Proceedings of the 2nd International Conference on 3D Imaging, Modeling, Processing, Visualization & Transmission.Zurich: IEEE, 2012: 144-151.
[30] LU Luping, ZHANG Yong, LIU Kai. Block partitioning and merging for processing large-scale structure from motion problems in distributed manner[J]. IEEE Access, 2019, 7: 114400-114413.
[31] BHOWMICK B, PATRA S, CHATTERJEE A, et al.Divide and conquer: efficient large-scale structure from motion using graph partitioning[C]//Proceedings of 2014 Asian Conference on Computer Vision.Cham: Springer,2014.
[32] SWEENEY C, FRAGOSO V, HÖLLERER T, et al. Large scale SfM with the distributed camera model[C]//Proceedings of 2016 Fourth International Conference on 3D Vision (3DV). Stanford: IEEE, 2016: 230-238.
[33] ZHU Siyu, SHEN Tianwei, ZHOU Lei, et al. Parallel structure from motion from local increment to global averaging[EB/OL].[2023-01-20].https://arxiv.org/pdf/1702.08601.
[34] CHEN Y, SHEN S, CHEN Y, et al. Graph-based parallel large scale structure from motion [J]. Pattern Recognition, 2020, 107: 107537.
[35] SHI Jianbo, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.
[36] CHATTERJEE A, GOVINDU V M. Efficient and robust large-scale rotation averaging[C]//Proceedings of 2013 IEEE International Conference on Computer Vision. Sydney:IEEE, 2014: 521-528.
[37] MOULON P, MONASSE P, MARLET R. Global fusion of relative motions for robust, accurate and scalable structure from motion[C]//Proceedings of 2013 IEEE International Conference on Computer Vision. Sydney: IEEE, 2014.
[38] 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.