The paper deals with the problem of the enhancement of the operating speed of the algorithm of adaptive compression of binary bitmap images (BBI) on the basis of entropy coding using context simulation. The influence of the size of the maximal order context on the compression rate is considered. The enhancement of the speed of the algorithm depending on the number of the threads used is considered.
The development of specialized algorithms, targeted for a specific data type, remains relevant in many areas. These algorithms use the knowledge of the internal data structure to achieve a greater degree of compression. One of the important areas is the compression of monochrome black-and-white binary images (MBI). Among the most effective methods of compression of data with a certain structure and specificity there are contextual data compression techniques based on the PPM technique (Prediction by Partial Matching).
The PPM algorithm involves entropy coding using individual context models (CM) for each context, encountered in the stream of encoded data. Each CM includes the counters for all the characters, encountered after the corresponding context. At the same time, the implicit weighting of estimates is used for the application of the context models of several orders. The PPM model itself only predicts the value of a character, while the encoding itself is performed by an encoder using entropy coding algorithms, such as Huffman's algorithm and arithmetic encoding. this algorithm, as compared to the standard PPM algorithm, is the use of twodimensional binary context of a specific shape and size, instead of standard onedimensional context. The use of the property of the two-dimensionality of data in the process of image compression makes it possible to substantially improve the compression ratio, by taking into account the relationships between the neighboring pixels both in horizontal and vertical directions.
The algorithm uses a specific context shape and models of 31th, 11th, 7th, 4th and zeroth order. The B-tree storage structure is used for the efficient storage of context models in the memory.
The following techniques and methods are used in the algorithm: the proprietary algorithm of the estimation of the probability of escape, the method of exclusion of the last encountered symbol, the method of scaling the last encountered symbol using the chosen scaling factor, the modified method of information inheritance.
An arithmetic encoder is used as the entropy encoder. The decoding process is symmetric to the coding process.
The implementation of the algorithm has shown high efficiency in terms of the
compression ratio (Rc), but the time expenditures were too high. The time, required
for encoding, was reduced by 1.5-2 times by optimization of the computation [
This paper deals with the problem of the reduction of the algorithm run-time and RAM consumption. To further enhance the operating speed of the algorithm, the methods of the parallelization and reduction of the size of maximal order context (MOC) are proposed.
One way to enhance the speed of the algorithm is the optimization of existing
computations. As part of the work [
In order to optimize the computation function of a new MOC, the sequence order of the context pixels was changed from fixed, predetermined by a programmer, to serial row-major, from the leftmost pixel of the context, which is in line with the pixel to be encoded, to the rightmost, located as far as possible in vertical direction from the pixel to be encoded. This conversion made it possible to reduce the number of access operations to the image when calculating a new MOC from the value of the entire context to the value of the context in height. In the transition to a new line of the image, the fast computation was realized only for those context pixels that did not go beyond the boundaries of the image. A method of calculating lower order contexts, using the MOC calculated with the help of the predetermined mask, is proposed. A mask is a fixed list of serial numbers of MOC pixels, specified by a programmer.
In order to limit RAM consumption, the upper limit for the number of context models, stored in a context model tree, is introduced. When the predefined limit is exceeded, the tree of maximal order context models is purged completely.
A link to a parent context model was added to each context model, in order to accelerate the operation of identification of the parent context model, used in information inheritance and in the escape to the lower order contexts.
Initially, the algorithm used the AVL-tree structure to store the context models. Various options of the storage of the model tree were considered. As a result of the experimental testing, the B-tree turned out to be more efficient with respect to the operating speed, and it was taken as the basic structure for the storage of the context model tree.
The transition of the program to the Qt 4.8.3 programming environment made it possible to improve efficiency and make the program structure more flexible.
The procedure of the updating of the percentage indicator of the encoding/decoding process was also optimized to improve efficiency.
The above approaches made it possible to reduce significantly, by 1.5-2 times, the time, required for encoding/decoding. The RAM consumption was also limited. Despite the fact that the acceleration proved to be essential, the algorithm still was significantly slower than its counterparts. Due to that, the work on the improvement of the algorithm performance was continued.
One way to enhance the operating speed of programs is to identify the "hot spots of a program" or, in other words, the parts of the program code, consuming the most amount of computer resources. As a result of the research conducted by using a profiler, it was found, that most of the CPU time and RAM are consumed by the functions of calculating a new MOC and searching for a new CM in the CM tree. As noted above, these functions have already been optimized with respect to computation. However, it was noted, that MOC size has a strong influence on the operation of the said functions. Consequently, MOC size affects not only the compression ratio, but also the operating speed of the algorithm and the amount of memory consumed. It has been suggested, that in case of decrease in the MOC size to a certain level, Rc will be reduced slightly, but the compression rate will increase significantly. In view of this, the experiments were conducted to identify the dependence of Rc, compression time and RAM consumption on the MOC size. The results of this experiment are presented in Table 1. According to the experiments conducted, in case of the reduction of the size of the context to 15, the compression ratio is reduced slightly, while a significant decrease in the time required for compression and reduction of the amount of the RAM consumed are noted. The reduction of MOC size to less than 15 leads to a significant reduction in the compression ratio complete with less significant reduction in the RAM consumed and the time required for compression. In Tables 1-3, the rows correspond to the number of the compressed file, and the columns correspond to the size of the maximal order File\context 1 2 3 4 5 File\context 1 2 3 4 5 context. At the same time, the reduction of MOC size to below 20 almost does not affect the level of RAM consumption.
Modern computers are often equipped with processors, containing multiple cores,
which enables parallel computing. This feature is currently often used to speed up the
algorithms. In order to further enhance the coding/decoding speed, the possibility of
encoding and decoding BBI through the parallelization of processing into multiple
threads was implemented in the compression algorithm. The parallelization algorithm
for the compression of indexed images [
Where, in the first column of Tables 4 and 5 the number of threads used for image encoding is indicated. In the second and the third columns the corresponding encoding time in seconds is indicated for PC1 and PC2. The last column shows the Rc for this file, depending on the number of the threads used. This ratio depends on the number of threads, but doesn't depend on the computer used for encoding, so the two computers possess the same factors. It is seen from the experiments, that, as expected, 1 2 4 8 16 32 64 1 2 4 8 16 32 64 the optimal number of threads is equal to the number of cores in the system. Thus, the compression ratio reduces linearly, but very slightly, and at 64 threads, the losses less than 3% are observed, while at n-16 threads, the losses are less than 1%.
The problem of the enhancement of the operating speed of the algorithm of adaptive compression of binary bitmap images was considered. The experiments were conducted for the enhancement of the operating speed of the proposed algorithm by parallelizing the algorithm into several threads and reducing MOC size. Both approaches proved to be effective. The MOC size, the reduction to which greatly reduces the file encoding time and significantly reduces RAM consumption, while only slightly reducing the Rc, was identified. The experiments were conducted for parallelizing the algorithm into several threads. Using these two approaches together, it is possible to enhance the rate of compression to an average of 8 times on a computer with a 4-core processor, to reduce RAM consumption by 2 times, with the average Rc losses being less than 10%.
This work was supported by RFBR (Projects No. 13-07-00521-А and No. 13-0712211 OFI_M.)