Lair Of The Multimedia Guru


FFmpegs Huffyuv

In the last few weeks FFmpegs huffyuv codec has grown the ability to encode and decode a much broader list of pixel formats. From planar rgb variants 4:4:4 YUV to 4:1:0 YUV and bit depths up to 16bit and alpha support.
One might ask why anyone cares about all this, the awnser is simple

1 thread YUV420 10bit, matrixbench
FFv1 Huffyuv
encode fps 63fps 281fps
decode fps 82fps 418fps
filesize 478mb 765mb

Encoding parameters used:
-an -threads 1 -pix_fmt yuv420p10le -strict -2 -vcodec ffvhuff -context 1
-an -threads 1 -pix_fmt yuv420p10le -strict -2 -vcodec ffv1

6 threads YUV420 10bit, matrixbench
FFv1 Huffyuv
encode fps 269fps 1173fps
decode fps 386fps 2675fps
filesize 480mb 771mb

Encoding parameters used:
-threads 6 -an -pix_fmt yuv420p10le -strict -2 -vcodec ffvhuff -pass 2 test.nut
-threads 6 -an -pix_fmt yuv420p10le -strict -2 -vcodec ffv1 -level 3 -slices 6 test1.nut

As can be seen above huffyuv while it doesnt even get close to ffv1 in terms of compression even though i used per frame huffman tables and 2pass mode in the 2 tests, its simply much faster.

Filed under: Entropy Coding,FFmpeg,VideoCoding — Michael @ 02:27



I always wanted to write my own general purpose compressor, a short while ago i actually did. Its based on the BWT + MTF variant described in yesterdays blog post + snows/ffv1s range coder with a state transition table borrowed from bbb/paq8 source code under GPL is of course available too.

compressed file sizes of the Canterbury Corpus

alice29.txt asyoulik.txt cp.html fields.c grammar.lsp kennedy.xls lcet10.txt plrabn12.txt ptt5 sum xargs.1
bzip2 1.0.3 43202 39569 7624 3039 1283 130280 107706 145577 49759 12909 1762
7zip 4.43 beta 48555 44606 7692 3076 1350 50904 119569 165462 42153 9619 1860
bbb ver. 1 40839 37818 7736 3253 1349 76523 101117 135829 44816 12593 1792
mnzip r32 with plain MTF 42698 39286 7572 2962 1227 19804 105883 143634 50624 12591 1698
mnzip r32 40950 37835 7431 2983 1237 19287 101140 137191 45604 12428 1699

Time needed to compress

alice29.txt asyoulik.txt lcet10.txt plrabn12.txt cp.html fields.c grammar.lsp kennedy.xls ptt5 sum xargs.1
bzip2 1.0.3 0m0.166s 0m0.133s 0m0.533s 0m0.633s 0m0.047s 0m0.037s 0m0.007s 0m1.062s 0m0.151s 0m0.056s 0m0.006s
7zip 4.43 beta 0m0.539s 0m0.417s 0m1.732s 0m2.161s 0m0.070s 0m0.035s 0m0.019s 0m6.048s 0m1.402s 0m0.105s 0m0.022s
bbb ver. 1 0m2.675s 0m2.271s 0m7.455s 0m8.599s 0m0.559s 0m0.344s 0m0.230s 0m17.446s 0m45.407s 0m0.813s 0m0.235s
mnzip r32 0m0.273s 0m0.206s 0m0.951s 0m1.099s 0m0.031s 0m0.012s 0m0.006s 0m3.545s 0m1.173s 0m0.051s 0m0.006s

time needed to decompress

alice29.txt asyoulik.txt lcet10.txt plrabn12.txt cp.html fields.c grammar.lsp kennedy.xls ptt5 sum xargs.1
bzip2 1.0.3 0m0.063s 0m0.049s 0m0.177s 0m0.222s 0m0.007s 0m0.003s 0m0.002s 0m0.210s 0m0.053s 0m0.009s 0m0.003s
7zip 4.43 beta 0m0.033s 0m0.027s 0m0.066s 0m0.085s 0m0.009s 0m0.011s 0m0.007s 0m0.099s 0m0.043s 0m0.016s 0m0.006s
bbb ver. 1 0m2.265s 0m1.918s 0m6.015s 0m6.916s 0m0.511s 0m0.332s 0m0.231s 0m13.492s 0m6.660s 0m0.715s 0m0.237s
mnzip r32 0m0.073s 0m0.061s 0m0.215s 0m0.261s 0m0.010s 0m0.005s 0m0.003s 0m0.441s 0m0.155s 0m0.017s 0m0.002s

Options used where -9 for bzip2, -mx=9 for 7zip, f for bbb to use fast but memory hungry mode (this doesnt affect compression rate for bbb). The benchmark score are just single run based no proper mean so dont take them too serious, and i hope ive not messed up the file order ;)

Patches are welcome!

Filed under: Entropy Coding — Michael @ 01:20


Move to front coder/transform

First a little explanation about what a move to front coder is. Its a revesible transform which remaps symbols to an index into a table which initially contains (0,1,2,3,…) and every time a symbol is used its moved to the front of the table.

