Traditional lossy image compression methods such as the JPEG [1] family of codecs or HEVC [2] are transform-based: They compress images by applying a cosine or wavelet transform and quantising the coefficients coarsely, which constitutes a loss of information in the frequency domain. In recent years, inpainting-based codecs [3] [4] [5] [6] [7] [8] [9] have challenged this concept. They discard information directly in the spatial domain by representing the images through a sparse subset of pixels also known as the inpainting mask or in short, the mask.
For decoding, they reconstruct the discarded information through inpainting. Especially for high compression ratios, they can outperform transform-based codecs.
However, these approaches require careful and unconstrained optimisation of both the positions and values of the known data [4, [10] [11] [12] [13] [14] . This creates a delicate compression problem: In general, storing optimised data is expensive. Additionally, any deviations, e.g. by inexact, cheaper positions, can also reduce the reconstruction quality during decompression. While having deviations in pixel values is feasible and many inpainting operators are robust under quantisation [6, 7, 9] , storing pixel locations is a much more sensitive task. Storing pixel locations is equivalent to storing a sparse binary image. Depending on the inpainting operator, the distribution of these points aligns with image structures or might be lacking obvious patterns (see Fig.2 ).
Most inpainting operators perform best for unconstrained, optimised data that are stored losslessly [7] . Consequently, many optimisation methods [4, [10] [11] [12] [13] [14] would benefit from codecs specifically aimed at optimised inpainting masks. Even beyond inpainting -based compression, unconstrained mask codecs could be useful for other applications such as storage of sparse image features (e.g. SIFT [15] , SURF [16] ). However, there is only a small number of publications [5, 7, 8] that directly address the compression of unconstrained masks. This is unsatisfactory.
To close this gap, we offer the first systematic review and in-depth analysis of suitable compression techniques from different fields and propose best practice recommendations for storing unconstrained masks. Our contributions are threefold:
We start with a systematic review of suitable coding strategies from different fields of compression. We cover dedicated positional coding strategies [5, 8] , image compression codecs (JBIG [17] , PNG [18] , JBIG2 [19] , DjVu [20] , BPG lossless [21] ), and state-of-the-art general purpose encoders (PAQ, LPAQ [22] ). In addition, we discuss how these approaches can be applied to different representations of the sparse binary images, such as run-length encoding and methods from data science like Coordinate List (COO) [23] and Compressed Sparse Row (CSR) [23] .
Afterwards we perform an ablation study of context mixing methods. Such approaches combine information from multiple sources of already encoded information to predict the remaining file content, thus increasing compression efficiency. In a top-down approach, we evaluate which parts of complex stateof-the-art methods like LPAQ2 [24] are useful. Moreover, we use a bottom-up strategy to construct a novel context mixing strategy that is simple, yet effective.
Finally we provide a methodical comparison of all existing and newly proposed methods from the previous two contributions w.r.t. compression efficiency and runtime. In our experiments, we choose the Kodak image dataset [25] , which is widely used in compression studies. In order to obtain meaningful results, we consider different densities of known data (1% through 10%) and different point distributions. We take into account random masks, results from probabilistic sparsification [11] with homogeneous diffusion [26] , and densification [27] with Shepard interpolation [28] . In total, this yields a database of 720 diverse real-world test images. This setup allows us to propose best practice recommendations based on our analysis.
Overall, our three contributions allow us to identify the coding methods that yield the best compression performance as well as the best trade-off between speed and coding efficiency.
During the last decade, inpainting-based compression has become a diverse field of research with many conceptually different approaches. While most of the existing works focus on the optimisation of known data and inpainting operators, they have also contributed some concepts for efficient storage methods.
1) Regular grid approaches restrict the positions of sparse known data to a fixed grid. Some codecs specify only a global grid size of Cartesian [9] or hexagonal [29] grids, thus steering the density of the inpainting mask. Apart from a few exceptions such as Peter 2019 [9] , most regular grid approaches for inpainting-based compression do not offer competitive performance.
2) Subdivision approaches additionally allow some adaptation to the image. Most of them use error-based refinement of the grid, splitting areas with high inpainting error into smaller subimages with a finer grid. They store these splitting decisions efficiently as a binary or quad tree. Originally, Galić et al. [3] and Livada et al. [30] employed a triangular subdivision while later works [7, 31] use the more efficient rectangular subdivision by Schmaltz et al. [6] .
3) Semantic approaches select known data directly based on image features and belong to the oldest inpainting-based compression techniques. They date back to early approaches of Carlsson [32] . Contemporary semantic codecs are particularly popular for the compression of images with pronounced edges [33, 34] such as cartoons [35] [36] [37] [38] , depth maps [29, 39, 40] , or flow fields [41] . These methods extract and store image edges and use those as known data for inpainting. Since edges are connected structures, chain codes can be used for efficient encoding.
4) Unconstrained mask approaches: While there are numerous publications that deal with optimal selection of sparse known data for inpainting [4, [11] [12] [13] [14] [42] [43] [44] [45] [46] [47] , only few use them for actual compression. Hoffman et al. [29] primarily use a regular grid as already mentioned, but it also uses some unconstrained mask points to further enhance quality which are encoded using JBIG . Demaret et al. [10] originally used a hybrid approach that combines a subdivision strategy with storage of exact positions. In a later publication [5] , Demaret 
In Section 2, we give a short overview of inpainting-based compression, which establishes the foundations for our systematic analysis. We review different entropy coding methods in Section 3. In Section 4, we discuss and compare different popular image compression codecs. Since not only the coding strategy, but also the representation of point locations are important, we introduce several alternative approaches in Section 5. We investigate the successful ideas of context mixing in detail with an ablation study in Section 6. Furthermore, we do a consolidated comparison of the best methods that were considered in previous sections in Section 7 to give best practice recommendations. Finally, we discuss our conclusions and ideas for future work in Section 8.
Inpainting-based compression relies on two main components: An inpainting method for reconstruction and a selection approach for the sparse known data to be stored.
Let f : Ω → R be a grey value image that is only known on a subset K ⊂ Ω, also called the inpainting mask. The goal is to reconstruct the missing values in Ω \ K by solving for the steady state of the diffusion equation [48] ∂ t u = div(D∇u)
on
n Du = 0 on ∂Ω × (0, ∞).
Here u(x, y, t) is the grey value at time t and position (x, y) and n is the outer image normal. The spatial gradient operator is denoted by ∇f (x, y) = (∂ x f, ∂ y f ) , and div(f ) = ∂ x f 1 + ∂ y f 2 denotes the divergence. The diffusion tensor D is a positive definite matrix which specifies the behaviour of the diffusion process.
Eq. 1 models the evolution of the image over time. Eq. 2 and Eq. 3 define the boundary conditions for the diffusion process. The Dirichlet boundary conditions in Eq. 2 guarantee that known pixel values stay unmodified. Eq. 3 uses Neumann boundary conditions to avoid diffusion across the image boundaries.
The simplest choice for the diffusion tensor is D = I , where I is the identity matrix. In that case, Eq. 1 can be written as ∂ t u = div(∇u) = ∆u = ∂ xx u + ∂ yy u.
This equation describes homogeneous diffusion as the propagation of information is equal in all directions at all locations [26] . There are more sophisticated choices for D which allow e.g. direction-dependent adaptation of the inpainting as in edge-enhancing anisotropic diffusion [49] . However, a full review of inpainting operators is beyond the scope of our compression-focused contribution.
Shepard Interpolation is a simple inpainting method that uses inverse distance weighting [28] , i.e. pixel values are inpainted by receiving more information from closer pixel neighbours than from those further away. Considering an image f : Ω → R where the inpainting mask is given by K ⊂ Ω and Ω is the image domain. We compute the reconstruction u at a point given by the position vector p as
.
We use a truncated Gaussian G(x) := exp(− x 2 2 /(2σ 2 )) for the weighting function w. The standard deviation σ is adapted to the mask density according to σ = (m · n)/(π|K|) as proposed by Achanta et al. [50] where m and n are the width and height of the image respectively. original image [25] 5% random mask 5% sparsification + 5% densification + homogeneous diffusion Shepard interpolation Figure 2 : We can see here that even though we start with the same image, different point selection strategies or inpainting operators can lead to very different unconstrained mask distributions.
Beyond the two aforementioned types of inpainting methods, there are many more, such as exemplar-based [14, 51] or pseudodifferential inpainting [52] . While each of those methods has interesting properties, including them into our considerations would go beyond the scope of our evaluation.
While there are many different strategies to find mask points, we use two of the most popular ones from the literature.
Sparsification [11] is a top-down algorithm where we start with the original image. The main idea is that pixels that are harder to reconstruct are more important. In each iteration, the algorithm randomly chooses a set of candidate pixels and removes those with the lowest per-pixel inpainting errors which explains the probabilistic nature of the process. With the new mask, it updates the inpainting error before it proceeds to the next iteration. This way, the number of mask points is reduced until the desired density is achieved.
Densification [27] is the bottom-up analogue of sparsification. The algorithm starts with an empty mask image and a fixed amount of mask pixels is added in every iteration until the required density is achieved. However, it has been found that densification generally performs worse than sparsification due to the fact that very little information is available in the beginning. For the same reason, densification tends to perform better on noisy images, where sparsification is prone to select noisy pixels [27] .
We consider these particular methods since they generate binary masks with very characteristic distributions as seen in Fig. 2 . As a worst case scenario for encoding we consider uniformly random distributions of mask points. On the other side of the spectrum, we use probabilistic sparsification [11] and homogeneous diffusion [26] , which creates masks that are highly adaptive to image structures. Finally, masks from probabilistic densification [27] with Shepard interpolation [28] are a compromise between both, since they are not randomly distributed, but conform less to image features.
Unless stated otherwise, all experiments in this paper consider average compression performance over all the aforementioned point selection methods, and over all mask densities from 1% to 10%.
In the following, we review approaches that are not specialised to image data, but are still a vital part of most image codecs. The principle of entropy coders is to convert input data into a more compact representation which can be converted back to its original form by exploiting the redundancies present in said data. Such general purpose coders take as an input a sequence of generic symbols from an alphabet A. Note that for our purposes, this alphabet depends on the chosen representation of the binary image from Section 5. For a vector representation, we have A = {0, 1}, and in the other representations A = {0, 1, ..., N } ⊂ N is a set of integers.
Huffman coding [53] is a classical prefix-free encoding scheme that maps a binary codeword to each symbol of the alphabet. These codewords are assigned according to a binary tree which is constructed from the occurrence probabilities of the symbols. As a classical entropy coder, Huffman coding aims at distributing the code lengths in such a way that the overall coding cost is minimised. The theoretical lower limit for the coding cost of a given symbol distribution S → {S 1 , S 2 , ..., S n } with a probability distribution p 1 , p 2 , ..., p n is given by the Shannon entropy [54] ,
Huffman coding is simple, easy to implement, and fast, but it is inefficient for symbol probabilities that are not close to powers of 1 2 , as all symbols are encoded with an integer number of bits. While Huffman-coding has been superseded by more efficient entropy coders, it is still part of some widely-used image compression codecs such as JPEG [1] and PNG [18] .
In contrast to Huffman coding, arithmetic coding can encode symbols with fractional bit cost per symbol, as it maps the whole source word directly to a binary code word.
In its original form [55] , arithmetic coding achieves this by an interval subdivision scheme. Starting with the range [0, 1), each symbol from the alphabet A is associated with a subinterval. The length of these subintervals is proportional to the probability of the associated symbol. Successively, each encoded symbol leads to a refinement of the interval. The final interval is uniquely represented by a dyadic fraction. Due to the coupling of the interval size to the symbol probabilities, the code length adapts to the symbol distribution.
Since this strategy requires floating-point operations and is therefore slow and prone to rounding errors, we consider the WNC implementation of Witten, Neal and Cleary [56] . It replaces the real-valued intervals by sets of integers. This greatly improves computational performance and allows an easier generation of the binary code word.
Due to its good approximation of the Shannon limit, arithmetic coding is used in many lossless and lossy image compression codecs [2, 3, 5, 6, 8, 17, [19] [20] [21] and also forms the foundation for more advanced general purpose encoders such as context coding and context mixing methods which we will discuss in the subsequent sections.
Arithmetic coding estimates the symbol probabilities only from the symbol counts i.e. the number of times that the symbol has been encountered. This pure consideration of the occurrence frequency is referred to as a 0th-order context from which the probabilities are derived. However, more complex contexts can be considered to incorporate more structural information of the input data into the encoding process, thus allowing a better compression performance.
As a direct extension of the 0th-order context, we can use a history of m previously encoded symbols to predict the next symbol. The collection of m previously encoded symbols is called the mth-order context. For images, one can also consider 2D neighbourhoods of varying size (see Fig. 5 ). Using a single context allows us to adapt the probabilities to recurring patterns inside the scope of the corresponding contexts. This enables approaches like Prediction by Partial Matching (PPM) [57] , Context Adapative Binary Arithmetic Coding (CABAC) which is used in HEVC [2] and Extended Block Coding with Optimised Truncation (EBCOT) which is used in JPEG2000 [21] which have better performance than standard arithmetic coding.
Context mixing approaches extend upon the idea of context coding. Instead of using only a single context to estimate the symbol probability, the probabilities derived from many contexts can be combined with weighted averaging.
Originating from the pioneering work of Mahoney, the so-called PAQ1 context-mixing algorithm [58] , many versions with increasingly sophisticated contexts have been developed. All versions of PAQ encode bits individually rather than the symbols themselves and convert input data into a bit stream accordingly. The small alphabet reduces the number of possible contexts and has the additional advantage that PAQ can be combined with fast binary arithmetic coding algorithms.
As general purpose compressors, the full versions of PAQ aim at compressing mixed data such as combinations of text, audio, executables, HTML code, and many other data types. Thus, many of their additional contexts would not be useful for our purposes. In the following sections, we consider LPAQ2 by Rhatushnyak [24] , since we identified it as the most promising member of the expansive PAQ family.
LPAQ is a lightweight variant of PAQ that uses six local contexts, and a prediction context. The local contexts depend on the bits already encoded in the current byte and the previous encoded 4 bytes. The prediction context finds the longest context that was already seen which is the same as the current one and tries to predict the next bits. A neural network mixes the probabilities which were obtained from the mentioned contexts.
The neural network has a simple structure: It consists of an input layer with seven nodes and an output layer that computes the weighted average of the probabilities in the logistic domain. This method of mixing the probabilities is called logistic mixing and uses logarithmic transformations known as stretching and squashing. Their mathematical formulations are given by
The algorithm learns the weight for each context during the encoding process by a modified form of gradient descent that tries to minimise coding cost. This results in larger weights for contexts that give good predictions for the given input data. The mixed probability obtained from the neural network is still not perfect. The algorithm refines this probability further using two SSE (Secondary Symbol Estimation) stages. Each SSE stage takes an input probability and then stretches and quantises them. The encoder interpolates the output using a context table to give an adjusted probability. Finally, we use this probability to encode the next bit using arithmetic coding.
However, an individual context can have a different amount of contribution in predicting the next bit depending on the local statistics. Therefore, using the same neural network to encode all bits can be sub-optimal. To this end, LPAQ2 maintains 80 neural networks and chooses which one to use by looking at the match length from the prediction context combined and the bits already encoded in the current byte.
Variants of PAQ have been used successfully in many inpainting-based compression approaches, primarily for storing quantised pixel values [3, 6, 7, 29, 31] . Since the PAQ family of codecs is so successful, we dedicate Section 6 to a detailed, separate analysis for them.
Before discussing specialised methods to compress sparse binary images, we consider well-established image compression methods to provide a performance baseline for the specialised codecs. We discuss and compare five popular lossless image compression methods: PNG, JBIG, DjVu, JBIG2, and BPG-lossless. Since the salient information of a sparse binary image is the non-zero pixels, the compression ratio as a traditional metric is not the most transparent choice for our evaluation. To this end, we use bytes per mask pixel instead, which can be computed as the compressed file size divided by the number of non-zero pixels in the image. Such a normalisation allows us to attribute the cost to the salient image features that need to be stored.
Portable Network Graphics (PNG) [18] is a widely used lossless image compression codec. PNG compression has two stages: filtering and entropy coding. The filtering stage aims at predicting the pixel to be encoded from its already encoded neighbourhood. While the prediction can be wrong, the prediction errors are generally cheaper to compress compared to the original pixel values due to an overall lower entropy. For predictions, PNG uses only the left, upper and the upper-left diagonal neighbours -either directly as a prediction, or by averaging.
The entropy coding uses LZ77 and Huffman coding. LZ77 [59] is a dictionary based coding method where the subsequent values are encoded by looking for a match in the already encoded values. If a match is found, the difference in position to the current position and the length of the match is encoded. If no match is found, the next value is written explicitly. PNG compresses the values given by LZSS using Huffman coding.
Joint Bi-Level Image Expert Group (JBIG) [17] is a specialised codec from the JPEG family for binary images. JBIG was originally implemented for fax transmissions. It employs progressive coding which uses a coarse-to-fine strategy to encode the image. On the decoding side, JBIG decodes the coarse scale pixels first to give a low resolution preview of the image and then the finer scale pixels subsequently to display the high resolution image. JBIG uses arithmetic coding to encode the lowest resolution pixels where it estimates the probabilities using the neighbouring pixels as contexts. It encodes the next finer scale using the neighbouring coarser scale pixels and the neighbouring pixels in the current scale. The algorithm does this until it finishes encoding the finest scale pixels. The cartoon-like image compression codec by Mainberger et al. [37] uses JBIG to store the edge positions.
DjVu is an image compression algorithm [20] originally written for compressing images in documents. DjVu includes a bi-tonal image compression algorithm called JB2 which stores the binary image used to separate the image into foreground and background. The foreground and background images are then compressed using other methods. If the input is a binary image, DjVu uses only JB2. The algorithm segments the image into connected components of black pixels called marks. The marks are clustered based on similarity. Then DjVu compresses and codes a mark using the previously encoded marks by storing the mark index and relative position. The other marks with no matches are stored using a statistical model and arithmetic coding.
JBIG2 [19] is a binary image codec based on the DjVu JB2 coder. JBIG2 has separate methods for encoding text which uses pattern matching similar to JB2. It also contains separate methods to encode half-tones and generic data. For our purposes, we need to look at only the generic data coder which stores two binary images, the coarse image and the refinement bits like in JBIG. The bit-planes are then stored with arithmetic coding.
Better Portable Graphics (BPG) [21] is a coding method used within the video coding standard HEVC [2] . BPG employs a prediction method which uses three modes: One to model constant regions, one to model directional structures and one to model smooth regions.
In Fig. 3 , we see that on masks derived from the Kodak dataset, PNG compresses the fastest as it combines simple prediction schemes with Huffman coding. DjVu performs best w.r.t. file size reduction. JBIG and JBIG2 uses similar methods to compress non-text data which explains their comparable performance and compression times. Both give a good trade-off between speed and performance. BPG yields inferior results because our sparse test images violate BPG's assumptions on natural images.
As with any other data stream, there are many ways to represent sparse binary images, and the way in which the data is represented has an impact on the final performance of lossless compression. In the following, we describe and compare common representations originating from different fields of research.
A naive representation that allows to apply many standard sequential entropy coders is the vector representation. We convert the image into a vector by traversing it row-by-row.
One of the most popular methods for compression of sparse images is runlength encoding. It replaces sequences of identical symbols, so-called runs, by their length.
For our setting where sparse binary images are considered, run-length encoding becomes even more efficient. We assume that known values are mostly isolated and thus only have to store runs of intermediate zeroes. Consecutive ones can be represented by a zero run.
The image has to be scanned in some order to calculate the run-lengths. Potential options include for example column-by-column, row-by-row, diagonal or zigzag as done in JPEG. We found that the scanning order does not have a significant impact on the final compressed file size. Therefore, we only consider the most straightforward approach which is column by column. 
A COO [23] stores each non-zero point as a (row, column) tuple. A differential scheme on the coordinates can also be considered, where we encode the difference in position between the current point and the previous point. However, if we sort the points based on their rows and columns, we get a representation that is almost identical to run-length encoding.
As another well known sparse image representation, CSR [23] is mainly used for fast operations on large images in scientific computing. CSR traverses the image row-by-row and stores the column positions of each non-zero element. In addition, the total number of non-zero elements encountered is stored when a complete row is encoded. We make a slight modification to the basic CSR method to yield better compression results. Instead of storing the total number of encountered non-zero elements, we only store the number of non-zero elements encountered in the previous row. This reduces the range of values needed to be stored thus reducing the source entropy.
In Fig. 4 , we see that the vector representation and run-length encoding are the better choices as they clearly lead to smaller compressed files than both COO and CSR.
The file size after compression depends on two aspects: the initial file size and the entropy of the file. The vectorised form has the same probability distribution as the original image. For a sparse binary image the probability distribution is heavily skewed towards zero, yielding a low entropy. This means that the original image is highly compressible which leads to high performance.
Run-length encoding gives the shortest representation, as can be seen in Table 1 , which in turn yields high compression performance especially for lower densities. On the other hand, COO and CSR have short representations, but not as short as RLE. Also, their entropy is not as low as the vectorised form. These factors combined make COO and CSR non-viable choices for compression. 
In Sections 3 and 4 we have introduced a wide range of coding strategies that are viable candidates for good performance on binary images. However, context mixing is not only the most sophisticated coding strategy, it also has a track record of many applications in inpainting-based compression [3, 6, 7, 29, 31] . Therefore, we investigate which of the many components of these complex methods are useful for our purpose.
In the following we describe our setup for a detailed ablation study for context mixing on sparse binary images. In Fig. 4 , we saw that the vector and RLE representations were best suited for compression. Therefore , we pursue two approaches involving these representations: In a bottom-up strategy, we combine established as well as new contexts in a novel, minimalistic context mixing codec involving the vector representation. Furthermore, we deconstruct LPAQ2 in a top-down approach to compress run-lengths.
The reference point that we start with is the codec used by Marwood et al. [8] . It uses a global context where the probability of the next bit being a 1 is estimated as V r /N r where the remaining number of significant pixels to be encoded is denoted by V r and the total remaining pixels to be coded is N r . From now on, we will refer to this probability as the Marwood context probability. We also considered using the context proposed by Demaret et al. [5] , where the context is defined by the number of non-zero pixels in the 12 neighbouring pixels to the current pixel that were already encoded. However, we found that even though this performs well on its own, it does not offer any performance gain when combined with our models.
We implemented a lightweight codec BPAQ-2D-S (Skeletal PAQ for 2D binary data) inspired by the context mixing structure of Mahoney [22] where we have only the first order local context (neighbouring pixel to the left) in addition with the Marwood context.
The set of equations is given in Algorithm 1 where n 10 ,n 11 ,w 1 are the counts for 0 and 1 occurring in the first order context and its weight. The bit currently being encoded is denoted by x. A semi-stationary update for local contexts is done where we halve the count of the non-observed symbol. We update counts this way so that the context probabilities can adapt more quickly to local statistics [22] . V r is initialised to the number of non-zero pixels in the image and N r is initialised to the total number of pixels in the image.
When calculating p f inal , we make use of a dynamically weighted local probability, a statically weighted local probability, and a statically weighted global probability. The global probability is statically weighted due to the fact that the counts for 0 and 1 cannot be defined for the Marwood context as it is done for the local context. We noticed through experimental observations that combining static and dynamic weights gives a better performance than just using dynamic weights. We determined the static weights empirically. Finally, we encode the next bit with arithmetic coding using p f inal .
BPAQ-2D-M (More efficient PAQ for 2D binary data) is an extended version of BPAQ-2D-S. As shown in Fig. 5 , it has twelve local contexts instead of one. Increasing the order from m to m + 1 adds one pixel to the contextneighbourhood and allows a better adaptivity to local statistics.
The difference in expressions from BPAQ-2D-S (Algorithm 1) is given in Algorithm 2 where n i0 , n i1 , w i are the counts for 0 and 1 occurring in the ith context and its corresponding weight, where 1 ≤ i ≤ 12. The static local probability here comes from the fourth order context instead of the first context Algorithm 1 BPAQ-2D-S 1: Compute evidence for the next bit being 0:
S 0 = ε + w 1 n 10 2: Compute evidence for the next bit being 1:
3: Compute total evidence: S = S 0 + S 1 4: Compute weighted local probability that the next bit is 1:
Compute unweighted local probability from the first order context: 
10: Compute final probability:
in BPAQ-2D-S. Again, it was found out experimentally that the fourth order context worked best. Apart from these changes, the rest of the expressions stay the same as in BPAQ-2D-S.
Algorithm 2 BPAQ-2D-M 1: Compute evidence for the next bit being 0:
2: Compute evidence for the next bit being 1:
3: Compute unweighted local probability from the fourth order context:
4: Update context weights:
6.1.3. BPAQ-2D-L BPAQ-2D-L (Logistic PAQ for 2D binary data) is similar to BPAQ-2D-M that uses logistic mixing instead of linear mixing where the probabilities are first stretched and then the final probability is squashed. Unlike BPAQ-2D-M where the final probability is obtained by statically mixing the mixed local context probability and the Marwood context probability, here the final probability is obtained dynamically where the weights change in each step for all contexts.
In Algorithm 3, p 1 ,. . . ,p 12 are the probabilities obtained from the 12 local contexts and p 13 from the Marwood context. n i0 , n i1 , w i are the counts for 0 and 1 occurring in the i-th context and its weight. The bit currently being encoded is denoted by x, and the learning rate α is set to 0.02.
Finally, we have BPAQ-2D-XL (eXtended Logistic PAQ for 2D binary data) which is derived from BPAQ-2D-L where the only change is the structure of the local contexts. In the previous models, the higher order contexts were always contiguously extended from the lower context as seen in Fig. 5 . Here, we removed the contiguity conditions and generated contexts that could be disconnected. We only consider the four nearest pixels to the current pixels, and consequentially we would have four different first order contexts, six different second order contexts , four different third order contexts and one fourth order Algorithm 3 BPAQ-2D-L 1: Compute context probabilities:
2: Stretch context probabilities:
3: Combine stretched probabilities:
: Compute the final probability by squashing:
5: Update context weights:
6: Semi-stationary update of local context counts:
Update counts for the Marwood probability:
Uses 1 local context with linear mixing BPAQ-2D-M Uses 12 local contexts with linear mixing BPAQ-2D-L BPAQ-2D-M but with logistic mixing BPAQ-2D-XL BPAQ-2D-L but with non-contiguous contexts Table 2 : Summary of the four proposed bottom-up PAQ approaches context. Therefore, we have 15 local contexts in total. The main differences between the proposed bottom-up PAQ models are listed in Table 2 .
6.1.5. Evaluation: performance vs. runtime
In Fig. 6 , we see that the performance mostly correlates with the complexity of our proposed models. The simplest model, BPAQ-2D-S, is the fastest one and BPAQ-2D-XL the slowest. Surprisingly, BPAQ-2D-L outperforms all other approaches.
BPAQ-2D-M performs better w.r.t. compression ratio than BPAQ-2D-S due to the additional contexts at the cost of speed. BPAQ-2D-L gains additional compression efficiency, but the use of logarithmic and exponential functions in logistic mixing slows down the method further. The additional contexts of BPAQ-2D-XL do not only increase its complexity, but even slightly increase the cost per mask point. Thus, one should either choose BPAQ-2D-L for the lowest bit cost per mask point or the method of Demaret et al. [5] for a good mix of compression ratio and speed.
LPAQ2 is a very good entropy coder for a wide range of data and already constitutes a lightweight version of PAQ. However, it is unclear if all of the individual steps of the method really contribute to its performance. In order to identify these parts, we eliminate features step-by-step in a top-down manner to see the performance and runtime behaviour.
We start out with the full original implementation of LPAQ2 with parameter settings for highest compression (compression level 9). From there on, we perform multiple reduction steps.
Step 1: We remove the prediction context (no prediction model).
Step 2: We reduce the amount of neural nets from 80 to a single one (single net model).
Step 3: We retain only the intra-byte context and discard the rest (intra only model).
Step 4: For ULPAQ (ultra lite PAQ), we also discard the second SSE stage (RLE + ULPAQ). 
A comparison for the aforementioned reduction steps is shown in Fig. 7 . As the most complex model, the original LPAQ is the slowest of the evaluated methods. The no prediction model and the single network model only have a minor difference in bits per mask pixel, but they are about 20% faster than the original version. This shows that a single neural net without prediction comes at virtually no disadvantage to the more complex full version of the codec. The intra only model and ULPAQ are even 10 times faster than the original version. Additionally, ULPAQ performs better than intra only model. Thereby, the second step of SSE is detrimental for binary input data. For reference, we also consider LPAQ level 0, the fastest parameter setting for standard LPAQ. It is not as fast as RLE+ULPAQ, but also produces smaller encoded files. In practice, ULPAQ offers a slight advantage in speed while LPAQ (Level 0) provides a slight advantage in compression ratio.
In this section we perform a consolidated comparison of the best candidates for sparse binary mask compression from the previous Sections 3, 5, and 6. We consider BPAQ-2D-L and the codec of Demaret et al. [5] from Fig. 6 Our evaluation is based on the two essential mask characteristics: Point distribution and density. Both of these aspects are relevant for practical use. The distribution depends on the inpainting operator and mask selection strategy, while the density is closely connected to the desired final compression ratio of the inpainting method. Thus, any best practice recommendations need to take into account the behaviour of the algorithms w.r.t. these two factors.
The different methods that we considered to generate the mask points have varying point distributions; see Fig. 2 . We want to see if compression performance changes with respect to the point distribution. Here we present the results averaged over all densities from 1% to 10% for different point distributions.
From Fig. 8 we observe that the relative rankings of different compression methods change over different types of distributions. For homogeneous diffusion masks, we see that DjVu offers both fast compression and a very good compression ratio. If runtime is no concern, BPAQ-2D-L provides the lowest cost of bits per mask point.
For Shepard and random masks, we see that the two best methods on homogeneous diffusion masks, BPAQ-2D-L and DjVu, perform worse. This is due to the fact that masks derived from homogeneous diffusion are more structured. Both BPAQ-2D-L and DjVu can therefore benefit from their ability to detect such patterns. This structure is absent from the masks derived using Shepard interpolation and, in the extreme case, completely random mask distributions. This is also why all the codecs perform better on homogeneous diffusion masks than on Shepard and random masks. In such a case, the approach of Demaret et al. [5] is a good alternative.
Next we evaluate if the relative performance of the selected codecs differ for varying densities. We present the results averaged over all point distributions for masks having densities of 1%, 5%, and 10%. In addition, we also consider an average over all point distributions and all point densities between 1% and 10%. Fig. 9 shows that the relative rankings between codecs are consistent over increasing densities and also in the average of all densities. This implies that 10% masks averaged over 1% to 10% Masks Figure 9 : Performance vs. time comparison of different coders tested on different densities averaged over masks derived from the Kodak image dataset using sparsification + homogeneous diffusion, densification + Shepard interpolation, and random masks.
the choice of the binary mask compression algorithm has to be only adapted to the distribution but not to the compression ratio. For time critical applications, RLE + ULPAQ is the most suitable combination. BPAQ-2D-L from our ablation study of context mixing, yields the best compression performance at the cost of runtime. Between those two extremes, the method of Demaret et al. provides a good balance between speed and performance.
Additionally, a general trend can be inferred from Fig. 4 : The relative cost of storing positions declines for denser masks. This shows that storing mask positions will decrease the compression performance by a larger amount for sparse masks than dense masks.
The first systematic study of sparse binary image compression allows us to understand, compare, and improve upon a wide variety of codecs. With an ablation study, we have determined the aspects of context mixing methods that make them successful for the compression of sparse binary images. As a consequence of the ablation study, we proposed two different classes of methods: one to compress the image itself and the other to compress run-lengths.
Our best practice recommendations provide a foundation for future inpainting-based codecs that use unconstrained masks. Our results from Section 7 suggest that optimal mask compression should adapt to the specific point distribution caused by the combination of inpainting operator and mask selection method. However, the compression method does not need to be changed based on density since that does not impact the relative rankings of the codecs.
Based our full evaluation, we have concrete recommendations for different use cases: RLE + ULPAQ for time-critical applications, BPAQ-2D-L for highest amount of compression, and the codec of Demaret et al. [5] for a good compromise between compression performance and speed.
These results have interesting implications for future codecs that use unconstrained mask based inpainting methods. Due to the increased relative cost of storing very sparse unconstrained masks, we can infer that this is viable only when they offer a massive improvement in inpainting quality over regular or structured masks. It might also be interesting to consider codecs that produce unconstrained masks which consider not only inpainting quality but also the cost of storing them.