用户名: 密码: 验证码:
SHEAR-WARP算法的改进
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
本文主要基于CT医学断层数据来研究三维体绘制算法。三维体绘制算法是直接将体数据按一定的采样和映射规则合成,生成的图像具有更丰富的表现力。三维体绘制算法是当前研究的一个热点,被广泛应用于医学图像、CAD/CAM造型、工业设计、资源探测、虚拟现实等信息可视化领域。因此对三维可视化的研究,具有重要的学术意义和应用价值。
     Shear-Warp算法是被认为基于软件加速的最快的体绘制算法。本文主要对Shear-Warp算法的绘制质量和绘制速度两方面进行了深入的研究和探讨。
     在绘制图像质量方面,Shear-Warp算法为了取得较快的绘制速度而牺牲了图像质量。当用Shear-Warp算法进行绘制图像时,视线角度过大会使绘制生成的图像出现明显的波纹失真现象。主要原因是由于在重采样的过程中采样距离过大,违背了Nyquist采样定理,使得利用重采样的数据点无法恢复原来的数据信息。针对这个缺点,本文提出了一种消除Shear-Warp算法中波纹失真现象的新方法:基于插值逼近原理,先利用沿着主视方向相邻的四个原始采样点构造二次曲线;然后在构造的二次曲线上获得新采样点,再将新采样点添加相邻两层体切片之间来提高采样精度,达到消除波纹失真的目的。文中给出了加层原理、具体实现算法以及算法复杂度的分析。当然,在采用该方法改善绘制图像质量的同时,会影响到算法的绘制速度和消耗的空间。如何取得整体效果最佳的改进方法是我们以后要继续研究的问题。
     在绘制速度方面,Shear-Warp算法是最快的基于软件的体绘制算法,它对数据场和生成的图像采用一种巧妙的编码方式,在绘制的过程中,同时遍历数据场和图像,跳过数据场中透明的体素和图像中不透明的区域。这样大大加快了绘制速度。Shear-Warp是在单核CPU基础上,完全基于数据结构对算法的一种改进,与硬件完全无关。但是最近几年,随着多核CPU的普及,多核CPU在多任务处理和并行计算上体现出单核处理器无法比拟的优势,多核CPU逐渐取代单核CPU成为桌面和移动计算机的主流配置。因此针对多核CPU对体绘制算法进行速度优化十分必要。本文利用多线程、向量化运算等技术加速Shear-Warp算法,充分发挥多核CPU的特点,使其能够适应当前CPU的发展趋势,被更广泛的应用推广。
     本文利用CT医学断层数据对改进后的Shear-Warp算法进行了实验,实验结果表明,改进后的算法不论在图像质量方面还是绘制速度方面都取得了显著的改进。
The main research of this thesis is on the Direct Volume Rendering (DVR) based on the CT volume data sets. According to the certain sampling and rendering rules, Direct Volume Rendering algorithm directly render the volume data to get an image. DVR is one of the most important techniques in the field of information visualization which is widely used in medical image, CAD/CAM prototyping, industrial design, oil and gas exploration, virtual reality and so on. So the research on DVR is very significant in academia and practice.
     Shear-warp algorithm has been recognized as the fastest software-based rendering method. This paper mainly does some research on two aspects of Shear-warp: the rendering quality and the rendering speed.
     In the rendering quality aspect, Shear-warp algorithm loss the quality of the image for improving rendering speed. The big view orientation angle will cause serious staircasing phenomenon in the final image when we render the volume data set by Shear-warp algorithm The primary cause is that the resampling distance is so long that violate the Nyquist theorem in the resampling process. So the resampling data are unable to restore the original data message. In this paper we brought a new method for removing the staircasing phenomenon. Based on the theory of interpolation and approximation, a quadratic curve is constructed from four ordinal original sampling points along the viewing orientation. A new resampling voxel is obtained from the quadratic curve. Then a new slice is constructed between two original neighboring slices so that the sampling precision can be improved. Based on the new sampling slices, staircasing phenomenon can be reduced in Shear-warp rendering. In the paper we will show the adding slices principle, the specific algorithm and the complexity analysis. Surely, what we do to improve the image quality will affect the rendering speed and consume more space. How to get the best effect of the algorithm is still our further research.
     In the rendering speed aspect, Shear-warp algorithm employed a clever volume and image encoding scheme, coupled with a simultaneous traversal of volume and image that skips opaque image regions and transparent voxels. This will speed up the rendering speed. Shear-warp is totally based on the data structures to do some improvements that have nothing to do with the hardware. But recently, as the multi-core processor is more and more popular, it becomes the main stream processor in common PC and notebook. The multi-core processor has incomparable advantages to single-core processor in the aspect of multi-processing and Parallel Computation. It's very necessary for the volume rendering algorithm to be optimized based on multi-core CPU. In this paper we use multi-thread and vectorization methods to accelerate the Shear-warp algorithm which make full use of the multi-core CPU Characteristics. That makes it possible for the Shear-warp algorithm to become moreand more popular.
     In this paper, we do some experiments on the improved Shear-warp algorithmwith CT volume data sets. The experiment results show the efficiency of the improvements on both rendering quality and rendering speed.
