Publication Details

The Parallel Algorithm for the 2D Discrete Wavelet Transform

BAŘINA David, NAJMAN Pavel, KLEPÁRNÍK Petr, KULA Michal and ZEMČÍK Pavel. The Parallel Algorithm for the 2-D Discrete Wavelet Transform. In: Ninth International Conference on Graphic and Image Processing (ICGIP 2017). Qingdao: SPIE - the international society for optics and photonics, 2017, pp. 1-6. ISBN 978-1-5106-1741-4. ISSN 0277-786X.
Czech title
Paralelní algoritmus pro 2D diskrétní vlnkovou transformaci
Type
conference paper
Language
english
Authors
Keywords

discrete wavelet transform, lifting scheme, multi-core processors, parallel architecture

Abstract

The discrete wavelet transform can be found at the heart of many image-processing algorithms. Until now, the transform on general-purpose processors (CPUs) was mostly computed using a separable lifting scheme. As the lifting scheme consists of a small number of operations, it is preferred for processing using single-core CPUs. However, considering a parallel processing using multi-core processors, this scheme is inappropriate due to a large number of steps. On such architectures, the number of steps corresponds to the number of points that represent the exchange of data. Consequently, these points often form a performance bottleneck. Our approach appropriately rearranges calculations inside the transform, and thereby reduces the number of steps. In other words, we propose a new scheme that is friendly to parallel environments. When evaluating on multi-core CPUs, we consistently overcome the original lifting scheme. The evaluation was performed on 61-core Intel Xeon Phi and 8-core Intel Xeon processors.

Annotation

The discrete wavelet transform can be found at the heart of many image-processing algorithms. Until now, the transform on general-purpose processors (CPUs) was mostly computed using a separable lifting scheme. As the lifting scheme consists of a small number of operations, it is preferred for processing using single-core CPUs. However, considering a parallel processing using multi-core processors, this scheme is inappropriate due to a large number of steps. On such architectures, the number of steps corresponds to the number of points that represent the exchange of data. Consequently, these points often form a performance bottleneck. Our approach appropriately rearranges calculations inside the transform, and thereby reduces the number of steps. In other words, we propose a new scheme that is friendly to parallel environments. When evaluating on multi-core CPUs, we consistently overcome the original lifting scheme. The evaluation was performed on 61-core Intel Xeon Phi and 8-core Intel Xeon processors.

Published
2017
Pages
1-6
Journal
Proceedings of SPIE, vol. 10615, no. 4, ISSN 0277-786X
Proceedings
Ninth International Conference on Graphic and Image Processing (ICGIP 2017)
Conference
International Conference on Graphic and Image Processing 2017, Qingdao, CN
ISBN
978-1-5106-1741-4
Publisher
SPIE - the international society for optics and photonics
Place
Qingdao, CN
DOI
UT WoS
000434707200060
EID Scopus
BibTeX
@INPROCEEDINGS{FITPUB11530,
   author = "David Ba\v{r}ina and Pavel Najman and Petr Klep\'{a}rn\'{i}k and Michal Kula and Pavel Zem\v{c}\'{i}k",
   title = "The Parallel Algorithm for the 2D Discrete Wavelet Transform",
   pages = "1--6",
   booktitle = "Ninth International Conference on Graphic and Image Processing (ICGIP 2017)",
   journal = "Proceedings of SPIE",
   volume = 10615,
   number = 4,
   year = 2017,
   location = "Qingdao, CN",
   publisher = "SPIE - the international society for optics and photonics",
   ISBN = "978-1-5106-1741-4",
   ISSN = "0277-786X",
   doi = "10.1117/12.2302881",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11530"
}
Files
Back to top