Fast 3D wavelet transform on multicore and many-core computing platforms

详细信息    查看全文

• 作者：V. Galiano (1)
  O. López-Granado (1)
  M. P. Malumbres (1)
  H. Migallón (1)
  
• 关键词：3D wavelet transform ; Video coding ; Parallel algorithms ; In ; place computing ; OpenMP ; CUDA ; GPU
• 刊名：The Journal of Supercomputing
• 出版年：2013
• 出版时间：August 2013
• 年：2013
• 卷：65
• 期：2
• 页码：848-865
• 全文大小：1245KB
• 参考文献：1. Campisi P, Neri A (2005) Video watermarking in the 3D-DWT domain using perceptual masking. In: IEEE international conference on image processing, September 2005, pp?997-000
  2. Schelkens P, Munteanu A, Barbariend J, Galca M, Giro-Nieto X, Cornelis J (2003) Wavelet coding of volumetric medical datasets. IEEE Trans Med Imaging 22(3):441-58 CrossRef
  3. Dragotti PL, Poggi G (2000) Compression of multispectral images by three-dimensional SPITH algorithm. IEEE Trans Geosci Remote Sens 38(1):416-28 CrossRef
  4. Aviles M, Moran F, Garcia N (2005) Progressive lower trees of wavelet coefficients: efficient spatial and SNR scalable coding of 3D models. Lect Notes Comput Sci 3767:61-2 CrossRef
  5. Podilchuk CI, Jayant NS, Farvardin N (1995) Three dimensional subband coding of video. IEEE Trans Image Process 4(2):125-35 CrossRef
  6. Taubman D, Zakhor A (1994) Multirate 3-D subband coding of video. IEEE Trans Image Process 3(5):572-88 CrossRef
  7. Shapiro JM (1993) Embedded image coding using zerotrees of wavelet coefficients. IEEE Trans Signal Process 41(12):1- CrossRef
  8. Said A, Pearlman A (1996) A?new, fast and efficient image codec based on set partitioning in hierarchical trees. IEEE Trans Circuits Syst Video Technol 6(3):243-50 CrossRef
  9. Oliver J, Malumbres MP (2006) Low-complexity multiresolution image compression using wavelet lower trees. IEEE Trans Circuits Syst Video Technol 16(11):1437-444 CrossRef
  10. Chen Y, Pearlman WA (1996) Three-dimensional subband coding of video using the zero-tree method. In: Visual communications and image processing. Proc SPIE, vol?2727, pp?1302-309 CrossRef
  11. Luo J, Wang X, Chen CW, Parker KJ (1996) Volumetric medical image compression with three-dimensional wavelet transform and octave zerotree coding. In: Visual communications and image processing. Proc SPIE, vol?2727, pp?579-90 CrossRef
  12. Kim BJ, Xiong Z, Pearlman WA (2000) Low bit-rate scalable video coding with 3D set partitioning in hierarchical trees (3D SPIHT). IEEE Trans Circuits Syst Video Technol 10:1374-387 CrossRef
  13. Lopez O, Martinez-Rach M, Pi?ol P, Malumbres MP, Oliver J (2010) Low bit-rate video coding with 3D lower trees (3D-LTW). Lect Notes Comput Sci 6077:256-63 CrossRef
  14. Wong T-T, Leung C-S, Heng P-A, Wang J (2007) Discrete wavelet transform on consumer-level graphics hardware. IEEE Trans Multimed 9(3):668-73 CrossRef
  15. Tenllado C, Setoain J, Prieto M, Pinuel L, Tirado F (2008) Parallel implementation of the 2D discrete wavelet transform on graphics processing units: filter bank versus lifting. IEEE Trans Parallel Distrib Syst 19(3):299-10 CrossRef
  16. Franco J, Bernabé G, Fernández J, Acacio ME, Ujaldón M (2010) The GPU on the 2D wavelet transform. survey and contributions. In: Proceedings of para 2010: state of the art in scientific and parallel computing
  17. Galiano V, López O, Malumbres MP, Migallón H (2011) Improving the discrete wavelet transform computation from multicore to gpu-based algorithms. In: Proceedings of international conference on computational and mathematical methods in science and engineering
  18. Franco J, Bernabé G, Fernández J, Ujaldón M (2010) Parallel 3D fast wavelet transform on manycore gpus and multicore cpus. Proc Comput Sci 1(1):1101-110 CrossRef
  19. Mallat SG (1989) A?theory for multi-resolution signal decomposition: the wavelet representation. IEEE Trans Pattern Anal Mach Intell 11(7):674-93 CrossRef
  20. OpenMP application program interface, version 3.1. OpenMP Architecture Review Board (2011). http://www.openmp.org
  21. ICC, intel software network. http://software.intel.com/en-us/intel-compilers/, 2009-011
  22. GCC, the GNU compiler collection. Free Software Foundation, Inc 2009-012 http://gcc.gnu.org
  23. Nickolls J, Buck I, Garland M, Skadron K (2008) Scalable parallel programming with cuda. In: Queue, vol?6, pp?40-3
  24. NVIDIA Corporation. Nvidia CUDA C programming guide. version 3.2
  
• 作者单位：V. Galiano (1)
  O. López-Granado (1)
  M. P. Malumbres (1)
  H. Migallón (1)
  
  1. Physics and Computer Architecture Dept., Miguel Hernández University, 03202, Elche, Spain
  

文摘

The three-dimensional wavelet transform (3D-DWT) has focused the attention of the research community, most of all in areas such as video watermarking, compression of volumetric medical data, multispectral image coding, 3D model coding and video coding. In this work, we present several strategies to speed up the 3D-DWT computation through multicore processing. An in depth analysis of the available compiler optimizations is also presented. Depending on both the multicore platform and the GOP size, the developed parallel algorithm obtains efficiencies above 95?% using up to four cores (or processes), and above 83?% using up to 12 cores. Furthermore, the extra memory requirements is under 0.12?% for low resolution video frames, and under 0.017?% for high resolution video frames. In this work, we also present a CUDA-based algorithm to compute the 3D-DWT using the shared memory for the extra memory demands, obtaining speed-ups up to 12.68 on the many-core GTX280 platform. In areas such as video processing or ultra high definition image processing, the memory requirements can significantly degrade the developed algorithms, however, our algorithm increases the memory requirements in a negligible percentage, being able to perform a nearly in-place computation of the 3D-DWT whereas in other state-of-the-art 3D-DWT algorithms it is quite common to use a different memory space to store the computed wavelet coefficients doubling in this manner the memory requirements.