收稿日期： ２０１０唱０９唱１５； 修回日期： ２０１０唱１０唱２５ 基金项目： 校级青年自然科学基金资助项目（２００９ＱＮ１７）
作者简介：高向军（１９７５唱） ，男，副教授，博士，主要研究方向为医学图像处理与模式识 别（ ｘｊｇａｏ７５＠１６３．ｃｏｍ） ；杨克领（１９７１唱） ，男，实验师， 主
要研究方向为现代信息检索技术．
虚 拟 内 窥 镜 的 路 径 规 划 算 法 研 究
倡
高向军， 杨克领
（商丘师范学院 计算机科学系， 河南 商丘 ４７６０００）
摘 要： 路径规划算法是虚拟内窥镜系统的关键技术之一，以分类的形式对虚拟内窥镜的路径规划算法进行了
综述性研究。 简要介绍了路径规划算法的研究内容及分类，重点分析了中心路径规划算法的性能和特点，并讨
论了相关的改进算法。 通过对各种路径规划算法的性能比较和特点总结，概括出虚拟内窥镜中路径规划算法的
研究重点和思路。
关键词： 虚拟内窥镜； 路径规划算法； 中心路径规划
中图分类号： ＴＰ３９１畅４ 文献标志码： Ａ 文章编号： １００１唱３６９５（２０１１）０３唱０８２３唱０５
ｄｏｉ：１０．３９６９ ／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．０３．００６
Ｓｔｕｄｙ ｏｆ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｖｉｒｔｕａｌ ｅｎｄｏｓｃｏｐｙ
ＧＡＯ Ｘｉａｎｇ唱ｊｕｎ， ＹＡＮＧ Ｋｅ唱ｌｉｎｇ
（ Ｄｅｐｔ．ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｓｈａｎｇｑｉｕ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｈａｎｇｑｉｕ Ｈｅｎａｎ ４７６０００， Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ： Ｔｈｅ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｋｅｙ ｔｅｃｈｎｉｑｕｅｓ ｏｆ ｔｈｅ ｖｉｒｔｕａｌ ｅｎｄｏｓｃｏｐｙ．Ｔｈｉｓ ｐａｐｅｒ ｒｅｖｉｅｗｅｄ ｔｈｅ ｐａｔｈ
ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｖｉｒｔｕａｌ ｅｎｄｏｓｃｏｐｙ ｂｙ ｃａｔｅｇｏｒｙ．Ｉｎｔｒｏｄｕｃｅｄ ｂｒｉｅｆｌｙ ｔｈｅ ｃｏｎｔｅｎｔ ａｎｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｏｆ ｔｈｅ ｐａｔｈ ｐｌａｎｎｉｎｇ
ｍｅｔｈｏｄ．Ｔｈｅｎ ａｎａｌｙｚｅｄ ｄｅｅｐｌｙ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｆｅａｔｕｒｅ ｏｆ ｔｈｅ ｃｅｎｔｅｒｌｉｎｅ ｅｘｔｒａｃｔｉｏｎ ｍｅｔｈｏｄ， ｍｏｒｅｏｖｅｒ， ｄｉｓｃｕｓｓｅｄ ｃｏｒｒｅ唱
ｓｐｏｎｄｉｎｇ ｉｍｐｒｏｖｅｄ ｍｅｔｈｏｄｓ．Ｆｉｎａｌｌｙ， ｂｙ ｃｏｍｐａｒｉｎｇ ａｄｖａｎｔａｇｅｓ ａｎｄ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｖａｒｉｏｕｓ ｍｅｔｈｏｄｓ， ａｎｄ ｓｕｍｍａｒｉｚｉｎｇ ｔｈｅｉｒ
ｆｅａｔｕｒｅｓ， ｔｈｅ ｐａｐｅｒ ｐｏｉｎｔｅｄ ｏｕｔ ｆｕｔｕｒｅ ｒｅｓｅａｒｃｈ ｏｒｉｅｎｔａｔｉｏｎｓ ｏｆ ｔｈｅ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｖｉｒｔｕａｌ ｅｎｄｏｓｃｏｐｙ．
Ｋｅｙ ｗｏｒｄｓ： ｖｉｒｔｕａｌ ｅｎｄｏｓｃｏｐｙ（ＶＥ）； ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ； ｃｅｎｔｅｒｌｉｎｅ ｅｘｔｒａｃｔｉｏｎ ｍｅｔｈｏｄ
虚拟内窥镜（ＶＥ）提供一种非侵入式的无损检查技术，可
多角度、多方位地任意观察，还可检查传统内窥镜无法检查的
区域，所以它在计算机辅助医学教学、手术规划、临床诊断等领
域有着广阔的应用前景
［１］
。 自 １９９３ 年 Ｖｉｎｉｎｇ 等人
［２］
首次提
出虚拟支气管内窥镜以来，虚拟内窥镜技术就成为了信息学科
在医学领域的研究热点。
虚拟内窥镜的实现包括影像数据采集、图像的组织分割、
路径规划、三维重建、实时绘制、导航等关键技术
［３］
。 其中路
径规划是 ＶＥ 实现导航的基础，要想快速准确地进行虚拟内窥
漫游，首先要对视点（ 虚拟相机） 的移动路径进行规划
［４］
。 由
于手工导航非常困难，耗时且易迷失方向，为让使用者如同使
用传统内窥镜那样在器官中漫游，需要预先规划其导航路径，
使视点能够在规划好的路径上行进，获得最佳观察位置进行器
官的内部及表面检查，判断器官的病变情况，并定位病灶区域，
从而使 ＶＥ 起到辅助诊断的作用。 这一过程的技术实现称做
路径规划。 由于检查器官解剖结构的复杂性，决定了路径规划
算法的复杂性，它已成为制约 ＶＥ 走向临床的瓶颈
［５］
。 本文将
以分类的形式总结目前路径规划算法的特点，重点对中心路径
规划算法的性能进行分析，并讨论了相关的改进算法，通过总
结各种算法的特点，指明路径规划算法的研究重点和方向。
１ 路径规划的研究内容及分类
根据导航对路径的要求，路径规划技术的研究内容归纳为
如何在器官内部，快速、准确地规划一条或多条连续、平滑的路
径，使得器官表面的每个体素尽可能地被路径上的点看到。 理
想的路径应该保证每个边界体素至少被一条路径上的点检测
到
［６］
。
根据虚拟内窥镜系统不同的导航方式，路径规划分为：
ａ）手工路径规划，就是操作者通过系统接口，输入每一步
需要的路径参数，控制视点在虚拟器官中，一步步前行。 这是
一个十分耗时的漫游方式，倘若是一个毫无经验的操作者，可
能迷失方向。
ｂ）自动路径规划，就是在漫游之前自动提取出虚拟器官
的整体导航路径。 因此利用自动路径规划技术，可以快速地完
成对虚拟器官的自动漫游，辅助医生快速了解器官的整体结构
及病变情况。 但是在自动路径规划技术下的自动漫游方式，无
法实现系统与操作者的交互功能，不能让操作者对有怀疑的器
官区域做细致的检查。
ｃ）交互式路径规划，它突破了上述两者的不足，实现了系
统与操作者的互动。 交互式路径规划根据操作者指定路径的
起点和终点，实时地提取导航路径，实现实时漫游功能。 为了
满足实时性的要求，交互式路径规划算法的计算量要小，能够
快速提取连接起点和终点的连续、平滑的路径。 这种高性能要
求，使得交互式路径规划技术成为虚拟内窥镜系统的关键技术
及研究热点
。
第 ２８ 卷第 ３ 期
２０１１ 年 ３ 月
计 算 机 应 用 研 究
Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ
Ｖｏｌ．２８ Ｎｏ．３
Ｍａｒ．２０１１
资源评论
