侯慧玲,王明泉,任少卿
中北大学 仪器科学与动态测试教育部重点实验室,太原 030051
工业CT数据场面绘制和体绘制改进算法研究
侯慧玲,王明泉,任少卿
中北大学 仪器科学与动态测试教育部重点实验室,太原 030051
HOU Huiling,WANG Mingquan,REN Shaoqing.Research for improved surface rendering and volume rendering algorithms based on ICT data field.Computer Engineering and Applications,2014,50(23):172-175.
工业 CT(Industrial Computerized Tomography)断层图像的三维可视化技术在工业CT无损检测系统中起着非常重要的作用,也是图像三维可视化技术在工业领域的一个重要应用[1-2]。目前工业CT断层图像三维结构可视化成像方法主要分为面绘制(Surface Rendering)和体绘制(Direct Volume Rendering)两大类[3-4]。其中面绘制[5]是通过构造中间图元来实现三维重建,对数据分割要求高,运算量大且易遭受到噪声干扰而使得物体局部边缘特征模糊,传统阈值分割方法难以得到较好的效果。体绘制[6]不产生中间几何图元,直接将三维体数据映射成二维图像,展示体细节,绘制质量高,但由于需要对每一个体素进行操作,其计算复杂度大,绘制速度较慢,很难达到实时性。
本文针对面绘制中的MC算法采用相似性区域分割的方法进行准确分割,再利用分割结果进行等值面的精确提取,可显著提高运算速度。针对体绘制技术中的光线投射算法,采用二维最大熵的阈值分割技术来重建工业CT断层图像,可使体绘制技术加速实现。
面绘制算法基于二维断层图像的边缘或轮廓提取,借助了传统的计算机图形学技术,并可以充分利用现有的图形加速硬件实现绘制功能,是一种常用的三维可视化算法,在有实时交互性能要求的应用中广泛应用。
2.1 传统的MC算法
Marching Cube(MC)算法是三维数据场等值面生成的经典算法,1987年由Lorensen等提出,其基本思想是逐个处理数据场中的立方体,提取出与等值面相交的立方体[5,7]。
传统的MC算法求等值面的步骤可以描述如下:
(1)将三维离散规则数据场分层读入内存;(2)扫描两层数据,逐个构造体素,每个体素中的8个顶点取自相邻的两层;(3)体素中每个顶点的函数值与给定的等值面值做比较,根据比较结果,构造该体素的索引表;(4)根据索引表得出将与等值面有交点的体素边界;(5)通过线性插值方法计算出体素边界与等值面的交点;(6)利用中心差分方法,求出体素各顶点处的法向量,再通过线性插值方法,求出三角面片各顶点处的法向;(7)根据各三角面片各顶点的坐标及法向量绘制等值面图像。
MC算法实质上是通过阈值分割来提取等值面,阈值分割会造成图像中目标物体不可避免地受到噪声的干扰,使得物体局部边缘特征模糊,用阈值分割难以得到较好的效果。此外,传统MC算法是顺序检测每个立方体,浪费很多时间在检测根本就无三角面片的空立方体上,文献[8]分析得出真正与等值面相交的立方体只占总数据量的很小一部分,算法执行中30%~70%的时间用在空单元的检测上,因此需要研究一种合理的数据结构对空间数据进行有效遍历的方法,以加速对空单元的检测和过滤。
2.2 基于相似性区域分割的改进算法
区域增长是一种根据事前定义的准则将像素或子区域聚合成更大区域的过程,基本的方法是以一组种子作为增长的起点,将与种子性质相似的相邻像素附加到增长区域的每个种子上。重复上面过程,直到再没有满足条件的像素可被包括进来[9]。区域分割法的关键是寻找具有相似性的像素群,相似性检测准则多从灰度特性、梯度特性、纹理特性等角度给予考虑。本研究基于区域内灰度分布相似性,提出了分割出目标体素和背景体素的方法。
对像素(x,y)的8-邻域 M,定义:
来判别(k,l)与(x,y)的相似性。如果这两个像素具有相似性,则将它们划分到同一区域,如果不具有相似性,则将它们划分到不同的区域。对512×512的摩托车发动机CT断层图像切片分割结果如图1所示。
图1 相似性区域分割结果
根据工业断层图像特点,本文在MC算法的基础上,选择相似性区域分割方法,将体素分为目标体素和背景体素,利用分割结果再进行等值面的构造,减少了冗余信息的检测,对空间数据能够进行有效遍历,提高了检测效率。
2.3 改进MC算法的实验结果
对512×512×194规模的摩托车发动机工业CT数据进行面绘制实验,绘制结果如图2所示。其中图2(a)为发动机整体三维显示,图2(b)、(c)为不同角度的局部剖面三维显示。
图2 改进MC算法绘制的三维显示结果
通过实验数据比较可知(见表1),由于算法过程中仅对三维重建有意义的目标体素进行处理,该算法在一定程度上减少了拟合的三角片面数量,从而加快了绘制速度,在一定程度上改进了MC算法。
表1 绘制时间比较 ms
与面绘制方法不同,体绘制方法不需要构造曲线或曲面这一中间环节,采用体光照模型对三维数据场进行直接显示,体绘制比表面绘制具有更高的绘制精度。
3.1 光线投射算法
光线投射法(Ray Casting)是一种基于图像空间为序的算法,由P.Sabella和M.Levoy提出,在三维重建中得到广泛的应用[10]。其原理为:从图像平面的每个像素根据投影方向发出一条射线穿过体数据场,在这条射线上等间距采样,计算每个采样点的透明度、颜色和梯度向量等,按一定的绘制模型计算每个像素的亮度,最终得到投影图像[11-12]。如图3所示。
图3 光线投射算法原理图
传统光线投影算法,由于采用为每个体素分配不透明的光强的方法合成图像,因此,有利于保留图像的细节,绘制高品质的图像。但同时也不难看出计算量相当大,需要对每一个体素进行操作,对每条光线又多次采样,极大地限制了绘制速度[13]。因此,要在保证图像精度的同时如何对绘制速度进行改进就成为必需解决的问题。
3.2 基于最大熵阈值分割的改进算法
为了减少重建过程中所需处理的体素数量,在体绘制中引入图像分割的概念。
二维最大熵阈值分割算法[14-15]如下:
若一幅图像的灰度级数为 L,总的像素点数为N(m×n),设 fi,j为图像中点灰度为i及其区域灰度均值为 j的像素点数,pi,j=fi,j/N 为点灰度-区域灰度均值对 (i,j)发生的概率,则 {pi,j,i,j=1,2,…,L} 是该图像关于点灰度-区域灰度均值的二维直方图。二维直方图能有效利用图像的灰度信息和邻域的空间相关信息。
图4为二维直方图的xoy平面图。沿对角线分布的 A区和B区分别代表目标和背景,远离对角线的C区和D区代表边界和噪声,所以应该在A区和B区上利用点灰度-区域灰度均值二维最大熵法确定最佳阈值,可使真正代表目标和背景的信息量最大。用像素灰度等于s和邻域平均灰度等于t的两个门限来划分图像的二维灰度直方图。定义离散二维熵为:
图4 二维直方图xoy平面图
以上为二维最大熵阈值分割算法,但式(7)忽略了背景与目标在图像上所占比例的不同,由此引入权重系数ξ,介于0和1之间,以调整背景灰度熵与目标灰度熵在判断函数中所占的比例:
本文处理的摩托车发动机CT断层图像中被测工件所在区域灰度值相对较小,见图5(a),先计算图像整体的灰度均值,然后在均值以下的范围内搜索获得矢量(S,T),ξ取0.7。结合阈值面积消除法对断层图像进行二维最大熵阈值分割,分割结果见图5(b)。
图5 二维最大熵阈值分割结果
本文通过对原始的体素数据集进行遍历,选择最终的分割阈值,将原始的体素数据集中的体素分为目标体素和背景体素。基于该方法改进后的光线投射体绘制算法在绘制图像时,只对目标体素数据集中的体素进行绘制,对背景体素数据集中的体素不做任何操作。从而减少了绘制图像时所需处理的体素数据量,加快了图像的三维绘制速度,改进了传统的光线投射算法。
3.3 改进光线投射算法的实验结果
基于VTK实现了改进的光线投射法,对512×512× 194规模的摩托车发动机工业CT数据进行体绘制实验,得到整体绘制结果图,其绘制结果如图6(a)所示。另外,在图6(b)(c)中分别运用了平面虚拟切割和立方体虚拟切割,得到剖面三维显示,可以帮助技术人员通过不同的方向观察不同位置的二维图像。
图6 改进算法绘制的发动机断层三维图
表2为传统方法和改进方法对摩托车发动机断层图像绘制时间比较。实验结果表明,改进算法在绘制速度上有一定的提高,说明改进的光线投射算法的效果较为理想。
表2 体绘制时间比较 ms
本文对三维数据场可视化的关键技术进行了研究,对面绘制的经典MC算法进行了改进和优化,根据工业图像特点,采用相似性区域分割方法,实现准确分割,并利用分割结果精确地提取等值面,改善了生成图像的质量。另外,改进了体绘制的经典光线投射算法,采用一种基于最大熵阈值分割光线投射算法的加速算法,该算法只对目标体素进行处理,加快重采样计算过程,在保证绘制质量的前提下,提高三维空间离散数据场重采样的速度,较好地解决了光线投影算法绘制时间长的问题。最后,利用发动机的工业CT断层切片,验证了改进算法在绘制速度及绘制效果方面的有效性。
[1]Bonnet S,Koenig A.Dynamic X-ray computed tomography[J].Proceeding of the IEEE,2003,91(10):1574-1588.
[2]胡剑,王明泉.使用GPU编程的工业CT断层图像三维可视化技术[J].应用科技,2011,38(5):61-65.
[3]沈海戈,柯有安.医学体数据三维可视化方法的分类与评价[J].中国图象图形学报,2000,85(7):545-550.
[4]黄辉,陆利忠,闫镔,等.三维可视化技术研究[J].信息工程大学学报,2010,11(2):218-222.
[5]Lorensen W E,Cline H E.Marching cubes:a high resolution 3D surfaceconstruction algorithm[J].Computer Graphics,1987,21(4):163-169.
[6]Philipp M O,Kubin K,Mang T.Three-dimensional volume rendering of multidetector-row CT data:applicable for emergency radiology[J].European Journal of Radiology,2003,48(1):33-38.
[7]钱峰,马秀丽,杨胜齐,等.移动立方体算法的研究和改进[J].计算机工程与应用,2010,46(34):177-180.
[8]Wilhelms J,Van Gelder A.Topological considerations in isosurface generation[J].ACM Transactions on Graphics,1994,13(4):337-375.
[9]杨静宇,曹雨龙.计算机图像处理及常用算法手册[M].南京:南京大学出版社,1997:173-209.
[10]Levoy M.Display of surfaces from volume data[J].IEEE Computer Graphics and Applications,1998,8(3):29-37.
[11]钱鹰,张翔,赖均.改进的光线投射法[J].计算机工程与设计,2011,32(11):3780-3783.
[12]何士和,王小鹏,吴双,等.一种改进的光线投射方法[J].中国体视学与图像分析,2013,18(2):130-134.
[13]丁庆木,张虹.图像体绘制算法的分析与评价[J].系统仿真学报,2007,19(4):897-900.
[14]张红顺,杨凯达,张浩.基于二维最大熵阈值的SAR图像分割算法[J].科技信息,2012(6).
[15]周德芳,张健.二维最大熵阈值分割的一种快速递推算法及应用[J].现代电子技术,2003(24):85-87.
HOU Huiling,WANG Mingquan,REN Shaoqing
Ministry Education Key Lab for Instrumentation Science and Dynamic Test,North University of China,Taiyuan 030051,China
Reconstruction speed and accuracy are two important indicators of industrial CT products.According to the MC surface rendering algorithm,an improved algorithm is proposed based on the comparability region segmentation.The accurate segmentation result is used as the input of MC to generate equivalence surfaces.The detection efficiency can be improved significantly.According to ray casting algorithm,an 2D maximum entropy threshold segmentation preprocessing is proposed.The 2D histogram entropy maximization is used to define the extent of threshold,and research the optimal combination of the parameters.The results of reconstruction show that the improved algorithm can greatly reduce reconstruction volume data and improve the efficiency of ray casting.
industrial Computerized Tomography(CT);surface rendering;volume rendering;Marching Cube(MC)algorithm;ray casting algorithm
工业CT图像的重建速度和精度是工业CT产品的两个重要指标。针对面绘制的MC算法提出了一种基于相似性区域分割的三维工业图像表面重建算法,实现了准确分割,并利用分割结果精确地提取等值面,显著提高了检测效率;针对体绘制的光线投射算法提出了一种基于二维最大熵阈值的分割预处理方法,利用二维直方图熵最大化寻找阈值的最佳组合,能有效减少重建体数据量,实测数据表明体绘制速度明显提高。
工业CT;面绘制;体绘制;MC算法;光线投射算法
A
TP391.41
10.3778/j.issn.1002-8331.1204-0310
国家自然科学基金(No.61171177);山西省青年基金(No.2009021019-2)。
侯慧玲(1981—),女,博士研究生,讲师,主要研究方向:工业CT图像处理;王明泉(1970—),男,教授,博导,主要研究方向:信号与图像处理、分析与重建;任少卿(1980—),男,硕士,研究方向:图像处理与重建。E-mail:hou_huiling@126.com
2012-04-18
2013-12-10
1002-8331(2014)23-0172-04
CNKI网络优先出版:2013-12-19,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1204-0310.html