Feature Line Extraction from 3D Model of Oblique Photogrammetry Based on Multi-Objective Weighted Shortest Path
-
摘要: 针对倾斜摄影测量三维重建得到的三维模型在地物拐角棱线处结构粗糙、噪声较大、规则性缺失，难以快速准确提取出理想特征线的难题，提出一种基于多目标加权最短路径的特征线提取方法. 首先对模型进行预处理，使模型具有完整、连续的拓扑结构，并将模型以有向图结构进行组织；其次顾及距离、方向和三角网变化趋势计算权重，约束迪杰斯特拉算法获取最短路径得到特征线；最后，为了修复模型特征不明显的棱线区域，设计了一种棱线修复算法. 研究结果表明：与交互式方法对比，本文方法效率高，只需选取两个特征点指定目标，同时提取结果不依赖人工经验，客观性强；与基于边和面的自动提取方法相比，本文方法受噪声影响小，能在简单交互下提取到指定特征线.Abstract: Oblique photogrammetry 3D models suffer from coarse structure, high noise and regularity deficiency in corner or ridge regions, which make it difficult to extract feature lines quickly and accurately from these regions. To deal with this problem, a method of feature line extraction from 3D model of photogrammetry based on multi-objective weighted shortest path is proposed. First, the model is pre-processed to build a complete and continuous topological structure, and organized as a weighted directed graph. Then, considering the distance, direction and the change trend of the triangulation, the weights are calculated; the Dijkstra algorithm is constrained to obtain the shortest path to get the feature lines. Finally, using the feature line extraction results, a method is proposed to repair the regions without distinct features. Results show that compared with the interactive method, the proposed method is efficient and only need select two feature points to specify the target. At the same time, the extraction results do not rely on artificial experience and are highly objective. Compared with the automatic extraction method based on edges and faces, this method is less affected by noise, and can extract the specified feature line under simple interaction.
-
Key words:
- 3D model /
- photogrammetry /
- feature extraction /
- directed graphs /
- shortest path
-
图 1 基于多目标加权最短路径的倾斜摄影测量三维模型特征线提取算法流程
Figure 1. Flow of feature line extraction from 3D model of oblique photogrammetry based on multi-objective weighted shortest path
-
李德仁,邵振峰,杨小敏. 从数字城市到智慧城市的理论与实践[J]. 地理空间信息,2011,9(6): 1-5.LI Deren, SHAO Zhenfeng, YANG Xiaomin. Theory and practice from digital city to smart city[J]. Geospatial Information, 2011, 9(6): 1-5. 朱庆. 三维GIS及其在智慧城市中的应用[J]. 地球信息科学学报,2014,16(2): 151-157.ZHU Qing. Full three-dimensional GIS and its key roles in smart city[J]. Journal of Geo-information Science, 2014, 16(2): 151-157. GUO X, XIAO J, WANG Y. A survey on algorithms of hole filling in 3D surface reconstruction[J]. The Visual Computer, 2018, 34(1): 93-103. doi: 10.1007/s00371-016-1316-y PHAN T. A triangle mesh-based corner detection algorithm for catadioptric images[J]. Imaging Science Journal, 2017(5): 1-11. 王钦瑞,张应中,罗晓芳. 综合平均曲率与网格边的特征线提取方法[J]. 计算机应用与软件,2017,34(1): 236-240.WANG Qingrui, ZHANG Yingzhong, LUO Xiaofang. A feature line extraction method combining mean curvature with mesh edges[J]. Computer Applications and Software, 2017, 34(1): 236-240. 胡事民,杨永亮,来煜坤. 数字几何处理研究进展[J]. 计算机学报,2009,32(8): 1451-1469.HU Shimin, YANG Yongliang, LAI Yikun. Research progress of digital geometry processing[J]. Chinese Journal of Computers, 2009, 32(8): 1451-1469. BOROUCHAKI H, VILLARD J, LAUG P, et al. Surface mesh enhancement with geometric singularities identification[J]. Computer Methods in Applied Mechanics & Engineering, 2005, 194(48/49): 4885-4894. TSUCHIE S, HIGASHI M. Extraction of surface-feature lines on meshes using normal tensor framework[J]. Computer-Aided Design and Applications, 2014, 2(11): 172-181. SHAH S, BENNAMOUN M, BOUSSAID F, et al. Evolutionary feature learning for 3-D object recognition[J]. Browse Journals & Magazines, 2017, 99: 2434-2444. OHTAKE Y, BELYAEV A, SEIDEL H P. Ridge-valley lines on meshes via implicit surface fitting[J]. ACM Transactions on Graphics, 2004, 23(3): 609-612. KESSENICH J, SELLERS G, SHREINER D. OpenGL programming guide[M]. 9th Edition. Boston: Addison-Wesley, 2016: 108-151. 戴宁,廖和文,陈春美. STL数据快速拓扑重建关键算法[J]. 计算机辅助设计与图形学学报,2005,17(11): 2447-2452.DAI Ning, LIAO Hewen, CHEN Chunmei. Efficient algorithm of topological reconstruction for STL data[J]. Journal of Computer-Aided Design and Computer Graphics, 2005, 17(11): 2447-2452. DEROSE T. Subdivision exterior calculus for geometry processing[J]. ACM Transactions on GRAPHICS, 2016, 35(4): 133. JAIMEZ M, CASHMAN T, FITZGIBBON A, et al. An efficient background term for 3D reconstruction and tracking with smooth surface models[C]//IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Hawaii: IEEE, 2017: 7177-7185. MADKOUR A, AREF W, REHMAN F, et al. A survey of shortest-path algorithms[J]. Data Structures and Algorithms, 2017, 5: 1705-2044. GUO Y W, PENG Q S, HU G F. Smooth feature line detection for meshes[J]. Journal of Zhejiang University, 2005, 6(5): 460-468. doi: 10.1631/jzus.2005.A0460 WOOD J. The geomorphological characterisation of digital elevation models[J]. Dissertations & Theses - Gradworks, 1996, 4(13): 834-848. STYLIANOU G, FARIN G. Crest lines for surface segmentation and flattening[J]. IEEE Transactions on Visualization and Computer Graphics, 2004, 10(5): 536-544. doi: 10.1109/TVCG.2004.24 WØHLK S, LAPORTE G. Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs[J]. Computers & Operations Research, 2017, 87: 107-113. DEO N. Graph theory with applications to engineering and computer science[M]. New York: Courier Dover Publications, 2017: 482-490. 陆锋. 最短路径算法:分类体系与研究进展[J]. 测绘学报,2001(3): 269-275.LU Feng. Shortest path algorithms:taxonomy and advance in research[J]. Acta Geodaetica et Cartographica Sinica, 2001(3): 269-275. FRÉDÉRIC C, MARC P. Topology driven algorithms for ridge extraction on meshes [EB/OL]. （2006-5-19）[2018-2-14]. https://hal.univ-lille3.fr/INRIA-RRRT/inria-00070481 YOSHIZAWA S, BELYAEV A, YOKOTA H, et al. Fast,robust,and faithful methods for detecting crest lines on meshes[J]. Computer Aided Geometric Design, 2008, 25(8): 545-560. -
下载:
点击查看大图
图(9)
计量
- 文章访问数: 618
- HTML全文浏览量: 262
- PDF下载量: 21
- 被引次数: 0