Lossless Picture Compression in O(n) Time
— Wednesday, November twenty fourth 2021
Introducing QOI — the Quite OK Image Format. It losslessly compresses RGB and
RGBA pictures to an analogous measurement of PNG, whereas providing a 20x-50x speedup in
compression and 3x-4x speedup in decompression. All single-threaded, no
SIMD. It is also stupidly easy.
tl;dr: 300 strains of C, single header,
source on github,
benchmark results here.
I need to preface this text by saying that I don’t know what I am doing.
I am not a compression man. I barely perceive how Huffman Coding and DCT works.
Fortunately, QOI makes use of neither.
I used to be simply tinkering with some concepts that I thought would possibly compress
pictures. The end result shocked me fairly a bit.
Why? A Quick Rant.
File codecs. They suck. I completely detest the same old suspects. PNG, JPEG or
even worse MPEG, MOV, MP4. They burst with complexity on the seams. Each tiny
side screams “design by consortium”.
Some time in the past I dabbled into MPEG a
bit. The essential concepts for video compression in MPEG are ingenious, much more so
for 1993, however the ensuing file format is an abomination.
I can nearly image the assembly of the Shifting Image Consultants Group the place
some random swimsuit demanded there to be a strategy to point out a video stream is
copyrighted. And thus, the copyright bit flag made its method into the usual
and efficiently stopped film piracy earlier than it even started.
MPEG, an business customary conceived 3 many years previous, all patents lengthy expired,
all skilled curiosity deserted. But, the holy specification —
there named ISO/IEC 11172-2 — is a effectively guarded secret, revealed solely to these
that fork over a cool $200 to endow the sacred work of the ISO.
Various open video codecs exist, however are once more immensely advanced. They
compete with the state-of-the-art, require enormous libraries, are compute hungry
and troublesome to work with. Options for PNG all compete on the compression
ratio too, with ever growing complexity.
There completely is a marketplace for video, audio and picture codecs that commerce
compression ratio for pace and ease, however nobody is serving it. (Effectively,
these guys maybe, nevertheless it’s all proprietary.)
Sure, stb_image saved us all from the pains of
coping with libpng and is subsequently utilized in numerous video games and apps. Some time
in the past I aimed to do the identical for video with
pl_mpeg, with some success.
However with all that we realized, why did nobody return and implement a easy
compression scheme to compete with PNG, however with out the cruft? Why did nobody
implement a easy video compression scheme much like MPEG, however in a sane
file format as an alternative?
I used to be tinkering to do the latter: to take elements of MPEG-1 and make it simpler to
parse, simpler to speed up on a GPU. A adequate video codec.
As a substitute I stumbled into an answer for the previous: a lossless picture format that
competes with PNG for some use circumstances. A barely worse compression ratio, however
magnitudes much less complexity.
Technical Particulars
QOI encodes and decodes pictures in a single go. It touches each pixel simply
as soon as.
Pixels are encoded as
- a run of the earlier pixel
- an index into an array of beforehand seen pixels
- a distinction to the earlier pixel worth in r,g,b
- full r,g,b or r,g,b,a values
The ensuing values are packed into chunks beginning with a 2- or 8-bit tag
(indicating a kind of strategies) adopted by various information bits. All of
these chunks (tag and information bits) are byte aligned, so there isn’t any bit twiddling
wanted between these chunks.
The totally different chunk sorts are:
1. A run of the earlier pixel
If the present pixel is strictly the identical because the earlier pixel, the run size
is elevated by 1. When a pixel is encountered that’s totally different from the
earlier one, this run size is saved to the encoded information and the present pixel
is packed by one of many different 3 strategies.
┌─ QOI_OP_RUN ────────────┐
│ Byte[0] │
│ 7 6 5 4 3 2 1 0 │
│───────┼─────────────────│
│ 1 1 │ run │
└───────┴─────────────────┘
2-bit tag b11
6-bit run-length repeating the earlier pixel: 1..622. An index right into a beforehand seen pixel
The encoder retains a operating array of the 64 pixels it beforehand encountered.
When the encoder finds the present pixel nonetheless current on this array, the index
into this array is saved to the stream.
To maintain issues O(n) when encoding, there’s just one lookup into this array.
The lookup place is decided by a “hash” of the rgba worth (actually simply
(r * 3 + g * 5 + b * 7 + a * 11). A linear search or some extra advanced bookkeeping
would end in a slightly higher compression ratio, however would additionally gradual issues
down a bit.
┌─ QOI_OP_INDEX ──────────┐
│ Byte[0] │
│ 7 6 5 4 3 2 1 0 │
│───────┼─────────────────│
│ 0 0 │ index │
└───────┴─────────────────┘
2-bit tag b00
6-bit index into the colour index array: 0..633. The distinction to the earlier pixel
When the present pixel coloration isn’t too removed from the earlier one, the
distinction to the earlier pixel is saved to the stream.
This is available in 2 totally different flavors, relying on how huge the distinction is. Notice
that this focuses on the RGB worth; alpha modifications are extra pricey.
┌─ QOI_OP_DIFF ───────────┐
│ Byte[0] │
│ 7 6 5 4 3 2 1 0 │
│───────┼─────┼─────┼─────│
│ 0 1 │ dr │ dg │ db │
└───────┴─────┴─────┴─────┘
2-bit tag b01
2-bit crimson channel distinction from the earlier pixel -2..1
2-bit inexperienced channel distinction from the earlier pixel -2..1
2-bit blue channel distinction from the earlier pixel -2..1
┌─ QOI_OP_LUMA ───────────┬─────────────────────────┐
│ Byte[0] │ Byte[1] │
│ 7 6 5 4 3 2 1 0 │ 7 6 5 4 3 2 1 0 │
│───────┼─────────────────┼─────────────┼───────────│
│ 1 0 │ diff inexperienced │ dr - dg │ db - dg │
└───────┴─────────────────┴─────────────┴───────────┘
2-bit tag b10
6-bit inexperienced channel distinction from the earlier pixel -32..31
4-bit crimson channel distinction minus inexperienced channel distinction -8..7
4-bit blue channel distinction minus inexperienced channel distinction -8..74. Full rgb/rgba values
If all earlier strategies fail, the rgb or rgba values are saved to the stream as full bytes.
┌─ QOI_OP_RGB ────────────┬─────────┬─────────┬─────────┐
│ Byte[0] │ Byte[1] │ Byte[2] │ Byte[3] │
│ 7 6 5 4 3 2 1 0 │ 7 .. 0 │ 7 .. 0 │ 7 .. 0 │
│─────────────────────────┼─────────┼─────────┼─────────│
│ 1 1 1 1 1 1 1 0 │ crimson │ inexperienced │ blue │
└─────────────────────────┴─────────┴─────────┴─────────┘
8-bit tag b11111110
8-bit crimson channel worth
8-bit inexperienced channel worth
8-bit blue channel worth
┌─ QOI_OP_RGBA ───────────┬─────────┬─────────┬─────────┬─────────┐
│ Byte[0] │ Byte[1] │ Byte[2] │ Byte[3] │ Byte[4] │
│ 7 6 5 4 3 2 1 0 │ 7 .. 0 │ 7 .. 0 │ 7 .. 0 │ 7 .. 0 │
│─────────────────────────┼─────────┼─────────┼─────────┼─────────│
│ 1 1 1 1 1 1 1 1 │ crimson │ inexperienced │ blue │ alpha │
└─────────────────────────┴─────────┴─────────┴─────────┴─────────┘
8-bit tag b11111111
8-bit crimson channel worth
8-bit inexperienced channel worth
8-bit blue channel worth
8-bit alpha channel worthThat is it.
You probably have a minute, please learn by means of the
qoi.h supply.
Onward
Significantly, I am dumbfounded. BMP and TIFF have run-length-encoding after which GIF
comes round with LZW. However there’s nothing in between. Why? I discovered the house
between RLE and LZW to be giant sufficient to spend many days on. And there is a lot
extra to discover.
Engaged on QOI was numerous enjoyable. I had a “take a look at runner” with some pattern
pictures mendacity round. Seeing how each change I made affected the compression
ratio was fairly thrilling.
With some extra work, QOI might function the premise for a lossless video codec,
appropriate for screencasts and the like.
SIMD acceleration for QOI would even be cool however (from my very restricted information
about some SIMD directions on ARM), the format does not appear to be effectively suited
for it. Perhaps somebody with a bit extra expertise can shed some gentle?
I am additionally fairly hyped to discover the even bigger house of a easy, lossy
picture compression format. Many texture compression schemes have very thrilling
concepts, but there’s nothing that competes with JPEG however with much less complexity.