Virtual Navigation Path Planning Based on Octree Potential Field for Endonasal Endoscope

doi:10.16182/j.issn1004731x.joss.22-1441

Abstract

Abstract:

Virtual navigation can intuitively display the internal structure of human tissue from multiple viewpoints. The navigation path planning algorithm is the key to achieving excellent navigation effects. The traditional centerline extraction algorithm can ensure a wide field of view during navigation, but the time efficiency is not high enough on the complex nasal-skull base volume model. To solve the problem, a rapid navigation path planning algorithm based on the octree potential field is proposed. The space outside the obstacles is modeled by an octree, and the octree potential field is constructed by calculating the potential of all the octree nodes. According to the adjacency relationship of the cubes in the octree, the octree adjacency graph is constructed by taking the path integral of the potential field as the edge weight. The A^*algorithm is used to obtain the navigation path with a smaller total weight in the adjacency graph. The experiments are carried out on image data of real patients to test the performance and effect of the algorithm. The experimental results show that the proposed algorithm has higher time efficiency than traditional algorithms and the octree-based accelerated distance transform method. Based on the planned navigation path, the dynamic visualization of the virtual navigation process can be realized by volume rendering, which can provide users with a great nasal-skull base observation effect and help preoperative planning of nasal-skull base surgery.

Key words: navigation path planning, octree, artificial potential field, A* algorithm, volume rendering

CLC Number:

TP301.6

Li Wenjing, Luo Yanlin, Wang Yuhui, Zhu Li. Virtual Navigation Path Planning Based on Octree Potential Field for Endonasal Endoscope[J]. Journal of System Simulation, 2023, 35(9): 2054-2063.

Figures/Tables 10

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Table 2

Table 3

Fig. 5

Fig. 6

Fig. 7

References 21

1	徐驰宇, 朱丽, 骆岩林. 鼻窦和鼻颅底手术解剖的历史与进展[J]. 解剖学报, 2020, 51(5): 732-737.
	Xu Chiyu, Zhu Li, Luo Yanlin. History and Progress of the Paranasal Sinuses and Nasal-skull Based Surgical Anatomy[J]. Acta Anatomica Sinica, 2020, 51(5): 732-737.
