Meta Adaptive ANS

[Manan-J98]

Hi, I would like to read more about how meta-adaptive ANS trees work and how is it different from a MANIAC tree. The comment on this https://gitlab.com/wg1/jpeg-xl/-/issues/55#note_432479750 by @jonsneyers did help me get an insight but it will be really helpful if someone could provide some resources or an explanation on how exactly does MAANS work.

This is not an issue/bug, Apologies in advance.

[jonsneyers]

The main difference between MAANS and MANIAC is the entropy coding 'backend' — both use MA trees as a way to determine the context, but in MAANS the entropy coding is ANS with fixed histograms per context, while in MANIAC it is basically CABAC with dynamically updated probabilities per context.

Another important difference between the MA trees of MANIAC/FLIF and the MA trees of MAANS/JXL is that in JXL, the MA tree does not only determine the context, but also the predictor and even a multiplier ("quantization factor") and offset.
In FLIF, predictors are fixed per channel, e.g. the entire channel is using the ClampedGradient predictor. In JXL, the predictor choice can vary per context.

Other than that, both MAANS and MANIAC are based on a decision tree that is signaled (so can be chosen by the encoder / adapted based on image contents), where decision nodes are of the form if [property] > [value] then BRANCH1 else BRANCH2. The set of properties that can be used is larger in JXL than in FLIF, but other than that, the idea is the same. The main advantage of using a decision tree is that an encoder can create few but relevant contexts (compared to the usual way of doing context modeling, which is to take a cartesian product of some quantized properties, which tends to create many irrelevant contexts while missing precision in the segmentations that can be done).

In FLIF, the leaf nodes of this tree are just CABAC contexts (i.e. a set of dynamically updated probabilities), while in JXL they are a context ID plus predictor choice plus multiplier/offset. The context IDs can be shared between leafs, making it effectively a DAG and not a tree. This is useful since in JXL the histograms are static and fully signaled (so there is some signaling cost), while in FLIF they are dynamically updated and not signaled at all (in FUIF the initialization is coarsely signaled but it's still MANIAC with dynamically updated probabilities).

I hope this helps to explain things a bit more. Probably we should at some point write a paper (something like this one: https://flif.info/papers/FLIF_ICIP16.pdf) about JPEG XL's entropy coding.