A Fast Route Planning Method with 3D Reconstruct Triangular Grid

doi:10.3969/j.issn.1006-2475.2017.11.004

Abstract

Abstract: The 3D environment reconstruction data are often represented with triangular grid, 3D reconstruction data based path planning is a basic work for UAV’s autonomous flight. However, the biggest difficulty in the planning process is the large amount of planning data, the long planning time and the excessive consumption of memory. Based on the triangular grid environment data obtained by 3D reconstruction, this paper proposed a three-dimensional path planning algorithm based on visibility analysis. By experiment, the method based on the visibility analysis was compared with the A * algorithm and particle swarm optimization. The experimental results showed that the proposed algorithm can generate three-dimensional feasible track rapidly in the case of less memory space.

Key words: three-dimensional reconstruction, triangle grid, visibility analysis, fast route planning, A * search

CLC Number:

TP18

MENG Zhao-xu, CAI Chao. A Fast Route Planning Method with 3D Reconstruct Triangular Grid[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.11.004.

References

[1] 陈文山. 基于三角网格模型的心脏超声图像三维表面重建[J]. 福建电脑, 2014(11):20-22.

[2] 卫洪春,刘洋,马丰玺. 三角网格细分法在重建隧道三维结构中的应用[J]. 计算机与信息技术, 2006(10):22-23.

[3] 胡立堂,周爱国. 工程中三角网格等值线的实现与应用[J]. 工程地质计算机应用, 2002(2):14-15.

[4] 王新宇. 基于计算机立体视觉的三维重建[D]. 长沙:中南大学, 2004.

[5] Hartley R, Zisserman A. Multiple View Geometry in Computer Vision[M]. Cambridge University Press, 2003.

[6] Hwang J Y, Kim J S, Lim S S, et al. A fast path planning by path graph optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2003,33(1):121-129.

[7] Gilmore J F, Czuchry A J. A neural network model for route planning constraint integration[C]// Proceedings of the 1992 IEEE International Joint Conference on Neural Networks. 1992,3:221-226.

[8] 孟祥恒,王社伟,陶军. 基于改进蚁群算法的多无人机航路规划研究[J]. 计算机仿真, 2008,25(11):56-59.

[9] Eberhart R, Kennedy J. A new optimizer using particle swarm theory[C]// Proceedings of the 6th International Symposium on Micro Machine and Human Science. 1995:39-43.

[10] 刘莉,于成龙,王祝,等. 小型无人机快速三维航迹规划方法[J]. 系统工程与电子技术, 2013,35(12):2521-2526.

[11] 莫宏伟,马靖雯. 基于蚁群算法的四旋翼航迹规划[J]. 智能系统学报, 2016,11(2):216-225.

[12] Bortoff S. Path planning for UAVs[C]// Proceedings of the 2000 American Control Conference. 2000,1:364-368.

[13] Toussaint G. Shortest path solves edge-to-edge visibility in a polygon[J]. Pattern Recognition Letters, 1986,4(3):165-170.

[14] 李元臣,刘维群. 基于Dijkstra算法的网络最短路径分析[J]. 微计算机应用, 2004,25(3):295-298.

[15] Harmany Z T, Marcia R F, Willett R M. Sparse Poisson intensity reconstruction algorithms[C]// Proceedings of the 15th IEEE/SP Workshop on Statistical Signal Processing. 2009:634-637.

[16] 刘金玲,唐棣. 基于泊松方程实现点云的表面重构[J]. 计算机应用与软件, 2009,26(4):227-228.

[17] 陈寅. 基于泊松方程的浮雕处理技术研究[D]. 长沙:国防科学技术大学, 2010.