海量断层数据的三维重建算法优化
|
摘要
MC(Marching Cubes)算法作为一种经典的三维重建算法,得到了广泛的应用。但针对海量断层数据,采用MC算法进行三维重建时,存在很多问题:如拓扑关系的求解,算法程序效率的提高等等。因此,三维重建算法的优化问题便成为当前研究的一个热点。
文章首先介绍MC算法的基本原理与实现流程,然后介绍采用MC算法进行三维重建的主要流程,并简单介绍了构网、平滑、简化、合并这几个关键步骤。其中,平滑、简化、合并这三个步骤都是基于包含拓扑信息的网格数据进行的,因此需要对传统的构网算法实施改进:使之能够在构网的同时同步取得各三角面片间的拓扑关系。
拓扑关系的取得,比较有效的方法是边构网边获取,但对于海量断层数据,这一方法面临计算资源与计算规模之间的矛盾,为了解决这一矛盾,文章提出了“双缓存、三层交换”的方法对构网关键算法进行优化,使得算法程序既能满足海量断层数据处理的要求,又能满足算法程序性能的要求。文章着重分析了这一方法的机理与实现流程,最后结合实际数据对算法程序性能进行对比分析,得出结论。
从结论分析可以得出,针对海量断层数据处理,利用MC算法进行三维重建时,“双缓存、三层交换”的机制确实能在一定程度上给算法程序的性能带来提升,能够达到优化算法的目的。
MC (Marching Cubes) is a popular 3-D surfaces reconstruction algorithm. But for huge segment datasets, thers is many problems for this typical algorithm, such as realized method is complex and performance of algorithm program is inefficient. So how to improve the effect of the algorithm program is a hot topic.
Because the data used for reconstruction is very huge, the reconstruction and its optimizing operation base on these data is very complex and inefficient. So it’s very important to study 3-D surfaces reconstruction algorithm optimization.
This paper introduces the basic principles of MC algorithm and implementation processes firstly. Secondly, it introduces the key steps of digital virtual human 3-D surfaces reconstruction using MC algorithm, which includes reconstruction,smooth, simplification,combinations and so on. The implementation of last three steps bases on the topological relationship of the triangles,so we must obtain the topological relationship of triangles while reconstructing.
The more effective method of obtaining the triangles topological relationship is computing while creating triangles. But for massive slice dataset processing,this method is inefficient. In order to solve this problem,this paper presents a "double cache,three layer switching "method. Practice shows it can make a high performance while processing massive slice dataset.
文章首先介绍MC算法的基本原理与实现流程,然后介绍采用MC算法进行三维重建的主要流程,并简单介绍了构网、平滑、简化、合并这几个关键步骤。其中,平滑、简化、合并这三个步骤都是基于包含拓扑信息的网格数据进行的,因此需要对传统的构网算法实施改进:使之能够在构网的同时同步取得各三角面片间的拓扑关系。
拓扑关系的取得,比较有效的方法是边构网边获取,但对于海量断层数据,这一方法面临计算资源与计算规模之间的矛盾,为了解决这一矛盾,文章提出了“双缓存、三层交换”的方法对构网关键算法进行优化,使得算法程序既能满足海量断层数据处理的要求,又能满足算法程序性能的要求。文章着重分析了这一方法的机理与实现流程,最后结合实际数据对算法程序性能进行对比分析,得出结论。
从结论分析可以得出,针对海量断层数据处理,利用MC算法进行三维重建时,“双缓存、三层交换”的机制确实能在一定程度上给算法程序的性能带来提升,能够达到优化算法的目的。
MC (Marching Cubes) is a popular 3-D surfaces reconstruction algorithm. But for huge segment datasets, thers is many problems for this typical algorithm, such as realized method is complex and performance of algorithm program is inefficient. So how to improve the effect of the algorithm program is a hot topic.
Because the data used for reconstruction is very huge, the reconstruction and its optimizing operation base on these data is very complex and inefficient. So it’s very important to study 3-D surfaces reconstruction algorithm optimization.
This paper introduces the basic principles of MC algorithm and implementation processes firstly. Secondly, it introduces the key steps of digital virtual human 3-D surfaces reconstruction using MC algorithm, which includes reconstruction,smooth, simplification,combinations and so on. The implementation of last three steps bases on the topological relationship of the triangles,so we must obtain the topological relationship of triangles while reconstructing.
The more effective method of obtaining the triangles topological relationship is computing while creating triangles. But for massive slice dataset processing,this method is inefficient. In order to solve this problem,this paper presents a "double cache,three layer switching "method. Practice shows it can make a high performance while processing massive slice dataset.
引文
[1] W. E. Lorensen, H. E. Cline. Marching Cubes: A High- Resolution 3-D Surface Construction Algorithm. Computer Graphics, 1987, 21(4): 163~169
[2] Gregory M. Nielson. On Marching Cubes. Visualization and Computer Graphics, 2003, 9(3): 283~297
[3]高蕾娜,何建英.医学断层图像三维重构的研究及应用.机械与电子, 2005, 3: 77~78
[4]安新伟,张晓兵,尹涵春.医学图像三维重建的研究.电子器件, 2001, 24(3): 207~211
[5]万里洲,王博亮,黄绍辉.三维重建中表面平滑算法的应用研究.厦门大学学报, 2002, 41(1): 17~19
[6]崔世华,刘杰.两种简化标准Marching Cubes算法拓扑构形的方法.系统仿真学报, 2006, 18(1): 336~339
[7]李华,蒙培生,王乘.医学图像重建MC算法三角片的合并与实现.计算机应用, 2003, 23(6): 104~105
[8]宋卫卫,李冠华,欧宗瑛.医学体数据三维可视化技术.计算机工程与应用, 2006, 18: 22~26
[9]断宝山,潘振宽.医学断层图像三维重建的辅助轮廓线法.计算机辅助设计与图形学学报, 2005, 17(8): 208~211
[10]朱志峰,余德义.利用OPENGL技术开发3D飞行仿真应用程序.计算机仿真, 2005, 21(3): 194~196
[11]郭旭升.基于PC图形硬件的直接体绘制技术综述.微计算机应用, 2006, 27(5): 517~520
[12]王征,章品正,周正东等.基于投影法的四面体网格切割算法.数据采集与处理, 2006, 21(4): 423~427
[13]权勇,李文辉,庞云阶.利用表面元素绘制图形的方法.吉林大学学报, 2004, 42(4): 554 558
[14]邓福庆,尚晓军,卢茁.中国教育科研网格:促进教育信息资源的优化和全面发展.思想政治教育研究, 2006, 5: 12~14
[15]杨廷武.数字化虚拟人向我们走来.科技时空, 2005, 10
[16] G. Wyvill, C. McPheeters and B. Wyvill. Data structures for soft objects. The VisualComputer 1986, 2(4): 227~234
[17] J. Wilhelms and A. Van Gelder. Topological Considerations in Isosurface Generation. Computer Graphics 1990, 24(5): 79~86
[18] W. J. Schroeder, J. A. Zarge. Decimation of triangle meshes. Computer Graphics, 1992, 26(2): 65~70
[19]笪良龙,杨廷武,李玉阳等.基于PC硬件加速的三维数据场直接体可视化.系统仿真学报, 2005, 17(10): 2422~2425
[20]沈振强,陈婷.三维医学图像MC表面重建的相关性处理.大学时代下半月, 2009, 9
[21]梁秀霞,张彩明,刘,毅等.拓扑结构正确的三线性插值曲面的三角片逼近.计算机研究与发展, 2006, 43(3): 528~535
[22] Evgeni V. Chernyaev. Marching Cubes 33: Construction of Topologically Correct Isosurfaces. Computer Graphics, 1989, 21(3): 163~169
[23] G. M. Nielson, B. Hamann. The Asymptotic Decider Resolving the Ambiguity in Marching Cubes. Proceedings of Visualization, 1991: 83~90
[24]杨上供,王辉金,洪震. CT图像的计算机制全息三维重建.光电工程, 2006, 33(12): 22~26
[25]沃焱,韩国强,张见威.基于自适应预处理的图像分割方法.电子与信息学报, 2007, 2(1): 86~89
[26]刘秀文,解翠,金一丞.保持视觉外观特征的网格简化.计算机辅助设计与图形学学报, 2006, 18(11): 1664~1669
[27]何婧.地学三维建模技术.现代电子技术, 2006, 24: 33~36
[28] Wang J Y, Gao WJ. A singular boundary value problem for the one-dimensional p-Laplacian[J]. J Math Anal Appl, 1996, 201: 851~866
[29]孙增国,韩崇昭.基于Laplacian算子的图像增强.计算机应用研究, 2007, 1: 222~227
[30]李衷怡,胡薇.基于Globus Toolkit的网格服务实现.计算机与数字工程, 2006, 34(3): 10~12
[31]耿国华,赵杰,赵宗涛.医学图像处理中三维模型的快速重构与简化.西北大学学报(自然科学版), 2002, 32(3): 221~224
[32] TURK G. Retiling polygonal surface[J]. Computer Graphics, 1992, 26(2): 55~64
[33] HAMANN B. A data reduction scheme for triangulated surfaces[J]. CA GD, 1994, (11): 197~214
[34]李衷怡,胡薇,吴勇等.海量断层数据的三维重建.计算机工程与科学, 2006, 28(9): 38~40
[35] E Keppel. Approximating Complex Surfaces by Triangulation of Contour Lines[J]. IBM Journal of Research and Development, 1975, 19(1): 2~11
[36] G T Herman, H K Liu. Three-Dimensional Display of Human Organs from Computed Tomograms[J]. Computer Graphics and Image Processing, 1979, 9(1): 1~21
[37]江东,冯成德,林大全等.基于MC重建算法等值面的优化.中国测试技术, 2006, 32(1): 80~84
[38] Jane Wilhelms, Allen Van Gelder. Octrees for Faster Isosurface Generation[J]. ACM Transactions on Graphics, 1992, 11(3): 201~271
[39] Michael Laszlo. Fast Generation and Display of Isosurface Wi- reframes[J]. Computer Vision Graphics and Image Processing, 1992, 54(6): 473~483
[40]吴佩华,郭勇,漆锋滨.软件流水技术在GCC上的实现.高性能计算技术, 2004, 169: 1~5
[2] Gregory M. Nielson. On Marching Cubes. Visualization and Computer Graphics, 2003, 9(3): 283~297
[3]高蕾娜,何建英.医学断层图像三维重构的研究及应用.机械与电子, 2005, 3: 77~78
[4]安新伟,张晓兵,尹涵春.医学图像三维重建的研究.电子器件, 2001, 24(3): 207~211
[5]万里洲,王博亮,黄绍辉.三维重建中表面平滑算法的应用研究.厦门大学学报, 2002, 41(1): 17~19
[6]崔世华,刘杰.两种简化标准Marching Cubes算法拓扑构形的方法.系统仿真学报, 2006, 18(1): 336~339
[7]李华,蒙培生,王乘.医学图像重建MC算法三角片的合并与实现.计算机应用, 2003, 23(6): 104~105
[8]宋卫卫,李冠华,欧宗瑛.医学体数据三维可视化技术.计算机工程与应用, 2006, 18: 22~26
[9]断宝山,潘振宽.医学断层图像三维重建的辅助轮廓线法.计算机辅助设计与图形学学报, 2005, 17(8): 208~211
[10]朱志峰,余德义.利用OPENGL技术开发3D飞行仿真应用程序.计算机仿真, 2005, 21(3): 194~196
[11]郭旭升.基于PC图形硬件的直接体绘制技术综述.微计算机应用, 2006, 27(5): 517~520
[12]王征,章品正,周正东等.基于投影法的四面体网格切割算法.数据采集与处理, 2006, 21(4): 423~427
[13]权勇,李文辉,庞云阶.利用表面元素绘制图形的方法.吉林大学学报, 2004, 42(4): 554 558
[14]邓福庆,尚晓军,卢茁.中国教育科研网格:促进教育信息资源的优化和全面发展.思想政治教育研究, 2006, 5: 12~14
[15]杨廷武.数字化虚拟人向我们走来.科技时空, 2005, 10
[16] G. Wyvill, C. McPheeters and B. Wyvill. Data structures for soft objects. The VisualComputer 1986, 2(4): 227~234
[17] J. Wilhelms and A. Van Gelder. Topological Considerations in Isosurface Generation. Computer Graphics 1990, 24(5): 79~86
[18] W. J. Schroeder, J. A. Zarge. Decimation of triangle meshes. Computer Graphics, 1992, 26(2): 65~70
[19]笪良龙,杨廷武,李玉阳等.基于PC硬件加速的三维数据场直接体可视化.系统仿真学报, 2005, 17(10): 2422~2425
[20]沈振强,陈婷.三维医学图像MC表面重建的相关性处理.大学时代下半月, 2009, 9
[21]梁秀霞,张彩明,刘,毅等.拓扑结构正确的三线性插值曲面的三角片逼近.计算机研究与发展, 2006, 43(3): 528~535
[22] Evgeni V. Chernyaev. Marching Cubes 33: Construction of Topologically Correct Isosurfaces. Computer Graphics, 1989, 21(3): 163~169
[23] G. M. Nielson, B. Hamann. The Asymptotic Decider Resolving the Ambiguity in Marching Cubes. Proceedings of Visualization, 1991: 83~90
[24]杨上供,王辉金,洪震. CT图像的计算机制全息三维重建.光电工程, 2006, 33(12): 22~26
[25]沃焱,韩国强,张见威.基于自适应预处理的图像分割方法.电子与信息学报, 2007, 2(1): 86~89
[26]刘秀文,解翠,金一丞.保持视觉外观特征的网格简化.计算机辅助设计与图形学学报, 2006, 18(11): 1664~1669
[27]何婧.地学三维建模技术.现代电子技术, 2006, 24: 33~36
[28] Wang J Y, Gao WJ. A singular boundary value problem for the one-dimensional p-Laplacian[J]. J Math Anal Appl, 1996, 201: 851~866
[29]孙增国,韩崇昭.基于Laplacian算子的图像增强.计算机应用研究, 2007, 1: 222~227
[30]李衷怡,胡薇.基于Globus Toolkit的网格服务实现.计算机与数字工程, 2006, 34(3): 10~12
[31]耿国华,赵杰,赵宗涛.医学图像处理中三维模型的快速重构与简化.西北大学学报(自然科学版), 2002, 32(3): 221~224
[32] TURK G. Retiling polygonal surface[J]. Computer Graphics, 1992, 26(2): 55~64
[33] HAMANN B. A data reduction scheme for triangulated surfaces[J]. CA GD, 1994, (11): 197~214
[34]李衷怡,胡薇,吴勇等.海量断层数据的三维重建.计算机工程与科学, 2006, 28(9): 38~40
[35] E Keppel. Approximating Complex Surfaces by Triangulation of Contour Lines[J]. IBM Journal of Research and Development, 1975, 19(1): 2~11
[36] G T Herman, H K Liu. Three-Dimensional Display of Human Organs from Computed Tomograms[J]. Computer Graphics and Image Processing, 1979, 9(1): 1~21
[37]江东,冯成德,林大全等.基于MC重建算法等值面的优化.中国测试技术, 2006, 32(1): 80~84
[38] Jane Wilhelms, Allen Van Gelder. Octrees for Faster Isosurface Generation[J]. ACM Transactions on Graphics, 1992, 11(3): 201~271
[39] Michael Laszlo. Fast Generation and Display of Isosurface Wi- reframes[J]. Computer Vision Graphics and Image Processing, 1992, 54(6): 473~483
[40]吴佩华,郭勇,漆锋滨.软件流水技术在GCC上的实现.高性能计算技术, 2004, 169: 1~5