Codec
AV1

AV1 Specofication を読む(パース処理 2)

AV1 specification 日本語訳

算術符号化されたシンタックス要素の復号方法です。


9. パース処理

9.3 ツリーエンコードされたシンタックス要素のパース

この処理は、シンタックステーブ内のシンタックス要素のデスクリプタがTの時に呼ばれます。

この処理の入力は、シンタックス要素の名前です。

子sンタックス要素のデコードは、ツリーと確率リストに依存します。

9.3.1節で、各シンタックス要素でどのようにツリー(あるいは値)が選ばれるかを規定します。

9.3.2節で、各シンタックス要素でどのように確率が選ばれるかを規定します。

9.3.3節で、シンタックス要素が、選択されたツリーと確率に基づいてどのようにデコードされるかを規定します。

9.3.4節で、シンタックス要素値に基づいて、どのようにカウントを更新するかを規定します。

本節内の記述で変数を使用するとき、そのシンタックス要素がデコードされている時点でのシンタックステーブルで定義された値をとります。

この処理が呼ばれたとき、以下の手順を適用します。

  1. 9.3.1節で規定されるツリー選択処理を、シンタックス要素名とともに呼び出します。次の動作は戻り値に依存します。
    • 戻り値が整数ならば、シンタックス要素をその整数値とします。
    • 戻り値がツリーならば、シンタックス要素値を9.3.3節で規定されるツリーデコード処理の戻り値とします。
  2. 9.3.4節で規定されるシンタックス用とカウント処理を、シンタックス要素名とともに呼び出します。

9.3.1 ツリー選択処理

この処理の入力は、シンタックス要素名です。

この処理の出力は、ツリー(整数の配列で表現)あるいは、シンタックス要素値を与える1つの整数値です(この場合、シンタックス要素はビットを読まずに決定できます)。

以下のように、ツリーをシンタックス要素に基づいて選択します。

partition

ツリーは hasRows, halCols に依存し明日。

  • hasRows==1 && hasCols==1 ならば、ツリーは paritiion_tree
  • else halCols==1 ならば、ツリーは cols_partition_tree
  • else hasRow==1 ならば、ツリーは rows_partition_tree
  • else return PARTITION_SPLIT
partition_tree[6] =
{
    -PARTITION_NONE, 2, -PARTITION_HORZ, 4, -PARTITION_VERT, -PARTITION_SPLIT
}
cols_partition_tree[2] =
{
    -PARTITION_HORZ, -PARTITION_SPLIT

}
cols_partition_tree[2] =
{
    -PARTITION_VERT, -PARTITION_SPLIT

}

default_intramode, default_uv_mode, intra_mode, sub_intra_mode, uvMode

intra_mode_tree[18] =
{
    -DC_PRED, 2, -TM_PRED, 4, -V_PRED, 6, 8, 12,
    -H_PRE, 10, -D135_PRED, -D117_PRED, -D45_PRED, 14,
    -D63_PRED, 16, -D153_PRED, -D207_PRED
}

segment_id

segment_tree [14] =
{
    2, 4, 6 ,8, 10, 12, 0, -1, -2, -3, -4, -5, -6, -7
}

skip, seg_id_predicted, is_inter, comp_mode, comp_ref, single_ref_p1, single_ref_p2, mv_sign, mv_bit, mv_class0_bit, core_coefs

bnary_tree[2] =
{
    0, -1
}

注意:
これらのシンタックス要素は、ストリームから直接 read_bool を使って読み込むとも言えます。
確率の計算処理がとても複雑で、シンタックステーブル内で簡単に表現できるので、ツリー構造を使って表現しています。

tx_size

  • maxTxSIze==TX_32X32 ならば、ツリーは tx_size_32_tree
  • else maxTxSize==TX_16X16 ならば、ツリーは tx_size_16_tree
  • else ツリーは tx_size8_tree
tx_size_32_tree[6] =
{
    -TX_4X4, 2,
    -TX_8X8, 5,
    -TX_16X16, -TX_32X32    
}
tx_size_16_tree[4] =
{
    -TX_4X4, 2,
    -TX_8X8, -TX_16X16
}
tx_size_8_tree[2] =
{
    -TX_4X4, -TX_8X8
}

inter_mode

inter_mode_tree[6] =
{
    -(ZEROMV - NEARESTV), 2,
    -(NEARESTMV - NEARESTMV), 5,
    -(NEARMV - NEARESTMV). -(NEWMV - NEARESTMV)
}

