The previous papers of the authors offer approach to building the ordered sequence of image pixels at lossless compression, which comprises methods of cascading fragmentation and the use of bypasses code book. For fragment sized 6*6 the code book contains 22144 various bypasses, the cost of coding to be estimated for every one of them. The search of optimal bypass is an exhaustive search type. The present paper describes ways of increasing the image lossless compression rate by using parallel computation based on OpenCL. Algorithm functions with great runtime were changed in order to transfer calculations to OpenCL using GPU/CPU. The acceleration degree for different algorithm functions gained in experiments amounted to 3..32.
The basic algorithm inherently consists in cascading fragmentation of image [
The runtime of image compression program depends on the processed image size. Due to a number of algorithmic solutions
such as cascading fragmentation, and the use of bypasses codebook instead of calculating the possible bypasses for each image
fragment, the runtime was reduced. However, the image compression duration is still high enough [
In computational terms the most complex of the basic algorithm functions is to estimate the encoding cost for all possible bypasses. Meanwhile, this algorithm function is suitable for parallelization, since the optimal bypass choice uses exhaustive search of obtained cost estimates. For a fragment sized 6*6 the total bypasses number from the upper left corner is 22144.
To use all multi-core CPU resources it is necessary to effectively implement paralleling of functions between all cores. The basic program features parallel execution of optimal fragment bypass search cycle done with .Net Framework standard classes (SSE instructions). It is possible to use a more powerful CPU, but even in this case, the speed increase will not be significant.
In recent years the increasing number of programs with parallel data processing use GPU computing [
Taking into account the above said, it was decided to move part of the compression algorithm functions to GPU. Obviously, this will require some significant changes in the functions, but it will allow for significant decrease in the program runtime without changing the basic algorithm.
Currently there are several approaches to programs execution on GPU. OpenCL is an open standard [
At the moment there exist quite a big number of various compression algorithms in general and algorithms for images in
particular. Images compressed both as lossy and lossless are widely and effectively used. For example, lossless compression is
used in PNG files where the actual compression is implemented with Deflate algorithm [
In addition to the basic algorithm, image preprocessing was implemented which was described in the authors’ previous
works: interchannel decorrelation of image color layers [
g n i s s e c o p e r P
decorrelation of
color layers Transformation based on integervalued wavelet Haar s e s s a p y b e l b i s s o p ll a r o f t s o c g n i d o c n e f o n o i t a l u c l a C
encoding cost
for bypass Search the minimum cost among the possible bypasses t n e m g a r f f o s s a p y b l a t p o r o f h c r a e S m i
End s s a p y b f o g n i d o c n E
to OpenCL. Image compression algorithm is shown in Fig. 1. 3.1. Preparation of fragments
The function receives separate color layers of an image. The function output is arrays of separate fragments of fixed size.
Pixel values of the fragment nodes beyond the image borders are virtual pixels and the values of these pixels are set as constant
(white pixels on Fig. 2). The top left pixels of each fragment on level 0 constitute the fragments on level 1 and so on, as long as
the fragments number on a level is more than one. Data structure passed to the OpenCL kernel represents the matrix of image
values, the output structure is the array of separate fragments [
This function is designed to calculate the interchannel decorrelation between the groups of color channels (layers) of the
original image and to find the best variant to group them [
When function is started the arrays containing pixels values of all color channels of the fragment, and also the number of channels have to be conveyed (Fig. 3). In addition, data on the possible grouping of channels is needed.
Formula for calculating interchannel decorrelation for arbitrary channels number based on the mean and interchannel
differences is applied [
The color channels can be independent from each other, therefore, the grouping variant with a minimum encoding costs estimate has to be selected. It is necessary to implement the decorrelation formulas for all dependent channels groups. The minimum channels number in the group is 2. If the image consists of 3 channels (24 bits per pixel), we get the following grouping variants: ( ) ( ) ( ) ( ) = argmin ∑ ∑ ∑
Cost where decorrelation formulas are to be applied to groups of channels in parenthesis.
The calculation of decorrelation is performed for all possible groups (g=1..G). The result is the index of g grouping: where Pij – is the pixel value after the interchannel decorrelation for the grouping index g; i– channel index; j– pixel index; n– number of channels; k– number of pixels number in the fragment.
Cost is the a some estimation function of encoding costs estimate, for example, the length of the Fibonacci code which encoding the value Pij value, or the estimated length of binary coding: log
=x − Round
a=c h= − Round( ⁄2) + v= − Round( ⁄2) + d=c − + be carried out as multiresolution at multiple scale, by repeating the transform on the blocks consisting of grouped values ai, each time and reducing their size in 2 timesby half for in each coordinate every time, as long as it is possible to form 2*2 block from ai values on a subsequent scale. Cascading transform will stop then the block ai with size 2*2 is absent.
It should be noted that when with the fragment sized of 2m*2m it is possible to use preprocessing (interchannel decorrelation, and Haar transform) after the function of dividing on the fragmentations. In this case, the Haar transformation is possible only within the same fragment. With In this approach, the fragment encoding is completely independently of the other fragments and therefore the decoding is possible for a single fragment.
1 x 1 prerequisite for encoding and decoding., but not the edges of bypass (path). 3.3.1.2. Computing the delta-code of bypasses edges
This function is designed to calculate the difference of values for all pairs of nodes that make up the edge on a given fragment
bypass [
= start( ) − stop( ) wWhere xstart(e), xstop(e) areis the pixel values are connected by an edge e; start(e) and stop(e) are- nodes indeixes of edge e. 3.3.1.3. Calculation of encoding costs for bypass
For each fragment, estimates the encoding costs for each of the possible bypasses are calculated. The function receives the previously prepared fragments and details data onof all the fragment bypasses in afrom the codebook. (5) (6) (7) Примечание [K2]: Resolution не уверена насколько здесь обосновано применять его в значении масштаб???
The result is the fragment-specific array containing estimated encoding costs for each bypass of the fragment (fFig. 5, tTable 1).
Estimationg of the encoding costs of a bypass through all edges (with its all delta-codes) of bypass edges it is possible to producecan be done in different ways. The cost of bypass fFor each fragment is needhas to findbe found the cost of the bypass: = ∑ 3.3.2. Search of the minimum among the possible bypasses smallest estimate for each fragment is picked and saved.
= argmin( ) where E is– the length of bypass (the number of edges); e - edge index; S -– the number of bypasses; s - bypass index; ∆e delta-code of edge; zes – presence of thean edge e in bypass s; Cost – is the somean estimation function of encoding costs, it is similar to the Cost in interchannel decorrelation function.
It should be noted that the estimate of bypasses encoding costs based on the table 1 is effective from the point of view of parallel computing. In tThis function there isrelies on parallel processing of all possible bypasses downloaded from the codebook, for all fragments making up, forming the processed image.
After the estimates of encoding costs of all paths is selectedare estimated, and the save path of each fragment bypass with the (8) (9) x x x 1 e 4 e 3 8 e e 1 6 7 e 11 x x 2 e 5 e 4 9 x 8 e e 2 7 e 12 x x 3 e 6 e x 9 5 10 x x x 1 z
1
4
z
8
7 z
z
6
11
x
x
5
x
2 z
2
z
7
8 z
12
3
z
5
x
x
x
6
9
which employs using a more sophisticated method [
Image Processing, Geoinformation Technology and Information Security / A. Khokhlachev, V. Smirnov, A. Korobeynikov 1.1.1.3.4.1. Encoding of bypass edge with different predictors and encoders
In the simplest most common case, the edge delta-code described above is used as the a predictor uses the edge delta-code
described above, and Fibonacci codes are used as encoders uses the Fibonacci codes [
In this embodiment,This variation of compression algorithm to encode with which each bypass edge is encoded uses the most
optimal encoding parameters (predictor/encoder) based ondefined by dynamic programming [
In the result tThe function creates produces a data file containing information with on the size of the encoded using encoders
predictors values for edges and additional information – optimal switching of the predictors/encoders for edges of bypass
encoding [
Due to the complexity of the dynamic programming algorithm it was found possible to transfer toto run on OpenCL managed to transfer only a small part, responsible for the coding directly to OpenCL. This part contains branching, and is switching large sections of the algorithm takes place. These operations are an integral part of the algorithm, or changand changinge the calculations flow in aim of parallel execution without the use of branches is not possible.
Screen formThe interface of the developed software is shown in Fig. 6. The program displays the following information: used hardware processor deviceprocessing unit and software platform being used; the number of files to be processed; the current processed file; the execution duration time of the compression program particular functions; the execution duration ofoverall compression time; the compression ratio.
To useHardware requirements for OpenCL acceleration requires the presence ofare GPU or CPU with support of OpenCL
1.2 [
To The compilatione of the developed image compression program requires the following software components [
The basic program required about 250 MB of RAM. When algorithm wasTo adapted the algorithm for accelerating on OpenCL was added usinglarge-volume arrays were addedof large volume and hence memory required demand increased to 900 MB. Отформатировано: многоуровневый + Уровень: 3 + Стиль нумерации: 1, 2, 3, … + Начать с: 1 + Выравнивание: слева + Выровнять по: 0 см + Отступ: 0 см Image Processing, Geoinformation Technology and Information Security / A. Khokhlachev, V. Smirnov, A. Korobeynikov
Fig. 6. Screen formInterface of the developed software.
Test batch sample of images designed is intended to assess acceleration of all core functions of modified program in comparing withrelative to basic one. To estimate the dependence of the program speed runtime on the to images size, the batch have the images of different sizes are sampled. To check usedFor test purposes 4 images from the standard set provided by the Institute of signal processing and images processing were used: 4.1.06.tiff, 4.2.05.tiff, 4.2.06.tiff, 4.2.07.tiff. The color depth of the images are is 24 bit. Image sizes are: 256*256, 512*512, 1024*1024, 2048*2048.
At tTesting was performed using image compression was performed with bothas the the basic program on the CPU AMD Phenom II X4 955 platform and a program using OpenCL. For testing OpenCL parallel processing was used different 4 different devices were used: 1) GPU AMD Radeon HD6850; 2) GPU Nvidia GTX 960; 3) CPU AMD Phenom II X4 955; 4) CPU AMD FX-4300. The time spent on the particular functions of the algorithm, and the total processing time for each image are given in Table 2 and Fig. 7, where F1is - integer-valued Haar transform, F2 -– interchannel decorrelation of color layers, F3 - search of the optimal bypass, F4 - encoding bypass using dynamic programming.
When testing for eEach fragment hadwas fixed size: 6*6 pixels, and the number of bypasses: 22144 at testing.
It should be noted, that when using thewith GPU Nvidia GTX 960 configuration,, according to Profiler, the load does not exceed 60% while despite numerous sthe high number of processing devices and high work frequency. , according to Profiler the load does not exceed 6 Compression The image of size 2048*2048 pixels size could not be compressed on the GPU AMD Radeon HD6850 failed to produce due to the lack ofinsufficient graphics memory. In the future, to avoid this situationsuch failures, the necessary modification of the program needs to be modified: to run the performed calculations flow should be divided into several groups threads and processed sequentially.
In the basic program were not implementedthe functions of the integer-valued Haar transform and the interchannel decorrelation were not implemented, and therefore, testing of these functions was not carried out.
Testing showed yielded approximately the same reduction in the compression total overall compression time when usingwith both CPU and GPU application. The larger the size of the processed image, the greater the acceleration obtained as long as there is memory available to for OpenCL.
GPU showed the best resultsperformed better in the for searching of the optimal bypass task. CPU well with the function of handles dynamic programming well, due to because of presences of a large number of branches in the function, despite the small number of processorof processor cores.
Time spent on cCalculatingons of interchannel decorrelation and integer-valued Haar transform is performed using OpenCL for a short timeis insignificant compared to total compression time. program / device
L C n e p O n o m a r g o r P
AMD Radeon HD 6850 Nvidia GeForce GTX 960 AMD FX-4300 AMD Phenom II
X4 955 Basic program / AMD Phenom II X4 955 size, pixels
In the course of this work was modified the basic program forof lossless image compression without losseswas modified, with the aim of increasing shortening its runtimethe speed. The pParallel processing based on OpenCL was used for program acceleration. This solution significantly affected the processing speed, enabling making it possible to reduce computational time. This modification will allow provide for more efficient use of the program in the future, will facilitate future further research aimed at improving the compression ratio.
The changing of optimal bypass search function allowed for to obtain the acceleration up to 32-fold acceleration on the large images. This acceleration has been achieved because of executing OpenCL functions executed on OpenCL are almost linear, and branching, even where they arewhen it is the case, is limited tohave only a few simple operations. Furthermore,For future program modification theto acceleratione of this function is important for future program modification because it is makes possible to use fragments of larger size that which was previously impossibleunattainable earlier due to too muchgreat execution time. Among other thingsMoreover, fragments with the sized of 2k*2k will effectivelyallow applying the integer-valued Haar transformation for the fragmentto them, and will allow to compressing every each fragment separately.
Somewhat worse is the situation withAs regards dynamic programming, the prospects are not as bright during encoding fragment bypass. Speed Performance managed to increase was gained mostly by due to ordinary conventional parallel execution of some operations, shutdown ofcancel of operations which need onlyused solely for debugging purposes, and the use of the packet data read operations. The part that runs on OpenCL gives the increase in performance is of only about 30% compared with to ordinary parallel computing. On the other hand, even this result is relatively good enough, given the factprovided that OpenCL function has rathera wide large enough branching. It should be nNoted that the bypass encoding can be performed in various ways, for example,e.g. with Huffman algorithm or arithmetic coding.