引文
[1]田捷,包尚联,周明全.医学影像处理与分析,北京:电子工业出版社,2003.
    [2]韦巍,王国荣,姜立军.医学X射线图像三维重建技术,北京生物医学工程,2004.9.
    [3]管伟光,马颂德.体视化技术及其应用,电子工业出版社,1998,4.
    [4]康晓东.医学图像的数字化处理技术,北京:人民卫生出版社,2001.
    [5]杨广夫,靳宝善.磁共振诊断学,陕西:科学技术出版社,1991.
    [6]石教英,蔡文立.科学计算可视化算法与系统,北京:科学出版社,1996.
    [7]唐泽圣.三维数据场可视化,北京:清华大学出版社,1999.
    [8]Meibner M,Huang J,Bartz D,et.A practical evaluation of popular volume rendering algorithms.In:IEEE/ACM Symposium on Volume Visualization,Salt Lake City:Utah,2000,pp.52-63.
    [9]Zhou Y,Chen W,Tang Z.An elaborate ambiguity detection method for cpnstructing isosurface within tetrahedral meshes.Computer & Graphics,1995,19(3):355-364.
    [10]N.Max.Optical models for direct volume rendering.IEEE Transactions on Visualization and Computer Graphics,February 1995,1(2):99-108.
    [11]S.Jaffery,K Duta.Digital Reconstruction Methods for 3D Image Visualization,SPIE,1984,Vol.507.
    [12]T.Porter.Computer digital images.Computer Graphics,1984,18(3):253-259.
    [13]P.Sabella.A Rendering Algorithm for Visualizing 3D Scalar Fields,Computer Graphics,1988,22(4):51-58.
    [14]Tiede U,Schiemann T,Hoehne KH.High quality rendering of attributed volume data.In:Davd Ebert,ed.Proc IEEE Visualization' 98.Los Alamitos:IEEE Computer Society Press,1988,pp.255-262.
    [15]M.Levoy.Display of surfaces from volume data,IEEE CG & A,1988,8(3):29-37.
    [16]P.Sabella.A rendering algorithm for visualizing 3D scalar fields,Computer Graphics,1985,22(4):51-58.
    [17]R.A Drebin,L.Carpenter,P Hanraban.Volume rendering,Computer Graphics,1988,22(4):65-74.
    [18]N.Max,P.Hanrahan.Area and volume coherence for efficient visualization of 3D scalar functions,Computer Graphics,1990,24(5):27-33.
    [19]C.UPson,T.Faulhaber et aL.V_Buffer:visible volume rendering,Computer Graphics,1988,22(4):59-64.
    [20]L.Westover.Footprint evaluation for volume rendering,Computer Graphics,1990,24(4):367-376.
    [21]G.Cameron and P.E.Undrill.Rendering volumetric medical image data on a SIMD architecture computer,Proceedings of the third Eurographics Workshop on Rendering,1992,pp.135-145.
    [22]Philip Lacroute,Marc Levoy.Fast volume rendering using shear-warp factorization of the viewing transformation.Computer Graphics(ACM SIGGRAPH Proceedings),1994,pp.451-458.
    [23]J.Wilhelms and A.V.Gelder.A coherent Projection approach to direct volume rendering,Computer Graphics,1991,25(4):275-284.
    [24]Zhou Y.and Tang Z.S.,volume partioning:a coherent subvolume projection approach for volume rendering,Proceedings of Pacific Graphics'94,1994,pp.325-340.
    [25]Zhou Y.and Tang Z.S.,Construction of isosurfaces in tetrahedral meshes based on ambiguity detection.Proceeding of Pacific Graphics'94,1994,pp33-48.
    [26]Deng Z.H.Tang Z.S.,Xu M.H.,Color assignment and boundary sharpening in frequency somain volume rendering,Proceedings of Pacific Graphics'95,1995,pp.240-252.
    [27]邓俊辉,周嘉玉,唐泽圣.基于物质分类的频域体绘制算法,计算机学报,1996,19(8):576-586.
    [28]Akeley K,Reality Engine Graphics,Computer Graphics,Proceedings,1993,pp.109-116.
    [29]Marc Levoy.Efficient ray tracing of volume data.ACM Transactions on Graphics,July 1990,9(3):245-261.
    [30]Marc Levoy.Volume rendering by adaptive refinement.UNC Technical Report:88030,June 1988.
    [31]R.A Drebin,L.Carpenter,P.Hanrahan.Volume rendering.Computer Graphics,1988,22(4):65-74.
    [32]唐荣锡,汪嘉业,彭群生等.计算机图形学教程,科学出版社.pp.327-332.1990年4月.
    [33]唐泽圣.用图像空间为序的体绘制技术显示三维数据场.计算机学报,1994,17(11):801-808.
    [34]David Laur,Pat Harahan.Hierarchical splatting:A progressive refinement algorithm for volume rendering.Proceeding of SIGGRAPH'91.Computer Graphics,July 1991,25(4):285-288.
    [35]Philip Lacroute.Fast volume rendering using shear-warp factorization of the viewing transformation.Technical Report:CSL-TR-95-678,September 1995.
    [36]A.V.Aho,J.E.Hopcroft,J.D.Ullman.The Design and Analysis of Computer Algorithms,Addision-Wesley,Reading,MA,1974.
    [37]T.H.Cormen,C.E.Leiserson,R.L.Rivest.Introduction to Algorithms,MIT Press,Cambridge,MA,1990.
    [38]Sara Baase,Allen Van G-elder.Computer Algorithms,3rd edition,Addision-Wesley,Reading,MA,2000.
    [39]M.Meissner,J.Huang,D.Bartz,K.Mueller,and R.Crawfis,A practical comparison of popular volume rendering algorithms,Proc.2000 Symp on Volume Rendering[C],Salt-Lake City,October 2000,pp.81-90.
    [40]Zhang Yan-wei,Zhang Cai-ming.Using Virtual Slice Method to Improve Image Quality by Shear-warp Algorithm.Journal of System Simulation,2001,13(Supplement):85-89.
    [41]J Sweeney,K Mueller.Shear-Warp Deluxe:The shear warp algorithm revisited.Joint Eurographics-IEEE TCVG Symposium on Visualization 2002 Barcelona,Spain,2002,pp.95-104.
    [42] Hyman J.M. Accurate monotonicity preserving cubic interpolation. SIAM J. Sci. Statist. Comput, 1983, 4(4):645-654.
    [43] Su Buqing, Liu Dingyuan. Computational Geometry [M]. Shanghai: Science and Technology Press of Shanghai, 1981.
    [44] Shi Fazhong Computer Aided Geometric Design & NURBS[M] 2nd ed1 Beijing: Higher Education Press , 2001.
    [45] J. Wilhelms and A.V. Gelder, A coherent projection approach for direct volume rendering. Computer Graphics 25, 1991, pp.275-284.
    [46] H. Pfister, J. Hardenbergh, J. Knittel, H. Lauer, and L. Seiler. The volumepro real-time ray-casting system In Proceedings of SIGGRAPH, 1999, pp.251-260.
    [47] Grimm, et al. Memory efficient acceleration structures and techniques for CPU-based volume raycasting of large data[R].IEEE Symposium on Volume Visualization and Graphics 2004,October 11-12,Austin,Texas,USA,2004.
    [48] M. Meissner, U. Kanus, G.Wetekam, J. Hirche, A. Ehlert,W. Strasser, M. Doggett, P. Forthmann, and R. Proksa. Vizard II, a reconfigurable interactive volume rendering system. In Proceedings of the Eurographics Workshop on Graphics Hardware, 2002, pp. 137-146.
    [49] B. Cabral, N. Cam, and J. Foran. Accelerated volume rendering and tomographic reconstruction using texture mapping hardware. In Proceedings of the Symposium on Volume Visualization, 1994, pp. 91-98.
    [50] S. Guthe, M. Wand, J. Gonser, and W. Strasser. Interactive rendering of large volume data sets. In Proceedings of IEEE Visualization, 2002, pp. 53-60.
    [51] R. Westermann and T. Ertl. Efficiently using graphics hardware in volume rendering applications. In Proceedings of SIGGRAPH, 1998, pp. 169-177.
    [52] C. Rezk-Salama, K. Engely, M. Bauer, G. Greiner and T. Ertl. Interactive Volume Rendering on Standard PC Graphics Hardware Using Multi-Textures and Multi-Stage Rasterization proc. Eurographics/SIGGRAPH Workshop on Graphics Hardware 2000(HWWS00),2000.
    [53] Philippe Lacroute. Real-Time Volume Rendering on Shared Memory Multiprocessors Using the Shear-Warp Factorization. IEEE Parallel Rendering Symposium'95 Proceeding,1995,pp.15-22.
    [54]Intel Pentium D Processor 800 Sequence Datasheet from http://www.intel.com
    [55]Intel 64 and IA-32 Architectures Software Developer's Manuals from http://www.intel.com

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700