interp_filter

interp_filter_tree[4] =
{
    -EIGHTTAP, 2,
    -EIGHTTAP_SMOOTH, -EIGHTTAP_SHARP
}

mv_joint

mv_joint_ress[6] =
{
    -MV_JOINT_ZERO, 2,
    -MV_JOINT_HNZVZ, 4,
    -MV_JOINT_HZVNZ, -MV_JOINT_HNZVNZ
}

mv_class

mv_class_tree[20] =
{
    -MV_CLASS_0, 2,
    -MV_CLASS_1, 4,
    6, 8,
    -MV_CLASS_2, -MV_CLASS_3,
    10, 12,
    -MV_CLASS_4, -MV_CLASS_5,
    -MV_CLASS_6, 14,
    16, 18,
    -MV_CLASS_7, -MV_CLASS_8,
    -MV_CLASS_9, -MV_CLASS_10
}

mv_class0, mv_fr

mv_fr_tree[6] =
{
    -0, 2,
    -1, 4,
    -2, -3  
}

mv_class0_hp, mv_hp

ツリーは、allow_high_precision_mv に依存します。

  • allow_high_precision_mv==1 ならば、ツリーは binary_tree
  • そうでなければ、戻り値は 1

token

token_tree[20] =
{
    -ZERO_TOKEN, 2,
    -ONE_TOKEN, 4,
    6, 10,
    -TWO_TOKEN, 8,
    -THREE_TOKEN, -FOUR_TOKEN,
    12, 14,
    -DCT_VAL_CATEGORY_1, -DCT_VAL_CATEGORY_2,
    16, 18,
    -DCT_VAL_CATEGORY_3, -DCT_VAL_CATEGORY_4,
    -DCT_VAL_CATEGORY_5, -DCT_VAL_CATEGORY_6
}

9.3.2 確率選択処理

この処理の入力は以下の通りです。

  • シンタックス要素名
  • どの確率を要求するかの変数 node

この処理の出力は、確率(1..255の整数値で、2値が0である確率)です。

シンタックス要素に依存する確率は以下の通りです。

partition

変数 node2 を以下のように求めます。

  • hasRows==1 && halCols==1 ならば、node2 = node
  • else hasCols==1 ならば、node2 = 1
  • else node2 = 2

確率は、FrameIsIntra に依存します。

  • FrameIsIntra==0 ならば、確率は kf_partitionProbs[ctx][node2] で与えられます。
  • そうではなければ、確率は partitionProbs[ctx][node2] で与えられます。

ここで、ctx は以下のように計算します。

above   = 0
left    = 0
bsl     = mi_width_log2_lookup[bSize]
boffset = mi_width_log2_lookup[BLOCK_64X64] - bsl

for (i=0; i<num8x8; i++)
{
    above |= AbovePartitionContext[c + i]
    left  |= LeftpartitionContext[r + i]
}

above = (above & (1 << boffset)) > 0
left  = (left  & (1 << boffset)) > 0

ctx  = bsl * 4 + left * 2 + above

default_intra_mode

確率は kfYModeProbs[abovemode][leftmode][node] で与えられます。
ここで、abovemode, leftmode はこのブロックの上と左のイントラモードです。

if (MiSize >= BLOCK_8X8)
{
    abovemode = AvailU ? SubModes[MiRow-1][MiCol  ][2] : DC_PRED
    leftMmode = AvailL ? SubModes[MiRow  ][MiCol-1][1] : DC_PRED
}
else
{
    if (idy)
        abovemode = sub_modes[idx]
    else
        abovemode = AvaliU ? SubModes[MiRow-1][MiCol][2+idx] : DC_PRED

    if (idx)
        leftmode = sub_modes[idy*2]
    else
        leftmode = AvailL ? SubModes[MiRow  ][MiCol-1][1+idy*2] : DC_PRED
}

注意:
わかりやすさのために、SubMdesに2次元配列を使っています。
各8x8縦横位置のイントラモードだけを格納する(つまり、2つの1次元配列を使う)ことで、メモリ消費を減らすことができます。

defualt_uv_mode

kf_uvMode_probs[yMode][node]

intra_mode

yMode_probs[ctx][node]

ctx = size_group_loopkup[MiSize]

sub_intra_mode

yMode_probs[ctx][node], ctx=0

