Encoding FLAC residuals (alternatives to Rice encoding)

[flubadubadoo]

I've been wanting to work on a pet project to basically re-implement FLAC (lossless audio codec). It seems like at a very high level there is a predictor, then a coding applied to compress the residuals (error) of the predictor. While FLAC uses Rice coding to compress these, I noticed that the format reserves a space for extra types of codings.

So I was thinking to make this more interesting, then maybe we can compress these codes with Huffman, arithmetic coding, etc. and see what that looks like. Recently I have been made aware of various ANS implementations (FSE, etc.) and their success - maybe even more interesting to implement, and could maybe allow for better compression ratios.

However, I'm wondering if there exists some sort of corpus for FLAC residual bitstreams or if the probability distribution of these residuals (for most music/audio files) is known to any extent, which would inform whether or not ANS/arithmetic coding would bring any compression ratio benefits in the first place. According to the FLAC format these numbers are typically small, which is why Rice is efficient, but I can't seem to find anything about their distributions.

[Shelwien]

You can compare FLAC compression with results of other lossless audio codecs which use arithmetic coding, like Monkey's Audio or optimfrog
(though the latter likely has a better predictor too).
Based on squeezechart wav stats:

SAC  21324487+65919345+20771857+22759276+25340833+52216710 = 208332508
OFR  21394272+65905363+20880497+23179339+25262790+52433236 = 209055497
MAC  21773012+66797828+21499324+23246616+25823788+52855336 = 211995904
FLAC 22369503+69547135+22708163+24927481+26791804+54394889 = 220738975

(1-211995904/220738975)*100 = 3.96%
(1-208332508/220738975)*100 = 5.62%

You can expect about 4% compression improvement over FLAC by using better entropy coding, and another 1.5% by using too much computing time.

In any case, residuals for testing should be easy to acquire since flac is open-source.

[Jarek]

Residuals are typically from Laplace distribution centered in zero: rho(x) = exp(-|x|/b) / 2b
Here is penalty of using Golomb comparing to accurate entropy coding, strongly depends on width b:



The difficulty is choosing this b based on context, also adapt such model - here are some techniques: https://arxiv.org/pdf/1906.03238

In short, MLE estimation is just: b = average of |x|
For context dependence you need to predict b e.g. using some linear combination of functions of context, or neural networks to minimize: (b(context) - |x|)^2
Simplest adaptivity is replacing this average with exponential moving average- use update step: b <- mu * b + (1-mu) |x|

In practice you can have prepared entropy coder for some discretization of b, encoder and decoder need to choose the same.
Here was supposed to be discussion about it: https://encode.su/threads/3124-LOCO-...ny-alternatves

[dnd]

Probably, it is simple to insert file write statements in the FLAC file output functions.
Write the integer values into a raw 32 bits format for better testing.

Possible methods for encoding with entropy coding:
1 - Encode the rice coding output with a bitwise range coder like Turbo-Range-Coder instead of bit I/O.
You can use (length limited) rice coding for the quotient and code the remainder with bit i/o.

2 - Encode the residuals with variable length coding using a range coder, Huffman or ANS.
- Gamma Coding with RC: You can test this with the gamma coding in Turbo-Range-Coder
​ by writing the integer values into a raw 32 bits file.
- Golomb/Rice Coding with RC: Encode the quotient with RC like in RC gamma coding and encode the remainder with bit i/o
- Limited Length Golomb/Rice Coding: use the same golomb parameters like in FLAC.
Encode the length limited part (ex. 8 bits) with a fixed length entropy coder (RC, Huffman or ANS) and the remainder with bit i/o

[WinnieW]

What I know:
In the lossless audio codec MPEG-4 ALS an algorithm named Block Gilbert Moore Coding (BGMC) is used to code residuals. There is a PDF document that provides some information about it.