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

```C++
partition_tree[6] =
{
	-PARTITION_NONE, 2, -PARTITION_HORZ, 4, -PARTITION_VERT, -PARTITION_SPLIT
}
```

 
```C++
cols_partition_tree[2] =
{
	-PARTITION_HORZ, -PARTITION_SPLIT

}
```

```C++
cols_partition_tree[2] =
{
	-PARTITION_VERT, -PARTITION_SPLIT

}
```

####default_intramode, default_uv_mode, intra_mode, sub_intra_mode, uvMode

```C++
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

```C++
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

```C++
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

```C++
tx_size_32_tree[6] =
{
	-TX_4X4, 2,
	-TX_8X8, 5,
	-TX_16X16, -TX_32X32	
}
```

```C++
tx_size_16_tree[4] =
{
	-TX_4X4, 2,
	-TX_8X8, -TX_16X16
}
```

```C++
tx_size_8_tree[2] =
{
	-TX_4X4, -TX_8X8
}
```

####inter_mode

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

####interp_filter

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

####mv_joint

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

####mv_class

```C++
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

```C++
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

```C++
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 は以下のように計算します。


```C++
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 はこのブロックの上と左のイントラモードです。

```C++
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]


```C++
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]

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

####seg_id_predicted

SegmentationPredProbs[ctx]

```C++
ctx = LeftSegPredContext[MiRow] + AboveSegPredContext[MiCol]
```

####is_inter

isInterProb[ctx]

```C++
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]

```C++
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]

```C++
ctx = ...
```

####single_ref_p1

singleRefProb[ctx][0]

```C++
ctx = ...
```

####single_ref_p2

singleRefProb[ctx][1]

```C++
ctx = ...
```

####mv_ign

mvSignProb[comp]

####mv_bit

mvBitsProb[comp][i]

####mv_class0_bit

mvClass0BitProb[comp]

####tx_size

tx_probs[maxTxSze][ctx][node]

```C++
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]

```C++
ctx = ModeContext[refFrame[0]]
```

#### interp_filter

interpFilterProbs[ctx][node]

```C++
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]

```C++
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
}
```

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


```C++
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)]) です。

```C++
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
 * シンタックス要素名

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

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

```C++
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] |