uvMode

uvModeProbs[ctx][node], ctx=yMode

segment_id

SegmentationTreeProbs[node]

skip

skipProb[ctx]

ctx = 0
if (AvailU) ctx += Skips[MiRow-1][MiCol  ]
if (AvallL) ctx += Skips[MiRow  ][MiCol-1]

seg_id_predicted

SegmentationPredProbs[ctx]

ctx = LeftSegPredContext[MiRow] + AboveSegPredContext[MiCol]

is_inter

isInterProb[ctx]

if (AvilU && AvailL)
    ctx = (LeftIntra && AboveIntra) ? 3 : LeftIntra || AboveIntra
else if (AvailU || AvailL)
    ctx = 2 * (AvailU ? AboveIntra : LeftIntra)
else
    ctx = 0

comp_mode

compModePorob[ctx]

if (AvilU && AvailL)
{
    if (AboveSIngle && LeftSingle)
        ctx = (AboveRefRrame[0] == CompFixedRef) ^ (LeftRefFrame[0] == CompFixedRef)
    else if (AboveSingle)
        ctx = 2 + (AboveRefFrame[0] == CompFixedRef || AboveIntra)
    else if (LeftSingle)
        ctx = 2 + (LeftRefFrame[0] == CompFixedRef || leftIntra)
    else
        ctx = 3
}
else if (AvailU)
{
    if (AboveSingle)
        ctx = AboveRefFrame[0] == CompFxedRef   
    else
        ctx = 3
}
else if (AvailL)
{
    if (LeftSingle)
        ctx = LeftRefFrame[0] == CompFxedRef    
    else
        ctx = 3
}
else
{
    ctx = 1
}

comp_ref

compRefProb[ctx]

ctx = ...

single_ref_p1

singleRefProb[ctx][0]

ctx = ...

single_ref_p2

singleRefProb[ctx][1]

ctx = ...

mv_ign

mvSignProb[comp]

mv_bit

mvBitsProb[comp][i]

mv_class0_bit

mvClass0BitProb[comp]

tx_size

tx_probs[maxTxSze][ctx][node]

above = maxTxSize
left  = maxTxSize

if (AvailU && !Skips[MiRow-1][MiCol  ]) above = TxSizes[MiRow-1][MiCol  ]
if (AvailL && !Skips[MiRow  ][MiCol-1]) left  = TxSizes[MiRow  ][MiCol-1]
if (!AvailL) left  = above
if (!AvailU) above = left

ctx = (above + left) > maxTxSize

inter_mode

interModeProbs[ctx][node]

ctx = ModeContext[refFrame[0]]

interp_filter

interpFilterProbs[ctx][node]

leftInterp  = (AvailL && LeftRefFrame[0 ] > INTRA_FRAME) ? InterpFilters[MiRow][MiCol-1] : 3
aboveInterp = (AvailU && AboveRefFrame[0] > INTRA_FRAME) ? InterpFilters[MiRow-1][MiCol] : 3

if (leftInterp == AboveInterp)                ctx = leftInterp
else if (leftInterp == 3 && aboveInterp != 3) ctx = aboveInterp
else if (leftInterp != 3 && aboveInterp == 3) ctx = leftInterp
ekse                                          ctx = 3

mv_joint

mvJointProvbs[node]

mv_class

mvClssProbs[comp]

mv_class0_fr

mvClass0FrProbs[comp][mvclass0_bit][node]

mvclass0_hp

mvClass0HpProbs[comp]

mv_fr

mvFrProbs[comp][node]

mv_hp

mvHpProbs[comp]

mode_coefs

coef_probs[txSz][plane>0][is_inter][band][ctx][0]

if (c==0)
{
    sx = plane > 0 ? subsampling_x : 0
    sy = plane > 0 ? subsampling_y : 0
    maxX = (2 * MiCols) >> sx
    maxY = (2 * MiRows) >> sy
    numpts = 1 << txSz
    x = startX >> 2
    y = startY >> 2
    above = 0
    left = 0

    for (i=0; i<numpts; i++)
    {
        if (x4+i < maxX) above |= AboveNonzeroContext[plane][x4+i]
        if (y4+i < maxY) left  |= LeftNonzeroContext[plane][u4+i]
    }
    ctx = above + left
}
else
{
    ctx = ( + TokenCache[nb[0]] + TokenCache[nb[1]]) >> 1
}

