虚拟内窥镜的可见性分块绘制装置及其方法转让专利
申请号 : CN200410009813.3
文献号 : CN1779718B
文献日 : 2010-11-24
发明人 : 张晓鹏 , 刘剑飞
申请人 : 中国科学院自动化研究所
摘要 :
本发明涉及医学图像处理与科学计算可视化相结合的技术领域，特别是一种虚拟内窥镜的可见性分块绘制装置及其方法。装置包括：输入部分，中间的处理部分，输出部分。方法包括：(1)通过CT、MRI医学成像设备得到一组连续的二维切片；(2)通过图像分割方法提取出用户感兴趣的区域；(3)将分割出来的组织器官以三维网格的形式表示出来；(4)提取出模型的中心线以指导漫游时视点的移动；(5)通过本方法结合模型的中心线和模型的网格数据进行虚拟漫游；(6)将用户看到和浏览的屏幕图像以文件的形式记录下来。可见性分析和分块处理主要是用于虚拟现实、实时绘制和以及医学影像分析中。
权利要求 :
1.一种虚拟内窥镜的可见性分块绘制方法，其特征在于，步骤如下：步骤S1：通过CT、MRI医学成像设备或者网络传输得到一组连续的二维切片，并将这组数据输入到以下处理部分中；
步骤S2：通过图像分割方法从切片中提取出用户感兴趣人体组织器官的区域；
步骤S3：将步骤S2的分割结果进行二值化，提取中心线；
步骤S4：将分割出来的组织器官的切片数据进行三维重建，并以三维网格的形式表示；
步骤S5：通过分块漫游算法对得到的中心线和三维网格进行分块以及可见性计算，并结合提取中心线，对得到的三维网格数据进行可见性分析，得到人体组织器官的可见性信息，以指导漫游时视点的移动；
步骤S6：通过上面的可见性信息，进行实时的漫游，并可以通过键盘和鼠标进行交互；
步骤S7：将用户看到和浏览的屏幕图像以文件的形式记录下来，以备查用，并通过网络发送到远端，以便实时的诊断。
说明书 :
技术领域
本发明涉及医学图像处理与科学计算可视化相结合的技术领域，特别是一种虚拟内窥镜的可见性分块绘制装置及其方法。
背景技术
最近几年，虚拟内窥镜被广泛地应用于人体器官的检查中。结合了医学图像处理和计算机图形学技术，虚拟内窥镜逐渐地取代了传统内窥镜。与传统内窥镜相比，虚拟内窥镜是一种完全无接触式的检查手段，它无需往病人体内插入异物，从而极大地减轻了病人的痛苦，同时还能到达常规内窥镜无法检查的区域，视点方向改变容易，可以使一次检查数据重复使用。
但伴随着医学影像设备的飞速发展，医学图像的分辨率也越来越高。虽然现在的计算机硬件水平也得到了飞速发展，但总也赶不上数据量的增长。具体到我们所研究的虚拟内窥镜，也不可避免的遇到这样的问题，主要表现在其对实时显示所带来的困难。虚拟内窥镜因为在人体内漫游，因此漫游的速度是衡量系统性能的重要指标。一般来说，若计算机每秒能够显示15幅画面，人眼即不会感觉到抖动。但对虚拟内窥镜而言，每秒5幅左右也是可以接受的，因为它是用于医疗检查，医生需要仔细观察，变化太快反而不利，但太慢了又会影响工作效率。例如市场上的商品虚拟内窥镜软件(如GE的Advanced Windows)一般都要两三秒才能显示一幅画面，这就太慢了。事实上这也是虚拟内窥镜软件发展的瓶颈所在，难点也在于此。
为了加快绘制的速度，在虚拟内窥镜中陆续提出了一些典型方法，主要可分为面绘制和体绘制。
1面绘制
通过Marching Cubes方法从数据场中抽取物体表面的几何信息，进而生成观察对象的计算机表示(通常是三角片网格)，面绘制以此为基础进行显示。但伴随着医学影像设备的飞速发展，医学图像的分辨率越来越高，这就使得产生的面片数越来越庞大。如果直接对全部面片数据进行绘制，则漫游达不到实时的要求，这就需要降低面片的绘制量。目前有两种提高面绘制速度的方法：网格化简和可见性分析。
曹勇等将Hoppe的progressive meshes(渐进网格)方法首次应用到虚拟内窥镜中，并根据医学数据的特点，对该方法做了一些应用上的改进。器官的入口处的化简做了严格的限制，防止因为化简破坏了数据原有的拓补性。同时对一些错误的边折叠做了惩罚约束，以使该方法更加适合虚拟漫游。李光明将网格化简和与视点相关的细分结合起来以加快虚拟漫游。根据医学图像的特点，通过改进误差准则的QEM方法对重建后的三维模型进行简化，得到简化的基网格，同时记录下原始网格与基网格的映射关系；然后在绘制时，对视点内的部分进行细分，并根据映射关系调整细分顶点的位置，使其更逼近于原始模型。
虽然通过网格化简可加快漫游的速度，但是图像的质量并不能得到保证。在虚拟内窥镜中，为了使用户能够更快更正确地确定病变体的位置，漫游时的图像质量应该始终放在第一位。在漫游时，因为视点始终与肠壁很近，任何化简以后的数据都会造成图像质量的减低，而这样的化简甚至会造成病变小息肉的消失。由于内窥镜的检查环境是封闭的区域，因此通过分块操作可以建立Portal(入口)和Cell(封闭区域)这样的结构来进行可见性分析。通过肠道的弯曲特性，Hong提出了基于中心线的分块，在漫游时将Portal上的点投影到屏幕坐标上，并通过Z-缓存计算块与块之间的可见性。Knapp加强了中心线分块的操作，解决了在肠道隆起区域的分块。
2体绘制
一些虚拟内窥镜系统采用虚拟摄像机来模拟现实中的摄像机，所以很自然地采用光线投射来进行虚拟摄像机的成像；通过表面检测方法来获取表面点的位置与方向，再通过光照模型就可以得到最终的成像结果。最常用的光照模型是Phone光照模型，它综合考虑了物体表面的吸收、反射和透射三种效应。光线投射法是基于Phone光照模型的。通过该方法，可以直接得到每个检测到的表面点到光学中心(焦点)的距离。所以，除了最终生成的图像之外，还可以获得场景的表面信息和深度信息，这将有利于实现在虚拟内窥镜体数据的漫游。而且光线投射法，在一定条件约束下，照射光线以特定的透视几何形状从显示体积内部发出来，穿过三维图像的体元，生成许多表面视图。通过适当修改方法和透视显示参数，所生成的虚拟表面视图就能够有效地模拟那些用真内窥镜获取的图像。
为了完成虚拟内窥镜体数据的实时真实感绘制，在内窥镜体绘制时可以应用一种体数据动态精简技术。对于内窥镜图像的绘制，仅需对与视点有关的数据进行绘制，需处理的数据仅仅局限于视点附近，体绘制的取景体可定义为一个四棱锥。这样每次绘制仅对此四棱锥中的数据进行透视体绘制。由于四棱锥的数据量在整个数据场总数据量中所占比例非常小，对于每次绘制，四棱锥之外的信息无需考虑，所以很容易实现实时显示。此外，Gobetti等将高性能显卡中的纹理映射技术应用于虚拟内窥镜。但是纹理映射缺乏阴影，使漫游的图像缺乏真实性。此外纹理内存的容量也限制了显示的数据量。József使用光线跟踪方法来判断空的体素以减少绘制时间。Mehran将体数据细分成很多的体素块，通过光线跟踪方法计算这些体素块边界体素之间的可见性，然后将直接体绘制方法用于那些可见的体素块上。
在虚拟内窥镜中，为了使得医生能够更快更正确地确定病变体的位置，漫游时的图像质量应该始终放在第一位。但直接对器官网格模型的所有多边形全部绘制，则漫游达不到实时的要求，这就需要降低绘制模型的多边形量。综合比较以上两种绘制方法，本发明采用可见性分析来降低绘制模型的多边形数量。
但伴随着医学影像设备的飞速发展，医学图像的分辨率也越来越高。虽然现在的计算机硬件水平也得到了飞速发展，但总也赶不上数据量的增长。具体到我们所研究的虚拟内窥镜，也不可避免的遇到这样的问题，主要表现在其对实时显示所带来的困难。虚拟内窥镜因为在人体内漫游，因此漫游的速度是衡量系统性能的重要指标。一般来说，若计算机每秒能够显示15幅画面，人眼即不会感觉到抖动。但对虚拟内窥镜而言，每秒5幅左右也是可以接受的，因为它是用于医疗检查，医生需要仔细观察，变化太快反而不利，但太慢了又会影响工作效率。例如市场上的商品虚拟内窥镜软件(如GE的Advanced Windows)一般都要两三秒才能显示一幅画面，这就太慢了。事实上这也是虚拟内窥镜软件发展的瓶颈所在，难点也在于此。
为了加快绘制的速度，在虚拟内窥镜中陆续提出了一些典型方法，主要可分为面绘制和体绘制。
1面绘制
通过Marching Cubes方法从数据场中抽取物体表面的几何信息，进而生成观察对象的计算机表示(通常是三角片网格)，面绘制以此为基础进行显示。但伴随着医学影像设备的飞速发展，医学图像的分辨率越来越高，这就使得产生的面片数越来越庞大。如果直接对全部面片数据进行绘制，则漫游达不到实时的要求，这就需要降低面片的绘制量。目前有两种提高面绘制速度的方法：网格化简和可见性分析。
曹勇等将Hoppe的progressive meshes(渐进网格)方法首次应用到虚拟内窥镜中，并根据医学数据的特点，对该方法做了一些应用上的改进。器官的入口处的化简做了严格的限制，防止因为化简破坏了数据原有的拓补性。同时对一些错误的边折叠做了惩罚约束，以使该方法更加适合虚拟漫游。李光明将网格化简和与视点相关的细分结合起来以加快虚拟漫游。根据医学图像的特点，通过改进误差准则的QEM方法对重建后的三维模型进行简化，得到简化的基网格，同时记录下原始网格与基网格的映射关系；然后在绘制时，对视点内的部分进行细分，并根据映射关系调整细分顶点的位置，使其更逼近于原始模型。
虽然通过网格化简可加快漫游的速度，但是图像的质量并不能得到保证。在虚拟内窥镜中，为了使用户能够更快更正确地确定病变体的位置，漫游时的图像质量应该始终放在第一位。在漫游时，因为视点始终与肠壁很近，任何化简以后的数据都会造成图像质量的减低，而这样的化简甚至会造成病变小息肉的消失。由于内窥镜的检查环境是封闭的区域，因此通过分块操作可以建立Portal(入口)和Cell(封闭区域)这样的结构来进行可见性分析。通过肠道的弯曲特性，Hong提出了基于中心线的分块，在漫游时将Portal上的点投影到屏幕坐标上，并通过Z-缓存计算块与块之间的可见性。Knapp加强了中心线分块的操作，解决了在肠道隆起区域的分块。
2体绘制
一些虚拟内窥镜系统采用虚拟摄像机来模拟现实中的摄像机，所以很自然地采用光线投射来进行虚拟摄像机的成像；通过表面检测方法来获取表面点的位置与方向，再通过光照模型就可以得到最终的成像结果。最常用的光照模型是Phone光照模型，它综合考虑了物体表面的吸收、反射和透射三种效应。光线投射法是基于Phone光照模型的。通过该方法，可以直接得到每个检测到的表面点到光学中心(焦点)的距离。所以，除了最终生成的图像之外，还可以获得场景的表面信息和深度信息，这将有利于实现在虚拟内窥镜体数据的漫游。而且光线投射法，在一定条件约束下，照射光线以特定的透视几何形状从显示体积内部发出来，穿过三维图像的体元，生成许多表面视图。通过适当修改方法和透视显示参数，所生成的虚拟表面视图就能够有效地模拟那些用真内窥镜获取的图像。
为了完成虚拟内窥镜体数据的实时真实感绘制，在内窥镜体绘制时可以应用一种体数据动态精简技术。对于内窥镜图像的绘制，仅需对与视点有关的数据进行绘制，需处理的数据仅仅局限于视点附近，体绘制的取景体可定义为一个四棱锥。这样每次绘制仅对此四棱锥中的数据进行透视体绘制。由于四棱锥的数据量在整个数据场总数据量中所占比例非常小，对于每次绘制，四棱锥之外的信息无需考虑，所以很容易实现实时显示。此外，Gobetti等将高性能显卡中的纹理映射技术应用于虚拟内窥镜。但是纹理映射缺乏阴影，使漫游的图像缺乏真实性。此外纹理内存的容量也限制了显示的数据量。József使用光线跟踪方法来判断空的体素以减少绘制时间。Mehran将体数据细分成很多的体素块，通过光线跟踪方法计算这些体素块边界体素之间的可见性，然后将直接体绘制方法用于那些可见的体素块上。
在虚拟内窥镜中，为了使得医生能够更快更正确地确定病变体的位置，漫游时的图像质量应该始终放在第一位。但直接对器官网格模型的所有多边形全部绘制，则漫游达不到实时的要求，这就需要降低绘制模型的多边形量。综合比较以上两种绘制方法，本发明采用可见性分析来降低绘制模型的多边形数量。
发明内容
本发明欲解决的技术问题是虚拟内窥镜中的漫游加速和图像质量保持以及如何将该技术很好的和硬件结合在一起。为此，本发明的目的是提供一种虚拟内窥镜的可见性分块绘制装置及其方法。
本发明是基于可见性分析和中心线的方法的人体器官网格模型实时渲染方法。该方法首先对中心线进行光滑处理以消除漫游中的“镜头抖动”现象，同时使该中心线更加有利于分块处理。然后根据肠道的饶曲特性和气管的分叉特性，通过中心线的特征对网格数据进行分块。同以往基于中心线的分块方法相比，我们的分块方法更加合理。最后该方法将建筑物漫游中的可见性分析应用于虚拟内窥镜中，第一次实现了对分叉的可见性计算和分块处理。它不仅加快了漫游的速度，而且使漫游的图像质量得到了保证。
虚拟内窥镜是计算机图形图像处理与虚拟现实技术在医学领域的应用，通过构建虚拟人体模型和计算机显示技术实现人体内窥观察，为真实的物理内窥镜检查提供功能补充，在临床上具有重要的意义。
在本节中我们首先具体说明我们的方法，然后描述它和硬件相结合的发明装置，最后阐述我们方法的具体执行步骤。
通过研究虚拟内窥镜中基于可见性分析的漫游方法，我们发现当前的方法都是先分块得到cell然后再计算这些cell之间的可见性。这样的分块对于可见性来说并不合理，因为在漫游时会造成在某些视点的cell比较多，而在某些视点的cell比较少，使漫游速度不均匀。我们的方法将建筑物漫游中的可见性计算和医学模型的特点结合起来，对实时绘制给出了自己的解决方法。通过光滑后的中心线得到分块的初始位置，再结合可见性的分析对这些分块位置进行调整，使最终的分块对可见性是最优的。
我们的可见性绘制方法是Hong方法的一种推广，通过可见性和中心线来确定分块，并且将这样的分块方法推广到具有分叉的气管漫游。该方法包括四个部分：中心线光滑、网格分解、可见性计算、Cells和Portals的建立。
我们提出的可见性分析和分块处理主要是用于虚拟现实、实时绘制和以及医学影像分析中。同以往的分块方法相比，我们第一次提出了分块的5个准则。通过这些准则，不仅使分块有了监督的标准，而且对类似的虚拟环境中的分块也有很强的指导意义。
本发明是基于可见性分析和中心线的方法的人体器官网格模型实时渲染方法。该方法首先对中心线进行光滑处理以消除漫游中的“镜头抖动”现象，同时使该中心线更加有利于分块处理。然后根据肠道的饶曲特性和气管的分叉特性，通过中心线的特征对网格数据进行分块。同以往基于中心线的分块方法相比，我们的分块方法更加合理。最后该方法将建筑物漫游中的可见性分析应用于虚拟内窥镜中，第一次实现了对分叉的可见性计算和分块处理。它不仅加快了漫游的速度，而且使漫游的图像质量得到了保证。
虚拟内窥镜是计算机图形图像处理与虚拟现实技术在医学领域的应用，通过构建虚拟人体模型和计算机显示技术实现人体内窥观察，为真实的物理内窥镜检查提供功能补充，在临床上具有重要的意义。
在本节中我们首先具体说明我们的方法，然后描述它和硬件相结合的发明装置，最后阐述我们方法的具体执行步骤。
通过研究虚拟内窥镜中基于可见性分析的漫游方法，我们发现当前的方法都是先分块得到cell然后再计算这些cell之间的可见性。这样的分块对于可见性来说并不合理，因为在漫游时会造成在某些视点的cell比较多，而在某些视点的cell比较少，使漫游速度不均匀。我们的方法将建筑物漫游中的可见性计算和医学模型的特点结合起来，对实时绘制给出了自己的解决方法。通过光滑后的中心线得到分块的初始位置，再结合可见性的分析对这些分块位置进行调整，使最终的分块对可见性是最优的。
我们的可见性绘制方法是Hong方法的一种推广，通过可见性和中心线来确定分块，并且将这样的分块方法推广到具有分叉的气管漫游。该方法包括四个部分：中心线光滑、网格分解、可见性计算、Cells和Portals的建立。
我们提出的可见性分析和分块处理主要是用于虚拟现实、实时绘制和以及医学影像分析中。同以往的分块方法相比，我们第一次提出了分块的5个准则。通过这些准则，不仅使分块有了监督的标准，而且对类似的虚拟环境中的分块也有很强的指导意义。
附图说明
图1.中心线的阶梯效应示意图。
图2.中心线光滑示意图。
图3.网格分解示意图。
图4.不同可能边界点的判断角比较图。
图5.Cell的边界面Portal示意图。
图6.可见性计算示意图。
图7.分叉处的可见性要求示意图。
图8.主枝干上不同portal位置的可见性示意图。
图9.分枝上portal位置的确定示意图。
图10.cell的结构图。
图11.网格分割的结果示意图。
图12.portal的结果图。
图13.分块与不分块方法漫游质量的比较图。
图14.本发明的虚拟内窥镜的可见性分块绘制装置结构图。
图15.本发明的虚拟内窥镜的可见性分块绘制方法流程图。
图16.本发明的虚拟内窥镜的可见性分块绘制装置及其方法界面图。
图2.中心线光滑示意图。
图3.网格分解示意图。
图4.不同可能边界点的判断角比较图。
图5.Cell的边界面Portal示意图。
图6.可见性计算示意图。
图7.分叉处的可见性要求示意图。
图8.主枝干上不同portal位置的可见性示意图。
图9.分枝上portal位置的确定示意图。
图10.cell的结构图。
图11.网格分割的结果示意图。
图12.portal的结果图。
图13.分块与不分块方法漫游质量的比较图。
图14.本发明的虚拟内窥镜的可见性分块绘制装置结构图。
图15.本发明的虚拟内窥镜的可见性分块绘制方法流程图。
图16.本发明的虚拟内窥镜的可见性分块绘制装置及其方法界面图。
具体实施方式
1中心线光滑
在虚拟内窥镜中，为了保持漫游时镜头的稳定性，需要一条平滑的中心线。但路径提取是基于体素空间的，因此中心线是由一系列离散的点所组成，这就产生了“阶梯效应”，如附图1所示。通过对中心线的分段线性化来光滑中心线，不仅可以消除小的跳跃现象，而且还可以得到中心线段之间的分块信息。
Bitter采用B-样条曲线对离散的中心线进行光滑，得到的曲线虽然能够很好的解决阶梯效应，但是对分块的意义不大，尤其对于弯曲和分叉的物体。在我们的方法中，通过对中心线的分段线性化来光滑中心线，不仅可以消除小的跳跃现象，而且还可以得到中心线段之间的分块信息。
假设S{X1，X2，……，Xn}是指中心线上所有的中心点所组成的一个点集。s{X1，X2，……，Xm}是S中的一个m个点的子集合。D表示光滑后中心线上的点和以前中心线上点之间的距离阈值。最优的直线段l是指将点集s{X1，X2，……，Xm}投影到l得到一组新的点集s′{X′1，X′2，……，X′m}，满足max(|X1-X′1|，|X2-X′2|，……，|Xm-X′m|)＜D且m为满足该条件的点的最大数目的线段。一条光滑的中心线L就是由许多最优的直线段l所组成。附图2为中心线光滑的过程，其中黑线是原始的中心线，红线是经过光滑以后的中心线。
在执行中心线光滑时，我们采用了贪婪方法，它包括以下两步：
步骤1：设定一个初始值n。从当前的第i点选择n个前后相连的点集{Xi，Xi+1，……，Xi+n}。连接Xi和Xi+n得到初始的线段l，将点集{Xi，Xi+1，……，Xi+n}投影到l上得到另外一个点集{X′i，X′i+1，……，X′i+n}.
步骤2：distance＝|Xj-X′j|，i＜j＜i+n.
如果distance＞D，则n＝n-1。继续步骤1，直到distance＜D，m＝n.
如果distance＜D，则n＝n+1。继续步骤1，直到distance＞D，m＝n-1.
2网格分解
网格分解是cell和portal建立的基础。它通过切割平面和网格相交，对网格进行分解。在网格分解中，最重要的是如何确定分割处网格的边界点和边界线，附图3显示了网格分解的过程，切割平面为左图的虚线，右图的红线为分解后网格上的边界线。
我们的方法是基于中心线的网格分解，首先通过中心线上的点来确定分割平面，但光滑后的中心线只有点的坐标信息，因此需要计算点的法向量才能确定分割平面的位置。在光滑后的中心线上，每段折线上点的法向量都是一样的，因此关键是求取不同线段之间连接点的法向量。我们的计算方法是通过对连接点前后的两个中心点的法向量求平均，从而得到每个中心点的坐标O和法向量V，进而通过S和V确定分割平面P。
dis(P，x)表示了点x和切割平面P之间的距离。网格分解开始于网格中离切割平面最短点的选择，数学表达为：
其中x是网格中的任意一点。
为了加快选择过程，可通过中心点上的半径值来设定一个包围盒，当网格点在该包围盒之外则不需进行计算，在包围盒以内，则通过上面的公式判断是否为最小值。在选择了初始点A以后，为了使得边界点的搜索沿着固定的方向，防止“饶圈”现象的产生，可以建立一个以点O为中心，以OA作为判断角初始边的参考系，如附图4所示。
如果当前选定的边界点是附图4中的点B，则其他点的选择可通过以下两个条件来确定：
1.x为与点B相连的点。
2.极角必须增大。如果当前极角是∠AOB，那么极角∠AOD和∠AOC必须比∠AOB大，其中C和D都是可能的边界点.
通过上面的判断条件，最终可以得到附图3中的红线所表示的边界线。
3可见性计算
在虚拟场景的可见性计算中，网格数据往往被分成很多封闭的Cell。通过估算当前视点能够看到的cell，并只对这些cell进行绘制，可大大的降低面片的渲染时间。此外，虚拟内窥镜中并未存在像建筑物漫游中需要经常对网格数据修改的问题，比如在建筑物漫游中常常出现“在某处加一个窗户，或加一个房间”这样的修改问题。因此在我们的可见性绘制方法中，可见性和分块的计算都在预处理中完成。
经过网格分解，可得到每个Cell上的边界点，但这些边界点并不共面。这些边界点可投影到分割平面，得到附图5所表示的不规则多边形ABCDEFGHIJK。通过这样一个不规则的多边形计算可见性是很困难的，在我们的方法中通过最小外接圆来取代这个不规则多边形。此外，外接圆也可以很好的模拟肠道并消除各向异性的影响。
Cell和Cell之间的可见性计算可通过判断两个Cell之间是否存在不受阻挡的光线来判断。很明显，这样的光线一定穿过Cell与Cell之间Portal。附图6显示了可见性计算的过程。在Pn处的切割平面是Sn，n＝1，2，3……。Project(Sn，，Pn)表示Pn投影到切割平面Sn的面积。Visible(Cn，Cm)表示判断两个Cell Cn和Cm之间的可见性。如果Visible(Cn，Cm)是TRUE，则Cn和Cm是可见的。否则，Cn和Cm是不可见的。
假设当前的视点位于C1，P1是连接C1和C2的portal。因为该portal是当前视点的最大可见性区域，因此初始的非遮挡光线区域的面积是P1。
通过附图6可以得出如下的结论：
因为P1≠0，因此Visible(C1，C2)＝TRUE。
如果Visible(C1，C3)＝TRUE。否则Visible(C1，C3)＝FALSE。
如果Visible(C1，C4)＝TRUE。否则Visible(C1，C4)＝FALSE。
根据以上的推导，任意两个Cell的可见性都能够被确立。
4Cells和Portals的建立
我们的目的是为了减少绘制时当前视点所看到的Cell数目，因此切割平面位置的选取是非常重要的。根据肠道的弯曲特性，切割平面可以非常方便地在肠道中选取，但是在分叉处的切割平面的选取上存在着困难。同以往基于中心线的分块方法相比，我们的方法结合可见性分析解决了分叉处的分块问题以及块的大小和可见性的平衡问题。
在描述如何建立cell和portal之前，首先描述五个分块要求：
1.中心线上转折点的位置可作为初始的分块位置。
2.cell的长度必须在一定的阈值范围之内。
3.肠道上最窄的位置是分块的最优位置。
4.分叉处的分块使分叉前的cell和分叉以后的cell互不可见。在附图7中，通过在分叉处的分块使cell1和cell2、cell3互不可见。
5.Cell的面片数必须超过一定的阈值。
cell和portal的建立是我们方法的核心，它包括以下四个步骤：
1.初始化Portal的位置
经过光滑操作，中心线可很好的指导分块，所有中心线上的线段连接点都可以作为portal的初始位置。
2.分叉处的网格切割
在处理分叉的时候，主枝干上的portal的位置首先被确定。根据要求1，离分叉最近的初始portal位置被选定。然后计算该位置和分叉位置之间的距离，判断是否满足要求2。再根据cell的最大和最小长度确定一个范围，通过该范围在分叉附近寻找肠道最窄的位置。附图8显示了主枝干上portal的不同位置对可见性的影响。
当位于主枝干的portal位置被确定以后，接下来需要确定分枝上portal的位置，并且使该位置的portal满足要求4。确定分枝上portal的位置包括以下两步：
(1)粗计算
直接结合可见性和网格分解来确定分枝上portal的位置是十分耗时的。幸运的是包含距离信息的中心线上的每个点O都包含该点的坐标信息S和该点到边界的最短距离R，可表示为O(S，R)。在图4-9中，将中心点O投影到切割平面P可得到一个新点O’(S’，R’)。在附图5中，每个portal都可表示为P(S，R)，S是该portal的中心，R是portal的半径。从分叉处开始寻找满足distance(OB’(SB’，RB’)，P(S，R))＜(RB+R)和distance(OC’(Sc’，RC’)，P(S，R))＜(RC+R)的初始位置，最终可得到附图9中的B和C两点。
(2)精确计算
如附图9所示，分叉处精确的位置可以从粗计算得到的初始位置B和C处开始寻找。沿着两条分枝逐点地寻找新的portal P1和P2，直到P1和P2满足Project(P，P1)-A＜0和Project(P，P2)-A＜0为止。最终可得到分枝上portal的位置D和E。
3.调整最终的portal的位置
保持分叉处的portal位置不变，包括主枝干和分枝上的portal。调整其他的portal以满足条件2。
4.存储cell并建立各个cell之间的可见性表
因为面数据是以半边数据结构进行存储的，因此很容易得到各个portal之间cell的数据。此外每个cell也存储当前cell中视点所能看到的其他cell。Cell的数据结构如附图10所示。
5与硬件结合的装置图
本发明的主要实际作用是为了降低虚拟内窥镜的硬件成本。在当前流行的虚拟内窥镜平台都是基于工作站的，而本方法所结合的硬件装置是PC机。因为我们的方法是通过可见性计算加速了虚拟漫游，因此一般的PC机就可以满足医生的诊断要求。图14给出了本发明的虚拟内窥镜的可见性分块绘制装置结构图，其中，a)是装置的实物图。b)是装置的方框图。虚拟内窥镜的可见性分块绘制装置，由输入装置1，中间的处理装置2，输出装置3组成，输入装置1连接于中间的处理装置2，中间的处理装置2连接于输出装置3，输入装置1、中间的处理装置2、输出装置3依次顺序连接。其中输入装置1一般为CT/MRI(核磁共振)机，但也可以通过计算机网络进行传输。中间的处理装置2是本文技术的处理核心PC机。输出装置3则是显示器或者计算机网络，可以通过鼠标或者键盘对当前的显示结果进行实时交互，并可以实时的将当前的运行结果通过计算机网络传输出去，以进行远程诊断。
6装置的框架图以及界面图
附图15给出了包含本文所介绍技术的虚拟内窥镜的可见性分块绘制方法流程图，步骤为7步：
S1，在虚拟内窥镜中为了方便医学图像分割，会对数据采集有特殊的要求如虚拟肠镜，为了将息肉与肠内残渣更好的区分开来，要先行清洁病人的肠道，检查前需经肛门注入气体使肠道扩张并肌肉注射平滑肌松弛剂。又如仿真胃镜，检查前需口服适量产气粉，充分扩张胃腔，肌肉注射平滑肌松弛剂降低胃蠕动，然后多体位扫描技术确保充分显示胃的不同部位的细节。然后通过CT、MRI等医学成像设备或者计算机网络传输得到一组连续的二维病人切片，并将这组数据输入到图14所表示PC机部分；
S2，对得到的二维数据进行配准以及平滑处理，通过区域增长或者基于level set的医学图像分割方法提取出用户感兴趣的区域。因为经过前面的特殊处理，通常切片中的这些区域更容易被分离出来；
S3和S4同时进行处理，利用marching cube算法对分割出来的组织器官进行三维重建，并以三维网格的这样的标准形式表示并存储；
S5，对分割的结果进行二值化，并用我们以前提出的DCC算法对这些二值结果进行中心线提取，中心线上的点就可以作为漫游时的视点；
S6，利用本文所提出的分块漫游算法对得到的中心线和三维网格进行分块以及可见性计算，并将最终的结果显示在计算机屏幕上，以用户友好的界面方便用户对病变区域进行观察，并能够通过键盘和鼠标对感兴趣的区域做进一步的分析和观察；
S7，最后将看到和浏览的屏幕图像以文件的形式记录下来，以备查用，并可以通过网络发送到远端，以便实时的诊断。
附图16显示了根据上面的框架所实现的虚拟漫游平台。界面包括三部分：控制面板、参考窗口和主窗口。在控制面板中漫游速度可以任意的调节，观察视角也可以任意的旋转以方便用户的观察附图16显示了根据上面的框架所实现的虚拟漫游平台。它的界面包。通过参考窗口的引入，用户可以实时地知道当前视点所在的位置，这就很好地解决了漫游时“迷路”的问题。
具体实现方式
我们用C++语言实现了本发明所描述的方法，并且在几个不同的数据集上作了实验。所有的实验都是在一台P42.4G，512MB内存，操作系统为Windows 2000的PC机上完成的，显示部分使用了标准的OpenGL图形函数库。
可见性绘制方法在两种数据上进行了测试：简单气管和复杂气管。实验数据列举在表5-2中。
表1.可见性绘制方法的实验数据。
附图11显示了网格分割的结果，原始的数据显示在左列中，右列显示分块以后的结果，不同的色彩表示不同的块。基于中心线，可得到综合可见性和面片数的cell。此外，可见性也能够在这些cell中得到保证，这不仅加快漫游的速度，而且还能保证图像的质量。经过测试，该方法的漫游速度大概比直接绘制提高了2-5倍。
具有portal的漫游图显示在附图12，左边的图显示了主枝干上的portal，右图显示分枝上的portal。
附图13比较了基于分块的漫游图像和没有分块的漫游图像，左边是无分块的，右边是基于分块的。很明显的可以看出，我们的方法不仅能够加快速度，而且还能保持漫游的质量。
在虚拟内窥镜中，为了保持漫游时镜头的稳定性，需要一条平滑的中心线。但路径提取是基于体素空间的，因此中心线是由一系列离散的点所组成，这就产生了“阶梯效应”，如附图1所示。通过对中心线的分段线性化来光滑中心线，不仅可以消除小的跳跃现象，而且还可以得到中心线段之间的分块信息。
Bitter采用B-样条曲线对离散的中心线进行光滑，得到的曲线虽然能够很好的解决阶梯效应，但是对分块的意义不大，尤其对于弯曲和分叉的物体。在我们的方法中，通过对中心线的分段线性化来光滑中心线，不仅可以消除小的跳跃现象，而且还可以得到中心线段之间的分块信息。
假设S{X1，X2，……，Xn}是指中心线上所有的中心点所组成的一个点集。s{X1，X2，……，Xm}是S中的一个m个点的子集合。D表示光滑后中心线上的点和以前中心线上点之间的距离阈值。最优的直线段l是指将点集s{X1，X2，……，Xm}投影到l得到一组新的点集s′{X′1，X′2，……，X′m}，满足max(|X1-X′1|，|X2-X′2|，……，|Xm-X′m|)＜D且m为满足该条件的点的最大数目的线段。一条光滑的中心线L就是由许多最优的直线段l所组成。附图2为中心线光滑的过程，其中黑线是原始的中心线，红线是经过光滑以后的中心线。
在执行中心线光滑时，我们采用了贪婪方法，它包括以下两步：
步骤1：设定一个初始值n。从当前的第i点选择n个前后相连的点集{Xi，Xi+1，……，Xi+n}。连接Xi和Xi+n得到初始的线段l，将点集{Xi，Xi+1，……，Xi+n}投影到l上得到另外一个点集{X′i，X′i+1，……，X′i+n}.
步骤2：distance＝|Xj-X′j|，i＜j＜i+n.
如果distance＞D，则n＝n-1。继续步骤1，直到distance＜D，m＝n.
如果distance＜D，则n＝n+1。继续步骤1，直到distance＞D，m＝n-1.
2网格分解
网格分解是cell和portal建立的基础。它通过切割平面和网格相交，对网格进行分解。在网格分解中，最重要的是如何确定分割处网格的边界点和边界线，附图3显示了网格分解的过程，切割平面为左图的虚线，右图的红线为分解后网格上的边界线。
我们的方法是基于中心线的网格分解，首先通过中心线上的点来确定分割平面，但光滑后的中心线只有点的坐标信息，因此需要计算点的法向量才能确定分割平面的位置。在光滑后的中心线上，每段折线上点的法向量都是一样的，因此关键是求取不同线段之间连接点的法向量。我们的计算方法是通过对连接点前后的两个中心点的法向量求平均，从而得到每个中心点的坐标O和法向量V，进而通过S和V确定分割平面P。
dis(P，x)表示了点x和切割平面P之间的距离。网格分解开始于网格中离切割平面最短点的选择，数学表达为：
其中x是网格中的任意一点。
为了加快选择过程，可通过中心点上的半径值来设定一个包围盒，当网格点在该包围盒之外则不需进行计算，在包围盒以内，则通过上面的公式判断是否为最小值。在选择了初始点A以后，为了使得边界点的搜索沿着固定的方向，防止“饶圈”现象的产生，可以建立一个以点O为中心，以OA作为判断角初始边的参考系，如附图4所示。
如果当前选定的边界点是附图4中的点B，则其他点的选择可通过以下两个条件来确定：
1.x为与点B相连的点。
2.极角必须增大。如果当前极角是∠AOB，那么极角∠AOD和∠AOC必须比∠AOB大，其中C和D都是可能的边界点.
通过上面的判断条件，最终可以得到附图3中的红线所表示的边界线。
3可见性计算
在虚拟场景的可见性计算中，网格数据往往被分成很多封闭的Cell。通过估算当前视点能够看到的cell，并只对这些cell进行绘制，可大大的降低面片的渲染时间。此外，虚拟内窥镜中并未存在像建筑物漫游中需要经常对网格数据修改的问题，比如在建筑物漫游中常常出现“在某处加一个窗户，或加一个房间”这样的修改问题。因此在我们的可见性绘制方法中，可见性和分块的计算都在预处理中完成。
经过网格分解，可得到每个Cell上的边界点，但这些边界点并不共面。这些边界点可投影到分割平面，得到附图5所表示的不规则多边形ABCDEFGHIJK。通过这样一个不规则的多边形计算可见性是很困难的，在我们的方法中通过最小外接圆来取代这个不规则多边形。此外，外接圆也可以很好的模拟肠道并消除各向异性的影响。
Cell和Cell之间的可见性计算可通过判断两个Cell之间是否存在不受阻挡的光线来判断。很明显，这样的光线一定穿过Cell与Cell之间Portal。附图6显示了可见性计算的过程。在Pn处的切割平面是Sn，n＝1，2，3……。Project(Sn，，Pn)表示Pn投影到切割平面Sn的面积。Visible(Cn，Cm)表示判断两个Cell Cn和Cm之间的可见性。如果Visible(Cn，Cm)是TRUE，则Cn和Cm是可见的。否则，Cn和Cm是不可见的。
假设当前的视点位于C1，P1是连接C1和C2的portal。因为该portal是当前视点的最大可见性区域，因此初始的非遮挡光线区域的面积是P1。
通过附图6可以得出如下的结论：
因为P1≠0，因此Visible(C1，C2)＝TRUE。
如果Visible(C1，C3)＝TRUE。否则Visible(C1，C3)＝FALSE。
如果Visible(C1，C4)＝TRUE。否则Visible(C1，C4)＝FALSE。
根据以上的推导，任意两个Cell的可见性都能够被确立。
4Cells和Portals的建立
我们的目的是为了减少绘制时当前视点所看到的Cell数目，因此切割平面位置的选取是非常重要的。根据肠道的弯曲特性，切割平面可以非常方便地在肠道中选取，但是在分叉处的切割平面的选取上存在着困难。同以往基于中心线的分块方法相比，我们的方法结合可见性分析解决了分叉处的分块问题以及块的大小和可见性的平衡问题。
在描述如何建立cell和portal之前，首先描述五个分块要求：
1.中心线上转折点的位置可作为初始的分块位置。
2.cell的长度必须在一定的阈值范围之内。
3.肠道上最窄的位置是分块的最优位置。
4.分叉处的分块使分叉前的cell和分叉以后的cell互不可见。在附图7中，通过在分叉处的分块使cell1和cell2、cell3互不可见。
5.Cell的面片数必须超过一定的阈值。
cell和portal的建立是我们方法的核心，它包括以下四个步骤：
1.初始化Portal的位置
经过光滑操作，中心线可很好的指导分块，所有中心线上的线段连接点都可以作为portal的初始位置。
2.分叉处的网格切割
在处理分叉的时候，主枝干上的portal的位置首先被确定。根据要求1，离分叉最近的初始portal位置被选定。然后计算该位置和分叉位置之间的距离，判断是否满足要求2。再根据cell的最大和最小长度确定一个范围，通过该范围在分叉附近寻找肠道最窄的位置。附图8显示了主枝干上portal的不同位置对可见性的影响。
当位于主枝干的portal位置被确定以后，接下来需要确定分枝上portal的位置，并且使该位置的portal满足要求4。确定分枝上portal的位置包括以下两步：
(1)粗计算
直接结合可见性和网格分解来确定分枝上portal的位置是十分耗时的。幸运的是包含距离信息的中心线上的每个点O都包含该点的坐标信息S和该点到边界的最短距离R，可表示为O(S，R)。在图4-9中，将中心点O投影到切割平面P可得到一个新点O’(S’，R’)。在附图5中，每个portal都可表示为P(S，R)，S是该portal的中心，R是portal的半径。从分叉处开始寻找满足distance(OB’(SB’，RB’)，P(S，R))＜(RB+R)和distance(OC’(Sc’，RC’)，P(S，R))＜(RC+R)的初始位置，最终可得到附图9中的B和C两点。
(2)精确计算
如附图9所示，分叉处精确的位置可以从粗计算得到的初始位置B和C处开始寻找。沿着两条分枝逐点地寻找新的portal P1和P2，直到P1和P2满足Project(P，P1)-A＜0和Project(P，P2)-A＜0为止。最终可得到分枝上portal的位置D和E。
3.调整最终的portal的位置
保持分叉处的portal位置不变，包括主枝干和分枝上的portal。调整其他的portal以满足条件2。
4.存储cell并建立各个cell之间的可见性表
因为面数据是以半边数据结构进行存储的，因此很容易得到各个portal之间cell的数据。此外每个cell也存储当前cell中视点所能看到的其他cell。Cell的数据结构如附图10所示。
5与硬件结合的装置图
本发明的主要实际作用是为了降低虚拟内窥镜的硬件成本。在当前流行的虚拟内窥镜平台都是基于工作站的，而本方法所结合的硬件装置是PC机。因为我们的方法是通过可见性计算加速了虚拟漫游，因此一般的PC机就可以满足医生的诊断要求。图14给出了本发明的虚拟内窥镜的可见性分块绘制装置结构图，其中，a)是装置的实物图。b)是装置的方框图。虚拟内窥镜的可见性分块绘制装置，由输入装置1，中间的处理装置2，输出装置3组成，输入装置1连接于中间的处理装置2，中间的处理装置2连接于输出装置3，输入装置1、中间的处理装置2、输出装置3依次顺序连接。其中输入装置1一般为CT/MRI(核磁共振)机，但也可以通过计算机网络进行传输。中间的处理装置2是本文技术的处理核心PC机。输出装置3则是显示器或者计算机网络，可以通过鼠标或者键盘对当前的显示结果进行实时交互，并可以实时的将当前的运行结果通过计算机网络传输出去，以进行远程诊断。
6装置的框架图以及界面图
附图15给出了包含本文所介绍技术的虚拟内窥镜的可见性分块绘制方法流程图，步骤为7步：
S1，在虚拟内窥镜中为了方便医学图像分割，会对数据采集有特殊的要求如虚拟肠镜，为了将息肉与肠内残渣更好的区分开来，要先行清洁病人的肠道，检查前需经肛门注入气体使肠道扩张并肌肉注射平滑肌松弛剂。又如仿真胃镜，检查前需口服适量产气粉，充分扩张胃腔，肌肉注射平滑肌松弛剂降低胃蠕动，然后多体位扫描技术确保充分显示胃的不同部位的细节。然后通过CT、MRI等医学成像设备或者计算机网络传输得到一组连续的二维病人切片，并将这组数据输入到图14所表示PC机部分；
S2，对得到的二维数据进行配准以及平滑处理，通过区域增长或者基于level set的医学图像分割方法提取出用户感兴趣的区域。因为经过前面的特殊处理，通常切片中的这些区域更容易被分离出来；
S3和S4同时进行处理，利用marching cube算法对分割出来的组织器官进行三维重建，并以三维网格的这样的标准形式表示并存储；
S5，对分割的结果进行二值化，并用我们以前提出的DCC算法对这些二值结果进行中心线提取，中心线上的点就可以作为漫游时的视点；
S6，利用本文所提出的分块漫游算法对得到的中心线和三维网格进行分块以及可见性计算，并将最终的结果显示在计算机屏幕上，以用户友好的界面方便用户对病变区域进行观察，并能够通过键盘和鼠标对感兴趣的区域做进一步的分析和观察；
S7，最后将看到和浏览的屏幕图像以文件的形式记录下来，以备查用，并可以通过网络发送到远端，以便实时的诊断。
附图16显示了根据上面的框架所实现的虚拟漫游平台。界面包括三部分：控制面板、参考窗口和主窗口。在控制面板中漫游速度可以任意的调节，观察视角也可以任意的旋转以方便用户的观察附图16显示了根据上面的框架所实现的虚拟漫游平台。它的界面包。通过参考窗口的引入，用户可以实时地知道当前视点所在的位置，这就很好地解决了漫游时“迷路”的问题。
具体实现方式
我们用C++语言实现了本发明所描述的方法，并且在几个不同的数据集上作了实验。所有的实验都是在一台P42.4G，512MB内存，操作系统为Windows 2000的PC机上完成的，显示部分使用了标准的OpenGL图形函数库。
可见性绘制方法在两种数据上进行了测试：简单气管和复杂气管。实验数据列举在表5-2中。
表1.可见性绘制方法的实验数据。
附图11显示了网格分割的结果，原始的数据显示在左列中，右列显示分块以后的结果，不同的色彩表示不同的块。基于中心线，可得到综合可见性和面片数的cell。此外，可见性也能够在这些cell中得到保证，这不仅加快漫游的速度，而且还能保证图像的质量。经过测试，该方法的漫游速度大概比直接绘制提高了2-5倍。
具有portal的漫游图显示在附图12，左边的图显示了主枝干上的portal，右图显示分枝上的portal。
附图13比较了基于分块的漫游图像和没有分块的漫游图像，左边是无分块的，右边是基于分块的。很明显的可以看出，我们的方法不仅能够加快速度，而且还能保持漫游的质量。