We add a sigmoid layer to predict the final value of \(\mu \)  in VQ-VAE module to make sure it is close to 128.
fig:klu and fig:predictedu show that this technique almost deals with no BPD loss.
Experiments
In this section, we evaluate the model and coder effectiveness with extensive experiments and we conduct experiments on both low resolution and high resolution images which demonstrate our framework obtains the fastest compression speed with a competitive compression ratio.
Experimental Settings
Implementation Details. The AR and VQ-VAE module are jointly trained. The AR module contains 12 parameters. In VQ-VAE, the codebook size \(K\)  is set to 256 and the codebook dimension \(D\)  is set to 32.
The encoder and decoder both have 4 residual blocks, all with 32 channels. The encoder downsampling ratio is 2, and pixel shuffle is used when upsampling in the decoder. Thus, an image \(x \)  with shape \(32 \times 32 \times 3\)  would be quantized to \(16 \times 16 \times 1\)  vectors.
\(\beta \)  in  eq: vq loss is set to 0.25 as in [1]}, and \(\alpha \)  in  eq:totalloss is set to 125.
We do all experiments in a Linux docker with Intel(R) Xeon(R) Gold 6151 CPU (3.0 GHz, 72 threads), and one NVIDIA Tesla V100 32GB.
For speed tests, we ignore the time for disk I/O, since it has nothing to do with compression algorithms.
But for fair comparison between AI and traditional methods, we do count the time for data transfer between CPU memory and GPU memory.
That means for all AI algorithms, timer starts when data is loaded into RAM and ends when compressed data is stored in RAM.
Different from previous AI compression works which focus on density estimation, this paper targets practical compression. Therefore, for BPD values reported in this paper, all storage required to recover the original image is counted, including meta data, Huffman tables, auxiliary bits, etc.. For AI algorithms, real BPD is reported instead of theoretical one unless specified otherwise, which means for each image, we calculate the number of bytes (instead of bits) needed for each image, then take the average.
<TABLE><TABLE>Datasets.
For low resolution experiments, we train and evaluate on CIFAR10, ImageNet32/64. For high resolution experiments, we train our model on 50000 images from Open Image Train Dataset[2]} which are randomly selected and preprocessed as [3]} to prevent overfitting on JPEG artifacts. Then, we evaluate on natural high resolution datasets, CLIC.mobile, CLIC.pro[4]} and DIV2K[5]} to test the model generalization ability. For
high resolution setting, we crop 32 \(\times \)  32 patches for evaluating.
<FIGURE>
Model Effectiveness
<TABLE>Effectiveness of model architecture. We analyze single and combinations of each component to evaluate the effectiveness of model architecture. In tab:archcomponents, the vanilla Auto-encoder (AE) contains the same encoder and decoder architecture as VQ-VAE with latent feature shape 16\(\times \) 16\(\times \) 1. In AE and VQ-VAE, we directly use the model to predict the distribution of the original image. In the single AR, we compress the residual with a static entropy coder to get the BPD. AR+AE follows the same process as AR+VQ-VAE. As shown in tab:archcomponents, VQ-VAE outperforms AE which demonstrates the effectiveness of the learned codebook \(Z\) . We could intuitively explain that 16\(\times \) 16\(\times \) 1 vector indexes would contain more diversity features than 16\(\times \) 16\(\times \) 1 numbers in AE's latent. Our proposed AR+VQ-VAE model achieves the best theoretical BPD on CIFAR10 which suggests the effectiveness of predicting residual.
Effectiveness of Three-Way AR and parallel mechanism. We compare different receptive fields of the AR model and the parallel mechanism. Experiments are conducted on red channel of CIFAR10 images. The receptive field of AR model means the current point is predicted by how many previous points. In our model, the receptive field is three. As shown in tab:arreceptivefield, as the receptive field increases, the BPD indeed descends, but the decline is very limited. With the parallel mechanism we designed in subsec:modelarchitecture, the Three-Way AR achieves a throughput of 382.5 MB/s when recovering original images from residual in decompression, and outperforms other settings which cannot be paralleled.

