基于八叉树势场的鼻内镜虚拟导航路径规划

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

系统仿真学报 ›› 2023, Vol. 35 ›› Issue (9): 2054-2063.doi: 10.16182/j.issn1004731x.joss.22-1441

基于八叉树势场的鼻内镜虚拟导航路径规划

李文静¹(), 骆岩林¹(), 王玉辉², 朱丽²

^1.北京师范大学人工智能学院，北京 100875
^2.北京大学第三医院，北京 100191

收稿日期:2022-11-29 修回日期:2023-03-30 出版日期:2023-09-25 发布日期:2023-09-19
通讯作者: 骆岩林 E-mail:202121081035@mail.bnu.edu.cn;luoyl@bnu.edu.cn
第一作者简介:李文静（1998-），女，硕士生，研究方向为可视化与虚拟现实。E-mail：202121081035@mail.bnu.edu.cn
基金资助:
国家自然科学基金(61977063)

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

Li Wenjing¹(), Luo Yanlin¹(), Wang Yuhui², Zhu Li²

^1.School of Artificial Intelligence, Beijing Normal University, Beijing 100875, China
^2.Peking University Third Hospital, Beijing 100191, China

Received:2022-11-29 Revised:2023-03-30 Online:2023-09-25 Published:2023-09-19
Contact: Luo Yanlin E-mail:202121081035@mail.bnu.edu.cn;luoyl@bnu.edu.cn

摘要/Abstract

摘要：

虚拟导航可从多角度直观展示人体组织内部结构，其中导航路径规划算法是影响导航效果的关键，传统中心路径提取算法能保证导航过程视野开阔，但在复杂鼻-颅底体模型上时间效率不够高。为此提出基于八叉树势场的快速导航路径规划算法。通过八叉树对障碍物外部空间进行建模，计算所有八叉树节点所在位置的势，构建八叉树势场；根据八叉树中正方体的邻接关系，以势场路径积分为边的权重，构建八叉树邻接图；基于A*算法得到邻接图中总权重较小的导航路径。在真实患者影像数据上测试算法性能和效果，实验结果表明，本文算法的时间效率高于传统算法和基于八叉树加速的距离变换法。基于规划的导航路径，通过体绘制实现虚拟导航过程的动态可视化，可为用户提供良好的鼻-颅底观察效果，为鼻-颅底外科手术术前规划提供帮助。

关键词: 导航路径规划, 八叉树, 人工势能场, A*算法, 体绘制

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

中图分类号:

TP301.6

李文静,骆岩林,王玉辉等 . 基于八叉树势场的鼻内镜虚拟导航路径规划[J]. 系统仿真学报, 2023, 35(9): 2054-2063.

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

图/表 10

图1

图2

图3

图4

表1

表2

表3

图5

图6

图7

参考文献 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]	李腾, 丁佩佩, 刘金芳. 货到人拣选系统多阶段可穿行多AGV路径规划[J]. 系统仿真学报, 2022, 34(7): 1512-1523.
[2]	蒙盾, 胡卓, 张华军. 基于改进A^*算法的多层邮轮疏散系统仿真[J]. 系统仿真学报, 2022, 34(6): 1375-1382.
[3]	李颀, 汪伟. 多全向轮协同分拣平台的路径规划[J]. 系统仿真学报, 2021, 33(3): 698-709.
[4]	毕硕本, 贡毓成, 路明月, 周浩, 毛远翔. 气象数据标量场的建模与可视化研究[J]. 系统仿真学报, 2020, 32(7): 1331-1340.
[5]	石敏, 魏育坤, 金相臣, 王素琴, 毛天露. 可支持跃层寻径的虚拟场景漫游方法[J]. 系统仿真学报, 2019, 31(7): 1358-1366.
[6]	赵萍, 雷新宇, 陈波芝, 杨矫云. 基于TI-A*的多机器人动态规划协调方法研究[J]. 系统仿真学报, 2019, 31(5): 925-935.
[7]	罗明, 孙水发, 王骊雯, 董方敏. 基于三维梯度幅值的CT图像体绘制[J]. 系统仿真学报, 2018, 30(7): 2666-2674.
[8]	曾艳阳, 张泽浩, 冯云霞. 自适应可调混沌粒子群算法的体绘制视点选择[J]. 系统仿真学报, 2018, 30(12): 4595-4601.
[9]	曾艳阳, 裴庆庆, 李保锟. 基于自适应复合插值的光线投射算法[J]. 系统仿真学报, 2018, 30(11): 4187-4194.
[10]	周守东. 基于Woodcock Tracking的快速蒙特卡罗直接体绘制方法[J]. 系统仿真学报, 2017, 29(5): 1125-1131.
[11]	蒋秉川, 万刚, 范承啸, 夏青. 战场环境体素模型适应性分析及体要素分类方法研究[J]. 系统仿真学报, 2017, 29(2): 241-247.
[12]	宋汉戈, 刘世光. 三维流场可视化综述[J]. 系统仿真学报, 2016, 28(9): 1929-1936.
[13]	许佳奕, 黄旋旋. 强风暴结构特征的识别与可视辅助分析[J]. 系统仿真学报, 2015, 27(11): 2701-2713.

基于八叉树势场的鼻内镜虚拟导航路径规划

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 21

相关文章 13

编辑推荐

Metrics

本文评价