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]	Wang Man, Li Dapeng, Ding Lianghui, Zhu Tianlin. Formation Obstacle Avoidance Algorithm Based on Joint Virtual Sub-target and Boundary Force [J]. Journal of System Simulation, 2023, 35(9): 1918-1930.
[2]	Junqiang Lin, Hongjun Wang, Xiangjun Zou, Po Zhang, Chengen Li, Yipeng Zhou, Shujie Yao. Obstacle Avoidance Path Planning and Simulation of Mobile Picking Robot Based on DPPO [J]. Journal of System Simulation, 2023, 35(8): 1692-1704.
[3]	Junxiao Xue, Xiangyan Kong, Bowei Dong, Hao Tao, Haiyang Guan, Lei Shi, Mingliang Xu. Obstacle Avoidance and Simulation of Carrier-Based Aircraft on the Deck of Aircraft Carrier [J]. Journal of System Simulation, 2023, 35(3): 592-603.
[4]	Yuchao Zhang, Yuan Jiang, Jiyang Dai. Dynamic Obstacle Avoidance Control of Three-order Multi-robot Cooperative Formation [J]. Journal of System Simulation, 2022, 34(8): 1762-1774.
[5]	Teng Li, Peipei Ding, Jinfang Liu. Multi-Stage Multi-AGV Path Planning with Walk under Shelves for Robotic Mobile Fulfillment Systems [J]. Journal of System Simulation, 2022, 34(7): 1512-1523.
[6]	Dun Meng, Zhuo Hu, Huajun Zhang. Simulation of Multi-layer Ship Evacuation System Based on Improved A* Algorithm [J]. Journal of System Simulation, 2022, 34(6): 1375-1382.
[7]	Guangjian Tian, Jiyang Dai, Jin Ying, Ning Wang. Multi-UAV Trajectory Planning Based on Adaptive Segmented Potential Field Method [J]. Journal of System Simulation, 2022, 34(11): 2368-2376.
[8]	Li Qi, Wang Wei. Path Designing of Multi-omnidirectional Wheel Collaborative Sorting Platform [J]. Journal of System Simulation, 2021, 33(3): 698-709.
[9]	Bi Shuoben, Gong Yucheng, Lu Mingyue, Zhou Hao, Mao Yuanxiang. Modeling and Visualization On Scalar Fields of Meteorological Data [J]. Journal of System Simulation, 2020, 32(7): 1331-1340.
[10]	Chen Haiyun, Chen Huazhou, Liu Qiang. Multi-UAV 3D Formation Path Planning Based on Improved Artificial Potential Field [J]. Journal of System Simulation, 2020, 32(3): 414-420.
[11]	Fu Xiuwen, Yang Yongsheng. Simulation Platform for Invulnerability of Industrial Wireless Sensor Networks [J]. Journal of System Simulation, 2019, 31(7): 1342-1350.
[12]	Shi Min, Wei Yukun, Jin Xiangchen, Wang Suqin, Mao Tianlu. Virtual Scene Roaming Method Supporting Multi-layer Path Planning [J]. Journal of System Simulation, 2019, 31(7): 1358-1366.
[13]	Zhao Ping, Lei Xinyu, Chen Bozhi, Yang Jiaoyun. TI-A* Based Multi-robot Dynamic Planning and Coordination Method [J]. Journal of System Simulation, 2019, 31(5): 925-935.
[14]	Yang Shengqing, Ye Wenyu, He Yubin, Wan Yabin. Satellite Formation Keeping and Its Stability Analysis Based on Artificial Potential Field Method [J]. Journal of System Simulation, 2019, 31(2): 332-339.
[15]	Luo Ming, Sun Shuifa, Wang Liwen, Dong Fangmin. Volume Rendering for CT Images Based on 3D Gradient Amplitude [J]. Journal of System Simulation, 2018, 30(7): 2666-2674.