Coder Effectiveness
We implement the GPU coder based on alg:tansencode and alg:tansdecode. We test the coder on the randomly generated data (1000000 pieces, each with length 1000, and range 0-255). The signals have the same dimension with each value in 0-7. For each setting, we run 10 times and take the average speed. From fig:coderspeed, we see that GPU coder is slow for the small number of threads. Fortunately, the number of threads can easily reach one million with a V100 32G. Therefore, we can inference on million batches, and save the result in GPU. Then we can code all of the batches at once.
This is beneficial for the GPU coder, in the sense that the data transfer times and the amount is smaller for both compression and decompression.

Distribution Effectiveness
<FIGURE>We count the predicted location parameter \(\mu \)  for the distribution specified in subsec:intermodelcoder.
It can be shown in fig:predictedu that for all the three datasets, the predicted values nearly always fall in \([96, 160]\) . As stated in subsec:intermodelcoder, this cause almost no loss in BPD.

Compression performance
Compare with exists methods. We reproduce all methods in  tab:overallspeed on the same platform explained in subsec:expsettings for fair comparison. We use Python CV2 lib for PNG and JPEG2000. We adopt FLIF version 1.0.1 and use command `flif -e –effort=0' for fastest setting. For WebP, we use version 1.2.1 and the command `cwebp -lossless -z 0'. For L3C, we reproduce the results using the official model[6]} and we replace the original coder in L3C with ours to test the speed as the original coder is very slow. The throughput results are reported based on high resolution settings.  tab:overallspeed shows our framework achieves the fastest compress and decompress throughput. Also, the framework achieves a competitive compression ratio on low resolution images and we still outperform PNG, WebP and JPEG2000 on high resolution images.
End-to-end throughput. To fully use the GPU coder and make the measured speed more accurate, we duplicate the CIFAR10 validation set 100 times (1 million images).  tab:decomposition shows the details of the throughput and time taken for each step.
<TABLE>
Limitation Analysis
Our framework, although very light-weighted, requires an AI chip such as Tesla V100 to work efficiently, which is inaccessible for most end-users. For example, one image with 2K resolution compresses only about 1.3 MB/s in the CPU of our server machine. Therefore, our framework is only applicable to file/cloud servers.

Conclusion
In this work, we develop the first efficient end-to-end generative model based image lossless compression framework with throughput of about 200 MB/s, and compression ratio 30% better than PNG. To achieve this result, we develop a model that combines AR model and VQ-VAE, and a semi-dynamic coder that is computation efficient.
To further improve PILC, future works could focus on algorithms that are more friendly in everyday devices, such as a PC, or mobile phone. This requires a network with much less FLOPS than the current VQ-VAE one.

Coder Design
With the same notation as ours, the original rANS can be written as:
\(\text{Encoding: } S \leftarrow 2^M \times \lfloor S / P_x \rfloor + C_x + S \bmod P_x,\) 
\(\text{Decoding: } S \leftarrow P_x \times \lfloor S / 2^M \rfloor + S \bmod 2^M - C_x,\) 
where in decoding, same as the modified one, to get \(x\) , binary search is also needed to be applied on \(S \bmod 2^M\) .
Let \(n\)  be the message length, if applying eq:originalransencoding and eq:originalransdecoding directly, the time complexity is \(O(n^2)\) . So in real applications, \(S\)  is usually truncated to a range, such as \([2^{32}, 2^{64})\) , reducing the time complexity to \(O(n)\)  for encoding and \(O(n \log X)\)  for decoding, with minor reduction in compression ratio. However, it is still not efficient enough for real-time applications due to:
\(P_x\)  and \(C_x\)  need to be calculated online for each \(x\) .

One division operation and one modular operation are required for encoding.

Binary search is needed for decoding.
In this work, \(S\)  is truncated to \([2^M, 2^{M+1})\) , which boosts the efficiency, but affects the compression ratio more severely, and more memory is needed. In next subsections, we prove that the BPD loss and memory are both upper-bounded by an acceptable value.
BPD loss for ANS-AI
Lemma 1 BPD for the ANS-AI is at most \(2 - \log _2 e\)  worse than the original rANS.

