Subject: [Cellar] [PATCH FFV1] Quantization table sets and contexts

From: Jerome Martinez <[email-masked]>
Date: Fri, 14 Apr 2017 16:34:13 +0200

I had difficulties to understand FFV1 quantization table sets, 
quantization tables and context, with some items not defined (e.g. abs() 
of a table).

I propose the following patch:
- I reuse "quantization table set" name when relevant (this words were 
already present, I put them everywhere)
- I added info about which quantization table set is used (or did I miss 
it somewhere else?)
- "Table_" replaced by quant_tables[i][j][k] as it is already used 
elsewhere in the spec
- Looks like the scale is indicated twice (in "Quantization Tables" 
chapter and in "context" chapter), I removed one (the one in "context" 
chapter)
- "The second half doesn’t need to be stored as it is identical to the 
first with flipped sign." is misleading from my point of view as values 
are mirrored, the first value of this second half is a copy of the last 
value of the first half so the the first value is discarded during the 
"identical" process, I removed the sentence and added a reference to the 
pseudo code. Is it intended that it is not an exact mirror? (I have no 
idea about maths behind that, I just see an incoherency between text and 
code)
- I changed the type of the length of "number of equal entries -1" from 
signed to unsigned, looks like this is unsigned in reality
- removed MAX_CONTEXT_INPUTS as this constant is hard coded to "5" 
everywhere in the spec and depends of design choices about the context
- some formatting

A Pull request is open on GitHub:
https://github.com/FFmpeg/FFV1/pull/56

Jérôme

From 5823a720054c8945052e91bd97b9e022ab894d20 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=B4me=20Martinez?= <[email-masked]>
Date: Fri, 14 Apr 2017 14:25:56 +0200
Subject: [PATCH] Improvement of context and quantization tables paragraphs

---
 ffv1.md | 67 +++++++++++++++++++++++++++++++++++++++--------------------------
 1 file changed, 40 insertions(+), 27 deletions(-)

diff --git a/ffv1.md b/ffv1.md
index 0af341b..8021174 100644
--- a/ffv1.md
+++ b/ffv1.md
@@ -191,6 +191,8 @@ Background: a two's complement signed 16-bit signed integer was used for storing
 
 ## Context
 
+For samples, compared to pixel X, named:
+
 ```
 +---+---+---+---+
 |   |   | T |   |
@@ -201,28 +203,41 @@ Background: a two's complement signed 16-bit signed integer was used for storing
 +---+---+---+---+
 ```
 
-The quantized sample differences L-l, l-tl, tl-t, t-T, t-tr are used as context:
+The quantized sample differences are used as context:
 
-PDF:$$context=Q_{0}[l-tl]+\left|Q_{0}\right|(Q_{1}[tl-t]+\left|Q_{1}\right|(Q_{2}[t-tr]+\left|Q_{2}\right|(Q_{3}[L-l]+\left|Q_{3}\right|Q_{4}[T-t])))$$
+PDF:$$context=Q_{0}[l-tl]+Q_{1}[tl-t]+Q_{2}[t-tr]+Q_{3}[L-l]+Q_{4}[T-t]$$
 RFC:```
-RFC:context =              Q_0[l−tl] +
-RFC:          abs(Q_0) * ( Q_1[tl−t] +
-RFC:          abs(Q_1) * ( Q_2[t−tr] +
-RFC:          abs(Q_2) * ( Q_3[L−l]  +
-RFC:          abs(Q_3) *   Q_4[T−t]  )))
+RFC:context = Q_{0}[l − tl] +
+RFC:          Q_{1}[tl − t] +
+RFC:          Q_{2}[t − tr] +
+RFC:          Q_{3}[L − l]  +
+RFC:          Q_{4}[T − t]
 RFC:```
 
-If the context is smaller than 0 then -context is used and the difference between the sample and its predicted value is encoded with a flipped sign.
+If context >= 0 then `context` is used and the difference between the sample and its predicted value is encoded as is, else `-context` is used and the difference between the sample and its predicted value is encoded with a flipped sign.
 
-## Quantization
+## Quantization tables
 
-There are 5 quantization tables for the 5 sample differences, both the number of quantization steps and their distribution are stored in the bitstream. Each quantization table has exactly 256 entries, and the 8 least significant bits of the sample difference are used as index:
+For each quantization table set, there are 5 quantization tables for the 5 sample differences, both the number of quantization steps and their distribution are stored in the bitstream. Each quantization table has exactly 256 entries, and the 8 least significant bits of the sample difference are used as index:
 
-PDF:$$Q_{i}[a-b]=Table_{i}[(a-b)\&255]$$
+PDF:$$Q_{j}[k]=quant_tables[i][j][k\&255]$$
 RFC:```
-RFC:Q_{i}[a − b] = Table_{i}[(a − b)&255]
+RFC:Q_{j}[k] = quant_tables[i][j][k&255]
 RFC:```
 
+In this formula, `i` is the quantization table sets index (see below).
+
+## Quantization table sets
+
+Several quantization table sets can be used in the same bitstream.
+
+For each plane of each slice, a quantization table set is selected from an index:
+- For Y plane, `quant_table_index [ 0 ]` index is used
+- For Cb and Cr planes, `quant_table_index [ 1 ]` index is used
+- For Alpha plane, `quant_table_index [ (version <= 3 || chroma_planes) ? 2 : 1 ]` index is used
+
+Background: in first implementations of FFV1 bitstream, the index for Cb and Cr planes was stored even if it is not used (chroma_planes set to 0), this index is kept for version <= 3 on order to keep compatibility with bitstreams in the wild.
+
 ## Colorspace
 
 FFV1 supports two colorspaces: YCbCr and JPEG2000-RCT. Both colorspaces allow an optional Alpha plane that can be used to code transparency data.
