1. Faculty of Geosciences and Environmental Engineering，Southwest Jiaotong University，Chengdu 611756，China; 2. The Key Laboratory of Ministry of Land and Resources，Ministry of Land and Resources, Shenzhen 518034，China; 3. Beijing Advanced Innovation Center for Imaging Technology，Capital Normal University，Beijing 100048，China; 4. Faculty of Construction and Environment，The Hong Kong Polytechnic University，Hongkong 999077，China; 5. Institute of Space and Earth Information Science，The Chinese University of Hongkong，Hongkong 999077，China
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.
李德仁,邵振峰,杨小敏. 从数字城市到智慧城市的理论与实践[J]. 地理空间信息,2011,9(6): 1-5LI Deren, SHAO Zhenfeng, YANG Xiaomin. Theory and practice from digital city to smart city[J]. Geospatial Information, 2011, 9(6): 1-5
[2]
朱庆. 三维GIS及其在智慧城市中的应用[J]. 地球信息科学学报,2014,16(2): 151-157ZHU Qing. Full three-dimensional GIS and its key roles in smart city[J]. Journal of Geo-information Science, 2014, 16(2): 151-157
[3]
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
[4]
PHAN T. A triangle mesh-based corner detection algorithm for catadioptric images[J]. Imaging Science Journal, 2017(5): 1-11
[5]
王钦瑞,张应中,罗晓芳. 综合平均曲率与网格边的特征线提取方法[J]. 计算机应用与软件,2017,34(1): 236-240WANG 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
[6]
胡事民,杨永亮,来煜坤. 数字几何处理研究进展[J]. 计算机学报,2009,32(8): 1451-1469HU Shimin, YANG Yongliang, LAI Yikun. Research progress of digital geometry processing[J]. Chinese Journal of Computers, 2009, 32(8): 1451-1469
[7]
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
[8]
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
[9]
SHAH S, BENNAMOUN M, BOUSSAID F, et al. Evolutionary feature learning for 3-D object recognition[J]. Browse Journals & Magazines, 2017, 99: 2434-2444
[10]
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
[11]
KESSENICH J，SELLERS G，SHREINER D. OpenGL programming guide[M]. 9th Edition. Boston：Addison-Wesley，2016：108-151.
[12]
戴宁,廖和文,陈春美. STL数据快速拓扑重建关键算法[J]. 计算机辅助设计与图形学学报,2005,17(11): 2447-2452DAI 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
[13]
DEROSE T. Subdivision exterior calculus for geometry processing[J]. ACM Transactions on GRAPHICS, 2016, 35(4): 133
[14]
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.
[15]
MADKOUR A, AREF W, REHMAN F, et al. A survey of shortest-path algorithms[J]. Data Structures and Algorithms, 2017, 5: 1705-2044
[16]
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
[17]
WOOD J. The geomorphological characterisation of digital elevation models[J]. Dissertations & Theses - Gradworks, 1996, 4(13): 834-848
[18]
STYLIANOU G, FARIN G. Crest lines for surface segmentation and flattening[J]. IEEE Transactions on Visualization and Computer Graphics, 2004, 10(5): 536-544
[19]
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
[20]
DEO N. Graph theory with applications to engineering and computer science[M]. New York：Courier Dover Publications，2017：482-490.
[21]
陆锋. 最短路径算法:分类体系与研究进展[J]. 测绘学报,2001(3): 269-275LU Feng. Shortest path algorithms:taxonomy and advance in research[J]. Acta Geodaetica et Cartographica Sinica, 2001(3): 269-275
[22]
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
[23]
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
