Context-based method for lossless compression of RGB and multispectral images A V Borusyak1, P A Pakhomov1, D Yu Vasin1 and V E Turlapov1 1 Lobachevsky State University of Nizhni Novgorod, Prospekt Gagarina 23, Nizhni Novgorod, Russia, 603952 Abstract. We consider the problem of compression of RGB and multispectral images by context-based methods. The algorithm' logic allows for its examination by using the example of full-color images as a particular case of multispectral images. The image-forming channels are divided into two groups: main and additional (detecting) channels. A distinguishing feature of the main channels is a significant correlation between neighbors. A number of variants of prediction from the adjacent channel for the main and additional channels for lossless image compression were considered. In the experiment on a series of images of different contents, the proposed algorithm showed a superior compression ratio in comparison with the popular WinRar, 7z, PNG archivers for all prediction variants. The leader among popular compression methods, JPEG-LS, was surpassed in the record configuration 2b on the image from the Landsat series by 40%. We expect to continue research on a wider sample of images and to use this algorithm to compress multispectral images with a greater number of channels. 1. Introduction Context-based modeling is an important step in high-performance lossless data compression. Serious advantages offered by high compression degree enable prediction based on the model of matching (coincidence) of contexts. These advantages were successfully demonstrated using the Prediction by Partial Matching (PPM) method published in 1984 [1] to solve the task of text compression. In 2005, the PPM method was significantly improved in [2] by mixing several contexts with weights that change during the method execution (based on machine learning methods). In this method, the model of each context independently estimates the probability and confidence that the next data bit will be 0 or 1. The forecasts are further weighed (the sum of the weights is 1), the weights are corrected by the prediction success criterion. Open source code (www.mattmahoney.net/dc) software (PAQ8) is implemented in the method. This software demonstrated a high rating in several independent tests. The wide use of this approach to images compression began around the early 2000s, but it was used primarily for binary images containing mostly text and lines [3]. It offered a compression improved by 14% compared with the analog and a 25% better performance. In 2002, a parallel algorithm for this method was developed [4]. In 2001, the context-based method was applied in the development of a new video coding standard for entropy estimation in the coding procedure using binary adaptive arithmetic coding technology, which increased the coding rate by 35% [5]. Of essential importance in the application of the context-based approach is the difference between images and texts consisting in the presence of noise in the images. Therefore, the result obtained in [6] in 2008 was very important for image compression: the prediction method for images with the help of IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) Image Processing and Earth Remote Sensing A V Borusyak, P A Pakhomov, D Yu Vasin and V E Turlapov Prediction by Partial Approximate Matching (PPAM) was presented. Unlike the PPM modeling method that uses exact contexts, PPAM introduces the notion of approximate contexts. Thus, PPAM models the probability of encoding a symbol based on its previous contexts, and contextual occurrences as a result are considered in an approximate manner. The method demonstrated competitive lossless compression and good performance when compressing images that have repeating areas with similar characteristics. However, the use of the context method for compressing color and multichannel images has remained complicated and ambiguous for a very significant reason: the effective definition and use of contexts for such images is a complex task, since in essence it is the compression of three or more images simultaneously. Nevertheless, in 2011, the publication [7] explored the prospects of using PAQ family methods in combination with machine learning (ML) methods for simple color images and for lossy compression. A number of problems were identified: 1) PAQ can be applied only to one- dimensional sequences, and the expansion for several sequences is not trivial (even in the case of identification of chicken carcass parts); 2) the authors were unable to construct parametric models of typical image contexts, which required for PAQ methods a huge storage capacity. In all four test images used to compare the PAQ-ML method with JPEG and JPEG2000, it was superior to JPEG2000 both in terms of the compression ratio and the quality of the compressed image. The method proposed by the authors showed a significant change in color amounting to the distortion of the palette, while JPEG2000 maintained the ratio of color channels in the local context, was able to locally parameterize the change of this ratio and thus proved to be the winner. It is also of interest to study the possibilities of using context-based compression methods for color (RGB) and multispectral images of Earth remote sensing (ERS). In the general case, ERS images are multi-channel, i.e. each pixel in the image is specified by the channel value vector. The early compression algorithms included, as a rule, independent operations on individual sample matrices, which were the matrices of the original image channels, or one, two or all the three RGB channels assigned to represent them. Therefore, the publications at that time primarily considered algorithms for processing single-channel (halftone) images, which are basic for implementing all compression methods. More recent publications are related to the compression of hyperspectral images, where the hierarchical compression method for both hyperspectral images (HSI) and for ERS as a whole occupies one of the leading positions [8], [9], [10]. In [9], the following statistical characteristics of the HSI are given: • the difference between the maximum and minimum brightness gradations reaches thousands and tens of thousands times; such images cannot be converted to "byte images"; • components are very dependent; intercomponent correlation is extremely high (above 0.95 for 85.2% of the pairs of neighboring components); • most components have high intracomponent correlation (above 0.85 for 87.4% of all components). In what follows, we will be guided by these considerations. The hierarchical multiscale representation is based on the results of a number of previous studies. It serves to solve not only the problem of ERS data compression, but also several other problems at the same time, such as the problem of compact storage and high-performance adaptive (in terms of permissible losses and the observer’s position) visualization of the terrain surfaces with a controlled value of distortions [11]. In this paper, we use a multi-scale wavelet representation of elevation data and a JPEG2000 encoder to compress 8-bit quantized height differences between their predicted and accurate values. This approach can be used without any significant changes to compress any channel (including the reference channel) of multi- and hyperspectral images. The high correlation of most of the neighboring HSI channels allows us to apply context-based compression methods at a new level and to use the previous high-correlation channel as the context for the current channel, which has been successfully realized and investigated in publications [9], [10]. The high correlation of the HSI channels has made it possible to bring the level of their lossless compression to the values of the order of 4-5. Unfortunately, it has not been possible so far to achieve this level for the compression of multispectral data, because the high correlation of neighbors is not a rule for such type of data. When IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 324 Image Processing and Earth Remote Sensing A V Borusyak, P A Pakhomov, D Yu Vasin and V E Turlapov considering the problem of compressing multispectral data, we will assume the channels of multispectral images to be unequal in terms of their information role in the summary image. One of the channels will be taken as the main (reference) channel, while the others will be used as: 1) special contrast channels for detecting objects of interest; 2) complementary channels, highly correlated with the reference channel (if any). For example, in the RGB image of an oasis in the desert, the yellow sand will be determined by almost identical maps of the red (reference) and green (complementary) channels, and the blue water will be determined by the contrast blue (water-detecting) channel. A similar situation would arise if we were to shift the infrared and ultraviolet (detection) channels to the visible region around the green (reference) channel. Obviously, for evolutionary reasons, the red or green channels are more acceptable to us as support channels. We will take one of them as a reference channel in a "conditionally RGB" image to be compressed, which is quite close to the method of "common reference" spectral components for compressing hyperspectral images [9]. The context- based method for compressing RGB and multispectral images proposed below is the development of an algorithm for adaptive compression of indexed and color images with the use of context modeling [12-14]. 2. The algorithm for lossless compression of RGB images Compression of each pixel is performed channel-by-channel. First, the color component responsible for the red color is compressed, next, the value of the color component of the green color is encoded, and then the value of the blue component is encoded. For each channel, its own context is formed. The structure for context storage is identical to the structure of the algorithm for indexed images [13,14]. For each channel, individual context models of the following orders are used: 6,4,2,1,0. The full-color probability coder (FPC) compression algorithm [14] is as follows: 3 separate keys of the current context and 3 independent forests of AVL-trees are used to store context models (for each of the RGB channels). The following actions are performed in the cycle:  A consecutive pixel is extracted from the input image file as a current one;  The maximum-order context (MOC) is formed as the current context: the contexts Cont1, Cont2, Cont3 of the maximum order are formed sequentially for the red, green and blue channels, respectively, as an array of unsigned one-byte integers storing the previous values of the corresponding channel of the current pixel.  The procedure of channel-by-channel coding of the current pixel value in the current context is performed (for details, see [13]);  If it is not possible to evaluate and encode the current channel value in the current context, since this value is encountered in the current context for the first time, a lesser order context is formed and this context becomes current, thus a return to point 3 occurs. This continues until the current value of the color component is encoded, which is guaranteed by the fact that occurrence counters for all pixel values in the context of the smallest (zero) order are initially assigned the value of unity. The descent to a lesser order context is realized by applying the exclusion technique, which allows, in case of departure to the contexts of a smaller order m, to exclude from consideration all the values of the pixel occurrence counters that are contained in the context model of the order r, 0