Lepton: A Lossless JPEG Compression Format
Dropbox has open-sourced Lepton, a streaming image compression format that reduces the size of existing JPEG files by 22% without altering a single bit of the original data. The format encodes JPEG files at 5 MB/s and decodes them back to the original bits at 15 MB/s, using less than 24 MB of memory. Lepton has already been used to encode 16 billion images stored on Dropbox, saving multiple petabytes of storage.
The compression is built on predicting coefficients within JPEG blocks and feeding those predictions as context into an arithmetic coder. The project is available under the Apache license, and Dropbox is inviting community contributions to further develop the algorithm.
How JPEG compression works
JPEG divides an image into 8×8 pixel blocks, each represented as 64 signed 10-bit coefficients. These coefficients are produced by a reversible Discrete Cosine Transform (DCT). One coefficient, the DC, captures the overall brightness of the entire 8×8 block. The remaining 63 AC coefficients encode the fine detail within the block—textures like sand on a beach or the weave of a fabric.
When viewed together, the DC values of all blocks form a thumbnail of the original image at one-eighth the resolution. The AC coefficients progressively add detail to that thumbnail as they are decoded sequentially.
Encoding AC coefficients
Lepton first records the number of non-zero AC coefficients in a block, then traverses the 8×8 block in zigzag order. Each coefficient is written using a three-part scheme:
- A unary-coded length indicating how many bits the coefficient's binary representation needs
- A sign bit: 1 for positive, 0 for negative
- The absolute value of the coefficient in standard binary, minus its leading 1 (which is redundant for non-zero values)
For example, the value 47 would be encoded with a run of ones equal to its bit length, followed by a zero terminator, then the sign bit, and finally the binary digits after the leading 1.
This representation produces fewer symbols for the typical coefficient distributions found in JPEG files than pure unary or fixed-length two's complement coding. The encoded symbols are then passed through the VP8 arithmetic coder, which uses context from adjacent regions of the image to achieve high compression efficiency.
Improving DC coefficient compression
DC coefficients occupy more than 8% of a typical iPhone photo, making them a worthwhile compression target. Most formats place DC values before AC coefficients, but Lepton reverses this order, encoding each block's DC last. This lets the decoder use the fully-coded AC coefficients and neighboring blocks as context for predicting the DC value, and only the prediction delta needs to be stored.
Predicting DC from boundary pixels
One straightforward approach is to find the brightness that minimizes differences across the 16 boundary pixels shared with the block above and the block to the left. Averaging over a median of 8 of those pixels reduces the DC data by about 30% over baseline JPEG.
However, natural images rarely contain sharp brightness discontinuities at 8×8 block boundaries. A more accurate model accounts for smooth gradients, such as a sky that fades from blue to orange. A good predictor should continue those gradients across block borders rather than assuming they stop abruptly.
Middle-out gradient prediction
Because the DC coefficient represents brightness and gradients are brightness-independent, Lepton can estimate gradients within the current block (from its AC coefficients) and from the fully-decoded neighboring blocks. It computes two gradients: one from the second row of the current block toward its edge, and one from the neighbor block back toward that same edge.
The prediction point is where these two gradients meet, between the edge pixels of adjacent blocks. The delta between the actual DC and this predicted value is then encoded using the same length-sign-residual scheme as the AC coefficients. This approach trims the stored size of DC coefficients to just 61% of their original size—a 39% saving on a component that makes up about 8% of a typical JPEG file.
Deployment and verification
Lepton is designed for safety and determinism. It runs inside a seccomp sandbox that permits only reads and writes to already-open file descriptors. Dropbox verified bit-exact decode determinism on over 4 billion photos: once an image is confirmed to decode back to its original bits, it will always decode that way in the future.
Every compressed file is decoded at least once and compared bit-for-bit against the input before it is persisted. During this verification, compressed files are held in kernel-protected read-only memory, ensuring they cannot be altered mid-check.
The resulting format is fully streamable, so decompression can run concurrently with a file's network transfer, hiding much of the computational latency. Lepton achieves consistent 22% savings across a broad range of images from modern cameras and phones, and its open-source code is now available for developers to examine, use, and improve.
