医学图像三维表面重建算法研究
|
摘要
科学计算可视化是计算机图形学的一个重要研究方向,它在各个领域都有着广泛的应用。在医学领域,人们利用可视化技术由二维医学断层图像序列构建特定组织或器官的三维模型,以辅助进行临床医学诊断。科学计算可视化技术的核心是三维数据场的可视化,即三维重建。结合国家自然科学基金项目《三维肿瘤概率映射辅助前列腺活组织穿刺取样方法研究》,对医学图像三维表面重建算法进行了研究,并实现了一个医学图像三维表面可视化系统。
三维表面重建可以分为基于轮廓线的表面重建和基于体素的表面重建。基于轮廓线的表面重建可以在轮廓线序列之间构建目标表面模型,采用此方法实现了前列腺的三维表面重建。其过程为先准确提取前列腺轮廓边缘,然后进行轮廓线插值,最后利用三角剖分算法构建出前列腺的三维表面模型,以辅助医生进行前列腺的活组织穿刺。
移动立方体是基于体素的经典表面重建算法,此算法可在由二维医学断层图像序列构成的高密度三维数据场中提取特定组织或器官的三维表面模型,被广泛地应用于医学领域。然而,移动立方体算法存在体素搜索冗余,生成三角面片过多等不足,导致重建速度偏慢。针对这些不足,提出了一种改进算法,并在三套数据集上进行了对比实验。实验结果显示,改进算法消耗时间大为减少,满足临床医学应用中的实时性要求。
三维模型在二维屏幕上显示需要经过一系列复杂的变换。OpenGL是一个性能优越的图形库,可实现三维图形的高效绘制。使用OpenGL对三维表面模型进行绘制,最后得到一个具有高真实感和操控性的三维模型,可以更好地在临床诊断中发挥作用。
Scientific computation visualization is a very important research direction in computer graphics, and is used in various fields now. People use visualization technology to construct the 3D model of some tissues and organs, and use it in clinical examination. 3D reconstruction is the core of scientific computation visualization. Research is done on 3D surface reconstruction of medical images and a 3D visualization system based on the project named on 3D Probability Model Assisted Prostate Tumor Biopsy Navigation System is implemented.
3D surface reconstruction can be based on contours and voxels. 3D surface reconstruction algorithms based on contours can construct 3D surface between series prostate contours. Firstly, edge detection and extraction should be done on series prostate images, and then, contours interpolation and triangles plotting must be implemented on series contours to construct the 3D surface model of prostate that can be used in the prostate tumor biopsy.
Marching Cubes is a classical 3D surface reconstruction algorithm based on voxels which can extract the 3D surface model from 3D medical data. However, this algorithm search lots of blank voxels and generate too many triangles, so it is time consumption. A new algorithm for overcoming the deficiencies is presented. As the experimental result proving, the new algorithm presented accelerates the reconstruction.
To display a 3D model on a 2D screen, a series of transform should be done. OpenGL is a widely used graphics interface lib that can render 3D scene efficiently. The 3D surface model rendered by OpenGL has high reality and manipulation that can play an important role in clinical diagnosis.
三维表面重建可以分为基于轮廓线的表面重建和基于体素的表面重建。基于轮廓线的表面重建可以在轮廓线序列之间构建目标表面模型,采用此方法实现了前列腺的三维表面重建。其过程为先准确提取前列腺轮廓边缘,然后进行轮廓线插值,最后利用三角剖分算法构建出前列腺的三维表面模型,以辅助医生进行前列腺的活组织穿刺。
移动立方体是基于体素的经典表面重建算法,此算法可在由二维医学断层图像序列构成的高密度三维数据场中提取特定组织或器官的三维表面模型,被广泛地应用于医学领域。然而,移动立方体算法存在体素搜索冗余,生成三角面片过多等不足,导致重建速度偏慢。针对这些不足,提出了一种改进算法,并在三套数据集上进行了对比实验。实验结果显示,改进算法消耗时间大为减少,满足临床医学应用中的实时性要求。
三维模型在二维屏幕上显示需要经过一系列复杂的变换。OpenGL是一个性能优越的图形库,可实现三维图形的高效绘制。使用OpenGL对三维表面模型进行绘制,最后得到一个具有高真实感和操控性的三维模型,可以更好地在临床诊断中发挥作用。
Scientific computation visualization is a very important research direction in computer graphics, and is used in various fields now. People use visualization technology to construct the 3D model of some tissues and organs, and use it in clinical examination. 3D reconstruction is the core of scientific computation visualization. Research is done on 3D surface reconstruction of medical images and a 3D visualization system based on the project named on 3D Probability Model Assisted Prostate Tumor Biopsy Navigation System is implemented.
3D surface reconstruction can be based on contours and voxels. 3D surface reconstruction algorithms based on contours can construct 3D surface between series prostate contours. Firstly, edge detection and extraction should be done on series prostate images, and then, contours interpolation and triangles plotting must be implemented on series contours to construct the 3D surface model of prostate that can be used in the prostate tumor biopsy.
Marching Cubes is a classical 3D surface reconstruction algorithm based on voxels which can extract the 3D surface model from 3D medical data. However, this algorithm search lots of blank voxels and generate too many triangles, so it is time consumption. A new algorithm for overcoming the deficiencies is presented. As the experimental result proving, the new algorithm presented accelerates the reconstruction.
To display a 3D model on a 2D screen, a series of transform should be done. OpenGL is a widely used graphics interface lib that can render 3D scene efficiently. The 3D surface model rendered by OpenGL has high reality and manipulation that can play an important role in clinical diagnosis.
引文
[1]管伟光.体视化技术及其应用.第一版.北京:电子工业出版社,1998.8~16
[2]唐泽圣.三维数据场可视化.第一版.北京:清华大学出版社,1999.1~190
[3] A. B. Ekoule, F. C. Peyrin, C. L. Odet. A Triangulation Algorithm from Arbitrary Shaped Multiple Planar Contours. ACM Transactions on Graphics,1991, 10(2):182~191
[4] H. Fuchs, Z. M. Kedem, S. P. Uselton. Optimal Surface Reconstruction from Planar Contours. Communications of ACM,1977,20(10):693~702
[5] J. D. Boissonnat. Shape Reconstruction from Planar Cross-Sections. Computer Vision, Graphics, and Image Processing,1988,44(1):1~29
[6] W. C. Lin. A New Surface Interpolation Technique for Reconstruction 3D Objects from Serial Cross-Sections. Computer Vision, Graphics, and Image Processing, 1989,48(1):124~143
[7] G. T. Herman, H. K. Liu. Three-Dimensional Display of Human Organs from Computed Tomography. Computer Graphics and Image Processing,1979,9(1):1~29
[8] W. E. Lorensen, H. E. Cline. Marching Cubes: A High Resolution 3D Surface Construction Algorithm. Computer Graphics,1987,21(4):163~169
[9]徐美和,唐泽圣,邓俊辉.用于构造等值面的剖分立方体算法的改进及应用.计算机辅助设计与图形学报,1997,9(3):233~240
[10] M. J. Durst. Letters: Additional Reference to Marching Cubes. Computer Graphics, 1988,22(2):128~133
[11] T. Itoh, Y. Yamaguchi, K. Koyamada. Fast Isosurface Generation Using the Volume Thinning Algorithm. Visualization and Computer Graphics,2001,7(1):32~46
[12] D. A. Rajon, W. E. Bolch. Marching Cube Algorithm: Review and Trilinear Interpolation Adaptation for Image-Based Dosimetric Models. Computerized Medical Imaging and Graphics,2003,27(5):411~435
[13] S. W. Lee, A. Senot, H. Y. Jung. Regularized Marching Cubes Mesh. Image Processing, 2005,3(11):788~791
[14] A. Doi, A. Koide. An Efficient Method of Triangulating Euqi-Valued Surfaces by Using Tetrahedral Cells. IEICE Transactions on Communications,1991, E74(1):214~224
[15] M. Levoy. Volume Rendering by Adaptive Refinement. The Visual Computer, 1990,6(1):2~7
[16] M. Levoy. Efficient Ray Tracing of Volume Data. ACM Transaction on Graphics, 1990,9(3):254~261
[17] Y. Zhou, Z. Tang. A Full Exploitation of Function Coherence for Volume Rendering. The Journal of Visualization and Computer Animation,1995,6(4):207~218
[18]李冠峰,黄毓瑜,杨光.体可视化的快速光线投射算法.工程图学学报, 2000,3(3):97~102
[19] P. Lacroute, M. Levoy. Fast Volume Rendering Using a Shear-Warp Factorization of The Viewing Transformation. Computer Graphics, 1994,28(4):451~458
[20] G. Dorn. Visualization in 3D Seismic Interpretation. The Leading Edge. 1995,14(9):1045~1049
[21] S. Doug. 3D Visualization Technology Application: Complex-Structure Interpretation, Journal of Pentecostal Theology,1997,4(1):73~79
[22] L. Westover. Interactive Volume Rendering. in: R. A. Robb ed. Proceedings of the Chapel Hill Workshop on Volume Visualization. University of North Carolina.1989. New York: ACM Press,1989.9~16
[23] L. Westover. Footprint Evaluation for Volume Rendering. Computer Graphics, 1990,24(4):367~376
[24] L. Yuan, W. H. Huang, L. Tang. Image Processing in Treatment of Digitized Virtual Chinese No.1 Female. Chinese Journal of Clinical Anatomy, 2003,21(3):193~196
[25]钱勇先,高智勇,林家瑞. MRI图像重建网格化算法的研究进展.国外医学生物医学工程分册,2001,4(24):38~43
[26] R. C. Gonzalez, R. E. Woods.数字图像处理.第二版.阮秋琦等译.北京:电子工业出版社,2003.463~473
[27] J. Canny. A Computational Approach to Edge Detection. Pattern Analysis and Machine Intelligences,1986,8(6):679~696
[28]章毓晋.图象分割.第一版.北京:科学出版社,2001.17~19
[29] M. Kass, M. Withkin, D. Terzopoulos. Snakes: Active Contour Models. International Journal of Computer Vision,1988,1(4):321~331
[30] S. S. Lyengar, W. Deng. An Efficient Edge Detection Algorithm Using Relaxing Labeling. Pattern Recongition,1995,28(4):519~536
[31] Y. P. Wang, S. L. Lee. Scale-Space Derived from B-Splines. Pattern Analysis and Machine Intelligneces,1998,20(10):1040~1055
[32] A. Goshtasby. Design and Recovery of 2D and 3D Shapes Using Rational Gaussian Curves and Surfaces. Intonation Journal of Computer Vision,1993,10(3):233~256
[33] A. Moghaddamzadeh, N. Bourbakis. A Fuzzy Region Growing Approach for Segmentation of Color Images. Pattern Recognition,1997,30(6):867~881
[34] D. Zugai, V. Lattuati. A New Approach of Color Images Segmentation Based on Fusing Region and Edge Segmentations Output. Pattern Recognition,1998, 31(2):105~113
[35] T. L. Chia, K. B. Wang, L. R. Chen. A Parallel Algorithm for Generating Chain Code of Objects in Binary Images. Information Sciences-Informatics and Computer Science, 2003,149(4):219~243
[36] M. Brejl, M. Sonka. Directional 3D Edge Detection in Anisotropic Data: Detector Design and Performance Assessment. Computer Vision and Image Understanding,2000,77(2):84~110
[37] H. Yamada, K. Yamamoto, K. Hosokawa. Directional Mathematical Morphology and Reformalized Hough Transformation for the Analysis of Topographic Maps. Pattern Analysis and Machine Intelligences,1993,15(4):380~387
[38] A. K. Sen, A. Bagchi, W. Zhang. Average-Case Analysis of Best-First Search in Two Representative Directed Acyclic Graphs. Artificial Intelligence,2004,155(1): 183~2006
[39] D. Eppstein, Z. Galil, G. F. Italiano. Separator-Based Sparsification II: Edge and Vertex Connectivity. SIAM Journal on Computing,1999, 28(1):341~381
[40] G. T. Herman, J. Zheng, G. A. Bucholtz. Shape-Based Interpolation. Computer Graphics,1992,112(3):69~79
[41] A. G.. Bors, L. Kechagias, I. Pitas. Virtual Drilling in 3-D Objects Reconstructed by Shape-Based Interpolation. in: F. Roli ed. Proceedings of the 4th International Workshop on Visual Form. Italy.2001.London: Springer-Verlag, 2001.729~738
[42] W. C. Lin, C. C. Liang. Dynamic Elastic Interpolation for 3D Medical Image Reconstruction from Serial Cross-Sections. Medical Imaging,1988,7(3):225~232
[43]邓小英,周振平,康春涛.一种用于CT片层间轮廓线插值的算法.吉林大学学报,2002,20(3):34~36
[44] D. Levin. Multidimensional Reconstruction by Set-Valued Approximation. IMA Journal of Numerical Analysis,1986,6(22):173~184
[45] S. P. Raya, J. K. Udupa. Shape-Based Interpolation of Multidimensional Objects. Medical Imaging,1990,9(3):32~42
[46] D. J. Burr. A Dynamic Model for Image Registration. Computer Graphics and Image Processing,1981,15(1):102-112
[47] C. Montani, R. Scateni, R. Scopigno. Discretized Marching Cubes. in: R.D. Bergeron, A. E. Kaufman eds. Proceedings of the Conference on Visualization. Washinton DC.1994.Los Angeles: IEEE Computer Society Press,1994.281~287
[48]陈传波,陆枫.计算机图形学基础.第一版.北京:电子工业出版社,2002.189~201
[49] S. Dave, W. Masoon, N. Jakie. OpenGL Programming Guide. 5th Edition. California: Addison-Wesley Press,2006.13~35
[2]唐泽圣.三维数据场可视化.第一版.北京:清华大学出版社,1999.1~190
[3] A. B. Ekoule, F. C. Peyrin, C. L. Odet. A Triangulation Algorithm from Arbitrary Shaped Multiple Planar Contours. ACM Transactions on Graphics,1991, 10(2):182~191
[4] H. Fuchs, Z. M. Kedem, S. P. Uselton. Optimal Surface Reconstruction from Planar Contours. Communications of ACM,1977,20(10):693~702
[5] J. D. Boissonnat. Shape Reconstruction from Planar Cross-Sections. Computer Vision, Graphics, and Image Processing,1988,44(1):1~29
[6] W. C. Lin. A New Surface Interpolation Technique for Reconstruction 3D Objects from Serial Cross-Sections. Computer Vision, Graphics, and Image Processing, 1989,48(1):124~143
[7] G. T. Herman, H. K. Liu. Three-Dimensional Display of Human Organs from Computed Tomography. Computer Graphics and Image Processing,1979,9(1):1~29
[8] W. E. Lorensen, H. E. Cline. Marching Cubes: A High Resolution 3D Surface Construction Algorithm. Computer Graphics,1987,21(4):163~169
[9]徐美和,唐泽圣,邓俊辉.用于构造等值面的剖分立方体算法的改进及应用.计算机辅助设计与图形学报,1997,9(3):233~240
[10] M. J. Durst. Letters: Additional Reference to Marching Cubes. Computer Graphics, 1988,22(2):128~133
[11] T. Itoh, Y. Yamaguchi, K. Koyamada. Fast Isosurface Generation Using the Volume Thinning Algorithm. Visualization and Computer Graphics,2001,7(1):32~46
[12] D. A. Rajon, W. E. Bolch. Marching Cube Algorithm: Review and Trilinear Interpolation Adaptation for Image-Based Dosimetric Models. Computerized Medical Imaging and Graphics,2003,27(5):411~435
[13] S. W. Lee, A. Senot, H. Y. Jung. Regularized Marching Cubes Mesh. Image Processing, 2005,3(11):788~791
[14] A. Doi, A. Koide. An Efficient Method of Triangulating Euqi-Valued Surfaces by Using Tetrahedral Cells. IEICE Transactions on Communications,1991, E74(1):214~224
[15] M. Levoy. Volume Rendering by Adaptive Refinement. The Visual Computer, 1990,6(1):2~7
[16] M. Levoy. Efficient Ray Tracing of Volume Data. ACM Transaction on Graphics, 1990,9(3):254~261
[17] Y. Zhou, Z. Tang. A Full Exploitation of Function Coherence for Volume Rendering. The Journal of Visualization and Computer Animation,1995,6(4):207~218
[18]李冠峰,黄毓瑜,杨光.体可视化的快速光线投射算法.工程图学学报, 2000,3(3):97~102
[19] P. Lacroute, M. Levoy. Fast Volume Rendering Using a Shear-Warp Factorization of The Viewing Transformation. Computer Graphics, 1994,28(4):451~458
[20] G. Dorn. Visualization in 3D Seismic Interpretation. The Leading Edge. 1995,14(9):1045~1049
[21] S. Doug. 3D Visualization Technology Application: Complex-Structure Interpretation, Journal of Pentecostal Theology,1997,4(1):73~79
[22] L. Westover. Interactive Volume Rendering. in: R. A. Robb ed. Proceedings of the Chapel Hill Workshop on Volume Visualization. University of North Carolina.1989. New York: ACM Press,1989.9~16
[23] L. Westover. Footprint Evaluation for Volume Rendering. Computer Graphics, 1990,24(4):367~376
[24] L. Yuan, W. H. Huang, L. Tang. Image Processing in Treatment of Digitized Virtual Chinese No.1 Female. Chinese Journal of Clinical Anatomy, 2003,21(3):193~196
[25]钱勇先,高智勇,林家瑞. MRI图像重建网格化算法的研究进展.国外医学生物医学工程分册,2001,4(24):38~43
[26] R. C. Gonzalez, R. E. Woods.数字图像处理.第二版.阮秋琦等译.北京:电子工业出版社,2003.463~473
[27] J. Canny. A Computational Approach to Edge Detection. Pattern Analysis and Machine Intelligences,1986,8(6):679~696
[28]章毓晋.图象分割.第一版.北京:科学出版社,2001.17~19
[29] M. Kass, M. Withkin, D. Terzopoulos. Snakes: Active Contour Models. International Journal of Computer Vision,1988,1(4):321~331
[30] S. S. Lyengar, W. Deng. An Efficient Edge Detection Algorithm Using Relaxing Labeling. Pattern Recongition,1995,28(4):519~536
[31] Y. P. Wang, S. L. Lee. Scale-Space Derived from B-Splines. Pattern Analysis and Machine Intelligneces,1998,20(10):1040~1055
[32] A. Goshtasby. Design and Recovery of 2D and 3D Shapes Using Rational Gaussian Curves and Surfaces. Intonation Journal of Computer Vision,1993,10(3):233~256
[33] A. Moghaddamzadeh, N. Bourbakis. A Fuzzy Region Growing Approach for Segmentation of Color Images. Pattern Recognition,1997,30(6):867~881
[34] D. Zugai, V. Lattuati. A New Approach of Color Images Segmentation Based on Fusing Region and Edge Segmentations Output. Pattern Recognition,1998, 31(2):105~113
[35] T. L. Chia, K. B. Wang, L. R. Chen. A Parallel Algorithm for Generating Chain Code of Objects in Binary Images. Information Sciences-Informatics and Computer Science, 2003,149(4):219~243
[36] M. Brejl, M. Sonka. Directional 3D Edge Detection in Anisotropic Data: Detector Design and Performance Assessment. Computer Vision and Image Understanding,2000,77(2):84~110
[37] H. Yamada, K. Yamamoto, K. Hosokawa. Directional Mathematical Morphology and Reformalized Hough Transformation for the Analysis of Topographic Maps. Pattern Analysis and Machine Intelligences,1993,15(4):380~387
[38] A. K. Sen, A. Bagchi, W. Zhang. Average-Case Analysis of Best-First Search in Two Representative Directed Acyclic Graphs. Artificial Intelligence,2004,155(1): 183~2006
[39] D. Eppstein, Z. Galil, G. F. Italiano. Separator-Based Sparsification II: Edge and Vertex Connectivity. SIAM Journal on Computing,1999, 28(1):341~381
[40] G. T. Herman, J. Zheng, G. A. Bucholtz. Shape-Based Interpolation. Computer Graphics,1992,112(3):69~79
[41] A. G.. Bors, L. Kechagias, I. Pitas. Virtual Drilling in 3-D Objects Reconstructed by Shape-Based Interpolation. in: F. Roli ed. Proceedings of the 4th International Workshop on Visual Form. Italy.2001.London: Springer-Verlag, 2001.729~738
[42] W. C. Lin, C. C. Liang. Dynamic Elastic Interpolation for 3D Medical Image Reconstruction from Serial Cross-Sections. Medical Imaging,1988,7(3):225~232
[43]邓小英,周振平,康春涛.一种用于CT片层间轮廓线插值的算法.吉林大学学报,2002,20(3):34~36
[44] D. Levin. Multidimensional Reconstruction by Set-Valued Approximation. IMA Journal of Numerical Analysis,1986,6(22):173~184
[45] S. P. Raya, J. K. Udupa. Shape-Based Interpolation of Multidimensional Objects. Medical Imaging,1990,9(3):32~42
[46] D. J. Burr. A Dynamic Model for Image Registration. Computer Graphics and Image Processing,1981,15(1):102-112
[47] C. Montani, R. Scateni, R. Scopigno. Discretized Marching Cubes. in: R.D. Bergeron, A. E. Kaufman eds. Proceedings of the Conference on Visualization. Washinton DC.1994.Los Angeles: IEEE Computer Society Press,1994.281~287
[48]陈传波,陆枫.计算机图形学基础.第一版.北京:电子工业出版社,2002.189~201
[49] S. Dave, W. Masoon, N. Jakie. OpenGL Programming Guide. 5th Edition. California: Addison-Wesley Press,2006.13~35