Lepton Free Format Compresses JPEG Files by 22% Lossless

Pied Piper arithmetic coding

Prediction of discrete cosine transform coefficients in adjacent 64-bit JPEG blocks

The company Dropbox has published the source code of a new format of stream compression of images Lepton ( repository on Github ). The source code of Lepton is published under the free Apache license. Everyone is invited to optimize the new free algorithm.

Lepton demonstrates an average compression ratio of 22% on JPEG files, predicting DCT coefficients in JPEG blocks and considering these coefficients as a context for an arithmetic coder, that is, encoding the delta coefficients in neighboring blocks.

How does Lepton work?

As is known, the JPEG format splits images into blocks of 8 × 8 pixels. Each such block is subjected to discrete cosine transform (DCT) with the calculation of 10-bit DCT coefficients for brightness and chrominance. Thus, the 16 × 16 image will be encoded into four JPEG blocks of 64 DCT coefficients each.
')


The resulting 10-bit DCT coefficients are quantized and packed using serial coding and Huffman codes.

The JPEG standard also allows for the use of much more efficient arithmetic coding , but due to patent restrictions (the patent for the arithmetic QM coder described in the JPEG standard belongs to IBM), it was rarely used in practice.

The Lepton algorithm runs through coefficients from a block in a zigzag fashion, encoding data with a VP8 arithmetic coder .



The coding efficiency increases significantly if you carefully select the context information from the previous 64-bit block in the image. For example, predicting the value of coefficients for specific pixels by the values ​​from the border pixels in the adjacent block.





Lepton performs other arithmetic with coefficients. For example, an additional advantage is obtained by transferring the luminance factor to the end of the chain after all the chromaticity coefficient. In addition, in this format, the values ​​of the coefficients are written in a more compact binary representation, discarding the first one, because in all binary values ​​greater than zero, the first character is one.



The method of predicting coefficients in neighboring blocks by analyzing them using this information for lossless compression was described in the series “Silicon Valley”, invented by the fictional company Pied Piper. In the frame from the film, this agorhythm is shown on one of the slides of the presentation with the caption “MIDDLE OUT !!”

Performance

Coding only the luminance factor delta allows you to reduce their volume by 39% in a typical JPEG file, where luminance factors usually take about 8% of the file size. But along with other compression techniques, the overall compression ratio is, on average, 22%. The graph shows the result of processing 10,000 images in a test sample from various digital cameras and smartphones.



JPEG files are compressed at a speed of 5-9 MB / s, decompression is 15-25 MB / s, consuming 24 MB of RAM, on an Intel Xeon E5 2650 v2 2.6 GHz computer, the developers write.

Dropbox used the Lepton format to encode 16 billion images on Dropbox hosting, freeing up a few petabytes. Now, Dropbox is rapidly moving to work on coding all the old files: this will significantly save on the amount of information stored. Data integrity is guaranteed by the encoding process: each file is compressed bit-by-bit with the original after compression and decompression, and only after that the original copy is deleted. For additional security, Lepton, at the Linux kernel level, runs the seccomp system call seccomp , which prohibits all system calls except read and write operations for already open file descriptors.

JPEG out of date

Currently, there are many image compression formats that exceed JPEG in compression ratio and speed of operation. For example, the WebP format also uses a VP8 encoder and is superior to JPEG in performance. The WebP format is supported in many browsers and is increasingly used to publish images on the Internet.

There is also the free FLIF format, which in tests even surpasses WebP. As shown by comparative testing ( results ), FLIF files on average:

• 14% less than lossless WebP,
• 22% less than lossless BPG,
• 33% less than PNG with brute force through ZopfliPNG,
• 43% less typical PNG,
• 46% less than PNG optimized by Adam7 interlaced image processing algorithm
• 53% less lossless JPEG2000,
• 74% less lossless JPEG XR.

Even if for each individual image to choose the best compression format among competitors, depending on the type of picture - photo, graphics, 8 bits or more - FLIF still has an advantage of about 12% in the median (or 19% on average). Thus, the key advantages of FLIF are the best compression ratio and versatility, working with any kind of images. FLIF defeats all competitors on all types of images . The results of comparative testing by type of images, see here .



The problem is that it is very difficult to refuse outdated JPEG in favor of WebP or FLIF: this format has become too widespread. So Lepton's “backward compatible” format can be useful as a temporary solution. If you keep 5 gigabytes of photos on disk, you can quickly free up 1 gigabyte of disk space using lossless compression.