Design And Research Of Wavelet Mallat Algorithm And The Lifting Scheme Based On CUDA Platform

Image compression, an effective way of data compression, is becoming a hot research direction. The core algorithm of image compression is Discrete Wavelet Transform because of excellent spatial-frequency and time-frequency characteristics. But Wavelet Transform Mallat Algorithm has high computational complexity and memory occupation. Therefore, researching on parallel implementation of Discrete Wavelet Transform has great theoretical value and practical significance. In this work, based on the goal of improving algorithm speed but few image losses, a kind of Lifting Scheme is proposed. In addition, analyze the parallelism of wavelet transform and Lifting Scheme. Meanwhile, parallel acceleration of algorithm was achieved under the CUDA platform.Mallat algorithm of 9/7 wavelet transform is based on convolution, filter coefficients and image data are floating-point. According to Mallat algorithm's characteristic and wavelet lifting's general steps, a kind of Lifting Scheme of 9/7 wavelet transform is proposed. The proposed Lifting Scheme has two prediction steps and two update steps, aiming to guarantee image signal's integrity. Experiments demonstrate that Lifting Scheme of wavelet transform can reconstruct image perfectly. Compared with Mallat algorithm, it has 3~4 times acceleration. Lifting Scheme has good performance.Based on convolution, Mallat algorithm has high computational complexity, but suitable for parallel implementation, this feature can make full use of the advantage of CUDA's multi-core computation. According to the above analysis, a method achieves a high degree of parallelism is proposed, which can make good use of the CUDA's multithread. The experimental result indicated that the Mallat algorithm on CUDA has obtained ten times or even several times the speed, and the acceleration will be improving with the increase of image resolution.Lifting scheme is in-place computation, which saves memory occupation, but the dependencies between neighboring items are not suitable for parallel implementation on CUDA. Studies show that the dependence of lifting scheme only exists between the prediction step and the update step, that is to say, prediction or update internal does not have any interdependence. Therefore, a parallel Lifting Scheme that separate parallel prediction step and parallel update step is proposed. The experimental results indicated that this kind of lifting scheme obtained satisfactory acceleration .The ADL algorithm which is anther kind of lifting scheme, in which the interpolation and directional lifting transform of ADL can be parallel on CUDA, but the degree of parallelism is not high, and the experiment results are unsatisfactory.