As ANS-AI and the modified rANS are numerically equivalent, it suffices to prove the effectiveness of the latter.
Without loss of generality, assume quantization for pdf values does not introduce bias in density estimation, which means \(p(x=i) = P_i / 2^M\)  for all \(i\) , otherwise both original and modified ones are affected by the same way.
Also each symbol \(x\)  is independent of each other.
Unless specified otherwise, all \(\log \)  in this material means logarithm function with base 2. Then from Shannon's source coding theorem:
\(\begin{split}\mathtt {BPD(rANS)} & \ge \frac{\sum _i P_i \times \log 2^M / P_i}{2^M} \\& = M - \frac{\sum _i P_i \times \log P_i}{2^M}.\end{split}\) 
For the ANS-AI, BPD value equals to the expected number of bits to push to steam during encoding. The value \(S\)  before each encoding is uniform in \([2^M, 2^{M+1})\)  since \(P_i\)  is proportional to \(p(x=i)\) . Therefore:
\(\begin{split}\mathtt {BPD(ANS\_AI)} & = \sum _{j \in [2^M, 2^{M+1})}\frac{\sum _i P_i \times \lfloor \log (j/P_i) \rfloor / 2^M}{2^M} \\& \le \frac{\sum _{j \in [2^M, 2^{M+1})} \sum _i P_i \times \log (j/P_i)}{2^{2M}} \\& = \frac{\sum _{j \in [2^M, 2^{M+1})}\log j}{2^M} - \frac{\sum _i P_i \times \log P_i}{2^M} \\& \le \frac{\int _{2^M}^{2^{M+1}} \log j}{2^M} - \frac{\sum _i P_i \times \log P_i}{2^M} \\& = M + 2 - \log e - \frac{\sum _i P_i \times \log P_i}{2^M}.\end{split}\) 
Bring eq:bpdans and eq:bpdansai together, we get
\(\mathtt {BPD(ANS\_AI) - BPD(rANS) \le 2 - \log e}.\) 

Memory consumption for ANS-AI
Lemma 2 
In our frame work, when \(M \le 12\) , \(\delta \)  can be represented as an 16 bit unsigned integer.

Let \(k\)  be the integer such that \(P_x \times 2^k \in [2^M, 2^{M+1})\) . In our framework, it always satisfies that \(P_x \in [1, 2^{M-1})\) , thus \(k \in [2, M]\) . Therefore:
\(\lfloor \frac{\delta [d,x]+S}{2^M} \rfloor = {\left\lbrace \begin{array}{ll}k & S \in [P_x \times 2^k, 2^{M+1}) \\k - 1 & S \in [2^M, P_x \times 2^k)\end{array}\right.}\) 
Then it suffices to prove that when \(\delta [d,x] = k \times 2^M - P_x \times 2^k\) , both unsigned 16 bit constraint and eq:rangedelta are satisfied.

\(\delta [d,x] < k \times 2^M - 2^M < (M - 1) \times 2^M \le 11 \times 2^{12} < 2^{16}\) , and \(\delta [d,x] \ge 2 \times 2^M - P_x \times 2^k > 0\) . Therefore \(\delta [d,x]\)  is in range of unsigned 16 bit integer.

If \(S \in [P_x \times 2^k, 2^{M+1})\) , then \(\delta [d,x] + S \ge \delta [d,x] + P_x \times 2^k = k \times 2^M\) , and \(\delta [d,x] + S < k \times 2^M - P_x \times 2^k + 2^{M+1} \le k \times 2^M - 2^M + 2^{M+1} = (k+1)\times 2^M\) . Therefore, in this case, \(\lfloor \frac{\delta [d,x]+S}{2^M} \rfloor = k\) .