各係数の隣接は以下のように計算します。

if (c==0)
{
    nb[0] = 0
    nb[1] = 0
}
else
{
    n = 4 << txSz
    i = pos / n
    j = pos % n
    if (i>0 && j>0)
    {
        a  = (i-1) * n + j
        a2 = i * n + j - 1
        if (TxType == DCT_ADST)
        {
            nb[0] = a
            nb[1] = a
        }
        else if (TxType == ADST_DCT)
        {
            nb[0] = a2
            nb[1] = a2
        }
        else
        {
            nb[0] = a
            nb[1] = a2
        }
    }
    else if (i>0)
    {
        nb[0] = (i-1) * n + j
        nb[1] = (i-1) * n + j
    }
    else
    {
        nb[0] = i * n + j - 1
        nb[1] = i * n + j - 1
    }
}

token

ctxは、more_coefsと同じ方法で計算します。
確率は pareto(node, coef_probex[txSz][plane>0][is_inter][band][ctx][Min(2,1+node)]) です。

pareto(node, prob)
{
    if (node < 2)
    {
        return prob
    }
    x = (prob - 1) / 2
    if (prob & 1)
    {
        return pareto_table[x][node-2]
    }
    else
    {
        return (pareto_table[x][node-2] + pareto_table[x+1][node-2]) >> 1
    }
}

ここで、定数テーブルpareto_tableは10.3節で定義します。

9.3.3 ツリーデコード処理

この処理の入力は以下の通りです。

  • 整数配列で表現されたツリー T
  • シンタックス要素名

この処理の出力は、デコードされた値です。

出力値は以下のように求めます。

do
{
    n = T[n + read_bool( P(n>>1) )]
} while (n>0)

関数 P(x) は 9.3.2節で定義される確率選択処理で定義され、入力はシンタックス要素名と入力変数node=xです。

出力値は -n です。

9.3.4 シンタックス要素カウント処理

この処理の入力は以下の通りです。

  • シンタックス要素名
  • シンタックス要素値

シンタックス要素をデコードするために使う確率を計算するとき、9.3.2節で規定される確率選択処理で定義された陰々胃の変数をアクセスします。

各シンタックス要素のためのアクションは、なにもしないか、配列要素に1カウントするかです。

more_coefsについての特殊な場合については、本節の最後に説明します。

以下の表は、どの名称の時度の要素をカウントするかを定義します。
表内の変数syntaxは、そのシンタックス要素の値です。
更新項目が "NA" ならば、そのシンタックス要素ではカウントしません。

シンタックス要素名 インクリメントする変数
partition counts_partition[ctx][syntax]
default_intra_mode NA
default_uv_mode NA
intra_mode counts_intra_mode[ctx][syntax]
sub_intra_mode counts_intra_mode[ctx][syntax]
uv_mode counts_uv_mode[ctx][syntax]
segment_id NA
Skip counts_skip[ctx][syntax]
seg_id_predicted NA
is_inter counts_is_inter[ctx][syntax]
comp_mode counts_comp_mode[ctx][syntax]
comp_ref counts_comp_ref[ctx][syntax]
single_ref_p1 counts_single_ref[ctx][0][syntax]
single_ref_p2 counts_single_ref[ctx][1][syntax]
mv_sign counts_mv_sign[comp][syntax]
mv_class0_bit counts_mv_class0_bit[comp][syntax]
mv_bit counts_mv_bits[comp][i][syntax]
tx_size counts_tx_size[maxTxSize][ctx][syntax]
inter_mode counts_inter_mode[ctx][syntax]
interp_filter counts_interp_filter[ctx][syntax]
mv_joint counts_mv_joint[syntax]
mv_class counts_mv_class[comp][syntax]
mv_class0_fr counts_mv_class0_fr[comp][ mv_class0_bit][syntax]
mv_class0_hp counts_mv_class0_hp[comp][syntax]
mv_fr counts_mv_fr[comp][syntax]
mv_hp counts_mv_hp[comp][syntax]
token counts_token[txSz][plane>0][is_inter][band][ctx][Min(2,syntax)]
more_coefs counts_more_coefs[txSz][plane>0][is_inter][band][ctx][syntax]
segment_id counts_segment_id[syntax]
seg_id_predicted counts_seg_id_predicted[ctx][syntax]
segment_id (when seg_id_predicted = 0) counts_seg_id_mispredicted[syntax]