@@ -924,10 +939,10 @@ Parameters( ) {                                               |
     if (version >= 3) {                                       |
         num_h_slices - 1                                      | ur
         num_v_slices - 1                                      | ur
-        quant_table_count                                     | ur
+        quant_table_set_count                                 | ur
     }                                                         |
-    for( i = 0; i < quant_table_count; i++ )                  |
-        QuantizationTable( i )                                |
+    for( i = 0; i < quant_table_set_count; i++ )              |
+        QuantizationTablePerSet( i )                          |
     if (version >= 3) {                                       |
         for( i = 0; i < quant_table_count; i++ ) {            |
             states_coded                                      | br
@@ -1061,9 +1076,9 @@ Inferred to be 1 if not present.
 `num_v_slices` indicates the number of vertical elements of the slice raster.
 Inferred to be 1 if not present.
 
-### quant_table_count
+### quant_table_set_count
 
-`quant_table_count` indicates the number of quantization table sets.
+`quant_table_set_count` indicates the number of quantization table sets.
 Inferred to be 1 if not present.
 
 ### states_coded
@@ -1105,20 +1120,20 @@ initial\_state[ i ][ j ][ k ] = ( pred + initial\_state\_delta[ i ][ j ][ k ] )
 
 ## Quantization Tables
 
-The quantization tables are stored by storing the number of equal entries -1 of the first half of the table using the method described in [Range Non Binary Values](#range-non-binary-values). The second half doesn’t need to be stored as it is identical to the first with flipped sign.
+The quantization tables are stored by storing the number of equal entries minus one of the first half of the table using the method described in [Range Non Binary Values](#range-non-binary-values). The second half doesn’t need to be stored as it is computed following the formula below.
 
 example:
 
-Table: 0 0 1 1 1 1 2 2-2-2-2-1-1-1-1 0
+Table: 0 0 1 1 1 1 2 2 -2 -2 -2 -1 -1 -1 -1 0
 
 Stored values: 1, 3, 1
 
 ```c
 function                                                      | type
 --------------------------------------------------------------|-----
-QuantizationTable( i ) {                                      |
+QuantizationTablePerSet( i ) {                                |
     scale = 1                                                 |
-    for( j = 0; j < MAX_CONTEXT_INPUTS; j++ ) {               |
+    for( j = 0; j < 5; j++ ) {                                |
         QuantizationTablePerContext( i, j, scale )            |
         scale *= 2 * len_count[ i ][ j ] - 1                  |
     }                                                         |
@@ -1126,16 +1141,14 @@ QuantizationTable( i ) {                                      |
 }                                                             |
 ```
 
-MAX\_CONTEXT\_INPUTS is 5.
-
 ```c
 function                                                      | type
 --------------------------------------------------------------|-----
 QuantizationTablePerContext(i, j, scale) {                    |
     v = 0                                                     |
     for( k = 0; k < 128; ) {                                  |
-        len - 1                                               | sr
-        for( a = 0; a < len; a++ ) {                          |
+        len_minus1                                            | ur
+        for( a = 0; a < len_minus1 + 1; a++ ) {               |
             quant_tables[ i ][ j ][ k ] = scale* v            |
             k++                                               |
         }                                                     |
@@ -1153,11 +1166,11 @@ QuantizationTablePerContext(i, j, scale) {                    |
 
 ### quant_tables
 
-`quant_tables` indicates the quantification table values.
+`quant_tables` indicates the quantification table values for quantization table set `i`.
 
 ### context_count
 
-`context_count` indicates the count of contexts.
+`context_count` indicates the count of contexts for quantization table set `i`.
 
 ### Restrictions
 
-- 
2.7.0.windows.1

---

From: Dave Rice <[email-masked]>
Date: Fri, 14 Apr 2017 13:47:47 -0400

> On Apr 14, 2017, at 10:34 AM, Jerome Martinez <[email-masked]> wrote:
> 
> I had difficulties to understand FFV1 quantization table sets, quantization tables and context, with some items not defined (e.g. abs() of a table).
> 
> - I reuse "quantization table set" name when relevant (this words were already present, I put them everywhere)
> - I added info about which quantization table set is used (or did I miss it somewhere else?)
> - "Table_" replaced by quant_tables[i][j][k] as it is already used elsewhere in the spec
> - Looks like the scale is indicated twice (in "Quantization Tables" chapter and in "context" chapter), I removed one (the one in "context" chapter)
> - "The second half doesn’t need to be stored as it is identical to the first with flipped sign." is misleading from my point of view as values are mirrored, the first value of this second half is a copy of the last value of the first half so the the first value is discarded during the "identical" process, I removed the sentence and added a reference to the pseudo code. Is it intended that it is not an exact mirror? (I have no idea about maths behind that, I just see an incoherency between text and code)
> - I changed the type of the length of "number of equal entries -1" from signed to unsigned, looks like this is unsigned in reality
> - removed MAX_CONTEXT_INPUTS as this constant is hard coded to "5" everywhere in the spec and depends of design choices about the context
> - some formatting
> 

I added a review directly on the pull request at https://github.com/FFmpeg/FFV1/pull/56/files.

[...]

Dave Rice