If \(S \in [2^M, P_x \times 2^k)\) , then \(\delta [d,x] + S < \delta [d,x] + P_x \times 2^k = k \times 2^M\) , and \(\delta [d,x] + S >= k \times 2^M - P_x \times 2^k + 2^M > k \times 2^M - 2^{M+1} + 2^M = (k-1) \times 2^M\) . Therefore, in this case, \(\lfloor \frac{\delta [d,x]+S}{2^M} \rfloor = k - 1\) .

Corollary 2.1 
In general, when \(M \le 11\) , \(\delta \)  can be represented as a 16 bit signed integer.

If one is using distributions different from us, then the range of \(P_x\)  may changed to \([1, 2^M)\) , which means the probability of one symbol may be at least \(0.5\) , then the condition is changed to the one shown in Corollary REF . The proof is almost the same with Lemma REF .
Corollary 2.2 When \(M \le 12\) , ANS-AI encoding requires \(4 \times D \times X\)  bytes of memory, and decoding requires \(D \times 2^{M+2}\)  bytes.


Speed comparison of rANS and ANS-AI
We compare the speed of rANS coder and ours in the same machine as stated in experiment section of the main body. For fair comparison, both coders are implemented using C++ with OpenMP, and run on CPU. As is shown in table:throughputransai, ANS-AI is 10 to 100 times faster than rANS.
<TABLE>
GPU Coder vs CPU Coder
We use the same algorithm we designed to create a CPU Coder. As shown in tab:cpucodergpucoder, we compare the composition throughput between CPU Coder and GPU Coder. The CPU Coder is set to 16 threads. We duplicate the CIFAR10 validation set for ten times for experiment.
Compress. In terms of compression time, the throughput of CPU and GPU coders is comparable because both require two RAM-GPU transfers. We notice that GPU to RAM time is different between the two Coder. Because the residual data, latent data, and distribution parameters must all be transferred from GPU to RAM for CPU Coder, but only compressed data must be transferred from GPU to RAM for GPU Coder, which takes less time.
<TABLE><TABLE>Decompress. The CPU Coder requires two additional RAM-GPU transfers during decompression because the Coder decoding is done on the CPU. The CPU Coder decodes latent vector indexes before sending them to the GPU. Then we need to transmit the distribution parameters to RAM after VQ-VAE decodes them. The residual is then decoded by the Coder and passed back to the GPU. The Three-Way Auto-regressive recovers original data from residual data. The GPU Coder, on the other hand, only requires two RAM-GPU transfers, and all Coder decoding is done on the GPU, which saves a lot of time.
<FIGURE><TABLE><TABLE>
Model architecture
We do further experiments to see how different codebook sizes and dimensions affect the results.
A large codebook size or codebook dimension favors the BPD but reduces performance, as seen in tab:resblockandcodebook. A tiny codebook size or codebook dimension does indeed produce substantially faster throughput, but it would contains relatively little information when applying our model to high resolution images. As a result, on codebook size/dimension, there is a trade-off between BPD and throughput. To balance the trade-off, we set the codebook size to 256 and the codebook dimension to 32 in our framework.
We investigate the impact of various model capacities. We modify the number of residual block and the mid channel dimension to change the model capacity. As shown in tab:resblockandcodebook, the larger model achieves lower BPD, but the throughput of the model drops even faster, which deviates from the 'practical' aim. As a result, we adjust our model to 4 residual blocks and 32 mid channel dimensions.

Receptive field rules of AR model
fig:receptivefield demonstrates the receptive field rules of the auto-regressive model on a single channel which we use in the ablation study. As the figure suggests, these receptive field settings cannot be parallelized using what we implement in Three-Way Auto-regressive.

Parallel vs No Parallel
We add the experiment result of Three-Way Auto-regressive without parallel. As shown in tab:w/oparallel, Three-Way Auto-regressive using our designed parallel mechanism achieves the fastest throughput with competitive compression ratio.

Why predict residual given original image?
We investigate the different input of VQ-VAE model. We use the original image, reconstruction image, residual, and original image concatenated with residual to predict the residual. As illustrated in tab:vqvaediffinputs, directly using residual to predict residual is not the best solution. As the original image has a lot of spatial information, we choose to model the residual given original image.
