第２３卷第１期 ２０１０年３月 湖南理工学院学报（自然科学版）
Ｊｏｕｒｎａｌ ｏｆ Ｈｕｎａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅｓ） ＶＯ１．２３ ＮＯ．１
ＭａＬ ２０１０
序列图像三维重建中的关键算法 方 欣 ，郭观七 ， 沈中ｒ阳２ （１．湖南理工学院信息与通讯工程学院，湖南岳阳４１４０００；２．资兴市青少年活动中心，湖南郴州４２３４００） 摘要：主要讨论了基于序列图像的三维重建中的两个关键算法：特征数据点列的重采样算法与三角化算法．本文改 进了Ｃｈｅｔｖｅｒｉｋｏｖ等提出的轮廓曲线中高曲率点的检测算法，使在重采样时，数据的压缩比得到了明显的改善，也显著地提 高了可视化速度．并使用一种简单的三角化算法，对重采样后的数据点列进行三角化，实现目标的三维重建． 关键词：图像序列；三维重建；高曲率；重采样；三角化 中图分类号：ＴＰ３ １７．４ 文献标识码：Ａ 文章编号：１６７２．５２９８（２０１０）０１—００３５—０４
Ｔｈｅ Ａｌｇｏｒｉｔｈｍ ａｂｏｕｔ ３Ｄ Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ０ｆ Ｉｍａｇｅ Ｓｅｑｕｅｎｃｅｓ ＦＡＮＧ Ｘｉｎ ，ＧＵＯ Ｇｕａｎ—ｑｉ ，ＳＨＥＮ Ｚｈｏｎｇ—ｙａｎｇ （１．Ｃｏｌｌｅｇｅ ｏｆＩｎｆｏｒｍａｔｉｏｎ＆Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｕｎａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆＳｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｙｕｅｙａｎｇ ４１４００６，Ｃｈｉｎａ； ２．Ｚｉｘｉｎｇ Ａｃｔｉｖｉｔｙ Ｃｅｎ￣ｅ ｆｏｒ Ｔｅｅｎａｇｅｒｓ，Ｃｈｅｎｚｈｏｕ ４２３４００，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｗｏ ｉｍｐｏｒｔａｎｔ ａｌｇｏｒｉｔｈｍ ｉｎ ３Ｄ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｉｍａｇｅ ｓｅｑｕｅｎｃｅｓ ａｒｅ ｓｔｕｄｉｅｄ，ｉ．ｅ．ｒｅ—ｓａｍｐｌｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｒｉａｎｇｕｌａｔｉｏｎ ａｌｇｏｒｉｔｈｍ．Ａｎ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｔｅｃｔｉｏｎ ｏｆ ｈｉｇｈ ｃｕｒｖａｔｕｒｅ ｐｏｉｎｔｓ ｉｎ ｐｌａｎａｒ ｃｕｒｖｅｓ ｉｓ ｐｒｅｓｅｎｔｅｄ．Ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｒｅ—ｓａｍｐｌｉｎｇ ａｎｄ ３Ｄ ｄａｔａ ｆｉｅｌｄ ｖｉｓｕａｌｉｚａｔｉｏｎ．Ｔｒｉａｎｇｕｌａｔｉｏｎ ｉｓ ｉｍｐｌｅｍｅｎｔｅｄ ｂｙ ｕｓｉｎｇ ａ ｓｉｍｐｌｅ ｔｒｉａｎｇｕｌａｔｉｏｎ ａｌｇｏｒｉｔｈｍ．Ｓｅｑｕｅｎｔｉａｌｌｙ，３Ｄ ｏｂｊｅｃｔ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｗａｓ ａｃｈｉｅｖｅｄ． Ｋｅｙ ｗｏｒｄｓ：ｉｍａｇｅ ｓｅｑｕｅｎｃｅ；３Ｄ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ；Ｈｉｇｈ Ｃｕｒｖａｔｕｒｅ；ｒｅ—ｓａｍｐｌｉｎｇ；ｔｒｉａｎｇｕｌａｔｉｏｎ
引言
随着计算机软硬件技术和医学成像技术的日益发展，基于数字图像技术的医学应用系统也得到了长 足的发展．在这些医学应用系统中，在有效精确地提取出医学图像中相应目标特征量的基础上，进行人体 组织或器官的三维重建［¨，是很多实用系统的基础，如基于图像的病理分析【２Ｊ、基于图像的手术导引与增
、虚拟手术平台［ ］等应用系统，因此医学图像的三维重建一直是国内外医学界及图像处理领域的研究 与应用热点之一． 三维重建的目的是从一系列二维切片数据（图像）中得到物体的三维表示，一般使用网格的形式来表 示．目前，三维重建过程中经常沿用的一种经典算法是Ｌｏｒｅｎｓｅｎ等人于１ ９８７年提出的Ｍａｒｃｈｉｎｇ Ｃｕｂｅｓ方 法［刚，其原理简单，易于实现．但这种方法计算效率低，输出的三角网格数量巨大．因此近些年来，研究者 们从不同角度对该算法进行改进【 ，８］．本文在文献［５］的基础上提出了一种基于轮廓的三维重建方法，运 用并改进了相关算法，与直接运用文献［５］所提出的算法相比较，本文所提出并改进的方法处理速度更快， 输出的三角网格数量也较少，而且三角网格的形态也比较理想．
１算法描述 作者实现基于序列图像三维重建的主要思路如下： ｆ１）特征提取：在序列图像中提取出需要重建目标的轮廓； （２）特征点列重采样：将（１）中检测出的边缘按创建Ｃｈａｉｎ—ｃｏｄｅ的方法，形成点列，并对此点列进行重 采样，以减少后续阶段中处理的数据量； （３）基于轮廓的空间点三角化：采用一种简单有效的三角化算法，对（２）中重采样后的点列进行三角
化，形成三角面片；
收稿日期：２００９－０９—２９ 作者简介：方欣（１９７卜）＇男，湖南岳阳人，硕士，湖南理工学院信息与通讯工程学院讲师．主要研究方向：计算机网络、图像处理 湖南理工学院学报（自然科学版） 第２３卷 （４）三角面片的可视化：使用ＯｐｅｎＧＬ技术，实现重建目标的三维显示． 本文主要讨论了第（２）与第（３）过程中所采用及改进的算法．特征点列重采样采用文献［５］所描述的算法， 但该算法主要应用于轮廓曲线上高曲率点的检测，而应用于重采样时，数据的压缩比并不理想，本文提出 了对该算法的改进方法，使得重采样数据的压缩比得到了明显改善． 经过实验测试比较，在提取序列图像中目标的边缘轮廓过程中，使用传统的Ｒｏｂｅ￣算子或Ｃａｎｎｙ算子， 能较好地保证分割出来的边缘是单像素点．否则的话，则可使用细化（Ｔｈｉｎｎｉｎｇ）算法作进一步处理．当得 到单像素点的边缘后，按照创建Ｃｈａｉｎ—ｃｏｄｅ的方法，扫描检测出的边缘点，由此而形成点序列，便于重采 样算法的操作． １．１特征点列重采样 文献【５］提出了一种两次扫描算法：对获得的特征点列进行两次扫描．第一次扫描，选择出可能的高 曲率点，作为重采样点列的候选点；第二次扫描，根据特定的条件，在第一次扫描所产生的候选点中进一 步剔除一些点，形成最终的重采样点列结果． ｆＩ）第一次扫描 在本次扫描中，文献［５］中采用一种非严格数学意义上的高曲率定义。如图１所示，在当前所处理的点 Ｐ两侧，分别找出满足表达式（１）与（２）的点对 与Ｐ＋，并计算出由此三点所构成三角形的一个内角 ，如 果角 满足表达式（３），则称Ｐ为高曲率点，将其作为重采样点列的候选点．继续处理轮廓点列中的下一个 点，如此反复，直到所有轮廓点处理完毕．记录所有候选点的坐标值及其一个内角 ． ≤ｊＰ—Ｐ ｊ ≤ （１） ｉ ≤ｌＰ—Ｐ—ｌ ≤ （２） ≤ （３）
Ｏ／＝ａｒｃｃｏｓ ∈ ７ｃ］） 式中：ＩＰ— ｒ表示在图像坐标系中，点Ｐ与Ｐ＋之间的直线距离．兀－ｌ ｌ称为点Ｐ的尖锐度． （２）第二次扫描 如图２所示，在第一次扫描所产生的候选点列中选择一个初始处理点尸，在其一侧查找满足表达式（４） 或（５）的所有点 ，如果有任意一个点 使表达式（６）成立，则Ｐ点被剔除．继续处理下一个候选点，如此 反复直至处理所有候选点，最后所剩下的点就是重采样点列． ＩＪＰ一 Ｉ ≤ ｆ尸一 ｆ ≤ ｉ ＞ ） 式中： Ｐ）表示在第一次扫描过程所记录下来的Ｐ点所对应的三角形内角 （３）算法中的参数 图１ 图２ （４） （５） （６） 第１期 方欣等：序列图像三维重建中的关键算法 ３７ 算法在上述表达式（１）～（５）中使用了三个可调参数：ａｍ ，ｄｍｉ ， ，分别表示距离的最大、最小值与角
度的最大值．文献［５］中设定 ＝ｄｍｉｎ＋２．如图３中（ａ）～（ｄ）分别是ｄｍｉｎ与 取不同值时的实验结果． （４）算法改进 作者在自己实现的上述算法测试程序中，以及在文献［５］所提供的网站上进行实验比较，在两次扫描 过程中设定参数为ｄｍ ＝５， ｉｎ＝３， ＝Ｉ７０时得到了该算法的最佳效果，如图４（ｂ）所示，从图中可以
很明显地看到，还可以剔除大量的点，但文献［５］所提出的算法对此已无能为力了．经实验测试，本文提出 了如下改进方法： 增加第四个参数．在原算法第二次扫描中，表达式（４）与（５）中所使用参数仍然与第一次扫描中参数一 致，本文经测试，如果增加一个与第一次扫描中无任何关系的新参数，则重采样数据的压缩比有明显改善， 即本文将式（４）与（５）中参数 ａｘ的值设置为１０，与式（１）与（２）中参数ｄｍａｘ无约束关系．如图４所示，（ａ）是用 来处理的原始切片图像，（ｂ）是使用文献［５］的算法处理结果图，（ｃ）是改进算法处理结果图．
（ａ） 厂
（ｃ） 图３（ａ）ｄｍｌ ＝２， ＝１５０ （ｂ） ｉ ＝２， ＝１７０ （Ｃ） ｍ ５， １５０ （ｄ） ｎ ５， １７０
（ａ） ，／一、． ．．－ ；
ｉ ’： ＿； 、 一。 ＼ 。、 ．
（ｂ） 图４特征点列重采样结果
（ｄ）
原始算法的检测结果，（ｃ）是使用改进算法的检测结果．显然（ｃ）所示结果图中产生的点数量比（ｂ）要少 得多，也即重采样的压缩比高，同时仍然可以逼真的拟合原始轮廓曲线． １．２简单的三角化算法 在这一过程中，对重采样后的轮廓点列采用如下简单的三角化算法： （１）对所有序列图像中重采样后的轮廓点按同一方向扫描，形成新的点序列； （２）在相邻两帧图像的轮廓点序列中查找出其空间距离最小的两个点； （３）将（２）中所选择的两点作为三角形的两个顶点； （４）如图５所示，第三个顶点有两种选择方案，但选择。【角较小者作为最优三角形，形成一个三角面 片（网格）．