2	Spock T, Kessler R, Lerner D, et al. Endoscopic Skull Base Surgery Protocol from the Frontlines: Transnasal Surgery During the COVID-19 Pandemic[J]. Otolaryngology-Head and Neck Surgery, 2020, 163(3): 482-490.
3	Kim D H, Kim Y, Park J S, et al. Virtual Reality Simulators for Endoscopic Sinus and Skull Base Surgery: the Present and Future[J]. Clinical and Experimental Otorhinolaryngology, 2019, 12(1): 12-17.
4	He Yucheng, Zhang Peng, Qi Xiaozhi, et al. Endoscopic Path Planning in Robot-assisted Endoscopic Nasal Surgery[J]. IEEE Access, 2020, 8: 17039-17048.
5	Palágyi Kálmán, Németh Gábor. A Pair of Equivalent Sequential and Fully Parallel 3D Surface-thinning Algorithms[J]. Discrete Applied Mathematics, 2017, 216, Part 2: 348-361.
6	Zhao Fengjun, Sun Feifei, Hou Yuqing, et al. A Monocentric Centerline Extraction Method for Ring-like Blood Vessels[J]. Medical & Biological Engineering & Computing, 2018, 56(4): 695-707.
7	Bitter I, Kaufman A E, Sato M. Penalized-distance Volumetric Skeleton Algorithm[J]. IEEE Transactions on Visualization and Computer Graphics, 2001, 7(3): 195-206.
8	Chaudhuri P, Khandekar R, Sethi D, et al. An Efficient Central Path Algorithm for Virtual Navigation[C]// Proceedings Computer Graphics International. Piscataway, NJ, USA: IEEE, 2004: 188-195.
9	Cao T T, Tang Ke, Mohamed A, et al. Parallel Banding Algorithm to Compute Exact Distance Transform with the GPU[C]//2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. New York, USA: Association for Computing Machinery, 2010: 83-90.
10	Manduhu M, Jones M W. A Work Efficient Parallel Algorithm for Exact Euclidean Distance Transform[J]. IEEE Transactions on Image Processing, 2019, 28(11): 5322-5335.
11	Favaro A, Segato A, Muretti F, et al. An Evolutionary-optimized Surgical Path Planner for a Programmable Bevel-tip Needle[J]. IEEE Transactions on Robotics, 2021, 37(4): 1039-1050.
12	Favaro A, Cerri L, Galvan S, et al. Automatic Optimized 3D Path Planner for Steerable Catheters with Heuristic Search and Uncertainty Tolerance[C]//2018 IEEE International Conference on Robotics and Automation (ICRA). Piscataway, NJ, USA: IEEE, 2018: 9-16.
13	Li Pan, Jiang Shan, Yang Jun, et al. A Combination Method of Artificial Potential Field and Improved Conjugate Gradient for Trajectory Planning for Needle Insertion Into Soft Tissue[J]. Journal of Medical and Biological Engineering, 2014, 34(6): 568-573.
14	Perona P, Malik J. Scale-space and Edge Detection Using Anisotropic Diffusion[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 12(7): 629-639.
15	Chaudhary A, Jhaveri S J, Sanchez A, et al. Cross-platform Ubiquitous Volume Rendering Using Programmable Shaders in VTK for Scientific and Medical Visualization[J]. IEEE Computer Graphics and Applications, 2019, 39(1): 26-43.
16	Zhou Zeyang, Jiang Shan, Yang Zhiyong, et al. Surgical Navigation System for Brachytherapy Based on Mixed Reality Using a Novel Stereo Registration Method[J]. Virtual Reality, 2021, 25(4): 975-984.
17	Magdics M, White D, Marks S. Extending a Virtual Reality Nasal Cavity Education Tool with Volume Rendering[C]//2018 IEEE International Conference on Teaching, Assessment, and Learning for Engineering (TALE). Piscataway, NJ, USA: IEEE, 2018: 811-814.
18	Luo Yanlin, Gao Bin, Deng Yiyi, et al. Automated Brain Extraction and Immersive Exploration of Its Layers in Virtual Reality for the Rhesus Macaque MRI Data Sets[J]. Computer Animation and Virtual Worlds, 2019, 30(1): e1841.
19	张尤赛, 陈福民. 基于纹理映射与Phong光照模型的体绘制加速算法[J]. 中国图象图形学报, 2003, 8(9): 1048-1054.
	Zhang Yousai, Chen Fumin. Accelerated Volume Rendering Using Texture Mapping with Phong Shading[J]. Journal of Image and Graphics, 2003, 8(9): 1048-1054.
20	Khatib O. Real-time Obstacle Avoidance for Manipulators and Mobile Robots[J]. The International Journal of Robotics Research, 1986, 5(1): 90-98.
21	Wan Ming, Liang Zhengrong, Ke Qi, et al. Automatic Centerline Extraction for Virtual Colonoscopy[J]. IEEE Transactions on Medical Imaging, 2002, 21(12): 1450-1460.

患者	DFB	APF	oct-DFB	oct-APF
1	297.75	83.66	10.71	1.46
2	>1 000	>1 000	52.96	28.33

数据	分组	起点	终点
患者1 (256×256×225)	1-1	(0.455,0.075,0.555)	(0.420,0.390,0.580)
	1-2		(0.450,0.235,0.335)
	1-3		(0.530,0.280,0.520)
	1-4		(0.420,0.410,0.470)
	1-5		(0.445,0.310,0.435)
患者2 (512×512×177)	2-1	(0.480,0.120,0.245)	(0.510,0.470,0.410)
	2-2		(0.525,0.240,0.640)
	2-3		(0.650,0.340,0.390)
	2-4		(0.500,0.585,0.490)
	2-5		(0.535,0.295,0.535)

分组	计算时间/s		加速比	路径长度/mm
分组	oct-DFB	oct-APF	加速比	oct-DFB	oct-APF
1-1	11.44	4.75	2.41	100.66	81.81
1-2	23.51	2.65	8.88	75.78	70.23
1-3	11.74	2.12	5.53	58.98	55.45
1-4	20.53	6.19	3.31	91.22	97.67
1-5	14.65	3.27	4.48	69.68	71.15
2-1	53.12	29.33	1.81	91.84	87.10
2-2	58.13	53.82	1.08	106.56	97.89
2-3	741.14	67.08	11.05	108.66	98.19
2-4	>5 000	104.56	>47	150.10	139.61
2-5	56.14	38.88	1.44	83.38	76.57

[1]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[2]	Ni Peilong, Mao Pengjun, Wang Ning, Yang Mengjie. Robot Path Planning Based on Improved A-DDQN Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2420-2430.
[3]	Yu Die, Bao Baizhong, Si Yan, Duan Jian, Zhan Xiaobin, Shi Tielin. Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm [J]. Journal of System Simulation, 2025, 37(4): 1041-1050.
[4]	Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction [J]. Journal of System Simulation, 2025, 37(3): 667-678.
[5]	Li Jiongyi, Li Qiang, Zhang Xinwen, Htet Zin Myo, Cai Yongbin. Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2025, 37(2): 498-507.
[6]	Xing Lijing, Li Min, Zeng Xiangguang, Zhang Ping, Peng Bei. AUV Path Planning Based on Behavior Cloning and Improved DQN in Partially Unknown Environments [J]. Journal of System Simulation, 2025, 37(11): 2754-2767.
[7]	Zhang Chi, Wei Wei. Path Planning for Mobile Robots Based on Improved Artificial Potential Field Algorithm [J]. Journal of System Simulation, 2025, 37(11): 2918-2926.
[8]	Yang Lanying, Li Chao, Zou Haifeng, Wan Jiangtao, Zhang Renqiang, Liu Hui, Lu Hong. Robot Path Planning Optimization Based on Fusion of Improved Ant Colony Algorithm and A* Algorithm [J]. Journal of System Simulation, 2025, 37(11): 2956-2965.
[9]	Xu Jianmin, Song Lei, Deng Dongdong, Chen Yaoruo, Yang Wei. Path Planning of Mobile Robot Based on the Integration of Multi-scale A* and Optimized DWA Algorithm [J]. Journal of System Simulation, 2025, 37(1): 257-270.
[10]	Ji Peng, Zhang Xinyuan, Gao Shuaixuan, Wei Shuorang. Path Planning Based on Improved A* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(9): 2171-2180.
[11]	Lai Rongshen, Dou Lei, Wu Zhiyong, Sun Shuai. Fusion of Improved A* and Dynamic Window Approach for Mobile Robot Path Planning [J]. Journal of System Simulation, 2024, 36(8): 1884-1894.
[12]	Yu Xiang, Deng Qianrui, Duan Sirui, Jiang Chen. A Multi-UAV Collaborative Priority Coverage Search Algorithm [J]. Journal of System Simulation, 2024, 36(4): 991-1000.
[13]	Gui Xueqi, Li Chuntao. UAV Swarm Obstacle Avoidance Algorithm Based on Visual Field and Velocity Guidance [J]. Journal of System Simulation, 2024, 36(3): 545-554.
[14]	Liu Fulin, Li Qingxin. Formation Strategy of Hybrid Obstacle Avoidance Algorithm for Multiple Mobile Robots [J]. Journal of System Simulation, 2024, 36(3): 726-734.
[15]	Yu Xiang, Jiang Chen, Duan Sirui, Deng Qianrui. Path Planning for Improvement of A* Algorithm and Artificial Potential Field Method [J]. Journal of System Simulation, 2024, 36(3): 782-794.