example: input: “to be or not to be” initial table: (abcdefghijklmnopqrstuvwxyz), for the first ‘t’ we output 19 as its the 19th entry in the table and move it to the front to build the new table (tabcdefghijklmnopqrsuvwxyz) the complete list of steps looks like:

abcdefghijklmnopqrstuvwxyz  19(t)
tabcdefghijklmnopqrsuvwxyz  15(o)
otabcdefghijklmnpqrsuvwxyz  27( )
 otabcdefghijklmnpqrsuvwxyz 4(b)
b otacdefghijklmnpqrsuvwxyz 7(e)
eb otacdfghijklmnpqrsuvwxyz 2( )
 ebotacdfghijklmnpqrsuvwxyz 3(o)
o ebtacdfghijklmnpqrsuvwxyz 19(r)
ro ebtacdfghijklmnpqsuvwxyz 2( )
 roebtacdfghijklmnpqsuvwxyz 17(n)
n roebtacdfghijklmpqsuvwxyz 3(o)
on rebtacdfghijklmpqsuvwxyz 6(t)
ton rebacdfghijklmpqsuvwxyz 3( )
 tonrebacdfghijklmpqsuvwxyz 1(t)
t onrebacdfghijklmpqsuvwxyz 2(o)
ot nrebacdfghijklmpqsuvwxyz 2( )
ot nrebacdfghijklmpqsuvwxyz 6(b)
bot nreacdfghijklmpqsuvwxyz 6(e)

As you can see the mtf transform will generally favor small numbers on “non random” data, on its own its not too usefull for compression but together with the BWT and a simple order 0 entropy coder its a pretty good general purpose compressor.

Now to the actual reason why i am writing this blog entry, can you use the symbol which the index represents as context for the entropy coder coding the index? You say no because thats like knowing the index together with the table.

Well if you think so, you are wrong, the trick is not to know the table :)

First to compress our data we run an mtf transform over it, we store the mtf table after the whole transform (this is not strictly needed but simplifies things). Next we encode the indexes from the end to the begin each time moving the zero entry of our table to the point pointed to by the index, each time we do know the symbol before the index and so can use it as context. This really is nothing else as the MTF coder in reverse.

An example, we start with the table (ebot nracdfghijklmpqsuvwxyz), the first symbol is ‘e’ the corresponding index is 6 (we know this from the forward MTF pass), so we store 6 with context ‘e’ and move e to the 6th place to find the table (bot nreacdfghijklmpqsuvwxyz), the next steps are all just the same than the MTF example above just in reverse.

Decompression is pretty much the same, read the table (again this isnt needed but its simpler as it avoids a 2nd pass over the data) then take the value from position 0 of the table and use it as context to decode the next index, after that use the index to move the entry from position 0 to its new position and repeat until you are out of input data.

Filed under: Entropy Coding — Michael @ 23:09


Universal vlc codes

Its quite well known that to optimally store some variable x with value v, we should use -log2(p) bits where p is the probability that x has value v, obviously the decoder has to know the probability distribution the encoder used or the bitstrings generated from that to be able decode it…
now if we limit ourselfs to an interger count of bits then huffman codes are optimal, building an huffman code is trivial, just recursively merge the 2 least probable symbols, but if there are many different variables with different probablility distributions or the maximum value is large or unbounded or you dont know the probabilities or you want low complexity then huffman codes might be a bad choice

Universal vlc codes might be a better choice, they all assume small values are more likely and often have very good compression rates
heres a table of common ones

v Unary Unary2 Exp Golomb Exp Golomb2 Fibonacci rice k=2 rice k=3
0 0 0 0 0 11 00 000
1 10 11 100 101 011 01 001
2 110 101 101 111 0011 100 010
3 1110 1001 11000 10001 1011 101 011
4 111110 10001 11001 10011 00011 1100 1000
5 1111110 100001 11010 11001 10011 1101 1001
6 11111110 1000001 11011 11011 01011 11100 1010
7 111111110 10000001 1110000 1000001 000011 11101 1011
8 1111111110 100000001 1110001 1000011 100011 111100 11000

Note1: Exp Golomb2 is identical to Exp Golomb except that its a reversible vlc, it can be decoded from right to left too, same for Unary2 and Unary

The smart reader will probably have noticed that Exp Golomb coding is simply unary coding for the number of bits + the bits, and rice coding is unary coding with k bits, more generally you can take any vlc code to encode some “class” and then give every such class its own number of additional bits

The ideal choice of uvlc code depends upon the probability distribution of the values which will be encoded, there is no single perfect one

Well, hmm there was something else …ahh yes negative numbers, we where just dealing with positive ones above, negative ones are trivial, just map them to odd positive ones and map the actual positive ones to even ones or the other way around
in C the following will do the trick quickly:

v = -2*i-1;
v ^= v>>31;

and the following will reverse it:

(v>>1) ^ -(v&1)
Filed under: Entropy Coding — Michael @ 22:18

Powered by WordPress